(57)【要約】  本発明は離散最適化によるデジタル集積回路のレイアウト方法および端末装置を提供する。前記方法は、所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成し、かつ各第一レイアウトを調節することによりレイアウトコンフリクトが除去される第二レイアウトを形成するステップと、各第二レイアウトの第一接続線全長を獲得し、かつ前記第一接続線全長と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップと、貪欲算法により各第三レイアウトに対して局部最適化をすることにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長をそれぞれ計算するステップと、計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップとを含む。本発明はスタンダードセルに位置離散コードをつけ、かつ離散最適化方法によりレイアウトに対して最適化をすることにより最適化レイアウトの性能を向上させ、かつレイアウトの難易度を低減することができる。
2021530825.tif 000002
【特許請求の範囲】
【請求項１】
所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成し、かつ各第一レイアウトを調節することによりレイアウトコンフリクトが除去される第二レイアウトを形成するステップと、
各第二レイアウトの第一接続線全長を獲得し、かつ前記第一接続線全長と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップと、
貪欲算法により各第三レイアウトに対して局部最適化をすることにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長をそれぞれ計算するステップと、
計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップとを含むことを特徴とする離散最適化によるデジタル集積回路のレイアウト方法。
【請求項２】
所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成し、かつ第一レイアウトを調節することによりレイアウトコンフリクトが除去される第二レイアウトを形成する前記ステップは具体的に、
所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成するステップと、
第一レイアウト中の任意の２個のスタンダードセルがｃｉ≠ｃｊになるようにし、ｃｉとｃｊがｘｉ＝ｘｊを満たすとき、ｙｉ＝ｙｊにするステップであって、ｘｉとｘｊは第一レイアウト中のスタンダードセルの列位置であり、ｙｉとｙｊは第一レイアウト中のスタンダードセルの行位置であるステップと、
それを満たすとき、第ｙｉ行中の第ｘｊ列のスタンダードセルを右に一列移動させ、第一レイアウトにレイアウトコンフリクトが含まれないときまでそのステップを繰り返すことにより第二レイアウトを獲得するステップとを含むことを特徴とする請求項１に記載の離散最適化によるデジタル集積回路のレイアウト方法。
【請求項３】
前記所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成するステップは具体的に、
スタンダードセルのレイアウトコードを予め設定の数量がｎである２ｍ次元のベクトルＰｉにするステップであって、ｍはスタンダードセルの数量であり、ｉ＝１、２、．．．、ｎであるステップと、
前記ベクトルＰｉに対してリバースコーディングをすることによりスタンダードセルの位置集合を獲得し、前記位置集合により前記第一レイアウトを確定するステップとを含むことを特徴とする請求項２に記載の離散最適化によるデジタル集積回路のレイアウト方法。
【請求項４】
前記ベクトルＰｉに対してリバースコーディングをすることによりスタンダードセルの位置集合を獲得し、前記位置集合により前記第一レイアウトを確定するステップは具体的に、
Ｐｉにおいて前部ｍ個の値と後部ｍ個の値をとることによりサブベクトルＰｉ={Ｐｘ|Ｐｙ}を形成するステップであって、ＰｘとＰｙ中の数値は１つずつ対応するステップと、
Ｐｙ中の数値を順番に配列させることにより行位置ベクトルＹを形成し、Ｐｘ中の数値が行位置と一致する数値を同一のサブベクトルＰｘｙに挿入するステップと、
各Ｐｘｙ中の数値を順番に配列させることにより列位置サブベクトルＸｙを形成し、すべてのＸｙを合併させることにより列位置ベクトルＸを形成することにより前記第一レイアウトを獲得するステップとを含むことを特徴とする請求項３に記載の離散最適化によるデジタル集積回路のレイアウト方法。
【請求項５】
各第二レイアウトの第一接続線全長を獲得し、かつ前記第一接続線全長と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップは具体的に、
予め設定された接続線の集合を獲得し、前記接続線の集合により各第二レイアウトの第一接続線全長を獲得するステップと、
前記第一接続線全長により第二レイアウトのフィットネス函数値を確定するステップと、
前記フィットネス函数値と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップとを含むことを特徴とする請求項１に記載の離散最適化によるデジタル集積回路のレイアウト方法。
【請求項６】
前記貪欲算法により各第三レイアウトに対して局部最適化をすることにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長をそれぞれ計算するステップは具体的に、
第三レイアウト中の任意のスタンダードセルｃｉ（ｘｉ,ｙｉ）において、予め設定規則によりｃｉの高位ユニットのコネクティビティーＤｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を計算するステップと、
Ｄｕｐｐｅｒ（ｃｉ）＞Ｄｌｏｗｅｒ（ｃｉ）であるとき、ｃｉを上へ一行移動させた後、第三レイアウトの第三接続線全長を計算し、第三接続線全長が第二接続線全長より小さいとき、ｃｉを上へ一行移動させた後、高位ユニットのコネクティビティーＤｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を複数回計算し、逆の場合、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を計算するステップと、
Ｄｕｐｐｅｒ（ｃｉ）＜Ｄｌｏｗｅｒ（ｃｉ）であるとき、ｃｉを下へ一行移動させた後、第三レイアウトの第三接続線全長を計算し、第三接続線全長が第二接続線全長より小さいとき、ｃｉを下へ一行移動させた後、高位ユニットのコネクティビティーＤｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を複数回計算し、逆の場合、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を計算するステップと、
Ｄｒｉｇｈｔ（ｃｉ）＞Ｄｌｅｆｔ（ｃｉ）であるとき、ｃｉを右側一列へ移動させた後、第三レイアウトの第三接続線全長を計算し、第三接続線全長が第二接続線全長より小さいとき、ｃｉとその右側の一列のスタンダードセルの位置を変換させた後、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を複数回計算し、逆の場合、次のスタンダードセルへ移動させることによりすべてのスタンダードセルを検索するステップと、
Ｄｒｉｇｈｔ（ｃｉ）＜Ｄｌｅｆｔ（ｃｉ）であるとき、ｃｉを左側一列へ移動させた後、第三レイアウトの第三接続線全長を計算し、第三接続線全長が第二接続線全長より小さいとき、ｃｉとその左側の一列のスタンダードセルの位置を変換させた後、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を複数回計算し、逆の場合、次のスタンダードセルへ移動させることによりすべてのスタンダードセルを検索することにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長を計算するステップとを含むことを特徴とする請求項１に記載の離散最適化によるデジタル集積回路のレイアウト方法。
【請求項７】
前記計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップは具体的に、
前記第四レイアウトに対応するイテレーション回数を獲得し、かつ前記イテレーション回数と予め設定イテレーション回数を比較するステップと、
前記イテレーション回数と前記予め設定イテレーション回数が等しいとき、計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップとを含むことを特徴とする請求項１に記載の離散最適化によるデジタル集積回路のレイアウト方法。
【請求項８】
前記計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップは、前記イテレーション回数が前記予め設定イテレーション回数より小さいとき、前記第四レイアウトを第一レイアウトにし、かつ第一レイアウトで調節をするステップに戻り、イテレーション回数が予め設定イテレーション回数に達するとそのステップを停止させるステップを更に含むことを特徴とする請求項７に記載の離散最適化によるデジタル集積回路のレイアウト方法。
【請求項９】
コンピュータ読み取り可能な記憶媒体であって、前記コンピュータ読み取り可能な記憶媒体は１個または複数個のプログラムを記憶させ、前記１個または複数個のプログラムが１個または複数個のプロセッサーに実行されることにより請求項１〜８のうちいずれか一項に記載の離散最適化によるデジタル集積回路のレイアウト方法中のステップを実施することを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１０】
端末装置であって、前記端末装置は、プロセッサー、メモリおよびバスを含み、
前記メモリには前記プロセッサーによって実行されるコンピュータ読み取り可能なプログラムが記憶され、
前記バスはプロセッサーとメモリとの間の通信を担当し、
前記プロセッサーはコンピュータ読み取り可能なプログラムを実行することにより請求項１〜８のうちいずれか一項に記載の離散最適化によるデジタル集積回路のレイアウト方法中のステップを実施することを特徴とする端末装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル集積回路の技術分野に属し、特に、離散最適化（discrete  optimizing）によるデジタル集積回路のレイアウト方法および端末装置に関するものである。
【背景技術】
【０００２】
デジタル集積回路（integrated  circuit、ＩＣ）をチップともいい、それは半導体技術によるマイクロエレクトロニクスデバイス（microelectronic  device）である。現在の集積回路は通常、スタンダードセル（Standard  Cell）で構成されるものである。スタンダードセルは一定の機能を具備する回路モジュールであり、例えばトリガー（trigger）、ゲート回路（gate  circuit）、加算装置（Adder）、バッファー（buffer）、レジスター（register）、ＲＡＭメモリユニット等を含む。図１に示すとおり、１つのレイアウトにおいて各スタンダードセルの高さは通常揃えられている。各スタンダードセルの高さが一致するが、その機能が増加することにより、その幅は増加し、その構造は複雑になり、設けられるトランジスタの数量は増加し、全体幅も増加する。デジタル集積回路の設定において、機能ポートの位置によって所定のスタンダードセルをポートの付近に位置させることにより接続の利便性の向上させることができる。スタンダードセルの間には内部接続線が設けられており、レイアウトの結果は接続線の結線完了率（completion  rate  of  wire  connection）に直接に影響を与える。応用の需要とチップの集積度が増加することにより、多機能のデジタル集積回路は数万個または数千万個のスタンダードセルで構成され、スタンダードセルのレイアウト方法は大規模のデジタル集積回路の設計において重要な課題になっている。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
従来の技術的課題を解決するため、本発明の目的は離散最適化によるデジタル集積回路のレイアウト方法および端末装置を提供することにある。
【課題を解決するための手段】
【０００４】
本発明の技術的特徴は次のとおりである。
【０００５】
離散最適化によるデジタル集積回路のレイアウト方法であって、前記デジタル集積回路は基板を含み、前記基板は複数個のスタンダードセルを含み、前記離散最適化によるデジタル集積回路のレイアウト方法は、
所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成し、かつ各第一レイアウトを調節することによりレイアウトコンフリクトが除去される第二レイアウトを形成するステップと、
各第二レイアウトの第一接続線全長を獲得し、かつ前記第一接続線全長と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップと、
貪欲算法により各第三レイアウトに対して局部最適化をすることにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長をそれぞれ計算するステップと、
計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップとを含む。
【０００６】
前記離散最適化によるデジタル集積回路のレイアウト方法において、前記所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成し、かつ第一レイアウトを調節することによりレイアウトコンフリクトが除去される第二レイアウトを形成する前記ステップは具体的に、
所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成するステップと、
第一レイアウト中の任意の２個のスタンダードセルがｃｉ≠ｃｊになるようにし、ｃｉとｃｊがｘｉ＝ｘｊを満たすとき、ｙｉ＝ｙｊにするステップであって、ｘｉとｘｊは第一レイアウト中のスタンダードセルの列位置であり、ｙｉとｙｊは第一レイアウト中のスタンダードセルの行位置であるステップと、
それを満たすとき、第ｙｉ行中の第ｘｊ列のスタンダードセルを右に一列移動させ、第一レイアウトにレイアウトコンフリクトが含まれないときまでそのステップを繰り返すことにより第二レイアウトを獲得するステップとを含む。
【０００７】
前記離散最適化によるデジタル集積回路のレイアウト方法において、前記所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成するステップは具体的に、
スタンダードセルのレイアウトコードを予め設定の数量がｎである２ｍ次元のベクトルＰｉにするステップであって、ｍはスタンダードセルの数量であり、ｉ＝１、２、．．．、ｎであるステップと、
前記ベクトルＰｉに対してリバースコーディングをすることによりスタンダードセルの位置集合を獲得し、前記位置集合により前記第一レイアウトを確定するステップとを含む。
【０００８】
前記離散最適化によるデジタル集積回路のレイアウト方法において、前記ベクトルＰｉに対してリバースコーディングをすることによりスタンダードセルの位置集合を獲得し、前記位置集合により前記第一レイアウトを確定するステップは具体的に、
Ｐｉにおいて前部ｍ個の値と後部ｍ個の値をとることによりサブベクトルＰｉ={Ｐｘ|Ｐｙ}を形成するステップであって、ＰｘとＰｙ中の数値は１つずつ対応するステップと、
Ｐｙ中の数値を順番に配列させることにより行位置ベクトルＹを形成し、Ｐｘ中の数値が行位置と一致する数値を同一のサブベクトルＰｘｙに挿入するステップと、
各Ｐｘｙ中の数値を順番に配列させることにより列位置サブベクトルＸｙを形成し、すべてのＸｙを合併させることにより列位置ベクトルＸを形成することにより前記第一レイアウトを獲得するステップとを含む。
【０００９】
前記離散最適化によるデジタル集積回路のレイアウト方法において、前記各第二レイアウトの第一接続線全長を獲得し、かつ前記第一接続線全長と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップは具体的に、
予め設定された接続線の集合を獲得し、前記接続線の集合により各第二レイアウトの第一接続線全長を獲得するステップと、
前記第一接続線全長により第二レイアウトのフィットネス函数値を確定するステップと、
前記フィットネス函数値と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップとを含む。
【００１０】
前記離散最適化によるデジタル集積回路のレイアウト方法において、前記貪欲算法により各第三レイアウトに対して局部最適化をすることにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長をそれぞれ計算するステップは具体的に、
第三レイアウト中の任意のスタンダードセルｃｉ（ｘｉ,ｙｉ）において、予め設定規則によりｃｉの高位ユニットのコネクティビティーＤｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を計算するステップと、
Ｄｕｐｐｅｒ（ｃｉ）＞Ｄｌｏｗｅｒ（ｃｉ）であるとき、ｃｉを上へ一行移動させた後、第三レイアウトの第三接続線全長を計算し、第三接続線全長が第二接続線全長より小さいとき、ｃｉを上へ一行移動させた後、高位ユニットのコネクティビティーＤｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を複数回計算し、逆の場合、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を計算するステップと、
Ｄｕｐｐｅｒ（ｃｉ）＜Ｄｌｏｗｅｒ（ｃｉ）であるとき、ｃｉを下へ一行移動させた後、第三レイアウトの第三接続線全長を計算し、第三接続線全長が第二接続線全長より小さいとき、ｃｉを下へ一行移動させた後、高位ユニットのコネクティビティーＤｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を複数回計算し、逆の場合、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を計算するステップと、
Ｄｒｉｇｈｔ（ｃｉ）＞Ｄｌｅｆｔ（ｃｉ）であるとき、ｃｉを右側一列へ移動させた後、第三レイアウトの第三接続線全長を計算し、第三接続線全長が第二接続線全長より小さいとき、ｃｉとその右側の一列のスタンダードセルの位置を変換させた後、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を複数回計算し、逆の場合、次のスタンダードセルへ移動させることによりすべてのスタンダードセルを検索するステップと、
Ｄｒｉｇｈｔ（ｃｉ）＜Ｄｌｅｆｔ（ｃｉ）であるとき、ｃｉを左側一列へ移動させた後、第三レイアウトの第三接続線全長を計算し、第三接続線全長が第二接続線全長より小さいとき、ｃｉとその左側の一列のスタンダードセルの位置を変換させた後、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を複数回計算し、逆の場合、次のスタンダードセルへ移動させることによりすべてのスタンダードセルを検索することにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長を計算するステップとを含む。
【００１１】
前記離散最適化によるデジタル集積回路のレイアウト方法において、前記計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップは具体的に、
前記第四レイアウトに対応するイテレーション回数を獲得し、かつ前記イテレーション回数と予め設定イテレーション回数を比較するステップと、
前記イテレーション回数と前記予め設定イテレーション回数が等しいとき、計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップとを含む。
【００１２】
前記離散最適化によるデジタル集積回路のレイアウト方法において、前記計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップは、前記イテレーション回数が前記予め設定イテレーション回数より小さいとき、前記第四レイアウトを第一レイアウトにし、かつ第一レイアウトで調節をするステップに戻り、イテレーション回数が予め設定イテレーション回数に達するとそのステップを停止させるステップを更に含む。
【００１３】
コンピュータ読み取り可能な記憶媒体であって、前記コンピュータ読み取り可能な記憶媒体は１個または複数個のプログラムを記憶させ、前記１個または複数個のプログラムが１個または複数個のプロセッサーに実行されることにより前記いずれか１つの離散最適化によるデジタル集積回路のレイアウト方法中のステップを実施する。
【００１４】
端末装置であって、前記端末装置は、プロセッサー、メモリおよびバスを含み、
前記メモリには前記プロセッサーによって実行されるコンピュータ読み取り可能なプログラムが記憶され、
前記バスはプロセッサーとメモリとの間の通信を担当し、
前記プロセッサーはコンピュータ読み取り可能なプログラムを実行することにより前記いずれか１つの離散最適化によるデジタル集積回路のレイアウト方法中のステップを実施する。
【発明の効果】
【００１５】
本発明は離散最適化によるデジタル集積回路のレイアウト方法および端末装置を提供する。前記離散最適化によるデジタル集積回路のレイアウト方法は、所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成し、かつ各第一レイアウトを調節することによりレイアウトコンフリクトが除去される第二レイアウトを形成するステップと、各第二レイアウトの第一接続線全長を獲得し、かつ前記第一接続線全長と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップと、貪欲算法により各第三レイアウトに対して局部最適化をすることにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長をそれぞれ計算するステップと、計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップとを含む。本発明はスタンダードセルに位置離散コードをつけ、かつ離散最適化方法によりレイアウトに対して最適化をすることにより最適化レイアウトの性能を向上させ、かつレイアウトの難易度を低減することができる。
【図面の簡単な説明】
【００１６】
【図１】デジタル集積回路のスタンダードセルのレイアウトを示す図である。
【図２】本発明の離散最適化によるデジタル集積回路のレイアウト方法を示す流れ図である。
【図３】本発明の離散最適化によるデジタル集積回路のレイアウト方法において、リバースコーディングによりレイアウト位置を確定することを示す流れ図である。
【図４】本発明の離散最適化によるデジタル集積回路のレイアウト方法において、貪欲算法により行を比較することを示す流れ図である。
【図５】本発明の離散最適化によるデジタル集積回路のレイアウト方法において、貪欲算法により列を比較することを示す流れ図である。
【図６】本発明の自己起動制御システムの好適な実施例の構造を示す原理図である。
【発明を実施するための形態】
【００１７】
本発明は離散最適化によるデジタル集積回路のレイアウト方法および端末装置を提供する。本発明の目的、技術的特徴および発明の効果を詳細に明確に理解してもらうため、以下、図面により本発明の実施例をより詳細に説明する。下記具体的な実施例は本発明を説明するものであるが、本発明を限定するものでない。
【００１８】
本発明の明細書において、特別な説明がない限り、この明細書中の「１つ」、「１個」、「前記」および「該」等の用語は、１つの事項を含むだけでなく、複数の事項を含むこともできる。本発明の明細書中の「含む」という用語は、特徴、整数、ステップ、操作、部品と／或いはモジュールを含むことを意味するが、１個または複数個の特徴、整数、ステップ、操作、部品と／或いはモジュールの組合せが存在するか或いはそれらの組合せを更に含むことを意味することもできる。注意されたいことは、部品が他の部品に「連結」または「接続」されるとき、その部品は他の部品に直接に連結または接続されるか或いは中間部品により他の部品に間接的に連結または接続されることができる。この明細書中の「連結」または「接続」は無線連結または無線接続であることができる。この明細書中の「と／或いは」という用語は、係っている１個または複数個の事項のうちいずれかの１つまたは複数、いずれかの組合せまたは全部を含むことを意味することができる。
【００１９】
本発明の明細書において、特別な説明がない限り、この明細書中の用語（技術的用語と科学的用語を含む）はこの技術分野の技術者が常用している用語の意味を指す。注意されたいことは、本発明と従来の技術中の用語は、辞書に記載されている用語の意味を参照することができるが、特別な定義がある場合、特別に定義される意味を指すことができる。
【００２０】
以下、図面と具体的な実施例により本発明の技術的特徴をより詳細に説明する。
【００２１】
本発明の実施例において離散最適化（discrete  optimizing）によるデジタル集積回路のレイアウト方法を提供する。図２に示されるとおり、前記方法は下記ステップを含む。
【００２２】
ステップＳ１０において、所定の数量のスタンダードセル（Standard  Cell）の位置離散コードの第一レイアウトを予めランダムに形成し、かつ各第一レイアウトを調節することによりレイアウトコンフリクト（Layout  conflict）が除去される第二レイアウトを形成する。
【００２３】
具体的に、前記デジタル集積回路は基板を含み、前記基板の面積はｓ＝ｈ×ｗであり、その式においてｈは基板の高さであり、ｗは基板の幅である。前記基板上には複数個のスタンダードセルが配置され、前記スタンダードセルの集合をＣ＝｛ｃ１,ｃ２,...,ｃｍ｝と表記し、前記スタンダードセルの数量はｍ個であり、前記デジタル集積回路に含まれる接続線の集合をＥ＝｛ｅ１,ｅ２,...,ｅｐ｝と表記し、前記接続線の数量はｐ個である。前記接続線の集合において各接続線には２個のスタンダードセルが接続されるか或いは２個のスタンダードセルと所定のインターフェースが接続される。
【００２４】
デジタル集積回路に配置されるスタンダードセルと接続線を確定した後、前記デジタル集積回路に向いて所定の数量の第一レイアウトをランダムに形成する。前記第一レイアウト中の各スタンダードセルの位置を表記するため離散コードを採用する。すなわち前記第一レイアウト中の各スタンダードセルが前記第一レイアウトに位置している位置を１つの二次元座標で表記し、それにより前記スタンダードセルが前記第一レイアウトに位置している個所の行位置と列位置を表記することができる。各スタンダードセルに対応する行位置を離散コードで表記し、各スタンダードセルに対応する列位置も離散コードで表記することができる。
【００２５】
本実施例において、所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成し、かつ第一レイアウトを調節することによりレイアウトコンフリクトが除去される第二レイアウトを形成する前記ステップは具体的に下記ステップを含む。
【００２６】
ステップＳ２１において、所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成する。
【００２７】
ステップＳ２２において、第一レイアウト中の任意の２個のスタンダードセルがｃｉ≠ｃｊになるようにし、ｃｉとｃｊがｘｉ＝ｘｊを満たすとき、ｙｉ＝ｙｊにする。ｘｉとｘｊは第一レイアウト中のスタンダードセルの列位置であり、ｙｉとｙｊは第一レイアウト中のスタンダードセルの行位置である。
【００２８】
ステップＳ２３において、それを満たすとき、第ｙｉ行中の第ｘｊ列のスタンダードセルを右に一列移動させ、第一レイアウトにレイアウトコンフリクトが含まれないときまでそのステップを繰り返すことにより第二レイアウトを獲得する。
【００２９】
具体的に、前記第一レイアウト中のスタンダードセルの位置離散コードは２ｍ次元のベクトルをランダムに形成した後その２ｍ次元のベクトルに対してリバースコーディング（Reverse  coding）をすることにより獲得することができる。前記所定の数量のスタンダードセルの位置離散コードの第一レイアウトを予めランダムに形成するステップは具体的に、下記ステップを含む。
【００３０】
スタンダードセルのレイアウトコードを予め設定の数量がｎである２ｍ次元のベクトルＰｉに設定する。ｍはスタンダードセルの数量であり、ｉ＝１、２、．．．、ｎである。
【００３１】
前記ベクトルＰｉに対してリバースコーディングをすることによりスタンダードセルの位置集合を獲得し、前記位置集合により前記第一レイアウトを確定する。
【００３２】
前記２ｍ次元のベクトルＰｉをＰｉ＝｛ｒｘ１,ｒｘ２,...,ｒｘｍ,ｒｙ１,ｒｙ２,...,ｒｙｍ｝だと表記し、前記ベクトルＰｉの値はランダムに形成されるものでありかつ均等に配置される正整数であり、前記方法により予め設定の数量がｎである各ベクトルＰｉをランダムに形成する。すなわちデジタル集積回路レイアウトの進化ポピュレーション（Evolutionary  population）ｐｓ＝｛Ｐ１,Ｐ２,...,Ｐｎ｝を獲得する。ベクトルＰｉを獲得した後、前記ベクトルＰｉに対してリバースコーディングをし、かつ前記リバースコーディングによりスタンダードセルの位置集合を確定する。図３に示すとおり、前記ベクトルＰｉに対してリバースコーディングをすることによりスタンダードセルの位置集合を獲得し、前記位置集合により前記第一レイアウトを確定するステップは具体的に、下記ステップを含む。
【００３３】
Ｐｉにおいて前部ｍ個の値と後部ｍ個の値をとることによりサブベクトルＰｉ={Ｐｘ|Ｐｙ}を形成する。ＰｘとＰｙ中の数値は１つずつ対応する。
【００３４】
Ｐｙ中の数値を順番に配列させることにより行位置ベクトルＹを形成し、Ｐｘ中の数値が行位置と一致する数値を同一のサブベクトルＰｘｙに挿入する。
【００３５】
各Ｐｘｙ中の数値を順番に配列させることにより列位置サブベクトルＸｙを形成し、すべてのＸｙを合併させることにより列位置ベクトルＸを形成することにより前記第一レイアウトを獲得する。
【００３６】
具体的に、ｐｓ中の任意のＰｉにおいて、Ｐｉ中の前部ｍ個の値と後部ｍ個の値をとり、前記前部ｍ個の値をＰｘ＝｛ｒｘ１,ｒｘ２,...,ｒｘｍ｝にし、後部ｍ個の値をＰｙ＝｛ｒｙ１,ｒｙ２,...,ｒｙｍ｝にする。それにより前記ＰｘとＰｙはサブベクトルＰｉ={Ｐｘ|Ｐｙ}を形成する。ＰｘとＰｙ中の数値が配列順番において１つずつ対応することによりｍ個のスタンダードセルの配置位置を決定する。サブベクトルＰｉ={Ｐｘ|Ｐｙ}を獲得した後、Ｐｙ中の数値を順番に配列させることにより行位置ベクトルＹを形成する。ＹはＹ＝｛ｙｉ＝ｒａｎｋ（ｒｙｉ）,ｒｙｉ∈Ｐｙ｝であり、特に、ｒｙｉ＝ｒｙｊであるとき、ｒａｎｋ（ｒｙｉ）＝ｒａｎｋ（ｒｙｊ）である。
【００３７】
位置ベクトルを獲得した後、任意のｒｘｉ,ｒｘｊ∈Ｐｘにおいて、行数が一致することすなわちｙｉ＝ｙｊが存在すると、前記ｒｘｉ,ｒｘｊを同一のサブベクトルＰｘｙ＝｛ｒｘｉ,ｒｘｊ,....｝に挿入する。すなわちＰｘｙ中の各元素の行数が一致すると、複数個のＰｘｙを順に獲得する。Ｐｘｙの数量はＹであり、Ｙは異なる行数を有しているベクトルの数量である。Ｐｘｙを獲得した後、Ｐｘｙ中の数値を順番に配列させることにより列位置サブベクトルＸｙを形成する。ＸｙはＸｙ＝｛ｘｉ＝ｒａｎｋ（ｒｘｉ）,ｒｘｉ∈Ｐｘｙ｝であり、ｒｘｉ＝ｒｘｊ,ｙｉ＝ｙｊであるとき、ｒａｎｋ（ｒｘｉ）＝ｒａｎｋ（ｒｘｊ）である。最後に、すべてのＸｙを合併させることにより列位置ベクトルＸを獲得し、Ｐｉの位置集合｛Ｘ,Ｙ｝を獲得し、前記位置集合｛Ｘ,Ｙ｝により第一レイアウトを獲得する。前記第一レイアウト中の各スタンダードセルは隙間を含まない。
【００３８】
ステップＳ２０において、各第二レイアウトの第一接続線全長を獲得し、かつ前記第一接続線全長と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得する。
【００３９】
前記第一接続線全長とは第二レイアウトの各接続線の全長をいう。第一接続線全長を獲得するとき、半周長方法により第二レイアウトに含まれるＰ本の接続線の各接続線の長さを算出し、かつ接続線の長さにより第一接続線全長を獲得することができる。第一接続線全長を獲得した後、前記第一接続線全長をフィットネス函数値（Fitness  Function  value）にし、前記フィットネス函数値と離散最適化方法により各第二レイアウトに対して最適化をする。前記離散最適化方法は制限がついている離散的な差異進化（Discrete  differential  evolution、ＤＤＥ）と離散粒子群最適化（Discrete  particle  swarm  optimization、ＤＰＳＯ）等であることができる。離散最適化方法による最適化方法の制限は下記のとおりである。
【００４０】
【数１】
2021530825.tif 000003
【００４１】
この式において、ｈｃｅｌｌはスタンダードセルの高さであり、ｗｘ,ｙは第ｙ∈Ｙ行中の第ｘ個のスタンダードセルの幅であり、Ｙはｍ個のスタンダードセルの行位置である。
【００４２】
本発明の実施例において、各第二レイアウトの第一接続線全長を獲得し、かつ前記第一接続線全長と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得するステップは具体的に下記ステップを含む。
【００４３】
Ｓ２１において、予め設定された接続線の集合を獲得し、前記接続線の集合により各第二レイアウトの第一接続線全長を獲得する。
【００４４】
Ｓ２２において、前記第一接続線全長により第二レイアウトのフィットネス函数値を確定する。
【００４５】
Ｓ２３において、前記フィットネス函数値と離散最適化方法により各第二レイアウトに対して最適化をすることにより各第三レイアウトを獲得する。
【００４６】
具体的に、前記接続線全長をフィットネス函数値にし、フィットネス函数値は下記のとおりである。
【００４７】
【数２】
2021530825.tif 000004
【００４８】
前記
【数３】
2021530825.tif 000005
において、ｅｉは第二レイアウト中の各接続線の長さを表記する。
【００４９】
ステップＳ３０において、貪欲算法（greedy  algorithm）により各第三レイアウトに対して局部最適化をすることにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長をそれぞれ計算する。
【００５０】
具体的に、第三レイアウトを獲得した後、目標により接続線全長を最小にし、貪欲算法により第三レイアウトを調節することにより接続線全長が一番小さい第四レイアウトを獲得する。図４と図５に示すとおり、前記貪欲算法により各第三レイアウトに対して局部最適化をすることにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長をそれぞれ計算するステップは具体的に下記ステップを含む。
【００５１】
第三レイアウト中の任意のスタンダードセルｃｉ（ｘｉ,ｙｉ）において、予め設定規則によりｃｉの高位ユニットのコネクティビティー（connectivity）Ｄｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を計算する。
【００５２】
Ｄｕｐｐｅｒ（ｃｉ）＞Ｄｌｏｗｅｒ（ｃｉ）であるとき、ｃｉを上へ一行移動させた後、第三レイアウトの第三接続線全長を計算する。第三接続線全長が第二接続線全長より小さいとき、ｃｉを上へ一行移動させた後、高位ユニットのコネクティビティーＤｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を複数回計算し、逆の場合、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を計算する。
【００５３】
Ｄｕｐｐｅｒ（ｃｉ）＜Ｄｌｏｗｅｒ（ｃｉ）であるとき、ｃｉを下へ一行移動させた後、第三レイアウトの第三接続線全長を計算する。第三接続線全長が第二接続線全長より小さいとき、ｃｉを下へ一行移動させた後、高位ユニットのコネクティビティーＤｕｐｐｅｒ（ｃｉ）と低位ユニットのコネクティビティーＤｌｏｗｅｒ（ｃｉ）を複数回計算し、逆の場合、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を計算する。
【００５４】
Ｄｒｉｇｈｔ（ｃｉ）＞Ｄｌｅｆｔ（ｃｉ）であるとき、ｃｉを右側一列へ移動させた後、第三レイアウトの第三接続線全長を計算する。第三接続線全長が第二接続線全長より小さいとき、ｃｉとその右側の一列のスタンダードセルの位置を変換させた後、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を複数回計算し、逆の場合、次のスタンダードセルへ移動させることによりすべてのスタンダードセルを検索する。
【００５５】
Ｄｒｉｇｈｔ（ｃｉ）＜Ｄｌｅｆｔ（ｃｉ）であるとき、ｃｉを左側一列へ移動させた後、第三レイアウトの第三接続線全長を計算する。第三接続線全長が第二接続線全長より小さいとき、ｃｉとその左側の一列のスタンダードセルの位置を変換させた後、高位ユニットのコネクティビティーＤｒｉｇｈｔ（ｃｉ）と低位ユニットのコネクティビティーＤｌｅｆｔ（ｃｉ）を複数回計算し、逆の場合、次のスタンダードセルへ移動させることによりすべてのスタンダードセルを検索することにより第四レイアウトを獲得し、かつ各第四レイアウトの第二接続線全長を計算する。
【００５６】
具体的に、第三レイアウト中の位置が｛ｘｉ,ｙｊ｝であるスタンダードセルｃｉ（ｘｉ,ｙｉ）において、前記スタンダードセルの高位ユニットのコネクティビティーは下記のとおりである。
【００５７】
【数４】
2021530825.tif 000006
【００５８】
前記スタンダードセルの低位ユニットのコネクティビティーは下記のとおりである。
【００５９】
【数５】
2021530825.tif 000007
【００６０】
この式において、ｅｋ,ｉはスタンダードセルｃｋとｃｉとの間の接続線の長さである。
【００６１】
第三レイアウト中の位置が｛ｘｉ,ｙｊ｝であるスタンダードセルｃｉ（ｘｉ,ｙｉ）において、前記スタンダードセルの高位ユニットのコネクティビティーは下記のとおりである。
【００６２】
【数６】
2021530825.tif 000008
【００６３】
前記スタンダードセルの低位ユニットのコネクティビティーは下記のとおりである。
【００６４】
【数７】
2021530825.tif 000009
【００６５】
この式において、ｅｋ,ｉはスタンダードセルｃｋとｃｉとの間の接続線の長さである。
【００６６】
ステップＳ４０において、計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させる。
【００６７】
具体的に、第四レイアウトを獲得した後、すべての第四レイアウトの第二接続線全長を計算し、かつ第二接続線全長が小さい第四レイアウトを最適化レイアウトにすることによりデジタル集積回路のレイアウトを獲得する。実際の応用において、デジタル集積回路の正確性を向上させるため、すべての第四レイアウトを獲得した後、第四レイアウトを第一レイアウトにしかつ最適化を繰り返すことにより最適化の第四レイアウトを獲得する。計算により獲得したすべての第二接続線全長によりすべての第四レイアウト中の最適化レイアウトを獲得し、かつ前記最適化レイアウトによりスタンダードセルを基板上に配置させるステップは具体的に下記ステップを含む。
【００６８】
前記第四レイアウトに対応するイテレーション回数（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  バス
【図１】
2021530825.tif 000010
【図２】
2021530825.tif 000011
【図３】
2021530825.tif 000012
【図４】
2021530825.tif 000013
【図５】
2021530825.tif 000014
【図６】
2021530825.tif 000015
【国際調査報告】
2021530825.tif 000016
2021530825.tif 000017
2021530825.tif 000018
2021530825.tif 000019