JP4326462B2 - 半導体集積回路の設計を支援する設計支援装置、設計支援プログラム、及び設計支援方法 - Google Patents

Description

本発明は、半導体集積回路の設計を支援する設計支援装置、設計支援方法、設計支援プログラムに関し、特に、半導体集積回路に含まれるセル（論理ゲートを複数組み合わせて、それぞれ異なる機能を実現するもの）間を、斜め配線を用いて接続する場合の設計を支援する設計支援装置等に関する。

一般に、半導体集積回路における配線は、論理ゲートを複数組み合わせて、それぞれ異なる機能を実現するセル（例えば、フリップフロップ、カウンタ、セレクタ、マルチプレクサ、加算器等）を、基板となるシリコンウェハ上に配置した後に行われる。半導体集積回路は、基板上にアルミニウム等の配線層が何重かに重なる多層構造をしており、最下層に接するある半導体素子の出力端子と別の半導体素子の入力端子は、この配線層を用いて接続される。

各配線層においては、配線層を上から眺めたとき、縦方向又は横方向の配線が配置されるが、近年、縦方向又は横方向の配線に加えて、斜め方向（例えば、４５度方向、１３５度方向）の配線を用いた半導体集積回路が提案されている。例えば、特許文献１によれば、斜め配線を含む多層配線を用いることで配線領域を小さくする半導体集積回路装置が提案され、特許文献２によれば、斜め配線を用いる場合に、配線層同士を接続するための接続孔の位置が合わせられた半導体集積回路装置が提案され、特許文献３によれば、斜め配線のピッチ間隔を所定長にすることでクロストークが防止された半導体集積回路が提案される。

半導体集積回路の設計にあたり、設計者は、PC(Personal Computer)等の情報処理装置と専用のソフトウェアツールを用いて、セルが基板に配置された状態を再現する。設計段階で行われるセル間の配線は、設計者により手動で、又は、専用ツールにより自動で行われる。
特開平５−２４３３７９号公報 特開２０００−８２７４３号公報 特開平１−１１２７４９号公報

しかしながら、従来技術においては、セル同士を接続する複数の経路のうち、どの経路に対して斜め配線を適用すべきかについて明確な基準や有効な判断手法がなく、むやみに斜め配線を配置することによって、かえって縦方向や横方向の配線（従来配線）を迂回させる必要が生じる、あるいは、従来配線の迂回を防止するため配線層を増やさなければならない事態が生じていた。また、斜め配線を適用しても意味がない経路に対して斜め配線が適用されることもあり、斜め配線を有効に活用した設計が行われないでいた。

そこで、本発明の目的は、斜め配線を有効に活用してセル間の配線設計を行うことのできる設計支援装置、及び関連するプログラム、設計支援方法を提供することにある。

上記目的は、本発明の第一の側面として、論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定するレイアウトプログラムが格納される記憶部と、前記記憶部から前記レイアウトプログラムを読み出して実行する制御部とを有する設計支援装置であって、前記記憶部には、前記複数のセルが配置される位置を特定する位置情報が格納され、前記制御部は、一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行う位置判定機能と、前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置するレイアウト機能とを前記レイアウトプログラムを実行して実現することを特徴とする設計支援装置を提供することにより達成される。

上記発明の第一の側面においてより好ましい実施例によれば、前記制御部は、更に、前記ドライバの前記出力端子と前記基準点とを結ぶ線分の傾き、及び、前記斜め配線の傾きに基づき、該斜め配線に隣接する配線の方向を縦方向又は横方向と決定し、前記斜め配線を前記決定された隣接配線方向に平行移動させて、前記斜め配線を配置可能な範囲を見つける探索を行う探索機能を、前記レイアウトプログラムを実行して実現し、前記レイアウト機能では、前記探索された範囲において選択された位置に前記斜め配線を配置すると仮定するとき、それぞれ、前記仮配置された前記斜め配線の両端のうち前記ドライバに近い端点は前記ドライバの前記出力端子と、前記基準点に近い端点は前記レシーバの前記入力端子と、縦方向及び／又は横方向の配線により接続可能かが確認される接続判定が行われ、接続可能であれば該選択された位置に前記斜め配線が配置される。

上記発明の第一の側面においてより好ましい実施例によれば、前記探索機能では、前記斜め配線の長さを予め設定された所定の初期値として前記探索が開始され、前記斜め配線を配置可能な範囲がない場合、該斜め配線の長さを前記所定の初期値より短くして再探索が行われる。上記発明の第一の側面においてより好ましい実施例によれば、前記所定の領域は、前記１つ又は複数のレシーバを囲む最小の矩形である。

上記発明の第一の側面においてより好ましい実施例によれば、前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間が、前記ネット毎に算出されており、前記位置判定機能では、前記複数のネットのうち、前記遅延時間が第２の閾値以上である前記経路を含む前記ネットが前記位置判定の対象とされる。上記発明の第一の側面においてより好ましい実施例によれば、前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差が前記ネット毎に算出されており、前記位置判定機能では、前記複数のネットのうち、前記差が第３の閾値以上である前記ネットが前記位置判定の対象とされる。

上記発明の第一の側面においてより好ましい実施例によれば、前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間と、前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差とが、それぞれ前記ネット毎に算出されており、前記位置判定機能では、前記遅延時間と前記差とに重み付き係数を掛けて算出される評価値に基づき前記ネットの順位が決定され、前記順位の高い前記ネットから順に前記位置判定が行われる。上記発明の第一の側面においてより好ましい実施例によれば、前記配線レイアウトは、互いに直交するｘ軸とｙ軸とによって形成される２次元平面にて決定され、前記斜め配線は、前記ｘ軸に対してα度（０＜α＜９０）をなす第１の斜め配線と前記ｘ軸に対してβ度（９０＜β＜１８０）をなす第２の斜め配線とを含み、前記レイアウト機能では、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が０度より大きく９０度より小さい場合には、前記第１の斜め配線が使用され、該線分が前記ｘ軸となす角が９０度より大きい場合には、前記第２の斜め配線が使用される。

また、上記目的は、第二の側面として、論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定し、かつ、前記複数のセルが配置される位置を特定する位置情報が格納されるコンピュータに、一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行う位置判定機能と、前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置するレイアウト機能とを実現させるためのプログラムを提供することにより達成される。

また、上記目的は、第三の側面として、論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定する設計支援方法であって、予め前記複数のセルが配置される位置を特定する位置情報が記憶されており、一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行い、前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置することを特徴とする設計支援方法を提供することにより達成される。

本発明によれば、ドライバがレシーバ群の外部に位置するネットにおいて、ドライバとレシーバの接続に斜め配線が配置されることになり、１つのネットで複数種類の斜め配線が用いられることなく、効率的な配線が可能になる。こうして、斜め配線を有効に活用してセル間の配線設計を行うことができる。

以下、本発明の実施の形態について図面に従って説明する。しかしながら、本発明の技術的範囲はかかる実施の形態に限定されるものではなく、特許請求の範囲に記載された発明とその均等物にまで及ぶものである。

図１は、本発明の実施形態における設計支援装置１の構成ブロック図である。設計支援装置１は、デスクトップ型PC、ノートブック型PC、PDA(Personal Digital Assistance)、サーバ、ワークステーション等の情報処理装置であって、バス１４を介して互いに接続される制御部１１、RAM(Random Access Memory)１２、記憶部１３、周辺機器接続用インタフェース(周辺機器I/F)１５、情報が入力される入力部１６、情報を出力し、利用者に情報を与えるための出力部１７を含む。

制御部１１は、図示省略されたCPU(Central Processing Unit)を含み、RAM１２に格納されるプログラムを実行し、設計支援装置１に含まれる各部を制御する。RAM１２は、設計支援装置１の処理における演算結果やプログラムが一時的に格納される記憶手段である。記憶部１３は、ハードディスク、光ディスク、磁気ディスク、フラッシュメモリ等の不揮発性記憶手段であり、各種データやRAM１２へ読み出される前のOS(Operating System)等のプログラムが格納される。

周辺機器I/F１５は、設計支援装置１に周辺機器を接続するためのインタフェースであり、パラレルポート、USB(Universal Serial Bus)ポートや、PCIカードスロット等である。周辺機器としては、プリンタ、TVチューナ、SCSI(Small Computer System Interface)機器、オーディオ機器、ドライブ装置、メモリカードリーダライタ、ネットワークインタフェースカード、無線LANカード、モデムカード、キーボードやマウス、ディスプレイ装置など多岐に渡る。周辺機器と設計支援装置１との接続形態は、有線であっても無線であっても構わない。

出力部１７は、情報を出力し、利用者に情報を与えるための出力手段であり、CRT(Cathode Ray Tube)、液晶ディスプレイ等ユーザに情報を提示する表示手段の他、音声によって指示や情報を読み上げて利用者に伝えるスピーカなどであってもよい。入力部１６は、キーボード、マウス等ユーザの要求が入力される入力手段である。また、設計支援装置１は、CD(Compact Disc)、DVD(Digital Versatile Disk)、MO(Magneto-Optical)ディスク等の記憶媒体を読み出すためのドライブ装置を持つ場合がある。ドライブ装置を使用すれば、記憶媒体に格納された情報が読み出され、設計支援装置１に入力される。つまり、ドライブ装置も、入力部１６として機能する。

図２は、設計支援の対象である半導体集積回路を説明する図である。半導体集積回路１００は、複数の機能ブロック１０１を含む。機能ブロック１０１とは、例えば、マイクロプロセッサ、MPEG(Moving Picture Experts Group)デコーダ、SRAM(Static Random Access Memory)、ROM(Read Only Memory)、入出力回路、ASIC(Application Specific Integrated Circuit)等の１０万〜１００万個程度の半導体素子が集積された回路である。

各機能ブロック１０１は、複数のセル１０２を含む。セル１０２とは、例えば、セルとは、フリップフロップ、セレクタ、マルチプレクサ、カウンタ等の１００〜１０００個程度の半導体素子が集積された回路である。セル１０２は、数個から数十個の論理ゲートを含む。図２には、セル１０２の一例として、４つの論理ゲートからなるフリップフロップ１０３が描かれる。

セル１０２は、入力端子と出力端子を持ち、他のセル１０２と駆動関係が築かれる。セルの駆動関係とは、あるセルの出力端子が別のセルの入力端子に接続されることを意味する。

図３Ａは、セルの駆動を説明する図である。図３Ａにおいて、セルCEL1の出力端子が、セルCEL2の入力端子に接続され、セルCEL1がセルCEL2を駆動する。このとき、駆動する側のセルCEL1をドライバ、駆動される側のセルCEL2をレシーバと呼ぶ。

