回路分割

本システムでは、縦割り指向戦略により、回路を静的に分割する。この戦略で
は,回路入力端子から順にゲート接続関係をたどり,縦方向につながったゲートを
グループにまとめることによって、回路を幾つかのクラスタに分割する。全ゲート
のグループ化終了後、クラスタの大きさの均一化処理を行い、最後にクラスタをラ
ンダムに各PEに割り当てる。
本戦略は、回路分割を行う時の目標である、・負荷の均一化、・プロセッサ間
通信低減、・高い並列性抽出の3点を満たす。




図 4: 縦割り指向戦略

性能評価

ISCAS'89のベンチマークのうち、五つの順序回路について、PIM/mを用い
てシミュレーションを行った。各回路規模(ゲート数)を表1に、また、性能とプ
ロセッサ台数の関係を図5に示す。



回路
s38584
s38417
s35932
s15850
s13207
ゲート数
27,965
31,995
26,433
13,354
11,965

表1: 回路規模 



256プロセッサを用いた場合、最高537Kイベント/秒の性能を得た。また、
この時の台数効果は166倍であった。


					- 55 -