並列ルーティングプロセッサの試作研究

概要

論文の詳細を見る
本論文では,Leeの迷路法を並列化,ハードウェア化した並列ルーティングプロセッサの構成法,試作結果,及び対話型設計システムヘの応用について論じる.Leeの迷路法は,グリッドに対応するN×Nのプロセッサアレイを用意することにより,径路探索時間をO(N^2)からO(N)に短縮することが可能である.しかし,必要とするハードウェア量はO(N^2)で増加し,実用規模のシステムでは膨大なものとなる.これに対して,本論文で提案するアーキテクチャは,ウェーブフロント上のセルのみにプロセッサが割り当てられる方式であるため,O(N)台のプロセッサにより,処理時間をO(M)に短縮することが可能となっている.また,実際に128×128のグリッドを扱える,64台のプロセッサによる構成の試作を行った.迷路法には,数々の変形があり,これらのアルゴリズムは,配線領域が混雑していない段階では,ソフトウェアによる実行でも平均的には,O(M)の時間で径路を発見できることが知られているが,処理が進み配線領域が混雑している段階では,O(N^2)の時間を必要とする.これに対して,並列ルーティングプロセッサは,配線領域の混雑度に関係なくO(M)の時間で径路を発見することができる.この特徴は,配線工程の最終段階において,対話型システムを使用し,障害となっている既配線の引きはがし,及び再配線を行う際には,さらに有効なものとなる.
一般社団法人情報処理学会の論文
1986-06-15

並列ルーティングプロセッサの試作研究

スポンサーリンク

概要

著者

関連論文

スポンサーリンク