JPH09283629A - 半導体集積回路の論理素子配置処理方法 - Google Patents

Abstract

(57)【要約】 【課題】本発明の目的は、半導体集積回路の動作速度に
関して、より最適な半導体集積回路の論理素子配置が行
える半導体集積回路の論理素子配置処理方法を提供する
にある。 【解決手段】論理ブロック単位に論理分割して階層的に
論理設計されている論理素子群の各論理素子を、半導体
集積回路の基板上に配置する。そのために、配置位置指
示処理部１１０によって、半導体集積回路の基板上を領
域分割し、この分割された領域の中の特定の領域に、論
理素子もしくは論理ブロックからなる論理素子群の中の
特定の論理素子群を対応づけて配置位置を指示する。さ
らに、論理素子（群）配置処理部１２０は、この配置位
置の指示に基づいて、特定の論理素子群を基板上に配置
し、さらに、他の論理素子を基板上に配置する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、半導体集積回路の
論理素子配置処理方法に係り、特に、信号伝播遅延時間
に関して論理素子の最適配置をする半導体集積回路の論
理素子配置処理方法に関する。

【０００２】

【従来の技術】半導体集積回路の論理素子を配置する処
理方法としては、従来は、例えば、米国特許第４５７７
２７６号明細書に記載されているものが知られている。
この方式は、エッジプロパゲーション法と呼ばれてお
り、基板上の論理素子の配置領域を領域分割し、それぞ
れの領域に配置する論理素子を決定する処理を繰り返し
実行して論理素子の配置を行うものである。

【０００３】また、例えば、２７ｔｈ ＡＣＭ／ＩＥＥ
Ｅ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ Ｃｏｎｆｅ
ｒｅｎｃｅ Ｐａｐｅｒ ６．１ ”ＴＩＭＩＮＧ Ｄ
ＲＩＶＥＮ ＰＬＡＣＥＭＥＮＴ ＵＳＩＮＧ ＣＯＭ
ＰＵＴＥＲ ＰＡＴＨ ＤＥＬＡＹＳ”に記載されてい
るように、基板上の論理素子を配置する領域をサブ領域
まで分割し、論理素子群をサブ論理ブロックに分割し、
それらのサブ論理ブロックをサブ領域に対して対応付け
し、この対応関係に基づいて、サブ論理ブロックに属す
る論理素子群をサブ領域に配置することによって、半導
体集積回路の基板上における論理素子の配置を行うもの
である。

【０００４】

【発明が解決しようとする課題】しかしながら、上述し
た２つの従来の方式は、いずれも、論理素子間の配線長
を短縮することを目的としたものである。半導体集積回
路の動作速度を律速するのは、特定の論理素子間の結線
に係る信号伝播遅延時間であり、論理素子間の全ての配
線長を短くしようとする従来技術では、半導体集積回路
の動作速度に関して必ずしも最適の配置結果を得られな
いという問題があった。

【０００５】本発明の目的は、半導体集積回路の動作速
度に関して、より最適な半導体集積回路の論理素子配置
が行える半導体集積回路の論理素子配置処理方法を提供
するにある。

【０００６】

【課題を解決するための手段】上記目的を達成するため
に、本発明は、論理ブロック単位に論理分割して階層的
に論理設計されている論理素子群の各論理素子を、半導
体集積回路の基板上に配置する半導体集積回路の論理素
子配置処理方法において、上記半導体集積回路の基板上
を領域分割し、この分割された領域の中の特定の領域
に、論理素子もしくは論理ブロックからなる論理素子群
の中の特定の論理素子群を対応づけて配置位置を指示
し、次に、この配置位置の指示に基づいて、上記特定の
論理素子群を上記基板上に配置し、さらに、他の論理素
子を上記基板上に配置するようにしたものであり、かか
る方法により、半導体集積回路の動作速度を向上し得る
ものとなる。

【０００７】上記半導体集積回路の論理素子配置処理方
法において、好ましくは、上記領域分割は、上記基板平
面上の位置を記述する任意の２次元座標系において、領
域を分割する境界線の座標，領域を分割する個数若しく
は領域を分割する座標幅に基づいてなされるようにした
ものである。

【０００８】上記半導体集積回路の論理素子配置処理方
法において、好ましくは、上記領域分割は、分割前の全
領域，分割された領域に対して、さらに、階層的若しく
は多重的に繰り返しなされるようにしたものであり、か
かる方法により、大きさの異なる論理素子や論理ブロッ
クを同一のレベルで処理し得るものとなる。

【０００９】上記半導体集積回路の論理素子配置処理方
法において、好ましくは、上記配置位置の指示は、上記
階層的な領域分割により生成された親子関係を持つ分割
領域と、論理的に親子関係を持つ論理素子と論理素子群
とを、それぞれ対応づけて行うようにしたものである。

【００１０】上記半導体集積回路の論理素子配置処理方
法において、好ましくは、上記基板上への論理素子群の
配置は、上記配置位置の指示の際に使用する領域を分割
する分割線を基準として行うようにしたものであり、か
かる方法により、自動配置処理において配置指示を確実
に守らせ得るものとなる。

【００１１】

【発明の実施の形態】以下、本発明の一実施の形態によ
る半導体集積回路の論理素子配置処理方法について、図
１乃至図１３を用いて説明する。図１は、本発明の一実
施の形態による半導体集積回路の論理素子配置処理方法
を実現するシステムのブロック図であり、図２は、本発
明の一実施の形態による半導体集積回路の論理素子配置
処理方法における論理素子（群）の配置位置指示処理を
示すフローチャートである。

