(57)【要約】  本発明は二進コードによるデジタル集積回路の配線方法および端末装置を提供する。前記方法は、所定の数量の第一接続方式を確定し、各接続線に対応する配線サブ空間により各第一接続方式の第一フィットネス函数値を計算し、各第一フィットネス函数値によって各第一接続方式に対して処理をすることにより各第二接続方式を獲得するステップと、第一接続方式と第二接続方式の合併によって形成された集合において第一数量の第三接続方式を選択し、各第三接続方式の第二フィットネス函数値をそれぞれ計算するステップと、計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップとを含む。本発明は、均等なグリッドの二進コードを採用することにより、非グリッド中のコードの長さが異なる問題を避け、オプティマイゼーションスペースの範囲を減小させ、配線の効率を向上させることができる。
2021532605.tif 000002
【特許請求の範囲】
【請求項１】
二進コードによるデジタル集積回路の配線方法であって、前記デジタル集積回路は、複数個のスタンダードセルが配置される基板を含み、前記基板は複数個の接続線を含み、前記二進コードによるデジタル集積回路の配線方法は、
所定の数量のバイナリーベクトルを形成し、形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成するステップと、
各接続線に対応する配線サブ空間により第一接続方式のパスコストベクトルを計算するステップと、
各パスコストベクトルにより各第一接続方式の第一フィットネス函数値を計算し、各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより各第二接続方式を獲得するステップと、
第一接続方式と第二接続方式の合併によって形成された集合において第一数量の第三接続方式を選択し、各第三接続方式の第二フィットネス函数値をそれぞれ計算するステップと、
計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップとを含むことを特徴とする二進コードによるデジタル集積回路の配線方法。
【請求項２】
所定の数量のバイナリーベクトルを形成し、形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成するステップは具体的に、
各接続線に対応する配線サブ空間の第一次元を獲得するステップと、
獲得したすべての第一次元により第二次元を計算し、前記第二次元により所定の数量のバイナリーベクトルを形成するステップと、
形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成するステップであって、前記バイナリーベクトルの次元は第二次元であるステップとを含むことを特徴とする請求項１に記載の二進コードによるデジタル集積回路の配線方法。
【請求項３】
各接続線に対応する配線サブ空間により第一接続方式のパスコストベクトルを計算するステップは具体的に、
各接続線に対応する配線サブ空間の第一次元を獲得するステップと、
各接続線に対応する第一次元により各第一接続方式を複数のサブベクトルに分けるステップと、
各サブベクトル中のコード１に対応するグリッド交差点によりグリッド交差点集合を形成し、各グリッド交差点集合によりそれらに対応するサブベクトルのパス長を確定し、各パス長によりパスコストベクトルを形成するステップとを含むことを特徴とする請求項１に記載の二進コードによるデジタル集積回路の配線方法。
【請求項４】
前記各接続線に対応する配線サブ空間の第一次元を獲得する前、
前記基板上の各ピンの位置情報を獲得し、かつ獲得したすべての位置情報により前記基板を複数個のグリッドに分けるステップと、
各接続線によって接続される２つのピンに対応するグリッド交差点を獲得し、かつ獲得したグリッド交差点により各接続線のバイナリーベクトルを確定し、各バイナリーベクトルにより各接続線に対応する配線サブ空間を確定するステップとを含むことを特徴とする請求項２または３に記載の二進コードによるデジタル集積回路の配線方法。
【請求項５】
前記各パスコストベクトルにより各第一接続方式の第一フィットネス函数値を計算し、前記各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより各第二接続方式を獲得するステップは具体的に、
各パスコストベクトルにおいて、各次元のパスコストがすべてのパスコストベクトルに対応する次元のパスコスト中のパスコストのシーケンス値を計算するステップと、
各次元のパスコストのシーケンス値によりパスコストのシーケンスベクトルを形成し、かつ各前記パスコストのシーケンスベクトルにより各第一接続方式の第一フィットネス函数値を計算するステップと、
各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより各第二接続方式を獲得するステップとを含むことを特徴とする請求項１に記載の二進コードによるデジタル集積回路の配線方法。
【請求項６】
計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップは具体的に、
計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択するステップと、
前記最適な接続方式中の各接続線の最短グリッドパスを計算し、かつ最短グリッドパスによりスタンダードセルのピンを接続させるステップとを含むことを特徴とする請求項１に記載の二進コードによるデジタル集積回路の配線方法。
【請求項７】
計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップは具体的に、
前記第三接続方式に対応するイテレーション回数を獲得し、かつ前記イテレーション回数と予め設定されるイテレーション回数を比較するステップと、
前記イテレーション回数と予め設定されるイテレーション回数が等しいとき、計算により獲得したすべての第二フィットネス函数値により第三接続方式中の最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップとを含むことを特徴とする請求項１に記載の二進コードによるデジタル集積回路の配線方法。
【請求項８】
前記イテレーション回数が予め設定されるイテレーション回数より小さいとき、前記第三接続方式を第一接続方式にし、かつ第一接続方式を形成するステップに戻った後イテレーション回数が予め設定されるイテレーション回数に達するときまでそのステップを繰り返すことを特徴とする請求項７に記載の二進コードによるデジタル集積回路の配線方法。
【請求項９】
コンピュータ読み取り可能な記憶媒体であって、前記コンピュータ読み取り可能な記憶媒体は１個または複数個のプログラムを記憶させ、前記１個または複数個のプログラムが１個または複数個のプロセッサーによって実行されることにより、請求項１〜８のうちいずれか１つに記載の二進コードによるデジタル集積回路の配線方法中のステップを実施することを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１０】
端末装置であって、プロセッサー、メモリおよびバスを含み、前記メモリにはプロセッサーによって実施されることができるコンピュータ読み取り可能なプログラムが記憶され、
前記バスはプロセッサーとメモリとの間の通信を担当し、
前記プロセッサーはコンピュータ読み取り可能なプログラムを実行することにより請求項１〜８のうちいずれか１つに記載の二進コードによるデジタル集積回路の配線方法中のステップを実施することを特徴とする端末装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル集積回路の技術分野に属し、特に、二進コードによるデジタル集積回路の配線方法および端末装置に関するものである。
【背景技術】
【０００２】
デジタル集積回路（integrated  circuit、ＩＣ）をチップともいい、それは半導体技術によるマイクロエレクトロニクスデバイス（microelectronic  device）である。現在のデジタル集積回路は通常、図１に示されたスタンダードセル（Standard  Cell）で構成されるものである。スタンダードセルは所定の機能を具備する回路モジュールであり、例えばトリガー（trigger）、ゲート回路（gate  circuit）、加算装置（Adder）、バッファー（buffer）、レジスター（register）、ＲＡＭメモリユニット等を含む。デジタル集積回路の設計において、接続線の配線率（Routability）等によりスタンダードセルの位置を決定する。次に、スタンダードセルの位置、入力出力ピンおよびネットリスト（netlist）情報により配線の位置を決定する。それによりデジタル集積回路のネットワークラジエーション（Network  radiation）を確保する前提下において接続線の全長を最短にすることができる。
【０００３】
しかしながら、従来のデジタル集積回路においてスタンダードセルを配置させた後それらを接続させるとき通常、引き出し方法により配線を設計する。例えば粒子スワームの最適化、アリコロニーアルゴリズム（Ant  Colony  Algorithm）等により配線を設計する。しかしながら、ＩＣ配線は大規模でありかつ複雑な好適化過程であるので、従来の引き出し方法により容易に処理することができないので、配線の効率が低下するおそれがある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の技術の技術的問題を解決するため、本発明の旨は二進コードによるデジタル集積回路の配線方法および端末装置を提供することにある。
【課題を解決するための手段】
【０００５】
本発明の技術的事項は下記のとおりである。
【０００６】
二進コードによるデジタル集積回路の配線方法であって、前記デジタル集積回路は、複数個のスタンダードセルが配置される基板を含み、前記基板は複数個の接続線を含み、前記二進コードによるデジタル集積回路の配線方法は、
所定の数量のバイナリーベクトルを形成し、形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成するステップと、
各接続線に対応する配線サブ空間により第一接続方式のパスコストベクトルを計算するステップと、
各パスコストベクトルにより各第一接続方式の第一フィットネス函数値を計算し、各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより各第二接続方式を獲得するステップと、
第一接続方式と第二接続方式の合併によって形成された集合において第一数量の第三接続方式を選択し、各第三接続方式の第二フィットネス函数値をそれぞれ計算するステップと、
計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップとを含む。
【０００７】
前記二進コードによるデジタル集積回路の配線方法において、所定の数量のバイナリーベクトルを形成し、形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成するステップは具体的に、
各接続線に対応する配線サブ空間の第一次元を獲得するステップと、
獲得したすべての第一次元により第二次元を計算し、前記第二次元により所定の数量のバイナリーベクトルを形成するステップと、
形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成するステップであって、前記バイナリーベクトルの次元は第二次元であるステップとを含む。
【０００８】
前記二進コードによるデジタル集積回路の配線方法において、各接続線に対応する配線サブ空間により第一接続方式のパスコストベクトルを計算するステップは具体的に、
各接続線に対応する配線サブ空間の第一次元を獲得するステップと、
各接続線に対応する第一次元により各第一接続方式を複数のサブベクトルに分けるステップと、
各サブベクトル中のコード１に対応するグリッド交差点によりグリッド交差点集合を形成し、各グリッド交差点集合によりそれらに対応するサブベクトルのパス長を確定し、各パス長によりパスコストベクトルを形成するステップとを含む。
【０００９】
前記二進コードによるデジタル集積回路の配線方法において、前記各接続線に対応する配線サブ空間の第一次元を獲得する前、
前記基板上の各ピンの位置情報を獲得し、かつ獲得したすべての位置情報により前記基板を複数個のグリッドに分けるステップと、
各接続線によって接続される２つのピンに対応するグリッド交差点を獲得し、かつ獲得したグリッド交差点により各接続線のバイナリーベクトルを確定し、各バイナリーベクトルにより各接続線に対応する配線サブ空間を確定するステップとを含む。
【００１０】
前記二進コードによるデジタル集積回路の配線方法において、前記各パスコストベクトルにより各第一接続方式の第一フィットネス函数値を計算し、前記各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより各第二接続方式を獲得するステップは具体的に、
各パスコストベクトルにおいて、各次元のパスコストがすべてのパスコストベクトルに対応する次元のパスコスト中のパスコストのシーケンス値を計算するステップと、
各次元のパスコストのシーケンス値によりパスコストのシーケンスベクトルを形成し、かつ各前記パスコストのシーケンスベクトルにより各第一接続方式の第一フィットネス函数値を計算するステップと、
各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより各第二接続方式を獲得するステップとを含む。
【００１１】
前記二進コードによるデジタル集積回路の配線方法において、計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップは具体的に、
計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択するステップと、
前記最適な接続方式中の各接続線の最短グリッドパスを計算し、かつ最短グリッドパスによりスタンダードセルのピンを接続させるステップとを含む。
【００１２】
前記二進コードによるデジタル集積回路の配線方法において、計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップは具体的に、
前記第三接続方式に対応するイテレーション回数を獲得し、かつ前記イテレーション回数と予め設定されるイテレーション回数を比較するステップと、
前記イテレーション回数と予め設定されるイテレーション回数が等しいとき、計算により獲得したすべての第二フィットネス函数値により第三接続方式中の最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップとを含む。
【００１３】
前記二進コードによるデジタル集積回路の配線方法において、前記イテレーション回数が予め設定されるイテレーション回数より小さいとき、前記第三接続方式を第一接続方式にし、かつ第一接続方式を形成するステップに戻った後イテレーション回数が予め設定されるイテレーション回数に達するときまでそのステップを繰り返す。
【００１４】
コンピュータ読み取り可能な記憶媒体であって、前記コンピュータ読み取り可能な記憶媒体は１個または複数個のプログラムを記憶させ、前記１個または複数個のプログラムが１個または複数個のプロセッサーによって実行されることにより、前記二進コードによるデジタル集積回路の配線方法中のステップを実施する。
【００１５】
前記端末装置であって、プロセッサー、メモリおよびバスを含み、前記メモリにはプロセッサーによって実施されることができるコンピュータ読み取り可能なプログラムが記憶され、
前記バスはプロセッサーとメモリとの間の通信を担当し、
前記プロセッサーはコンピュータ読み取り可能なプログラムを実行することにより前記二進コードによるデジタル集積回路の配線方法中のステップを実施する。
【発明の効果】
【００１６】
従来の技術と比較してみると、本発明の二進コードによるデジタル集積回路の配線方法および端末装置により下記発明の効果を奏することができる。前記二進コードによるデジタル集積回路の配線方法は、所定の数量の第一接続方式を確定し、各接続線に対応する配線サブ空間により各第一接続方式の第一フィットネス函数値を計算し、各第一フィットネス函数値によって各第一接続方式に対して処理をすることにより各第二接続方式を獲得するステップと、第一接続方式と第二接続方式の合併によって形成された集合において第一数量の第三接続方式を選択し、各第三接続方式の第二フィットネス函数値をそれぞれ計算するステップと、計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップとを含む。本発明は、均等なグリッドの二進コードを採用することにより、非グリッド中のコードの長さが異なる問題を避け、オプティマイゼーションスペース（Optimization  space）の範囲を減少させ、配線の効率を向上させることができる。
【図面の簡単な説明】
【００１７】
【図１】デジタル集積回路のスタンダードセルの配置を示す図である。
【図２】本発明の二進コードによるデジタル集積回路の配線方法を示す流れ図である。
【図３】本発明の二進コードによるデジタル集積回路の配線方法を示す他の流れ図である。
【図４】本発明の二進コードによるデジタル集積回路の配線方法において配線路線を確定することを示す流れ図である。
【図５】本発明の自己起動制御システム（端末装置に対応する）の好適な実施例の構造を示す原理図である。
【発明を実施するための形態】
【００１８】
本発明は二進コードによるデジタル集積回路の配線方法および端末装置を提供する。本発明の目的、技術的特徴および発明の効果を詳細に明確に理解してもらうため、以下、図面により本発明の実施例をより詳細に説明する。下記具体的な実施例は本発明を説明するものであるが、本発明を限定するものでない。
【００１９】
本発明の明細書において、特別な説明がない限り、この明細書中の「１つ」、「１個」、「前記」および「該」等の用語は、１つの事項を含むだけでなく、複数の事項を含むこともできる。本発明の明細書中の「含む」という用語は、特徴、整数、ステップ、操作、部品と／或いはモジュールを含むことを意味するが、１個または複数個の特徴、整数、ステップ、操作、部品と／或いはモジュールの組合せが存在するか或いはそれらの組合せを更に含むことを意味することもできる。注意されたいことは、部品が他の部品に「連結」または「接続」されるとき、その部品は他の部品に直接に連結または接続されるか或いは中間部品により他の部品に間接的に連結または接続されることができる。この明細書中の「連結」または「接続」は無線連結または無線接続であることができる。この明細書中の「と／或いは」という用語は、係っている１個または複数個の事項のうちいずれかの１つまたは複数、いずれかの組合せまたは全部を含むことを意味することができる。
【００２０】
本発明の明細書において、特別な説明がない限り、この明細書中の用語（技術的用語と科学的用語を含む）はこの技術分野の技術者が常用している用語の意味を指す。注意されたいことは、本発明と従来の技術中の用語は、辞書に記載されている用語の意味を参照することができるが、特別な定義がある場合、特別に定義される意味を指すことができる。
【００２１】
以下、図面と具体的な実施例により本発明の技術的特徴をより詳細に説明する。
【００２２】
本発明の実施例において二進コードによるデジタル集積回路の配線方法を提供する。図２〜図４に示されるとおり、前記方法は下記ステップを含む。
【００２３】
ステップＳ１０において、所定の数量のバイナリーベクトルを形成し、形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成する。
【００２４】
前記バイナリーベクトルはランダムに形成されるものであり、前記バイナリーベクトルをＳｉと表記し、前記Ｓｉ中の各元素は０と１によりランダムに形成されるものである。すなわち前記Ｓｉは０と１によりランダムに形成される第二次元のベクトルである。前記Ｓｉの次元デジタル集積回路はスタンダードセルが配置された後に形成されるデジタル集積回路の各配置サブ空間の第一次元の次元の総計であり、それを第二次元だと表記する。各配置サブ空間は各接続線に対応する配線可能な区間である。本実施例において、所定の数量の第一接続方式は最初進化ポピュレーションｐｓ＝｛Ｓ１,Ｓ２,...,Ｓｐｓ｝を構成する。
【００２５】
本発明の実施例において、所定の数量のバイナリーベクトルを形成し、形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成するステップは具体的に下記ステップを含む。
【００２６】
各接続線に対応する配線サブ空間の第一次元を獲得する。
【００２７】
獲得したすべての第一次元により第二次元を計算し、前記第二次元により所定の数量のバイナリーベクトルを形成する。
【００２８】
形成された所定の数量のバイナリーベクトルにより所定の数量の第一接続方式を形成し、前記バイナリーベクトルの次元は第二次元である。
【００２９】
前記デジタル集積回路は、基板、複数個のスタンダードセルおよび複数個の接続線を含み、前記複数個のスタンダードセルは前記基板上に配置される。すなわち本発明はスタンダードセルが配置されているデジタル集積回路に用いられる。基板上にスタンダードセルを配置した後、接続線によりデジタル集積回路上の各ピンを接続させる。前記ピンはスタンダードセルの部品ピンと基板上のポートピンを含む。デジタル集積回路上のピン集合をＰ＝｛ｐ１,ｐ２,...,ｐｍ｝だと表記し、その式においてｍはピンの個数であり、ｍは整数倍である。複数個の接続線の集合をＥ＝｛ｅ１,ｅ２,...,ｅｎ｝だと表記し、その式においてｎは接続線の本数であり、ｎは整数倍である。前記Ｅ中の各接続線はＰ中の２つのピンを接続させる。スタンダードセルが配置されるデジタル集積回路の配線問題は、配線が可能なチップ空間内において接続線全長ＴＷＬを最小にすることである。ＴＷＬの計算式は下記のとおりである。
【００３０】
【数１】
2021532605.tif 000003
【００３１】
前記
【数２】
2021532605.tif 000004
はｅｉの長さである。
【００３２】
ｅｉの長さを算出するため、スタンダードセルが配置されるデジタル集積回路において基板を複数個のグリッドに分ける必要がある。前記各接続線に対応する配線サブ空間の第一次元を獲得する前に下記ステップを更に実施する。
【００３３】
前記基板上の各ピンの位置情報を獲得し、かつ獲得したすべての位置情報により前記基板を複数個のグリッドに分ける。
【００３４】
各接続線によって接続される２つのピンに対応するグリッド交差点を獲得し、かつ獲得したグリッド交差点により各接続線のバイナリーベクトルを確定し、各バイナリーベクトルにより各接続線に対応する配線サブ空間を確定する。
【００３５】
具体的に、前記位置情報は各ピンが予め設定される座標中に位置している座標点を指す。位置情報を獲得した後、各位置情報によりＰ中の任意の２つのピンを連結させる横座標距離とＰ中の任意の２つのピンを連結させる縦座標距離を算出し、かつ横座標距離と縦座標距離の最大公約数（Highest  common  factor、ＨＣＦ）をそれぞれ算出する。横座標距離の最大公約数をグリッドの幅ｗにし、横座標距離の最大公約数をグリッドの高さｈにする。前記横座標距離と横座標距離は前記基板上に形成される座標中の座標である。例えば、前記基板の左下コーナー（left  lower  corner）に位置する原点、右へ延伸する横方向軸および上へ延伸する横方向軸により形成される座標中の座標であることができる。本実施例において、前記グリッドの幅とグリッドの高さの計算式は下記のとおりである。
【００３６】
【数３】
2021532605.tif 000005
【００３７】
この式において、ｅｉ,ｊはＥ中の接続ピンｐｉとｐｊの間の接続線である。
【００３８】
前記グリッドの幅ｗとグリッドの高さｈを算出した後、基板を幅と高さがｗ×ｈである複数個のグリッドに分ける。その場合、各ピンはいずれもグリッドの交差点に位置する。Ｅ中の任意の接続線において、その接続線によって接続されるピンが位置しているグリッド位置の座標点により、接続線に対応する配線サブ空間の第一次元を確定する。その場合、ピンｐｉとｐｊを接続させる接続線をｅｉ,ｊだと表記する。ｅｉ,ｊに対応する配線サブ空間はピンｐｉとｐｊの座標点により確定される。具体的な過程は下記のとおりである。ピンｐｉとｐｊの座標点｛ｘｉ,ｙｉ｝と｛ｘｊ,ｙｊ｝を獲得し、座標点｛ｘｉ,ｙｉ｝と｛ｘｊ,ｙｊ｝により座標点｛ｘｉ,ｙｊ｝と｛ｘｊ,ｙｉ｝を獲得し、座標点｛ｘｉ,ｙｉ｝、｛ｘｊ,ｙｊ｝、｛ｘｉ,ｙｊ｝および｛ｘｊ,ｙｉ｝の頂部の矩形区域をｅｉ,ｊの配線サブ空間にする。有効グリッド交差点はスタンダードセルに覆われないグリッド交差点を指す。
【００３９】
ｅｉ,ｊの配線サブ空間を獲得した後、ｅｉ,ｊの配線サブ空間に含まれている有効グリッド交差点を検出する。検出される有効グリッド交差点の番号を１、２、．．．ｋだと表記し、ｅｉ,ｊの配線コードをｋ次元バイナリーベクトルＣｉ,ｊ＝（ｃ１,ｃ２,...,ｃｋ）だと表記する。任意のｌ∈ｋにおいて、ｃｌ＝１はｅｉ,ｊ配線がグリッド交差点ｌを通過することを意味し、ｃｌ＝０はｅｉ,ｊ配線がグリッド交差点ｌを通過しないことを意味する。その場合、接続線ｅｉ,ｊの配線サブ空間の第一次元はｋであり、第二次元は第一次元の合計と同様である。すなわち第二次元は
【数４】
2021532605.tif 000006
である。
【００４０】
ステップＳ２０において、各接続線に対応する配線サブ空間により第一接続方式のパスコストベクトル（Path  cost  vector）を計算する。
【００４１】
前記パスコストベクトルの次元は第三次元であり、前記第三次元は接続線の数量ｎと等しい。すなわち前記パスコストベクトルはｎ次元ベクトルである。前記パスコストベクトルを各接続線の配線サブ空間の次元によって分割することにより複数のサブベクトルを獲得し、分割によって獲得した複数のサブベクトルにより前記パスコストベクトルを獲得する。すなわち、各第一接続方式に対応するパスコストベクトルを計算するとき、各パスコストベクトルを分割する必要がある。各接続線に対応する配線サブ空間により第一接続方式のパスコストベクトルを計算するステップは具体的に下記ステップを含む。
【００４２】
ステップＳ２１において、各接続線に対応する配線サブ空間の第一次元を獲得する。
【００４３】
ステップＳ２２において、各接続線に対応する第一次元により各第一接続方式を複数のサブベクトルに分ける。
【００４４】
ステップＳ２３において、各サブベクトル中のコード１に対応するグリッド交差点によりグリッド交差点集合を形成し、各グリッド交差点集合によりそれらに対応するサブベクトルのパス長（Path  length）を確定し、各パス長によりパスコストベクトルを形成する。
【００４５】
第一次元を獲得した後、各第一次元により第一接続方式を複数のサブベクトルに分けることによりＳｉ＝｛Ｃ１｜Ｃ２｜...｜Ｃｎ｝を獲得する。前記｛Ｃ１｜Ｃ２｜...｜Ｃｎ｝中の各サブベクトルの次元と各接続線の配線サブ空間の次元は１つずつ対応する。すなわち
【数５】
2021532605.tif 000007
である。その式において、ｋｌは接続線ｅｌの配線サブ空間の次元である。サブベクトルを獲得した後、各サブベクトルＣｌ＝｛Ｃ１,Ｃ２,...,Ｃｋｌ｝はｋｌの各グリッド交差点を含み、Ｃｌ＝｛Ｃ１,Ｃ２,...,Ｃｋｌ｝中の二進コードが１である交差点を検出することにより交差点集合Ｖ＝｛ｖｉ＝ｉ,∀ｉ∈ｋｌ,ｃｉ＝１｝を獲得する。
【００４６】
交差点集合Ｖ＝｛ｖｉ＝ｉ,∀ｉ∈ｋｌ,ｃｉ＝１｝を獲得した後、前記交差点集合中の各交差点を通過するグリッドパスの最小値を計算し、前記グリッドパスの最小値をサブベクトルのパス長
【数６】
2021532605.tif 000008
だと表記する。グリッドパスの最小値は線形プログラミング等の従来の計算方法により算出することができるが、ここでは再び説明しない。各サブベクトルのパス長を獲得した後、獲得した各パス長によりＳｉのパスコストベクトルを計算する。前記ＳｉのパスコストベクトルはＦｉ＝｛ｆｉ,１,ｆｉ,２,...,ｆｉ,ｎ｝であり、
【数７】
2021532605.tif 000009
はＣｌに対するＳｉのパスコストである。
【００４７】
ステップＳ３０において、各パスコストベクトルにより各第一接続方式の第一フィットネス函数値（Fitness  Function  value）を計算し、各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズム（binary  strings  genetic  algorithm）を採用して各第一接続方式を処理することにより各第二接続方式を獲得する。
【００４８】
前記第一フィットネス函数値は各パスコストベクトルにより算出してえたものである。第一フィットネス函数値を獲得した後、前記第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより第二接続方式を獲得する。すなわち最初ポピュレーション（population）に対して最適化を実施することにより最適化ポピュレーションを獲得する。前記バイナリストリング遺伝的アルゴリズムにより最初ポピュレーションに対して実施する処理は、最初ポピュレーションに対して交差、変異操作をすることにより最適化ポピュレーションを獲得することである。前記最適化ポピュレーションの個体の数量と最初ポピュレーションの個体の数量は等しいことができる。注意されたいことは、前記交差、変異操作として従来の技術を採用することができるので、ここではそれを再び説明しない。
【００４９】
本発明の実施例において、前記各パスコストベクトルにより各第一接続方式の第一フィットネス函数値を計算し、前記各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより各第二接続方式を獲得するステップは具体的に下記ステップを含む。
【００５０】
ステップＳ３１において、各パスコストベクトルにおいて、各次元のパスコストがすべてのパスコストベクトルに対応する次元のパスコスト中のパスコストのシーケンス値（sequence  value）を計算する。具体的に、各パスコストベクトルの各次元のパスコストを獲得しかつパスコストを配列させることにより、その次元の各パスコストベクトルのパスコストのシーケンス値を計算する。次に、そのステップを各次元において実施することにより、その次元の各パスコストベクトルのパスコストのシーケンス値を把握することができる。
【００５１】
ステップＳ３２において、各次元のパスコストのシーケンス値によりパスコストのシーケンスベクトルを形成し、かつ各前記パスコストのシーケンスベクトルにより各第一接続方式の第一フィットネス函数値を計算する。
【００５２】
ステップＳ３３において、各第一フィットネス函数値とバイナリストリング遺伝的アルゴリズムを採用して各第一接続方式を処理することにより各第二接続方式を獲得する。
【００５３】
任意のパスコストベクトルＦｉ＝｛ｆｉ,１,ｆｉ,２,...,ｆｉ,ｎ｝において、そのパスコストベクトルがすべてのパスベクトル中の第一次元上に位置するコストシーケンス値を獲得する。すなわち、任意のパスコストベクトルＡにおいて、そのパスコストベクトルの第一次元上のパスコストを獲得した後、他のすべてのパスコストベクトルが第一次元上に位置するパスコストを獲得し、かつ獲得したすべてのパスコストをシークエンシングさせることによりパスコストベクトルＡの第一次元上のパスコストが、すべての第一次元上のパスコスト中のシーケンス値を獲得する。第一次元のパスコストのシーケンス値を獲得した後、第二次元のパスコストのシーケンス値を獲得し、それを繰り返すことにより第ｎ次元のパスコストのシーケンス値を獲得する。前記ｎ個のパスコストのシーケンス値によりパスコストのシーケンスベクトルＲｉ＝｛ｒｉ,１,ｒｉ,２,...,ｒｉ,ｎ｝が形成される。その式においてｒｉ,ｌ＝ｒａｎｋ（ｆｉ,ｌ）,ｉ＝１,２,…,｜ｐｓ｜である。パスコストのシーケンスベクトルを獲得した後、前記パスコストのシーケンスベクトルによりそれに対応する第一接続方式の第一フィットネス函数値を計算する。前記第一フィットネス函数値は下記のとおりである。
【００５４】
【数８】
2021532605.tif 000010
【００５５】
ステップＳ４０において、第一接続方式と第二接続方式の合併によって形成された集合において第一数量の第三接続方式を選択し、各第三接続方式の第二フィットネス函数値をそれぞれ計算する。
【００５６】
各第二接続方式を獲得した後、各第二接続方式は進化ポピュレーションｐｓ＊を構成し、各第二接続方式で構成される集合と各第一接続方式で構成される集合を合併させることにより第一接続方式と第二接続方式の合併集合ｐｓｃｏｍｂを形成し、かつ第一接続方式と第二接続方式の合併により形成される集合において第一数量の第三接続方式を選択する。第一数量の第三接続方式を選択した後、前記フィットネス函数値の計算方法により各第三接続方式の第二フィットネス函数値を計算する。
【００５７】
ステップＳ５０において、計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させる。
【００５８】
各第三接続方式の第二フィットネス函数値を計算し、かつ第二フィットネス函数値が小さい第三接続方式を選択して接続方式にすることによりデジタル集積回路のスタンダードセルが配置される接続方式を獲得することができる。しかしながら、実際の応用においてデジタル集積回路の配線最適性（接続線の最短化）を向上させるため、すべての第三接続方式を獲得した後、第三接続方式を第一配置にする最適化ステップを繰り返すことにより最適化の第三接続方式を獲得する。計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップは具体的に下記ステップを含む。
【００５９】
前記第三接続方式に対応するイテレーション回数（iteration  number）を獲得し、かつ前記イテレーション回数と予め設定されるイテレーション回数を比較する。
【００６０】
前記イテレーション回数と予め設定されるイテレーション回数が等しいとき、計算により獲得したすべての第二フィットネス函数値により第三接続方式中の最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させる。
【００６１】
前記イテレーション回数が予め設定されるイテレーション回数より小さいとき、前記第三接続方式を第一接続方式にし、かつ第一接続方式を形成するステップに戻った後イテレーション回数が予め設定されるイテレーション回数に達するときまでそのステップを繰り返す。
【００６２】
前記予め設定されるイテレーション回数Ｇは予め設定される値である。例えば前記予め設定されるイテレーション回数は５０等であることができる。イテレーション回数が予め設定されるイテレーション回数に達し、最適の第三接続方式を選択した後、第三接続方式の最短パスを再び計算し、第三接続方式中の各接続線が所定の最短パスに設けられるように制御する。計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択し、かつ前記最適な接続方式によりスタンダードセルのピンを接続させるステップは具体的に下記ステップを含む。計算により獲得したすべての第二フィットネス函数値によりすべての第三接続方式において最適な接続方式を選択する。前記最適な接続方式中の各接続線の最短グリッドパスを計算し、かつ最短グリッドパスによりスタンダードセルのピンを接続させる。最短グリッドパスの計算方法は配線の最適化構造中の最短パスの計算方法と同様である。
【００６３】
前記二進コードによるデジタル集積回路の配線方法により本発明はコンピュータ読み取り可能な記憶媒体を更に提供する。前記コンピュータ読み取り可能な記憶媒体は１個または複数個のプログラムを記憶させ、前記１個または複数個のプログラムが１個または複数個のプロセッサーにより実行されることにより、本発明の前記実施例に係る二進コードによるデジタル集積回路の配線方法中のステップを実施することができる。
【００６４】
前記二進コードによるデジタル集積回路の配線方法により本発明は下記端末装置を更に提供する。図５に示すとおり、前記端末装置は、少なくとも１つのプロセッサー（processor）２０、表示パネル２１およびメモリ（memory）２２を含む。前記端末装置は通信インターフェース（Communications  Interface）２３とバス２４を更に含むことができる。プロセッサー２０、表示パネル２１、メモリ２２および通信インターフェース２３はバス２４により通信可能に接続される。表示パネル２１は最初の設定モデル中の予め設定されるガイダンスインターフェイスを表示するように設けられる。通信インターフェース２３により情報を伝送することができる。プロセッサー２０はメモリ２２中のロジック指令を用いることにより本発明の前記実施例に係る二進コードによるデジタル集積回路の配線方法を実施することができる。
【００６５】
前記メモリ２２中のロジック指令はソフトウェアユニットにより実行されることができる。前記メモリ２２中のロジック指令を独立の製品として販売するか或いは用いるとき、そのロジック指令をコンピュータ読み取り可能な記憶媒体に記憶させることができる。
【００６６】
メモリ２２は、コンピュータ読み取り可能な記憶媒体であり、ソフトウェアプログラム、コンピュータ実行可能なプログラム、例えば本発明の実施例に係るプログラム指令またはプログラムモジュールを記憶させるように設けられる。プロセッサー２０は、メモリ２２に記憶されるソフトウェアプログラム、プログラム指令またはプログラムモジュールを実行することにより所定の機能とデータの処理をする。例えば本発明の前記実施例に係る二進コードによるデジタル集積回路の配線方法を実施することができる。
【００６７】
メモリ２２はプログラム記憶区域とデータ記憶区域を含むことができる。プログラム記憶区域は、オペレーティングシステム（operating  system）、少なくとも１つの機能を実施する応用プログラム（application  program）を記憶させ、データ記憶区域は端末装置の使用により形成されるデータ等を記憶させることができる。メモリ２２は高速ランダムアクセスメモリまたは不揮発性記憶装置（non-volatile  memory）を含むことができる。例えば、ＵＳＢフラッシュディスク、モバイルハードディスク（Mobile  Hard  disk）、読み取り専用メモリ（Read-Only  Memory、ＲＯＭ）、ランダムアクセスメモリ（Random  Access  Memory、ＲＡＭ）、磁気ディスクまたはライトディスク等のプルグラムコードを記憶させる媒体であるか或いは一時的な記憶媒体であることができる。
【００６８】
前記記憶媒体および端末装置中の複数の指令がプロセッサーにより実施される具体的な過程は前記二進コードによるデジタル集積回路の配線方法を参照することができるので、ここで再び説明しない。
【００６９】
注意されたいことは、前記実施例は本発明の技術的事項を説明するものであるが、本発明を限定するものでない。以上、本発明の実施例により本発明の技術的特徴を詳述してきたが、前記実施例は本発明の例示にしか過ぎないものであり、本発明は前記実施例の構成にのみ限定されるものでない。本技術分野の技術者は、本発明の要旨を逸脱しない範囲内において設計の変更、代替等をすることができ、それらがあっても本発明に含まれることは勿論である。
【符号の説明】
【００７０】
20  プロセッサー
21  表示パネル
22  メモリ
23  通信インターフェース
24  バス
【図１】
2021532605.tif 000011
【図２】
2021532605.tif 000012
【図３】
2021532605.tif 000013
【図４】
2021532605.tif 000014
【図５】
2021532605.tif 000015
【国際調査報告】
2021532605.tif 000016
2021532605.tif 000017
2021532605.tif 000018
2021532605.tif 000019