図３Ｂは、セルの駆動関係の例を説明する図である。図３Ｂにおいて矢印で示されるように、半導体集積回路に配置されるセル１０２は、自分がどのセルを駆動するか、そして、自分がどのセルから駆動されるかが設定される。例えば、図１のセルCEL2は、セルCEL1から駆動されるが、同時に、セルCEL3とセルCEL4を駆動する。こうして、１つのドライバに対し、１つ又は複数のレシーバが対応することになる。

図３Ｃは、ドライバとレシーバの組をまとめたネットを示す図である。上述したように、１つのドライバに対応して、１つ又は複数のレシーバが存在し、その両者を１つのグループとしたものがネットである。図３Ｃには、ドライバであるセルCEL1と、それに対応するレシーバである、セルCEL2、セルCEL5、セルCEL6を含むネットN1が描かれる。

図３Ｄは、ネットの別の例を示す図である。図３Ｄには、ドライバであるセルCEL6と、それに対応するレシーバであるセルCEL8を含むネットN2が描かれる。このように別のネットにおいて、レシーバであったセルが、ドライバになることもある。また、ネットに含まれるレシーバは、１つの場合と、複数の場合とがある。

以上に説明したセル１０２の情報や駆動関係は、図３Ｂに示されるｘｙ軸によって定まる座標によって特定される位置情報によって表現され、本実施形態の設計支援の前提として記憶部１３に格納されるものとする。つまり、配線前にセル１０２の配置は完了しているものとする。

図４Ａは、記憶部１３に格納されるセル情報のデータ構成例である。図４Ａのセル情報は、「セル」「入力端子座標」「出力端子座標」というデータ項目を持つ。

「セル」は、セル１０２を識別するための識別子である。「入力端子座標」は、セル１０２がレシーバとなる場合に関係する、セル１０２の入力端子の位置を示すｘｙ座標である。「出力端子座標」は、セル１０２がドライバとなる場合に関係する、セル１０２の出力端子の位置を示すｘｙ座標である。

図４Ｂは、記憶部１３に格納される駆動関係を特定する情報のデータ構成例である。図４Ｂの駆動関係情報は、「ネット」「ドライバ」「レシーバ」というデータ項目を持つ。

「ネット」は、ネットを識別するための識別子である。「ドライバ」は、そのネットに含まれるドライバとなるセル１０２を特定する識別子である。「レシーバ」は、そのネットに含まれるレシーバとなるセル１０２を特定する識別子である。

図５Ａは、実施形態の説明において共通に用いられる斜め配線を説明する図である。斜め配線を用いると、縦方向及び／又は横方向の配線を用いるより、配線長が短くなる。

図５Ａに示されるように、ドライバＤの出力端子とレシーバＲの入力端子の位置関係に応じて使用される斜め配線が変更される。ドライバＤの出力端子の位置を原点とするとき、レシーバＲの入力端子の位置が第１象限又は第３象限にある場合には、α度（０＜α＜９０）の傾きを持つ第１の斜め配線が用いられる。ドライバＤの出力端子の位置を原点とするとき、レシーバＲの入力端子の位置が第２象限又は第４象限にある場合には、β度（９０＜β＜１８０）の傾きを持つ第２の斜め配線が用いられる。

図５Ｂは、第１の斜め配線と第２の斜め配線の関係を示す図である。以降の説明においては、第１の斜め配線を基に説明を行うが、図５Ｂに示されるように、説明に用いる角度αを、角度（１８０−β）として読み替えることにより、第２の斜め配線に適用できる場合が多い。なお、斜め配線の角度が、０度、９０度、１８０度となる場合は、従来通り、縦方向及び／又は横方向の配線（従来配線と呼ぶ）をすればよいため、除かれる。

図６Ａは、半導体集積回路１００における配線層の構造を示す図である。図６Ａに示されるように、半導体集積回路１００は、基板２００上にアルミニウム等の配線層が何重かに重なる多層構造をしている。例えば、第１層には、横方向の配線が配置され、第２層には、縦方向の配線が配置され、第３層には、横方向の配線に加え、第１の斜め配線が配置され、第４層には、縦方向の配線に加え、第２の斜め配線が配置される。

縦方向の配線層と横方向の配線層とが交互に現れる多層配線構造を取ることによって、少ない領域に複雑な配線を配置することができる。また、斜め配線が配置される層に、縦方向又は横方向の配線を共存させることで、その配線層がより効率的に使用されることになる。

図６Ｂは、半導体集積回路１００の断面図である。図６Ｂには、最下層である第１層２０１に接するPチャネル型半導体の端子２０６が、上位の配線層を用いて接続される様子が描かれる。配線層同士は、ビア(via)２０５と呼ばれる接続部材により接続される。

図６Ｃは、第１の斜め配線を用いた配線が行われる場合の配線と配線層との関係を説明する図である。第１の斜め配線は第３層２０３に配置されている。図６Ａで説明したように、第３層は、横方向の配線も配置可能であり、ビア２０５の位置との関係から、第１の斜め配線にビア２０５まで延びる横方向の配線が接続される。残りの区間は、セルの端子が接続される第１層に向かって、第３層から第２層を経て、縦方向及び横方向の配線が配置されている。ビア２０５を経由すると、層が１つ降順する。

図６Ｄは、第２の斜め配線を用いた配線が行われる場合の配線と配線層との関係を説明する図である。第２の斜め配線は第４層２０４に配置されている。図６Ａで説明したように、第４層は、縦方向の配線も配置可能であり、ビア２０５の位置との関係から、第２の斜め配線にビア２０５まで延びる縦方向の配線が接続される。残りの区間は、セルの端子が接続される第１層に向かって、第４層から第３層、第２層を経て、縦方向及び横方向の配線が配置されている。ビア２０５を経由すると、層が１つ降順する。

続いて第１の実施形態について説明する。第１の実施形態では、以上で説明した半導体集積回路の設計に際し、斜め配線を配置する位置を、ドライバとレシーバの位置関係に応じて最適化するものである。

図７は、第１の実施形態における設計支援装置１の制御部１１を説明する機能ブロック図である。制御部１１は、位置判定部１１２、探索部１１３、レイアウト部１１４を含んでいる。制御部１１の各機能部は、制御部１１に備えられる図示省略されたCPUで実行されるプログラムとして実現されるが、ハードウェアにより実現することも可能である。

位置判定部１１２は、ネット毎に、ドライバとレシーバの位置関係に基づき、そのネットにおいて斜め配線が用いられるべきかを判定する。特に、ネットに含まれるレシーバが複数あると、斜め配線を用いる意味がない場合や、かえって配線を複雑にしてしまう場合があるため、位置判定部１１２は、これらの場合を排除する。

探索部１１３は、位置判定部１１２により斜め配線を用いると判定されたネット毎に、斜め配線を配置可能な領域を探索する。探索部１１３は、斜め配線が配置される配線層において、斜め配線を所定の方向にスライドさせるとき、信号線（通常配線も含め）を配置できない障害物箇所や既に配線に使用されている使用箇所がないかを探索し、それらの箇所があれば、斜め配線を配置可能な領域から除外する。

レイアウト部１１４は、斜め配線を配置可能な領域内に、斜め配線を仮配置し、仮配置された斜め配線を用いて、ドライバとレシーバ間を接続可能かを判定する。従来技術において、２点間を従来配線により接続するための解法は提案されており、ドライバとレシーバを接続する経路のうち斜め配線以外の区間は、そうした従来技術の解法を使用することができる。レイアウト部１１４は、仮配置される斜め配線の位置を変更しても、ドライバとレシーバ間を接続可能にする斜め配線を見つけることができなければ、斜め配線を取りやめ、従来配線に切替えてドライバとレシーバ間を接続する。

図８は、第１の実施形態における設計支援装置１の動作を説明するフローチャートである。まず、位置判定部１１２が、ネット毎に、そのネットに含まれるドライバがレシーバ群の外側にあるかに基づき、そのネットに斜め配線を用いるべきかを判定する（Ｓ５１）。レシーバ群とは、そのネットに含まれるレシーバ全体を指す。ステップＳ５１の処理を位置判定と呼ぶことにする。

位置判定部１１２は、位置判定として、複数のレシーバを囲む所定の領域（矩形、円、楕円等）を求め、ドライバがその所定の領域の外部にあるかを判定する。位置判定部１１２は、記憶部１３に格納されるセル情報（図４Ａ）を参照して、ドライバの出力端子の座標、レシーバの入力端子の座標を取得し、位置判定を行う。

図９は、位置判定の例を説明する図であり、図９Ａは、所定の領域として矩形が用いられる場合、図９Ｂは、所定の領域として楕円が用いられる場合を示す。図９Ａには、ドライバＤと３つのレシーバＲを含むネットが描かれている。図９Ａ上段では、所定の領域として、３つのレシーバＲを囲む最小の矩形２１が使用され、矩形２１の内部にドライバＤが位置している。

ドライバＤが矩形の内部に位置する場合、そのネットに斜め配線を配置すべきではない。なぜなら、ドライバＤが矩形の内部に位置する場合、ドライバＤとレシーバＲとの距離が近くなることが多いからである。距離が近いセル同士に対して斜め配線を用いても、その短縮効果はあまり期待できず、斜め配線を用いる意味があまりない。

また仮に、ドライバＤとレシーバＲとの距離が斜め配線を用いる意味がある程度に離れているとしても、ドライバＤが矩形の内部に位置することにより、１つのネットに対して２つの斜め配線を用いる必要が生じる。これは、ドライバＤが矩形の内側に位置するということは、ドライバＤの上下左右にレシーバが配置される可能性が高く、図５Ａを参照すれば、象限に応じて２つの斜め配線が共に必要になる可能性が高いからである。

図９Ａ下段では、３つのレシーバＲを囲む最小の矩形２２外側にドライバＲが位置する。この場合、そのネットに斜め配線を配置すべきである。それは、図９Ａ上段のような問題は生じないためである。なお、このネットに対しては、第１の斜め配線（図５Ｂ参照）の適用が可能であり、第２の斜め配線の必要はないようである。

矩形２２は、レシーバＲの入力端子の座標のうち、最小のｘ座標をｘ１、最小のｙ座標をｙ１、最大のｘ座標をｘ２、最大のｙ座標をｙ２とすれば、（ｘ１、ｙ１）、（ｘ１、ｙ２）、（ｘ２、ｙ１）、（ｘ２、ｙ２）という４点を結ぶ図形として求めることができる。また、ドライバの出力端子の座標も分かっているため、ドライバが矩形の外部にあるかどうかも簡単に確認できる。

