集積回路の配線方法、集積回路の配線プログラム及びそれを記憶した記憶媒体
【課題】 要求性能を満たすとともに、消費電力を削減することができる配線方法を提供すること。
【解決手段】 本発明の実施形態による集積回路の配線方法は、所定の動作周波数を満たすように第１の配線を求め、前記所定の動作周波数と前記第１の配線のクリティカルパスとを用いて最大迂回配線長を算出し、集積回路の配線を複数の群に分けた場合に、配線群に含まれる前記第１の配線を、前記第１の配線を含む他の配線群内の配線を用いて迂回させることで第２の配線を求め、前記第２の配線と前記第１の配線との差分が前記最大迂回配線長以下ならば、前記第２の配線によって前記第１の配線を更新し、前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きければ、前記第１の配線を更新しないことを特徴としている。
【解決手段】 本発明の実施形態による集積回路の配線方法は、所定の動作周波数を満たすように第１の配線を求め、前記所定の動作周波数と前記第１の配線のクリティカルパスとを用いて最大迂回配線長を算出し、集積回路の配線を複数の群に分けた場合に、配線群に含まれる前記第１の配線を、前記第１の配線を含む他の配線群内の配線を用いて迂回させることで第２の配線を求め、前記第２の配線と前記第１の配線との差分が前記最大迂回配線長以下ならば、前記第２の配線によって前記第１の配線を更新し、前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きければ、前記第１の配線を更新しないことを特徴としている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は集積回路の配線方法、集積回路の配線プログラム及びそれを記憶した記憶媒体に関する。
【背景技術】
【０００２】
利用者が独自の論理回路を書き込み、ユーザが所望する動作を実現することができる集積回路の一種に、ＦＰＧＡ（Field Programmable Gate Array）がある。ＦＰＧＡでは、製品出荷後も内部回路を書き換えることができる。従来のＦＰＧＡのレイアウトにおいて、配置された論理ブロックを繋ぐ配線を行うには、予め選択された複数の配線を使用して、論理ブロック間の配線長が最も短くなるように、つまり動作周波数が最も高くなるように配線する。そして、ユーザが要求する性能（動作周波数）を満たすならばその配置配線を採用し、満たさなければ配線の選択からやり直す。
【０００３】
このように配置配線されたＦＰＧＡは、ＡＳＩＣ（Application Specific Integrated Circuit）と異なり、回路として使用されていない配線や論理ブロックが多数存在する可能性がある。このような配線や論理ブロックには、使用していないにも関わらず電流が流れるため、ＦＰＧＡ全体の消費電力（特に静的消費電力）が大きくなってしまうという問題がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】KARA K. W. POON, STEVEN J.E. Wilton, and Andy YAN, “A Derailed Power Model for Field-Programmable Gate Arrays”, ACM Trans. on Design Automation of Electronic Systems, Vol. 10, No2, April 2005.
【特許文献】
【０００５】
【特許文献１】米国特許第７２８１２３３号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
そこで本発明は、要求性能を満たすとともに、消費電力を削減することができる配線方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明の実施形態による集積回路の配線方法は、所定の動作周波数を満たすように第１の配線を求め、前記所定の動作周波数と前記第１の配線のクリティカルパスとを用いて最大迂回配線長を算出し、集積回路の配線を複数の群に分けた場合に、配線群に含まれる前記第１の配線を、前記第１の配線を含む他の配線群内の配線を用いて迂回させることで第２の配線を求め、前記第２の配線と前記第１の配線との差分が前記最大迂回配線長以下ならば、前記第２の配線によって前記第１の配線を更新し、前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きければ、前記第１の配線を更新しないことを特徴としている。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態に係るＦＰＧＡの概念を示す図。
【図２】本発明の実施形態に係る配線の電源を制御するための回路の一例を示す図。
【図３】本発明の実施形態に係るインバータとトランジスタとの接続部分を詳細に示す図。
【図４】本発明の実施形態に係るＦＰＧＡの配置配線を行うＰＣのブロック図。
【図５】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図６】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図７】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図８】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図９】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図１０】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図１１】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図１２】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態について図面を参照して説明する。図１は、本実施形態に係るＦＰＧＡの概念を示す図である。本実施形態に係るＦＰＧＡは、ＦＰＧＡに含まれる配線をいくつかの群（以降では、配線群と称する）に分け、１つの配線群に含まれる複数（ｎ本であるとする）の配線の電源のＯＮ／ＯＦＦを１つのメモリーから出力された信号で制御する。図では全ての配線群に含まれる本数が同じように描かれているが、実際は本数が異なっていても構わない。図１では、メモリーＤ１〜Ｄ１８が接続された制御用配線に、ＦＰＧＡの配線群が接続されている様子を示している。なお、メモリーＤ１〜Ｄ１８は、ＳＲＡＭ等の揮発性メモリーを用いても良いし、ＤＲＡＭ等の不揮発性メモリーを用いても良い。不揮発性メモリーを使用した場合には、ＦＰＧＡ全体の電源をＯＦＦにしたとしても、情報を保持することができるため、揮発性メモリーと比較して情報の再書込みが必要無く、消費電力が低く抑えることができる。
【００１０】
このように構成することで、配線群に含まれる複数の配線がＦＰＧＡの動作で使用されないならば、この配線群の電源をＯＦＦにすることができる。ＦＰＧＡにおいて、配線部分の消費電力量は高いため、使用されない配線群の電源をＯＦＦにすることで静的消費電力を削減することができる。また、本実施形態に係るＦＰＧＡのように、複数の配線の電源を１つのメモリーで管理することによって、各配線に対して１つずつメモリーを設ける場合と比較して、メモリー数が少なくて済み、メモリー配置のための面積増大を抑制することができる。
【００１１】
図２は、配線の電源を制御するための回路の一例（メモリーＤ１に接続された回路の例）を示す図である。例えばＦＰＧＡ上のスイッチ部分には、図２に示すような２入力マルチプレクサが使用されている。このマルチプレクサによって、例えばメモリーＤ１０によって制御されている配線をメモリーＤ１によって制御されている配線に接続することが可能となり、これにより異なる配線への経路切り替えが可能となる。この２入力マルチプレクサは、ＦＰＧＡを制御するためのメモリー２３からの出力に応じて選択されるＮ型ＭＯＳＦＥＴ２１またはＰ型ＭＯＳＦＥＴ２２に入力された配線の信号を出力する。図２の例では、メモリーＤ１０によって制御される配線の信号はＮ型ＭＯＳＦＥＴ２１に入力し、メモリーＤ１によって制御される配線の信号はＰ型ＭＯＳＦＥＴ２１に入力するものとしている。また、この２入力マルチプレクサには、信号増幅のためのインバータ２４〜２６が設けられており、このインバータ２４〜２６のそれぞれに対して、メモリーＤ１ないしはメモリーＤ１０からの出力信号によってＯＮ／ＯＦＦするトランジスタ２７〜２９が設けられている。なお、図２では、配線群に含まれる１つの配線に設けられるマルチプレクサの回路を図示しているが、同一のメモリーＤ１に接続される全ての配線に設けられているインバータ全てに対して、同様のトランジスタ回路が設けられる。
【００１２】
図３は、図２におけるインバータ２４とトランジスタ２７との接続部分（図２において破線で囲った部分）を詳細に示す図である。インバータ２４とトランジスタ２７接続部分は、例えば図３（ａ）〜（ｃ）のいずれかのように構成される。図３（ａ）と（ｂ）は、インバータ２４を構成するＮ型ＭＯＳＦＥＴもしくはＰ型ＭＯＳＦＥＴのいずれかの一端に１つのトランジスタ２７を接続した回路を示している。図３（ｃ）は、インバータ２４を構成するＮ型ＭＯＳＦＥＴの一端に１つのトランジスタ２７を接続し、インバータ２４を構成するＰ型ＭＯＳＦＥＴの一端にもう１つのトランジスタ２７を接続した回路を示している。
【００１３】
インバータ２４に接続されるトランジスタ２７をメモリーＤ１からの出力信号によってＯＦＦに設定すると、インバータを流れる電流を遮断することができる。特に、図３（ｃ）に示す回路では、図３（ａ）や（ｂ）と比較して、必要なトランジスタ２７が１つ多いが、より安定してインバータ２４が接続された配線の電源ＯＮ／ＯＦＦを設定することができる。なお、図２のインバータ２５とトランジスタ２８の接続部分やインバータ２６とトランジスタ２９の接続部分も図３（ａ）〜（ｃ）を用いて説明した回路によって構成することができる。
【００１４】
次に、図１〜図３にて説明したＦＰＧＡの配置配線について説明する。本実施形態によるＦＰＧＡの配置配線は、例えばパーソナルコンピュータ（ＰＣ）によって実行される。図４は、ＦＰＧＡの配置配線を行うＰＣ１のブロック図である。ＰＣ１は、プロセッサ１０、メインメモリー２０、ハードディスク３０、入出力装置４０が内部インタフェースで接続されている。また、メインメモリー２０には不揮発性メモリー５０が接続されている。プロセッサ１０は、演算処理を行うプロセッサエレメント１１とキャッシュ１２を有し、ＰＣ１全体の制御を行う。入出力装置４０は、様々な外部機器と接続し、例えば配置配線の情報をＦＰＧＡに書き込む際に配置配線の情報を出力するために用いられる。ＦＰＧＡの配置配線のためのプログラムは、例えばハードディスク３０に記憶されており、メインメモリー２０がそのプログラムを読み込んで、プロセッサエレメント１１がメインメモリー２０に読み込まれたプログラムに従って演算を行って実行される。ハードディスク３０に記憶されるＦＰＧＡの配置配線プログラムは、そのプログラムを記憶した記憶媒体（記録型ＣＤ／ＤＶＤやＵＳＢメモリ等）から、入出力装置４０経由で入手しても良いし、プログラムを記憶したサーバから、図示しないアンテナ経由で入手しても良い。
【００１５】
本実施形態によるＦＰＧＡの配置配線は、図５〜図７の処理をプロセッサエレメント１１が実行することで行われる。プロセッサエレメント１１は、図５に示す処理を行ってユーザの要求性能を満たすよう配置および仮の配線を行い、図６および図７に示す処理を行って、ユーザの要求性能を満たす範囲内で、仮の配線を変更して、より多くの配線の電源をＯＦＦすることができるような配線を行う。
【００１６】
図５に示す処理について説明する。なお、図５に示す仮の配線処理フローの各ステップにおける処理については、非特許文献１に記載があるため、詳細な説明を省略する。プロセッサエレメント１１は、ユーザが所望するための回路を実現する論理ブロックの配置を行う（Ｓ１０）。そして、複数の配線を選択し（Ｓ１１）、選択された配線を使用して、ステップＳ１０にて配置された論理ブロックを繋ぐ配線を行う（Ｓ１２）。
【００１７】
選択された配線を使用して配線ができれば（Ｓ１３のＹｅｓ）、作成した配置配線のクリティカルパスを計算する（Ｓ１４）。そして、計算されたクリティカルパスに基づいて、作成した配置配線の最大動作周波数を求め、予め与えられたユーザが要求する動作周波数（以下、要求周波数と称する）を満たすかどうかを判断する（Ｓ１５）。もし、ステップＳ１５にて、作成された配置配線が要求周波数を満たさないと判断されたときには（Ｓ１５のＮｏ）、ステップＳ１１に戻って配線をやり直す。一方、要求周波数を満たす配置配線が作成できた場合には（Ｓ１５のＹｅｓ）、図５に示す仮の配線処理を終了する。以降では、作成された配置配線に用いられている配線をレイアウトに使用される配線と称する。
【００１８】
次に、図６および図７に示す処理について説明する。仮の配線処理では、要求周波数を満たす配置配線が得られるが、配線の消費電力を削減することは考慮されていない。そこで、プロセッサエレメント１１は、図５に示す仮の配線処理が終了すると、図６および図７に示す再配線処理を開始する。
【００１９】
プロセッサエレメント１１は、まず、要求周波数を満たす範囲内で、現状の配線のクリティカルパスを最大限迂回可能な配線長を算出する（Ｓ２０）。迂回可能配線長ＢＮＵＭの算出は、例えば式（１）によって行う。
BNUM = (1/fR - DPATH)/DCLB ・・・（１）
ここで、ＤＰＡＴＨはクリティカルパスＣＰＡＴＨによって生じる遅延時間を表し、ＤＣＬＢは論理ブロック１辺の長さの配線によって生じる遅延時間を表す。つまり、迂回可能配線長ＢＮＵＭは、ユーザの要求性能を満たす範囲内で、現状の配線のクリティカルパスＣＰＡＴＨから配線を迂回させる場合、論理ブロック何辺分だけ配線を迂回させることができるかどうかを示している。
【００２０】
なお、迂回可能配線長ＢＮＵＭの算出方法は、数１に限らず、ユーザの要求性能とクリティカルパスとを用いた、他の算出方法でも良い。例えば式（２）のような算出方法が考えられる。
BNUM = (LMAX - LC)/LCLB ・・・（２）
ここで、ＬＭＡＸは要求周波数ｆＲを満たす最大の配線の長さを表し、ＬＣはクリティカルパスＣＰＡＴＨの長さを表し、ＬＣＬＢは論理ブロック１辺の長さを表す。
【００２１】
プロセッサエレメント１１は、このようにして算出した迂回可能配線長ＢＮＵＭが２以上であるか否かを判断する（Ｓ２１）。図８（ａ）に示すように、縦方向に配置された論理ブロック１辺分の配線Ｔ１を迂回させる場合、横方向の論理ブロック２辺分の配線Ｔ２、Ｔ３と、縦方向の論理ブロック１辺分の配線Ｔ４の配線が少なくとも必要である。同様に、図８（ｂ）に示すように、横方向に配置された論理ブロック１辺分の配線Ｔ５を迂回させる場合、縦方向の論理ブロック２辺分の配線Ｔ６、Ｔ７と、横方向の論理ブロック１辺分の配線Ｔ８が少なくとも必要である。つまり、クリティカルパスＣＰＡＴＨの配線を迂回させると、少なくとも論理ブロック２辺分配線長が増えることを意味する。
【００２２】
そこで、迂回可能配線長ＢＮＵＭを２と比較することによって、ユーザの要求性能を満たす範囲内で配線を迂回させることが可能であるか否かを判断することができる。そして、迂回可能配線長ＢＮＵＭが２未満であれば（Ｓ２１のＮｏ）、配線処理は終了する。このように事前にユーザの要求性能を満たす範囲内で配線を迂回させることが可能か否かを判断することによって、ユーザの要求性能を満たすことができないにも関わらず配線の迂回を試行するという無駄な処理を省くことができる。
【００２３】
ステップＳ２１で迂回可能配線長ＢＮＵＭが２以上であると判断されると、プロセッサエレメント１１は、配線群内でレイアウトとして使用されている配線の本数によって配線群を分類する（Ｓ２２）。つまり、配線群を構成するｋ本の配線のうち、レイアウトに使用されている配線（以降、使用配線と称する）がｉ本の配線群（０≦ｉ≦ｎ）のものに分類する。そして、再配線が行われたかどうかの判断（Ｓ２８にて後述する）に用いるためのフラグをリセットする（Ｓ２３）。
【００２４】
そして、使用配線が１本の分類Ｇ１を選択し（Ｓ２４）、分類Ｇ１内に配線群が存在するならば（Ｓ２５のＹｅｓ）、図７に示すフローチャートに移り、存在しないならば（Ｓ２５のＮｏ）、現在選択している分類よりも使用配線が１本多い分類を選択して、変数Iがｎとなるまで、ステップＳ２５の処理を繰り返す。
【００２５】
ステップＳ２５において、分類ＧＩに配線群が存在すると判断された場合、プロセッサエレメント１１は、分類ＧＩから任意の配線群ＷＴＡＲＧＥＴを１つ選択する（Ｓ４０）。そして、配線群ＷＴＡＲＧＥＴに含まれるレイアウトに使用されているＩ本の配線それぞれについて、使用配線が１本からｎ本の配線群の配線を使用した迂回経路を算出する（Ｓ４１）。なお、ステップＳ４１で算出される迂回経路が複数ある場合には、最短の迂回経路を選ぶ。
【００２６】
そして、プロセッサエレメント１１は、配線群ＷＴＡＲＧＥＴに含まれる全ての使用配線が配線群ＷＴＡＲＧＥＴとは異なる配線群に迂回可能であるならば（Ｓ４２のＹｅｓ）、元の配線と比較した迂回後の配線の増加長ＢＡＤＤを算出する（Ｓ４３）。なお、配線増加分の長さを示すＢＡＤＤは、迂回可能配線長ＢＮＵＭと比較できるように、論理ブロック何辺分の長さであるかを示す値として算出する。ただし、これに限らず、ＢＡＤＤとＢＮＵＭとが比較できるように両者の単位が揃っていれば良い。
【００２７】
配線増加長ＢＡＤＤが最大迂回配線長ＢＮＵＭよりも短ければ（Ｓ４４のＹｅｓ）、迂回後の配線が要求周波数を満たすことが保障される。そのため、プロセッサエレメント１１は、迂回後の配線を採用する（Ｓ４５）。迂回後の配線が採用される場合には、式（３）に示すように、配線群ＷＴＡＲＧＥＴの分類が使用配線０本の分類に変更され、最大迂回配線長ＢＮＵＭの値が更新される。さらに、配線群ＷＴＡＲＧＥＴの配線の迂回に用いられた配線を含む配線群の分類が、迂回配線採用後の使用配線数に応じて変更される。
Ｇ０＝Ｇ０∪｛ＷＴＡＲＧＥＴ｝
ＧＩ＝ＧＩ−｛ＷＴＡＲＧＥＴ｝
ＢＮＵＭ＝ＢＮＵＭ−ＢＡＤＤ ・・・（３）
ステップＳ４５にて、迂回経路を採用する処理が終了すると、プロセッサエレメント１１は、再配線が行われたことを示すフラグをセットする（Ｓ４６）。そして、最大迂回配線長ＢＮＵＭが２未満ならば（Ｓ４７のＮｏ）、これ以上配線を迂回させることができないため、図６のステップＳ２９にて再配線後のクリティカルパスを計算し、ステップＳ２０からの処理を繰り返す。それに対して、最大迂回配線長ＢＮＵＭが２以上ならば（Ｓ４７のＹｅｓ）、ステップＳ２５に戻り、分類ＧＩに含まれる配線群の再配線処理を行う。
【００２８】
ステップＳ４４において、配線増加長ＢＡＤＤが最大迂回配線長ＢＮＵＭよりも長い場合（Ｓ４４のＮｏ）や、配線群ＷＴＡＲＧＥＴの使用配線の内、少なくとも１本の使用配線が迂回できない場合（Ｓ４２のＮｏ）、迂回後の配線は採用されない（Ｓ４８）。迂回後の配線が採用されない場合には、配線群ＷＴＡＲＧＥＴが処理済であることが判別するための情報を付与する。例えば、処理済の配線群を示す分類ＧＦＩＮＩＳＨを設け、式（４）に示すように、配線群ＷＴＡＲＧＥＴを分類ＧＦＩＮＩＳＨに移動させることによって、処理済を判別させる。
ＧＦＩＮＩＳＨ＝ＧＦＩＮＩＳＨ∪｛ＷＴＡＲＧＥＴ｝
ＧＩ＝ＧＩ−｛ＷＴＡＲＧＥＴ｝ ・・・（４）
そして、ステップＳ４８の処理が終了すると、ステップＳ２５に戻り、分類ＧＩに含まれる配線群の再配線処理を行う。なお、最大迂回配線長ＢＮＵＭが２以上の状態で、全ての分類Ｇ１〜Ｇｎ−１に含まれる全ての配線群に対する再配線処理が終了すると（Ｓ２７のＹｅｓ）、ステップＳ２８にて、迂回配線が採用されたかどうかが判断され、迂回配線が採用されていなければ（Ｓ２８のＮｏ）、配線処理を終了する。迂回配線が採用されたかどうかは、再配線が行われたことを示すフラグによって判断できる。
【００２９】
以上説明したような処理によれば、要求周波数を満たしている配線を基にして、要求周波数を満たしながら、レイアウトに使用される配線が無い配線群の数を増やした配線を得ることができる。
【００３０】
なお、本実施形態では、使用配線が少ない分類に含まれる配線群から順に再配線処理を行ったが、再配線処理を行う順番はこれに限られない。例えば、配線群を、使用配線が０本の分類、使用配線がｎ本の分類、および使用配線が１本〜（ｎ−１）本のいずれかである分類の３つに分け、使用配線が１本〜（ｎ−１）本のいずれかの配線群から任意の順で再配線処理を行っても良い。
【００３１】
図６および図７を用いて説明した再配線処理では、処理の終了条件は、最大迂回配線長ＢＮＵＭが２よりも小さくなった場合か、最大迂回配線長ＢＮＵＭを算出した後に、いずれの配線群も迂回配線が採用されなかった場合の２つである。しかしながら、採用された配置配線によっては、最大迂回配線長ＢＮＵＭが２以上であっても、これ以上再配置することができない場合がある。そこで、上述の終了条件だけでなく、以下の変形例１〜３に示すような終了条件を加えても良い。なお、以下の変形例のフローチャートでは、図６、図７を用いて説明した処理と同じ処理には同じ番号を付与し、詳細な説明を省略する。
【００３２】
（変形例１）
例えば、最大迂回配線長ＢＮＵＭが２の場合、再配置計算を行っていない配線群の使用配線数がいずれも２以上であるならば、例え１本の使用配線を迂回することができたとしても、他の使用配線を迂回することができない。つまり、使用配線の本数が少ない分類に含まれる配線群から順に再配置計算を行う場合、最大迂回配線長ＢＮＵＭが２×Ｉ（Ｉは、使用配線の本数）未満となると、使用配線の全てを迂回させることはできない。
【００３３】
そこで、図６に示した処理に代えて図９のように、最大迂回配線長ＢＮＵＭと２×Ｉとを比較し（Ｓ１０１）、最大迂回配線長ＢＮＵＭが２×Ｉ以上ならば（Ｓ１０１のＹｅｓ）、ステップＳ４０へ進み、分類ＧＩ内の配線群の再配線処理を行い、最大迂回配線長ＢＮＵＭが２×Ｉ未満ならば（Ｓ１０１のＮｏ）、ステップＳ２８の処理に進むことで、再配置できないにもかかわらず再配置を試みる処理を行うことを防ぐことができる。
【００３４】
（変形例２）
迂回配線が何度も連続で採用されなかった場合、その時点で配線処理を終了させても良い。図１０及び図１１は、迂回経路の不採用が所定の回数（ＮＦ回）を超えた時点で配線処理を終了させる場合のプロセッサエレメント１１の処理を示すフローチャートである。
【００３５】
図１０及び図１１に示す処理において、迂回経路の不採用回数をカウントする変数Ｎｃｏｕｎｔを用いる。変数Ｎｃｏｕｎｔは、迂回経路の探索が行われる前に（例えば、図１０のステップＳ１１１）、０にリセットされる。そして、図１１のステップＳ４８にて迂回経路が採用されなかった場合には、変数Ｎｃｏｕｎｔが１増加する（Ｓ１１２）。そして、変数Ｎｃｏｕｎｔが閾値ＮＦよりも大きくなった場合（Ｓ１１３のＹｅｓ）、配線処理を終了する。一方、図１１のステップＳ４５にて迂回経路が採用された場合には、変数Ｎｃｏｕｎｔが０にリセットされる（Ｓ１１４）。
【００３６】
（変形例３）
予め再配置計算対象の分類を定め、再配置計算対象の分類に含まれる配線群の再配置計算が終了すると、処理を終了させても良い。そのためには、図６に示した処理に代えて図１２に基づいて処理を行う。図１２に示す処理では、再配置計算を行う前に（例えば図１２のＳ１２１）再配置計算対象の分類を設定する。ここでは、何本の使用配線の分類に属する配線群までが再配線出来る可能性を持っているのかを式（５）および式（６）により計算する。
【数１】
ここで、Ｒｉは、横方向の配線から成る配線群であり、使用配線の本数がｉ本である配線群の数を表す。また、Ｃｉは、縦方向の配線群であり、使用配線の本数がｉ本である配線群の数を表す。プロセッサエレメント１１は、式（５）および式（６）の両方を満たすように再配線対象分類の最大使用配線数Ｊを求める。
【００３７】
配線群の中で、レイアウトに使用されている配線がｉ本の縦方向の配線である場合、迂回配線として横方向の配線を２×ｉ本と縦方向の配線ｉ本が必要である。また、レイアウトに使用されている配線がｉ本の横方向の配線である場合、迂回配線として横方向の配線をｉ本と縦方向の配線を２×ｉ本が必要である。
【００３８】
式（５）の左辺は、配線群内のレイアウトに使用されている配線が１〜Ｊ本であると分類された配線群に含まれる配線を全て迂回させるときに必要な横方向の配線の本数を表している。式（５）の右辺は、配線群内のレイアウトに使用されている配線が（Ｊ＋１）本〜ｎ本であると分類された配線群に含まれるレイアウトに使用されていない横方向の配線の合計本数を表している。つまり、式（５）では、配線群内のレイアウトに使用されている配線が１〜Ｊ本であると分類された配線群に含まれる配線を全て迂回させる場合に、迂回先となる横方向の配線が足りるか否かを検証している。
【００３９】
同様に、式（６）では、配線群内のレイアウトに使用されている配線が１〜Ｊ本であると分類された配線群に含まれる配線を全て迂回させる場合に、迂回先となる縦方向の配線が足りるか否かを検証している。そして、式（５）および式（６）を満たすＪを探索し、レイアウトに使用されている配線が１〜Ｊ本の配線群を配線迂回の候補とする。
【００４０】
このような変形例を用いることによって、再配線の処理にかかる時間を短縮し、より短時間で配線経路を得ることができる。なお、変形例１〜３は複数を組み合わせて使用しても良い。
【００４１】
以上説明したように、本発明の実施形態やその変形例の構成をとることで、要求周波数を満たしながら、レイアウトに使用される配線が無い配線群の数ができるだけ多くなるよう配線することができる。使用されない配線群の電源はＯＦＦにすることができるため、消費電力を削減することができる。
【００４２】
なお、上記実施形態に限定されることはなく、本発明の要旨を逸脱しない範囲において、適宜変更しても良い。
【符号の説明】
【００４３】
１…ＰＣ、 １０…プロセッサ、 １１…プロセッサエレメント、 １２…キャッシュ、 ２０…メインメモリー、 ３０…ハードディスク、 ４０…入出力装置、 ２１…Ｎ型ＭＯＳＦＥＴ、 ２２…Ｐ型ＭＯＳＦＥＴ、 ２３…メモリー、 ２４，２５，２６…インバータ、 ２７，２８，２９…トランジスタ
【技術分野】
【０００１】
本発明の実施形態は集積回路の配線方法、集積回路の配線プログラム及びそれを記憶した記憶媒体に関する。
【背景技術】
【０００２】
利用者が独自の論理回路を書き込み、ユーザが所望する動作を実現することができる集積回路の一種に、ＦＰＧＡ（Field Programmable Gate Array）がある。ＦＰＧＡでは、製品出荷後も内部回路を書き換えることができる。従来のＦＰＧＡのレイアウトにおいて、配置された論理ブロックを繋ぐ配線を行うには、予め選択された複数の配線を使用して、論理ブロック間の配線長が最も短くなるように、つまり動作周波数が最も高くなるように配線する。そして、ユーザが要求する性能（動作周波数）を満たすならばその配置配線を採用し、満たさなければ配線の選択からやり直す。
【０００３】
このように配置配線されたＦＰＧＡは、ＡＳＩＣ（Application Specific Integrated Circuit）と異なり、回路として使用されていない配線や論理ブロックが多数存在する可能性がある。このような配線や論理ブロックには、使用していないにも関わらず電流が流れるため、ＦＰＧＡ全体の消費電力（特に静的消費電力）が大きくなってしまうという問題がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】KARA K. W. POON, STEVEN J.E. Wilton, and Andy YAN, “A Derailed Power Model for Field-Programmable Gate Arrays”, ACM Trans. on Design Automation of Electronic Systems, Vol. 10, No2, April 2005.
【特許文献】
【０００５】
【特許文献１】米国特許第７２８１２３３号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
そこで本発明は、要求性能を満たすとともに、消費電力を削減することができる配線方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明の実施形態による集積回路の配線方法は、所定の動作周波数を満たすように第１の配線を求め、前記所定の動作周波数と前記第１の配線のクリティカルパスとを用いて最大迂回配線長を算出し、集積回路の配線を複数の群に分けた場合に、配線群に含まれる前記第１の配線を、前記第１の配線を含む他の配線群内の配線を用いて迂回させることで第２の配線を求め、前記第２の配線と前記第１の配線との差分が前記最大迂回配線長以下ならば、前記第２の配線によって前記第１の配線を更新し、前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きければ、前記第１の配線を更新しないことを特徴としている。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態に係るＦＰＧＡの概念を示す図。
【図２】本発明の実施形態に係る配線の電源を制御するための回路の一例を示す図。
【図３】本発明の実施形態に係るインバータとトランジスタとの接続部分を詳細に示す図。
【図４】本発明の実施形態に係るＦＰＧＡの配置配線を行うＰＣのブロック図。
【図５】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図６】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図７】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図８】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図９】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図１０】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図１１】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【図１２】本発明の実施形態に係るＦＰＧＡの配置配線処理を示すフローチャート。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態について図面を参照して説明する。図１は、本実施形態に係るＦＰＧＡの概念を示す図である。本実施形態に係るＦＰＧＡは、ＦＰＧＡに含まれる配線をいくつかの群（以降では、配線群と称する）に分け、１つの配線群に含まれる複数（ｎ本であるとする）の配線の電源のＯＮ／ＯＦＦを１つのメモリーから出力された信号で制御する。図では全ての配線群に含まれる本数が同じように描かれているが、実際は本数が異なっていても構わない。図１では、メモリーＤ１〜Ｄ１８が接続された制御用配線に、ＦＰＧＡの配線群が接続されている様子を示している。なお、メモリーＤ１〜Ｄ１８は、ＳＲＡＭ等の揮発性メモリーを用いても良いし、ＤＲＡＭ等の不揮発性メモリーを用いても良い。不揮発性メモリーを使用した場合には、ＦＰＧＡ全体の電源をＯＦＦにしたとしても、情報を保持することができるため、揮発性メモリーと比較して情報の再書込みが必要無く、消費電力が低く抑えることができる。
【００１０】
このように構成することで、配線群に含まれる複数の配線がＦＰＧＡの動作で使用されないならば、この配線群の電源をＯＦＦにすることができる。ＦＰＧＡにおいて、配線部分の消費電力量は高いため、使用されない配線群の電源をＯＦＦにすることで静的消費電力を削減することができる。また、本実施形態に係るＦＰＧＡのように、複数の配線の電源を１つのメモリーで管理することによって、各配線に対して１つずつメモリーを設ける場合と比較して、メモリー数が少なくて済み、メモリー配置のための面積増大を抑制することができる。
【００１１】
図２は、配線の電源を制御するための回路の一例（メモリーＤ１に接続された回路の例）を示す図である。例えばＦＰＧＡ上のスイッチ部分には、図２に示すような２入力マルチプレクサが使用されている。このマルチプレクサによって、例えばメモリーＤ１０によって制御されている配線をメモリーＤ１によって制御されている配線に接続することが可能となり、これにより異なる配線への経路切り替えが可能となる。この２入力マルチプレクサは、ＦＰＧＡを制御するためのメモリー２３からの出力に応じて選択されるＮ型ＭＯＳＦＥＴ２１またはＰ型ＭＯＳＦＥＴ２２に入力された配線の信号を出力する。図２の例では、メモリーＤ１０によって制御される配線の信号はＮ型ＭＯＳＦＥＴ２１に入力し、メモリーＤ１によって制御される配線の信号はＰ型ＭＯＳＦＥＴ２１に入力するものとしている。また、この２入力マルチプレクサには、信号増幅のためのインバータ２４〜２６が設けられており、このインバータ２４〜２６のそれぞれに対して、メモリーＤ１ないしはメモリーＤ１０からの出力信号によってＯＮ／ＯＦＦするトランジスタ２７〜２９が設けられている。なお、図２では、配線群に含まれる１つの配線に設けられるマルチプレクサの回路を図示しているが、同一のメモリーＤ１に接続される全ての配線に設けられているインバータ全てに対して、同様のトランジスタ回路が設けられる。
【００１２】
図３は、図２におけるインバータ２４とトランジスタ２７との接続部分（図２において破線で囲った部分）を詳細に示す図である。インバータ２４とトランジスタ２７接続部分は、例えば図３（ａ）〜（ｃ）のいずれかのように構成される。図３（ａ）と（ｂ）は、インバータ２４を構成するＮ型ＭＯＳＦＥＴもしくはＰ型ＭＯＳＦＥＴのいずれかの一端に１つのトランジスタ２７を接続した回路を示している。図３（ｃ）は、インバータ２４を構成するＮ型ＭＯＳＦＥＴの一端に１つのトランジスタ２７を接続し、インバータ２４を構成するＰ型ＭＯＳＦＥＴの一端にもう１つのトランジスタ２７を接続した回路を示している。
【００１３】
インバータ２４に接続されるトランジスタ２７をメモリーＤ１からの出力信号によってＯＦＦに設定すると、インバータを流れる電流を遮断することができる。特に、図３（ｃ）に示す回路では、図３（ａ）や（ｂ）と比較して、必要なトランジスタ２７が１つ多いが、より安定してインバータ２４が接続された配線の電源ＯＮ／ＯＦＦを設定することができる。なお、図２のインバータ２５とトランジスタ２８の接続部分やインバータ２６とトランジスタ２９の接続部分も図３（ａ）〜（ｃ）を用いて説明した回路によって構成することができる。
【００１４】
次に、図１〜図３にて説明したＦＰＧＡの配置配線について説明する。本実施形態によるＦＰＧＡの配置配線は、例えばパーソナルコンピュータ（ＰＣ）によって実行される。図４は、ＦＰＧＡの配置配線を行うＰＣ１のブロック図である。ＰＣ１は、プロセッサ１０、メインメモリー２０、ハードディスク３０、入出力装置４０が内部インタフェースで接続されている。また、メインメモリー２０には不揮発性メモリー５０が接続されている。プロセッサ１０は、演算処理を行うプロセッサエレメント１１とキャッシュ１２を有し、ＰＣ１全体の制御を行う。入出力装置４０は、様々な外部機器と接続し、例えば配置配線の情報をＦＰＧＡに書き込む際に配置配線の情報を出力するために用いられる。ＦＰＧＡの配置配線のためのプログラムは、例えばハードディスク３０に記憶されており、メインメモリー２０がそのプログラムを読み込んで、プロセッサエレメント１１がメインメモリー２０に読み込まれたプログラムに従って演算を行って実行される。ハードディスク３０に記憶されるＦＰＧＡの配置配線プログラムは、そのプログラムを記憶した記憶媒体（記録型ＣＤ／ＤＶＤやＵＳＢメモリ等）から、入出力装置４０経由で入手しても良いし、プログラムを記憶したサーバから、図示しないアンテナ経由で入手しても良い。
【００１５】
本実施形態によるＦＰＧＡの配置配線は、図５〜図７の処理をプロセッサエレメント１１が実行することで行われる。プロセッサエレメント１１は、図５に示す処理を行ってユーザの要求性能を満たすよう配置および仮の配線を行い、図６および図７に示す処理を行って、ユーザの要求性能を満たす範囲内で、仮の配線を変更して、より多くの配線の電源をＯＦＦすることができるような配線を行う。
【００１６】
図５に示す処理について説明する。なお、図５に示す仮の配線処理フローの各ステップにおける処理については、非特許文献１に記載があるため、詳細な説明を省略する。プロセッサエレメント１１は、ユーザが所望するための回路を実現する論理ブロックの配置を行う（Ｓ１０）。そして、複数の配線を選択し（Ｓ１１）、選択された配線を使用して、ステップＳ１０にて配置された論理ブロックを繋ぐ配線を行う（Ｓ１２）。
【００１７】
選択された配線を使用して配線ができれば（Ｓ１３のＹｅｓ）、作成した配置配線のクリティカルパスを計算する（Ｓ１４）。そして、計算されたクリティカルパスに基づいて、作成した配置配線の最大動作周波数を求め、予め与えられたユーザが要求する動作周波数（以下、要求周波数と称する）を満たすかどうかを判断する（Ｓ１５）。もし、ステップＳ１５にて、作成された配置配線が要求周波数を満たさないと判断されたときには（Ｓ１５のＮｏ）、ステップＳ１１に戻って配線をやり直す。一方、要求周波数を満たす配置配線が作成できた場合には（Ｓ１５のＹｅｓ）、図５に示す仮の配線処理を終了する。以降では、作成された配置配線に用いられている配線をレイアウトに使用される配線と称する。
【００１８】
次に、図６および図７に示す処理について説明する。仮の配線処理では、要求周波数を満たす配置配線が得られるが、配線の消費電力を削減することは考慮されていない。そこで、プロセッサエレメント１１は、図５に示す仮の配線処理が終了すると、図６および図７に示す再配線処理を開始する。
【００１９】
プロセッサエレメント１１は、まず、要求周波数を満たす範囲内で、現状の配線のクリティカルパスを最大限迂回可能な配線長を算出する（Ｓ２０）。迂回可能配線長ＢＮＵＭの算出は、例えば式（１）によって行う。
BNUM = (1/fR - DPATH)/DCLB ・・・（１）
ここで、ＤＰＡＴＨはクリティカルパスＣＰＡＴＨによって生じる遅延時間を表し、ＤＣＬＢは論理ブロック１辺の長さの配線によって生じる遅延時間を表す。つまり、迂回可能配線長ＢＮＵＭは、ユーザの要求性能を満たす範囲内で、現状の配線のクリティカルパスＣＰＡＴＨから配線を迂回させる場合、論理ブロック何辺分だけ配線を迂回させることができるかどうかを示している。
【００２０】
なお、迂回可能配線長ＢＮＵＭの算出方法は、数１に限らず、ユーザの要求性能とクリティカルパスとを用いた、他の算出方法でも良い。例えば式（２）のような算出方法が考えられる。
BNUM = (LMAX - LC)/LCLB ・・・（２）
ここで、ＬＭＡＸは要求周波数ｆＲを満たす最大の配線の長さを表し、ＬＣはクリティカルパスＣＰＡＴＨの長さを表し、ＬＣＬＢは論理ブロック１辺の長さを表す。
【００２１】
プロセッサエレメント１１は、このようにして算出した迂回可能配線長ＢＮＵＭが２以上であるか否かを判断する（Ｓ２１）。図８（ａ）に示すように、縦方向に配置された論理ブロック１辺分の配線Ｔ１を迂回させる場合、横方向の論理ブロック２辺分の配線Ｔ２、Ｔ３と、縦方向の論理ブロック１辺分の配線Ｔ４の配線が少なくとも必要である。同様に、図８（ｂ）に示すように、横方向に配置された論理ブロック１辺分の配線Ｔ５を迂回させる場合、縦方向の論理ブロック２辺分の配線Ｔ６、Ｔ７と、横方向の論理ブロック１辺分の配線Ｔ８が少なくとも必要である。つまり、クリティカルパスＣＰＡＴＨの配線を迂回させると、少なくとも論理ブロック２辺分配線長が増えることを意味する。
【００２２】
そこで、迂回可能配線長ＢＮＵＭを２と比較することによって、ユーザの要求性能を満たす範囲内で配線を迂回させることが可能であるか否かを判断することができる。そして、迂回可能配線長ＢＮＵＭが２未満であれば（Ｓ２１のＮｏ）、配線処理は終了する。このように事前にユーザの要求性能を満たす範囲内で配線を迂回させることが可能か否かを判断することによって、ユーザの要求性能を満たすことができないにも関わらず配線の迂回を試行するという無駄な処理を省くことができる。
【００２３】
ステップＳ２１で迂回可能配線長ＢＮＵＭが２以上であると判断されると、プロセッサエレメント１１は、配線群内でレイアウトとして使用されている配線の本数によって配線群を分類する（Ｓ２２）。つまり、配線群を構成するｋ本の配線のうち、レイアウトに使用されている配線（以降、使用配線と称する）がｉ本の配線群（０≦ｉ≦ｎ）のものに分類する。そして、再配線が行われたかどうかの判断（Ｓ２８にて後述する）に用いるためのフラグをリセットする（Ｓ２３）。
【００２４】
そして、使用配線が１本の分類Ｇ１を選択し（Ｓ２４）、分類Ｇ１内に配線群が存在するならば（Ｓ２５のＹｅｓ）、図７に示すフローチャートに移り、存在しないならば（Ｓ２５のＮｏ）、現在選択している分類よりも使用配線が１本多い分類を選択して、変数Iがｎとなるまで、ステップＳ２５の処理を繰り返す。
【００２５】
ステップＳ２５において、分類ＧＩに配線群が存在すると判断された場合、プロセッサエレメント１１は、分類ＧＩから任意の配線群ＷＴＡＲＧＥＴを１つ選択する（Ｓ４０）。そして、配線群ＷＴＡＲＧＥＴに含まれるレイアウトに使用されているＩ本の配線それぞれについて、使用配線が１本からｎ本の配線群の配線を使用した迂回経路を算出する（Ｓ４１）。なお、ステップＳ４１で算出される迂回経路が複数ある場合には、最短の迂回経路を選ぶ。
【００２６】
そして、プロセッサエレメント１１は、配線群ＷＴＡＲＧＥＴに含まれる全ての使用配線が配線群ＷＴＡＲＧＥＴとは異なる配線群に迂回可能であるならば（Ｓ４２のＹｅｓ）、元の配線と比較した迂回後の配線の増加長ＢＡＤＤを算出する（Ｓ４３）。なお、配線増加分の長さを示すＢＡＤＤは、迂回可能配線長ＢＮＵＭと比較できるように、論理ブロック何辺分の長さであるかを示す値として算出する。ただし、これに限らず、ＢＡＤＤとＢＮＵＭとが比較できるように両者の単位が揃っていれば良い。
【００２７】
配線増加長ＢＡＤＤが最大迂回配線長ＢＮＵＭよりも短ければ（Ｓ４４のＹｅｓ）、迂回後の配線が要求周波数を満たすことが保障される。そのため、プロセッサエレメント１１は、迂回後の配線を採用する（Ｓ４５）。迂回後の配線が採用される場合には、式（３）に示すように、配線群ＷＴＡＲＧＥＴの分類が使用配線０本の分類に変更され、最大迂回配線長ＢＮＵＭの値が更新される。さらに、配線群ＷＴＡＲＧＥＴの配線の迂回に用いられた配線を含む配線群の分類が、迂回配線採用後の使用配線数に応じて変更される。
Ｇ０＝Ｇ０∪｛ＷＴＡＲＧＥＴ｝
ＧＩ＝ＧＩ−｛ＷＴＡＲＧＥＴ｝
ＢＮＵＭ＝ＢＮＵＭ−ＢＡＤＤ ・・・（３）
ステップＳ４５にて、迂回経路を採用する処理が終了すると、プロセッサエレメント１１は、再配線が行われたことを示すフラグをセットする（Ｓ４６）。そして、最大迂回配線長ＢＮＵＭが２未満ならば（Ｓ４７のＮｏ）、これ以上配線を迂回させることができないため、図６のステップＳ２９にて再配線後のクリティカルパスを計算し、ステップＳ２０からの処理を繰り返す。それに対して、最大迂回配線長ＢＮＵＭが２以上ならば（Ｓ４７のＹｅｓ）、ステップＳ２５に戻り、分類ＧＩに含まれる配線群の再配線処理を行う。
【００２８】
ステップＳ４４において、配線増加長ＢＡＤＤが最大迂回配線長ＢＮＵＭよりも長い場合（Ｓ４４のＮｏ）や、配線群ＷＴＡＲＧＥＴの使用配線の内、少なくとも１本の使用配線が迂回できない場合（Ｓ４２のＮｏ）、迂回後の配線は採用されない（Ｓ４８）。迂回後の配線が採用されない場合には、配線群ＷＴＡＲＧＥＴが処理済であることが判別するための情報を付与する。例えば、処理済の配線群を示す分類ＧＦＩＮＩＳＨを設け、式（４）に示すように、配線群ＷＴＡＲＧＥＴを分類ＧＦＩＮＩＳＨに移動させることによって、処理済を判別させる。
ＧＦＩＮＩＳＨ＝ＧＦＩＮＩＳＨ∪｛ＷＴＡＲＧＥＴ｝
ＧＩ＝ＧＩ−｛ＷＴＡＲＧＥＴ｝ ・・・（４）
そして、ステップＳ４８の処理が終了すると、ステップＳ２５に戻り、分類ＧＩに含まれる配線群の再配線処理を行う。なお、最大迂回配線長ＢＮＵＭが２以上の状態で、全ての分類Ｇ１〜Ｇｎ−１に含まれる全ての配線群に対する再配線処理が終了すると（Ｓ２７のＹｅｓ）、ステップＳ２８にて、迂回配線が採用されたかどうかが判断され、迂回配線が採用されていなければ（Ｓ２８のＮｏ）、配線処理を終了する。迂回配線が採用されたかどうかは、再配線が行われたことを示すフラグによって判断できる。
【００２９】
以上説明したような処理によれば、要求周波数を満たしている配線を基にして、要求周波数を満たしながら、レイアウトに使用される配線が無い配線群の数を増やした配線を得ることができる。
【００３０】
なお、本実施形態では、使用配線が少ない分類に含まれる配線群から順に再配線処理を行ったが、再配線処理を行う順番はこれに限られない。例えば、配線群を、使用配線が０本の分類、使用配線がｎ本の分類、および使用配線が１本〜（ｎ−１）本のいずれかである分類の３つに分け、使用配線が１本〜（ｎ−１）本のいずれかの配線群から任意の順で再配線処理を行っても良い。
【００３１】
図６および図７を用いて説明した再配線処理では、処理の終了条件は、最大迂回配線長ＢＮＵＭが２よりも小さくなった場合か、最大迂回配線長ＢＮＵＭを算出した後に、いずれの配線群も迂回配線が採用されなかった場合の２つである。しかしながら、採用された配置配線によっては、最大迂回配線長ＢＮＵＭが２以上であっても、これ以上再配置することができない場合がある。そこで、上述の終了条件だけでなく、以下の変形例１〜３に示すような終了条件を加えても良い。なお、以下の変形例のフローチャートでは、図６、図７を用いて説明した処理と同じ処理には同じ番号を付与し、詳細な説明を省略する。
【００３２】
（変形例１）
例えば、最大迂回配線長ＢＮＵＭが２の場合、再配置計算を行っていない配線群の使用配線数がいずれも２以上であるならば、例え１本の使用配線を迂回することができたとしても、他の使用配線を迂回することができない。つまり、使用配線の本数が少ない分類に含まれる配線群から順に再配置計算を行う場合、最大迂回配線長ＢＮＵＭが２×Ｉ（Ｉは、使用配線の本数）未満となると、使用配線の全てを迂回させることはできない。
【００３３】
そこで、図６に示した処理に代えて図９のように、最大迂回配線長ＢＮＵＭと２×Ｉとを比較し（Ｓ１０１）、最大迂回配線長ＢＮＵＭが２×Ｉ以上ならば（Ｓ１０１のＹｅｓ）、ステップＳ４０へ進み、分類ＧＩ内の配線群の再配線処理を行い、最大迂回配線長ＢＮＵＭが２×Ｉ未満ならば（Ｓ１０１のＮｏ）、ステップＳ２８の処理に進むことで、再配置できないにもかかわらず再配置を試みる処理を行うことを防ぐことができる。
【００３４】
（変形例２）
迂回配線が何度も連続で採用されなかった場合、その時点で配線処理を終了させても良い。図１０及び図１１は、迂回経路の不採用が所定の回数（ＮＦ回）を超えた時点で配線処理を終了させる場合のプロセッサエレメント１１の処理を示すフローチャートである。
【００３５】
図１０及び図１１に示す処理において、迂回経路の不採用回数をカウントする変数Ｎｃｏｕｎｔを用いる。変数Ｎｃｏｕｎｔは、迂回経路の探索が行われる前に（例えば、図１０のステップＳ１１１）、０にリセットされる。そして、図１１のステップＳ４８にて迂回経路が採用されなかった場合には、変数Ｎｃｏｕｎｔが１増加する（Ｓ１１２）。そして、変数Ｎｃｏｕｎｔが閾値ＮＦよりも大きくなった場合（Ｓ１１３のＹｅｓ）、配線処理を終了する。一方、図１１のステップＳ４５にて迂回経路が採用された場合には、変数Ｎｃｏｕｎｔが０にリセットされる（Ｓ１１４）。
【００３６】
（変形例３）
予め再配置計算対象の分類を定め、再配置計算対象の分類に含まれる配線群の再配置計算が終了すると、処理を終了させても良い。そのためには、図６に示した処理に代えて図１２に基づいて処理を行う。図１２に示す処理では、再配置計算を行う前に（例えば図１２のＳ１２１）再配置計算対象の分類を設定する。ここでは、何本の使用配線の分類に属する配線群までが再配線出来る可能性を持っているのかを式（５）および式（６）により計算する。
【数１】
ここで、Ｒｉは、横方向の配線から成る配線群であり、使用配線の本数がｉ本である配線群の数を表す。また、Ｃｉは、縦方向の配線群であり、使用配線の本数がｉ本である配線群の数を表す。プロセッサエレメント１１は、式（５）および式（６）の両方を満たすように再配線対象分類の最大使用配線数Ｊを求める。
【００３７】
配線群の中で、レイアウトに使用されている配線がｉ本の縦方向の配線である場合、迂回配線として横方向の配線を２×ｉ本と縦方向の配線ｉ本が必要である。また、レイアウトに使用されている配線がｉ本の横方向の配線である場合、迂回配線として横方向の配線をｉ本と縦方向の配線を２×ｉ本が必要である。
【００３８】
式（５）の左辺は、配線群内のレイアウトに使用されている配線が１〜Ｊ本であると分類された配線群に含まれる配線を全て迂回させるときに必要な横方向の配線の本数を表している。式（５）の右辺は、配線群内のレイアウトに使用されている配線が（Ｊ＋１）本〜ｎ本であると分類された配線群に含まれるレイアウトに使用されていない横方向の配線の合計本数を表している。つまり、式（５）では、配線群内のレイアウトに使用されている配線が１〜Ｊ本であると分類された配線群に含まれる配線を全て迂回させる場合に、迂回先となる横方向の配線が足りるか否かを検証している。
【００３９】
同様に、式（６）では、配線群内のレイアウトに使用されている配線が１〜Ｊ本であると分類された配線群に含まれる配線を全て迂回させる場合に、迂回先となる縦方向の配線が足りるか否かを検証している。そして、式（５）および式（６）を満たすＪを探索し、レイアウトに使用されている配線が１〜Ｊ本の配線群を配線迂回の候補とする。
【００４０】
このような変形例を用いることによって、再配線の処理にかかる時間を短縮し、より短時間で配線経路を得ることができる。なお、変形例１〜３は複数を組み合わせて使用しても良い。
【００４１】
以上説明したように、本発明の実施形態やその変形例の構成をとることで、要求周波数を満たしながら、レイアウトに使用される配線が無い配線群の数ができるだけ多くなるよう配線することができる。使用されない配線群の電源はＯＦＦにすることができるため、消費電力を削減することができる。
【００４２】
なお、上記実施形態に限定されることはなく、本発明の要旨を逸脱しない範囲において、適宜変更しても良い。
【符号の説明】
【００４３】
１…ＰＣ、 １０…プロセッサ、 １１…プロセッサエレメント、 １２…キャッシュ、 ２０…メインメモリー、 ３０…ハードディスク、 ４０…入出力装置、 ２１…Ｎ型ＭＯＳＦＥＴ、 ２２…Ｐ型ＭＯＳＦＥＴ、 ２３…メモリー、 ２４，２５，２６…インバータ、 ２７，２８，２９…トランジスタ
【特許請求の範囲】
【請求項１】
所定の動作周波数を満たすように第１の配線を求め、
前記所定の動作周波数と前記第１の配線のクリティカルパスとを用いて最大迂回配線長を算出し、
集積回路の配線を複数の群に分けた場合に、配線群に含まれる前記第１の配線を、前記第１の配線を含む他の配線群内の配線を用いて迂回することで第２の配線を求め、
前記第２の配線と前記第１の配線との差分が前記最大迂回配線長以下ならば、前記第２の配線によって前記第１の配線を更新し、前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きければ、前記第１の配線を更新しないことを特徴とする集積回路の配線方法。
【請求項２】
前記最大迂回配線長が集積回路の論理ブロック２辺分の長さよりも短い場合には、迂回経路を求める処理を行わずに、前記第１の配線を更新しないことを特徴とする請求項１に記載の集積回路の配線方法。
【請求項３】
前記迂回経路を再配線された配線として採用した場合に、前記第２の配線と前記第１の配線の差分を用いて前記最大迂回配線長を更新し、更新された最大迂回配線長が集積回路の論理ブロック２辺分の長さよりも長い場合には、前記第１の配線群とは異なる第２の配線群に対して迂回経路の算出を行うことを特徴とする請求項１または２に記載の集積回路の配線方法。
【請求項４】
前記迂回経路を再配線された配線として採用した場合に、前記迂回経路と前記第１の配線の差分を用いて前記最大迂回配線長を更新し、更新された最大迂回配線長が集積回路の論理ブロック２辺分の長さよりも短い場合には、再配線された配線のクリティカルパスを算出し、前記所定の動作周波数と前記再配線された配線のクリティカルパスとを用いて最大迂回配線長を更新し、更新された最大迂回配線長が集積回路の論理ブロック２辺分の長さよりも長い場合には、前記第１の配線群とは異なる第２の配線群に対して迂回経路の算出を行うことを特徴とする請求項１乃至３のいずれかに記載の集積回路の配線方法。
【請求項５】
前記迂回経路の算出は、前記第１の配線に使用されていない配線が１以上であって他の配線群よりも少ない本数である配線群を前記第１の配線群として迂回経路の算出を行う処理であって、前記第１の配線群で前記第１の配線に使用されていない配線の本数をＩとしたときに、前記最大迂回配線長が集積回路の論理ブロック２辺分のＩ倍である場合には、前記迂回経路の算出処理を行わずに配線処理を終了することを特徴とする請求項１乃至４のいずれかに記載の集積回路の配線方法。
【請求項６】
前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きく、前記第１の配線を更新しない状態が生じた回数をカウントし、この回数が所定の回数を上回ると、配線処理を終了することを特徴とする請求項１乃至５のいずれかに記載の集積回路の配線方法。
【請求項７】
前記迂回経路の算出を行う配線群を予め設定し、この中の１つの配線群を前記第１の配線群として迂回経路の算出を行う請求項１乃至６のいずれかに記載の集積回路の配線方法。
【請求項８】
コンピュータに、
所定の動作周波数を満たすように第１の配線を算出する手段と、
前記所定の動作周波数と前記第１の配線のクリティカルパスとを用いて最大迂回配線長を算出する手段と、
集積回路の配線を複数の群に分けた場合に、配線群に含まれる第一の配線を、第１の配線を含む他の配線群内の配線を用いて迂回させることで第２の配線を算出する手段と、
前記第２の配線と前記第１の配線との差分が前記最大迂回配線長以下ならば、前記第２の配線によって前記第１の配線を更新し、前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きければ、前記第１の配線を更新しない手段とを実行させることを特徴とする集積回路の配線プログラム。
【請求項９】
請求項８に記載の集積回路の配線プログラムを記録したコンピュータ読み取り可能な記憶媒体。
【請求項１】
所定の動作周波数を満たすように第１の配線を求め、
前記所定の動作周波数と前記第１の配線のクリティカルパスとを用いて最大迂回配線長を算出し、
集積回路の配線を複数の群に分けた場合に、配線群に含まれる前記第１の配線を、前記第１の配線を含む他の配線群内の配線を用いて迂回することで第２の配線を求め、
前記第２の配線と前記第１の配線との差分が前記最大迂回配線長以下ならば、前記第２の配線によって前記第１の配線を更新し、前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きければ、前記第１の配線を更新しないことを特徴とする集積回路の配線方法。
【請求項２】
前記最大迂回配線長が集積回路の論理ブロック２辺分の長さよりも短い場合には、迂回経路を求める処理を行わずに、前記第１の配線を更新しないことを特徴とする請求項１に記載の集積回路の配線方法。
【請求項３】
前記迂回経路を再配線された配線として採用した場合に、前記第２の配線と前記第１の配線の差分を用いて前記最大迂回配線長を更新し、更新された最大迂回配線長が集積回路の論理ブロック２辺分の長さよりも長い場合には、前記第１の配線群とは異なる第２の配線群に対して迂回経路の算出を行うことを特徴とする請求項１または２に記載の集積回路の配線方法。
【請求項４】
前記迂回経路を再配線された配線として採用した場合に、前記迂回経路と前記第１の配線の差分を用いて前記最大迂回配線長を更新し、更新された最大迂回配線長が集積回路の論理ブロック２辺分の長さよりも短い場合には、再配線された配線のクリティカルパスを算出し、前記所定の動作周波数と前記再配線された配線のクリティカルパスとを用いて最大迂回配線長を更新し、更新された最大迂回配線長が集積回路の論理ブロック２辺分の長さよりも長い場合には、前記第１の配線群とは異なる第２の配線群に対して迂回経路の算出を行うことを特徴とする請求項１乃至３のいずれかに記載の集積回路の配線方法。
【請求項５】
前記迂回経路の算出は、前記第１の配線に使用されていない配線が１以上であって他の配線群よりも少ない本数である配線群を前記第１の配線群として迂回経路の算出を行う処理であって、前記第１の配線群で前記第１の配線に使用されていない配線の本数をＩとしたときに、前記最大迂回配線長が集積回路の論理ブロック２辺分のＩ倍である場合には、前記迂回経路の算出処理を行わずに配線処理を終了することを特徴とする請求項１乃至４のいずれかに記載の集積回路の配線方法。
【請求項６】
前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きく、前記第１の配線を更新しない状態が生じた回数をカウントし、この回数が所定の回数を上回ると、配線処理を終了することを特徴とする請求項１乃至５のいずれかに記載の集積回路の配線方法。
【請求項７】
前記迂回経路の算出を行う配線群を予め設定し、この中の１つの配線群を前記第１の配線群として迂回経路の算出を行う請求項１乃至６のいずれかに記載の集積回路の配線方法。
【請求項８】
コンピュータに、
所定の動作周波数を満たすように第１の配線を算出する手段と、
前記所定の動作周波数と前記第１の配線のクリティカルパスとを用いて最大迂回配線長を算出する手段と、
集積回路の配線を複数の群に分けた場合に、配線群に含まれる第一の配線を、第１の配線を含む他の配線群内の配線を用いて迂回させることで第２の配線を算出する手段と、
前記第２の配線と前記第１の配線との差分が前記最大迂回配線長以下ならば、前記第２の配線によって前記第１の配線を更新し、前記第２の配線と前記第１の配線の差分が前記最大迂回配線長よりも大きければ、前記第１の配線を更新しない手段とを実行させることを特徴とする集積回路の配線プログラム。
【請求項９】
請求項８に記載の集積回路の配線プログラムを記録したコンピュータ読み取り可能な記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１３−４５２９４（Ｐ２０１３−４５２９４Ａ）
【公開日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願番号】特願２０１１−１８２８３３（Ｐ２０１１−１８２８３３）
【出願日】平成２３年８月２４日（２０１１．８．２４）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願日】平成２３年８月２４日（２０１１．８．２４）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]