【００１２】図１において、本発明の一実施の形態によ
る半導体集積回路の論理素子配置処理方法を実現するシ
ステムは、論理素子もしくは論理ブロック等の論理素子
群の配置位置を指示する配置位置指示処理部１１０と、
配置位置指示処理部１１０において、指示された配置位
置を守って基板上への論理素子（群）を配置する処理を
行う配置処理部１２０から構成されている。配置位置指
示処理部１１０の処理については、図２に示すフローチ
ャートを用いて後述する。

【００１３】配置処理部１２０は、さらに、配置位置決
定のための分割線処理部１２２と、分割領域への割り付
け処理部１２４と、分割領域内での再分割処理部１２６
から構成されている。分割線処理部１２２の処理につい
ては、図１０に示すフローチャートを用いて後述する。
割り付け処理部１２４の処理については、図１３に示す
フローチャートの前半のステップ１３０１，…，１３０
５を用いて後述する。再分割処理部１２６の処理につい
ては、図１３に示すフローチャートの後半のステップ１
３０６，…，１３１０を用いて後述する。

【００１４】次に、図２を用いて、論理素子（群）の配
置位置指示処理部１１０の処理について説明する。配置
位置指示処理部１１０は、論理素子もしくは論理ブロッ
ク等の論理素子群の配置位置を指示し、自動配置システ
ムを起動する。

【００１５】ステップ２０１において、配置位置指示処
理部１１０は、半導体集積回路の基板上を領域分割し、
領域定義カードを作成する。

【００１６】ここで、半導体集積回路の基板上の領域分
割について、図３を用いて説明し、領域定義カードにつ
いて、図４を用いて説明する。図３は、本発明の一実施
の形態による半導体集積回路の論理素子配置処理方法に
おける半導体集積回路の基板上の領域分割の説明図であ
り、図４は、本発明の一実施の形態による半導体集積回
路の論理素子配置処理方法において用いる領域定義カー
ドの説明図である。

【００１７】図３に示すように、半導体集積回路の基板
上を、階層的に領域分割される。この例では、基板平面
上の位置を記述するための２次元座標系として、図に示
したように、最も一般的な直交するＸ／Ｙの２軸を用い
ている。基板平面は、Ｘ１からＸ４までと、Ｙ１からＹ
４までの太線で示される領域に展開しているものとす
る。

【００１８】分割領域を定義するやり方として、分割数
を指定して分割する方法をとるものとしている。ここで
は、基板平面をＸ軸方向及びＹ軸方向について、それぞ
れ、３分割するものとする。

【００１９】ＭＥＳＨ１は、基板全体をＸ／Ｙ軸の両方
向ともに３等分する領域を表わしている。基板全体の形
状を示す座標Ｘ１，Ｘ４，Ｙ１，Ｙ４を予め与えられて
おけば、Ｘ軸方向の幅（Ｘ４−Ｘ１）を３等分して座標
Ｘ２とＸ３が計算でき、また、Ｙ軸方向の幅（Ｙ４−Ｙ
１）を３等分して座標Ｙ２とＹ３が計算できるため、分
割数を指定するだけで分割領域の定義が可能となる。即
ち、Ｘ２＝（Ｘ４−Ｘ１）／３，Ｘ３＝２・（Ｘ４−Ｘ
１）／３の座標で表され、Ｙ２＝（Ｙ４−Ｙ１）／３，
Ｙ３＝２・（Ｙ４−Ｙ１）／３の座標で表される。

【００２０】ＭＥＳＨ−２は、ＭＥＳＨ−１の中の右上
の領域，即ち、Ｘ３からＸ４までと、Ｙ３からＹ４まで
によって定義される領域を、Ｘ軸方向に２分割し、Ｙ軸
方向に３分割する領域を表している。ＭＥＳＨ−２のＸ
軸方向の分割線の座標をＸ５とする。また、ＭＥＳＨ−
２のＹ軸方向の分割線の座標を、それぞれ、Ｙ５，Ｙ６
とする。

【００２１】ＭＥＳＨ−３は、ＭＥＳＨ−１の中の左側
中央の領域，即ち、Ｘ１からＸ２までと、Ｙ２からＹ３
までによって定義される領域を、Ｘ軸方向に３分割し、
Ｙ軸方向に２分割する領域を表している。ＭＥＳＨ−３
のＸ軸方向の分割線の座標を、それぞれ、Ｘ６，Ｘ７と
する。また、ＭＥＳＨ−３のＹ軸方向の分割線の座標を
Ｙ７とする。

【００２２】ＭＥＳＨ−４は、ＭＥＳＨ−２の左下の領
域，即ち、Ｘ３からＸ５までと、Ｙ３からＹ５までによ
って定義される領域を、Ｘ軸方向に２分割し、Ｙ軸方向
に２分割する領域を表している。ＭＥＳＨ−４のＸ軸方
向の分割線の座標をＸ８とする。また、ＭＥＳＨ−４の
Ｙ軸方向の分割線の座標をＹ８とする。

【００２３】以上のようにして、大きな分割領域の一つ
の領域を、さらに、再分割し、再分割された領域の一つ
をさらに、分割するというように、階層構造にて、領域
分割を行う。図示した例では、ＭＥＳＨ−４が最小分割
領域であり、Ｘ軸方向を１２分割し、Ｙ軸方向を１８分
割したものであるが、これは、説明の都合上であり、実
際には、さらに、小さな領域まで、階層分割を行う。そ
して、最小の分割領域の大きさは、一つの論理素子が配
置される大きさ程度まで分割を行う。

【００２４】次に、図４を用いて、領域定義カードの指
定例について説明する。「ＭＥＳＨＤＥＦ＝ＭＥＳＨ
１」は、ＭＥＳＨＤＥＦカードでＭＥＳＨ１を定義する
ことを宣言している。この宣言に続く「ＣＨＩＰ＝
（３，３）」は、基板（ＣＨＩＰ）全体を、Ｘ／Ｙ軸の
両方向ともに３等分することを示している。この２つの
領域定義カードによって、図３に示したＭＥＳＨ−１の
分割領域が定義される。