なお、所定の領域は、レシーバＲを囲む矩形であればよい。その場合、その矩形の面積が所定の閾値以下であるように矩形を選択しておき、不用意に所定の領域が広くなることを防止しておく。

図９Ｂ上段では、所定の領域として、３つのレシーバＲを囲む楕円２３が使用され、楕円２３の内部にドライバＤが位置している。この場合も図９Ａ上段と同様の理由で、斜め配線を配置すべきではない。

図９Ｂ下段では、３つのレシーバＲを囲む楕円２４の外側にドライバＲが位置する。この場合も図９Ａ下段と同様の理由で、そのネットに斜め配線を配置すべきである。なお、このネットに対しても、第１の斜め配線（図５Ｂ参照）の適用が可能であり、第２の斜め配線の必要はないようである。

レシーバＲを内部に含む楕円は、レシーバの入力端子の座標を基に算出することができる。
例えば、楕円の式をｆ（ｘ，ｙ）＝ｘ＾２／ａ＋ｙ＾２／ｂ−ｃとすると、レシーバＲの入力端子のｘｙ座標を代入して、ｆ（ｘ、ｙ）＜０となるようなａ、ｂ、ｃは探せば済む。ドライバＤが、その楕円の外部にあるかどうかについても、ドライバＤの出力端子のｘｙ座標を代入してｆ（ｘ、ｙ）＞０となれば外部にあると簡単に判定することができる。

このとき、楕円の面積が所定の閾値以下であるように楕円を選択しておき、不用意に所定の領域が広くなることを防止しておく。「不用意に」とは、どのように判定してもドライバＤが所定の領域内部に含まれるほどという意味である。

所定の領域としては、図９に示した矩形、楕円に限らず、レシーバＲを内部に含む任意の図形を用いてもよい。その場合も、その任意の図形の面積が所定の閾値以下であるように図形を選択しておき、不用意に所定の領域が広くなることを防止しておけばよい。

図８に戻り、ステップＳ５１の位置判定が完了すれば、レイアウト部１１４は、位置判定により、斜め配線が配置されるべきとされたネット毎に、位置判定に用いた所定の領域から任意の点を基準点に決定し、その座標を記憶部１３に格納する（Ｓ５２）。基準点は、所定の領域内にあるという条件が満たされていればよい。また、ネットに含まれるレシーバが１つであれば、そのレシーバの入力端子の位置を基準点とすればよい。

図１０は、基準点の決定方法の一部を示す図である。図１０Ａは、グラフ理論に基づき、ドライバＤとレシーバＲとを１回は通過する木を求め、ドライバＤとレシーバ群との境界にあたる位置を基準点とするものである。図１０Ａでは従って、セルCEL5の入力端子位置が基準点と決定される。

図１０Ｂは、グラフ理論に基づき木の作成の結果生じるジョイントを基準点とするものである。図１０Ｂには、スタイナー木におけるジョイント（スタイナー点）が描かれ、このジョイントが基準点として決定される。図１０Ｃは、３つあるレシーバＲを結ぶ図形の重心をレシーバ群の中心として求め、レシーバ群の中心を基準点とするものである。多角形の重心は、多角形への頂点の位置ベクトルの和を頂点数で割れば得られる。

図１０Ｄは、ドライバＤとレシーバＲとの距離が最大又は最小となるレシーバＲの入力端子の位置を基準点とするものである。上記以外の方法で基準点が選択されてもよい。図１０に描かれる基準点は、一例に過ぎない。

図８に戻り、次に、レイアウト部１１４は、斜め配線が配置されるべきとされたネット毎に、基準点とレシーバとを従来配線により接続可能かを判定する（Ｓ５３）。レイアウト部１１４は、ネットに含まれるレシーバに対してそれぞれ斜め配線を用意するのではなく、１つの斜め配線をネット内で共有して、ドライバとレシーバとを接続する。従って、ドライバと基準点とを接続する斜め配線を含む配線を幹線として、幹線の終点である基準点とレシーバが接続可能であることが要求される。

ステップＳ５３の処理は、２点間を従来配線により接続することであり、その解法は従来技術で提案されており、その従来技術の解法が使用される。接続可能と判定されると（Ｓ５３Ｙｅｓ）、レイアウト部１１４は、ステップＳ５３で接続可能と判定されたネット毎に、ドライバと基準点とを斜め配線を用いて接続する（Ｓ５４）。ステップＳ５４の斜め配線の配置処理については、図１１にて後述する。

なお、ステップＳ５１において、ドライバがレシーバ群の内部にある場合（Ｓ５１Ｎｏ）、ステップＳ５３において、基準点とレシーバとを従来配線により接続可能でない場合（Ｓ５３Ｎｏ）には、そのネットに対して斜め配線の配置が中止され、ドライバとレシーバ間をそれぞれ従来配線で接続する処理に切替えられる。

ステップＳ５４又はＳ５５が完了すると、未処理のネットが無いかが判定される（Ｓ５６）。未処理のネットがあれば（Ｓ５６Ｙｅｓ）、再びステップＳ５１から処理が行われ、未処理のネットが無ければ（Ｓ５６Ｎｏ）、処理を終了する。

図１１は、ステップＳ５４の斜め配線の配置処理を説明するフローチャートである。まず、探索部１１３が、ステップＳ５３で接続可能と判定されたネット毎に、ドライバと基準点の位置に基づき、第１の斜め配線か第２の斜め配線かどちらを使用するかを決定する（Ｓ５４１）。

これは、図５Ａにおけるレシーバを基準点と置き換えたとき、ドライバと基準点とが第１象限又は第３象限の関係にある場合、第１の斜め配線が使用され、第２象限又は第３象限の関係にある場合、第２の斜め配線が使用されることが決定される。次に、探索部１１３は、その斜め配線に隣接する配線の方向を決定する（Ｓ５４２）。

図１２は、斜め配線に隣接する配線の方向を決定する様子を説明する図である。図１２においては、ドライバＤと基準点Ｂが図５Ａに示す第１象限の関係にあるものとして説明する。太い線が、斜め配線を用いた配線である。

図１２Ａは、第１の斜め配線の傾きα度がドライバＤと基準点Ｂを結ぶ線分の傾きθ度以上で、θが４５度以下の場合である。この場合、図１２Ａに示されるように、第１の斜め配線に隣接する配線の方向は、横方向になる。

図１２Ｂは、第１の斜め配線の傾きα度がドライバＤと基準点Ｂを結ぶ線分の傾きθ度より小さく、θが４５度以下の場合である。この場合、図１２Ｂに示されるように、第１の斜め配線に隣接する配線の方向は、縦方向になる。

図１２Ｃは、第１の斜め配線の傾きα度がドライバＤと基準点Ｂを結ぶ線分の傾きθ度以上で、θが４５度以上の場合である。この場合、図１２Ｃに示されるように、第１の斜め配線に隣接する配線の方向は、横方向になる。

図１２Ｄは、第１の斜め配線の傾きα度がドライバＤと基準点Ｂを結ぶ線分の傾きθ度より小さく、θが４５度以上の場合である。この場合、図１２Ｄに示されるように、第１の斜め配線に隣接する配線の方向は、縦方向になる。

ステップＳ５４２において、探索部１１３は、ドライバＤの出力端子の座標と基準点の座標に基づきドライバＤと基準点Ｂを結ぶ線分の傾きθ度を算出する。２点の座標があれば、tanθを容易に求めることができ、線分の傾きθの算出が可能である。

図１１に戻り、ステップＳ５４２が済むと、探索部１１３は、斜め配線を配置可能な範囲をサーチする（Ｓ５４３）。探索部１１３は、ステップＳ５４２で決定された、斜め配線に隣接する配線の方向に、斜め配線をずらしながら、信号線（通常配線も含め）を配置できない障害物箇所や既に配線に使用されている使用箇所がないかを探索し、それらの箇所があれば、斜め配線を配置可能な領域から除外する。

図１３は、サーチの様子を説明する図である。図１３Ａは、横方向にサーチする場合、図１３Ｂは、縦方向にサーチする場合を示す。図１３Ａや図１３Ｂにおいては、障害物箇所や使用箇所がなく、広い範囲で斜め配線の配置が可能になっている。図１３Ｃは、横方向にずらす場合に、障害物箇所や使用箇所が存在することで、配線可能領域が狭まる場合を示す。

図１４は、障害物箇所と使用箇所の位置情報を配線層別に格納した表のデータ構成例である。図１４の表には、「層」「タイプ」「位置」というデータ項目が含まれる。「層」は、配線層を識別する識別子である。「タイプ」は、使用箇所を示す情報か、障害箇所情報かを示す。「位置」は、それぞれの箇所を特定する座標情報である。

図１１に戻り、探索部１１３は、ステップＳ５４３において、ｙ＝（ｔａｎα）ｘ＋ｂ、ｙ１≦ｙ≦ｙ２という線分を用い、図１４の表を参照して、ステップＳ５４１で決定された斜め配線が配置される配線層における障害物箇所や使用箇所に、その直線が重なるかを確認する。
ここで、ｙ１は、ドライバの出力端子のｙ座標と基準点のｙ座標のうち値が小さい方の値、ｙ２は、ドライバの出力端子のｙ座標と基準点のｙ座標のうち値が大きい方の値である。

そして、探索部１１３は、ｙ切片ｂを変化させながら、障害物箇所や使用箇所に直線が重ならないと確認されたｙ切片ｂを記憶部１３に記憶することで、斜め配線を配置可能な範囲をサーチする。ステップＳ５４３のサーチが完了すると、ステップＳ５４３において、斜め配線を配置可能な範囲が見つかったかが判定される（Ｓ５４４）。

サーチにおいて、斜め配線を配置可能な範囲が見つかっていれば、即ち、記憶部１３にｙ切片ｂの情報が格納されていれば（Ｓ５４４Ｙｅｓ）、レイアウト部１１４は、斜め配線を配置可能な範囲の斜め配線を選択する（Ｓ５４５）。ステップＳ５４５においてレイアウト部１１４は、記憶部１３に格納されたｙ切片ｂを１つ選択すればよい。

この時、ｙ切片ｂの上限値から下限値までの範囲のうち、中ほどの値から選択し、徐々に上限値から下限値に向かって選択していくとよい。例えば、ｙ切片ｂが０〜１００程度の範囲を持つ場合、ｂ＝５０として処理を開始するとよい。これは、斜め配線を配置可能な範囲の中央付近から選択していくことによって配線層の配線領域をより広く使用することを意図するものである。

