An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations

• Item type: SIG Technical Reports(1)
• 公開日: 2011-11-21
• タイトル: An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
• タイトル / 言語: en
• タイトル: An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 実装技術と低消費電力化
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Communication and Integrated Systems, Tokyo Institute of Technology
• 著者所属: Division of Electrical, Electronic and Information Engineering, Osaka University
• 著者所属: Department of Communication and Integrated Systems, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Communication and Integrated Systems, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Division of Electrical, Electronic and Information Engineering, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Communication and Integrated Systems, Tokyo Institute of Technology
• 著者名: Yiqiang, Sheng; Atsushi, Takahashi; Shuichi, Ueno
• 著者名(英): Yiqiang, Sheng; Atsushi, Takahashi; Shuichi, Ueno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The 3D packing for VLSI physical design is facing big challenges to get better solution quality with less computational time. In this paper, we propose 2-stage simulated annealing with crossover operator (2-SA-X) to solve a general rectangular 3D-packing problem by using sequence-k-tuple representation, where k is defined by 3 and 5. The basic ideas of this research are to reuse the information of past solution by integrating the crossover operator from genetic algorithm and to improve the global search ability by using two different stages. The first stage mainly focuses on the global search by moving methods with big changes, including the crossover, while the second stage focuses on local search by the moving methods with small changes. Based on the experiment using ami98_3D benchmark, the computational performance of 3D packing is considerably improved. The paper shows how much the 3D-packing ratio of volume and the computational time can be improved by using the proposed 2-SA-X algorithm, comparing with normal 2-stage simulated annealing (2-SA) without the crossover operator.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The 3D packing for VLSI physical design is facing big challenges to get better solution quality with less computational time. In this paper, we propose 2-stage simulated annealing with crossover operator (2-SA-X) to solve a general rectangular 3D-packing problem by using sequence-k-tuple representation, where k is defined by 3 and 5. The basic ideas of this research are to reuse the information of past solution by integrating the crossover operator from genetic algorithm and to improve the global search ability by using two different stages. The first stage mainly focuses on the global search by moving methods with big changes, including the crossover, while the second stage focuses on local search by the moving methods with small changes. Based on the experiment using ami98_3D benchmark, the computational performance of 3D packing is considerably improved. The paper shows how much the 3D-packing ratio of volume and the computational time can be improved by using the proposed 2-SA-X algorithm, comparing with normal 2-stage simulated annealing (2-SA) without the crossover operator.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 研究報告システムLSI設計技術（SLDM）; 巻 2011-SLDM-153, 号 37, p. 1-6, 発行日 2011-11-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会