三次元集積電気回路の配線構造及びそのレイアウト方法
【課題】複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減する。
【解決手段】本発明による三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は前記二次元集積電気回路モジュールのほぼ中央を貫通する貫通ビアを通して構成され、前記電気回路モジュール及び前記交換接続手段とを接続する配線構成をFat Treeトポロジ又はFat H−Treeトポロジを用いて構成される。
【解決手段】本発明による三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は前記二次元集積電気回路モジュールのほぼ中央を貫通する貫通ビアを通して構成され、前記電気回路モジュール及び前記交換接続手段とを接続する配線構成をFat Treeトポロジ又はFat H−Treeトポロジを用いて構成される。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は三次元集積電気回路の配線構造及びそのレイアウト方法に関する。詳しくは、ツリー型のトポロジについて、垂直方向配線を用いて配線長を削減し、配線遅延を短縮可能とする三次元集積電気回路の配線構造及びそのレイアウト方法に関する。
【背景技術】
【0002】
半導体技術の進歩により、単一チップ上にプロセッサやメモリ、入出力(I/O)インタフェースなど複数の設計モジュールをタイル状に実装できるようになった。このようなタイルアーキテクチャでは、タイルだけでなくタイル同士を結合するための配線ネットワークを含めてチップ上に(主として2次元チップ上に)構成するチップ上ネットワーク(Network−on−Chip、略してNoCという。)トポロジが用いられ、そのネットワークトポロジはアプリケーションの性能と面積、消費電力を決定付ける一要素となっている。(非特許文献1参照)
【0003】
近年注目を浴びているのが、チップの3次元化である。3次元集積回路(IC)は複数枚のウエハまたはダイを垂直方向に重ね合わせることで実現される。複数枚のチップを垂直方向に積み重ねることで、個々のチップの寸法を小さく抑えることができ、結果的に配線長および配線遅延を削減できる。(非特許文献2〜4参照)
【0004】
図23に2次元ICと3次元ICの比較を示す。図23(a)は通常の2次元ICを、図23(b)はそれと同面積の3次元ICを示す。この3次元ICでは4枚のチップを積層することにより、個々のチップの面積は1/4、チップの両端を結ぶ配線長は1/2に削減される。これに伴い配線遅延及び必要なリピータの数も削減される。
【0005】
通常の2次元ICにおいては2−Dメッシュ(Mesh)や2−Dトーラス(Torus)などのグリッド型のトポロジが広く用いられている。3次元ICを想定したNoCの研究はまだ数が少ないが、3−D Meshや3−D Torusをベースにしたものがいくつか報告されている。これらは、通常の2次元NoCで広く用いられる2−D Meshや2−D Torusから容易に拡張できるという利点を持つ。
【0006】
【非特許文献1】Dally,W.J.and Towles,B.:Route Packets,Not Wires:On−Chip Interconnection Networks,Proceedings of the 38th Design Automation Conference,pp. 684−689 (2001)
【非特許文献2】Davis,W.R.,Wilson,J.,Mick,S.,Xu,J.,Hua,H.,Mineo,C.,Sule,A.M.,Steer,M.and Franzon,P.D.:Demystifying 3D ICs:The Pros and Cons of Going Vertical,IEEE Design & Test of Computers,Vol.22,No.6,pp.498−510 (2005)
【非特許文献3】Li,F.and et.al.:Design and Management of 3D Chip Multiprocessors Using Network−in−Memory,Proceedings of the International Symposium on Computer Architecture,pp.130−141 (2006)
【非特許文献4】Das,S.and et.al.:Technology,Performance,and Computer Aided Design of Three−Demensional Integrated Circuits,Proceedings of the International Symposium on Physical Design,pp.108−115 (2004)
【発明の開示】
【発明が解決しようとする課題】
【0007】
しかし、3−D Meshでは2−D Meshと比べ、オンチップルータのリンク数が4から6に増え、これに伴いオンチップルータのチャネルバッファおよびクロスバスイッチの面積が増加する、また、垂直方向のリンクは数十μm程度と非常に短いため、パケットが垂直方向に移動する度にルータでラッチする必要はない、すなわちラッチにより電力が余分に消費され遅延も生じるという欠点が指摘されており、ルータのハードウェア量の割りに得られるメリットは大きくない。
【0008】
他方、ツリー型トポロジについては、上位リンクの配線長が長くなるため、リンクの配線長が均一なグリッド型トポロジに比べて、配線遅延やリピータ数、消費電力の点で不利となると考えられ、NoCへの適用がためらわれてきた。しかしながら、3次元化によって上位リンクの配線長を短くでき、上記弱点を克服できると考えられる。また、3次元ICではグリッド型のトポロジに比して性能パフォーマンスが優ることが期待できる。
【0009】
本発明は、複数のモジュール間を接続する集積電気回路の配線構造において、適正なツリー型トポロジで3次元構造を実現することにより、2次元配線構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することを目的とする。
【課題を解決するための手段】
【0010】
上記課題を解決するために本発明の第1の態様における三次元集積電気回路の配線構造は、例えば図8に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリー(Fat Tree)トポロジを用いて構成される。
【0011】
ここにおいて、交換接続手段とはモジュールを1対多数又は多数対多数の接続が可能な接続手段をいい、ルータ、交換機のスイッチ等が該当する。また、Fat Treeトポロジは例えば図11のような電気回路モジュールと交換接続手段の配線接続関係を規定するトポロジであるが、交換接続手段の上向きリンク数p、下向きリンク数q及び電気回路モジュールの上向きリンク数cにより複数の態様があり、このような態様のFat Treeを(p,q,c)Fat Treeと称する。このように構成すると、複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【0012】
上記課題を解決するために本発明の第2の態様における三次元集積電気回路の配線構造は、例えば図19及び図20に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリー(Fat H−Tree)トポロジを用いて構成される。
【0013】
ここにおいてFat H−Treeトポロジは、Fat Treeトポロジと同様に電気回路モジュールと交換接続手段の配線接続関係を規定するトポロジで、発明者達の提案による高パフォーマンスのトポロジである(松谷宏紀、鯉渕道紘、天野英晴:3次元IC向けFat TreeベースNetwork−on−Chips、情報処理学会研究報告2007−ARC−171,2007−EMB−3,p75−80,Jan,2007 及び、松谷宏紀、鯉渕道紘、天野英晴:チップ内ネットワークにおけるFat H−Treeトポロジの性能評価、情報処理学会研究報告2006−ARC−169,p109−114,Aug,2006 参照)。このように構成すると、複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【0014】
また、本発明の好ましい態様によれば、第1の態様又は第2の態様の三次元集積電気回路の配線構造において、前記交換接続手段を制御する制御手段と前記交換接続手段と前記制御手段とを接続する制御信号線を備え、前記二次元集積電気回路モジュール間に布設される制御信号線は貫通ビアを通して配線される。このように構成すると、制御系配線についても配線長を低減し、モジュール間の通信遅延を低減できる。
【0015】
また、本発明の好ましい態様によれば、以上の態様の三次元集積電気回路の配線構造において、前記貫通ビアの少なくとも1つは前記二次元集積電気回路モジュールのほぼ中央を貫通する。ここにおいて、貫通ビアは二次元集積電気回路モジュールのほぼ中央を貫通するものに加え、別の位置にあっても良い。また、貫通ビアは連結する最下層の二次元集積電気回路モジュールについては配線接続できれば必ずしも貫通する必要はない。このように構成すると、垂直方向配線の配線長を低減でき、モジュール間の通信遅延を低減できる。
【0016】
また、本発明の好ましい態様によれば、以上の態様の三次元集積電気回路の配線構造において、例えば図8に示すように、各電気回路領域は同一寸法の正方形又は長方形である。ここにおいて正方形又は長方形の辺の寸法や内角は設計誤差や製造ばらつきにより多少のばらつきが有っても良い。このように構成すると、電気回路モジュールを2次元平面内に無駄なく配置でき、また3次元の配線構造の設計も効率化できる。
【0017】
また、本発明の好ましい態様によれば、第1の態様の三次元集積電気回路の配線構造において、例えば図8に示すように、下位の交換接続手段に繋がる上位の交換接続手段は2個または4個である。このように構成すると、モジュール間の接続パスを多重ルートにして通信トラヒックの集中を緩和できる。また、単一モジュールへの複数入力を要する演算、複数モジュールへの出力等を効率化できる。
【0018】
また、本発明の好ましい態様によれば、第1の態様の三次元集積電気回路の配線構造において、例えば図8に示すように、電気回路モジュールを二次元平面に2行2列に配置して第1レイヤモジュールを構成し、第1レイヤモジュールを二次元平面に2行2列に配置して第2レイヤモジュールを構成し、第m−1レイヤモジュールを二次元平面に2行2列に配置して第mレイヤモジュールを構成し、第mレイヤモジュールを三次元空間に4層積層して第m+1レイヤモジュールを構成し、第m+1レイヤモジュールを三次元空間に4層積層して第m+2レイヤモジュールを構成し、第n−1レイヤモジュールを三次元空間に4層積層して第nレイヤモジュールを構成し(1<m<nとする)、4個の第1レイヤモジュールの面心付近に4つの電気回路領域と2つ又は4つの第2ランク交換接続手段に繋がる第1ランク交換接続手段を備え、4個の第2レイヤモジュールの面心付近に4つの第1ランク交換接続手段と2つ又は4つの第3ランク交換接続手段に繋がる第2ランク交換接続手段を備え、4個の第m−1レイヤモジュールの面心付近に4つの第m−2ランク交換接続手段と2つ又は4つの第mランク交換接続手段に繋がる第m−1ランク交換接続手段を備え、4層の第mレイヤモジュールの各層に4つの第m−1ランク交換接続手段と2つ又は4つの第m+1ランク交換接続手段に繋がる第mランク交換接続手段を備え、4層の第mレイヤモジュールを貫き4つの第mランク交換接続手段と第m+1ランク交換接続手段を繋ぐ第mの垂直方向配線を備え、4層の第m+1レイヤモジュールの各層に4つの第mランク交換接続手段と2つ又は4つの第m+2ランク交換接続手段に繋がる第m+1ランク交換接続手段を備え、4層の第m+1レイヤモジュールを貫き4つの第m+1ランク交換接続手段と第m+2ランク交換接続手段を繋ぐ第m+1の垂直方向配線を備え、4層の第n−1レイヤモジュールの各層に4つの第n−2ランク交換接続手段と2つ又は4つの第nランク交換接続手段に繋がる第n−1ランク交換接続手段を備え、4層の第n−1レイヤモジュールを貫き4つの第n−1ランク交換接続手段と第nランク交換接続手段を繋ぐ第n−1の垂直方向配線を備える。
【0019】
ここにおいて、レイヤモジュールの面心とは、当該レイヤモジュールが4個の下位のレイヤモジュール又は4個の電気回路モジュールで構成されている場合には、これら4個のモジュールの頂点が集まる位置をいう。また、m及びnは整数で、1<m<nである。このように構成すると、3次元空間にFat Treeトポロジを適用した、配線遅延が低減された三次元集積電気回路を実現できる。
【0020】
また、本発明の好ましい態様によれば、第2の態様の三次元集積電気回路の配線構造において、例えば図19及び図20に示すように、電気回路モジュールを二次元平面に2行2列に配置して第1レイヤモジュールを構成し、第1レイヤモジュールを二次元平面に2行2列に配置して第2レイヤモジュールを構成し、第m−1レイヤモジュールを二次元平面に2行2列に配置して第mレイヤモジュールを構成し、4個の第1レイヤモジュールの面心付近に4つの電気回路領域と1つの第2ランク交換接続手段に繋がる第1ランク交換接続手段を備え、4個の第2レイヤモジュールの面心付近に4つの第1ランク交換接続手段と1つの第3ランク交換接続手段に繋がる第2ランク交換接続手段を備え、4個の第m−1レイヤモジュールの面心付近に4つの第m−2ランク交換接続手段と1つの第mランク交換接続手段に繋がる第m−1ランク交換接続手段を備え、前記全ての第1ランク交換接続手段乃至第m−1ランク交換接続手段を右方向及び下方向に1モジュールずつ循環シフトした位置に第1ランク交換接続手段乃至第m−1ランク交換接続手段を備え、第mレイヤモジュールを三次元空間に4層積層して第m+1レイヤモジュールを構成し、第m+1レイヤモジュールを三次元空間に4層積層して第m+2レイヤモジュールを構成し、第n−1レイヤモジュールを三次元空間に4層積層して第nレイヤモジュールを構成し(1<m<nとする)、4層の第mレイヤモジュールの重心付近の第m−1レイヤモジュールに4つの第m−1ランク交換接続手段と1つの第m+1ランク交換接続手段に繋がる第mランク交換接続手段を備え、4層の第mレイヤモジュールを貫き4つの第mランク交換接続手段と第m+1ランク交換接続手段を繋ぐ第mの垂直方向配線を備え、4層の第m+1レイヤモジュールの重心付近の第mレイヤモジュールに4つの第mランク交換接続手段と1つの第m+2ランク交換接続手段に繋がる第m+1ランク交換接続手段を備え、4層の第m+1レイヤモジュールを貫き4つの第m+1ランク交換接続手段と第m+2ランク交換接続手段を繋ぐ第m+1の垂直方向配線を備え、4層の第n−1レイヤモジュールの重心付近の第n−2レイヤモジュールに4つの第n−2ランク交換接続手段と1つの第nランク交換接続手段に繋がる第n−1ランク交換接続手段を備え、4層の第n−1レイヤモジュールを貫き4つの第n−1ランク交換接続手段と第nランク交換接続手段を繋ぐ第n−1の垂直方向配線を備え、前記第mレイヤモジュール乃至前記第nレイヤモジュール内の電気回路モジュールの配置は第nレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし、前記全ての第1ランク交換接続手段乃至第m−1ランク交換接続手段を右方向及び下方向に1モジュールずつ循環シフトした位置に配置された第1ランク交換接続手段乃至第m−1ランク交換接続手段については、前記第mレイヤモジュール乃至前記第nレイヤモジュール内の電気回路モジュールの配置を第nレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし、同一の第1レイヤモジュールに属する電気回路モジュールで第1ランク交換接続手段と異なる二次元平面に配置されたものと前記第1ランク交換接続手段を繋ぐ第1の垂直方向配線を備え、前記再配置した第mレイヤモジュール乃至第nレイヤモジュールにおいても前記第mランク交換接続手段乃至前記第nランク交換接続手段と同様の接続関係を有する。
【0021】
ここにおいて、レイヤモジュールの重心付近とは、二次元平面での面心付近で、さらに三次元積層構造の垂直方向においても中心に近いことをいい、当該レイヤモジュールが4層の下位のレイヤモジュールで構成されている場合には、第2層目又は第3層目が該当する。この下位のレイヤモジュールがさらに下位の4層のレイヤモジュールで構成されている場合には、垂直方向においてできるだけ中心に近い1層に配置されるのが好ましい。このように構成すると、3次元空間にFat H−Treeトポロジを適用した、配線遅延が低減された三次元集積電気回路を実現できる。
【0022】
上記課題を解決するために本発明の第3の態様における三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される。
【0023】
ここにおいて、配線には無線による配線を含むものとする。また、無線送受信手段として一体化された送受信回路を用いても良く、個別の送信回路と受信回路とを用いても良い。このように構成すると、複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【0024】
上記課題を解決するために本発明の第4態様における三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される。
【0025】
このように構成すると、複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【0026】
また、以上の態様の三次元集積電気回路の配線構造において、前記電気回路モジュールは空モジュールを含む。ここにおいて、空モジュールは電気回路を搭載していないモジュールであり、今後電気回路を搭載したモジュールに置換が予定されているものでも良く、本来電気回路が不要で空きスペースになっているものでも良い。このように構成すると、モジュール数(コア数)が4n等に該当しない場合にも本発明の配線構造を適用できる。
【0027】
上記課題を解決するために本発明の第1の態様における三次元集積電気回路の配線構造のレイアウト方法は、例えば図14に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される三次元集積電気回路の配線構造のレイアウト方法であって、前記ファットツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程(S10)と、前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程(S20)と、前記ノードマッピング工程(S20)で配置された前記三次元集積電気回路を前記ツリー分割工程(S10)で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程(S30)と、前記折り畳み工程(S30)で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクする垂直リンク工程(S40)とを備える。このように構成すると、本発明の第1の態様における三次元集積電気回路の配線構造を効率的に実現できる。なお、第3の態様における三次元集積電気回路の配線構造については、垂直リンク工程(S40)の貫通ビアを無線配線に代えることにより、同様に実現可能である。
【0028】
上記課題を解決するために本発明の第2の態様における三次元集積電気回路の配線構造のレイアウト方法は、例えば図14に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される三次元集積電気回路の配線構造のレイアウト方法であって、前記ファットエイチツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程(S10)と、前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程(S20)と、前記ノードマッピング工程(S20)で配置された前記三次元集積電気回路を前記ツリー分割工程(S10)で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程(S30)と、前記折り畳み工程(S30)で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクする垂直リンク工程(S40)とを備える。このように構成すると、本発明の第1の態様における三次元集積電気回路の配線構造を効率的に実現できる。なお、第3の態様における三次元集積電気回路の配線構造については、垂直リンク工程(S40)の貫通ビアを無線配線に代えることにより、同様に実現可能である。
【0029】
また、本発明は、第1又は第2の態様の三次元集積電気回路の配線構造のレイアウト方法をコンピュータに実行させるためのコンピュータ読み取り可能なプログラムとして実現できる。
【発明の効果】
【0030】
本発明によれば、複数のモジュール間を接続する集積電気回路の配線構造において、適正なツリー型トポロジで3次元構造を実現することにより、2次元構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することができる。
【発明を実施するための最良の形態】
【0031】
[配線トポロジ]
以下に、図面に基づき本発明の実施の形態について説明する。まず、NoCで用いられる2次元及び3次元配線のトポロジについて説明する。
【0032】
図1に、リンク数が小さく対称な2次元レイアウトが可能なトポロジの代表例を示す。図1(a)に2−D Mesh、図1(b),(e)に2−D Torus、図1(c)にエイチツリー(H−Tree)、図1(d)にFat Treeのトポロジを示す。各トポロジにおいて、複数のルータが行列で配列され、四角はルータ、丸はコアをそれぞれ表す。図1(a)の2−D Meshは、隣り合うルータを格子状に配線したもので、Rawプロセッサ、Tripsプロセッサ、ストリーム処理向けNoCであるaSOC(Adaptive System on a Chip)、picoChip社の超並行処理プロセッサアレイなどに幅広い用途で用いられている。図1(e)の2−D Torusは、2−D Meshの配線に加え、ネットワークの両端のコアを結ぶラップアラウンド(wrap−around)チャネルを有している。図1(b)はこれを、チャネル長が均一になるようにコアの行、列を0,3,1,2の順に配置換えしたものである。2−D TorusはIMEC社のNoCなどで用いられている。図1(c)のH−Treeは、4分木配線構造を取る。すなわち、4個のコアをレベル1ルータで交換接続し、さらに4個のレベル1ルータをレベル2ルータで交換接続し、ツリー構造で通信対象を拡大する方式である。このため、2次元平面実装に適しているが、トラフィックがツリーの上位のルータ付近に集中しやすいという問題がある。H−Treeはアンドレ・デホン(Andre Dehon)らが提案した計算システムSCORE(Stream Computations Organized for Reconfigurable Execution)やQuickSilver社のACM(Adaptive Computing Machine)などのリコンフィギャラブルシステムで利用されている。
【0033】
次に、本発明の3次元配線に適用するトポロジであるFat Treeについて説明する。図1(d)のFat TreeはH−Treeにおけるツリー構造を多重化したものであるが、ルータの上向きリンク数p、下向きリンク数q、コアの上向きリンク数cの組み合わせがあり、これを(p,q,c)で表わす。図1(d)のFat Treeは(2,4,2)Fat Treeと表わされる。H−Treeに比して多重化した上位ツリーにより経路分散が可能で、トラフィックの集中が緩和される。既存のNoCへの適応例としてはSPINなどがある。
【0034】
これまで、ツリー型トポロジは、上位のルータ付近のリンクの長さが長くなるため配線遅延の点で不利である、すなわち、Fat Treeでは最上位リンクの配線長が長くなり、このため、リンクの配線長が均一なグリッド型トポロジに比べて、配線遅延やリピータ数、消費電力の点で不利となると考えられてきたが、我々の検討結果、3次元化によってこの弱点を克服できることが分かった。ここでは、Fat Treeおよび後述するFat H−Treeトポロジを用いて3次元NoCに適した配線構造を提案し、チップ面積、配線量、最長配線長、配線遅延、リピータ数、消費電力について評価する。モジュール間の相互接続トポロジとしてルータのリンク数を抑えつつ、一定の高い性能を実現するツリーの多重化を基にする。全体の配線長を短くするために3次元方向のルータ間の配線に貫通ビア等を用いるが、配線が交錯しないように、最上位ランクのルータの周りに次上下位レベルのルータを分散配置する。
【0035】
図2に64コアFat Treeのツリー構造の例を示す。64コアをランク1ルータ(第1ランクルータのこと、以下第nランクルータをランクnルータという)からランク3ルータを介して相互接続する階層構造である。四角の中の数字はルータのランク数である。ランク1ルータとランク2ルータ間の配線及びランク2ルータとランク3ルータ間の配線は2重化されており、ランク1ルータは4コアと2個のランク2ルータに、ランク2ルータは4個のランク1ルータと2個のランク3ルータに、ランク3ルータは4個のランク2ルータに接続される。
【0036】
次に、本発明の他の3次元配線に適用するトポロジであるFat H−Treeについて説明する。Fat H−Treeはレッドツリー(Red Tree)とブラックツリー(Black Tree)と呼ばれる2つのH−Treeを組み合わせたトポロジであり、トーラス構造を内包している。すなわち、Black Treeを介してネットワークの両端のコア(第0行と第7行、第0列と第7列)を結ぶラップアラウンドチャネルを有している。各コアは2つのリンクを有し、1つをRed Treeとの接続に、他の1つをBlack Treeとの接続に用いる。Fat H−TreeはFat Tree より構成が複雑であるが、コスト性能比で優れる。
【0037】
図3に64コアRed Treeのツリー構造の例を示す。丸で描かれた各コアには2次元座標(x,y)がそれぞれ割り当てられる。以降、コアをランク0ルータとも呼ぶ。まず、ランク0ルータに対し式(1)で求まるRed Tree座標R(r0,r1,・・・,ri,・・・,rn−1)を割り当てる。ここで、iはランクを表す。
ri=((x/2i)mod2)+2×((y/2i)mod2) (1)
Red Tree座標R(r0,r1,・・・,rn−1)となるランク0ルータの上位ルータをランク1ルータと呼び、R(r1,・・・,rn−1)のRed Tree座標を割り当てる。同様の方法でランク2ルータからランクnルータにもRed Tree座標を割り当てる。ただし、最上位ランク(ランクn)ルータのRed Tree座標をRとする。また、任意のランクのルータに繋がる次位ランクのルータは4つずつになり、これらのルータに付する符号の順序は左上を0、右上を1、左下を2、右下を3とする。例として図中にランク3ルータR、ランク2ルータR(0)、ランク1ルータR(2,0)、コアR(2,2,0)の位置座標を示す。ここで、R(0)はランク3ルータRにつながる4つのランク2ルータのうち左上のものを表し、R(2,0)はR(0)につながる4つのランク1ルータのうち左下のものを表し、R(2,2,0)はR(2,0)につながる4つのコアのうち左下のものを表す。
【0038】
図4に64コアBlack Treeのツリー構造の例を示す。Black TreeはRed Treeの座標を右方向及び下方向に1コア分ずつずらしたものである。
【0039】
図5にRed Treeの座標とBlack Treeの座標の関係を示す。Red Treeのコア座標RiはBlack Treeのコア座標Biに移る。ルータおよび配線の座標も同様に右方向及び下方向に1コア分ずつずれる。さらに、Black Treeの7行目のコアは8行目、7列目のコアは8列目に移動するが、これを0行目、0列目に移動する。また、第7行7列目のコアは第8行8列目に移動するが、これを第0行0列目に移動する。このずれと移動を循環シフトと称することとする。このためランク0ルータのBlack Tree座標B(b0,b1,・・・,bi,・・・,bn−1)は式(2)で求まる。
bi=((((x−1)mod2n)/2i)mod2)+2×((((y−1)mod2n)/2i)mod2) (2)
Black Treeにおいてもランク1ルータからランクnルータにBlack Tree座標を割り当てる。最上位ランク(ランクn)ルータのBlack Tree座標をBとする。また、任意のランクのルータに繋がる次位ランクのルータは4つずつになり、これらのルータに付する符号の順序は左上を0、右上を1、左下を2、右下を3とする。例として図中にランク3ルータB、ランク2ルータB(2)、ランク1ルータB(1,2)、コアB(0,1,2)の位置座標を示す。ここで、B(2)は4つのランク2ルータのうち左下のものを表し、B(1,2)はB(2)につながる4つのランク1ルータのうち右上のものを表し、B(0,1,2)はR(1,2)につながる4つのコアのうち左上のものを表す。
【0040】
図6に64コアFat H−Treeの2次元レイアウトを示す。各コア(ランク0ルータ)に対し、Red TreeおよびBlack Treeを接続したものをFat H−Treeと称する。Fat H−Treeにおいてはトーラス構造が形成される。すなわち、各コアはRed Treeのランク1ルータおよびBlack Treeのランク1ルータにつながり、コア−Red Treeのランク1ルータ−コア−Black Treeのランク1ルータ−コアの順序でリンクが形成され、第0行目のコアと第7行目のコア、第0列目のコアと第7列目のコアはBlack Treeのランク1ルータを介して接続され、ラップアラウンドチャネルが形成される。
【0041】
図7に畳み込み処理されたFat H−Treeの2次元レイアウトを示す。Fat H−Treeは、トーラス同様、畳み込むことで2次元チップ上に容易にレイアウトできる。畳み込みとは2次元平面の配置の仕方で、例えば行、列の配置を0,7,1,6,2,5,3,4のように並び換えるものである。図6において、配線接続関係を保ちながら、畳み込み処理により再配置したレイアウトが図7に相当し、図6と図7は等価なトポロジである。最上位リンクを除き、Fat H−Treeの各リンクは畳み込みによって配線長が約2倍に延びるが、最上位リンクの配線長は大幅に短縮される。そのため、最上位の次のランクのリンク(第2位リンク)がFat H−Treeの最長配線となる。
【0042】
次にFat Treeの3次元IC向けレイアウトについて説明する。Fat Treeの弱点は、最上位リンク(ランク3ルータとランク2ルータ間の配線)の配線長が長くなることによる配線遅延の増加、リピータ数の増加、およびそれに伴う消費電力の増加である。これらの問題を同時に解決するために、図2で示したFat Treeを半分の寸法から成る4枚のチップに分割し、これらを3次元的に結合する。こうすることで、すべての最上位リンクは距離数十μm程度のチップ間リンクに置き換えられ、配線長の問題は解決される。
【0043】
図8にFat Treeを4分割した例を示す。3−D(2,4,1)Fat Treeの例である。Fat Treeの4分割手順は次のとおりである。
(ステップ1:チップの分割)まず、チップの分割を行う。2次元Fat Treeのコア座標(x2D,y2D)を、次のような3次元座標(x3D,y3D,z3D)に変換する。
x3D=x2Dmod2n−1
y3D=y2Dmod2n−1
z3D=2×(y2D/2n−1)+(x2D/2n−1)
例えば、図2の64コアFat Treeは図8のように4枚の16コアチップに分割される。
(ステップ2:ルータの配置)ルータを各チップに均等に振り分け配置する。図8の例では、各チップは4個のランク1ルータ、2個のランク2ルータ、1個のランク3ルータを有する。
(ステップ3:チップ間配線)他のランクに配置されたルータ同士をチップ間配線でつなぐ。最上位リンクは、マイクロバンプ、無線、貫通ビアなどのチップ間通信技術を用いてチップ面に対して垂直方向に結合される。
(ステップ4:ルータの再配置)垂直方向のチップ間リンク同士が重ならないように、ルータの位置を調整する。図8の例では、チップの中心にランク3ルータを置き、その周囲に他のランクと重ならないように各ランク2ルータを位置をずらして配置している。これにより最上位リンクはチップ間リンクに置き換えられる。結果的に、最上位リンクの1/2の長さの第2位リンクが最長配線となるため、4分割によって最長配線長は1/2に短縮される。この方法は、(2,4,2)Fat Treeなど他の構成のFat Treeに対しても適用できる。
【0044】
次に4分割以外の分割方法について説明する。iを正の整数とするとき、チップの2i分割はチップの4分割と2分割を組み合わせることで実現できる。チップの2分割の場合、2次元のコア座標から3次元座標への変換は次のようになる。
x3D=x2D
y3D=y2Dmod2n−1
z3D=y2D/2n−1
これ以外の点については4分割の場合と同じである。チップ間リンクの距離を無視するとき、最上位リンクの長さは2分割によって、縦方向が1/2になり、横方向がそのままなので3/4に短縮される。
【0045】
次に、Fat H−Treeの3次元IC向けレイアウトについて説明する。Fat H−Treeでは、畳み込みによって第2位リンク(ランク2ルータとランク1ルータ間の配線、図3の配線長の2倍になる)が最長配線となる。この最長配線の長さはFat Treeの最長配線(ランク3ルータとランク2ルータ間の配線、図2参照)の長さと同じであり、配線遅延、リピータ、および消費電力の増加を引き起こす。ここでは、Fat Treeと同様に、これらの問題を3次元化によって解決する。
【0046】
次に、Fat H−Treeの4分割について説明する。Fat H−Treeは2個のH−Treeの他に2−D Torus構造を内包するため、チップの分割後もこの2−D Torus構造が保存されていなければならない。このためFat H−Treeの分割では、チップの分割時にコア座標の転置処理を行う。
【0047】
図9にRed Treeを4分割した例を、図10にBlack Treeを4分割した例を示す。Fat H−Treeの4分割手順は次のとおりである。
(ステップ1:チップの分割)まず、チップの分割を行う。2次元Fat H−Treeのコア座標(x2D,y2D)を、次のような3次元座標(x3D,y3D,z3D)に変換する。
x3D=x2Dmod2n−1 (x2D<2n−1 のとき)
x3D=2n−1−(x2Dmod2n−1) (x2D>=2n−1 のとき)
y3D=y2Dmod2n−1 (y2D< 2n−1 のとき)
y3D=2n−1−(y2Dmod2n−1) (y2D>=2n−1 のとき)
z3D=2×(y2D/2n−1)+(x2D/2n−1)
この処理によって、元のチップはチップの中心を軸に水平方向、および、垂直方向に折り畳まれ4枚のチップに分割される。例えば、図3のRed Treeは図9のように、また、図4のBlack Treeは図10のようにそれぞれ分割される。
(ステップ2:ルータの配置)ルータを各チップに均等に振り分け配置する。この例では、Red Tree(図9参照)およびBlack Tree(図10参照)ともに、各チップに4個のランク1ルータ、1個のランク2ルータを有する。一方、ランク3ルータは、Red Treeはチップ1(第2層目)に、Black Tree はチップ2(第3層目)にそれぞれ1個ずつ有する。
(ステップ3:チップ間配線)他のランクに配置されたルータ同士をチップ間配線でつなぐ。Black Treeでは最上位ルータに加え、ランク1ルータも異なるランクのコア同士をつないでいる。この様子を図10の端部のコアに接続先のチップを表示して示す)。なお、接続されるコア同士は折り畳まれた時に垂直方向に重なり合うこととなる。
(ステップ4:ルータの再配置)必要に応じて行う。ランク2ルータは垂直方向に重ならないので、ここでは再配置を行なわなくても良い。
【0048】
図9および図10のレイアウトを組み合わせたものがFat H−Treeの3次元レイアウトであり、分割後も2−D Torus構造が保存されている。例えば、コアR(1,0,0)の2ホップ先(Red Treeのランク1ルータ−コア−Black Treeのランク1ルータを介する)はコアR(1,1,0)であり、その次はコアR(1,2,0),コアR(1,3,0)と移動した後、チップ2に移り、コアR(1,3、2),コアR(1,2,2),コアR(1,1,2)、コアR(1,0,2)を経て、再びチップ0のコアR(1,0,0)に戻る。図6にこの軌跡を矢印で示す。チップ間を除き2ホップ先へはRed TreeとBlack Tree各1個のランク1ルータを介して配線接続される。またチップ間については、図7を参照するとコアR(1,0,0)とコアR(1,0,2),コアR(1,3,0)とコアR(1,3,2)は垂直方向に重なり、垂直方向の配線で接続されることが分かる。
【0049】
次に、4分割以外の分割方法について説明する。チップの2分割の場合、2次元のコア座標から3次元座標への変換は次のようになる。
x3D=x2D
y3D=y2Dmod2n−1 (y2D<2n−1 のとき)
y3D=2n−1−(y2Dmod2n−1) (y2D>=2n−1 のとき)
z3D=2×(y2D/2n−1)+(x2D/2n−1)
この場合、x方向のリンクは単一チップ内で完結するため、x方向に対してのみ図7のような畳み込みを行う。これ以外の点については4分割の場合と同じである。チップ間リンクの距離を無視するとき、最上位リンクの長さは2分割によって3/4に短縮される。
【0050】
[第1の実施の形態]
第1の実施の形態では、64コア、3階層のFat Treeトポロジの例を説明する。一般的には、4n個のモジュール間を、2ν個の2次元平面を積層した3次元空間に集積化するために、4本または6本の配線を持つ交換接続手段を用いたFat Treeで階層的に接続する。
【0051】
図11に64コア3階層のFat Treeトポロジの例を示す。43=64個のモジュールを3階層に積層した64コアFat Treeトポロジである。最下層の第1のレイヤには64個のコアが存在し、それぞれに電気回路で構成されるモジュールが配置されており、第i行第j列〜第i+1行第j+1列(i,j=0〜14の偶数)内の4個のモジュールを集めて1つの第1レイヤモジュールを構成し、第1レイヤモジュールにはこれら4個のモジュール間を交換接続するランク1ルータ、図中□内に「1」と表示)が配置されている。第1レイヤモジュールは16個存在する。また、ランク1ルータは2つの上位のランク2ルータへのリンクを有し(すなわちルートが2重化されている)、4個のモジュールとこれら2個のランク2ルータとの交換接続も行う。第2のレイヤでは、第i行第j列〜第i+3行第j+3列(i,j=0,4)内の4個の第1レイヤモジュールを集めて1つの第2レイヤモジュールを構成し、第2レイヤモジュールにはこれら4個の第1レイヤモジュール間を交換接続するランク2ルータ(図中□内に「2」と表示)が配置されている。第2レイヤモジュールは8個存在する。また、ランク2ルータは2つの上位のランク3ルータへのリンクを有し(すなわちルートが2重化されている)、4個の第1レイヤモジュールとこれら2個のランク3ルータとの交換接続も行う。第3のレイヤでは、第i行第j列〜第i+7行第j+7列(i,j=0)内の4個の第2レイヤモジュールを集めて1つの第3レイヤモジュールを構成し、第3レイヤモジュールにはこれら4個の第2レイヤモジュール間を交換接続するランク3ルータ(図中□内に「3」と表示)が配置されている。第3レイヤモジュールは4個存在する。このようなツリートポロジを構成することにより、64個のモジュールのうちの任意の2モジュール間の接続が複数ルート(2×2=4)で可能になる。これは特定のルータへのトラフィックの集中を回避するのに役立つ。
【0052】
図12に64コアFat Treeトポロジを4つのチップに分割した構成を示す。各チップは第2レイヤモジュールに対応し、16個のモジュール、4個のランク1ルータ、2個のランク2ルータとこれらの間の配線を含んでいる。2個のランク2ルータがそれぞれ4個のランク1ルータに共に接続されることから、1個のチップには2個の第2レイヤモジュールが重複形成されている。各チップには更に1個のランク3ルータ及び当該ランク3ルータと当該チップに配置された1個のランク2ルータを接続する配線が含まれる。各チップは3次元空間に4層に積層される。異なるチップに存在するランク3ルータとランク2ルータを接続する配線はチップ間を繋ぐ垂直方向配線で接続される。
【0053】
図13に64コアFat Treeトポロジを4つのチップに分割し、4つのチップを積層したときの各ランクのルータ配置とルータ間配線の3次元レイアウトの概要を示す。図13(a)に各チップにおける2次元平面内の各ランクのルータ配置とルータ間配線を、図13(b)に各チップの3次元配置とランク2ルータ、ランク3ルータの配置を示す。図13(a)に示すように、各層のチップにおいて4個のモジュールを2行2列に配置して第1レイヤモジュールが構成され、ランク1ルータは第1レイヤモジュールのほぼ中心に配置され、また、4個の第1レイヤモジュールを2行2列に配置して第2レイヤモジュールが構成され、ランク2ルータは第2レイヤモジュールのほぼ中心に配置される。ランク2ルータと各4個のランク1ルータとはチップ面内の配線により接続される。各チップに第2レイヤモジュールが2重に構成され、4つのチップを積層して第3レイヤモジュールが構成される。第3レイヤモジュールも2重のものが2組合計4つ構成される。また、図13(b)に示すように、最上位のランク3ルータを各チップの2次元平面構造の中心に配置し、ランク2ルータをランク3ルータの隣接周辺に、2次元平面に対して垂直方向に重ならないように配置する。各ランク3ルータから4個のランク2ルータに到る4本の配線のうち、1本は同一層内の1個の隣接するランク2ルータにチップ内で接続され、他の3層のランク2ルータに到る3本は垂直方向配線を4つのチップの中心付近を貫く貫通ビア(最下層は必ずしも貫く必要はない)を通して各層に延び、各層において貫通ビアに隣接する1個のランク2ルータに接続される。例えば、第1層と第3層のランク3ルータは第1層の上、第2層の右上、第3層の右、第4層の右下に隣接配置されたランク2ルータに接続され、第2層と第4層のランク3ルータは第1層の下、第2層の左下、第3層の左、第4層の左上に隣接配置されたランク2ルータに接続される。垂直方向配線は、第1層と第2層間に6本、第2層と第3層間に8本、第3層と第4層間に6本となるが(図12参照)、これらは貫通ビアを通してまとめて配線される。このような配線構造により、モジュールから遠いルータ間の配線長、すなわちランク2ルータとランク3ルータ間の配線長を削減でき、これらの配線における信号の遅延を無視できるようにしている。
【0054】
なお、これまで各ランクのルータを制御する制御手段について言及しなかったが、かかる制御手段を備えるものとし、モジュール間での信号を伝達する配線だけでなく、これらの制御手段と各ランクのルータを接続する制御信号線、さらに電源線についてもチップ間に布設されるものは貫通ビアを通してまとめて配線しても良い。このようにすれば制御線や電源線の遅延も削減できる。
【0055】
図14にFat Treeトポロジの配線レイアウトのアルゴリズムの大略を示す。本実施の形態では64コア(2,4,1)Fat Treeの配線レイアウトについて説明する。まず、ファットツリートポロジを二次元集積電気回路モジュールに相当するチップ対応に分割する(ツリー分割工程:S10)。一般的にはコア数4nのFat Treeでは4n―m分割が可能である。ここでは図11のFat Treeを図12のように4分割する。
【0056】
次にノードのマッピング、すなわち、三次元集積電気回路を二次元平面に展開した状態で、電気回路モジュール(コア)と交換接続手段(ルータ)の配置を行なう(ノードマッピング工程:S20)。一般的には4nのコアとルータを2次元平面に展開し、コアとルータを配置する。ここではまず、n=3であり、コアを2行×2列の4コアずつにわけてランク1ルータをその中心に配置して第1レイヤモジュールを形成する。第1レイヤモジュールは全部で16個になる。次に、2行×2列の4つの第1レイヤモジュールのランク1ルータの中心付近にランク2ルータを配置して第2レイヤモジュールを形成し、ランク2ルータとランク1ルータを配線接続する。4つの第1レイヤモジュールに対してランク2ルータは2つ、すなわち第2レイヤモジュールは2重に形成される。第1レイヤモジュールは全部で8個になる。次に、2行×2列の4つの第2レイヤモジュールのランク2ルータの中心付近にランク3ルータを配置して第3レイヤモジュールを形成する。4つの第2レイヤモジュールに対してランク3ルータは2つ、すなわち第3レイヤモジュールは2重に形成される。第3レイヤモジュールは全部で2重のものが2組合計4個形成される。この平面構成は図2に示される。次に、このように構成されたモジュールの各コアに番号を付する。
【0057】
図15はコアのマッピングと折り畳みを説明するための図である。コアの番号は図15に示すように、第0行目の第0列から第2n−1(=7)列へ、第1行目の第0列から第2n−1(=7)列へ、・・・、第2n−1(=7)行目の第0列から第2n−1(=7)列へ採番する。図15の左側の符号はコアの行を、上側の符号はコアの列を示し、1st〜4thはグループ(層)を示す。さらに、ランク1ルータからランク3ルータに番号を付する。ルータの番号は例えばRed Tree座標R(r1,・・・,rn−1)のように採番する。
【0058】
次にノードマッピング工程で配置された三次元集積電気回路をツリー分割工程で分割した二次元集積電気回路モジュール(チップ)を積層するように折り畳む(折り畳み工程:S30)。一般的には4n―m分割するのでn−m重に折り畳むが、ここではn=3、m=2で、4重に折り畳む。図15の太枠のように全体を4つにグループに分け、各グループに層番号を付する。第3行目と第4行目の間及び第3列目と第4行列目の間に境界線を引くことにより、4つのグループに分けられる。各グループは第2レイヤモジュールに相当し、4×4=16コアを有する。例えば、左下の第1グループを第1層目、左上の第2グループを第2層目、右上の第3グループを第3層目、右下の第4グループを第4層目とする。第1グループは第3行目と第4行目の間の境界線に沿って第2グループの下に折畳み第1層目とする。第3グループは第3列目と第4行列目の間の境界線に沿って第2グループの上に折畳み第3層目とする。第4グループは第3列目と第4行列目の間の境界線に沿って第3グループと共に折畳み、さらに第3行目と第4行目の間の境界線に沿って第3グループの上に折畳み第4層目とする。このように折畳むと、コアの配置は図19(後述する)、ランク1ルータ、ランク2ルータの配置は図13(a)のようになる。ランク2ルータは各チップすなわち各グループの中心付近に2つずつ(2重に)配置される。ランク3ルータは全体に4個(2重×2組)であり、各チップの中心付近に1つずつ配置される。なお、上記境界線を用いて折り畳めばどのように折り畳んでも良い。
【0059】
次に、折り畳み工程で各チップに配置された交換接続手段(ルータ)のうちチップ間に分散された上位ランクの交換接続手段(ルータ)間を垂直方向配線でリンクする(リンク工程:S40)。4チップの中心付近でランク3ルータの近傍に貫通ビアを設け、各チップにおいて垂直方向から見てランク3ルータの周囲にランク2ルータを配置し、ランク3ルータとランク2ルータを配線接続する。各ランク3ルータからは同層の1個のランク2ルータには面内配線で接続され、他の3層のランク2ルータへは垂直配線で接続される。合計12本の垂直配線が1つの貫通ビア内に布設される。この場合に、例えば図13(b)に示すように、8個のランク2ルータが垂直方向に重ならないように配置する。このようにするとランク3ルータから各ランク2ルータへの配線を交錯させずに直線的に形成できる。
【0060】
[第2の実施の形態]
第2の実施の形態では、256コア、4階層のFat Treeトポロジの第1の例を説明する。図11の3階層のFat Treeトポロジを第3レイヤモジュールとし、この第3レイヤモジュールを4層積層して第4レイヤモジュールが構成される。チップは全体で16層積層される。各第3レイヤモジュールにはそれぞれ4個、全体で16個の第3ランクルータがあり、例えば各チップに配置される。8個のランク4ルータが例えば第2層目の第3レイヤモジュールの最上層のチップに4個、第3層目の第3レイヤモジュールの最下層のチップに4個配置され、これらのランク3ルータとランク4ルータは各チップのほぼ中心に配置され、8個のランク4ルータと16個のランク3ルータを接続する配線は、ルータが同一チップ内にある場合は面内配線で隣接接続され、異なるチップ間にある場合は主としてチップ間を繋ぐ垂直方向配線で接続される。
【0061】
図16に16個のランク3ルータと8個のランク4ルータ間の配線のトポロジを示す。それぞれの第3レイヤモジュールには4層のチップが積層されている。さらに第3レイヤモジュールを4層積層して第4レイヤモジュールが構成され、全体で16層のチップが積層されている。ランク3ルータは各チップに配置される。第2層目の第3レイヤモジュールの最上層のチップに配置された4個のランク4ルータのうち、第k番目(k=1〜4)のルータは4個の第3レイヤモジュールの第k層目のチップ(第2レイヤモジュール)に配置されたランク3ルータに配線接続される。第3層目の第3レイヤモジュールの最下層のチップに配置された4個のランク4ルータについても同様に、第k番目(k=1〜4)のルータは4個の第3レイヤモジュールの第k層目のチップ(第2レイヤモジュール)に配置されたランク3ルータに配線接続される。このように、ランク3ルータとランク4ルータ間の配線は二重化されている。
【0062】
図17に各第3レイヤモジュールの3次元配置とランク3ルータ、ランク4ルータの配置の例を示す。ランク3ルータ(図では「3」と表示)とランク4ルータ(図では「4」と表示)を結ぶ垂直方向配線は、それぞれのランク4ルータから上方向へ2本、下方向へ2本で、全体で上下各方向へ16本ずつ(同層への配線を除くと15本ずつ)となり、中央の貫通ビアを通してまとめて配線され、それぞれランク3ルータが配置されたチップに延びて隣接するランク3ルータに接続される。また、各第3レイヤモジュール内でランク2ルータとランク3ルータを結ぶ垂直方向配線は、第3レイヤモジュールの層内を超えて延びることはないので、ランク3ルータはランク4ルータとの垂直方向配線に隣接して設ければ良く、垂直方向に重ならない方が交錯を避け易いが重ねて設けても良い。
【0063】
次に配線レイアウトのアルゴリズムについて述べる。256コア(2,4,1)Fat Treeでは第1の実施の形態に比して1階層大きくなっており、コア及びルータが増えている。ツリー分割工程(S10)では16チップに分割するが、チップ内のレイアウトは第1の実施の形態と同様である。ノードマッピング工程(S20)では256コアのマッピングを第0行第0列から第15行第5列まで行なうが、第1の実施の形態と同様の順序で行なえば良く、ランク1ルータとランク2ルータのマッピングも同様である。ランク3ルータとランク4は垂直方向配線に関わりチップの中央付近に配置される。折り畳み工程(S30)については境界線が第3行目と第4行目の間、第7行目と第8行目の間、第11行目と第12行目の間、第3列目と第4列目の間、第7列目と第8列目の間、第11列目と第12列目の間と縦横共3本ずつになるが、これらを境界線として折り畳めばどのように折り畳んでも良い。リンク工程(S40)については第1の実施の形態にランク3ルータとランク4ルータとの垂直方向配線が加わるが、図17で説明したように行なえば良い。
【0064】
[第3の実施の形態]
第3の実施の形態では、256コア、4階層のFat Treeトポロジの第2の例を説明する。図11の3階層のFat Treeトポロジを第3レイヤモジュールとし、第3レイヤモジュールが1チップ内の2次元平面に構成される。第3のレイヤでは、4個の第2レイヤモジュールが2行2列に配置されて1つの第3レイヤモジュールを構成し、これら4個の第2レイヤモジュール間を交換接続するランク3ルータが第3レイヤモジュールの中心に配置される。1個のチップには4つの第3レイヤモジュールと4個のランク3ルータが存在する。この第3レイヤモジュールを4層積層して第4のレイヤモジュールが構成され、これら4層合計16個の第3レイヤモジュール間を交換接続するランク4ルータが2個ずつ各第3レイヤモジュールの各層すなわち各チップのほぼ中心に配置され、合計8つの第4レイヤモジュールと8個のランク4ルータが存在する。ルータ間の配線の接続関係は第2の実施の形態と同様である。
【0065】
最上位のランク4ルータを各チップの2次元平面構造のほぼ中心に2個ずつ配置し、ランク3ルータをランク4ルータの隣接周辺に4個ずつ配置する。各ランク4ルータから各チップの4個のランク3ルータに到る4本の配線のうち、1本は同一層内の1個の隣接するランク3ルータにチップ内で接続され、他の3層のランク3ルータに到る3本は垂直方向配線を4つのチップの中心付近を貫く貫通ビアを通して各層に延び、各層において貫通ビアに隣接する1個のランク3ルータに接続される。例えば、第1層、第2層、第3層、第4層の第1番目のランク4ルータはそれぞれ各層の上、右上、右下に隣接配置されたランク3ルータ(各4個ずつ)に接続され、第1層、第2層、第3層、第4層の第2番目のランク4ルータはそれぞれ各層の下、左下、左、左上に隣接配置されたランク3ルータ(各4個ずつ)に接続される。垂直方向配線は、第1層と第2層間に6本、第2層と第3層間に8本、第3層と第4層間に6本となるが、これらは貫通ビアを通してまとめて配線される。
【0066】
次に配線レイアウトのアルゴリズムについて述べる。256コア(2,4,1)Fat Treeでは第1の実施の形態に比して1階層大きくなっており、コア及びルータが増えている。ツリー分割工程(S10)では4チップに分割する。このためチップが第1、第2の実施の形態に比して1階層分大きくなっており、第3レイヤモジュール、ランク3ルータまで含む。ノードマッピング工程(S20)は第2の実施の形態と同様である。折り畳み工程(S30)については境界線が第7行目と第8行目の間、第7列目と第8列目の間になり、縦横共1本ずつで第1の実施の形態と同じ本数になり、第1の実施の形態と同様に折り畳むと理解しやすい。なお、これらを境界線として折り畳めばどのように折り畳んでも良い。リンク工程(S40)については第1の実施の形態におけるランク2ルータとランク3ルータとの垂直方向配線の関係を本実施の形態におけるラン3クルータとランク4ルータとの垂直方向配線の関係に代えれば良い。
【0067】
[第4の実施の形態]
本実施の形態では、64コア、3階層のFat H−Treeトポロジの例を説明する。Fat H−TreeトポロジはRed TreeとBlack Treeと呼ばれる2つのH−Treeトポロジを組み合わせたトポロジである。1つのモジュールは2つのリンクを持ち、1つのリンクをRed Treeとの接続に、他の1つのリンクをBlack Treeとの接続に用いる。
【0068】
図3の64コアRed Treeのツリー構造の例を再度参照する。各コア(モジュール)を○で示す。この配線構造は第1の実施の形態で示した図11の64コアFat Treeトポロジを平面展開したもので、モジュールが8×8の行列に配置されている。第3の実施の形態における第3レイヤモジュールの配線構造とほぼ同じであるが、ランク1ルータ以上の配線が多重化されていない点が異なる。第i行第j列〜第i+1行第j+1列(i,j=0〜6の偶数)内の4つのモジュールがランク1ルータに接続されて第1レイヤモジュールを構成し、第i行第j列〜第i+3行第j+3列(i,j=0,4)内の4つの第1レイヤモジュールがランク2ルータに接続されて第2レイヤモジュールを構成し、第i行第j列〜第i+7行第j+7列(i,j=0)内の4つの第2レイヤモジュールがランク3ルータに接続されて第3レイヤモジュールを構成する。
【0069】
図4の64コアBlack Treeのツリー構造の例を再度参照する。各モジュールを○で示す。このモジュールの配置及びモジュール間の配線構造は、図3の64コアRed Treeのモジュールの配置及びモジュール間の配線構造を右方向に1モジュール分、下方向に1モジュール分ずらした構造である。そして、Red Treeの第7行目のモジュールが右方向に1モジュール分ずれたものがBlack Treeの第0行目となり、Red Treeの第7列目のモジュールが下方向に1モジュール分ずれたものがBlack Treeの第0列目となり、Red Treeの第7行第7列目のモジュールがBlack Treeの第0行第0列目のモジュールとなる。すなわち、Black TreeのモジュールはRed Treeのモジュールを右方向及び下方向に1モジュールずつ循環シフトしたものである。Black Treeの各モジュール間の配線接続関係は、モジュールの配置を右方向に1モジュール分、下方向に1モジュール分ずらした場合のRed Treeの各モジュール間の配線接続関係と同じである。すなわち、第i行第j列〜第i+1行第j+1列(i,j=1〜716の奇数)内の4つのモジュールがランク1ルータに接続されて第1レイヤモジュールを構成し、第i行第j列〜第i+3行第j+3列(i,j=1,5)内の4つの第1レイヤモジュールがランク2ルータに接続されて第2レイヤモジュールを構成し、第i行第j列〜第i+7行第j+7列(i,j=1)内の4つの第2レイヤモジュールがランク3ルータに接続されて第3レイヤモジュールを構成する。ただし、これらの行列において7行目に該当するモジュールはBlack Treeでは0行目のモジュールとして配置され、7列目に該当するモジュールはBlack Treeでは0列目のモジュールとして配置され、第7行第7列目に該当するモジュールはBlack Treeでは第0行第0列目のモジュールとして配置される。そして、ランク1ルータは0行目と7行目のモジュール、0列目と7列目のモジュールを配線接続する。
【0070】
図18に64コアFat H−Treeトポロジの例を示す。このモジュールの配置及びモジュール間の配線構造は、図3のRed Treeのモジュールの配置及びモジュール間の配線構造と図4のBlack Treeのモジュールの配置及びモジュール間の配線構造とを合せ持つ構造である。配線が二重化されていることにより、特定のルータへのトラフィックの集中を回避できる。
【0071】
図19に64コアFat H−Treeを4分割した時のRed Treeの3次元レイアウトを示す。これは図3のRed Treeのモジュール配置とモジュール間の配線接続構造を4つのチップに分割した時のレイアウトを示すもので、(a)は第1層目のチップのレイアウト、(b)は第2層目のチップのレイアウト、(c)は第3層目のチップのレイアウト、(d)は第4層目のチップのレイアウトを示す。全体構成は第1の実施の形態における第3レイヤモジュールに相当し、同じく第1の実施の形態における第2レイヤモジュールに相当する4つのチップを4層積層して第3レイヤモジュールを構成する。図3のRed Treeの各モジュールに、第0行目を第0列から第7列へモジュール番号0〜7を、第1行目を第0列から第7列へモジュール番号8〜15を、・・・第7行目を第0列から第7列へモジュール番号56〜63を順番に付与する。第2層目を図3の左上側の第2レイヤモジュールとする。第1層目は図3の左下側の第2レイヤモジュールを第2層目となる左上側の第2レイヤモジュールとの境界線にそってその下側に折畳んだときのモジュール番号の配置となる。第3層目は図3の右上側の第2レイヤモジュールを第2層目となる左上側の第2レイヤモジュールとの境界線にそってその上側に折畳んだときのモジュール番号の配置となる。第4層目は図3の右下側の第2レイヤモジュールを第3層目となる右上側の第2レイヤモジュールと共に第2層目となる左上側の第2レイヤモジュールの上に折畳んだ後にさらに右上側の第2レイヤモジュールとの境界線にそってその上側に折畳んだときのモジュール番号の配置となる。このように4つの第2レイヤモジュールを積層して第3レイヤモジュールを構成する。
【0072】
Red Tree系で第2レイヤモジュールは4つ、第3レイヤモジュールは1つである。ランク2ルータとランク1ルータを接続する配線はチップ内で接続され、ランク3ルータとランク2ルータを接続する配線は主としてチップ間を繋ぐ垂直方向配線で接続される(同層内では面内配線接続される)。ランク3ルータはRed Tree系では第3層目の第2レイヤモジュールを搭載するチップの中央に配置される。これらの配線構造は第1の実施の形態におけるFat Treeトポロジとほぼ同じであるが、ランク2ルータが二重化されず各チップに1個、合計4個である点、ランク3ルータが上記のように合計1個である点と、これらに伴い、これらランク3ルータとラン2クルータを繋ぐ配線の本数が異なる。
【0073】
図20に64コアFat H−Treeを4分割した時のBlack Treeの3次元レイアウトを示す。これは図4のBlack Treeのモジュール配置とモジュール間の配線接続構造を4つのチップに分割した時のレイアウトを示すもので、(a)は第1層目のチップのレイアウト、(b)は第2層目のチップのレイアウト、(c)は第3層目のチップのレイアウト、(d)は第4層目のチップのレイアウトを示す。4つのチップの積層の仕方は図19のRed Treeと同じであり、したがって、各層のチップのモジュールの配置は図19のRed Treeと同様であり、そして配線接続構造は図4のモジュール間の配線接続構造を採用している。
【0074】
この結果、例えば、第1層目のチップでは、Red Treeの場合に比して第1レイヤモジュール、第2レイヤモジュールが上方向及び右方向にそれぞれ1モジュール分ずれ、ランク1ルータ、ランク2ルータも上方向及び右方向にそれぞれ1モジュール分ずれる。そして、4つのモジュール41,42,49,50からなる第1レイヤモジュールは第1層目のチップ内に存在するが、4つのモジュール43,44,51,52からなる第1レイヤモジュールは第1層目に43,51、第4層目に44,52と2層のチップにまたがり、ランク1ルータからこれらのモジュールを接続する配線は2つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第1層目と第4層目で垂直方向に重なった位置にあり、1束の垂直方向配線で接続可能である。また、4つのモジュール1,2,57,58からなる第1レイヤモジュールは第1層目に57,58、第2層目に1,2と2層のチップにまたがり、ランク1ルータからこれらのモジュールを接続する配線は2つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第1層目と第2層目で垂直方向に重なった位置にあり、1束の垂直方向配線で接続可能である。また、4つのモジュール3,4,59,60からなる第1レイヤモジュールは第1層目に59,第2層目に3、第3層目に4,第4層目に60と4層のチップにまたがり、ランク1ルータからこれらのモジュールを接続する配線は4つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第1層目から第4層目まで垂直方向に重なった位置にあり、1束の垂直方向配線で接続可能である。このような垂直方向配線も貫通ビアを使用できる。
【0075】
また、第2層目のチップでは、Red Treeの場合に比して第1レイヤモジュール、第2レイヤモジュールが下方向及び右方向にそれぞれ1モジュール分ずれ、ランク1ルータ、ランク2ルータも下方向及び右方向にそれぞれ1モジュール分ずれ、配線についても第1層目と類似の関係が存在する。また、第3層目のチップでは、Red Treeの場合に比して第1レイヤモジュール、第2レイヤモジュールが下方向及び左方向にそれぞれ1モジュール分ずれ、ランク1ルータ、ランク2ルータも下方向及び左方向にそれぞれ1モジュール分ずれ、配線についても第1層目と類似の関係が存在する。また、第4層目のチップでは、Red Treeの場合に比して第1レイヤモジュール、第2レイヤモジュールが上方向及び左方向にそれぞれ1モジュール分ずれ、ランク1ルータ、ランク2ルータも上方向及び左方向にそれぞれ1モジュール分ずれ、配線についても第1層目と類似の関係が存在する。なお、図20中の端部にある各ランク1ルータには接続されるモジュールの番号と( )内にそのモジュールが存在する層を示している。
【0076】
Black Tree系では、第2レイヤモジュールは4つ、第3レイヤモジュールは1つであり、ランク2ルータが各チップに1個、合計4個、ランク3ルータが合計1個である点はRed Treeの場合と同様であるが、ランク2ルータとランク3ルータの位置が異なる。各第2レイヤモジュールにおいて4つのランク1ルータに接続するランク2ルータは4つのランク1ルータの中央付近に配置され、ランク1ルータとランク2ルータを接続する配線は面内に布設される。また、第3レイヤモジュールにおいて4つのランク2ルータに接続するランク3ルータは第3層目のチップの中央に配置され、ランク2ルータとランク3ルータを接続する配線はチップ間では垂直方向配線となり、貫通ビア内にまとめて布設され、各チップ内で貫通ビアからランク2ルータまで面内配線で繋がれる。
【0077】
Fat H−TreeトポロジはRed TreeとBlack Treeと呼ばれる2つのH−Treeトポロジを組み合わせたトポロジである。したがって、その配線構造は両者の配線構造を合わせ持つ。しかし、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク2ルータとランク3ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。
【0078】
Fat H−Treeトポロジの配線レイアウトのアルゴリズムも大略は図14で表されるが、細部はFat Treeトポロジの場合と異なる。本実施の形態では64コア3階層Fat H−Treeのツリー構造配線レイアウトについて説明する。まず、ファットエイチツリートポロジを二次元集積電気回路モジュールに相当するチップ対応に分割する(ツリー分割工程:S10)。ここでは4分割する。
【0079】
次に三次元集積電気回路を二次元平面に展開した状態で、電気回路モジュール(コア)と交換接続手段(ルータ)の配置を行なう(ノードマッピング工程:S20)。コアの配置はFat Treeの場合と同様である。他方、ルータの配置はRed TreeではFat Treeの場合と同様であるが、Black TreeではFat Treeに対し1モジュール分下方及び右側に循環シフトしている。また、Red Tree内、Black Tree内では配線の多重化はされていない。
【0080】
次にノードマッピング工程で配置された三次元集積電気回路をツリー分割工程で分割した二次元集積電気回路モジュール(チップ)を積層するように折り畳む(折り畳み工程:S30)。折り畳み方はFat Treeの場合と同様である。従って、コアの配置はFat Treeの場合と同様である。他方、ルータの配置は図20に示すように、Red TreeではFat Treeの場合と同様であるが、Black TreeではFat Treeに対し1モジュール分、第1層目が右上に、第2層目が右下に、第3層目が左下に、第4層目が左上にシフトしている。また、第1レイヤモジュールが層間に亘るものがある。ランク2ルータは各チップにRed Treeで1つ、Black Treeで1つ、全体で8つである。ランク3ルータはRed Treeで第2層目中心に1つ、Black Treeで第3層目中心に1つ、全体で2つである。
【0081】
次に、折り畳み工程で各チップに配置された交換接続手段(ルータ)のうちチップ間に分散された上位ランクの交換接続手段(ルータ)間を垂直方向配線でリンクする(リンク工程:S40)。4チップの中心に貫通ビアを設け、各チップにおいて垂直方向から見てランク3ルータの周囲にランク2ルータを配置し、ランク3ルータとランク2ルータを配線接続する。2つのランク3ルータからは、それぞれ同層の1つランク2ルータには面内配線で接続され、他の3層のランク2ルータへは垂直方向配線で接続される。合計6本の垂直方向配線が1つの貫通ビア内に布設される。この場合に、例えば図17に示すように、8つのランク2ルータが垂直方向に重ならないように配置する。このようにするとランク3ルータから各ランク2ルータへの配線を交錯させずに直線的に形成できる。また、Black Tree内ではチップのエッジ部分においてラン13ルータとモジュールを接続するための8束の垂直方向配線が設けられる(図20参照)。
【0082】
[第5の実施の形態]
以上の実施形態では4分割Fat Treeトポロジの例を説明したが、第5の実施の形態では2分割Fat H−Treeトポロジの例について説明する。ここでは、64コア3階層のFat H−Treeトポロジを32コア2チップに分割する例を説明する。
【0083】
図21に、64コアFat H−Treeを2分割した時のRed Treeの3次元レイアウトの例を示す。図21(a)は第1層目のチップのレイアウト、図21(b)は第2層目のチップのレイアウトを示す。第1層目は図19における第1層目と第4層目のモジュールを合せて配置を変更したものであり、第2層目のモジュールは図19における第2層目と第3層目のモジュールを合せて配置を変更したものである。2分割の場合、横方向には分割しないので、横方向のモジュールの配置は初めから固定される。本実施の形態では第1層目は左から56,63,57,62,58,61,59,60の順序、第2層目は左から0,7,1,6,2,5,3,4の順序であり、この配置は図7のモジュールの配置と同様であり、図6の配置すなわち図19の配置と等価である。縦方向のモジュールの配置は図19の配置と同様である。ランク1ルータとモジュールを接続する配線の関係、ランク2ルータとランク1ルータを接続する配線の関係は第4の実施の形態と同様であり、このため、ランク1ルータの位置は横方向では第0行目と第1行目の間、第2行目と第3行目の間で、縦方向では第1、2、5,6列目の中央となり、ランク2ルータの位置はチップの中央付近となる。これらの配線はチップ内で接続される。ランク2ルータは二重化されず各チップに2個、合計4個である。ランク3ルータは全体に1個で第1層目のチップの中央となり、ランク3ルータから4個のランク2ルータを接続する4本の配線のうち、2本は同一層内の隣接するランク2ルータにチップ内で接続され、他の層のランク2ルータに到る2本はチップ間を繋ぐ垂直方向配線で接続される。なお、図21では各モジュールを正方形で示しているが、縦横比を2:1にするとチップは正方形となり、既存の製造ラインに適合するので好適である。
【0084】
図22に、64コアFat H−Treeを2分割した時のBlack Treeの3次元レイアウトの例を示す。図22(a)は第1層目のチップのレイアウト、図22(b)は第2層目のチップのレイアウトを示す。第1層目は図20における第1層目と第4層目のモジュールを合せて配置を変更したものであり、第2層目のモジュールは図20における第2層目と第3層目のモジュールを合せて配置を変更したものである。横方向のモジュールの配置は初めから固定され、第1層目は左から56,63,57,62,58,61,59,60の順序、第2層目は左から0,7,1,6,2,5,3,4の順序である。縦方向のモジュールの配置は図20の配置と同様である。ランク1ルータとモジュールを接続する配線の関係、ランク2ルータとランク1ルータを接続する配線の関係は第4の実施の形態と同様であり、このため、第1層目において、ランク1ルータの位置は横方向では第0行目の上端、第1行目と第2行目の間で、縦方向では第0列目と第1列目の間、第3列目の中央、第4列目の中央、第6列目と第7列目の間となり、ランク2ルータの位置は横方向では第2列目の右から1/4モジュールの位置、第5列目の左から1/4モジュールの位置、縦方向では第0行目と第1行目の間となる。第2層目において、ランク1ルータの位置は横方向では第1行目と第2行目の間、第3行目の下端で、縦方向では第0列目と第1列目の間、第3列目の中央、第4列目の中央、第6列目と第7列目の間となり、ランク2ルータの位置は横方向では第2列目の右から1/4モジュールの位置、第5列目の左から1/4モジュールの位置、縦方向では第第2行目と第3行目の間となる。
【0085】
4つのモジュール40,47,48,55からなる第1レイヤモジュールなどの4つの第1レイヤモジュールは第1層目のチップ内に存在し、4つのモジュール8,15,16,23からなる第1レイヤモジュールなどの4つの第1レイヤモジュールは第2層目のチップ内に存在するが、4つのモジュール0,7,56,63からなる第1レイヤモジュールは第1層目に56,63、第2層目に0,7と2層のチップにまたがり、4つのモジュール1,2,57,58からなる第1レイヤモジュールなどの他の7つの第1レイヤモジュールも2層のチップにまたがり、ランク1ルータからこれらのモジュールを接続する配線は2つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第1層目と第2層目で垂直方向に重なった位置にあり、それぞれ1束の垂直方向配線で接続可能である。このような垂直方向配線も貫通ビアを使用できる。ランク2ルータは二重化されず各チップに2個、合計4個であり、ランク2ルータとランク1ルータを接続する配線はチップ内で接続される。ランク3ルータは全体に1個で第3層目のチップの中央となり、ランク3ルータから4個のランク2ルータを接続する4本の配線のうち、2本は同一層内のランク2ルータにチップ内で接続され、他の層のランク2ルータに到る2本はチップ間を繋ぐ垂直方向配線で他のチップに到り、そのチップ内でランク2ルータの位置まで延びる。なお、図22では各モジュールを正方形で示しているが、縦横比を2:1にするとチップは正方形となり、既存の製造ラインに適合するので好適である。
【0086】
Fat H−TreeトポロジはRed TreeとBlack Treeと呼ばれる2つのH−Treeトポロジを組み合わせたトポロジである。したがって、その配線構造は両者の配線構造を合わせ持つ。しかし、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク2ルータとランク3ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。なお、上記の説明は2分割Fat H−Treeトポロジの例であるが、2分割Fat Treeトポロジについても2分割Red Treeのランク1ルータからランク2ルータへの配線を二重化し、さらにランク2ルータからランク3ルータへの配線を二重化することにより実現可能であり、同様に、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク2ルータとランク3ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。
【0087】
次に2分割Fat H−Treeトポロジの配線レイアウトのアルゴリズムについて述べる。第4の実施の形態に比して階層は同じで、チップ数が半分になっている。ツリー分割工程(S10)では2チップに分割する。ノードマッピング工程(S20)は第4の実施の形態とほぼ同様であるが、レッドツリー系のランク2ルータはチップの中心付近に配置される。折り畳み工程(S30)については境界線が第3行目と第4行目の間の1本のみになる。リンク工程(S40)についてはランク2ルータとランク3ルータ間のリンクを2チップ間で行なうが、第4の実施の形態と同様にBlack Tree系ではランク2ルータの位置がシフトしており、また、第1レイヤモジュールが層間に亘るものがある。ランク2ルータは各チップにRed Treeで2つ、Black Treeで2つ、全体で8つである。ランク3ルータはRed Treeで第1層目中心に1つ、Black Treeで第2層目中心に1つ、全体で2つである。
【0088】
[第6の実施の形態]
以上の実施形態では二次元集積電気回路モジュール間の配線が貫通ビアを通して構成される例について説明したが、第6の実施の形態では二次元集積電気回路モジュール間の配線に無線配線を用いる例を説明する。例えば第1の実施の形態の配線構造において、貫通ビアを通る垂直方向配線に代えて無線通信で信号を伝達する。モジュール間での信号を伝達する配線だけでなく、各ランクのルータを制御する制御信号線、電源線についても無線配線で置換しても良い。この場合、チップすなわち二次元集積電気回路モジュールの二次元平面に垂直な方向にほぼ直線上に並べて無線送受信手段が配置される。チップ間の通信を行なうランク2ルータ及びランク3ルータに無線送受信手段として例えば各1個の無線送受信回路を用いても良く、各1個の無線送信回路及び無線受信回路を用いても良い。また、これら送信回路又は受信回路としてインダクターなどの電磁結合や容量結合を用いても良い。無線送受信手段を二次元平面に垂直な方向にほぼ直線上に並べるのは、チップ間で良好な無線通信が可能な送信手段と受信手段間の距離がμmオーダーの範囲では可能なのに対し、mmオーダー以上では困難だからである。したがって、チップ間配線に無線配線を用いる場合にも、モジュール、各ランクのルータの配置及びこれらの間の配線構造について、貫通ビアの場合と同じアルゴリズムを適用できる。また、配線レイアウトのアルゴリズムは第1の実施の形態の貫通ビアを無線配線に代えれば良い。
【0089】
なお、上記の説明は第1の実施の形態に無線配線を適用する例であるが、第2〜第5の実施の形態にも同様に無線配線を適用可能である。
【0090】
[評価]
次に、以上の実施の形態で説明した3−D Fat Tree および3−D Fat H−Treeについて、チップ面積,配線量,配線遅延,リピータ数,消費電力について評価する。これらの3次元レイアウトは2γ枚のチップ上に実現できるが,ここでは積層するチップ数を4層として評価する。
【0091】
(1)ルータのリンク数と個数
表1に、3−D Fat Treeおよび3−D Fat H−Treeトポロジで必要となるルータの個数を見積もった結果を示す。比較のため3−D Meshと3−D Torusの結果も示す。Fat H−Treeをはじめツリー系のトポロジでは3−D Meshや3−D Torusに比べてルータの数が少ない。また、表には示されていないが、ルータの最大リンク数はH−TreeとFat H−Treeで5個,Fat Treeで6個であるのに対し,3−D Meshと3−D Torusでは7個(xyz各方向に2個ずつに、(ローカル)コア(プロセッシングエレメント)へのリンクを含めて7個とした)となり、ルータ1個当たりの面積でもツリー系トポロジのほうが有利である。ただし,(2,4,2)Fat TreeとFat H−Treeでは各コアは2本のリンクを有するため、他のトポロジと比べネットワークインターフェイス(NI)の面積が増加する。
【0092】
【表1】
【0093】
(2)ルータとネットワークインターフェイス(NI)の面積
表2に3−D Fat Treeおよび3−D Fat H−Treeトポロジにおける、オンチップルータとNIからなる部分の面積(mm2)を示す。比較のため3−D Meshと3−D Torusにおける同部分の面積も示す。
【表2】
【0094】
なお、カッコ内の数字は2次元レイアウトからの増分を示すものである。この数字はツリー型トポロジでは貫通ビアのみの面積を表し、MeshやTorusでは3次元化に伴うルータ面積の増分と貫通ビアの面積を表す。この結果より、ツリー型トポロジでは、3次元化のための貫通ビアによって総面積が最大5.0%増加しているのに対し、MeshとTorusでは3次元化によってルータのリンク数が増えるため、面積がMeshで最大21.5%、Torusで最大47.3%増加しており、3次元化のオーバーヘッドが非常に大きいことが分かる。
【0095】
各トポロジの面積は次の手順で見積もった。(1)まず、Verilog−HDL(Hardware Description Language)で記述されたルータ回路とNI回路を組み合わせ対象トポロジを構築した。(2)次に、これを0.18μmスタンダードセルライブラリを用いてSynopsys社のDesign Compilerで合成することでNoCの面積を抽出した。(3)次に、各トポロジに含まれるチップ間リンクの数から貫通ビアの面積を計算し、NoCの面積に足し合わせた。ここにおいて、ルータ回路は4段のパイプラインステージから構成され,パイプラインステージごとに1−フリット(flit)分のリピータを有し、NI回路として2−flit分のFIFO(First In, First Out)を入力側と出力側にそれぞれ有するものとした。また、Fat H−Treeと(2,4,2)Fat Treeでは2ポートのNIが必要になる。とくにFat H−Treeでは,片方のポートからもう片方のポートへパケットを転送する機能が必要であり、このためにNI内に小さなマルチプレクサが実装されているものとした。貫通ビアのサイズはチップを重ね合わせるときのアライメントの精度によって制限され、一般的には1μm角〜10μm角となる。ここでは、1−ビット(bit)の単方向チップ間リンクが1枚のチップを貫通する度に、貫通ビアの面積として100μm2を加算した。
【0096】
(3)総配線長
表3にFat Tree及びFat H−Treeについて、2次元レイアウトにおける総配線長を示す。比較のため2−D Meshと2−D Torusにおける総配線長も示す。ここで、隣接コア間距離を1−ユニット(unit)とし、配線長をユニット数で表す。
【表3】
【0097】
階層数nのH−Treeの2次元レイアウトにおける総配線長L2D,htを式(3)で表す。
【数1】
ただし,lihtをH−Treeにおけるランクiルータからその4個の下位ルータへの総リンク長,rihtをランクiルータの数とする。コア数をN=2n×2nとすると、liht=2i+1,riht=N/4iとなる。したがって,式(3)は式(4)のように変形できる。
【数2】
同様にして,階層数nのFat H−Tree の2次元レイアウトにおける総配線長L2D,fhtを求める式は式(5)のように導びかれる。
【数3】
表3の見積りではMesh及びTorusのコア−ルータ間リンクの長さを無視しているものの、Fat H−Treeや(2,4,2)Fat Treeなどツリー型トポロジの総配線長が圧倒的に長く、これがツリー型トポロジの欠点になっていることが分かる。
【0098】
表4にFat Tree及びFat H−Treeについて、3次元レイアウトの総配線長L3D,htを示す。比較のため3−D Meshと3−D Torusにおける総配線長も示す。ここで、隣接コア間距離を1−unitとし、配線長をユニット数で表す。
【表4】
【0099】
3次元レイアウトではチップ間の距離は数十μm程度と、水平方向のリンク長に比べて圧倒的に短い。そのため、ここではチップ間リンクの長さは考慮しないものとする。まず、階層数nのH−Treeを3次元化したときの総配線長L3D,htを求める。チップの枚数は4枚なので、すべての最上位リンクが長さ0のチップ間リンクに置き換えられることになる。したがって、式(4)は3次元化によって式(6)のように変化する。
【数4】
【0100】
Fat H−Treeの場合はRed TreeとBlack Treeに分けて考える。Red TreeはH−Treeの3次元レイアウトと等価である(図9参照)。一方、Black Treeはこれに加え、最上位リンクの長さとしてそれぞれ2−unit必要となる(図10参照)。よって総配線長は式(7)のようになる。
【数5】
表4と表3を比較することにより、総配線長が3次元化によってどれだけ削減できるかが分かる。Fat TreeおよびFat H−Treeでは、3次元化によって総配線長が25.0%から最大50.0%削減できた。その結果、総配線長は、(2,4,2)Fat Treeを除き、3−D Torusと同程度かそれ以下に削減された。
【0101】
(4)消費電力
1−flitのデータを送信元から宛先ノードに転送するのに要する平均転送エネルギーは式(8)で計算できる。
Eflit=wHave(Esw+Elink) (8)
ただし、wを1−flitのビット数、Haveを平均ホップ数、Eswをルータが1−bitのデータ転送に消費するエネルギー、Elinkをリンクが1−bitのデータ転送に消費するエネルギーとする。(2)のルータとNIの面積において見積もったルータを、250MHzでの動作を仮定してゲートレベルでシミュレーションしたところ、Eswは1.13pJとなった。
【0102】
一方,Elinkは式(9)で計算できる。
Elink=dV2Cwire/2 (9)
ただし、dを1−hop当たりの平均距離(mm)、Vを動作電圧、Cwireを配線容量とする。ここではVを1.8Vとし、Cwireは0.18μmプロセスを仮定するとき414fF/mmとなった。チップサイズは12mm角とし、16コア、64コア、256コアの場合について、上記のパラメータをもとに転送エネルギーEflitを計算した。
【0103】
表5にリピータを挿入しないときの2次元レイアウトにおける1−flit当りの転送エネルギーEflit(pJ)を示す。
【表5】
【0104】
Fat H−Treeは畳み込みによって1−hop当たりの平均距離dが延びたが、平均ホップ数はこの中で最も小さく、消費電力においても有利となった。H−TreeやFat Treeはその次に平均ホップ数が小さいが、最上位リンクの利用率が高いため転送エネルギーはFat H−Treeよりも大きくなった。2−D Torusは畳み込みによって1−hop当たりの平均距離dが延びるため16コアでは2−D Meshより転送エネルギーが多い。一方,256コアではEswのウェイトが高くなり、平均ホップ数の小さい2−D Torusは2−D Meshより有利になっている。
【0105】
チップサイズが12mm角のとき、ツリー型トポロジにおける最長配線長はコア数によらず常に6mmである。このときの配線遅延は715psecとなり、プロセスの微細化に伴いさらに深刻化すると考えられる。そこで、マイ達の計算式(Ho,R.,Mai,K.W.and Horowitz,M.A.:The Future of Wires,Proceedings of the IEEE,Vol.89,No.4, pp.490−504 (2001)参照)に基づきリピータを挿入し、配線遅延を441psecまで抑えることができたが、新たにリピータの消費電力を考慮する必要が生じた。
【0106】
表6にリピータを挿入したときの2次元レイアウトにおける1−flit当り転送エネルギーEflit(pJ)を示す。リピータは5mm以上のリンクに挿入するものとして計算した。
【表6】
【0107】
上記マイ達の文献の図10によれば、4mm以下の配線にリピータを挿入しても配線遅延の消費効果が小さいことが分かる。そこで消費電力の増加を少しでも抑えるため、リピータの挿入は5mm以上のリンクに制限した。
【0108】
ツリー系のトポロジの最長リンクには平均4.9個のリピータが挿入されたため,リピータを挿入しない表5と比べ、転送エネルギーが大幅に増加した。また、16コアの2−D Torusにおいては畳み込みにより一部のルータ−ルータ間リンクが5mmを越えたため、ツリー型トポロジと同様に転送エネルギーEflitが増加した。
【0109】
次に、3次元レイアウトにおける転送エネルギーEflitを計算する。非特許文献2によると貫通ビアの容量は4.34fFであり、本評価で仮定している配線10.5μm分の容量に相当し、水平方向の配線長に比べて十分小さい。そのためチップ間リンクで消費されるエネルギーは考慮しないものとする。
【0110】
表7に3次元レイアウトにおける転送エネルギーEflit(pJ)を示す。
【表7】
【0111】
3次元化レイアウトでは、どのトポロジにおいても5mmを越えるリンクが発生しなかったためリピータは不要となった。Fat Treeの転送エネルギーEflitは表5と比べて最大44.3%、表6と比べて最大59.7%削減された。同様にFat H−Treeの転送エネルギーEflitは表5と比べて最大32.8%、表6と比べて最大53.5%削減された。このように3次元化により、配線長およびリピータを減らすことができ、結果的に転送エネルギーを大幅に減らすことができた。
【0112】
以上説明したように、Fat Tree およびFat H−Treeの3次元レイアウトは、同サイズの2次元レイアウトに比べ、(1)配線長は25.0%から最大50.0%削減された、(2)配線遅延が小さくなり、挿入されるリピータ数を削減できた、(3)これにより、1フリット当りの転送エネツギーが最大59.7%削減された。なお、3次元化によってチップ面積が最大5.0%増加したが、メッシュの3次元化に比して十分低コストになっている。このように、本発明によれば、複数のモジュール間を接続する集積電気回路の配線構造において、適正なトポロジで3次元構造を実現することにより、2次元構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することができる。
【0113】
以上、本発明の実施の形態について説明したが、本発明は以上の実施の形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で実施の形態に種々変更を加えられることは明白である。
【0114】
例えば、以上の実施の形態では、三次元集積電気回路の配線構造に64コア又は256コアのFat Treeトポロジ、64コアのFat H−Treeトポロジを適用する例について説明したが、他の4nコア、2ν層のFat Treeトポロジ、Fat H−Treeトポロジにも適用可能であり、ルータの上向きリンク数p、ルータの下向きリンク数q、コアの上向きリンク数cの組み合わせについても特に制限はない。また、第1の実施の形態以外でも、交換接続手段を制御する制御信号線や電源線についてもチップ間に布設されるものは貫通ビア内に配置する構成としても良い。このように構成すると、制御系配線についても配線長を低減し、モジュール間の通信遅延を低減できる。また、以上の実施の形態では交換接続手段がルータである場合について説明したが、交換接続手段がクロスバスイッチ等の交換機のスイッチの場合についても同様に適用できる。また、以上の実施の形態では貫通ビアや無線配線が1箇所の例を主に説明したが、貫通ビアや無線配線を複数箇所に設けても良く、また、貫通ビアと無線配線とを併用しても良い。また、各電気回路領域は同一寸法の正方形又は長方形に限定されず、正三角形、正六角形や台形等の平面に隙間なく敷き詰められる形状であれば望ましいが、円形等隙間が生じる構造についても、Fat Treeトポロジ、Fat H−Treeトポロジを適用可能である。
【産業上の利用可能性】
【0115】
本発明はLSI、IC等の3次元配線に利用できる。
【図面の簡単な説明】
【0116】
【図1】リンク数が小さく対称な2次元レイアウトが可能なトポロジの代表例を示す図である。
【図2】64コアFat Treeのツリー構造の例を示す図である。
【図3】64コアRed Treeのツリー構造の例を示す図である。
【図4】64コアBlack Treeのツリー構造の例を示す図である。
【図5】Red Treeの座標とBlack Treeの座標の関係を示す図である。
【図6】64コアFat H−Treeの2次元レイアウトを示す図である。
【図7】畳み込み処理されたFat H−Treeの2次元レイアウトを示す図である。
【図8】Fat Treeを4分割した例を示す図である。
【図9】Red Treeを4分割した例を示す図である。
【図10】Black Treeを4分割した例を示す図である。
【図11】64コア3階層のFat Treeトポロジの例を示す図である。
【図12】64コアFat Treeトポロジを4つのチップに分割した構成を示す図である。
【図13】64コアFat Treeトポロジを4つのチップに分割し、積層したときの各ランクルータ配置とルータ間配線の3次元レイアウトの概要を示す図である。
【図14】Fat Treeトポロジ及びFat H−Treeの配線レイアウトのアルゴリズムの大略を示す図である。
【図15】コアのマッピングと折り畳みを説明するための図である。
【図16】16個のランク3ルータと8個のランク4ルータ間の配線のトポロジを示す図である。
【図17】各第3レイヤモジュールの3次元配置とランク3ルータ、ランク4ルータの配置の例を示す図である。
【図18】64コアFat H−Treeトポロジの例を示す図である。
【図19】64コアFat H−Treeを4分割した時のRed Treeの3次元レイアウトを示す図である。
【図20】64コアFat H−Treeを4分割した時のBlack Treeの3次元レイアウトを示す図である。
【図21】64コアFat H−Treeを2分割した時のRed Treeの3次元レイアウトの例を示す図である。
【図22】64コアFat H−Treeを2分割した時のBlack Treeの3次元レイアウトの例を示す図である。
【図23】2次元ICと3次元ICの比較を示す図である。
【符号の説明】
【0117】
i(i=1〜3) ランクiルータ
bi Black Treeのランクiルータの座標
B(b0,b1,…,bi,…,bn) Black Treeのルータの座標
(p,q,c) Fat Treeのリンク構成
p ルータの上向きリンク数
q ルータの下向きリンク数
c コアの上向きリンク数
ri Red Treeのランクiルータの座標
R(r0,r1,…,ri,…,rn) Red Treeのルータの座標
x2D,y2D,z2D コアの2次元座標
x3D,y3D,z3D コアの3次元座標
【技術分野】
【0001】
本発明は三次元集積電気回路の配線構造及びそのレイアウト方法に関する。詳しくは、ツリー型のトポロジについて、垂直方向配線を用いて配線長を削減し、配線遅延を短縮可能とする三次元集積電気回路の配線構造及びそのレイアウト方法に関する。
【背景技術】
【0002】
半導体技術の進歩により、単一チップ上にプロセッサやメモリ、入出力(I/O)インタフェースなど複数の設計モジュールをタイル状に実装できるようになった。このようなタイルアーキテクチャでは、タイルだけでなくタイル同士を結合するための配線ネットワークを含めてチップ上に(主として2次元チップ上に)構成するチップ上ネットワーク(Network−on−Chip、略してNoCという。)トポロジが用いられ、そのネットワークトポロジはアプリケーションの性能と面積、消費電力を決定付ける一要素となっている。(非特許文献1参照)
【0003】
近年注目を浴びているのが、チップの3次元化である。3次元集積回路(IC)は複数枚のウエハまたはダイを垂直方向に重ね合わせることで実現される。複数枚のチップを垂直方向に積み重ねることで、個々のチップの寸法を小さく抑えることができ、結果的に配線長および配線遅延を削減できる。(非特許文献2〜4参照)
【0004】
図23に2次元ICと3次元ICの比較を示す。図23(a)は通常の2次元ICを、図23(b)はそれと同面積の3次元ICを示す。この3次元ICでは4枚のチップを積層することにより、個々のチップの面積は1/4、チップの両端を結ぶ配線長は1/2に削減される。これに伴い配線遅延及び必要なリピータの数も削減される。
【0005】
通常の2次元ICにおいては2−Dメッシュ(Mesh)や2−Dトーラス(Torus)などのグリッド型のトポロジが広く用いられている。3次元ICを想定したNoCの研究はまだ数が少ないが、3−D Meshや3−D Torusをベースにしたものがいくつか報告されている。これらは、通常の2次元NoCで広く用いられる2−D Meshや2−D Torusから容易に拡張できるという利点を持つ。
【0006】
【非特許文献1】Dally,W.J.and Towles,B.:Route Packets,Not Wires:On−Chip Interconnection Networks,Proceedings of the 38th Design Automation Conference,pp. 684−689 (2001)
【非特許文献2】Davis,W.R.,Wilson,J.,Mick,S.,Xu,J.,Hua,H.,Mineo,C.,Sule,A.M.,Steer,M.and Franzon,P.D.:Demystifying 3D ICs:The Pros and Cons of Going Vertical,IEEE Design & Test of Computers,Vol.22,No.6,pp.498−510 (2005)
【非特許文献3】Li,F.and et.al.:Design and Management of 3D Chip Multiprocessors Using Network−in−Memory,Proceedings of the International Symposium on Computer Architecture,pp.130−141 (2006)
【非特許文献4】Das,S.and et.al.:Technology,Performance,and Computer Aided Design of Three−Demensional Integrated Circuits,Proceedings of the International Symposium on Physical Design,pp.108−115 (2004)
【発明の開示】
【発明が解決しようとする課題】
【0007】
しかし、3−D Meshでは2−D Meshと比べ、オンチップルータのリンク数が4から6に増え、これに伴いオンチップルータのチャネルバッファおよびクロスバスイッチの面積が増加する、また、垂直方向のリンクは数十μm程度と非常に短いため、パケットが垂直方向に移動する度にルータでラッチする必要はない、すなわちラッチにより電力が余分に消費され遅延も生じるという欠点が指摘されており、ルータのハードウェア量の割りに得られるメリットは大きくない。
【0008】
他方、ツリー型トポロジについては、上位リンクの配線長が長くなるため、リンクの配線長が均一なグリッド型トポロジに比べて、配線遅延やリピータ数、消費電力の点で不利となると考えられ、NoCへの適用がためらわれてきた。しかしながら、3次元化によって上位リンクの配線長を短くでき、上記弱点を克服できると考えられる。また、3次元ICではグリッド型のトポロジに比して性能パフォーマンスが優ることが期待できる。
【0009】
本発明は、複数のモジュール間を接続する集積電気回路の配線構造において、適正なツリー型トポロジで3次元構造を実現することにより、2次元配線構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することを目的とする。
【課題を解決するための手段】
【0010】
上記課題を解決するために本発明の第1の態様における三次元集積電気回路の配線構造は、例えば図8に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリー(Fat Tree)トポロジを用いて構成される。
【0011】
ここにおいて、交換接続手段とはモジュールを1対多数又は多数対多数の接続が可能な接続手段をいい、ルータ、交換機のスイッチ等が該当する。また、Fat Treeトポロジは例えば図11のような電気回路モジュールと交換接続手段の配線接続関係を規定するトポロジであるが、交換接続手段の上向きリンク数p、下向きリンク数q及び電気回路モジュールの上向きリンク数cにより複数の態様があり、このような態様のFat Treeを(p,q,c)Fat Treeと称する。このように構成すると、複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【0012】
上記課題を解決するために本発明の第2の態様における三次元集積電気回路の配線構造は、例えば図19及び図20に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリー(Fat H−Tree)トポロジを用いて構成される。
【0013】
ここにおいてFat H−Treeトポロジは、Fat Treeトポロジと同様に電気回路モジュールと交換接続手段の配線接続関係を規定するトポロジで、発明者達の提案による高パフォーマンスのトポロジである(松谷宏紀、鯉渕道紘、天野英晴:3次元IC向けFat TreeベースNetwork−on−Chips、情報処理学会研究報告2007−ARC−171,2007−EMB−3,p75−80,Jan,2007 及び、松谷宏紀、鯉渕道紘、天野英晴:チップ内ネットワークにおけるFat H−Treeトポロジの性能評価、情報処理学会研究報告2006−ARC−169,p109−114,Aug,2006 参照)。このように構成すると、複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【0014】
また、本発明の好ましい態様によれば、第1の態様又は第2の態様の三次元集積電気回路の配線構造において、前記交換接続手段を制御する制御手段と前記交換接続手段と前記制御手段とを接続する制御信号線を備え、前記二次元集積電気回路モジュール間に布設される制御信号線は貫通ビアを通して配線される。このように構成すると、制御系配線についても配線長を低減し、モジュール間の通信遅延を低減できる。
【0015】
また、本発明の好ましい態様によれば、以上の態様の三次元集積電気回路の配線構造において、前記貫通ビアの少なくとも1つは前記二次元集積電気回路モジュールのほぼ中央を貫通する。ここにおいて、貫通ビアは二次元集積電気回路モジュールのほぼ中央を貫通するものに加え、別の位置にあっても良い。また、貫通ビアは連結する最下層の二次元集積電気回路モジュールについては配線接続できれば必ずしも貫通する必要はない。このように構成すると、垂直方向配線の配線長を低減でき、モジュール間の通信遅延を低減できる。
【0016】
また、本発明の好ましい態様によれば、以上の態様の三次元集積電気回路の配線構造において、例えば図8に示すように、各電気回路領域は同一寸法の正方形又は長方形である。ここにおいて正方形又は長方形の辺の寸法や内角は設計誤差や製造ばらつきにより多少のばらつきが有っても良い。このように構成すると、電気回路モジュールを2次元平面内に無駄なく配置でき、また3次元の配線構造の設計も効率化できる。
【0017】
また、本発明の好ましい態様によれば、第1の態様の三次元集積電気回路の配線構造において、例えば図8に示すように、下位の交換接続手段に繋がる上位の交換接続手段は2個または4個である。このように構成すると、モジュール間の接続パスを多重ルートにして通信トラヒックの集中を緩和できる。また、単一モジュールへの複数入力を要する演算、複数モジュールへの出力等を効率化できる。
【0018】
また、本発明の好ましい態様によれば、第1の態様の三次元集積電気回路の配線構造において、例えば図8に示すように、電気回路モジュールを二次元平面に2行2列に配置して第1レイヤモジュールを構成し、第1レイヤモジュールを二次元平面に2行2列に配置して第2レイヤモジュールを構成し、第m−1レイヤモジュールを二次元平面に2行2列に配置して第mレイヤモジュールを構成し、第mレイヤモジュールを三次元空間に4層積層して第m+1レイヤモジュールを構成し、第m+1レイヤモジュールを三次元空間に4層積層して第m+2レイヤモジュールを構成し、第n−1レイヤモジュールを三次元空間に4層積層して第nレイヤモジュールを構成し(1<m<nとする)、4個の第1レイヤモジュールの面心付近に4つの電気回路領域と2つ又は4つの第2ランク交換接続手段に繋がる第1ランク交換接続手段を備え、4個の第2レイヤモジュールの面心付近に4つの第1ランク交換接続手段と2つ又は4つの第3ランク交換接続手段に繋がる第2ランク交換接続手段を備え、4個の第m−1レイヤモジュールの面心付近に4つの第m−2ランク交換接続手段と2つ又は4つの第mランク交換接続手段に繋がる第m−1ランク交換接続手段を備え、4層の第mレイヤモジュールの各層に4つの第m−1ランク交換接続手段と2つ又は4つの第m+1ランク交換接続手段に繋がる第mランク交換接続手段を備え、4層の第mレイヤモジュールを貫き4つの第mランク交換接続手段と第m+1ランク交換接続手段を繋ぐ第mの垂直方向配線を備え、4層の第m+1レイヤモジュールの各層に4つの第mランク交換接続手段と2つ又は4つの第m+2ランク交換接続手段に繋がる第m+1ランク交換接続手段を備え、4層の第m+1レイヤモジュールを貫き4つの第m+1ランク交換接続手段と第m+2ランク交換接続手段を繋ぐ第m+1の垂直方向配線を備え、4層の第n−1レイヤモジュールの各層に4つの第n−2ランク交換接続手段と2つ又は4つの第nランク交換接続手段に繋がる第n−1ランク交換接続手段を備え、4層の第n−1レイヤモジュールを貫き4つの第n−1ランク交換接続手段と第nランク交換接続手段を繋ぐ第n−1の垂直方向配線を備える。
【0019】
ここにおいて、レイヤモジュールの面心とは、当該レイヤモジュールが4個の下位のレイヤモジュール又は4個の電気回路モジュールで構成されている場合には、これら4個のモジュールの頂点が集まる位置をいう。また、m及びnは整数で、1<m<nである。このように構成すると、3次元空間にFat Treeトポロジを適用した、配線遅延が低減された三次元集積電気回路を実現できる。
【0020】
また、本発明の好ましい態様によれば、第2の態様の三次元集積電気回路の配線構造において、例えば図19及び図20に示すように、電気回路モジュールを二次元平面に2行2列に配置して第1レイヤモジュールを構成し、第1レイヤモジュールを二次元平面に2行2列に配置して第2レイヤモジュールを構成し、第m−1レイヤモジュールを二次元平面に2行2列に配置して第mレイヤモジュールを構成し、4個の第1レイヤモジュールの面心付近に4つの電気回路領域と1つの第2ランク交換接続手段に繋がる第1ランク交換接続手段を備え、4個の第2レイヤモジュールの面心付近に4つの第1ランク交換接続手段と1つの第3ランク交換接続手段に繋がる第2ランク交換接続手段を備え、4個の第m−1レイヤモジュールの面心付近に4つの第m−2ランク交換接続手段と1つの第mランク交換接続手段に繋がる第m−1ランク交換接続手段を備え、前記全ての第1ランク交換接続手段乃至第m−1ランク交換接続手段を右方向及び下方向に1モジュールずつ循環シフトした位置に第1ランク交換接続手段乃至第m−1ランク交換接続手段を備え、第mレイヤモジュールを三次元空間に4層積層して第m+1レイヤモジュールを構成し、第m+1レイヤモジュールを三次元空間に4層積層して第m+2レイヤモジュールを構成し、第n−1レイヤモジュールを三次元空間に4層積層して第nレイヤモジュールを構成し(1<m<nとする)、4層の第mレイヤモジュールの重心付近の第m−1レイヤモジュールに4つの第m−1ランク交換接続手段と1つの第m+1ランク交換接続手段に繋がる第mランク交換接続手段を備え、4層の第mレイヤモジュールを貫き4つの第mランク交換接続手段と第m+1ランク交換接続手段を繋ぐ第mの垂直方向配線を備え、4層の第m+1レイヤモジュールの重心付近の第mレイヤモジュールに4つの第mランク交換接続手段と1つの第m+2ランク交換接続手段に繋がる第m+1ランク交換接続手段を備え、4層の第m+1レイヤモジュールを貫き4つの第m+1ランク交換接続手段と第m+2ランク交換接続手段を繋ぐ第m+1の垂直方向配線を備え、4層の第n−1レイヤモジュールの重心付近の第n−2レイヤモジュールに4つの第n−2ランク交換接続手段と1つの第nランク交換接続手段に繋がる第n−1ランク交換接続手段を備え、4層の第n−1レイヤモジュールを貫き4つの第n−1ランク交換接続手段と第nランク交換接続手段を繋ぐ第n−1の垂直方向配線を備え、前記第mレイヤモジュール乃至前記第nレイヤモジュール内の電気回路モジュールの配置は第nレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし、前記全ての第1ランク交換接続手段乃至第m−1ランク交換接続手段を右方向及び下方向に1モジュールずつ循環シフトした位置に配置された第1ランク交換接続手段乃至第m−1ランク交換接続手段については、前記第mレイヤモジュール乃至前記第nレイヤモジュール内の電気回路モジュールの配置を第nレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし、同一の第1レイヤモジュールに属する電気回路モジュールで第1ランク交換接続手段と異なる二次元平面に配置されたものと前記第1ランク交換接続手段を繋ぐ第1の垂直方向配線を備え、前記再配置した第mレイヤモジュール乃至第nレイヤモジュールにおいても前記第mランク交換接続手段乃至前記第nランク交換接続手段と同様の接続関係を有する。
【0021】
ここにおいて、レイヤモジュールの重心付近とは、二次元平面での面心付近で、さらに三次元積層構造の垂直方向においても中心に近いことをいい、当該レイヤモジュールが4層の下位のレイヤモジュールで構成されている場合には、第2層目又は第3層目が該当する。この下位のレイヤモジュールがさらに下位の4層のレイヤモジュールで構成されている場合には、垂直方向においてできるだけ中心に近い1層に配置されるのが好ましい。このように構成すると、3次元空間にFat H−Treeトポロジを適用した、配線遅延が低減された三次元集積電気回路を実現できる。
【0022】
上記課題を解決するために本発明の第3の態様における三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される。
【0023】
ここにおいて、配線には無線による配線を含むものとする。また、無線送受信手段として一体化された送受信回路を用いても良く、個別の送信回路と受信回路とを用いても良い。このように構成すると、複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【0024】
上記課題を解決するために本発明の第4態様における三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される。
【0025】
このように構成すると、複数のモジュール間を3次元的に接続する3次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【0026】
また、以上の態様の三次元集積電気回路の配線構造において、前記電気回路モジュールは空モジュールを含む。ここにおいて、空モジュールは電気回路を搭載していないモジュールであり、今後電気回路を搭載したモジュールに置換が予定されているものでも良く、本来電気回路が不要で空きスペースになっているものでも良い。このように構成すると、モジュール数(コア数)が4n等に該当しない場合にも本発明の配線構造を適用できる。
【0027】
上記課題を解決するために本発明の第1の態様における三次元集積電気回路の配線構造のレイアウト方法は、例えば図14に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される三次元集積電気回路の配線構造のレイアウト方法であって、前記ファットツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程(S10)と、前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程(S20)と、前記ノードマッピング工程(S20)で配置された前記三次元集積電気回路を前記ツリー分割工程(S10)で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程(S30)と、前記折り畳み工程(S30)で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクする垂直リンク工程(S40)とを備える。このように構成すると、本発明の第1の態様における三次元集積電気回路の配線構造を効率的に実現できる。なお、第3の態様における三次元集積電気回路の配線構造については、垂直リンク工程(S40)の貫通ビアを無線配線に代えることにより、同様に実現可能である。
【0028】
上記課題を解決するために本発明の第2の態様における三次元集積電気回路の配線構造のレイアウト方法は、例えば図14に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される三次元集積電気回路の配線構造のレイアウト方法であって、前記ファットエイチツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程(S10)と、前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程(S20)と、前記ノードマッピング工程(S20)で配置された前記三次元集積電気回路を前記ツリー分割工程(S10)で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程(S30)と、前記折り畳み工程(S30)で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクする垂直リンク工程(S40)とを備える。このように構成すると、本発明の第1の態様における三次元集積電気回路の配線構造を効率的に実現できる。なお、第3の態様における三次元集積電気回路の配線構造については、垂直リンク工程(S40)の貫通ビアを無線配線に代えることにより、同様に実現可能である。
【0029】
また、本発明は、第1又は第2の態様の三次元集積電気回路の配線構造のレイアウト方法をコンピュータに実行させるためのコンピュータ読み取り可能なプログラムとして実現できる。
【発明の効果】
【0030】
本発明によれば、複数のモジュール間を接続する集積電気回路の配線構造において、適正なツリー型トポロジで3次元構造を実現することにより、2次元構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することができる。
【発明を実施するための最良の形態】
【0031】
[配線トポロジ]
以下に、図面に基づき本発明の実施の形態について説明する。まず、NoCで用いられる2次元及び3次元配線のトポロジについて説明する。
【0032】
図1に、リンク数が小さく対称な2次元レイアウトが可能なトポロジの代表例を示す。図1(a)に2−D Mesh、図1(b),(e)に2−D Torus、図1(c)にエイチツリー(H−Tree)、図1(d)にFat Treeのトポロジを示す。各トポロジにおいて、複数のルータが行列で配列され、四角はルータ、丸はコアをそれぞれ表す。図1(a)の2−D Meshは、隣り合うルータを格子状に配線したもので、Rawプロセッサ、Tripsプロセッサ、ストリーム処理向けNoCであるaSOC(Adaptive System on a Chip)、picoChip社の超並行処理プロセッサアレイなどに幅広い用途で用いられている。図1(e)の2−D Torusは、2−D Meshの配線に加え、ネットワークの両端のコアを結ぶラップアラウンド(wrap−around)チャネルを有している。図1(b)はこれを、チャネル長が均一になるようにコアの行、列を0,3,1,2の順に配置換えしたものである。2−D TorusはIMEC社のNoCなどで用いられている。図1(c)のH−Treeは、4分木配線構造を取る。すなわち、4個のコアをレベル1ルータで交換接続し、さらに4個のレベル1ルータをレベル2ルータで交換接続し、ツリー構造で通信対象を拡大する方式である。このため、2次元平面実装に適しているが、トラフィックがツリーの上位のルータ付近に集中しやすいという問題がある。H−Treeはアンドレ・デホン(Andre Dehon)らが提案した計算システムSCORE(Stream Computations Organized for Reconfigurable Execution)やQuickSilver社のACM(Adaptive Computing Machine)などのリコンフィギャラブルシステムで利用されている。
【0033】
次に、本発明の3次元配線に適用するトポロジであるFat Treeについて説明する。図1(d)のFat TreeはH−Treeにおけるツリー構造を多重化したものであるが、ルータの上向きリンク数p、下向きリンク数q、コアの上向きリンク数cの組み合わせがあり、これを(p,q,c)で表わす。図1(d)のFat Treeは(2,4,2)Fat Treeと表わされる。H−Treeに比して多重化した上位ツリーにより経路分散が可能で、トラフィックの集中が緩和される。既存のNoCへの適応例としてはSPINなどがある。
【0034】
これまで、ツリー型トポロジは、上位のルータ付近のリンクの長さが長くなるため配線遅延の点で不利である、すなわち、Fat Treeでは最上位リンクの配線長が長くなり、このため、リンクの配線長が均一なグリッド型トポロジに比べて、配線遅延やリピータ数、消費電力の点で不利となると考えられてきたが、我々の検討結果、3次元化によってこの弱点を克服できることが分かった。ここでは、Fat Treeおよび後述するFat H−Treeトポロジを用いて3次元NoCに適した配線構造を提案し、チップ面積、配線量、最長配線長、配線遅延、リピータ数、消費電力について評価する。モジュール間の相互接続トポロジとしてルータのリンク数を抑えつつ、一定の高い性能を実現するツリーの多重化を基にする。全体の配線長を短くするために3次元方向のルータ間の配線に貫通ビア等を用いるが、配線が交錯しないように、最上位ランクのルータの周りに次上下位レベルのルータを分散配置する。
【0035】
図2に64コアFat Treeのツリー構造の例を示す。64コアをランク1ルータ(第1ランクルータのこと、以下第nランクルータをランクnルータという)からランク3ルータを介して相互接続する階層構造である。四角の中の数字はルータのランク数である。ランク1ルータとランク2ルータ間の配線及びランク2ルータとランク3ルータ間の配線は2重化されており、ランク1ルータは4コアと2個のランク2ルータに、ランク2ルータは4個のランク1ルータと2個のランク3ルータに、ランク3ルータは4個のランク2ルータに接続される。
【0036】
次に、本発明の他の3次元配線に適用するトポロジであるFat H−Treeについて説明する。Fat H−Treeはレッドツリー(Red Tree)とブラックツリー(Black Tree)と呼ばれる2つのH−Treeを組み合わせたトポロジであり、トーラス構造を内包している。すなわち、Black Treeを介してネットワークの両端のコア(第0行と第7行、第0列と第7列)を結ぶラップアラウンドチャネルを有している。各コアは2つのリンクを有し、1つをRed Treeとの接続に、他の1つをBlack Treeとの接続に用いる。Fat H−TreeはFat Tree より構成が複雑であるが、コスト性能比で優れる。
【0037】
図3に64コアRed Treeのツリー構造の例を示す。丸で描かれた各コアには2次元座標(x,y)がそれぞれ割り当てられる。以降、コアをランク0ルータとも呼ぶ。まず、ランク0ルータに対し式(1)で求まるRed Tree座標R(r0,r1,・・・,ri,・・・,rn−1)を割り当てる。ここで、iはランクを表す。
ri=((x/2i)mod2)+2×((y/2i)mod2) (1)
Red Tree座標R(r0,r1,・・・,rn−1)となるランク0ルータの上位ルータをランク1ルータと呼び、R(r1,・・・,rn−1)のRed Tree座標を割り当てる。同様の方法でランク2ルータからランクnルータにもRed Tree座標を割り当てる。ただし、最上位ランク(ランクn)ルータのRed Tree座標をRとする。また、任意のランクのルータに繋がる次位ランクのルータは4つずつになり、これらのルータに付する符号の順序は左上を0、右上を1、左下を2、右下を3とする。例として図中にランク3ルータR、ランク2ルータR(0)、ランク1ルータR(2,0)、コアR(2,2,0)の位置座標を示す。ここで、R(0)はランク3ルータRにつながる4つのランク2ルータのうち左上のものを表し、R(2,0)はR(0)につながる4つのランク1ルータのうち左下のものを表し、R(2,2,0)はR(2,0)につながる4つのコアのうち左下のものを表す。
【0038】
図4に64コアBlack Treeのツリー構造の例を示す。Black TreeはRed Treeの座標を右方向及び下方向に1コア分ずつずらしたものである。
【0039】
図5にRed Treeの座標とBlack Treeの座標の関係を示す。Red Treeのコア座標RiはBlack Treeのコア座標Biに移る。ルータおよび配線の座標も同様に右方向及び下方向に1コア分ずつずれる。さらに、Black Treeの7行目のコアは8行目、7列目のコアは8列目に移動するが、これを0行目、0列目に移動する。また、第7行7列目のコアは第8行8列目に移動するが、これを第0行0列目に移動する。このずれと移動を循環シフトと称することとする。このためランク0ルータのBlack Tree座標B(b0,b1,・・・,bi,・・・,bn−1)は式(2)で求まる。
bi=((((x−1)mod2n)/2i)mod2)+2×((((y−1)mod2n)/2i)mod2) (2)
Black Treeにおいてもランク1ルータからランクnルータにBlack Tree座標を割り当てる。最上位ランク(ランクn)ルータのBlack Tree座標をBとする。また、任意のランクのルータに繋がる次位ランクのルータは4つずつになり、これらのルータに付する符号の順序は左上を0、右上を1、左下を2、右下を3とする。例として図中にランク3ルータB、ランク2ルータB(2)、ランク1ルータB(1,2)、コアB(0,1,2)の位置座標を示す。ここで、B(2)は4つのランク2ルータのうち左下のものを表し、B(1,2)はB(2)につながる4つのランク1ルータのうち右上のものを表し、B(0,1,2)はR(1,2)につながる4つのコアのうち左上のものを表す。
【0040】
図6に64コアFat H−Treeの2次元レイアウトを示す。各コア(ランク0ルータ)に対し、Red TreeおよびBlack Treeを接続したものをFat H−Treeと称する。Fat H−Treeにおいてはトーラス構造が形成される。すなわち、各コアはRed Treeのランク1ルータおよびBlack Treeのランク1ルータにつながり、コア−Red Treeのランク1ルータ−コア−Black Treeのランク1ルータ−コアの順序でリンクが形成され、第0行目のコアと第7行目のコア、第0列目のコアと第7列目のコアはBlack Treeのランク1ルータを介して接続され、ラップアラウンドチャネルが形成される。
【0041】
図7に畳み込み処理されたFat H−Treeの2次元レイアウトを示す。Fat H−Treeは、トーラス同様、畳み込むことで2次元チップ上に容易にレイアウトできる。畳み込みとは2次元平面の配置の仕方で、例えば行、列の配置を0,7,1,6,2,5,3,4のように並び換えるものである。図6において、配線接続関係を保ちながら、畳み込み処理により再配置したレイアウトが図7に相当し、図6と図7は等価なトポロジである。最上位リンクを除き、Fat H−Treeの各リンクは畳み込みによって配線長が約2倍に延びるが、最上位リンクの配線長は大幅に短縮される。そのため、最上位の次のランクのリンク(第2位リンク)がFat H−Treeの最長配線となる。
【0042】
次にFat Treeの3次元IC向けレイアウトについて説明する。Fat Treeの弱点は、最上位リンク(ランク3ルータとランク2ルータ間の配線)の配線長が長くなることによる配線遅延の増加、リピータ数の増加、およびそれに伴う消費電力の増加である。これらの問題を同時に解決するために、図2で示したFat Treeを半分の寸法から成る4枚のチップに分割し、これらを3次元的に結合する。こうすることで、すべての最上位リンクは距離数十μm程度のチップ間リンクに置き換えられ、配線長の問題は解決される。
【0043】
図8にFat Treeを4分割した例を示す。3−D(2,4,1)Fat Treeの例である。Fat Treeの4分割手順は次のとおりである。
(ステップ1:チップの分割)まず、チップの分割を行う。2次元Fat Treeのコア座標(x2D,y2D)を、次のような3次元座標(x3D,y3D,z3D)に変換する。
x3D=x2Dmod2n−1
y3D=y2Dmod2n−1
z3D=2×(y2D/2n−1)+(x2D/2n−1)
例えば、図2の64コアFat Treeは図8のように4枚の16コアチップに分割される。
(ステップ2:ルータの配置)ルータを各チップに均等に振り分け配置する。図8の例では、各チップは4個のランク1ルータ、2個のランク2ルータ、1個のランク3ルータを有する。
(ステップ3:チップ間配線)他のランクに配置されたルータ同士をチップ間配線でつなぐ。最上位リンクは、マイクロバンプ、無線、貫通ビアなどのチップ間通信技術を用いてチップ面に対して垂直方向に結合される。
(ステップ4:ルータの再配置)垂直方向のチップ間リンク同士が重ならないように、ルータの位置を調整する。図8の例では、チップの中心にランク3ルータを置き、その周囲に他のランクと重ならないように各ランク2ルータを位置をずらして配置している。これにより最上位リンクはチップ間リンクに置き換えられる。結果的に、最上位リンクの1/2の長さの第2位リンクが最長配線となるため、4分割によって最長配線長は1/2に短縮される。この方法は、(2,4,2)Fat Treeなど他の構成のFat Treeに対しても適用できる。
【0044】
次に4分割以外の分割方法について説明する。iを正の整数とするとき、チップの2i分割はチップの4分割と2分割を組み合わせることで実現できる。チップの2分割の場合、2次元のコア座標から3次元座標への変換は次のようになる。
x3D=x2D
y3D=y2Dmod2n−1
z3D=y2D/2n−1
これ以外の点については4分割の場合と同じである。チップ間リンクの距離を無視するとき、最上位リンクの長さは2分割によって、縦方向が1/2になり、横方向がそのままなので3/4に短縮される。
【0045】
次に、Fat H−Treeの3次元IC向けレイアウトについて説明する。Fat H−Treeでは、畳み込みによって第2位リンク(ランク2ルータとランク1ルータ間の配線、図3の配線長の2倍になる)が最長配線となる。この最長配線の長さはFat Treeの最長配線(ランク3ルータとランク2ルータ間の配線、図2参照)の長さと同じであり、配線遅延、リピータ、および消費電力の増加を引き起こす。ここでは、Fat Treeと同様に、これらの問題を3次元化によって解決する。
【0046】
次に、Fat H−Treeの4分割について説明する。Fat H−Treeは2個のH−Treeの他に2−D Torus構造を内包するため、チップの分割後もこの2−D Torus構造が保存されていなければならない。このためFat H−Treeの分割では、チップの分割時にコア座標の転置処理を行う。
【0047】
図9にRed Treeを4分割した例を、図10にBlack Treeを4分割した例を示す。Fat H−Treeの4分割手順は次のとおりである。
(ステップ1:チップの分割)まず、チップの分割を行う。2次元Fat H−Treeのコア座標(x2D,y2D)を、次のような3次元座標(x3D,y3D,z3D)に変換する。
x3D=x2Dmod2n−1 (x2D<2n−1 のとき)
x3D=2n−1−(x2Dmod2n−1) (x2D>=2n−1 のとき)
y3D=y2Dmod2n−1 (y2D< 2n−1 のとき)
y3D=2n−1−(y2Dmod2n−1) (y2D>=2n−1 のとき)
z3D=2×(y2D/2n−1)+(x2D/2n−1)
この処理によって、元のチップはチップの中心を軸に水平方向、および、垂直方向に折り畳まれ4枚のチップに分割される。例えば、図3のRed Treeは図9のように、また、図4のBlack Treeは図10のようにそれぞれ分割される。
(ステップ2:ルータの配置)ルータを各チップに均等に振り分け配置する。この例では、Red Tree(図9参照)およびBlack Tree(図10参照)ともに、各チップに4個のランク1ルータ、1個のランク2ルータを有する。一方、ランク3ルータは、Red Treeはチップ1(第2層目)に、Black Tree はチップ2(第3層目)にそれぞれ1個ずつ有する。
(ステップ3:チップ間配線)他のランクに配置されたルータ同士をチップ間配線でつなぐ。Black Treeでは最上位ルータに加え、ランク1ルータも異なるランクのコア同士をつないでいる。この様子を図10の端部のコアに接続先のチップを表示して示す)。なお、接続されるコア同士は折り畳まれた時に垂直方向に重なり合うこととなる。
(ステップ4:ルータの再配置)必要に応じて行う。ランク2ルータは垂直方向に重ならないので、ここでは再配置を行なわなくても良い。
【0048】
図9および図10のレイアウトを組み合わせたものがFat H−Treeの3次元レイアウトであり、分割後も2−D Torus構造が保存されている。例えば、コアR(1,0,0)の2ホップ先(Red Treeのランク1ルータ−コア−Black Treeのランク1ルータを介する)はコアR(1,1,0)であり、その次はコアR(1,2,0),コアR(1,3,0)と移動した後、チップ2に移り、コアR(1,3、2),コアR(1,2,2),コアR(1,1,2)、コアR(1,0,2)を経て、再びチップ0のコアR(1,0,0)に戻る。図6にこの軌跡を矢印で示す。チップ間を除き2ホップ先へはRed TreeとBlack Tree各1個のランク1ルータを介して配線接続される。またチップ間については、図7を参照するとコアR(1,0,0)とコアR(1,0,2),コアR(1,3,0)とコアR(1,3,2)は垂直方向に重なり、垂直方向の配線で接続されることが分かる。
【0049】
次に、4分割以外の分割方法について説明する。チップの2分割の場合、2次元のコア座標から3次元座標への変換は次のようになる。
x3D=x2D
y3D=y2Dmod2n−1 (y2D<2n−1 のとき)
y3D=2n−1−(y2Dmod2n−1) (y2D>=2n−1 のとき)
z3D=2×(y2D/2n−1)+(x2D/2n−1)
この場合、x方向のリンクは単一チップ内で完結するため、x方向に対してのみ図7のような畳み込みを行う。これ以外の点については4分割の場合と同じである。チップ間リンクの距離を無視するとき、最上位リンクの長さは2分割によって3/4に短縮される。
【0050】
[第1の実施の形態]
第1の実施の形態では、64コア、3階層のFat Treeトポロジの例を説明する。一般的には、4n個のモジュール間を、2ν個の2次元平面を積層した3次元空間に集積化するために、4本または6本の配線を持つ交換接続手段を用いたFat Treeで階層的に接続する。
【0051】
図11に64コア3階層のFat Treeトポロジの例を示す。43=64個のモジュールを3階層に積層した64コアFat Treeトポロジである。最下層の第1のレイヤには64個のコアが存在し、それぞれに電気回路で構成されるモジュールが配置されており、第i行第j列〜第i+1行第j+1列(i,j=0〜14の偶数)内の4個のモジュールを集めて1つの第1レイヤモジュールを構成し、第1レイヤモジュールにはこれら4個のモジュール間を交換接続するランク1ルータ、図中□内に「1」と表示)が配置されている。第1レイヤモジュールは16個存在する。また、ランク1ルータは2つの上位のランク2ルータへのリンクを有し(すなわちルートが2重化されている)、4個のモジュールとこれら2個のランク2ルータとの交換接続も行う。第2のレイヤでは、第i行第j列〜第i+3行第j+3列(i,j=0,4)内の4個の第1レイヤモジュールを集めて1つの第2レイヤモジュールを構成し、第2レイヤモジュールにはこれら4個の第1レイヤモジュール間を交換接続するランク2ルータ(図中□内に「2」と表示)が配置されている。第2レイヤモジュールは8個存在する。また、ランク2ルータは2つの上位のランク3ルータへのリンクを有し(すなわちルートが2重化されている)、4個の第1レイヤモジュールとこれら2個のランク3ルータとの交換接続も行う。第3のレイヤでは、第i行第j列〜第i+7行第j+7列(i,j=0)内の4個の第2レイヤモジュールを集めて1つの第3レイヤモジュールを構成し、第3レイヤモジュールにはこれら4個の第2レイヤモジュール間を交換接続するランク3ルータ(図中□内に「3」と表示)が配置されている。第3レイヤモジュールは4個存在する。このようなツリートポロジを構成することにより、64個のモジュールのうちの任意の2モジュール間の接続が複数ルート(2×2=4)で可能になる。これは特定のルータへのトラフィックの集中を回避するのに役立つ。
【0052】
図12に64コアFat Treeトポロジを4つのチップに分割した構成を示す。各チップは第2レイヤモジュールに対応し、16個のモジュール、4個のランク1ルータ、2個のランク2ルータとこれらの間の配線を含んでいる。2個のランク2ルータがそれぞれ4個のランク1ルータに共に接続されることから、1個のチップには2個の第2レイヤモジュールが重複形成されている。各チップには更に1個のランク3ルータ及び当該ランク3ルータと当該チップに配置された1個のランク2ルータを接続する配線が含まれる。各チップは3次元空間に4層に積層される。異なるチップに存在するランク3ルータとランク2ルータを接続する配線はチップ間を繋ぐ垂直方向配線で接続される。
【0053】
図13に64コアFat Treeトポロジを4つのチップに分割し、4つのチップを積層したときの各ランクのルータ配置とルータ間配線の3次元レイアウトの概要を示す。図13(a)に各チップにおける2次元平面内の各ランクのルータ配置とルータ間配線を、図13(b)に各チップの3次元配置とランク2ルータ、ランク3ルータの配置を示す。図13(a)に示すように、各層のチップにおいて4個のモジュールを2行2列に配置して第1レイヤモジュールが構成され、ランク1ルータは第1レイヤモジュールのほぼ中心に配置され、また、4個の第1レイヤモジュールを2行2列に配置して第2レイヤモジュールが構成され、ランク2ルータは第2レイヤモジュールのほぼ中心に配置される。ランク2ルータと各4個のランク1ルータとはチップ面内の配線により接続される。各チップに第2レイヤモジュールが2重に構成され、4つのチップを積層して第3レイヤモジュールが構成される。第3レイヤモジュールも2重のものが2組合計4つ構成される。また、図13(b)に示すように、最上位のランク3ルータを各チップの2次元平面構造の中心に配置し、ランク2ルータをランク3ルータの隣接周辺に、2次元平面に対して垂直方向に重ならないように配置する。各ランク3ルータから4個のランク2ルータに到る4本の配線のうち、1本は同一層内の1個の隣接するランク2ルータにチップ内で接続され、他の3層のランク2ルータに到る3本は垂直方向配線を4つのチップの中心付近を貫く貫通ビア(最下層は必ずしも貫く必要はない)を通して各層に延び、各層において貫通ビアに隣接する1個のランク2ルータに接続される。例えば、第1層と第3層のランク3ルータは第1層の上、第2層の右上、第3層の右、第4層の右下に隣接配置されたランク2ルータに接続され、第2層と第4層のランク3ルータは第1層の下、第2層の左下、第3層の左、第4層の左上に隣接配置されたランク2ルータに接続される。垂直方向配線は、第1層と第2層間に6本、第2層と第3層間に8本、第3層と第4層間に6本となるが(図12参照)、これらは貫通ビアを通してまとめて配線される。このような配線構造により、モジュールから遠いルータ間の配線長、すなわちランク2ルータとランク3ルータ間の配線長を削減でき、これらの配線における信号の遅延を無視できるようにしている。
【0054】
なお、これまで各ランクのルータを制御する制御手段について言及しなかったが、かかる制御手段を備えるものとし、モジュール間での信号を伝達する配線だけでなく、これらの制御手段と各ランクのルータを接続する制御信号線、さらに電源線についてもチップ間に布設されるものは貫通ビアを通してまとめて配線しても良い。このようにすれば制御線や電源線の遅延も削減できる。
【0055】
図14にFat Treeトポロジの配線レイアウトのアルゴリズムの大略を示す。本実施の形態では64コア(2,4,1)Fat Treeの配線レイアウトについて説明する。まず、ファットツリートポロジを二次元集積電気回路モジュールに相当するチップ対応に分割する(ツリー分割工程:S10)。一般的にはコア数4nのFat Treeでは4n―m分割が可能である。ここでは図11のFat Treeを図12のように4分割する。
【0056】
次にノードのマッピング、すなわち、三次元集積電気回路を二次元平面に展開した状態で、電気回路モジュール(コア)と交換接続手段(ルータ)の配置を行なう(ノードマッピング工程:S20)。一般的には4nのコアとルータを2次元平面に展開し、コアとルータを配置する。ここではまず、n=3であり、コアを2行×2列の4コアずつにわけてランク1ルータをその中心に配置して第1レイヤモジュールを形成する。第1レイヤモジュールは全部で16個になる。次に、2行×2列の4つの第1レイヤモジュールのランク1ルータの中心付近にランク2ルータを配置して第2レイヤモジュールを形成し、ランク2ルータとランク1ルータを配線接続する。4つの第1レイヤモジュールに対してランク2ルータは2つ、すなわち第2レイヤモジュールは2重に形成される。第1レイヤモジュールは全部で8個になる。次に、2行×2列の4つの第2レイヤモジュールのランク2ルータの中心付近にランク3ルータを配置して第3レイヤモジュールを形成する。4つの第2レイヤモジュールに対してランク3ルータは2つ、すなわち第3レイヤモジュールは2重に形成される。第3レイヤモジュールは全部で2重のものが2組合計4個形成される。この平面構成は図2に示される。次に、このように構成されたモジュールの各コアに番号を付する。
【0057】
図15はコアのマッピングと折り畳みを説明するための図である。コアの番号は図15に示すように、第0行目の第0列から第2n−1(=7)列へ、第1行目の第0列から第2n−1(=7)列へ、・・・、第2n−1(=7)行目の第0列から第2n−1(=7)列へ採番する。図15の左側の符号はコアの行を、上側の符号はコアの列を示し、1st〜4thはグループ(層)を示す。さらに、ランク1ルータからランク3ルータに番号を付する。ルータの番号は例えばRed Tree座標R(r1,・・・,rn−1)のように採番する。
【0058】
次にノードマッピング工程で配置された三次元集積電気回路をツリー分割工程で分割した二次元集積電気回路モジュール(チップ)を積層するように折り畳む(折り畳み工程:S30)。一般的には4n―m分割するのでn−m重に折り畳むが、ここではn=3、m=2で、4重に折り畳む。図15の太枠のように全体を4つにグループに分け、各グループに層番号を付する。第3行目と第4行目の間及び第3列目と第4行列目の間に境界線を引くことにより、4つのグループに分けられる。各グループは第2レイヤモジュールに相当し、4×4=16コアを有する。例えば、左下の第1グループを第1層目、左上の第2グループを第2層目、右上の第3グループを第3層目、右下の第4グループを第4層目とする。第1グループは第3行目と第4行目の間の境界線に沿って第2グループの下に折畳み第1層目とする。第3グループは第3列目と第4行列目の間の境界線に沿って第2グループの上に折畳み第3層目とする。第4グループは第3列目と第4行列目の間の境界線に沿って第3グループと共に折畳み、さらに第3行目と第4行目の間の境界線に沿って第3グループの上に折畳み第4層目とする。このように折畳むと、コアの配置は図19(後述する)、ランク1ルータ、ランク2ルータの配置は図13(a)のようになる。ランク2ルータは各チップすなわち各グループの中心付近に2つずつ(2重に)配置される。ランク3ルータは全体に4個(2重×2組)であり、各チップの中心付近に1つずつ配置される。なお、上記境界線を用いて折り畳めばどのように折り畳んでも良い。
【0059】
次に、折り畳み工程で各チップに配置された交換接続手段(ルータ)のうちチップ間に分散された上位ランクの交換接続手段(ルータ)間を垂直方向配線でリンクする(リンク工程:S40)。4チップの中心付近でランク3ルータの近傍に貫通ビアを設け、各チップにおいて垂直方向から見てランク3ルータの周囲にランク2ルータを配置し、ランク3ルータとランク2ルータを配線接続する。各ランク3ルータからは同層の1個のランク2ルータには面内配線で接続され、他の3層のランク2ルータへは垂直配線で接続される。合計12本の垂直配線が1つの貫通ビア内に布設される。この場合に、例えば図13(b)に示すように、8個のランク2ルータが垂直方向に重ならないように配置する。このようにするとランク3ルータから各ランク2ルータへの配線を交錯させずに直線的に形成できる。
【0060】
[第2の実施の形態]
第2の実施の形態では、256コア、4階層のFat Treeトポロジの第1の例を説明する。図11の3階層のFat Treeトポロジを第3レイヤモジュールとし、この第3レイヤモジュールを4層積層して第4レイヤモジュールが構成される。チップは全体で16層積層される。各第3レイヤモジュールにはそれぞれ4個、全体で16個の第3ランクルータがあり、例えば各チップに配置される。8個のランク4ルータが例えば第2層目の第3レイヤモジュールの最上層のチップに4個、第3層目の第3レイヤモジュールの最下層のチップに4個配置され、これらのランク3ルータとランク4ルータは各チップのほぼ中心に配置され、8個のランク4ルータと16個のランク3ルータを接続する配線は、ルータが同一チップ内にある場合は面内配線で隣接接続され、異なるチップ間にある場合は主としてチップ間を繋ぐ垂直方向配線で接続される。
【0061】
図16に16個のランク3ルータと8個のランク4ルータ間の配線のトポロジを示す。それぞれの第3レイヤモジュールには4層のチップが積層されている。さらに第3レイヤモジュールを4層積層して第4レイヤモジュールが構成され、全体で16層のチップが積層されている。ランク3ルータは各チップに配置される。第2層目の第3レイヤモジュールの最上層のチップに配置された4個のランク4ルータのうち、第k番目(k=1〜4)のルータは4個の第3レイヤモジュールの第k層目のチップ(第2レイヤモジュール)に配置されたランク3ルータに配線接続される。第3層目の第3レイヤモジュールの最下層のチップに配置された4個のランク4ルータについても同様に、第k番目(k=1〜4)のルータは4個の第3レイヤモジュールの第k層目のチップ(第2レイヤモジュール)に配置されたランク3ルータに配線接続される。このように、ランク3ルータとランク4ルータ間の配線は二重化されている。
【0062】
図17に各第3レイヤモジュールの3次元配置とランク3ルータ、ランク4ルータの配置の例を示す。ランク3ルータ(図では「3」と表示)とランク4ルータ(図では「4」と表示)を結ぶ垂直方向配線は、それぞれのランク4ルータから上方向へ2本、下方向へ2本で、全体で上下各方向へ16本ずつ(同層への配線を除くと15本ずつ)となり、中央の貫通ビアを通してまとめて配線され、それぞれランク3ルータが配置されたチップに延びて隣接するランク3ルータに接続される。また、各第3レイヤモジュール内でランク2ルータとランク3ルータを結ぶ垂直方向配線は、第3レイヤモジュールの層内を超えて延びることはないので、ランク3ルータはランク4ルータとの垂直方向配線に隣接して設ければ良く、垂直方向に重ならない方が交錯を避け易いが重ねて設けても良い。
【0063】
次に配線レイアウトのアルゴリズムについて述べる。256コア(2,4,1)Fat Treeでは第1の実施の形態に比して1階層大きくなっており、コア及びルータが増えている。ツリー分割工程(S10)では16チップに分割するが、チップ内のレイアウトは第1の実施の形態と同様である。ノードマッピング工程(S20)では256コアのマッピングを第0行第0列から第15行第5列まで行なうが、第1の実施の形態と同様の順序で行なえば良く、ランク1ルータとランク2ルータのマッピングも同様である。ランク3ルータとランク4は垂直方向配線に関わりチップの中央付近に配置される。折り畳み工程(S30)については境界線が第3行目と第4行目の間、第7行目と第8行目の間、第11行目と第12行目の間、第3列目と第4列目の間、第7列目と第8列目の間、第11列目と第12列目の間と縦横共3本ずつになるが、これらを境界線として折り畳めばどのように折り畳んでも良い。リンク工程(S40)については第1の実施の形態にランク3ルータとランク4ルータとの垂直方向配線が加わるが、図17で説明したように行なえば良い。
【0064】
[第3の実施の形態]
第3の実施の形態では、256コア、4階層のFat Treeトポロジの第2の例を説明する。図11の3階層のFat Treeトポロジを第3レイヤモジュールとし、第3レイヤモジュールが1チップ内の2次元平面に構成される。第3のレイヤでは、4個の第2レイヤモジュールが2行2列に配置されて1つの第3レイヤモジュールを構成し、これら4個の第2レイヤモジュール間を交換接続するランク3ルータが第3レイヤモジュールの中心に配置される。1個のチップには4つの第3レイヤモジュールと4個のランク3ルータが存在する。この第3レイヤモジュールを4層積層して第4のレイヤモジュールが構成され、これら4層合計16個の第3レイヤモジュール間を交換接続するランク4ルータが2個ずつ各第3レイヤモジュールの各層すなわち各チップのほぼ中心に配置され、合計8つの第4レイヤモジュールと8個のランク4ルータが存在する。ルータ間の配線の接続関係は第2の実施の形態と同様である。
【0065】
最上位のランク4ルータを各チップの2次元平面構造のほぼ中心に2個ずつ配置し、ランク3ルータをランク4ルータの隣接周辺に4個ずつ配置する。各ランク4ルータから各チップの4個のランク3ルータに到る4本の配線のうち、1本は同一層内の1個の隣接するランク3ルータにチップ内で接続され、他の3層のランク3ルータに到る3本は垂直方向配線を4つのチップの中心付近を貫く貫通ビアを通して各層に延び、各層において貫通ビアに隣接する1個のランク3ルータに接続される。例えば、第1層、第2層、第3層、第4層の第1番目のランク4ルータはそれぞれ各層の上、右上、右下に隣接配置されたランク3ルータ(各4個ずつ)に接続され、第1層、第2層、第3層、第4層の第2番目のランク4ルータはそれぞれ各層の下、左下、左、左上に隣接配置されたランク3ルータ(各4個ずつ)に接続される。垂直方向配線は、第1層と第2層間に6本、第2層と第3層間に8本、第3層と第4層間に6本となるが、これらは貫通ビアを通してまとめて配線される。
【0066】
次に配線レイアウトのアルゴリズムについて述べる。256コア(2,4,1)Fat Treeでは第1の実施の形態に比して1階層大きくなっており、コア及びルータが増えている。ツリー分割工程(S10)では4チップに分割する。このためチップが第1、第2の実施の形態に比して1階層分大きくなっており、第3レイヤモジュール、ランク3ルータまで含む。ノードマッピング工程(S20)は第2の実施の形態と同様である。折り畳み工程(S30)については境界線が第7行目と第8行目の間、第7列目と第8列目の間になり、縦横共1本ずつで第1の実施の形態と同じ本数になり、第1の実施の形態と同様に折り畳むと理解しやすい。なお、これらを境界線として折り畳めばどのように折り畳んでも良い。リンク工程(S40)については第1の実施の形態におけるランク2ルータとランク3ルータとの垂直方向配線の関係を本実施の形態におけるラン3クルータとランク4ルータとの垂直方向配線の関係に代えれば良い。
【0067】
[第4の実施の形態]
本実施の形態では、64コア、3階層のFat H−Treeトポロジの例を説明する。Fat H−TreeトポロジはRed TreeとBlack Treeと呼ばれる2つのH−Treeトポロジを組み合わせたトポロジである。1つのモジュールは2つのリンクを持ち、1つのリンクをRed Treeとの接続に、他の1つのリンクをBlack Treeとの接続に用いる。
【0068】
図3の64コアRed Treeのツリー構造の例を再度参照する。各コア(モジュール)を○で示す。この配線構造は第1の実施の形態で示した図11の64コアFat Treeトポロジを平面展開したもので、モジュールが8×8の行列に配置されている。第3の実施の形態における第3レイヤモジュールの配線構造とほぼ同じであるが、ランク1ルータ以上の配線が多重化されていない点が異なる。第i行第j列〜第i+1行第j+1列(i,j=0〜6の偶数)内の4つのモジュールがランク1ルータに接続されて第1レイヤモジュールを構成し、第i行第j列〜第i+3行第j+3列(i,j=0,4)内の4つの第1レイヤモジュールがランク2ルータに接続されて第2レイヤモジュールを構成し、第i行第j列〜第i+7行第j+7列(i,j=0)内の4つの第2レイヤモジュールがランク3ルータに接続されて第3レイヤモジュールを構成する。
【0069】
図4の64コアBlack Treeのツリー構造の例を再度参照する。各モジュールを○で示す。このモジュールの配置及びモジュール間の配線構造は、図3の64コアRed Treeのモジュールの配置及びモジュール間の配線構造を右方向に1モジュール分、下方向に1モジュール分ずらした構造である。そして、Red Treeの第7行目のモジュールが右方向に1モジュール分ずれたものがBlack Treeの第0行目となり、Red Treeの第7列目のモジュールが下方向に1モジュール分ずれたものがBlack Treeの第0列目となり、Red Treeの第7行第7列目のモジュールがBlack Treeの第0行第0列目のモジュールとなる。すなわち、Black TreeのモジュールはRed Treeのモジュールを右方向及び下方向に1モジュールずつ循環シフトしたものである。Black Treeの各モジュール間の配線接続関係は、モジュールの配置を右方向に1モジュール分、下方向に1モジュール分ずらした場合のRed Treeの各モジュール間の配線接続関係と同じである。すなわち、第i行第j列〜第i+1行第j+1列(i,j=1〜716の奇数)内の4つのモジュールがランク1ルータに接続されて第1レイヤモジュールを構成し、第i行第j列〜第i+3行第j+3列(i,j=1,5)内の4つの第1レイヤモジュールがランク2ルータに接続されて第2レイヤモジュールを構成し、第i行第j列〜第i+7行第j+7列(i,j=1)内の4つの第2レイヤモジュールがランク3ルータに接続されて第3レイヤモジュールを構成する。ただし、これらの行列において7行目に該当するモジュールはBlack Treeでは0行目のモジュールとして配置され、7列目に該当するモジュールはBlack Treeでは0列目のモジュールとして配置され、第7行第7列目に該当するモジュールはBlack Treeでは第0行第0列目のモジュールとして配置される。そして、ランク1ルータは0行目と7行目のモジュール、0列目と7列目のモジュールを配線接続する。
【0070】
図18に64コアFat H−Treeトポロジの例を示す。このモジュールの配置及びモジュール間の配線構造は、図3のRed Treeのモジュールの配置及びモジュール間の配線構造と図4のBlack Treeのモジュールの配置及びモジュール間の配線構造とを合せ持つ構造である。配線が二重化されていることにより、特定のルータへのトラフィックの集中を回避できる。
【0071】
図19に64コアFat H−Treeを4分割した時のRed Treeの3次元レイアウトを示す。これは図3のRed Treeのモジュール配置とモジュール間の配線接続構造を4つのチップに分割した時のレイアウトを示すもので、(a)は第1層目のチップのレイアウト、(b)は第2層目のチップのレイアウト、(c)は第3層目のチップのレイアウト、(d)は第4層目のチップのレイアウトを示す。全体構成は第1の実施の形態における第3レイヤモジュールに相当し、同じく第1の実施の形態における第2レイヤモジュールに相当する4つのチップを4層積層して第3レイヤモジュールを構成する。図3のRed Treeの各モジュールに、第0行目を第0列から第7列へモジュール番号0〜7を、第1行目を第0列から第7列へモジュール番号8〜15を、・・・第7行目を第0列から第7列へモジュール番号56〜63を順番に付与する。第2層目を図3の左上側の第2レイヤモジュールとする。第1層目は図3の左下側の第2レイヤモジュールを第2層目となる左上側の第2レイヤモジュールとの境界線にそってその下側に折畳んだときのモジュール番号の配置となる。第3層目は図3の右上側の第2レイヤモジュールを第2層目となる左上側の第2レイヤモジュールとの境界線にそってその上側に折畳んだときのモジュール番号の配置となる。第4層目は図3の右下側の第2レイヤモジュールを第3層目となる右上側の第2レイヤモジュールと共に第2層目となる左上側の第2レイヤモジュールの上に折畳んだ後にさらに右上側の第2レイヤモジュールとの境界線にそってその上側に折畳んだときのモジュール番号の配置となる。このように4つの第2レイヤモジュールを積層して第3レイヤモジュールを構成する。
【0072】
Red Tree系で第2レイヤモジュールは4つ、第3レイヤモジュールは1つである。ランク2ルータとランク1ルータを接続する配線はチップ内で接続され、ランク3ルータとランク2ルータを接続する配線は主としてチップ間を繋ぐ垂直方向配線で接続される(同層内では面内配線接続される)。ランク3ルータはRed Tree系では第3層目の第2レイヤモジュールを搭載するチップの中央に配置される。これらの配線構造は第1の実施の形態におけるFat Treeトポロジとほぼ同じであるが、ランク2ルータが二重化されず各チップに1個、合計4個である点、ランク3ルータが上記のように合計1個である点と、これらに伴い、これらランク3ルータとラン2クルータを繋ぐ配線の本数が異なる。
【0073】
図20に64コアFat H−Treeを4分割した時のBlack Treeの3次元レイアウトを示す。これは図4のBlack Treeのモジュール配置とモジュール間の配線接続構造を4つのチップに分割した時のレイアウトを示すもので、(a)は第1層目のチップのレイアウト、(b)は第2層目のチップのレイアウト、(c)は第3層目のチップのレイアウト、(d)は第4層目のチップのレイアウトを示す。4つのチップの積層の仕方は図19のRed Treeと同じであり、したがって、各層のチップのモジュールの配置は図19のRed Treeと同様であり、そして配線接続構造は図4のモジュール間の配線接続構造を採用している。
【0074】
この結果、例えば、第1層目のチップでは、Red Treeの場合に比して第1レイヤモジュール、第2レイヤモジュールが上方向及び右方向にそれぞれ1モジュール分ずれ、ランク1ルータ、ランク2ルータも上方向及び右方向にそれぞれ1モジュール分ずれる。そして、4つのモジュール41,42,49,50からなる第1レイヤモジュールは第1層目のチップ内に存在するが、4つのモジュール43,44,51,52からなる第1レイヤモジュールは第1層目に43,51、第4層目に44,52と2層のチップにまたがり、ランク1ルータからこれらのモジュールを接続する配線は2つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第1層目と第4層目で垂直方向に重なった位置にあり、1束の垂直方向配線で接続可能である。また、4つのモジュール1,2,57,58からなる第1レイヤモジュールは第1層目に57,58、第2層目に1,2と2層のチップにまたがり、ランク1ルータからこれらのモジュールを接続する配線は2つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第1層目と第2層目で垂直方向に重なった位置にあり、1束の垂直方向配線で接続可能である。また、4つのモジュール3,4,59,60からなる第1レイヤモジュールは第1層目に59,第2層目に3、第3層目に4,第4層目に60と4層のチップにまたがり、ランク1ルータからこれらのモジュールを接続する配線は4つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第1層目から第4層目まで垂直方向に重なった位置にあり、1束の垂直方向配線で接続可能である。このような垂直方向配線も貫通ビアを使用できる。
【0075】
また、第2層目のチップでは、Red Treeの場合に比して第1レイヤモジュール、第2レイヤモジュールが下方向及び右方向にそれぞれ1モジュール分ずれ、ランク1ルータ、ランク2ルータも下方向及び右方向にそれぞれ1モジュール分ずれ、配線についても第1層目と類似の関係が存在する。また、第3層目のチップでは、Red Treeの場合に比して第1レイヤモジュール、第2レイヤモジュールが下方向及び左方向にそれぞれ1モジュール分ずれ、ランク1ルータ、ランク2ルータも下方向及び左方向にそれぞれ1モジュール分ずれ、配線についても第1層目と類似の関係が存在する。また、第4層目のチップでは、Red Treeの場合に比して第1レイヤモジュール、第2レイヤモジュールが上方向及び左方向にそれぞれ1モジュール分ずれ、ランク1ルータ、ランク2ルータも上方向及び左方向にそれぞれ1モジュール分ずれ、配線についても第1層目と類似の関係が存在する。なお、図20中の端部にある各ランク1ルータには接続されるモジュールの番号と( )内にそのモジュールが存在する層を示している。
【0076】
Black Tree系では、第2レイヤモジュールは4つ、第3レイヤモジュールは1つであり、ランク2ルータが各チップに1個、合計4個、ランク3ルータが合計1個である点はRed Treeの場合と同様であるが、ランク2ルータとランク3ルータの位置が異なる。各第2レイヤモジュールにおいて4つのランク1ルータに接続するランク2ルータは4つのランク1ルータの中央付近に配置され、ランク1ルータとランク2ルータを接続する配線は面内に布設される。また、第3レイヤモジュールにおいて4つのランク2ルータに接続するランク3ルータは第3層目のチップの中央に配置され、ランク2ルータとランク3ルータを接続する配線はチップ間では垂直方向配線となり、貫通ビア内にまとめて布設され、各チップ内で貫通ビアからランク2ルータまで面内配線で繋がれる。
【0077】
Fat H−TreeトポロジはRed TreeとBlack Treeと呼ばれる2つのH−Treeトポロジを組み合わせたトポロジである。したがって、その配線構造は両者の配線構造を合わせ持つ。しかし、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク2ルータとランク3ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。
【0078】
Fat H−Treeトポロジの配線レイアウトのアルゴリズムも大略は図14で表されるが、細部はFat Treeトポロジの場合と異なる。本実施の形態では64コア3階層Fat H−Treeのツリー構造配線レイアウトについて説明する。まず、ファットエイチツリートポロジを二次元集積電気回路モジュールに相当するチップ対応に分割する(ツリー分割工程:S10)。ここでは4分割する。
【0079】
次に三次元集積電気回路を二次元平面に展開した状態で、電気回路モジュール(コア)と交換接続手段(ルータ)の配置を行なう(ノードマッピング工程:S20)。コアの配置はFat Treeの場合と同様である。他方、ルータの配置はRed TreeではFat Treeの場合と同様であるが、Black TreeではFat Treeに対し1モジュール分下方及び右側に循環シフトしている。また、Red Tree内、Black Tree内では配線の多重化はされていない。
【0080】
次にノードマッピング工程で配置された三次元集積電気回路をツリー分割工程で分割した二次元集積電気回路モジュール(チップ)を積層するように折り畳む(折り畳み工程:S30)。折り畳み方はFat Treeの場合と同様である。従って、コアの配置はFat Treeの場合と同様である。他方、ルータの配置は図20に示すように、Red TreeではFat Treeの場合と同様であるが、Black TreeではFat Treeに対し1モジュール分、第1層目が右上に、第2層目が右下に、第3層目が左下に、第4層目が左上にシフトしている。また、第1レイヤモジュールが層間に亘るものがある。ランク2ルータは各チップにRed Treeで1つ、Black Treeで1つ、全体で8つである。ランク3ルータはRed Treeで第2層目中心に1つ、Black Treeで第3層目中心に1つ、全体で2つである。
【0081】
次に、折り畳み工程で各チップに配置された交換接続手段(ルータ)のうちチップ間に分散された上位ランクの交換接続手段(ルータ)間を垂直方向配線でリンクする(リンク工程:S40)。4チップの中心に貫通ビアを設け、各チップにおいて垂直方向から見てランク3ルータの周囲にランク2ルータを配置し、ランク3ルータとランク2ルータを配線接続する。2つのランク3ルータからは、それぞれ同層の1つランク2ルータには面内配線で接続され、他の3層のランク2ルータへは垂直方向配線で接続される。合計6本の垂直方向配線が1つの貫通ビア内に布設される。この場合に、例えば図17に示すように、8つのランク2ルータが垂直方向に重ならないように配置する。このようにするとランク3ルータから各ランク2ルータへの配線を交錯させずに直線的に形成できる。また、Black Tree内ではチップのエッジ部分においてラン13ルータとモジュールを接続するための8束の垂直方向配線が設けられる(図20参照)。
【0082】
[第5の実施の形態]
以上の実施形態では4分割Fat Treeトポロジの例を説明したが、第5の実施の形態では2分割Fat H−Treeトポロジの例について説明する。ここでは、64コア3階層のFat H−Treeトポロジを32コア2チップに分割する例を説明する。
【0083】
図21に、64コアFat H−Treeを2分割した時のRed Treeの3次元レイアウトの例を示す。図21(a)は第1層目のチップのレイアウト、図21(b)は第2層目のチップのレイアウトを示す。第1層目は図19における第1層目と第4層目のモジュールを合せて配置を変更したものであり、第2層目のモジュールは図19における第2層目と第3層目のモジュールを合せて配置を変更したものである。2分割の場合、横方向には分割しないので、横方向のモジュールの配置は初めから固定される。本実施の形態では第1層目は左から56,63,57,62,58,61,59,60の順序、第2層目は左から0,7,1,6,2,5,3,4の順序であり、この配置は図7のモジュールの配置と同様であり、図6の配置すなわち図19の配置と等価である。縦方向のモジュールの配置は図19の配置と同様である。ランク1ルータとモジュールを接続する配線の関係、ランク2ルータとランク1ルータを接続する配線の関係は第4の実施の形態と同様であり、このため、ランク1ルータの位置は横方向では第0行目と第1行目の間、第2行目と第3行目の間で、縦方向では第1、2、5,6列目の中央となり、ランク2ルータの位置はチップの中央付近となる。これらの配線はチップ内で接続される。ランク2ルータは二重化されず各チップに2個、合計4個である。ランク3ルータは全体に1個で第1層目のチップの中央となり、ランク3ルータから4個のランク2ルータを接続する4本の配線のうち、2本は同一層内の隣接するランク2ルータにチップ内で接続され、他の層のランク2ルータに到る2本はチップ間を繋ぐ垂直方向配線で接続される。なお、図21では各モジュールを正方形で示しているが、縦横比を2:1にするとチップは正方形となり、既存の製造ラインに適合するので好適である。
【0084】
図22に、64コアFat H−Treeを2分割した時のBlack Treeの3次元レイアウトの例を示す。図22(a)は第1層目のチップのレイアウト、図22(b)は第2層目のチップのレイアウトを示す。第1層目は図20における第1層目と第4層目のモジュールを合せて配置を変更したものであり、第2層目のモジュールは図20における第2層目と第3層目のモジュールを合せて配置を変更したものである。横方向のモジュールの配置は初めから固定され、第1層目は左から56,63,57,62,58,61,59,60の順序、第2層目は左から0,7,1,6,2,5,3,4の順序である。縦方向のモジュールの配置は図20の配置と同様である。ランク1ルータとモジュールを接続する配線の関係、ランク2ルータとランク1ルータを接続する配線の関係は第4の実施の形態と同様であり、このため、第1層目において、ランク1ルータの位置は横方向では第0行目の上端、第1行目と第2行目の間で、縦方向では第0列目と第1列目の間、第3列目の中央、第4列目の中央、第6列目と第7列目の間となり、ランク2ルータの位置は横方向では第2列目の右から1/4モジュールの位置、第5列目の左から1/4モジュールの位置、縦方向では第0行目と第1行目の間となる。第2層目において、ランク1ルータの位置は横方向では第1行目と第2行目の間、第3行目の下端で、縦方向では第0列目と第1列目の間、第3列目の中央、第4列目の中央、第6列目と第7列目の間となり、ランク2ルータの位置は横方向では第2列目の右から1/4モジュールの位置、第5列目の左から1/4モジュールの位置、縦方向では第第2行目と第3行目の間となる。
【0085】
4つのモジュール40,47,48,55からなる第1レイヤモジュールなどの4つの第1レイヤモジュールは第1層目のチップ内に存在し、4つのモジュール8,15,16,23からなる第1レイヤモジュールなどの4つの第1レイヤモジュールは第2層目のチップ内に存在するが、4つのモジュール0,7,56,63からなる第1レイヤモジュールは第1層目に56,63、第2層目に0,7と2層のチップにまたがり、4つのモジュール1,2,57,58からなる第1レイヤモジュールなどの他の7つの第1レイヤモジュールも2層のチップにまたがり、ランク1ルータからこれらのモジュールを接続する配線は2つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第1層目と第2層目で垂直方向に重なった位置にあり、それぞれ1束の垂直方向配線で接続可能である。このような垂直方向配線も貫通ビアを使用できる。ランク2ルータは二重化されず各チップに2個、合計4個であり、ランク2ルータとランク1ルータを接続する配線はチップ内で接続される。ランク3ルータは全体に1個で第3層目のチップの中央となり、ランク3ルータから4個のランク2ルータを接続する4本の配線のうち、2本は同一層内のランク2ルータにチップ内で接続され、他の層のランク2ルータに到る2本はチップ間を繋ぐ垂直方向配線で他のチップに到り、そのチップ内でランク2ルータの位置まで延びる。なお、図22では各モジュールを正方形で示しているが、縦横比を2:1にするとチップは正方形となり、既存の製造ラインに適合するので好適である。
【0086】
Fat H−TreeトポロジはRed TreeとBlack Treeと呼ばれる2つのH−Treeトポロジを組み合わせたトポロジである。したがって、その配線構造は両者の配線構造を合わせ持つ。しかし、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク2ルータとランク3ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。なお、上記の説明は2分割Fat H−Treeトポロジの例であるが、2分割Fat Treeトポロジについても2分割Red Treeのランク1ルータからランク2ルータへの配線を二重化し、さらにランク2ルータからランク3ルータへの配線を二重化することにより実現可能であり、同様に、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク2ルータとランク3ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。
【0087】
次に2分割Fat H−Treeトポロジの配線レイアウトのアルゴリズムについて述べる。第4の実施の形態に比して階層は同じで、チップ数が半分になっている。ツリー分割工程(S10)では2チップに分割する。ノードマッピング工程(S20)は第4の実施の形態とほぼ同様であるが、レッドツリー系のランク2ルータはチップの中心付近に配置される。折り畳み工程(S30)については境界線が第3行目と第4行目の間の1本のみになる。リンク工程(S40)についてはランク2ルータとランク3ルータ間のリンクを2チップ間で行なうが、第4の実施の形態と同様にBlack Tree系ではランク2ルータの位置がシフトしており、また、第1レイヤモジュールが層間に亘るものがある。ランク2ルータは各チップにRed Treeで2つ、Black Treeで2つ、全体で8つである。ランク3ルータはRed Treeで第1層目中心に1つ、Black Treeで第2層目中心に1つ、全体で2つである。
【0088】
[第6の実施の形態]
以上の実施形態では二次元集積電気回路モジュール間の配線が貫通ビアを通して構成される例について説明したが、第6の実施の形態では二次元集積電気回路モジュール間の配線に無線配線を用いる例を説明する。例えば第1の実施の形態の配線構造において、貫通ビアを通る垂直方向配線に代えて無線通信で信号を伝達する。モジュール間での信号を伝達する配線だけでなく、各ランクのルータを制御する制御信号線、電源線についても無線配線で置換しても良い。この場合、チップすなわち二次元集積電気回路モジュールの二次元平面に垂直な方向にほぼ直線上に並べて無線送受信手段が配置される。チップ間の通信を行なうランク2ルータ及びランク3ルータに無線送受信手段として例えば各1個の無線送受信回路を用いても良く、各1個の無線送信回路及び無線受信回路を用いても良い。また、これら送信回路又は受信回路としてインダクターなどの電磁結合や容量結合を用いても良い。無線送受信手段を二次元平面に垂直な方向にほぼ直線上に並べるのは、チップ間で良好な無線通信が可能な送信手段と受信手段間の距離がμmオーダーの範囲では可能なのに対し、mmオーダー以上では困難だからである。したがって、チップ間配線に無線配線を用いる場合にも、モジュール、各ランクのルータの配置及びこれらの間の配線構造について、貫通ビアの場合と同じアルゴリズムを適用できる。また、配線レイアウトのアルゴリズムは第1の実施の形態の貫通ビアを無線配線に代えれば良い。
【0089】
なお、上記の説明は第1の実施の形態に無線配線を適用する例であるが、第2〜第5の実施の形態にも同様に無線配線を適用可能である。
【0090】
[評価]
次に、以上の実施の形態で説明した3−D Fat Tree および3−D Fat H−Treeについて、チップ面積,配線量,配線遅延,リピータ数,消費電力について評価する。これらの3次元レイアウトは2γ枚のチップ上に実現できるが,ここでは積層するチップ数を4層として評価する。
【0091】
(1)ルータのリンク数と個数
表1に、3−D Fat Treeおよび3−D Fat H−Treeトポロジで必要となるルータの個数を見積もった結果を示す。比較のため3−D Meshと3−D Torusの結果も示す。Fat H−Treeをはじめツリー系のトポロジでは3−D Meshや3−D Torusに比べてルータの数が少ない。また、表には示されていないが、ルータの最大リンク数はH−TreeとFat H−Treeで5個,Fat Treeで6個であるのに対し,3−D Meshと3−D Torusでは7個(xyz各方向に2個ずつに、(ローカル)コア(プロセッシングエレメント)へのリンクを含めて7個とした)となり、ルータ1個当たりの面積でもツリー系トポロジのほうが有利である。ただし,(2,4,2)Fat TreeとFat H−Treeでは各コアは2本のリンクを有するため、他のトポロジと比べネットワークインターフェイス(NI)の面積が増加する。
【0092】
【表1】
【0093】
(2)ルータとネットワークインターフェイス(NI)の面積
表2に3−D Fat Treeおよび3−D Fat H−Treeトポロジにおける、オンチップルータとNIからなる部分の面積(mm2)を示す。比較のため3−D Meshと3−D Torusにおける同部分の面積も示す。
【表2】
【0094】
なお、カッコ内の数字は2次元レイアウトからの増分を示すものである。この数字はツリー型トポロジでは貫通ビアのみの面積を表し、MeshやTorusでは3次元化に伴うルータ面積の増分と貫通ビアの面積を表す。この結果より、ツリー型トポロジでは、3次元化のための貫通ビアによって総面積が最大5.0%増加しているのに対し、MeshとTorusでは3次元化によってルータのリンク数が増えるため、面積がMeshで最大21.5%、Torusで最大47.3%増加しており、3次元化のオーバーヘッドが非常に大きいことが分かる。
【0095】
各トポロジの面積は次の手順で見積もった。(1)まず、Verilog−HDL(Hardware Description Language)で記述されたルータ回路とNI回路を組み合わせ対象トポロジを構築した。(2)次に、これを0.18μmスタンダードセルライブラリを用いてSynopsys社のDesign Compilerで合成することでNoCの面積を抽出した。(3)次に、各トポロジに含まれるチップ間リンクの数から貫通ビアの面積を計算し、NoCの面積に足し合わせた。ここにおいて、ルータ回路は4段のパイプラインステージから構成され,パイプラインステージごとに1−フリット(flit)分のリピータを有し、NI回路として2−flit分のFIFO(First In, First Out)を入力側と出力側にそれぞれ有するものとした。また、Fat H−Treeと(2,4,2)Fat Treeでは2ポートのNIが必要になる。とくにFat H−Treeでは,片方のポートからもう片方のポートへパケットを転送する機能が必要であり、このためにNI内に小さなマルチプレクサが実装されているものとした。貫通ビアのサイズはチップを重ね合わせるときのアライメントの精度によって制限され、一般的には1μm角〜10μm角となる。ここでは、1−ビット(bit)の単方向チップ間リンクが1枚のチップを貫通する度に、貫通ビアの面積として100μm2を加算した。
【0096】
(3)総配線長
表3にFat Tree及びFat H−Treeについて、2次元レイアウトにおける総配線長を示す。比較のため2−D Meshと2−D Torusにおける総配線長も示す。ここで、隣接コア間距離を1−ユニット(unit)とし、配線長をユニット数で表す。
【表3】
【0097】
階層数nのH−Treeの2次元レイアウトにおける総配線長L2D,htを式(3)で表す。
【数1】
ただし,lihtをH−Treeにおけるランクiルータからその4個の下位ルータへの総リンク長,rihtをランクiルータの数とする。コア数をN=2n×2nとすると、liht=2i+1,riht=N/4iとなる。したがって,式(3)は式(4)のように変形できる。
【数2】
同様にして,階層数nのFat H−Tree の2次元レイアウトにおける総配線長L2D,fhtを求める式は式(5)のように導びかれる。
【数3】
表3の見積りではMesh及びTorusのコア−ルータ間リンクの長さを無視しているものの、Fat H−Treeや(2,4,2)Fat Treeなどツリー型トポロジの総配線長が圧倒的に長く、これがツリー型トポロジの欠点になっていることが分かる。
【0098】
表4にFat Tree及びFat H−Treeについて、3次元レイアウトの総配線長L3D,htを示す。比較のため3−D Meshと3−D Torusにおける総配線長も示す。ここで、隣接コア間距離を1−unitとし、配線長をユニット数で表す。
【表4】
【0099】
3次元レイアウトではチップ間の距離は数十μm程度と、水平方向のリンク長に比べて圧倒的に短い。そのため、ここではチップ間リンクの長さは考慮しないものとする。まず、階層数nのH−Treeを3次元化したときの総配線長L3D,htを求める。チップの枚数は4枚なので、すべての最上位リンクが長さ0のチップ間リンクに置き換えられることになる。したがって、式(4)は3次元化によって式(6)のように変化する。
【数4】
【0100】
Fat H−Treeの場合はRed TreeとBlack Treeに分けて考える。Red TreeはH−Treeの3次元レイアウトと等価である(図9参照)。一方、Black Treeはこれに加え、最上位リンクの長さとしてそれぞれ2−unit必要となる(図10参照)。よって総配線長は式(7)のようになる。
【数5】
表4と表3を比較することにより、総配線長が3次元化によってどれだけ削減できるかが分かる。Fat TreeおよびFat H−Treeでは、3次元化によって総配線長が25.0%から最大50.0%削減できた。その結果、総配線長は、(2,4,2)Fat Treeを除き、3−D Torusと同程度かそれ以下に削減された。
【0101】
(4)消費電力
1−flitのデータを送信元から宛先ノードに転送するのに要する平均転送エネルギーは式(8)で計算できる。
Eflit=wHave(Esw+Elink) (8)
ただし、wを1−flitのビット数、Haveを平均ホップ数、Eswをルータが1−bitのデータ転送に消費するエネルギー、Elinkをリンクが1−bitのデータ転送に消費するエネルギーとする。(2)のルータとNIの面積において見積もったルータを、250MHzでの動作を仮定してゲートレベルでシミュレーションしたところ、Eswは1.13pJとなった。
【0102】
一方,Elinkは式(9)で計算できる。
Elink=dV2Cwire/2 (9)
ただし、dを1−hop当たりの平均距離(mm)、Vを動作電圧、Cwireを配線容量とする。ここではVを1.8Vとし、Cwireは0.18μmプロセスを仮定するとき414fF/mmとなった。チップサイズは12mm角とし、16コア、64コア、256コアの場合について、上記のパラメータをもとに転送エネルギーEflitを計算した。
【0103】
表5にリピータを挿入しないときの2次元レイアウトにおける1−flit当りの転送エネルギーEflit(pJ)を示す。
【表5】
【0104】
Fat H−Treeは畳み込みによって1−hop当たりの平均距離dが延びたが、平均ホップ数はこの中で最も小さく、消費電力においても有利となった。H−TreeやFat Treeはその次に平均ホップ数が小さいが、最上位リンクの利用率が高いため転送エネルギーはFat H−Treeよりも大きくなった。2−D Torusは畳み込みによって1−hop当たりの平均距離dが延びるため16コアでは2−D Meshより転送エネルギーが多い。一方,256コアではEswのウェイトが高くなり、平均ホップ数の小さい2−D Torusは2−D Meshより有利になっている。
【0105】
チップサイズが12mm角のとき、ツリー型トポロジにおける最長配線長はコア数によらず常に6mmである。このときの配線遅延は715psecとなり、プロセスの微細化に伴いさらに深刻化すると考えられる。そこで、マイ達の計算式(Ho,R.,Mai,K.W.and Horowitz,M.A.:The Future of Wires,Proceedings of the IEEE,Vol.89,No.4, pp.490−504 (2001)参照)に基づきリピータを挿入し、配線遅延を441psecまで抑えることができたが、新たにリピータの消費電力を考慮する必要が生じた。
【0106】
表6にリピータを挿入したときの2次元レイアウトにおける1−flit当り転送エネルギーEflit(pJ)を示す。リピータは5mm以上のリンクに挿入するものとして計算した。
【表6】
【0107】
上記マイ達の文献の図10によれば、4mm以下の配線にリピータを挿入しても配線遅延の消費効果が小さいことが分かる。そこで消費電力の増加を少しでも抑えるため、リピータの挿入は5mm以上のリンクに制限した。
【0108】
ツリー系のトポロジの最長リンクには平均4.9個のリピータが挿入されたため,リピータを挿入しない表5と比べ、転送エネルギーが大幅に増加した。また、16コアの2−D Torusにおいては畳み込みにより一部のルータ−ルータ間リンクが5mmを越えたため、ツリー型トポロジと同様に転送エネルギーEflitが増加した。
【0109】
次に、3次元レイアウトにおける転送エネルギーEflitを計算する。非特許文献2によると貫通ビアの容量は4.34fFであり、本評価で仮定している配線10.5μm分の容量に相当し、水平方向の配線長に比べて十分小さい。そのためチップ間リンクで消費されるエネルギーは考慮しないものとする。
【0110】
表7に3次元レイアウトにおける転送エネルギーEflit(pJ)を示す。
【表7】
【0111】
3次元化レイアウトでは、どのトポロジにおいても5mmを越えるリンクが発生しなかったためリピータは不要となった。Fat Treeの転送エネルギーEflitは表5と比べて最大44.3%、表6と比べて最大59.7%削減された。同様にFat H−Treeの転送エネルギーEflitは表5と比べて最大32.8%、表6と比べて最大53.5%削減された。このように3次元化により、配線長およびリピータを減らすことができ、結果的に転送エネルギーを大幅に減らすことができた。
【0112】
以上説明したように、Fat Tree およびFat H−Treeの3次元レイアウトは、同サイズの2次元レイアウトに比べ、(1)配線長は25.0%から最大50.0%削減された、(2)配線遅延が小さくなり、挿入されるリピータ数を削減できた、(3)これにより、1フリット当りの転送エネツギーが最大59.7%削減された。なお、3次元化によってチップ面積が最大5.0%増加したが、メッシュの3次元化に比して十分低コストになっている。このように、本発明によれば、複数のモジュール間を接続する集積電気回路の配線構造において、適正なトポロジで3次元構造を実現することにより、2次元構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することができる。
【0113】
以上、本発明の実施の形態について説明したが、本発明は以上の実施の形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で実施の形態に種々変更を加えられることは明白である。
【0114】
例えば、以上の実施の形態では、三次元集積電気回路の配線構造に64コア又は256コアのFat Treeトポロジ、64コアのFat H−Treeトポロジを適用する例について説明したが、他の4nコア、2ν層のFat Treeトポロジ、Fat H−Treeトポロジにも適用可能であり、ルータの上向きリンク数p、ルータの下向きリンク数q、コアの上向きリンク数cの組み合わせについても特に制限はない。また、第1の実施の形態以外でも、交換接続手段を制御する制御信号線や電源線についてもチップ間に布設されるものは貫通ビア内に配置する構成としても良い。このように構成すると、制御系配線についても配線長を低減し、モジュール間の通信遅延を低減できる。また、以上の実施の形態では交換接続手段がルータである場合について説明したが、交換接続手段がクロスバスイッチ等の交換機のスイッチの場合についても同様に適用できる。また、以上の実施の形態では貫通ビアや無線配線が1箇所の例を主に説明したが、貫通ビアや無線配線を複数箇所に設けても良く、また、貫通ビアと無線配線とを併用しても良い。また、各電気回路領域は同一寸法の正方形又は長方形に限定されず、正三角形、正六角形や台形等の平面に隙間なく敷き詰められる形状であれば望ましいが、円形等隙間が生じる構造についても、Fat Treeトポロジ、Fat H−Treeトポロジを適用可能である。
【産業上の利用可能性】
【0115】
本発明はLSI、IC等の3次元配線に利用できる。
【図面の簡単な説明】
【0116】
【図1】リンク数が小さく対称な2次元レイアウトが可能なトポロジの代表例を示す図である。
【図2】64コアFat Treeのツリー構造の例を示す図である。
【図3】64コアRed Treeのツリー構造の例を示す図である。
【図4】64コアBlack Treeのツリー構造の例を示す図である。
【図5】Red Treeの座標とBlack Treeの座標の関係を示す図である。
【図6】64コアFat H−Treeの2次元レイアウトを示す図である。
【図7】畳み込み処理されたFat H−Treeの2次元レイアウトを示す図である。
【図8】Fat Treeを4分割した例を示す図である。
【図9】Red Treeを4分割した例を示す図である。
【図10】Black Treeを4分割した例を示す図である。
【図11】64コア3階層のFat Treeトポロジの例を示す図である。
【図12】64コアFat Treeトポロジを4つのチップに分割した構成を示す図である。
【図13】64コアFat Treeトポロジを4つのチップに分割し、積層したときの各ランクルータ配置とルータ間配線の3次元レイアウトの概要を示す図である。
【図14】Fat Treeトポロジ及びFat H−Treeの配線レイアウトのアルゴリズムの大略を示す図である。
【図15】コアのマッピングと折り畳みを説明するための図である。
【図16】16個のランク3ルータと8個のランク4ルータ間の配線のトポロジを示す図である。
【図17】各第3レイヤモジュールの3次元配置とランク3ルータ、ランク4ルータの配置の例を示す図である。
【図18】64コアFat H−Treeトポロジの例を示す図である。
【図19】64コアFat H−Treeを4分割した時のRed Treeの3次元レイアウトを示す図である。
【図20】64コアFat H−Treeを4分割した時のBlack Treeの3次元レイアウトを示す図である。
【図21】64コアFat H−Treeを2分割した時のRed Treeの3次元レイアウトの例を示す図である。
【図22】64コアFat H−Treeを2分割した時のBlack Treeの3次元レイアウトの例を示す図である。
【図23】2次元ICと3次元ICの比較を示す図である。
【符号の説明】
【0117】
i(i=1〜3) ランクiルータ
bi Black Treeのランクiルータの座標
B(b0,b1,…,bi,…,bn) Black Treeのルータの座標
(p,q,c) Fat Treeのリンク構成
p ルータの上向きリンク数
q ルータの下向きリンク数
c コアの上向きリンク数
ri Red Treeのランクiルータの座標
R(r0,r1,…,ri,…,rn) Red Treeのルータの座標
x2D,y2D,z2D コアの2次元座標
x3D,y3D,z3D コアの3次元座標
【特許請求の範囲】
【請求項1】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される;
三次元集積電気回路の配線構造。
【請求項2】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される;
三次元集積電気回路の配線構造。
【請求項3】
前記交換接続手段を制御する制御手段と前記交換接続手段と前記制御手段とを接続する制御信号線を備え;
前記二次元集積電気回路モジュール間に布設される制御信号線は貫通ビアを通して配線される;
請求項1又は請求項2に記載の三次元集積電気回路の配線構造。
【請求項4】
前記貫通ビアの少なくとも1つは前記二次元集積電気回路モジュールのほぼ中央を貫通する;
請求項1乃至請求項3のいずれか1項に記載の三次元集積電気回路の配線構造。
【請求項5】
各電気回路領域は同一寸法の正方形又は長方形である;
請求項1乃至請求項4のいずれか1項に記載の三次元集積電気回路の配線構造。
【請求項6】
下位の交換接続手段に繋がる上位の交換接続手段は2個または4個である;
請求項1に記載の三次元集積電気回路の配線構造。
【請求項7】
電気回路モジュールを二次元平面に2行2列に配置して第1レイヤモジュールを構成し;
第1レイヤモジュールを二次元平面に2行2列に配置して第2レイヤモジュールを構成し;
第m−1レイヤモジュールを二次元平面に2行2列に配置して第mレイヤモジュールを構成し;
第mレイヤモジュールを三次元空間に4層積層して第m+1レイヤモジュールを構成し;
第m+1レイヤモジュールを三次元空間に4層積層して第m+2レイヤモジュールを構成し;
第n−1レイヤモジュールを三次元空間に4層積層して第nレイヤモジュールを構成し(1<m<nとする);
4個の第1レイヤモジュールの面心付近に4つの電気回路領域と2つ又は4つの第2ランク交換接続手段に繋がる第1ランク交換接続手段を備え;
4個の第2レイヤモジュールの面心付近に4つの第1ランク交換接続手段と2つ又は4つの第3ランク交換接続手段に繋がる第2ランク交換接続手段を備え;
4個の第m−1レイヤモジュールの面心付近に4つの第m−2ランク交換接続手段と2つ又は4つの第mランク交換接続手段に繋がる第m−1ランク交換接続手段を備え;
4層の第mレイヤモジュールの各層に4つの第m−1ランク交換接続手段と2つ又は4つの第m+1ランク交換接続手段に繋がる第mランク交換接続手段を備え;
4層の第mレイヤモジュールを貫き4つの第mランク交換接続手段と第m+1ランク交換接続手段を繋ぐ第mの垂直方向配線を備え;
4層の第m+1レイヤモジュールの各層に4つの第mランク交換接続手段と2つ又は4つの第m+2ランク交換接続手段に繋がる第m+1ランク交換接続手段を備え;
4層の第m+1レイヤモジュールを貫き4つの第m+1ランク交換接続手段と第m+2ランク交換接続手段を繋ぐ第m+1の垂直方向配線を備え;
4層の第n−1レイヤモジュールの各層に4つの第n−2ランク交換接続手段と2つ又は4つの第nランク交換接続手段に繋がる第n−1ランク交換接続手段を備え;
4層の第n−1レイヤモジュールを貫き4つの第n−1ランク交換接続手段と第nランク交換接続手段を繋ぐ第n−1の垂直方向配線を備える;
請求項1に記載の三次元集積電気回路の配線構造。
【請求項8】
電気回路モジュールを二次元平面に2行2列に配置して第1レイヤモジュールを構成し;
第1レイヤモジュールを二次元平面に2行2列に配置して第2レイヤモジュールを構成し;
第m−1レイヤモジュールを二次元平面に2行2列に配置して第mレイヤモジュールを構成し;
4個の第1レイヤモジュールの面心付近に4つの電気回路領域と1つの第2ランク交換接続手段に繋がる第1ランク交換接続手段を備え;
4個の第2レイヤモジュールの面心付近に4つの第1ランク交換接続手段と1つの第3ランク交換接続手段に繋がる第2ランク交換接続手段を備え;
4個の第m−1レイヤモジュールの面心付近に4つの第m−2ランク交換接続手段と1つの第mランク交換接続手段に繋がる第m−1ランク交換接続手段を備え;
前記全ての第1ランク交換接続手段乃至第m−1ランク交換接続手段を右方向及び下方向に1モジュールずつ循環シフトした位置に第1ランク交換接続手段乃至第m−1ランク交換接続手段を備え;
第mレイヤモジュールを三次元空間に4層積層して第m+1レイヤモジュールを構成し;
第m+1レイヤモジュールを三次元空間に4層積層して第m+2レイヤモジュールを構成し;
第n−1レイヤモジュールを三次元空間に4層積層して第nレイヤモジュールを構成し(1<m<nとする);
4層の第mレイヤモジュールの重心付近の第m−1レイヤモジュールに4つの第m−1ランク交換接続手段と1つの第m+1ランク交換接続手段に繋がる第mランク交換接続手段を備え;
4層の第mレイヤモジュールを貫き4つの第mランク交換接続手段と第m+1ランク交換接続手段を繋ぐ第mの垂直方向配線を備え;
4層の第m+1レイヤモジュールの重心付近の第mレイヤモジュールに4つの第mランク交換接続手段と1つの第m+2ランク交換接続手段に繋がる第m+1ランク交換接続手段を備え;
4層の第m+1レイヤモジュールを貫き4つの第m+1ランク交換接続手段と第m+2ランク交換接続手段を繋ぐ第m+1の垂直方向配線を備え;
4層の第n−1レイヤモジュールの重心付近の第n−2レイヤモジュールに4つの第n−2ランク交換接続手段と1つの第nランク交換接続手段に繋がる第n−1ランク交換接続手段を備え;
4層の第n−1レイヤモジュールを貫き4つの第n−1ランク交換接続手段と第nランク交換接続手段を繋ぐ第n−1の垂直方向配線を備え;
前記第mレイヤモジュール乃至前記第nレイヤモジュール内の電気回路モジュールの配置は第nレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし;
前記全ての第1ランク交換接続手段乃至第m−1ランク交換接続手段を右方向及び下方向に1モジュールずつ循環シフトした位置に配置された第1ランク交換接続手段乃至第m−1ランク交換接続手段については、前記第mレイヤモジュール乃至前記第nレイヤモジュール内の電気回路モジュールの配置を第nレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし;
同一の第1レイヤモジュールに属する電気回路モジュールで第1ランク交換接続手段と異なる二次元平面に配置されたものと前記第1ランク交換接続手段を繋ぐ第1の垂直方向配線を備え;
前記再配置した第mレイヤモジュール乃至第nレイヤモジュールにおいても前記第mランク交換接続手段乃至前記第nランク交換接続手段と同様の接続関係を有する;
請求項2に記載の三次元集積電気回路の配線構造。
【請求項9】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される;
三次元集積電気回路の配線構造。
【請求項10】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジで構成される;
三次元集積電気回路の配線構造。
【請求項11】
前記電気回路モジュールは空モジュールを含む;
請求項1乃至請求項10のいずれか1項に記載の三次元集積電気回路の配線構造。
【請求項12】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される;
三次元集積電気回路の配線構造のレイアウト方法であって;
前記ファットツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程と;
前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程と;
前記ノードマッピング工程で配置された前記三次元集積電気回路を前記ツリー分割工程で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程と;
前記折り畳み工程で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクするリンク工程とを備える;
三次元集積電気回路の配線構造のレイアウト方法。
【請求項13】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される;
三次元集積電気回路の配線構造のレイアウト方法であって;
前記ファットエイチツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程と;
前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程と;
前記ノードマッピング工程で配置された前記三次元集積電気回路を前記ツリー分割工程で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程と;
前記折り畳み工程で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクするリンク工程とを備える;
三次元集積電気回路の配線構造のレイアウト方法。
【請求項14】
請求項12又は請求項13に記載の三次元集積電気回路の配線構造のレイアウト方法をコンピュータに実行させるためのコンピュータ読み取り可能なプログラム。
【請求項1】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される;
三次元集積電気回路の配線構造。
【請求項2】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される;
三次元集積電気回路の配線構造。
【請求項3】
前記交換接続手段を制御する制御手段と前記交換接続手段と前記制御手段とを接続する制御信号線を備え;
前記二次元集積電気回路モジュール間に布設される制御信号線は貫通ビアを通して配線される;
請求項1又は請求項2に記載の三次元集積電気回路の配線構造。
【請求項4】
前記貫通ビアの少なくとも1つは前記二次元集積電気回路モジュールのほぼ中央を貫通する;
請求項1乃至請求項3のいずれか1項に記載の三次元集積電気回路の配線構造。
【請求項5】
各電気回路領域は同一寸法の正方形又は長方形である;
請求項1乃至請求項4のいずれか1項に記載の三次元集積電気回路の配線構造。
【請求項6】
下位の交換接続手段に繋がる上位の交換接続手段は2個または4個である;
請求項1に記載の三次元集積電気回路の配線構造。
【請求項7】
電気回路モジュールを二次元平面に2行2列に配置して第1レイヤモジュールを構成し;
第1レイヤモジュールを二次元平面に2行2列に配置して第2レイヤモジュールを構成し;
第m−1レイヤモジュールを二次元平面に2行2列に配置して第mレイヤモジュールを構成し;
第mレイヤモジュールを三次元空間に4層積層して第m+1レイヤモジュールを構成し;
第m+1レイヤモジュールを三次元空間に4層積層して第m+2レイヤモジュールを構成し;
第n−1レイヤモジュールを三次元空間に4層積層して第nレイヤモジュールを構成し(1<m<nとする);
4個の第1レイヤモジュールの面心付近に4つの電気回路領域と2つ又は4つの第2ランク交換接続手段に繋がる第1ランク交換接続手段を備え;
4個の第2レイヤモジュールの面心付近に4つの第1ランク交換接続手段と2つ又は4つの第3ランク交換接続手段に繋がる第2ランク交換接続手段を備え;
4個の第m−1レイヤモジュールの面心付近に4つの第m−2ランク交換接続手段と2つ又は4つの第mランク交換接続手段に繋がる第m−1ランク交換接続手段を備え;
4層の第mレイヤモジュールの各層に4つの第m−1ランク交換接続手段と2つ又は4つの第m+1ランク交換接続手段に繋がる第mランク交換接続手段を備え;
4層の第mレイヤモジュールを貫き4つの第mランク交換接続手段と第m+1ランク交換接続手段を繋ぐ第mの垂直方向配線を備え;
4層の第m+1レイヤモジュールの各層に4つの第mランク交換接続手段と2つ又は4つの第m+2ランク交換接続手段に繋がる第m+1ランク交換接続手段を備え;
4層の第m+1レイヤモジュールを貫き4つの第m+1ランク交換接続手段と第m+2ランク交換接続手段を繋ぐ第m+1の垂直方向配線を備え;
4層の第n−1レイヤモジュールの各層に4つの第n−2ランク交換接続手段と2つ又は4つの第nランク交換接続手段に繋がる第n−1ランク交換接続手段を備え;
4層の第n−1レイヤモジュールを貫き4つの第n−1ランク交換接続手段と第nランク交換接続手段を繋ぐ第n−1の垂直方向配線を備える;
請求項1に記載の三次元集積電気回路の配線構造。
【請求項8】
電気回路モジュールを二次元平面に2行2列に配置して第1レイヤモジュールを構成し;
第1レイヤモジュールを二次元平面に2行2列に配置して第2レイヤモジュールを構成し;
第m−1レイヤモジュールを二次元平面に2行2列に配置して第mレイヤモジュールを構成し;
4個の第1レイヤモジュールの面心付近に4つの電気回路領域と1つの第2ランク交換接続手段に繋がる第1ランク交換接続手段を備え;
4個の第2レイヤモジュールの面心付近に4つの第1ランク交換接続手段と1つの第3ランク交換接続手段に繋がる第2ランク交換接続手段を備え;
4個の第m−1レイヤモジュールの面心付近に4つの第m−2ランク交換接続手段と1つの第mランク交換接続手段に繋がる第m−1ランク交換接続手段を備え;
前記全ての第1ランク交換接続手段乃至第m−1ランク交換接続手段を右方向及び下方向に1モジュールずつ循環シフトした位置に第1ランク交換接続手段乃至第m−1ランク交換接続手段を備え;
第mレイヤモジュールを三次元空間に4層積層して第m+1レイヤモジュールを構成し;
第m+1レイヤモジュールを三次元空間に4層積層して第m+2レイヤモジュールを構成し;
第n−1レイヤモジュールを三次元空間に4層積層して第nレイヤモジュールを構成し(1<m<nとする);
4層の第mレイヤモジュールの重心付近の第m−1レイヤモジュールに4つの第m−1ランク交換接続手段と1つの第m+1ランク交換接続手段に繋がる第mランク交換接続手段を備え;
4層の第mレイヤモジュールを貫き4つの第mランク交換接続手段と第m+1ランク交換接続手段を繋ぐ第mの垂直方向配線を備え;
4層の第m+1レイヤモジュールの重心付近の第mレイヤモジュールに4つの第mランク交換接続手段と1つの第m+2ランク交換接続手段に繋がる第m+1ランク交換接続手段を備え;
4層の第m+1レイヤモジュールを貫き4つの第m+1ランク交換接続手段と第m+2ランク交換接続手段を繋ぐ第m+1の垂直方向配線を備え;
4層の第n−1レイヤモジュールの重心付近の第n−2レイヤモジュールに4つの第n−2ランク交換接続手段と1つの第nランク交換接続手段に繋がる第n−1ランク交換接続手段を備え;
4層の第n−1レイヤモジュールを貫き4つの第n−1ランク交換接続手段と第nランク交換接続手段を繋ぐ第n−1の垂直方向配線を備え;
前記第mレイヤモジュール乃至前記第nレイヤモジュール内の電気回路モジュールの配置は第nレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし;
前記全ての第1ランク交換接続手段乃至第m−1ランク交換接続手段を右方向及び下方向に1モジュールずつ循環シフトした位置に配置された第1ランク交換接続手段乃至第m−1ランク交換接続手段については、前記第mレイヤモジュール乃至前記第nレイヤモジュール内の電気回路モジュールの配置を第nレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし;
同一の第1レイヤモジュールに属する電気回路モジュールで第1ランク交換接続手段と異なる二次元平面に配置されたものと前記第1ランク交換接続手段を繋ぐ第1の垂直方向配線を備え;
前記再配置した第mレイヤモジュール乃至第nレイヤモジュールにおいても前記第mランク交換接続手段乃至前記第nランク交換接続手段と同様の接続関係を有する;
請求項2に記載の三次元集積電気回路の配線構造。
【請求項9】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される;
三次元集積電気回路の配線構造。
【請求項10】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジで構成される;
三次元集積電気回路の配線構造。
【請求項11】
前記電気回路モジュールは空モジュールを含む;
請求項1乃至請求項10のいずれか1項に記載の三次元集積電気回路の配線構造。
【請求項12】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される;
三次元集積電気回路の配線構造のレイアウト方法であって;
前記ファットツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程と;
前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程と;
前記ノードマッピング工程で配置された前記三次元集積電気回路を前記ツリー分割工程で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程と;
前記折り畳み工程で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクするリンク工程とを備える;
三次元集積電気回路の配線構造のレイアウト方法。
【請求項13】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって;
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され;
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される;
三次元集積電気回路の配線構造のレイアウト方法であって;
前記ファットエイチツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程と;
前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程と;
前記ノードマッピング工程で配置された前記三次元集積電気回路を前記ツリー分割工程で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程と;
前記折り畳み工程で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクするリンク工程とを備える;
三次元集積電気回路の配線構造のレイアウト方法。
【請求項14】
請求項12又は請求項13に記載の三次元集積電気回路の配線構造のレイアウト方法をコンピュータに実行させるためのコンピュータ読み取り可能なプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【公開番号】特開2008−282108(P2008−282108A)
【公開日】平成20年11月20日(2008.11.20)
【国際特許分類】
【出願番号】特願2007−123980(P2007−123980)
【出願日】平成19年5月8日(2007.5.8)
【新規性喪失の例外の表示】特許法第30条第1項適用申請有り 社団法人情報処理学会、「情報処理学会研究報告」、第2007巻、第4号、平成19年1月22日発行
【出願人】(504202472)大学共同利用機関法人情報・システム研究機構 (119)
【Fターム(参考)】
【公開日】平成20年11月20日(2008.11.20)
【国際特許分類】
【出願日】平成19年5月8日(2007.5.8)
【新規性喪失の例外の表示】特許法第30条第1項適用申請有り 社団法人情報処理学会、「情報処理学会研究報告」、第2007巻、第4号、平成19年1月22日発行
【出願人】(504202472)大学共同利用機関法人情報・システム研究機構 (119)
【Fターム(参考)】
[ Back to top ]