【００２５】「ＭＥＳＨＤＥＦ＝ＭＥＳＨ２」は、ＭＥ
ＳＨＤＥＦカードでＭＥＳＨ２を定義することを宣言し
ている。この宣言に続く「ＭＥＳＨ１（３，３）＝
（２，３）」において、左辺は、先に定義したＭＥＳＨ
１のＸ／Ｙ軸の両方向ともに、原点側から数えて３番目
の領域を分割することを示し、右辺は、その指定された
領域をＸ軸方向に２分割し、Ｙ軸方向に３分割すること
を示している。この２つの領域定義カードによって、図
３に示したＭＥＳＨ−２の分割領域が定義される。

【００２６】「ＭＥＳＨＤＥＦ＝ＭＥＳＨ３」は、ＭＥ
ＳＨＤＥＦカードでＭＥＳＨ３を定義することを宣言し
ている。この宣言に続く「ＭＥＳＨ１（１，２）＝
（３，２）」において、左辺は、先に定義したＭＥＳＨ
１のＸ軸方向は、原点側から数えて１番目で、Ｙ軸方向
は、原点側から数えて２番目の領域を分割することを示
し、右辺は、その指定された領域をＸ軸方向に３分割
し、Ｙ軸方向に２分割することを示している。この２つ
の領域定義カードによって、図３に示したＭＥＳＨ−３
の分割領域が定義される。

【００２７】「ＭＥＳＨＤＥＦ＝ＭＥＳＨ４」は、ＭＥ
ＳＨＤＥＦカードでＭＥＳＨ４を定義することを宣言し
ている。この宣言に続く「ＭＥＳＨ２（１，１）＝
（２，２）」において、左辺は、先に定義したＭＥＳＨ
２のＸ／Ｙ軸の両方向に、原点側から数えて１番目の領
域を分割することを示し、右辺は、その指定された領域
をＸ軸方向に２分割し、Ｙ軸方向に２分割することを示
している。この２つの領域定義カードによって、図３に
示したＭＥＳＨ−４の分割領域が定義される。

【００２８】このように、任意の階層、任意の分割数で
の領域定義が、本実施の形態では可能であり、定義した
分割領域を２次元配列に見立てて、例えば、ＭＥＳＨ１
のＸ／Ｙ両方向ともに３番目の領域をＭＥＳＨ１（３，
３）と名付けている。

【００２９】以上のような領域定義カードによって、図
３に示したような階層領域分割が定義できる。

【００３０】なお、図３に示した例では、ＭＥＳＨ２を
表わすのに、ＭＥＳＨ１の（３，３）の領域のみをＸ方
向に２分割、Ｙ方向に３分割して定義したが、基板全体
をＸ方向に６分割、Ｙ方向に９分割して定義しても、同
じ領域が定義できる。このように同じ領域を違う分割形
状で多重的に定義しても、階層的な領域分割を取り扱う
ことができる。

【００３１】また、図３に示した例では、基板平面上の
位置を記述するための２次元座標系として、最も一般的
な直交するＸ／Ｙの２軸を用いているが、これに代え
て、対象とする基板および論理素子の形状や配線の走る
方向に応じて、Ｘ／Ｙ軸を原点Ｏを中心に回転させたも
のや、Ｘ／Ｙ軸が直交しないものや、あるいは、Ｘ／Ｙ
軸の代わりに原点からの距離とある基準方向からの角度
を用いたものも使用可能である。

【００３２】また、分割領域を定義するやり方として、
分割数を指定して分割する方法をとるものとしている
が、これに代えて、分割幅を指定して分割する方法や、
分割境界の座標を指定して分割する方法や、以上の３種
類を組み合わせて分割する方法も使用可能である。

【００３３】分割幅を指定して分割するやり方によれ
ば、Ｘ方向の分割幅ＷＸとＹ方向の分割幅ＷＹを与えれ
ば、それぞれＸ１とＹ１から順番にＷＸとＷＹを加えて
いくやり方で座標Ｘ２，Ｘ３，Ｙ２，Ｙ３が計算できる
ため、分割幅を指定するだけで分割領域の定義が可能と
なる。このとき、分割数で割っていったときに余りが出
る場合や、分割幅で区切っていったときに最後に分割幅
以下の領域ができてしまう場合などがあるので、厳密に
は等分割にはならない。

【００３４】また、半導体集積回路の基板上で論理素子
の配置できる場所が、論理素子の基本回路構造の整数倍
の位置に限定されている場合には、分割境界の座標をこ
の位置に合わせて修正する必要もある。しかし、計算法
を決めておけば一意に分割領域が決まるので、簡単な分
割領域の定義法として有効である。

【００３５】もちろん、分割境界の座標Ｘ２、Ｘ３、Ｙ
２、Ｙ３を個別に指定して分割することも可能である。

【００３６】領域定義カードとしては、分割幅を指定し
て分割する方法では、定義例の「＝（３，３）」の代わ
りに「＝ＷＩＤＴＨ（５０，６０）」と指定すれば、Ｘ
方向の分割幅を５０、Ｙ方向の分割幅を６０で分割する
ことを指示できる。また、分割境界の座標を指定して分
割する方法では、定義例の「＝（３，３）」の代わりに
「＝（Ｘ，Ｙ）」と指定して、その分割定義カードの下
に「Ｘ＝１００，２００」の分割定義カードと「Ｙ＝１
５０，３００」の分割定義カードの２枚のカードを入れ
れば、Ｘ方向の分割境界の座標を１００と２００、Ｙ方
向の分割境界の座標を１５０と３００として分割するこ
とを指示できる。

