1. HOME
  2. 電気・情報関連(専門)
  3. 研究情報(登録番号320)

LSIの統計力学的配置理論とそれに基づく配線収容性予測技術

  • 写真なし原田 紀夫(拓殖大学)
ゲートアレイの模式図

図1 ゲートアレイの模式図

ゲートアレイのチャネルモデル

図2 ゲートアレイのチャネルモデル

論理回路の結線モデル(LSIモデル)

図3 論理回路の結線モデル(LSIモデル)

配線長の理論分布と実測分布の比較

図4 配線長の理論分布と実測分布の比較

温度と平均配線長の関係(高温)

図5 温度と平均配線長の関係(高温)

温度と平均配線長の関係(低温)

図6 温度と平均配線長の関係(低温)

統計的最適配置方程式

図7 統計的最適配置方程式

平均配線長と配線長分布

図1 平均配線長と配線長分布

 スーパーコンピュータなどに用いられるLSIを生産する場合、限られたスペースを生かすためLSIチップの適正配置と配線収容性の予測が極めて重要である。この研究はゲートアレイ方式で製造するLSI(図1参照)のレイアウト設計に関するものである。配線領域を広く取ればチップ面積を増大させ、狭すぎればレイアウト設計が難しくなって必要な回路が搭載できなくなる。これを解決するために世界で初めてLSIの統計力学的配置理論を構築し、その理論に基づいたLSIの配線長予測法を開発し、その妥当性と実用性を明らかにした。

 ゲートアレイ方式や同じ機能をもつセル配列のLSIを対象とし、同一のセルを縦v1、横v2に並べたセル配列(図2参照)でモデル化するが、理論は記述を簡単にするために v = v1 = v2 として正方形状(v×v) (v≥1)の格子グラフとする。搭載される論理回路は、例えばセルを節点に対応させ、セル間の配線は結線の情報だけが必要なので、向きのない無向枝をもつグラフで表す。

 節点間には、(1)たかだか一つの枝のある連結グラフで表現するLSIモデル(図3)と、(2)並行枝を許すMCPモデルと、(3)すべての枝を区別するモデルの3通りに分けられるが、この論文では(1)について理論を説明している。また搭載される論理回路を表すグラフの節点数は、基板のサイズv×v=v2(=Vとおく)と同じとする。すなわち理論は、すべてのセルは使用されるものと仮定して構築される。配線のNETの問題やセル使用率など、理論と実際のギャップは適用技術で補うことにする。

 このようにモデル化したとき配置問題は、搭載されるグラフの各節点を基板の格子グラフのそれぞれ一つの格子点に割り当てる問題となる。このとき配置の評価は、基板上の枝をその両端の格子点間のマンハッタン距離をその枝の配線長とし、すべての枝の配線長の総和(総配線長)が短いものを良い配置とする。この配置全体の評価関数を最小にする配置を求めることや最小値を求めることは「NP完全問題」あるいは「NP困難問題」と呼ばれ、現時点では多項式時間で解くアルゴリズムは見つかっていない。

 この問題を配置問題そのものとして捉えるのでは難しいがしかし配線収容性予測という立場からはひとつの最適な配置を求めることが重要なのではなく、予測を的確に行うことができる手法を作ることである。予測が必要となるのはLSIの基板を設計する時点であり、このときはまだ搭載される論理回路の詳細が決定していない。また論理回路の数が数百に上ること、多くの工程が同時並行的に進められることも考慮して解決しなければならない。また設計された論理回路が実際に用意された基板に搭載できるか否かを判定する問題にも対応する必要がある。このような問題点や状況の分析からこれらの問題を実用的に解決するためには本質的な配置の理論を構築し、少数のパラメータで記述される方法が不可欠であるという考えに至った。

 こうした難題の解決に役立ったのは統計力学的方法であった。これによって明確な配置理論を構築し、その理論に基づいて配線長を予測する手法を開発し、さらに理論の妥当性と予測法の実用性までを検証した。

 この理論では、回路を表す連結グラフの枝 (配線) を統計力学における「粒子」に、枝が基板上に置かれたときの配線の長さを「粒子のエネルギー」に、配置の不規則さ(複維さ)を「温度」に対応させる。これによりLSIモデル(枝がたかだか1本の連結グラフ)では配線長分布が統計力学における「フェルミ・ディラック統計」に、MCPモデル(並行枝を許す連結グラフ)では「ボーズ・アインシュタイン統計」になること、また近似分布理論では「ボルツマン統計」となることが導かれた。

 ただし、ボルツマン係数に当たる定数は1としている。近似理論では平均配線長Rと配線長分布は温度Tのみで決まり、平均配線長と配線長分布は式1(図表群の最後)で与えられる。また絶対零度ではすべての配線が1という配置に対応することが分かる。図4は、この近似理論分布と実際のLSIの配線長の実測分布を比較したもので、近似分布が実測分布をよく表していることが分かる。

 しかし図5図6のように、温度と平均配線長の関係を用いてプロットしてみると、実際のLSIの配置問題が取り扱うのは理論における極く低温に相当することが分かる。低温に属するということは、ボルツマン統計ではなく、フェルミ・ディラック統計、ボーズ・アインシュタイン統計として扱わなければならないことを意味している。この場合には平均配線長の最も短い配置は、温度などが極限の状態になった場合に相当すると考えられる。このとき分布形がフェルミ・ディラック統計に従うとして成立する関係式が導かれ、統計的最適配置方程式(図7)として提出されている。

 配線収容性の予測の多くは配線長の予測が基礎になっているが、この統計的最適配置方程式により、統計的意味における最適配置の平均配線長を求めることが可能となる。この方法は実際のスーパーコンピュータ用LSIの基板やMCPの設計・開発・製造などで生ずる配線収容性の問題に適用され、これを解決している。

 以上のように、この論文はLSIの配線収容性予測という技術的難題を全く新しい統計力学的配置理論で解決し、それを基礎に実用的予測法を確立した。またLSIのレイアウト問題にとどまらず、組合せ問題に関連する広い分野の発展に貢献するものと期待される。

