(57)【要約】【課題】ＦＰＧＡを操作して、その最適により、エッジによって接続された複数の頂点を有するグラフの望ましいパーティショニングが表される関数を計算する方法が提供される。【解決手段】本発明の一実施例によれば、ＦＰＧＡは、複数のセルを有する区画状態レジスタを備える。各セルは、グラフの頂点の１つに対応し、対応する頂点の現在割り当てられている区画を表す番号を記憶するために用いられる。個々の区画に対する頂点の割り当ては、コスト関数が最小になるように行われる。頂点の任意の割り当てに関して、ＦＰＧＡは、ＦＰＧＡから構成される２つの回路を利用して、コスト関数の計算を行う。第１の回路は、異なる区画に属する頂点を接続するエッジ数を計算する。第２の回路は、個々の区画のサイズが互いに異なる程度を表した数を計算する。理想のパーティショニングは、これら計算された数の重み付きの和を最小化するパーティショニングである。【選択図】図１
2007035065.tif 000002
【特許請求の範囲】
【請求項１】
複数の直列接続されたセルを有し、前記直列セルが、最初のセルと、最後のセルと、１つ以上の中間セルとを有し、前記各セルが、２進状態を記憶し状態値を出力する回路と出力端子とを有し、前記セルの次の状態が、該セルの現在の状態と第１および第２の入力との関数であり、前記各中間セルの前記第１および第２の入力が、それぞれ、前記直列をなす前記中間セルの各側におけるセルの前記状態出力に接続されるように前記中間セルが接続され、前記最初のセルの入力の１つが、出力が、２を法とする前記セル状態のすべての和である回路に接続される、シーケンスをなす乱数を発生する回路。
【請求項２】
制御値によって決定される１の密度を有し、１の配置がランダムである２進ベクトルを発生する回路であって、
シフトすべき２進値を受信するための入力を有する第１のシフト・レジスタであって、各セルが該セルに記憶された値を示す出力を有する、前記受信された２進値がシフトされる複数のセルと、第１のシーケンスをなす乱数を出力する第１の乱数発生回路と、前記第１のシフト・レジスタの前記入力に接続された出力を有し、前記第１のシーケンスをなす乱数における各数と第１の値とを比較する第１のコンパレータと、を有する第１のシフト・レジスタと、
シフトすべき２進値を受信するための入力を有する第２のシフト・レジスタであって、各セルが該セルに記憶された値を示す出力を有する、前記受信された２進値がシフトされる複数のセルと、第２のシーケンスをなす乱数を出力する第２の乱数発生回路と、前記第２のシフト・レジスタの前記入力に接続された出力を有し、前記第２のシーケンスをなす乱数における各数と第２の値とを比較する第２のコンパレータと、を有する第２のシフト・レジスタと、
前記第１および第２のシフト・レジスタにおける対応する前記セルの出力に接続され、前記２進ベクトルのビットを発生する回路と、
を備えている回路。
【請求項３】
前記２進ベクトルのビットを発生する前記回路が、各ＡＮＤゲートの一方の入力が前記第１のシフト・レジスタのビットに接続され、他方の入力が前記第２のシフト・レジスタのビットに接続された、複数の２ビットＡＮＤゲートを備えている、請求項２に記載の回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータに関するものであり、とりわけ、グラフ・パーティショニング問題を解決するためのフィールド・プログラマブル・ゲート・アレイに関するものである。
【背景技術】
【０００２】
この論述のために、プログラマブル論理回路は、高速で、任意のトポロジの他のデジタル・システムをエミュレートするため、ユーザによる構成が可能な固定接続性のデジタル回路要素と定義される。その利用によって、高速論理シミュレータを創造し、かつ、所定のタスクにおいて何分の１かのコストでスーパコンピュータの性能をしのぐことが可能な構成可能コンピュート・エンジンを創造することが可能になる。大形デジタル回路（何十万のゲートを備える）のエミュレートが可能なプログラマブル論理システムは、高価で、一般に、エミュレートされる各ゲート当たり約２〜４ドルのコストがかかり、複数の複雑なプリント回路基板にわたって多数の集積回路を分散する必要がある。
【０００３】
あるクラスのプログラマブル論理回路は、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）・テクノロジをベースにしたものである。このアプローチでは、固定トポロジをなすように互いに接続されたいくつかのＦＰＧＡが利用される。各ＦＰＧＡには、２タイプの資源、すなわち、（１）特定の論理機能（「ＡＮＤ」または「ＥＸＣＬＵＳＩＶＥ ＯＲ」のような）を実施するようにプログラミングまたは構成可能ないくつかのプログラマブル論理セル（ＰＬＣ）、及び、（２）論理セルを互いに、及び、外部入力／出力ピンと相互接続するようにプログラミングすることが可能な経路選択資源が含まれている。プログラミングされたＦＰＧＡは、従って、シミュレートすべき論理システム全体のサブセットである有用な論理回路を形成し、ＦＰＧＡをまとめたセット全体は、従って、所望の論理システムをシミュレートすることになる。こうしたアーキテクチャをなすＦＰＧＡは、それらの間において、変更できない固定された物理的接続を有しているので、論理システムをシミュレートするには、相互接続されたＦＰＧＡに問題となる論理システムの回路のマッピングを施して、もとの回路の論理機能及び相互接続が、ＦＰＧＡのプログラミングによって精確に表現されるようにする必要がある。ＦＰＧＡ内の論理セルが並列に計算を実施し、経路選択ネットワークを通じてその結果を互いに伝達するので、高速シミュレーションが可能である。
【０００４】
ＦＰＧＡをベースにしたコンピュータの潜在速度によって、解決すべき問題に合うように、そのアーキテクチャを適応させるクラスの再構成可能コンピュータが得られることになった。こうしたコンピュータのマシン・サイクル時間は、従来の高性能ワークステーションよりも１桁〜２桁遅くなる可能性があるとしても、多くの問題の暗黙的並列性を利用する能力によって、従来のコンピュータに比べると、性能利得が数桁分とかなりのものになる。
【０００５】
ＦＰＧＡベースのコンピュータを用いることが有益に働く可能性のある問題のクラスの１つは、グラフ・パーティショニング問題のクラスである。グラフは、エッジによって互いに接続された頂点の集合である。いくつかの問題は、区画間にわたるエッジ数を最小限に抑えることになる、グラフの頂点のパーティショニングを見つけ出すということに還元することができる。
【０００６】
例えば、集積回路は、頂点が回路素子に対応し、エッジが各種素子間の接続に対応するグラフで表現することが可能である。大きすぎて、単一チップに納まらない、従って、２つのチップを１セットとして構成しなければならない集積回路について考察することにする。チップ間の接続コストは、極めて高いので、設計者は接続数を最小限に抑えようとする。設計者が直面する問題は、接続数すなわち２グループ間のエッジ数が最小限で、ほぼ等しいサイズの２つのグループになる、回路素子の分割、すなわち、パーティショニングを見つけ出すことである。
【０００７】
頂点の任意のパーティショニングに関して、パーティショニングによってカットされるエッジ数と、区画のサイズの類似度によって決まる、コスト関数が発生する可能性がある。この問題は、可能性のある全ての区画の集合に対するこのコスト関数の極小を見つけ出すということに還元される。大きいグラフの場合、可能性のある全ての区画の集合は、天文学的な大きさになり、従って、可能性のある解を探究する何らかの方法が必要になる。
【０００８】
このタイプの最適化を解決する際に一般に用いられる技法の１つは、シミュレーション式アニーリングと呼ばれるものである。この技法では、探索される表面が基本的に平滑であるが、いくつかの極小を有する可能性があるものと仮定する。始めに、可能性のある解の全範囲にわたってランダムにポイントが選択される。実際に極小を含んでいる可能性のある解の領域に関して、より良い推定値が得られるにつれて、探索領域は、これまで見つかった最良の解に基づいて常に縮小を続ける領域に制限される。
【０００９】
グラフ問題に関して、該技法についてより精確に述べると、次のようになる。最初に、ランダムに初期区画が選択される。この区画は、現在の最適解と現在のワーキング解の両方になる。現在のワーキング解を用いて、区画間においてランダムな頂点の移動が行われる。新しいコストが評価される。ワーキング解のコストが現在の最適解以下であれば、ワーキング解が現在の最適解になる。コストが現在の最適解より高くなるが、その解が現在の最適解のある指定の範囲内に納まる場合、新しい解が、現在のワーキング解になる。この結果、該アルゴリズムが、現在の最適解の近傍における解空間を探って、「極小から脱却する」ことが可能になる。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
一般に、本発明の目的は、ＦＰＧＡベースのコンピュータを用いて、グラフ・パーティショニング問題を解決するための改良された方法を提供することにある。
【００１１】
本発明のもう１つの目的は、グラフのランダム区画を発生するようにＦＰＧＡベースのコンピュータを構成するための方法を提供することにある。
【００１２】
本発明のさらにもう１つの目的は、ＦＰＧＡベースのコンピュータに対するグラフ・パーティショニング・コスト関数のマッピングが行えるようにすることである。
【００１３】
本発明の以上の及び他の目的については、当該技術の熟練者には後述の実施例及び添付の図面から明らかになる。
【課題を解決するための手段】
【００１４】
本発明は、ＦＰＧＡを操作して、その最適がエッジによって接続された複数の頂点を有するグラフの望ましいパーティショニングを表す関数を計算する方法から構成される。本発明の望ましい実施例の場合、ＦＰＧＡは、複数のセルを有する区画状態レジスタを提供するように構成される。各セルは、グラフの頂点の１つに対応し、対応する頂点が現在割り当てられている区画を表す番号を記憶するために用いられる。最適区画を判定するアルゴリズムは、２つの要素を備えるコスト関数を計算する。個々の区画に対する頂点の割り当ては、このコスト関数が最小になるように行われる。頂点の任意の割り当てに関して、ＦＰＧＡは、ＦＰＧＡから構成される２つの回路を利用して、コスト関数の計算を行う。第１の回路は、異なる区画に属する頂点を接続するエッジ数を計算する。第２の回路は、個々の区画のサイズが互いに異なる程度を表した数を計算する。理想のパーティショニングは、これら計算された数の重み付きの和を最小化するパーティショニングである。
【００１５】
上述の２つの「コスト」を計算するように構成されたＦＰＧＡを利用するコンピュータが、可能性のあるさまざまな区画の解を探ることができる速度を増すため、本発明の望ましい実施例では、少数の１がランダムに分配されている２進「状態変更」ベクトルの計算を行う特殊回路が利用される。各１は、探索アルゴリズムの次の繰り返しでその区画割り当てが変更されることになる頂点を表している。探索効率を高めるため、ＦＰＧＡから構成されるもう１つの回路を利用して、区画の境界上にない頂点に対応する１にマスキングが施される。
【００１６】
望ましい状態変更ベクトル発生回路は、乱数発生器によって提供される２つのシフト・レジスタを利用する。本発明では、それによって発生する対称パターン数を減少させるための特殊なフィードバック・システムを備えた乱数発生器を利用している。
【発明を実施するための最良の形態】
【００１７】
特定のグラフに関して、頂点は区画状態レジスタ（ＰＳＲ）と称される大レジスタのエントリによって表現することが可能である。グラフがｋ個の区画に分割すべきＮ個の頂点を備えている場合、ＰＳＲは、それぞれ、「ｌｏｇ2ｋビット」を有するＮ個のセルを備えることになる。各セルの値は、その頂点が現在割り当てられている区画の番号である。区画問題の解決は、２つのＰＳＲ、すなわち、現在の最適解に関するＰＳＲと現在のワーキング解に関するＰＳＲを用いて実施するのが望ましい。
【００１８】
任意の区画に関して、コンピュータは、区画の「コスト」を求めなければならない。本発明の場合、コストは、現在のワーキング解を保持するＰＳＲにおける個々のセルに接続された論理セルを介して、単一マシン・サイクルで求められる。さらに詳細に後述するように、特定の論理回路接続は、分割されるグラフにどのエッジが存在するかによって決まる。区画コストは、２つの要素コスト、すなわち、カットされるエッジ数を表すコスト・ペナルティと、区画サイズ間の不均衡を表すコスト・ペナルティによって決まる。
【００１９】
最も単純な形の場合、２つの要素コストは等しい重み付けが施されるが、当該技術の熟練者には明らかなように、他の重み付け構成を利用することも可能である。例えば、ネット・リストを２つの集積回路に分割する場合、２つの等サイズの回路を備えるよりも、Ｉ／Ｏピンを最小限に抑えるほうが有益である。この場合、カット・サイズ要素の重みを大きくすることになる。コストのカット・サイズ要素は、異なる区画における頂点を接続するエッジ数である。Ｃは次にようにして求められる：
【００２０】
【数１】
2007035065.tif 000003
【００２１】
ここで、ｎは頂点の数であり、Ｅijは、頂点ｉ及びｊがエッジによって接続されている場合には１で、別様の場合には０になり、Ｐijは、頂点ｉ及びｊが異なる区画にある場合には１で、別様の場合には０になる区画クロス関数である。コストの不均衡要素Ｂは、理想の区画サイズからの偏差を示す全ての区画の和である。本発明の望ましい実施例の場合、Ｂは次のようにして求められる：
【００２２】
【数２】
2007035065.tif 000004
【００２３】
ここで、ｋは区画数であり、Ｍijは、頂点ｊが区画ｉのメンバである場合には、１になる。
【００２４】
次に、コスト関数回路１０を示す図１を参照して、コスト関数計算がＦＰＧＡにマッピングされる方法についてさらに詳述することにする。ＰＳＲ１１の各セルには、０〜ｋ−１の数が含まれており、ｋは区画数である。グラフがＩ番目とＪ番目の頂点を接続するエッジを備えている場合、図１に１２で示すように、コンパレータの入力は、ＰＳＲのＩ番目とＪ番目のセルに接続される。エッジによって接続される頂点の各対毎に、こうしたコンパレータが１つずつ設けられている。Ｍ番目とＮ番目の頂点に対応する第２のコンパレータが１３で示されている。コンパレータの出力は、２つの入力が等しくなければ１になり、別様であれば０になる。従って、カット・サイズ・コスト関数は、全コンパレータ回路の出力の和である。この和は、桁上げ保存型加算器１４によって計算される。ｋ＝２の場合、コンパレータ回路は、排他的ＯＲ回路に置き換えることが可能である。
【００２５】
次に、図２を参照して、ｋ分割区画に関する不均衡コストが得られるようにする、不均衡コスト関数を計算するための望ましいハードウェア構成についてさらに詳述することにする。上述のように、ＰＳＲ１１の各セルには、各区画に対応する１つのセルが含まれている。各区画の理想のサイズは、ｋ／ｎと仮定される。ＰＳＲ１１の各セルには、ｋ分割部分デコーダが接続されている。典型的なデコーダが２１〜２３で示されている。デコーダの出力の和が、ｋ桁上げ保存型加算器において求められる。典型的な加算器が３１〜３３で示されている。各加算器の和と理想の区画サイズの差は、差分回路で計算される。加算器３１〜３３に対応する差分回路が、それぞれ、４１〜４３で示されている。各差分回路の出力は、絶対値回路に入力される。差分回路４１〜４３に対応する絶対値回路が、それぞれ、５１〜５３で示されている。最後に、絶対値回路の全ての出力が、桁上げ保存型加算器６０によって計算される。
【００２６】
ｋ＝２、すなわち、グラフを２分割する場合、図２に示すデコーダを排除することが可能である。この場合、理想サイズからのサイズの偏差は、もう一方の区画サイズが同じになるので、一方の区画についてしか計算されない。この近似は、最終結果に２を掛けて補正することが可能であるが、これは、２つのコスト要素の相対的重みの変更に相当する。
【００２７】
次に、試算の解を発生する方法についてさらに詳述することにする。既存のＰＳＲを利用して、長さの等しいベクトルである区画状態変更ベクトルとの排他的ＯＲ演算を施すことによって、試算の解が発生する。変更ベクトルが位置Ｌに１を含んでいる場合、この操作によって、ＰＳＲの対応するビットが変化する。変更ベクトルにまばらにランダムな１の分布を施すことによって、現在のＰＳＲの近傍における解空間が探索される。２つの順次ＰＳＲベクトル間の距離は、変更ベクトルにおける１の数によって決まり、該距離は、変更ベクトルにおける１の数が増すにつれて拡大する。上述のように、アニーリング・アルゴリズムは、長い有効距離で開始され、探索が進むにつれて、距離が短縮される。従って、該アルゴリズムは、変更ベクトルにおける１の数を制御しさえすればよい。
【００２８】
次に、本発明に基づいて区画変更ベクトルを発生するための回路７０のブロック図である図３を参照することにする。回路７０は、ｎビット・シフト・レジスタ８１及び８２のそれぞれの対応するビットを２入力ＡＮＤゲートに接続することによって、この２つのレジスタから変更ベクトルを発生し、こうしたＡＮＤゲートはｎ個設けられている。パルス密度の制御が可能な２つの非相関パルス・ストリームを用いて、２つのシフト・レジスタに供給される。一方のストリームは、ビットを左から右にシフトする第１のシフト・レジスタ８１に加えられ、もう一方のストリームは、ビットを右から左にシフトする第２のシフト・レジスタ８２に加えられる。２つのシフト・レジスタにおける２つの対応するビット間に一致が生じる毎に、対応するＡＮＤゲートの出力から１が発生する。変更ベクトルは、ＡＮＤゲートの出力から構成される。結果生じる変更ベクトルにおける１の密度が、加えられた２つのパルス・ストリームのパルス密度の積によって決まるのは明らかである。
【００２９】
本発明の望ましい実施例の場合、パルス密度を指定する基準値を備えたデジタル・コンパレータに乱数を加えることによって、パルス密度関数の制御可能なパルス・ストリームが発生する。シフト・レジスタ８２に対する供給に用いられる乱数発生器が、７２で示されている。対応するデジタル・コンパレータは、それぞれ、７４及び７５で示されている。デジタル・コンパレータの基準入力は、共通の密度制御レジスタ７３から供給されるのが望ましい。乱数が基準値未満の場合、コンパレータ値は１になり、そうでなければ、０になる。これによって、この問題は、２つのシーケンスをなす乱数の発生に還元される。
【００３０】
当該技術の熟練者には明らかなように、セルラー・オートマトンの１次元アレイによって、乱数シーケンスを得ることが可能である。あいにく、先行技術によるセルラー・オートマトンをベースにした乱数発生器は、対称データ・パターンのシーケンスを発生する。本発明では、モジュロ２の加法によるフィードバック項を含む新規のオートマトン・アレイを利用して、こうしたパターンを破壊することによって、この問題を回避している。
【００３１】
乱数発生器に用いられる基本セルが、図４に１００で示されている。このセルの次の状態は、該セルの現在の状態と線形アレイにおけるその左と右の近傍セルの状態との関数である。この３つのセル間において、１にセットされた現在の出力数が奇数であれば、基本セルの次の状態は１になり、別様であれば、次の状態は０になる。こうしたセルは、２つのフリップ・フロップ１０１及び１０２、ＸＯＲゲート１０３、及び、その入力の１つまたは３つが論理１にセットされている場合には、その出力が１になる回路１０４から構成することが可能である。このタイプのセルは、当該技術において既知のところである。図面を簡略化するため、フリップ・フロップ及び他の論理素子に対するクロック入力は省略されている。本発明では、図５に１１０で示すように、パイプライン処理されるモジュロ２の加法によるフィードバック項を利用して、アレイ内の対称パターンを破壊する。乱数のビットは、アレイ内において互いに最大限に分離された選択セルから取り出される。こうして出力を互いに離すことによって、ビット間の相関関係が軽減される。
【００３２】
一般に、上述のアルゴリズムによれば、最適な区画が見つかるが、試算の解を区画の境界上の点に制限すれば、最適区画を見つけるのに必要な時間を大幅に短縮することが可能になる。従って、本発明の望ましい実施例では、区画状態変更ベクトルを制限して、区画の境界上の頂点だけにしか再割り当てが行われないようにすることによって、そうした解の制限が可能になる。
【００３３】
上述のように、グラフにおける比較的少数の頂点に割り当てられる区画を変更することによって、試算の解が発生する。一般に、これは、現在の区画状態レジスタを用いた区画変更ベクトルの排他的ＯＲ演算によって実施される。グラフが２つのグループに分割される単純な事例について考察することにする。区画変更ベクトルが、頂点ｋに対応する位置に１を含んでいる場合、頂点ｋは、その現在の区画割り当てから代替区画にスイッチされる。
【００３４】
次に、別様であれば区画の境界上になかった試算の解をもたらすことになる、区画変更ベクトルのビットにマスキングを施すための回路２００の略図である、図６を参照することにする。回路２００は、ＰＳＲ１１に接続されており、状態割り当てを調べて、どの頂点が区画のエッジ上にあるか判定する。ある頂点が異なる区画の頂点に接続されている場合、その頂点は区画の境界上にある。従って、回路２００には、グラフの各エッジ毎にＸＯＲゲートが含まれている。典型的なＸＯＲゲートが、２１２及び２１３で示されている。対応するエッジによって接続される頂点が、異なる区画にある場合、ＸＯＲゲートの出力は真になる。
【００３５】
回路２００には、対応する頂点に接続された各エッジに関するファン・インが１の、各頂点に対応するＯＲゲートも含まれている。典型的なＯＲゲートが、２１５及び２１６で示されている。頂点が区画の境界上に位置する場合、頂点に対応するＯＲゲートの出力は真になる。回路２００の目的は、現在のＰＳＲの内容の変更を境界上の頂点に関する頂点割り当ての移動だけに限定することにある。これは、境界上にない頂点に対応する位置に生じる変更ベクトル中の１を除去することによって実施される。回路２００は、ＡＮＤゲート２１７及び２１８のようなＡＮＤゲートを利用して、内部頂点に対応する変更ベクトルのビットにマスキングを施すことによって、これを実施する。変更ベクトルの各ビット毎に、こうしたＡＮＤゲートが１つずつ設けられている。
【００３６】
以上の説明は、パーティショニング問題が２のオーダである、すなわち、２つの区画しか存在しないと仮定したものである。３つ以上の区画が存在する場合、図６に示すＸＯＲゲートは、その入力が等しくない場合に、その出力が真になるコンパレータに置き換えなければならない。新しい変更ベクトルは、従って、変更されることになる各頂点位置毎に１を有することになる。しかし、変更の絶対値は、回路２００では得られない。新しいＰＳＲ値は、いくつかある方法の任意の１つによって得ることが可能である。例えば、変更ベクトル・ビットは、ｋを法として各セルのビットに加算することが可能である。代替案として、変更ベクトルの１に対応するＰＳＲセルの内容を０と（ｋ−１）の間の乱数に置き換えることも可能である。
【００３７】
上述のシステムの性能は、ハイパーグラフをグラフの他の部分とは別様に扱うことによってさらに向上させることが可能である。ハイパーグラフは、頂点とハイパーエッジの集合である。ハイパーエッジは、２つ以上の頂点の部分集合である。例えば、他の８つのゲートを駆動するゲートを備えた論理回路は、ハイパーグラフである。ハイパーグラフは、通常のグラフとして取り扱う場合、上述のアルゴリズムにおいてカット・サイズ・コストを膨張させることになりがちである。これが生じるのは、１つのパーティショニング・オプションが、２つの区画間において問題となる８つのゲートを均等に分割することであって、電気的に１つしか必要とされない場合には、８つの区画クロッシングを生じることになる可能性があるからである。
【００３８】
本発明では、解を制限して、ハイパーグラフが区画間で分割された場合に課せられるペナルティを最小限に抑えることによって、この問題を回避する。ハイパーグラフの２分割という単純な事例を考察することにする。カット・サイズは当然１または０になる。全ての頂点が同じ区画にある場合、カット・サイズは０になる。頂点が２つの異なる区画内にある場合、所与の区画におけるハイパーエッジによって接続された頂点は、その区画の共通導体によって接続することが可能である。同様に、ハイパーエッジによって接続された他の区画の頂点は、互いに接続することが可能である。ハイパーエッジの２つの部分を接続するため、２つの区画間に単一導体が必要になる。従って、最大カット・サイズは当然１になる。
【００３９】
本発明の望ましい実施例では、特殊ハイパーグラフカット・サイズ回路を利用して、ハイパーグラフのカット・サイズを計算することが可能である。次に、本発明によるハイパーグラフ・コスト回路２５０の略図である図７を参照することにする。頂点Ｖ1、Ｖ2、．．．ＶMがハイパーエッジによって接続される事例について考察することにする。２つのＡＮＤゲート２５１及び２５２がＰＳＲ１１に接続され、各頂点は、各ＡＮＤゲートの対応する入力に接続される。問題となるセルが、全て、同じ区画に割り当てられる場合、ＡＮＤゲートの一方は、その入力の全てが１または０にセットされ、もう一方のＡＮＤゲートは、その入力の全てがもう一方の状態にセットされる。ＯＲ回路２５３及びインバータ２５４によって、この状態は０に変換され、カット・サイズの和を求めるために利用される桁上げ保存型加算器２５５に入力される。一方、頂点の１つが異なる区画にある場合、両方のＡＮＤゲートとも、０を発生し、これがＯＲ２５３及びインバータ２５４によって１に変換されることになる。
【００４０】
上述の実施例では、区画は２分割されるものと仮定した。一般に、区画数がｋの場合、最大カット・サイズは、当然（ｋ−１）になる。一般的な区画事例に関するカット・サイズの発生回路が、図８に３００で示されている。この場合、１〜ｋのデコーダは、ハイパーエッジによって接続される頂点に対応するＰＳＲ１１の各セルに接続される。典型的なデコーダが３０１〜３０３で示されている。Ｍ個のデコーダの出力は、Ｍ個のｋ入力ＯＲゲートに対する入力として利用され、該ＯＲゲートの出力は、桁上げ保存型加算器３１０によって和が求められる。典型的なＯＲゲートが、３０４〜３０６で示されている。桁上げ保存型加算器３１０の出力は、デクリメンタ３１１を利用して１ずつデクリメントされ、これによって、カット・サイズが発生する。
【００４１】
当該技術の熟練者には、以上の説明及び添付の図面からさまざまな修正案が明らかになるであろう。
【００４２】
以上、本発明の実施例について詳述したが、以下、本発明の各実施態様の例を示す。
【００４３】
[実施態様１]  その最適により、エッジによって接続される複数の頂点を有するグラフのパーティショニングが表される関数の計算を行う、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）を操作するための方法であって、複数のセルを有し、前記各セルが前記頂点の１つに対応し、前記頂点の現在割り当てられている区画を表した番号を記憶している、区画状態レジスタ（ＰＳＲ）と、異なる区画の頂点を接続するエッジの和を計算するための回路と、区画が備えているサイズの相違度を表した値を計算するための回路と、を設けるように、前記ＦＰＧＡを構成することを特徴とする操作方法。
【００４４】
[実施態様２]  さらに、前記ＰＳＲの各セルに対応する１つのビットを有する状態変更ベクトルを発生するための回路を設けるように、前記ＦＰＧＡを構成するステップを有することと、値１を有する前記ビットの数が、前記ビット合計の半分より少ないことと、値１を有する前記ビットが前記ベクトル内にランダムに配置されることを特徴とする、実施態様１に記載の操作方法。
【００４５】
[実施態様３]  前記状態変更ベクトル回路が、２つの区画の境界上にない頂点に対応する、前記状態変更ベクトルのビットにマスキングを施すための手段を備えていることを特徴とする、実施態様１に記載の操作方法。
【００４６】
[実施態様４]  前記状態発生回路を設けるように前記ＦＰＧＡを構成する前記ステップが、シフトすべき２進値を受信するための入力を備えた第１のシフト・レジスタであって、各セルが該セルに記憶された値を示す出力を有する複数のセルと、出力が第１のシーケンスをなす乱数を有する第１の乱数発生回路と、出力が前記第１のシフト・レジスタの入力に接続されており、前記第１のシーケンスをなす乱数における各数と第１の値を比較する第１のコンパレータとを有する第１のシフト・レジスタと、シフトすべき２進値を受信するための入力を備えた第２のシフト・レジスタであって、各セルが該セルに記憶された値を示す出力を有する複数のセルと、出力が第２のシーケンスをなす乱数を有する第２の乱数発生回路と、出力が前記第２のシフト・レジスタの入力に接続されており、前記第２のシーケンスをなす乱数における各数と第２の値を比較する第２のコンパレータとを有する第２のシフト・レジスタと、前記第１と第２のシフト・レジスタにおける対応する前記セルの前記出力に接続されて、前記変更ベクトルを発生するための手段と、を設けるように、前記ＦＰＧＡを構成するステップを備えていることを特徴とする実施態様１に記載の操作方法。
【００４７】
[実施態様５]  前記乱数発生回路の１つが、複数の直列に接続されたセルを有することと、前記直列セルが、最初のセル、最後のセル、及び、１つ以上の中間セルを有することと、前記各セルが、２進状態を記憶し、状態値を出力するための回路と出力端子とを有することと、前記セルの次の状態が、該セルの現在の状態と第１と第２の入力の関数であることと、前記中間セルの接続が、前記各中間セルの前記第１と第２の入力が、それぞれ、前記直列をなす前記中間セルの両側における前記セルの前記状態出力に接続されるように行われることと、前記最初のセルの前記入力の１つが、出力が２を法とする前記セル状態の全ての和である回路に接続されることを特徴とする、実施態様４に記載の操作方法。
【００４８】
[実施態様６]  前記グラフにおける少なくとも３つの頂点が、ハイパーエッジに接続されることと、さらに、前記ハイパーエッジに接続された前記頂点に対応する、前記ＰＳＲの前記セルに接続された回路を設けるように、前記ＦＰＧＡを構成するステップを有することと、前記回路の出力が０〜ｋ−１であることと、ここで、ｋは前記グラフを分割する区画数であり、前記出力０は、前記ハイパーエッジに接続された頂点より１つ少ない数に相当する、前記ＰＳＲの前記セルにおける異なる値の数に等しいことを特徴とする、実施態様１に記載の操作方法。
【００４９】
[実施態様７]  複数の直列に接続されたセルを有し、前記直列セルが、最初のセル、最後のセル、及び、１つ以上の中間セルを有し、前記各セルが、２進状態を記憶し、状態値を出力するための回路と出力端子とを有し、前記セルの次の状態が該セルの現在の状態と第１と第２の入力の関数であり、前記中間セルの接続が、前記各中間セルの前記第１と第２の入力が、それぞれ、前記直列をなす前記中間セルの両側における前記セルの前記状態出力に接続されるように行われ、前記最初のセルの前記入力の１つが、出力が２を法とする前記セル状態の全ての和である回路に接続されるようになっている、シーケンスをなす乱数を発生するための回路。
【００５０】
[実施態様８]  １の密度が制御値によって決まり、１の配置がランダムな、２進ベクトルを発生するための回路であって、シフトすべき２進値を受信するための入力を備えた第１のシフト・レジスタであって、各セルが該セルに記憶された値を示す出力を有する複数のセルと、出力が第１のシーケンスをなす乱数を有する第１の乱数発生回路と、出力が前記第１のシフト・レジスタの入力に接続されており、前記第１のシーケンスをなす乱数における各数と第１の値を比較する第１のコンパレータとを有する第１のシフト・レジスタと、シフトすべき２進値を受信するための入力を備えた第２のシフト・レジスタであって、各セルが該セルに記憶された値を示す出力を有する複数のセルと、出力が第２のシーケンスをなす乱数を有する第２の乱数発生回路と、出力が前記第２のシフト・レジスタの入力に接続されており、前記第２のシーケンスをなす乱数における各数と第２の値を比較する第２のコンパレータとを有する第２のシフト・レジスタと、前記第１と第２のシフト・レジスタにおける対応する前記セルの前記出力に接続されて、前記２進ベクトルのビットを発生するための手段と、を備えて成る２進ベクトル発生回路。
【００５１】
[実施態様９]  前記２進ベクトルのビットを発生するための手段が、それぞれ、一方の入力が前記第１のシフト・レジスタのビットに接続され、もう一方の入力が前記第２のシフト・レジスタのビットに接続される、複数の２ビットＡＮＤゲートを備えて成ることを特徴とする、実施態様８に記載の回路。
【００５２】
以上説明したように、本発明を用いることにより、グラフ・パーティショニング問題が解決される。
【図面の簡単な説明】
【００５３】
【図１】本発明によるカット・サイズ計算回路の略図である。
【図２】本発明による不均衡コスト計算回路の略図である。
【図３】本発明による区画変更ベクトル発生回路の略図である。
【図４】本発明による乱数発生器の実施例に用いられる基本セルの略図である。
【図５】本発明による乱数発生器の略図である。
【図６】別様であれば区画の境界線上になかった試算の解をもたらすことになる、区画変更ベクトルのビットにマスキングを施すための回路の略図である。
【図７】頂点集合が２分割されることになるパーティショニング問題におけるハイパーグラフのカット・サイズを計算するための本発明による回路の略図である。
【図８】頂点集合がｋの区画に分割されることになるパーティショニング問題におけるハイパーグラフのカット・サイズを計算するための本発明による回路の略図である。
【符号の説明】
【００５４】
１０：コスト関数回路
１１：ＰＳＲ
１２：第１のコンパレータ
１３：第２のコンパレータ
１４：桁上げ保存型加算器
２１：デコーダ
２２：デコーダ
２３：デコーダ
３１：加算器
３２：加算器
３３：加算器
４１：差分回路
４２：差分回路
４３：差分回路
５１：絶対値回路
５２：絶対値回路
５３：絶対値回路
７０：区画変更ベクトル発生器
７３：密度制御レジスタ
７４：デジタル・コンパレータ
７５：デジタル・コンパレータ
８１：シフト・レジスタ
８２：シフト・レジスタ
１００：基本セル
１０１：フリップ・フロップ
１０２：フリップ・フロップ
１０３：ＸＯＲゲート
２００：マスキング回路
２１２：ＸＯＲゲート
２１３：ＸＯＲゲート
２１５：ＯＲゲート
２１６：ＯＲゲート
２１７：ＡＮＤゲート
２１８：ＡＮＤゲート
２５０：ハイパーグラフ・コスト回路
２５１：ＡＮＤゲート
２５２：ＡＮＤゲート
２５３：ＯＲ回路
２５４：インバータ
２５５：桁上げ保存型加算器
３００：カット・サイズ発生回路
３０１：デコーダ
３０２：デコーダ
３０３：デコーダ
３０４：ＯＲゲート
３０５：ＯＲゲート
３０６：ＯＲゲート
３１０：桁上げ保存型加算器
３１１：デクリメータ
【図１】
2007035065.tif 000005
【図２】
2007035065.tif 000006
【図３】
2007035065.tif 000007
【図４】
2007035065.tif 000008
【図５】
2007035065.tif 000009
【図６】
2007035065.tif 000010
【図７】
2007035065.tif 000011
【図８】
2007035065.tif 000012