【００３７】次に、図２に戻って、ステップ２０２にお
いて、配置位置指示処理部１１０は、論理ブロック以外
の単位で論理素子群を定義したいか否かを判断し、論理
ブロック以外の単位で論理素子群を定義したい場合は、
ステップ２０３に進む。定義したくない場合には、ステ
ップ２０４に進む。

【００３８】ステップ２０３において、配置位置指示処
理部１１０は、予め論理素子もしくは論理ブロックをま
とめてグループ化し、グループ定義カードを作成する。

【００３９】ここで、論理素子をまとめてグループ化す
る場合について、図５を用いて説明する。図５は、本発
明の一実施の形態による半導体集積回路の論理素子配置
処理方法において用いるグループ化の説明図である。

【００４０】論理素子であるアンド回路ＣＥＬＬ Ｃ，
フリップフロップ回路ＣＥＬＬ Ｄ，及びアンド回路Ｃ
ＥＬＬ Ｅが、図示のように接続されている場合に、こ
れらを個別の論理素子として配置指定するようにしても
よいが、これをグループ化して配置指定した方が都合の
よい場合には、これをグループ化して定義するようにし
ている。

【００４１】次に、グループ定義カードについて、図６
を用いて説明する。図６は、本発明の一実施の形態によ
る半導体集積回路の論理素子配置処理方法において用い
るグループ定義カードの説明図である。

【００４２】「ＧＲＯＵＰＤＥＦ」は、グループを定義
することを宣言している。この宣言に続く「ＧＲＯＵＰ
Ｂ＝ＣＥＬＬ Ｃ，ＣＥＬＬ Ｄ，ＣＥＬＬ Ｅ」
は、グループＢが、論理素子Ｃと論理素子Ｄと論理素子
Ｅから構成されることが定義される。

【００４３】以上のようにして、グループ化して配置指
定した方が都合のよい場合には、グループ定義カードに
よって、グループ化して定義するようにしている。

【００４４】次に、図２に戻って、ステップ２０４にお
いて、配置位置指示処理部１１０は、論理素子群を領域
に対応づけ、配置指示カードを作成する。ここで、論理
素子群を分割された領域に対応づけする方法について、
図７、図８を用いて説明する。図７は、論理素子群の説
明図であり、図８は、本発明の一実施の形態による半導
体集積回路の論理素子配置処理方法において指定される
領域の説明図である。

【００４５】図７に示すように、論理ブロックＢｌｏ．
Ａは、ｎ個の論理素子Ａ１，…，Ａｎから構成されてい
るとする。論理ブロックＢｌｏ．Ｂは、ｍ個の論理素子
Ｂ１，Ｂ２，…Ｂｍから構成されているとする。論理ブ
ロックＢｌｏ．Ｃは、ｐ個の論理素子Ｃ１，…Ｃｐから
構成されているとする。論理グループＧｒ．Ｂは、論理
素子Ｃ，Ｄ，Ｅから構成されているとする。論理ブロッ
クＢｌｏ．Ｄは、論理素子Ｄ１，Ｄ２から構成されてい
るとする。

【００４６】ここで、半導体集積回路の動作速度を考慮
して、特定の論理素子（群）の配置を検討する。論理ブ
ロックＢｌｏ．Ａは、基板の複数の入力端子の内のほぼ
中央に位置する入力端子ＩＮ２から信号が入力され、基
板の複数の出力端子の内のほぼ中央に位置する出力端子
ＯＵＴ２から出力するように配置するのが適当であると
して、図７に示すように、基板のほぼ中央に配置したい
ものとする。

【００４７】また、論理ブロックＢｌｏ．Ｂは、基板の
左上の入力端子ＩＮ１から信号が入力されるものとし、
論理ブロックＢｌｏ．Ｃは、基板の左下の入力端子ＩＮ
３から信号が入力されるものとすると、論理ブロックＢ
ｌｏ．Ｂ及び論理ブロックＢｌｏ．Ｃは、図７に示すよ
うな位置に配置したいものとする。さらに、論理グルー
プＧｒ．Ｂの中の論理素子Ｃは、論理ブロックＢｌｏ．
Ｂの出力信号と、論理ブロックＢｌｏ．Ｃの出力信号の
アンドをとるものとすると、論理素子Ｃの位置は、論理
ブロックＢｌｏ．Ｂと論理ブロックＢｌｏ．Ｃと論理グ
ループＧｒ．Ｂのバランスの中点に配置することが好ま
しく、図７に示すような位置に配置したいものとする。

【００４８】また、論理ブロックＢｌｏ．Ｄは、その入
力信号を論理グループＧｒ．Ｂの出力信号とし、その出
力信号を基板の右上の出力端子ＯＵＴ１から出力するも
のとすると、図７に示すような位置に配置したいものと
する。

【００４９】以上のようにして、信号伝播遅延時間が少
なくなり、動作速度が早くなるような配置を検討した結
果、図７に示すような大まかな配置が決定したものとす
る。

【００５０】次に、配置位置の指示について、図８を用
いて説明する。以上のような検討結果に基づいて、配置
位置を指示する。即ち、論理ブロックＢｌｏ．Ａは、基
板のほぼ中央に配置すればよく、図８の領域Ａに配置を
指示すればよい。また、論理グループＧｒ．Ｂは、基板
の右上に配置すればよく、図８の領域Ｂに配置を指示す
ればよい。ここで、論理グループＧｒ．Ｂの中の論理素
子Ｃは、特に、図８の領域Ｂの中でも、領域Ｃに配置す
るのが好適である。

【００５１】次に、図９を用いて、上述した領域定義を
使用して、論理素子もしくは論理ブロック等の論理素子
群の配置位置を指示するための、配置指示カードについ
て説明する。図９は、本発明の一実施の形態による半導
体集積回路の論理素子配置処理方法において用いる配置
指示定義カードの説明図である。