次に、レイアウト部１１３は、選択された斜め配線を用いるとき、その端点をドライバと基準点に従来配線を用いて接続可能かを判定する（Ｓ５４６）。これは、斜め配線の端点のうち、ドライバ側の端点をドライバに接続可能か、基準点側の端点を基準点に接続可能かを判定するものである。ステップＳ５４６の処理は、ステップＳ５３と同じく、２点間を従来配線により接続することであり、その解法は従来技術で提案されており、その従来技術の解法が使用される。

そして、ステップＳ５４６で、接続可能と判定されると（Ｓ５４６Ｙｅｓ）、レイアウト部１１４は、ステップＳ５４５で選択された斜め配線を実際に配置し、ドライバと基準点を接続する斜め配線以外の区間については、ステップＳ５４６にて使用された従来配線を用いて接続を行い（Ｓ５４８）、斜め配線の配置処理が完了する。

ステップＳ５４６において、接続不可能と判定されると（Ｓ５４６Ｎｏ）、レイアウト部１１４は、斜め配線を配置可能な範囲に未処理の斜め配線があるかを判定する（Ｓ５４７）。レイアウト部１１４は、記憶部１３に、まだ試していないｙ切片ｂが格納されているかを確認し、格納されていれば（Ｓ５４７Ｙｅｓ）、新たな斜め配線としてステップＳ５４５に戻り処理が行われる。

サーチにおいて、斜め配線を配置可能な範囲が見つからなかった場合（Ｓ５４４Ｎｏ）とステップＳ５４３でサーチされた結果の範囲には適当な斜め配線がなかった場合（Ｓ５４７Ｎｏ）、斜め配線の配線長を短くして再度サーチが行われる（Ｓ５４９）。しかし、斜め配線の配線長を短くしすぎると、斜め配線を配置する意味が無くなるため、短くした後の配線長が所定の閾値以上である場合（Ｓ５５０Ｙｅｓ）、ステップＳ５４３に戻り再度サーチが行われる。

短くした後の配線長が所定の閾値を下回る場合（Ｓ５５０Ｎｏ）、そのネットに対して斜め配線の配置が中止され、ドライバとレシーバ間をそれぞれ従来配線で接続する処理に切替えられ（Ｓ５５１）、斜め配線の配置処理が完了する。

図１５は、斜め配線を短くして再サーチを行う場合の様子を説明する図である。図１５Ａは、斜め配線を引く余地が無い状況を示しており、図１１におけるステップＳ５４４Ｎｏの状況に対応する。図１５Ｂは、斜め配線の端点からドライバ、基準点に対する従来配線ができない状況を示しており、図１１におけるステップＳ５４７Ｎｏの状況に対応する。

図１５Ｃは、短くなった斜め配線をドライバ側に寄せて再サーチを行う状況を説明する図である。図１５Ｄは、短くなった斜め配線を基準点側（レシーバ側）に寄せて再サーチを行う状況を説明する図である。図１５Ｅは、短くなった斜め配線をドライバ側と基準点側の中間に位置した状態で再サーチを行う状況を説明する図である。このように、再サーチの方法は自由に選択してよい。最初に、図１５Ｃの方法で再サーチし、それでも再サーチの必要があれば、図１５Ｄの方法で再サーチし、最後に図１５Ｅの方法で再サーチするようにしてもよい。

以上に説明した第１の実施形態によれば、ドライバがレシーバ群の外部に位置するネットにおいて、ドライバとレシーバの接続に斜め配線が配置されることになり、１つのネットで複数種類の斜め配線が用いられることなく、効率的な配線が可能になる。これは、１つのネットで使用する斜め配線の向きを１つに決めることが寄与している。

また、レシーバ群を囲む所定領域内で定められた基準点とドライバとの配線に、そのネットに含まれるレシーバとの接続に共有して使用できる幹線となる斜め配線を配置することで、レシーバ毎に斜め配線を配置する手間を省くことができる。これは、配線処理が高速化され、また短縮化の効果を共有することで配線が効率化される。更に、サーチを行うことで配線層の中央付近から斜め配線がなされ、領域の有効活用が図れる。また、斜め配線部の最低長が決められているため、効果のない斜め配線が配置されることが防止される。

なお、第１の実施形態においては、探索部が斜め配線を配置可能な範囲を探索し、その範囲内で選択された位置に斜め配線を配置するが、基準点が決定された後、ドライバと基準点とを斜め配線を用いて接続する方法は他にも存在する。例えば、レイアウト部１１４が、ドライバ又は基準点を端点とする所定長の斜め配線を（サーチなしで）配置し、残りの区間については従来配線を行うようにしてもよい。その所定長の斜め配線を使用するとき、ドライバとレシーバとの接続ができない場合には、レイアウト部が従来配線に切り替えて処理を行ってもよいし、又は、その所定長を短くして斜め配線を再配置することもできる。このようにして、ドライバ又は基準点を端点とし、斜め配線をずらすことなく直接配置することで、第１の実施形態の設計支援装置は、斜め配線を設置可能な範囲を探索する探索部を設けない構成を取ることも可能である。

続いて、第２の実施形態について説明する。第１の実施形態においては、特に斜め配線を配置するネットの選別を行わないため、すべてのネットについて位置判定を行うと時間がかかることがある。そこで、第２の実施形態においては、まず、斜め配線を配置すべきネットを絞り込み、選別されたネットに対して位置判定を行うことによって処理を高速化するものである。

図１６は、第２の実施形態における設計支援装置１の動作を説明するフローチャートである。第１の実施形態と異なる箇所は、ステップＳ５１の前段に、位置判定を行うネットを絞り込むステップが設けられている点であり、それ以外の箇所は、第１の実施形態における動作フロー（図８）と同じであるため説明は省略する。

まず、位置判定部１１２は、斜め配線を適用するネットの絞込みを行う（Ｓ３１）。そして、ステップＳ３１が完了すると、ステップＳ３１により絞り込まれたネットに対して、位置判定部１１２が位置判定を行う（Ｓ５１）。以降の処理は、第１の実施形態（図８）と同じであり説明は省略する。

図１７は、図１６ステップＳ３１の斜め配線を適用するネットの絞込みを行う絞込み処理の例を説明するフローチャートである。絞込み処理においては、斜め配線を適用する効果やネットの規模が算出される。そして、算出された数値に基づき、斜め配線を配置する効果があると予測されるネットや規模が大きいネットに対して斜め配線が配置されるようネットを絞り込むことが行われる。

図１７Ａは、ネット毎の遅延時間に基づき、位置判定を行うネットを絞り込むものである。図１７Ａの処理を行うにあたり、記憶部１３には予めネット毎の遅延時間が格納されているものとする。

図１８は、記憶部１３に格納される遅延時間表のデータ構成例である。図１８の遅延時間表には、「ネット」「遅延時間」というデータ項目が含まれる。「ネット」は、ネットを識別するための識別子である。「遅延時間」は、ネットに含まれるドライバと各レシーバとを従来配線で接続する経路に生じる遅延時間のうち最大のものを示す。

セルの配置が完了した状態で、それらのセル間を従来配線により接続する経路に生じる遅延時間は、従来技術においてもシミュレーションツールなどを使用することにより容易に取得可能な情報である。この遅延時間表を参照すれば、ネット毎の（最大）遅延時間が取得できる。なお、図１８においては、各ネットにおける最大遅延時間のみが格納されるが、ネットに含まれる経路毎の遅延時間が、ネット毎に格納されていてもよい。

図１７Ａに戻り、まず、位置判定部１１２は、記憶部１３に格納される遅延時間表を参照し、ネット毎の（最大）遅延時間を取得する。そして、ネット毎に、取得した遅延時間が所定の閾値以上であるかを確認する（Ｓ３１１）。

遅延時間が所定の閾値を超えている場合、そのネットに斜め配線を配置することで遅延時間を減少させることができる効果が期待される。ネットにおける遅延時間の減少は、半導体集積回路全体で見ても動作速度の改善・向上につながるため、遅延時間が所定の閾値以上である場合（Ｓ３１１Ｙｅｓ）、位置判定部１１２は、そのネットを位置判定の対象として選択する（Ｓ３１２）。

逆に、遅延時間が所定の閾値を下回る場合（Ｓ３１１Ｎｏ）、そのネットは位置判定の対象として選択されず、その結果、そのネットに斜め配線が配置されることはない。ステップＳ３１２が済むと、未処理のネットがあるかが判定され（Ｓ３１３）、位置判定部１１２は、未処理のネットに対してステップＳ３１１の処理を繰り返す（Ｓ３１３Ｙｅｓ）。すべてのネットについて処理が完了すれば（Ｓ３１３Ｎｏ）、図１６ステップＳ５１に進み、ステップＳ３１２で選択されたネットに対して位置判定以下の処理が行われる。

図１７Ｂは、ネット毎の斜め配線を配置する場合の短縮長（従来配線の場合の配線長と、斜め配線を配置する場合の配線長の差）に基づき、位置判定を行うネットを絞り込むものである。まず、位置判定部１１２は、基準点を決定する（Ｓ３１４）。

この処理は、図８ステップＳ５２で説明した処理と同じである。つまり、レシーバ群を囲む所定の領域（矩形、円、楕円等）を求め、その所定領域内から任意の１点を選択すればよい。その選択方法の一例が図１０に示されるが、所定領域内であれば基準点の選択方法に特に制約はない。

そして、位置判定部１１２は、ドライバと基準点とを斜め配線を用いて接続する場合の短縮長をネット毎に算出する（Ｓ３１５）。短縮長ΔＬの算出の方法を図１２を用いて説明する。まず、図１２に登場する記号について説明しておく。

図１２において、折り返し点ＭＰは、ドライバＤと基準点Ｂとのマンハッタン距離を測るための折り返し点であり、折り返し点ＭＰ、基準点Ｂ、ドライバＤの出力端子の位置との３点で直角三角形が形成されるよう配置される。そして、折り返し点ＭＰとドライバＤの出力端子との距離をLx、折り返し点ＭＰと基準点Ｂとの距離をLyとしている。

折り返し点ＳＰは、斜め配線を用いる場合の折り返し点であり、縦方向又は横方向の配線と斜め配線との交点である。そして、折り返し点ＳＰとドライバＤの出力端子間の距離をSL、横方向の配線で接続される場合の折り返し点ＳＰと基準点Ｂとの距離をRLx、縦方向の配線で接続される場合の折り返し点ＳＰと基準点Ｂとの距離をRLyとしている。

以下、図１２Ａから順に短縮長ΔＬを算出する。図１２Ａは、第１の斜め配線の傾きα度がドライバＤと基準点Ｂを結ぶ線分の傾きθ度以上で、θが４５度以下の場合である。ドライバＤの出力端子と基準点Ｂ間のマンハッタン距離はLx+Lyで与えられる。これが、ドライバＤと基準点Ｂを従来配線する場合の配線長である。

