(57)【要約】【課題】複数のモジュール間を３次元的に接続する３次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減する。【解決手段】本発明による三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は前記二次元集積電気回路モジュールのほぼ中央を貫通する貫通ビアを通して構成され、前記電気回路モジュール及び前記交換接続手段とを接続する配線構成をＦａｔ  Ｔｒｅｅトポロジ又はＦａｔ  Ｈ−Ｔｒｅｅトポロジを用いて構成される。【選択図】図１３
2008282108.tif 000002
【特許請求の範囲】
【請求項１】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって；
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され；
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される；
三次元集積電気回路の配線構造。
【請求項２】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって；
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され；
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される；
三次元集積電気回路の配線構造。
【請求項３】
前記交換接続手段を制御する制御手段と前記交換接続手段と前記制御手段とを接続する制御信号線を備え；
前記二次元集積電気回路モジュール間に布設される制御信号線は貫通ビアを通して配線される；
請求項１又は請求項２に記載の三次元集積電気回路の配線構造。
【請求項４】
前記貫通ビアの少なくとも１つは前記二次元集積電気回路モジュールのほぼ中央を貫通する；
請求項１乃至請求項３のいずれか１項に記載の三次元集積電気回路の配線構造。
【請求項５】
各電気回路領域は同一寸法の正方形又は長方形である；
請求項１乃至請求項４のいずれか１項に記載の三次元集積電気回路の配線構造。
【請求項６】
下位の交換接続手段に繋がる上位の交換接続手段は２個または４個である；
請求項１に記載の三次元集積電気回路の配線構造。
【請求項７】
電気回路モジュールを二次元平面に２行２列に配置して第１レイヤモジュールを構成し；
第１レイヤモジュールを二次元平面に２行２列に配置して第２レイヤモジュールを構成し；
第ｍ−１レイヤモジュールを二次元平面に２行２列に配置して第ｍレイヤモジュールを構成し；
第ｍレイヤモジュールを三次元空間に４層積層して第ｍ＋１レイヤモジュールを構成し；
第ｍ＋１レイヤモジュールを三次元空間に４層積層して第ｍ＋２レイヤモジュールを構成し；
第ｎ−１レイヤモジュールを三次元空間に４層積層して第ｎレイヤモジュールを構成し（１＜ｍ＜ｎとする）；
４個の第１レイヤモジュールの面心付近に４つの電気回路領域と２つ又は４つの第２ランク交換接続手段に繋がる第１ランク交換接続手段を備え；
４個の第２レイヤモジュールの面心付近に４つの第１ランク交換接続手段と２つ又は４つの第３ランク交換接続手段に繋がる第２ランク交換接続手段を備え；
４個の第ｍ−１レイヤモジュールの面心付近に４つの第ｍ−２ランク交換接続手段と２つ又は４つの第ｍランク交換接続手段に繋がる第ｍ−１ランク交換接続手段を備え；
４層の第ｍレイヤモジュールの各層に４つの第ｍ−１ランク交換接続手段と２つ又は４つの第ｍ＋１ランク交換接続手段に繋がる第ｍランク交換接続手段を備え；
４層の第ｍレイヤモジュールを貫き４つの第ｍランク交換接続手段と第ｍ＋１ランク交換接続手段を繋ぐ第ｍの垂直方向配線を備え；
４層の第ｍ＋１レイヤモジュールの各層に４つの第ｍランク交換接続手段と２つ又は４つの第ｍ＋２ランク交換接続手段に繋がる第ｍ＋１ランク交換接続手段を備え；
４層の第ｍ＋１レイヤモジュールを貫き４つの第ｍ＋１ランク交換接続手段と第ｍ＋２ランク交換接続手段を繋ぐ第ｍ＋１の垂直方向配線を備え；
４層の第ｎ−１レイヤモジュールの各層に４つの第ｎ−２ランク交換接続手段と２つ又は４つの第ｎランク交換接続手段に繋がる第ｎ−１ランク交換接続手段を備え；
４層の第ｎ−１レイヤモジュールを貫き４つの第ｎ−１ランク交換接続手段と第ｎランク交換接続手段を繋ぐ第ｎ−１の垂直方向配線を備える；
請求項１に記載の三次元集積電気回路の配線構造。
【請求項８】
電気回路モジュールを二次元平面に２行２列に配置して第１レイヤモジュールを構成し；
第１レイヤモジュールを二次元平面に２行２列に配置して第２レイヤモジュールを構成し；
第ｍ−１レイヤモジュールを二次元平面に２行２列に配置して第ｍレイヤモジュールを構成し；
４個の第１レイヤモジュールの面心付近に４つの電気回路領域と１つの第２ランク交換接続手段に繋がる第１ランク交換接続手段を備え；
４個の第２レイヤモジュールの面心付近に４つの第１ランク交換接続手段と１つの第３ランク交換接続手段に繋がる第２ランク交換接続手段を備え；
４個の第ｍ−１レイヤモジュールの面心付近に４つの第ｍ−２ランク交換接続手段と１つの第ｍランク交換接続手段に繋がる第ｍ−１ランク交換接続手段を備え；
前記全ての第１ランク交換接続手段乃至第ｍ−１ランク交換接続手段を右方向及び下方向に１モジュールずつ循環シフトした位置に第１ランク交換接続手段乃至第ｍ−１ランク交換接続手段を備え；
第ｍレイヤモジュールを三次元空間に４層積層して第ｍ＋１レイヤモジュールを構成し；
第ｍ＋１レイヤモジュールを三次元空間に４層積層して第ｍ＋２レイヤモジュールを構成し；
第ｎ−１レイヤモジュールを三次元空間に４層積層して第ｎレイヤモジュールを構成し（１＜ｍ＜ｎとする）；
４層の第ｍレイヤモジュールの重心付近の第ｍ−１レイヤモジュールに４つの第ｍ−１ランク交換接続手段と１つの第ｍ＋１ランク交換接続手段に繋がる第ｍランク交換接続手段を備え；
４層の第ｍレイヤモジュールを貫き４つの第ｍランク交換接続手段と第ｍ＋１ランク交換接続手段を繋ぐ第ｍの垂直方向配線を備え；
４層の第ｍ＋１レイヤモジュールの重心付近の第ｍレイヤモジュールに４つの第ｍランク交換接続手段と１つの第ｍ＋２ランク交換接続手段に繋がる第ｍ＋１ランク交換接続手段を備え；
４層の第ｍ＋１レイヤモジュールを貫き４つの第ｍ＋１ランク交換接続手段と第ｍ＋２ランク交換接続手段を繋ぐ第ｍ＋１の垂直方向配線を備え；
４層の第ｎ−１レイヤモジュールの重心付近の第ｎ−２レイヤモジュールに４つの第ｎ−２ランク交換接続手段と１つの第ｎランク交換接続手段に繋がる第ｎ−１ランク交換接続手段を備え；
４層の第ｎ−１レイヤモジュールを貫き４つの第ｎ−１ランク交換接続手段と第ｎランク交換接続手段を繋ぐ第ｎ−１の垂直方向配線を備え；
前記第ｍレイヤモジュール乃至前記第ｎレイヤモジュール内の電気回路モジュールの配置は第ｎレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし；
前記全ての第１ランク交換接続手段乃至第ｍ−１ランク交換接続手段を右方向及び下方向に１モジュールずつ循環シフトした位置に配置された第１ランク交換接続手段乃至第ｍ−１ランク交換接続手段については、前記第ｍレイヤモジュール乃至前記第ｎレイヤモジュール内の電気回路モジュールの配置を第ｎレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし；
同一の第１レイヤモジュールに属する電気回路モジュールで第１ランク交換接続手段と異なる二次元平面に配置されたものと前記第１ランク交換接続手段を繋ぐ第１の垂直方向配線を備え；
前記再配置した第ｍレイヤモジュール乃至第ｎレイヤモジュールにおいても前記第ｍランク交換接続手段乃至前記第ｎランク交換接続手段と同様の接続関係を有する；
請求項２に記載の三次元集積電気回路の配線構造。
【請求項９】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって；
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され；
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される；
三次元集積電気回路の配線構造。
【請求項１０】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって；
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され；
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジで構成される；
三次元集積電気回路の配線構造。
【請求項１１】
前記電気回路モジュールは空モジュールを含む；
請求項１乃至請求項１０のいずれか１項に記載の三次元集積電気回路の配線構造。
【請求項１２】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって；
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され；
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される；
三次元集積電気回路の配線構造のレイアウト方法であって；
前記ファットツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程と；
前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程と；
前記ノードマッピング工程で配置された前記三次元集積電気回路を前記ツリー分割工程で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程と；
前記折り畳み工程で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクするリンク工程とを備える；
三次元集積電気回路の配線構造のレイアウト方法。
【請求項１３】
複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって；
前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され；
前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される；
三次元集積電気回路の配線構造のレイアウト方法であって；
前記ファットエイチツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程と；
前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程と；
前記ノードマッピング工程で配置された前記三次元集積電気回路を前記ツリー分割工程で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程と；
前記折り畳み工程で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクするリンク工程とを備える；
三次元集積電気回路の配線構造のレイアウト方法。
【請求項１４】
請求項１２又は請求項１３に記載の三次元集積電気回路の配線構造のレイアウト方法をコンピュータに実行させるためのコンピュータ読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は三次元集積電気回路の配線構造及びそのレイアウト方法に関する。詳しくは、ツリー型のトポロジについて、垂直方向配線を用いて配線長を削減し、配線遅延を短縮可能とする三次元集積電気回路の配線構造及びそのレイアウト方法に関する。
【背景技術】
【０００２】
半導体技術の進歩により、単一チップ上にプロセッサやメモリ、入出力（Ｉ／Ｏ）インタフェースなど複数の設計モジュールをタイル状に実装できるようになった。このようなタイルアーキテクチャでは、タイルだけでなくタイル同士を結合するための配線ネットワークを含めてチップ上に（主として２次元チップ上に）構成するチップ上ネットワーク（Ｎｅｔｗｏｒｋ−ｏｎ−Ｃｈｉｐ、略してＮｏＣという。）トポロジが用いられ、そのネットワークトポロジはアプリケーションの性能と面積、消費電力を決定付ける一要素となっている。（非特許文献１参照）
【０００３】
近年注目を浴びているのが、チップの３次元化である。３次元集積回路（ＩＣ）は複数枚のウエハまたはダイを垂直方向に重ね合わせることで実現される。複数枚のチップを垂直方向に積み重ねることで、個々のチップの寸法を小さく抑えることができ、結果的に配線長および配線遅延を削減できる。（非特許文献２〜４参照）
【０００４】
図２３に２次元ＩＣと３次元ＩＣの比較を示す。図２３（ａ）は通常の２次元ＩＣを、図２３（ｂ）はそれと同面積の３次元ＩＣを示す。この３次元ＩＣでは４枚のチップを積層することにより、個々のチップの面積は１／４、チップの両端を結ぶ配線長は１／２に削減される。これに伴い配線遅延及び必要なリピータの数も削減される。
【０００５】
通常の２次元ＩＣにおいては２−Ｄメッシュ（Ｍｅｓｈ）や２−Ｄトーラス（Ｔｏｒｕｓ）などのグリッド型のトポロジが広く用いられている。３次元ＩＣを想定したＮｏＣの研究はまだ数が少ないが、３−Ｄ  Ｍｅｓｈや３−Ｄ  Ｔｏｒｕｓをベースにしたものがいくつか報告されている。これらは、通常の２次元ＮｏＣで広く用いられる２−Ｄ  Ｍｅｓｈや２−Ｄ  Ｔｏｒｕｓから容易に拡張できるという利点を持つ。
【０００６】
【非特許文献１】Ｄａｌｌｙ，Ｗ．Ｊ．ａｎｄ  Ｔｏｗｌｅｓ，Ｂ．：Ｒｏｕｔｅ  Ｐａｃｋｅｔｓ，Ｎｏｔ  Ｗｉｒｅｓ：Ｏｎ−Ｃｈｉｐ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ  Ｎｅｔｗｏｒｋｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３８ｔｈ  Ｄｅｓｉｇｎ  Ａｕｔｏｍａｔｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ，ｐｐ．  ６８４−６８９  （２００１）
【非特許文献２】Ｄａｖｉｓ，Ｗ．Ｒ．，Ｗｉｌｓｏｎ，Ｊ．，Ｍｉｃｋ，Ｓ．，Ｘｕ，Ｊ．，Ｈｕａ，Ｈ．，Ｍｉｎｅｏ，Ｃ．，Ｓｕｌｅ，Ａ．Ｍ．，Ｓｔｅｅｒ，Ｍ．ａｎｄ  Ｆｒａｎｚｏｎ，Ｐ．Ｄ．：Ｄｅｍｙｓｔｉｆｙｉｎｇ  ３Ｄ  ＩＣｓ：Ｔｈｅ  Ｐｒｏｓ  ａｎｄ  Ｃｏｎｓ  ｏｆ  Ｇｏｉｎｇ  Ｖｅｒｔｉｃａｌ，ＩＥＥＥ  Ｄｅｓｉｇｎ  ＆  Ｔｅｓｔ  ｏｆ  Ｃｏｍｐｕｔｅｒｓ，Ｖｏｌ．２２，Ｎｏ．６，ｐｐ．４９８−５１０  （２００５）
【非特許文献３】Ｌｉ，Ｆ．ａｎｄ  ｅｔ．ａｌ．：Ｄｅｓｉｇｎ  ａｎｄ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  ３Ｄ  Ｃｈｉｐ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ  Ｕｓｉｎｇ  Ｎｅｔｗｏｒｋ−ｉｎ−Ｍｅｍｏｒｙ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ，ｐｐ．１３０−１４１  （２００６）
【非特許文献４】Ｄａｓ，Ｓ．ａｎｄ  ｅｔ．ａｌ．：Ｔｅｃｈｎｏｌｏｇｙ，Ｐｅｒｆｏｒｍａｎｃｅ，ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ  ｏｆ  Ｔｈｒｅｅ−Ｄｅｍｅｎｓｉｏｎａｌ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｈｙｓｉｃａｌ  Ｄｅｓｉｇｎ，ｐｐ．１０８−１１５  （２００４）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、３−Ｄ  Ｍｅｓｈでは２−Ｄ  Ｍｅｓｈと比べ、オンチップルータのリンク数が４から６に増え、これに伴いオンチップルータのチャネルバッファおよびクロスバスイッチの面積が増加する、また、垂直方向のリンクは数十μｍ程度と非常に短いため、パケットが垂直方向に移動する度にルータでラッチする必要はない、すなわちラッチにより電力が余分に消費され遅延も生じるという欠点が指摘されており、ルータのハードウェア量の割りに得られるメリットは大きくない。
【０００８】
他方、ツリー型トポロジについては、上位リンクの配線長が長くなるため、リンクの配線長が均一なグリッド型トポロジに比べて、配線遅延やリピータ数、消費電力の点で不利となると考えられ、ＮｏＣへの適用がためらわれてきた。しかしながら、３次元化によって上位リンクの配線長を短くでき、上記弱点を克服できると考えられる。また、３次元ＩＣではグリッド型のトポロジに比して性能パフォーマンスが優ることが期待できる。
【０００９】
本発明は、複数のモジュール間を接続する集積電気回路の配線構造において、適正なツリー型トポロジで３次元構造を実現することにより、２次元配線構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するために本発明の第１の態様における三次元集積電気回路の配線構造は、例えば図８に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリー（Ｆａｔ  Ｔｒｅｅ）トポロジを用いて構成される。
【００１１】
ここにおいて、交換接続手段とはモジュールを１対多数又は多数対多数の接続が可能な接続手段をいい、ルータ、交換機のスイッチ等が該当する。また、Ｆａｔ  Ｔｒｅｅトポロジは例えば図１１のような電気回路モジュールと交換接続手段の配線接続関係を規定するトポロジであるが、交換接続手段の上向きリンク数ｐ、下向きリンク数ｑ及び電気回路モジュールの上向きリンク数ｃにより複数の態様があり、このような態様のＦａｔ  Ｔｒｅｅを（ｐ，ｑ，ｃ）Ｆａｔ  Ｔｒｅｅと称する。このように構成すると、複数のモジュール間を３次元的に接続する３次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【００１２】
上記課題を解決するために本発明の第２の態様における三次元集積電気回路の配線構造は、例えば図１９及び図２０に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリー（Ｆａｔ  Ｈ−Ｔｒｅｅ）トポロジを用いて構成される。
【００１３】
ここにおいてＦａｔ  Ｈ−Ｔｒｅｅトポロジは、Ｆａｔ  Ｔｒｅｅトポロジと同様に電気回路モジュールと交換接続手段の配線接続関係を規定するトポロジで、発明者達の提案による高パフォーマンスのトポロジである（松谷宏紀、鯉渕道紘、天野英晴：３次元ＩＣ向けＦａｔ  ＴｒｅｅベースＮｅｔｗｏｒｋ−ｏｎ−Ｃｈｉｐｓ、情報処理学会研究報告２００７−ＡＲＣ−１７１，２００７−ＥＭＢ−３，ｐ７５−８０，Ｊａｎ，２００７  及び、松谷宏紀、鯉渕道紘、天野英晴：チップ内ネットワークにおけるＦａｔ  Ｈ−Ｔｒｅｅトポロジの性能評価、情報処理学会研究報告２００６−ＡＲＣ−１６９，ｐ１０９−１１４，Ａｕｇ，２００６  参照）。このように構成すると、複数のモジュール間を３次元的に接続する３次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【００１４】
また、本発明の好ましい態様によれば、第１の態様又は第２の態様の三次元集積電気回路の配線構造において、前記交換接続手段を制御する制御手段と前記交換接続手段と前記制御手段とを接続する制御信号線を備え、前記二次元集積電気回路モジュール間に布設される制御信号線は貫通ビアを通して配線される。このように構成すると、制御系配線についても配線長を低減し、モジュール間の通信遅延を低減できる。
【００１５】
また、本発明の好ましい態様によれば、以上の態様の三次元集積電気回路の配線構造において、前記貫通ビアの少なくとも１つは前記二次元集積電気回路モジュールのほぼ中央を貫通する。ここにおいて、貫通ビアは二次元集積電気回路モジュールのほぼ中央を貫通するものに加え、別の位置にあっても良い。また、貫通ビアは連結する最下層の二次元集積電気回路モジュールについては配線接続できれば必ずしも貫通する必要はない。このように構成すると、垂直方向配線の配線長を低減でき、モジュール間の通信遅延を低減できる。
【００１６】
また、本発明の好ましい態様によれば、以上の態様の三次元集積電気回路の配線構造において、例えば図８に示すように、各電気回路領域は同一寸法の正方形又は長方形である。ここにおいて正方形又は長方形の辺の寸法や内角は設計誤差や製造ばらつきにより多少のばらつきが有っても良い。このように構成すると、電気回路モジュールを２次元平面内に無駄なく配置でき、また３次元の配線構造の設計も効率化できる。
【００１７】
また、本発明の好ましい態様によれば、第１の態様の三次元集積電気回路の配線構造において、例えば図８に示すように、下位の交換接続手段に繋がる上位の交換接続手段は２個または４個である。このように構成すると、モジュール間の接続パスを多重ルートにして通信トラヒックの集中を緩和できる。また、単一モジュールへの複数入力を要する演算、複数モジュールへの出力等を効率化できる。
【００１８】
また、本発明の好ましい態様によれば、第１の態様の三次元集積電気回路の配線構造において、例えば図８に示すように、電気回路モジュールを二次元平面に２行２列に配置して第１レイヤモジュールを構成し、第１レイヤモジュールを二次元平面に２行２列に配置して第２レイヤモジュールを構成し、第ｍ−１レイヤモジュールを二次元平面に２行２列に配置して第ｍレイヤモジュールを構成し、第ｍレイヤモジュールを三次元空間に４層積層して第ｍ＋１レイヤモジュールを構成し、第ｍ＋１レイヤモジュールを三次元空間に４層積層して第ｍ＋２レイヤモジュールを構成し、第ｎ−１レイヤモジュールを三次元空間に４層積層して第ｎレイヤモジュールを構成し（１＜ｍ＜ｎとする）、４個の第１レイヤモジュールの面心付近に４つの電気回路領域と２つ又は４つの第２ランク交換接続手段に繋がる第１ランク交換接続手段を備え、４個の第２レイヤモジュールの面心付近に４つの第１ランク交換接続手段と２つ又は４つの第３ランク交換接続手段に繋がる第２ランク交換接続手段を備え、４個の第ｍ−１レイヤモジュールの面心付近に４つの第ｍ−２ランク交換接続手段と２つ又は４つの第ｍランク交換接続手段に繋がる第ｍ−１ランク交換接続手段を備え、４層の第ｍレイヤモジュールの各層に４つの第ｍ−１ランク交換接続手段と２つ又は４つの第ｍ＋１ランク交換接続手段に繋がる第ｍランク交換接続手段を備え、４層の第ｍレイヤモジュールを貫き４つの第ｍランク交換接続手段と第ｍ＋１ランク交換接続手段を繋ぐ第ｍの垂直方向配線を備え、４層の第ｍ＋１レイヤモジュールの各層に４つの第ｍランク交換接続手段と２つ又は４つの第ｍ＋２ランク交換接続手段に繋がる第ｍ＋１ランク交換接続手段を備え、４層の第ｍ＋１レイヤモジュールを貫き４つの第ｍ＋１ランク交換接続手段と第ｍ＋２ランク交換接続手段を繋ぐ第ｍ＋１の垂直方向配線を備え、４層の第ｎ−１レイヤモジュールの各層に４つの第ｎ−２ランク交換接続手段と２つ又は４つの第ｎランク交換接続手段に繋がる第ｎ−１ランク交換接続手段を備え、４層の第ｎ−１レイヤモジュールを貫き４つの第ｎ−１ランク交換接続手段と第ｎランク交換接続手段を繋ぐ第ｎ−１の垂直方向配線を備える。
【００１９】
ここにおいて、レイヤモジュールの面心とは、当該レイヤモジュールが４個の下位のレイヤモジュール又は４個の電気回路モジュールで構成されている場合には、これら４個のモジュールの頂点が集まる位置をいう。また、ｍ及びｎは整数で、１＜ｍ＜ｎである。このように構成すると、３次元空間にＦａｔ  Ｔｒｅｅトポロジを適用した、配線遅延が低減された三次元集積電気回路を実現できる。
【００２０】
また、本発明の好ましい態様によれば、第２の態様の三次元集積電気回路の配線構造において、例えば図１９及び図２０に示すように、電気回路モジュールを二次元平面に２行２列に配置して第１レイヤモジュールを構成し、第１レイヤモジュールを二次元平面に２行２列に配置して第２レイヤモジュールを構成し、第ｍ−１レイヤモジュールを二次元平面に２行２列に配置して第ｍレイヤモジュールを構成し、４個の第１レイヤモジュールの面心付近に４つの電気回路領域と１つの第２ランク交換接続手段に繋がる第１ランク交換接続手段を備え、４個の第２レイヤモジュールの面心付近に４つの第１ランク交換接続手段と１つの第３ランク交換接続手段に繋がる第２ランク交換接続手段を備え、４個の第ｍ−１レイヤモジュールの面心付近に４つの第ｍ−２ランク交換接続手段と１つの第ｍランク交換接続手段に繋がる第ｍ−１ランク交換接続手段を備え、前記全ての第１ランク交換接続手段乃至第ｍ−１ランク交換接続手段を右方向及び下方向に１モジュールずつ循環シフトした位置に第１ランク交換接続手段乃至第ｍ−１ランク交換接続手段を備え、第ｍレイヤモジュールを三次元空間に４層積層して第ｍ＋１レイヤモジュールを構成し、第ｍ＋１レイヤモジュールを三次元空間に４層積層して第ｍ＋２レイヤモジュールを構成し、第ｎ−１レイヤモジュールを三次元空間に４層積層して第ｎレイヤモジュールを構成し（１＜ｍ＜ｎとする）、４層の第ｍレイヤモジュールの重心付近の第ｍ−１レイヤモジュールに４つの第ｍ−１ランク交換接続手段と１つの第ｍ＋１ランク交換接続手段に繋がる第ｍランク交換接続手段を備え、４層の第ｍレイヤモジュールを貫き４つの第ｍランク交換接続手段と第ｍ＋１ランク交換接続手段を繋ぐ第ｍの垂直方向配線を備え、４層の第ｍ＋１レイヤモジュールの重心付近の第ｍレイヤモジュールに４つの第ｍランク交換接続手段と１つの第ｍ＋２ランク交換接続手段に繋がる第ｍ＋１ランク交換接続手段を備え、４層の第ｍ＋１レイヤモジュールを貫き４つの第ｍ＋１ランク交換接続手段と第ｍ＋２ランク交換接続手段を繋ぐ第ｍ＋１の垂直方向配線を備え、４層の第ｎ−１レイヤモジュールの重心付近の第ｎ−２レイヤモジュールに４つの第ｎ−２ランク交換接続手段と１つの第ｎランク交換接続手段に繋がる第ｎ−１ランク交換接続手段を備え、４層の第ｎ−１レイヤモジュールを貫き４つの第ｎ−１ランク交換接続手段と第ｎランク交換接続手段を繋ぐ第ｎ−１の垂直方向配線を備え、前記第ｍレイヤモジュール乃至前記第ｎレイヤモジュール内の電気回路モジュールの配置は第ｎレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし、前記全ての第１ランク交換接続手段乃至第ｍ−１ランク交換接続手段を右方向及び下方向に１モジュールずつ循環シフトした位置に配置された第１ランク交換接続手段乃至第ｍ−１ランク交換接続手段については、前記第ｍレイヤモジュール乃至前記第ｎレイヤモジュール内の電気回路モジュールの配置を第ｎレイヤモジュールを二次元平面に展開配置したときの行列の並びを折畳んで積層した順序に再配置した構成とし、同一の第１レイヤモジュールに属する電気回路モジュールで第１ランク交換接続手段と異なる二次元平面に配置されたものと前記第１ランク交換接続手段を繋ぐ第１の垂直方向配線を備え、前記再配置した第ｍレイヤモジュール乃至第ｎレイヤモジュールにおいても前記第ｍランク交換接続手段乃至前記第ｎランク交換接続手段と同様の接続関係を有する。
【００２１】
ここにおいて、レイヤモジュールの重心付近とは、二次元平面での面心付近で、さらに三次元積層構造の垂直方向においても中心に近いことをいい、当該レイヤモジュールが４層の下位のレイヤモジュールで構成されている場合には、第２層目又は第３層目が該当する。この下位のレイヤモジュールがさらに下位の４層のレイヤモジュールで構成されている場合には、垂直方向においてできるだけ中心に近い１層に配置されるのが好ましい。このように構成すると、３次元空間にＦａｔ  Ｈ−Ｔｒｅｅトポロジを適用した、配線遅延が低減された三次元集積電気回路を実現できる。
【００２２】
上記課題を解決するために本発明の第３の態様における三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される。
【００２３】
ここにおいて、配線には無線による配線を含むものとする。また、無線送受信手段として一体化された送受信回路を用いても良く、個別の送信回路と受信回路とを用いても良い。このように構成すると、複数のモジュール間を３次元的に接続する３次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【００２４】
上記課題を解決するために本発明の第４態様における三次元集積電気回路の配線構造は、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向にほぼ直線上に並べて配置された無線送受信手段を介して構成され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される。
【００２５】
このように構成すると、複数のモジュール間を３次元的に接続する３次元集積電気回路の配線構造において、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減できる。
【００２６】
また、以上の態様の三次元集積電気回路の配線構造において、前記電気回路モジュールは空モジュールを含む。ここにおいて、空モジュールは電気回路を搭載していないモジュールであり、今後電気回路を搭載したモジュールに置換が予定されているものでも良く、本来電気回路が不要で空きスペースになっているものでも良い。このように構成すると、モジュール数（コア数）が４ｎ等に該当しない場合にも本発明の配線構造を適用できる。
【００２７】
上記課題を解決するために本発明の第１の態様における三次元集積電気回路の配線構造のレイアウト方法は、例えば図１４に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットツリートポロジを用いて構成される三次元集積電気回路の配線構造のレイアウト方法であって、前記ファットツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程（Ｓ１０）と、前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程（Ｓ２０）と、前記ノードマッピング工程（Ｓ２０）で配置された前記三次元集積電気回路を前記ツリー分割工程（Ｓ１０）で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程（Ｓ３０）と、前記折り畳み工程（Ｓ３０）で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクする垂直リンク工程（Ｓ４０）とを備える。このように構成すると、本発明の第１の態様における三次元集積電気回路の配線構造を効率的に実現できる。なお、第３の態様における三次元集積電気回路の配線構造については、垂直リンク工程（Ｓ４０）の貫通ビアを無線配線に代えることにより、同様に実現可能である。
【００２８】
上記課題を解決するために本発明の第２の態様における三次元集積電気回路の配線構造のレイアウト方法は、例えば図１４に示すように、複数の電気回路モジュールと、前記電気回路モジュールを相互に交換接続する交換接続手段と、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線とで構成される二次元集積電気回路モジュールを三次元的に積層して構成される三次元集積電気回路の配線構造であって、前記二次元集積電気回路モジュール間の配線は複数の前記二次元集積電気回路モジュールをその二次元平面に垂直な方向に貫通する貫通ビアを通して布設され、前記電気回路モジュールと前記交換接続手段とを接続する配線及び前記交換接続手段間を接続する配線はファットエイチツリートポロジを用いて構成される三次元集積電気回路の配線構造のレイアウト方法であって、前記ファットエイチツリートポロジを前記二次元集積電気回路モジュールに相当するチップ対応に分割するツリー分割工程（Ｓ１０）と、前記三次元集積電気回路を二次元平面に展開した状態で、前記電気回路モジュールと前記交換接続手段の配置を行なうノードマッピング工程（Ｓ２０）と、前記ノードマッピング工程（Ｓ２０）で配置された前記三次元集積電気回路を前記ツリー分割工程（Ｓ１０）で分割した前記二次元集積電気回路モジュールを積層するように折り畳む折り畳み工程（Ｓ３０）と、前記折り畳み工程（Ｓ３０）で各チップに配置された前記交換接続手段のうちチップ間に分散された上位ランクの交換接続手段間を垂直方向配線でリンクする垂直リンク工程（Ｓ４０）とを備える。このように構成すると、本発明の第１の態様における三次元集積電気回路の配線構造を効率的に実現できる。なお、第３の態様における三次元集積電気回路の配線構造については、垂直リンク工程（Ｓ４０）の貫通ビアを無線配線に代えることにより、同様に実現可能である。
【００２９】
また、本発明は、第１又は第２の態様の三次元集積電気回路の配線構造のレイアウト方法をコンピュータに実行させるためのコンピュータ読み取り可能なプログラムとして実現できる。
【発明の効果】
【００３０】
本発明によれば、複数のモジュール間を接続する集積電気回路の配線構造において、適正なツリー型トポロジで３次元構造を実現することにより、２次元構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することができる。
【発明を実施するための最良の形態】
【００３１】
［配線トポロジ］
以下に、図面に基づき本発明の実施の形態について説明する。まず、ＮｏＣで用いられる２次元及び３次元配線のトポロジについて説明する。
【００３２】
図１に、リンク数が小さく対称な２次元レイアウトが可能なトポロジの代表例を示す。図１（ａ）に２−Ｄ  Ｍｅｓｈ、図１（ｂ），（ｅ）に２−Ｄ  Ｔｏｒｕｓ、図１（ｃ）にエイチツリー（Ｈ−Ｔｒｅｅ）、図１（ｄ）にＦａｔ  Ｔｒｅｅのトポロジを示す。各トポロジにおいて、複数のルータが行列で配列され、四角はルータ、丸はコアをそれぞれ表す。図１（ａ）の２−Ｄ  Ｍｅｓｈは、隣り合うルータを格子状に配線したもので、Ｒａｗプロセッサ、Ｔｒｉｐｓプロセッサ、ストリーム処理向けＮｏＣであるａＳＯＣ（Ａｄａｐｔｉｖｅ  Ｓｙｓｔｅｍ  ｏｎ  ａ  Ｃｈｉｐ）、ｐｉｃｏＣｈｉｐ社の超並行処理プロセッサアレイなどに幅広い用途で用いられている。図１（ｅ）の２−Ｄ  Ｔｏｒｕｓは、２−Ｄ  Ｍｅｓｈの配線に加え、ネットワークの両端のコアを結ぶラップアラウンド（ｗｒａｐ−ａｒｏｕｎｄ）チャネルを有している。図１（ｂ）はこれを、チャネル長が均一になるようにコアの行、列を０，３，１，２の順に配置換えしたものである。２−Ｄ  ＴｏｒｕｓはＩＭＥＣ社のＮｏＣなどで用いられている。図１（ｃ）のＨ−Ｔｒｅｅは、４分木配線構造を取る。すなわち、４個のコアをレベル１ルータで交換接続し、さらに４個のレベル１ルータをレベル２ルータで交換接続し、ツリー構造で通信対象を拡大する方式である。このため、２次元平面実装に適しているが、トラフィックがツリーの上位のルータ付近に集中しやすいという問題がある。Ｈ−Ｔｒｅｅはアンドレ・デホン（Ａｎｄｒｅ  Ｄｅｈｏｎ）らが提案した計算システムＳＣＯＲＥ（Ｓｔｒｅａｍ  Ｃｏｍｐｕｔａｔｉｏｎｓ  Ｏｒｇａｎｉｚｅｄ  ｆｏｒ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｅｘｅｃｕｔｉｏｎ）やＱｕｉｃｋＳｉｌｖｅｒ社のＡＣＭ（Ａｄａｐｔｉｖｅ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅ）などのリコンフィギャラブルシステムで利用されている。
【００３３】
次に、本発明の３次元配線に適用するトポロジであるＦａｔ  Ｔｒｅｅについて説明する。図１（ｄ）のＦａｔ  ＴｒｅｅはＨ−Ｔｒｅｅにおけるツリー構造を多重化したものであるが、ルータの上向きリンク数ｐ、下向きリンク数ｑ、コアの上向きリンク数ｃの組み合わせがあり、これを（ｐ，ｑ，ｃ）で表わす。図１（ｄ）のＦａｔ  Ｔｒｅｅは（２，４，２）Ｆａｔ  Ｔｒｅｅと表わされる。Ｈ−Ｔｒｅｅに比して多重化した上位ツリーにより経路分散が可能で、トラフィックの集中が緩和される。既存のＮｏＣへの適応例としてはＳＰＩＮなどがある。
【００３４】
これまで、ツリー型トポロジは、上位のルータ付近のリンクの長さが長くなるため配線遅延の点で不利である、すなわち、Ｆａｔ  Ｔｒｅｅでは最上位リンクの配線長が長くなり、このため、リンクの配線長が均一なグリッド型トポロジに比べて、配線遅延やリピータ数、消費電力の点で不利となると考えられてきたが、我々の検討結果、３次元化によってこの弱点を克服できることが分かった。ここでは、Ｆａｔ  Ｔｒｅｅおよび後述するＦａｔ  Ｈ−Ｔｒｅｅトポロジを用いて３次元ＮｏＣに適した配線構造を提案し、チップ面積、配線量、最長配線長、配線遅延、リピータ数、消費電力について評価する。モジュール間の相互接続トポロジとしてルータのリンク数を抑えつつ、一定の高い性能を実現するツリーの多重化を基にする。全体の配線長を短くするために３次元方向のルータ間の配線に貫通ビア等を用いるが、配線が交錯しないように、最上位ランクのルータの周りに次上下位レベルのルータを分散配置する。
【００３５】
図２に６４コアＦａｔ  Ｔｒｅｅのツリー構造の例を示す。６４コアをランク１ルータ（第１ランクルータのこと、以下第ｎランクルータをランクｎルータという）からランク３ルータを介して相互接続する階層構造である。四角の中の数字はルータのランク数である。ランク１ルータとランク２ルータ間の配線及びランク２ルータとランク３ルータ間の配線は２重化されており、ランク１ルータは４コアと２個のランク２ルータに、ランク２ルータは４個のランク１ルータと２個のランク３ルータに、ランク３ルータは４個のランク２ルータに接続される。
【００３６】
次に、本発明の他の３次元配線に適用するトポロジであるＦａｔ  Ｈ−Ｔｒｅｅについて説明する。Ｆａｔ  Ｈ−Ｔｒｅｅはレッドツリー（Ｒｅｄ  Ｔｒｅｅ）とブラックツリー（Ｂｌａｃｋ  Ｔｒｅｅ）と呼ばれる２つのＨ−Ｔｒｅｅを組み合わせたトポロジであり、トーラス構造を内包している。すなわち、Ｂｌａｃｋ  Ｔｒｅｅを介してネットワークの両端のコア（第０行と第７行、第０列と第７列）を結ぶラップアラウンドチャネルを有している。各コアは２つのリンクを有し、１つをＲｅｄ  Ｔｒｅｅとの接続に、他の１つをＢｌａｃｋ  Ｔｒｅｅとの接続に用いる。Ｆａｔ  Ｈ−ＴｒｅｅはＦａｔ  Ｔｒｅｅ  より構成が複雑であるが、コスト性能比で優れる。
【００３７】
図３に６４コアＲｅｄ  Ｔｒｅｅのツリー構造の例を示す。丸で描かれた各コアには２次元座標（ｘ，ｙ）がそれぞれ割り当てられる。以降、コアをランク０ルータとも呼ぶ。まず、ランク０ルータに対し式（１）で求まるＲｅｄ  Ｔｒｅｅ座標Ｒ（ｒ０，ｒ１，・・・，ｒｉ，・・・，ｒｎ−１）を割り当てる。ここで、ｉはランクを表す。
ｒｉ＝（（ｘ／２ｉ）ｍｏｄ２）＋２×（（ｙ／２ｉ）ｍｏｄ２）        （１）
Ｒｅｄ  Ｔｒｅｅ座標Ｒ（ｒ０，ｒ１，・・・，ｒｎ−１）となるランク０ルータの上位ルータをランク１ルータと呼び、Ｒ（ｒ１，・・・，ｒｎ−１）のＲｅｄ  Ｔｒｅｅ座標を割り当てる。同様の方法でランク２ルータからランクｎルータにもＲｅｄ  Ｔｒｅｅ座標を割り当てる。ただし、最上位ランク（ランクｎ）ルータのＲｅｄ  Ｔｒｅｅ座標をＲとする。また、任意のランクのルータに繋がる次位ランクのルータは４つずつになり、これらのルータに付する符号の順序は左上を０、右上を１、左下を２、右下を３とする。例として図中にランク３ルータＲ、ランク２ルータＲ（０）、ランク１ルータＲ（２，０）、コアＲ（２，２，０）の位置座標を示す。ここで、Ｒ（０）はランク３ルータＲにつながる４つのランク２ルータのうち左上のものを表し、Ｒ（２，０）はＲ（０）につながる４つのランク１ルータのうち左下のものを表し、Ｒ（２，２，０）はＲ（２，０）につながる４つのコアのうち左下のものを表す。
【００３８】
図４に６４コアＢｌａｃｋ  Ｔｒｅｅのツリー構造の例を示す。Ｂｌａｃｋ  ＴｒｅｅはＲｅｄ  Ｔｒｅｅの座標を右方向及び下方向に１コア分ずつずらしたものである。
【００３９】
図５にＲｅｄ  Ｔｒｅｅの座標とＢｌａｃｋ  Ｔｒｅｅの座標の関係を示す。Ｒｅｄ  Ｔｒｅｅのコア座標ＲｉはＢｌａｃｋ  Ｔｒｅｅのコア座標Ｂｉに移る。ルータおよび配線の座標も同様に右方向及び下方向に１コア分ずつずれる。さらに、Ｂｌａｃｋ  Ｔｒｅｅの７行目のコアは８行目、７列目のコアは８列目に移動するが、これを０行目、０列目に移動する。また、第７行７列目のコアは第８行８列目に移動するが、これを第０行０列目に移動する。このずれと移動を循環シフトと称することとする。このためランク０ルータのＢｌａｃｋ  Ｔｒｅｅ座標Ｂ（ｂ０，ｂ１，・・・，ｂｉ，・・・，ｂｎ−１）は式（２）で求まる。
ｂｉ＝（（（（ｘ−１）ｍｏｄ２ｎ）／２ｉ）ｍｏｄ２）＋２×（（（（ｙ−１）ｍｏｄ２ｎ）／２ｉ）ｍｏｄ２）          （２）
Ｂｌａｃｋ  Ｔｒｅｅにおいてもランク１ルータからランクｎルータにＢｌａｃｋ  Ｔｒｅｅ座標を割り当てる。最上位ランク（ランクｎ）ルータのＢｌａｃｋ  Ｔｒｅｅ座標をＢとする。また、任意のランクのルータに繋がる次位ランクのルータは４つずつになり、これらのルータに付する符号の順序は左上を０、右上を１、左下を２、右下を３とする。例として図中にランク３ルータＢ、ランク２ルータＢ（２）、ランク１ルータＢ（１，２）、コアＢ（０，１，２）の位置座標を示す。ここで、Ｂ（２）は４つのランク２ルータのうち左下のものを表し、Ｂ（１，２）はＢ（２）につながる４つのランク１ルータのうち右上のものを表し、Ｂ（０，１，２）はＲ（１，２）につながる４つのコアのうち左上のものを表す。
【００４０】
図６に６４コアＦａｔ  Ｈ−Ｔｒｅｅの２次元レイアウトを示す。各コア（ランク０ルータ）に対し、Ｒｅｄ  ＴｒｅｅおよびＢｌａｃｋ  Ｔｒｅｅを接続したものをＦａｔ  Ｈ−Ｔｒｅｅと称する。Ｆａｔ  Ｈ−Ｔｒｅｅにおいてはトーラス構造が形成される。すなわち、各コアはＲｅｄ  Ｔｒｅｅのランク１ルータおよびＢｌａｃｋ  Ｔｒｅｅのランク１ルータにつながり、コア−Ｒｅｄ  Ｔｒｅｅのランク１ルータ−コア−Ｂｌａｃｋ  Ｔｒｅｅのランク１ルータ−コアの順序でリンクが形成され、第０行目のコアと第７行目のコア、第０列目のコアと第７列目のコアはＢｌａｃｋ  Ｔｒｅｅのランク１ルータを介して接続され、ラップアラウンドチャネルが形成される。
【００４１】
図７に畳み込み処理されたＦａｔ  Ｈ−Ｔｒｅｅの２次元レイアウトを示す。Ｆａｔ  Ｈ−Ｔｒｅｅは、トーラス同様、畳み込むことで２次元チップ上に容易にレイアウトできる。畳み込みとは２次元平面の配置の仕方で、例えば行、列の配置を０，７，１，６，２，５，３，４のように並び換えるものである。図６において、配線接続関係を保ちながら、畳み込み処理により再配置したレイアウトが図７に相当し、図６と図７は等価なトポロジである。最上位リンクを除き、Ｆａｔ  Ｈ−Ｔｒｅｅの各リンクは畳み込みによって配線長が約２倍に延びるが、最上位リンクの配線長は大幅に短縮される。そのため、最上位の次のランクのリンク（第２位リンク）がＦａｔ  Ｈ−Ｔｒｅｅの最長配線となる。
【００４２】
次にＦａｔ  Ｔｒｅｅの３次元ＩＣ向けレイアウトについて説明する。Ｆａｔ  Ｔｒｅｅの弱点は、最上位リンク（ランク３ルータとランク２ルータ間の配線）の配線長が長くなることによる配線遅延の増加、リピータ数の増加、およびそれに伴う消費電力の増加である。これらの問題を同時に解決するために、図２で示したＦａｔ  Ｔｒｅｅを半分の寸法から成る４枚のチップに分割し、これらを３次元的に結合する。こうすることで、すべての最上位リンクは距離数十μｍ程度のチップ間リンクに置き換えられ、配線長の問題は解決される。
【００４３】
図８にＦａｔ  Ｔｒｅｅを４分割した例を示す。３−Ｄ（２，４，１）Ｆａｔ  Ｔｒｅｅの例である。Ｆａｔ  Ｔｒｅｅの４分割手順は次のとおりである。
（ステップ１：チップの分割）まず、チップの分割を行う。２次元Ｆａｔ  Ｔｒｅｅのコア座標（ｘ２Ｄ，ｙ２Ｄ）を、次のような３次元座標（ｘ３Ｄ，ｙ３Ｄ，ｚ３Ｄ）に変換する。
ｘ３Ｄ＝ｘ２Ｄｍｏｄ２ｎ−１
ｙ３Ｄ＝ｙ２Ｄｍｏｄ２ｎ−１
ｚ３Ｄ＝２×（ｙ２Ｄ／２ｎ−１）＋（ｘ２Ｄ／２ｎ−１）
例えば、図２の６４コアＦａｔ  Ｔｒｅｅは図８のように４枚の１６コアチップに分割される。
（ステップ２：ルータの配置）ルータを各チップに均等に振り分け配置する。図８の例では、各チップは４個のランク１ルータ、２個のランク２ルータ、１個のランク３ルータを有する。
（ステップ３：チップ間配線）他のランクに配置されたルータ同士をチップ間配線でつなぐ。最上位リンクは、マイクロバンプ、無線、貫通ビアなどのチップ間通信技術を用いてチップ面に対して垂直方向に結合される。
（ステップ４：ルータの再配置）垂直方向のチップ間リンク同士が重ならないように、ルータの位置を調整する。図８の例では、チップの中心にランク３ルータを置き、その周囲に他のランクと重ならないように各ランク２ルータを位置をずらして配置している。これにより最上位リンクはチップ間リンクに置き換えられる。結果的に、最上位リンクの１／２の長さの第２位リンクが最長配線となるため、４分割によって最長配線長は１／２に短縮される。この方法は、（２，４，２）Ｆａｔ  Ｔｒｅｅなど他の構成のＦａｔ  Ｔｒｅｅに対しても適用できる。
【００４４】
次に４分割以外の分割方法について説明する。ｉを正の整数とするとき、チップの２ｉ分割はチップの４分割と２分割を組み合わせることで実現できる。チップの２分割の場合、２次元のコア座標から３次元座標への変換は次のようになる。
ｘ３Ｄ＝ｘ２Ｄ
ｙ３Ｄ＝ｙ２Ｄｍｏｄ２ｎ−１
ｚ３Ｄ＝ｙ２Ｄ／２ｎ−１
これ以外の点については４分割の場合と同じである。チップ間リンクの距離を無視するとき、最上位リンクの長さは２分割によって、縦方向が１／２になり、横方向がそのままなので３／４に短縮される。
【００４５】
次に、Ｆａｔ  Ｈ−Ｔｒｅｅの３次元ＩＣ向けレイアウトについて説明する。Ｆａｔ  Ｈ−Ｔｒｅｅでは、畳み込みによって第２位リンク（ランク２ルータとランク１ルータ間の配線、図３の配線長の２倍になる）が最長配線となる。この最長配線の長さはＦａｔ  Ｔｒｅｅの最長配線（ランク３ルータとランク２ルータ間の配線、図２参照）の長さと同じであり、配線遅延、リピータ、および消費電力の増加を引き起こす。ここでは、Ｆａｔ  Ｔｒｅｅと同様に、これらの問題を３次元化によって解決する。
【００４６】
次に、Ｆａｔ  Ｈ−Ｔｒｅｅの４分割について説明する。Ｆａｔ  Ｈ−Ｔｒｅｅは２個のＨ−Ｔｒｅｅの他に２−Ｄ  Ｔｏｒｕｓ構造を内包するため、チップの分割後もこの２−Ｄ  Ｔｏｒｕｓ構造が保存されていなければならない。このためＦａｔ  Ｈ−Ｔｒｅｅの分割では、チップの分割時にコア座標の転置処理を行う。
【００４７】
図９にＲｅｄ  Ｔｒｅｅを４分割した例を、図１０にＢｌａｃｋ  Ｔｒｅｅを４分割した例を示す。Ｆａｔ  Ｈ−Ｔｒｅｅの４分割手順は次のとおりである。
（ステップ１：チップの分割）まず、チップの分割を行う。２次元Ｆａｔ  Ｈ−Ｔｒｅｅのコア座標（ｘ２Ｄ，ｙ２Ｄ）を、次のような３次元座標（ｘ３Ｄ，ｙ３Ｄ，ｚ３Ｄ）に変換する。
ｘ３Ｄ＝ｘ２Ｄｍｏｄ２ｎ−１  （ｘ２Ｄ＜２ｎ−１  のとき）
ｘ３Ｄ＝２ｎ−１−（ｘ２Ｄｍｏｄ２ｎ−１）  （ｘ２Ｄ＞＝２ｎ−１  のとき）
ｙ３Ｄ＝ｙ２Ｄｍｏｄ２ｎ−１  （ｙ２Ｄ＜  ２ｎ−１  のとき）
ｙ３Ｄ＝２ｎ−１−（ｙ２Ｄｍｏｄ２ｎ−１）  （ｙ２Ｄ＞＝２ｎ−１  のとき）
ｚ３Ｄ＝２×（ｙ２Ｄ／２ｎ−１）＋（ｘ２Ｄ／２ｎ−１）
この処理によって、元のチップはチップの中心を軸に水平方向、および、垂直方向に折り畳まれ４枚のチップに分割される。例えば、図３のＲｅｄ  Ｔｒｅｅは図９のように、また、図４のＢｌａｃｋ  Ｔｒｅｅは図１０のようにそれぞれ分割される。
（ステップ２：ルータの配置）ルータを各チップに均等に振り分け配置する。この例では、Ｒｅｄ  Ｔｒｅｅ（図９参照）およびＢｌａｃｋ  Ｔｒｅｅ（図１０参照）ともに、各チップに４個のランク１ルータ、１個のランク２ルータを有する。一方、ランク３ルータは、Ｒｅｄ  Ｔｒｅｅはチップ１（第２層目）に、Ｂｌａｃｋ  Ｔｒｅｅ  はチップ２（第３層目）にそれぞれ１個ずつ有する。
（ステップ３：チップ間配線）他のランクに配置されたルータ同士をチップ間配線でつなぐ。Ｂｌａｃｋ  Ｔｒｅｅでは最上位ルータに加え、ランク１ルータも異なるランクのコア同士をつないでいる。この様子を図１０の端部のコアに接続先のチップを表示して示す）。なお、接続されるコア同士は折り畳まれた時に垂直方向に重なり合うこととなる。
（ステップ４：ルータの再配置）必要に応じて行う。ランク２ルータは垂直方向に重ならないので、ここでは再配置を行なわなくても良い。
【００４８】
図９および図１０のレイアウトを組み合わせたものがＦａｔ  Ｈ−Ｔｒｅｅの３次元レイアウトであり、分割後も２−Ｄ  Ｔｏｒｕｓ構造が保存されている。例えば、コアＲ（１，０，０）の２ホップ先（Ｒｅｄ  Ｔｒｅｅのランク１ルータ−コア−Ｂｌａｃｋ  Ｔｒｅｅのランク１ルータを介する）はコアＲ（１，１，０）であり、その次はコアＲ（１，２，０），コアＲ（１，３，０）と移動した後、チップ２に移り、コアＲ（１，３、２），コアＲ（１，２，２），コアＲ（１，１，２）、コアＲ（１，０，２）を経て、再びチップ０のコアＲ（１，０，０）に戻る。図６にこの軌跡を矢印で示す。チップ間を除き２ホップ先へはＲｅｄ  ＴｒｅｅとＢｌａｃｋ  Ｔｒｅｅ各１個のランク１ルータを介して配線接続される。またチップ間については、図７を参照するとコアＲ（１，０，０）とコアＲ（１，０，２），コアＲ（１，３，０）とコアＲ（１，３，２）は垂直方向に重なり、垂直方向の配線で接続されることが分かる。
【００４９】
次に、４分割以外の分割方法について説明する。チップの２分割の場合、２次元のコア座標から３次元座標への変換は次のようになる。
ｘ３Ｄ＝ｘ２Ｄ
ｙ３Ｄ＝ｙ２Ｄｍｏｄ２ｎ−１  （ｙ２Ｄ＜２ｎ−１  のとき）
ｙ３Ｄ＝２ｎ−１−（ｙ２Ｄｍｏｄ２ｎ−１）  （ｙ２Ｄ＞＝２ｎ−１  のとき）
ｚ３Ｄ＝２×（ｙ２Ｄ／２ｎ−１）＋（ｘ２Ｄ／２ｎ−１）
この場合、ｘ方向のリンクは単一チップ内で完結するため、ｘ方向に対してのみ図７のような畳み込みを行う。これ以外の点については４分割の場合と同じである。チップ間リンクの距離を無視するとき、最上位リンクの長さは２分割によって３／４に短縮される。
【００５０】
［第１の実施の形態］
第１の実施の形態では、６４コア、３階層のＦａｔ  Ｔｒｅｅトポロジの例を説明する。一般的には、４ｎ個のモジュール間を、２ν個の２次元平面を積層した３次元空間に集積化するために、４本または６本の配線を持つ交換接続手段を用いたＦａｔ  Ｔｒｅｅで階層的に接続する。
【００５１】
図１１に６４コア３階層のＦａｔ  Ｔｒｅｅトポロジの例を示す。４３＝６４個のモジュールを３階層に積層した６４コアＦａｔ  Ｔｒｅｅトポロジである。最下層の第１のレイヤには６４個のコアが存在し、それぞれに電気回路で構成されるモジュールが配置されており、第ｉ行第ｊ列〜第ｉ＋１行第ｊ＋１列（ｉ，ｊ＝０〜１４の偶数）内の４個のモジュールを集めて１つの第１レイヤモジュールを構成し、第１レイヤモジュールにはこれら４個のモジュール間を交換接続するランク１ルータ、図中□内に「１」と表示）が配置されている。第１レイヤモジュールは１６個存在する。また、ランク１ルータは２つの上位のランク２ルータへのリンクを有し（すなわちルートが２重化されている）、４個のモジュールとこれら２個のランク２ルータとの交換接続も行う。第２のレイヤでは、第ｉ行第ｊ列〜第ｉ＋３行第ｊ＋３列（ｉ，ｊ＝０，４）内の４個の第１レイヤモジュールを集めて１つの第２レイヤモジュールを構成し、第２レイヤモジュールにはこれら４個の第１レイヤモジュール間を交換接続するランク２ルータ（図中□内に「２」と表示）が配置されている。第２レイヤモジュールは８個存在する。また、ランク２ルータは２つの上位のランク３ルータへのリンクを有し（すなわちルートが２重化されている）、４個の第１レイヤモジュールとこれら２個のランク３ルータとの交換接続も行う。第３のレイヤでは、第ｉ行第ｊ列〜第ｉ＋７行第ｊ＋７列（ｉ，ｊ＝０）内の４個の第２レイヤモジュールを集めて１つの第３レイヤモジュールを構成し、第３レイヤモジュールにはこれら４個の第２レイヤモジュール間を交換接続するランク３ルータ（図中□内に「３」と表示）が配置されている。第３レイヤモジュールは４個存在する。このようなツリートポロジを構成することにより、６４個のモジュールのうちの任意の２モジュール間の接続が複数ルート（２×２＝４）で可能になる。これは特定のルータへのトラフィックの集中を回避するのに役立つ。
【００５２】
図１２に６４コアＦａｔ  Ｔｒｅｅトポロジを４つのチップに分割した構成を示す。各チップは第２レイヤモジュールに対応し、１６個のモジュール、４個のランク１ルータ、２個のランク２ルータとこれらの間の配線を含んでいる。２個のランク２ルータがそれぞれ４個のランク１ルータに共に接続されることから、１個のチップには２個の第２レイヤモジュールが重複形成されている。各チップには更に１個のランク３ルータ及び当該ランク３ルータと当該チップに配置された１個のランク２ルータを接続する配線が含まれる。各チップは３次元空間に４層に積層される。異なるチップに存在するランク３ルータとランク２ルータを接続する配線はチップ間を繋ぐ垂直方向配線で接続される。
【００５３】
図１３に６４コアＦａｔ  Ｔｒｅｅトポロジを４つのチップに分割し、４つのチップを積層したときの各ランクのルータ配置とルータ間配線の３次元レイアウトの概要を示す。図１３（ａ）に各チップにおける２次元平面内の各ランクのルータ配置とルータ間配線を、図１３（ｂ）に各チップの３次元配置とランク２ルータ、ランク３ルータの配置を示す。図１３（ａ）に示すように、各層のチップにおいて４個のモジュールを２行２列に配置して第１レイヤモジュールが構成され、ランク１ルータは第１レイヤモジュールのほぼ中心に配置され、また、４個の第１レイヤモジュールを２行２列に配置して第２レイヤモジュールが構成され、ランク２ルータは第２レイヤモジュールのほぼ中心に配置される。ランク２ルータと各４個のランク１ルータとはチップ面内の配線により接続される。各チップに第２レイヤモジュールが２重に構成され、４つのチップを積層して第３レイヤモジュールが構成される。第３レイヤモジュールも２重のものが２組合計４つ構成される。また、図１３（ｂ）に示すように、最上位のランク３ルータを各チップの２次元平面構造の中心に配置し、ランク２ルータをランク３ルータの隣接周辺に、２次元平面に対して垂直方向に重ならないように配置する。各ランク３ルータから４個のランク２ルータに到る４本の配線のうち、１本は同一層内の１個の隣接するランク２ルータにチップ内で接続され、他の３層のランク２ルータに到る３本は垂直方向配線を４つのチップの中心付近を貫く貫通ビア（最下層は必ずしも貫く必要はない）を通して各層に延び、各層において貫通ビアに隣接する１個のランク２ルータに接続される。例えば、第１層と第３層のランク３ルータは第１層の上、第２層の右上、第３層の右、第４層の右下に隣接配置されたランク２ルータに接続され、第２層と第４層のランク３ルータは第１層の下、第２層の左下、第３層の左、第４層の左上に隣接配置されたランク２ルータに接続される。垂直方向配線は、第１層と第２層間に６本、第２層と第３層間に８本、第３層と第４層間に６本となるが（図１２参照）、これらは貫通ビアを通してまとめて配線される。このような配線構造により、モジュールから遠いルータ間の配線長、すなわちランク２ルータとランク３ルータ間の配線長を削減でき、これらの配線における信号の遅延を無視できるようにしている。
【００５４】
なお、これまで各ランクのルータを制御する制御手段について言及しなかったが、かかる制御手段を備えるものとし、モジュール間での信号を伝達する配線だけでなく、これらの制御手段と各ランクのルータを接続する制御信号線、さらに電源線についてもチップ間に布設されるものは貫通ビアを通してまとめて配線しても良い。このようにすれば制御線や電源線の遅延も削減できる。
【００５５】
図１４にＦａｔ  Ｔｒｅｅトポロジの配線レイアウトのアルゴリズムの大略を示す。本実施の形態では６４コア（２，４，１）Ｆａｔ  Ｔｒｅｅの配線レイアウトについて説明する。まず、ファットツリートポロジを二次元集積電気回路モジュールに相当するチップ対応に分割する（ツリー分割工程：Ｓ１０）。一般的にはコア数４ｎのＦａｔ  Ｔｒｅｅでは４ｎ―ｍ分割が可能である。ここでは図１１のＦａｔ  Ｔｒｅｅを図１２のように４分割する。
【００５６】
次にノードのマッピング、すなわち、三次元集積電気回路を二次元平面に展開した状態で、電気回路モジュール（コア）と交換接続手段（ルータ）の配置を行なう（ノードマッピング工程：Ｓ２０）。一般的には４ｎのコアとルータを２次元平面に展開し、コアとルータを配置する。ここではまず、ｎ＝３であり、コアを２行×２列の４コアずつにわけてランク１ルータをその中心に配置して第１レイヤモジュールを形成する。第１レイヤモジュールは全部で１６個になる。次に、２行×２列の４つの第１レイヤモジュールのランク１ルータの中心付近にランク２ルータを配置して第２レイヤモジュールを形成し、ランク２ルータとランク１ルータを配線接続する。４つの第１レイヤモジュールに対してランク２ルータは２つ、すなわち第２レイヤモジュールは２重に形成される。第１レイヤモジュールは全部で８個になる。次に、２行×２列の４つの第２レイヤモジュールのランク２ルータの中心付近にランク３ルータを配置して第３レイヤモジュールを形成する。４つの第２レイヤモジュールに対してランク３ルータは２つ、すなわち第３レイヤモジュールは２重に形成される。第３レイヤモジュールは全部で２重のものが２組合計４個形成される。この平面構成は図２に示される。次に、このように構成されたモジュールの各コアに番号を付する。
【００５７】
図１５はコアのマッピングと折り畳みを説明するための図である。コアの番号は図１５に示すように、第０行目の第０列から第２ｎ−１（＝７）列へ、第１行目の第０列から第２ｎ−１（＝７）列へ、・・・、第２ｎ−１（＝７）行目の第０列から第２ｎ−１（＝７）列へ採番する。図１５の左側の符号はコアの行を、上側の符号はコアの列を示し、１ｓｔ〜４ｔｈはグループ（層）を示す。さらに、ランク１ルータからランク３ルータに番号を付する。ルータの番号は例えばＲｅｄ  Ｔｒｅｅ座標Ｒ（ｒ１，・・・，ｒｎ−１）のように採番する。
【００５８】
次にノードマッピング工程で配置された三次元集積電気回路をツリー分割工程で分割した二次元集積電気回路モジュール（チップ）を積層するように折り畳む（折り畳み工程：Ｓ３０）。一般的には４ｎ―ｍ分割するのでｎ−ｍ重に折り畳むが、ここではｎ＝３、ｍ＝２で、４重に折り畳む。図１５の太枠のように全体を４つにグループに分け、各グループに層番号を付する。第３行目と第４行目の間及び第３列目と第４行列目の間に境界線を引くことにより、４つのグループに分けられる。各グループは第２レイヤモジュールに相当し、４×４＝１６コアを有する。例えば、左下の第１グループを第１層目、左上の第２グループを第２層目、右上の第３グループを第３層目、右下の第４グループを第４層目とする。第１グループは第３行目と第４行目の間の境界線に沿って第２グループの下に折畳み第１層目とする。第３グループは第３列目と第４行列目の間の境界線に沿って第２グループの上に折畳み第３層目とする。第４グループは第３列目と第４行列目の間の境界線に沿って第３グループと共に折畳み、さらに第３行目と第４行目の間の境界線に沿って第３グループの上に折畳み第４層目とする。このように折畳むと、コアの配置は図１９（後述する）、ランク１ルータ、ランク２ルータの配置は図１３（ａ）のようになる。ランク２ルータは各チップすなわち各グループの中心付近に２つずつ（２重に）配置される。ランク３ルータは全体に４個（２重×２組）であり、各チップの中心付近に１つずつ配置される。なお、上記境界線を用いて折り畳めばどのように折り畳んでも良い。
【００５９】
次に、折り畳み工程で各チップに配置された交換接続手段（ルータ）のうちチップ間に分散された上位ランクの交換接続手段（ルータ）間を垂直方向配線でリンクする（リンク工程：Ｓ４０）。４チップの中心付近でランク３ルータの近傍に貫通ビアを設け、各チップにおいて垂直方向から見てランク３ルータの周囲にランク２ルータを配置し、ランク３ルータとランク２ルータを配線接続する。各ランク３ルータからは同層の１個のランク２ルータには面内配線で接続され、他の３層のランク２ルータへは垂直配線で接続される。合計１２本の垂直配線が１つの貫通ビア内に布設される。この場合に、例えば図１３（ｂ）に示すように、８個のランク２ルータが垂直方向に重ならないように配置する。このようにするとランク３ルータから各ランク２ルータへの配線を交錯させずに直線的に形成できる。
【００６０】
［第２の実施の形態］
第２の実施の形態では、２５６コア、４階層のＦａｔ  Ｔｒｅｅトポロジの第１の例を説明する。図１１の３階層のＦａｔ  Ｔｒｅｅトポロジを第３レイヤモジュールとし、この第３レイヤモジュールを４層積層して第４レイヤモジュールが構成される。チップは全体で１６層積層される。各第３レイヤモジュールにはそれぞれ４個、全体で１６個の第３ランクルータがあり、例えば各チップに配置される。８個のランク４ルータが例えば第２層目の第３レイヤモジュールの最上層のチップに４個、第３層目の第３レイヤモジュールの最下層のチップに４個配置され、これらのランク３ルータとランク４ルータは各チップのほぼ中心に配置され、８個のランク４ルータと１６個のランク３ルータを接続する配線は、ルータが同一チップ内にある場合は面内配線で隣接接続され、異なるチップ間にある場合は主としてチップ間を繋ぐ垂直方向配線で接続される。
【００６１】
図１６に１６個のランク３ルータと８個のランク４ルータ間の配線のトポロジを示す。それぞれの第３レイヤモジュールには４層のチップが積層されている。さらに第３レイヤモジュールを４層積層して第４レイヤモジュールが構成され、全体で１６層のチップが積層されている。ランク３ルータは各チップに配置される。第２層目の第３レイヤモジュールの最上層のチップに配置された４個のランク４ルータのうち、第ｋ番目（ｋ＝１〜４）のルータは４個の第３レイヤモジュールの第ｋ層目のチップ（第２レイヤモジュール）に配置されたランク３ルータに配線接続される。第３層目の第３レイヤモジュールの最下層のチップに配置された４個のランク４ルータについても同様に、第ｋ番目（ｋ＝１〜４）のルータは４個の第３レイヤモジュールの第ｋ層目のチップ（第２レイヤモジュール）に配置されたランク３ルータに配線接続される。このように、ランク３ルータとランク４ルータ間の配線は二重化されている。
【００６２】
図１７に各第３レイヤモジュールの３次元配置とランク３ルータ、ランク４ルータの配置の例を示す。ランク３ルータ（図では「３」と表示）とランク４ルータ（図では「４」と表示）を結ぶ垂直方向配線は、それぞれのランク４ルータから上方向へ２本、下方向へ２本で、全体で上下各方向へ１６本ずつ（同層への配線を除くと１５本ずつ）となり、中央の貫通ビアを通してまとめて配線され、それぞれランク３ルータが配置されたチップに延びて隣接するランク３ルータに接続される。また、各第３レイヤモジュール内でランク２ルータとランク３ルータを結ぶ垂直方向配線は、第３レイヤモジュールの層内を超えて延びることはないので、ランク３ルータはランク４ルータとの垂直方向配線に隣接して設ければ良く、垂直方向に重ならない方が交錯を避け易いが重ねて設けても良い。
【００６３】
次に配線レイアウトのアルゴリズムについて述べる。２５６コア（２，４，１）Ｆａｔ  Ｔｒｅｅでは第１の実施の形態に比して１階層大きくなっており、コア及びルータが増えている。ツリー分割工程（Ｓ１０）では１６チップに分割するが、チップ内のレイアウトは第１の実施の形態と同様である。ノードマッピング工程（Ｓ２０）では２５６コアのマッピングを第０行第０列から第１５行第５列まで行なうが、第１の実施の形態と同様の順序で行なえば良く、ランク１ルータとランク２ルータのマッピングも同様である。ランク３ルータとランク４は垂直方向配線に関わりチップの中央付近に配置される。折り畳み工程（Ｓ３０）については境界線が第３行目と第４行目の間、第７行目と第８行目の間、第１１行目と第１２行目の間、第３列目と第４列目の間、第７列目と第８列目の間、第１１列目と第１２列目の間と縦横共３本ずつになるが、これらを境界線として折り畳めばどのように折り畳んでも良い。リンク工程（Ｓ４０）については第１の実施の形態にランク３ルータとランク４ルータとの垂直方向配線が加わるが、図１７で説明したように行なえば良い。
【００６４】
［第３の実施の形態］
第３の実施の形態では、２５６コア、４階層のＦａｔ  Ｔｒｅｅトポロジの第２の例を説明する。図１１の３階層のＦａｔ  Ｔｒｅｅトポロジを第３レイヤモジュールとし、第３レイヤモジュールが１チップ内の２次元平面に構成される。第３のレイヤでは、４個の第２レイヤモジュールが２行２列に配置されて１つの第３レイヤモジュールを構成し、これら４個の第２レイヤモジュール間を交換接続するランク３ルータが第３レイヤモジュールの中心に配置される。１個のチップには４つの第３レイヤモジュールと４個のランク３ルータが存在する。この第３レイヤモジュールを４層積層して第４のレイヤモジュールが構成され、これら４層合計１６個の第３レイヤモジュール間を交換接続するランク４ルータが２個ずつ各第３レイヤモジュールの各層すなわち各チップのほぼ中心に配置され、合計８つの第４レイヤモジュールと８個のランク４ルータが存在する。ルータ間の配線の接続関係は第２の実施の形態と同様である。
【００６５】
最上位のランク４ルータを各チップの２次元平面構造のほぼ中心に２個ずつ配置し、ランク３ルータをランク４ルータの隣接周辺に４個ずつ配置する。各ランク４ルータから各チップの４個のランク３ルータに到る４本の配線のうち、１本は同一層内の１個の隣接するランク３ルータにチップ内で接続され、他の３層のランク３ルータに到る３本は垂直方向配線を４つのチップの中心付近を貫く貫通ビアを通して各層に延び、各層において貫通ビアに隣接する１個のランク３ルータに接続される。例えば、第１層、第２層、第３層、第４層の第１番目のランク４ルータはそれぞれ各層の上、右上、右下に隣接配置されたランク３ルータ（各４個ずつ）に接続され、第１層、第２層、第３層、第４層の第２番目のランク４ルータはそれぞれ各層の下、左下、左、左上に隣接配置されたランク３ルータ（各４個ずつ）に接続される。垂直方向配線は、第１層と第２層間に６本、第２層と第３層間に８本、第３層と第４層間に６本となるが、これらは貫通ビアを通してまとめて配線される。
【００６６】
次に配線レイアウトのアルゴリズムについて述べる。２５６コア（２，４，１）Ｆａｔ  Ｔｒｅｅでは第１の実施の形態に比して１階層大きくなっており、コア及びルータが増えている。ツリー分割工程（Ｓ１０）では４チップに分割する。このためチップが第１、第２の実施の形態に比して１階層分大きくなっており、第３レイヤモジュール、ランク３ルータまで含む。ノードマッピング工程（Ｓ２０）は第２の実施の形態と同様である。折り畳み工程（Ｓ３０）については境界線が第７行目と第８行目の間、第７列目と第８列目の間になり、縦横共１本ずつで第１の実施の形態と同じ本数になり、第１の実施の形態と同様に折り畳むと理解しやすい。なお、これらを境界線として折り畳めばどのように折り畳んでも良い。リンク工程（Ｓ４０）については第１の実施の形態におけるランク２ルータとランク３ルータとの垂直方向配線の関係を本実施の形態におけるラン３クルータとランク４ルータとの垂直方向配線の関係に代えれば良い。
【００６７】
［第４の実施の形態］
本実施の形態では、６４コア、３階層のＦａｔ  Ｈ−Ｔｒｅｅトポロジの例を説明する。Ｆａｔ  Ｈ−ＴｒｅｅトポロジはＲｅｄ  ＴｒｅｅとＢｌａｃｋ  Ｔｒｅｅと呼ばれる２つのＨ−Ｔｒｅｅトポロジを組み合わせたトポロジである。１つのモジュールは２つのリンクを持ち、１つのリンクをＲｅｄ  Ｔｒｅｅとの接続に、他の１つのリンクをＢｌａｃｋ  Ｔｒｅｅとの接続に用いる。
【００６８】
図３の６４コアＲｅｄ  Ｔｒｅｅのツリー構造の例を再度参照する。各コア（モジュール）を○で示す。この配線構造は第１の実施の形態で示した図１１の６４コアＦａｔ  Ｔｒｅｅトポロジを平面展開したもので、モジュールが８×８の行列に配置されている。第３の実施の形態における第３レイヤモジュールの配線構造とほぼ同じであるが、ランク１ルータ以上の配線が多重化されていない点が異なる。第ｉ行第ｊ列〜第ｉ＋１行第ｊ＋１列（ｉ，ｊ＝０〜６の偶数）内の４つのモジュールがランク１ルータに接続されて第１レイヤモジュールを構成し、第ｉ行第ｊ列〜第ｉ＋３行第ｊ＋３列（ｉ，ｊ＝０，４）内の４つの第１レイヤモジュールがランク２ルータに接続されて第２レイヤモジュールを構成し、第ｉ行第ｊ列〜第ｉ＋７行第ｊ＋７列（ｉ，ｊ＝０）内の４つの第２レイヤモジュールがランク３ルータに接続されて第３レイヤモジュールを構成する。
【００６９】
図４の６４コアＢｌａｃｋ  Ｔｒｅｅのツリー構造の例を再度参照する。各モジュールを○で示す。このモジュールの配置及びモジュール間の配線構造は、図３の６４コアＲｅｄ  Ｔｒｅｅのモジュールの配置及びモジュール間の配線構造を右方向に１モジュール分、下方向に１モジュール分ずらした構造である。そして、Ｒｅｄ  Ｔｒｅｅの第７行目のモジュールが右方向に１モジュール分ずれたものがＢｌａｃｋ  Ｔｒｅｅの第０行目となり、Ｒｅｄ  Ｔｒｅｅの第７列目のモジュールが下方向に１モジュール分ずれたものがＢｌａｃｋ  Ｔｒｅｅの第０列目となり、Ｒｅｄ  Ｔｒｅｅの第７行第７列目のモジュールがＢｌａｃｋ  Ｔｒｅｅの第０行第０列目のモジュールとなる。すなわち、Ｂｌａｃｋ  ＴｒｅｅのモジュールはＲｅｄ  Ｔｒｅｅのモジュールを右方向及び下方向に１モジュールずつ循環シフトしたものである。Ｂｌａｃｋ  Ｔｒｅｅの各モジュール間の配線接続関係は、モジュールの配置を右方向に１モジュール分、下方向に１モジュール分ずらした場合のＲｅｄ  Ｔｒｅｅの各モジュール間の配線接続関係と同じである。すなわち、第ｉ行第ｊ列〜第ｉ＋１行第ｊ＋１列（ｉ，ｊ＝１〜７１６の奇数）内の４つのモジュールがランク１ルータに接続されて第１レイヤモジュールを構成し、第ｉ行第ｊ列〜第ｉ＋３行第ｊ＋３列（ｉ，ｊ＝１，５）内の４つの第１レイヤモジュールがランク２ルータに接続されて第２レイヤモジュールを構成し、第ｉ行第ｊ列〜第ｉ＋７行第ｊ＋７列（ｉ，ｊ＝１）内の４つの第２レイヤモジュールがランク３ルータに接続されて第３レイヤモジュールを構成する。ただし、これらの行列において７行目に該当するモジュールはＢｌａｃｋ  Ｔｒｅｅでは０行目のモジュールとして配置され、７列目に該当するモジュールはＢｌａｃｋ  Ｔｒｅｅでは０列目のモジュールとして配置され、第７行第７列目に該当するモジュールはＢｌａｃｋ  Ｔｒｅｅでは第０行第０列目のモジュールとして配置される。そして、ランク１ルータは０行目と７行目のモジュール、０列目と７列目のモジュールを配線接続する。
【００７０】
図１８に６４コアＦａｔ  Ｈ−Ｔｒｅｅトポロジの例を示す。このモジュールの配置及びモジュール間の配線構造は、図３のＲｅｄ  Ｔｒｅｅのモジュールの配置及びモジュール間の配線構造と図４のＢｌａｃｋ  Ｔｒｅｅのモジュールの配置及びモジュール間の配線構造とを合せ持つ構造である。配線が二重化されていることにより、特定のルータへのトラフィックの集中を回避できる。
【００７１】
図１９に６４コアＦａｔ  Ｈ−Ｔｒｅｅを４分割した時のＲｅｄ  Ｔｒｅｅの３次元レイアウトを示す。これは図３のＲｅｄ  Ｔｒｅｅのモジュール配置とモジュール間の配線接続構造を４つのチップに分割した時のレイアウトを示すもので、（ａ）は第１層目のチップのレイアウト、（ｂ）は第２層目のチップのレイアウト、（ｃ）は第３層目のチップのレイアウト、（ｄ）は第４層目のチップのレイアウトを示す。全体構成は第１の実施の形態における第３レイヤモジュールに相当し、同じく第１の実施の形態における第２レイヤモジュールに相当する４つのチップを４層積層して第３レイヤモジュールを構成する。図３のＲｅｄ  Ｔｒｅｅの各モジュールに、第０行目を第０列から第７列へモジュール番号０〜７を、第１行目を第０列から第７列へモジュール番号８〜１５を、・・・第７行目を第０列から第７列へモジュール番号５６〜６３を順番に付与する。第２層目を図３の左上側の第２レイヤモジュールとする。第１層目は図３の左下側の第２レイヤモジュールを第２層目となる左上側の第２レイヤモジュールとの境界線にそってその下側に折畳んだときのモジュール番号の配置となる。第３層目は図３の右上側の第２レイヤモジュールを第２層目となる左上側の第２レイヤモジュールとの境界線にそってその上側に折畳んだときのモジュール番号の配置となる。第４層目は図３の右下側の第２レイヤモジュールを第３層目となる右上側の第２レイヤモジュールと共に第２層目となる左上側の第２レイヤモジュールの上に折畳んだ後にさらに右上側の第２レイヤモジュールとの境界線にそってその上側に折畳んだときのモジュール番号の配置となる。このように４つの第２レイヤモジュールを積層して第３レイヤモジュールを構成する。
【００７２】
Ｒｅｄ  Ｔｒｅｅ系で第２レイヤモジュールは４つ、第３レイヤモジュールは１つである。ランク２ルータとランク１ルータを接続する配線はチップ内で接続され、ランク３ルータとランク２ルータを接続する配線は主としてチップ間を繋ぐ垂直方向配線で接続される（同層内では面内配線接続される）。ランク３ルータはＲｅｄ  Ｔｒｅｅ系では第３層目の第２レイヤモジュールを搭載するチップの中央に配置される。これらの配線構造は第１の実施の形態におけるＦａｔ  Ｔｒｅｅトポロジとほぼ同じであるが、ランク２ルータが二重化されず各チップに１個、合計４個である点、ランク３ルータが上記のように合計１個である点と、これらに伴い、これらランク３ルータとラン２クルータを繋ぐ配線の本数が異なる。
【００７３】
図２０に６４コアＦａｔ  Ｈ−Ｔｒｅｅを４分割した時のＢｌａｃｋ  Ｔｒｅｅの３次元レイアウトを示す。これは図４のＢｌａｃｋ  Ｔｒｅｅのモジュール配置とモジュール間の配線接続構造を４つのチップに分割した時のレイアウトを示すもので、（ａ）は第１層目のチップのレイアウト、（ｂ）は第２層目のチップのレイアウト、（ｃ）は第３層目のチップのレイアウト、（ｄ）は第４層目のチップのレイアウトを示す。４つのチップの積層の仕方は図１９のＲｅｄ  Ｔｒｅｅと同じであり、したがって、各層のチップのモジュールの配置は図１９のＲｅｄ  Ｔｒｅｅと同様であり、そして配線接続構造は図４のモジュール間の配線接続構造を採用している。
【００７４】
この結果、例えば、第１層目のチップでは、Ｒｅｄ  Ｔｒｅｅの場合に比して第１レイヤモジュール、第２レイヤモジュールが上方向及び右方向にそれぞれ１モジュール分ずれ、ランク１ルータ、ランク２ルータも上方向及び右方向にそれぞれ１モジュール分ずれる。そして、４つのモジュール４１，４２，４９，５０からなる第１レイヤモジュールは第１層目のチップ内に存在するが、４つのモジュール４３，４４，５１，５２からなる第１レイヤモジュールは第１層目に４３，５１、第４層目に４４，５２と２層のチップにまたがり、ランク１ルータからこれらのモジュールを接続する配線は２つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第１層目と第４層目で垂直方向に重なった位置にあり、１束の垂直方向配線で接続可能である。また、４つのモジュール１，２，５７，５８からなる第１レイヤモジュールは第１層目に５７，５８、第２層目に１，２と２層のチップにまたがり、ランク１ルータからこれらのモジュールを接続する配線は２つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第１層目と第２層目で垂直方向に重なった位置にあり、１束の垂直方向配線で接続可能である。また、４つのモジュール３，４，５９，６０からなる第１レイヤモジュールは第１層目に５９，第２層目に３、第３層目に４，第４層目に６０と４層のチップにまたがり、ランク１ルータからこれらのモジュールを接続する配線は４つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第１層目から第４層目まで垂直方向に重なった位置にあり、１束の垂直方向配線で接続可能である。このような垂直方向配線も貫通ビアを使用できる。
【００７５】
また、第２層目のチップでは、Ｒｅｄ  Ｔｒｅｅの場合に比して第１レイヤモジュール、第２レイヤモジュールが下方向及び右方向にそれぞれ１モジュール分ずれ、ランク１ルータ、ランク２ルータも下方向及び右方向にそれぞれ１モジュール分ずれ、配線についても第１層目と類似の関係が存在する。また、第３層目のチップでは、Ｒｅｄ  Ｔｒｅｅの場合に比して第１レイヤモジュール、第２レイヤモジュールが下方向及び左方向にそれぞれ１モジュール分ずれ、ランク１ルータ、ランク２ルータも下方向及び左方向にそれぞれ１モジュール分ずれ、配線についても第１層目と類似の関係が存在する。また、第４層目のチップでは、Ｒｅｄ  Ｔｒｅｅの場合に比して第１レイヤモジュール、第２レイヤモジュールが上方向及び左方向にそれぞれ１モジュール分ずれ、ランク１ルータ、ランク２ルータも上方向及び左方向にそれぞれ１モジュール分ずれ、配線についても第１層目と類似の関係が存在する。なお、図２０中の端部にある各ランク１ルータには接続されるモジュールの番号と（  ）内にそのモジュールが存在する層を示している。
【００７６】
Ｂｌａｃｋ  Ｔｒｅｅ系では、第２レイヤモジュールは４つ、第３レイヤモジュールは１つであり、ランク２ルータが各チップに１個、合計４個、ランク３ルータが合計１個である点はＲｅｄ  Ｔｒｅｅの場合と同様であるが、ランク２ルータとランク３ルータの位置が異なる。各第２レイヤモジュールにおいて４つのランク１ルータに接続するランク２ルータは４つのランク１ルータの中央付近に配置され、ランク１ルータとランク２ルータを接続する配線は面内に布設される。また、第３レイヤモジュールにおいて４つのランク２ルータに接続するランク３ルータは第３層目のチップの中央に配置され、ランク２ルータとランク３ルータを接続する配線はチップ間では垂直方向配線となり、貫通ビア内にまとめて布設され、各チップ内で貫通ビアからランク２ルータまで面内配線で繋がれる。
【００７７】
Ｆａｔ  Ｈ−ＴｒｅｅトポロジはＲｅｄ  ＴｒｅｅとＢｌａｃｋ  Ｔｒｅｅと呼ばれる２つのＨ−Ｔｒｅｅトポロジを組み合わせたトポロジである。したがって、その配線構造は両者の配線構造を合わせ持つ。しかし、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク２ルータとランク３ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。
【００７８】
Ｆａｔ  Ｈ−Ｔｒｅｅトポロジの配線レイアウトのアルゴリズムも大略は図１４で表されるが、細部はＦａｔ  Ｔｒｅｅトポロジの場合と異なる。本実施の形態では６４コア３階層Ｆａｔ  Ｈ−Ｔｒｅｅのツリー構造配線レイアウトについて説明する。まず、ファットエイチツリートポロジを二次元集積電気回路モジュールに相当するチップ対応に分割する（ツリー分割工程：Ｓ１０）。ここでは４分割する。
【００７９】
次に三次元集積電気回路を二次元平面に展開した状態で、電気回路モジュール（コア）と交換接続手段（ルータ）の配置を行なう（ノードマッピング工程：Ｓ２０）。コアの配置はＦａｔ  Ｔｒｅｅの場合と同様である。他方、ルータの配置はＲｅｄ  ＴｒｅｅではＦａｔ  Ｔｒｅｅの場合と同様であるが、Ｂｌａｃｋ  ＴｒｅｅではＦａｔ  Ｔｒｅｅに対し１モジュール分下方及び右側に循環シフトしている。また、Ｒｅｄ  Ｔｒｅｅ内、Ｂｌａｃｋ  Ｔｒｅｅ内では配線の多重化はされていない。
【００８０】
次にノードマッピング工程で配置された三次元集積電気回路をツリー分割工程で分割した二次元集積電気回路モジュール（チップ）を積層するように折り畳む（折り畳み工程：Ｓ３０）。折り畳み方はＦａｔ  Ｔｒｅｅの場合と同様である。従って、コアの配置はＦａｔ  Ｔｒｅｅの場合と同様である。他方、ルータの配置は図２０に示すように、Ｒｅｄ  ＴｒｅｅではＦａｔ  Ｔｒｅｅの場合と同様であるが、Ｂｌａｃｋ  ＴｒｅｅではＦａｔ  Ｔｒｅｅに対し１モジュール分、第１層目が右上に、第２層目が右下に、第３層目が左下に、第４層目が左上にシフトしている。また、第１レイヤモジュールが層間に亘るものがある。ランク２ルータは各チップにＲｅｄ  Ｔｒｅｅで１つ、Ｂｌａｃｋ  Ｔｒｅｅで１つ、全体で８つである。ランク３ルータはＲｅｄ  Ｔｒｅｅで第２層目中心に１つ、Ｂｌａｃｋ  Ｔｒｅｅで第３層目中心に１つ、全体で２つである。
【００８１】
次に、折り畳み工程で各チップに配置された交換接続手段（ルータ）のうちチップ間に分散された上位ランクの交換接続手段（ルータ）間を垂直方向配線でリンクする（リンク工程：Ｓ４０）。４チップの中心に貫通ビアを設け、各チップにおいて垂直方向から見てランク３ルータの周囲にランク２ルータを配置し、ランク３ルータとランク２ルータを配線接続する。２つのランク３ルータからは、それぞれ同層の１つランク２ルータには面内配線で接続され、他の３層のランク２ルータへは垂直方向配線で接続される。合計６本の垂直方向配線が１つの貫通ビア内に布設される。この場合に、例えば図１７に示すように、８つのランク２ルータが垂直方向に重ならないように配置する。このようにするとランク３ルータから各ランク２ルータへの配線を交錯させずに直線的に形成できる。また、Ｂｌａｃｋ  Ｔｒｅｅ内ではチップのエッジ部分においてラン１３ルータとモジュールを接続するための８束の垂直方向配線が設けられる（図２０参照）。
【００８２】
［第５の実施の形態］
以上の実施形態では４分割Ｆａｔ  Ｔｒｅｅトポロジの例を説明したが、第５の実施の形態では２分割Ｆａｔ  Ｈ−Ｔｒｅｅトポロジの例について説明する。ここでは、６４コア３階層のＦａｔ  Ｈ−Ｔｒｅｅトポロジを３２コア２チップに分割する例を説明する。
【００８３】
図２１に、６４コアＦａｔ  Ｈ−Ｔｒｅｅを２分割した時のＲｅｄ  Ｔｒｅｅの３次元レイアウトの例を示す。図２１（ａ）は第１層目のチップのレイアウト、図２１（ｂ）は第２層目のチップのレイアウトを示す。第１層目は図１９における第１層目と第４層目のモジュールを合せて配置を変更したものであり、第２層目のモジュールは図１９における第２層目と第３層目のモジュールを合せて配置を変更したものである。２分割の場合、横方向には分割しないので、横方向のモジュールの配置は初めから固定される。本実施の形態では第１層目は左から５６，６３，５７，６２，５８，６１，５９，６０の順序、第２層目は左から０，７，１，６，２，５，３，４の順序であり、この配置は図７のモジュールの配置と同様であり、図６の配置すなわち図１９の配置と等価である。縦方向のモジュールの配置は図１９の配置と同様である。ランク１ルータとモジュールを接続する配線の関係、ランク２ルータとランク１ルータを接続する配線の関係は第４の実施の形態と同様であり、このため、ランク１ルータの位置は横方向では第０行目と第１行目の間、第２行目と第３行目の間で、縦方向では第１、２、５，６列目の中央となり、ランク２ルータの位置はチップの中央付近となる。これらの配線はチップ内で接続される。ランク２ルータは二重化されず各チップに２個、合計４個である。ランク３ルータは全体に１個で第１層目のチップの中央となり、ランク３ルータから４個のランク２ルータを接続する４本の配線のうち、２本は同一層内の隣接するランク２ルータにチップ内で接続され、他の層のランク２ルータに到る２本はチップ間を繋ぐ垂直方向配線で接続される。なお、図２１では各モジュールを正方形で示しているが、縦横比を２：１にするとチップは正方形となり、既存の製造ラインに適合するので好適である。
【００８４】
図２２に、６４コアＦａｔ  Ｈ−Ｔｒｅｅを２分割した時のＢｌａｃｋ  Ｔｒｅｅの３次元レイアウトの例を示す。図２２（ａ）は第１層目のチップのレイアウト、図２２（ｂ）は第２層目のチップのレイアウトを示す。第１層目は図２０における第１層目と第４層目のモジュールを合せて配置を変更したものであり、第２層目のモジュールは図２０における第２層目と第３層目のモジュールを合せて配置を変更したものである。横方向のモジュールの配置は初めから固定され、第１層目は左から５６，６３，５７，６２，５８，６１，５９，６０の順序、第２層目は左から０，７，１，６，２，５，３，４の順序である。縦方向のモジュールの配置は図２０の配置と同様である。ランク１ルータとモジュールを接続する配線の関係、ランク２ルータとランク１ルータを接続する配線の関係は第４の実施の形態と同様であり、このため、第１層目において、ランク１ルータの位置は横方向では第０行目の上端、第１行目と第２行目の間で、縦方向では第０列目と第１列目の間、第３列目の中央、第４列目の中央、第６列目と第７列目の間となり、ランク２ルータの位置は横方向では第２列目の右から１／４モジュールの位置、第５列目の左から１／４モジュールの位置、縦方向では第０行目と第１行目の間となる。第２層目において、ランク１ルータの位置は横方向では第１行目と第２行目の間、第３行目の下端で、縦方向では第０列目と第１列目の間、第３列目の中央、第４列目の中央、第６列目と第７列目の間となり、ランク２ルータの位置は横方向では第２列目の右から１／４モジュールの位置、第５列目の左から１／４モジュールの位置、縦方向では第第２行目と第３行目の間となる。
【００８５】
４つのモジュール４０，４７，４８，５５からなる第１レイヤモジュールなどの４つの第１レイヤモジュールは第１層目のチップ内に存在し、４つのモジュール８，１５，１６，２３からなる第１レイヤモジュールなどの４つの第１レイヤモジュールは第２層目のチップ内に存在するが、４つのモジュール０，７，５６，６３からなる第１レイヤモジュールは第１層目に５６，６３、第２層目に０，７と２層のチップにまたがり、４つのモジュール１，２，５７，５８からなる第１レイヤモジュールなどの他の７つの第１レイヤモジュールも２層のチップにまたがり、ランク１ルータからこれらのモジュールを接続する配線は２つのチップを接続する垂直方向配線を含む。ただし、これらのモジュールは第１層目と第２層目で垂直方向に重なった位置にあり、それぞれ１束の垂直方向配線で接続可能である。このような垂直方向配線も貫通ビアを使用できる。ランク２ルータは二重化されず各チップに２個、合計４個であり、ランク２ルータとランク１ルータを接続する配線はチップ内で接続される。ランク３ルータは全体に１個で第３層目のチップの中央となり、ランク３ルータから４個のランク２ルータを接続する４本の配線のうち、２本は同一層内のランク２ルータにチップ内で接続され、他の層のランク２ルータに到る２本はチップ間を繋ぐ垂直方向配線で他のチップに到り、そのチップ内でランク２ルータの位置まで延びる。なお、図２２では各モジュールを正方形で示しているが、縦横比を２：１にするとチップは正方形となり、既存の製造ラインに適合するので好適である。
【００８６】
Ｆａｔ  Ｈ−ＴｒｅｅトポロジはＲｅｄ  ＴｒｅｅとＢｌａｃｋ  Ｔｒｅｅと呼ばれる２つのＨ−Ｔｒｅｅトポロジを組み合わせたトポロジである。したがって、その配線構造は両者の配線構造を合わせ持つ。しかし、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク２ルータとランク３ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。なお、上記の説明は２分割Ｆａｔ  Ｈ−Ｔｒｅｅトポロジの例であるが、２分割Ｆａｔ  Ｔｒｅｅトポロジについても２分割Ｒｅｄ  Ｔｒｅｅのランク１ルータからランク２ルータへの配線を二重化し、さらにランク２ルータからランク３ルータへの配線を二重化することにより実現可能であり、同様に、垂直方向配線を有し、モジュールから遠いルータ間の配線長、すなわちランク２ルータとランク３ルータ間の配線長を削減でき、これらの配線における信号の遅延を殆ど無くしている。
【００８７】
次に２分割Ｆａｔ  Ｈ−Ｔｒｅｅトポロジの配線レイアウトのアルゴリズムについて述べる。第４の実施の形態に比して階層は同じで、チップ数が半分になっている。ツリー分割工程（Ｓ１０）では２チップに分割する。ノードマッピング工程（Ｓ２０）は第４の実施の形態とほぼ同様であるが、レッドツリー系のランク２ルータはチップの中心付近に配置される。折り畳み工程（Ｓ３０）については境界線が第３行目と第４行目の間の１本のみになる。リンク工程（Ｓ４０）についてはランク２ルータとランク３ルータ間のリンクを２チップ間で行なうが、第４の実施の形態と同様にＢｌａｃｋ  Ｔｒｅｅ系ではランク２ルータの位置がシフトしており、また、第１レイヤモジュールが層間に亘るものがある。ランク２ルータは各チップにＲｅｄ  Ｔｒｅｅで２つ、Ｂｌａｃｋ  Ｔｒｅｅで２つ、全体で８つである。ランク３ルータはＲｅｄ  Ｔｒｅｅで第１層目中心に１つ、Ｂｌａｃｋ  Ｔｒｅｅで第２層目中心に１つ、全体で２つである。
【００８８】
［第６の実施の形態］
以上の実施形態では二次元集積電気回路モジュール間の配線が貫通ビアを通して構成される例について説明したが、第６の実施の形態では二次元集積電気回路モジュール間の配線に無線配線を用いる例を説明する。例えば第１の実施の形態の配線構造において、貫通ビアを通る垂直方向配線に代えて無線通信で信号を伝達する。モジュール間での信号を伝達する配線だけでなく、各ランクのルータを制御する制御信号線、電源線についても無線配線で置換しても良い。この場合、チップすなわち二次元集積電気回路モジュールの二次元平面に垂直な方向にほぼ直線上に並べて無線送受信手段が配置される。チップ間の通信を行なうランク２ルータ及びランク３ルータに無線送受信手段として例えば各１個の無線送受信回路を用いても良く、各１個の無線送信回路及び無線受信回路を用いても良い。また、これら送信回路又は受信回路としてインダクターなどの電磁結合や容量結合を用いても良い。無線送受信手段を二次元平面に垂直な方向にほぼ直線上に並べるのは、チップ間で良好な無線通信が可能な送信手段と受信手段間の距離がμｍオーダーの範囲では可能なのに対し、ｍｍオーダー以上では困難だからである。したがって、チップ間配線に無線配線を用いる場合にも、モジュール、各ランクのルータの配置及びこれらの間の配線構造について、貫通ビアの場合と同じアルゴリズムを適用できる。また、配線レイアウトのアルゴリズムは第１の実施の形態の貫通ビアを無線配線に代えれば良い。
【００８９】
なお、上記の説明は第１の実施の形態に無線配線を適用する例であるが、第２〜第５の実施の形態にも同様に無線配線を適用可能である。
【００９０】
［評価］
次に、以上の実施の形態で説明した３−Ｄ  Ｆａｔ  Ｔｒｅｅ  および３−Ｄ  Ｆａｔ  Ｈ−Ｔｒｅｅについて、チップ面積，配線量，配線遅延，リピータ数，消費電力について評価する。これらの３次元レイアウトは２γ枚のチップ上に実現できるが，ここでは積層するチップ数を４層として評価する。
【００９１】
（１）ルータのリンク数と個数
表１に、３−Ｄ  Ｆａｔ  Ｔｒｅｅおよび３−Ｄ  Ｆａｔ  Ｈ−Ｔｒｅｅトポロジで必要となるルータの個数を見積もった結果を示す。比較のため３−Ｄ  Ｍｅｓｈと３−Ｄ  Ｔｏｒｕｓの結果も示す。Ｆａｔ  Ｈ−Ｔｒｅｅをはじめツリー系のトポロジでは３−Ｄ  Ｍｅｓｈや３−Ｄ  Ｔｏｒｕｓに比べてルータの数が少ない。また、表には示されていないが、ルータの最大リンク数はＨ−ＴｒｅｅとＦａｔ  Ｈ−Ｔｒｅｅで５個，Ｆａｔ  Ｔｒｅｅで６個であるのに対し，３−Ｄ  Ｍｅｓｈと３−Ｄ  Ｔｏｒｕｓでは７個（ｘｙｚ各方向に２個ずつに、（ローカル）コア（プロセッシングエレメント）へのリンクを含めて７個とした）となり、ルータ１個当たりの面積でもツリー系トポロジのほうが有利である。ただし，（２，４，２）Ｆａｔ  ＴｒｅｅとＦａｔ  Ｈ−Ｔｒｅｅでは各コアは２本のリンクを有するため、他のトポロジと比べネットワークインターフェイス（ＮＩ）の面積が増加する。
【００９２】
【表１】
2008282108.tif 000003
【００９３】
（２）ルータとネットワークインターフェイス（ＮＩ）の面積
表２に３−Ｄ  Ｆａｔ  Ｔｒｅｅおよび３−Ｄ  Ｆａｔ  Ｈ−Ｔｒｅｅトポロジにおける、オンチップルータとＮＩからなる部分の面積（ｍｍ２）を示す。比較のため３−Ｄ  Ｍｅｓｈと３−Ｄ  Ｔｏｒｕｓにおける同部分の面積も示す。
【表２】
2008282108.tif 000004
【００９４】
なお、カッコ内の数字は２次元レイアウトからの増分を示すものである。この数字はツリー型トポロジでは貫通ビアのみの面積を表し、ＭｅｓｈやＴｏｒｕｓでは３次元化に伴うルータ面積の増分と貫通ビアの面積を表す。この結果より、ツリー型トポロジでは、３次元化のための貫通ビアによって総面積が最大５．０％増加しているのに対し、ＭｅｓｈとＴｏｒｕｓでは３次元化によってルータのリンク数が増えるため、面積がＭｅｓｈで最大２１．５％、Ｔｏｒｕｓで最大４７．３％増加しており、３次元化のオーバーヘッドが非常に大きいことが分かる。
【００９５】
各トポロジの面積は次の手順で見積もった。（１）まず、Ｖｅｒｉｌｏｇ−ＨＤＬ（Ｈａｒｄｗａｒｅ  Ｄｅｓｃｒｉｐｔｉｏｎ  Ｌａｎｇｕａｇｅ）で記述されたルータ回路とＮＩ回路を組み合わせ対象トポロジを構築した。（２）次に、これを０．１８μｍスタンダードセルライブラリを用いてＳｙｎｏｐｓｙｓ社のＤｅｓｉｇｎ  Ｃｏｍｐｉｌｅｒで合成することでＮｏＣの面積を抽出した。（３）次に、各トポロジに含まれるチップ間リンクの数から貫通ビアの面積を計算し、ＮｏＣの面積に足し合わせた。ここにおいて、ルータ回路は４段のパイプラインステージから構成され，パイプラインステージごとに１−フリット（ｆｌｉｔ）分のリピータを有し、ＮＩ回路として２−ｆｌｉｔ分のＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ，  Ｆｉｒｓｔ  Ｏｕｔ）を入力側と出力側にそれぞれ有するものとした。また、Ｆａｔ  Ｈ−Ｔｒｅｅと（２，４，２）Ｆａｔ  Ｔｒｅｅでは２ポートのＮＩが必要になる。とくにＦａｔ  Ｈ−Ｔｒｅｅでは，片方のポートからもう片方のポートへパケットを転送する機能が必要であり、このためにＮＩ内に小さなマルチプレクサが実装されているものとした。貫通ビアのサイズはチップを重ね合わせるときのアライメントの精度によって制限され、一般的には１μｍ角〜１０μｍ角となる。ここでは、１−ビット（ｂｉｔ）の単方向チップ間リンクが１枚のチップを貫通する度に、貫通ビアの面積として１００μｍ２を加算した。
【００９６】
（３）総配線長
表３にＦａｔ  Ｔｒｅｅ及びＦａｔ  Ｈ−Ｔｒｅｅについて、２次元レイアウトにおける総配線長を示す。比較のため２−Ｄ  Ｍｅｓｈと２−Ｄ  Ｔｏｒｕｓにおける総配線長も示す。ここで、隣接コア間距離を１−ユニット（ｕｎｉｔ）とし、配線長をユニット数で表す。
【表３】
2008282108.tif 000005
【００９７】
階層数ｎのＨ−Ｔｒｅｅの２次元レイアウトにおける総配線長Ｌ２Ｄ，ｈｔを式（３）で表す。
【数１】
2008282108.tif 000006
ただし，ｌｉｈｔをＨ−Ｔｒｅｅにおけるランクｉルータからその４個の下位ルータへの総リンク長，ｒｉｈｔをランクｉルータの数とする。コア数をＮ＝２ｎ×２ｎとすると、ｌｉｈｔ＝２ｉ＋１，ｒｉｈｔ＝Ｎ／４ｉとなる。したがって，式（３）は式（４）のように変形できる。
【数２】
2008282108.tif 000007
同様にして，階層数ｎのＦａｔ  Ｈ−Ｔｒｅｅ  の２次元レイアウトにおける総配線長Ｌ２Ｄ，ｆｈｔを求める式は式（５）のように導びかれる。
【数３】
2008282108.tif 000008
表３の見積りではＭｅｓｈ及びＴｏｒｕｓのコア−ルータ間リンクの長さを無視しているものの、Ｆａｔ  Ｈ−Ｔｒｅｅや（２，４，２）Ｆａｔ  Ｔｒｅｅなどツリー型トポロジの総配線長が圧倒的に長く、これがツリー型トポロジの欠点になっていることが分かる。
【００９８】
表４にＦａｔ  Ｔｒｅｅ及びＦａｔ  Ｈ−Ｔｒｅｅについて、３次元レイアウトの総配線長Ｌ３Ｄ，ｈｔを示す。比較のため３−Ｄ  Ｍｅｓｈと３−Ｄ  Ｔｏｒｕｓにおける総配線長も示す。ここで、隣接コア間距離を１−ｕｎｉｔとし、配線長をユニット数で表す。
【表４】
2008282108.tif 000009
【００９９】
３次元レイアウトではチップ間の距離は数十μｍ程度と、水平方向のリンク長に比べて圧倒的に短い。そのため、ここではチップ間リンクの長さは考慮しないものとする。まず、階層数ｎのＨ−Ｔｒｅｅを３次元化したときの総配線長Ｌ３Ｄ，ｈｔを求める。チップの枚数は４枚なので、すべての最上位リンクが長さ０のチップ間リンクに置き換えられることになる。したがって、式（４）は３次元化によって式（６）のように変化する。
【数４】
2008282108.tif 000010
【０１００】
Ｆａｔ  Ｈ−Ｔｒｅｅの場合はＲｅｄ  ＴｒｅｅとＢｌａｃｋ  Ｔｒｅｅに分けて考える。Ｒｅｄ  ＴｒｅｅはＨ−Ｔｒｅｅの３次元レイアウトと等価である（図９参照）。一方、Ｂｌａｃｋ  Ｔｒｅｅはこれに加え、最上位リンクの長さとしてそれぞれ２−ｕｎｉｔ必要となる（図１０参照）。よって総配線長は式（７）のようになる。
【数５】
2008282108.tif 000011
表４と表３を比較することにより、総配線長が３次元化によってどれだけ削減できるかが分かる。Ｆａｔ  ＴｒｅｅおよびＦａｔ  Ｈ−Ｔｒｅｅでは、３次元化によって総配線長が２５．０％から最大５０．０％削減できた。その結果、総配線長は、（２，４，２）Ｆａｔ  Ｔｒｅｅを除き、３−Ｄ  Ｔｏｒｕｓと同程度かそれ以下に削減された。
【０１０１】
（４）消費電力
１−ｆｌｉｔのデータを送信元から宛先ノードに転送するのに要する平均転送エネルギーは式（８）で計算できる。
Ｅｆｌｉｔ＝ｗＨａｖｅ（Ｅｓｗ＋Ｅｌｉｎｋ）        （８）
ただし、ｗを１−ｆｌｉｔのビット数、Ｈａｖｅを平均ホップ数、Ｅｓｗをルータが１−ｂｉｔのデータ転送に消費するエネルギー、Ｅｌｉｎｋをリンクが１−ｂｉｔのデータ転送に消費するエネルギーとする。（２）のルータとＮＩの面積において見積もったルータを、２５０ＭＨｚでの動作を仮定してゲートレベルでシミュレーションしたところ、Ｅｓｗは１．１３ｐＪとなった。
【０１０２】
一方，Ｅｌｉｎｋは式（９）で計算できる。
Ｅｌｉｎｋ＝ｄＶ２Ｃｗｉｒｅ／２      （９）
ただし、ｄを１−ｈｏｐ当たりの平均距離（ｍｍ）、Ｖを動作電圧、Ｃｗｉｒｅを配線容量とする。ここではＶを１．８Ｖとし、Ｃｗｉｒｅは０．１８μｍプロセスを仮定するとき４１４ｆＦ／ｍｍとなった。チップサイズは１２ｍｍ角とし、１６コア、６４コア、２５６コアの場合について、上記のパラメータをもとに転送エネルギーＥｆｌｉｔを計算した。
【０１０３】
表５にリピータを挿入しないときの２次元レイアウトにおける１−ｆｌｉｔ当りの転送エネルギーＥｆｌｉｔ（ｐＪ）を示す。
【表５】
2008282108.tif 000012
【０１０４】
Ｆａｔ  Ｈ−Ｔｒｅｅは畳み込みによって１−ｈｏｐ当たりの平均距離ｄが延びたが、平均ホップ数はこの中で最も小さく、消費電力においても有利となった。Ｈ−ＴｒｅｅやＦａｔ  Ｔｒｅｅはその次に平均ホップ数が小さいが、最上位リンクの利用率が高いため転送エネルギーはＦａｔ  Ｈ−Ｔｒｅｅよりも大きくなった。２−Ｄ  Ｔｏｒｕｓは畳み込みによって１−ｈｏｐ当たりの平均距離ｄが延びるため１６コアでは２−Ｄ  Ｍｅｓｈより転送エネルギーが多い。一方，２５６コアではＥｓｗのウェイトが高くなり、平均ホップ数の小さい２−Ｄ  Ｔｏｒｕｓは２−Ｄ  Ｍｅｓｈより有利になっている。
【０１０５】
チップサイズが１２ｍｍ角のとき、ツリー型トポロジにおける最長配線長はコア数によらず常に６ｍｍである。このときの配線遅延は７１５ｐｓｅｃとなり、プロセスの微細化に伴いさらに深刻化すると考えられる。そこで、マイ達の計算式（Ｈｏ，Ｒ．，Ｍａｉ，Ｋ．Ｗ．ａｎｄ  Ｈｏｒｏｗｉｔｚ，Ｍ．Ａ．：Ｔｈｅ  Ｆｕｔｕｒｅ  ｏｆ  Ｗｉｒｅｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＩＥＥＥ，Ｖｏｌ．８９，Ｎｏ．４，  ｐｐ．４９０−５０４  （２００１）参照）に基づきリピータを挿入し、配線遅延を４４１ｐｓｅｃまで抑えることができたが、新たにリピータの消費電力を考慮する必要が生じた。
【０１０６】
表６にリピータを挿入したときの２次元レイアウトにおける１−ｆｌｉｔ当り転送エネルギーＥｆｌｉｔ（ｐＪ）を示す。リピータは５ｍｍ以上のリンクに挿入するものとして計算した。
【表６】
2008282108.tif 000013
【０１０７】
上記マイ達の文献の図１０によれば、４ｍｍ以下の配線にリピータを挿入しても配線遅延の消費効果が小さいことが分かる。そこで消費電力の増加を少しでも抑えるため、リピータの挿入は５ｍｍ以上のリンクに制限した。
【０１０８】
ツリー系のトポロジの最長リンクには平均４．９個のリピータが挿入されたため，リピータを挿入しない表５と比べ、転送エネルギーが大幅に増加した。また、１６コアの２−Ｄ  Ｔｏｒｕｓにおいては畳み込みにより一部のルータ−ルータ間リンクが５ｍｍを越えたため、ツリー型トポロジと同様に転送エネルギーＥｆｌｉｔが増加した。
【０１０９】
次に、３次元レイアウトにおける転送エネルギーＥｆｌｉｔを計算する。非特許文献２によると貫通ビアの容量は４．３４ｆＦであり、本評価で仮定している配線１０．５μｍ分の容量に相当し、水平方向の配線長に比べて十分小さい。そのためチップ間リンクで消費されるエネルギーは考慮しないものとする。
【０１１０】
表７に３次元レイアウトにおける転送エネルギーＥｆｌｉｔ（ｐＪ）を示す。
【表７】
2008282108.tif 000014
【０１１１】
３次元化レイアウトでは、どのトポロジにおいても５ｍｍを越えるリンクが発生しなかったためリピータは不要となった。Ｆａｔ  Ｔｒｅｅの転送エネルギーＥｆｌｉｔは表５と比べて最大４４．３％、表６と比べて最大５９．７％削減された。同様にＦａｔ  Ｈ−Ｔｒｅｅの転送エネルギーＥｆｌｉｔは表５と比べて最大３２．８％、表６と比べて最大５３．５％削減された。このように３次元化により、配線長およびリピータを減らすことができ、結果的に転送エネルギーを大幅に減らすことができた。
【０１１２】
以上説明したように、Ｆａｔ  Ｔｒｅｅ  およびＦａｔ  Ｈ−Ｔｒｅｅの３次元レイアウトは、同サイズの２次元レイアウトに比べ、（１）配線長は２５．０％から最大５０．０％削減された、（２）配線遅延が小さくなり、挿入されるリピータ数を削減できた、（３）これにより、１フリット当りの転送エネツギーが最大５９．７％削減された。なお、３次元化によってチップ面積が最大５．０％増加したが、メッシュの３次元化に比して十分低コストになっている。このように、本発明によれば、複数のモジュール間を接続する集積電気回路の配線構造において、適正なトポロジで３次元構造を実現することにより、２次元構造に比して、ネットワークの高い性能及びハードウェアの量と機能を維持しつつ、配線長を低減し、モジュール間の通信遅延を低減することができる。
【０１１３】
以上、本発明の実施の形態について説明したが、本発明は以上の実施の形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で実施の形態に種々変更を加えられることは明白である。
【０１１４】
例えば、以上の実施の形態では、三次元集積電気回路の配線構造に６４コア又は２５６コアのＦａｔ  Ｔｒｅｅトポロジ、６４コアのＦａｔ  Ｈ−Ｔｒｅｅトポロジを適用する例について説明したが、他の４ｎコア、２ν層のＦａｔ  Ｔｒｅｅトポロジ、Ｆａｔ  Ｈ−Ｔｒｅｅトポロジにも適用可能であり、ルータの上向きリンク数ｐ、ルータの下向きリンク数ｑ、コアの上向きリンク数ｃの組み合わせについても特に制限はない。また、第１の実施の形態以外でも、交換接続手段を制御する制御信号線や電源線についてもチップ間に布設されるものは貫通ビア内に配置する構成としても良い。このように構成すると、制御系配線についても配線長を低減し、モジュール間の通信遅延を低減できる。また、以上の実施の形態では交換接続手段がルータである場合について説明したが、交換接続手段がクロスバスイッチ等の交換機のスイッチの場合についても同様に適用できる。また、以上の実施の形態では貫通ビアや無線配線が１箇所の例を主に説明したが、貫通ビアや無線配線を複数箇所に設けても良く、また、貫通ビアと無線配線とを併用しても良い。また、各電気回路領域は同一寸法の正方形又は長方形に限定されず、正三角形、正六角形や台形等の平面に隙間なく敷き詰められる形状であれば望ましいが、円形等隙間が生じる構造についても、Ｆａｔ  Ｔｒｅｅトポロジ、Ｆａｔ  Ｈ−Ｔｒｅｅトポロジを適用可能である。
【産業上の利用可能性】
【０１１５】
本発明はＬＳＩ、ＩＣ等の３次元配線に利用できる。
【図面の簡単な説明】
【０１１６】
【図１】リンク数が小さく対称な２次元レイアウトが可能なトポロジの代表例を示す図である。
【図２】６４コアＦａｔ  Ｔｒｅｅのツリー構造の例を示す図である。
【図３】６４コアＲｅｄ  Ｔｒｅｅのツリー構造の例を示す図である。
【図４】６４コアＢｌａｃｋ  Ｔｒｅｅのツリー構造の例を示す図である。
【図５】Ｒｅｄ  Ｔｒｅｅの座標とＢｌａｃｋ  Ｔｒｅｅの座標の関係を示す図である。
【図６】６４コアＦａｔ  Ｈ−Ｔｒｅｅの２次元レイアウトを示す図である。
【図７】畳み込み処理されたＦａｔ  Ｈ−Ｔｒｅｅの２次元レイアウトを示す図である。
【図８】Ｆａｔ  Ｔｒｅｅを４分割した例を示す図である。
【図９】Ｒｅｄ  Ｔｒｅｅを４分割した例を示す図である。
【図１０】Ｂｌａｃｋ  Ｔｒｅｅを４分割した例を示す図である。
【図１１】６４コア３階層のＦａｔ  Ｔｒｅｅトポロジの例を示す図である。
【図１２】６４コアＦａｔ  Ｔｒｅｅトポロジを４つのチップに分割した構成を示す図である。
【図１３】６４コアＦａｔ  Ｔｒｅｅトポロジを４つのチップに分割し、積層したときの各ランクルータ配置とルータ間配線の３次元レイアウトの概要を示す図である。
【図１４】Ｆａｔ  Ｔｒｅｅトポロジ及びＦａｔ  Ｈ−Ｔｒｅｅの配線レイアウトのアルゴリズムの大略を示す図である。
【図１５】コアのマッピングと折り畳みを説明するための図である。
【図１６】１６個のランク３ルータと８個のランク４ルータ間の配線のトポロジを示す図である。
【図１７】各第３レイヤモジュールの３次元配置とランク３ルータ、ランク４ルータの配置の例を示す図である。
【図１８】６４コアＦａｔ  Ｈ−Ｔｒｅｅトポロジの例を示す図である。
【図１９】６４コアＦａｔ  Ｈ−Ｔｒｅｅを４分割した時のＲｅｄ  Ｔｒｅｅの３次元レイアウトを示す図である。
【図２０】６４コアＦａｔ  Ｈ−Ｔｒｅｅを４分割した時のＢｌａｃｋ  Ｔｒｅｅの３次元レイアウトを示す図である。
【図２１】６４コアＦａｔ  Ｈ−Ｔｒｅｅを２分割した時のＲｅｄ  Ｔｒｅｅの３次元レイアウトの例を示す図である。
【図２２】６４コアＦａｔ  Ｈ−Ｔｒｅｅを２分割した時のＢｌａｃｋ  Ｔｒｅｅの３次元レイアウトの例を示す図である。
【図２３】２次元ＩＣと３次元ＩＣの比較を示す図である。
【符号の説明】
【０１１７】
ｉ（ｉ＝１〜３）  ランクｉルータ
ｂｉ  Ｂｌａｃｋ  Ｔｒｅｅのランクｉルータの座標
Ｂ（ｂ０，ｂ１，…，ｂｉ，…，ｂｎ）  Ｂｌａｃｋ  Ｔｒｅｅのルータの座標
（ｐ，ｑ，ｃ）  Ｆａｔ  Ｔｒｅｅのリンク構成
ｐ    ルータの上向きリンク数
ｑ    ルータの下向きリンク数
ｃ    コアの上向きリンク数
ｒｉ  Ｒｅｄ  Ｔｒｅｅのランクｉルータの座標
Ｒ（ｒ０，ｒ１，…，ｒｉ，…，ｒｎ）  Ｒｅｄ  Ｔｒｅｅのルータの座標
ｘ２Ｄ，ｙ２Ｄ，ｚ２Ｄ  コアの２次元座標
ｘ３Ｄ，ｙ３Ｄ，ｚ３Ｄ  コアの３次元座標
【図１】
2008282108.tif 000015
【図２】
2008282108.tif 000016
【図３】
2008282108.tif 000017
【図４】
2008282108.tif 000018
【図５】
2008282108.tif 000019
【図６】
2008282108.tif 000020
【図７】
2008282108.tif 000021
【図８】
2008282108.tif 000022
【図９】
2008282108.tif 000023
【図１０】
2008282108.tif 000024
【図１１】
2008282108.tif 000025
【図１２】
2008282108.tif 000026
【図１３】
2008282108.tif 000027
【図１４】
2008282108.tif 000028
【図１５】
2008282108.tif 000029
【図１６】
2008282108.tif 000030
【図１７】
2008282108.tif 000031
【図１８】
2008282108.tif 000032
【図１９】
2008282108.tif 000033
【図２０】
2008282108.tif 000034
【図２１】
2008282108.tif 000035
【図２２】
2008282108.tif 000036
【図２３】
2008282108.tif 000037