【００５２】配置指示カードでは、先程名付けた分割領
域の名称と論理素子もしくは論理ブロック等の論理素子
群の名称を”＝”で結んで対応づけることにより、配置
位置を指示するようにしている。

【００５３】最初の配置指示カード「ＰＬＡＣＥ」は、
論理素子群の配置位置の指示を定義している。次の配置
指示カード「ＢＬＯＣＫ Ａ＝ＭＥＳＨ１ （２，
２）」は、ＢＬＯＣＫ Ａという名称の論理ブロック
を、ＭＥＳＨ１のＸ／Ｙ軸の両方向に原点から２番目の
領域位置（図８の領域Ａ）に配置指示している。

【００５４】また、配置指示カード「ＧＲＯＵＰ Ｂ＝
ＭＥＳＨ２ （１，１）」は、ＧＲＯＵＰ Ｂという名
称の論理素子群を、ＭＥＳＨ２のＸ／Ｙ軸の両方向に原
点から１番目の領域位置（図８の領域Ｂ）に配置指示し
ている。

【００５５】さらに、配置指示カード「ＣＥＬＬ Ｃ＝
ＭＥＳＨ４ （１，２）は、ＣＥＬＬ Ｃという論理素
子を、ＭＥＳＨ４のＸ軸方向に１番目で、Ｙ軸方向に２
番目の領域位置（図８の領域Ｃ）に配置指示している。

【００５６】ここで、ＧＲＯＵＰ Ｂという名称の論理
素子群は、図６に示したグループ指示の定義カードによ
り、ＣＥＬＬ Ｃ，ＣＥＬＬ Ｄ，ＣＥＬＬ Ｅという
名称の論理素子から構成されていることがわかる。ここ
で、ＣＥＬＬ Ｃを含むＧＲＯＵＰ Ｂという名称の論
理素子群は、図８の領域Ｂに配置することを指示され、
その中でも特にＣＥＬＬ Ｃは、領域Ｂの左上の部分に
当たる図８の領域Ｃに配置するよう指示されている。す
なわち、階層的な領域分割により生成された親子関係を
持つ分割領域と、同じく論理的に親子関係を持つ論理素
子もしくは論理素子群とをそれぞれ対応づけることによ
り、異なる論理階層の論理素子の配置指示が一括して行
われている。これにより、論理素子もしくは論理素子群
を半導体集積回路の基板上の特定の位置に対応づけるこ
とができ、配置位置の指示が可能となる。

【００５７】次に、図２に戻って、ステップ２０５にお
いて、配置位置指示処理部１１０は、それまでに作成し
たカードを配置指示情報格納用のファイルに格納する。

【００５８】以上の準備を行った後、ステップ２０６に
おいて、配置位置指示処理部１１０は、自動配置システ
ムを起動する。

【００５９】図４，図６，図９に示したカードは、全て
配置指示情報格納用のファイルに収めて、自動配置シス
テムが読み込みを行う。また、配置指示情報ファイル
は、カードイメージファイルを用いることで、汎用的な
エディタにより作成、編集が可能である。以上により、
論理素子もしくは論理素子群の配置位置を外部より指示
し、自動配置システムを起動するまでを行うことができ
る。

【００６０】次に、論理素子（群）配置処理部１２０の
処理について、図１０，図１１，図１２，図１３，図１
４を用いて説明する。図１０は、本発明の一実施の形態
による半導体集積回路の論理素子配置処理方法における
論理素子群の配置処理を示すフローチャートであり、図
１１は、本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法において用いる座標テーブルの構
成図であり、図１２は、本発明の一実施の形態による半
導体集積回路の論理素子配置処理方法において用いる分
割順序テーブルの構成図であり、図１３は、本発明の一
実施の形態による半導体集積回路の論理素子配置処理方
法における論理素子群の配置処理を示す図１０に続くフ
ローチャートであり、図１４は、本発明の一実施の形態
による半導体集積回路の論理素子配置処理方法における
論理素子群の配置処理において用いる分割領域テーブル
の構成図である。

【００６１】図１０は、配置指示情報ファイルを読み込
み、読み込まれた領域定義情報より、後続の配置処理で
用いる分割順序テーブルを作成するまでの処理フローを
示している。

【００６２】図１０のステップ１００１において、論理
素子（群）配置処理部１２０の分割線決定処理部１２２
は、配置指示の有無が判断される。配置指示がある場合
は、ステップ１００２に進み、配置指示がない場合に
は、ステップ１００５に進む。

【００６３】配置指示があると、ステップ１００２にお
いて、分割線決定処理部１２２は、配置指示情報ファイ
ルより、領域定義，グループ定義，配置指示情報を読み
込む。領域定義は、図４に示されたように配置指示情報
ファイルに格納されており、グループ定義は、図６に示
されたように配置指示情報ファイルに格納されており、
配置指示情報は、図９に示されたように配置指示情報フ
ァイルに格納されている。

【００６４】ステップ１００３において、分割線決定処
理部１２２は、読み込んだ領域定義を基に、全ての領域
分割線の位置を計算して求め、Ｘ座標／Ｙ座標別に座標
テーブルに登録する。

【００６５】ここで、図１１を用いて、Ｘ座標／Ｙ座標
別の座標テーブルの構成について説明する。図１１
（Ａ）は、ステップ１００３において、Ｘ座標／Ｙ座標
別の座標テーブルにそれぞれ、分割線の位置が登録され
た状態を示している。階層領域定義は、図４に示したよ
うに、ＭＥＳＨ１，ＭＥＳＨ２，ＭＥＳＨ３，ＭＥＳＨ
４の順に、大きな領域を順次再分割していく形態であ
り、図３に示したそれぞれの分割線が順次Ｘ座標／Ｙ座
標別の座標テーブルに登録される。ここで、Ｘ１，Ｘ
４，Ｙ１，Ｙ４以外の分割線の位置は、それぞれ、Ｘ
１，Ｘ４、Ｙ１，Ｙ４に基づいて分割線の位置が計算さ
れたものであり、例えば、Ｘ２＝（Ｘ４−Ｘ１）／３の
ように計算された値が登録されている。