折り返し点ＳＰは、基準点Ｂから引くｘ軸に平行な線と、ドライバＤの出力端子を端点とする第１の斜め配線との交点である。斜め配線を使用する場合の配線長がSL+RLxで与えられる。

従って、従来配線する場合の配線長Lx+Lyと斜め配線を使用する場合の配線長SL+RLxとの差が、斜め配線をすることにより短縮される配線長ΔＬとなる。短縮される配線長ΔＬを第１の斜め配線の角度αと距離Lyを用いて整理すると、以下のようになる。

次に、図１２Ｂは、第１の斜め配線の傾きα度がドライバＤと基準点Ｂを結ぶ線分の傾きθ度より小さく、θが４５度以下の場合である。この場合、従来配線を使用する場合の配線長は、図１２Ａの場合と同じだが、斜め配線を使用する場合の配線長は、SL+RLyとなる。短縮長ΔＬを第１の斜め配線の角度αと距離Lxを用いて整理すると、以下のようになる。

図１２Ｃは、第１の斜め配線の傾きα度がドライバＤと基準点Ｂを結ぶ線分の傾きθ度以上で、θが４５度以上の場合である。この場合、短縮長ΔＬは、従来配線する場合の配線長Lx+Lyと斜め配線を使用する場合の配線長SL+RLxとの差として与えられ、第１の斜め配線の角度αと距離Lyを用いて整理すると、図１２Ａの場合と同じ結果が得られる。

図１２Ｄは、第１の斜め配線の傾きα度がドライバＤと基準点Ｂを結ぶ線分の傾きθ度より小さく、θが４５度以上の場合である。この場合、短縮長ΔＬは、従来配線する場合の配線長Lx+Lyと斜め配線を使用する場合の配線長SL+RLyとの差として与えられ、第１の斜め配線の角度αと距離Lxを用いて整理すると、図１２Ｂの場合と同じ結果が得られる。

上記算出方法は、ドライバと基準点の位置関係が第１象限と第３象限にある場合に適用可能である。ドライバと基準点の位置関係が第２象限と第４象限にある場合には、角度αを角度（１８０−β）と読み替えることにより上記算出方法の適用が可能になる。

図１７Ｂに戻り、位置判定部１１２は、ネット毎に、ステップＳ３１５で算出された短縮長が所定の閾値以上であるかを確認する（Ｓ３１６）。短縮長が所定の閾値を超えている場合、そのネットに斜め配線を配置する効果が大きいことを意味する。短縮長が大きいと、そのネットにおける遅延時間を他のネットよりも減少させることができる効果が期待され、半導体集積回路全体で見ても動作速度の改善・向上につながるからである。従って、短縮長が所定の閾値以上である場合（Ｓ３１６Ｙｅｓ）、位置判定部１１２は、そのネットを位置判定の対象として選択する（Ｓ３１２）。

逆に、短縮長が所定の閾値を下回る場合（Ｓ３１６Ｎｏ）、そのネットは位置判定の対象として選択されず、その結果、そのネットに斜め配線が配置されることはない。ステップＳ３１２が済むと、未処理のネットがあるかが判定され（Ｓ３１３）、位置判定部１１２は、未処理のネットに対してステップＳ３１４の処理を繰り返す（Ｓ３１３Ｙｅｓ）。すべてのネットについて処理が完了すれば（Ｓ３１３Ｎｏ）、図１６ステップＳ５１に進み、ステップＳ３１２で選択されたネットに対して位置判定以下の処理が行われる。

図１７Ｃは、ネット毎のドライバとレシーバの最長距離に基づき、位置判定を行うネットを絞り込むものである。まず、位置判定部１１２は、ドライバとレシーバの最長距離をネット毎に算出する（Ｓ３１７）。位置判定部１１２は、記憶部１３に格納されるセル情報、駆動関係情報（共に図４）を参照し、ドライバの出力端子の座標、レシーバの入力端子の座標を取得する。そして、ドライバの出力端子とレシーバの入力端子間のユークリッド距離をそれぞれ算出し、最長距離を求める。

その最長距離が所定の閾値を超えている場合、ネットの規模が大きいことを意味し、そのネットに斜め配線を配置することで遅延時間を減少させることができる効果が期待される。ネットにおける遅延時間の減少は、半導体集積回路全体で見ても動作速度の改善・向上につながるため、最長距離が所定の閾値以上である場合（Ｓ３１８Ｙｅｓ）、位置判定部１１２は、そのネットを位置判定の対象として選択する（Ｓ３１２）。

逆に、最長距離が所定の閾値を下回る場合（Ｓ３１８Ｎｏ）、そのネットは位置判定の対象として選択されず、その結果、そのネットに斜め配線が配置されることはない。ステップＳ３１２が済むと、未処理のネットがあるかが判定され（Ｓ３１３）、位置判定部１１２は、未処理のネットに対してステップＳ３１７の処理を繰り返す（Ｓ３１３Ｙｅｓ）。すべてのネットについて処理が完了すれば（Ｓ３１３Ｎｏ）、図１６ステップＳ５１に進み、ステップＳ３１２で選択されたネットに対して位置判定以下の処理が行われる。

図１９は、斜め配線を適用するネットの絞込みを行う絞込み処理の別の例を説明するフローチャートである。図１９Ａは、ネット毎にすべてのレシーバを接続する木を求め、その木の規模に基づき、位置判定を行うネットを絞り込むものである。

まず、位置判定部１１２は、レシーバ群のレシーバを接続する木をグラフ理論に基づき探索し、木の全長を計測する（Ｓ３１９）。レシーバを接続する木の探索法には、任意の解法を適用してよい。

木の全長が所定の閾値を超えている場合、ネットの規模が大きいことを意味し、そのネットに斜め配線を配置することで遅延時間を減少させることができる効果が期待される。ネットにおける遅延時間の減少は、半導体集積回路全体で見ても動作速度の改善・向上につながるため、木の全長が所定の閾値以上である場合（Ｓ３２０Ｙｅｓ）、位置判定部１１２は、そのネットを位置判定の対象として選択する（Ｓ３１２）。

逆に、木の全長が所定の閾値を下回る場合（Ｓ３２０Ｎｏ）、そのネットは位置判定の対象として選択されず、その結果、そのネットに斜め配線が配置されることはない。ステップＳ３１２が済むと、未処理のネットがあるかが判定され（Ｓ３１３）、位置判定部１１２は、未処理のネットに対してステップＳ３１９の処理を繰り返す（Ｓ３１３Ｙｅｓ）。すべてのネットについて処理が完了すれば（Ｓ３１３Ｎｏ）、図１６ステップＳ５１に進み、ステップＳ３１２で選択されたネットに対して位置判定以下の処理が行われる。

図１９Ｂは、ネット毎にすべてのレシーバを囲む所定領域を求め、その所定領域の面積に基づき、位置判定を行うネットを絞り込むものである。

まず、位置判定部１１２は、レシーバ群を囲む所定領域を求める（Ｓ３２１）。この処理は、位置判定（図８ステップＳ５１）で行われる処理と同じである。つまり、図９に一例が示されるが例えば、レシーバ群を囲む最小の矩形を求めればよい。

所定領域の面積が所定の閾値を超えている場合、レシーバ群が広がりを持っており、ネットの規模が大きいことが予想される。そのネットに斜め配線を配置すれば、遅延時間を減少させる効果が期待される。ネットにおける遅延時間の減少は、半導体集積回路全体で見ても動作速度の改善・向上につながるため、所定領域の面積が所定の閾値以上である場合（Ｓ３２２Ｙｅｓ）、位置判定部１１２は、そのネットを位置判定の対象として選択する（Ｓ３１２）。

逆に、所定領域の面積が所定の閾値を下回る場合（Ｓ３２２Ｎｏ）、そのネットは位置判定の対象として選択されず、その結果、そのネットに斜め配線が配置されることはない。ステップＳ３１２が済むと、未処理のネットがあるかが判定され（Ｓ３１３）、位置判定部１１２は、未処理のネットに対してステップＳ３２１の処理を繰り返す（Ｓ３１３Ｙｅｓ）。すべてのネットについて処理が完了すれば（Ｓ３１３Ｎｏ）、図１６ステップＳ５１に進み、ステップＳ３１２で選択されたネットに対して位置判定以下の処理が行われる。

なお、図１７、図１９において説明した絞込み処理を組み合わせてネットを絞り込むことも可能である。例えば、遅延時間が所定の閾値以上で、短縮長も所定の閾値以上であるネットを位置判定の対象としてもよい。

また、図１７Ｂの絞込み処理を行う場合、ステップＳ３１４で基準点が決定されるため、重複する図１６ステップＳ５２は省略される。

図１７、図１９においては、斜め配線を適用する効果やネットの規模を数値化し、その数値が所定の閾値以上であるネットを選別しているが、数値の大小に応じて順位を付け、その順位に沿って位置判定を行ってもよい。例えば、遅延時間の大きいネットからソートした結果を順位表として格納しておく場合などである。

また、例えば、遅延時間と短縮長に重み付き係数を掛けた評価値を求め、評価値の高い順に位置判定を行うようにしてもよい。例えば、評価値＝係数１×遅延時間＋係数２×短縮長として、評価値を求めることができる。すると、重み付き係数（係数１、係数２）を変えることで、タイミング優先で斜め配線を行うか、配線長短縮による配線混雑度緩和を優先して斜め配線を行うかの戦略を評価値に反映させることができる。

図２０は、順位を示す表のデータ構成例である。図２０の順位表には、「順位」「ネット」というデータ項目が含まれる。「順位」は、順番を示し、「ネット」はネットを識別するための識別子である。例えば図２０の順位表を位置判定部１１２が参照すると、最初にネットN3に対して位置判定を行い、次に、ネットN1に対して位置判定を行う。以上の処理が、図１６ステップＳ３１の絞込み処理として行われてもよい。

以上に説明した第２の実施形態によれば、第１の実施形態の効果に加えて、遅延時間や回路規模を示す数値等に基づき、斜め配線の配置が必要なネットに斜め配線が配置されるように配線が最適化される。また、斜め配線の配置による効果を数値化して、より効果の期待できるネットに斜め配線が配置されるように配線が最適化される。更に、順位付けを行い、順位に基づき優先的に斜め配線が配置されるように配線を最適化することもできる。

次に、第３の実施形態について説明する。第１、第２の実施形態においては、第１の斜め配線の角度α、第２の斜め配線の角度βとして、予め定められた角度が用いられるが、第３の実施形態においては、斜め配線を配置すると仮定して短縮長が最も大きくなる角度を選択することによって、斜め配線の角度を最適化するものである。

