(57)【要約】【課題】自動的な制御により特定の複数の配線経路における遅延時間のばらつきを抑制できる自動配置配線装置を提供することを目的とする。【解決手段】自動配置配線装置は、配線長を揃える複数のノードＮ１〜Ｎ３を指定すると共に、配線長の目標値（目標配線長）を指定する。そして各指定ノードＮ１〜Ｎ３の配線を適宜迂回させることでそれらの長さを調整し、それらを目標配線長に揃える。また自動配置配線装置は、配線長を調整するために、ノードＮ１〜Ｎ３が接続するセルＣ１ａ，Ｃ１ｂ，Ｃ２ａ，Ｃ２ｂ，Ｃ３ａ，Ｃ３ｂの位置を移動させることもできる。【選択図】図２
2009032051.tif 000002
【特許請求の範囲】
【請求項１】
複数の指定された配線ノード（指定ノード）について、それらの配線長を揃える配線長調整機能を備える
ことを特徴とする自動配置配線装置。
【請求項２】
前記配線長調整機能は、
前記指定ノードの配線長を調整するために、当該指定ノードの配線を迂回させる機能を含む
ことを特徴とする請求項１記載の自動配置配線装置。
【請求項３】
前記配線長調整機能は、
前記指定ノードの配線長のそれぞれを、指定された目標値に揃える機能を含む
ことを特徴とする請求項２記載の自動配置配線装置。
【請求項４】
前記配線長調整機能は、
前記指定ノードが接続するセル間のマンハッタン距離の最大値を前記目標値として設定する機能を含む
ことを特徴とする請求項３記載の自動配置配線装置。
【請求項５】
前記配線長調整機能は、
前記指定ノードについての配線処理を行い、その結果得られた当該指定ノードの配線長の最大値を前記目標値として設定する機能を含む
ことを特徴とする請求項３記載の自動配置配線装置。
【請求項６】
前記配線長調整機能は、
全ての配線ノードについての配線処理を行い、その結果得られた前記指定ノードの配線長の最大値を前記目標値として設定する機能を含む
ことを特徴とする請求項３記載の自動配置配線装置。
【請求項７】
前記配線長調整機能は、
前記目標値に対して指定された許容範囲から外れた前記指定ノードについてのみ、配線長の調整を行う機能を含む
ことを特徴とする請求項２から請求項６のいずれか記載の自動配置配線装置。
【請求項８】
前記配線を迂回させる機能は、
前記配線が複数の配線層から成る場合に、当該配線の指定された配線層に属する部分を迂回させる機能を含む
ことを特徴とする請求項２から請求項７のいずれか記載の自動配置配線装置。
【請求項９】
前記配線を迂回させる機能は、
複数の配線層を用いて前記配線の迂回経路を形成する機能を含む
ことを特徴とする請求項２から請求項７のいずれか記載の自動配置配線装置。
【請求項１０】
前記配線を迂回させる機能は、
隣接する２又は３の配線トラックを使用して前記配線を迂回させる機能を含む
ことを特徴とする請求項２から請求項７のいずれか記載の自動配置配線装置。
【請求項１１】
前記配線を迂回させる機能は、
配線が経由すべき通過ポイントを想定し、当該通過ポイントの位置決めを行う機能である
ことを特徴とする請求項２から請求項１０のいずれか記載の自動配置配線装置。
【請求項１２】
前記通過ポイントは、仮想のセルである
ことを特徴とする請求項１１記載の自動配置配線装置。
【請求項１３】
前記配線長調整機能は、
前記指定ノードの配線長を調整するために、当該指定ノードが接続するセルの位置を移動させる機能を含む
ことを特徴とする請求項１記載の自動配置配線装置。
【請求項１４】
前記配線長調整機能は、
前記指定ノードの配線長のそれぞれを、指定された目標値に揃える機能を含む
ことを特徴とする請求項１３記載の自動配置配線装置。
【請求項１５】
前記配線長調整機能は、
前記指定ノードが接続するセル間のマンハッタン距離の最大値を、前記目標値として設定する機能を含む
ことを特徴とする請求項１４記載の自動配置配線装置。
【請求項１６】
前記配線長調整機能は、
前記指定ノードが接続するセル間のマンハッタン距離の最小値を、前記目標値として設定する機能を含む
ことを特徴とする請求項１４記載の自動配置配線装置。
【請求項１７】
前記配線長調整機能は、
前記指定ノードが接続するセル間のマンハッタン距離の平均値を、前記目標値として設定する機能を含む
ことを特徴とする請求項１４記載の自動配置配線装置。
【請求項１８】
前記配線長調整機能は、
前記目標値に対して指定された許容範囲から外れた前記指定ノードについてのみ、配線長の調整を行う機能を含む
ことを特徴とする請求項１４から請求項１７のいずれか記載の自動配置配線装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体装置設計における自動配置配線装置に関するものである。
【背景技術】
【０００２】
半導体装置設計の分野において、セル（半導体装置の機能を構成する最小単位）や当該セル間の接続ノードに対応する配線を自動的にレイアウトする自動配置配線装置が知られている。例えば、シノプシス社（Synopsys, Inc.）の自動配置配線装置「Astro」や、ケイデンス・デザイン・システムズ社（Cadence Design Systems, Inc.）の自動配置配線装置「SocEncounter/NanoEncounter」がある。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従来の自動配置配線装置では、セルおよび配線のレイアウトの際に、各配線の長さ（配線長）が所定の設定値以下になるようすることや、配線長ができるだけ短くなるようにすることを、自動制御によって行うことが可能である。また、特定の配線経路（パス）における信号の遅延時間を指定した値に近づけることも自動制御により可能であった。
【０００４】
しかし、従来の自動配置配線装置では個々の配線長までは指定することができなかったため、複数の配線ノード（以下単に「ノード」）の配線長を、自動的に揃えることはできなかった。
【０００５】
自動配置配線装置の配線処理では、原則として配線はセル間を最短経路で接続するように引かれるため、その配線長はセル間のマンハッタン距離に等しくなる。つまりセル間のマンハッタン距離の差が、そのまま配線長の差となって現れる。逆に言えば、セル間のマンハッタン距離を揃えることができれば、基本的にはそれを接続する配線の長さが揃うであろう。しかし従来の自動配置配線装置は、自動的にそのようにセルを配置する機能を有していない。
【０００６】
またセル間のマンハッタン距離が揃っていたとしても、他の配線によって経路を妨げられるなどの理由で、配線を迂回させざるを得ない場合もあり、必ずしも配線長が揃うとは限らない。従って従来の自動配置配線装置で特定のノードの配線長を揃えるには、そのノードの配線を他の配線よりも優先的に引き、他の配線の方を迂回させればよい。しかし特定のノードを必ずしも最優先に配線できるとは限らず、その場合は人の手を介して配線を引き直す必要があった。よって、複数のノードの配線長を揃えようとすると、多大な労力がかかっていた。
【０００７】
またセル間のマンハッタン距離が揃っていたとしても、配線禁止領域によって経路を妨げられるなどの理由で、配線を迂回させざるを得ない場合もあり、配線可能な最短経路長が特定のノード毎に異なってしまうことがある。この場合は特定のノードを優先的に配線したとしても配線長を揃えることができず、人の手を介して配線を引き直す必要があった。よって、複数のノードの配線長を揃えようとすると、多大な労力がかかっていた。
【０００８】
上記のとおり従来の自動配置配線装置においても、パスごとの遅延時間に制約を与えて自動制御すれば、複数のパスにおける信号の遅延時間を揃えることは可能であった。しかし、自動制御で考慮される遅延時間は理論的なものであり、各々のパスのセルサイズや配線長などを実際に揃えるわけではない。そのため、半導体装置の製造ばらつきや使用環境の変化による特性変動が生じたときに、揃えたはずの遅延時間にパスごとのばらつきが生じていた。
【０００９】
つまり従来の自動配置配線装置により信号の遅延時間を揃えても、製造ばらつきや使用環境に応じた遅延時間のばらつきまでは抑えることは困難であった。例えばクロック信号線などは、比較的高い精度でタイミング制御する必要があるため、その遅延時間のばらつきは問題となる。そして従来はこの問題を回避するためにも、やはり人の手を介して特定のノードの配線長を揃えるなど、多大な労力を要していた。
【００１０】
本発明は以上のような課題を解決するためになされたものであり、自動的な制御により特定の複数の配線経路における遅延時間のばらつきを抑制できる自動配置配線装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明に係る自動配置配線装置は、複数の指定された配線ノード（指定ノード）について、それらの配線長を揃える配線長調整機能を備えるものである。
【発明の効果】
【００１２】
本発明によれば、複数の指定ノードの配線長が自動的に揃えられる。その結果、当該指定ノードにおける、製造ばらつきや使用環境に起因する信号の遅延時間の変動を抑えることができ、半導体装置の信頼性の向上に寄与できる。また、これまで配線長を揃えるために行われていた人的作業を減らすことができ、設計者・製造者の労力を削減することができる。
【発明を実施するための最良の形態】
【００１３】
＜実施の形態１＞
本実施の形態に係る自動配置配線装置は、特定の複数の配線ノード（以下単に「ノード」）について、それらの配線長を揃える配線長調整機能を有するものである。
【００１４】
図１は、当該機能を説明するためのフロー図である。本実施の形態に係る自動配置配線装置では、まず設計者側で予め設定した情報に基づき、配線長を揃えたい複数のノードが指定される（Ｓ１）。そして指定されたノード（指定ノード）の配線長を揃える配線処理が自動的に行われる（Ｓ２）。
【００１５】
図２を参照し、当該機能をより具体的に説明する。ここでは、上記ステップＳ１において図２に示す３つのノード、すなわちセルＣ１ａ，Ｃ１ｂを接続するノードＮ１と、セルＣ２ａ，Ｃ２ｂを接続するノードＮ２と、セルＣ３ａ，Ｃ３ｂを接続するノードＮ３とが、配線長を揃えるノードとして指定されたものとする。
【００１６】
セルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）、セルＣ２ａ，Ｃ２ｂ間のマンハッタン距離Ｄ（Ｎ２）、セルＣ３ａ，Ｃ３ｂ間のマンハッタン距離Ｄ（Ｎ３）は、それぞれ異なっている。従来の自動配置配線装置であれば、原則としてセル間を最短距離で配線するため、ノードＮ１〜Ｎ３の配線長はそれぞれマンハッタン距離Ｄ（Ｎ１）〜Ｄ（Ｎ３）と等しくなり、その結果、ノードＮ１〜Ｎ３の配線は互いに異なる長さになっていた。
【００１７】
それに対し、本実施の形態に係る自動配置配線装置は、最短距離で配線することに拘らず、指定されたノードＮ１〜Ｎ３の各配線長Ｌ（Ｎ１）〜Ｌ（Ｎ３）を全て等しくすることに重点を置いて配線する。
【００１８】
この配線長調整機能を実現するためには、自動配置配線装置が、各指定ノードの配線長を所望の値（目標値）にするように調整する機能を有していることが必要である。本実施の形態の自動配置配線装置は、配線長を調整する機能として、配線を意図的に迂回させる機能を有している。
【００１９】
この配線の迂回機能について説明する。図３（ａ）を参照し、例えばセルＣ１ａ，Ｃ１ｂ間のノードＮ１を、最短距離で配線すると、同図の如く配線長Ｌ（Ｎ１）はセルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）と同じになる。しかし本実施の形態の自動配置配線装置は、図３（ｂ）のように配線を意図的に迂回させ、あえて配線長Ｌ（Ｎ１）をマンハッタン距離Ｄ（Ｎ１）よりも長くする。その際、配線の迂回経路の長さ調整することで配線長Ｌ（Ｎ１）の調整を行うのである。
【００２０】
ここで迂回経路の調整方法を説明する。例えば図４（ａ）に示すセルＣ１ａ，Ｃ１ｂ間のノードＮ１を最短距離（マンハッタン距離）で配線すると、同図の如く配線長Ｌ（Ｎ１）はセルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）と同じになる。本実施の形態の自動配置配線装置は、この配線長を調整するために、セルＣ１ａ，Ｃ１ｂの間にノードＮ１の配線が経由すべき「通過ポイント」を想定する。ここではその通過ポイントとして、図４（ｂ）の如く仮想のセルＣｖ（仮想セル）を発生させる。
【００２１】
またこのときノードＮ１を、セルＣ１ａと仮想セルＣｖ間のノードＮ１ａと、仮想セルＣｖとセルＣ１ｂ間のノードＮ１ｂとに一時的に分割する。そしてセルＣ１ａと仮想セルＣｖとのマンハッタン距離Ｄ（Ｎ１ａ）、仮想セルＣｖとセルＣ１ｂとのマンハッタン距離Ｄ（Ｎ１ｂ）の和が、ノードＮ１についての配線長の目標値（目標配線長）となるように、仮想セルＣｖの位置を調整する。そしてマンハッタン距離Ｄ（Ｎ１ａ），Ｄ（Ｎ１ｂ）の和がノードＮ１の目標配線長となる仮想セルＣｖの位置が定まれば、そこに仮想セルＣｖの固定し、ノードＮ１ａ，Ｎ１ｂを配線する。
【００２２】
その後は図３（ｃ）の如く、ノードＮ１ａ，Ｎ１ｂをノードＮ１として結合すると共に、仮想セルＣｖを消去する。自動配置配線装置が以上の動作を自動的制御により行うことで、配線長の自動調整機能を実現できる。
【００２３】
なお、ここでは通過ポイントとして、セルＣ１ａ，Ｃ１ｂと同様の仮想セルを用いたが、必ずしも通過ポイントは「セル」である必要はない。例えば、後述する実施の形態７のように、配線が複数の配線層に跨って構成されており、配線を特定の配線層で迂回させたい場合には、その配線層内に通過ポイントを設ければよい。但し、通過ポイントを仮想の「セル」とした場合、それは通常のセルと同じように取り扱うことができるため、例えば既存の自動配置配線装置に本発明を適用することが、比較的容易になるという利点がある。
【００２４】
また図３（ａ）〜（ｃ）では最も単純な迂回の例を示したが、この手法は迂回経路をより複雑にしたい場合（例えば図１３（ｂ），（ｃ）等）にも応用可能である。その場合は、一のノード上に通過ポイントを複数個設け、それにより分割したノードの総和が、そのノードの目標配線長となるように、複数の通過ポイントそれぞれの位置決めを行えばよい。
【００２５】
以上のように本実施の形態によれば、複数の指定ノードの配線長を自動的に揃えることができる。その結果、当該指定ノードにおける、製造ばらつきや使用環境に起因する信号の遅延時間の変動を抑えることができ、半導体装置の信頼性の向上に寄与できる。また、これまで配線長を揃えるために行われていた人的作業を減らすことができ、設計者・製造者の労力を削減することができる。
【００２６】
＜実施の形態２＞
図５は、実施の形態２に係る配線長調整機能を説明するためのフロー図である。本実施の形態に係る自動配置配線装置は、予め設計者側で設定した情報に基づき、まず配線長を揃えたい複数のノードが指定されると共に（Ｓ１１）、その指定ノードの配線長の目標値（目標配線長）が指定される（Ｓ１２）。そして各指定ノードの配線長を、その目標配線長に揃えるための配線処理が自動的に行われる（Ｓ１３）。
【００２７】
本実施の形態の配線長調整機能をより具体的に説明する。ここでは、上記ステップＳ１１において図６に示す２つのノード、すなわちセルＣ１ａ，Ｃ１ｂを接続するノードＮ１と、セルＣ２ａ，Ｃ２ｂを接続するノードＮ２とが、配線長を揃えるノードとして指定されたものとする。
【００２８】
本実施の形態では、上記ステップＳ１２にて、それら指定ノードの目標配線長Ｔも指定される。自動配置配線装置は、ノードＮ１，Ｎ２の各配線長Ｌ（Ｎ１），Ｌ（Ｎ２）が、共に目標配線長Ｔに揃うように配線を引く。その結果、ノードＮ１，Ｎ２の配線長Ｌ（Ｎ１），Ｌ（Ｎ２）が等しく揃うことになる。自動配置配線装置が、各指定ノードの配線長を目標配線長Ｔにする際には、図６の如く配線を迂回させる手法をとればよい。当該手法については実施の形態１で説明したとおりであるので、ここでの説明は省略する。
【００２９】
本実施の形態においては、実施の形態１で説明した効果に加え、指定ノードの配線長を設計者側で設定できるため、当該配線経路における信号の遅延時間をより厳格に管理することが可能になるという効果が得られる。
【００３０】
＜実施の形態３＞
実施の形態２においては、指定ノードの目標配線長Ｔを設計者側で設定していたが、本実施の形態では、その目標配線長Ｔを、当該指定ノードが接続するセル間のマンハッタン距離の最大値に自動的に設定する。
【００３１】
例えば、自動配置配線装置によって、図７（ａ）に示す３つのノード、すなわちセルＣ１ａ，Ｃ１ｂを接続するノードＮ１と、セルＣ２ａ，Ｃ２ｂを接続するノードＮ２と、セルＣ３ａ，Ｃ３ｂを接続するノードＮ３とが、配線長を揃えるノードとして指定されたものとする。この場合、セルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）、セルＣ２ａ，Ｃ２ｂ間のマンハッタン距離Ｄ（Ｎ２）、セルＣ３ａ，Ｃ３ｂ間のマンハッタン距離Ｄ（Ｎ３）のうちの最大値が、目標配線長Ｔとして自動的に設定される。この例ではマンハッタン距離Ｄ（Ｎ２）が最も大きいため、それが目標配線長Ｔとして設定される。
【００３２】
このようにして目標配線長Ｔが定まれば、それ以降は実施の形態２と同様に指定ノードを目標配線長Ｔに揃える配線処理が行われる。即ちノードＮ１〜Ｎ３の各配線長Ｌ（Ｎ１）〜Ｌ（Ｎ３）を全て目標配線長Ｔ（ここではマンハッタン距離Ｄ（Ｎ２））に揃える配線処理が行われる。その結果、図７（ｂ）の如く、ノードＮ１〜Ｎ３の配線長Ｌ（Ｎ１）〜Ｌ（Ｎ３）は全て同じになる。
【００３３】
本実施の形態によれば、自動配置配線装置が目標配線長Ｔを自動的に設定するので、実施の形態２のように目標配線長を設計者側で設定しておく必要がない。つまり設計者側で設定する必要のあるパラメータが減るため、実施の形態１で説明した効果を、容易な手順で得ることができるようになる。
【００３４】
＜実施の形態４＞
実施の形態４では、自動配置配線装置が目標配線長Ｔを自動的に設定する手法の他の例を示す。
【００３５】
図８は実施の形態４に係る自動配置配線装置の機能を説明するフロー図である。本実施の形態に係る自動配置配線装置は、予め設計者が設定した情報に基づき、まず配線長を揃える複数のノードを指定する（Ｓ２１）。次いで、その指定ノードについてのみ配線処理を行う（Ｓ２２）。そしてその配線処理の結果得られた各指定ノードの配線長の最大値を求め、その値を目標配線長Ｔとして設定する（Ｓ２３）。そして実施の形態２と同様に、各指定ノードの配線長を目標配線長Ｔに揃えるための配線処理が自動的に行われる（Ｓ２４）。また、指定ノード以外の残りのノードについての配線処理はこの後で行う（Ｓ２５）。
【００３６】
例えば図９（ａ）に示す２つのノード、すなわちセルＣ１ａ，Ｃ１ｂを接続するノードＮ１と、セルＣ２ａ，Ｃ２ｂを接続するノードＮ２とが、配線長を揃えるノードとして指定されたものとする。すると自動配置配線装置は、そのノードＮ１，Ｎ２についてのみ配線処理を行う。その結果、同図に示すような配線が引かれたとする。
【００３７】
続いて当該自動配置配線装置は、上記の配線処理によって引かれたノードＮ１，Ｎ２の配線長Ｌ（Ｎ１），Ｌ（Ｎ２）を求め、そのうちの最大値を目標配線長Ｔとして設定する。図９（ａ）の例では配線長Ｌ（Ｎ１），Ｌ（Ｎ２）では、配線長Ｌ（Ｎ２）の方が大きいため、それが目標配線長Ｔとして設定される。
【００３８】
このようにして目標配線長Ｔが定まれば、それ以降は実施の形態２と同様に指定ノードを目標配線長Ｔに揃える配線処理が行われる。即ちノードＮ１の各配線長Ｌ（Ｎ１）を目標配線長Ｔ（ここでは配線長Ｌ（Ｎ２））に揃える配線処理が行われる。その結果、図９（ｂ）の如く、ノードＮ１，Ｎ２の配線長Ｌ（Ｎ１），Ｌ（Ｎ２）が等しくなる。
【００３９】
本実施の形態によれば、自動配置配線装置が目標配線長Ｔを自動的に設定するので、実施の形態３と同様に、目標配線長を設計者側で設定する必要がない。つまり設計者側で指定する必要のあるパラメータが減るため、実施の形態１で説明した効果を、容易な手順で得ることができるようになる。
【００４０】
また上記のように、本実施の形態では配線処理によって各指定ノードの配線を一旦引いてから、その後それらの配線長を揃える処理が行われる。従って、配線禁止領域（例えばノイズの影響を受けやすいアナログ回路上の領域）を避けるための配線の迂回など、実際に配線処理を行うときに考慮すべき具体的な要素を考慮に入れての処理が可能になる。
【００４１】
＜実施の形態５＞
実施の形態４では、図８のフロー図からも分かるように、指定ノードの配線の配線処理（Ｓ２２）を、それ以外の配線処理（Ｓ２５）に先立って行っている。つまり指定ノードの配線を最も高い優先度で引き、その後にそれ以外の配線を引いている。優先度の高い配線は、原則としてセル間を最短距離で接続するように自動配線される。
【００４２】
しかし実際には、指定ノードを最も高い優先度で配線処理すべきでない場合も考えられる。例えば、クロック信号の遅延を抑える必要がある場合には、クロック信号線が指定ノードでなかったとしても、最優先で配線すべきである。
【００４３】
図１０は実施の形態５に係る自動配置配線装置の機能を説明するフロー図である。本実施の形態に係る自動配置配線装置は、指定ノードか否かに関係なく、まず全てのノードについての配線処理を行い（Ｓ３１）、その後に配線長を揃えたい複数のノードを指定する（Ｓ３２）。続いて当該自動配置配線装置は、上記の配線処理の結果得られた各指定ノードの配線の長さの最大値を求め、その値を目標配線長Ｔとして設定する（Ｓ３３）。その後は実施の形態２と同様に、各指定ノードの配線長を目標配線長Ｔに揃えるための処理が自動的に行われる（Ｓ３４）。
【００４４】
本実施の形態においても、自動配置配線装置が目標配線長Ｔを自動的に設定するので、実施の形態３と同様に、目標配線長を設計者側で指定する必要がない。つまり設計者側で指定する必要のあるパラメータが減るため、実施の形態１で説明した効果を、容易な手順で得ることができるようになる。
【００４５】
また本実施の形態では、実際の配線処理によって全ノードの配線を引いてから、その後に指定ノードの配線長を揃える処理が行われる。従って、指定ノードよりも優先度の高い他の配線を避けるための迂回を、指定ノードの配線処理の際に考慮に入れることができる。つまり、実施の形態４よりもさらに具体的な要素を考慮に入れての、指定ノードの配線処理が可能になる。
【００４６】
＜実施の形態６＞
実施の形態４では、図８のフロー図からも分かるように、指定ノードの配線の配線処理（Ｓ２２）を、それ以外の配線処理（Ｓ２５）に先立って行っている。つまり指定ノードの配線を最も高い優先度で引き、その後にそれ以外の配線を引いている。優先度の高い配線は、原則としてセル間を最短距離で接続するように自動配線される。
【００４７】
しかし実際には、指定ノードを最も高い優先度で配線処理すべきでない場合も考えられる。例えば、クロック信号の遅延を抑える必要がある場合には、クロック信号線が指定ノードでなかったとしても、最優先で配線すべきである。
【００４８】
図１８は実施の形態６に係る自動配置配線装置の機能を説明するフロー図である。本実施の形態に係る自動配置配線装置は、まず優先的に配線すべきノードについてのみ配線処理を実施しておく（Ｓ４１）。この処理は既存技術を利用すればよい。この処理を実施した状態から、実施の形態４と同じ処理（Ｓ４２〜Ｓ４６）を実施する。
【００４９】
本実施の形態においても、自動配置配線装置が目標配線長Ｔを自動的に設定するので、実施の形態３と同様に、目標配線長を設計者側で指定する必要がない。つまり設計者側で指定する必要のあるパラメータが減るため、実施の形態１で説明した効果を、容易な手順で得ることができるようになる。
【００５０】
また優先的に配線すべきノードの配線処理が終了している状態から、実施の形態４を実施することで、指定ノードよりも優先度の高い他の配線を避けるための迂回を、指定ノードの配線処理の際に考慮に入れることができる。つまり、実施の形態４よりもさらに具体的な要素を考慮に入れての、指定ノードの配線処理が可能になる。
【００５１】
また優先的に配線すべきノードの配線処理（Ｓ４１）および指定された複数のノードの配線長を揃える処理（Ｓ４３）が行われてから、その後に残りのノードの配線処理（Ｓ４６）が行われる。従って、上記残りのノードの配線に邪魔されること無く配線長を揃える処理を行うことができるため、実施の形態５よりも比較的安易に指定ノードの配線長を揃える処理を行うことができ、また実施の形態５よりも、それを短い配線長で揃えることができる可能性が高くなる。
【００５２】
＜実施の形態７＞
高集積化が進んだ現在の半導体装置では、半導体装置は多層配線構造をとるものが多く、１つのノードの配線が複数の層に跨っている場合も考えられる。そこで実施の形態７では、自動配置配線装置に、複数の配線層に跨った構造を有する配線の長さを調整する際に、配線の迂回を行う配線層を指定する機能を持たせる。
【００５３】
図１１は実施の形態７に係る自動配置配線装置の機能を説明する図である。当該自動配置配線装置では、設計者は、予め指定ノードの配線をどの配線層で迂回させるのか設定可能である。当該自動配置配線装置は、指定ノードの配線を迂回させるとき、その指定された層でそれを行う。
【００５４】
例えば上記した実施の形態１〜５において、図１１（ａ）の如く第１，第２の配線層に跨ったノードＮ１の配線に対しての、配線長の調整を行う必要が生じたとする。また自動配置配線装置には、第２の配線層で迂回を行うように予め設定されていたとする。この場合、自動配置配線装置は、図１１（ｂ）のようにノードＮ１の配線の第２の配線層に属する部分を迂回させることで、配線長の調整を行う。
【００５５】
一般に、配線の幅や厚さは配線層によって異なることが多く、指定ノードごとに異なる配線層で迂回をすると、その迂回によって信号の遅延時間にばらつきが生じることが懸念される。その点、本実施の形態では、迂回させる配線層を指定できるため、各指定ノードが同じ配線層で迂回を行うように設定すれば、そのばらつきの発生を抑えることができる。
【００５６】
＜実施の形態８＞
実施の形態８においては、本発明の自動配置配線装置に、複数の配線層を用いて配線の迂回経路を形成する機能を持たせる。図１２は当該機能を説明するための図である。
【００５７】
例えば上記した実施の形態１〜５において、本来は図１２（ａ）の如く第１配線層のみから成るノードＮ１の配線に対し、その配線長の調整を行う必要が生じたとする。本実施の形態では、例えば図１２（ｂ）のように、第１配線層上の第２，第３配線層を用いてその迂回経路を形成し、それによって配線長の調整を行う。
【００５８】
本実施によれば、同一配線層内での迂回経路だけでなく、複数の配線層に跨った迂回経路も選択できるため、迂回経路の選択肢が増える。配線を迂回させるときには、それによる他の配線への影響をより小さくなるように経路を選択すること望ましいが、迂回経路の選択肢が増えることでそれが容易になる。
【００５９】
＜実施の形態９＞
実施の形態９では、本発明の自動配置配線装置に、配線長の調整のために配線を迂回させる際、互いに隣接する２又は３の配線トラックのみの使用に限定させる機能を持たせる。
【００６０】
図１３は当該機能を説明するための図である。例えば図１３（ａ）のように、ノードＮ１の配線の迂回経路として、配線トラックＴｒ２〜Ｔｒ６に跨る経路が形成された場合、当該迂回経路の存在によりトラックＴｒ１〜Ｔｒ６を他の配線が使用できなくなり、半導体装置の高集積化の妨げとなり得る。つまり迂回経路が使用するトラック数はできるだけ少ない方がよい。そこで本実施の形態では、迂回経路が使用するトラックを２又は３に限定する。
【００６１】
例えば図１３（ｂ）は、トラックＴｒ１上に位置するセルＣ１ａ，Ｃ１ｂ間のノードＮ１の配線に対し、互いに隣接するトラックＴｒ１，Ｔｒ２のみを使用して迂回経路を形成した例である。迂回経路はトラックＴｒ１，Ｔｒ２間をジグザグに引かれる。この場合、同図のトラックＴｒ３〜Ｔｒ５は迂回経路に使用されないため、他の配線が使用することができる。
【００６２】
但し、例えばセルＣ１ａ，Ｃ１ｂ間のマンハッタン距離が極めて短い場合には、図１３（ｂ）の手法では充分な長さの迂回経路を確保できないことが考えられる。その場合には図１３（ｃ）の如く、隣接する３つのトラックＴｒ１〜Ｔｒ３を使用して迂回経路を形成すればよい。即ちトラックＴｒ１から迂回した配線をトラックＴｒ２，トラックＴｒ３に上に長く延在させれば、セルＣ１ａ，Ｃ１ｂ間のマンハッタン距離に関係なく長距離の迂回経路を確保できる。
【００６３】
本実施の形態によれば、迂回経路に使用されるトラック数が少なくなるので、効率の良い配線が可能であり、半導体装置の高集積化に寄与できる。
【００６４】
＜実施の形態１０＞
以上の実施の形態においては、全ての指定ノードの配線長を揃えることを前提としていたが、必要とされる精度によっては、全指定ノードの配線長が完全に一致する必要はなく、ある程度同じ長さであればよい場合もある。そこで実施の形態１０では、本発明の自動配置配線装置に、予め設計者側で設定した許容範囲から外れたものに対してのみ配線長を揃える機能を持たせる。
【００６５】
図１４は、実施の形態１０に係る自動配置配線装置の機能を説明する図であり、本実施の形態を、前述の実施の形態２に適用した例である。
【００６６】
例えば、配線長を揃えるノードとして、図１４（ａ）に示す３つのノード、すなわちセルＣ１ａ，Ｃ１ｂを接続するノードＮ１と、セルＣ２ａ，Ｃ２ｂを接続するノードＮ２と、セルＣ３ａ，Ｃ３ｂを接続するノードＮ３とが指定されたとする。そして所定の目標配線長Ｔ（この例ではセルＣ２ａ，Ｃ２ｂ間のマンハッタン距離）が指定されたとする。本実施の形態ではさらに、予め設計者で設定した情報に基づいて、当該目標配線長Ｔに対する許容範囲が指定される。許容範囲の設定の方法は任意でよいが、例えば図１４（ａ）に示すように許容最大値Ｔｍａｘおよび許容最小値Ｔｍｉｎを設定し、その間を許容範囲とするのが簡単な方法の１つである。
【００６７】
同図の如く、この例ではノードＮ１，Ｎ２の配線長は許容範囲内であり、ノードＮ３の配線長のみが許容範囲から外れている。この場合は、ノードＮ１，Ｎ２に対しては配線長の調整は行わず、ノードＮ３に対してのみ配線を迂回させ、配線長を目標配線長Ｔに揃える処理が行われる。
【００６８】
本実施の形態のように、指定された配線長にある程度の許容範囲をもたせることで、配線長の調整を行う必要があるノードの数を少なくできることが見込まれる。従って、本発明に係る自動配置配線に要する処理時間の短縮化に寄与できる。
【００６９】
なお、ここでは本実施の形態を実施の形態２に適用した例を示したが、本実施の形態はその他全ての実施の形態に対しても適用可能である。
【００７０】
＜実施の形態１１＞
以上の実施の形態においては、指定ノードの配線を迂回させることでその配線長を調整する手法を示したが、本実施の形態ではそれとは異なる手法を示す。
【００７１】
即ち、本実施の形態の自動配置配線装置は、指定ノードの配線長を目標値（目標配線長）にする場合に、当該指定ノードが接続するセルの位置を移動させる。
【００７２】
図１５は実施の形態１１に係る自動配置配線装置の機能を説明する図である。例えば図１５（ａ）に示す３つのノード、すなわちセルＣ１ａ，Ｃ１ｂを接続するノードＮ１と、セルＣ２ａ，Ｃ２ｂを接続するノードＮ２と、セルＣ３ａ，Ｃ３ｂを接続するノードＮ３とが、配線長を揃えるノードとして指定されたものとする。
【００７３】
ここで指定ノードの目標配線長Ｔが指定される。目標配線長Ｔは、例えば実施の形態２のように予め設計者が設定した値が指定されてもよいが、本実施の形態では、実施の形態３のように指定ノードが接続するセル間のマンハッタン距離の最大値に自動的に設定されるものとする。
【００７４】
図１５（ａ）の例では、セルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）、セルＣ２ａ，Ｃ２ｂ間のマンハッタン距離Ｄ（Ｎ２）、セルＣ３ａ，Ｃ３ｂ間のマンハッタン距離Ｄ（Ｎ３）のうち、マンハッタン距離Ｄ（Ｎ２）が最も大きいため、それが目標配線長Ｔとして設定される。
【００７５】
このようにして目標配線長Ｔが定まれば、指定ノードを目標配線長Ｔに揃える配線処理が行われる。即ちノードＮ１〜Ｎ３の各配線長Ｌ（Ｎ１）〜Ｌ（Ｎ３）を全て目標配線長Ｔ（ここではマンハッタン距離Ｄ（Ｎ２））に揃える配線処理が行われる。本実施の形態の自動配置配線装置は、セルＣ１ｂ，Ｃ３ｂの位置を、マンハッタン距離Ｄ（Ｎ１），Ｄ（Ｎ３）が共に目標配線長Ｔと等しくなるところに移動させる。そして、セルＣ１ａ，Ｃ１ｂ間、セルＣ２ａ，Ｃ２ｂ間およびセルＣ３ａ，Ｃ３ｂ間のそれぞれに、最短距離（マンハッタン距離）で接続する配線を引く。その結果、図１５（ｂ）の如く、ノードＮ１〜Ｎ３の配線長Ｌ（Ｎ１），Ｌ（Ｎ２），Ｌ（Ｎ３）は全て揃うことになる。
【００７６】
本実施の形態においても、指定ノードの配線長を揃えることができるので、実施の形態１で説明した効果を得ることができる。また、自動配置配線装置が目標配線長Ｔを自動的に設定するので、実施の形態３と同様に、目標配線長を設計者側で指定する必要がないという効果が得られる。
【００７７】
なお、図１５においては、配線長の調整の際、信号の出力先（信号を受ける側）のセルＣ１ｂ，Ｃ３ｂの位置を移動させたが、信号の出力元（信号を出力する側）のセルＣ１ａ，Ｃ３ａの方の位置を移動させてもよい。
【００７８】
また本実施の形態のようにセルの位置を移動させる手法と、上記した実施の形態１〜１０のように配線を迂回させる手法とを組み合わせてもよい。
【００７９】
＜実施の形態１２＞
配線を迂回させる手法では、配線長を長くすることしかできないため、目標配線長Ｔは、必然的に指定ノードが接続するセル間のマンハッタン距離の最大値以上に設定される必要があった。それに対し、セルの位置を移動させる手法では、配線長を長くすることも短くすることもできるので、理論的には目標配線長Ｔを任意の値に設定することが可能である。
【００８０】
そこで本実施の形態では、セルの位置を移動させる手法において、目標配線長Ｔを指定ノードが接続するセル間のマンハッタン距離の最小値とする。
【００８１】
図１６を用いて具体的に説明する。例えば図１６（ａ）に示す３つのノードＮ１〜Ｎ３が、配線長を揃えるノードとして指定されたものとする。本実施の形態では、セルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）、セルＣ２ａ，Ｃ２ｂ間のマンハッタン距離Ｄ（Ｎ２）、セルＣ３ａ，Ｃ３ｂ間のマンハッタン距離Ｄ（Ｎ３）のうちの最小値が、目標配線長Ｔとして設定される。この例では図１６（ａ）に示すようにマンハッタン距離Ｄ（Ｎ３）が最も小さいため、それの値が目標配線長Ｔとされる。
【００８２】
目標配線長Ｔが定まれば、指定ノードを目標配線長Ｔに揃える配線処理が行われる。即ちノードＮ１〜Ｎ３の各配線長Ｌ（Ｎ１）〜Ｌ（Ｎ３）を全て目標配線長Ｔ（ここではマンハッタン距離Ｄ（Ｎ３））に揃える配線処理が行われる。本実施の形態では、セルＣ１ｂ，Ｃ２ｂの位置を動かし、セルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）およびセルＣ２ａ，Ｃ２ｂのマンハッタン距離Ｄ（Ｎ２）を共に目標配線長Ｔに等しくする。そして、セルＣ１ａ，Ｃ１ｂ間、セルＣ２ａ，Ｃ２ｂ間およびセルＣ３ａ，Ｃ３ｂ間のそれぞれに、最短距離（マンハッタン距離）で接続する配線を引く。その結果、図１６（ｂ）の如く、ノードＮ１〜Ｎ３の配線長Ｌ（Ｎ１）〜Ｌ（Ｎ３）は全て揃うことになる。
【００８３】
本実施の形態においても実施の形態１１と同様の効果が得られる。また、本実施の形態のように目標配線長Ｔをより短く設定した場合には、配線長を揃えた後の指定ノードにおいて、信号の遅延時間のばらつきが少なくなるという利点もある。
【００８４】
＜実施の形態１３＞
本実施の形態１３では、セルの位置を移動させる手法において、目標配線長Ｔを指定ノードが接続するセル間のマンハッタン距離の平均値とする。
【００８５】
図１７を用いて具体的に説明する。例えば図１７（ａ）に示す３つのノードＮ１〜Ｎ３が、配線長を揃えるノードとして指定されたものとする。本実施の形態では、セルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）、セルＣ２ａ，Ｃ２ｂ間のマンハッタン距離Ｄ（Ｎ２）、セルＣ３ａ，Ｃ３ｂ間のマンハッタン距離Ｄ（Ｎ３）の平均値が、目標配線長Ｔとして設定される。
【００８６】
目標配線長Ｔが定まれば、指定ノードを目標配線長Ｔに揃える配線処理が行われる。即ちノードＮ１〜Ｎ３の各配線長Ｌ（Ｎ１）〜Ｌ（Ｎ３）を全て目標配線長Ｔ（ここではマンハッタン距離Ｄ（Ｎ１）〜Ｄ（Ｎ３）の平均値）に揃える配線処理が行われる。本実施の形態では、セルＣ１ｂ，Ｃ２ｂ，Ｃ３ｂの位置を動かし、セルＣ１ａ，Ｃ１ｂ間のマンハッタン距離Ｄ（Ｎ１）、セルＣ２ａ，Ｃ２ｂ間のマンハッタン距離Ｄ（Ｎ２）およびセルＣ３ａ，Ｃ３ｂのマンハッタン距離Ｄ（Ｎ３）を全て目標配線長Ｔに等しくする。そして、セルＣ１ａ，Ｃ１ｂ間、セルＣ２ａ，Ｃ２ｂ間およびセルＣ３ａ，Ｃ３ｂ間のそれぞれに、最短距離（マンハッタン距離）で接続する配線を引く。その結果、図１７（ｂ）の如く、ノードＮ１〜Ｎ３の配線長Ｌ（Ｎ１）〜Ｌ（Ｎ３）は全て揃うことになる。
【００８７】
本実施の形態においても実施の形態１１と同様の効果が得られる。また、本実施の形態のように目標配線長Ｔを、指定ノードが接続するセル間のマンハッタン距離の平均値とすることで、指定ノードそれぞれの配線長の調整の際に、セルを移動させる量を全体的に少なくできる。実施の形態１１のように目標配線長Ｔをマンハッタン距離の最大値とする場合、例えば指定ノードの中に極端にマンハッタン距離の長いものが１つ含まれていただけでも、それに全ての指定ノードを合わせる必要があるので不経済である。本実施の形態ではそのような自体を回避して、効率のよい配線処理を行うことができる。
【図面の簡単な説明】
【００８８】
【図１】実施の形態１に係る自動配置配線装置の機能を説明するフロー図である。
【図２】実施の形態１に係る自動配置配線装置の機能を説明する図である。
【図３】実施の形態１に係る自動配置配線装置の機能を説明する図である。
【図４】実施の形態１に係る自動配置配線装置の機能を説明する図である。
【図５】実施の形態２に係る自動配置配線装置の機能を説明する図である。
【図６】実施の形態２に係る自動配置配線装置の機能を説明するフロー図である。
【図７】実施の形態３に係る自動配置配線装置の機能を説明する図である。
【図８】実施の形態４に係る自動配置配線装置の機能を説明するフロー図である。
【図９】実施の形態４に係る自動配置配線装置の機能を説明する図である。
【図１０】実施の形態５に係る自動配置配線装置の機能を説明するフロー図である。
【図１１】実施の形態７に係る自動配置配線装置の機能を説明する図である。
【図１２】実施の形態８に係る自動配置配線装置の機能を説明する図である。
【図１３】実施の形態９に係る自動配置配線装置の機能を説明する図である。
【図１４】実施の形態１０に係る自動配置配線装置の機能を説明する図である。
【図１５】実施の形態１１に係る自動配置配線装置の機能を説明する図である。
【図１６】実施の形態１２に係る自動配置配線装置の機能を説明する図である。
【図１７】実施の形態１３に係る自動配置配線装置の機能を説明する図である。
【図１８】実施の形態６に係る自動配置配線装置の機能を説明するフロー図である。
【符号の説明】
【００８９】
Ｃ１ａ〜Ｃ３ａ，Ｃ１ｂ〜Ｃ３ｂ  セル、Ｃｖ  仮想セル、Ｎ１〜Ｎ３  ノード、Ｔｒ１〜Ｔｒ４  トラック。
【図１】
2009032051.tif 000003
【図２】
2009032051.tif 000004
【図３】
2009032051.tif 000005
【図４】
2009032051.tif 000006
【図５】
2009032051.tif 000007
【図６】
2009032051.tif 000008
【図７】
2009032051.tif 000009
【図８】
2009032051.tif 000010
【図９】
2009032051.tif 000011
【図１０】
2009032051.tif 000012
【図１１】
2009032051.tif 000013
【図１２】
2009032051.tif 000014
【図１３】
2009032051.tif 000015
【図１４】
2009032051.tif 000016
【図１５】
2009032051.tif 000017
【図１６】
2009032051.tif 000018
【図１７】
2009032051.tif 000019
【図１８】
2009032051.tif 000020