【００６６】次に、ステップ１００４において、分割線
決定処理部１２２は、Ｘ座標／Ｙ座標それぞれについて
座標テーブルを昇順にソートする。ソートされた結果
は、図１１（Ｂ）に示すようになる。

【００６７】一方、ステップ１００１において、配置指
示がないと判断された場合は、ステップ１００５におい
て、分割線決定処理部１２２は、半導体集積回路の基板
上を分割して論理素子の配置位置を決定するための分割
線の座標を、以下の方法で求める。即ち、分割線間隔
が、最大の論理素子の占める大きさに合うように、Ｘ，
Ｙ方向それぞれの分割数を決め、各々の分割線の座標を
Ｘ座標／Ｙ座標それぞれについて昇順に座標テーブルに
登録する。例えば、Ｘ座標に付いてみると、最大の論理
素子の占める大きさを（Ｘ４−Ｘ１）／１００とする
と、Ｘ１，（Ｘ４−Ｘ１）／１００，２・（Ｘ４−Ｘ
１）／１００，３・（Ｘ４−Ｘ１）／１００，…，Ｘ４
のように、座標テーブルに登録される。

【００６８】以上のようにして、座標テーブルへの分割
線の位置の登録が終了すると、ステップ１００６におい
て、分割線決定処理部１２２は、Ｘ／Ｙ交互に座標テー
ブル上でバイナリサーチを行い、この順番に分割順序テ
ーブルに登録する。

【００６９】例えば、図３に示した分割線の位置の例に
ついて、Ｘ座標方向を例にとって、以下に説明する。図
１２は、登録される分割順序テーブルの一例を示してい
る。図１１（Ｂ）に示す座標テーブルにおいて、中央位
置の座標は、Ｘ２若しくはＸ３である。ここで、例え
ば、Ｘ２を選択し、図１２に示す分割順序テーブルに登
録する。次に、座標Ｘ１と座標Ｘ２間でバイナリサーチ
を行い、例えば、Ｘ６を選択し、分割順序テーブルに登
録する。次に、座標Ｘ２と座標Ｘ４間でバイナリサーチ
を行い、Ｘ８を選択し、分割順序テーブルに登録する。
次に、座標Ｘ６と座標Ｘ２間でバイナリサーチを行い、
Ｘ７を選択し、分割順序テーブルに登録する。以下、順
次バイナリサーチを行い、図１２に示すように、Ｘ２，
Ｘ６，Ｘ８，Ｘ７，Ｘ３，Ｘ５を分割順序テーブルに登
録する。Ｙ座標についても同様にバイナリサーチを行
い、分割順序テーブルに登録する。

【００７０】次に、図１３は、この分割順序テーブルを
もとにして半導体集積回路の基板上を領域に分割し、全
ての論理素子を分割領域と１対１に割り当てることで配
置位置を決定するまでの処理フローを示している。

【００７１】図１３のステップ１３０１において、論理
素子（群）配置処理部１２０の割付け処理部１２４は、
分割順序テーブルから、最初の分割線を取り出す。即
ち、Ｘ軸方向についてみるなら、図１２に示した分割順
序テーブルから、最初の分割線であるＸ２を取り出す。

【００７２】ステップ１３０２において、割付け処理部
１２４は、分割対象領域内の配置指示された論理素子
を、指定された位置を含む分割領域に割り当てる。ま
た、ステップ１３０３において、分割対象領域内の残り
の論理素子を、分割線の両側の領域の容量のバランスを
取りながら、分割線をまたぐ結線数が最小となるよう分
配し、その結果をそれぞれの分割領域テーブルに格納す
る。

【００７３】即ち、配置指示されているものが、図９の
配置指示定義カードに記載のように、論理ブロックＢＬ
ＯＣＫ Ａ，論理グループＧＲＯＵＰ Ｂ，論理素子Ｃ
ＥＬＬ Ｃとし、それ以外の論理素子、論理ブロックの
配置は指示されていないものとする。ステップ１３０２
では、配置指示されているものに対する処理であるの
で、最初の分割線Ｘ２に対して、図９の配置指示定義カ
ードによって指示されているように、論理ブロックＢＬ
ＯＣＫ Ａ，論理グループＧＲＯＵＰ Ｂ，論理素子Ｃ
ＥＬＬ Ｃを配置する。これらの配置指示された論理素
子（群）は、いずれも、分割線の右側（Ｘ軸方向の座標
値が大なる側）に配置されるものであるため、そのよう
に、分割領域テーブルに格納される。

【００７４】ここで、図１４を用いて分割領域テーブル
の一例について説明する。図１４（Ａ）に示すように、
分割領域テーブルは、分割対象の分割線と、この分割線
の左側に配置する論理素子（群）を格納するフィールド
と、分割線の右側に配置する論理素子（群）を格納する
フィールドとから構成されている。分割線Ｘ２に対し
て、ステップ１３０２によって、分割線Ｘ２の右側に
は、論理ブロックＢＬＯＣＫ Ａ，論理グループＧＲＯ
ＵＰ Ｂ，論理素子ＣＥＬＬ Ｃが配置されるので、
Ａ，Ｂ，Ｃが格納される。

【００７５】さらに、ステップ１３０３において、割付
け処理部１２４は、配置指示のされていない残りの論理
素子（群）Ｒがバランスをとって、左右に配置されるの
で、それぞれ、例えば、左側にＲ１が格納され、右側に
Ｒ２が配置される。ここで、Ｒ１，Ｒ２の詳細について
は、説明を省略する。

