(57)【要約】【課題】レイアウト済みのセルのタイミング関係を崩すことなく所望のセルを追加配置可能なレイアウトを行う。【解決手段】あらたなセル（追加セル）を追加する際に、配置可能な空き領域が無い場合には、レイアウト済みのセルの中から、最も信号伝搬のタイミングに影響しないセルを、あらたなセルを配置するための空き領域を用意するための移動対象セルとして選択する。選択されたセルを移動させた空き領域にあらたなセルを配置することによって、追加セルの挿入に伴うタイミング調整を不要もしくは必要最低限に留めることができる。【選択図】図１
2010204749.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
半導体回路を構成するセル群の配置状態を表すレイアウト情報と、前記セル群に含まれるセルの種類に応じて設定された優先度情報と、を取得する取得手段、
前記レイアウト情報に含まれるセル群の中の任意のセルに対応して配置させる追加セルの情報を受け付ける受付手段、
前記追加セルを配置可能な空き領域があるか否かを判断する判断手段、
前記判断手段によって、前記追加セルを配置可能な空き領域がないと判断された場合、前記任意のセルからの距離と前記優先度情報とに基づいて、移動対象セルを抽出する抽出手段、
前記抽出手段によって抽出された移動対象セルを配置可能な空き領域を探索する探索手段、
前記探索手段によって空き領域が探索された場合、前記移動対象セルを前記空き領域に移動させる移動手段、
前記移動手段によって前記空き領域に移動された移動対象セルが配置されていた位置に、前記追加セルを配置する再配置手段、
前記再配置手段によって追加セルが配置された前記半導体回路のレイアウト情報を出力する出力手段、
として機能させることを特徴とするレイアウト支援プログラム。
【請求項２】
前記探索手段は、前記抽出手段によって抽出された移動対象セルから所定の範囲内を対象に当該移動対象セルを配置可能な空き領域を探索することを特徴とする請求項１に記載のレイアウト支援プログラム。
【請求項３】
前記探索手段は、前記移動対象セルを配置可能な空き領域が探索されなかった場合、当該空き領域が探索されるまで、前記所定の範囲を特定のサイズごとに拡大することを特徴とする請求項２に記載のレイアウト支援プログラム。
【請求項４】
前記探索手段は、前記移動対象セルの前段に接続されたセルからの伝搬時間に比例した範囲の中から前記移動対象セルを配置可能な空き領域を探索することを特徴とする請求項１〜３のいずれか一つに記載のレイアウト支援プログラム。
【請求項５】
前記抽出手段は、前記探索手段によって空き領域が探索されなかった場合、さらに、前記抽出された移動対象セルからの距離と、前記優先度情報とに基づいてあらたな移動対象セルを抽出し、
前記探索手段は、前記抽出手段によって抽出されたあらたな移動対象セルを配置可能な空き領域を探索し、
前記移動手段は、前記探索手段によって前記あらたな移動対象セルを配置可能な空き領域が探索された場合、前記あらたな移動対象セルを前記空き領域に移動させ、前記移動対象セルを前記あらたな移動対象セルが配置されていた位置に移動させることを特徴とする請求項２〜４のいずれか一つに記載のレイアウト支援プログラム。
【請求項６】
半導体回路を構成するセル群の配置状態を表すレイアウト情報と、前記セル群に含まれるセルの種類に応じて設定された優先度情報と、を取得する取得手段と、
前記レイアウト情報に含まれるセル群の中の任意のセルに対応して配置させる追加セルの情報を受け付ける受付手段と、
前記追加セルを配置可能な空き領域があるか否かを判断する判断手段と、
前記判断手段によって、前記追加セルを配置可能な空き領域がないと判断された場合、前記任意のセルからの距離と前記優先度情報とに基づいて、移動対象セルを抽出する抽出手段と、
前記抽出手段によって抽出された移動対象セルを配置可能な空き領域を探索する探索手段と、
前記探索手段によって空き領域が探索された場合、前記移動対象セルを前記空き領域に移動させる移動手段と、
前記移動手段によって前記空き領域に移動された移動対象セルが配置されていた位置に、前記追加セルを配置する再配置手段と、
前記再配置手段によって追加セルが配置された前記半導体回路のレイアウト情報を出力する出力手段と、
を備えることを特徴とするレイアウト支援装置。
【請求項７】
コンピュータが、
半導体回路を構成するセル群の配置状態を表すレイアウト情報と、前記セル群に含まれるセルの種類に応じて設定された優先度情報と、を取得する取得工程と、
前記レイアウト情報に含まれるセル群の中の任意のセルに対応して配置させる追加セルの情報を受け付ける受付工程と、
前記追加セルを配置可能な空き領域があるか否かを判断する判断工程と、
前記判断工程によって、前記追加セルを配置可能な空き領域がないと判断された場合、前記任意のセルからの距離と前記優先度情報とに基づいて、移動対象セルを抽出する抽出工程と、
前記抽出工程によって抽出された移動対象セルを配置可能な空き領域を探索する探索工程と、
前記探索工程によって空き領域が探索された場合、前記移動対象セルを前記空き領域に移動させる移動工程と、
前記移動工程によって前記空き領域に移動された移動対象セルが配置されていた位置に、前記追加セルを配置する再配置工程と、
前記再配置工程によって追加セルが配置された前記半導体回路のレイアウト情報を出力する出力工程と、
を実行することを特徴とするレイアウト支援方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ポストレイアウトＥＣＯ（Ｅｎｇｉｎｅｅｒｉｎｇ  Ｃｈａｎｇｅ  Ｏｒｄｅｒｉｎｇ）処理におけるレイアウト支援プログラム、レイアウト支援装置およびレイアウト支援方法に関する。
【背景技術】
【０００２】
従来より、すでに各セルが所定のタイミングを保つようにレイアウトされた半導体回路に対して、回路機能を拡張するために、あらたなセルを追加するポストレイアウトＥＣＯ処理が提案されている。ポストレイアウトＥＣＯ処理では、レイアウト済みの各セルに対する信号伝搬までのタイミングの余裕値を参照して、あらたなセルを挿入可能な領域を抽出する技術が開示されている（たとえば、下記特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００１−１８８８１８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述したような従来技術の場合、あらたなセルを挿入可能な領域が無い場合には、レイアウトされた各セルのタイミングを保持できないことがある。たとえば、あらたなセルを挿入するために、レイアウト済みのセルのうち、いずれかのセルを移動させて空き領域を用意しなければならない。
【０００５】
このとき、移動させるセルによっては、論理変更に関係のないセル同士のタイミングを崩してしまうことがあった。一旦、レイアウト済みのセルのタイミングが崩れてしまうと、各セルに対して再度タイミング調整が必要になり、調整処理のために多大な負荷と時間を費やしてしまうという問題があった。
【０００６】
この発明は、上述した従来技術による問題点を解消するため、レイアウト済みのセルのタイミング関係を崩すことなく所望のセルを追加配置することができるレイアウト支援プログラム、レイアウト支援装置およびレイアウト支援方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上述した課題を解決し、目的を達成するため、このレイアウト支援プログラム、レイアウト支援装置およびレイアウト支援方法は、コンピュータが、半導体回路を構成するセル群の配置状態を表すレイアウト情報と、前記セル群に含まれるセルの種類に応じて設定された優先度情報と、を取得する処理と、前記レイアウト情報に含まれるセル群の中の任意のセルに対応して配置させる追加セルの情報を受け付ける処理と、前記追加セルを配置可能な空き領域があるか否かを判断する処理と、前記追加セルを配置可能な空き領域がないと判断された場合、前記任意のセルからの距離と、前記優先度情報とに基づいて移動対象セルを抽出する処理と、抽出された移動対象セルを配置可能な空き領域を探索する処理と、空き領域が探索された場合、前記移動対象セルを前記空き領域に移動させる処理と、前記空き領域に移動された移動対象セルが配置されていた位置に、前記追加セルを配置する処理と、追加セルが配置された前記半導体回路のレイアウト情報を出力する処理と、を含むことを要件とする。
【０００８】
このレイアウト支援プログラム、レイアウト支援装置およびレイアウト支援方法によれば、追加セルを配置可能な空き領域が無い場合には、タイミングに影響を与える可能性の低いセルを抽出して、他の空き領域に移動させることによって、追加セルを対象セルの近傍に配置したレイアウトを実現することができる。
【発明の効果】
【０００９】
本発明にかかるレイアウト支援プログラム、レイアウト支援装置およびレイアウト支援方法によれば、レイアウト済みのセルのタイミング関係を崩すことなく所望のセルを追加配置することができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】本実施の形態にかかるレイアウト支援処理の概要を示す説明図である。
【図２】本実施の形態にかかるレイアウト支援装置のハードウェア構成を示すブロック図である。
【図３】本実施の形態にかかるレイアウト支援装置の機能的構成を示す説明図である。
【図４】レイアウト設計対象となる半導体回路の一例を示す回路図である。
【図５】図４に示した半導体回路の各セルのレイアウト情報を示す説明図である。
【図６】セルの種類に応じた優先度を示す説明図である。
【図７】追加セルをオーバーラップして配置する手順を示す説明図である。
【図８】実施の形態１におけるレイアウト支援処理を用いた追加セルの配置を示す説明図である。
【図９】実施の形態１におけるレイアウト支援処理の手順を示すフローチャートである。
【図１０】実施の形態２におけるレイアウト支援処理を用いた追加セルの配置を示す説明図である。
【図１１】実施の形態２におけるレイアウト支援処理の手順を示すフローチャートである。
【図１２】実施の形態３におけるレイアウト支援処理を用いた追加セルの配置を示す説明図である。
【図１３】実施の形態３におけるレイアウト支援処理の手順を示すフローチャートである。
【図１４】実施の形態４におけるレイアウト支援処理を用いた追加セルの配置を示す説明図である。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して、このレイアウト支援プログラム、レイアウト支援装置およびレイアウト支援方法の好適な実施の形態を詳細に説明する。このレイアウト支援プログラム、レイアウト支援装置およびレイアウト支援方法では、あらたなセルを追加する際に、配置可能な空き領域が無い場合には、レイアウト済みのセルの中から、最も信号伝搬のタイミングに影響しないセルを、あらたなセルを配置するための空き領域を用意するための移動対象セルとして選択する。選択されたセルを移動させた空き領域にあらたなセルを配置することによって、追加セルの挿入に伴うタイミング調整を不要もしくは必要最低限に留めることができる。そこで、以下には上述した処理を実現するためのレイアウト支援処理について説明する。
【００１２】
（レイアウト支援処理の概要）
まず、本実施の形態にかかるレイアウト支援処理の概要について説明する。図１は、本実施の形態にかかるレイアウト支援処理の概要を示す説明図である。図１のように、レイアウト例Ａのように複数のセル群が配置された半導体回路において、対象セルの近傍に追加セルを挿入して機能を拡張しなければならないとする。
【００１３】
まず、対象セルから所定の範囲内に（たとえば、図１の領域Ｒ）追加セルを挿入できる空き領域があるか否かを判断する。ここで、空き領域があると判断されれば、その空き領域に追加セルを挿入すればよい。しかしながら図１のレイアウト例Ａの場合、追加セルを挿入できる空き領域は存在しない。
【００１４】
そこで、つぎに領域Ｒ内に配置されているセルの優先度を参照する。優先度とは、追加セルを挿入するために空き領域を用意しなければならない場合に、優先的に移動させる度合いを示した値である。図１のレイアウト例Ａでは、優先度１〜４の設定が施されており、優先度の値が小さいセルを優先的に移動させるセルと判断する。ここで優先的に移動させるセルとは、移動によってタイミングへ及ぼす影響が小さいセルである。したがって、タイミングへ及ぼす影響が小さいほど優先度の値が小さく、タイミングへ及ぼす影響が大きいほど優先度の値が大きく設定されている。したがって、優先度はセルの種類に応じて設定されている。
【００１５】
そして、レイアウト例Ａの場合には、対象セルの上段に優先度１のセルが隣接している。したがって、レイアウト例Ｂのように、優先度１のセルを移動対象セルとして、隣接する空き領域へ移動させる。その後、優先度１のセルの移動によって生じた空き領域に追加セルを配置することによって、追加セルを追加した再配置レイアウトが生成される。
【００１６】
このように本実施の形態では、優先度に基づいて、セル群の中から移動によるタイミングへの影響が最も少ないセルを選択する。そして、選択されたセルの移動によって生じた空き領域に追加セルを配置することによって半導体回路の機能を拡張することができる。以下、上述したレイアウト支援処理を実現するための具体的な構成について説明する。
【００１７】
（レイアウト支援装置のハードウェア構成）
図２は、実施の形態にかかるレイアウト支援装置のハードウェア構成を示すブロック図である。図２において、レイアウト支援装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ  Ｍｅｍｏｒｙ）２０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２０３と、磁気ディスクドライブ２０４と、磁気ディスク２０５と、通信Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）２０６と、入力デバイス２０７と、出力デバイス２０８と、を備えている。また、各構成部はバス２１０によってそれぞれ接続されている。
【００１８】
ここで、ＣＰＵ２０１は、レイアウト支援装置１００の全体の制御を司る。ＲＯＭ２０２は、ブートプログラムや、本実施の形態にかかるレイアウト支援処理を実現するレイアウト支援プログラムなどの各種プログラムを記憶している。ＲＡＭ２０３は、ＣＰＵ２０１のワークエリアとして使用される。磁気ディスクドライブ２０４は、ＣＰＵ２０１の制御にしたがって磁気ディスク２０５に対するデータの更新／参照を制御する。磁気ディスク２０５は、磁気ディスクドライブ２０４の制御で書き込まれたデータを記憶する。なお、図２のハードウェア構成では、磁気ディスク２０５を用いているが、光ディスクや、フラッシュメモリなど他の記録媒体を利用してもよい。
【００１９】
通信Ｉ／Ｆ２０６は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク（ＮＥＴ）２０９に接続され、このネットワーク２０９を介して他のレイアウト支援装置１００に接続される。そして、通信Ｉ／Ｆ２０６は、ネットワーク２０９と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。通信Ｉ／Ｆ２０６の構成例としては、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００２０】
入力デバイス２０７は、レイアウト支援装置１００に対しての外部からの入力を受け付ける。入力デバイス２０７としては、具体的には、キーボード、マウスなどが挙げられる。
【００２１】
キーボードの場合、たとえば、文字、数字、各種指示などの入力のためのキーを備え、データの入力を行う。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウスの場合、たとえば、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。また、ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００２２】
出力デバイス２０８は、レイアウト支援装置１００が取得したレイアウト情報や、レイアウト支援処理によって生成されたレイアウト情報を出力する。出力デバイス２０８としては、具体的には、ディスプレイ、プリンタなどが挙げられる。
【００２３】
ディスプレイの場合、たとえば、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイとしてさらに、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。また、プリンタの場合、たとえば、画像データや文書データを印刷する。さらに、レーザプリンタやインクジェットプリンタを採用することができる。
【００２４】
（レイアウト支援装置の機能的構成）
つぎに、レイアウト支援装置１００の機能的構成について説明する。図３は、レイアウト支援装置の機能的構成を示すブロック図である。レイアウト支援装置１００は、取得部３０１と、受付部３０２と、判断部３０３と、抽出部３０４と、探索部３０５と、移動部３０６と、再配置部３０７と、出力部３０８と、を含む構成である。この制御部となる機能（取得部３０１〜出力部３０８）は、具体的には、たとえば、図２に示したＲＯＭ２０２、ＲＡＭ２０３、磁気ディスク２０５などの記憶領域に記憶されたレイアウト支援プログラムをＣＰＵ２０１に実行させることにより、または、通信Ｉ／Ｆ２０６により、その機能を実現する。
【００２５】
取得部３０１は、半導体回路を構成するセル群の配置状態を表すレイアウト情報１０１と、セル群に含まれるセルの種類に応じて設定された優先度情報１０２とを取得する機能を有する。具体的には、レイアウト情報１０１とは、処理対象となる半導体回路を構成するセル群がそれぞれ、どのような種類のセルであり、たとえばＲＯＷ上にどのような間隔で配置されているかを表す情報である。
【００２６】
ここで、図４は、レイアウト支援対象となる半導体回路の一例を示す回路図である。図４のように、半導体回路４００は、３つのＦＦ（Ｆｌｉｐ  Ｆｌｏｐ）回路１，９，１０と、２つのインバータ回路２，３と、４つのバッファ回路４，５，６，７と、１つのＡＮＤ回路８と、１つのＯＲ回路１２と、１つのクロックドライバ１１とを備えている。
【００２７】
そして、図５は、図４に示した半導体回路の各セルのレイアウト情報を示す説明図である。レイアウト支援装置１００が、半導体回路４００のレイアウト支援をおこなう場合、取得部３０１は、図５の示したレイアウト情報５００を取得して、後段の処理に利用させる。なお、本実施の形態では、以下レイアウト情報５００を用いてレイアウト支援処理を説明する。
【００２８】
また、図６は、セルの種類に応じた優先度を示す説明図である。取得部３０１では、上述したレイアウト情報５００とともに、半導体回路４００を構成する各セルの種類に応じて設定された優先度が取得される。図６に示すように、半導体回路４００を構成するセルの場合、優先度１：インバータ（インバータ回路２，３）→優先度２：バッファ（バッファ回路４，５，６，７）→優先度３：論理素子（ＡＮＤ回路８、ＯＲ回路１２）→優先度４：クロックドライバ（クロックドライバ１１）→優先度５：記憶素子（ＦＦ回路１，９，１０）の順番で優先度が設定されている。これらの優先度は、入出力が少ないセルほど、他のセルのタイミングへの影響が少ないものとして設定している。また、記録素子は複数のセルのタイミングに影響する可能性が高いため、最も移動させたくないセルとして優先度を最低値に設定している。
【００２９】
なお、本実施の形態では、値が低いほど優先度が高いと判断されるように設定しているが（優先度１＞優先度５）、優先度値の取り扱いについては適宜設定することができる。そして、取得部３０１によって取得されたレイアウト情報１０１および優先度情報１０２は、ＲＡＭ２０３、磁気ディスク２０５などの記憶領域に記憶される。
【００３０】
図３の説明に戻り、続いて受付部３０２は、レイアウト情報１０１に含まれるセル群の中の任意のセルに対応して配置させる追加セル情報１０３を受け付ける。追加セル情報１０３には、レイアウト情報５００によって表されたセル群の中のいずれのセルに対応したどのような種類のセルであるか設定されている。具体的には、レイアウト情報５００によって表されたセル群の中のＦＦ回路１に対応したバッファ回路であるというような設定がなされている。なお、受付部３０２によって受付けられた追加セル情報１０３は、ＲＡＭ２０３、磁気ディスク２０５などの記憶領域に記憶される。
【００３１】
判断部３０３は、受付部３０２によって受け付けた追加セル情報１０３を参照して、レイアウト情報５００内に追加セルを配置可能な空き領域があるか否かを判断する機能を有する。このとき、空き領域の有無を判断する対象領域は、レイアウト情報５００全体でもよいし、対象セルを基準とした所定範囲内であってもよい。特に、対象セルと追加セルとの信号伝搬時間が短く余裕がない場合には、対象セルと追加セルとのタイミングを崩さないような範囲内に空き領域があるか否かを判断しなければならない。なお、判断部３０３による判断結果は、ＲＡＭ２０３、磁気ディスク２０５などの記憶領域に記憶される。
【００３２】
抽出部３０４は、判断部３０３によって、追加セルを配置可能な空き領域がないと判断された場合に、対象セルからの距離と、優先度情報１０２とに基づいて移動対象セルを抽出する機能を有する。移動対象セルとは、追加セルを配置するための空き領域を確保するために、移動させるセルである。したがって、対象セルの近くに配置されており、なおかつ、優先度が高く設定されているセルが移動対象セルとして抽出される。なお、抽出部３０４による抽出結果は、ＲＡＭ２０３、磁気ディスク２０５などの記憶領域に記憶される。また、判断部３０３によって、追加セルを配置可能な空き領域があると判断された場合には、この空き領域に追加セルを配置すればよい。
【００３３】
探索部３０５は、抽出部３０４によって抽出された移動対象セルを配置可能な空き領域を探索する機能を有する。ここでも、探索部３０５による空き領域の探索範囲は、レイアウト情報５００によって表される全域としてもよいし、移動対象セルの種類に応じて適宜設定してもよい。探索範囲の設定例としては、１）抽出部３０４によって抽出された移動対象セルから所定の範囲内を対象として、移動対象セルを配置可能な空き領域を探索する。２）移動対象セルを配置可能な空き領域が探索されなかった場合、空き領域が探索されるまで、所定の範囲を特定のサイズごとに拡大する。３）移動対象セルの前段に接続されたセルからの伝搬時間に比例した範囲の中から移動対象セルを配置可能な空き領域を探索するなどの例が挙げられる。
【００３４】
移動部３０６は、探索部３０５によって空き領域が探索された場合、移動対象セルを探索された空き領域に移動させる機能を有する。なお、ここで説明する移動の処理対象は、レイアウト情報１０１である。すなわち、実際に移動対象セルを移動させるのではなく、レイアウト情報１０１の設定値の変更に過ぎない。したがって、移動部３０６によって、レイアウト情報１０１に設定された移動対象セルの配置位置のアドレスは、探索された空き領域のアドレスに変更される。なお、移動部３０６によって移動対象セルが移動されたレイアウト情報１０１は、ＲＡＭ２０３、磁気ディスク２０５などの記憶領域に記憶される。
【００３５】
また、上述した抽出部３０４では同一の条件を満たすセルが複数存在する場合（たとえば、対象セルからの距離もセルの種類も同じセルなど）がある。このような場合には、抽出部３０４によって複数の移動対象セルが抽出されてしまうため、移動部３０６では、これら複数の移動対象セルを比較して、特定の条件を満たすセルを移動対象セルとして移動させる。
【００３６】
たとえば、移動部３０６は、抽出部３０４によって抽出された複数の移動対象セルのうち、最も入出力数が少ないセルを他のセルのタイミングに影響を与える可能性の低いセルとして空き領域に移動させる。なお、入出力数は、各セルのファインアウトを参照することによって確認できる。
【００３７】
また、移動部３０６は、抽出部３０４によって抽出された複数の移動対象セルのうち、接続された他のセルへの駆動電流が大きいセルを他のセルのタイミングに影響を与える可能性の低いセルとして空き領域に移動させてもよい。なお、他のセルへの駆動電流の大小は、各セルのドライブ能力を参照することによって確認できる。
【００３８】
また、移動部３０６は、抽出部３０４によって抽出された複数の移動対象セルのうち、前段に接続されたセルからの信号伝搬時間が最も長いセルを他のセルのタイミングに影響を与える可能性の低いセルとして空き領域に移動させてもよい。なお、前段に接続されたセルからの信号伝搬時間は、各セルのパスのタイミングの余裕値（スラック）を参照することによって確認できる。
【００３９】
つぎに、再配置部３０７は、移動部３０６によって空き領域に移動された移動対象セルが配置されていた位置に、追加セルを配置する。なお、上述した移動部３０６の処理と同様に、再配置の処理対象は、レイアウト情報１０１である。したがって、再配置部３０７によって、レイアウト情報１０１に替わって、追加セル情報１０３を含んだあらたなレイアウト情報１０４が生成される。なお、再配置部３０７によって生成されたレイアウト情報１０４は、ＲＡＭ２０３、磁気ディスク２０５などの記憶領域に記憶される。
【００４０】
また、上述した探索部３０５によって空き領域が探索されなかった場合、抽出部３０４によって、再度、移動対象セルからの距離と、優先度情報１０２とに基づいてあらたな移動対象セルを抽出してもよい。この抽出処理によってあらたな移動対象セルが抽出された場合、探索部３０５は、このあらたな移動対象セルを配置可能な空き領域を探索する。そして、探索部３０５によって空き領域が探索された後、移動部３０６によって探索された空き領域にあらたな移動対象セルを移動させる。
【００４１】
上述の処理によって、あらたな移動対象セルが配置されていた領域は、抽出部３０４によって最初に抽出された移動対象セルを移動するため空き領域として提供される。そして、移動部３０６は、あらたな移動対象セルを空き領域に移動させた後、最初に抽出された移動対象セルをあらたな移動対象セルが配置されていた位置に移動させることができる。すなわち、最初に抽出された移動対象セルは、玉突きのように、あらたな移動対象セルを押し出して配置領域を入れ替える。この入れ替えによって生じた空き領域が追加セルの再配置領域として確保される。
【００４２】
最後に出力部３０８は、再配置部３０７によって追加セルが配置された半導体回路４００のレイアウト情報１０４を出力する機能を有する。出力形式としては、たとえば、出力デバイス２０８のディスプレイへの表示、プリンタへの印刷出力、通信Ｉ／Ｆ２０６による外部装置への送信がある。また、ＲＡＭ２０３、磁気ディスク２０５などの記憶領域に記憶されてもよい。
【００４３】
このように、本実施の形態にかかるレイアウト支援処理では、ポストレイアウトＥＣＯ処理によって、追加セルを挿入する際に、空き領域が無い場合であっても、他のセルのタイミングへの影響が最小になるように追加セルを挿入することができる。具体的には、各セルに設定された優先度や入出力条件に基づいて抽出した他のセルのタイミングへの影響が最も少ないセルを移動して、追加セルを挿入するための空き領域を確保することができる。したがって、レイアウト済みのセルのタイミング関係を崩すことなく追加セルを挿入したレイアウトを生成することができる。
【００４４】
つぎに、上述したレイアウト支援処理の具体的な４種類の実施の形態（実施の形態１〜実施の形態４）について説明する。
【００４５】
（実施の形態１）
実施の形態１は、図６にて説明した優先度に基づいて、移動による他のセルのタイミングへの影響が小さいセルを移動対象セルとして抽出して、追加セルを配置する領域を確保する。この移動対象セルの抽出処理は、本実施の形態の最も基本となる処理である。なお、後述する実施の形態２〜実施の形態４も、実施の形態１にて説明する移動対象セルの抽出処理に、抽出処理の精度や効率を上げるための処理を追加した構成になっている。
【００４６】
ここで、まず、従来の追加セルの挿入例について説明する。図７は、追加セルをオーバーラップして配置する手順を示す説明図である。図７では、レイアウト情報５００において、対象セルであるＦＦ回路１に対応した追加セルを挿入する処理を示している。ＦＦ回路１と、バッファ回路７との間の領域７１０に追加セル（バッファ）が追加される。このとき、領域７１０は、追加セルの面積よりも小さいため、追加セルは、ＦＦ回路１とオーバーラップしている（ＳＴＥＰ１）。
【００４７】
その後、追加セルとＦＦ回路１とのオーバーラップを解消するために、まず、ＦＦ回路１を右に移動する。すると、この移動によって今度はＦＦ回路１と、後段に配置されたＦＦ回路９との間の領域７２０がオーバーラップしてしまう（ＳＴＥＰ２）。
【００４８】
したがって、今度はＦＦ回路１とＦＦ回路９とのオーバーラップを解消するために、ＦＦ回路９を右の領域７３０に移動する（ＳＴＥＰ３）。このように、ＳＴＥＰ１〜ＳＴＥＰ３の処理によって、一見問題なく追加セルが挿入されたようにみえるが、実際には、ＦＦ回路１とＦＦ回路９とが移動したため、多数のセルのタイミングに影響を与えてしまっている可能性が高い。一般的にＦＦ回路のクロック信号端子に接続されているクロック信号伝搬時の遅延値が変化してしまうクロック信号の遅延値の変化は、クロック信号が伝搬されるすべてのＦＦ回路に影響を与えてしまうため、多くのタイミングポイントにおいてタイミングエラーの発生を招いてしまう。
【００４９】
そこで、本実施の形態１では、他のセルのタイミングに影響を及ぼさないセルを抽出して、効率的に追加セルを挿入する。図８は、実施の形態１におけるレイアウト支援処理を用いた追加セルの配置を示す説明図である。図８でも、図７と同様に、対象セルであるＦＦ回路１に対応した追加セルを挿入する処理を示している。
【００５０】
レイアウト情報５００では、ＦＦ回路１の近傍に追加セルを挿入する空き領域がないため、優先度に基づいて、バッファ回路４を移動対象セル８１０として抽出する（ＳＴＥＰ１）。つぎに、移動対象セル８１０が、近傍の空き領域８２０に移動されたため、バッファ回路４が配置されていた領域が空き領域となる（ＳＴＥＰ２）。したがって、空き領域８３０に追加セルが挿入され、あたらしいレイアウトとなる（ＳＴＥＰ３）。
【００５１】
図８にて説明した処理の場合、図７の処理とは異なり、バッファ回路４が移動されているため、このセルに関して他のセルへのタイミングの影響を考慮すればよい。しかしながら、バッファ回路４は、レイアウト情報５００に配置されたセルのうち、最も他のセルのタイミングへの影響が少ないため、たとえ、他のセルへのタイミングに何らかの影響を与えていたとしても、必要最低限のタイミング調整のみ行なえばよい。
【００５２】
つぎに、上述した実施の形態１におけるレイアウト支援処理の手順について説明する。図９は、実施の形態１におけるレイアウト支援処理の手順を示すフローチャートである。図９のフローチャートにおいて、まず、対象ＦＦ回路１に隣接するセルのうち最も優先度が高いインバータを抽出し（ステップＳ９０１）、このステップＳ９０１によってインバータが抽出されたか否かを判断する（ステップＳ９０２）。
【００５３】
上述のステップＳ９０２において、インバータが抽出された場合（ステップＳ９０２：Ｙｅｓ）、抽出されたインバータを移動することによって追加セルを配置できるか否かを判断する（ステップＳ９０３）。このステップＳ９０３によって、インバータの移動によって追加セルを配置できると判断された場合は（ステップＳ９０３：Ｙｅｓ）、インバータを移動して（ステップＳ９０４）、移動後の空き領域に追加セルを配置して（ステップＳ９１５）、一連の処理を終了する。
【００５４】
一方、インバータが抽出されなかった場合（ステップＳ９０２：Ｎｏ）または、インバータを移動しても追加セルを配置できないと判断された場合は（ステップＳ９０３：Ｎｏ）、続いて、対象ＦＦ回路１に隣接するセルのうち２番目に優先度が高いバッファを抽出する（ステップＳ９０５）。そして、このステップＳ９０５によってバッファが抽出されたか否かを判断する（ステップＳ９０６）。
【００５５】
上述のステップＳ９０６において、バッファが抽出された場合（ステップＳ９０６：Ｙｅｓ）、抽出されたバッファを移動することによって追加セルを配置できるか否かを判断する（ステップＳ９０７）。そして、ステップＳ９０６において、バッファが抽出されなかった場合（ステップＳ９０６：Ｎｏ）、または、ステップＳ９０７において、追加セルを配置できないと判断された場合（ステップＳ９０７：Ｎｏ）、３番目に優先度が高い論理素子を移動して（ステップＳ９０８）、移動後の空き領域に追加セルを配置して（ステップＳ９１５）、一連の処理を終了する。
【００５６】
一方、ステップＳ９０７において、追加セルを配置できると判断された場合（ステップＳ９０７：Ｙｅｓ）、さらに各バッファのファインアウトを確認する（ステップＳ９０９）。そして、他のセルへの影響が小さいファインアウト１対１のバッファが複数あるか否かを判断する（ステップＳ９１０）。このステップＳ９１０において、ファインアウト１対１のバッファが１つのみと判断された場合（ステップＳ９１０：Ｎｏ）、このバッファを移動して（ステップＳ９１１）、移動後の空き領域に追加セルを配置して（ステップＳ９１５）、一連の処理を終了する。
【００５７】
一方、ステップＳ９１０において、ファインアウト１対１のバッファが複数あると判断された場合（ステップＳ９１０：Ｙｅｓ）、さらに、他のセルへの影響が小さいバッファを抽出するため、対象ＦＦに影響しないバッファの中にドライブ能力が高いバッファがあるか否かを判断する（ステップＳ９１２）。このステップＳ９１２におけるドライブ能力の高低は、基準値以上か未満かに基づいて判断される。
【００５８】
したがって、このステップＳ９１２において、ドライブ能力が高いバッファがあると判断された場合（ステップＳ９１２：Ｙｅｓ）、このドライブ能力の高いバッファを移動して（ステップＳ９１３）、移動後の空き領域に追加セルを配置して（ステップＳ９１５）、一連の処理を終了する。
【００５９】
そして、このステップＳ９１２において、ドライブ能力が高いバッファがないと判断された場合（ステップＳ９１２：Ｎｏ）、タイミング余裕値の高いセルを移動して（ステップＳ９１４）、移動後の空き領域に追加セルを配置して（ステップＳ９１５）、一連の処理を終了する。タイミング余裕値（スラック）とは、セルに接続されたパスからの信号伝搬を受付けるタイミングの猶予時間を表す値であり。５００ｐｓｅｃなど実際の猶予時間によって表現される。
【００６０】
このように、実施の形態１では、優先度や、バッファの条件に基づいて移動対象セルを抽出して、追加セルの挿入先に設定する。この処理によって、従来の挿入処理と異なり、オーバーラップの発生を防ぐことが可能となり、クロック信号伝搬に関する遅延時間の変化を抑えることができる。したがって、論理変更部分以外のタイミング違反の発生を抑制することができる。
【００６１】
（実施の形態２）
実施の形態２では、実施の形態１のレイアウト支援処理の中で、移動対象セルを抽出する際に、抽出対象領域を限定し、抽出結果に応じて抽出対象領域を段階的に拡大することによって効率的に移動対象セルを抽出することができる。
【００６２】
図１０は、実施の形態２におけるレイアウト支援処理を用いた追加セルの配置を示す説明図である。図１０のように、実施の形態２では、移動対象セルを抽出する際には、まず、第一セル選択領域を対象とする。そして、第一セル選択領域の中から移動対象セルが抽出されなかった場合、より領域を拡大した第二セル選択領域の中から移動対象セルを抽出する。
【００６３】
つぎに、上述した実施の形態２におけるレイアウト支援処理の手順について説明する。図１１は、実施の形態２におけるレイアウト支援処理の手順を示すフローチャートである。図１１のフローチャートにおいて、まず、追加セルの挿入を受付けると、移動対象セルの選択領域を作成する（ステップＳ１１０１）。移動対象セルの選択領域とは、図１０に示したような第一セル選択領域や第二セル選択領域を意味する。また、ステップＳ１１０１の処理において、どの程度のサイズの選択領域を作成するかは、任意に設定することができる。
【００６４】
つぎに、上述の選択領域に追加セルの挿入領域が有るか否かを判断する（ステップＳ１１０２）。すなわち、第一セル選択領域内に移動対象セルを挿入可能な空き領域が有るか否かを判断している。このステップＳ１１０２において、追加セルの挿入領域が有ると判断された場合（ステップＳ１１０２：Ｙｅｓ）、挿入領域に、追加セルを挿入して（ステップＳ１１０６）、一連の処理を終了する。
【００６５】
一方、ステップＳ１１０２において、追加セルの挿入領域が無いと判断された場合（ステップＳ１１０２：Ｎｏ）、追加セルの挿入先を確保するために、選択領域の中から移動対象セルを選択する（ステップＳ１１０３）。そして、選択された移動対象セルのタイミング余裕値（スラック）が基準値よりも大きいか否かを判断する（ステップＳ１１０４）。
【００６６】
ステップＳ１１０４において、タイミング余裕値（スラック）が基準値よりも大きいと判断された場合（ステップＳ１１０４：Ｙｅｓ）、選択領域を移動して（ステップＳ１１０５）、あらたな選択領域にて追加セルの挿入領域が有るか否かを判断する（ステップＳ１１０２）。ステップＳ１１０５の選択領域を移動とは、たとえば、図１０の例では、第一セル選択領域から第二セル選択領域への移動を意味する。
【００６７】
一方、ステップＳ１１０４において、タイミング余裕値（スラック）が基準値に満たないと判断された場合（ステップＳ１１０４：Ｎｏ）、ステップＳ１１０１によって作成された選択領域の中から移動対象セルを選択する。すなわち、移動対象セルのタイミング余裕値の値が小さいため、選択領域を広げるとタイミングに影響を及ぼしてしまう。したがって、ステップＳ１１０３に戻って最初に作成した選択領域内で最適な移動対象セルを選択する。
【００６８】
このように、実施の形態２では、移動対象セルを特定の領域に絞って探索する。移動対象セルが探索されなかった場合には、探索範囲をタイミング余裕値に基づいた制限範囲まで、段階的に拡大していく。したがって、必要最低限の領域から探索を開始するため、効率的な探索が可能となる。
【００６９】
（実施の形態３）
実施の形態３では、移動対象セルを特定の領域に絞って探索する際に、上述したタイミング余裕値（スラック）から移動可能な距離を算出し、算出されたエリア内に対して空き領域があるか否かを判断する。
【００７０】
図１２は、実施の形態３におけるレイアウト支援処理を用いた追加セルの配置を示す説明図である。たとえば、対象セルがインバータ２の場合、インバータ２のタイミング余裕値からマンハッタン長ベースの遅延や、ワイヤ・ロード（Ｗｉｒｅ  Ｌｏａｄ）モデルを用いて移動可能な距離を算出する。したがって、インバータ２の場合、円１２１０が移動可能な範囲となり、円１２１０内で移動対象セルを探索する。同様に、インバータ３の場合も、タイミング余裕値から求まった移動可能な範囲は円１２２０となる。そして、この範囲内で移動対象セルを探索する。
【００７１】
図１３は、実施の形態３におけるレイアウト支援処理の手順を示すフローチャートである。図１３のフローチャートにおいて、追加セルの挿入を受付けると、移動対象セルの選択領域を作成する（ステップＳ１３０１）。移動対象セルの選択領域とは、図１２に示したような円１２１０や円１２２０を意味する。また、ステップＳ１３０１の処理において、どの程度のサイズの選択領域を作成するかは、任意に設定することができる。
【００７２】
つぎに、上述の選択領域に追加セルの挿入領域が有るか否かを判断する（ステップＳ１３０２）。すなわち、円１２１０内に移動対象セルを挿入可能な空き領域が有るか否かを判断している。このステップＳ１３０２において、追加セルの挿入領域が有ると判断された場合（ステップＳ１３０２：Ｙｅｓ）、挿入領域に、追加セルを挿入して（ステップＳ１３０８）、一連の処理を終了する。
【００７３】
一方、ステップＳ１３０２において、追加セルの挿入領域が無いと判断された場合（ステップＳ１３０２：Ｎｏ）、追加セルの挿入先を確保するために、選択領域の中から移動対象セルを選択する（ステップＳ１３０３）。そして、選択された移動対象セルのタイミング余裕値（スラック）を確認して（ステップＳ１３０４）、移動可能領域を算出する（ステップＳ１３０５）。
【００７４】
そして、算出された移動可能領域にて移動対象セルの挿入領域ｎが有るか否かを判断する（ステップＳ１３０６）。ステップＳ１３０６において追加セルの挿入領域ｎが有ると判断された場合（ステップＳ１３０６：Ｙｅｓ）、ステップＳ１３０３に戻り、移動対象セルの挿入領域ｎが無くなったと判断されるまで、ステップＳ１３０３から１３０６の処理を繰り返す。一方、ステップＳ１３０６において、移動対象セルの挿入領域ｎが無くなったと判断されると（ステップＳ１３０６：Ｎｏ）、移動対象セルを移動させ（ステップＳ１３０７）、ステップＳ１３０２の処理に戻る。
【００７５】
このように、実施の形態３では、タイミング余裕値に基づいて、移動可能な距離を算出して得られた範囲内で、移動対象セルを選択するため、タイミングの遅延が発生しないセルのみを移動対象セルとして選択することができる。
【００７６】
（実施の形態４）
実施の形態４は、移動対象セルを挿入する空き領域が探索されなかった場合に、まず、移動対象セルを挿入するための空き領域を用意する。そして、用意された空き領域に、移動対象セルを挿入し、移動対象セルが配置されていた領域に、追加セルを挿入する。すなわち、順番に空き領域を用意して、セルを移動させていく。
【００７７】
図１４は、実施の形態４におけるレイアウト支援処理を用いた追加セルの配置を示す説明図である。図１４では、まずインバータ回路３が移動対象セルとして選択されたが、インバータ回路３の選択可能範囲１４１０にはインバータ回路３を挿入可能な空き領域がない。そこで、インバータ回路３を対象セルとして、移動対象セルを選択する。すると、移動対象セルとしてＦＦ回路９が選択される。したがって、ＦＦ回路９が選択可能範囲１４２０の空き領域に移動されると、ＦＦ回路９の空き領域にインバータ回路３を挿入して、追加セルを挿入可能な空き領域が確保される。
【００７８】
このように、実施の形態４では、玉突きのように、あらたな移動対象セルを押し出して配置領域を入れ替える。この入れ替えによって生じた空き領域が追加セルの再配置領域として確保される。
【００７９】
以上説明したように、本実施の形態によれば、追加セルを配置可能な空き領域が無い場合には、タイミングに影響を与える可能性の低いセルを抽出して、他の空き領域に移動させることによって、追加セルを対象セルの近傍に配置したレイアウトを実現することができる。したがって、レイアウト済みのセルのタイミング関係を崩すことなく所望のセルを追加配置することができ、レイアウト設計者の処理負担を大幅に軽減することができる。
【００８０】
なお、本実施の形態で説明したレイアウト支援方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また、このプログラムは、インターネットなどのネットワークを介して配布することが可能な媒体であってもよい。
【００８１】
上述した実施の形態に関し、さらに以下の付記を開示する。
【００８２】
（付記１）コンピュータを、
半導体回路を構成するセル群の配置状態を表すレイアウト情報と、前記セル群に含まれるセルの種類に応じて設定された優先度情報と、を取得する取得手段、
前記レイアウト情報に含まれるセル群の中の任意のセルに対応して配置させる追加セルの情報を受け付ける受付手段、
前記追加セルを配置可能な空き領域があるか否かを判断する判断手段、
前記判断手段によって、前記追加セルを配置可能な空き領域がないと判断された場合、前記任意のセルからの距離と前記優先度情報とに基づいて、移動対象セルを抽出する抽出手段、
前記抽出手段によって抽出された移動対象セルを配置可能な空き領域を探索する探索手段、
前記探索手段によって空き領域が探索された場合、前記移動対象セルを前記空き領域に移動させる移動手段、
前記移動手段によって前記空き領域に移動された移動対象セルが配置されていた位置に、前記追加セルを配置する再配置手段、
前記再配置手段によって追加セルが配置された前記半導体回路のレイアウト情報を出力する出力手段、
として機能させることを特徴とするレイアウト支援プログラム。
【００８３】
（付記２）前記移動手段は、前記抽出手段によって複数の移動対象セルが抽出された場合、当該複数の移動対象セルのうち、最も入出力数が少ないセルを前記空き領域に移動させることを特徴とする付記１に記載のレイアウト支援プログラム。
【００８４】
（付記３）前記移動手段は、前記抽出手段によって複数の移動対象セルが抽出された場合、当該複数の移動対象セルのうち、他のセルへの駆動電流が大きいセルを前記空き領域に移動させることを特徴とする付記１または２に記載のレイアウト支援プログラム。
【００８５】
（付記４）前記移動手段は、前記抽出手段によって複数の移動対象セルが抽出された場合、当該複数の移動対象セルのうち、前段に接続されたセルからの信号伝搬時間が最も長いセルを前記空き領域に移動させることを特徴とする付記１〜３のいずれか一つに記載のレイアウト支援プログラム。
【００８６】
（付記５）前記探索手段は、前記抽出手段によって抽出された移動対象セルから所定の範囲内を対象に当該移動対象セルを配置可能な空き領域を探索することを特徴とする付記１〜４のいずれか一つに記載のレイアウト支援プログラム。
【００８７】
（付記６）前記探索手段は、前記移動対象セルを配置可能な空き領域が探索されなかった場合、当該空き領域が探索されるまで、前記所定の範囲を特定のサイズごとに拡大することを特徴とする付記５に記載のレイアウト支援プログラム。
【００８８】
（付記７）前記探索手段は、前記移動対象セルの前段に接続されたセルからの伝搬時間に比例した範囲の中から前記移動対象セルを配置可能な空き領域を探索することを特徴とする付記１〜５のいずれか一つに記載のレイアウト支援プログラム。
【００８９】
（付記８）前記抽出手段は、前記探索手段によって空き領域が探索されなかった場合、さらに、前記抽出された移動対象セルからの距離と、前記優先度情報とに基づいてあらたな移動対象セルを抽出し、
前記探索手段は、前記抽出手段によって抽出されたあらたな移動対象セルを配置可能な空き領域を探索し、
前記移動手段は、前記探索手段によって前記あらたな移動対象セルを配置可能な空き領域が探索された場合、前記あらたな移動対象セルを前記空き領域に移動させ、前記移動対象セルを前記あらたな移動対象セルが配置されていた位置に移動させることを特徴とする付記５〜７のいずれか一つに記載のレイアウト支援プログラム。
【００９０】
（付記９）半導体回路を構成するセル群の配置状態を表すレイアウト情報と、前記セル群に含まれるセルの種類に応じて設定された優先度情報と、を取得する取得手段と、
前記レイアウト情報に含まれるセル群の中の任意のセルに対応して配置させる追加セルの情報を受け付ける受付手段と、
前記追加セルを配置可能な空き領域があるか否かを判断する判断手段と、
前記判断手段によって、前記追加セルを配置可能な空き領域がないと判断された場合、前記任意のセルからの距離と前記優先度情報とに基づいて、移動対象セルを抽出する抽出手段と、
前記抽出手段によって抽出された移動対象セルを配置可能な空き領域を探索する探索手段と、
前記探索手段によって空き領域が探索された場合、前記移動対象セルを前記空き領域に移動させる移動手段と、
前記移動手段によって前記空き領域に移動された移動対象セルが配置されていた位置に、前記追加セルを配置する再配置手段と、
前記再配置手段によって追加セルが配置された前記半導体回路のレイアウト情報を出力する出力手段と、
を備えることを特徴とするレイアウト支援装置。
【００９１】
（付記１０）コンピュータが、
半導体回路を構成するセル群の配置状態を表すレイアウト情報と、前記セル群に含まれるセルの種類に応じて設定された優先度情報と、を取得する取得工程と、
前記レイアウト情報に含まれるセル群の中の任意のセルに対応して配置させる追加セルの情報を受け付ける受付工程と、
前記追加セルを配置可能な空き領域があるか否かを判断する判断工程と、
前記判断工程によって、前記追加セルを配置可能な空き領域がないと判断された場合、前記任意のセルからの距離と前記優先度情報とに基づいて、移動対象セルを抽出する抽出工程と、
前記抽出工程によって抽出された移動対象セルを配置可能な空き領域を探索する探索工程と、
前記探索工程によって空き領域が探索された場合、前記移動対象セルを前記空き領域に移動させる移動工程と、
前記移動工程によって前記空き領域に移動された移動対象セルが配置されていた位置に、前記追加セルを配置する再配置工程と、
前記再配置工程によって追加セルが配置された前記半導体回路のレイアウト情報を出力する出力工程と、
を実行することを特徴とするレイアウト支援方法。
【符号の説明】
【００９２】
１００  レイアウト支援装置
１０１  レイアウト情報
１０２  優先度情報
１０３  追加セル情報
１０４  レイアウト情報（追加セルを含む）
３０１  取得部
３０２  受付部
３０３  判断部
３０４  抽出部
３０５  探索部
３０６  移動部
３０７  再配置部
３０８  出力部
【図１】
2010204749.tif 000003
【図２】
2010204749.tif 000004
【図３】
2010204749.tif 000005
【図４】
2010204749.tif 000006
【図５】
2010204749.tif 000007
【図６】
2010204749.tif 000008
【図７】
2010204749.tif 000009
【図８】
2010204749.tif 000010
【図９】
2010204749.tif 000011
【図１０】
2010204749.tif 000012
【図１１】
2010204749.tif 000013
【図１２】
2010204749.tif 000014
【図１３】
2010204749.tif 000015
【図１４】
2010204749.tif 000016