でき、(2)エージェント数を15まで増やした場合最高でリニアの高速化が達成されている。
デモの概要
図1と図2に示したような回路を例としてco-LODEXの動作を説明する。エージェントの協調動作を説明するために、実際の実行結果のログ情報を元にした特別なインターフェースを用意した。協調アルゴリズムの詳細については付録を参照されたい。
最後に、実機上でco-LODEXによる大規模回路の設計を実演する。
参考文献
[Minoda1992]Y.Minoda,et a1."A Cooperative Logic Design
Expert System on a Mu1tiprocessor,"Proc.of FGCS'92,pp.1181-1189(1992).
並列LSI配線プログラム
概要
LSIは、年々、高密度・高集積化の傾向にあり、高速な配線プログラムが望まれている。ICOTでは、並列処理に適したプロセス指向に基づくLSI配線の新方式を開発した。そして、それを並列推論マシンPIM上に実現し、処理性能を検証した。
特徴
並列オブジェクトモデルに基づくプログラミング
高い並列性を実現するため、並列オブジェクトモデルに基づき、分散配線アルゴリズムを設計。
配線格子における既配線、未配線の全線分をオブジェクト(ラインプロセス)に対応させ、それらがメッセージを交換しながら配線経路を決定。
マスタラインプロセスが、ラインプロセス間のメッセージ通信を制御。
大規模データヘの適用
ディストリビュータプロセスを各プロセッサに割り当て、プロセッサ間の通信量を軽減させ、大規模データに対応。大規模データ(格子規模2746×3643、ネット数556)に対し配線率100%達成。
背景
LSI配線とは、LSIチップ上に焼き付ける回路の端子位置が決定された後、端子間の配線経路を決める作業である。大規模なLSIほど、その配線設計には多大の計算時間を要し、高速で、配線制約に柔軟に対処できる配線プログラムが望まれている。
LSI配線では・並列推論マシンPIMを汎用の分散メモリ型MIMD計算機として位置付け、その方式に適した並列オブジェクトモデルに基づく配線プログラムを開発し、その有効性を検証した。
システム仕様
本配線プログラムでは、2層配線を対象とする。すなわち、端子間の配線を行うのにチップ上に直交格子を仮定し、縦方向の配線、横方向の配線とで層を使い分けて配線経路を決定する。
また、第一層と第二層とを接続するときには、スルーホールを用いるため、スルーホールに関する制約を守りながら、配線を行う。
並列オブジェクトモデルに基づくプログラミング
並列オブジェクトモデルによる問題の定式化は、問題から並列性を引き出すのに有効な方法の一つである。本配線プログラムでは、配線格子上にある全ての既配線、未配線をオブジェクト＝プロセスに対応させ、それらが、メッセージを交換しながら配線経路を決定するように設計した。
そして、それらのプロセスの中でメッセージを頻繁に交換するもの同士をグループ化し、そのグループを単位としてプロセッサに割り付けることにより、通信の局所性とプロセッサ間の並列実行を実現した。
並列配線アルゴリズム
本配線プログラムは、線分をプロセスに対応させているので、配線経路探索の基本アルゴリズムとして、予測線分探索法を採用した。この手法は、線分探索に”先読み”を加えた逐次配線手法で、二重探索を避けるフラグとバックトラックなどを導入し、経路が存在すれば必ず発見できることを保証している。
本プログラムでは、2種類の並列性を実現している。一つは、複数ネットの同時配線、もう一つは、“先読み"処理の並列化である。
１ネット探索での”先読み”処理の並列化の様子を以下に示す。Sを始点、Tを目標点とする。Sから垂直方向に探索を始める場合、Sを含む未配線領域のライン・プロセスは、自分と直交する同じく未配線領域のライン・プロセスに対して、各領域中で目標点に最も近い位置、すなわち期待位置の計算を依頼する(estimateメッセージ）。依頼元のライン・プロセスは回答が全て集まった時点で、その中から最も目標点に近い期待位置を回答してきたライン・プロセスを選び、自分との交点とSとの問を新たな既配線領域とする。
それ以降の探索は、先の最も目標点に近い期待位置を回答してきたライン・プロセスに制御が移され(routeメッセージ)、同様に進められる。
大規模データに適用するためのプロセス構造
並列オブジェクトモデルに基づき配線プログラムを設計すると、多数のプロセッサ間通信路がプロセッサの間に張り巡らされ、それを管理するためのメモリを大量消費する。そこで我々は、各プロセッサ間のメッセージを管理するディストリビュータプロセスを各プロセッサにおき、プロセッサをまたがるプロセス問通信路の数を減らし、大規模問題が扱える配線プログラムを開発した。
性能評価
PIM/m上での配線プログラムの性能評価結果を示す。
256プロセッサを用いた場合、最高92倍の台数効果を得た。また、このときの配線率は、99%から100%と良好な結果を得た。
デモ概要
小規模LSIの実データ(格子規模262×106、ネット数136)と大規模LSIの実データ(格子規模1048×636、ネット数3264)に対し、PIM/m256プロセッサを用いて、配線プログラムを動作させる。大規模データを高速に配線することによりPIM上での配線プログラムの有効性を示す。