図２１は、第３の実施形態における設計支援装置１の制御部１１を説明する機能ブロック図である。第１の実施形態と異なる箇所は、斜め配線の最適な傾きを決定する傾き決定部１１１を備える点であり、それ以外の箇所は、第１の実施形態における制御部１１の機能ブロック図（図７）と同じであるため説明は省略する。

図２２は、第３の実施形態における設計支援装置１の動作を説明するフローチャートである。
第２の実施形態と異なる箇所は、ステップＳ３１の前段に、斜め配線の傾きを決定するステップが設けられている点であり、それ以外の箇所は、第２の実施形態における動作フロー（図１６）と同じであるため説明は省略する。

まず、傾き決定部１１１は、斜め配線の最適な傾きを決定する（Ｓ１１）。そして、ステップＳ１１が完了すると、ステップＳ１１で決定された傾きを持つ斜め配線を用いて、位置判定部１１２が、絞込み処理を行い（Ｓ３１）、絞り込まれたネットに対して位置判定を行う（Ｓ５１）。以降の処理は、第２の実施形態（図１６）と同じであり説明は省略する。

図２３は、図２２ステップＳ１１の斜め配線の最適な傾きを決定する傾き決定処理の例を説明するフローチャートである。ここでは、図５に示す第１の斜め配線と第２の斜め配線の傾きα度（０＜α＜９０）、β度（９０＜β＜１８０）を最適化するものとする。

まず、傾き決定部１１１は、第１の斜め配線の傾き（第１角度）と第２の斜め配線の傾き（第２角度）の初期値を設定する（Ｓ１１１）。例えば、第１角度の初期値を１度、第２角度の初期値を９１度として、以後１度ずつ変化させていくことにする。始めに第１角度を最適化する。

そこで、傾き決定部１１１は、ネット毎に、ドライバとの位置関係が第１象限又は第３象限に属するレシーバを抽出する（Ｓ１１２）。傾き決定部１１１は、各ネットに含まれるドライバとレシーバの座標を、記憶部１３に格納されるセル情報、駆動関係情報（図４）を参照することにより取得する。

そして、図５Ａに示すようにドライバが原点となるように座標を平行移動し、レシーバのｘｙ座標を見ることでそのレシーバが属する象限を決定する。ｘｙ座標が共に正なら、そのレシーバは第１象限に属する。同様に、ｘ座標が負、ｙ座標が正なら第２象限、ｘｙ座標が共に負なら第３象限、ｘ座標が正、ｙ座標が負なら第４象限に属する。

こうして、第１象限又は第３象限に属するレシーバを抽出すると、傾き決定部１１１は、抽出されたレシーバとドライバとを斜め配線で接続するときの短縮長の合計をネット毎に算出する（Ｓ１１３）。ステップＳ１１３における短縮長の算出法は、図１７Ｂの絞込み処理におけるステップＳ３１５で説明した通りである。ただし、絞り込み処理においては、レシーバ群を代表する基準点とドライバとの短縮長を算出したが、ここでは、各レシーバとドライバに対して短縮長を求める点が異なる。

傾き決定部１１１は、未処理のネットがあるかを判定し、あれば（Ｓ１１４Ｙｅｓ）、ステップＳ１１２に戻り処理を続ける。すべてのネットに対して、ステップＳ１１１で設定された初期値の斜め配線を用いた場合の短縮長が算出できたら（Ｓ１１４Ｎｏ）、ネット全体の短縮長の合計値を算出し、第１角度（ここでは、ステップＳ１１１で設定された初期値）に対応付けて記憶部１３に格納する（Ｓ１１５）。

そして、傾き決定部１１１は、第１角度に所定値を追加する（Ｓ１１６）。例えば、１度追加する。所定値を追加した後の第１角度が９０度未満であれば（Ｓ１１７Ｎｏ）、傾き決定部１１１は、ステップＳ１１２からの処理を新たな第１角度を用いて続行する。

第１角度が９０度以上になれば（Ｓ１１７Ｙｅｓ）、傾き決定部１１１は、記憶部１３を参照して、変化させた角度毎に対応付けられる短縮長が最大となる角度を第１角度として決定する（Ｓ１１８）。こうして第１角度が最適化される。同様にして第２角度を最適化する。

傾き決定部１１１は、ネット毎に、ドライバとの位置関係が第２象限又は第４象限に属するレシーバを抽出する（Ｓ１１９）。この処理は、ステップＳ１１２と同様に処理される。第２象限又は第４象限に属するレシーバを抽出すると、傾き決定部１１１は、抽出されたレシーバとドライバとを斜め配線で接続するときの短縮長の合計をネット毎に算出する（Ｓ１２０）。ステップＳ１２０の処理は、ステップＳ１１３と同じである。

傾き決定部１１１は、未処理のネットがあるかを判定し、あれば（Ｓ１２１Ｙｅｓ）、ステップＳ１１９に戻り処理を続ける。すべてのネットに対して、ステップＳ１１１で設定された初期値の斜め配線を用いた場合の短縮長が算出できたら（Ｓ１２１Ｎｏ）、ネット全体の短縮長の合計値を算出し、第２角度（ここでは、ステップＳ１１１で設定された初期値）に対応付けて記憶部１３に格納する（Ｓ１２２）。

そして、傾き決定部１１１は、第２角度に所定値を追加する（Ｓ１２３）。例えば、１度追加する。所定値を追加した後の第２角度が１８０度未満であれば（Ｓ１２４Ｎｏ）、傾き決定部１１１は、ステップＳ１１９からの処理を新たな第２角度を用いて続行する。

第２角度が１８０度以上になれば（Ｓ１２４Ｙｅｓ）、傾き決定部１１１は、記憶部１３を参照して、変化させた角度毎に対応付けられる短縮長が最大となる角度を第２角度として決定する（Ｓ１２５）。こうして第２角度も最適化される。

以上に説明した第３の実施形態によれば、斜め配線の傾きをセルの配置に応じて最適化した上で、第１の実施形態、第２の実施形態の動作を設計支援装置１にさせることができ、より斜め配線使用時の効果を高めることができる。

なお、第１から第３の実施形態においては、傾きの異なる２種類の斜め配線を用いる場合について説明したが、１種類のみの斜め配線を用いる場合にも適用が可能である。

図２４は、第１の斜め配線のみを用いる場合の配線を示す図である。図２４に示されるように、α度（０＜α＜９０）の斜め配線のみを用いる場合には、ドライバと基準点との位置関係が第１象限又は第３象限にある場合に斜め配線が使用され、それ以外の場合には、縦方向及び／又は横方向の配線による従来配線を行えばよい。

以上まとめると付記のようになる。

（付記１）
論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定するレイアウトプログラムが格納される記憶部と、前記記憶部から前記レイアウトプログラムを読み出して実行する制御部とを有する設計支援装置であって、
前記記憶部には、前記複数のセルが配置される位置を特定する位置情報が格納され、
前記制御部は、
一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行う位置判定機能と、
前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置するレイアウト機能とを前記レイアウトプログラムを実行して実現することを特徴とする設計支援装置。

（付記２）
付記１において、
前記制御部は、更に、前記ドライバの前記出力端子と前記基準点とを結ぶ線分の傾き、及び、前記斜め配線の傾きに基づき、該斜め配線に隣接する配線の方向を縦方向又は横方向と決定し、前記斜め配線を前記決定された隣接配線方向に平行移動させて、前記斜め配線を配置可能な範囲を見つける探索を行う探索機能を、前記レイアウトプログラムを実行して実現し、
前記レイアウト機能では、前記探索された範囲において選択された位置に前記斜め配線を配置すると仮定するとき、それぞれ、前記仮配置された前記斜め配線の両端のうち前記ドライバに近い端点は前記ドライバの前記出力端子と、前記基準点に近い端点は前記基準点と、縦方向及び／又は横方向の配線により接続可能かが確認される接続判定が行われ、接続可能であれば該選択された位置に前記斜め配線が配置されることを特徴とする設計支援装置。

（付記３）
付記２において、
前記探索機能では、前記斜め配線の長さを予め設定された所定の初期値として前記探索が開始され、前記斜め配線を配置可能な範囲がない場合、該斜め配線の長さを前記所定の初期値より短くして再探索が行われることを特徴とする設計支援装置。

（付記４）
付記３において、
前記探索機能では、前記斜め配線の長さが第１の閾値以下となる場合、前記探索が中止されることを特徴とする設計支援装置。

（付記５）
付記１又は２において、
前記所定の領域は、前記１つ又は複数のレシーバを囲む最小の矩形であることを特徴とする設計支援装置。

（付記６）
付記１又は２において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間が、前記ネット毎に算出されており、
前記位置判定機能では、前記複数のネットのうち、前記遅延時間が第２の閾値以上である前記経路を含む前記ネットが前記位置判定の対象とされることを特徴とする設計支援装置。

（付記７）
付記１又は２において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間が、前記ネット毎に算出されており、
前記位置判定機能では、前記遅延時間が長い前記ネットから順に前記位置判定が行われることを特徴とする設計支援装置。

（付記８）
付記１又は２において、
前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差が前記ネット毎に算出されており、
前記位置判定機能では、前記複数のネットのうち、前記差が第３の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援装置。（６）
（付記９）
付記１又は２において、
前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差が前記ネット毎に算出されており、
前記位置判定機能では、前記差が大きい前記ネットから順に前記位置判定が行われることを特徴とする設計支援装置。

（付記１０）
付記１又は２において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間と、前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差とが、それぞれ前記ネット毎に算出されており、
前記位置判定機能では、前記遅延時間と前記差とに重み付き係数を掛けて算出される評価値に基づき前記ネットの順位が決定され、前記順位の高い前記ネットから順に前記位置判定が行われることを特徴とする設計支援装置。

（付記１１）
付記１又は２において、
前記位置判定機能では、前記ネットに含まれる前記ドライバから前記レシーバまでの最長距離が前記ネット毎に算出され、前記複数のネットのうち、前記最長距離が第４の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援装置。

（付記１２）
付記１又は２において、
前記位置判定機能では、前記ネットに含まれる前記１つ又は複数のレシーバを接続する木が探索され、前記木の全長が前記ネット毎に算出され、前記全長が第５の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援装置。

（付記１３）
付記１又は２において、
前記位置判定機能では、前記ネット毎に前記所定の領域の面積が算出され、前記面積が第６の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援装置。

