3次元パッキング問題と3次元VLSI実装技術への応用に関する研究

点击翻译按钮获取中文摘要

近年の大規模集積回路における製造技術の進歩に伴い、3次元のSiP(System in Package)や回路素子自体を3次元に集積し、複数の能動層を持つ3次元密度実装に関する研究が注目されている。その基本となる問題に、「複数の3次元モジュールを互いに重なり合うことなく最も体積の小さい直方体内に配置する」という3次元パッキング問題がある。本研究課題では3次元パッキング問題の解法の提案とともに、3次元高密度実装技術への応用に関する基礎研究を行う。具体的には、次の3点についての研究を行った。(1)3次元パッキングの表現手法について3次元パッキング問題の解法のためには、計算機上で3次元パッキング問題を扱うための表現方法が必要である。この要求に対して、本研究では、これまでに平面(2次元)上での矩形パッキング表現方法として提案されているBSG(Bounded Sliceline Grid)構造を拡張した3DBSG(3-Dimensional Bounded Sliceplane Grid)構造を提案した。(2)シミュレーティッドアニーリングを用いた3次元パッキングの解法について3次元パッキング問題はNP困難な組み合わせ最適化問題である。このため、3DBSG構造で表現された3次元パッキングを最適化問題として定式化し、計算機を用いて解を求める必要がある。本研究課題ではシミュレーティッドアニーリング手法を用いた3次元パッキング問題の解法に関して検証を行った。この結果、本研究課題で提案する3DBSGを用いた手法の有用性を示すことができた。(3)O-treeに基づくパッキング手法の考察とその解法に関する研究本研究では、新たなパッキング手法としてO-tree手法を取り上げ、この手法について考察した。さらに、この手法に対して、タブーサーチ手法を拡張した新たな最適化手法を提案した。本研究での提案手法は、従来の手法に対して非常に有効であることを、コンピュータシミュレーションを通して明らかにした。