長方形シストリックアレーの再配線問題

鈴木 善尚  平田 富夫  今井 正治  山下 雅史  茨木 俊秀  

誌名
電子情報通信学会論文誌 D   Vol.J70-D   No.3   pp.534-542
発行日: 1987/03/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 計算機システム・構成要素
キーワード: 


本文: PDF(882.8KB)>>
論文を購入




あらまし: 
一般に,集積回路が大規模になると,そこに不良素子の含まれる比率は高くなり,製造の歩留まりが低下する.これを解決するために,再配線の工程を加えることによって回路に耐故障性(フォールトトレランス)を持たせる方法がある.再配線を行うには,あらかじめ,そのための回路や配線を集積回路の中に組み込んでおかなければならないが,これらは,その集積回路本来の目的からはオーバーヘッドとなる.本論文では,シストリックアレーの代表的な形である長方形アレーを対象にして,オーバーヘッドの大小を考慮した3種類の再配線の制約を考え,各制約のもとでの再配線問題がNP完全であることを示し,更に,それぞれに対し近似再配線アルゴリズムを提案する.