背景

LSI配線とは、LSIチップ上に焼き付ける回路の端子位置が決定された後、端
子間の配線経路を決める作業である。大規模なLSIほど、その配線設計には多大
の計算時間を要し、高速で、配線制約に柔軟に対処できる配線プログラムが望ま
れている。
LSI配線では・並列推論マシンPIMを汎用の分散メモリ型MIMD計算機とし
て位置付け、その方式に適した並列オブジェクトモデルに基づく配線プログラム
を開発し、その有効性を検証した。

システム仕様

本配線プログラムでは、2層配線を対象とする。すなわち、端子間の配線を行
うのにチップ上に直交格子を仮定し、縦方向の配線、横方向の配線とで層を使い
分けて配線経路を決定する。
また、第一層と第二層とを接続するときには、スルーホールを用いるため、ス
ルーホールに関する制約を守りながら、配線を行う。



P.48 Figure 1

２層配線の例 



並列オブジェクトモデルに基づくプログラミング

並列オブジェクトモデルによる問題の定式化は、問題から並列性を引き出すの
に有効な方法の一つである。本配線プログラムでは、配線格子上にある全ての既
配線、未配線をオブジェクト＝プロセスに対応させ、それらが、メッセージを交
換しながら配線経路を決定するように設計した。
そして、それらのプロセスの中でメッセージを頻繁に交換するもの同士をグルー
プ化し、そのグループを単位としてプロセッサに割り付けることにより、通信の
局所性とプロセッサ間の並列実行を実現した。


					- 48 -