依頼元のライン・プロセスは回答が全て集まった時点で、その中から最も目標
点に近い期待位置を回答してきたライン・プロセスを選び、自分との交点とSと
の間を新たな既配線領域とする。
それ以降の探索は、先の最も目標点に近い期待位置を回答してきたライン・プ
ロセスに制御が移され(routeメッセージ)、同様に進められる。目標点＝期待位置
となるライン・プロセスまで制御が移れば１ネットの配線が終了する。

大規模データに適用するためのプロセス構造

並列オブジェクトモデルに基づき配線プログラムを設計すると、多数のプロセ
ッサ間通信路がプロセッサの間に張り巡らされ、それを管理するためのメモリを大
量消費する。そこで我々は、各プロセッサ間のメッセージを管理するディストリ
ビュータプロセスを各プロセッサにおき、プロセッサをまたがるプロセス問通信
路の数を減らし、大規模問題が扱える配線プログラムを開発した。

性能評価

PIM/m上での配線プログラムの性能評価結果を示す。



P.50 Figure 1

性能と使用プロセッサ数



256プロセッサを用いた場合、最高92倍の台数効果を得た。また、このときの
配線率は、99%から100%と良好な結果を得た。

デモ概要

小規模LSIの実データ(格子規模262×106、ネット数136)と大規模LSIの実
データ(格子規模1048×636、ネット数3264)に対し、PIM/m256プロセッサ
を用いて、配線プログラムを動作させる。大規模データを高速に配線することに
よりPIM上での配線プログラムの有効性を示す。


					- 50 -