（付記１４）
付記１又は２において、
前記配線レイアウトは、互いに直交するｘ軸とｙ軸とによって形成される２次元平面にて決定され、
前記斜め配線は、前記ｘ軸に対してα度（０＜α＜９０）をなす第１の斜め配線と前記ｘ軸に対してβ度（９０＜β＜１８０）をなす第２の斜め配線とを含み、
前記レイアウト機能では、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が０度より大きく９０度より小さい場合には、前記第１の斜め配線が使用され、該線分が前記ｘ軸となす角が９０度より大きい場合には、前記第２の斜め配線が使用されることを特徴とする設計支援装置。

（付記１５）
付記１又は２において、
前記第１の斜め配線の傾きは、前記第１の斜め配線の傾きを変化させて第１の合計値を算出するとき、前記第１の合計値を最大にする傾きであり、
前記第２の斜め配線の傾きは、前記第２の斜め配線の傾きを変化させて第２の合計値を算出するとき、前記第２の合計値を最大にする傾きであって、
前記第１の合計値は、前記第１の斜め配線の傾きを固定するとき、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が０度より大きく９０度より小さいという第１の条件を満たす前記基準点に対して、前記ドライバの前記出力端子と前記第１の条件を満たす基準点とのマンハッタン距離と、前記ドライバから前記条件を満たす基準点までを該傾きの固定された第１の斜め配線を用いた配線で接続する場合の配線長との差の前記複数のネットでの合計値として算出され、
前記第２の合計値は、前記第２の斜め配線の傾きを固定するとき、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が９０度より大きいという第２の条件を満たす前記基準点に対して、前記ドライバの前記出力端子と前記第２の条件を満たす基準点とのマンハッタン距離と、前記ドライバから前記第２の条件を満たす基準点までを該傾きの固定された第２の斜め配線を用いた配線で接続する場合の配線長との差の前記複数のネットでの合計値として算出されることを特徴とする設計支援装置。

（付記１６）
論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定する配線設計支援装置であって、
前記複数のセルが配置される位置を特定する位置情報が格納される記憶部と、
一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行う位置判定部と、
前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置するレイアウト部とを有することを特徴とする設計支援装置。

（付記１７）
付記１６において、更に、
前記ドライバの前記出力端子と前記基準点とを結ぶ線分の傾き、及び、前記斜め配線の傾きに基づき、該斜め配線に隣接する配線の方向を縦方向又は横方向と決定し、前記斜め配線を前記決定された隣接配線方向に平行移動させて、前記斜め配線を配置可能な範囲を見つける探索を行う探索部を有し、
前記レイアウト部は、前記探索された範囲において選択された位置に前記斜め配線を配置すると仮定するとき、それぞれ、前記仮配置された前記斜め配線の両端のうち前記ドライバに近い端点は前記ドライバの前記出力端子と、前記基準点に近い端点は前記基準点と、縦方向及び／又は横方向の配線により接続可能かを確認する接続判定が行われ、接続可能であれば該選択された位置に前記斜め配線を配置することを特徴とする設計支援装置。

（付記１８）
論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定し、かつ、前記複数のセルが配置される位置を特定する位置情報が格納されるコンピュータに、
一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行う位置判定機能と、
前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置するレイアウト機能とを実現させるためのプログラム。

（付記１９）
付記１８において、
更に、前記ドライバの前記出力端子と前記基準点とを結ぶ線分の傾き、及び、前記斜め配線の傾きに基づき、該斜め配線に隣接する配線の方向を縦方向又は横方向と決定し、前記斜め配線を前記決定された隣接配線方向に平行移動させて、前記斜め配線を配置可能な範囲を見つける探索を行う探索機能を実現させ、
前記レイアウト機能では、前記探索された範囲において選択された位置に前記斜め配線を配置すると仮定するとき、それぞれ、前記仮配置された前記斜め配線の両端のうち前記ドライバに近い端点は前記ドライバの前記出力端子と、前記基準点に近い端点は前記基準点と、縦方向及び／又は横方向の配線により接続可能かが確認される接続判定が行われ、接続可能であれば該選択された位置に前記斜め配線が配置されることを特徴とするプログラム。

（付記２０）
付記１９において、
前記探索機能では、前記斜め配線の長さを予め設定された所定の初期値として前記探索が開始され、前記斜め配線を配置可能な範囲がない場合、該斜め配線の長さを前記所定の初期値より短くして再探索が行われることを特徴とするプログラム。

（付記２１）
付記２０において、
前記探索機能では、前記斜め配線の長さが第１の閾値以下となる場合、前記探索が中止されることを特徴とするプログラム。

（付記２２）
付記１８又は１９において、
前記所定の領域は、前記１つ又は複数のレシーバを囲む最小の矩形であることを特徴とするプログラム。

（付記２３）
付記１８又は１９において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間が、前記ネット毎に算出されており、
前記位置判定機能では、前記複数のネットのうち、前記遅延時間が第２の閾値以上である前記経路を含む前記ネットが前記位置判定の対象とされることを特徴とするプログラム。

（付記２４）
付記１８又は１９において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間が、前記ネット毎に算出されており、
前記位置判定機能では、前記遅延時間が長い前記ネットから順に前記位置判定が行われることを特徴とするプログラム。

（付記２５）
付記１８又は１９において、
前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差が前記ネット毎に算出されており、
前記位置判定機能では、前記複数のネットのうち、前記差が第３の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とするプログラム。

（付記２６）
付記１８又は１９において、
前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差が前記ネット毎に算出されており、
前記位置判定機能では、前記差が大きい前記ネットから順に前記位置判定が行われることを特徴とするプログラム。

（付記２７）
付記１８又は１９において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間と、前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差とが、それぞれ前記ネット毎に算出されており、
前記位置判定機能では、前記遅延時間と前記差とに重み付き係数を掛けて算出される評価値に基づき前記ネットの順位が決定され、前記順位の高い前記ネットから順に前記位置判定が行われることを特徴とするプログラム。

（付記２８）
付記１８又は１９において、
前記位置判定機能では、前記ネットに含まれる前記ドライバから前記レシーバまでの最長距離が前記ネット毎に算出され、前記複数のネットのうち、前記最長距離が第４の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とするプログラム。

（付記２９）
付記１８又は１９において、
前記位置判定機能では、前記ネットに含まれる前記１つ又は複数のレシーバを接続する木が探索され、前記木の全長が前記ネット毎に算出され、前記全長が第５の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とするプログラム。

（付記３０）
付記１８又は１９において、
前記位置判定機能では、前記ネット毎に前記所定の領域の面積が算出され、前記面積が第６の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とするプログラム。

（付記３１）
付記１８又は１９において、
前記配線レイアウトは、互いに直交するｘ軸とｙ軸とによって形成される２次元平面にて決定され、
前記斜め配線は、前記ｘ軸に対してα度（０＜α＜９０）をなす第１の斜め配線と前記ｘ軸に対してβ度（９０＜β＜１８０）をなす第２の斜め配線とを含み、
前記レイアウト機能では、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が０度より大きく９０度より小さい場合には、前記第１の斜め配線が使用され、該線分が前記ｘ軸となす角が９０度より大きい場合には、前記第２の斜め配線が使用されることを特徴とするプログラム。

（付記３２）
付記１８又は１９において、
前記第１の斜め配線の傾きは、前記第１の斜め配線の傾きを変化させて第１の合計値を算出するとき、前記第１の合計値を最大にする傾きであり、
前記第２の斜め配線の傾きは、前記第２の斜め配線の傾きを変化させて第２の合計値を算出するとき、前記第２の合計値を最大にする傾きであって、
前記第１の合計値は、前記第１の斜め配線の傾きを固定するとき、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が０度より大きく９０度より小さいという第１の条件を満たす前記基準点に対して、前記ドライバの前記出力端子と前記第１の条件を満たす基準点とのマンハッタン距離と、前記ドライバから前記条件を満たす基準点までを該傾きの固定された第１の斜め配線を用いた配線で接続する場合の配線長との差の前記複数のネットでの合計値として算出され、
前記第２の合計値は、前記第２の斜め配線の傾きを固定するとき、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が９０度より大きいという第２の条件を満たす前記基準点に対して、前記ドライバの前記出力端子と前記第２の条件を満たす基準点とのマンハッタン距離と、前記ドライバから前記第２の条件を満たす基準点までを該傾きの固定された第２の斜め配線を用いた配線で接続する場合の配線長との差の前記複数のネットでの合計値として算出されることを特徴とするプログラム。

（付記３３）
論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定する設計支援方法であって、
予め前記複数のセルが配置される位置を特定する位置情報が記憶されており、
一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、
前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行い、
前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、
前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置することを特徴とする設計支援方法。

（付記３４）
付記３３において、更に、
前記ドライバの前記出力端子と前記基準点とを結ぶ線分の傾き、及び、前記斜め配線の傾きに基づき、該斜め配線に隣接する配線の方向を縦方向又は横方向と決定し、
前記斜め配線を前記決定された隣接配線方向に平行移動させて、前記斜め配線を配置可能な範囲を見つける探索を行い、
前記探索された範囲において選択された位置に前記斜め配線を配置すると仮定するとき、それぞれ、前記仮配置された前記斜め配線の両端のうち前記ドライバに近い端点は前記ドライバの前記出力端子と、前記基準点に近い端点は前記基準点と、縦方向及び／又は横方向の配線により接続可能かを確認する接続判定を行い、
接続可能であれば該選択された位置に前記斜め配線を配置することを特徴とする設計支援方法。

（付記３５）
付記３４において、
前記斜め配線の長さを予め設定された所定の初期値として前記探索が開始され、前記斜め配線を配置可能な範囲がない場合、該斜め配線の長さを前記所定の初期値より短くして再探索が行われることを特徴とする設計支援方法。

（付記３６）
付記３５において、
前記斜め配線の長さが第１の閾値以下となる場合、前記探索が中止されることを特徴とする設計支援方法。

（付記３７）
付記３３又は３４において、
前記所定の領域は、前記１つ又は複数のレシーバを囲む最小の矩形であることを特徴とする設計支援方法。

（付記３８）
付記３３又は３４において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間が、前記ネット毎に算出されており、
前記複数のネットのうち、前記遅延時間が第２の閾値以上である前記経路を含む前記ネットが前記位置判定の対象とされることを特徴とする設計支援方法。

（付記３９）
付記３３又は３４において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間が、前記ネット毎に算出されており、
前記遅延時間が長い前記ネットから順に前記位置判定が行われることを特徴とするレイアウ方法。ト
（付記４０）
付記３３又は３４において、
前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差が前記ネット毎に算出されており、
前記複数のネットのうち、前記差が第３の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援方法。

（付記４１）
付記３３又は３４において、
前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差が前記ネット毎に算出されており、
前記差が大きい前記ネットから順に前記位置判定が行われることを特徴とする設計支援方法。

