(57)【要約】【課題】  効率的な機能ブロックの配置を可能にする半導体集積回路のレイアウト方法、半導体集積回路のレイアウトプログラム、半導体集積回路のレイアウト装置を提供する。【解決手段】  半導体集積回路のレイアウト方法であって、複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、ブロック群に含まれる１つまたは複数のブロックを、サイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成する分類工程と、ブロック群内の単位ブロックを互いに近接して配置する第１の配置工程と、ブロックのそれぞれに接続される入力端子との配線長がタイミング制約条件を満たす基準距離よりも長いか否かを判定し、基準距離よりも長い第１のブロックがタイミング制約条件を満たすように、第１のブロックのタイミング制約条件を満たす配置可能領域の情報に基づいてブロック間の配置交換を行う第２の配置工程と、を有する。【選択図】  図７
2014056522.tif 000002
【特許請求の範囲】
【請求項１】
ネットリスト及びタイミング制約条件に基づいて、機能毎に分割された複数のブロックを配置する半導体集積回路のレイアウト方法であって、
前記複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、前記ブロック群に含まれる１つまたは複数の前記ブロックを、全ての前記ブロックのうちサイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成する分類工程と、
前記単位ブロック内の前記各ブロックに対応する前記半導体集積回路の入力端子の位置に基づいて、前記ブロック群内の前記単位ブロックを互いに近接して配置する第１の配置工程と、
前記第１の配置工程によって配置された前記各ブロックについて、前記各ブロックのそれぞれに接続される前記入力端子との配線長が前記タイミング制約条件を満たす基準距離よりも長いか否かを判定し、前記基準距離よりも長い第１のブロックが前記タイミング制約条件を満たすように、前記第１のブロックの前記タイミング制約条件を満たす配置可能領域の情報に基づいて前記各ブロック間の配置交換を行う第２の配置工程と、を有することを特徴とする半導体集積回路のレイアウト方法。
【請求項２】
請求項１において、
前記第２の配置工程では、前記第１のブロックの前記タイミング制約条件を満たす第１の配置可能領域に配置され前記配線長が前記基準距離と同じか短い第２のブロックであって、当該第２のブロックの前記タイミング制約条件を満たす第２の配置可能領域が前記第１のブロックの配置位置を含む第２のブロックと、前記第１のブロックとを配置交換することを特徴とする半導体集積回路のレイアウト方法。
【請求項３】
請求項１または２において、
前記第２の配置工程では、前記第１のブロックの前記タイミング制約条件を満たす第１の配置可能領域に配置される前記タイミング制約条件のない第３のブロックと、前記第１のブロックとを配置交換することを特徴とする半導体集積回路のレイアウト方法。
【請求項４】
請求項１乃至３のいずれか一項において、
前記第２の配置工程では、前記第１のブロックの前記タイミング制約条件を満たす第１の配置可能領域に配置され前記配線長が前記基準距離よりも長い第４のブロックであって、当該第４のブロックの前記タイミング制約条件を満たす第４の配置可能領域が前記第１のブロックの配置位置を含む前記第４のブロックと、前記第１のブロックとを配置交換することを特徴とする半導体集積回路のレイアウト方法。
【請求項５】
請求項１乃至４のいずれか一項において、
前記第２の配置工程では、前記第１のブロックが複数ある場合に、前記複数の第１のブロックのうち、前記タイミング制約条件との乖離が大きい前記第１のブロックを優先して配置交換することを特徴とする半導体集積回路のレイアウト方法。
【請求項６】
請求項１乃至５のいずれか一項において、
前記第２の配置工程では、同一の前記ブロック群内の前記各ブロック間について優先して配置交換することを特徴とする半導体集積回路のレイアウト方法。
【請求項７】
請求項１乃至６のいずれか一項において、
前記第１の配置工程は、前記ブロック群内の前記単位ブロックを、Ｘ方向、またはＹ方向に配置することを特徴とする半導体集積回路のレイアウト方法。
【請求項８】
ネットリスト及びタイミング制約条件に基づいて、機能毎に分割された複数のブロックを配置するレイアウト処理をコンピュータに実行させるコンピュータ読み取り可能な半導体集積回路のレイアウトプログラムであって、
前記レイアウト処理は、
前記複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、前記ブロック群に含まれる１つまたは複数の前記ブロックを、全ての前記ブロックのうちサイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成する分類工程と、
前記単位ブロック内の前記各ブロックに対応する前記半導体集積回路の入力端子の位置に基づいて、前記ブロック群内の前記単位ブロックを互いに近接して配置する第１の配置工程と、
前記第１の配置工程によって配置された前記各ブロックについて、前記各ブロックのそれぞれに接続される前記入力端子との配線長が前記タイミング制約条件を満たす基準距離よりも長いか否かを判定し、前記基準距離よりも長い第１のブロックが前記タイミング制約条件を満たすように、前記第１のブロックの前記タイミング制約条件を満たす配置可能領域の情報に基づいて前記各ブロック間の配置交換を行う第２の配置工程と、を有することを特徴とする半導体集積回路のレイアウトプログラム。
【請求項９】
ネットリスト及びタイミング制約条件に基づいて、機能毎に分割された複数のブロックを配置する半導体集積回路のレイアウト装置であって、
前記複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、前記ブロック群に含まれる１つまたは複数の前記ブロックを、全ての前記ブロックのうちサイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成する分類手段と、
前記単位ブロック内の前記各ブロックに対応する前記半導体集積回路の入力端子の位置に基づいて、前記ブロック群内の前記単位ブロックを互いに近接して配置する第１の配置手段と、
前記第１の配置手段によって配置された前記各ブロックについて、前記各ブロックのそれぞれに接続される前記入力端子との配線長が前記タイミング制約条件を満たす基準距離よりも長いか否かを判定し、前記基準距離よりも長い第１のブロックが前記タイミング制約条件を満たすように、前記第１のブロックの前記タイミング制約条件を満たす配置可能領域の情報に基づいて前記各ブロック間の配置交換を行う第２の配置手段と、を有することを特徴とする半導体集積回路のレイアウト装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路のレイアウト方法、半導体集積回路のレイアウトプログラム、及び、半導体集積回路のレイアウト装置に関する。
【背景技術】
【０００２】
近年、半導体集積回路装置（ＬＳＩ）は、大規模化・高集積化が進められるとともに、その開発期間の短縮が要求されている。そこで、半導体集積回路のレイアウト設計を効率化するために、所定の機能を提供する機能ブロック毎にレイアウトが行われる。
【０００３】
機能ブロック（以下、単にブロックと称する）には、面積や形状の異なるさまざまなブロックが多数存在すると共に、ブロック間に多数の接続関係が存在する。そこで、ブロックの配置は、ブロック間の配線及び配線数、ブロックの端子位置、ブロック配置後に結線される配線の凹凸、ブロックへの入力信号のタイミング制約条件等が考慮される。さらに、顧客の要求するチップサイズ、動作スピード、消費電力の要求についても考慮される。このため、機能ブロックの配置処理は、人手によるマニュアル作業によって行われる。
【０００４】
半導体集積回路のレイアウトについては、例えば、特許文献１に記載される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−４９６３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、人手によるマニュアル作業では膨大な工数を要する。そこで、自動レイアウトを実行する自動レイアウト設計ツール、いわゆるＥＤＡ（Electronic Design Automation）ツールが提供されているが、ＥＤＡツールでは配線の凹凸、ブロック間の配線領域、入力信号のタイミング等が考慮されない。このため、配線混雑の発生やタイミング制約条件を満たせない等の課題を有している。
【０００７】
そこで、本発明は、効率的な機能ブロックの配置を可能にする半導体集積回路のレイアウト方法、半導体集積回路のレイアウトプログラム、半導体集積回路のレイアウト装置を提供する。
【課題を解決するための手段】
【０００８】
第１の側面は、ネットリスト及びタイミング制約条件に基づいて、機能毎に分割された複数のブロックを配置する半導体集積回路のレイアウト方法であって、前記複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、前記ブロック群に含まれる１つまたは複数の前記ブロックを、全ての前記ブロックのうちサイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成する分類工程と、前記単位ブロック内の前記各ブロックに対応する前記半導体集積回路の入力端子の位置に基づいて、前記ブロック群内の前記単位ブロックを互いに近接して配置する第１の配置工程と、前記第１の配置工程によって配置された前記各ブロックについて、前記各ブロックのそれぞれに接続される前記入力端子との配線長が前記タイミング制約条件を満たす基準距離よりも長いか否かを判定し、前記基準距離よりも長い第１のブロックが前記タイミング制約条件を満たすように、前記第１のブロックの前記タイミング制約条件を満たす配置可能領域の情報に基づいて前記各ブロック間の配置交換を行う第２の配置工程と、を有する。
【発明の効果】
【０００９】
第１の側面によれば、本発明は、効率的な機能ブロックの配置を可能にする。
【図面の簡単な説明】
【００１０】
【図１】本実施の形態例における半導体集積回路のレイアウト装置の構成例を示す図である。
【図２】半導体集積回路のレイアウト工程の概要を示すフローチャート図である。
【図３】クロックドメインへの分類工程を説明する図である。
【図４】単位ブロックの生成工程を説明する図である。
【図５】単位ブロックの配置工程によるブロックの配置例を表す図である。
【図６】入力信号のタイミング制約条件に基づく概算配線長とマンハッタン長とを表す表図である。
【図７】ブロックの配置交換処理の第１の手法について説明するフローチャート図である。
【図８】ブロックの配置交換処理の第２の手法について説明するフローチャート図である。
【図９】ブロックの配置交換処理の第３の手法について説明するフローチャート図である。
【図１０】第１〜第３の手法の具体例について説明する図である。
【発明を実施するための形態】
【００１１】
以下、図面にしたがって本発明の実施の形態について説明する。ただし、本発明の技術的範囲はこれらの実施の形態に限定されず、特許請求の範囲に記載された事項とその均等物まで及ぶものである。
【００１２】
［レイアウト装置の構成］
図１は、本実施の形態例における半導体集積回路のレイアウト装置１の構成の一例を示す図である。本実施の形態において、機能ブロックの配置方法は、図１のようなパーソナルコンピュータやワークステーション等の半導体集積回路のレイアウト装置１によって実現される。
【００１３】
図１の半導体集積回路のレイアウト装置１は、プロセッサ１１と、メモリ１２と、出力部１３、入力部１４とを有し、バス線１５を介して相互に接続される。プロセッサ１１は、レイアウト装置１全体を制御する。出力部１３は、例えば、システム上の出力情報を表示するディスプレイ等の表示装置であり、入力部１４はマウスやキーボード等であり、システムへの入力を受け付ける。
【００１４】
また、メモリ１２は、例えば、機能ブロックの配置プログラム（以下、ブロック配置プログラム）ＰＲ、ネットリストＮＬ、タイミングスクリプトＴＳ、ライブラリＬＢを有する。機能ブロック（以下、ブロック）とは、論理的に関連する複数のマクロセルを機能単位に有するブロックである。ライブラリＬＢは、配置対象のブロックの識別情報、形状、及び、サイズ等の情報を有する。ネットリストＮＬは、配置対象の各ブロックについて、チップ（半導体集積回路）の入力端子との接続情報、及び、他のブロックの端子との接続情報を有する。また、タイミングスクリプトＴＳは、配置対象の各ブロックについて、入力信号の遅延時間をタイミング制約条件として有する。
【００１５】
ブロック配置プログラムＰＲは、プロセッサ１１によってメモリ１２から読み出され実行される。本実施の形態例におけるブロック配置プログラムＰＲは、配置対象のブロックを、ネットリストＮＬ、タイミングスクリプトＴＳ、ライブラリＬＢ等に基づいて、ブロックへの入力信号のタイミング制約条件が満たされるように配置する。ブロック配置プログラムＰＲの実行後のブロックの配置結果は、出力部１３に表示されると共に、メモリ１２等に格納される。
【００１６】
本実施の形態例におけるブロック配置プログラムＰＲによると、同一クロックドメインのブロック同士が近接して配置されることによってクロックスキューが抑えられると共に、配置後のブロック同士の形状の凹凸が抑制されることにより、各ブロックに接続される配線の混雑が軽減される。また、ブロック配置プログラムＰＲによって、各ブロックへの入力信号のタイミング制約条件を満たすようなブロックの配置調整が自動的に行われることにより、フロアプランに係る工数が大幅に削減される。
【００１７】
ここで、本実施の形態例における半導体集積回路のレイアウト工程の概要について説明する。
【００１８】
［レイアウト工程の概要］
図２は、半導体集積回路のレイアウト工程の概要を示すフローチャート図である。ブロック配置プログラムＰＲは、フロアプランとして、ブロックの配置処理Ｓ１１〜Ｓ１６を行う。本実施の形態例におけるブロック配置プログラムＰＲは、まず、ブロックを分類して単位ブロックを生成し、単位ブロックの接続対象の入力端子の傾向に基づいて、チップのアクティブ領域上に単位ブロック毎に概算配置する。
【００１９】
初めに、ブロック配置プログラムＰＲは、配置対象のブロックを、ブロックに入力されるクロック信号に基づいてブロックドメイン毎に分類する（Ｓ１１）。具体的に、ブロック配置プログラムＰＲは、タイミングスクリプトＴＳを参照して、各ブロックの入力クロック信号情報を取得し、同一のクロック信号が入力されるブロック毎に分類する。
【００２０】
続いて、ブロック配置プログラムＰＲは、分類されたクロックドメイン毎に、各クロックドメインに含まれる１つまたは複数のブロックを、配置対象のブロックにおいて、最大サイズのブロックと形状及びサイズが近似するように組み合わせて再グループ化し、単位ブロックを生成する（Ｓ１２）。続いて、ブロック配置プログラムＰＲは、単位ブロックを、同一クロックドメイン毎に、チップのアクティブ領域のＸ方向、またはＹ方向の同一ライン上に配置する（Ｓ１３）。
【００２１】
工程Ｓ１３において、具体的に、ブロック配置プログラムＰＲは、例えば、ネットリストＮＬを参照して、同一クロックドメインの単位ブロック内の各ブロックの接続対象の入力端子の情報を取得する。そして、ブロック配置プログラムＰＲは、取得した接続対象の入力端子がチップのＸ方向、Ｙ方向のいずれに多く位置するかによって、Ｘ方向に配置するか、Ｙ方向に配置するかを判定する。さらに、ブロック配置プログラムＰＲは、Ｘ方向に配置する場合はチップの上部または下部、Ｙ方向に配置する場合はチップの右部または左部に、接続対象の入力端子がより多く位置するかを判定する。
【００２２】
そして、ブロック配置プログラムＰＲは、同一クロックドメイン毎に、単位ブロックを単位として、配線の長さが最適化されるように、適宜、配置していく。なお、同一ドメインの単位ブロックがＸ方向の１ライン、またはＹ方向の１ラインに納まらない場合、ブロック配置プログラムＰＲは複数の行に渡って単位ブロックを配置する。
【００２３】
このように、ブロック配置プログラムＰＲは、単位ブロック内の各ブロックの接続対象の入力端子情報の傾向に基づいて、同一クロックドメインの単位ブロック同士が近接するように配置する。これにより、配置対象の各ブロックが概算配置される。
【００２４】
ここで、工程Ｓ１１〜工程Ｓ１３の処理について、具体的に基づいて説明する。
【００２５】
［具体例：クロックドメインへの分類（Ｓ１１）］
図３は、クロックドメインへの分類工程（Ｓ１１）を説明する図である。同図の（Ａ）には、本実施の形態例における配置対象のブロックが表される。また、同図の（Ｂ）は、配置対象のブロックが、入力されるクロック信号に基づいて、クロックドメイン毎に分類された図を表す。同図の（Ｂ）において、配置対象のブロックは、入力クロック信号に基づいて４つのクロックドメインＤｘ、Ｄｙ、Ｄｚ、Ｄｗに分類される。
【００２６】
具体的に、図３の（Ｂ）において、例えば、網点で表されたブロック群は、５０ＭＨｚのクロック信号が入力されるクロックドメインＤｘのブロックである。また、斜線で表されたブロック群は、１００ＭＨｚのクロック信号が入力されるクロックドメインＤｙのブロックである。クロックドメインＤｚ、Ｄｗのブロック群についても同様に、それぞれ共通のクロック信号が入力される。このように、入力されるクロック信号に基づいて、１つまたは複数のブロックを有するクロックドメインＤｘ、Ｄｙ、Ｄｚ、Ｄｗに分類される。
【００２７】
［具体例：単位ブロックの生成（Ｓ１２）］
図４は、単位ブロックの生成工程（Ｓ１２）を説明する図である。同図には、各クロックドメインＤｘ、Ｄｙ、Ｄｚ、Ｄｗのブロックが単位ブロックに分類されて表されている。前述したとおり、単位ブロックは、ブロックのうち、サイズが一番大きいブロックの形状に近似するように、クロックドメイン内の１つまたは複数のブロックが組み合わされて生成される。
【００２８】
図４において、ブロックＮ１は、配置対象の全てのブロックのうち、サイズが一番大きい。そこで、ブロック配置プログラムＰＲは、クロックドメインＤｘについて、ブロックＮ１とサイズが同等になるように、クロックドメインＤｘのブロックを組み合わせて単位ブロックを生成する。そこで、まず、クロックドメインＤｘのサイズが最小の９つのブロックについて、ブロックＮ１と同等のサイズになるように組み合わされ、単位ブロックＮ２が生成される。
【００２９】
同様にして、図４において、クロックドメインＤｘのサイズが最小の残りの８つのブロックについて、ブロックＮ１と形状が近似するように組み合わされ、単位ブロックＮ３、Ｎ４が生成される。この場合、６つのブロックからなる単位ブロックＮ３と、２つのブロックからなる単位ブロックＮ４が生成される。これにより、ブロックＮ３の少なくとも１つの辺についてブロックＮ１とサイズが近くなると共に、ブロックＮ４についても形状がブロックＮ１と近似する。また、クロックドメインＤｘの残りの２つのブロックについて、１つの単位ブロックＮ５が生成される。
【００３０】
同様にして、クロックドメインＤｙについても、ブロックＮ１と、形状、または、サイズが近似するように、単位ブロックＮ６、Ｎ７が生成される。他のクロックドメインＤｚ、Ｄｗについても同様である。
【００３１】
このようにして、同一クロックドメイン内のブロックについて、一番大きいサイズのブロックと形状が近似するように、１つまたは複数のブロックが組み合わされて、単位ブロックが生成される。これにより、単位ブロックが配置されたときのブロック間の形状の凹凸が抑えられ、配線の混線が抑制される。なお、図４において表わされる単位ブロックＮ１〜Ｎ９は、一例であって、各単位ブロックはブロックの別の組み合わせを有していてもよい。
【００３２】
［具体例：単位ブロックの配置（Ｓ１３）］
図５は、単位ブロックの配置工程（Ｓ１３）によるブロックの配置例ＣＨを表す図である。ブロック配置プログラムＰＲは、ネットリストＮＬの情報に基づいて、工程Ｓ１２で生成した単位ブロックＮ１〜Ｎ９毎に、チップのアクティブ領域に配置する。
【００３３】
例えば、ブロック配置プログラムＰＲは、ネットリストＮＬを参照して、クロックドメインＤｘの単位ブロックＮ１〜Ｎ５の各ブロックの接続対象の入力端子の情報を取得する。この例において、単位ブロックＮ１〜Ｎ５内ブロックの接続対象の入力端子は、チップのＹ方向ｄｙよりも、Ｘ方向ｄｘにより多く位置する。また、単位ブロックＮ１〜Ｎ５内のブロックの接続対象の入力端子は、チップの上部のＸ方向ｄｘにより多く位置する。これにより、クロックドメインＤｘの各単位ブロックＮ１〜Ｎ５は、チップのアクティブ領域の上部のＸ方向ｄｘに配置される。
【００３４】
ただし、図５の例において、クロックドメインＤｘの各単位ブロックのＸ方向ｄｘのサイズ（図４のｘ１〜ｘ５）の合計は、チップのアクティブ領域のＸ方向ｄｘのサイズを越える。このため、クロックドメインＤｘの単位ブロックＮ１〜Ｎ５は、チップのアクティブ領域のＸ方向ｄｘに２行に渡って配置される。
【００３５】
そして、ブロック配置プログラムＰＲは、クロックドメインＤｘの単位ブロックＮ１〜Ｎ５について、サイズの大きい単位ブロックＮ１から順に配置する。そして、ブロック配置プログラムＰＲは、単位ブロックＮ１を、チップのアクティブ領域の上部のＸ方向ｄｘのうち、配置対象の単位ブロックＮ１に含まれるブロックＲの接続対象の入力端子と近くなる位置に配置する。この例において、単位ブロックＮ１のブロックＲは、例えば、入力端子ＩＯ＿１０と接続される。このため、単位ブロックＮ１は、チップのアクティブ領域の上部のＸ方向ｄｘのうち、中央部に配置される。
【００３６】
同様にして、クロックドメインＤｘの単位ブロックのうち、次にサイズの大きい単位ブロックＮ２が配置される。この例において、単位ブロックＮ２に含まれるブロックＡ〜Ｉは、例えば、入力端子ＩＯ＿１〜ＩＯ＿１０とより多く接続される。このため、単位ブロックＮ２は、チップのアクティブ領域の上部のＸ方向ｄｘのうち、左端に配置される。クロックドメインＤｘの単位ブロックＮ３についても同様に配置される。そして、同様にして、クロックドメインＤｘの残りの単位ブロックＮ４、Ｎ５が、Ｘ方向ｄｘの２行目に配置される。
【００３７】
続いて、チップのアクティブ領域におけるＸ方向に、クロックドメインＤｙの単位ブロックＮ６、Ｎ７が配置される。クロックドメインＤｙについても、単位ブロックＮ６、Ｎ７内のブロックの接続対象の入力端子情報に基づいて、Ｘ方向ｄｘの配線の長さが最適化される位置に配置される。この例において、単位ブロックＮ６のブロックＳ〜Ｚは、例えば、入力端子ＩＯ＿３０〜ＩＯ_４０とより多く接続される。このため、単位ブロックＮ６は、チップのアクティブ領域の上部のＸ方向ｄｘのうち、右端に配置される。そして、単位ブロックＮ７は、例えば、ＩＯ＿１０〜ＩＯ＿１５と接続されることから、単位ブロックＮ６の左隣に配置される。
【００３８】
別のクロックドメインＤｚ、Ｄｗについても同様にして、クロックドメインＤｚ、Ｄｗ毎に、ブロックの接続対象の端子情報の傾向に基づいて、単位ブロックＮ８、Ｎ９が配置される。また、このとき、単位ブロックについて、チップの入力端子との接続情報に加えて、他のブロックの入力端子との接続情報についても加味され、配線の長さが最適化されるように配置されてもよい。
【００３９】
このようにして、クロックドメイン毎に、単位ブロックが、単位ブロック内の各ブロックの入力端子との位置関係の傾向に基づいて、同一の方向に近接して概算配置される。この処理において、形状を近似させた単位ブロックＮ１〜Ｎ９毎に配置されることにより、ブロックに結線される配線の凹凸が抑えられる。また、同一のクロックドメインの単位ブロックが同一の方向に近接して配置されることにより、クロック配線が容易になりクロックスキューが抑えられる。
【００４０】
ただし、単位ブロック毎に、単位ブロック内のブロックの接続対象の入力端子位置の傾向に基づいて配置されることにより、ブロックによっては、接続対象の入力端子から遠い場所に配置される。これにより、当該ブロックと入力端子間の配線長が長くなり、タイミングスクリプトＴＳに規定された入力信号のタイミング制約条件を満たすことができないことがある。そこで、本実施の形態例におけるブロック配置プログラムＰＲは、続いて、工程Ｓ１１〜Ｓ１３によって概算配置したブロックについて、入力信号のタイミング制約条件を満たすように、ブロック間で配置交換を行う。
【００４１】
図２のフローチャート図に戻り、続いて、ブロック配置プログラムＰＲは、概算配置によって配置された各ブロックについて、接続される入力端子からの入力信号の遅延時間に基づく概算配線長を算出すると共に、入力端子との配置位置に基づくマンハッタン長を、仮想配線の配線長として算出する（Ｓ１４）。
【００４２】
具体的に、ブロック配置プログラムＰＲは、タイミングスクリプトＴＳを参照して、対象のブロックと、当該ブロックと接続される入力端子とのタイミング制約条件に基づいて、当該タイミング制約条件を満たす配線の長さを、概算配線長として算出する。また、ブロック配置プログラムＰＲは、配置されたブロックと接続対象の入力端子とのマンハッタン長を算出する。マンハッタン長とは、ブロックと入力端子の２点間の直角距離を示す。
【００４３】
続いて、ブロック配置プログラムＰＲは、算出した概算配線長からマンハッタン長を減算して減算値を算出する（Ｓ１５）。減算値に基づいて、ブロックの仮想配線を行った場合におけるブロックへの入力信号の遅延時間がタイミング制約条件を満たすか否かが検証される。具体的に、概算配線長からマンハッタン長の減算値がマイナス値の場合、ブロックへの入力信号が、タイミング制約条件で規定するクロックタイミングとその前後のセットアップタイム、ホールドタイムの時間帯よりも遅く入力されることを示す。このため、入力信号がクロックの立ち上がりに間に合わず、入力信号がラッチされない。
【００４４】
この場合、概算配置によって配置されたブロックと入力端子とのマンハッタン長である仮配線長が長過ぎることを意味する。そこで、ブロックと入力端子とのマンハッタン長が短く調整される必要がある。即ち、ブロックが入力端子により近い位置に配置調整される必要がある。
【００４５】
一方、概算配線長からマンハッタン長の減算値がプラス値の場合、ブロックへの入力信号がタイミング制約条件で規定するクロックタイミングとその前後のセットアップタイム、ホールドタイムの時間帯に対してより早く入力されることを示す。このような場合、例えば、ゲートの追加処理や配線の延長等によって入力信号の遅延時間が調整されることにより、タイミング制約条件を満たすように調整可能である。このため、概算配置によって配置されたブロックと入力端子とのマンハッタン長である仮配線長が短いものの、タイミング制約条件を満たすことが可能であるため、ブロックは、必ずしも、配置調整される必要はない。
【００４６】
このように、概算配線長からマンハッタン長の減算値がマイナス値の場合、マンハッタン長が短くなるようにブロックが配置調整される必要性がある。また、概算配線長からマンハッタン長の減算値がプラス値の場合、入力信号を遅らせることが可能であるため、必ずしも、ブロックの配置調整の必要性はない。本実施の形態例では、概算配線長からマンハッタン長の減算値がマイナス値である場合を、タイミング制約条件を満たしていない場合として説明する。
【００４７】
そこで、ブロック配置プログラムＰＲは、概算配線長からマンハッタン長の減算値がマイナス値のブロックについて、減算値がプラス値になるように、即ち、タイミング制約条件を満たすようにブロック同士の配置交換を行う（Ｓ１６）。配置交換処理の詳細については、別のフローチャート図に基づいて後述する。
【００４８】
続く工程Ｓ１７において、ブロックの配置交換処理後、Ｐ＆Ｒ処理として、スタンダードセルが配置され（Ｐｌａｃｅ）、端子間の配線が接続される（Ｒｏｕｔｅ）。そして、タイミングスクリプトＴＳに規定されたタイミング制約条件に基づいて、配線後の回路の遅延計算を行い、タイミング制約条件を満たすか否かが検証される（Ｓ１８）。タイミング検証で何らかの問題が見つかった場合には、必要に応じてブロックの配置修正等の処理が行われるが、本実施の形態例では、予め、タイミング制約条件を満たすようにブロックの配置調整が行われる。このため、配置後のブロックと入力端子との配線長が長くなり過ぎてタイミング制約条件に入力信号が間に合わず、ブロックの配置調整が必要になることが回避される。続いて、配置及び配線の結果に基づいて、電源が投入され回路の物理的検証が行われる（Ｓ１９）。
【００４９】
ここで、フローチャート図の工程Ｓ１４、Ｓ１５にて算出される概算配線長、及び、マンハッタン長、概算配線長からマンハッタン長の減算値の具体例について説明する。
【００５０】
［概算配線長からマンハッタン長の減算値の具体例］
図６は、図５の概算配置に基づく各ブロックと接続対象の入力端子とにおけるマンハッタン長、入力信号のタイミング制約条件に基づく概算配線長、及び、概算配線長からマンハッタン長の減算値を表す表図ＬＴである。同図におけるタイミング制約条件は、入力信号の遅延時間を示す。
【００５１】
同図の表ＬＴの１行目によると、入力端子ＩＯ＿１はブロックＡと接続され、ブロックＡへの入力信号のタイミング制約条件は１０ｎｓである。例えば、本実施の形態例において、タイミング制約条件が１０ｎｓである場合、タイミング制約条件を満たす配線の長さは１５０ｕｍである。また、図５の配置によると、ブロックＡと入力端子ＩＯ＿１とのマンハッタン長は、１４０ｕｍである。そのため、タイミング制約条件１０ｎｓに基づく概算配線長１５０ｕｍからマンハッタン長１４０ｕｍの減算値は、１０ｕｍ（＝１５０−１４０）となる。入力端子ＩＯ＿１はブロックＡとにおいて、配置位置に基づくマンハッタン長は、タイミング制約条件に基づく概算配線長よりも短い。即ち、ブロックＡへの入力端子ＩＯ＿１からの入力信号が１０ｎｓよりも早く入力されることを示す。このため、ブロックＡの再配置は、必須ではない。
【００５２】
同様にして、入力端子ＩＯ＿２とブロックＢ、入力端子ＩＯ＿１６とブロックＪについても、タイミング制約条件に基づく概算配線長からマンハッタン長の差分値がプラス値となる。他のブロックＫ、ブロックＺについても同様である。これらのブロックについては、ブロックの再配置は必須ではない。
【００５３】
一方、図６の表ＬＴの３行目によると（ｎ１）、入力端子ＩＯ＿３はブロックＱと接続され、ブロックＱへの入力信号のタイミング制約条件は１０ｎｓである。例えば、本実施の形態例において、タイミング制約条件が１０ｎｓである場合、タイミング制約条件を満たす配線の長さは１５０ｕｍと概算される。また、図５の配置によると、ブロックＱと入力端子ＩＯ＿３とのマンハッタン長は、９５０ｕｍである。そのため、タイミング制約条件１０ｎｓに基づく概算配線長１５０ｕｍからマンハッタン長９５０ｕｍの減算値は、−８００ｕｍ（＝１５０−９５０）となる。入力端子ＩＯ＿３とブロックＱとのマンハッタン長は、タイミング制約条件に基づく概算配線長よりも長い。即ち、ブロックＱへの入力端子ＩＯ＿３からの入力信号が１０ｎｓよりも遅れて入力されることを示す。これは、ブロックＱの再配置が必要であることを示す。
【００５４】
同様にして、入力端子ＩＯ＿３３とブロックβ（ｎ２）、入力端子ＩＯ＿４０とブロックＬ（ｎ３）についても、タイミング制約条件に基づく概算配線長からマンハッタン長の差分値がマイナス値となる。即ち、ブロックβ、ブロックＬについても再配置が必要である。
【００５５】
このように、本実施の形態例では、単位ブロック内のブロックに接続される入力端子の位置の傾向に基づいて、単位ブロック毎に概算配置されるため、ブロックによっては接続対象の入力端子から遠い位置に配置されることがある。これにより、ブロックへの入力信号がタイミングスクリプトＴＳに規定されたタイミング制約条件を満たすことができず、配置調整が必要となることがある。そこで、配置調整が必要なブロックについて、ブロック間の配置交換（図２のＳ１６）が行われる。
【００５６】
［ブロックの配置交換処理］
続いて、図２のフローチャート図の工程Ｓ１６の処理の詳細について、フローチャート図に基づいて説明する。本実施の形態例では、第１〜第３の配置交換の手法について説明されている。この例では、第１の手法に基づく配置交換の後、配置調整が必要なブロックが残存する場合に、さらに、第２の手法に基づいて配置交換が行われる。そして、第２の手法に基づく配置交換の結果、配置調整が必要なブロックが残存する場合に、第３の手法に基づいて配置交換が行われる。ただし、この例に限定されるものではなく、３つの手法のうち、いずれかの手法の配置交換処理のみが行われてもよいし、いずれか２つの手法の組み合わせによって配置交換処理が行われてもよい。
【００５７】
［ブロックの配置交換：第１の手法］
図７は、ブロックの配置交換処理の第１の手法について説明するフローチャート図である。第１の方法では、ブロック配置プログラムＰＲは、概算配置の結果、ブロックとそれに接続される入力端子とのマンハッタン長がタイミング制約条件を満たす概算配線長よりも長いブロックと、当該ブロックのタイミング制約条件を満たす配置可能領域に位置するタイミング制約条件のないブロックとを配置交換する。タイミング制約条件のないブロックは配置の自由度が高いことから、マンハッタン長がタイミング制約条件を満たす概算配線長よりも長いブロックがより簡易に配置交換可能となると共に、同一クロックドメイン同士での配置交換がより容易となる。
【００５８】
マンハッタン長がタイミング制約条件を満たす概算配線長よりも長いブロックとは、図２のフローチャート図の工程Ｓ１４にて算出される概算配線長からマンハッタン長の減算値がマイナス値であるブロック（以下、マイナス値のブロック）を示す。マイナス値のブロックは、入力信号がタイミング制約条件に規定される遅延時間より遅れるブロックであって、配置調整の必要性のあるブロックである。
【００５９】
ブロック配置プログラムＰＲは、まず、入力信号のタイミング制約条件のないブロックを検出する（Ｓ２１）。続いて、ブロック配置プログラムＰＲは、配置調整の必要のあるブロックが、配置交換されることでタイミング制約条件を満たす位置に配置されるタイミング制約条件のないブロックを検出する（Ｓ２２）。具体的に、ブロック配置プログラムＰＲは、マイナス値のブロックのタイミング制約条件を満たす配置可能領域、即ち、減算値がプラス値になる配置可能領域に位置するブロックであって、タイミング制約条件のないブロックを検出ブロックとして検出する。
【００６０】
続いて、ブロック配置プログラムＰＲは、マイナス値のブロックのうち、マイナスの度合いの大きいブロック、即ち、タイミング制約条件との乖離が大きいブロックから優先して、検出ブロックと配置交換していく（Ｓ２３）。また、このとき、マイナス値のブロックは、検出ブロックのうち、同じクロックドメインの検出ブロックと優先して配置交換される（Ｓ２４）。または、マイナス値のブロックは、検出ブロックのうち、同じクロックドメインのブロックが近くに配置される検出ブロックと優先的に配置交換される。
【００６１】
続いて、ブロック配置プログラムＰＲは、配置交換した両ブロックについて、同一のクロックドメインに属するブロックであるか否かを判定する（Ｓ２５）。同一のクロックドメインに属さない場合（Ｓ２５のＮＯ）、クロック配線が調整される（Ｓ２６）。
【００６２】
そして、ブロック配置プログラムＰＲは、マイナス値の他のブロックがあるか否かを判定する（Ｓ２７）。つまり、配置交換の必要性のあるブロックが存在するか否かを判定する。配置交換の必要性のあるブロックがまだ存在する場合（Ｓ２７のＹＥＳ）、続いて説明する第２の手法に基づいて配置交換が行われる。一方、配置交換の必要性のあるブロックが存在しない場合（Ｓ２７のＮＯ）、ブロック配置プログラムＰＲは処理を終了する。
【００６３】
続いて、ブロックの配置交換の第２の手法について説明する。
【００６４】
［ブロックの配置交換：第２の手法］
図８は、ブロックの配置交換処理の第２の手法について説明するフローチャート図である。第２の方法では、ブロック配置プログラムＰＲは、概算配置の結果、ブロックとそれに接続される入力端子とのマンハッタン長がタイミング制約条件を満たす概算配線長よりも長い対象ブロックと、当該対象ブロックのタイミング制約条件を満たす配置可能領域に配置されマンハッタン長がタイミング制約条件を満たす概算配線長と同じか短いブロックであってその配置可能領域に対象ブロックの配置位置を含むブロックとを配置交換する。つまり、マイナス値のブロックについて、マイナス値のブロックの配置可能領域に配置され、その配置可能領域にマイナス値のブロックの配置位置を含むタイミング制約条件を満たすブロックと配置交換される。
【００６５】
まず、ブロック配置プログラムＰＲは、図２のフローチャート図の工程Ｓ１４にて算出される概算配線長からマンハッタン長の減算値がプラス値であるブロック（以下、プラス値のブロック）について、ブロックの配置可能領域を算出する（Ｓ３１）。具体的に、ブロック配置プログラムＰＲは、プラス値のブロック、即ち、入力端子とのマンハッタン長に余裕があり、入力端子からより遠くの位置に配置可能なブロックについて、最大の配置可能領域を算出する。配置可能領域とは、プラス値のブロックのタイミング制約条件を満たす配置可能領域、即ち、概算配線長からマンハッタン長の減算値がプラス値に収まる領域を示す。
【００６６】
そして、ブロック配置プログラムＰＲは、プラス値の対象ブロックの配置可能領域に位置する、概算配線長からマンハッタン長の減算値がマイナス値であるブロック（検出ブロック）を検出する（Ｓ３２）。そして、ブロック配置プログラムＰＲは、マイナス値の検出ブロックのうち、プラス値の対象ブロックと配置交換することで、概算配線長からマンハッタン長の減算値がプラス値となるマイナス値の検出ブロックの組み合わせを全て検出して配置交換する（Ｓ３３）。つまり、ブロック配置プログラムＰＲは、マイナス値の検出ブロックのうち、その配置可能領域がプラス値のブロックの配置位置を含むブロックを検出し配置交換する。
【００６７】
また、このとき、プラス値の対象ブロックは、検出ブロックのうち、同じクロックドメインの検出ブロックと優先して配置交換される（Ｓ３４）。または、プラス値の対象ブロックは、検出ブロックのうち、同じクロックドメインのブロックが近くに配置される検出ブロックと優先的に配置交換される。なお、第１の手法と同様にして、複数のマイナス値の検出ブロックが交換候補となる場合、マイナスの度合いの大きいブロック、即ち、マンハッタン長の超過度合いの大きいブロックから優先して配置交換されてもよい。
【００６８】
続いて、ブロック配置プログラムＰＲは、第１の手法と同様にして、配置交換した両ブロックについて、同一のクロックドメインに属するブロックであるか否かを判定する（Ｓ３５）。同一のクロックドメインに属さない場合（Ｓ３５のＮＯ）、クロック配線が調整される（Ｓ３６）。
【００６９】
そして、ブロック配置プログラムＰＲは、全てのプラス値のブロックを対象として工程Ｓ３１〜Ｓ３６の処理を行い、マイナス値の他のブロックがあるか否かを判定する（Ｓ３７）。つまり、配置交換の必要性のあるブロックが残存するか否かを判定する。配置交換の必要性のあるブロックがまだ存在する場合（Ｓ３７のＹＥＳ）、続いて説明する第３の手法に基づいて配置交換が行われる。一方、配置交換の必要性のあるブロックが存在しない場合（Ｓ３７のＮＯ）、ブロック配置プログラムＰＲは処理を終了する。
【００７０】
続いて、ブロックの配置交換の第３の手法について説明する。
【００７１】
［ブロックの配置交換：第３の手法］
図９は、ブロックの配置交換処理の第３の手法について説明するフローチャート図である。第３の方法では、ブロック配置プログラムＰＲは、概算配置の結果、ブロックとそれに接続される入力端子とのマンハッタン長がタイミング制約条件を満たす概算配線距離よりも長い対象ブロックと、当該対象ブロックのタイミング制約条件を満たす配置可能領域に配置されるマンハッタン長が概算配線距離よりも長い別のブロックであって、その配置可能領域が対象ブロックの配置位置を含むブロックとを配置交換する。つまり、マイナス値のブロックについて、マイナス値のブロックの配置可能領域に配置され、その配置可能領域にマイナス値のブロックの配置位置を含む別のマイナス値のブロックと配置交換される。
【００７２】
まず、ブロック配置プログラムＰＲは、図２のフローチャート図の工程Ｓ１４にて算出される概算配線長からマンハッタン長の減算値がマイナス値であるブロック（マイナス値のブロック）について、配置交換することで互いの減算値をプラス値にする別のマイナス値のブロックを検出する（Ｓ４１）。具体的に、ブロック配置プログラムＰＲは、マイナス値の対象ブロックについて、減算値がプラス値に収まる配置可能領域を算出する。続いて、ブロック配置プログラムＰＲは、対象ブロックの配置可能領域に位置する別のマイナス値のブロックの配置可能領域をさらに算出し、その配置可能領域に対象のマイナス値のブロックの配置位置が含まれる別のブロック（検出ブロック）を検出する。
【００７３】
そして、ブロック配置プログラムＰＲは、マイナス値の対象ブロックとマイナス値の検出ブロックの組み合わせを全て配置交換する（Ｓ４２）。つまり、ブロック配置プログラムＰＲは、２つのマイナス値の対象ブロックを配置交換することで、互いの概算配線長からマンハッタン長の減算値を、マイナス値からプラス値にする。
【００７４】
また、このとき、マイナス値の対象ブロックは、検出ブロックのうち、同じクロックドメインの検出ブロックと優先して配置交換される（Ｓ４３）。または、対象ブロックは、検出ブロックのうち、同じクロックドメインのブロックが近くに配置される検出ブロックと優先的に配置交換される。なお、第１、２の手法と同様にして、複数のマイナス値の検出ブロックが交換候補となる場合、マイナスの度合いの大きいブロック、即ち、マンハッタン長の超過度合いの大きいブロックから優先して配置交換されてもよい。
【００７５】
続いて、ブロック配置プログラムＰＲは、第１、２の手法と同様にして、配置交換した両ブロックについて、同一のクロックドメインに属するブロックであるか否かを判定する（Ｓ４４）。同一のクロックドメインに属さない場合（Ｓ４４のＮＯ）、クロック配線が調整される（Ｓ４５）。
【００７６】
そして、ブロック配置プログラムＰＲは、全てのマイナス値のブロックを対象として工程Ｓ４１〜Ｓ４５の処理を行い、マイナス値の他のブロックがあるか否かを判定する（Ｓ４６）。つまり、配置交換の必要性のあるブロックが残存するか否かを判定する。配置交換の必要性のあるブロックがまだ存在する場合（Ｓ４６のＹＥＳ）、マニュアル調整、即ち、手動によって配置交換が行われる。一方、配置交換の必要性のあるブロックが存在しない場合（Ｓ４６のＮＯ）、ブロック配置プログラムＰＲは処理を終了する。これにより、全てのブロックについて、タイミング制約条件を満たすように配置交換が行われる。
【００７７】
このように、本実施の形態例におけるブロック配置プログラムＰＲによると、配置調整の必要性のあるブロックについて、タイミング制約条件を満たすように、配置可能領域の情報に基づいて自動的に配置交換処理が行われる。また、ブロック配置プログラムＰＲの処理を経た後に、配置調整の必要性のあるブロックが残存する場合であっても、その残存数は少ないため容易にマニュアル作業によって調整可能である。このため、マニュアル作業によって各ブロックを配置、または配置調整する場合に対して、フロアレイアウトに係る工数が大幅に低減される。また、本実施の形態例では、ブロックの配置可能領域、即ち、ブロックの入力信号のタイミング制約条件を満たす配置範囲情報に基づいて、交換対象のブロックが検出されることにより、より容易に配置交換が実現される。
【００７８】
［ブロックの配置交換の具体例］
図１０は、図７〜図９のフローチャート図で説明した第１〜第３の手法の具体例について説明する図である。同図は、概算配置された図５のブロックの配置例ＣＨに対して、第１〜第３の手法によって配置交換された後のブロックの配置例ＣＨ´を表す。まず、第１の手法について説明する。
【００７９】
図１０では、第１の手法によって、ブロックＣとブロックＱとが配置交換されている（Ｚ１）。この例において、ブロックＣはタイミング制約条件のないブロックである。一方、ブロックＱは、図６で前述したとおり（ｎ１）、入力端子ＩＯ＿３と接続される。そして、配置後のブロックＱと入力端子ＩＯ＿３とのマンハッタン長は９５０ｕｍであるのに対し、タイミング制約条件に基づく概算配線長１５０ｕｍである。このため、タイミング制約条件に基づく概算配線長１５０ｕｍからマンハッタン長９５０ｕｍの減算値が−８００ｕｍとなり、ブロックＱが、入力端子ＩＯ＿３の近くに配置される必要があることを示す。
【００８０】
そこで、ブロック配置プログラムＰＲは、ブロックＱの配置可能領域ｅＱを算出する。そして、ブロックＱの配置可能領域ｅＱ内に、タイミング制約条件のないブロックＣの配置位置が含まれることから、ブロックＱとブロックＣとが配置交換される（Ｚ１）。このとき、ブロックＣとブロックＱとは同一クロックドメインＤｘのブロックであるため、クロック配線の調整が不要になる。
【００８１】
続いて、第２の手法について説明する。図１０の例において、ブロックＬとブロックＺとが配置交換されている（Ｚ２）。この例において、図６に示すように、ブロックＺは入力端子ＩＯ＿３２と接続され、ブロックＺと入力端子ＩＯ＿３２とのマンハッタン長は４００ｕｍである。これに対し、ブロックＺの入力端子ＩＯ＿３２からの入力信号のタイミング制約条件に基づく概算配線長７５０ｕｍである。このため、タイミング制約条件に基づく概算配線長７５０ｕｍからマンハッタン長４００ｕｍの減算値が３５０ｕｍとなる。これは、ブロックＺが入力端子ＩＯ＿３２に対して、より遠くに配置可能であることを示す。
【００８２】
一方、図６に示すように（ｎ３）、ブロックＬは入力端子ＩＯ＿４０と接続され、ブロックＬと入力端子ＩＯ＿４０とのマンハッタン長は５５０ｕｍであるのに対しタイミング制約条件に基づく概算配線長１５０ｕｍである。これにより、タイミング制約条件に基づく概算配線長１５０ｕｍからマンハッタン長５５０ｕｍの減算値が−４００ｕｍとなる。即ち、ブロックＬは入力端子ＩＯ＿４０に対してより近い位置に配置される必要性がある。
【００８３】
そこで、ブロック配置プログラムＰＲは、より遠くに配置可能なブロックＺの配置可能領域ｅＺを算出する（Ｓ３１）。そして、ブロック配置プログラムＰＲは、配置可能領域ｅＺに位置するブロックであって、当該ブロックの配置可能領域（図示せず）にブロックＺの配置位置を含むブロックＬを検出する（Ｓ３２）。このとき、ブロックＺとブロックＬとは同一クロックドメインのブロックではないものの、ブロックＬは、配置可能領域ｅＺに位置するブロックのうち、ブロックＱに続いて、概算配線長からマンハッタン長の減算値のマイナスの度合いが大きい。そこで、ブロックＺとブロックＬとが配置交換される。これにより、ブロックＬの概算配線長からマンハッタン長の減算値がプラス値になると共に、ブロックＺについても概算配線長からマンハッタン長の減算値がプラス値のままとなる。
【００８４】
続いて、第３の手法について説明する。図１０の具体例において、ブロックβとブロックＶとが配置交換されている。この例において、図６に示すように（ｎ２）、ブロックβは入力端子ＩＯ＿３３と接続され、ブロックβと入力端子ＩＯ＿３３とのマンハッタン長は１８０ｕｍであるのに対しタイミング制約条件に基づく概算配線長１５０ｕｍである。これにより、タイミング制約条件に基づく概算配線長１５０ｕｍからマンハッタン長１８０ｕｍの減算値が−３０ｕｍとなる。即ち、ブロックβは入力端子ＩＯ＿３３に対してより近い位置に配置される必要性がある。また、図６に図示していないものの、ブロックＶは、入力端子ＩＯ＿４３と接続され、入力端子ＩＯ＿４３に対してより近い位置に配置される必要性がある。
【００８５】
そこで、ブロック配置プログラムＰＲは、ブロックβのタイミング制約条件を満たす配置可能領域ｅβに配置される減算値がマイナス値の別のブロック（ブロックＶ）であって、その配置可能領域ｅＶがブロックβの配置位置を含むブロックＶを検出し、配置交換を行う。これにより、ブロックβ、ブロックＶのそれぞれの概算配線長からマンハッタン長の減算値がプラス値になる。
【００８６】
以上のようにして、本実施の形態例における半導体集積回路のレイアウト装置１は、複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、ブロック群に含まれる１つまたは複数のブロックを、全てのブロックのうちサイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成し、単位ブロック内の各ブロックに対応する半導体集積回路（チップ）の入力端子の位置に基づいて、ブロック群内の単位ブロックを互いに近接して配置する。そして、半導体集積回路のレイアウト装置１は、単位ブロック毎に配置された各ブロックについて、各ブロックのそれぞれに接続される入力端子との配線長（マンハッタン長）がタイミング制約条件を満たす基準距離（概算配線長）よりも長いか否かを判定し、基準距離よりも長い第１のブロック（マイナス値のブロック）がタイミング制約条件を満たすように、第１のブロックのタイミング制約条件を満たす配置可能領域の情報に基づいて各ブロック間の配置交換を行う。
【００８７】
これにより、半導体集積回路のレイアウト装置１は、同一クロックドメインの単位ブロック毎に配置することにより、予め、同一のクロック信号が入力されるブロック同士を近くに配置することができ、クロックスキューが低減される。また、半導体集積回路のレイアウト装置１は、最大サイズのブロックに近似するように、同一のクロック信号が入力される１つまたは複数のブロックを組み合わせて単位ブロックを生成し、単位ブロック毎に配置する。これにより、ブロックの配置が整列され、ブロックの配線の凹凸が抑制され混線が回避される。
【００８８】
さらに、本実施の形態例における半導体集積回路のレイアウト装置１は、単位ブロック毎に概算配置した上で、各ブロックについて入力信号のタイミング制約条件を満たすように、ブロックの配置可能領域に基づいてブロック間の配置交換を自動的に行う。これにより、単位ブロック毎に配置されることにより接続対象の入力端子から遠い位置に配置され、タイミング制約条件を満たしていないブロックについて、ブロックの配置可能領域に基づいてブロック間の配置交換が行われる。予め、配線の混線やクロックのスキューが抑制されるように配置された上で、各ブロックが入力信号のタイミング制約条件を満たすように自動調整されるため、配線の混線やクロックのスキューが抑制される上、各ブロックのタイミング制約条件を満たすフロアプランが効率的に行われるため、工数が大幅に改善される。
【００８９】
また、本実施の形態例における配置交換では、第１のブロックのタイミング制約条件を満たす第１の配置可能領域に配置され配線長（マンハッタン長）が基準距離（概算配線長）と同じか短い第２のブロックであって、当該第２のブロックのタイミング制約条件を満たす第２の配置可能領域が第１のブロックの配置位置を含む第２のブロックと、第１のブロックとを配置交換する。つまり、配置調整の必要性のある第１のブロックが、その第１の配置可能領域に配置される配置調整の必要性のない第２のブロックであって、当該第２のブロックの概算配線長からマンハッタン長の減算値がプラス値に収まる第２の配置可能領域が第１のブロックの配置位置を含む場合に、当該第２のブロックと配置交換される。
【００９０】
これにより、各ブロックの配置可能領域に基づいて、簡易に配置調整が可能となる。具体的に、配置調整の必要のないブロックについて、その配置可能領域を利用して、配置調整の必要なブロックがタイミング制約条件を満たすように配置交換される。配置調整の必要のないブロックの配置可能領域に注目することによって、より多くの交換対象ブロックが抽出可能となる。これにより、より多くの配置調整が必要なブロックについてタイミング制約条件が満たされるように容易に配置交換可能になる。
【００９１】
また、本実施の形態例における配置交換では、第１のブロックのタイミング制約条件を満たす第１の配置可能領域に配置されるタイミング制約条件のない第３のブロックと、第１のブロックとを配置交換する。つまり、配置調整の必要性のある第１のブロックが、第１のブロックの概算配線長からマンハッタン長の減算値がマイナス値にならない配置可能領域に配置されるタイミング制約条件のない第３のブロックと配置交換されることによって、より簡易に配置交換される。タイミング制約条件のない第３のブロックは、いずれの位置にも配置可能であるため、より多くの配置調整が必要な第１のブロックを対象として配置交換が可能になる。このため、マンハッタン長が長くなり過ぎて配置調整が優先的に必要なブロックや、同一クロックドメインに属するブロックとの配置交換が容易になる。
【００９２】
また、本実施の形態例における配置交換では、第１のブロックのタイミング制約条件を満たす第１の配置可能領域に配置され配線長（マンハッタン長）が基準距離（概算配線長）よりも長い第４のブロックであって、当該第４のブロックのタイミング制約条件を満たす第４の配置可能領域が第１のブロックの配置位置を含む第４のブロックと、第１のブロックとを配置交換する。つまり、配置調整の必要性のある第１のブロックが、その第１の配置可能領域に配置される配置調整の必要性のある別の第４のブロックであって、当該第４のブロックの概算配線長からマンハッタン長の減算値がプラス値に収まる第４の配置可能領域が第１のブロックの配置位置を含む場合に、当該第４のブロックと配置交換される。
【００９３】
これにより、各ブロックの配置可能領域に基づいて、簡易に配置調整が可能となる。具体的に、配置調整の必要のあるブロックについて、その配置可能領域を利用して、別の配置調整の必要なブロックと、互いのタイミング制約条件を満たすように配置交換される。複数の配置調整の必要なブロックの配置可能領域に注目することによって、より多くの交換対象ブロックが抽出可能となる。これにより、より多くの配置調整の必要なブロックについてタイミング制約条件が満たされるように容易に配置交換可能になる。
【００９４】
また、ブロックの配置交換において、配線長（マンハッタン長）が基準距離（概算配線長）よりも長い第１のブロックが複数ある場合に、複数の第１のブロックのうち、タイミング制約条件との乖離が大きい第１のブロックが優先して配置交換される。これにより、より配置調整の必要性の高いブロックの優先的な配置交換が可能となる。さらに、ブロックの配置交換において、同一のブロック群のブロック間同士の配置交換が優先される。これにより、同一クロックドメインのブロック間の配置交換が優先的に行われるため、配置交換後のクロック配線の調整量が低減すると共に、クロックスキューが抑えられる。
【００９５】
以上の実施の形態をまとめると、次の付記のとおりである。
【００９６】
（付記１）
ネットリスト及びタイミング制約条件に基づいて、機能毎に分割された複数のブロックをチップに配置する半導体集積回路のレイアウト方法であって、
前記複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、前記ブロック群に含まれる１つまたは複数の前記ブロックを、全ての前記ブロックのうちサイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成する分類工程と、
前記単位ブロック内の前記各ブロックに対応する前記半導体集積回路の入力端子の位置に基づいて、前記ブロック群内の前記単位ブロックを互いに近接して配置する第１の配置工程と、
前記第１の配置工程によって配置された前記各ブロックについて、前記各ブロックのそれぞれに接続される前記入力端子との配線長が前記タイミング制約条件を満たす基準距離よりも長いか否かを判定し、前記基準距離よりも長い第１のブロックが前記タイミング制約条件を満たすように、前記第１のブロックの前記タイミング制約条件を満たす配置可能領域の情報に基づいて前記各ブロック間の配置交換を行う第２の配置工程と、を有することを特徴とする半導体集積回路のレイアウト方法。
【００９７】
（付記２）
付記１において、
前記第２の配置工程では、前記第１のブロックの前記タイミング制約条件を満たす第１の配置可能領域に配置され前記配線長が前記基準距離と同じか短い第２のブロックであって、当該第２のブロックの前記タイミング制約条件を満たす第２の配置可能領域が前記第１のブロックの配置位置を含む第２のブロックと、前記第１のブロックとを配置交換することを特徴とする半導体集積回路のレイアウト方法。
【００９８】
（付記３）
付記１または２において、
前記第２の配置工程では、前記第１のブロックの前記タイミング制約条件を満たす第１の配置可能領域に配置される前記タイミング制約条件のない第３のブロックと、前記第１のブロックとを配置交換することを特徴とする半導体集積回路のレイアウト方法。
【００９９】
（付記４）
付記１乃至３のいずれかひとつにおいて、
前記第２の配置工程では、前記第１のブロックの前記タイミング制約条件を満たす第１の配置可能領域に配置され前記配線長が前記基準距離よりも長い第４のブロックであって、当該第４のブロックの前記タイミング制約条件を満たす第４の配置可能領域が前記第１のブロックの配置位置を含む前記第４のブロックと、前記第１のブロックとを配置交換することを特徴とする半導体集積回路のレイアウト方法。
【０１００】
（付記５）
付記１乃至４のいずれかひとつにおいて、
前記第２の配置工程では、前記第１のブロックが複数ある場合に、前記複数の第１のブロックのうち、前記タイミング制約条件との乖離が大きい前記第１のブロックを優先して配置交換することを特徴とする半導体集積回路のレイアウト方法。
【０１０１】
（付記６）
付記１乃至５のいずれかひとつにおいて、
前記第２の配置工程では、同一の前記ブロック群内の前記各ブロック間について優先して配置交換することを特徴とする半導体集積回路のレイアウト方法。
【０１０２】
（付記７）
付記１乃至６のいずれかひとつにおいて、
前記第１の配置工程は、前記ブロック群内の前記単位ブロックを、Ｘ方向、またはＹ方向に配置することを特徴とする半導体集積回路のレイアウト方法。
【０１０３】
（付記８）
ネットリスト及びタイミング制約条件に基づいて、機能毎に分割された複数のブロックを配置するレイアウト処理をコンピュータに実行させるコンピュータ読み取り可能な半導体集積回路のレイアウトプログラムであって、
前記レイアウト処理は、
前記複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、前記ブロック群に含まれる１つまたは複数の前記ブロックを、全ての前記ブロックのうちサイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成する分類工程と、
前記単位ブロック内の前記各ブロックに対応する前記半導体集積回路の入力端子の位置に基づいて、前記ブロック群内の前記単位ブロックを互いに近接して配置する第１の配置工程と、
前記第１の配置工程によって配置された前記各ブロックについて、前記各ブロックのそれぞれに接続される前記入力端子との配線長が前記タイミング制約条件を満たす基準距離よりも長いか否かを判定し、前記基準距離よりも長い第１のブロックが前記タイミング制約条件を満たすように、前記第１のブロックの前記タイミング制約条件を満たす配置可能領域の情報に基づいて前記各ブロック間の配置交換を行う第２の配置工程と、を有することを特徴とする半導体集積回路のレイアウトプログラム。
【０１０４】
（付記９）
ネットリスト及びタイミング制約条件に基づいて、機能毎に分割された複数のブロックを配置する半導体集積回路のレイアウト装置であって、
前記複数のブロックを、同一のクロック信号が入力されるブロック群に分類し、前記ブロック群に含まれる１つまたは複数の前記ブロックを、全ての前記ブロックのうちサイズが最大のブロックと同等かそれ以下のサイズになるように組み合わせて単位ブロックを生成する分類手段と、
前記単位ブロック内の前記各ブロックに対応する前記半導体集積回路の入力端子の位置に基づいて、前記ブロック群内の前記単位ブロックを互いに近接して配置する第１の配置手段と、
前記第１の配置手段によって配置された前記各ブロックについて、前記各ブロックのそれぞれに接続される前記入力端子との配線長が前記タイミング制約条件を満たす基準距離よりも長いか否かを判定し、前記基準距離よりも長い第１のブロックが前記タイミング制約条件を満たすように、前記第１のブロックの前記タイミング制約条件を満たす配置可能領域の情報に基づいて前記各ブロック間の配置交換を行う第２の配置手段と、を有することを特徴とする半導体集積回路のレイアウト装置。
【符号の説明】
【０１０５】
１１：ＣＰＵ、１２：メモリ、１３：出力部、１４：入力部、１５：バス線、ＰＲ：ブロック配置プログラム、ＮＬ：ネットリスト、ＴＳ：タイミングスクリプト、ＬＢ：ライブラリ
【図１】
2014056522.tif 000003
【図２】
2014056522.tif 000004
【図３】
2014056522.tif 000005
【図４】
2014056522.tif 000006
【図５】
2014056522.tif 000007
【図６】
2014056522.tif 000008
【図７】
2014056522.tif 000009
【図８】
2014056522.tif 000010
【図９】
2014056522.tif 000011
【図１０】
2014056522.tif 000012