(57)【要約】【課題】ツリー構造型回路を生成するにあたって、レイアウトに最適化したツリー形状を作成すること。また、分配回路の挿入による回路素子の増加量や、分配回路による配線リソースの消費量を正確に見積もること。【解決手段】ＬＳＩの分割対象領域を複数の領域に分割し、それによってできた各領域に、分配対象となる構成素子を配置する（ステップＳ１１）。つづいて、ツリーを生成し（ステップＳ１２）、概略配線をおこない（ステップＳ１３）、クロック位相差を考慮してタイミング改善処理をおこなう（ステップＳ１４）。以上の処理を、予め設定された回数だけ繰り返しおこない（ステップＳ１５）、その繰り返しの回数が規定回数に達したら、構成素子および追加されたバッファ等の詳細配置をおこない（ステップＳ１６）、自動配線をおこなう（ステップＳ１７）。【選択図】　　　　図１
2004022864.tif 000002
【特許請求の範囲】
【請求項１】
ツリー状の分配構造を有する回路を生成するにあたって、
分割対象領域を複数の領域に分割し、当該分割によって新たにできた各領域に、分配対象となる構成素子を分配する第１の工程と、
前記各領域についてツリーを生成する第２の工程と、
生成したツリーに基づいて概略配線をおこなう第３の工程と、
前記構成素子および前記ツリーの生成時に追加された素子の詳細配置をおこなう第４の工程と、
を含むことを特徴とするツリー構造型回路生成方法。
【請求項２】
前記詳細配置された素子に対して自動配線をおこなう第５の工程をさらに有することを特徴とする請求項１に記載のツリー構造型回路生成方法。
【請求項３】
分配対象となる構成素子のうち、同一の領域に含まれ、かつ同一のソースから分配された構成素子を、等価であるとみなすことを特徴とする請求項１または２に記載のツリー構造型回路生成方法。
【請求項４】
前記第１の工程から前記第３の工程までを、予め設定された回数だけ繰り返した後、前記第４の工程をおこなうことを特徴とする請求項１〜３のいずれか一つに記載のツリー構造型回路生成方法。
【請求項５】
ツリー状の分配構造を有する回路を生成するにあたって、
分割対象領域を複数の領域に分割し、当該分割によって新たにできた各領域に、分配対象となる構成素子を分配する第１の工程と、
前記各領域についてツリーを生成する第２の工程と、
生成したツリーに基づいて概略配線をおこなう第３の工程と、
概略配線に基づいてタイミング改善処理をおこなう第４の工程と、
前記構成素子および前記ツリーの生成時に追加された素子の詳細配置をおこなう第５の工程と、
を含むことを特徴とするツリー構造型回路生成方法。
【請求項６】
前記詳細配置された素子に対して自動配線をおこなう第６の工程をさらに有することを特徴とする請求項５に記載のツリー構造型回路生成方法。
【請求項７】
分配対象となる構成素子のうち、同一の領域に含まれ、かつ同一のソースから分配された構成素子を、等価であるとみなすことを特徴とする請求項５または６に記載のツリー構造型回路生成方法。
【請求項８】
前記第１の工程から前記第４の工程までを、予め設定された回数だけ繰り返した後、前記第５の工程をおこなうことを特徴とする請求項５〜７のいずれか一つに記載のツリー構造型回路生成方法。
【請求項９】
前回のサイクルにおいて増加した回路を、領域分割により新たに生成される各領域に、当該各領域に割り振られる、分配対象となる構成素子の数に比例して、割り振ることを特徴とする請求項４または８に記載のツリー構造型回路生成方法。
【請求項１０】
ツリー状の分配構造を有する回路を生成するにあたって、分割対象領域を複数の領域に分割させ、当該分割によって新たにできた各領域に、分配対象となる構成素子を分配させる第１の工程と、
前記各領域についてツリーを生成させる第２の工程と、
生成したツリーに基づいて概略配線をおこなわせる第３の工程と、
前記構成素子および前記ツリーの生成時に追加された素子の詳細配置をおこなわせる第４の工程と、
をコンピュータに実行させることを特徴とするツリー構造型回路生成プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ツリー状の分配構造を有するツリー構造型回路生成方法およびツリー構造型回路生成プログラムに関し、特にクロック・ツリー法により設計されるクロック回路等のツリー構造型回路におけるツリー構造型回路生成方法およびツリー構造型回路生成プログラムに関する。
【０００２】
一般に、ＬＳＩのレイアウト設計において、クロック・スキュー対策としてクロック・ツリー法により、クロック回路をツリー型構造の回路で構成することがある。従来より、このようなツリー構造型回路は、レイアウト用のツールなどにより自動的に生成される。
【０００３】
【従来の技術】
たとえば、ツリー構造型のクロック回路を生成する方法として、つぎの二つの方法がある。第１の方法は、レイアウト前にツリー回路を生成する方法である。すなわち、図１０に示すフローチャートにしたがって、まず、図１１に示すようにツリー構造を生成する（ステップＳ１０１）。その後、そのツリー構造の分配回路に対して、図１２に示すように、クロックの位相差を考慮しないタイミングドリブン配置をおこない（ステップＳ１０２）、配置されたバッファや回路素子等に対して配線をおこなう（ステップＳ１０３）。
【０００４】
第２の方法は、初期レイアウト後にツリー回路を生成する方法である。すなわち、図１３に示すフローチャートにしたがって、まず、ツリー構造を考慮せずに、図１４に示すように回路のタイミングドリブン配置をおこなう（ステップＳ１３１）。この初期配置におけるタイミング考慮は、クロック位相差がないとするか、または一定マージンであるとする。その後、図１５に示すようにツリー構造を生成し、配置、配線をおこなう（ステップＳ１３２）。その際、ツリー構造は、分配先回路のレイアウトに合わせて最適化されるので、配線リソースの消費が最低限に抑えられる。その後、ツリー構造に基づいて、クロックの実位相差を考慮してタイミングドリブン配置の改善をおこない（ステップＳ１３３）、配線をおこなう（ステップＳ１３４）。
【０００５】
【発明が解決しようとする課題】
しかしながら、上述した従来の第１の方法では、図１１に示すように、ツリー構造が、分配回路の終端に位置する「ａ」、「ｂ」、「ｃ」、「ｘ」、「ｙ」および「ｚ」の各素子１１，１２，１３，１４，１５，１６の座標を考慮しない構造となってしまい、最適なツリー形状とならない。そのため、実際のレイアウトでは、図１２に示す「ｃ］や「ｚ」の素子１３，１６のように、遠いバッファ１７，１８を介してクロック供給元の回路１９に接続され、そのため配線長が他よりも長くなる素子が存在することがあり、位相差が大きく、配線リソースの消費が多く、高集積レイアウトをおこなえないという問題がある。
【０００６】
また、従来の方法では、ツリー生成後に配置改善をおこなっている。初期配置段階では、挿入される回路の規模やそれらが必要とする配置・配線リソースの位置が不明であるため、ツリー生成後にレイアウト不能となる場合があるという問題点がある。
【０００７】
本発明は、上記問題点に鑑みてなされたものであって、レイアウトに最適化したツリー形状を作成することができるとともに、分配回路の挿入による回路素子の増加量や、分配回路による配線リソースの消費量を正確に見積もることができるツリー構造型回路生成方法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、本発明は、トップダウンに素子の配置座標を決定する自動配置（Ｍｉｎ−Ｃｕｔアルゴリズムなどによる）の処理途中で、ツリー状の分配回路を生成することを特徴とする。
【０００９】
すなわち、図１に示すフローチャートのように、まず、ＬＳＩの分割対象領域を複数の領域に分割し、その分割によって新たにできた各領域に、分配対象であるＬＳＩの構成素子を領域に分配する（ステップＳ１１）。つづいて、ツリーを生成し（ステップＳ１２）、概略配線をおこなう（ステップＳ１３）。そして、必要に応じて、クロック位相差を考慮してタイミング改善処理をおこなう（ステップＳ１４）。以上の処理を、ＬＳＩの領域を繰り返し分割する回数（予め設定されている）だけ繰り返しおこなう（ステップＳ１５）。繰り返しの回数が規定回数に達したら、構成素子および追加されたバッファ等の詳細配置をおこなう（ステップＳ１６）。ここまでがタイミングドリブン自動配置処理である。最後に、自動配線をおこなう（ステップＳ１７）。
【００１０】
この発明によれば、ＬＳＩを構成する素子の配置座標をトップダウンに決定する自動配置処理の途中で、ツリー状の分配回路が生成される。
【００１１】
【発明の実施の形態】
以下に、本発明の実施の形態について図面を参照しつつ詳細に説明する。図２は、本発明方法の実施に供せられる自動レイアウトツールの機能構成の概略を示す図である。図２に示すように、自動レイアウトツールは、配線機能部２１、配置機能部２２、ツリー生成機能部２３およびタイミング改善機能部２４が共通データ２５にアクセスすることによって、最新のレイアウトデータおよびツリー生成による回路量増加等の見積もり結果を知ることができる構成となっている。
【００１２】
図３および図４は、本発明にかかるツリー構造型回路生成方法を適用して、ＬＳＩの構成素子をトップダウンに配置する際の、クロック回路の生成手順を示すフローチャートである。
【００１３】
図３に示すように、クロック回路の生成処理が開始されると、まず、制御カード３１から設計条件等の制御データを読み込む（ステップＳ３１）。そして、その制御データに、ＬＳＩの領域を繰り返し分割する回数（以下、繰り返し回数とする）が定義されているか否かの判定をおこなう（ステップＳ３２）。判定の結果、繰り返し回数が定義されていない場合には、繰り返し回数を回路規模に基づいて自動算出する（ステップＳ３３）。あるいは、オペレータが、図示しないキーボード等の入力手段を用いて、繰り返し回数を指示するようにしてもよい。
【００１４】
このようにして繰り返し回数が決定したら、ＬＳＩ構成素子のタイミングドリブン配置処理へ移行する（ステップＳ３４）。また、ステップＳ３２の判定処理において、制御データに繰り返し回数が定義されている場合は、そのままステップＳ３４のタイミングドリブン配置処理へ移行する。
【００１５】
ここで、ＬＳＩの領域を繰り返し分割する例として、２分割を繰り返す例を図６に模式的に示す。この場合、図６に示すように、ＬＳＩの全体領域６１は、１回目の分割により第１の領域６２と第２の領域６３の二つの領域に分割される。そして、２回目の分割により、第１の領域６２は第３の領域６４と第４の領域６５の二つの領域に分割されるとともに、第２の領域６３は第５の領域６６と第６の領域６７の二つの領域に分割される。繰り返し回数が３回以上である場合、３回目以降も同様に分割が繰り返される。２分割に限らず、３分割、４分割など、分割対象領域をいくつの領域に分割するかは任意である。
【００１６】
上述した図３、ステップＳ３４のタイミングドリブン配置処理へ移行すると、図４に示すように、まずＬＳＩの全体領域６１に対して１回目の領域分割処理をおこない、分割された各領域にＬＳＩの構成素子を分配する（ステップＳ４１、図６参照）。その際、分配対象となる構成素子の座標は詳細には決まっていないため、図６に示すように、各分割領域に含まれる構成素子６８ａ，６８ｂ，６８ｃ，６８ｄは、それぞれの分割領域の中央にあるものと仮定する。
【００１７】
図４に戻り、ステップＳ４１の領域分割処理につづいて、ツリーの生成処理をおこなう（ステップＳ４２）。その際、生成されたツリー上のバッファの配置座標については、分割された領域の中央の座標と仮定してもよいし、分割領域内のある座標に定めてもよい。また、ツリー生成処理の手法は、トップダウンでもよいし、ボトムアップでもよい。生成したツリーに基づいて、位相差情報４１、ネット情報４２およびセル情報４３を得、そのうちネット情報４２およびセル情報４３に基づいて概略配線をおこなう（ステップＳ４３）。つづいて、制御カード３１より与えられる制御データに基づいて、タイミング改善処理の実行の有無を判定する（ステップＳ４４）。
【００１８】
ステップＳ４４での判定の結果、タイミング改善処理をおこなう場合には、タイミング改善処理をおこなう（ステップＳ４５）。その際、制御カード３１より与えられる制御データに基づいて、クロック位相差を考慮することが指示されている場合には、前記位相差情報４１に基づいて、タイミング改善処理をおこなう。その後、図３に示すフローチャートのステップＳ３１〜Ｓ３３において自動算出またはオペレータによる入力により規定された繰り返し回数だけ、上述したステップＳ４１〜Ｓ４５の処理がおこなわれたか否かを判定する（ステップＳ４６）。
【００１９】
ステップＳ４４での判定の結果、タイミング改善処理をおこなわない場合には、ステップＳ４５をとばしてステップＳ４６の判定処理へ移行する。この場合には、レイアウトに最適なツリーが生成され、配線機能部２１および配置機能部２２（図２参照）には、ツリー生成による素子および配線の増加量が反映されるだけである。
【００２０】
ステップＳ４６での判定の結果、規定された繰り返し回数に達していない場合には、ステップＳ４１〜Ｓ４６を繰り返す。すなわち、２回目のサイクルの領域分割処理をおこない、分割された領域についてツリーを生成し、概略配線をおこない、タイミング改善処理をおこなう場合にはそれをおこない、再び規定の繰り返し回数に達したか否かを判定する。３回目以降のサイクルに関しても同様であり、ステップＳ４６において、規定された繰り返し回数に達したと判定されるまで、ステップＳ４１〜Ｓ４６を繰り返す。２回目以降のサイクルの領域分割処理をおこなうときには、前回の領域分割時に得られた前記セル情報４３が参照される。
【００２１】
そして、規定された繰り返し回数に達したら、ＬＳＩの構成素子や追加されたバッファなどの配置を詳細におこない、それらの座標を決める（ステップＳ４７）。その後、詳細配置に基づいて、自動配線処理をおこない（ステップＳ４８）、ＬＳＩの構成素子のタイミングドリブン自動配置および自動配線の処理が終了する。
【００２２】
ここで、ステップＳ４２で生成されたツリー上のバッファの配置座標が定められていなくてもよい。この場合には、そのバッファは、そのバッファが存在する現在の領域をつぎのサイクルの領域分割処理によってさらに分割してできたいずれかの区画に含められ、当初の座標位置から移動する。そして、最終的には、ステップＳ４７の詳細配置処理において、そのバッファの配置座標が決定される。
【００２３】
また、１回目の領域分割処理から規定の繰り返し回数に達するまでのすべてのサイクルにおいて、ステップＳ４５のタイミング改善処理の際にクロック位相差を考慮する必要はない。つまり、タイミング改善処理においてクロック位相差を考慮するか否かは任意であり、ステップＳ４１〜Ｓ４６の繰り返しサイクルの中で、あるサイクル（たとえば３サイクル）まではクロック位相差を考慮せずにタイミング改善処理をおこない、そのつぎのサイクル（たとえば４サイクル）からタイミング改善処理時にクロック位相差を考慮するようにすることができる。
【００２４】
また、２回目以降のサイクルでは、ステップＳ４２のツリー生成処理において、前回のサイクルのときに見積もった内容を継承する必要があるため、図７に示すように、前回のサイクル時のレイアウト状態（ツリー形状）を意識したツリー生成をおこなう。図７は、ツリー生成において前回のサイクルでの経路を継承した様子を模式的に示す図であり、同図において、符号７１はｎ回目の分割後の領域であり、符号７２、７３、７４、および７５はｎ＋１回目の分割後の領域である。また、符号７６ａ、７６ｂ、７６ｃ、７６ｄ、７６ｅ、７６ｆおよび７６ｇは追加されたバッファである。
【００２５】
また、図８の８９から見て、分配対象となる素子（８１〜８６）の入力が、第１に、極性が同一であること、すなわち論理的反転・非反転が同じことと、第２に、途中に他入力セルを通過しないことの両方をともに満たせば、これらの構成素子は等価なものとみなされる。したがって、図８に示すように、ソース８９からバッファ８７，８８を介して末端の構成素子８１，８２，８３，８４，８５，８６までの接続情報は意味を持たないので、たとえば図示例のように、ｎ回目のサイクルのツリーで「１」のバッファ８７に接続されていた「ｃ」の素子８３と、「２」のバッファ８８に接続されていた「ｚ」の素子８６とが、ｎ＋１回目のサイクルで入れ代わってもよい。これは、つぎのサイクルでより詳細に領域分割をおこなうときに、領域の分割の仕方が構成素子の接続関係の影響を受けないことを意味する。
【００２６】
図５は、本発明にかかるツリー構造型回路生成方法の２回目以降のサイクルにおけるツリー生成処理の詳細を示すフローチャートである。２回目以降のサイクルでは、まず、前回のサイクルで得られた結果５１および新レイアイウト５２に基づいて、前回のサイクルまでに作成したツリーの確定部分の修正をおこなう（ステップＳ５１）。この修正処理は、制御カード３１より与えられる制御データに基づいて実施される。つづいて、規定段数分の未確定部分のツリーを生成する（ステップＳ５２）。このときの段数は、制御カード３１より与えられる制御データに基づいて規定される。
【００２７】
つづいて、分配回路のタイミング調整をおこなう（ステップＳ５３）。このタイミング調整処理は、任意のサイクルにおいて実施可能であり、その実施の有無は、制御カード３１より与えられる制御データに基づいて決められる。つづいて、新規に作成した部分のツリーを確定する（ステップＳ５４）。そして、未定部分のツリーを生成し（ステップＳ５５）、位相差情報４１、追加ネット情報５３および追加セル情報５４を得て、概略配線処理へ進む。
【００２８】
つぎに、上述した回路生成方法において、ツリー構造の分配を意識した素子のトップダウン配置方法について説明する。前回のサイクルにおいて増加した回路は、今回のサイクルの領域分割処理において、分割により新たにできる各領域に割り振られる。その際、分割により新たにできた各領域には、それぞれの領域に含まれる、分配対象となる構成素子の数に比例して、前回のサイクルにおいて増加した回路が割り振られる。
【００２９】
たとえば、図９に示すように、同図左側に示す領域９１の右上の区画９２を、さらに同図右側に示す四つの区画９３，９４，９５，９６に分割した場合について説明する。前回のサイクルにおいて、左側に示す領域９１の右上の区画９２には、今後１００個のバッファが発生すると予測されているとする。そして、左側に示す領域９１の右上の区画９２に含まれている、分配対象となる構成素子のうち、今回のサイクルの領域分割処理により、その１０％が右側に示す左上の区画９３と右上の区画９４に割り振られ、２０％が左下の区画９５に割り振られ、６０％が右下の区画９６に割り振られるとする。
【００３０】
この場合には、図９の左側に示す領域９１の右上の区画９２に発生する１００個のバッファのうち、１０個が右側に示す左上の区画９３と右上の区画９４にそれぞれ割り振られ、２０個が左下の区画９５に割り振られ、６０個が右下の区画９６に割り振られることになる。これは、当初１００個のバッファを用いて駆動すべき素子が、新たな領域分割により、上述した比率で、図９の右側に示す四つの区画９３，９４，９５，９６に振り分けられた場合、その四つの区画９３，９４，９５，９６において、それぞれ振り分けられた素子を駆動するのに必要となるバッファ数は、おおよそその振り分けた比率に比例するからである。
【００３１】
以上説明したツリー構造型回路生成方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、上記記録媒体を介して、インターネットなどのネットワークを介して配布することができる。
【００３２】
上述した実施の形態によれば、ＬＳＩを構成する素子の配置座標をトップダウンに決定する自動配置処理の途中で、ツリー状の分配回路が生成されるので、レイアウトに最適化したツリー形状を作成することができるとともに、分配回路の挿入による回路素子の増加量や、分配回路による配線リソースの消費量を正確に見積もることができる。また、配置が完了する前にクロックの位相差を調べてタイミング調整をおこなうことができるので、タイミングドリブン配置の完了後にタイミングエラーが起こるのを抑止することができる。
【００３３】
以上において本発明は、クロック回路の生成に限らず、クロック回路以外のツリー構造型回路の生成にも適用できる。
【００３４】
（付記１）ツリー状の分配構造を有する回路を生成するにあたって、
分割対象領域を複数の領域に分割し、当該分割によって新たにできた各領域に、分配対象となる構成素子を分配する第１の工程と、
前記各領域についてツリーを生成する第２の工程と、
生成したツリーに基づいて概略配線をおこなう第３の工程と、
前記構成素子および前記ツリーの生成時に追加された素子の詳細配置をおこなう第４の工程と、
を含むことを特徴とするツリー構造型回路生成方法。
【００３５】
（付記２）前記詳細配置された素子に対して自動配線をおこなう第５の工程をさらに有することを特徴とする付記１に記載のツリー構造型回路生成方法。
【００３６】
（付記３）前記第１の工程において、分配対象となる構成素子の座標を、当該構成素子が含まれる領域の中央にあるものとして扱うことを特徴とする付記１または２に記載のツリー構造型回路生成方法。
【００３７】
（付記４）前記第２の工程において追加された素子の座標を、当該素子が含まれる領域の中央にあるものとして扱うことを特徴とする付記１〜３のいずれか一つに記載のツリー構造型回路生成方法。
【００３８】
（付記５）分配対象となる構成素子のうち、同一の領域に含まれ、かつ同一のソースから分配された構成素子を、等価であるとみなすことを特徴とする付記１〜４のいずれか一つに記載のツリー構造型回路生成方法。
【００３９】
（付記６）前記第１の工程から前記第３の工程までを、予め設定された回数だけ繰り返した後、前記第４の工程をおこなうことを特徴とする付記１〜５のいずれか一つに記載のツリー構造型回路生成方法。
【００４０】
（付記７）ツリー状の分配構造を有する回路を生成するにあたって、
分割対象領域を複数の領域に分割し、当該分割によって新たにできた各領域に、分配対象となる構成素子を分配する第１の工程と、
前記各領域についてツリーを生成する第２の工程と、
生成したツリーに基づいて概略配線をおこなう第３の工程と、
概略配線に基づいてタイミング改善処理をおこなう第４の工程と、
前記構成素子および前記ツリーの生成時に追加された素子の詳細配置をおこなう第５の工程と、
を含むことを特徴とするツリー構造型回路生成方法。
【００４１】
（付記８）前記詳細配置された素子に対して自動配線をおこなう第６の工程をさらに有することを特徴とする付記７に記載のツリー構造型回路生成方法。
【００４２】
（付記９）前記第１の工程において、分配対象となる構成素子の座標を、当該構成素子が含まれる領域の中央にあるものとして扱うことを特徴とする付記７または８に記載のツリー構造型回路生成方法。
【００４３】
（付記１０）前記第２の工程において追加された素子の座標を、当該素子が含まれる領域の中央にあるものとして扱うことを特徴とする付記７〜９のいずれか一つに記載のツリー構造型回路生成方法。
【００４４】
（付記１１）分配対象となる構成素子のうち、同一の領域に含まれ、かつ同一のソースから分配された構成素子を、等価であるとみなすことを特徴とする付記７〜１０のいずれか一つに記載のツリー構造型回路生成方法。
【００４５】
（付記１２）前記第１の工程から前記第４の工程までを、予め設定された回数だけ繰り返した後、前記第５の工程をおこなうことを特徴とする付記７〜１１のいずれか一つに記載のツリー構造型回路生成方法。
【００４６】
（付記１３）前記第２の工程の初めに、前回のサイクルまでに作成したツリーの確定部分の修正をおこなうことを特徴とする付記６または１２に記載のツリー構造型回路生成方法。
【００４７】
（付記１４）前回のサイクルにおいて増加した回路を、領域分割により新たに生成される各領域に、当該各領域に割り振られる、分配対象となる構成素子の数に比例して、割り振ることを特徴とする付記６、１２または１３に記載のツリー構造型回路生成方法。
【００４８】
（付記１５）ツリー状の分配構造を有する回路を生成するにあたって、
分割対象領域を複数の領域に分割させ、当該分割によって新たにできた各領域に、分配対象となる構成素子を分配させる第１の工程と、
前記各領域についてツリーを生成させる第２の工程と、
生成したツリーに基づいて概略配線をおこなわせる第３の工程と、
前記構成素子および前記ツリーの生成時に追加された素子の詳細配置をおこなわせる第４の工程と、
をコンピュータに実行させることを特徴とするツリー構造型回路生成プログラム。
【００４９】
（付記１６）ツリー状の分配構造を有する回路を生成するにあたって、
分割対象領域を複数の領域に分割させ、当該分割によって新たにできた各領域に、分配対象となる構成素子を分配させる第１の工程と、
前記各領域についてツリーを生成させる第２の工程と、
生成したツリーに基づいて概略配線をおこなわせる第３の工程と、
概略配線に基づいてタイミング改善処理をおこなわせる第４の工程と、
前記構成素子および前記ツリーの生成時に追加された素子の詳細配置をおこなわせる第５の工程と、
をコンピュータに実行させることを特徴とするツリー構造型回路生成プログラム。
【００５０】
【発明の効果】
本発明によれば、レイアウトに最適化したツリー形状を作成することができるとともに、分配回路の挿入による回路素子の増加量や、分配回路による配線リソースの消費量を正確に見積もることができる。また、本発明によれば、タイミングドリブン配置をおこなう場合、配置完了後にタイミングエラーが起こるのを抑止することができる。
【図面の簡単な説明】
【図１】本発明にかかるツリー構造型回路生成方法を示すフローチャートである。
【図２】本発明にかかるツリー構造型回路生成方法の実施に供せられる自動レイアウトツールの機能構成を示す概略図である。
【図３】本発明にかかるツリー構造型回路生成方法を適用してクロック回路を生成する手順の一部を示すフローチャートである。
【図４】本発明にかかるツリー構造型回路生成方法を適用してクロック回路を生成する手順の一部を示すフローチャートである。
【図５】本発明にかかるツリー構造型回路生成方法の２回目以降のサイクルにおけるツリー生成処理の詳細を示すフローチャートである。
【図６】本発明にかかるツリー構造型回路生成方法を実施した際の回路分割とレイアウトイメージを模式的に示す図である。
【図７】本発明にかかるツリー構造型回路生成方法のツリー生成処理において前回のサイクルでの経路を継承した様子を模式的に示す図である。
【図８】本発明にかかるツリー構造型回路生成方法のツリー生成過程において等価接続された構成素子を交換した様子を模式的に示す図である。
【図９】本発明にかかるツリー構造型回路生成方法の領域分割処理において回路増加量の見積もりを継承する方法について説明するための図である。
【図１０】従来のクロック回路生成方法の第１の方法を示すフローチャートである。
【図１１】従来のクロック回路生成方法の第１の方法により生成されたツリー構造を模式的に示す図である。
【図１２】従来のクロック回路生成方法の第１の方法により生成されたレイアウトを模式的に示す図である。
【図１３】従来のクロック回路生成方法の第２の方法を示すフローチャートである。
【図１４】従来のクロック回路生成方法の第２の方法により生成されたレイアウトを模式的に示す図である。
【図１５】従来のクロック回路生成方法の第２の方法により生成されたツリー構造を模式的に示す図である。
【符号の説明】
６１〜６３，７１，９２　分割対象領域
６２〜６７，７２〜７５，９３〜９６　分割によって新たにできた領域
６８ａ〜６８ｄ，８１〜８６　分配対象となる構成素子
７６ａ〜７６ｇ　前回のサイクルにおいて増加した回路（バッファ）
８９　ソース
【図１】
2004022864.tif 000003
【図２】
2004022864.tif 000004
【図３】
2004022864.tif 000005
【図４】
2004022864.tif 000006
【図５】
2004022864.tif 000007
【図６】
2004022864.tif 000008
【図７】
2004022864.tif 000009
【図８】
2004022864.tif 000010
【図９】
2004022864.tif 000011
【図１０】
2004022864.tif 000012
【図１１】
2004022864.tif 000013
【図１２】
2004022864.tif 000014
【図１３】
2004022864.tif 000015
【図１４】
2004022864.tif 000016
【図１５】
2004022864.tif 000017