(57)【要約】  【課題】  マクロセルやソフトマクロ等の特殊セルについても適正な電源線の配置配線が行われ、また互いに結びつきの強い標準セルが互いに異なった回路ブロックに配置されることがないようにする。  【解決手段】  半導体集積回路の配置領域における特定領域にマクロセル等の特殊セルを配置するステップＳ１と、該特殊セルに電源供給を行う第１の電源線を配置配線するステップＳ２と、特殊セルの消費電流および前記第１の電源線とバランスがとれるように、前記配置領域の内の前記特定領域以外の領域をｎ個の分割領域に分割するステップＳ３と、半導体集積回路からなる論理回路の内の前記特殊セルによる回路を除く回路を論理的な結び付きに応じて前記ｎ個の回路ブロックに分割するステップＳ４と、前記論理回路の論理的な結び付きおよび前記各分割領域に供給される電流供給量に応じて、前記ｎ個の分割領域に前記ｎ個の回路ブロックを配置するステップＳ５〜Ｓ１０と、を具備する。【選択図】  図１
2005157487.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置を備えたコンピュータにより、該記憶装置から少なくとも１つのマクロセル、ソフトマクロ展開されたセル群あるいはスキューが問題となるセル群等の特殊セルおよび複数の標準セルを読み出し、該特殊セルおよび該標準セル並びに電源線を配置配線して半導体集積回路のレイアウトを作成する自動配置配線方法において、
前記半導体集積回路の配置領域における特定領域に前記特殊セルを配置する第１のステップと、
前記特殊セルに電源供給を行う第１の電源線を前記配置領域に配置配線する第２のステップと、
前記特殊セルの消費電流および前記第１の電源線とバランスがとれるように、前記配置領域の内の前記特定領域以外の領域を分割してｎ個の分割領域を形成し、電源線を配置配線する第３のステップと、
前記半導体集積回路からなる論理回路の内の前記特殊セルによる回路を除く回路を論理的な結び付きに応じて分割してｎ個の回路ブロックを形成する第４のステップと、
前記論理回路の論理的な結び付きおよび前記ｎ個の分割領域に供給される電流供給量に応じて、前記ｎ個の分割領域に対して前記ｎ個の回路ブロックを配置する第５のステップと、
を具備することを特徴とする自動配置配線方法。
【請求項２】
請求項１に記載の自動配置配線方法において、
前記第３のステップにおける前記ｎ個の分割領域の形成および前記第４のステップにおける前記ｎ個の回路ブロックの形成は、前記ｎ個の回路ブロックを構成する前記標準セルおよび前記ｎ個の回路ブロックの消費電流、並びに前記ｎ個の分割領域に配置配線する電源線の配線長および配線幅に応じて行うことを特徴とする自動配置配線方法。
【請求項３】
請求項１又は２に記載の自動配置配線方法において、
前記第５のステップは、前記ｎ個の分割領域を遺伝子座とし、前記ｎ個の回路ブロックを遺伝子として、前記ｎ個の回路ブロック相互間および前記ｎ個の回路ブロックと前記特殊セルとの関係の緊密度、前記ｎ個の回路ブロックに供給される供給電力量と前記ｎ個の回路ブロックでの消費電流量との関係を制約条件として、前記ｎ個の分割領域に対する前記ｎ個の回路ブロックの最適な割り付けを遺伝的アルゴリズムにより行うことを特徴とする自動配置配線方法。
【請求項４】
請求項３に記載の自動配置配線方法において、
前記遺伝的アルゴリズムは、前記ｎ個の分割領域に対する前記ｎ個の回路ブロックの割り付けの組合せを複数作成し、各組合せにおける各回路ブロックを前記制約条件により評価し、該評価結果に応じて淘汰、増殖、進化を繰り返して前記制約条件をほぼ満たす最適な１つの組合せを選定することを特徴とする自動配置配線方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置を備えたコンピュータにより、該記憶装置から少なくとも１つのマクロセル、ソフトマクロ展開されたセル群あるいはスキューが問題となるセル群等の特殊セルおよび複数の標準セルを読み出して、該特殊セルおよび該標準セル並びに電源線を配置配線して半導体集積回路のレイアウトを作成する自動配置配線方法に関するものである。
【背景技術】
【０００２】
半導体集積回路において、配線層を構成するメタル配線は、半導体プロセスの微細化や配線層の多層化に伴ってますます薄膜化および配線ピッチ縮小化が進み、これにより配線抵抗や配線容量等の寄生素子が増大し、レイアウトを設計する上でこれらの寄生素子を考慮することが重要な課題となってきている。
【０００３】
特に、半導体集積回路の個々の回路ブロックに電源電圧を供給する個々の電源線の配置設計においては、回路ブロックの消費電流と電源線の寄生素子とにより、電源線に電圧変動が生じる点を考慮する必要がある。動作周波数が高い半導体集積回路においては、配線抵抗に起因する電圧降下と該電圧降下に起因する遅延に対する対策が重要な課題となる。
【０００４】
そこで従来では、電源線の電圧降下を低減するために、各標準セル毎に、固有の消費電流データ、負荷インピーダンスデータおよび回路活性化率データを基にしてその実質消費電流を算出しておき、論理回路全体をある程度の単位で分割した各回路ブロック毎の消費電流（当該回路ブロックを構成する複数の標準セルの合計消費電流）と、論理回路全体の消費電流を回路ブロック数で除した各回路ブロックの平均消費電流との差が小さくなるように、各回路ブロックを分割する手法が提案されている（例えば、特許文献１参照）。また、ここでは、回路ブロック内では相対的に消費電流が大きい標準セルは電源線の近くに配置し、１つの回路ブロックに属する標準セルと他の回路ブロックに属する標準セルとを交換する再配置工程を備えている。
【０００５】
これらの手法を採用することで、各回路ブロックの消費電流を均等化するよう回路全体を分割（グループ化）して、各回路ブロックに標準セルが配置されるため、電源線の電圧降下量が均等化され、回路遅延のばらつきを抑えることができる。これにより、回路の動作速度や電源線の幅等の設計マージンを必要最小限にまで削減できることから、半導体集積回路の高速化及び高集積化を図ることができる。
【特許文献１】特開平１１−２３８８０２号
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記の手法は電源線及び消費電流を優先して配置配線を処理するものであるため、同一回路ブロック内に分類しておくべき標準セルが、他の回路ブロックのセルと交換される可能性が生じる。また、電源を供給する必要があり分割領域が制限されるＰＬＬ、メモリ等のマクロセルやソフトマクロについては全く考慮されていない。
【０００７】
本発明の目的は、マクロセルやソフトマクロ等の特殊セルについても適正な電源線の配置配線が行われ、また互いに結びつきの強い標準セルが互いに異なった回路ブロックに配置されることがないようにした自動配置配線方法を提供することである。
【課題を解決するための手段】
【０００８】
請求項１にかかる発明の自動配置配線方法は、記憶装置を備えたコンピュータにより、該記憶装置から少なくとも１つのマクロセル、ソフトマクロ展開されたセル群あるいはスキューが問題となるセル群等の特殊セルおよび複数の標準セルを読み出し、該特殊セルおよび該標準セル並びに電源線を配置配線して半導体集積回路のレイアウトを作成する自動配置配線方法において、前記半導体集積回路の配置領域における特定領域に前記特殊セルを配置する第１のステップと、前記特殊セルに電源供給を行う第１の電源線を前記配置領域に配置配線する第２のステップと、前記特殊セルの消費電流および前記第１の電源線とバランスがとれるように、前記配置領域の内の前記特定領域以外の領域を分割してｎ個の分割領域を形成し、電源線を配置配線する第３のステップと、前記半導体集積回路からなる論理回路の内の前記特殊セルによる回路を除く回路を論理的な結び付きに応じて分割してｎ個の回路ブロックを形成する第４のステップと、前記論理回路の論理的な結び付きおよび前記ｎ個の分割領域に供給される電流供給量に応じて、前記ｎ個の分割領域に対して前記ｎ個の回路ブロックを配置する第５のステップと、を具備することを特徴とする自動配置配線方法とした。
請求項２にかかる発明は、請求項１に記載の自動配置配線方法において、前記第３のステップにおける前記ｎ個の分割領域の形成および前記第４のステップにおける前記ｎ個の回路ブロックの形成は、前記ｎ個の回路ブロックを構成する前記標準セルおよび前記ｎ個の回路ブロックの消費電流、並びに前記ｎ個の分割領域に配置配線する電源線の配線長および配線幅に応じて行うことを特徴とする自動配置配線方法とした。
請求項３にかかる発明は、請求項１又は２に記載の自動配置配線方法において、前記第５のステップは、前記ｎ個の分割領域を遺伝子座とし、前記ｎ個の回路ブロックを遺伝子として、前記ｎ個の回路ブロック相互間および前記ｎ個の回路ブロックと前記特殊セルとの関係の緊密度、前記ｎ個の回路ブロックに供給される供給電力量と前記ｎ個の回路ブロックでの消費電流量との関係を制約条件として、前記ｎ個の分割領域に対する前記ｎ個の回路ブロックの最適な割り付けを遺伝的アルゴリズムにより行うことを特徴とする自動配置配線方法とした。
請求項４にかかる発明は、請求項３に記載の自動配置配線方法において、前記遺伝的アルゴリズムは、前記ｎ個の分割領域に対する前記ｎ個の回路ブロックの割り付けの組合せを複数作成し、各組合せにおける各回路ブロックを前記制約条件により評価し、該評価結果に応じて淘汰、増殖、進化を繰り返して前記制約条件をほぼ満たす最適な１つの組合せを選定することを特徴とする自動配置配線方法とした。
【発明の効果】
【０００９】
本発明によれば、マクロセル、ソフトマクロ展開されたセル群あるいはスキューが問題となるセル群等の特殊セルは、最初に配置領域の特定領域に配置され且つ特殊セル用の電源線も必要十分な条件で最初に配置され、その後に他の回路ブロックやそれに電源供給する電源線についてはこれら特殊セルとバランスがとれるように配置配線されるので、特殊セルやその電源線を他からの影響を受けずに要求仕様通りに配置することができる。また、ｎ個に分割する回路ブロックは論理的な結び付きに応じて分割されるので、同一の回路ブロック内に分類しておくべきセルが別の回路ブロックに分類されるようなことはなくなる。さらに、ｎ個の分割領域にｎ個の回路ブロックを割り付けるときは、所定の制約条件を満足するように遺伝的アルゴリズムにより行えば、迅速に最適な割り付けを行うことができる。
【発明を実施するための最良の形態】
【００１０】
本発明の実施形態では、記憶装置を備えたコンピュータにより、該記憶装置から少なくとも１つのマクロセル、ソフトマクロ展開されたセル群あるいはスキューが問題となるセル群等の特殊セルおよび複数の標準セル、並びに回路接続情報、設計制約、その他の自動配置配線に必要なデータを読み出し、該特殊セルおよび該標準セル、並びに電源線を配置配線して半導体集積回路のレイアウトを作成する。その概要は次の通りである。
【００１１】
(1)特殊セル（１又は２以上）を半導体集積回路の配置領域における予め決められた特定領域に配置し、その特殊セルに電源を供給する電源線を要求仕様通りに配置配線する。
(2)次に、全部のセルおよび各回路ブロック（分類されたセル群からなる）の消費電流と配置配線される電源線の配線長および配線幅を一定の基準で数値化して評価する。
(3)次に、半導体集積回路上で(1)によって配置された特殊セルおよび該特殊セルの電源線を配置した特定領域以外の領域を仮に分割してｎ個の分割領域とし、特殊セルの消費電流の値と電源線の配線長および配線幅とバランスがとれるように、つまり特殊セル側が他からの影響を受けないように、新たな電源線を配線する。
【００１２】
(4)次に、論理的な結びつき等を考慮して、つまり論理関係が緊密なセルが同じ回路ブロックに含まれるように、論理回路中の前記特殊セルを除く回路部分をｎ個に分割する。  なお、これらの(3)と(4)では、特殊セル以外のｎ個の回路ブロックを(2)の要領（セルや回路の消費電流、電源線の配線長や配線幅）で評価し、その評価結果に応じて電源線の配線幅を変更し、あるいは分岐を変更し、分割領域や数ｎおよび回路ブロックの内容や数ｎを変更する。
【００１３】
(5)次に、ｎ個の分割領域にｎ個の回路ブロックを割り付けて配置する。このとき、すでに配置された特殊セルとの結びつきの重みを優先する。つまり特殊セルと結びつきの強い回路ブロックはその特殊セルの近くの分割領域に配置する。なお、ある程度ｎ個の回路ブロックの消費電流と既配線の電源供給能力も考慮する。ここでも、(2)の要領の評価でバランスがとれるまで、ｎ個の分割領域に対するｎ個の回路ブロックの割り付けを繰り返す。なお以上では、信号線の配置配線については、本発明の要旨から外れるので、その説明は省略した。
【００１４】
以上により、特殊セルと該特殊セルに電源を供給する電源線をまず最初に配置配線した後に、半導体集積回路全体のバランスをとるように電源線が配置配線されたｎ個の分割領域に、論理回路を分割したｎ個の回路ブロックを配置していくので、特殊セルは後の回路ブロックの配置配線の影響を受けることはなく、またｎ個の回路ブロックは論理関係が緊密なセルが同じ回路ブロックに含まれるように分割されるので、同一の回路ブロック内に分類しておくべきセルが別の回路ブロックに分類されるようなことはなく、さらに特殊セルと関連が深い回路ブロックはその特殊セルの近くに配置されるので、最適な配置配線が実現でき、遅延時間を要求仕様内に確実に納めながら、回路全体の電力消費が局所に偏ることを防ぐことができる。以下、具体例で詳しく説明する。
【実施例１】
【００１５】
図１は実施例１の配置配線の処理のフローチャート、図２は配置配線の対象としての半導体集積回路の領域（フロア）を示す図である。まず、特殊セルを当該特殊セルに予め割り付けられた特定領域２に配置し（ステップＳ１）、次にその特殊セルへの電源線の配置配線を行う（ステップＳ２）。そして、半導体集積回路上の領域において、特殊セルの特定領域２以外の領域をｎ個（図２では簡単のため７個とした）に分割し、分割領域１、３〜８を得、電源線を配置する（ステップＳ３）。次に、論理回路の内の前記特殊セルによる回路を除く回路部分を、ｎ個の回路ブロックに分割する（ステップＳ４）。以上の処理ステップＳ１〜Ｓ４は前記した(1)、(3)、(4)に対応する。ステップＳ３，Ｓ４では、前記したように、ｎ個の回路ブロックをセルや回路の消費電流、電源線の配線長や配線幅等で評価し、その評価結果に応じて電源線の配線幅を変更し、あるいは分岐を変更し、分割領域や数ｎおよび回路ブロックの内容や数ｎを変更する。
【００１６】
次のステップＳ６〜Ｓ１０はｎ個の分割領域にｎ個の回路ブロックを割り付けて配置する前記した(5)に対応する処理である。このｎ個の回路ブロックの割り付けは、各回路ブロック相互間の結び付き（特殊セルと他の回路ブロック相互間の結び付きも含むものとする）の重み、各回路ブロックに供給される電流が当該各ブロックの消費電流を満たすか等の制約条件を評価して配置する。このような割り付けは、単純にしらみつぶしに計算した場合、ｎの数が多くなったときに計算爆発を起こしてしまうので、以下のような手段を採用する。
【００１７】
すなわち、どの分割領域にどの回路ブロックを割り付けて配置するかという問題を、巡回セールスマン問題の変形としてとらえ、遺伝的アルゴリズムを用いて現実的な解を求める。この場合、回路ブロックを巡回する都市（遺伝子）と見立てる。評価関数として、回路ブロック相互間の結び付きの重みと、電源供給能力および消費電流量とを設定する。まず、回路ブロック間の重み付けは事前に設定しておく。回路ブロック間の距離は実測でもそれを正規化したものでも良い。回路ブロック間の結び付きの評価関数としては、例えばｆ(x)＝[重み付け／距離]という関数を定義する。同様に電源線の電源供給能力に対する回路ブロックの消費電流量がある程度の範囲で下回ればプラス、超えればマイナスとなるような評価関数を設定する。そして、以後、各回路ブロック（都市）を遺伝子の１ビットとみたてたシミュレーションを進め、最小値を求めると、最適な割り付けの配置となる。
【００１８】
以下、図３と図４をも参照して遺伝的アルゴリズムを適用して、ｎ個の分割領域にｎ個の回路ブロックをどのようにして配置するかについて説明する。なお、分割領域は遺伝子座に、回路ブロックは遺伝子に相当する。まず、後に交叉で説明する図３(a)に示すように、分割領域１、特定領域２、分割領域３〜８に対して回路ブロックＡ，ＰＬＬ，ＰＬＬ−ｃ，Ｂ〜Ｆを順に割り付けた組合せＰ１、回路ブロックＤ，ＰＬＬ，Ｆ，Ａ，Ｅ，Ｂ，ＰＬＬ−ｃ，Ｃを順に割り付けた組合せＰ２を、初代の組合せ（親の遺伝子集団）として設定する（図１のステップＳ５）。ここでは、簡単のために組合せの数は２組としたが、実際にはもっと多くなる。
【００１９】
ただし、回路ブロックＰＬＬはマクロセル等の特殊セルであり、特定領域２に固定である。また、回路ブロックＰＬＬ−ｃは回路ブロックＰＬＬと関係が密な回路ブロックであり、組合せＰ１ではその回路ブロックＰＬＬの近くの分割領域３に配置されているが、組合せＰ２では離れた分割領域７に配置している。
【００２０】
次に、以上のようにして所定の分割領域１、特定領域２、分割領域３〜８に割り付けた各回路ブロックの評価（ただし、回路ブロックＰＬＬを除く）を行う（図１のステップＳ６）。この評価は図４に示すような第１〜第３の制約条件で行う。
【００２１】
第１の制約条件では、ひとつの例として回路ブロックＡ−Ｂ間、Ａ−Ｃ間について説明すると、Ａ−Ｂ間では配線数がＸ１（例えば１０本）、Ａ−Ｃ間ではＸ２（例えば５本）である場合等であり、このような信号線数をＸとし、また、回路ブロック間の距離（中心点間の実測又はマンハッタン距離等）をＹとすると、「ｆ＝Ｘ×（１／Ｙ）」を評価関数として用いる。回路ブロック間の配線数が多いほど且つ距離が短いほど、評価ｆが高くなる。第２の制約条件では、当該回路ブロックへの供給電力量（電源線の幅、本数等で決まる。）が当該回路ブロックの消費電力量より大きいかどうかで評価し、「供給電力量＞消費電力量」のとき評価を高く（プラス）する。第３の制約条件では、当該回路ブロックへの供給電力量と当該ブロックの消費電力量の比率「消費電力量／供給電力量」を求めて、これが小さいほど高い評価を与えるが、逆に例えば３％以上のバラツキがある場合は評価値を最低値とする。
【００２２】
以上のようにして、複数の組合せ（Ｐ１，Ｐ２等）について評価して、各組合せのそれぞれの回路ブロックの評価の平均が、十分に高まるかあるいは最適解に収束したか否かを判定して（図１のステップＳ７）、それに該当する組合せがあればＹＥＳとして終了するが、ＮＯの場合は次のステップＳ８にすすむ。
【００２３】
このステップＳ８（淘汰）では、ステップＳ５で作成された複数の組合せについて、評価値の下位ｐ％を削除することにより、淘汰を行う。そして、次のステップＳ９（増殖）において、評価値の上位ｐ％の親の数を倍にして組合せの数を増やす。次に、以上の結果得られた優秀な組合せ（親）から、ステップＳ１０（進化）において交叉若しくは突然変異により、新たな組合せ（子）を作成する。
【００２４】
ここで、図３の(a)によって、組合せ（親）Ｐ１，Ｐ２から１点交叉により２つの組合せ（子）Ｑ１，Ｑ２を作成する手法について説明する。なお、ここでは遺伝子で説明する。図５はそのフローチャートである。まず、親Ｐ１の前半部分を子Ｑ１の前半部分にコピーし、親Ｐ２の前半部分を子Ｑ２の前半部分にコピーする（ステップＳ２１）。これにより、子Ｑ１の前半部分には、「Ａ，ＰＬＬ，ＰＬＬ−ｃ，Ｂ」がコピーされ、子Ｑ２の前半部分には「Ｄ，ＰＬＬ，Ｆ，Ａ」がコピーされる。
【００２５】
次に、親Ｐ１の後半部分の遺伝子で且つ子Ｑ２の前半部分に使われていない遺伝子を子Ｑ２の後半部分にコピーし、親Ｐ２の後半部分の遺伝子で且つ子Ｑ１の前半部分に使われていない遺伝子を子Ｑ１の後半部分にコピーする（ステップＳ２２）。これにより、子Ｑ１の後半部分には、「Ｅ，＊，＊，Ｃ」がコピーされ、子Ｑ２の後半部分には「Ｃ，＊，Ｅ，＊」がコピーされる。＊は前半部分に使われていてコピーされない分割領域である。
【００２６】
次に、子Ｑ１に格納されていない遺伝子を親Ｐ２の遺伝子座の小さい方から探し出して順に格納し、子Ｑ２に格納されていない遺伝子を親Ｐ１の遺伝子座の小さい方から探し出して順に格納する（ステップＳ２３）。これにより、子Ｑ１の遺伝子座６にはＤが、遺伝子座７にはＦが格納され、子Ｑ２の遺伝子座６にはＰＬＬ−ｃが、遺伝子座８にはＢが格納される。以上のようにして、親Ｐ１，Ｐ２から、その後半部分を変化させた子Ｑ１，Ｑ２が作成される。
【００２７】
突然変異の場合は、親Ｐ１の一部の遺伝子を交互に入れ替えて子Ｑ３を作成する。図３(b)の例では、親Ｐ１の遺伝子ＰＬＬ−ｃとＤを入れ替えて、子Ｑ３を作成している。
【００２８】
以上のようにしてステップＳ１０において、交叉あるいは突然変異により新たな複数の組合せを作成した後は、再度ステップＳ６に戻って、各組合せについて各回路ブロックの評価を行い、ステップＳ７で判定する。ステップＳ６〜Ｓ１０の一巡を１世代として、複数世代を処理することにより、比較的迅速にステップＳ７で全回路ブロックの評価の平均値が十分高まり、あるいは最適解に収束した１つの組合せを得ることができる。
【図面の簡単な説明】
【００２９】
【図１】本発明の自動配置配線方法の実施例１のフローチャートである。
【図２】半導体集積回路の配置領域の分割の説明図である。
【図３】遺伝的アルゴリズムの交叉と突然変異の説明図である。
【図４】遺伝的アルゴリズムにおける評価のための制約条件の説明図である。
【図５】遺伝的アルゴリズムにおける交叉のフローチャートである。
【符号の説明】
【００３０】
１，３〜８：分割領域（遺伝子座）
２：特定領域（遺伝子座）
Ａ〜Ｆ：回路ブロック（遺伝子）
ＰＬＬ：特殊セル（遺伝子）
ＰＬＬ−ｃ：特殊セルＰＬＬと関係の深い回路ブロック（遺伝子）
Ｐ１，Ｐ２：回路ブロックの組合せ（親の遺伝子集団）
Ｑ１〜Ｑ３：回路ブロックの組合せ（子の遺伝子集団）
【図１】
2005157487.tif 000003
【図２】
2005157487.tif 000004
【図３】
2005157487.tif 000005
【図４】
2005157487.tif 000006
【図５】
2005157487.tif 000007