方形パッキング法の一算法

長尾 明  澤 卓  重弘 裕二  白川 功  神戸 尚志  

誌名
電子情報通信学会論文誌 A   Vol.J81-A   No.10   pp.1362-1371
発行日: 1998/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: VLSI設計技術とCAD
キーワード: 
方形パッキング,  フロアプラン,  配置,  LSI,  CAD,  

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




あらまし: 
方形パッキング問題とは,幅と高さが任意であるいくつかの方形が与えられたとき,最小面積の方形内にこれらを互いに重複なく配置する問題であり,面積が製造コストに大きく影響するVLSIの配置設計に応用することができる.この問題はNP困難な最適化問題であることから,SA法などのヒューリスティック算法を用いた解法が試みられてきたが,その際配置解の表現法が探索の効率化の鍵となる.近年,Sequence-Pairと呼ばれる配置解の画期的な表現法が提案され,高品質な解を高速に探索する途が拓かれた.本論文では,この表現法に基づいて,単純な幾何学的な手続きによって方形パッキングを求める高速な算法を提案し,本算法が方形数の多いデータに対しても高速に良質な配置解を探索することを,MCNCベンチマークデータami49などの評価を通して示す.