【００７６】ステップ１３０４において、割付け処理部
１２４は、分割順序テーブルから次の分割線を取りだ
す。ここでは、図１２に示す分割順序テーブルから次の
分割線Ｘ６を取りだす。

【００７７】ステップ１３０５は、割付け処理部１２４
は、分割線の処理終了を判断するステップであるので、
ステップ１３０４において、次の分割線が取り出せた場
合には、ステップ１３０２に戻って、ステップ１３０
２，１３０３，１３０４を実行する。

【００７８】ここでは、分割線Ｘ６に対する処理である
ため、図１４（Ａ）の左側のフィールドに格納された論
理素子（群）に対する処理を行う。図１４（Ａ）の左側
のフィールドには、配置指示のない論理素子（群）Ｒ１
のみが格納されているため、ステップ１３０２をパスす
る。次に、ステップ１３０３の処理によって、分割線Ｘ
６の左側に、例えば、論理素子（群）Ｒ１ー１を配置
し、分割線Ｘ６の右側に、例えば、論理素子（群）Ｒ１
ー２を配置するように処理を行い、その結果を図１４
（Ｂ）に示すように、分割領域テーブルに格納する。

【００７９】次に、ステップ１３０４において、次の分
割線Ｘ８を図１２の分割順序テーブルから読み出す。ス
テップ１３０５の判断で、ＮＯとなり、ステップ１３０
２に戻る。

【００８０】ここでは、分割線Ｘ８に対する処理である
ため、図１４（Ａ）の右側のフィールドに格納された論
理素子（群）に対する処理を行う。図１４（Ａ）の右側
のフィールドには、配置指示のある論理素子（群）Ａ，
Ｂ，Ｃ及び配置指示のない論理素子（群）Ｒ２が格納さ
れているため、ステップ１３０２では、配置指示のある
論理素子（群）Ａ，Ｂ，Ｃの配置処理を行う。即ち、図
９の配置指示に基づいて、論理素子（群）Ａ，Ｃは、分
割線Ｘ８の左側に配置され、論理素子（群）Ｂは、分割
線Ｘ８を跨ぐ形で、Ｂ１，Ｂ２と分割して、それぞれ、
左右に配置する。

【００８１】さらに、ステップ１３０３の処理によっ
て、配置指示のない論理素子（群）Ｒ２の配置処理を行
い、分割線Ｘ８の左側に、例えば、論理素子（群）Ｒ２
ー１を配置し、分割線Ｘ８の右側に、例えば、論理素子
（群）Ｒ２ー２を配置するように処理を行い、その結果
を図１４（Ｃ）に示すように、分割領域テーブルに格納
する。ここで、図１４（Ａ）に示した分割領域テーブル
の格納内容は、図１４（Ｂ），（Ｃ）に示すように再分
割されているため、図１４（Ａ）に示した分割領域テー
ブルは内容を消去する。

【００８２】次に、ステップ１３０４において、次の分
割線Ｘ７を図１２の分割順序テーブルから読み出す。ス
テップ１３０５の判断で、ＮＯとなり、ステップ１３０
２に戻り、以下、ステップ１３０２，１３０３，１３０
４を実行する。ステップ１３０２，１３０３，１３０４
を繰り返し実行することによって、領域が細分割され、
それぞれの分割線の左右に論理素子（群）が配置され
る。また、それに伴って、最初の内に形成された分割領
域テーブルは順次消去されるので、分割領域テーブル
は、最小の分割単位に対して形成されていることにな
る。また、以上の分割配置処理は、Ｘ軸方向だけでな
く、Ｙ軸方向についても同様になされる。

【００８３】すべての分割線について処理が完了する
と、ステップ１３０５において、ＹＥＳと判断され、ス
テップ１３０６に進む。

【００８４】ステップ１３０６において、論理素子
（群）配置処理部１２０の再分割処理部１２６は、分割
領域テーブルから最初の領域を取り出す。さらに、ステ
ップ１３０７において、再分割処理部１２６は、領域内
の論理素子数が１個以下か判定する。これは、ステップ
１３０２，１３０３，１３０４を繰り返し実行すること
によって、領域が細分割され、それぞれの分割線の左右
に論理素子（群）が配置され、また、分割領域テーブル
は、最小の分割単位に対して形成されていることになっ
ているが、この分割単位が適当であるかどうかを判断し
ている。分割領域内に論理素子が２個以上ある場合，即
ち、分割が不十分である場合には、ステップ１３０８に
進む。

【００８５】ステップ１３０８において、再分割処理部
１２６は、Ｘ／Ｙ交互に領域の２分割を繰り返し、容量
の範囲内で分割線を跨ぐ結線数が最小となるように、論
理素子の分配を繰り返し、分割領域内の論理素子数を１
個以下にする。

【００８６】ステップ１３０７において、領域内の論理
素子数が１個以下と判定された場合及びステップ１３０
８における処理が終了すると、ステップ１３０９に進
む。

【００８７】ステップ１３０９において、再分割処理部
１２６は、分割領域テーブルから次の分割領域を取り出
し、ステップ１３１０において、全ての分割領域を処理
するまで、ステップ１３０７，１３０８，１３０９を繰
り返す。

【００８８】全ての分割領域の処理が終了した時点で、
全ての論理素子の配置位置が決定する。

【００８９】上記処理により、半導体集積回路の基板上
での論理素子もしくは論理素子群の配置位置の指定と、
その指定を守った配置が実現される。

【００９０】本実施の形態によれば、配置位置の指示
は、論理ブロック単位や論理素子単位の論理素子（群）
単位で行われる。通常、半導体集積回路で処理されるデ
ータは、半導体集積回路の基板上をある流れに沿って移
動するため、その流れに沿った位置に関係する論理素子
を配置することによって、半導体集積回路の動作速度を
向上し得るものとなる。

