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.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初期配置を決定する上で,有効であることが確認できた.