２００１年度プロジェクト型研究教育助成申請書
代表者氏名：磯 直行
所属学科：メデ ィア科学科
職名：専任講師
課題名：レイアウトアルゴリズムのシステム LSI チップ設計への適用

目的
研究の背景
インターネットにより，携帯電話，PHS をはじめとする携帯情報端末は一気に普及した．今後も「 IT 革命」の名のもと携帯情報端末は発展し続けるのは確実である．これらの携帯情報端末は，CPU ，メモリそして入出力用素子等を１つのチップに集積することにより小型軽量化，低消費電力化，高速化を実現したシステム LSI 技術により支えられている．
次々と開発されるネットワーク技術に追従するため，半導体メーカーは短い設計期間でシステム LSI を開発することが求められている．半導体製品は設計後に不具合を発見した時の損害が非常に大きいため，設計の各段階で何度も検証が行われる．
「配置処理」や「配線処理」といった素子間を接続する配線パタンの位置を決定する段階をレイアウト設計とよぶが，その段階における設計検証は以前より自動化が進んだものの設計者が CAD（ Computer-Aided-Design：計算機支援設計）システムと対話を行いながら最適な配置および配線パタンを決定しているのが現状である．
本研究者は，これまで VLSI やプ リント配線板のレイアウト設計における配置配線処理の自動化に関する研究を行ってきた．特に，レイアウト設計および設計検証に着目し，その処理に必要な時間および記憶量に関して効率の良いレイアウトアルゴリズムを開発してきた．現在，開発したアルゴリズムの有効性を確かめるため，実際のレイアウト設計データを操作するための設計 CAD の修得とチップ試作の準備を行っているところである．

研究目的
本研究は，システム LSI の配置位置決定処理および配線可能性検証処理について，実際の LSI 設計データを提案アルゴリズムに与えることにより，その性能を実験的に調べることを目的とする．また，この研究を学部生および大学院生の協力を得て実施することにより，本学部内でネットワークおよびシステム設計教育を実施するための基盤を作ることを目的とする．

学術的な特色・独創的な点および予想される結果と意義
システム LSI 設計における配置設計は，すべての素子間について，そこを通過する配線数に応じて必要最小限の間隙幅を確保した素子位置を決定することである．素子間を通過する配線数の見積りは，配線領域を小領域へ分割しそこを通過する配線を調べて行われる．本研究の特色の一つはこれまで本研究者が提案してきた領域分割法（三角形分割）を用いることで，配線数見積りの精度向上を実現できることである．
一方，配線設計は配線トポロジを決める概略配線処理と，配線トポロジを設計規則に従った実際の配線パタンに変換する詳細配線処理に分割して行われる．詳細配線時に配線が実現不可能であることが判明すると概略配線を再度行う．従って，設計期間の短縮のためには，概略配線処理の段階で概略配線から詳細配線への変換可能性を高速に検証することが必要である．本研究の二つ目の特徴は，配線処理のできるだけ早い段階で後の処理の可否が判定できることである．
本研究の結果として，システム LSI 設計において高速な処理が可能となる基礎技術が確立され，今後短期間で高性能なシステム LSI が開発されることが期待できる．また，本研究を共同して行う学生は，実際に動くシステムの設計方法やネットワークシステムに触れることができ，最先端のシステム教育を受けることができる．

1

国内外の研究の中での本研究の位置づけ
国内では早稲田大学理工学部大附，柳沢ら及び日本アイビーエム社の江藤らが配線を相対的位置で表現する方法についての研究を行っている．国外ではマサチューセッツ大学の Leiserson と Maley ，カリフォルニア大学サンタクルズ校の Dai らによりラバーバンド と呼ばれる概略配線モデルが提案されている．本研究では，これらのモデルを利用した配線処理に加え，配置位置決定処理と配線可能性判定処理を行うレイアウトアルゴリズムを開発し，その有効性を確認する．

プロジェクト 構成員
教員：磯 直行
大学院生：柘植 芳之（大学院１年生）
学部学生：中塚 昌樹，小林 正芳（学部４年生），および若干名の学部３年生

計画・方法
レイアウト アルゴリズムの改良
すでに，本研究者は平面上に障害物が存在する場合の配線経路探索モデルを提案し，その配線経路が実現できるかどうかの判定アルゴリズムを開発している．本研究ではその結果として素子の位置を修正しても配置配線作業に必要なデータを維持できるデータ構造を提案し，アルゴリズムを改良する．