文献

※本論文は同年に第3回米澤ファウンダーズ・メダル受賞記念特別賞を受賞し、また原田紀夫氏は1988年に再度関係論文で論文賞を再度受賞した。

[1] 原田紀夫、LSIの統計力学的配置理論とその応用、1983年、電子通信学会,論文誌A,Vol.J66-A,No.10
[2] Norio HARADA、A New Interconnection Length Prediction Method for
Masterslice LSI、1982年、IEEE, Proc. ISCAS'82, Rome, 1982, pp760-763
[3] Norio HARADA、LSI Interconnection Length Prediction Method
Using a Statistical Mechanical Placements
Theory、1984年、NEC Research & Development,No.72,pp56-63
[4] 原田紀夫、LSIの統計力学的配置理論とスーパーコンピュータ、1989年、土木学会(スーパーコンピュータ特集号)Vol.74,pp48-49
[5] 原田紀夫、統計力学を用いたLSIの配置:理論と応用、1996年、「応用数理」応用数理学会誌,Vol.6,No.3, pp17-32,Sept.1996
[6] 原田紀夫、統計力学的手法によるLSI配線収容性問題の解法、1998年、電気学会編「遺伝アルゴリズムとニューラルネット」
コロナ社,第8章,pp183-198
[7] 原田紀夫、スーパーコンピュ-タの波及効果を考える、2000年、拓殖大学理工学研究所報告Vol.7,No.3pp99-106
[8] 原田紀夫、統計力学的LSI配線長予測法の概要、1983年、昭58年度電子通信学会総合全国大会
[9] 速水 謙 原田紀夫、マルチチップパッケージのI/O配線長予測、1983年、昭58年度電子通信学会総合全国大会
[10] 原田紀夫、並列処理の平均膨張率理論とその応用、本技術に取り組むキッカケを与えたモデルの発展形、1987年、電子情報通信論文誌a Vol.J70-A,No.4,pp695-706

関連する研究を検索

分野のカテゴリ

情報処理
(その他(情報処理))

関連する出来事

1983年4月
NEC スーパーコンピュータSX-1,SX-2の発表

世の中の出来事

1985
つくば市で科学万博が開幕する。
1985
電電公社が民営化され、NTTが発足する。

Webページ

データなし

博物館等収蔵品

データなし

キーワード

VLSI設計技術、LSIレイアウト設計、配線収容性、統計力学、スーパーコンピュータ、平均配線長、配線長分布、フェルミディラック統計、統計的最適配置方程式、温度
Page Top