階層レイアウト設計装置、階層レイアウト設計方法およびプログラム
【課題】複数の下位階層ブロックに跨るセル同士を各下位階層ブロックに設けた端子を経由して相互に接続する場合に、セル間を結ぶ経路が迂回経路となること。
【解決手段】階層レイアウト設計装置は、第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する出力端子配置部と、第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する入力端子配置部と、を備えている。
【解決手段】階層レイアウト設計装置は、第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する出力端子配置部と、第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する入力端子配置部と、を備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路（ＬＳＩ）の階層レイアウト設計装置、階層レイアウト設計方法およびプログラムに関し、特に、下位階層ブロック毎に分割して配置配線を行うとともに、下位階層ブロック同士を接続するための端子の配置を決定する階層レイアウト設計装置、階層レイアウト設計方法およびプログラムに関する。
【背景技術】
【０００２】
半導体集積回路（ＬＳＩ）を設計する際に、回路全体のレイアウト設計を一括して行うと、データ量が膨大となり、困難を伴う。そこで、半導体集積回路を複数の下位階層ブロックに分割し、下位階層レイアウトごとにレイアウト設計を行う階層レイアウト設計が主流となっている。
【０００３】
階層レイアウト設計において、各下位階層ブロック間の配線を上位階層で結線するために、各下位階層ブロックに下位階層ブロック端子（以下、単に「端子」という。）が生成される。上位階層でのタイミング収束性および回路収容性を向上させるには、下位階層ブロックにおいて、端子を好適な位置に配置する必要がある。近年の回路動作速度の高速化に伴い、上位階層でのタイミングが非常に厳しくなっており、下位階層ブロックにおいて、端子を好適な位置に配置する重要性が増している。
【０００４】
例えば、特許文献１に、階層設計レイアウトにおいて、端子を最適な位置に配置する階層設計レイアウト方法が記載されている。
【０００５】
図１５は、特許文献１に記載された階層設計レイアウト処理手順を示すフローチャートである。ここでは、図１５のステップＳ５０９に示した最適化処理手順について詳細に説明する。図１６は、ステップＳ５０９に示した最適化処理手順を示すフローチャートである。
【０００６】
図１７は、図１５のステップＳ５０８に示した端子位置仮決定処理後におけるレイアウト情報の一例を示す説明図である。図１７において、レイアウト情報２１３は、チップ４００上にフロアプランされた下位階層ブロック４０１〜４０３が仮配置された情報である。下位階層ブロック４０１、４０３内の黒塗り矩形はセルをあらわしている。ここで、下位階層ブロック４０１が一方の下位階層ブロックに該当し、下位階層ブロック４０３が他方の下位階層ブロックに該当する。
【０００７】
レイアウト情報２１３では、下位階層ブロック４０１内のセル４１１から下位階層ブロック４０３内のセル４３１までセル間仮配線経路Ｒ１が仮配線されている。セル間仮配線経路Ｒ１は、配線禁止領域に設定された下位階層ブロック４０２を迂回して引かれている。
【０００８】
また、下位階層ブロック４０１の境界を表すバウンダリ４１２とセル間仮配線経路Ｒ１との交点が端子４１０の端子位置となる。以降、端子位置Ｘと称す。同様に、下位階層ブロック４０３の境界を表すバウンダリ４３２とセル間仮配線経路Ｒ１との交点が端子４３０の端子位置となる。以降、端子位置Ｙと称す。
【０００９】
また、ステップＳ５０９に示した最適化処理は仮決定された端子位置Ｘ、Ｙを最適化する。具体的には、仮配線経路検出部と、第１の仮配線経路上ポイント検出部と、第１のバウンダリポイント検出部と、第２の仮配線経路上ポイント検出部と、第２のバウンダリポイント検出部と、端子位置決定部と、から構成されている。
【００１０】
まず、仮配線経路検出部により、未処理のセル間仮配線経路があるか否かを判断し（ステップＳ５２１）、未処理のセル間仮配線経路がある場合（ステップＳ５２１：Ｙｅｓ）、第１の仮配線経路上ポイント検出部により、一方の端子を基準端子に決定する（ステップＳ５２２）。図１７に示したレイアウト情報では、セル間仮配線経路Ｒ１から端子位置Ｘと端子位置Ｙとの間の仮配線経路Ｒ２を検出し、一方の端子４１０を基準端子に決定する。
【００１１】
次に、仮配線経路上において、第１の仮配線経路上ポイント検出処理、すなわち他方の下位階層ブロックから所定距離以内で、かつ一方の端子からの配線長が最短となる第１の仮配線上ポイントを検出する（ステップＳ５２３）。そして、第１のバウンダリポイント検出部により、第１のバウンダリポイントを検出する（ステップＳ５２４）。
【００１２】
図１８は、第１の仮配線経路上ポイント検出処理を示す説明図である。図１８において、まず、仮配線経路Ｒ２上において、一方の端子４１０を基準とした場合、他方の端子４３０を有する他方の下位階層ブロック４０３から所定距離ｄ１以内の経路Ｒ３を検出する。そして、この経路Ｒ３中、一方の端子４１０からの配線長が最短となる点Ｐａを、第１の仮配線上ポイントとして検出する。そして、第１の仮配線経路上ポイントＰａから他方の下位階層ブロック４０３のバウンダリ４３２までの距離が最短となるバウンダリ４３２上の点Ｐｂを第１のバウンダリポイントとして検出する。
【００１３】
次に、第２の仮配線経路上ポイント検出部により、第２の仮配線経路上ポイント検出処理、すなわち仮配線経路上において、一方の下位階層ブロックから所定距離以内で、かつ第１の仮配線経路上ポイントからの配線長が最短となる第２の仮配線経路上ポイントを検出する（ステップＳ５２５）。そして、第２のバウンダリポイント検出部により、第２のバウンダリポイントを検出する（ステップＳ５２６）。
【００１４】
図１９は、第２の仮配線経路上ポイント検出処理を示す説明図である。図１９において、仮配線経路Ｒ２上で、一方の下位階層ブロック４０１から所定距離ｄ２以内の経路Ｒ４を検出する。そして、この経路Ｒ４中、第１の仮配線経路上ポイントＰａからの配線長が最短となる点Ｐｃを、第２の仮配線経路上ポイントとして検出する。そして、第２の仮配線経路上ポイントＰｃから一方の下位階層ブロック４０１のバウンダリ４１２までの距離が最短となるバウンダリ４１２上の点Ｐｄを第２のバウンダリポイントとして検出する。
【００１５】
次に、端子位置決定部により、第１および第２のバウンダリポイントを端子アサイン候補に決定し（ステップＳ５２７）、第１および第２のバウンダリポイントに端子を配置することがデザインルールを遵守するか否かを判断する（ステップＳ５２８）。デザインルール違反となると判断された場合（ステップＳ５２８：Ｎｏ）、ステップＳ５２２に戻る。一方、デザインルールを遵守すると判断された場合（ステップＳ５２８：Ｙｅｓ）、第１および第２のバウンダリポイントを新たな端子位置に決定する（ステップＳ５２９）。
【００１６】
図２０は、端子位置決定処理結果を示す説明図である。図２０において、第２のバウンダリポイントＰｄが一方の端子４１０の新たな端子位置に決定されている。第１のバウンダリポイントＰｂが他方の端子４３０の新たな端子位置に決定されている。
【００１７】
そして、ステップＳ５２１に戻る。また、ステップＳ５２１において、未処理のセル間仮配線経路が検出されなかった場合（ステップＳ５２１：Ｎｏ）、図１５に示したステップＳ５１０に移行する。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００８−００９７８７号公報（図４−１〜４−４、図５−１、５−２）
【発明の概要】
【発明が解決しようとする課題】
【００１９】
以下の分析は、本発明者によってなされたものである。
【００２０】
特許文献１に記載された技術によると、複数の下位階層ブロックを接続する際、迂回経路の発生を抑制できない場合が生じうるという問題がある。
【００２１】
その理由は、上位階層の配置配線時に下位階層ブロックのタイミング劣化の発生を抑止するため、端子を下位階層ブロックの境界を表すバウンダリ上に配置するからである。特許文献１に記載された技術によると、例えば、ある下位階層ブロックから２つの下位階層ブロックへの接続があり、これらの２つの接続が最初の下位階層ブロックを基準として座標上で反対側に配置されている場合に、これらの２つの接続のうちの一方を最短にできても、他方については迂回配線経路の発生を抑制できない場合がある。
【００２２】
図２１は、複数の下位階層ブロックが接続されている場合に、特許文献１に記載された技術により、端子の位置を決定した結果を示す図である。
【００２３】
図２１を参照すると、下位階層ブロック４０１は、下位階層ブロック４０３と接続されている。同時に、下位階層ブロック４０１は、下位階層ブロック４０１に対して、Ｘ（水平方向）座標に関して、下位階層ブロック４０３と反対側に位置する下位階層ブロック４０４と接続されている。
【００２４】
下位階層ブロック４０１から下位階層ブロック４０３への接続は配線禁止領域を跨いでいない。したがって、ステップＳ５０９に示した最適化処理によって、下位階層ブロック端子は下位階層ブロック４０１と下位階層ブロック４０３を最短で接続するために、端子４１０の位置と端子４３０の位置に配置されると考えられる。このとき、配線経路は、配線経路Ｌのように最短の経路となる。
【００２５】
特許文献１に記載された技術では複数の下位階層ブロックが同一信号で接続される場合が定義されていない。したがって、下位階層ブロック４０１から下位階層ブロック４０４への接続に関しては、図２１に示すように、下位階層ブロック４０１が配線禁止領域に設定されていない場合に、端子の位置は、既に決定されていた端子４１０の位置にそのまま決定されると考えられる。このとき、端子４１０から下位階層ブロック４０１を通過し、下位階層ブロック４０４へ接続することで、端子４４０の位置が決定される。端子が多数存在する場合には、これらの端子のＹ（垂直方向）座標と、端子４１０のＹ座標とが、大きく隔たるように配置される。
【００２６】
一般に、下位階層ブロック端子は、ネットリストの物理構造に従って生成される。下位階層ブロック４０１から下位階層ブロック４０３および４０４へ同一の信号が接続されている場合に、下位階層ブロック４０１を基準として下位階層ブロック４０３と下位階層ブロック４０４とが座標上で反対側に配置されていると、他の下位階層ブロックと接続するセルの多さに起因して、複数の端子を容易に生成することができず、下位階層ブロック４０１から下位階層ブロック４０４への配線がＬ１のような迂回配線経路となる。したがって、タイミング収束性が悪化したり、迂回配線経路により無駄な配線リソースを消費することで収容性が悪化したりして、設計品質が低下し、手戻りによる設計期間の増加を招く。
【００２７】
そこで、複数の下位階層ブロックに跨るセル同士を各下位階層ブロックに設けた端子を経由して相互に接続する場合に、セル間を結ぶ経路が迂回経路となることを防ぐことが課題となる。
【課題を解決するための手段】
【００２８】
本発明の第１の視点に係る階層レイアウト設計装置は、
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する出力端子配置部と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する入力端子配置部と、を備えている。
【００２９】
本発明の第２の視点に係る階層レイアウト設計方法は、
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する工程と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する工程と、を含む。
【００３０】
本発明の第３の視点に係るプログラムは、
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する処理と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する処理と、をコンピュータに実行させる。
【発明の効果】
【００３１】
本発明に係る階層レイアウト設計装置、階層レイアウト設計方法およびプログラムによると、複数の下位階層ブロックに跨るセル同士を各下位階層ブロックに設けた端子を経由して相互に接続する場合に、セル間を結ぶ経路が迂回経路となることを防ぐことができる。
【図面の簡単な説明】
【００３２】
【図１】本発明に係る階層レイアウト設計装置の構成を概略的に示すブロック図である。
【図２】実施形態に係る階層レイアウト設計方法の処理手順を示すフローチャートである。
【図３】実施形態に係る階層レイアウト設計方法における下位階層端子位置決定手順を示すフローチャートである。
【図４】実施形態に係る階層レイアウト設計方法におけるフロアプラン処理（図２のステップＳ１１２）の結果について説明するための図である。
【図５】実施形態に係る階層レイアウト設計方法における仮配置配線処理（図２のステップＳ１１３）の結果について説明するための図である。
【図６】実施形態に係る階層レイアウト設計方法における端子位置決定処理（図２のステップＳ１１４）の結果について説明するための図である。
【図７】実施形態に係る階層レイアウト設計方法における上位階層配置配線処理（図２のステップＳ１１５）の結果について説明するための図である。
【図８】実施形態に係る階層レイアウト設計方法における各下位階層の配置配線処理（図２のステップＳ１１７）について説明するための図である。
【図９】実施形態に係る階層レイアウト設計方法における階層レイアウトの結果について説明するための図である。
【図１０】実施形態に係る階層レイアウト設計方法における下位階層ブロック内の迂回配線経路について説明するための図である。
【図１１】実施形態に係る階層レイアウト設計方法における下位階層ブロック内の迂回配線抑制方法について説明するための図である。
【図１２】実施形態に係る階層レイアウト設計方法における入力端子の移動（図３のステップＳ２１５）について説明するための図である。
【図１３】実施形態に係る階層レイアウト設計方法における入力端子の移動（図３のステップＳ２１７）について説明するための図である。
【図１４】実施形態に係る階層レイアウト設計方法を実現するためのシステム構成を示すブロック図である。
【図１５】特許文献１に記載された階層設計レイアウト処理手順を示すフローチャートである。
【図１６】特許文献１に記載された最適化手順を示すフローチャートである。
【図１７】特許文献１に記載された仮決定処理後におけるレイアウト情報を一例として示す図である。
【図１８】特許文献１に記載された第１の仮配線経路上ポイント検出処理について説明するための図である。
【図１９】特許文献１に記載された第２の仮配線経路上ポイント検出処理について説明するための図である。
【図２０】特許文献１に記載された端子位置決定部による決定処理結果について説明するための図である。
【図２１】特許文献１に記載された端子位置決定処理の結果について説明するための図である。
【発明を実施するための形態】
【００３３】
はじめに、本発明の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００３４】
図１は、本発明に係る階層レイアウト設計装置の構成を概略的に示すブロック図である。図１および図１１を参照すると、階層レイアウト設計装置は、第１の下位階層ブロック（１０１）に含まれるセル（１１１）から出力された信号を受信する出力端子（２１）をセル（１１１）の近傍に配置する出力端子配置部（３１）と、第２の下位階層ブロック（１０２）に含まれる複数のセル（１２１，１３１）へ出力端子（２１）から出力された信号を供給する入力端子（２２）を、複数のセル（１２１，１３１）を囲む最小の矩形領域（Ｓ）の境界上であって、出力端子（２１）が配置された箇所からの距離が最短の箇所に配置する入力端子配置部（３２）と、を備えている。
【００３５】
また、図１２を参照すると、入力端子配置部（３２）は、入力端子（２２）が第２の下位階層ブロック（１０２）の領域外に配置された場合には、第２の下位階層ブロック（１０２）の領域内であって入力端子（２２）の配置箇所からの距離が最短の箇所（２２０）へ、入力端子（２２）を移動することが好ましい。
【００３６】
一方、図１３を参照すると、入力端子配置部（３２）は、入力端子（２２）が配線禁止領域（ＢＲ）に配置された場合には、配線禁止領域（ＢＲ）外であって入力端子（２２）の配置箇所からの距離が最短の箇所（２２０）へ、入力端子を移動することが好ましい。
【００３７】
また、階層レイアウト設計装置は、出力端子（２１）を配置した領域を第１の下位階層ブロック（１０１）に配線禁止領域として設定するとともに、入力端子（２２）を配置した領域を第２の下位階層ブロック（１０２）に配線禁止領域として設定する第１の配線禁止領域設定部（３３）を備えていることが好ましい。
【００３８】
さらに、図示しないが、出力端子配置部（３１）は、出力端子（２１）が配線禁止領域に配置された場合には、配線禁止領域外であって出力端子（２１）の配置箇所からの距離が最短の箇所へ、出力端子（２１）を移動することが好ましい。
【００３９】
また、図７および図８を参照すると、階層レイアウト装置は、第１の下位階層ブロック（１０１）に配置された出力端子（２１）と、第２の下位階層ブロック（１０３，１０４）に設けられた入力端子（２３，２４）との間を配線する上位階層配線部（３５）と、配線に用いられた領域を第１の下位階層ブロック（１０１）および第２の下位階層ブロック（１０３，１０４）に配線禁止領域（ＢＲ）として設定する第２の配線禁止領域設定部（３６）と、第２の配線禁止領域設定部（３６）により設定された配線禁止領域を回避しつつ、第１の下位階層ブロック（１０１）および第２の下位階層ブロック（１０３，１０４）における配線を実施する下位階層配線部（３７）と、を備えていることが好ましい。
【００４０】
本発明に係る階層レイアウト設計装置によると、複数の下位階層ブロックに跨るセル同士を各下位階層ブロックに設けた端子を経由して相互に接続する場合に、セル間を結ぶ経路が迂回経路となることを防ぐことができる。
【００４１】
また、本発明は、半導体集積回路のレイアウト設計方法に関し、特に、下位階層ブロック毎に分割して配置配線を行うために下位階層ブロック端子の位置決定処理を行う階層レイアウト設計方法に関する。
【００４２】
図２を参照すると、階層レイアウト設計方法は、下位階層ブロック端子を下位階層ブロック領域内に配置する工程（Ｓ１１４）と、上位階層の配置配線を下位階層ブロックの配置配線より先に実施する工程（Ｓ１１５、Ｓ１１７）と、下位階層ブロック領域上に位置する上位階層の配置配線情報を下位階層ブロック内に配置配線禁止領域として設定する工程（Ｓ１１６）とを含むことが好ましい。
【００４３】
また、図３を参照すると、下位階層ブロック端子を下位階層ブロック領域内に配置する工程（Ｓ１１４）は、さらに、下位階層ブロックの出力端子位置を下位階層ブロックの出力端子を駆動する下位階層ブロック領域内のセルの近傍に仮配置する工程（Ｓ２１２）と、下位階層ブロックの入力端子位置を下位階層ブロックの入力端子に接続される下位階層ブロック領域内のセルを囲む矩形領域の枠上で、かつ、前記セルに接続する他の階層（他の下位階層または上位階層）に属するセルの配置位置との距離が最も短い座標に仮配置する工程（Ｓ２１３）と、仮配置した入力端子が各々の下位階層ブロック領域外となった場合に（Ｓ２１４のＹｅｓ）、下位階層ブロック領域内のうち、仮配置した位置からの距離が最も短い座標に移動する工程（Ｓ２１５）と、仮配置した入力端子および出力端子の座標が配線禁止領域内に存在する場合に（Ｓ２１６のＹｅｓ）、各々の下位階層ブロック領域内における配線禁止領域外に移動する工程（Ｓ２１７）と、仮配置した入力端子および出力端子の配置位置を決定する工程（Ｓ２１８）と、配置位置が決定された下位階層ブロックの入力端子および出力端子の領域を配線禁止領域に設定する工程（Ｓ２１９）と、を含むことが好ましい。
【００４４】
本発明によると、下位階層ブロック間を下位階層ブロック領域内を通過させて短距離の配線経路で接続することができ、複数の下位階層ブロックが接続される場合にも、迂回配線経路の発生を抑制することができる。
【００４５】
（実施形態）
実施形態に係る階層レイアウト設計方法について、図面を参照して説明する。本実施形態に係る階層レイアウト設計方法は、図１４に示されるようなコンピュータを用いた設計システム上において実現することができる。
【００４６】
設計システムは、一例として、ＣＡＤ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ）装置として構成することができる。図１４を参照すると、ＣＡＤ装置は、中央処理装置（以下、ＣＰＵという）１、メモリ２、記憶装置３、表示装置４、入力装置５、および、ドライブ装置６を備え、これらはバス７を介して相互に接続されている。
【００４７】
ＣＰＵ１は、メモリ２を利用してプログラムを実行し、各種処理を実施する。メモリ２には、各種処理を提供するために必要なプログラムとデータが格納される。メモリ２は、キャッシュ・メモリ、システム・メモリおよびディスプレイ・メモリを含んでいてもよい。
【００４８】
表示装置４は、レイアウト表示、パラメータ入力画面等の表示に用いられる。表示装置４として、ＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）、ＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）、ＰＤＰ（Ｐｌａｓｍａ Ｄｉｓｐｌａｙ Ｐａｎｅｌ）等を用いることができる。入力装置５は、ユーザからの要求や指示、パラメータの入力に用いられる。入力装置５として、キーボードおよびマウス（非図示）等が用いられる。記憶装置３として、磁気ディスク装置、光ディスク装置または光磁気ディスク装置を用いることができる。記憶装置３には、後述する自動配線配置処理などの半導体装置設計処理のためのプログラムデータとファイルが格納される。ＣＰＵ１は、入力装置５による指示に応答して、プログラムおよびデータをメモリ２へ転送して実行する。
【００４９】
ＣＰＵ１が実行するプログラムデータは、記録媒体８により提供される。ドライブ装置６は、記録媒体８を駆動し、その記憶内容にアクセスする。ＣＰＵ１は、ドライブ装置６を介して記録媒体８からプログラムデータを読み出し、それを記憶装置３にインストールする。記録媒体８として、磁気テープ、メモリカード、フロッピー（登録商標）ディスク、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体を使用することができる。記録媒体８に、上述のプログラム、データを格納しておき、必要に応じて、メモリ２にロードして使用するようにしてもよい。
【００５０】
また、記録媒体８として、通信媒体を介してアップロードまたはダウンロードされたプログラムデータを記録した媒体、ディスク装置を用いることができる。さらに、記録媒体８として、コンピュータによって直接実行可能なプログラムを記録した記録媒体のみならず、いったん他の記録媒体（ハードディスク等）にインストールすることによって実行可能となるようなプログラムを記録した記録媒体、または、暗号化されたり、圧縮されたりしたプログラムを記録した記録媒体を用いることができる。
【００５１】
図２は、本実施形態に係る階層レイアウト設計方法の処理手順を示すフローチャートである。また、図３は、図２に示した下位階層端子位置決定処理工程Ｓ１１４の詳細な端子位置決定手順を示すフローチャートである。
【００５２】
本実施形態に係る階層レイアウト設計方法について、図２および図３のフローチャートの手順に従って説明する。
【００５３】
まず、設計対象の半導体集積回路に対するネットリストが読み込まれる（ステップＳ１１１）。
【００５４】
次に、フロアプランが生成される（ステップＳ１１２）。このとき、チップ領域が形成され、同時に階層レイアウトを適用する下位階層ブロックが抽出され、下位階層ブロック形状および下位階層ブロック配置位置が決定される。
【００５５】
図４は、フロアプラン生成処理（ステップＳ１１２）の結果を一例として示す図である。図４を参照すると、下位階層ブロック１０１，１０２，１０３，１０４が、各々下位階層ブロックの境界１１２，１２２，１３２，１４２で囲まれた形状に形成され、チップ領域１００に配置される。
【００５６】
次に、回路全体の仮配置配線処理が行われる（ステップＳ１１３）。
【００５７】
図５は、回路全体の仮配置配線処理（ステップＳ１１３）の結果を示す図である。図５を参照すると、各下位階層ブロックに属するセル１１１，１３１，１４１が、各々の下位階層ブロック領域内に配置され、端子位置決定前の仮配線経路Ｒ０によって、下位階層ブロック間が接続される。
【００５８】
次に、下位階層ブロック端子が配置される（ステップＳ１１４）。その理由は、下位階層ブロック単体で配置配線するときに下位階層ブロック外部との接続関係を認識するためである。
【００５９】
図６は、下位階層端子位置決定処理（ステップＳ１１４）の結果を示す図である。図６を参照すると、各下位階層ブロックに属するセル１１１，１３１，１４１が、各々の下位階層ブロック領域内に配置されている。また、上位階層で下位階層ブロック間を接続するために、出力端子２１が下位階層ブロックに属するセル１１１の近傍に配置され、入力端子２３，２４が、各々の下位階層ブロック領域内に配置されている。また、出力端子２１および入力端子２３，２４が配置される位置は、必ずしも端子位置決定前の仮配線経路Ｒ０の座標とは重ならない。下位階層端子位置決定処理（ステップＳ１１４）の内容については、後に詳述する。
【００６０】
次に、上位階層の配置配線処理が行われる（ステップＳ１１５）。下位階層ブロックよりも先に上位階層の配置配線を行う理由は、下位階層ブロックの配置配線前に上位階層での下位階層ブロック間のタイミング収束性を確認するためである。これにより、手戻りによる設計期間の増大を防ぐことができる。このとき、下位階層ブロックに属するすべてのセルを配置配線対象とする必要はなく、一般的な技術を用いて、下位階層ブロックに属するセルのうちの、下位階層ブロック外部と接続関係のあるセルのみを抽出するようにしてもよい。
【００６１】
図７は、上位階層配置配線処理（ステップＳ１１５）の結果を示す図である。図７を参照すると、各下位階層ブロックに属するセル１１１，１３１，１４１が配線経路Ｌによって接続され、下位階層ブロック間の接続が完了する。このとき、下位階層端子位置決定処理（ステップＳ１１４）で決定された各下位階層ブロックの出力端子２１と入力端子２３，２４とを中継するようにして配線が行われる。また、下位階層ブロック間のタイミング収束のために下位階層ブロック間の配線経路Ｌに挿入されるバッファ等の上位階層に属するセル１０は、迂回配線経路の発生を抑制するために、必要に応じて下位階層領域内にも配置される。
【００６２】
次に、下位階層領域内に存在する上位階層の配置配線情報が、下位階層領域内に配置配線禁止領域として設定される（ステップＳ１１６）。
【００６３】
次に、各下位階層ブロックの配置配線処理が実施される（ステップＳ１１７）。
【００６４】
図８は、各下位階層ブロックの配置配線処理（ステップＳ１１７）を示す図である。図８を参照すると、各下位階層ブロック１０１，１０２，１０４において、上位階層の配置配線情報を基に、配置禁止領域ＢＰ、および、配線禁止領域ＢＲが設定されている。配置禁止領域ＢＰおよび配線禁止領域ＢＲは、上位階層の配置配線に使用される領域であり、各下位階層ブロックの配置配線処理には使用されない領域である。
【００６５】
上位階層の配線を下位階層ブロックの内部に通すと、下位階層ブロック内のタイミングが劣化するため、一般に、上位階層の配置配線時に下位階層領域全体を配線禁止領域に設定する。しかし、本実施形態では、下位階層ブロック間を接続する際に迂回配線経路となることを防ぐために、下位階層ブロック端子を下位階層ブロック領域内部に配置する。したがって、上位階層の配線を下位階層ブロック領域内に通す必要がある。そこで、上位階層の配線情報に基づいて、配線禁止領域ＢＲを設定し、各下位階層ブロックの配置配線処理（ステップＳ１１７）において、上位階層の配線の影響を考慮し、下位階層ブロック内のタイミング設計に反映させる。
【００６６】
また、上位階層の配置配線（ステップＳ１１５）を下位階層ブロックの配置配線（ステップＳ１１７）よりも先に行うことで、上位階層の配線に必要な最低限の配線本数や配線層を抽出することができる。したがって、下位階層ブロック領域内を通過させる上位階層の配線のために設定する配線禁止領域を必要最低限とすることができ、無駄な配線リソースの消耗を防ぐことができる。
【００６７】
各下位階層ブロックの配置配線処理（ステップＳ１１７）が完了すると、各下位階層レイアウト結果が上位階層に結合される（ステップＳ１１８）。上位階層は、ステップＳ１１５において、すでに配置配線済みであるため、以上の処理により、本実施形態の階層レイアウトが完了する。
【００６８】
次に、図３を参照して、下位階層端子位置決定処理（ステップＳ１１４）における端子位置決定手順の詳細について説明する。
【００６９】
なお、図３に示した手順において、処理対象の下位階層ブロックおよび端子の選択順序は任意である。
【００７０】
まず、下位階層ブロック１０１が処理対象として選択される（ステップＳ２１０）。
【００７１】
次に、下位階層ブロック１０１から任意に選択された出力端子２１が出力端子であると判定される（ステップＳ２１１のＹｅｓ）。
【００７２】
次に、下位階層ブロック１０１の出力端子２１は、下位階層ブロック１０１に属し、かつ、出力端子２１を駆動するセル１１１の近傍の座標に仮配置される（ステップＳ２１２）。
【００７３】
次に、出力端子２１の座標が配線禁止領域内か否かが判定される（ステップＳ２１６）。その理由は、下位階層ブロックの端子が配線禁止領域上に配置されると、上位階層で下位階層ブロック間の配線ができなくなるからである。出力端子２１は、配線禁止領域内にないため（ステップＳ２１６のＮｏ）、配線禁止領域外に移動する処理（ステップＳ２１７）は実施されない。
【００７４】
次に、出力端子２１の位置が、仮配置した座標に決定される（ステップＳ２１８）。
【００７５】
次に、出力端子２１の領域が、配線禁止領域に設定される（ステップＳ２１９）。その理由は、以降の処理工程で他の端子の位置決定を行う際に、すでに位置が決定された端子の座標と重ならないようするためである。
【００７６】
下位階層ブロック１０１について未処理の端子が存在すると判定された場合には（ステップＳ２２０のＮｏ）、ステップＳ２１１に移行し、他の端子に対する処理が実施される。しかし、下位階層ブロック１０１について、未処理の端子は存在しないため（ステップＳ２２０のＹｅｓ）、ステップＳ２２１に移行する。
【００７７】
次に、未処理の下位階層ブロックがあると判定され（ステップＳ２２１のＮｏ）、ステップＳ２１０に移行し、下位階層ブロック１０４に対する処理が実施される。
【００７８】
下位階層ブロック１０１と同様に下位階層ブロック１０４から入力端子２４が任意に選択され、選択された入力端子２４が入力端子であると判定される（ステップＳ２１１のＮｏ）。
【００７９】
下位階層ブロック１０４に属するセルが複数存在する場合には、入力端子２４に接続される複数のセル１４１を囲む矩形領域Ｓが設定される。矩形領域Ｓを設定する処理の内容については、後述する。次に、入力端子２４に接続されるセル１１１の配置位置と、矩形領域Ｓとの距離Ｄが算出される。入力端子２４は、距離Ｄが最短で、かつ、矩形領域Ｓの枠上の座標に仮配置される（ステップＳ２１３）。
【００８０】
次に、入力端子２４の座標が下位階層ブロック１０４領域外に配置されているか否かが判定される（ステップＳ２１４）。入力端子２４は下位階層ブロック１０４の領域内に配置されているため（ステップＳ２１４のＮｏ）、下位階層ブロック領域内に移動する処理（ステップＳ２１５）は実施されない。なお、ステップＳ２１５の処理の内容については、後述する。
【００８１】
次に、入力端子２４の座標が配線禁止領域内か否かが判定される（ステップＳ２１６）。入力端子２４は、配線禁止領域内にないため（ステップＳ２１６のＮｏ）、配線禁止領域外に移動する処理（ステップ２１７）は実施されない。
【００８２】
次に、入力端子２４の位置が、仮配置した座標に決定される（ステップＳ２１８）。
【００８３】
次に、入力端子２４の領域が、配線禁止領域に設定される（ステップＳ２１９）。
【００８４】
下位階層ブロック１０４について未処理の端子が存在すると判定された場合には（ステップＳ２２０のＮｏ）、ステップＳ２１１に移行し、他の端子に対する処理が実施される。しかし、下位階層ブロック１０４について未処理の端子は存在しないため（ステップＳ２２０のＹｅｓ）、ステップＳ２２１に移行する。
【００８５】
次に、未処理の下位階層ブロックがあると判定され（ステップＳ２２１のＮｏ）、ステップＳ２１０に移行し、下位階層ブロック１０３に対する処理が実施される。
【００８６】
下位階層ブロック１０３から任意に選択された入力端子２３は、入力端子であるため（ステップＳ２１１のＮｏ）、下位階層ブロック１０４に対する処理と同様の処理により、入力端子２３の座標が決定される（ステップＳ２１３〜Ｓ２１８）。
【００８７】
次に、入力端子２３の領域が、配線禁止領域に設定される（ステップＳ２１９）。
【００８８】
次に、下位階層ブロック１０３について未処理の端子が存在しないと判定される（ステップＳ２２０のＹｅｓ）。
【００８９】
次に、未処理の下位階層ブロックが存在しないと判定され（ステップＳ２２１のＹｅｓ）、ステップＳ１１４の処理が完了する。
【００９０】
次に、ステップＳ２１３において、矩形領域Ｓを設定する処理の詳細について説明する。
【００９１】
入力端子は、出力端子の場合と異なり、下位階層ブロック内において、当該入力端子と接続されるセルが複数存在する場合がある。
【００９２】
図１０は、下位階層ブロック内の迂回配線経路を示す説明図である。下位階層ブロック１０２の入力端子２２が、下位階層ブロック１０２に属するセル１２１の近傍の座標に出力端子と同等の処理で配置されたとする。このとき、下位階層ブロック１０１に属するセル１１１からセル１２１までの配線経路Ｌは、迂回しない。一方、セル１１１から下位階層ブロック１０２に属するセル１３１までの配線経路Ｌ１は、下位階層ブロック１０２の領域内で迂回し、無駄に配線リソースを消耗する。
【００９３】
上記の場合、図１１に示すように、下位階層ブロック１０２に属するセルにおいて、入力端子２２と接続される複数のセル１２１，１３１を囲む矩形領域Ｓを設定する。そして、入力端子２２と接続される下位階層ブロック１０２以外の階層の下位階層ブロック１０１に属するセル１１１の座標と、矩形領域Ｓとの距離Ｄが算出される。入力端子２２は、距離Ｄが最短で、かつ、矩形領域Ｓの枠上の座標に仮配置される（ステップＳ２１３）。これにより、下位階層ブロック１０２の領域内で、迂回配線経路が発生することを抑制する。
【００９４】
次に、入力端子を下位階層ブロック領域内の座標に移動する処理（ステップＳ２１５）の詳細について説明する。
【００９５】
出力端子は、下位階層ブロックに属し、当該出力端子を駆動するセルの近傍の座標に配置される。したがって、出力端子は、下位階層ブロック領域外の座標に配置されることはない。一方、入力端子は、下位階層ブロックの形状が矩形でない場合には、下位階層ブロック領域外の座標に配置されることがある。このような場合には、各下位階層ブロックの配置配線を行う際に、下位階層ブロック外部との接続関係を認識することができなくなる。そこで、入力端子が下位階層ブロック領域外の座標に仮配置されたと判定された場合には（ステップＳ２１４のＹｅｓ）、仮配置された下位階層ブロックの入力端子の座標から距離が最も短い下位階層ブロック領域内の座標に、入力端子を移動する（ステップＳ２１５）。
【００９６】
図１２は、入力端子の移動（ステップＳ２１５）について説明するための図である。本実施形態によると、まず、入力端子２２は、図１２に示す座標に仮配置される（ステップＳ２１３）。図１２を参照すると、下位階層ブロック１０２の形状が矩形でないため、入力端子２２は下位階層ブロック１０２の領域外の座標に配置されている（ステップＳ２１４のＹｅｓ）。このとき、下位階層ブロック１０２の境界までの、水平方向距離Ｘ１および垂直方向距離Ｙ１の各々の距離が算出され、距離が短い方向に入力端子２２が移動される。図１２に示すように、Ｙ１＜Ｘ１である場合には、入力端子２２はＹ方向に移動される。すなわち、入力端子２２は、Ｙ座標に垂直方向距離Ｙ１を加算した入力端子２２０の座標に仮配置される（ステップＳ２１５）。
【００９７】
次に、入力端子および出力端子を配線禁止領域外の座標に移動する処理（ステップ２１７）の詳細について説明する。
【００９８】
端子の入出力属性に関係なく、下位階層ブロックの端子が配線禁止領域上の座標に配置されると、上位階層で下位階層ブロック間の配線ができなくなる。そこで、入力端子または出力端子の座標が配線禁止領域内に存在すると判定された場合には（ステップＳ２１６のＹｅｓ）、入力端子または出力端子を下位階層ブロック領域内の配線禁止領域外の座標に移動する（ステップＳ２１７）。
【００９９】
図１３は、入力端子の移動（ステップＳ２１７）について説明するための図である。図１３を参照すると、本実施形態において、入力端子２２は、図１３に示す座標に仮配置される（ステップＳ２１３）。入力端子２２の座標は、下位階層ブロック１０２領域内に存在する配線禁止領域ＢＲの領域内に存在する（ステップＳ２１６のＹｅｓ）。このとき、入力端子２２を基準に配線禁止領域ＢＲの枠に向かって、水平方向距離Ｘ１、Ｘ２および垂直方向距離Ｙ１、Ｙ２が算出され、水平方向と垂直方向の双方について、それぞれ距離が短い方に入力端子が移動される。図１３に示すように、Ｘ１＜Ｘ２，Ｙ１＜Ｙ２である場合には、Ｘ座標に水平方向距離Ｘ１、Ｙ座標に垂直方向距離Ｙ１を加算した入力端子２２０の座標に、入力端子が仮配置される（ステップＳ２１７）。なお、出力端子が配線禁止領域と重なった場合にも、同様の処理（ステップＳ２１７）が行われる。
【０１００】
本実施形態によると、複数の下位階層ブロックが接続されている場合にも、下位階層ブロック間の迂回配線経路を抑制することができる。
【０１０１】
実施形態に係る階層レイアウト設計方法によれば、下位階層ブロックの端子の位置を下位階層ブロックの領域内部に配置することで、図９に示したように、下位階層ブロック１０１（ないし下位階層ブロック１０１に属するセル１１１）から、下位階層ブロック１０３（ないし下位階層ブロック１０３に属するセル１３１）、および、下位階層ブロック１０４（ないし下位階層ブロック１０４に属するセル１４１）への２つの接続が、下位階層ブロック１０１を基準として、座標上で反対側に配置されていても、下位階層ブロック間の配線経路Ｌは、階層ブロック１０１から階層ブロック１０３までと、下位階層ブロック１０４までとの双方を最短で接続することができる。また、下位階層ブロック間の配線経路Ｌは、下位階層ブロック領域内（１０１，１０２等）を通過することで、迂回配線経路を抑制することができる。
【０１０２】
さらに、上位階層の配置配線（ステップＳ１１５）を下位階層ブロックの配置配線（ステップＳ１１７）よりも先に実施し、上位階層の配置配線情報を下位階層ブロック領域内で配置配線禁止領域に設定し（ステップＳ１１６）、下位階層ブロックの配置配線の際に上位階層の配線の影響を考慮することで（ステップＳ１１７）、下位階層ブロック内のタイミング設計に反映することが好ましい。したがって、上位階層の配線が下位階層ブロック領域内を通過していても、タイミングに関する問題が生じない。
【０１０３】
なお、上記の特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１０４】
１ ＣＰＵ（中央処理装置）
２ メモリ
３ 記憶装置
４ 表示装置
５ 入力装置
６ ドライブ装置
７ バス
８ 記憶媒体
１０ 上位階層に属するセル
２１ 出力端子
２２，２３，２４ 入力端子
３１ 出力端子配置部
３２ 入力端子配置部
３３，３６ 配線禁止領域設定部
３５ 上位階層配線部
３７ 下位階層配線部
１００，４００ チップ領域
１０１，１０２，１０３，１０４，４０１，４０２，４０３，４０４ 下位階層ブロック
１１１，１２１，１３１，１４１，４１１，４３１，４４１ セル
１１２，１２２，１３２，１４２，４１２，４３２，４４２ 境界（バウンダリ）
２２０ 移動後の入力端子
２１３ レイアウト情報
４１０，４３０，４４０ 端子
ＢＰ 配置禁止領域
ＢＲ 配線禁止領域
Ｄ 距離
ｄ１，ｄ２ 所定距離
Ｌ 下位階層ブロック間配線経路
Ｌ１ 迂回配線経路
Ｐａ 第１の仮配線上ポイント
Ｐｂ 第１のバウンダリポイント
Ｐｃ 第２の仮配線経路上ポイント
Ｐｄ 第２のバウンダリポイント
Ｒ０ 端子位置決定前の仮配線経路
Ｒ１，Ｒ２，Ｒ３，Ｒ４ セル間仮配線経路
Ｓ 矩形領域
Ｘ，Ｙ 端子位置
Ｘ１，Ｘ２ 水平方向距離
Ｙ１，Ｙ２ 垂直方向距離
【技術分野】
【０００１】
本発明は、半導体集積回路（ＬＳＩ）の階層レイアウト設計装置、階層レイアウト設計方法およびプログラムに関し、特に、下位階層ブロック毎に分割して配置配線を行うとともに、下位階層ブロック同士を接続するための端子の配置を決定する階層レイアウト設計装置、階層レイアウト設計方法およびプログラムに関する。
【背景技術】
【０００２】
半導体集積回路（ＬＳＩ）を設計する際に、回路全体のレイアウト設計を一括して行うと、データ量が膨大となり、困難を伴う。そこで、半導体集積回路を複数の下位階層ブロックに分割し、下位階層レイアウトごとにレイアウト設計を行う階層レイアウト設計が主流となっている。
【０００３】
階層レイアウト設計において、各下位階層ブロック間の配線を上位階層で結線するために、各下位階層ブロックに下位階層ブロック端子（以下、単に「端子」という。）が生成される。上位階層でのタイミング収束性および回路収容性を向上させるには、下位階層ブロックにおいて、端子を好適な位置に配置する必要がある。近年の回路動作速度の高速化に伴い、上位階層でのタイミングが非常に厳しくなっており、下位階層ブロックにおいて、端子を好適な位置に配置する重要性が増している。
【０００４】
例えば、特許文献１に、階層設計レイアウトにおいて、端子を最適な位置に配置する階層設計レイアウト方法が記載されている。
【０００５】
図１５は、特許文献１に記載された階層設計レイアウト処理手順を示すフローチャートである。ここでは、図１５のステップＳ５０９に示した最適化処理手順について詳細に説明する。図１６は、ステップＳ５０９に示した最適化処理手順を示すフローチャートである。
【０００６】
図１７は、図１５のステップＳ５０８に示した端子位置仮決定処理後におけるレイアウト情報の一例を示す説明図である。図１７において、レイアウト情報２１３は、チップ４００上にフロアプランされた下位階層ブロック４０１〜４０３が仮配置された情報である。下位階層ブロック４０１、４０３内の黒塗り矩形はセルをあらわしている。ここで、下位階層ブロック４０１が一方の下位階層ブロックに該当し、下位階層ブロック４０３が他方の下位階層ブロックに該当する。
【０００７】
レイアウト情報２１３では、下位階層ブロック４０１内のセル４１１から下位階層ブロック４０３内のセル４３１までセル間仮配線経路Ｒ１が仮配線されている。セル間仮配線経路Ｒ１は、配線禁止領域に設定された下位階層ブロック４０２を迂回して引かれている。
【０００８】
また、下位階層ブロック４０１の境界を表すバウンダリ４１２とセル間仮配線経路Ｒ１との交点が端子４１０の端子位置となる。以降、端子位置Ｘと称す。同様に、下位階層ブロック４０３の境界を表すバウンダリ４３２とセル間仮配線経路Ｒ１との交点が端子４３０の端子位置となる。以降、端子位置Ｙと称す。
【０００９】
また、ステップＳ５０９に示した最適化処理は仮決定された端子位置Ｘ、Ｙを最適化する。具体的には、仮配線経路検出部と、第１の仮配線経路上ポイント検出部と、第１のバウンダリポイント検出部と、第２の仮配線経路上ポイント検出部と、第２のバウンダリポイント検出部と、端子位置決定部と、から構成されている。
【００１０】
まず、仮配線経路検出部により、未処理のセル間仮配線経路があるか否かを判断し（ステップＳ５２１）、未処理のセル間仮配線経路がある場合（ステップＳ５２１：Ｙｅｓ）、第１の仮配線経路上ポイント検出部により、一方の端子を基準端子に決定する（ステップＳ５２２）。図１７に示したレイアウト情報では、セル間仮配線経路Ｒ１から端子位置Ｘと端子位置Ｙとの間の仮配線経路Ｒ２を検出し、一方の端子４１０を基準端子に決定する。
【００１１】
次に、仮配線経路上において、第１の仮配線経路上ポイント検出処理、すなわち他方の下位階層ブロックから所定距離以内で、かつ一方の端子からの配線長が最短となる第１の仮配線上ポイントを検出する（ステップＳ５２３）。そして、第１のバウンダリポイント検出部により、第１のバウンダリポイントを検出する（ステップＳ５２４）。
【００１２】
図１８は、第１の仮配線経路上ポイント検出処理を示す説明図である。図１８において、まず、仮配線経路Ｒ２上において、一方の端子４１０を基準とした場合、他方の端子４３０を有する他方の下位階層ブロック４０３から所定距離ｄ１以内の経路Ｒ３を検出する。そして、この経路Ｒ３中、一方の端子４１０からの配線長が最短となる点Ｐａを、第１の仮配線上ポイントとして検出する。そして、第１の仮配線経路上ポイントＰａから他方の下位階層ブロック４０３のバウンダリ４３２までの距離が最短となるバウンダリ４３２上の点Ｐｂを第１のバウンダリポイントとして検出する。
【００１３】
次に、第２の仮配線経路上ポイント検出部により、第２の仮配線経路上ポイント検出処理、すなわち仮配線経路上において、一方の下位階層ブロックから所定距離以内で、かつ第１の仮配線経路上ポイントからの配線長が最短となる第２の仮配線経路上ポイントを検出する（ステップＳ５２５）。そして、第２のバウンダリポイント検出部により、第２のバウンダリポイントを検出する（ステップＳ５２６）。
【００１４】
図１９は、第２の仮配線経路上ポイント検出処理を示す説明図である。図１９において、仮配線経路Ｒ２上で、一方の下位階層ブロック４０１から所定距離ｄ２以内の経路Ｒ４を検出する。そして、この経路Ｒ４中、第１の仮配線経路上ポイントＰａからの配線長が最短となる点Ｐｃを、第２の仮配線経路上ポイントとして検出する。そして、第２の仮配線経路上ポイントＰｃから一方の下位階層ブロック４０１のバウンダリ４１２までの距離が最短となるバウンダリ４１２上の点Ｐｄを第２のバウンダリポイントとして検出する。
【００１５】
次に、端子位置決定部により、第１および第２のバウンダリポイントを端子アサイン候補に決定し（ステップＳ５２７）、第１および第２のバウンダリポイントに端子を配置することがデザインルールを遵守するか否かを判断する（ステップＳ５２８）。デザインルール違反となると判断された場合（ステップＳ５２８：Ｎｏ）、ステップＳ５２２に戻る。一方、デザインルールを遵守すると判断された場合（ステップＳ５２８：Ｙｅｓ）、第１および第２のバウンダリポイントを新たな端子位置に決定する（ステップＳ５２９）。
【００１６】
図２０は、端子位置決定処理結果を示す説明図である。図２０において、第２のバウンダリポイントＰｄが一方の端子４１０の新たな端子位置に決定されている。第１のバウンダリポイントＰｂが他方の端子４３０の新たな端子位置に決定されている。
【００１７】
そして、ステップＳ５２１に戻る。また、ステップＳ５２１において、未処理のセル間仮配線経路が検出されなかった場合（ステップＳ５２１：Ｎｏ）、図１５に示したステップＳ５１０に移行する。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００８−００９７８７号公報（図４−１〜４−４、図５−１、５−２）
【発明の概要】
【発明が解決しようとする課題】
【００１９】
以下の分析は、本発明者によってなされたものである。
【００２０】
特許文献１に記載された技術によると、複数の下位階層ブロックを接続する際、迂回経路の発生を抑制できない場合が生じうるという問題がある。
【００２１】
その理由は、上位階層の配置配線時に下位階層ブロックのタイミング劣化の発生を抑止するため、端子を下位階層ブロックの境界を表すバウンダリ上に配置するからである。特許文献１に記載された技術によると、例えば、ある下位階層ブロックから２つの下位階層ブロックへの接続があり、これらの２つの接続が最初の下位階層ブロックを基準として座標上で反対側に配置されている場合に、これらの２つの接続のうちの一方を最短にできても、他方については迂回配線経路の発生を抑制できない場合がある。
【００２２】
図２１は、複数の下位階層ブロックが接続されている場合に、特許文献１に記載された技術により、端子の位置を決定した結果を示す図である。
【００２３】
図２１を参照すると、下位階層ブロック４０１は、下位階層ブロック４０３と接続されている。同時に、下位階層ブロック４０１は、下位階層ブロック４０１に対して、Ｘ（水平方向）座標に関して、下位階層ブロック４０３と反対側に位置する下位階層ブロック４０４と接続されている。
【００２４】
下位階層ブロック４０１から下位階層ブロック４０３への接続は配線禁止領域を跨いでいない。したがって、ステップＳ５０９に示した最適化処理によって、下位階層ブロック端子は下位階層ブロック４０１と下位階層ブロック４０３を最短で接続するために、端子４１０の位置と端子４３０の位置に配置されると考えられる。このとき、配線経路は、配線経路Ｌのように最短の経路となる。
【００２５】
特許文献１に記載された技術では複数の下位階層ブロックが同一信号で接続される場合が定義されていない。したがって、下位階層ブロック４０１から下位階層ブロック４０４への接続に関しては、図２１に示すように、下位階層ブロック４０１が配線禁止領域に設定されていない場合に、端子の位置は、既に決定されていた端子４１０の位置にそのまま決定されると考えられる。このとき、端子４１０から下位階層ブロック４０１を通過し、下位階層ブロック４０４へ接続することで、端子４４０の位置が決定される。端子が多数存在する場合には、これらの端子のＹ（垂直方向）座標と、端子４１０のＹ座標とが、大きく隔たるように配置される。
【００２６】
一般に、下位階層ブロック端子は、ネットリストの物理構造に従って生成される。下位階層ブロック４０１から下位階層ブロック４０３および４０４へ同一の信号が接続されている場合に、下位階層ブロック４０１を基準として下位階層ブロック４０３と下位階層ブロック４０４とが座標上で反対側に配置されていると、他の下位階層ブロックと接続するセルの多さに起因して、複数の端子を容易に生成することができず、下位階層ブロック４０１から下位階層ブロック４０４への配線がＬ１のような迂回配線経路となる。したがって、タイミング収束性が悪化したり、迂回配線経路により無駄な配線リソースを消費することで収容性が悪化したりして、設計品質が低下し、手戻りによる設計期間の増加を招く。
【００２７】
そこで、複数の下位階層ブロックに跨るセル同士を各下位階層ブロックに設けた端子を経由して相互に接続する場合に、セル間を結ぶ経路が迂回経路となることを防ぐことが課題となる。
【課題を解決するための手段】
【００２８】
本発明の第１の視点に係る階層レイアウト設計装置は、
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する出力端子配置部と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する入力端子配置部と、を備えている。
【００２９】
本発明の第２の視点に係る階層レイアウト設計方法は、
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する工程と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する工程と、を含む。
【００３０】
本発明の第３の視点に係るプログラムは、
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する処理と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する処理と、をコンピュータに実行させる。
【発明の効果】
【００３１】
本発明に係る階層レイアウト設計装置、階層レイアウト設計方法およびプログラムによると、複数の下位階層ブロックに跨るセル同士を各下位階層ブロックに設けた端子を経由して相互に接続する場合に、セル間を結ぶ経路が迂回経路となることを防ぐことができる。
【図面の簡単な説明】
【００３２】
【図１】本発明に係る階層レイアウト設計装置の構成を概略的に示すブロック図である。
【図２】実施形態に係る階層レイアウト設計方法の処理手順を示すフローチャートである。
【図３】実施形態に係る階層レイアウト設計方法における下位階層端子位置決定手順を示すフローチャートである。
【図４】実施形態に係る階層レイアウト設計方法におけるフロアプラン処理（図２のステップＳ１１２）の結果について説明するための図である。
【図５】実施形態に係る階層レイアウト設計方法における仮配置配線処理（図２のステップＳ１１３）の結果について説明するための図である。
【図６】実施形態に係る階層レイアウト設計方法における端子位置決定処理（図２のステップＳ１１４）の結果について説明するための図である。
【図７】実施形態に係る階層レイアウト設計方法における上位階層配置配線処理（図２のステップＳ１１５）の結果について説明するための図である。
【図８】実施形態に係る階層レイアウト設計方法における各下位階層の配置配線処理（図２のステップＳ１１７）について説明するための図である。
【図９】実施形態に係る階層レイアウト設計方法における階層レイアウトの結果について説明するための図である。
【図１０】実施形態に係る階層レイアウト設計方法における下位階層ブロック内の迂回配線経路について説明するための図である。
【図１１】実施形態に係る階層レイアウト設計方法における下位階層ブロック内の迂回配線抑制方法について説明するための図である。
【図１２】実施形態に係る階層レイアウト設計方法における入力端子の移動（図３のステップＳ２１５）について説明するための図である。
【図１３】実施形態に係る階層レイアウト設計方法における入力端子の移動（図３のステップＳ２１７）について説明するための図である。
【図１４】実施形態に係る階層レイアウト設計方法を実現するためのシステム構成を示すブロック図である。
【図１５】特許文献１に記載された階層設計レイアウト処理手順を示すフローチャートである。
【図１６】特許文献１に記載された最適化手順を示すフローチャートである。
【図１７】特許文献１に記載された仮決定処理後におけるレイアウト情報を一例として示す図である。
【図１８】特許文献１に記載された第１の仮配線経路上ポイント検出処理について説明するための図である。
【図１９】特許文献１に記載された第２の仮配線経路上ポイント検出処理について説明するための図である。
【図２０】特許文献１に記載された端子位置決定部による決定処理結果について説明するための図である。
【図２１】特許文献１に記載された端子位置決定処理の結果について説明するための図である。
【発明を実施するための形態】
【００３３】
はじめに、本発明の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００３４】
図１は、本発明に係る階層レイアウト設計装置の構成を概略的に示すブロック図である。図１および図１１を参照すると、階層レイアウト設計装置は、第１の下位階層ブロック（１０１）に含まれるセル（１１１）から出力された信号を受信する出力端子（２１）をセル（１１１）の近傍に配置する出力端子配置部（３１）と、第２の下位階層ブロック（１０２）に含まれる複数のセル（１２１，１３１）へ出力端子（２１）から出力された信号を供給する入力端子（２２）を、複数のセル（１２１，１３１）を囲む最小の矩形領域（Ｓ）の境界上であって、出力端子（２１）が配置された箇所からの距離が最短の箇所に配置する入力端子配置部（３２）と、を備えている。
【００３５】
また、図１２を参照すると、入力端子配置部（３２）は、入力端子（２２）が第２の下位階層ブロック（１０２）の領域外に配置された場合には、第２の下位階層ブロック（１０２）の領域内であって入力端子（２２）の配置箇所からの距離が最短の箇所（２２０）へ、入力端子（２２）を移動することが好ましい。
【００３６】
一方、図１３を参照すると、入力端子配置部（３２）は、入力端子（２２）が配線禁止領域（ＢＲ）に配置された場合には、配線禁止領域（ＢＲ）外であって入力端子（２２）の配置箇所からの距離が最短の箇所（２２０）へ、入力端子を移動することが好ましい。
【００３７】
また、階層レイアウト設計装置は、出力端子（２１）を配置した領域を第１の下位階層ブロック（１０１）に配線禁止領域として設定するとともに、入力端子（２２）を配置した領域を第２の下位階層ブロック（１０２）に配線禁止領域として設定する第１の配線禁止領域設定部（３３）を備えていることが好ましい。
【００３８】
さらに、図示しないが、出力端子配置部（３１）は、出力端子（２１）が配線禁止領域に配置された場合には、配線禁止領域外であって出力端子（２１）の配置箇所からの距離が最短の箇所へ、出力端子（２１）を移動することが好ましい。
【００３９】
また、図７および図８を参照すると、階層レイアウト装置は、第１の下位階層ブロック（１０１）に配置された出力端子（２１）と、第２の下位階層ブロック（１０３，１０４）に設けられた入力端子（２３，２４）との間を配線する上位階層配線部（３５）と、配線に用いられた領域を第１の下位階層ブロック（１０１）および第２の下位階層ブロック（１０３，１０４）に配線禁止領域（ＢＲ）として設定する第２の配線禁止領域設定部（３６）と、第２の配線禁止領域設定部（３６）により設定された配線禁止領域を回避しつつ、第１の下位階層ブロック（１０１）および第２の下位階層ブロック（１０３，１０４）における配線を実施する下位階層配線部（３７）と、を備えていることが好ましい。
【００４０】
本発明に係る階層レイアウト設計装置によると、複数の下位階層ブロックに跨るセル同士を各下位階層ブロックに設けた端子を経由して相互に接続する場合に、セル間を結ぶ経路が迂回経路となることを防ぐことができる。
【００４１】
また、本発明は、半導体集積回路のレイアウト設計方法に関し、特に、下位階層ブロック毎に分割して配置配線を行うために下位階層ブロック端子の位置決定処理を行う階層レイアウト設計方法に関する。
【００４２】
図２を参照すると、階層レイアウト設計方法は、下位階層ブロック端子を下位階層ブロック領域内に配置する工程（Ｓ１１４）と、上位階層の配置配線を下位階層ブロックの配置配線より先に実施する工程（Ｓ１１５、Ｓ１１７）と、下位階層ブロック領域上に位置する上位階層の配置配線情報を下位階層ブロック内に配置配線禁止領域として設定する工程（Ｓ１１６）とを含むことが好ましい。
【００４３】
また、図３を参照すると、下位階層ブロック端子を下位階層ブロック領域内に配置する工程（Ｓ１１４）は、さらに、下位階層ブロックの出力端子位置を下位階層ブロックの出力端子を駆動する下位階層ブロック領域内のセルの近傍に仮配置する工程（Ｓ２１２）と、下位階層ブロックの入力端子位置を下位階層ブロックの入力端子に接続される下位階層ブロック領域内のセルを囲む矩形領域の枠上で、かつ、前記セルに接続する他の階層（他の下位階層または上位階層）に属するセルの配置位置との距離が最も短い座標に仮配置する工程（Ｓ２１３）と、仮配置した入力端子が各々の下位階層ブロック領域外となった場合に（Ｓ２１４のＹｅｓ）、下位階層ブロック領域内のうち、仮配置した位置からの距離が最も短い座標に移動する工程（Ｓ２１５）と、仮配置した入力端子および出力端子の座標が配線禁止領域内に存在する場合に（Ｓ２１６のＹｅｓ）、各々の下位階層ブロック領域内における配線禁止領域外に移動する工程（Ｓ２１７）と、仮配置した入力端子および出力端子の配置位置を決定する工程（Ｓ２１８）と、配置位置が決定された下位階層ブロックの入力端子および出力端子の領域を配線禁止領域に設定する工程（Ｓ２１９）と、を含むことが好ましい。
【００４４】
本発明によると、下位階層ブロック間を下位階層ブロック領域内を通過させて短距離の配線経路で接続することができ、複数の下位階層ブロックが接続される場合にも、迂回配線経路の発生を抑制することができる。
【００４５】
（実施形態）
実施形態に係る階層レイアウト設計方法について、図面を参照して説明する。本実施形態に係る階層レイアウト設計方法は、図１４に示されるようなコンピュータを用いた設計システム上において実現することができる。
【００４６】
設計システムは、一例として、ＣＡＤ（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ）装置として構成することができる。図１４を参照すると、ＣＡＤ装置は、中央処理装置（以下、ＣＰＵという）１、メモリ２、記憶装置３、表示装置４、入力装置５、および、ドライブ装置６を備え、これらはバス７を介して相互に接続されている。
【００４７】
ＣＰＵ１は、メモリ２を利用してプログラムを実行し、各種処理を実施する。メモリ２には、各種処理を提供するために必要なプログラムとデータが格納される。メモリ２は、キャッシュ・メモリ、システム・メモリおよびディスプレイ・メモリを含んでいてもよい。
【００４８】
表示装置４は、レイアウト表示、パラメータ入力画面等の表示に用いられる。表示装置４として、ＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）、ＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）、ＰＤＰ（Ｐｌａｓｍａ Ｄｉｓｐｌａｙ Ｐａｎｅｌ）等を用いることができる。入力装置５は、ユーザからの要求や指示、パラメータの入力に用いられる。入力装置５として、キーボードおよびマウス（非図示）等が用いられる。記憶装置３として、磁気ディスク装置、光ディスク装置または光磁気ディスク装置を用いることができる。記憶装置３には、後述する自動配線配置処理などの半導体装置設計処理のためのプログラムデータとファイルが格納される。ＣＰＵ１は、入力装置５による指示に応答して、プログラムおよびデータをメモリ２へ転送して実行する。
【００４９】
ＣＰＵ１が実行するプログラムデータは、記録媒体８により提供される。ドライブ装置６は、記録媒体８を駆動し、その記憶内容にアクセスする。ＣＰＵ１は、ドライブ装置６を介して記録媒体８からプログラムデータを読み出し、それを記憶装置３にインストールする。記録媒体８として、磁気テープ、メモリカード、フロッピー（登録商標）ディスク、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体を使用することができる。記録媒体８に、上述のプログラム、データを格納しておき、必要に応じて、メモリ２にロードして使用するようにしてもよい。
【００５０】
また、記録媒体８として、通信媒体を介してアップロードまたはダウンロードされたプログラムデータを記録した媒体、ディスク装置を用いることができる。さらに、記録媒体８として、コンピュータによって直接実行可能なプログラムを記録した記録媒体のみならず、いったん他の記録媒体（ハードディスク等）にインストールすることによって実行可能となるようなプログラムを記録した記録媒体、または、暗号化されたり、圧縮されたりしたプログラムを記録した記録媒体を用いることができる。
【００５１】
図２は、本実施形態に係る階層レイアウト設計方法の処理手順を示すフローチャートである。また、図３は、図２に示した下位階層端子位置決定処理工程Ｓ１１４の詳細な端子位置決定手順を示すフローチャートである。
【００５２】
本実施形態に係る階層レイアウト設計方法について、図２および図３のフローチャートの手順に従って説明する。
【００５３】
まず、設計対象の半導体集積回路に対するネットリストが読み込まれる（ステップＳ１１１）。
【００５４】
次に、フロアプランが生成される（ステップＳ１１２）。このとき、チップ領域が形成され、同時に階層レイアウトを適用する下位階層ブロックが抽出され、下位階層ブロック形状および下位階層ブロック配置位置が決定される。
【００５５】
図４は、フロアプラン生成処理（ステップＳ１１２）の結果を一例として示す図である。図４を参照すると、下位階層ブロック１０１，１０２，１０３，１０４が、各々下位階層ブロックの境界１１２，１２２，１３２，１４２で囲まれた形状に形成され、チップ領域１００に配置される。
【００５６】
次に、回路全体の仮配置配線処理が行われる（ステップＳ１１３）。
【００５７】
図５は、回路全体の仮配置配線処理（ステップＳ１１３）の結果を示す図である。図５を参照すると、各下位階層ブロックに属するセル１１１，１３１，１４１が、各々の下位階層ブロック領域内に配置され、端子位置決定前の仮配線経路Ｒ０によって、下位階層ブロック間が接続される。
【００５８】
次に、下位階層ブロック端子が配置される（ステップＳ１１４）。その理由は、下位階層ブロック単体で配置配線するときに下位階層ブロック外部との接続関係を認識するためである。
【００５９】
図６は、下位階層端子位置決定処理（ステップＳ１１４）の結果を示す図である。図６を参照すると、各下位階層ブロックに属するセル１１１，１３１，１４１が、各々の下位階層ブロック領域内に配置されている。また、上位階層で下位階層ブロック間を接続するために、出力端子２１が下位階層ブロックに属するセル１１１の近傍に配置され、入力端子２３，２４が、各々の下位階層ブロック領域内に配置されている。また、出力端子２１および入力端子２３，２４が配置される位置は、必ずしも端子位置決定前の仮配線経路Ｒ０の座標とは重ならない。下位階層端子位置決定処理（ステップＳ１１４）の内容については、後に詳述する。
【００６０】
次に、上位階層の配置配線処理が行われる（ステップＳ１１５）。下位階層ブロックよりも先に上位階層の配置配線を行う理由は、下位階層ブロックの配置配線前に上位階層での下位階層ブロック間のタイミング収束性を確認するためである。これにより、手戻りによる設計期間の増大を防ぐことができる。このとき、下位階層ブロックに属するすべてのセルを配置配線対象とする必要はなく、一般的な技術を用いて、下位階層ブロックに属するセルのうちの、下位階層ブロック外部と接続関係のあるセルのみを抽出するようにしてもよい。
【００６１】
図７は、上位階層配置配線処理（ステップＳ１１５）の結果を示す図である。図７を参照すると、各下位階層ブロックに属するセル１１１，１３１，１４１が配線経路Ｌによって接続され、下位階層ブロック間の接続が完了する。このとき、下位階層端子位置決定処理（ステップＳ１１４）で決定された各下位階層ブロックの出力端子２１と入力端子２３，２４とを中継するようにして配線が行われる。また、下位階層ブロック間のタイミング収束のために下位階層ブロック間の配線経路Ｌに挿入されるバッファ等の上位階層に属するセル１０は、迂回配線経路の発生を抑制するために、必要に応じて下位階層領域内にも配置される。
【００６２】
次に、下位階層領域内に存在する上位階層の配置配線情報が、下位階層領域内に配置配線禁止領域として設定される（ステップＳ１１６）。
【００６３】
次に、各下位階層ブロックの配置配線処理が実施される（ステップＳ１１７）。
【００６４】
図８は、各下位階層ブロックの配置配線処理（ステップＳ１１７）を示す図である。図８を参照すると、各下位階層ブロック１０１，１０２，１０４において、上位階層の配置配線情報を基に、配置禁止領域ＢＰ、および、配線禁止領域ＢＲが設定されている。配置禁止領域ＢＰおよび配線禁止領域ＢＲは、上位階層の配置配線に使用される領域であり、各下位階層ブロックの配置配線処理には使用されない領域である。
【００６５】
上位階層の配線を下位階層ブロックの内部に通すと、下位階層ブロック内のタイミングが劣化するため、一般に、上位階層の配置配線時に下位階層領域全体を配線禁止領域に設定する。しかし、本実施形態では、下位階層ブロック間を接続する際に迂回配線経路となることを防ぐために、下位階層ブロック端子を下位階層ブロック領域内部に配置する。したがって、上位階層の配線を下位階層ブロック領域内に通す必要がある。そこで、上位階層の配線情報に基づいて、配線禁止領域ＢＲを設定し、各下位階層ブロックの配置配線処理（ステップＳ１１７）において、上位階層の配線の影響を考慮し、下位階層ブロック内のタイミング設計に反映させる。
【００６６】
また、上位階層の配置配線（ステップＳ１１５）を下位階層ブロックの配置配線（ステップＳ１１７）よりも先に行うことで、上位階層の配線に必要な最低限の配線本数や配線層を抽出することができる。したがって、下位階層ブロック領域内を通過させる上位階層の配線のために設定する配線禁止領域を必要最低限とすることができ、無駄な配線リソースの消耗を防ぐことができる。
【００６７】
各下位階層ブロックの配置配線処理（ステップＳ１１７）が完了すると、各下位階層レイアウト結果が上位階層に結合される（ステップＳ１１８）。上位階層は、ステップＳ１１５において、すでに配置配線済みであるため、以上の処理により、本実施形態の階層レイアウトが完了する。
【００６８】
次に、図３を参照して、下位階層端子位置決定処理（ステップＳ１１４）における端子位置決定手順の詳細について説明する。
【００６９】
なお、図３に示した手順において、処理対象の下位階層ブロックおよび端子の選択順序は任意である。
【００７０】
まず、下位階層ブロック１０１が処理対象として選択される（ステップＳ２１０）。
【００７１】
次に、下位階層ブロック１０１から任意に選択された出力端子２１が出力端子であると判定される（ステップＳ２１１のＹｅｓ）。
【００７２】
次に、下位階層ブロック１０１の出力端子２１は、下位階層ブロック１０１に属し、かつ、出力端子２１を駆動するセル１１１の近傍の座標に仮配置される（ステップＳ２１２）。
【００７３】
次に、出力端子２１の座標が配線禁止領域内か否かが判定される（ステップＳ２１６）。その理由は、下位階層ブロックの端子が配線禁止領域上に配置されると、上位階層で下位階層ブロック間の配線ができなくなるからである。出力端子２１は、配線禁止領域内にないため（ステップＳ２１６のＮｏ）、配線禁止領域外に移動する処理（ステップＳ２１７）は実施されない。
【００７４】
次に、出力端子２１の位置が、仮配置した座標に決定される（ステップＳ２１８）。
【００７５】
次に、出力端子２１の領域が、配線禁止領域に設定される（ステップＳ２１９）。その理由は、以降の処理工程で他の端子の位置決定を行う際に、すでに位置が決定された端子の座標と重ならないようするためである。
【００７６】
下位階層ブロック１０１について未処理の端子が存在すると判定された場合には（ステップＳ２２０のＮｏ）、ステップＳ２１１に移行し、他の端子に対する処理が実施される。しかし、下位階層ブロック１０１について、未処理の端子は存在しないため（ステップＳ２２０のＹｅｓ）、ステップＳ２２１に移行する。
【００７７】
次に、未処理の下位階層ブロックがあると判定され（ステップＳ２２１のＮｏ）、ステップＳ２１０に移行し、下位階層ブロック１０４に対する処理が実施される。
【００７８】
下位階層ブロック１０１と同様に下位階層ブロック１０４から入力端子２４が任意に選択され、選択された入力端子２４が入力端子であると判定される（ステップＳ２１１のＮｏ）。
【００７９】
下位階層ブロック１０４に属するセルが複数存在する場合には、入力端子２４に接続される複数のセル１４１を囲む矩形領域Ｓが設定される。矩形領域Ｓを設定する処理の内容については、後述する。次に、入力端子２４に接続されるセル１１１の配置位置と、矩形領域Ｓとの距離Ｄが算出される。入力端子２４は、距離Ｄが最短で、かつ、矩形領域Ｓの枠上の座標に仮配置される（ステップＳ２１３）。
【００８０】
次に、入力端子２４の座標が下位階層ブロック１０４領域外に配置されているか否かが判定される（ステップＳ２１４）。入力端子２４は下位階層ブロック１０４の領域内に配置されているため（ステップＳ２１４のＮｏ）、下位階層ブロック領域内に移動する処理（ステップＳ２１５）は実施されない。なお、ステップＳ２１５の処理の内容については、後述する。
【００８１】
次に、入力端子２４の座標が配線禁止領域内か否かが判定される（ステップＳ２１６）。入力端子２４は、配線禁止領域内にないため（ステップＳ２１６のＮｏ）、配線禁止領域外に移動する処理（ステップ２１７）は実施されない。
【００８２】
次に、入力端子２４の位置が、仮配置した座標に決定される（ステップＳ２１８）。
【００８３】
次に、入力端子２４の領域が、配線禁止領域に設定される（ステップＳ２１９）。
【００８４】
下位階層ブロック１０４について未処理の端子が存在すると判定された場合には（ステップＳ２２０のＮｏ）、ステップＳ２１１に移行し、他の端子に対する処理が実施される。しかし、下位階層ブロック１０４について未処理の端子は存在しないため（ステップＳ２２０のＹｅｓ）、ステップＳ２２１に移行する。
【００８５】
次に、未処理の下位階層ブロックがあると判定され（ステップＳ２２１のＮｏ）、ステップＳ２１０に移行し、下位階層ブロック１０３に対する処理が実施される。
【００８６】
下位階層ブロック１０３から任意に選択された入力端子２３は、入力端子であるため（ステップＳ２１１のＮｏ）、下位階層ブロック１０４に対する処理と同様の処理により、入力端子２３の座標が決定される（ステップＳ２１３〜Ｓ２１８）。
【００８７】
次に、入力端子２３の領域が、配線禁止領域に設定される（ステップＳ２１９）。
【００８８】
次に、下位階層ブロック１０３について未処理の端子が存在しないと判定される（ステップＳ２２０のＹｅｓ）。
【００８９】
次に、未処理の下位階層ブロックが存在しないと判定され（ステップＳ２２１のＹｅｓ）、ステップＳ１１４の処理が完了する。
【００９０】
次に、ステップＳ２１３において、矩形領域Ｓを設定する処理の詳細について説明する。
【００９１】
入力端子は、出力端子の場合と異なり、下位階層ブロック内において、当該入力端子と接続されるセルが複数存在する場合がある。
【００９２】
図１０は、下位階層ブロック内の迂回配線経路を示す説明図である。下位階層ブロック１０２の入力端子２２が、下位階層ブロック１０２に属するセル１２１の近傍の座標に出力端子と同等の処理で配置されたとする。このとき、下位階層ブロック１０１に属するセル１１１からセル１２１までの配線経路Ｌは、迂回しない。一方、セル１１１から下位階層ブロック１０２に属するセル１３１までの配線経路Ｌ１は、下位階層ブロック１０２の領域内で迂回し、無駄に配線リソースを消耗する。
【００９３】
上記の場合、図１１に示すように、下位階層ブロック１０２に属するセルにおいて、入力端子２２と接続される複数のセル１２１，１３１を囲む矩形領域Ｓを設定する。そして、入力端子２２と接続される下位階層ブロック１０２以外の階層の下位階層ブロック１０１に属するセル１１１の座標と、矩形領域Ｓとの距離Ｄが算出される。入力端子２２は、距離Ｄが最短で、かつ、矩形領域Ｓの枠上の座標に仮配置される（ステップＳ２１３）。これにより、下位階層ブロック１０２の領域内で、迂回配線経路が発生することを抑制する。
【００９４】
次に、入力端子を下位階層ブロック領域内の座標に移動する処理（ステップＳ２１５）の詳細について説明する。
【００９５】
出力端子は、下位階層ブロックに属し、当該出力端子を駆動するセルの近傍の座標に配置される。したがって、出力端子は、下位階層ブロック領域外の座標に配置されることはない。一方、入力端子は、下位階層ブロックの形状が矩形でない場合には、下位階層ブロック領域外の座標に配置されることがある。このような場合には、各下位階層ブロックの配置配線を行う際に、下位階層ブロック外部との接続関係を認識することができなくなる。そこで、入力端子が下位階層ブロック領域外の座標に仮配置されたと判定された場合には（ステップＳ２１４のＹｅｓ）、仮配置された下位階層ブロックの入力端子の座標から距離が最も短い下位階層ブロック領域内の座標に、入力端子を移動する（ステップＳ２１５）。
【００９６】
図１２は、入力端子の移動（ステップＳ２１５）について説明するための図である。本実施形態によると、まず、入力端子２２は、図１２に示す座標に仮配置される（ステップＳ２１３）。図１２を参照すると、下位階層ブロック１０２の形状が矩形でないため、入力端子２２は下位階層ブロック１０２の領域外の座標に配置されている（ステップＳ２１４のＹｅｓ）。このとき、下位階層ブロック１０２の境界までの、水平方向距離Ｘ１および垂直方向距離Ｙ１の各々の距離が算出され、距離が短い方向に入力端子２２が移動される。図１２に示すように、Ｙ１＜Ｘ１である場合には、入力端子２２はＹ方向に移動される。すなわち、入力端子２２は、Ｙ座標に垂直方向距離Ｙ１を加算した入力端子２２０の座標に仮配置される（ステップＳ２１５）。
【００９７】
次に、入力端子および出力端子を配線禁止領域外の座標に移動する処理（ステップ２１７）の詳細について説明する。
【００９８】
端子の入出力属性に関係なく、下位階層ブロックの端子が配線禁止領域上の座標に配置されると、上位階層で下位階層ブロック間の配線ができなくなる。そこで、入力端子または出力端子の座標が配線禁止領域内に存在すると判定された場合には（ステップＳ２１６のＹｅｓ）、入力端子または出力端子を下位階層ブロック領域内の配線禁止領域外の座標に移動する（ステップＳ２１７）。
【００９９】
図１３は、入力端子の移動（ステップＳ２１７）について説明するための図である。図１３を参照すると、本実施形態において、入力端子２２は、図１３に示す座標に仮配置される（ステップＳ２１３）。入力端子２２の座標は、下位階層ブロック１０２領域内に存在する配線禁止領域ＢＲの領域内に存在する（ステップＳ２１６のＹｅｓ）。このとき、入力端子２２を基準に配線禁止領域ＢＲの枠に向かって、水平方向距離Ｘ１、Ｘ２および垂直方向距離Ｙ１、Ｙ２が算出され、水平方向と垂直方向の双方について、それぞれ距離が短い方に入力端子が移動される。図１３に示すように、Ｘ１＜Ｘ２，Ｙ１＜Ｙ２である場合には、Ｘ座標に水平方向距離Ｘ１、Ｙ座標に垂直方向距離Ｙ１を加算した入力端子２２０の座標に、入力端子が仮配置される（ステップＳ２１７）。なお、出力端子が配線禁止領域と重なった場合にも、同様の処理（ステップＳ２１７）が行われる。
【０１００】
本実施形態によると、複数の下位階層ブロックが接続されている場合にも、下位階層ブロック間の迂回配線経路を抑制することができる。
【０１０１】
実施形態に係る階層レイアウト設計方法によれば、下位階層ブロックの端子の位置を下位階層ブロックの領域内部に配置することで、図９に示したように、下位階層ブロック１０１（ないし下位階層ブロック１０１に属するセル１１１）から、下位階層ブロック１０３（ないし下位階層ブロック１０３に属するセル１３１）、および、下位階層ブロック１０４（ないし下位階層ブロック１０４に属するセル１４１）への２つの接続が、下位階層ブロック１０１を基準として、座標上で反対側に配置されていても、下位階層ブロック間の配線経路Ｌは、階層ブロック１０１から階層ブロック１０３までと、下位階層ブロック１０４までとの双方を最短で接続することができる。また、下位階層ブロック間の配線経路Ｌは、下位階層ブロック領域内（１０１，１０２等）を通過することで、迂回配線経路を抑制することができる。
【０１０２】
さらに、上位階層の配置配線（ステップＳ１１５）を下位階層ブロックの配置配線（ステップＳ１１７）よりも先に実施し、上位階層の配置配線情報を下位階層ブロック領域内で配置配線禁止領域に設定し（ステップＳ１１６）、下位階層ブロックの配置配線の際に上位階層の配線の影響を考慮することで（ステップＳ１１７）、下位階層ブロック内のタイミング設計に反映することが好ましい。したがって、上位階層の配線が下位階層ブロック領域内を通過していても、タイミングに関する問題が生じない。
【０１０３】
なお、上記の特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１０４】
１ ＣＰＵ（中央処理装置）
２ メモリ
３ 記憶装置
４ 表示装置
５ 入力装置
６ ドライブ装置
７ バス
８ 記憶媒体
１０ 上位階層に属するセル
２１ 出力端子
２２，２３，２４ 入力端子
３１ 出力端子配置部
３２ 入力端子配置部
３３，３６ 配線禁止領域設定部
３５ 上位階層配線部
３７ 下位階層配線部
１００，４００ チップ領域
１０１，１０２，１０３，１０４，４０１，４０２，４０３，４０４ 下位階層ブロック
１１１，１２１，１３１，１４１，４１１，４３１，４４１ セル
１１２，１２２，１３２，１４２，４１２，４３２，４４２ 境界（バウンダリ）
２２０ 移動後の入力端子
２１３ レイアウト情報
４１０，４３０，４４０ 端子
ＢＰ 配置禁止領域
ＢＲ 配線禁止領域
Ｄ 距離
ｄ１，ｄ２ 所定距離
Ｌ 下位階層ブロック間配線経路
Ｌ１ 迂回配線経路
Ｐａ 第１の仮配線上ポイント
Ｐｂ 第１のバウンダリポイント
Ｐｃ 第２の仮配線経路上ポイント
Ｐｄ 第２のバウンダリポイント
Ｒ０ 端子位置決定前の仮配線経路
Ｒ１，Ｒ２，Ｒ３，Ｒ４ セル間仮配線経路
Ｓ 矩形領域
Ｘ，Ｙ 端子位置
Ｘ１，Ｘ２ 水平方向距離
Ｙ１，Ｙ２ 垂直方向距離
【特許請求の範囲】
【請求項１】
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する出力端子配置部と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する入力端子配置部と、を備えていることを特徴とする階層レイアウト設計装置。
【請求項２】
前記入力端子配置部は、前記入力端子が前記第２の下位階層ブロックの領域外に配置された場合には、前記第２の下位階層ブロックの領域内であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動することを特徴とする、請求項１に記載の階層レイアウト設計装置。
【請求項３】
前記出力端子配置部は、前記出力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記出力端子の配置箇所からの距離が最短の箇所へ、前記出力端子を移動することを特徴とする、請求項１または２に記載の階層レイアウト設計装置。
【請求項４】
前記入力端子配置部は、前記入力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動することを特徴とする、請求項１ないし３のいずれか１項に記載の階層レイアウト設計装置。
【請求項５】
前記出力端子を配置した領域を前記第１の下位階層ブロックに配線禁止領域として設定するとともに、前記入力端子を配置した領域を前記第２の下位階層ブロックに配線禁止領域として設定する第１の配線禁止領域設定部を備えていることを特徴とする、請求項１ないし４のいずれか１項に記載のレイアウト設計装置。
【請求項６】
前記第１の下位階層ブロックに配置された前記出力端子と、前記第２の下位階層ブロックに設けられた前記入力端子との間を配線する上位階層配線部と、
前記配線に用いられた領域を前記第１の下位階層ブロックおよび前記第２の下位階層ブロックに配線禁止領域として設定する第２の配線禁止領域設定部と、
前記第２の配線禁止領域設定部により設定された配線禁止領域を回避しつつ、前記第１の下位階層ブロックおよび前記第２の下位階層ブロックにおける配線を実施する下位階層配線部と、を備えていることを特徴とする、請求項１ないし５のいずれか１項に記載の階層レイアウト設計装置。
【請求項７】
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する工程と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する工程と、を含むことを特徴とする階層レイアウト設計方法。
【請求項８】
前記入力端子が前記第２の下位階層ブロックの領域外に配置された場合には、前記第２の下位階層ブロックの領域内であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動する工程を含むことを特徴とする、請求項７に記載の階層レイアウト設計方法。
【請求項９】
前記出力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記出力端子の配置箇所からの距離が最短の箇所へ、前記出力端子を移動する工程を含むことを特徴とする、請求項７または８に記載の階層レイアウト設計方法。
【請求項１０】
前記入力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動する工程を含むことを特徴とする、請求項７ないし９のいずれか１項に記載の階層レイアウト設計方法。
【請求項１１】
前記出力端子を配置した領域を前記第１の下位階層ブロックに配線禁止領域として設定する工程と、
前記入力端子を配置した領域を前記第２の下位配線ブロックに配線禁止領域として設定する工程と、を含むことを特徴とする、請求項７ないし１０のいずれか１項に記載のレイアウト設計方法。
【請求項１２】
前記第１の下位階層ブロックに配置された前記出力端子と、前記第２の下位階層ブロックに設けられた前記入力端子との間を配線する工程と、
前記配線に用いられた領域を前記第１の下位階層ブロックおよび前記第２の下位階層ブロックに配線禁止領域として設定する工程と、
設定された配線禁止領域を回避しつつ、前記第１の下位階層ブロックおよび前記第２の下位階層ブロックにおける配線を実施する工程と、を含むことを特徴とする、請求項７ないし１１のいずれか１項に記載の階層レイアウト設計方法。
【請求項１３】
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する処理と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する処理と、をコンピュータに実行させることを特徴とするプログラム。
【請求項１４】
前記入力端子が前記第２の下位階層ブロックの領域外に配置された場合には、前記第２の下位階層ブロックの領域内であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動する処理を、コンピュータに実行させることを特徴とする、請求項１３に記載のプログラム。
【請求項１５】
前記出力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記出力端子の配置箇所からの距離が最短の箇所へ、前記出力端子を移動する処理を、コンピュータに実行させることを特徴とする、請求項１３または１４に記載のプログラム。
【請求項１６】
前記入力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動する処理を、コンピュータに実行させることを特徴とする、請求項１３ないし１５のいずれか１項に記載のプログラム。
【請求項１】
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する出力端子配置部と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する入力端子配置部と、を備えていることを特徴とする階層レイアウト設計装置。
【請求項２】
前記入力端子配置部は、前記入力端子が前記第２の下位階層ブロックの領域外に配置された場合には、前記第２の下位階層ブロックの領域内であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動することを特徴とする、請求項１に記載の階層レイアウト設計装置。
【請求項３】
前記出力端子配置部は、前記出力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記出力端子の配置箇所からの距離が最短の箇所へ、前記出力端子を移動することを特徴とする、請求項１または２に記載の階層レイアウト設計装置。
【請求項４】
前記入力端子配置部は、前記入力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動することを特徴とする、請求項１ないし３のいずれか１項に記載の階層レイアウト設計装置。
【請求項５】
前記出力端子を配置した領域を前記第１の下位階層ブロックに配線禁止領域として設定するとともに、前記入力端子を配置した領域を前記第２の下位階層ブロックに配線禁止領域として設定する第１の配線禁止領域設定部を備えていることを特徴とする、請求項１ないし４のいずれか１項に記載のレイアウト設計装置。
【請求項６】
前記第１の下位階層ブロックに配置された前記出力端子と、前記第２の下位階層ブロックに設けられた前記入力端子との間を配線する上位階層配線部と、
前記配線に用いられた領域を前記第１の下位階層ブロックおよび前記第２の下位階層ブロックに配線禁止領域として設定する第２の配線禁止領域設定部と、
前記第２の配線禁止領域設定部により設定された配線禁止領域を回避しつつ、前記第１の下位階層ブロックおよび前記第２の下位階層ブロックにおける配線を実施する下位階層配線部と、を備えていることを特徴とする、請求項１ないし５のいずれか１項に記載の階層レイアウト設計装置。
【請求項７】
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する工程と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する工程と、を含むことを特徴とする階層レイアウト設計方法。
【請求項８】
前記入力端子が前記第２の下位階層ブロックの領域外に配置された場合には、前記第２の下位階層ブロックの領域内であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動する工程を含むことを特徴とする、請求項７に記載の階層レイアウト設計方法。
【請求項９】
前記出力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記出力端子の配置箇所からの距離が最短の箇所へ、前記出力端子を移動する工程を含むことを特徴とする、請求項７または８に記載の階層レイアウト設計方法。
【請求項１０】
前記入力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動する工程を含むことを特徴とする、請求項７ないし９のいずれか１項に記載の階層レイアウト設計方法。
【請求項１１】
前記出力端子を配置した領域を前記第１の下位階層ブロックに配線禁止領域として設定する工程と、
前記入力端子を配置した領域を前記第２の下位配線ブロックに配線禁止領域として設定する工程と、を含むことを特徴とする、請求項７ないし１０のいずれか１項に記載のレイアウト設計方法。
【請求項１２】
前記第１の下位階層ブロックに配置された前記出力端子と、前記第２の下位階層ブロックに設けられた前記入力端子との間を配線する工程と、
前記配線に用いられた領域を前記第１の下位階層ブロックおよび前記第２の下位階層ブロックに配線禁止領域として設定する工程と、
設定された配線禁止領域を回避しつつ、前記第１の下位階層ブロックおよび前記第２の下位階層ブロックにおける配線を実施する工程と、を含むことを特徴とする、請求項７ないし１１のいずれか１項に記載の階層レイアウト設計方法。
【請求項１３】
第１の下位階層ブロックに含まれるセルから出力された信号を受信する出力端子を該セルの近傍に配置する処理と、
第２の下位階層ブロックに含まれる複数のセルへ前記出力端子から出力された信号を供給する入力端子を、該複数のセルを囲む最小の矩形領域の境界上であって、前記出力端子が配置された箇所からの距離が最短の箇所に配置する処理と、をコンピュータに実行させることを特徴とするプログラム。
【請求項１４】
前記入力端子が前記第２の下位階層ブロックの領域外に配置された場合には、前記第２の下位階層ブロックの領域内であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動する処理を、コンピュータに実行させることを特徴とする、請求項１３に記載のプログラム。
【請求項１５】
前記出力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記出力端子の配置箇所からの距離が最短の箇所へ、前記出力端子を移動する処理を、コンピュータに実行させることを特徴とする、請求項１３または１４に記載のプログラム。
【請求項１６】
前記入力端子が配線禁止領域に配置された場合には、該配線禁止領域外であって前記入力端子の配置箇所からの距離が最短の箇所へ、前記入力端子を移動する処理を、コンピュータに実行させることを特徴とする、請求項１３ないし１５のいずれか１項に記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２０１２−１６８６６７（Ｐ２０１２−１６８６６７Ａ）
【公開日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願番号】特願２０１１−２８０３７（Ｐ２０１１−２８０３７）
【出願日】平成２３年２月１４日（２０１１．２．１４）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
【公開日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願日】平成２３年２月１４日（２０１１．２．１４）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
[ Back to top ]