[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP4511888B2 - Wiring pattern creation device, wiring pattern creation method, wiring pattern creation program, and recording medium - Google Patents

Wiring pattern creation device, wiring pattern creation method, wiring pattern creation program, and recording medium Download PDF

Info

Publication number
JP4511888B2
JP4511888B2 JP2004210397A JP2004210397A JP4511888B2 JP 4511888 B2 JP4511888 B2 JP 4511888B2 JP 2004210397 A JP2004210397 A JP 2004210397A JP 2004210397 A JP2004210397 A JP 2004210397A JP 4511888 B2 JP4511888 B2 JP 4511888B2
Authority
JP
Japan
Prior art keywords
wiring
wiring patterns
influence
wiring pattern
patterns
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP2004210397A
Other languages
Japanese (ja)
Other versions
JP2006031468A (en
Inventor
大輔 福田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP2004210397A priority Critical patent/JP4511888B2/en
Publication of JP2006031468A publication Critical patent/JP2006031468A/en
Application granted granted Critical
Publication of JP4511888B2 publication Critical patent/JP4511888B2/en
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Landscapes

  • Internal Circuitry In Semiconductor Integrated Circuit Devices (AREA)
  • Design And Manufacture Of Integrated Circuits (AREA)

Description

この発明は、半導体装置の配線パターンを作成する配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラムおよび記録媒体に関する。   The present invention relates to a wiring pattern creation device, a wiring pattern creation method, a wiring pattern creation program, and a recording medium for creating a wiring pattern of a semiconductor device.

近年、LSI設計において、配線処理の重要性が増々高まってきている。これは、回路
の大規模化によって、配線処理での所要時間が増大してきていることが理由に挙げられる。また最近特に注目される理由として、回路の微細化により配線がシグナルインテグリティに大きく影響を与えるようになってきている点がある。ノイズや遅延が回路に与える影響は配線パターンが確定しないと精度よく解析できないため、詳細配線が完了して初めて本格的な対策が可能となる。
In recent years, the importance of wiring processing has been increasing in LSI design. This is because the time required for wiring processing has increased due to the increase in circuit scale. Another reason that has recently attracted particular attention is that wiring has become a major influence on signal integrity due to circuit miniaturization. Since the influence of noise and delay on the circuit cannot be analyzed accurately unless the wiring pattern is determined, a full-scale countermeasure can be implemented only after the detailed wiring is completed.

このLSI設計では一般に、初期配線(概略配線)によって配線がどの領域を通過する
かを決定し、その後に、詳細な配線経路を確定する。この際、配線エラーを起こさないことが最も重要である。図13は、従来の配線エラーを示す説明図である。
In this LSI design, generally, an initial wiring (schematic wiring) determines which region the wiring passes through, and then a detailed wiring path is determined. At this time, it is most important not to cause a wiring error. FIG. 13 is an explanatory diagram showing a conventional wiring error.

図13において、たとえば、配線パターンaおよび配線パターンb、配線パターンcおよび配線パターンdのように、異なる配線パターンどうしの接触や、配線パターンeのように配線禁止領域1300との接触は、配線エラーとなるため、配線する際の配線エラー制約として処理をおこなう。   In FIG. 13, for example, contact between different wiring patterns such as wiring pattern a and wiring pattern b, wiring pattern c and wiring pattern d, or contact with the wiring prohibited area 1300 such as wiring pattern e is a wiring error. Therefore, processing is performed as a wiring error constraint when wiring.

しかし、近年はプロセスの微細化が進み、歩留まりの向上、タイミング制約、クロストークノイズの軽減などさまざまな観点から配線を行う必要が生じてきた。クロストークとは、配線間に生じる容量のために、信号の波形、遅延が変動する現象である。配線が長距離を近接すると、配線間容量が大きくなり、クロストークによる影響からノイズ、遅延が大きくなる。   However, in recent years, process miniaturization has progressed, and it has become necessary to perform wiring from various viewpoints such as improvement in yield, timing restriction, and reduction of crosstalk noise. Crosstalk is a phenomenon in which the waveform and delay of a signal fluctuate due to capacitance generated between wirings. When the wirings are close to each other over a long distance, the capacitance between the wirings increases, and noise and delay increase due to the influence of crosstalk.

配線が長距離隣接した場合、当該配線間に寄生容量が発生し、配線を伝達する信号の遅延が大きくなる。また一方の配線を伝わる信号が変化した際には、容量を伝わって他方の配線の電圧も変動することにより、誤動作を引き起こす場合もある。   When wirings are adjacent to each other for a long distance, a parasitic capacitance is generated between the wirings, and a delay of a signal transmitted through the wiring is increased. Further, when the signal transmitted through one wiring changes, the voltage of the other wiring also varies through the capacitance, which may cause malfunction.

また、信号遷移のタイミングが近い配線どうしが隣接すると、信号波形が変化し、遅延の変動などの悪影響が大きくなる。このような影響は、一般に配線どうしの隣接長が長い場合、配線を駆動するセルの駆動力の差が大きい場合、信号遷移のタイミングが近い場合に大きくなる。   In addition, if wirings having similar signal transition timings are adjacent to each other, the signal waveform changes, and adverse effects such as delay fluctuations increase. Such an effect is generally increased when the adjacent length between the wirings is long, when the difference in driving force between cells driving the wiring is large, and when the timing of signal transition is close.

また、従来のトラックアサインメント手法は、チップを小領域に分割し、領域内の線分集合をトラックへ、マッチングによって割り当てる手法であり、詳細配線の前工程としての使用や、一部の配線のみへの適用など、いくつかの手法が提案されている(たとえば、下記非特許文献1を参照。)。   The conventional track assignment method divides the chip into small areas and assigns a set of line segments to the track by matching. It can be used as a pre-process for detailed wiring or only for some wiring. Several methods have been proposed (eg, see Non-Patent Document 1 below).

シャビア・バテリワラ(Shabbir Batterywala),ナレンドラ・シェノイ(Narendra Shenoy),ウィリアム・ニコルズ(William Nicholls),ハイ・シュー(Hai Zhou)著,“トラック アサイメント:ア デザイラブル インターメディエイト ステップ ビットウィーン グローバル ルーティング アンド ディテイルド ルーティング(Track Assignment: A Desirable Intermediate Step Between Global Routing and Detailed Routing)”,インターナショナル カンファレンス イン コンピュータ エイデッド デザイン(International Conference in Computer Aided Design),2002年,pp.59-66"Track Assignment: A Desireable Intermediate Step Bit Vienna Global Routing and Detail" by Shabbir Batterywala, Narendra Shenoy, William Nicholls, and Hai Zhou Track Assignment: A Desirable Intermediate Step Between Global Routing and Detailed Routing ”, International Conference in Computer Aided Design, 2002, pp.59-66

しかしながら、上述した従来技術では、隣接配線が原因となるクロストークノイズやタイミングエラーなどが生じた際には、配線確定後に人手によって配線の隣接並行配線長を減らし、問題の改善をおこなっていた。このため、エラー修正にかかる所要時間の増大や、修正による回路特性の変化などが生じるという問題があった。   However, in the above-described prior art, when crosstalk noise or timing error caused by the adjacent wiring occurs, the adjacent parallel wiring length of the wiring is manually reduced after the wiring is determined to improve the problem. For this reason, there are problems that an increase in time required for error correction and a change in circuit characteristics due to the correction occur.

また、配線中に並行配線長を考慮してエラーの削減をおこなう手法も提案されているが、エラーとなる部分の修正のみであり、LSIの性能向上という観点での対策はなされて
いないという問題があった。さらに、近年、LSIの集積度向上や大規模化に伴い、LS
Iの製造歩留まりの低下がするという問題があった。
In addition, a method has been proposed to reduce errors in consideration of the parallel wiring length during wiring, but only the correction of the error part has been made, and no measures have been taken from the viewpoint of improving LSI performance. was there. Furthermore, in recent years, with the increase in integration density and scale of LSI, LS
There was a problem that the production yield of I was reduced.

この歩留まり低下の原因の一つとしてプロセス内の小さなごみ(デフェクト)によりチップ上の配線がショート/オープンを起こしてしまうランダム歩留まりがある。図14は、従来のデフェクトによる配線ショートを示す説明図である。   One of the causes of this decrease in yield is a random yield in which wiring on a chip is shorted / opened due to small debris in the process. FIG. 14 is an explanatory view showing a wiring short due to a conventional defect.

図14において、エッチング法によっておこなうアルミ配線では、配線パターン1401,1402間にデフェクトDが存在すると、配線のショートが生じる。このように、配線が密集し、配線パターンどうしの隣接配線長が大きくなると、デフェクトが原因となる歩留まりの低下は避けることができないという問題があった。   In FIG. 14, in the aluminum wiring performed by the etching method, if a defect D exists between the wiring patterns 1401 and 1402, a wiring short circuit occurs. As described above, when the wirings are densely packed and the adjacent wiring lengths between the wiring patterns become large, there is a problem that a reduction in yield due to defects cannot be avoided.

この発明は、上述した従来技術による問題点を解消するため、簡単かつ最適な配線パターン処理をおこなうことにより、後工程での配線パターンの修正を防止し、LSIの歩留
まりの向上を図ることができる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラム、および記録媒体を提供することを目的とする。
In order to solve the above-described problems caused by the prior art, the present invention can perform simple and optimal wiring pattern processing to prevent correction of the wiring pattern in a later process and improve the yield of the LSI. An object is to provide a wiring pattern creation device, a wiring pattern creation method, a wiring pattern creation program, and a recording medium.

上述した課題を解決し、目的を達成するため、この発明にかかる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラム、および記録媒体は、配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出し、抽出された配線パターンの集合から、前記隣接しあう配線パターン間に生じるクロストークの影響度を取得し、取得された影響度に基づいて完全グラフを作成し、作成された完全グラフを用いて、異なるグループどうしの配線パターン間におけるクロストークの影響度の総和が最小となるように、前記配線パターンの集合を複数のグループに分け、分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けることを特徴とする。 In order to solve the above-described problems and achieve the object, a wiring pattern creation device, a wiring pattern creation method, a wiring pattern creation program, and a recording medium according to the present invention include a plurality of wiring patterns wired in parallel on a wiring track. A set of adjacent wiring patterns is extracted from the set, and the degree of influence of crosstalk generated between the adjacent wiring patterns is obtained from the extracted set of wiring patterns, and based on the obtained degree of influence. A complete graph, and using the created complete graph, divide the set of wiring patterns into a plurality of groups so that the sum of the influence of crosstalk between the wiring patterns of different groups is minimized, Separate the wiring patterns in each group on the wiring track so that the wiring patterns in the same group are not adjacent to each other. And wherein the allocating.

また、上記発明において、隣接しあう配線パターン間の距離に基づいて、前記隣接しあう配線パターン間に生じるクロストークの影響度を取得することとしてもよい。 Moreover, in the said invention, it is good also as acquiring the influence degree of the crosstalk which arises between the said wiring patterns which adjoin based on the distance between the wiring patterns which adjoin each other.

また、上記発明において、隣接しあう配線パターンどうしの並行配線長に基づいて、前記隣接しあう配線パターン間に生じるクロストークの影響度を取得することとしてもよい。 In the above invention, the degree of influence of crosstalk generated between the adjacent wiring patterns may be acquired based on the parallel wiring length of the adjacent wiring patterns.

また、上記発明において、配線パターンに信号を供給するセルの駆動力に基づいて、前記隣接しあう配線パターン間に生じるクロストークの影響度を取得することとしてもよい。 In the above invention, the degree of influence of crosstalk generated between the adjacent wiring patterns may be acquired based on the driving force of a cell that supplies a signal to the wiring pattern.

また、上記発明において、前記配線パターンの集合の中から、配線長が所定長以上となる配線パターンを抽出し、抽出された配線パターンの集合を複数のグループにグループ分けすることとしてもよい。   In the above invention, a wiring pattern having a wiring length of a predetermined length or more may be extracted from the set of wiring patterns, and the extracted wiring pattern set may be grouped into a plurality of groups.

また、上記発明において、抽出された配線パターンの集合に基づいて、前記配線トラック上に前記各配線パターンを配線する場合に生じる配線エラーの制約に関する情報を取得し、取得された配線エラーの制約に関する情報に基づいて、グループ分けされた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けることとしてもよい。   Further, in the above invention, based on the set of extracted wiring patterns, information related to the wiring error constraint that occurs when wiring each wiring pattern on the wiring track is acquired, and the acquired wiring error constraint is related to Based on the information, the wiring patterns in the grouped groups may be allocated on the wiring track so that the wiring patterns in the same group are not adjacent to each other.

これらの発明によれば、クロストークの影響度が大きい配線パターンどうしを隣接配線トラックに割り付けることを防止することができる。特に、クロストークの影響度を配線パターン間の距離、並行配線長、セルの駆動能力に基づいて取得することにより、配線間容量の発生を抑制する回路設計を実現することができる。また、配線長の短い配線パターンをグループ分けの対象外とすることにより、配線自由度の向上を図ることができる。   According to these inventions, it is possible to prevent wiring patterns having a large degree of influence of crosstalk from being assigned to adjacent wiring tracks. In particular, by obtaining the degree of influence of crosstalk based on the distance between the wiring patterns, the parallel wiring length, and the cell driving capability, it is possible to realize a circuit design that suppresses the generation of inter-wiring capacitance. Further, by excluding a wiring pattern with a short wiring length from the grouping target, it is possible to improve the wiring flexibility.

本発明にかかる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラム、および記録媒体によれば、簡単かつ最適な配線パターン処理をおこなうことにより、後工程での配線パターンの修正を防止し、LSIの歩留まりの向上を図ることができ
るという効果を奏する。
According to the wiring pattern creation device, the wiring pattern creation method, the wiring pattern creation program, and the recording medium according to the present invention, by performing simple and optimal wiring pattern processing, it is possible to prevent correction of the wiring pattern in a later process, There is an effect that the yield of the LSI can be improved.

(実施の形態)
以下に添付図面を参照して、この発明にかかる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラムおよび記録媒体の好適な実施の形態を詳細に説明する。なお、下記の実施の形態にかかる配線パターン作成装置および配線パターン作成方法は、たとえば、この実施の形態にかかる配線パターン作成プログラムが記録された記録媒体を備えるCADによって実現することができる。
(Embodiment)
Exemplary embodiments of a wiring pattern creation device, a wiring pattern creation method, a wiring pattern creation program, and a recording medium according to the present invention will be explained below in detail with reference to the accompanying drawings. Note that the wiring pattern creation device and the wiring pattern creation method according to the following embodiment can be realized by, for example, a CAD including a recording medium in which the wiring pattern creation program according to this embodiment is recorded.

(配線パターン作成装置のハードウェア構成)
まず、この発明の実施の形態にかかる配線パターン作成装置のハードウェア構成について説明する。図1は、この発明の実施の形態にかかる配線パターン作成装置のハードウェア構成を示すブロック図である。
(Hardware configuration of wiring pattern creation device)
First, the hardware configuration of the wiring pattern creation device according to the embodiment of the present invention will be described. FIG. 1 is a block diagram showing a hardware configuration of a wiring pattern creation device according to an embodiment of the present invention.

図1において、配線パターン作成装置は、CPU101と、ROM102と、RAM103と、HDD(ハードディスクドライブ)104と、HD(ハードディスク)105と、FDD(フレキシブルディスクドライブ)106と、着脱可能な記録媒体の一例としてのFD(フレキシブルディスク)107と、ディスプレイ108と、I/F(インターフェース)109と、キーボード110と、マウス111と、スキャナ112と、プリンタ113と、を備えている。また、各構成部はバス100によってそれぞれ接続されている。   In FIG. 1, the wiring pattern creation device is an example of a CPU 101, ROM 102, RAM 103, HDD (hard disk drive) 104, HD (hard disk) 105, FDD (flexible disk drive) 106, and a removable recording medium. FD (flexible disk) 107, display 108, I / F (interface) 109, keyboard 110, mouse 111, scanner 112, and printer 113. Each component is connected by a bus 100.

ここで、CPU101は、配線パターン作成装置の全体の制御を司る。ROM102は、ブートプログラムなどのプログラムを記憶している。RAM103は、CPU101のワークエリアとして使用される。HDD104は、CPU101の制御にしたがってHD105に対するデータのリード/ライトを制御する。HD105は、HDD104の制御で書き込まれたデータを記憶する。   Here, the CPU 101 controls the entire wiring pattern creation apparatus. The ROM 102 stores a program such as a boot program. The RAM 103 is used as a work area for the CPU 101. The HDD 104 controls reading / writing of data with respect to the HD 105 according to the control of the CPU 101. The HD 105 stores data written under the control of the HDD 104.

FDD106は、CPU101の制御にしたがってFD107に対するデータのリード/ライトを制御する。FD107は、FDD106の制御で書き込まれたデータを記憶したり、FD107に記憶されたデータを配線パターン作成装置に読み取らせたりする。   The FDD 106 controls reading / writing of data with respect to the FD 107 according to the control of the CPU 101. The FD 107 stores data written under the control of the FDD 106 or causes the wiring pattern creation device to read data stored in the FD 107.

また、着脱可能な記録媒体として、FD107のほか、CD−ROM(CD−R、CD−RW)、MO、DVD(Digital Versatile Disk)、メモリーカードなどであってもよい。ディスプレイ108は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ108は、たとえば、CRT、TFT液晶ディスプレイ、プラズマディスプレイなどを採用することができる。   In addition to the FD 107, the removable recording medium may be a CD-ROM (CD-R, CD-RW), MO, DVD (Digital Versatile Disk), memory card, or the like. The display 108 displays data such as a document, an image, and function information as well as a cursor, an icon, or a tool box. As this display 108, for example, a CRT, a TFT liquid crystal display, a plasma display, or the like can be adopted.

I/F109は、通信回線を通じてインターネットなどのネットワーク114に接続され、このネットワーク114を介して他の装置に接続される。そして、I/F109は、ネットワーク114と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。I/F109には、たとえばモデムやLANアダプタなどを採用することができる。   The I / F 109 is connected to a network 114 such as the Internet through a communication line, and is connected to other devices via the network 114. The I / F 109 controls an internal interface with the network 114 and controls data input / output from an external device. For example, a modem or a LAN adapter may be employed as the I / F 109.

キーボード110は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス111は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。   The keyboard 110 includes keys for inputting characters, numbers, various instructions, and the like, and inputs data. Moreover, a touch panel type input pad or a numeric keypad may be used. The mouse 111 performs cursor movement, range selection, window movement, size change, and the like. A trackball or a joystick may be used as long as they have the same function as a pointing device.

スキャナ112は、画像を光学的に読み取り、配線パターン作成装置内に画像データを取り込む。なお、スキャナ112は、OCR機能を持たせてもよい。また、プリンタ113は、画像データや文書データを印刷する。プリンタ113には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。   The scanner 112 optically reads an image and takes in the image data into the wiring pattern creation device. The scanner 112 may have an OCR function. The printer 113 prints image data and document data. For example, a laser printer or an ink jet printer can be employed as the printer 113.

(配線パターン作成装置の機能的構成)
つぎに、この発明の実施の形態にかかる配線パターン作成装置の機能的構成について説明する。図2は、この発明の実施の形態にかかる配線パターン作成装置の機能的構成を示すブロック図である。
(Functional configuration of wiring pattern creation device)
Next, a functional configuration of the wiring pattern creation device according to the embodiment of the present invention will be described. FIG. 2 is a block diagram showing a functional configuration of the wiring pattern creation device according to the embodiment of the present invention.

図2において、配線パターン作成装置200は、記憶部201と、集合抽出部202と、影響度取得部203と、グループ分け部204と、割付部205と、配線パターン抽出部206と、配線エラー制約情報取得部207と、を備える。   In FIG. 2, the wiring pattern creation apparatus 200 includes a storage unit 201, a set extraction unit 202, an influence degree acquisition unit 203, a grouping unit 204, an allocation unit 205, a wiring pattern extraction unit 206, and a wiring error constraint. An information acquisition unit 207.

記憶部201は、配線トラック上に並行に配線された複数の配線パターン(のデータ)を記憶する。この記憶されている配線パターンは、たとえば、グローバル配線処理によって、任意の配線層の配線トラック上に適当に並行配線されたデータである。この記憶部201は、具体的には、たとえば、図1に示したROM102、RAM103、HD105、FD107等の記録媒体によってその機能を実現する。   The storage unit 201 stores a plurality of wiring patterns (data thereof) wired in parallel on the wiring track. The stored wiring pattern is data appropriately wired in parallel on a wiring track of an arbitrary wiring layer by, for example, global wiring processing. Specifically, the storage unit 201 realizes its function by a recording medium such as the ROM 102, the RAM 103, the HD 105, and the FD 107 shown in FIG.

また、集合抽出部202は、記憶部201に記憶されている、配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する。具体的には、配線トラックのうち、任意の配線トラック領域上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する。ここで、集合抽出部202によって抽出された一連の隣接する配線パターンの集合について説明する。図3は、集合抽出部202によって抽出された一連の隣接する配線パターンの集合を示す説明図である。   The set extraction unit 202 also extracts a set of adjacent wiring patterns from a plurality of wiring patterns that are stored in the storage unit 201 and are wired in parallel on the wiring track. Specifically, a set of adjacent wiring patterns is extracted from a plurality of wiring patterns wired in parallel on an arbitrary wiring track area among the wiring tracks. Here, a set of adjacent wiring patterns extracted by the set extraction unit 202 will be described. FIG. 3 is an explanatory diagram showing a set of a series of adjacent wiring patterns extracted by the set extraction unit 202.

図3において、配線パターンの集合Sk(k=1,2,・・・,K)は、任意の配線トラック領域Rk内に存在する配線パターンWi(i=1,2,・・・,P)の集合である。図3では、配線パターン数は5であるため、P=5である。また、配線トラック領域Rkは、5本の配線トラックT1〜T5を有する。   In FIG. 3, a set of wiring patterns Sk (k = 1, 2,..., K) is a wiring pattern Wi (i = 1, 2,..., P) existing in an arbitrary wiring track region Rk. Is a set of In FIG. 3, since the number of wiring patterns is 5, P = 5. Further, the wiring track region Rk has five wiring tracks T1 to T5.

ここで、配線パターンWi,Wj間の距離dijとは、図3中、y方向における配線パターンWi,Wj間の間隔である。jは、配線パターンWiの添え字iに対応し、i≠jである。配線パターンW1を例に挙げると、配線パターンW2との間隔は距離d12であらわされ、配線パターンW3との間隔は距離d13であらわされ、配線パターンW4との間隔は距離d14であらわされ、配線パターンW5との間隔は距離d15であらわされる。   Here, the distance dij between the wiring patterns Wi and Wj is an interval between the wiring patterns Wi and Wj in the y direction in FIG. j corresponds to the subscript i of the wiring pattern Wi, and i ≠ j. Taking the wiring pattern W1 as an example, the distance from the wiring pattern W2 is represented by a distance d12, the distance from the wiring pattern W3 is represented by a distance d13, and the distance from the wiring pattern W4 is represented by a distance d14. The distance from W5 is represented by a distance d15.

また、配線パターンWi,Wjどうしの並行配線長cijとは、任意の配線パターンと他の配線パターンとをy方向(従配線方向)に重ねた場合、x方向(主配線方向)に互いに
並行に配線されている配線長、すなわち、重複している配線長をいう。配線W3を例に挙げると、配線パターンW3と配線パターンW1との間では並行配線長c31であり、配線パターンW3と配線パターンW2との間では並行配線長c32であり、配線パターンW3と配線パターンW4との間では並行配線長c34であり、配線パターンW3と配線パターンW5との間では並行配線長c35である。
Further, the parallel wiring length cij between the wiring patterns Wi and Wj means that when an arbitrary wiring pattern and another wiring pattern are overlapped in the y direction (secondary wiring direction), they are parallel to each other in the x direction (main wiring direction). The wiring length that is wired, that is, the overlapping wiring length. Taking the wiring W3 as an example, the parallel wiring length c31 is between the wiring pattern W3 and the wiring pattern W1, and the parallel wiring length c32 is between the wiring pattern W3 and the wiring pattern W2. The parallel wiring length c34 is between W4 and the parallel wiring length c35 between the wiring pattern W3 and the wiring pattern W5.

また、配線パターンの集合Sk内の配線パターンWiは、それぞれ信号が供給されるセルの駆動力が対応付けられている。図4は、セルの駆動力と配線パターンの対応関係を示す図表である。この図表は、たとえば、上述の記憶部201に記憶されている。ここで、セルの駆動力biとは、セル内部の抵抗値の逆数そのもの、または当該逆数に比例する値であらわされており、相対的に駆動力biが低いと他の配線パターンの影響を受け易く、駆動力biが高いと他の配線パターンに影響を与え易い。   Each wiring pattern Wi in the wiring pattern set Sk is associated with a driving force of a cell to which a signal is supplied. FIG. 4 is a chart showing the correspondence between the cell driving force and the wiring pattern. This chart is stored in, for example, the storage unit 201 described above. Here, the driving force bi of the cell is represented by the reciprocal of the resistance value inside the cell itself or a value proportional to the reciprocal, and if the driving force bi is relatively low, it is affected by other wiring patterns. When the driving force bi is high, other wiring patterns are easily affected.

集合抽出部202は、配線パターンの集合Skを抽出する際、集合Sk内の各配線パターンWiに対応する駆動力も抽出する。この集合抽出部202は、具体的には、たとえば、図1に示したROM102、RAM103、HD105、FD107等に記録されたプログラムを、CPU101が実行することによって、またはI/F109によってその機能を実現する。   When extracting the wiring pattern set Sk, the set extraction unit 202 also extracts the driving force corresponding to each wiring pattern Wi in the set Sk. Specifically, the set extraction unit 202 realizes its function by the CPU 101 executing the program recorded in the ROM 102, RAM 103, HD 105, FD 107, etc. shown in FIG. 1 or by the I / F 109, for example. To do.

影響度取得部203は、集合抽出部202によって抽出された配線パターンの集合から、各配線パターンWi,Wj間に生じるクロストークの影響度を取得する。このクロストークの影響度Fijは、後述するグループ分け部204によるグループ分け処理の際に重み付けされるコスト値として用いられる。   The influence level acquisition unit 203 acquires the influence level of crosstalk generated between the wiring patterns Wi and Wj from the set of wiring patterns extracted by the set extraction unit 202. The influence level Fij of the crosstalk is used as a cost value weighted in the grouping process by the grouping unit 204 described later.

ここで、「クロストーク」とは、配線間に生じる容量のために、信号の波形、遅延が変動する現象であり、他の配線パターンに影響を与える。たとえば、隣接する一対の配線パターンWi,Wjが長距離にわたって近接したり、配線パターンWi,Wj間の距離が近接したりすると、配線間容量が大きくなり、クロストークが生じることとなる。その影響により他の配線パターンにノイズが発生したり、遅延量が大きくなったりする。また、上述したように、駆動力もクロストークの発生原因となる。   Here, “crosstalk” is a phenomenon in which the waveform and delay of a signal fluctuate due to capacitance generated between wirings, and affects other wiring patterns. For example, if a pair of adjacent wiring patterns Wi and Wj are close to each other over a long distance, or if the distance between the wiring patterns Wi and Wj is close, the inter-wiring capacity increases and crosstalk occurs. As a result, noise is generated in other wiring patterns, and the delay amount is increased. Further, as described above, the driving force also causes crosstalk.

この影響度取得部203は、各配線パターンWi,Wj間の距離dijに基づいて、各配線パターンWi,Wj間に生じるクロストークの影響度Fijを取得することができる。具体的には、集合Sk内の各配線パターンWi,Wj間の距離dijを抽出し、この抽出された距離dijをクロストークの影響度とすることができる。この距離dijが大きいと配線間容量が小さくなり、距離dijが小さいと配線間容量が大きくなる。   The degree of influence acquisition unit 203 can acquire the degree of influence Fij of crosstalk generated between the wiring patterns Wi and Wj based on the distance dij between the wiring patterns Wi and Wj. Specifically, the distance dij between the wiring patterns Wi and Wj in the set Sk can be extracted, and the extracted distance dij can be used as the degree of influence of crosstalk. If this distance dij is large, the interwiring capacitance decreases, and if the distance dij is small, the interwiring capacitance increases.

また、影響度取得部203は、配線パターンWi,Wjどうしの並行配線長cijに基づいて、各配線パターンWi,Wj間に生じるクロストークの影響度Fijを取得することができる。具体的には、集合Sk内の各配線パターンWi,Wjどうしの並行配線長cijを抽出し、この抽出された並行配線長cijをクロストークの影響度とすることができる。この並行配線長cijが大きいと配線間容量が大きくなり、並行配線長cijが小さいと配線間容量が小さくなる。   Further, the influence degree acquisition unit 203 can acquire the influence degree Fij of the crosstalk generated between the wiring patterns Wi and Wj based on the parallel wiring length cij between the wiring patterns Wi and Wj. Specifically, the parallel wiring length cij between the wiring patterns Wi and Wj in the set Sk can be extracted, and the extracted parallel wiring length cij can be set as the degree of influence of crosstalk. When the parallel wiring length cij is large, the inter-wiring capacity increases, and when the parallel wiring length cij is small, the inter-wiring capacity decreases.

また、影響度取得部203は、配線パターンに信号を供給するセルの駆動力biに基づいて、各配線パターンWi,Wj間に生じるクロストークの影響度Fijを取得することができる。たとえば、配線パターンWiごとに抽出されたセルの駆動力biを抽出し、抽出
元の一の配線パターンWiの駆動力biと他の配線パターンWjの駆動力bjとの差の絶対値bijを算出する。この算出された絶対値bijをクロストークの影響度Fijとすることができる。この絶対値bijが大きくなればなるほど、いずれか一方の配線パターンWiが他方の配線パターンWjに影響を与える。
The influence acquisition unit 203 can acquire the influence Fij of the crosstalk generated between the wiring patterns Wi and Wj based on the driving force bi of the cell that supplies a signal to the wiring pattern. For example, the cell driving power bi extracted for each wiring pattern Wi is extracted, and the absolute value bij of the difference between the driving power bi of one wiring pattern Wi of the extraction source and the driving power bj of another wiring pattern Wj is calculated. To do. The calculated absolute value bij can be used as the crosstalk influence Fij. As the absolute value bij increases, one of the wiring patterns Wi affects the other wiring pattern Wj.

また、影響度取得部203は、上述した距離dij、並行配線長cij、駆動力の差の絶対値bijの組み合わせに基づいて、各配線パターンWi,Wj間に生じるクロストークの影響度Fijを取得することができる。たとえば、距離dijと並行配線長cijを用いる場合、距離dijの逆数と並行配線長cijとを掛けることにより、クロストークの影響度Fijを算出することができる。   The influence acquisition unit 203 acquires the influence Fij of the crosstalk generated between the wiring patterns Wi and Wj based on the combination of the distance dij, the parallel wiring length cij, and the absolute value bij of the driving force difference. can do. For example, when the distance dij and the parallel wiring length cij are used, the crosstalk influence Fij can be calculated by multiplying the reciprocal of the distance dij and the parallel wiring length cij.

また、距離dijと駆動力biを用いる場合、距離dの逆数と駆動力の差の絶対値bijと
を掛けることにより、クロストークの影響度Fijを算出することができる。さらに、並行配線長cijと駆動力の差の絶対値bijを用いる場合、並行配線長cと駆動力の差の絶対値bijとを掛けることにより、クロストークの影響度Fijを算出することができる。また、距離dij、並行配線長cij、駆動力biをすべて用いる場合、距離dijの逆数と並行配線長cijと駆動力の差の絶対値bijとを掛けることにより、クロストークの影響度Fijを算出することができる。
When the distance dij and the driving force bi are used, the influence degree Fij of the crosstalk can be calculated by multiplying the reciprocal of the distance d by the absolute value bij of the difference between the driving forces. Further, when the parallel wiring length cij and the absolute value bij of the driving force difference are used, the influence Fij of the crosstalk can be calculated by multiplying the parallel wiring length c and the absolute value bij of the driving force difference. . When all of the distance dij, the parallel wiring length cij, and the driving force bi are used, the influence Fij of the crosstalk is calculated by multiplying the reciprocal of the distance dij by the parallel wiring length cij and the absolute value bij of the driving force difference. can do.

この影響度取得部203は、具体的には、たとえば、図1に示したROM102、RAM103、HD105、FD107等に記録されたプログラムを、CPU101が実行することによって、またはI/F109によってその機能を実現する。   Specifically, for example, the influence level acquisition unit 203 has its function executed by the CPU 101 executing the program recorded in the ROM 102, RAM 103, HD 105, FD 107, etc. shown in FIG. Realize.

グループ分け部204は、影響度取得部203によって取得された影響度Fijに基づいて、配線パターンの集合Skを複数のグループGm(m=1、2、・・・、M)に分ける。グループ数mは、あらかじめ設定することができる。このグループ分けは、たとえば、異なるグループGmどうしの配線パターンWi間におけるクロストークの影響度Fijの総和Σが最小となるように、配線パターンの集合を複数のグループに分けることができる。このグループ分けはミンカット法によっておこなうことができる。   The grouping unit 204 divides the wiring pattern set Sk into a plurality of groups Gm (m = 1, 2,..., M) based on the influence Fij acquired by the influence acquisition unit 203. The number of groups m can be set in advance. In this grouping, for example, a set of wiring patterns can be divided into a plurality of groups so that the sum Σ of the crosstalk influence Fij between the wiring patterns Wi of different groups Gm is minimized. This grouping can be done by the Minkat method.

この場合、配線トラック領域Rk内のトラック数をtとし、グループ分けされるグループ数をmとすると、各グループ内のノードNiの数の最大値、すなわち、配線パターンWiの数の最大値PがP=T/mとなるように、グループ内のノード数をほぼ均等に分配することができる。なお、P=T/mが割り切れない場合は小数点以下を切り上げる。   In this case, assuming that the number of tracks in the wiring track region Rk is t and the number of groups to be grouped is m, the maximum value of the number of nodes Ni in each group, that is, the maximum value P of the number of wiring patterns Wi is obtained. The number of nodes in the group can be distributed almost evenly so that P = T / m. If P = T / m is not divisible, the decimal part is rounded up.

このグループ分け部204によるグループ分けについて具体的に説明する。まず、配線パターンの集合Sk内の配線パターンWiと、影響度取得部203によって取得された配線パターン間の影響度Fijとを用いて、完全グラフを作成する。図5は、完全グラフの一例を示す説明図である。   The grouping by the grouping unit 204 will be specifically described. First, a complete graph is created by using the wiring pattern Wi in the wiring pattern set Sk and the influence Fij between the wiring patterns acquired by the influence acquisition unit 203. FIG. 5 is an explanatory diagram showing an example of a complete graph.

図5において、完全グラフ500は、配線パターンWiに対応するノードNiと、配線パターン間の影響度に対応するエッジeijとから構成されている。たとえば、エッジe12は、配線パターンW1と配線パターンW2との間の影響度F12をあらわしている。   In FIG. 5, a complete graph 500 includes nodes Ni corresponding to the wiring patterns Wi and edges eij corresponding to the degree of influence between the wiring patterns. For example, the edge e12 represents the influence F12 between the wiring pattern W1 and the wiring pattern W2.

なお、本例では、配線トラック領域Rk内のトラック数TがT=5であり、また、グループ分けされるグループ数mをm=2とすると、各グループ内のノードNiの数の最大値、すなわち、配線パターンWiの数の最大値Pは、P=3となる。したがって、グループ分け部204は、グループ数が2、グループ内のノードの最大値が3という条件が与えられる。   In this example, if the number T of tracks in the wiring track region Rk is T = 5 and the number m of groups to be grouped is m = 2, the maximum number of nodes Ni in each group, That is, the maximum value P of the number of wiring patterns Wi is P = 3. Therefore, the grouping unit 204 is given a condition that the number of groups is 2 and the maximum value of the nodes in the group is 3.

この条件下で、異なるグループGmどうしの配線パターン間におけるクロストークの影響度Fijの総和Σが最小となるように、配線パターンの集合を複数のグループに分けることができる。グループ内のノードはエッジによって連結される。図5に示した完全グラフでは、エッジe12、e13、e23、e45について影響度F12、F13、F23、F45が高く、残余のエッジe14、e15、e24、e25、e34、e35の影響度F14、F15、F24、F25、F34、F35は、エッジe12、e13、e23、e45の影響度F12、F13、F23、F45に比べて低い値とされている。   Under this condition, the set of wiring patterns can be divided into a plurality of groups so that the total sum Σ of the crosstalk influence Fij between the wiring patterns of different groups Gm is minimized. The nodes in the group are connected by edges. In the complete graph shown in FIG. 5, the influences F12, F13, F23, F45 are high for the edges e12, e13, e23, e45, and the influences F14, F15 of the remaining edges e14, e15, e24, e25, e34, e35. , F24, F25, F34, and F35 have lower values than the influences F12, F13, F23, and F45 of the edges e12, e13, e23, and e45.

この影響度F14、F15、F24、F25、F34、F35の総和Σが最小である場合、グループ分けがおこなわれる。図6は、グループ分けされたグループの一例を示す説明図である。図6において、グループG1には、ノードN1〜N3が含まれており、グループG2には、ノードN4、N5が含まれている。   When the sum Σ of the influences F14, F15, F24, F25, F34, and F35 is minimum, grouping is performed. FIG. 6 is an explanatory diagram showing an example of the grouped group. In FIG. 6, the group G1 includes nodes N1 to N3, and the group G2 includes nodes N4 and N5.

同一グループ内のノード、たとえば、グループG1内のノードN1〜N3によってあらわされる配線パターンW1〜W3は、互いに隣接配線してはいけないことを示しており、同様に、グループG2内のノードN4、N5によってあらわされる配線パターンW4、W5も互いに隣接配線してはいけないことを示している。   The wiring patterns W1 to W3 represented by the nodes in the same group, for example, the nodes N1 to N3 in the group G1, indicate that they should not be adjacent to each other. Similarly, the nodes N4 and N5 in the group G2 This also indicates that the wiring patterns W4 and W5 represented by can not be adjacent to each other.

なお、このグループ分け部204によってグループ分けされる条件を、配線トラック制約と呼ぶ。このグループ分け部204は、具体的には、たとえば、図1に示したROM102、RAM103、HD105、FD107等に記録されたプログラムを、CPU101が実行することによって、またはI/F109によってその機能を実現する。   The condition for grouping by the grouping unit 204 is called wiring track restriction. Specifically, the grouping unit 204 realizes its function by the CPU 101 executing the program recorded in the ROM 102, RAM 103, HD 105, FD 107, etc. shown in FIG. 1, or by the I / F 109, for example. To do.

また、配線パターン抽出部206は、配線パターンの集合Skの中から、配線長が所定長以上となる配線パターンを抽出する。具体的には、所定長以上の配線パターンをグループ分け対象の配線パターンとして抽出し、所定長以上でない配線パターンをグループ分けの対象外の配線パターンとして抽出する。そして、グループ分け対象の配線パターンについては、上述のグループ分け部204によってグループ分けされ、グループ分けの対象外の配線パターンについては、上述のグループ分け部204によってグループ分けされない。   Further, the wiring pattern extraction unit 206 extracts a wiring pattern having a wiring length equal to or longer than a predetermined length from the wiring pattern set Sk. Specifically, a wiring pattern having a predetermined length or more is extracted as a wiring pattern to be grouped, and a wiring pattern not having a predetermined length or more is extracted as a wiring pattern not to be grouped. The wiring patterns to be grouped are grouped by the grouping unit 204 described above, and the wiring patterns not to be grouped are not grouped by the grouping unit 204 described above.

この場合の完全グラフを図7に示す。図7は、完全グラフの他の例を示す説明図である。配線パターンW3〜W5の配線長が、所定長以上でないとすると、図6に示した、配線パターンW3〜W5に対応するノードN3〜N5は、図7において削除される。したがって、図6において、残余のノードN1、N2についてミンカット法により、グループ分けする。図8は、グループ分けされたグループの他の例を示す説明図である。図8において、グループG1には、ノードN1、N2が含まれており、グループG2は空集合Nullとなっている。   A complete graph in this case is shown in FIG. FIG. 7 is an explanatory diagram showing another example of a complete graph. If the wiring lengths of the wiring patterns W3 to W5 are not equal to or longer than the predetermined length, the nodes N3 to N5 corresponding to the wiring patterns W3 to W5 shown in FIG. 6 are deleted in FIG. Therefore, in FIG. 6, the remaining nodes N1 and N2 are grouped by the min cut method. FIG. 8 is an explanatory diagram showing another example of grouped groups. In FIG. 8, the group G1 includes nodes N1 and N2, and the group G2 is an empty set Null.

この配線パターン抽出部206は、具体的には、たとえば、図1に示したROM102、RAM103、HD105、FD107等に記録されたプログラムを、CPU101が実行することによって、またはI/F109によってその機能を実現する。   Specifically, the wiring pattern extraction unit 206 has its function executed by the CPU 101 executing the program recorded in the ROM 102, RAM 103, HD 105, FD 107, etc. shown in FIG. 1 or by the I / F 109, for example. Realize.

また、割付部205は、グループ分け部204によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように配線トラック上に割り付ける。換言すれば、他のグループ内の配線パターンどうしが隣接するように、配線トラック上に割り付ける。   The assigning unit 205 assigns the wiring patterns in each group divided by the grouping unit 204 on the wiring track so that the wiring patterns in the same group are not adjacent to each other. In other words, the wiring patterns in other groups are allocated on the wiring track so that they are adjacent to each other.

具体的には、グループ数がmの場合、まず、グループG1内のノードに対応する配線パターンを配線トラックT1に割り付け、グループG2内のノードに対応する配線パターンを配線トラックT2に割り付ける。そして、同様に、グループGmまで順次割り付ける。このあと、グループ内にノードが残っている場合、そのノードの対応する配線パターンを、配線トラックTm+1から割り付ける。   Specifically, when the number of groups is m, first, a wiring pattern corresponding to a node in the group G1 is assigned to the wiring track T1, and a wiring pattern corresponding to a node in the group G2 is assigned to the wiring track T2. Similarly, the group Gm is sequentially allocated. Thereafter, when a node remains in the group, the wiring pattern corresponding to the node is assigned from the wiring track Tm + 1.

より具体的に図を用いて説明する。図9は、配線トラック領域Rkに割り付けられた配線パターンの一例を示す説明図である。図9において、配線トラック領域Rkでは、グループ数が2の場合、グループG1の配線パターンW1〜W3は、奇数番号の配線トラックT1、T3、T5に割り付け、グループG2の配線パターンW4、W5は、偶数番号の配線トラックT2、T4に割り付ける。なお、図中900は、配線禁止領域である。これにより、同一グループ内のノードに対応する配線パターンどうしが隣接しないように配線することができる。   This will be described more specifically with reference to the drawings. FIG. 9 is an explanatory diagram showing an example of a wiring pattern assigned to the wiring track region Rk. In FIG. 9, in the wiring track region Rk, when the number of groups is 2, the wiring patterns W1 to W3 of the group G1 are assigned to the odd-numbered wiring tracks T1, T3, and T5, and the wiring patterns W4 and W5 of the group G2 are Allocation to even-numbered wiring tracks T2, T4. In the figure, reference numeral 900 denotes a wiring prohibited area. Thereby, it is possible to perform wiring so that wiring patterns corresponding to nodes in the same group are not adjacent to each other.

この割付部205は、具体的には、たとえば、図1に示したROM102、RAM103、HD105、FD107等に記録されたプログラムを、CPU101が実行することによって、またはI/F109によってその機能を実現する。   Specifically, the allocating unit 205 realizes its function when the CPU 101 executes the program recorded in the ROM 102, RAM 103, HD 105, FD 107, etc. shown in FIG. 1, or by the I / F 109, for example. .

また、配線エラー制約情報取得部207は、集合抽出部202によって抽出された配線パターンの集合に基づいて、配線トラック上に各配線パターンを配線する場合に生じる配線エラーの制約に関する情報(配線エラー制約情報)を取得する。そして、割付部205は、配線エラー制約情報取得部207によって取得された配線エラー制約情報に基づいて、グループ分け部204によってグループ分けされた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように配線トラック上に割り付ける。   In addition, the wiring error constraint information acquisition unit 207 is based on the wiring pattern set extracted by the set extraction unit 202, and information on the wiring error constraint (wiring error constraint) that occurs when wiring patterns are wired on the wiring track. Information). Then, the allocating unit 205 converts the wiring patterns in each group grouped by the grouping unit 204 based on the wiring error constraint information acquired by the wiring error constraint information acquiring unit 207 into the wiring patterns in the same group. Allocate on wiring tracks so that they are not adjacent.

ここで、「配線エラー制約」とは、LSIのレイアウト設計上要求されるデザインルー
ルであり、具体的には、たとえば、スペーシングエラーや接触不良、断線などを防止するための制約である。また、「配線エラー制約情報」とは、たとえば、上述した配線エラー制約を数値化したコスト値である。より具体的には、配線パターンWiの配線長や配線禁
止領域のx方向の長さや存在する配線トラック番号、配線トラック上の位置などによって
あらかじめ設定される。
Here, the “wiring error constraint” is a design rule required in the LSI layout design, and specifically, for example, a constraint for preventing a spacing error, contact failure, disconnection, and the like. The “wiring error constraint information” is, for example, a cost value obtained by quantifying the wiring error constraint described above. More specifically, it is set in advance according to the wiring length of the wiring pattern Wi, the length in the x direction of the wiring prohibited area, the existing wiring track number, the position on the wiring track, and the like.

ここで、上述した割付部205によって割り付けられた配線パターンの他の例を図10に示す。図10は、配線トラック領域に割り付けられた配線パターンの他の例を示す説明図である。この図10に示した例は、配線エラー制約を考慮せずに割り付けられた配線パターンであり、配線パターンW5が、配線トラックT4の配線禁止領域900と重なっている。このような場合、配線エラーとなるため、割付部205では、配線パターンの入れ替えをおこなう。具体的には、配線トラックT2に割り付けられた配線パターンW4と、配線トラックT4に割り付けられた配線パターンW5とを入れ替える。   Here, another example of the wiring pattern allocated by the above-described allocation unit 205 is shown in FIG. FIG. 10 is an explanatory diagram showing another example of the wiring pattern assigned to the wiring track area. The example shown in FIG. 10 is a wiring pattern assigned without considering the wiring error constraint, and the wiring pattern W5 overlaps the wiring prohibited area 900 of the wiring track T4. In such a case, since a wiring error occurs, the allocation unit 205 replaces the wiring pattern. Specifically, the wiring pattern W4 assigned to the wiring track T2 is replaced with the wiring pattern W5 assigned to the wiring track T4.

なお、割付部205による配線パターンの入れ替えをおこなっても配線エラーが解消されない場合、再度グループ分け部204によるグループ分けを実行する。この場合、今回のグループ分けによるクロストークの影響度Fijの総和Σは、前回の総和Σ以上となるが、グループ数を変更したり、グループ内のノード(配線パターン)の組み合わせを変更したりして、異なるグループ分けをおこなう。   If the wiring error is not eliminated even if the wiring pattern is replaced by the allocating unit 205, the grouping by the grouping unit 204 is performed again. In this case, the total sum Σ of the crosstalk influence Fij due to the current grouping is equal to or greater than the previous total sum Σ, but the number of groups may be changed or the combination of nodes (wiring patterns) within the group may be changed. Make different groupings.

この配線エラー制約情報取得部207は、具体的には、たとえば、図1に示したROM102、RAM103、HD105、FD107等に記録されたプログラムを、CPU101が実行することによって、またはI/F109によってその機能を実現する。   Specifically, the wiring error constraint information acquisition unit 207 is executed when the CPU 101 executes a program recorded in the ROM 102, RAM 103, HD 105, FD 107, or the like shown in FIG. Realize the function.

(配線パターン作成処理手順)
つぎに、この発明の実施の形態にかかる配線パターン作成処理手順の一例について説明する。図11は、この発明の実施の形態にかかる配線パターン作成処理手順の一例を示すフローチャートである。図11において、まず、配線パターンの集合数をKとし、初期値をk=1とする(ステップS1101)。
(Wiring pattern creation processing procedure)
Next, an example of a wiring pattern creation processing procedure according to the embodiment of the present invention will be described. FIG. 11 is a flowchart showing an example of a wiring pattern creation processing procedure according to the embodiment of the present invention. In FIG. 11, first, the number of sets of wiring patterns is set to K, and the initial value is set to k = 1 (step S1101).

つぎに、集合抽出部202により、配線パターンの集合Skを抽出する(ステップS1102)。また、配線エラー制約情報取得部207により、抽出された集合Skについての配線エラー制約情報を取得する(ステップS1103)。   Next, the set extraction unit 202 extracts a set Sk of wiring patterns (step S1102). Also, the wiring error constraint information acquisition unit 207 acquires the wiring error constraint information for the extracted set Sk (step S1103).

そして、影響度取得部203により、集合Sk内の配線パターンWi、Wjどうしのクロストークの影響度Fijを取得する(ステップS1104)。このあと、グループ分け部204により、集合Skのグループ分けをおこなう(ステップS1105)。   Then, the influence level acquisition unit 203 acquires the crosstalk influence level Fij between the wiring patterns Wi and Wj in the set Sk (step S1104). Thereafter, the grouping unit 204 groups the set Sk (step S1105).

そして、割付部205により、各グループの配線パターンを、配線トラックに割り付ける(ステップS1106)。このあと、割り付けられた配線パターンに配線エラーがあるかどうかを判定する(ステップS1107)。配線エラーがある場合(ステップS1107:Yes)、再割付回数が所定回数でないときは(ステップS1108:No)、ステップS1106に移行して、配線パターンの割り付け(再割付)をおこなう。   Then, the assignment unit 205 assigns the wiring patterns of each group to the wiring tracks (step S1106). Thereafter, it is determined whether or not there is a wiring error in the assigned wiring pattern (step S1107). When there is a wiring error (step S1107: Yes), when the number of reassignments is not a predetermined number (step S1108: No), the process proceeds to step S1106, and the wiring pattern is assigned (reassigned).

一方、再割付回数が所定回数となった場合(ステップS1108:Yes)、ステップS1105に移行して、再度グループ分けをおこなう。また、ステップS1107において、配線エラーがない場合(ステップS1107:No)、k=Kでない場合(ステップS1109:No)、kをインクリメントして(ステップS1110)、ステップS1102に移行し、配線パターンの集合Skを抽出する。一方、k=Kの場合(ステップS1109:Yes)、一連の処理を終了する。   On the other hand, when the number of reallocations reaches a predetermined number (step S1108: Yes), the process proceeds to step S1105 to perform grouping again. In step S1107, if there is no wiring error (step S1107: No), and if k = K is not satisfied (step S1109: No), k is incremented (step S1110), the process proceeds to step S1102, and a set of wiring patterns is obtained. Extract Sk. On the other hand, if k = K (step S1109: Yes), the series of processes is terminated.

この実施の形態によれば、配線パターンを最適な配線トラックに割り付けることができるため、隣接配線パターン間のクロストークの発生を抑制し、LSIの性能の向上を図ることができる。また、これにより、後工程での配線パターンの修正を防止し、LSIの歩
留まりの向上を図ることができる。
According to this embodiment, since a wiring pattern can be assigned to an optimal wiring track, occurrence of crosstalk between adjacent wiring patterns can be suppressed, and LSI performance can be improved. In addition, this makes it possible to prevent correction of the wiring pattern in a later process and improve the yield of the LSI.

つぎに、この発明の実施の形態にかかる配線パターン作成処理手順の他の例について説明する。図12は、この発明の実施の形態にかかる配線パターン作成処理手順の他の例を示すフローチャートである。このフローチャートは、図11の処理手順に、配線パターン抽出部206による配線パターンWiの抽出処理手順を追加した例である。なお、図11に示したフローチャートと同一ステップには同一ステップ番号を付し、その説明を省略する。   Next, another example of the wiring pattern creation processing procedure according to the embodiment of the present invention will be described. FIG. 12 is a flowchart showing another example of the wiring pattern creation processing procedure according to the embodiment of the present invention. This flowchart is an example in which a wiring pattern Wi extraction process procedure by the wiring pattern extraction unit 206 is added to the processing procedure of FIG. In addition, the same step number is attached | subjected to the same step as the flowchart shown in FIG. 11, and the description is abbreviate | omitted.

図12において、ステップS1103のあと、配線パターン数をPとし、初期値をi=1とする(ステップS1204)。配線パターンWiの配線長が所定長以上かどうかを判定する(ステップS1205)。所定長以上である場合(ステップS1205:Yes)、配線パターンWiをグループ分け対象の配線パターンとして抽出する(ステップS1206)。一方、所定長以上でない場合(ステップS1205:No)、配線パターンWiをグループ分け対象外の配線パターンとして抽出する(ステップS1207)。   In FIG. 12, after step S1103, the number of wiring patterns is set to P, and the initial value is set to i = 1 (step S1204). It is determined whether or not the wiring length of the wiring pattern Wi is a predetermined length or more (step S1205). When the length is equal to or longer than the predetermined length (step S1205: Yes), the wiring pattern Wi is extracted as a wiring pattern to be grouped (step S1206). On the other hand, if it is not longer than the predetermined length (step S1205: No), the wiring pattern Wi is extracted as a wiring pattern that is not subject to grouping (step S1207).

そして、i=Pでない場合(ステップS1208:No)、iをインクリメントして(ステップS1209)、ステップS1205に移行する。一方、i=Pの場合(ステップS1208:Yes)、配線パターンWiの抽出処理が終了したこととなり、グループ分け対象となった配線パターンWiについて、影響度取得部203により、クロストークの影響度Fijを取得する(ステップS1210)。   If i = P is not satisfied (step S1208: NO), i is incremented (step S1209), and the process proceeds to step S1205. On the other hand, if i = P (step S1208: Yes), the extraction process of the wiring pattern Wi is completed, and the influence degree acquisition unit 203 causes the influence degree acquisition unit 203 to perform the influence degree Fij of the crosstalk. Is acquired (step S1210).

そして、グループ分け部204により、グループ分け対象の配線パターンWiをグルー
プ分けする(ステップS1211)。割付部205により、各グループGiの配線パター
ンWiを、配線トラックに割り付ける(ステップS1212)。このあと、割り付けられ
た配線パターンWiに配線エラーがあるかどうかを判定する(ステップS1213)。配
線エラーがある場合(ステップS1213:Yes)、再割付回数が所定回数でないときは(ステップS1214:No)、ステップS1212に移行して、配線パターンの割り付け(再割付)をおこなう。
Then, the grouping unit 204 groups the wiring patterns Wi to be grouped (step S1211). The assignment unit 205 assigns the wiring pattern Wi of each group Gi to the wiring track (step S1212). Thereafter, it is determined whether or not there is a wiring error in the assigned wiring pattern Wi (step S1213). When there is a wiring error (step S1213: Yes), when the number of reassignments is not a predetermined number (step S1214: No), the process proceeds to step S1212 and the wiring pattern is assigned (reassigned).

一方、再割付回数が所定回数となった場合(ステップS1214:Yes)、ステップS1211に移行して、再度グループ分けをおこなう。また、ステップS1213において、配線エラーがない場合(ステップS1213:No)、k=Kでない場合(ステップS1215:No)、kをインクリメントして(ステップS1216)、ステップS1102に移行し、配線パターンの集合Skを抽出する。一方、k=Kの場合(ステップS1215:Yes)、一連の処理を終了する。   On the other hand, when the number of reallocations reaches a predetermined number (step S1214: Yes), the process proceeds to step S1211 and grouping is performed again. In step S1213, if there is no wiring error (step S1213: No), and if k = K is not satisfied (step S1215: No), k is incremented (step S1216), the process proceeds to step S1102, and a set of wiring patterns is obtained. Extract Sk. On the other hand, if k = K (step S1215: Yes), the series of processes is terminated.

この実施の形態によれば、配線長が所定長よりも短い配線パターンについては、配線間容量が小さくなるため、クロストークの影響が小さい配線パターンであるとして、グループ分けの対象外としている。したがって、このような配線パターンについては配線トラック制約を考慮せずに、配線エラー制約のみを考慮して配線トラックに割り付けることができ、配線パターンの割り付けの自由度の向上を図ることができる。これにより、配線パターンの作成を容易におこなうことができる。   According to this embodiment, a wiring pattern whose wiring length is shorter than a predetermined length is excluded from grouping because it is a wiring pattern having a small influence of crosstalk because the inter-wiring capacitance is small. Therefore, such a wiring pattern can be assigned to the wiring track in consideration of only the wiring error restriction without considering the wiring track restriction, and the degree of freedom of the wiring pattern assignment can be improved. Thereby, it is possible to easily create a wiring pattern.

また、配線長が所定長以上の配線パターンについては、上述した場合と同様、配線パターンを最適な配線トラックに割り付けることができるため、隣接配線パターン間のクロストークの発生を抑制し、LSIの性能の向上を図ることができる。したがって、後工程での配線パターンの修正を防止し、LSIの歩留まりの向上を図ることができる。   Also, for wiring patterns whose wiring length is greater than or equal to a predetermined length, the wiring pattern can be assigned to the optimal wiring track as in the case described above, so that the occurrence of crosstalk between adjacent wiring patterns can be suppressed and the performance of the LSI can be reduced. Can be improved. Therefore, correction of the wiring pattern in a later process can be prevented, and the yield of LSI can be improved.

以上説明したように、配線パターン作成装置200、配線パターン作成方法、および配線パターン作成プログラムによれば、簡単かつ最適な配線パターン処理をおこなうことにより、後工程での配線パターンの修正を防止し、LSIの歩留まりの向上を図ることがで
きるという効果を奏する。
As described above, according to the wiring pattern creation device 200, the wiring pattern creation method, and the wiring pattern creation program, by performing the simple and optimal wiring pattern processing, the correction of the wiring pattern in the subsequent process is prevented, There is an effect that the yield of the LSI can be improved.

なお、本実施の形態で説明した配線パターン作成方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、CD−ROM、MO、DVD等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。   The wiring pattern creation method described in this embodiment can be realized by executing a program prepared in advance on a computer such as a personal computer or a workstation. This program is recorded on a computer-readable recording medium such as a hard disk, a flexible disk, a CD-ROM, an MO, and a DVD, and is executed by being read from the recording medium by the computer. The program may be a transmission medium that can be distributed via a network such as the Internet.

(付記1)配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する集合抽出手段と、
前記集合抽出手段によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得する影響度取得手段と、
前記影響度取得手段によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けるグループ分け手段と、
前記グループ分け手段によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付ける割付手段と、
を備えることを特徴とする配線パターン作成装置。
(Appendix 1) A set extraction means for extracting a set of adjacent wiring patterns from a plurality of wiring patterns wired in parallel on the wiring track;
From the set of wiring patterns extracted by the set extraction means, an influence acquisition means for acquiring the influence degree of crosstalk generated between the wiring patterns;
Grouping means for dividing the set of wiring patterns into a plurality of groups based on the degree of influence obtained by the degree of influence obtaining means;
Allocating means for allocating the wiring patterns in each group divided by the grouping means on the wiring track so that the wiring patterns in the same group are not adjacent to each other;
A wiring pattern creation device comprising:

(付記2)前記影響度取得手段は、
前記各配線パターン間の距離に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することを特徴とする付記1に記載の配線パターン作成装置。
(Supplementary Note 2) The influence degree acquisition means
The wiring pattern creation device according to appendix 1, wherein an influence degree of crosstalk generated between the wiring patterns is acquired based on a distance between the wiring patterns.

(付記3)前記影響度取得手段は、
前記配線パターンどうしの並行配線長に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することを特徴とする付記1または2に記載の配線パターン作成装置。
(Supplementary Note 3) The influence degree acquisition means includes:
The wiring pattern creation device according to appendix 1 or 2, wherein the influence degree of crosstalk generated between the wiring patterns is acquired based on a parallel wiring length between the wiring patterns.

(付記4)前記影響度取得手段は、
前記配線パターンに信号を供給するセルの駆動力に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することを特徴とする付記1〜3のいずれか一つに記載の配線パターン作成装置。
(Supplementary Note 4) The degree of influence acquisition means includes:
The wiring pattern according to any one of appendices 1 to 3, wherein an influence degree of crosstalk generated between the wiring patterns is acquired based on a driving force of a cell that supplies a signal to the wiring pattern. Creation device.

(付記5)前記グループ分け手段は、
異なるグループどうしの配線パターン間におけるクロストークの影響度の総和が最小となるように、前記配線パターンの集合を複数のグループに分けることを特徴とする付記1〜4のいずれか一つに記載の配線パターン作成装置。
(Appendix 5) The grouping means
The set of wiring patterns is divided into a plurality of groups so that the total sum of influences of crosstalk between the wiring patterns of different groups is minimized. Wiring pattern creation device.

(付記6)前記配線パターンの集合の中から、配線長が所定長以上となる配線パターンを抽出する配線パターン抽出手段を備え、
前記グループ分け手段は、
前記配線パターン抽出手段によって抽出された配線パターンの集合を複数のグループにグループ分けすることを特徴とする付記5に記載の配線パターン作成装置。
(Additional remark 6) The wiring pattern extraction means which extracts the wiring pattern from which the wiring length becomes more than predetermined length from the collection of the said wiring patterns is provided,
The grouping means includes
6. The wiring pattern creation device according to appendix 5, wherein a set of wiring patterns extracted by the wiring pattern extraction unit is grouped into a plurality of groups.

(付記7)前記集合抽出手段によって抽出された配線パターンの集合に基づいて、前記配線トラック上に前記各配線パターンを配線する場合に生じる配線エラーの制約に関する情報を取得する配線エラー制約情報取得手段を備え、
前記割付手段は、
前記配線エラー制約情報取得手段によって取得された配線エラーの制約に関する情報に基づいて、前記グループ分け手段によってグループ分けされた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けることを特徴とする付記1〜6のいずれか一つに記載の配線パターン作成装置。
(Supplementary note 7) Wiring error constraint information acquisition means for acquiring information on restrictions on wiring errors that occur when wiring each wiring pattern on the wiring track based on a set of wiring patterns extracted by the set extraction means With
The assigning means is
Based on the information on the wiring error restriction acquired by the wiring error restriction information acquisition means, the wiring patterns in each group grouped by the grouping means are arranged so that the wiring patterns in the same group are not adjacent to each other. The wiring pattern creation device according to any one of appendices 1 to 6, wherein the wiring pattern creation device is assigned on a wiring track.

(付記8)配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する集合抽出工程と、
前記集合抽出工程によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得する影響度取得工程と、
前記影響度取得工程によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けるグループ分け工程と、
前記グループ分け工程によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付ける割付工程と、
を含んだことを特徴とする配線パターン作成方法。
(Supplementary note 8) A set extraction step of extracting a set of adjacent wiring patterns from a plurality of wiring patterns wired in parallel on the wiring track;
From the set of wiring patterns extracted by the set extraction step, an influence level acquisition step of acquiring the degree of influence of crosstalk generated between the wiring patterns;
A grouping step of dividing the set of wiring patterns into a plurality of groups based on the degree of influence obtained by the degree of influence obtaining step;
An allocating step of allocating the wiring patterns in each group divided by the grouping step on the wiring track so that the wiring patterns in the same group are not adjacent to each other;
A method of creating a wiring pattern characterized by comprising:

(付記9)配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出させる集合抽出工程と、
前記集合抽出工程によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得させる影響度取得工程と、
前記影響度取得工程によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けさせるグループ分け工程と、
前記グループ分け工程によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けさせる割付工程と、
をコンピュータに実行させることを特徴とする配線パターン作成プログラム。
(Supplementary note 9) A set extraction step of extracting a set of a series of adjacent wiring patterns from a plurality of wiring patterns wired in parallel on the wiring track;
From the set of wiring patterns extracted by the set extraction step, an influence degree acquisition step of acquiring the influence degree of crosstalk generated between the wiring patterns,
A grouping step for dividing the set of wiring patterns into a plurality of groups based on the degree of influence obtained by the degree of influence obtaining step;
An allocation step of allocating the wiring patterns in each group divided by the grouping step on the wiring track so that the wiring patterns in the same group are not adjacent to each other;
A wiring pattern creation program for causing a computer to execute the above.

(付記10)付記9に記載の配線パターン作成プログラムを記録したコンピュータ読み取り可能な記録媒体。 (Additional remark 10) The computer-readable recording medium which recorded the wiring pattern creation program of Additional remark 9.

以上のように、本発明にかかる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラム、および記録媒体は、LSIなどの半導体装置のレイアウト設計に有用であり、特に、アルミ配線などエッチング法によって配線をおこなう場合の配線設計に適している。   As described above, the wiring pattern creation device, the wiring pattern creation method, the wiring pattern creation program, and the recording medium according to the present invention are useful for the layout design of a semiconductor device such as an LSI. Suitable for wiring design when wiring.

この発明の実施の形態にかかる配線パターン作成装置のハードウェア構成を示すブロック図である。It is a block diagram which shows the hardware constitutions of the wiring pattern production apparatus concerning embodiment of this invention. この発明の実施の形態にかかる配線パターン作成装置の機能的構成を示すブロック図である。It is a block diagram which shows the functional structure of the wiring pattern production apparatus concerning embodiment of this invention. 集合抽出部によって抽出された一連の隣接する配線パターンの集合を示す説明図である。It is explanatory drawing which shows the set of a series of adjacent wiring patterns extracted by the set extraction part. セルの駆動力と配線パターンの対応関係を示す図表である。It is a graph which shows the correspondence of the driving force of a cell, and a wiring pattern. 完全グラフの一例を示す説明図である。It is explanatory drawing which shows an example of a complete graph. グループ分けされたグループの一例を示す説明図である。It is explanatory drawing which shows an example of the group divided into groups. 完全グラフの他の例を示す説明図である。It is explanatory drawing which shows the other example of a complete graph. グループ分けされたグループの他の例を示す説明図である。It is explanatory drawing which shows the other example of the group divided into groups. 配線トラック領域に割り付けられた配線パターンの一例を示す説明図である。It is explanatory drawing which shows an example of the wiring pattern allocated to the wiring track area. 配線トラック領域に割り付けられた配線パターンの他の例を示す説明図である。It is explanatory drawing which shows the other example of the wiring pattern allocated to the wiring track area | region. この発明の実施の形態にかかる配線パターン作成処理手順の一例を示すフローチャートである。It is a flowchart which shows an example of the wiring pattern creation process procedure concerning embodiment of this invention. この発明の実施の形態にかかる配線パターン作成処理手順の他の例を示すフローチャートである。It is a flowchart which shows the other example of the wiring pattern creation process procedure concerning embodiment of this invention. 従来の配線エラーを示す説明図である。It is explanatory drawing which shows the conventional wiring error. 従来のデフェクトによる配線ショートを示す説明図である。It is explanatory drawing which shows the wiring short by the conventional defect.

符号の説明Explanation of symbols

200 配線パターン作成装置
202 集合抽出部
203 影響度取得部
204 グループ分け部
205 割付部
206 配線パターン抽出部
207 配線エラー制約情報取得部

DESCRIPTION OF SYMBOLS 200 Wiring pattern production apparatus 202 Set extraction part 203 Influence degree acquisition part 204 Grouping part 205 Assignment part 206 Wiring pattern extraction part 207 Wiring error constraint information acquisition part

Claims (3)

配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する集合抽出手段と、
前記集合抽出手段によって抽出された配線パターンの集合から、前記各配線パターン間の距離、前記配線パターンどうしの並行配線長、前記配線パターンに信号を供給するセルの駆動力の差の絶対値のうち、当該各配線パターン間の距離を含む2つ以上の組み合わせに基づいて、前記各配線パターン間に生じるクロストークの影響度を取得する影響度取得手段と、
前記影響度取得手段によって取得された影響度に基づいて完全グラフを作成し、作成された完全グラフを用いて、異なるグループどうしの配線パターン間におけるクロストークの影響度の総和が最小となるように、前記配線パターンの集合を複数のグループに分けるグループ分け手段と、
前記グループ分け手段によって分けられた各グループ内の配線パターンを、他のグループ内の配線パターンどうしが隣接するように、前記配線トラック上に割り付ける割付手段と、
を備えることを特徴とする配線パターン作成装置。
A set extraction means for extracting a set of adjacent wiring patterns from a plurality of wiring patterns wired in parallel on the wiring track;
From the set of wiring patterns extracted by the set extraction means , out of the absolute value of the distance between the wiring patterns, the parallel wiring length between the wiring patterns, and the difference in the driving force of the cells supplying signals to the wiring patterns , Based on two or more combinations including the distance between the wiring patterns, an influence acquisition means for acquiring the influence of crosstalk generated between the wiring patterns;
A complete graph is created based on the degree of influence acquired by the degree of influence acquisition means, and the total sum of the degree of influence of crosstalk between the wiring patterns of different groups is minimized by using the created complete graph. Grouping means for dividing the set of wiring patterns into a plurality of groups;
Allocating means for allocating the wiring patterns in each group divided by the grouping means on the wiring track so that the wiring patterns in other groups are adjacent to each other ;
A wiring pattern creation device comprising:
集合抽出手段と、影響度取得手段と、グループ分け手段と、割付手段と、を備えるコンピュータが、
前記集合抽出手段により、配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する集合抽出工程と、
前記影響度取得手段により、前記集合抽出工程によって抽出された配線パターンの集合から、前記各配線パターン間の距離、前記配線パターンどうしの並行配線長、前記配線パターンに信号を供給するセルの駆動力の差の絶対値のうち、当該各配線パターン間の距離を含む2つ以上の組み合わせに基づいて、前記各配線パターン間に生じるクロストークの影響度を取得する影響度取得工程と、
前記グループ分け手段により、前記影響度取得工程によって取得された影響度に基づいて完全グラフを作成し、作成された完全グラフを用いて、異なるグループどうしの配線パターン間におけるクロストークの影響度の総和が最小となるように、前記配線パターンの集合を複数のグループに分けるグループ分け工程と、
前記割付手段により、前記グループ分け工程によって分けられた各グループ内の配線パターンを、他のグループ内の配線パターンどうしが隣接するように、前記配線トラック上に割り付ける割付工程と、
を実行することを特徴とする配線パターン作成方法。
A computer comprising a set extraction means, an influence acquisition means, a grouping means, and an assignment means,
A set extraction step of extracting a set of adjacent wiring patterns from a plurality of wiring patterns wired in parallel on the wiring track by the set extraction means;
From the set of wiring patterns extracted by the set extraction step by the influence acquisition means, the distance between the wiring patterns, the parallel wiring length between the wiring patterns, and the driving force of the cells supplying signals to the wiring patterns An influence degree obtaining step of obtaining an influence degree of crosstalk generated between the wiring patterns based on a combination of two or more including a distance between the wiring patterns among the absolute values of the differences between the wiring patterns;
A complete graph is created by the grouping means based on the degree of influence acquired by the influence degree acquisition step, and the total sum of the degree of influence of crosstalk between the wiring patterns of different groups is created using the created complete graph. A grouping step of dividing the set of wiring patterns into a plurality of groups so that the
An allocating step of allocating the wiring patterns in each group divided by the grouping step on the wiring track by the allocating means so that the wiring patterns in other groups are adjacent to each other ;
A method of creating a wiring pattern, characterized in that
配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出させる集合抽出工程と、
前記集合抽出工程によって抽出された配線パターンの集合から、前記各配線パターン間の距離、前記配線パターンどうしの並行配線長、前記配線パターンに信号を供給するセルの駆動力の差の絶対値のうち、当該各配線パターン間の距離を含む2つ以上の組み合わせに基づいて、前記各配線パターン間に生じるクロストークの影響度を取得させる影響度取得工程と、
前記影響度取得工程によって取得された影響度に基づいて完全グラフを作成し、作成された完全グラフを用いて、異なるグループどうしの配線パターン間におけるクロストークの影響度の総和が最小となるように、前記配線パターンの集合を複数のグループに分けさせるグループ分け工程と、
前記グループ分け工程によって分けられた各グループ内の配線パターンを、他のグループ内の配線パターンどうしが隣接するように、前記配線トラック上に割り付けさせる割付工程と、
をコンピュータに実行させることを特徴とする配線パターン作成プログラム。

A set extraction process for extracting a set of adjacent wiring patterns from a plurality of wiring patterns wired in parallel on the wiring track;
From the set of wiring patterns extracted by the set extraction step , out of the absolute value of the distance between the wiring patterns, the parallel wiring length between the wiring patterns, and the difference in the driving force of the cells supplying signals to the wiring patterns , Based on two or more combinations including the distance between the wiring patterns, an influence acquisition step of acquiring the influence of crosstalk generated between the wiring patterns;
Create a complete graph based on the impact level acquired by the impact level acquisition step, and use the created complete graph so that the sum of the impact levels of crosstalk between the wiring patterns of different groups is minimized. A grouping step for dividing the set of wiring patterns into a plurality of groups;
An allocation step of allocating the wiring patterns in each group divided by the grouping step on the wiring track so that the wiring patterns in other groups are adjacent to each other ;
A wiring pattern creation program characterized by causing a computer to execute.

JP2004210397A 2004-07-16 2004-07-16 Wiring pattern creation device, wiring pattern creation method, wiring pattern creation program, and recording medium Expired - Fee Related JP4511888B2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2004210397A JP4511888B2 (en) 2004-07-16 2004-07-16 Wiring pattern creation device, wiring pattern creation method, wiring pattern creation program, and recording medium

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2004210397A JP4511888B2 (en) 2004-07-16 2004-07-16 Wiring pattern creation device, wiring pattern creation method, wiring pattern creation program, and recording medium

Publications (2)

Publication Number Publication Date
JP2006031468A JP2006031468A (en) 2006-02-02
JP4511888B2 true JP4511888B2 (en) 2010-07-28

Family

ID=35897722

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2004210397A Expired - Fee Related JP4511888B2 (en) 2004-07-16 2004-07-16 Wiring pattern creation device, wiring pattern creation method, wiring pattern creation program, and recording medium

Country Status (1)

Country Link
JP (1) JP4511888B2 (en)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP5098688B2 (en) * 2008-02-18 2012-12-12 富士通株式会社 Design support program, recording medium storing the program, design support apparatus, and design support method

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08101854A (en) * 1994-09-30 1996-04-16 Nec Corp Method for wiring design of integrated circuit
JP2002259480A (en) * 2001-03-02 2002-09-13 Matsushita Electric Ind Co Ltd Method for avoiding crosstalk
JP2003308351A (en) * 2002-04-18 2003-10-31 Matsushita Electric Ind Co Ltd Method for lay-out design of semiconductor integrated circuit
JP2004133638A (en) * 2002-10-10 2004-04-30 Matsushita Electric Ind Co Ltd Method for designing semiconductor integrated circuit

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08101854A (en) * 1994-09-30 1996-04-16 Nec Corp Method for wiring design of integrated circuit
JP2002259480A (en) * 2001-03-02 2002-09-13 Matsushita Electric Ind Co Ltd Method for avoiding crosstalk
JP2003308351A (en) * 2002-04-18 2003-10-31 Matsushita Electric Ind Co Ltd Method for lay-out design of semiconductor integrated circuit
JP2004133638A (en) * 2002-10-10 2004-04-30 Matsushita Electric Ind Co Ltd Method for designing semiconductor integrated circuit

Also Published As

Publication number Publication date
JP2006031468A (en) 2006-02-02

Similar Documents

Publication Publication Date Title
US7765507B2 (en) Design support method, design support apparatus, computer product
US6601222B1 (en) Coupled noise estimation and avoidance of noise-failure using global routing information
TWI598758B (en) Method, device and computer program product for integrated circuit layout generation
JP4501728B2 (en) Crosstalk error control device, crosstalk error control method, and crosstalk error control program
US7367005B2 (en) Method and apparatus for designing a layout, and computer product
JP4511888B2 (en) Wiring pattern creation device, wiring pattern creation method, wiring pattern creation program, and recording medium
JP4723987B2 (en) Failure detection rate calculation device, failure detection rate calculation method, and failure detection method
JP2007264993A (en) Verification support apparatus, verification support method, verification support program and recording medium
US6487707B1 (en) Layout design system of semiconductor ic device, layout design method of semiconductor ic device and computer-readable recording medium on which programs for allowing computer to execute respective means in the system or respective steps in the method are recorded
JP5267327B2 (en) Design support program, design support apparatus, and design support method
US20080209368A1 (en) Layout design method, layout design apparatus, and computer product
JP2008009787A (en) Hierarchical design layout device, hierarchical design layout method, hierarchical design layout program, and recording medium recording the program
JP5239766B2 (en) Layout design method
JP2009076679A (en) Design support program, computer-readable recording medium with the same recorded therein, design support device, and design support method
JP4676911B2 (en) Crosstalk analysis program, recording medium, crosstalk analysis method, and crosstalk analysis apparatus
US7673266B2 (en) Timing analysis method and apparatus, computer-readable program and computer-readable storage medium
JP2006085635A (en) Timing analysis device, timing analysis method, timing analysis program and recording medium
JP2005309624A (en) Layout design device, method, and program, and recording medium
JP2011039757A (en) Design support program, design support apparatus, and design support method
CN113011124B (en) Crosstalk optimization method and device for layout wiring and readable storage medium
JP4783712B2 (en) Layout design method, layout design program, and layout design apparatus
US6701503B2 (en) Overlap remover manager
JP2006344165A (en) Layout design device, layout design method, layout design program and recording medium
JP2010211315A (en) Layout verification method and layout verification device
JP2010231631A (en) Designing support program, designing support device, and designing support method

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20061127

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20090519

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20090721

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20090929

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20091225

A911 Transfer to examiner for re-examination before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A911

Effective date: 20100113

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20100202

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20100405

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20100427

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20100507

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130514

Year of fee payment: 3

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130514

Year of fee payment: 3

LAPS Cancellation because of no payment of annual fees