2026-03-05T07:50:11Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00098528 2025-01-21T12:25:45Z 581:7397:7450

3次元交叉・突然変異を導入した3次元FPGA初期配置のための遺伝的アルゴリズム Genetic Algorithm for 3-D FPGA Initial Placement with 3-D Crossover and Mutation 大村, 道郎 太田, 雅也 Michiroh, Ohmura Masaya, Ohta [一般論文] 遺伝的アルゴリズム，3次元FPGA，初期配置 近年の大規模集積回路における製造技術の進歩にともない，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%配線長の総和が小さい配置を高速に得ることができた． 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. 2014-02-15 jpn journal article https://ipsj.ixsq.nii.ac.jp/records/98528 1882-7764 AN00116647 情報処理学会論文誌 55 2 1059 1068 https://ipsj.ixsq.nii.ac.jp/record/98528/files/IPSJ-JNL5502052.pdf application/pdf 1.9 MB 2016-02-15