（付記４２）
付記３３又は３４において、
前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間と、前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差とが、それぞれ前記ネット毎に算出されており、
前記遅延時間と前記差とに重み付き係数を掛けて算出される評価値に基づき前記ネットの順位が決定され、前記順位の高い前記ネットから順に前記位置判定が行われることを特徴とする設計支援方法。

（付記４３）
付記３３又は３４において、
前記ネットに含まれる前記ドライバから前記レシーバまでの最長距離が前記ネット毎に算出され、前記複数のネットのうち、前記最長距離が第４の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援方法。

（付記４４）
付記３３又は３４において、
前記ネットに含まれる前記１つ又は複数のレシーバを接続する木が探索され、前記木の全長が前記ネット毎に算出され、前記全長が第５の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援方法。

（付記４５）
付記３３又は３４において、
前記ネット毎に前記所定の領域の面積が算出され、前記面積が第６の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援方法。

（付記４６）
付記３３又は３４において、
前記配線レイアウトは、互いに直交するｘ軸とｙ軸とによって形成される２次元平面にて決定され、
前記斜め配線は、前記ｘ軸に対してα度（０＜α＜９０）をなす第１の斜め配線と前記ｘ軸に対してβ度（９０＜β＜１８０）をなす第２の斜め配線とを含み、
前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が０度より大きく９０度より小さい場合には、前記第１の斜め配線が使用され、該線分が前記ｘ軸となす角が９０度より大きい場合には、前記第２の斜め配線が使用されることを特徴とする設計支援方法。

（付記４７）
付記３３又は３４において、
前記第１の斜め配線の傾きは、前記第１の斜め配線の傾きを変化させて第１の合計値を算出するとき、前記第１の合計値を最大にする傾きであり、
前記第２の斜め配線の傾きは、前記第２の斜め配線の傾きを変化させて第２の合計値を算出するとき、前記第２の合計値を最大にする傾きであって、
前記第１の合計値は、前記第１の斜め配線の傾きを固定するとき、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が０度より大きく９０度より小さいという第１の条件を満たす前記基準点に対して、前記ドライバの前記出力端子と前記第１の条件を満たす基準点とのマンハッタン距離と、前記ドライバから前記条件を満たす基準点までを該傾きの固定された第１の斜め配線を用いた配線で接続する場合の配線長との差の前記複数のネットでの合計値として算出され、
前記第２の合計値は、前記第２の斜め配線の傾きを固定するとき、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が９０度より大きいという第２の条件を満たす前記基準点に対して、前記ドライバの前記出力端子と前記第２の条件を満たす基準点とのマンハッタン距離と、前記ドライバから前記第２の条件を満たす基準点までを該傾きの固定された第２の斜め配線を用いた配線で接続する場合の配線長との差の前記複数のネットでの合計値として算出されることを特徴とする設計支援方法。

本発明の実施形態における設計支援装置１の構成ブロック図である。 設計支援の対象である半導体集積回路を説明する図である Ａは、セルの駆動を説明する図であり、Ｂは、セルの駆動関係の例を説明する図であり、Ｃは、ドライバとレシーバの組をまとめたネットを示す図であり、Ｄは、ネットの別の例を示す図である。 Ａは、記憶部に格納されるセル情報のデータ構成例であり、Ｂは、記憶部１３に格納される駆動関係を特定する情報のデータ構成例である。 Ａは、実施形態の説明において共通に用いられる斜め配線を説明する図であり、Ｂは、第１の斜め配線と第２の斜め配線の関係を示す図である。 Ａは、半導体集積回路１００における配線層の構造を示す図であり、Ｂは、半導体集積回路の断面図であり、Ｃは、第１の斜め配線を用いた配線が行われる場合の配線と配線層との関係を説明する図であり、Ｄは、第２の斜め配線を用いた配線が行われる場合の配線と配線層との関係を説明する図である。 第１の実施形態における設計支援装置の制御部を説明する機能ブロック図である。 第１の実施形態における設計支援装置の動作を説明するフローチャートである。 位置判定の例を説明する図であり、Ａは、所定の領域として矩形が用いられる場合、Ｂは、所定の領域として楕円が用いられる場合を示す。 基準点の決定方法の一部を示す図である。 斜め配線の配置処理を説明するフローチャートである。 斜め配線に隣接する配線の方向を決定する様子を説明する図である。 サーチの様子を説明する図である。 障害物箇所と使用箇所の位置情報を配線層別に格納した表のデータ構成例である。 斜め配線を短くして再サーチを行う場合の様子を説明する図である。 第２の実施形態における設計支援装置の動作を説明するフローチャートである。 斜め配線を適用するネットの絞込みを行う絞込み処理の例を説明するフローチャートである。 遅延時間表のデータ構成例である。 斜め配線を適用するネットの絞込みを行う絞込み処理の別の例を説明するフローチャートである。 順位を示す表のデータ構成例である。 第３の実施形態における設計支援装置の制御部を説明する機能ブロック図である。 第３の実施形態における設計支援装置の動作を説明するフローチャートである。 斜め配線の最適な傾きを決定する傾き決定処理の例を説明するフローチャートである。 第１の斜め配線のみを用いる場合の配線を示す図である。

符号の説明

１ 設計支援装置、１１ 制御部、１２ RAM、１３ 記憶部、１４ バス、１５ 周辺機器インタフェース、１６ 入力部、１７ 出力部、１１１ 傾き決定部、１１２ 位置判定部、１１３ 探索部、１１４ レイアウト部

Claims (10)

1. 論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定するレイアウトプログラムが格納される記憶部と、前記記憶部から前記レイアウトプログラムを読み出して実行する制御部とを有する設計支援装置であって、
   前記記憶部には、前記複数のセルが配置される位置を特定する位置情報が格納され、
   前記制御部は、
   一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行う位置判定機能と、
   前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置するレイアウト機能とを前記レイアウトプログラムを実行して実現することを特徴とする設計支援装置。
2. 請求項１において、
   前記制御部は、更に、前記ドライバの前記出力端子と前記基準点とを結ぶ線分の傾き、及び、前記斜め配線の傾きに基づき、該斜め配線に隣接する配線の方向を縦方向又は横方向と決定し、前記斜め配線を前記決定された隣接配線方向に平行移動させて、前記斜め配線を配置可能な範囲を見つける探索を行う探索機能を、前記レイアウトプログラムを実行して実現し、
   前記レイアウト機能では、前記探索された範囲において選択された位置に前記斜め配線を配置すると仮定するとき、それぞれ、前記仮配置された前記斜め配線の両端のうち前記ドライバに近い端点は前記ドライバの前記出力端子と、前記基準点に近い端点は前記基準点と、縦方向及び／又は横方向の配線により接続可能かが確認される接続判定が行われ、接続可能であれば該選択された位置に前記斜め配線が配置されることを特徴とする設計支援装置。
3. 請求項２において、
   前記探索機能では、前記斜め配線の長さを予め設定された所定の初期値として前記探索が開始され、前記斜め配線を配置可能な範囲がない場合、該斜め配線の長さを前記所定の初期値より短くして再探索が行われることを特徴とする設計支援装置。
4. 請求項１又は２において、
   前記所定の領域は、前記１つ又は複数のレシーバを囲む最小の矩形であることを特徴とする設計支援装置。
5. 請求項１又は２において、
   前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間が、前記ネット毎に算出されており、
   前記位置判定機能では、前記複数のネットのうち、前記遅延時間が第２の閾値以上である前記経路を含む前記ネットが前記位置判定の対象とされることを特徴とする設計支援装置。
6. 請求項１又は２において、
   前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差が前記ネット毎に算出されており、
   前記位置判定機能では、前記複数のネットのうち、前記差が第３の閾値以上である前記ネットが前記位置判定の対象とされることを特徴とする設計支援装置。
7. 請求項１又は２において、
   前記ドライバから前記レシーバまでを縦方向及び／又は横方向の配線により接続するとき、前記ドライバと前記レシーバ間の各経路に生じる遅延時間と、前記ドライバと前記基準点とのマンハッタン距離と、前記ドライバから前記基準点までを前記斜め配線を用いた配線で接続する場合の配線長との差とが、それぞれ前記ネット毎に算出されており、
   前記位置判定機能では、前記遅延時間と前記差とに重み付き係数を掛けて算出される評価値に基づき前記ネットの順位が決定され、前記順位の高い前記ネットから順に前記位置判定が行われることを特徴とする設計支援装置。
8. 請求項１又は２において、
   前記配線レイアウトは、互いに直交するｘ軸とｙ軸とによって形成される２次元平面にて決定され、
   前記斜め配線は、前記ｘ軸に対してα度（０＜α＜９０）をなす第１の斜め配線と前記ｘ軸に対してβ度（９０＜β＜１８０）をなす第２の斜め配線とを含み、
   前記レイアウト機能では、前記ドライバの前記出力端子と前記基準点とを結ぶ線分が前記ｘ軸となす角が０度より大きく９０度より小さい場合には、前記第１の斜め配線が使用され、該線分が前記ｘ軸となす角が９０度より大きい場合には、前記第２の斜め配線が使用されることを特徴とする設計支援装置。
9. 論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定し、かつ、前記複数のセルが配置される位置を特定する位置情報が格納されるコンピュータに、
   一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行う位置判定機能と、
   前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置するレイアウト機能とを実現させるためのプログラム。
10. 論理ゲートを複数組み合わせて、それぞれ異なる機能を実現する複数のセルを持つ集積回路において、予め傾きが定められた斜め配線を用いて前記複数のセルを接続するときの配線レイアウトを決定するレイアウトプログラムが格納される記憶部と、前記記憶部から前記レイアウトプログラムを読み出して実行する制御部とを有する設計支援装置における設計支援方法であって、
    前記記憶部には、予め前記複数のセルが配置される位置を特定する位置情報が記憶されており、
    前記制御部は、
    一のセルと、該一のセルの出力端子を介して駆動される１つ又は複数のセルとから形成されるネットにおいて、該一のセルをドライバとし、前記ドライバにより駆動される前記１つ又は複数のセルをそれぞれレシーバとするとき、前記位置情報に基づき前記ネット毎に前記ネットに含まれる前記１つ又は複数のレシーバの全体を囲む所定の領域を求め、
    前記ネット毎に前記ドライバが前記所定の領域の外部にあるかを確認する位置判定を行い、
    前記ドライバが前記所定の領域の外部にあると判定された前記ネットに対して、前記所定領域の内部から基準点を決定し、
    前記基準点と前記レシーバの入力端子とを縦方向及び／又は横方向の配線により接続可能な場合に、前記ドライバの前記出力端子と前記基準点とを接続する配線に前記斜め配線を配置することを特徴とする設計支援方法。

Images