【００９１】また、基板上を階層的に領域分割すること
で配置位置を指示することにより、論理ブロックや論理
素子といった大きさの格段に異なるものを、同一手法で
同時に処理できるものとなる。

【００９２】また、外部からの配置指示情報を与える手
段としての領域分割の分割線と、後続の配置処理におい
て各論理素子の配置位置を決定する際に使用する分割線
を一致させることにより、自動配置処理において配置指
示を確実に守ることが可能となる。

【００９３】以上に説明したように、本実施の形態によ
れば、半導体集積回路の動作速度を律速する特定の論理
素子もしくは論理ブロック等の論理素子群の配置位置に
関し、その情報を知っている半導体集積回路の論理設計
者が配置位置を指示し、後続の配置処理において、指示
された配置位置を守って配置することにより、半導体集
積回路の動作速度を向上させることができるようにな
る。

【００９４】

【発明の効果】本発明によれば、半導体集積回路の論理
素子配置処理において、半導体集積回路の動作速度に関
して、より最適な半導体集積回路の論理素子配置が行え
るようになる。

【図面の簡単な説明】

【図１】本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法を実現するシステムのブロック図
である。

【図２】本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法における論理素子（群）の配置位
置指示処理を示すフローチャートである。

【図３】本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法における半導体集積回路の基板上
の領域分割の説明図である。

【図４】本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法において用いる領域定義カードの
説明図である。

【図５】本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法において用いるグループ化の説明
図である。

【図６】本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法において用いるグループ定義カー
ドの説明図である。

【図７】論理素子群の説明図である。

【図８】本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法において指定される領域の説明図
である。

【図９】本発明の一実施の形態による半導体集積回路の
論理素子配置処理方法において用いる配置指示定義カー
ドの説明図である。

【図１０】本発明の一実施の形態による半導体集積回路
の論理素子配置処理方法における論理素子群の配置処理
を示すフローチャートである。

【図１１】本発明の一実施の形態による半導体集積回路
の論理素子配置処理方法において用いる座標テーブルの
構成図である。

【図１２】本発明の一実施の形態による半導体集積回路
の論理素子配置処理方法において用いる分割順序テーブ
ルの構成図である。

【図１３】本発明の一実施の形態による半導体集積回路
の論理素子配置処理方法における論理素子群の配置処理
を示すフローチャートである。

【図１４】本発明の一実施の形態による半導体集積回路
の論理素子配置処理方法における論理素子群の配置処理
において用いる分割領域テーブルの構成図である。

【符号の説明】

１１０…配置位置指示処理部 １２０…論理素子（群）配置処理部 １２２…分割線決定処理部 １２４…割付け処理部 １２６…再分割処理部 Ｂｌｏ．Ａ，Ｂｌｏ．Ｂ，Ｂｌｏ．Ｃ，Ｂｌｏ．Ｄ…論
理ブロック Ｇｒ．Ｂ…論理素子グループ Ｃｅｌｌ Ｃ，Ｃｅｌｌ Ｄ，Ｃｅｌｌ Ｅ…論理素子

───────────────────────────────────────────────────── フロントページの続き (72)発明者 徳山 弘毅 神奈川県秦野市堀山下１番地 株式会社日 立製作所汎用コンピュータ事業部内 (72)発明者 檜山 徹 神奈川県秦野市堀山下１番地 株式会社日 立製作所汎用コンピュータ事業部内 (72)発明者 石井 建基 神奈川県秦野市堀山下１番地 株式会社日 立製作所汎用コンピュータ事業部内

Claims (5)

【特許請求の範囲】
1. 【請求項１】 論理ブロック単位に論理分割して階層的
   に論理設計されている論理素子群の各論理素子を、半導
   体集積回路の基板上に配置する半導体集積回路の論理素
   子配置処理方法において、 上記半導体集積回路の基板上を領域分割し、この分割さ
   れた領域の中の特定の領域に、論理素子もしくは論理ブ
   ロックからなる論理素子群の中の特定の論理素子群を対
   応づけて配置位置を指示し、 次に、この配置位置の指示に基づいて、上記特定の論理
   素子群を上記基板上に配置し、さらに、他の論理素子を
   上記基板上に配置することを特徴とする半導体集積回路
   の論理素子配置処理方法。
2. 【請求項２】 請求項１記載の半導体集積回路の論理素
   子配置処理方法において、 上記領域分割は、上記基板平面上の位置を記述する任意
   の２次元座標系において、領域を分割する境界線の座
   標，領域を分割する個数若しくは領域を分割する座標幅
   に基づいてなされることを特徴とする半導体集積回路の
   論理素子配置処理方法。
3. 【請求項３】 請求項１記載の半導体集積回路の論理素
   子配置処理方法において、 上記領域分割は、分割前の全領域，分割された領域に対
   して、さらに、階層的若しくは多重的に繰り返しなされ
   ることを特徴とする半導体集積回路の論理素子配置処理
   方法。
4. 【請求項４】 請求項３記載の半導体集積回路の論理素
   子配置処理方法において、 上記配置位置の指示は、上記階層的な領域分割により生
   成された親子関係を持つ分割領域と、論理的に親子関係
   を持つ論理素子と論理素子群とを、それぞれ対応づけて
   行うことを特徴とする半導体集積回路の論理素子配置処
   理方法。
5. 【請求項５】 請求項１記載の半導体集積回路の論理素
   子配置処理方法において、 上記基板上への論理素子群の配置は、上記配置位置の指
   示の際に使用する領域を分割する分割線を基準として行
   われることを特徴とする半導体集積回路の論理素子配置
   処理方法。