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

3D封装问题研究及其在3D VLSI实现技术中的应用

• 批准号: 17700079
• 负责人: 二宮 洋
• 金额: $ 0.96万
• 依托单位: Shonan Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2006
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17700079/
• 关键词: 3次元パッキング問題; 3次元VLSI; 3次元実装技術; 組合せ最適化問題; Simulated Annealing手法; タブーサーチ手法; 組み合わせ最適化問題; シミュレーティッドアニーリング手法

近年の大規模集積回路における製造技術の進歩に伴い、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手法を取り上げ、この手法について考察した。さらに、この手法に対して、タブーサーチ手法を拡張した新たな最適化手法を提案した。本研究での提案手法は、従来の手法に対して非常に有効であることを、コンピュータシミュレーションを通して明らかにした。

随着大型集成电路的制造技术的最新进展，研究了具有多个活跃层的3D密度包装，这些层将三维SIP（包装中的系统）集成到三个维度上，从而吸引了注意力。基本问题是3D填料问题，其中将多个3D模块放在最小的体积中而不相互重叠。该研究主题提出了解决3D包装问题的解决方案，并将对3D高密度包装技术的应用进行基础研究。具体而言，我们对以下三个点进行了研究：（1）为了解决3D包装问题的3D包装表达方法，需要在计算机上处​​理3D包装问题的表示方法。根据这一要求，本研究提出了一种3DBSG（3维有界的切片网格）结构，该结构扩展了BSG（有界的切片网格）结构，该结构已被提议作为表示平面上矩形堆积的方法（2d）。 （2）使用模拟退火的3D包装解决方案是一个组合优化问题，难以在NP中使用。因此，有必要制定3DBSG结构中表达的3D填料作为优化问题，并使用计算机找到解决方案。该研究主题使用模拟退火技术研究了3D包装问题的解决方案。结果，我们能够证明本研究主题中提出的3DBSG方法的有用性。 （3）研究基于O-Tree的包装方法和解决方案，该研究以O-Tree方法为新的包装方法，并研究了此方法。此外，已经为此方法提出了一种新的优化方法，该方法扩展了禁忌搜索方法。通过计算机模拟揭示了这项研究中提出的方法，它对传统方法非常有效。

项目成果

Two-stage Tabu Search for Nonslicing Floorplan Problem Represented by O-Tree

O-Tree 代表的非切片布局问题的两阶段禁忌搜索

• 发表时间: 2007
• 期刊: Journal of Signal Processing vol. 11
• 作者: Ninomiya;H.;Numayama;K.;Asai.H
• 通讯作者: Asai.H

Three-Dimensional Module Packing Using 3DBSG Structure

使用3DBSG结构的三维模块封装

• 发表时间: 2005
• 期刊: Journal of Signal Processing vol.9
• 作者: Ninomiya;H.;Yamagishi;H.;Asai;H.
• 通讯作者: H.