シーケンスペア
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/10/04 08:06 UTC 版)
シーケンスペア(Sequence-pair)は、矩形配置の表現方法のこと。矩形同士の相対位置関係を矩形名の順列の対により表すことができる。集積回路設計の一工程である配置計画(フロアプラン)での利用を目的として開発されたが、発見的探索法(メタヒューリスティックアルゴリズム)である焼きなまし法と組合わせて用いると、離散数学の組合せ論でNP困難な問題である矩形パッキング問題に有効なことが知られている。
- ^ H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair," IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 15(12):1518–1524, December 1996.
- ^ Ralph H.J.M. Otten, "Automatic Floorplan Design," IEEE Design Automation Conference, 261-267, 1982.
- ^ D.F. Wong and C.L. Liu, "A New Algorithm for Floorplan Design," IEEE Design Automation Conference: 101-107, 1986.
- ^ 中武繁寿, 村田洋, 藤吉邦洋, 梶谷洋司, "モジュール配置問題を解く限定スライス構造の提案," 情報処理学会 設計自動化研究会 研究報告, 設計自動化(72-4):19-24, 1994.
- ^ H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectangle-packing-based module placement," IEEE International Conference on Computer-Aided Design, 472-479, 1995.
- ^ http://www.env.kitakyu-u.ac.jp/faculty/kajitani/index.htm
- ^ H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair," IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 15(12):1518–1524, December 1996.
- ^ http://www.gemdt.com
- ^ X. Tang and D.F. Wong, "FAST-SP: a fast algorithm for block placement based on sequencepair," IEEE ASP-DAC 2001: 521-526, 2001.
- ^ C. Kodama and K. Fujiyoshi, "Selected sequence-pair: An efficient decodable packing representation in linear time using sequence-pair," IEEE ASP-DAC 2003: 331-337, 2003.
- ^ H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "Rectangle-packing-based module placement," IEEE International Conference on Computer-Aided Design, 472-479, 1995.
- ^ 児玉親亮, 藤吉邦洋, "空部屋数が極小な方形分割に対応するSequence-Pair," 電子情報通信学会和文論文誌, J90-D(1):1-15, Jan, 2007
- ^ H. Xiang, X. Tang and D.F. Wong, "Bus-Driven Floorplanning," IEEE ICCAD 2003: 66-73, 2003.
- ^ S. Koda, C. Kodama and K. Fujiyoshi, "Linear Programming-Based Cell Placement with Symmetry Constraints for Analog IC Layout," IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 26(4): 659-668, Apr, 2007.
- ^ 浅野寛治, 加藤直樹, 吉村茂久, "Sequence-Pairに基づく室・通路・出入口配置最適化手法 : 数理計画法と遺伝的アルゴリズムの融合による優良解探索," 日本建築学会計画系論文集, (572): 209-216, Oct, 2003.
- ^ K. Fujiyoshi and H. Murata "Arbitrary convex and concave rectilinear block packing usingsequence-pair," IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 19(2):224–233, Feb, 2000.
- ^ 児玉親亮, 高橋渉吾, 藤吉邦洋, "Sequence-pair表現を利用した服飾用自動マーキングシステム," 情報処理学会 数理モデル化と問題解決研究会 研究報告, 2000-MPS31(4): 9-12, 2000.
- 1 シーケンスペアとは
- 2 シーケンスペアの概要
- 3 関連項目
- シーケンスペアのページへのリンク