3次元VLSI配置設計における並列アルゴリズムに関する研究

3D VLSI版图设计并行算法研究

基本信息

批准号：
10780208
负责人：
大村道郎
金额：
$ 1.15万
依托单位：
Hiroshima Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 1999
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-10780208/
关键词：
3次元VLSI 初期配置並列可視化

项目摘要

本研究で得られた成果の概要を以下にまとめる.1.3次元グラフィックスを用いたレイアウト可視化ツールの開発当初,平成11年度から開発を始める予定であったが,3次元VLSI初期配置アルゴリズムを開発するときにレイアウト結果を確認することが必要なため,アルゴリズムの開発に先立って開発を始めた.開発したレイアウト可視化ツールの以下の機能を用いて,レイアウトの詳細な検討が可能となった.(1)ポップアップメニューとマウスを用いた,レイアウトデータに対する回転・拡大・縮小(2)アルゴリズムや配置パラメータの異なる2つのレイアウトデータの同時表示(3)配置領域内部の仮想配線領域の重なり具合の表示(4)特定の仮想配線領域以外の消去,もしくは半透明化(5)色および透明度を変化させることによる,配線混雑度の表示2.3次元配置設計のための並列アルゴリズムの開発まず,3次元VLSI初期配置問題を定式化し,比較対象とする最適解を求めるための並列アルゴリズムを開発した.また,その性能を評価するため,並列計算機上で実験を行った.実験の結果,提案したアルゴリズムは,CPUを2個使った場合で平均約40%,4個使ったときで平均約60%,それぞれ計算時間を短縮することができた.次に並列計算機を対象とした,3次元VLSI初期配置のためのヒューリスティックアルゴリズムを開発し,その性能を評価するため,並列計算機上で実験を行った.実験の結果,提案したアルゴリズムは,CPUを2個使った場合で平均約35%,4個使ったときで平均約50%,それぞれ計算時間を短縮することができた.これらのアルゴリズムは,3次元VLSI初期配置を決定する上で,有効であることが確認できた.

本研究中获得的结果的概述总结为1。最初计划在1999年开始开发3D图形时使用3D图形开发布局可视化工具，但是由于在开发3D VLSI初始位置算法时必须检查布局结果，因此在算法开发之前开始开发。使用已开发的布局可视化工具的以下功能，已经使详细的布局注意事项成为可能。（1）使用弹出菜单和鼠标的旋转，扩大和减少布局数据（2）同时显示两个带有不同算法和布局参数（3）在放置区域的重叠条件（4）删除的虚拟接线区域的布局数据（3）擦除特定的虚拟接线区域或半透明度（5）calling contrice calliend callience（5）carterion calling（5）carterifection（5）carterion calling（5）首次制定了3D VLSI初始布置问题，并开发了一种并行算法，用于查找要比较要比较的最佳解决方案。此外，为了评估其性能，在平行计算机上进行了实验。实验的结果表明，使用两个CPU时所提出的算法能够将计算时间减少约40％，而使用四个CPU时的计算时间约为60％。接下来，为平行计算机开发了针对3D VLSI初始布置的启发式算法，为了评估其性能，在平行计算机上进行了实验。实验的结果表明，使用两个CPU时所提出的算法能够将计算时间减少约35％，而使用四个CPU时的计算时间约为50％。这些算法被确认可以有效地确定3D VLSI初始布置。