レイアウト 処理に関する調査
レイアウトアルゴリズムの改良と並行して，書籍，学会誌，会議録等の文献調査を行う．また，普段からレイアウト設計に関わる企業の技術者と情報を交換し，実際のデータに耐えられるシステムについての調査を行う．

システム LSI 設計システムの構築
提案したアルゴリズムの有効性を確認するため，システム LSI 設計システム構築する．システムは VDEC（東京大学大規模集積システム設計教育研究センター）から提供される CAD を用いる．CAD の使用ライセンスについては VDEC 中部サブセンター（名古屋大学）からネットワークを介して取得する．この CAD を実用的に動作させるためには，大容量ディスク，高速な CPU ，メモリを必要とする．デ ィスクについてはメディアアートラボ内設置されている専用ワークステーションを用いる．CPU とメモリについては，現在の研究環境に専用ワークステーションが存在しないため，機器備品費としてワークスーテションを購入する．また，教員の指導のもと学生がこのワークステーションの設定を行うことで，実際のネットワークシステムの動作とその設定方法を習得することができる．

チップ設計
提案したアルゴリズムの実用性を確認するためには，実際のシステム LSI の設計データを用いて動作させると良い．上記のシステム LSI 設計システムを用いてチップ設計を行う．

システム LSI の試作とアルゴリズムの性能調査
システム LSI 設計で得た経験をもとにして，より大規模な設計データを生成し，提案したアルゴリズムへの入力とする．これにより，提案アルゴリズムの不具合点の発見，修正を行う．また，これにより設計した LSI チッ
プを VDEC の協力により試作する．この設計データを用いて，レイアウトアルゴリズムの性能（動作時間，使用メモリ量等）を調べる．

2

学会での成果発表
新しい配置配線アルゴリズムの提案とシステム LSI 設計への適用結果について論文としてまとめ，学会等で発表する．また，提案手法を用いて設計したシステム LSI の試作結果も報告する．

従来の活動経過・準備状況など
これまで，システム LSI ，プ リント配線板を対象とした素子配置手法および配線設計手法に関する研究を行ってきた．以下に現在から順に年度をさかのぼって説明する．
平成１２年度は，新しい配線アルゴリズムとしてビア数最少化についての研究を行った．ビアは多層配線において層間配線を実現する穴であり，これが少ないほど高速に動作することが知られている．提案したビア数最少化アルゴリズムは発見的アルゴリズムであり，今後実際の設計データを入力として与えることによりその性能を確かめることができる．
平成１１年は，これまで提案してきた配置配線アルゴリズムを実現するためのプロトタイプシステムを構築した．これも実際の設計データを適用することによりアルゴリズムの性能を確かめることができ，その準備を進めている．
平成９年，１０年は配線可能性検証に関する研究を行った．配線可能性検証は，配線設計について発見された経路トポロジが設計規則に従った平面配線パタンとして実現できるかどうかを判定することである．そこで配線可能性を高速に行う手法を提案した．レイアウト平面上を走査し比較的単純な処理で配線可能性を判定できることを示した．
平成７年，８年は配置設計についての研究を行った．素子間の相対的な位置関係をグラフで表現する方法を提案した．グラフ上に素子間を通過する配線の本数の見積りを保存し，その見積りから素子間に必要な間隙幅を求め，すべての素子位置を自動決定する方法を提案した．

経費
本研究を遂行するにあたり必要な経費は以下の通りである．

機器備品費：ワークステーション・システム
 本体
Sun Ultra 60 Model 1450
450MHz UltraSPARC II(4MB キャッシュ) x 1 、512MB メモリ、 36GB 10000 回転内蔵ディスク、Elite3D-m6 Series
2 グラフィックス A23-ULD1-9Z-512AV
Sun dot-com 価格：1,485,000 円（参考納入価格：約 1,262,000 円 ） モニタ 21inch
 増設メモリ 512MB
 内蔵フロッピィド ライブ 3.5inch
 内蔵 DVD-ROM ド ライブ
上記機器備品費（動作する最小システム）の参考見積り価格 1,800,750 円（内訳 1,715,000 円＋税 85,750 円 ）消耗品費：チップ試作費
VDEC を利用してローム株式会社へ 8.9mm 角（ PolySi ２層，メタル３層）チップ試作を依頼した場合の予定納入価格：
950,000 円（税抜き）（設計するチップの大きさ，層数，およびメーカにより，価格は大きく変動することがある．
）

3

