Japan Advanced Institute of Science and Technology
JAIST Repository
https://dspace.jaist.ac.jp/
Title 周期的繰り返し矩形配置の解表現と配置最適化
Author(s) 小川, 智之
Citation
Issue Date 2005‑03
Type Thesis or Dissertation Text version author
URL http://hdl.handle.net/10119/1929 Rights
Description Supervisor:金子 峰雄, 情報科学研究科, 修士
周期的繰り返し矩形配置の解表現と配置最適化
小川 智之(310025)
北陸先端科学技術大学院大学 情報科学研究科 2005年2月10日
キーワード: フロアプラン，シーケンスペア，コード表現，非スライス配置.
矩形配置問題とは，二次元平面上に複数の矩形を互いに重なることなく配置する問題で あり，VLSIレイアウトを始めとして，様々な応用を持つ最適化問題である．矩形の配置 領域の面積最小化などの最適配置問題はNP困難に属することが知られており，近似解法 やSimulated Annealing法などの確率的最適化法が考案されている．
本研究では，繰り返し配置と呼ばれる特殊な配置問題を取り扱う．これは基本矩形集合 が周期的に複数回（有限回，あるいは無限回）繰り返し並ぶ配置である．このような矩形 の周期的繰り返し配置は，同一構造のプロセッサが複数個並ぶオンチッププロセッサアレ イ，基本論理セルとスイッチボックスが規則正しく並ぶFPGA，あるいはメモリのような 同一の回路構造が繰り返し配置されるVLSIレイアウトに現れる問題である．また，複数 セットの部品切り出しや，矩形集合の円筒側面上への配置（平面化すると無限繰り返しと なる），ループ状の計算処理におけるループパイプラインスケジュール（ガントチャート 表現）など，回路レイアウトにとどまらない応用も期待される．
本研究では，繰り返し配置に対する研究の第一段階として，水平方向への一次元的な繰 り返し配置について検討し，繰り返し配置の組み合わせ問題としての解表現，配置の最適 化手法の開発を行った．
繰り返しのない通常の矩形配置問題の解表現手法としてシーケンスペアが提案されてい る．シーケンスペアは矩形名からなる二つの順列(Γ+,Γ−)によって構成され，各順列の 並びによってすべての二矩形間の相対位置関係を矛盾無く規定するものである．与えられ た矩形配置からシーケンスペアを抽出（エンコード）する操作としてグリッディングと呼 ばれるアルゴリズムがあるが，周期的繰り返し配置に対してもそれを適用することが可能 であり，抽出される二つの順列Γ+とΓ−は，ともに矩形名が周期的に繰り返す順列とな る．一方，Γ+,Γ−から逆に繰り返し配置を導く（デコード）することを考えた場合，繰り 返し配置では一周期内の相対位置関係だけでなく異なる周期にある矩形同士の相対位置 関係も規定する必要があるため，二矩形間の相対位置関係を一意に決定することができな いという問題に直面する．
Copyright c2005 by Tomoyuki Ogawa
1
このデコードにおける問題を解決するため，二つの順列に加え第三の順列Γsを導入す ることで，周期的繰り返し配置を解表現する新たなコーディングシステムを開発した．以 下，この三つの順列による解表現手法をシーケンスペアにならい，シーケンストリプルと 呼ぶ．シーケンストリプルでは，周期的に繰り返されるΓ−の一周期内におけるΓ+の並 びをΓsによって規定する．シーケンスペアと比べ，順列を一つ多く使うが，一周期内の 矩形間の相対位置関係だけでなく，異なる周期間にある矩形同士の相対位置関係をも規定 することが可能となった．なお，矩形数をnとするとき，本研究で開発したシーケンスト リプルのデコードの計算量はO(n3)であり，解空間の大きさはO((n!)3)である．
シーケンストリプルにより定義される解空間をSimulated Annealing法により探索し，
準最適な矩形配置を求めるプログラムをC言語を用いて実装し，矩形配置生成の実験を 行った．入力は無作為に生成した各矩形の幅と高さとし， 繰り返し周期の幅L ×配置領 域の高さH が最小となることを最適化の目標とした．様々な入力に対して実験を行った 結果，最適化される配置には縦長になる傾向があることがわかった．この傾向は，ランダ ムに生成されたシーケンストリプルにおいて，二つの矩形が上下関係になる確率と左右関 係になる確率に偏りがあることからも裏付けられ，良好な解の探索のためには，こうした 偏りを打ち消すような探索上の工夫が必要と考えられる．
今後の課題として，良好な解を得るための解空間探索手法，デコードアルゴリズムの高 速化，計算量と解空間の大きさについてより優れた解表現手法の開発が挙げられる．
2
