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

LSIクロック配線方式の開発

[sub]クロック配線問題[/sub]

図1 クロック配線問題

[sub]図1に対するクロック配線[/sub]

図2 図1に対するクロック配線

[sub]図1に対する最近接関係グラフ[/sub]

図3 図1に対する最近接関係グラフ

[sub]従来手法(配線長1582)[/sub]

図4 従来手法(配線長1582)

[sub]提案手法(配線長1253)[/sub]

図5 提案手法(配線長1253)

 LSIは、大規模なもので数千万個の素子がクロック信号により同期して動作している。近年では、LSIの微細化が進むに従って配線による信号遅延の影響が大きくなり、適切なクロック配線を行うことによってすべての素子を同期して動作させる技術が極めて重要になっている。ほ研究では、グラフアルゴリズム理論、回路理論、最適化理論を組み合わせる新手法により、世界最高のクロック配線方式を開発した。
 クロック配線において同期素子までの信号遅延にばらつきがあると、同期素子に対するクロック信号の到達時間差(スキュー)が生じる。到達時間差があると、回路の正常動作を保証するためにクロック周期を延ばすことが必要になり、性能低下を招く。また、信号遅延自体も波形鈍りを招き正常動作の障害となるため、最小化を図る必要がある。信号遅延は配線長と配線幅に依存するため、配線長と配線幅の最適化が必要である。したがって、信号遅延のばらつきを抑えつつ、配線長・配線幅を最適化するクロック配線を求める問題は、LSI設計において極めて重要である。
 まず本研究では、クロック配線が同期素子をノードするグラフであるとみなして、信号遅延と関係が深い配線長のばらつきを最小化する問題の解析を行い、グラフアルゴリズム理論により解が得られる(多項式時間問題となる)ことを証明した。しかし、配線長・配線幅を最適化するクロック配線を求める問題は、実用的な時間内に解が得られない(NP困難問題となる)。そこで本研究では、実用的な時間で信号遅延を極小化するクロック配線を求める発見的アルゴリズムを開発した。このアルゴリズムでは、配線を極小化するクロック配線を求めた後、そのクロック配線における信号遅延を最小化する配線幅を求める。
 クロック配線は最近接関係グラフ上のクラスタリングを反復して行うことによって求めるが、クラスタ数を制限することにより、配線長を極小に保ちながら、理論計算時間の爆発を抑えることができた。更にバケット手法を用いることにより高速化を図り、実問題では素子数に比例する時間で解けるようにできた。これに伴い最適化性能も向上し、従来比約2割の配線長短縮を達成した。
 上記で得られたクロック配線に対する配線幅は、クロック配線に対する回路微分方程式を解くことにより理論式として求められる。シミュレーションによる結果では、素子数が大きくなるほど信号遅延の削減効果が大きく、大きいものでは8割以上削減できることを示した。
 これらの成果のうち、配線長のばらつきを最小化する問題に対する解析と、配線幅の理論的最適値の算出については、世界初のものである。また、配線長の極小化・配線幅の最適化により信号遅延を極小化する発見的アルゴリズムについては世界最高性能を達成し、現在までこの結果は塗り替えられていない。
 本研究で開発したLSIクロック配線方式は、最新の計算機を用いれば、現在の最高規模の問題に対し数秒でクロック配線の算出が可能であるため、様々なLSIの微細化、大規模化、高速化に有効である。本方式はLSI実用設計に供され、国内におけるLSI事業の発展に大きく寄与している。また、IBM、MotorolaのPowerPCをはじめとする世界の最先端LSI設計にも多大な影響を与えている。

 本研究の成果に対して、電子情報通信学会は、2008年、枝廣正人に業績賞を贈った。

文献

[1] M. Edahiro, "Delay Minimization for Zero-Skew Routing," Proc. IEEE Int'l Conf. on Computer-Aided Design, 1993, pp. 563-566.
[2] M. Edahiro: “Equi-Spreading Tree in Manhattan Distance,” Algorithmica, 16 (1996), pp.316-338.
[3] M. Edahiro, "A Clustering-Based Optimization Algorithm in Zero-Skew Routing," Proc. ACM/IEEE Design Automation Conf., 1993, pp. 612-616.
[4] M. Edahiro, "An Efficient Zero-Skew Routing Algorithm," Proc. ACM/IEEE Design Automation Conf., 1994, pp. 375-380.
[5] A. B. Kahng and G. Robins, "On Optimal Interconnections for VLSI", Kluwer Academic Publishers, 1994.
[6] S. Ganguly and S. Hojat, “Clock Distribution Design and Verification for PowerPC Microprocessors. Proc. IEEE Int'l Conf. on Computer-Aided Design, 1995, pp. 58-61.
特許第2699831号「クロック分配回路」(平成19年度関東地方発明表彰発明奨励賞受賞)

関連する研究を検索

分野のカテゴリ

通信
(エレクトロニクス技術)
電子・デバイス
(基礎となる技術)

関連する出来事

データなし

世の中の出来事

2008
後期高齢者医療制度がスタートする。
2008
米投資銀行リーマン=ブラザースが経営破綻する(リーマン=ショック)。

Webページ

データなし

博物館等収蔵品

データなし

キーワード

LSI、クロック配線、グラフアルゴリズム理論
Page Top