機器備品費の明細
上記に示した経費のうち機器備品費に相当するものは「ワークステーションシステム」のみである．
ただし，上記は最小システムであり，予算金額に応じて以下順でワークステーション本体を変更することを希望する．
1. Sun Ultra 60 Model 2450
450MHz UltraSPARC II(4MB キャッシュ) x 2 、512MB メモリ、 36GB 10000 回転内蔵ディスク、Creator3D Series
3 グラフィックス A23-ULD2-9L-512AV
Sun dot-com 価格：1,808,000 円（参考納入価格：約 1,536,000 円 ）2. Sun Blade 1000 Model 1750
750MHz UltraSPARC III (8MB Cache) プロセッサ x 1 、Elite3D-m6 Series 2 グラフィックス、1024MB メモリ、
18GB 10,000 回転 FC-AL 内蔵デ ィスク A28UNF1-9Z-D1024JA
Sun dot-com 価格：1,937,000 円（参考納入価格：約 1,646,000 円 ）3. Sun Blade 1000 Model 2750
750MHz UltraSPARC III (8MB Cache) プロセッサ x 2 、Creator3D Series 3 グラフィックス 、1024MB メモリ、
36GB 10,000 回転 FC-AL 内蔵デ ィスク A28UNF2-9L-D1024JB
Sun dot-com 価格：2,583,000 円（参考納入価格：約 2,195,000 円 ）本助成が必要な理由（特に学部均等配分予算との関連）
本研究で用いる CAD は，VDEC から無償で提供されているものである．これは業界最新かつ標準的であるが，それが動作するワークステーションの機種は限られている．いくつか存在している動作機種のうち SunMicrosystem社製のワークステーションが最も流通しており，動作不具合時の対処が他の機種に比べて迅速に行われる．特に，本研究のように個人研究ではなくプロジェクトとして複数人でこのワークステーションを共有して使う場合には，十分な動作速度とメモリが必要である．
このワークステーションを学部均等配分予算で購入する場合，配分される予算のほとんどを機器備品費として計上しなければならない．この場合，研究室（ゼミ）運営や他の研究課題を停止せざるを得ない．この他，リースによる賃貸機器を複数利用する方法が考えられるが，その維持管理は各々の機器について行わなければならず，管理に携わる時間が必然的に増える．よって，一元管理ができ，多くのユーザ・プロセスを実行できる準サーバ級ワークステーションを購入し，短い研究期間内に有効に利用したいと考えている．
上記の理由により，学部均等配分予算だけでは所望のワークステーションを購入するには無理があり，本助成に頼らざるを得ない．

同一課題で申請している学内外の研究費の申請状況
本年度申請している学内外の研究助成は以下の通りである．

 平成１３年度科学研究費補助金（日本学術振興会）
研究題目：レイアウトアルゴリズムのシステム LSI チップ設計への適用（現在結果待ち） 第１０回一般研究者研究助成（財団法人 堀情報科学振興財団）
題目：VLSI CAD アルゴリズムのシステム LSI チップ設計への適用（不採用）

研究業績（著者、題目、論文誌名、ページ数、発行年など）本研究に関連する業績を重要なものから順に列挙する．

 磯 直行，平田 富夫，
平面配線可能性検証アルゴリズムの実現，情報処理学会論文誌, 40, No. 4, pp. 1636 { 1643 (1999)

4

 Naoyuki Iso, Yasushi Kawaguchi, Tomio Hirata,Ecient Routability Checking for Global Wires in Planar Layouts,
IEICE Trans. Fundamentals, E80{A, No. 10, pp. 171 { 177(1997) 磯 直行，平田 富夫，
配置処理のための領域分割の改善，
電子情報通信学会論文誌, J79{A, No. 8, pp. 1474 { 1476 (1996)

 川口 泰，磯 直行，平田 富夫，
配線可能性検証のための容量判定グラフとフロー導出グラフ，
電子情報通信学会論文誌, J80{A, No. 1, pp.135 { 142 (1997)

 Naoyuki Iso, Yasushi Kawaguchi, Tomio Hirata,

Ecient Routability Checking for Global Wires in Planar Layouts,
Proceedings of the Asia and South Paci c Design Automation Conference, Tokyo, pp. 641 { 644 (1997)
 宮田優治，磯 直行，平田富夫,２層配線における発見的ビア数最少化手法，
電子情報通信学会技術報告, VLD99{122, pp. 41 { 48 (2000)
 磯 直行，平田 富夫，
配線処理のための領域分割の改善，
情報処理学会 設計自動化研究会報告, DA78{25, pp. 151 { 156 (1995)

 磯 直行，伊藤 誠，平田 富夫，
詳細配線問題を組み込んだ配線モデル，
電子情報通信学会技術報告, VLD94{70, pp. 43 { 48 (1994)

5