3次元交叉・突然変異を導入した3次元FPGA初期配置のための遺伝的アルゴリズム

• Item type: Journal(1)
• 公開日: 2014-02-15
• タイトル: 3次元交叉・突然変異を導入した3次元FPGA初期配置のための遺伝的アルゴリズム
• タイトル / 言語: en
• タイトル: Genetic Algorithm for 3-D FPGA Initial Placement with 3-D Crossover and Mutation
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] 遺伝的アルゴリズム，3次元FPGA，初期配置
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 広島工業大学工学部
• 著者所属: 広島工業大学大学院工学系研究科／現在，西日本旅客鉄道株式会社
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima Institute of Technology / Presently with West Japan Railway Company
• 著者名: 大村, 道郎; 太田, 雅也
• 著者名(英): Michiroh, Ohmura; Masaya, Ohta
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年の大規模集積回路における製造技術の進歩にともない，TSVを用いた3次元VLSI設計が注目を集めている．TSVを使う方法では，1つのLSIに1,000本以上のTSVを使い配線することができるため，3次元に適したアルゴリズムから開発する必要がある．VLSIのレイアウト設計は，配置設計と配線設計に分かれ，その最初の段階に初期配置設計がある．本論文では3次元VLSIの中でも特に3次元FPGA初期配置について議論する．ところで，一般的に様々な最適化問題に対し，効率良く準最適解を求めるアルゴリズムの1つに，遺伝的アルゴリズムがあり，マクロセルを含む3次元FPGAの初期配置に対してもそのまま拡張できる．しかし1次元の遺伝子列（個体）で3次元の配置を表し，1次元配列を対象とした通常の遺伝的操作を行うと，配置構造が簡単に壊れて配線長の総和が小さい配置を得られない可能性がある．本論文では，マクロセルを考慮した3次元FPGA初期配置問題に対し，遺伝子に3次元構造を持たせ，3次元交叉，3次元突然変異を導入した，3次元FPGA初期配置のための遺伝的アルゴリズムを提案する．実験の結果，提案手法では立方体の配置領域に対し，順序交叉，交換突然変異を単純に適用した場合に比べ，平均24.4%配線長の総和が小さい配置を高速に得ることができた．また配置領域を直方体とした場合でも，従来手法に対し19.3%配線長の総和が小さい配置を高速に得ることができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: As manufacturing technology has advanced in recent years, 3-D VLSI with TSV has been the focus of attention. Because more than 1,000 TSV can be used to design a 3-D VLSI, we need 3-D layout algorithms. VLSI layout design consists of placement and routing, and initial placement is the first stage of this placement. In this paper, initial placement of 3-D FPGA, which is a kind of 3-D VLSI, is discussed. In general, a genetic algorithm is one of the most effective methods for a variety of optimization problem, and it can be applied to the 3-D FPGA initial placement problem with macro cell. Usually, the chromosome is represented by a one dimensional array, and if a 3-D placement region is represented by this chromosome, relative positions of modules are easily broken by the crossover. In this paper, we propose a genetic algorithm with 3-D crossover and mutation, in which the chromosome has 3-dimensional structure. The experimental results show that our approach achieves 24.4% shorter wire length for cube placement regions, and 19.3% shorter wire length for rectangular solid placement regions. In this paper, our proposed method and the experimental results are shown.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 55, 号 2, p. 1059-1068, 発行日 2014-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764