(57)【特許請求の範囲】
【請求項１】
複数個のノードと前記ノードを選択的に結合させる複数個の相互接続体とを包含する相互接続構成体Ｓにおいて、
ノードの組Ｔ、
前記ノードの組Ｔ内のノードを選択的に接続させる相互接続体の組Ｉ、
前記ノードの組Ｔと相互に排他的な装置の組Ａであって、装置の組Ａ内の装置は前記ノードの組Ｔ内の１個又はそれ以上のノードへデータを送信することが可能な装置の組Ａ、
前記ノードの組Ｔと相互に排他的な装置の組Ｚであって、装置の組Ｚ内の装置は前記ノードの組Ｔ内の１個又はそれ以上のノードからデータを受信することが可能な装置の組Ｚ、
前記ノードの組Ｔのノード副組の集合Ｃ、
を有しており、前記ノードの組Ｔ内の各ノードは以下のようにして集合Ｃの１個のメンバー内に包含されており、
前記装置の組Ｚ内の装置ｘの場合には、cx＝cx0,cx1,cx2,...、cxJが存在し、前記シーケンスcxの各メンバーは前記集合Ｃ内の一つのノードの組であり、前記シーケンスcxは前記装置の組Ａ内の装置から複数個の経路上で装置ｘへデータを通過させることが可能であり、前記複数個の経路の中で経路の組Ｐ（ｘ）は経路Ｒ上の各ノードがシーケンスcxのメンバー内にある場合にのみ経路Ｒが経路の組Ｐ（ｘ）内に包含されることを特徴としており、装置の組Ａ内の装置から直接メッセージを受信する経路Ｒのノードはノードの組cxUのメンバーであり且つ装置ｘへ直接データを送信する経路Ｒのノードはノードの組cxVのメンバーであり、ＵはＶよりも大きいものであり、
前記集合ＣのメンバーＹの場合には、メンバーＹがシーケンスcyのメンバーでもある場合にのみ装置ｙが該装置Ｚ（Ｙ）の組内に包含されるように対応する組の装置Ｚ（Ｙ）が装置の組Ｚ内に存在しており、
Ｈ＞ＫでシーケンスcxのメンバーcxH及びcxKの場合には、装置の組Ｚ（cxK）は装置の組Ｚ（cxH）の副組であり、
Ｌ＞Ｍで且つ前記装置の組Ｚ（cxM）が装置の組Ｚ（cxL）の副組である場合に前記シーケンスcxは２個のメンバーcxLとcxmとを包含しており且つ装置の組Ｚ（cxM）内に包含されていない装置の組Ｚ（cxL）内に装置が存在しており、且つ
前記ノードの組Ｔは３個の別個のノードｐ、ｑ、ｒを包含しており、ノードｐはシーケンスcxのメンバーcxD内にあり、ノードｑ及びｒは、Ｄ＞Ｅで、シーケンスcxのメンバーcxE内にあり、前記複数個の経路Ｐ（ｘ）の内の一つの経路において、メッセージがノードｐからノードｒへ直接的に移動し且つ前記複数個の経路Ｐ（ｘ）の別の経路内において、メッセージがノードｑからノードｒへ直接的に移動する、
ことを特徴とする相互接続構成体。
【請求項２】
相互接続構成体において、
ノードNEとノードの組Ｐとを包含する複数個のノードが設けられており、ノードの組ＰはノードNEへデータを送信することが可能な複数個のノードを包含しており、
前記複数個のノードを相互接続する複数個の相互接続経路が設けられており、前記相互接続経路は、ノードを対毎に相互接続するデータ相互接続経路を包含しており、ノード対は送信ノードと受信ノードとを包含しており、前記送信ノードは前記受信ノードへデータを送信することが可能であり、
ノードの組Ｐ内のノードはノードNEへデータを送信するための優先度関係を持っており、ノードの組Ｐ内のノードは別個のノードNF及びNAを包含しており、ノードNFはノードNEへデータを送信するためのノードの組Ｐ内のノードの中で最も高い優先度を持っており、従ってノードNFに到達するメッセージMFは、ノードNAに到達するメッセージMAによりノードNEへ移動することが阻止されることが無く、
ノードNAに到達するメッセージＭの場合には、メッセージＭはノードNEへ送信されることが阻止され、メッセージＭがノードNEへ送信されることが阻止されることは、メッセージＭをノードNAからノードNEとは別個のノードへ送信させる、
ことを特徴とする相互接続構成体。
【請求項３】
請求項２において、ノードNEへデータを送信することが可能なノードの組Ｐ内のノードの間の優先度関係は、相互接続構成体内のノードの組Ｐ内に個々のノードの位置に依存することを特徴とする相互接続構成体。
【請求項４】
複数個のノードと前記ノードを選択的に結合させる複数個の相互接続体とを包含する相互接続構成体Ｓにおいて、
ノードの組Ｔが設けられており、
前記ノードの組Ｔ内のノードを選択的に接続する相互接続体の組Ｉが設けられており、
前記ノードの組Ｔと相互に排他的な装置の組Ａが設けられており、装置の組Ａ内の各装置がノードの組Ｔ内のノードへデータを送信することが可能であり、
前記ノードの組Ｔと相互に排他的な装置の組Ｚが設けられており、装置の組Ｚ内の各装置がノードの組Ｔ内のノードからデータを受信することが可能であり、
一組のデータ担持経路Ｐが設けられており、経路の組Ｐの各経路が装置の組Ａ内の装置から装置の組Ｚ内の装置へデータを担持可能であり、経路の組Ｐの経路上の各ノードがノードの組Ｔ内に包含されており、且つ該経路内の各相互接続体が前記相互接続体の組Ｉ内に包含されており、
ノードの組Ｕは、経路の組Ｐ内に包含されている経路上にあるノードの組Ｔ内のノードの組として特性付けられ、
ノードＮが経路の組Ｐ内の経路上にあるようなノードの組Ｔ内のノードＮに対して、その経路がノードＮを包含するように装置の組Ａのメンバーから装置ｗへ経路の組Ｐ内に経路が存在する場合にのみ装置ｗが装置の組Ｚ（Ｎ）内に包含されるように対応する組の装置Ｚ（Ｎ）が装置の組Ｚ内に存在し、
前記ノードの組Ｕは、３個の個別的なノードNA,ND,NEを包含しており、ノードNAはノードND及びNEへデータを送信することが可能であり、且つ装置の組Ｚ（NA）は装置の組Ｚ（ND）と同じであり、且つ装置の組Ｚ（NE）は装置の組Ｚ（NA）の適切な副組である、
ことを特徴とする相互接続構成体。
【請求項５】
請求項４において、ノードNAに到達するメッセージはそのメッセージのノードNAにおける到達の時間TA内に別のノードへ送信されることを特徴とする相互接続構成体。
【請求項６】
請求項４において、更に、論理要素LAがノードNAからの経路付けを決定するノードNAと関連しており、ノードNXはノードNAとは別個であり、論理要素LXがノードNXに対する経路付けを決定するノードNXと関連しており、論理要素LXは論理要素LAとは別個である、ことを特徴とする相互接続構成体。
【請求項７】
請求項４において、更に、
前記複数個のノードがノードNFを包含しており、ノードNA、NE、NFは相互に別個であり、
複数個の論理要素が前記複数個のノードと関連しており、
複数個のデータ相互接続経路が前記複数個のノードを結合させ、データ相互接続経路が受信ノードと前記受信ノードへデータを送信することが可能な送信ノードとを包含する対毎に前記複数個のノードを結合させ、
前記送信ノードと関連するソースからの制御信号を前記受信ノードと関連する論理要素へ送信するために複数個の制御信号相互接続経路が前記複数個のノードを結合させ、
前記複数個のノードが、
ノードNAに対する経路付けの決定を行なうノードNAと関連する論理LAと、
送信ノードとして動作可能なノードNFから受信ノードとして動作可能なノードNEへのデータ相互接続経路と、
送信ノードとして動作可能なノードNAから受信ノードとして動作可能なノードNEへのデータ相互接続経路と、
送信ノードとして動作可能なノードNFと関連するソースから論理LAへの制御信号相互接続経路と、
を有しており、前記制御信号が、ノードNAからノードNEへのデータの送信よりもノードNFからノードNEへのデータの送信に対して優先度を強制する、ことを特徴とする相互接続構成体。
【請求項８】
請求項４において、更に、
前記複数個のノードがノードNFとノードの組Ｒとを包含しており、ノードNF及びNAはノードの組Ｒから排除された別個のノードであり、ノードNAはノードの組Ｒ内の各ノードへデータを送信することが可能であり、
前記複数個のデータ相互接続経路が前記複数個のノードを結合させ、データ相互接続経路が前記複数個のノードの内の一対を受信ノードへデータを送信可能な送信ノードとして結合させ、
前記複数個の制御相互接続経路が前記複数個のノードを結合させ、制御相互接続経路が制御信号送信ノードと関連するソースからの制御信号を制御信号使用ノードと関連する論理へ担持するために使用され、前記複数個の制御相互接続経路がノードNFと関連するソースからノードNAと関連する論理LAへの制御相互接続経路を包含しており、論理LAは、ノードの組ＲのどのノードへノードNAがデータを送信するかを決定するためにノードNFと関連するソースからの制御信号を使用する、
ことを特徴とする相互接続構成体。
【請求項９】
請求項４において、更に、
前記複数個のノードがノードNFを包含しており、
前記相互接続経路が制御相互接続経路とデータ相互接続経路とを包含しており、前記制御相互接続経路は制御信号送信ノードと関連するソースから制御信号使用ノードと関連する論理へ制御信号を送信することが可能であり、前記データ相互接続経路がデータ送信ノードからデータ受信ノードへデータを送信することが可能であり、
前記複数個の相互接続経路は、更に、ノードNAからノードNEへ及びノードNDへデータを送信するためのデータ相互接続経路、及びノードNFと関連するソースからノードNAと関連する論理要素LAへ制御信号を送信するための制御相互接続経路を包含しており、
ノードNFに到達するメッセージＭに対して、ノードNFと関連するソースが論理要素LAへ制御信号Ｓを送信し、論理要素LAは制御信号Ｓを使用してメッセージＭをノードNEへ送信するか又はノードNDへ送信するかを決定する、
ことを特徴とする相互接続構成体。
【請求項１０】
請求項４において、更に、
前記複数個のノードが入力データポートと、出力データポートと、ノードを介してのデータの流れを制御する複数個の論理要素とを包含しており、前記複数個のノードはノードNFを包含しており、ノードNF、NA、NE、NDは相互に別個であり、
前記複数個のデータ担持相互接続経路は、データ送信ノードの出力データポートからデータ受信ノードの入力データポートへ経路を形成するために、前記複数個のノードを結合させ、
前記複数個の制御信号相互接続経路は、制御信号に依存するデータの流れを有するノードと関連する論理要素へ制御信号を送信し、
論理要素LAはノードNAと関連しており、論理要素LAは、ノードNAを介して通過するメッセージＭをどこへ経路付けするかを決定するためにノードNFと関連するソースからの制御信号を使用し、ノードNFと関連するソースから受信した制御信号ＳはメッセージＭをノードNAからノードNEへ送信させ、ノードNFから受信した制御信号S'はメッセージＭをノードNAからノードNDへ送信させる、
ことを特徴とする相互接続構成体。
【請求項１１】
請求項４において、更に、
相互接続リンクILが相互接続体の組Ｉ内にあり、前記相互接続リンクILは経路の組Ｐ内の相互接続リンクILを包含する経路が装置の組Ａ内の装置から装置ｗへ存在する場合にのみ装置ｗが装置の組Ｚ（IL）内に包含されるように対応する組の装置Ｚ（IL）が装置の組Ｚ内に存在するような経路の組Ｐ内の経路上の相互接続リンクであり、
前記ノードの組Ｕは別個のノードNA、ND、NEを包含しており、ノードNAはリンクLAD上のノードNDへデータを送信することが可能であり、ノードNAはリンクLAE上のノードNEへデータを送信することが可能であり、装置の組Ｚ（LAE）は装置の副組Ｚ（LAD）の適切な副組である、
ことを特徴とする相互接続構成体。
【請求項１２】
相互接続構成体において、
データ送信ノード、データ受信ノード、又はデータ送信及びデータ受信の両方のノードとして機能する複数個のノードが設けられており、前記複数個のノードは相互に別個のノードNFと、ノードNAと、ノードNEと、ノードNDとを包含しており、
現在データ送信ノードとして機能しているノードから現在データ受信ノードとして機能しているノードへデータを担持することが可能な複数個の相互接続経路が設けられており、前記相互接続経路はノードNAからノードNEへデータを担持するためのデータ相互接続経路とノードNAからノードNDへデータを担持するためのデータ相互接続経路とを包含しており、前記相互接続経路はノードNFからのデータを担持するために使用する少なくとも２個のデータ相互接続経路を包含しており、
制御論理が設けられており、ノードNAではない受信ノードへノードNAを介して経路付けされるメッセージMA及びノードNFを介して経路付けされるメッセージMFに対して、ノードNFを介してメッセージMFの経路付けに関する情報が制御情報Ｃを決定するために使用され、
情報Ｃが値C1を有している場合には、メッセージMAはノードNDを介してノードNAから経路付けされ、
情報Ｃが値C2を有している場合には、メッセージMAはノードNEを介してノードNAから経路付けされる、
ことを特徴とする相互接続構成体。
【請求項１３】
請求項12において、更に、
前記複数個のノードはノードNFと、ノードNAとノードの組Ｐとを包含しており、ノードNF及びNAはノードの組Ｐ外部の別個のノードであり、ノードNAはノードの組Ｐ内の各ノードへデータを送信することが可能であり、
前記複数個のデータ相互接続経路は前記複数個のノードを結合させ、データ相互接続経路は前記複数個のノードの内の一対を受信ノードへデータを送信することが可能な送信ノードとして結合させ、
前記複数個の制御相互接続経路は前記複数個のノードを結合させ、制御相互接続経路は制御信号送信ノードと関連するソースから制御信号使用ノードと関連する論理へ制御信号を担持するために使用され、前記複数個の制御相互接続経路はノードNFと関連するソースからノードNAと関連する論理LAへの制御相互接続経路を包含しており、論理LAはノードの組Ｐ内のどのノードへノードNAがデータを送信するかを決定するためにノードNFと関連するソースからの制御信号を使用する、
ことを特徴とする相互接続構成体。
【請求項１４】
相互接続構成体Ｓにおいて、
ノードNA、ND、NEを包含する複数個のノードが設けられており、
構成体Ｓ内のノードを選択的に結合する複数個の相互接続線が設けられており、
前記複数個のノードと相互に排他的である装置の組Ｉ内の複数個の装置が設けられており、前記装置の組Ｉ内の装置は前記複数個のノードの内の一つ又はそれ以上へデータを送信することが可能であり、
前記複数個のノードと相互に排他的である装置の組Ｚ内の複数個の装置が設けられており、前記装置の組Ｚ内の装置は前記複数個のノードの内の一つ又はそれ以上からデータを受信することが可能であり、前記装置の組Ｚは複数個の装置の副組を有しており、更に、
装置の組Ｉ内の装置からノードNAを介して装置tAへメッセージを送信することが可能であるように装置tAからなる装置の副組TA、
装置の組Ｉ内の装置からノードNDを介して装置tDへメッセージを送信することが可能であるように装置tDからなる装置の副組TD、
装置の組Ｉ内の装置からノードNEを介して装置tEへメッセージを送信することが可能であるように装置tEからなる装置の副組TE、
を有しており、
ノードNAはノードNDへデータを送信することが可能であり、
ノードNAはノードNEへデータを送信することが可能であり、
装置の副組TA内の装置は装置の副組TD内に包含されており、且つ装置tAは装置の副組TA内に包含され且つ装置の副組TEから排除されて存在している、
ことを特徴とする相互接続構成体。
【請求項１５】
請求項14において、更に、
相互接続構成体Ｓを介して送信されるメッセージの通過を制御することが可能な論理Ｌが設けられており、
複数個のメッセージＰは装置の組Ｉ内の複数個の装置から複数個のノードへ送信させることが可能であり、
前記複数個のメッセージＰは装置の副組TA内のターゲット装置を有するメッセージMAを包含しており、
論理ＬはノードNAを介して装置の副組TA内の装置へメッセージMAを経路付けすることが可能である、
ことを特徴とする相互接続構成体。
【請求項１６】
請求項14において、
メッセージMAはヘッダーを有しており、
論理ＬはメッセージMAのヘッダー内の情報を使用して相互接続構成体Ｓを介してメッセージMAの経路付けを行なうことが可能である、
ことを特徴とする相互接続構成体。
【請求項１７】
請求項14において、
論理Ｌは前記複数個のノードの内の一つ又はそれ以上のノードにわたり分布されており、
前記複数個のノードはノードＮを包含しており、
ノードＮと関連する論理Ｌの論理は制御信号を使用してノードＮを介してのメッセージの経路付けを行なう、
ことを特徴とする相互接続構成体。
【請求項１８】
複数個のノードと前記ノードを選択的に結合させる複数個の相互接続体とを包含する相互接続構成体Ｓにおいて、
３個の別個のノードNA、ND、NEを包含するノードの組Ｔが設けられており、
ノードの組Ｔと相互に排他的であり且つノードの組Ｔ内の少なくとも１個のノードへデータを送信することが可能な装置を包含する装置の組Ｉが設けられており、
ノードの組Ｔと相互に排他的であり且つノードの組Ｔ内の少なくとも１個のノードからデータを受信することが可能な装置を包含する装置の組Ｚが設けられており、
相互接続構成体Ｓを介して装置の組Ｚ内の装置へデータを担持することが可能な複数個の経路Ｐが設けられており、
装置の組Ｉ内の装置からノードNAを介して装置の副組TA内の装置へ経路の組Ｐ内の経路上をメッセージを送信することが可能であるように装置の副組TAが存在しており、
装置の組Ｉ内の装置からノードNDを介して装置の副組TD内の装置へ経路の組Ｐ内の経路上をメッセージを送信することが可能であるように装置の副組TDが存在しており、
装置の組Ｉ内の装置からノードNEを介して装置の副組TE内の装置へ経路の組Ｐ内の経路上をメッセージを送信することが可能であるように装置の副組TEが存在しており、
ノードNAは経路の組Ｐ内の経路に沿ってノードNDへデータを送信することが可能であり、
ノードNAは経路の組Ｐ内の経路に沿ってノードNEへデータを送信することが可能であり、
装置の副組TA内の装置は装置の副組TD内に包含されており、
装置の副組TE内には包含されていないが装置の副組TA内に包含されている装置が存在する、
ことを特徴とする相互接続構成体。
【請求項１９】
複数個のノードと前記ノードを選択的に結合させる複数個の相互接続体とを包含する相互接続構成体Ｓにおいて、
３個の別個のノードNA、NC、NEを包含するノードの組Ｔが設けられており、
ノードの組Ｔと相互に排他的であり且つノードの組Ｔ内の少なくとも１個のノードへデータを送信することが可能な装置を包含している装置の組Ｉが設けられており、
ノードの組Ｔと相互に排他的であり且つノードの組Ｔ内の少なくとも１個のノードへデータを受信することが可能な装置を包含している装置の組Ｚが設けられており、
相互接続構成体Ｓを介して装置の組Ｚ内の装置へデータを担持することが可能な複数個の経路Ｐが設けられており、
装置の組Ｉ内の装置からノードNAを介して装置の副組TA内の装置へ経路の組Ｐ内の経路上をメッセージを送信することが可能であるように装置の副組TAが存在しており、
装置の組Ｉ内の装置からノードNCを介して装置の副組TC内の装置へ経路の組Ｐ内の経路上をメッセージを送信することが可能であるように装置の副組TCが存在しており、
装置の組Ｉ内の装置からノードNEを介して装置の副組TE内の装置へ経路の組Ｐ内の経路上をメッセージを送信することが可能であるように装置の副組TEが存在しており、
ノードNCは経路の組Ｐ内の経路に沿ってノードNEへデータを送信することが可能であり、
ノードNAは経路の組Ｐ内の経路に沿ってノードNEへデータを送信することが可能であり、
装置の副組TC内の装置は装置の副組TE内に包含されており、
装置の副組TE内には包含されないが装置の副組TA内に包含される装置が存在している、
ことを特徴とする相互接続構成体。
【請求項２０】
請求項19において、更に、
ノードNAと関連する論理LAがノードNAからのデータの流れを制御し、ノードNAに到達するメッセージはヘッダーを有しており且つ論理LAはヘッダー内の情報及び／又はノードNCからの情報を使用してメッセージＭをどこへ送信するかを決定する、
ことを特徴とする相互接続構成体。
【請求項２１】
メッセージを送信するための通信相互接続構成体において、
以下のものを包含する構成体に配設されている複数個のノードと、
ソースレベルからデスティネーションレベルへのレベルの階層、
レベルの断面をスパンする複数個のノード、
断面スパン内の複数個のノード、尚ノードのレベルは前記構成体におけるノードの位置によって完全に決定され、
レベルＬ上のノードＮに対して以下のものを包含する前記構成体内のノードを結合させる複数個の相互接続線と、
前のレベルＬ＋１上のノードへ結合されているメッセージ入力相互接続線、
レベルＬ上のノードへ結合されているメッセージ入力相互接続線、
レベルＬ上のノードへ結合されているメッセージ出力相互接続線、
後のレベルＬ−１上のノードＸへ結合されているメッセージ出力相互接続線、
レベルＬ−１上のノードＸとは別個のノードのメッセージ出力相互接続線へ結合されている制御入力相互接続線、
制御入力相互接続線上のメッセージを受信し且つ、そのメッセージに従って、後のレベルＬ−１ノードへ結合されているメッセージ出力相互接続線上又はレベルＬへ結合されているメッセージ出力相互接続線上にバッファリング無しでメッセージを選択的に送信するべく結合されているスイッチ、
を有することを特徴とする通信相互接続構成体。
【請求項２２】
通信相互接続構成体において、
複数個のノードと、
前記ノードを結合させる複数個の相互接続線と、
を有しており、前記複数個のノードの内のノードＸが、
ノードＸとは別個のノードＡへ結合されているメッセージ入力相互接続線、
ノードＡ及びノードＸとは別個のノードＢへ結合されているメッセージ入力相互接続線、
を具備しており、ノードＸはノードＡからのメッセージ入力及びノードＢからのメッセージ入力を受け付け、競合するメッセージの間の優先度関係を決定する制御信号を通信するためにノードＡとノードＢとの間に制御相互接続線が結合されており、前記制御信号はノードＡからノードＸへのメッセージの送信とノードＢからノードＸへのメッセージの送信との間の優先度関係を強制する、
ことを特徴とする通信相互接続構成体。
【請求項２３】
相互接続装置において、
複数個のノードと、
階層的多重レベル構成体におけるノードを選択的に結合させる相互接続構成体内の複数個の相互接続線と、
を有しており、前記階層的多重レベル構成体は、
最下位デスティネーションレベルL0から前記最下位デスティネーションレベルL0から最も遠い最高位レベルLJへ配列されたレベルからなる階層におけるＪ＋１複数個のレベルを包含しており、ノードのレベルは前記構成体内におけるそのノードの位置によって完全に決定され、前記相互接続構成体がメッセージＭを複数個の別個の時間ステップで送信し、メッセージＭは時間ステップにおいて移動し、且つ前記相互接続構成体は以下のものを包含する時間ステップにおいて３つの態様の内の一つでメッセージＭを移動させる相互接続を有しており、
メッセージＭが前記相互接続構成体外部の装置から前記相互接続構成体内のノードへ入り、
メッセージＭが前記相互接続構成体から指定された出力バッファへ出、
メッセージＭがレベルLk上のノードＵから同一のレベルLk上の異なるノードＶへ移動するか又はノードＵからレベルLi上のノードＷへ移動し、尚ｋはｉよりも大きく、従ってレベルLiはレベルLkよりもデスティネーションレベルL0に一層近く、且つノードＵはメッセージＭをどこへ送信するかを決定するためにノードＶ及びノードＷとは別個のソースからの制御信号を使用する、
ことを特徴とする相互接続装置。
【請求項２４】
相互接続装置において、
複数個のノードと、
メッセージＭを複数個の別個の時間ステップで送信する相互接続構成体内のノードを選択的に結合させる複数個の相互接続線と、
を有しており、
ノードNDは前記相互接続構成体内のノードNAからの直接的入力相互接続及び前記相互接続構成体外部の装置Ｇからの直接的入力相互接続を有しており、
ノードNAからの直接的入力相互接続は外部装置Ｇからの直接的入力相互接続を上回る優先度を有しており、従って外部装置ＧからノードNDへ指向されるメッセージMGと同一の時間ステップにおけるノードNAからノードNDへ指向されるメッセージMAは、ノードNAからノードNDへ成功裏に移動し且つメッセージMGは逸らされ、
ノードNDと別個のノードNAは前記相互接続構成体外部の装置Ｇへの直接的制御相互接続を有しており、前記制御相互接続はメッセージブロック用コマンドを送信するためである。
ことを特徴とする相互接続装置。
【請求項２５】
相互接続装置において、
複数個のノードと、
階層的多重レベル構成体内のノードを選択的に結合させる複数個の相互接続線と、
を有しており、ノードのレベルは前記構成体内のそのノードの位置によって完全に決定され、データはソースレベルからデスティネーションレベルへ一方的にのみ又は前記多重レベル構成体のレベルに沿って横方向に移動し、データメッセージは前記多重レベル構成体を介してソースノードから指定されたデスティネーションノードへ送信され、多重レベルの内の一つのレベルは１個又はそれ以上のグループのノードを包含しており、データメッセージはデスティネーションノードへの途中にある前記１個又はそれ以上のグループのノードの内の一つのグループへ送信され、前記１個又はそれ以上のグループの内の一つのグループは複数個のノードを包含しており、ノードがブロックされていない場合にはデスティネーションレベルへ向かって一方的に一つのグループの複数個のノードの内のノードＮへデータメッセージが送信され、且つそうでなくそのノードがブロックされている場合には、データメッセージが横方向に送信され、ノードＮへ一方的に送信を行なうノードはノードＮとは別個のノードによってノードＮにおいて潜在的なブロック条件が忠告される、
ことを特徴とする相互接続装置。
【請求項２６】
別個の時間ステップからなるシーケンスでメッセージを通信するネットワークにおいて、
複数個のノードが設けられており、前記ノードはメッセージを受信し且つメッセージを送信する通信装置を包含しており、
複数個のノードにおいて通信装置を相互接続する複数個の相互接続線Ｌが設けられており、前記複数個のノードの内のノードＮは、
装置ＵからノードＮへメッセージを送信するための相互接続線LUNへの接続、
装置ＶからノードＮへメッセージを送信するための相互接続線LVNへの接続、
を包含しており、
本ネットワークはノードＮと装置Ｕ及びＶとに関連する優先度関係PN（U,V）を有しており、ノードＮへメッセージを送信する場合に装置Ｕは装置Ｖよりも優先度を有しており、従って、時間ステップｔにおいて相互接続線LUNを介してノードＮへ指向される装置ＵにおけるメッセージMU及び同じく時間ステップｔにおいて相互接続線LVNを介してノードＮへ指向される装置ＶにおけるメッセージMVに対して、メッセージMUは成功裏にノードＮへ送信され且つノードＶはノードＶから直接にメッセージを受信することが不可能なノードからの制御信号を使用してそのメッセージMVをどこへ送信するかを決定する、
ことを特徴とするネットワーク。
【請求項２７】
ネットワークにおいて、
複数個のノードＮが設けられており、
所定のパターンで前記複数個のノードＮを接続する複数個の相互接続線Ｌが設けられており、前記相互接続線はメッセージＭと制御信号Ｃを担持し、メッセージＭ及び制御信号Ｃは別個の時間ステップｔにおいて前記複数個のノードの内の一つのノードによって受信され、メッセージＭは直ぐ後の別個の時間ステップｔ＋１において前記複数個のノードの内の後のノードへ移動され、前記複数個の相互接続線Ｌは、
メッセージMAを受信するためのメッセージ入力相互接続部と、制御信号CAを受信するための制御入力相互接続部と、ノードNDへの直接的メッセージ出力相互接続部と、ノードNEへの直接的メッセージ出力相互接続部と、装置Ｇへの直接的制御出力相互接続部と、
（１）ノードND及びノードNEとは別個のソースからの制御信号CA、
（２）前記複数個の相互接続線Ｌ内のノードNAの位置、
（３）メッセージMA内に包含されている経路付け情報、
に基づいてメッセージMAをノードNDへ又はノードNEへ送信するかを決定するための制御論理と、を具備しているノードNA、
を包含すべく前記複数個のノードＮを接続している、
ことを特徴とするネットワーク。
【請求項２８】
相互接続装置において、
複数個のノードＮ、
所定のパターンで前記複数個のノードＮを接続する複数個の相互接続線Ｌ、を有しており、前記複数個の相互接続線Ｌは、
メッセージMAを受信するための直接的メッセージ入力相互接続部を具備しており且つメッセージMAを受信するために最も好適な好適ノードNPを包含する複数個のノードへメッセージMAを送信する複数個の直接的メッセージ出力相互接続部を具備しているノードNA、
を包含すべく複数個のノードＮを接続しており、前記好適ノードNPはメッセージMAのヘッダー内の経路付け情報及び前記複数個の相互接続線Ｌ内のノードNAの位置にのみによって決定されるものであり、
前記好適ノードNPは好適ノードNPへメッセージを送信するための優先度を有している優先ノードNBを包含する複数個のノードからのメッセージMPを受信するための複数個の直接的メッセージ入力相互接続部を具備しており、前記優先ノードNBは前記複数個の相互接続線Ｌ内のノードNBの位置によって決定されるものであり、従って、
ノードNAがノードNBと同一である場合には、メッセージMAはメッセージMPであり且つノードNAからノードNPへ送信され、且つ
ノードNAがノードNBと同一でなく且つノードNBがメッセージMBをノードNPへ指向させる場合には、メッセージMBはノードNBからノードNPへ送信され、且つノードNAは制御信号を使用してメッセージMAをどこへ送信するかを決定し、前記制御信号はノードNAから直接的にメッセージを受信することが可能なノードから発生したものではない、
ことを特徴とする相互接続装置。
【請求項２９】
複数個のメッセージを同時的に担持することが可能なネットワークにおいて、
複数個の出力ポートＰが設けられており、
複数個のノードＮが設けられており、個々のノードＮは複数個の直接的メッセージ入力相互接続部と複数個の直接的メッセージ出力相互接続部とを包含しており、前記個々のノードＮはメッセージＭを前記複数個の出力ポートＰの内の所定の出力ポートへ通過させ、前記所定の出力ポートＰはメッセージＭによって指定されるものであり、
最下位デスティネーションレベルL0から該最下位デスティネーションレベルL0から最も遠い最上位レベルLJへ配設されているレベルの階層内のＪ＋１複数個のレベルを包含すべく配設されている階層的多重レベル構成体内のノードを選択的に結合させる相互接続構成体内に複数個の相互接続線が設けられており、前記出力ポートＰは最下位デスティネーションレベルL0におけるノードに接続されており、ノードのレベルは完全に前記構成体におけるそのノードの位置によって決定されるものであり、
本ネットワークは前記複数個のノードＮの内のノードNAを包含しており、ノードNAから発生したものではない制御信号はノードNAの所定の出力ポートの競合を排除するためにノードNAへ送信されることが許容されるメッセージの数を制限すべく作用し、従ってメッセージＭはノードNAの直接的メッセージ出力接続部を介してノードNAのレベルよりも高くないレベルＬのノードNHへ送信され、ノードNHはメッセージＭの指定された所定の出力ポートＰへの経路上にある、
ことを特徴とするネットワーク。
【請求項３０】
相互接続装置において、
複数個のノード、
Ｊ＋１複数個のレベルを包含すべく配設された階層的多重レベル構成体におけるノードを選択的に結合させる相互接続構成体における複数個の相互接続線、
を有しており、Ｊは最下位デスティネーションレベルL0から最下位レベルLJへ配設されたレベルからなる階層において０より大きな整数であり、ノードのレベルは完全に前記構成体におけるそのノードの位置によって決定されるものであり、前記相互接続構成体は前記相互接続構成体に入る複数個のマルチビットメッセージをソートせずに複数個の入力ポートを介して送信し、前記複数個のメッセージの内の個々のメッセージＭは自己経路付けを行い、複数個の態様で移動する個々のメッセージＭはメッセージＭによって指定される出力ポートを介して前記相互接続構成体を出るためにメッセージＭに対して十分な３つの態様を包含しており、これら三つの態様は、
（１）メッセージＭが前記相互接続構成体外部の装置から前記相互接続構成体における一つのノードへ入り、前記メッセージＭが一つ又はそれ以上の指定出力ポートを指定し、
（２）メッセージＭが指定出力ポートへバッファすること無しに前記相互接続構成体における一つのノードを介して移動し、
（３）メッセージＭが同一レベルLk上の異なるノードＶへバッファ無しで前記相互接続構成体のレベルLk上のノードＵを介して移動するか、又はレベルLkよりもデスティネーションレベルL0へ前記階層において一層近いレベルLi上のノードＷへバッファ無しで前記相互接続構成体のレベルLk上のノードＵを介して移動し、且つノードＵはメッセージＭをどこへ送信するかを決定するためにノードＶ及びノードＷとは別のソースからの制御信号を使用する、
ことを特徴とする相互接続装置。
【請求項３１】
相互接続装置において、
複数個のノード、
構成体におけるノードを選択的に結合する相互接続構成体における複数個の相互接続線、
を有しており、前記相互接続構成体は前記相互接続構成体へ入る複数個のマルチビットメッセージをソートせずに複数個の入力ポートを介して送信し、前記複数個のメッセージの個々のメッセージＭは自己経路付けを行い、前記相互接続構成体は、
ノードNAからの第１データ入力相互接続部及びノードNAとは別のノードNFからの第２データ入力相互接続部を具備しているノードNE、及び
ノードNAとノードNFとの間の制御相互接続部、
包含しており、前記制御相互接続部はノードNEへメッセージを送信するための競合を解決するための制御信号を担持し、前記制御信号はメッセージが通信されているノードNEとは別個のノードNA又はノードNFから供給される、
ことを特徴とする相互接続装置。
【請求項３２】
通信相互接続構成体において、
複数個のノード、
前記ノードを結合する複数個の相互接続線、
を有しており、前記複数個のノードの内のノードＸは、
ノードＸとは別個のノードＡへ結合されているメッセージ入力相互接続線と、
ノードＡ及びノードＸとは別個のノードＢへ結合されているメッセージ入力相互接続線と、
を具備しており、ノードＸは、競合するメッセージ間での優先度関係を決定するためにノードＡとノードＢとの間で通信する制御信号で、ノードＡからのメッセージ入力及びノードＢからのメッセージ入力を受け付け、前記制御信号は、ノードＡからノードＸへのメッセージの送信とノードＢからノードＸへのメッセージの送信との間の優先度関係を強制する、
ことを特徴とする通信相互接続構成体。
【請求項３３】
相互接続装置において、
複数個のノード、
最下位デスティネーションレベルL0から前記最下位デスティネーションレベルL0から最も遠い最高位レベルLJへ配設されたレベルの階層におけるＪ＋１複数個のレベルを包含すべく配設された階層的多重レベル構成体におけるノードを選択的に結合させる相互接続構成体における複数個の相互接続線、
を有しており、ノードのレベルは前記構成体におけるそのノードの位置によって完全に決定され、前記相互接続構成体は複数個の個別的な時間ステップにおいてメッセージＭを送信し、メッセージＭは時間ステップで移動し且つ前記相互接続構成体はメッセージＭを時間ステップにおいて以下を包含する三つの態様の内の一つで移動し、
メッセージＭが前記相互接続構成体外部の装置から前記相互接続構成体内の一つのノードへ入り、
メッセージＭが指定された出力バッファへ前記相互接続構成体を出、
メッセージＭがレベルLk上のノードＵから同一のレベルLk上の異なるノードＶへ移動するか又はノードＵからレベルLi上のノードＷへ移動し、その場合にｋはｉよりも大きく、従ってレベルLiはレベルLkよりもデスティネーションレベルL0へ一層近い、
ことを特徴とする相互接続装置。
【請求項３４】
相互接続装置において、
複数個のノード、
階層的多重レベル構成体におけるノードを選択的に結合させる複数個の相互接続線、
を有しており、ノードのレベルは、その中でデータがソースレベルからデスティネーションレベルへ一方的にのみ又は前記多重レベル構成体のレベルに沿って横方向に移動する前記構成体内のそのノードの位置によって完全に決定され、データメッセージは前記多重レベル構成体を介してソースノードから指定されたデスティネーションノードへ送信され、多重レベルの内の一つのレベルは、一つ又はそれ以上のグループのノードを包含しており、データメッセージはデスティネーションノードへの途中にある一つ又はそれ以上のグループのノードの内の一つのグループへ送信され、前記一つ又はそれ以上のグループの内の一つのグループは、複数個のノードを包含しており、データメッセージは、そのノードがブロックされていない場合には、デスティネーションレベルへ向かって一方的に一つのグループの複数個のノードの内のノードＮへ送信され、且つ、そうでない場合、データメッセージは、そのノードがブロックされている場合には、横方向に送信される、
ことを特徴とする相互接続装置。
【請求項３５】
個別的な時間ステップからなるシーケンスでメッセージを通信するネットワークにおいて、
複数個のノードが設けられており、前記ノードはメッセージを受信し且つメッセージを送信する通信装置を包含しており、
前記複数個のノードにおける通信装置を相互接続する複数個の相互接続線Ｌが設けられており、前記複数個のノードの内のノードＮは、
装置ＵからノードＮへメッセージを送信するために相互接続線LUNへの接続部と、
装置ＶからノードＮへメッセージを送信するために相互接続線LVNへの接続部と、
を包含しており、
本ネットワークは、ノードＮへメッセージを送信する場合に装置Ｕが装置Ｖよりも優先性を有するようにノードＮ及び装置Ｕ及びＶに関連する優先度関係PN（U,V）を具備しており、従って、装置ＵにおけるメッセージMUが時間ステップｔにおいて相互接続線LUNを介してノードＮへ指向され且つ装置ＶにおけるメッセージMVも時間ステップｔにおいて相互接続線LVNを介してノードＮへ指向される場合に、メッセージMUが成功裏にノードＮへ送信され且つノードＶが制御信号を使用してメッセージMVをどこへ送信するかを決定する、
ことを特徴とするネットワーク。
【請求項３６】
ネットワークにおいて、
複数個のノードＮ、
所定のパターンで前記複数個のノードＮを接続する複数個の相互接続線Ｌ、を有しており、
前記相互接続線はメッセージＭ及び制御信号Ｃを担持し、メッセージＭ及び制御信号Ｃは個別的時間ステップｔにおいて前記複数個のノードの内の一つのノードによって受信され且つメッセージＭは直ぐ後の別個の時間ステップｔ＋１において前記複数個のノードの内の後のノードへ移動され、前記複数個の相互接続線Ｌは、メッセージMAを受信するためのメッセージ入力相互接続部と、制御信号CAを受信するための制御入力相互接続部と、ノードNDへの直接的メッセージ出力相互接続部と、ノードNEへの直接的メッセージ出力相互接続部と、装置Ｇへの直接的制御出力相互接続部と、
（１）制御信号CA、
（２）複数個の相互接続線Ｌ内のノードNAの位置、
（３）メッセージMA内に包含されている経路付け情報、
に基づいてメッセージMAがノードNDへ又はノードNEへ送信されるかを決定する制御論理と、を具備するノードNAを包含するために前記複数個のノードＮを接続する、
ことを特徴とするネットワーク。
【発明の詳細な説明】
技術分野
本発明は、計算及び通信システム用の相互接続構成体に関するものである。更に詳細には、本発明は、制御回路及び論理回路が最少とされているマルチレベル相互接続構成体に関するものである。
背景技術
例えばスーパーコンピュータを含む多くの進化した計算システムは、並列システムと呼ばれる性能を改善するために複数個の計算装置を利用する。並列計算装置間の相互接続システムは性能を決定するための重要な特性である。並列計算装置を相互接続するための１つの技術はネットワーク要素のグループがスイッチングシステムへ接続されている電話回線に類似した通信ネットワークを構築することを包含している。スイッチングシステムは階層態様で相互接続され、従って任意のスイッチングステーションが動作可能な数の接続を管理する。
ネットワーク接続の１つの欠点は、メッセージの伝送がネットワークの幾つかの段階を経て行なわれるので、別の計算装置へのアクセスの待ち時間が増加するということである。典型的に、ネットワークが多数のメッセージで飽和している場合にピーク活動期間が発生し、従って多数のメッセージが同時的にスイッチングステーションを使用すべく競争する。渋滞を減少させ、伝送速度を改善し且つ妥当なコストを達成する目標を持って種々のネットワークタイプが考案されている。これらの目標は、典型的に、ノード間の迅速な通信及びノードがサポートせねばならない相互接続数を最少とすることによって達成される。
１つの従来の相互接続構成は、複数個のノードからなるリングであり、各ノードが２つのその他のノードへ接続しており、従って相互接続のラインが円を形成する。計算技術におけるリングネットワークのスタンダードな定義に従って（IBM計算の辞書（IBM  Dictionary  of  Computing）、McDaniel  G.編、マックグローヒル、インコポレイテッド、1994、584頁）、リングの定義は、閉じた経路を形成するために単一方向伝送リンクによって装置が接続されているネットワーク形態である。別の簡単な従来の構成は、メッシュであり、その場合には、各ノードがその４つの最も近い隣りのものへ接続している。リング及びメッシュ技術は、効果的に、１個のノードによってサポートされる相互接続の数を制限する。然しながら、リング及びメッシュネットワークは、典型的に、メッセージ通信における長い遅延によって影響を受ける。何故ならば、１つのノードから別のノードへメッセージを送る場合に遭遇するノードの数が極めて大きなものである場合があるからである。これらの長い遅延は、一般的に、計算装置をして該装置へ伝送中のメッセージを待機するためにアイドル状態とさせる。
一般的に、電話回線で開始する、初期のネットワークは、回線交換を利用しており、その場合に、各メッセージは通信相手間の単一の回路を介しての直接の接続に類似した通信機関に対してリザーブされる専用経路に沿ってのネットワークを介して経路付けされる。回路交換は、長いセットアップ時間を必要とするという欠点を有している。このような遅延は異なる計算装置間で行なわれる短く且つ迅速な交換期間中に許容可能なものではない。更に、専用経路はシステム帯域幅を浪費させるものである。回線交換を使用する場合に発生する場合の問題を解決する１つの技術は、パケット交換と呼ばれるものであり、その場合に、１つの計算装置から別の計算装置へ送られるメッセージは専用回路へ連続的なストリームの形態で伝達するものではない。その代わりに、各計算装置はメッセージを一連のデータパケットへ細分化するノードへ接続されている。１つのメッセージはアドレス情報によって先行される二進デジットからなる任意のシーケンスを有している。全メッセージの長さは定義された最大長へ制限されている。少なくとも宛先アドレス及びシーケンス番号を有する「ヘッダー」が各パケットに取付けられ、且つパケットがネットワークを介して送られる。アドレスが読取られ且つパケットが１秒より小さな時間以内に送給される。回路セットアップ遅延が課されることはない。何故ならば、どの回路もセットアップされないからである。２つの計算装置間での個別的な接続は存在しないので、システム帯域幅が浪費されることはない。然しながら、情報、ヘッダー及びその他の制御情報を経路付けさせるために、通信能力の小さな部分が使用される。通信が孤立された短いバーストで前進する場合には、パケット交換はネットワーク能力をより効率的に利用する。個別的な計算装置に対して何等伝送能力が特に予約されているものではないので、パケット間の時間ギャップは他のユーザからのパケットで充填される。パケット交換は、全てのユーザが継続的にネットワーク上のラインを共用することを可能とすることにより、１つのタイプの分散型マルチプレクス（多重化）システムを実現している。
技術における進化は、コンピュータシステムの性能を改善させる。然しながら、これらの技術的進化が実現される態様は、著しく性能における改良の範囲を決定する。例えば、完全に光学的な計算から発生する性能上の改善は、光学技術の利点を最も良く使用する相互接続技術に強く依存する。
発明の開示
本発明によれば、マルチレベル最少論理ネットワーク相互接続構成体が非常に高い帯域幅及び低い待ち時間を有している。相互接続構成体スイッチングの制御は、該構成体内の複数個のノードの間に分散されており、従ってグローバルな制御機能を提供する監視制御器は必要ではない。グローバル制御機能は取除かれており且つ複雑な論理構成は、該相互接続構成体を介して通信するメッセージのタイミング及び位置決めに基づいている新規なデータ流れ技術によって回避されている。更に、該相互接続構成体は、「偏向（defelction）」又は「ホットポテト（hot  patato）」構成を実現し、その場合に、所望の出力ポートが使用可能となるまでパケットを保持するのではなく付加的な出力ポートを介してメッセージパケットをルーチング即ち経路付けさせることによって、各ノードにおける処理及び格納オーバーヘッドを最少とさせている。従って、ノードにおけるバッファの使用を取除いている。グローバル制御器及びノードにおけるバッファ機能の除去は、相互接続構成体における制御及び論理構成の量を著しく減少させ、全体的な制御構成要素及びネットワーク相互接続構成要素を簡単化させ、メッセージ通信の速度性能を改良し且つ潜在的に相互接続コストを実質的に減少させている。相互接続構成体の実現は高度に柔軟性があり、従って、完全に電子的、完全に光学的及び混合電子・光学実施例が達成される。全て光学的なスイッチを使用する実現例は、独特の簡単な論理を使用するノード及び該ノードにおけるバッファ機能の除去によって簡単化されている。
マルチレベル最少論理ネットワーク相互接続アーキテクチュアは種々の目的のために使用される。例えば、ある実施例においては、該アーキテクチュアは例えばスーパーコンピュータ等の膨大な並列コンピュータに対する相互接続構成体として使用される。その他の例示的な実施例においては、該アーキテクチュアは１つのグループのワークステーション、コンピュータ、端子、ATM装置、全国飛行制御システムの構成要素等をリンクさせる相互接続構成体を形成する。別の利用は、種々の遠距離通信適用例における相互接続構成体又はビジネスメインフレームにおいて動作する多数のスケジューラー用の相互接続構成体である。
本発明の１つの側面によれば、相互接続装置が、複数個のノードを包含すると共に、そのレベルが豊富に相互接続されたリングの集まりを包含するマルチレベル構成体における該ノードを選択的に接続する複数個の相互接続線を包含している。該マルチレベル構成体は、レベルの階層において複数個のＪ＋１個のレベルを包含しており且つ各レベルにおいて複数個の2JK個のノードを包含している。整数Ｋが奇数である場合には、レベルＭ上のノードは2J-M個のリング上に位置されており、各リングは2MK個のノードを包含している。メッセージデータがレベル０上においてノードから相互接続構成体を出る。各ノードは複数個の通信端子を有している。幾つかはメッセージデータ入力及び出力端子である。その他のものは制御入力及び出力端子である。例えば、最も内側のレベルであるレベル０上のノードＡはレベル０上のノードＢからのメッセージデータを受取り、更にレベル１上のノードＣからのメッセージデータも受取る。ノードＡはレベル０上のノードＤへメッセージデータを送り、且つ、更に、典型的に該相互接続構成体外側である装置Ｅへメッセージデータを送る。装置Ｅの１つの例は計算装置の入力バッファである。ノードＡは一般的には該相互接続構成体の外側にある装置Ｆから制御入力信号を受取る。装置Ｆの一例は計算装置の出力バッファである。ノードＡはレベル１上のノードＧへ制御信号を送る。
全てのメッセージデータは最も外側のレベルＪ上において該装置接続構成体へエンターする。例えば、最も外側のレベルであるレベルＪ上のノードＡは、レベルＪ上のノードＢからのメッセージデータを受取り、且つ、更に、該相互接続構成体の外側である装置Ｃからのメッセージデータを受取る。装置Ｃの一例は、計算装置の出力バッファである。ノードＡはレベルＪ上のノードＤへメッセージデータを送り、且つ、更に、レベルＪ−１上のノードＥへメッセージデータへ送る。ノードＡはレベルＪ−１上のノードＦからの制御入力信号を受取る。ノードＡは典型的に該相互接続構成体の外部である装置Ｇへ制御信号を送る。装置Ｇの一例は計算装置の出力バッファである。
最も内側のレベル０と最も外側のレベルＪとの間のノードは、他のノード間においてメッセージデータ及び制御信号を通信する。例えば、レベル０でもレベルＪでもないレベルＴ上のノードＡは、レベルＴ上のノードＢからのメッセージデータを受取り、且つ、更に、レベルＴ＋１上のノードＣからのメッセージデータを受取る。ノードＡはレベルＴ上のノードＤへメッセージデータを送り、且つ、更に、レベルＴ−１上のノードＥへメッセージデータを送る。ノードＡはレベルＴ−１上のノードＦから制御入力信号を受取る。ノードＡはレベルＴ＋１上のノードＧへ制御信号を送る。
レベルＭは2J-M個のリングを有しており、各々はレベルＭ上で全部で2JK個のノードに対し2MK個のノードを有している。特に、
レベル０は2J個のリングを有しており、各々はレベル０上で全部で2JK個のノードに対し20K＝Ｋ個のノードを有している。
レベル１は2J-1個のリングを有しており、各々は、レベル１上で全部で2JK個のノードに対し21K＝2K個のノードを有している。
レベル２は2J-2個のリングを有しており、各々は、レベルＭ上で全部で2JK個のノードに対し22K＝4K個のノードを有している。
・・・
・・・
・・・
レベルＪ−２は2J-(J-2)＝４個のリングを有しており、各々は、レベルＪ−２上において全部で2JK個のノードに対し2(J-2)K個のノードを有している。
レベルＪ−１は2J-(J-1)＝２個のリングを有しており、各々はレベルＪ−１上で全部で2JK個のノードに対し2(J-1)K個のノードを有している。
レベルＪは2J-J＝１個のリングを有しており、レベルＪ上において全部で2JK個のノードに対し2(J-1)K個のノードを有している。
最も外側のレベルＪではないレベルＴ上のリングRTの場合には、レベルＴ＋１上の１個のリングRT+1が存在し、従って、リングRT上の各ノードＡはリングRT上のノードＢ及びリングRT+1上のノードＣからのデータを受取る。最も内側のレベル０ではないレベルＴ上のリングRTの場合には、レベルＴ−１上に正確に２個のリングR1T-1及びR2T-1が存在しており、従って、リングRT上のノードＡはリングRT上のノードＤ及びリングR1T-1又はリングR2T-1のいずれかの上のノードＥへメッセージデータを送る。該相互接続構成体の任意のレベルＭ上のメッセージは、レベルＭ−１上のリングのうちの２つへ進行することが可能であり且つ、究極的に、レベル０上のリングのうちの2M個へ進行することが可能である。
以下の説明において、ノードの「先行体（predecessor）」はそのノードへメッセージデータを送る。「直近の先行体（immediate predecessor）」同一のリング上の１個のノードへメッセージデータを送る。ノードの「後続体（successor）」はそのノードからメッセージデータを受取る。「直近の後続体」は同一のリング上の１個のノードへのメッセージデータを受取る。
レベルＴ上のリングRT上のノードARTの場合には、レベルＴのリングRT上にノードBRT及びDRTが存在しており、従って、ノードBRTはノードARTの直近の先行体であり且つノードDRTはノードARTの直近の後続体である。ノードARTはノードBRTからメッセージデータを受取り且つノードDRTへメッセージデータを送る。ノードARTはリングRT上にない装置Ｃからのメッセージデータを受取り且つリングRT上にない装置Ｅへデータを送る。そのレベルが最も内側のレベル０ではない場合には、装置ＥはレベルＴ−１上のノードであり、且つ装置Ｅと同一のリング上に直近の先行体ノードＦが存在している。ノードARTは装置Ｆから制御情報を受取る。ノードARTが０に等しいノードＴ上にある場合には、装置Ｅは該相互接続構成体の外側にあり且つ装置ＥはノードARTへ制御情報を送る。例えば、装置Ｅが計算装置の入力バッファである場合には、装置ＥからノードARTへの制御情報はノードARTに対して、装置ＥがノードARTからのメッセージデータを受取る準備がされているか否かを表わす。ノードDRTはリングRT上にはない装置Ｇからメッセージデータを受取る。ノードARTは装置Ｇへ制御信号を送る。
制御情報は該相互接続構成体におけるデータ伝送のコンフィリクト即ち競合を解決するために伝送される。各ノードは隣接する外側レベル上のノードに対する後続体であり且つ同一のレベル上のノードに対する直近の後続体である。直近の後続体からのメッセージデータは優先性を有している。制御情報があるレベル上のノードから隣接する外側レベル上のノードへ送られて切迫した競合の警告を与える。
レベルが均一に離隔されており且つ各リング上及び各レベル上のノードが均一に離隔されている場合には、該相互接続構成体は３次元円筒状構成体を形成する。該相互接続構成体は、装置又はノードB,C,D,E,F,Gに対する各レベルＴの各ノードＡに対する相互接続を指定することによって完全に定義される。各ノード又は装置は、３次元円筒座標（r,q,z）で指定される位置を有しており、半径ｒは０からＪの円筒番号を特定する整数であり、角度ｑは2p/Kの整数倍数であり、それは０乃至Ｋ−１の円筒の円形断面周りのノードの間隔を特定し、且つ高さＺは０から2J−１へのｚ軸に沿っての距離を特定する二進整数である。高さｚは二進数で表わされる。何故ならば、ｚ次元におけるノード間の相互接続は二進デジット処理として最も容易に記述されるからである。最も内側のレベル０上において、１個のリングは１回の通過で０乃至Ｋ−１の角度ｑを介してスパン即ち跨がっており且つ各高さｚは１個のリングを指定する。レベル１上において、１個のリングは角度ｑを介し２つの通過でスパンされ且つ１個のリングを指定するのに２つの高さｚが使用される。リング構成体は、このような態様で最も外側のリングＪを介して進行し、その場合に、１個のリングはｚ軸に沿っての全ての2J個の高さにおいてスパンされる。
リングＲ上のノードＡは、リングＲ上のノードＡの直近の先行体であるノードＢからメッセージデータを受取る。ノード位置Ｎ（r,q,z）に位置しているノードＡの場合には、ノードＢはレベルｒ上のＮ（r,（ｑ−１）modK,Hr（ｚ））に位置している。（ｑ−１）modKは、ｑが０に等しい場合にＫ−１と等しく且つそうでない場合にはｑ−１と等しい。レベルＲ上のHr（ｚ）へのｒの変換は、ｚ＝［zJ-1,zJ-2,...,zr,z0,z1,z2,...,zr-1］の形態で、zr-1乃至z0の低次ｚビットの順番を逆にし、該低次ビットから１（modulus2r）を減算し且つ該修正した低次ｚビットの順番を戻すことによって、ｚ＝［zJ-1,zJ-2,...,zr,zr-1,...,z2,z1,z0］に対して記述される。
ノードＡは、更に、レベルｒ上にない装置Ｃからのメッセージデータを受取る。ノードＡが最も外側のレベルｒ＝Ｊ上に位置されている場合には、装置Ｃは該相互接続構成体の外側にある。ノードＡが最も外側のレベル上に位置されていない場合には、装置ＣはレベルＲ＋１上の位置Ｎ（ｒ＋1,（ｑ−１）modK,z）に位置されているノードである。
ノードＡは、リングｒ上のノードＡに対する直近の後続体であるノードＤへメッセージデータを送る。ノードＤはレベルｒ上のノード位置Ｎ（r,（ｑ＋１）modK,hr（ｚ））に位置している。（ｑ＋１）modKは、ｑがＫ−１に等しい場合に０に等しく、且つそうでない場合には、ｑ＋１に等しい。レベルｒ上のhr（ｚ）へのｚの変換は、ｚ＝［zJ-1,zJ-2,...,zr,z0,z1,z2,...,zr−１］の形態にzr-1からz0まで低次ｚの順番を逆にし、１（modurus2r）を該低次ビットへ加算し且つ該低次ｚビットを戻すことによって、ｚ＝［zJ-1,zJ-2,...,zr,zr-1,...,z2,z1,z0］に対して記述される。
注意すべきことであるが、項hrはｚにおいて順方向に向いており且つ項Hrは逆方向に向いている。従って、hrとHrは相互に逆数であり、従ってHr（hr（ｚ））＝hr（Hr（ｚ））＝ｚである。
ノードＡも、ノードＡと同一のレベルｒ上にはない装置Ｅに対してメッセージデータを送る。ノードＡが最も内側のレベルであるｒ＝０上にある場合には、ノード位置Ｎ（r,q,z）におけるノードＡは該相互接続構成体の外部の装置（例えば、計算装置）と相互接続される。そうでない場合には、ノードＡはレベルｒ−１上のノード位置Ｎ（ｒ−1,（ｑ＋１）modK,z）に位置しているノードである装置Ｅへメッセージデータを送るために相互接続されている。
ノードＡは装置Ｆからの制御情報を受取る。ノードＡが最も内側のレベルｒ＝０上にある場合には、装置Ｆは装置Ｅと同一である。ノードＡが最も内側のレベル上にない場合には、装置Ｆは、装置Ｅとは別のノードである。ノードＦはレベルｒ−１上のノード位置（Ｎ（ｒ−1,q,Hr-1（ｚ））に位置している。
ノードＡは装置Ｇへ制御情報を送る。ノードＡが最も外側のレベルｒ＝Ｊ上にある場合には、装置Ｇは該相互接続構成体の外側に位置している。装置ＧはノードＤへメッセージデータを送る、例えば計算装置等の装置である。ノードＡがレベルｒ＝Ｊ上に位置していない場合には、装置Ｇは、レベルｒ＋１上のノード位置Ｎ（ｒ＋1,q,Hr+1（ｚ））に位置しているノードであり且つ装置ＧはノードＤへメッセージデータを送る。
本発明の第二の側面によれば、３次元のトポロジィ（topology）における複数個のノードとして配列されている相互接続構成体における３つの次元である第一、第二、第三次元におけるターゲット宛先へノードＮからメッセージを送信する方法が示される。該方法は、第一及び第二次元においてターゲット宛先への途中であり且つ第三次元の宛先レベルへ向かって１つのレベル前進させるノードが別のメッセージによってブロックされているか否かを決定し、該途中のノードがブロックされていない場合に該メッセージを第三次元の宛先レベルへ向かって１つのレベル前進させ且つそうでない場合には第三次元において一定のレベルに沿って第一及び第二次元において該メッセージを移動させる、上記各ステップを包含している。この方法は、更に、複数個のレベルを記述するために該第三次元を特定し且つ各レベル上の複数個のノードを記述するために第一及び第二次元を特定するステップを包含している。第三次元におけるレベルｑ上のノードＮへ該途中のノードから制御信号が送られ、該制御信号は該途中のノードがブロックされているか否かを特定する。メッセージの伝送は、特定の円筒高さにおけるノード数に整数時間係数を維持するためのタイミング間隔を特定するグローバルクロックを使用して同期され、グローバルクロック時間間隔は第二時間間隔と等しく且つ第一時間間隔はグローバル時間間隔よりも小さい。第一時間間隔ａは該メッセージを第一及び第二次元のみにおいて移動するために設定される。第二時間間隔ａ−ｂは、該メッセージを宛先レベルに向けて１つのレベル前進させるために設定される。第三時間間隔は、該制御信号を途中のノードからノードＮへ送るために設定され、該第三時間間隔はｂに等しい。
本発明の第三の側面によれば、相互接続構成体を介して入力装置から出力装置へメッセージを送信する方法が示される。該メッセージは三次元構造における複数個のノードを接続する該相互接続構成体を介して前進する。該メッセージは、該相互接続構成体のレベル０上のターゲットリングに対応するターゲット宛先を有している。該ターゲットリングがノードＮ′からアクセス可能であり且つメッセージＭの前進をブロックするためにその他のより高い優先性のメッセージがノードＮ′へ前進するものでない限り、レベル０上のターゲットリングへの途中のレベルＴ上のノードＮにおけるメッセージＭはレベルＴ−１上のノードＮ′へ前進する。該ターゲットリングがノードＮ′からアクセス可能であるか否かは、典型的に、該ターゲットリングを指定する二進コードの単一のビットをテストすることによって効率的に決定される。より高い優先性のメッセージがメッセージＭの前進をブロックしているか否かは、同期された制御信号を使用することによって効率的に決定される。メッセージが時間ｔにおいてブロックされている場合には、該メッセージは時間ｔ＋２において次のレベルへ前進する位置にある。メッセージがレベルｔ−１上のメッセージＭ′によってブロックされている場合には、メッセージＭ′が再度メッセージＭをブロックすることが可能となる前に、制限された時間期間が経過する。
グローバルクロックは該相互接続構成体における交通量を制御する。データの流れは、システムタイミング内に制御情報の多くを「隠す」ことを可能とする規則に従い、従って、全ての制御情報をメッセージパケットヘッダー内にコード化させるのではなく、タイミング考慮事項がある情報を担う。例えば、ターゲットリングはメッセージパケットヘッダー内にコード化されるが、該相互接続構成体の幾つかの実施例においては、ターゲット計算装置の指定は、グローバルクロック上の時間に関してメッセージの到着のタイミングによって決定される。
開示したマルチレベル相互接続構成体は多数の利点を有している。１つの利点は、該構成体が簡単であり、高度の秩序を有しており且つ小さなシステムから巨大なシステムにわたる広範な寸法を有するシステムに対して高速で且つ効率的な計算を実行する。
更に、本相互接続構成体は多くの理由により高度に有益的である。本相互接続構成体は同一のノードに対して指向されたメッセージ間の競合を解決し且つブロックされているメッセージが、ブロックしているメッセージが再度ブロックする位置となる前に、あるレベル上の与えられた角度におけるメッセージの完全な周遊を行なうことを確保する。このように、メッセージは、本来的に、次のレベルへの全ての可能な経路をカバーすべく移動する。ブロックしているメッセージは、典型的に、次のレベルへ前進し、従って上側に存在するメッセージが長い間ブロックされることはない。
【図面の簡単な説明】
新規であると考えられる本発明の特徴は、特に、添付の請求範囲に記載してある。然しながら、本発明自身、その構成及び動作方法の両方に関して、以下の説明及び添付の図面を参照して最も良く理解することが可能である。
図1A,1B,1C,1Dは、マルチレベル最少論理相互接続装置の１実施例の構造の抽象的な三次元模式図である。
図２はノード、ノード端子及び該端子へ接続されている相互接続線の概略図である。
図3A,3B,3Cは該相互接続構成体の種々のレベル上のノードの相互接続を例示する概略ブロック図である。
図４は相互接続構成体の複数個のレベルのトポロジィを示した抽象的な概略模式図である。
図５は相互接続構成体の複数個のノードのトポロジィを示した抽象的な概略模式図である。
図６は特定の円筒レベル上のリングのノードが相互接続されている態様を例示した抽象的な概略模式図である。
図７はレベル０上のノードの相互接続を例示している。
図８はレベル１上のノードの相互接続を示している。
図９はレベル２上のノードの相互接続を示している。
図10はレベル３上のノードの相互接続を示している。
図11は低レベル円筒上のリングの装置とノードとの間の相互接続を例示している抽象的な概略模式図である。
図12は２つの隣接する円筒レベルのノード間の相互接続を例示する抽象的な概略模式図である。
図13は円筒レベル１上の複数個のノードの相互接続を示した抽象的な概略模式図である。
図14は円筒レベル２上の複数個のノードの相互接続を示した抽象的な概略模式図である。
図15は円筒レベル３上の複数個のノードの相互接続を示した抽象的な概略模式図である。
図16は該相互接続構成体の１実施例の隣接したレベル上のメッセージの相互作用を例示した抽象的な概略模式図である。
図17は該説明した相互接続構成体におけるメッセージ通信のタイミングを例示したタイミング線図である。
図18はヘッダーとペイロードとを包含するメッセージパケットのフォーマットを例示した模式図である。
図19は第一の例示的ノード構造であるニオブ酸リチウムノードの動作を例示した模式図である。
図20は第二の例示的ノード構造である非線形光学的ループミラー（NOLM）の動作を例示した模式図である。
図21は第三の例示的ノード構造であるテラヘルツ光学的非対称デマルチプレクサ（TOAD）スイッチの動作を例示した模式図である。
図22はニオブ酸リチウムゲートを利用した再生器の動作を示した模式図である。
図23は装置が複数個のノードに対してメッセージパケットを発行する相互接続構成体の別の実施例を例示した抽象的な概略模式図である。
図24は装置が複数個のノードからメッセージパケットを受信する相互接続構成体の別の実施例を例示した抽象的な概略模式図である。
図25は装置が種々の相互接続レベルにおいてノードへメッセージパケットを発行する相互接続構成体の別の実施例を例示した抽象的な概略模式図である。
発明の実施の態様
図1A,1B,1C,1Dを参照すると、マルチレベル最少論理相互接続装置100の１実施例が、相互接続線によってマルチレベル相互接続構成体内において接続されている複数個のノード102を包含している。該マルチレベル相互接続構成体は理解を容易にするために三次元構成として例示的に示してある。
該マルチレベル相互接続構成体におけるノード102は、複数個のレベル110を包含すべく配列されており、各レベル110は階層有意性を有しており、従って、該構成体において１つのメッセージが開始された後に、該メッセージは、通常、前の階層有意性116のレベルから次の階層有意性118のレベルへの方向において、最初のレベル112から最後のレベル114へ移動する。例示として、各レベル110はリング120と呼ばれる複数個の構成体を包含している。各リング120は複数個のノード102を包含している。「リング」という用語は、単に、同心上の円筒レベル110の集まりとして該構成体の可視化が有用である抽象化においてネットワークの構造の容易を簡単化させるために使用されている。
異なる図1A,1B,1C,1Dが、ノード間の相互接続をより容易に想起し且つ理解するために包含されている。図1Aは種々の円筒レベル110上のノード102間のメッセージデータ伝送相互接続を例示している。図1Bは図1Aに例示した相互接続に対してノード102と装置130との間のメッセージデータ伝送相互接続の図示を付加している。図1Cは、更に、異なるレベル上のノード102間のメッセージデータ相互接続を示している。図1Dは、ノード102間の相互接続を制御することに加えて、図1A,1B,1Cに示した相互接続を累積的に示している。
相互接続構成体の実際の物理的な幾何学的構成は円筒構成体に制限されるべきものではない。重要なことは、複数個のノードが第一クラスのグループ内において配列されており且つ該第一クラスのグループが第二クラスのグループ内に配列されているということである。リングとしての第一クラスのグループに対する参照及びレベルとしての第二クラスのグループに対する参照は単に例示的なものであって制限的なものであることを意味しているものではない。
例示的な相互接続装置100は、複数個のＪ＋１個のレベル110を包含する構成を有している。各レベル110は複数個の2JK個のノード102を包含している。各レベルＭは2J-M個のリング120を有しており、各リングは2MK個のノード102を有している。全構成体におけるノード102の総数は（Ｊ＋１）2JKである。相互接続装置100は、更に、複数個の2JK個の装置130を包含している。例示的な実施例においては、2JK個の装置130の各装置が最後のレベル114の2J個のリングの各リングにおけるＫ個のノード102の各々のデータ出力ポートへ接続している。典型的に、コンピュータの相互接続構成体においては、装置130は例えばプロセス・メモリユニット又はプロセサ・メモリユニット及び入力及び出力バッファの集まりのような計算装置である。
図２を参照すると、ノード102の相互接続構成体200が３個の入力端子と３個の出力端子とを有している。該入力端子は、第一データ入力端子210、第二データ入力端子212、制御入力端子214を包含している。該出力端子は、第一データ出力端子220、第二データ出力端子222、制御出力端子224を包含している。１個のノードのデータ入力及び出力端子は、他のノードとメッセージデータを通信する。該制御端子は、メッセージデータの送信を制御するために、他のノードと制御ビットを通信する。メッセージ送信を制御するための制御ビットの数は、効率的に減少されている。何故ならば、相互接続構成体200を介しての論理の殆どは、以下に説明するような態様で制御ビット及びメッセージデータの受領のタイミングによって決定されるからである。与えられた時間ステップにおいて、１個の制御ビットのみが１個のノードへ入り且つ１個の制御ビットのみが出る。メッセージは、時間単位を同期させるクロック信号を発生することによって通信される。メッセージ送信は、１つの時間単位期間中に、いずれかのノード102がデータ入力端子212及び214のうちの１つの入力端子のみからメッセージデータを受取るように制御される。ノード202はバッファを有していないので、ノードの出力ポートのうちの１つのみが１つの時間単位においてアクティブ即ち活性状態にある。
図３乃至図６を参照して、相互接続構成体300のトポロジィについて説明する。理解を容易とさせるために構成体300は３つの次元r,q,zにおける同心状の円筒の集まりとして例示してある。各ノード又は装置は、三次元円筒座標における位置（r,2pq/K,z）に関係する（r,q,z）で指定される位置を有しており、半径ｒは０乃至Ｊの円筒番号を特定する整数であり、角度ｑは０乃至Ｋ−１の円筒の円形断面周りのノードの間隔を特定する整数であり、且つ高さｚは０乃至2J−１のｚ軸に沿っての距離を特定する二進整数である。ｚ次元におけるノード間の相互接続は二進デジットの操作として最も容易に記述されるので、高さｚは二進数として表現されている。従って、相互接続構成体300は２つの設計パラメータＪ及びＫに関して定義される。
図3A,3B,3Cは、該相互接続構成体の種々のレベル上のノードの相互接続を示した概略ブロック図である。図3Aは最も外側のレベルＪのリングｒ上のノードARJ320及びノードBRJ322、装置C324、ノードDRJ326、ノードER(J-1)329、ノードFR(J-1)330、装置G332へのノードARJ320の相互接続を示している。図3BはレベルＴのリングＲ上のノードART340及びノードBRT342、ノードCR(T+1)344、ノードDRT346、ノードER(T-1)348、ノードFR(T-1)350、ノードGR(T+1)352へのノードART340の相互接続を示している。図3Cは最も内側のレベル０のリングＲ上のノードAR0360及びノードBR0362、ノードCR1364、ノードDR0366、装置E368、ノードGR1372へのノードAR0360の相互接続を示している。図3A,3B,3Cにおいて、相互接続は実線で示してあり、矢印はメッセージデータ流れ方向を表わしており且つ矢印を有する点線は制御メッセージ流れ方向を表わしている。要約すると、ノードA,B,D及びノード又は装置C,E,F,Gに対して、以下の如くである。
（１）ＡがレベルＴ上にある。
（２）Ｂ及びＣがＡへデータを送る。
（３）Ｄ及びＥがＡからデータを受取る。
（４）ＦがＡへ制御信号を送る。
（５）ＧがＡから制御信号を受取る。
（６）Ｂ及びＤがレベルＴ上にある。
（７）ＢはＡの直近の先行体である。
（８）ＤはＡに対する直近の後続体である。
（９）C,E,F,GはレベルＴ上にはない。
種々のノード及び装置の三次元円筒表示における位置は以下の如くである。
（10）ＡはノードＮ（r,q,z）に位置している。
（11）ＢはノードＮ（r,q−1,hT（ｚ））に位置している。
（12）ＣはノードＮ（ｒ＋1,q−1,z）に位置しているか又は該相互接続構成体の外側のいずれかである。
（13）ＤはノードＮ（r,q＋1,hT（ｚ））に位置している。
（14）ＥはノードＮ（ｒ−1,q＋1,z）に位置しているか又は該相互接続構成体の外側のいずれかであり装置Ｆと同じである。
（15）ＦはノードＮ（ｒ−1,q,hT−１（ｚ））に位置しているか又は該相互接続構成体の外側のいずれかであり且つ装置Ｅと同一である。
（16）ＧはノードＮ（ｒ＋1,q,hT（ｚ））に位置しているか又は該相互接続構成体の外側のいずれかである。
注意すべきことであるが、ｑ＋１及びｑ−１は、夫々、係数（modulus）Ｋ、即ちＫを法とする加算及び減算のことを意味している。
この表記方法において、（ｑ−１）modKは、ｑが０に等しい場合には、Ｋに等しく、且つそうでない場合には、ｑ−１に等しい。レベルｒ上のHr（ｚ）へのｚの変換は、ｚ＝［zJ-1,zJ-2,...,zr,z0,z1,z2,...,zr-1］の形態にzr-1乃至z0の低次ｚビットの順番を逆にし、１（modulus2r）を減算し且つ該低次ｚビットを戻すことによって、ｚ＝［zJ-1,zJ-2,...,zr,zr-1,...,z2,z1,z0］に対して記述される。同様に、（ｑ＋１）modKは、ｑがＫ−１に等しい場合に、０に等しく、且つそうでない場合には、ｑ＋１に等しい。レベルｒ上のhr（ｚ）へのｚの変換は、ｚ＝［zJ-1,zJ-2,...,zr,z0,z1,z2,...,zr-1］の形態にzr-1乃至z0の低次ｚビットの順番を逆にし、１（modulus2r）を加算し、且つ該低次ｚビットを戻すことによって、ｚ＝［zJ-1,zJ-2,...,zr,zr-1,...,z2,z1,z0］に対して記述される。
図４を参照すると、同心円筒レベル０（310）、１（312）、２（314）、３（316）が、Ｊ＝３相互接続構成体300に対して示されており、その場合に、レベル０は最も内側の円筒レベルを示しており、外側に向かって最も外側の円筒レベル３に対して数値的に前進する。レベルＴ上のノード102はレベルＴノードと呼ばれる。
相互接続構成体は、Ｊ＋１個のレベルを有しており且つ各レベル上において2JK個のノードを有している。図５を参照すると、設計パラメータＫが５に等しく設定されており、従って相互接続構成体300は４個のレベル（Ｊ＋１＝３＋１＝４）を有しており、各レベル上に40（2JK＝（23）５＝40）個のノードを有している。
図６乃至10を参照すると、表記法を修正しており且つより簡潔なものとされており、従って、ノード位置（r,q,z）における文字は、その文字とそれに続く位置指定とで指定される。例えば、位置（r,q,z）におけるノードＡはノードＡ（r,q,z）と指定される。
図６を参照すると、該相互接続構成体は、各レベルＴの各ノードA530に対する、装置又はノードB532,C534,D536,E538,F540,G542への相互接続を指定することによって完全に定義される。
ノードＡ（r,q,z）530は、レベルｒ上の中間先行体ノードＢ（r,（ｑ−１）modK,Hr（ｚ））532と相互接続している。ノードＡ（r,q,z）530が最も外側のレベルｒ＝Ｊ上にある場合には、ノードＡ（r,q,z）530は該相互接続構成体の外側にある装置（例えば、コンピュータの計算装置）と相互接続している。そうでない場合には、ノードＡ（r,q,z）530はレベルｒ＋１上の先行体ノードＣ（ｒ＋1,（ｑ−１）modK,z）534と相互接続している。
ノードＡ（r,q,z）530は、レベルｒ上の直近の先行体ノードＤ（r,（ｑ＋１）modK,Hr（ｚ））536と相互接続している。ノードＡ（r,q,z）530が最も内側のレベルｒ＝０上にある場合には、ノードＡ（r,q,z）530は該相互接続構成体の外側の装置（例えば、計算装置）と相互接続している。そうでない場合には、ノードＡ（r,q,z）530は、メッセージデータを送るために、レベルｒ−１上の後続体ノードＥ（ｒ−1,（ｑ＋１）modK,z）538と相互接続している。
ノードＡ（r,q,z）530が最も内側のレベルｒ＝０上にある場合には、ノードＡ（r,q,z）530は、該相互接続構成体の外側にある装置（例えば計算装置）と相互接続している。そうでない場合にはノードＡ（r,q,z）530は、ノードＡ（r,q,z）530へ制御入力信号を供給するレベルｒ−１上のノードＦ（ｒ−1,q,Hr-（ｚ））540と相互接続している。
ノードＡ（r,q,z）530が最も外側のレベルｒ＝Ｊ上にある場合には、ノードＡ（r,q,z）530は該相互接続構成体の外側にある装置（例えば、計算装置）と相互接続している。そうでない場合にはノードＡ（r,q,z）530は、ノードＡ（r,q,z）530から制御入力信号を受取るレベルｒ＋１上のノードＧ（ｒ＋1,q,hr+1（ｚ））542と相互接続している。
特に、相互接続設定パラメータＪ＝３及びＫ＝５を有する相互接続構成体の例に対するノードＡの相互接続は１個のリング上の全てのノードに対して定義される。全てのリングは単一方向であり且つ閉じた曲線を形成し、従って全構成体は、各ノードＡに対して、ノードＡからデータを受取るノードＤを指定することによって定義される。
図3Cと関連して図７を参照すると、レベル０上のノードＡの相互接続が示されている。ノードＡ（0,q,z）360は、レベル０上の直近の先行体ノードＢ（0,（ｑ−１）mod5,z）362からのメッセージデータを受取り且つレベル０上の直近の後続体ノードＤ（0,（ｑ＋１）mod5,z）366へメッセージデータを送るべく相互接続されている。ノードＢ及びＤに対する第二次元における相互接続項は以前に、夫々、レベル０上におけるHr（ｚ）及びhr（ｚ）として定義されているが、Hr（ｚ）＝H0（ｚ）＝ｚ及びhr（ｚ）＝R0（ｚ）＝ｚである。ノードＡ（0,q,z）360も、レベル１上の先行体ノードＣ（1,（ｑ−１）mod5,z）364からのメッセージデータを受取り且つ装置Ｅ（q,z）368へメッセージデータを受取るべく相互接続されている。ノードＡ（0,q,z）360は、ネットワーク外側の装置Ｅ（q,z）368から制御情報を受取り且つレベル上のノードＧ（1,q,h0（ｚ））372へ制御出力信号を送るべく相互接続されている。
図６と関連して図８を参照すると、レベル１上のノードＡの相互接続が示されている。ノードＡ（1,q,z）530は、レベル１上の直近の先行体ノードＢ（1,（ｑ−１）mod5,H1（ｚ））532からのメッセージデータを受取り且つレベル１上の直近の後続体ノードＤ（1,（ｑ＋１）mod5,h1（ｚ））536へメッセージデータを送るべく相互接続されている。高さｚは、［z2,z1,z0］の形態を有する二進数（基数２）として表現される。レベル１の場合には、ｚが［z2,z1,z0］である場合にはh1（ｚ）及びH1（ｚ）は両方とも［z2,z1］である。ｚが［z2,z1,1］である場合にはh1（ｚ）及びH1（ｚ）は両方とも［z2,z1,0］である。ノードＡ（1,q,z）530も、レベル２上の先行体ノードＣ（2,（ｑ−１）mod5,z）534からのメッセージデータを受取り且つレベル０上の後続体ノードＥ（0,（ｑ＋１）mod5,z）538へメッセージデータを送るべく相互接続されている。ノードＡ（1,q,z）530は、レベル０上のノードＦ（0,q,H0（ｚ））540からの制御入力信号を受取り且つレベル２上のノードＧ（2,q,h1（ｚ））542へ制御出力信号を送るべく相互接続されている。
図６と関連して図９を参照すると、レベル２上のノードＡの相互接続が示されている。ノードＡ（2,q,z）530は、レベル２上の直近の先行体ノードＢ（2,（ｑ−１）mod5,H2（ｚ））532からのメッセージデータを受取り且つレベル２上の直近の後続体ノードＤ（2,（ｑ＋１）mod5,h2（ｚ））536へメッセージデータを送るべく相互接続されている。高さｚは、［z2,z1,z0］の形態を有する二進数（基数２）として表現されている。レベル２の場合には、ｚが［z2,0,0］である場合にはh2（ｚ）は［z2,1,0］であり且つH2（ｚ）は［z2,1,1］である。ｚが［z2,0,1］である場合には、h2（ｚ）は［z2,1,1］であり且つH2（ｚ）は［z2,1,0］である。ｚが［z2,1,0］である場合には、h2（ｚ）は［z2,0,1］であり且つH2（ｚ）は［z2,0,0］である。ｚが［z2,1,1］である場合には、h2（ｚ）は［z2,0,0］であり且つH2（ｚ）は［z2,0,1］である。ノードＡ（2,q,z）530も、レベル３上の先行体ノードＣ（3,（ｑ−１）mod5,z）534からメッセージデータを受取り且つレベル１上の後続体ノードＥ（1,（ｑ＋１）mod5,z）538へメッセージデータを送るべく相互接続されている。ノードＡ（2,q,z）530は、レベル１上のノードＦ（1,q,H1（ｚ））540からの制御入力信号を受取り且つレベル３上のノードＧ（3,q,h2（ｚ））542へ制御入力信号を送るべく相互接続されている。
図６と関連して図10を参照すると、Ｊ＞３及びＫ＝５の相互接続構成体のレベル３上のノードＡの相互接続が示されている。ノードＡ（3,q,z）530は、レベル３上の直近の先行体ノードＢ（3,（ｑ−１）mod5,H3（ｚ））532からのメッセージデータを受取り且つレベル３上の直近の後続体ノードＤ（3,（ｑ＋１）mod5,h3（ｚ））536へメッセージデータを送るべく相互接続されている。レベル３の場合には、ｚが［0,0,0］である場合には、h3（ｚ）は［1,0,0］であり且つH3（ｚ）は［1,1,1］である。ｚが［0,0,1］である場合には、h3（ｚ）は［1,0,1］であり且つH3（ｚ）は［1,1,0］である。ｚが［0,1,0］である場合には、h3（ｚ）は［1,1,0］であり且つH3（ｚ）は［1,0,0］である。ｚが［0,1,1］である場合には、h3（ｚ）は［1,1,1］であり且つH3（ｚ）は［1,0,1］である。ｚが［1,0,0］である場合には、h3（ｚ）は［0,1,0］であり且つH3（ｚ）は［0,0,0］である。ｚが［1,0,1］である場合には、h3（ｚ）は［0,1,1］であり且つH3（ｚ）は［0,0,1］である。ｚが［1,1,0］である場合には、h3（ｚ）は［0,0,1］であり且つH3（ｚ）は［0,1,0］である。ｚが［1,1,1］である場合には、h3（ｚ）は［0,0,0］であり且つH3（ｚ）は［0,1,1］である。ノードＡ（3,q,z）530も、レベル４上の先行体ノードＣ（4,（ｑ−１）mod5,z）534からのメッセージデータを受取り且つレベル２上の後続体ノードＥ（2,（ｑ＋１）mod5,z）538へメッセージデータを送るべく相互接続されている。ノードＡ（3,q,z）530は、レベル２上のノードＦ（2,q,H2（ｚ））540からの制御入力信号を受取り且つレベル４上のノードＧ（4,q,h3（ｚ））542へ制御出力信号を送るべく相互接続されている。
図11は円筒レベル０（110）上のリング120の装置130とノード102との間の相互接続を示している。図２を参照して説明したノード102の相互接続構成体200の説明に従って、ノード102は３個の入力端子と３個の出力端子とを有しており、２個のデータ入力端子及び１個の制御入力端子及び２個のデータ出力端子及び１個の制御出力端子を包含している。簡単な実施例においては、装置130は、１個のデータ入力端子402と、１個の制御ビット入力端子404と、１個のデータ出力端子406と、１個の制御ビット出力端子408を有している。
図11を参照すると、最も低い円筒レベル110におけるノード102、特にノードＮ（0,q,z）は、装置CU（q,z）へ接続している。特に、装置CU（q,z）のデータ入力端子402はノードＮ（0,q,z）の第二データ出力端子222へ接続している。装置CU（q,z）の制御ビット出力端子408は、ノードＮ（0,q,z）の制御入力端子214へ接続している。
装置CU（q,z）は、更に、最も外側の円筒レベルにおけるノードＮ（J,q,z）へ接続している。特に、装置CU（q,z）のデータ出力端子406は、ノードＮ（J,q,z）の第二データ入力端子212へ接続している。装置CU（q,z）の制御ビット入力端子404は、ノードＮ（0,q−1,Hr（ｚ））の制御出力端子224へ接続している。メッセージは、最も外側の円筒レベルＪにおけるノードＮ（J,q,z）へ装置CU（q,z）から通信される。次いで、メッセージは、逐次的に、最も外側の円筒レベルＪからレベルＪ−１へ、レベルＪ−２へ、等々内側へ移動し、該メッセージはレベル０へ到達し、次いで１個の装置へエンターする。最も外側の円筒Ｊ上のメッセージはレベル０における2J個のリングの内のいずれかに到達することが可能である。一般的には、任意の円筒レベルＴ上のメッセージは、レベル０上の2T個のリング上のノードへ到達することが可能である。
図12は２個の隣接する円筒レベル110のノード102間の相互接続を例示している。図２に関連して図12を参照すると、Ｔ円筒レベル110におけるノード102、特にノードＮ（T,q,z）450は、Ｔレベル、Ｔ＋１レベル及びＴ−１レベル上のノードへ接続した端子を有している。これらの接続は、ノードＮ（T,q,z）450が同一のレベルＴ上の１個のレベルへ接続した１個のデータ入力端子を有しており且つ、通常最も外側のレベルＪ上のノードを除いて次の外側のレベルＴ＋１上の１個のノードである別のソース（供給源）へ接続されている１個のデータ入力端子を有するようなものであり、装置はソース（供給源）である。特に、ノードＮ（T,q,z）450は、ノードＮ（Ｔ＋1,q−1,z）452の第一データ出力端子220へ接続している第一データ入力端子210を有している。又、ノードＮ（T,q,z）450は、ノードＮ（Ｔ−1,q＋1,z）454の第一データ入力端子210へ接続している第一データ出力端子220を有している。
ノードＮ（T,q,z）450は、更に、同一のレベルＴ上のノード102へ接続している第二データ入力端子212及び第二データ出力端子222を有している。ノードＮ（T,q,z）450の第二データ入力端子212はノードＮ（T,q−1,HT（ｚ））456の第二データ出力端子222へ接続している。ノードＮ（T,q,z）450の第二データ出力端子222は、ノードＮ（T,q＋1,hT（ｚ））458の第二データ入力端子212へ接続している。円筒高さの指定HT（ｚ）は、高さ指定hT（ｚ）を決定するための技術の逆の操作を使用して決定される。円筒高さから同一のレベルＴ上の高さへの（高さｚから高さHT（ｚ）へ及び高さhT（ｚ）から高さｚへ）ノードの相互接続は、高さ変換技術に従って精密に定義され且つメッセージが通信される特定のレベルＴに依存する。特に、高さ変換技術によると、高さ位置ｚは二進形態とされ、その場合ｚ＝zJ-12J-1＋zJ-22J-2＋...＋zT2T＋zT-12T-1＋...＋z121＋z020である。次の高さ位置hT（ｚ）は３つのステップを包含するプロセスを使用して決定される。第一に、係数z0で開始し且つ係数zTまでであるがそれを包含することがない二進係数の順番が逆にされ、一方係数zT及びそれより上のものは同一に維持される。従って、第一ステップの後に、高さ位置は、zJ-12J-1＋zJ-22J-2＋...＋zT2T＋z020＋z121＋...＋zT-22T-2＋zT-12T-1となる。第二に、奇数モジュラス（modulus）即ち係数2T、例えば１、が反転の後に該高さ位置へ加算される。第三に、該反転され且つmodulus2Tだけインクリメントされた高さ位置を制限することによって該高さ位置の循環を実行する。第四に、第一ステップを繰り返し行ない、この場合も、前に反転させたzJ係数より下側の二進係数を反転させ、インクリメントさせ且つ高さ位置を制限する。高さ記述子HT（ｚ）を派生するための反転操作は、順番を反転させたビットストリングに対して奇数modulus2Tを加算する代わりに、順番を反転させたビットストリングに対して同一の奇数modulus2Tを加算する点を除いて、同一の態様で決定される。
同一レベル上のノード102間の相互接続は注目に値にするものであり且つ多くの理由により高度に有益的なものである。例えば、本相互接続構成体は、同一のノードに向かって指向されたメッセージ間での競合を解決する。更に、本相互接続構成体は、次のレベル上のメッセージによってブロック即ち阻止されている特定のレベル上のメッセージが、いずれかのメッセージが再度ブロックする位置となる前に、そのレベル上のメッセージの完全なる周遊を行なうことを確保する。従って、メッセージは、本質的に、次のレベルへの全ての可能な経路をカバーすべく移動する。更に、ブロックしているメッセージは、メッセージを二度ブロックするために１つのレベルの全てのリングを介して循環せねばならない。従って、全てのメッセージは、他のメッセージを継続してブロックすることを回避すべくそらされる。更に、ブロックしているメッセージは、典型的に、爾後のレベルへ進行し、従って上側に存在するメッセージが長い間ブロックされることはない。
メッセージが、ノードＮ（T,q,z）450の第二データ出力端子222からノードＮ（T,q＋1,hT（ｚ））の第二データ入力端子212へ送られる場合に、制御コードもノードＮ（T,q,z）450の制御出力端子224から、ノードＮ（T,q,hT（ｚ））のデータ入力端子へ接続しているデータ出力端子を有するレベルＴ＋１上のノードであるノードＮ（Ｔ＋1,q,hT+1（ｚ））の制御入力端子214へ送られる。この制御コードは、ノードＮ（T,q,z）450がノードＮ（T,q＋1,hT+1（ｚ））へメッセージを送っている時に、ノードＮ（Ｔ＋1,q,hT+1（ｚ））がノードＮ（T,q＋1,hT+1（ｚ））へメッセージを送ることを禁止する。ノードＮ（Ｔ＋1,q,hT+1（ｚ））がノードＮ（T,q＋1,hT+1（ｚ））へメッセージを送ることがブロックされている場合に、該メッセージはレベルＴ＋１上のノードへ偏向される。従って、同一のレベル上で通信されるメッセージは、別のレベルから通信されるメッセージと比較して優先性を有している。
ノードＮ（T,q−1,HT（ｚ））の第二データ出力端子222はノードＮ（T,q,z）450の第二データ入力端子212へ接続しており、従ってノードＮ（T,q,z）450は、ノードＮ（Ｔ−1,q,HT（ｚ））への送信からブロックされているノードＮ（T,q−1,HT（ｚ））からのメッセージを受取る。更に、どのノードも同時に２つのソース（供給源）からデータを受取ることはないので、ブロックされているノードの警告を与え且つノードＮ（T,q,z）450に対して今データを送らないように知らせるために、ノードＮ（Ｔ−1,q,HT（ｚ））の制御出力端子224がノードＮ（T,q,z）450の制御入力端子214へ接続している。
図13を参照すると、円筒レベル１上のノード102の相互接続は、説明した相互接続を例示化しており且つ該一般的な相互接続技術から発生する特性及び利点を示している。この例においては、円筒高さにおけるノードＫの数は５であり且つ高さ2Jの数は、３レベル（Ｊ＋１）相互接続構成体500に対して、22即ち４である。ノードＮ（1,q,z）510は、（１）ノードＮ（2,q−1,z）512の第一データ出力端子220へ接続している第一データ入力端子210と、（２）ノードＮ（2,q,h1（ｚ））514の制御入力端子214へ接続している制御出力端子224と、（３）ノードＮ（0,q＋1,z）516の第一データ入力端子210へ接続している第一データ出力端子220と、（４）ノードＮ（0,q,z）518の制御出力端子224へ接続している制御入力端子214と、（５）ノードＮ（1,q−1,H1（ｚ））520の第二データ出力端子222へ接続している第二データ入力端子212と、（６）ノードＮ（1,q＋1,h1（ｚ））522の第二データ入力端子212へ接続している第二データ出力端子222とを有している。レベル１上のノードＮ（1,q,z）510の場合には、高さｚは最後のビット位置においてのみ高さh1（ｚ）及び高さH1（ｚ）と異なっている。
メッセージは、離散的な時間ステップで相互接続構成体500を介して通信される。グローバルクロック（不図示）が円筒レベルｒの円筒高さｚにおけるノード数Ｋの係数である離散時間ステップにおいてタイミング信号を発生する。内側のレベル上のノードがブロックされているので、メッセージが同一のレベル（例えば、レベル１）上で相互接続構成体500を横断する場合に、メッセージは離散時間ステップでノードからノードへ通信される。円筒レベルにおいて奇数（Ｋ＝５）のノードを有する相互接続構成体500の場合には、データが2K時間ステップに対してレベル１を横断する場合には、メッセージパケット2K個の異なるノードを包含する。時間ステップ2K＋１上において、メッセージパケットは最初のノード横断の逐次的な順番に続いてノードの繰返しを開始する。グローバルクロックは整数時間係数Ｋで離散時間ステップを発生するので、レベル１上のメッセージパケットが時間Ｔにおいてそのパケットのターゲットリング上に有り且つレベル０上のメッセージによって偏向される場合には、該メッセージは時間Ｔ＋２（modulusK）において該ターゲットリング上に有り、該ターゲットリングへエンターする別の試みを行なう。種々の実施例において、このタイミング特性は該相互接続構成体を介して一貫しており、従って、メッセージパケットが時間Ｔ＝０（modulusK）において次のレベルへ下降する位置にある場合には、該パケットは再度爾後の時間Ｔ＝０（modulusK）において下降する位置にある。
図13と関連して図14を参照すると、円筒レベル２上のノード102の相互接続は、更に、説明した相互接続を例示している。図14において、レベル２のメッセージ経路620がレベル１上を移動するメッセージの経路610及び612の上側に示されている。３レベル（Ｊ＋１）相互接続構成体500の場合には、円筒レベルにおけるノード数Ｋは５であり且つレベル数2Jは22即ち４である。ノードＮ（2,q,z）の同一レベルの相互接続は、（１）ノードＮ（2,q−1,h2（ｚ））の第二データ出力端子222へ接続している第二データ入力端子212と、ノードＮ（2,q＋1,H2（ｚ））の第二データ入力端子212へ接続している第二データ出力端子222とを包含している。レベル２上のノードＮ（2,q,z）の場合には、高さｚは最後の２つのビット位置においてのみ、高さh2（ｚ）及び高さH2（ｚ）から異なっている。ある高さにおける任意の適宜の数のノードＫ及び１つのレベルにおける高さ数2Jに対して二進形態で一般的に説明すると、円筒レベル２上のｚ及びｚ′＝h2（ｚ）は以下の如くに関係している。
［zJ-1,zJ-2,...,z2,0,0］′＝［zJ-1,zJ-2,...,z2,1,0］；
［zJ-1,zJ-2,...,z2,1,0］′＝［zJ-1,zJ-2,...,z2,0,1］；
［zJ-1,zJ-2,...,z2,0,1］′＝［zJ-1,zJ-2,...,z2,1,1］；
［zJ-1,zJ-2,...,z2,1,1］′＝［zJ-1,zJ-2,...,z2,0,0］
同一のレベル上のノードに対するこの相互接続技術の第二の利点は、ブロックされているメッセージが爾後のブロック作用を回避すべく指向されるという点である。図14はメッセージブロック条件及びその解決を示している。レベル１上において、メッセージm0610がノードNpqz＝N100において示されており且つメッセージm1612がノードN101において示されている。ノードN200におけるレベル２上のメッセージM620はリング０に対してターゲットされている。時間０において、メッセージM620がブロックされ且つ時間１においてノードN212に対してメッセージm1612によって偏向される。メッセージm0及びm1も偏向され且つレベル１をトラバース即ち横断するものと仮定すると、時間１において、メッセージm0610はノードN111にあり且つメッセージm1612はノードN110にある。時間２において、メッセージM620はノードN221へ移動し、メッセージm0610はノードN120へ移動し且つメッセージm1612はノードN121へ移動する。従って、時間２において、メッセージM620はメッセージm0610によって偏向される。時間４において、メッセージM620は、再度、メッセージm1612によってブロックされる。このメッセージm0610及びm1612によるメッセージM620の交互のブロック作用は、メッセージm0610及びm1612もブロックされる限り、無限に継続する。この特性は、本相互接続構成体全体にわたり普及しており、従って、内側レベル上の単一のメッセージが外側レベル上の１個のメッセージを継続してブロックすることは不可能である。単一のメッセージパケットが別のパケットをブロックすることが不可能であり且つブロックするパケットがレベルを介して継続的に進行するので、ブロック作用が持続することはない。
図15を参照すると、円筒レベル３上のノード102の相互接続が前に説明した相互接続の付加的な例を示している。レベル３のメッセージ経路720がレベル２上を移動するメッセージの経路710,712,714,716の上側に示されている。４レベル（Ｊ＋１）相互接続構成体の場合には、ある円筒高さにおけるノード数Ｋは７であり且つ高さ数2Jは23（８）である。ノードＮ（3,q,z）の同一レベルの相互接続は、（１）ノードＮ（3,q−1,h3（ｚ））の第二データ出力端子222へ接続している第二データ入力端子212と、（２）ノードＮ（3,q＋1,H3（ｚ））の第二データ入力端子212へ接続している第二データ出力端子222とを包含している。レベル３上のノードＮ（3,q,z）の場合、高さｚは最後の３つのビット位置においてのみ、高さh3（ｚ）及び高さH3（ｚ）とは異なっている。ある円筒高さにおける任意の適宜のノード数Ｋ及び１つのレベルにおける高さ数2Jに対して二進形態で一般的に説明すると、円筒レベル３上のビットｚ及びｚ′＝h3（ｚ）は以下の如くに関係している。
［zJ-1,zJ-2,...,z3,0,0,0］′＝［zJ-1,zJ-2,...,z3,1,0,0］；
［zJ-1,zJ-2,...,z3,1,0,0］′＝［zJ-1,zJ-2,...,z3,0,1,0］；
［zJ-1,zJ-2,...,z3,0,1,0］′＝［zJ-1,zJ-2,...,z3,1,1,0］；
［zJ-1,zJ-2,...,z3,1,1,0］′＝［zJ-1,zJ-2,...,z3,0,0,1］；
［zJ-1,zJ-2,...,z3,0,0,1］′＝［zJ-1,zJ-2,...,z3,1,0,1］；
［zJ-1,zJ-2,...,z3,1,0,1］′＝［zJ-1,zJ-2,...,z3,0,1,1］；
［zJ-1,zJ-2,...,z3,0,1,1］′＝［zJ-1,zJ-2,...,z3,1,1,1］；
［zJ-1,zJ-2,...,z3,1,1,1］′＝［zJ-1,zJ-2,...,z3,0,0,0］
図15はメッセージブロック条件及びその解決の別の例を示している。レベル２上において、メッセージm0710がノードN200において示されており、メッセージm1712がノードN201において示されており、メッセージm2714がノードN202において示されており、且つメッセージm3716がノードN203において示されている。ノードN303におけるレベル３上のメッセージM720はリング０に対してターゲットされている。時間０において、メッセージM720がブロックされ且つ時間１においてノードN317に対してメッセージm1712によって偏向される。メッセージm0,m1,m2,m3も偏向され且つレベル２をトラバースするものと仮定すると、時間１においてメッセージm0710はノードN212にあり、メッセージm1712はノードN213にあり、メッセージm2714はノードN211にあり、且つメッセージm3716はノードN210にある。時間２において、メッセージM720はノードN320へ移動し、メッセージm0710はノードN221へ移動し、メッセージm1712はノードN220へ移動し、メッセージm2714はノードN223へ移動し、且つメッセージm3716はノードN222へ移動する。従って、時間２において、メッセージM720は、メッセージm2714によって偏向される。時間４において、メッセージM720はメッセージm0710によってブロックされる。時間６において、メッセージM720はメッセージm3714によってブロックされる。時間８において、メッセージM720は、再度メッセージm1712によってブロックされる。メッセージm0710,m1712,m2714,m3716によるメッセージM720のこの交互のブロック作用は、メッセージm0710,m1712,m2714,m3716もブロックされる限り無限に継続する。
この解析は記載した本相互接続構成体が任意のレベルにおいてのブロック作用を回避する便益性を例示している。従って、該構成体における渋滞の「ホットスポット」は最小とされる。この特性は該構成体における全てのレベルにおいて維持される。
説明した相互接続構成体は、レベル０上の全てのノードＮ（0,q,z）が最も外側のレベルＪ上の任意のノードＮ（J,q,z）によってアクセス可能であることを与える。然しながら、最も外側のレベルから一度取除かれると、レベル０のノードＮ（0,q,z）の半分のみが該レベル上のノードＮ（Ｊ−1,q,z）によってアクセス可能であるに過ぎない。レベル１上のノードＮ（1,q,z）におけるデータは、レベル１の高さｚの二進表現及びレベル０のリングｒの二進表現が最後のビットにおいてのみ異なるものである限り、レベル０上の任意のノードＮ（0,q,z）へアクセスすることが可能である。同様に、レベル２上のノードＮ（2,q,z）におけるデータは、レベル２の高さｚの二進表現及びレベル０のリングｒの二進表現が最後の２つのビットにおいてのみ異なる限りレベル０上の任意のノードＮ（0,q,z）へアクセスすることが可能である。一般的な法則は、レベルＴの高さｚの二進表現とレベル０のリングｒの二進表現とが最後のＴ個のビットにおいてのみ異なる限り、レベルＴ上のノードＮ（T,q,z）におけるデータがレベル０上の任意のノードＮ（0,q,z）へアクセスすることが可能であるというものである。従って、最も外側のレベルＪからレベルＪ−１への移動は、ターゲットリングのアドレスの最大桁ビットを固定する。レベルＪ−１からレベルＪ−２への移動は、ターゲットリングのアドレスの次の最大桁ビットを固定し、以下同様である。レベル０において、固定されるべきビットは残っておらず、従って、ヘッダービットがテストされることはなく且つメッセージは常に装置へパスされる。幾つかの実施例においては、付加的なヘッダービットが包含しており且つレベル０のノードにおいてテストされる。この最後のビットは、例えばその装置がそのメッセージデータを受付ける場合に、メッセージデータを装置の特定のバッファへ指向させるような種々の目的のために使用することが可能である。ヘッダーにおいて付加的なビットを包含させ且つ最後のノードにおいてビットテストを実行することの利点は、該相互接続構成体の全てのレベルにおけるノードの全てが一貫性を持って動作するということである。
相互接続構成体の幾つかの実施例においては、付加的なヘッダービットがメッセージパケット内に含まれている。このビットは、メッセージパケットが送信中であることを表わす。このようなヘッダーにおける付加的なビットに対する別の目的は、該ヘッダー内のどのビットが制御ビットであるかを識別することである。
メッセージパケットは、２つの条件、即ち、（１）メッセージパケットのターゲットリングがレベルＴ−１からアクセス可能であること、及び（２）該メッセージパケットがレベルＴ−１上のメッセージによってブロックされないことの２つの条件を満足する限り、レベルＴから次の内側のレベルＴ−１へ移動する。
この構成体の１つの顕著な側面は、そのターゲットリングへアクセスすることの可能なレベルＴ上のノードＮ（T,q,z）における任意のメッセージパケットが、そのアドレスリングのビットＴ−１がそのターゲットリングのビットＴ−１と同一である場合にのみ、ノードＮ（Ｔ−1,q＋1,z）から該ターゲットリングへアクセスすることも可能であるということである。従って、単一ビットのみの解析が、正しいルーチング即ち経路付けの決定を行なうための全ての情報を発生する。
図16を参照して、２つの隣接するレベルＴとＴ＋１上のメッセージパケットの間の一般的な関係について説明する。この例においては、リング２に対してターゲットされているレベル４上のノードN400におけるメッセージパケットＭがレベル３上の高さ０乃至７の各々の上に存在するノードN30iにおける８個のメッセージパケットm0810,m1811,m2812,m3813,m4814,m5815,m6816,m7817によってブロックされる可能性がある。該相互接続構成体の挙動を例示のためにレベル３及び４に関して解析するが、この解析は全ての任意の隣接するレベルに対して適用可能である。例示的に時間ステップ０と呼ばれる任意の時間ステップにおいてメッセージＭが、ノードN310に接続されているデータ出力端子を有するレベル３のノードからノードN400へ制御コードが送られない限り、レベル４上のノードN400からレベル３上のノードN310へ移動する。この例においては、ノードN307はノードN310へ接続しているデータ出力端子を有しており、且つ時間ステップ０において、メッセージm7817はノードN307において存在する。従って、ノードN307は制御コード、この例においては、単一ビットのコードをノードN400へ送給し、相互接続線上でノードN418に対してメッセージＭを偏向させる。時間ステップ１において、リング１はノードN328からアクセス可能ではないので、ノードN328がブロックされているか否かに拘らず、メッセージＭは相互接続線上をノードN418からノードN424へ移動する。時間ステップ２において、メッセージＭは、制御ブロック用コードがノードN320からノードN424へ送給されない限り、メッセージＭはノードN424からノードN334へ移動する。尚、ノードN320は、ノードN334のデータ入力端子へ接続しているデータ出力端子を有するレベル３上のノードである。然しながら、メッセージm3813は現在ノードN320に存在しているので、メッセージＭはノードN334へアクセスすることからブロックされる。偏向制御コードが、ノードN320からノードN424へ送給される。更に、メッセージパケットmjのいずれもがレベル２及びそれを超えて進行することがないと仮定すると、時間ステップ４において、メッセージＭは制御ビット線上を送られる制御コードを介してメッセージm5815によってブロックされる。時間６において、メッセージＭは、制御ビット線上のブロック用制御コードを介してメッセージm1811によってブロックされる。
この例は、開示した相互接続構成体の種々の利点を例示している。第一に、レベルＴ−１上のメッセージmjが全てのレベルＴに対してレベルＴ−１へ進行することを継続してブロックする場合には、メッセージＭの偏向は、レベルＴ上の全ての高さを完全に周遊する。従って、レベルＴ上のメッセージＭは、2T-1個のメッセージがメッセージＭをブロックするためにレベルＴ−１上の所定の位置にある場合にのみ、レベルＴ上のメッセージＭは該高さの完全な周遊に対してブロックされる。一般的に、レベルＴ上の同一のメッセージＭを二度ブロックするためには、レベルＴ−１上のメッセージmjは、2T+1時間ステップの間レベルＴ−１上に留まられねばならない。
この説明は、高さ次元が宛先リング位置と一致する場合に１つのレベル前進させ且つ該リング位置が高さ指定と一致しない場合に該リングをトラバースさせることによって、メッセージが外側のレベルからコアの内側層における装置へ下降する相互接続構成体を例示している。その他の実施例においては、メッセージは内側のレベルから外側のレベルへ移動することが可能である。幾つかの実施例において、レベルが変化する場合に該高さをトラバースすることが可能であり、且つ該レベルが静止状態に留まる場合に該高さは一定に保持される。これらの実施例において、ノードを介してのメッセージの前進は説明した相互接続構成体と実質的に均等である。然しながら、メッセージのブロック作用を回避する説明したネットワークの利点は否定される。
図17を参照すると、タイミング線図が説明した相互接続構成体におけるメッセージ通信のタイミングを例示している。本相互接続構成体の種々の実施例において、メッセージ通信の制御はノードに到着するメッセージのタイミングによって決定される。例えば図18に示したパケット900等のメッセージパケットは同期ビット914とヘッダー910とペイロード920とを包含している。ヘッダー910は二進形態においてターゲットリングを指定する一連のビット912を包含している。角度q1及び高さz1におけるソース（供給源）装置CU（q1,z1）が角度q2及び高さz2における宛先（destination）装置CU（q2,z2）へメッセージパケットＭを送給する場合には、ヘッダー910のビット912が高さz2の二進表示へ設定される。
全相互接続構成体を司るグローバルクロックは整数時間係数Ｋを維持し、尚、Ｋは円筒高さｚにおけるノード数ｎを指定する。２つの定数ａ及びｂが存在しており、ａの期間はｂの期間を超えており且つ以下の５つの条件が充足されている。第一に、レベルＴ上のノードＮ（T,q,z）を出た後にレベルＴ上のノードＮ（T,q＋1,hT（ｚ））を出るためのメッセージＭに対する時間の量はａである。第二に、レベルＴ上のノードＮ（T,q,z）を出た後に、レベルＴ−１上のノードＮ（Ｔ−1,q＋1,z）を出るためのメッセージＭに対する時間の量はａ−ｂである。第三に、装置CUからノードＮ（r,q,z）へメッセージが進行するための時間の量はａ−ｂである。第四に、時間期間ａにおいてメッセージＭがノードＭ（r,q,z）からノードＮ（r,q＋1,hr（ｚ））へ移動する場合に、メッセージＭは、ノードＮ（r,q,z）からノードＮ（ｒ＋1,q＋1,hr（ｚ））へ制御コードを送給させ、外側のレベルｒ＋１上でメッセージを偏向させる。メッセージＭがノードＮ（r,q,z）へ入る時間から該制御ビットがノードＮ（ｒ＋1,q,hr+1（ｚ））に到着するまでに経過する時間は時間期間ｂである。前述した４番目の条件は、又、メッセージＭがノードＮ（J,q,z）から最も外側のレベルＪにおけるノードＮ（J,q＋1,hJ（ｚ））へ移動する場合にも適用可能であり、従って、メッセージＭは、更に、制御コードをノードＮ（J,q,z）から該ネットワーク外側の装置Ｄへ送給させ従ってＤはデータをＮ（J,q＋1,hj（ｚ））へ送る。１実施例においては、Ｄ＝CU（ｑ＋1,hj（ｚ））であり、メッセージＭがノードＮ（r,q,z）へ入る時間から該制御ビットが装置CU（q,z）に到着するまでに経過時間は時間期間ｂである。第五に、グローバルクロックはａの割合でタイミングパルスを発生する。
ソース即ち供給源装置CU（q1,z1）が宛先装置CU（q2,q2）へメッセージパケットＭを送給する場合には、メッセージパケットＭは装置CU（q1,z1）のデータ出力端子から最も外側のレベルＪにおけるノードＮ（J,q1,z1）のデータ入力端子へ送給される。メッセージパケット及び制御ビットが、ｎを正整数として、na＋Lbの形態を有する時間においてレベルＴ上のノードＮ（T,q,z）へ入る。装置CU（q1,z1）からのメッセージＭは時間t0−ｂにおいてノードＮ（J,q1,z1）のデータ入力端子へ送給され且つノードＮ（J,q1,z1）がレベルＪ上をトラバースするメッセージから発生する制御ビットによってブロックされない限り、時間t0においてノードＮ（J,q1,z1）のデータ入力端子へ挿入される。時間t0は（q2−q1）ａ＋Jbの形態を有している。同様に、ノードＮ（J,q1,z1）のデータ入力端子が装置CU（q1,z1）からのメッセージパケットを受取る（q2q1）ａ＋Jbの形態の時間が存在している。
ノードＮ（T,q,z）は、メッセージパケットＭのターゲットアドレス及びその他のノードからのタイミング信号に基づいてメッセージの経路付けを制御する論理を包含している。ノードＮ（T,q,z）の第一論理スイッチ（不図示）は、メッセージパケットＭが次のレベルＴ−１上のノードＮ（Ｔ−1,q＋1,z）へ進行すべきか否か又はノードＮ（Ｔ−1,q＋1,z）がブロックされるべきか否かを決定する。ノードＮ（T,q,z）の第一論理スイッチは、ノードＮ（Ｔ−1,q,Hr-1（ｚ））から送給された単一ビットブロック用制御コードが時間t0においてノードＮ（T,q,z）に到着するか否かに従って設定される。例えば、幾つかの実施例においては、第一論理スイッチは、ノードＮ（Ｔ−1,q＋1,z）がブロックされる場合に論理１の値をとり、且つそうでない場合には、論理０の値をとる。ノードＮ（T,q,z）の第二論理スイッチ（不図示）は、メッセージパケットＭが次のレベルＴ−１上のノードＮ（Ｔ−1,q＋1,z）へ進行すべきか否か、又はノードＮ（Ｔ−1,q＋1,z）がメッセージパケットＭのヘッダーの宛先装置CU（q2,z2）へアクセスするのに適当な経路内に存在するか否かを決定する。メッセージパケットＭのヘッダーは宛先高さz2の二進表示（z2(J),z2(J-19),...,z2(T),...,z2(1),z2(0)）を包含している。レベルＴのノードＮ（T,q,z）は、高さ指定ｚ（zJ,zJ-1,...,zT,...,z1,z0）の単一ビット宛先zTを包含している。この実施例においては、第一論理スイッチが論理０の値を有しており且つ宛先高さのビット指定z2(T)が高さ指定zTと等しい場合には、メッセージパケットＭはノードＮ（Ｔ−1,q＋1,z）における次のレベルへ進行し且つ宛先高さビットz2(T)がメッセージパケットＭのヘッダーから剥取られる。そうでない場合には、メッセージパケットＭは同一のレベルＴ上でノードＮ（T,q＋1,hT（ｚ））へトラバースする。メッセージパケットＭがノードＮ（Ｔ−1,q＋1,z）へ前進する場合には、メッセージパケットＭは時間t0＋（ａ−ｂ）に到着し、それは時間（z2−z1＋１）ａ＋（Ｊ−１）ｂと等しい。メッセージパケットＭがノードＮ（T,q＋1,hT（ｚ））をトラバースする場合には、メッセージパケットＭは時間t0＋ａに到着し、それは時間（z2−z1＋１）ａ＋Jbに等しい。メッセージパケットＭがノードＮ（r,q,z）からノードＮ（T,q＋1,hT（ｚ））へ送給される場合に、単一ビット制御コードがノードＮ（Ｔ＋1,q＋1,HT+1（ｚ））又は装置CU（q,z）へ送給され、それは時間t0＋ｂに到着する。このタイミング条件は該相互接続構成全体にわたって継続され、メッセージパケットが前進され且つ偏向される場合に同期性を維持する。
メッセージパケットＭは指定された宛先高さz2においてレベル０に到着する。更に、メッセージパケットＭは時間０係数Ｋ（高さｚにおけるノード数）においてターゲットされた宛先装置CU（q2,z2）に到着する。ターゲットされた宛先装置CU（q2,z2）がメッセージパケットＭを受付ける準備がなされている場合には、入力ポートが時間０係数Ｋにおいて活性化されてそのパケットを受付ける。効果的なことであるが、全ての経路付け制御動作は、２つのマルチビット値を比較することなしに、２つのビットを比較することによって達成される。更に効果的なことであるが、本相互接続構成体の出口点において、メッセージパケットが該ノードから該装置へ前進する場合に、比較論理は存在しないということである。装置がメッセージを受付ける準備がされている場合には、そのメッセージはクロック制御型ゲートを介して該装置へ入る。
開示したタイミング及び相互接続構成の結果として多数の利点が発生する。本相互接続構成体の電子的実現ではなく光学的実施例においては、ヘッダーのビットをコード化する信号は、典型的に、ペイロードをコード化するビットよりも一層長い期間を有している。メッセージが本相互接続構成体を介して通信する場合に、タイミングが僅かにスキュー即ち歪むために、ヘッダービットは期間が拡張されている。より長い期間のヘッダービットは、メッセージがスキューされている場合であってもビットの正確な読取を行なうことを可能とする。対照的に、ペイロードビットは該相互接続構成体を介しての通信期間中に読取られることのないデータをコード化する。開示したタイミング条件は、１つのメッセージにおけるヘッダービットの数が著しく減少されるので効果的である。更に、幾つかの実施例においては、ビットは各レベルにおける制御目的のために使用され、次いでメッセージが本相互接続構成体内のレベルからレベルへパスする間に廃棄されるので、ヘッダービットの数がデクリメントされる。本相互接続構成体の各レベルに対する制御ビットを廃棄する実施例においては、各ノードにおける論理が簡単化される。何故ならば、各レベルにおける制御ビットは本相互接続構成体全体にわたり同一の位置に位置されているからである。
同一のレベル上で通信されるメッセージが別のレベルから通信されるメッセージよりも優先性を有しているということは、同様に、有益的である。何故ならば、メッセージヘッダーにおいて優先性の情報を担持することなしに、メッセージの競合が解決されるからである。そうでない場合には、メッセージの競合は、典型的に、相互接続構成体内に最も長く存在しているメッセージに対して優先性を与えるか又は所定の優先付けに従って解決される。これらの技術は競合を解決するためにヘッダー内に格納されている情報を使用する。
本相互接続構成体及びメッセージ通信方法はノードに対して局所的であり且つメッセージタイミングに依存する自己経路付け決定を使用してメッセージ送信経路付けを決定することが有益的なものであるが、制御構造の幾つかの実施例においては、ローカルとグローバルの両方の通信制御が使用される。例えば、相互接続構成体の１つの実施例では、第一送信モードにおいてメッセージパケットの送信を制御するためのタイミングに基づくローカル即ち局所的な制御を使用し、且つ、代替的に、第二モードにおいて長いストリングのメッセージデータの通信を管理するためにスケジューラーを介してグローバル制御を使用する。グローバルモードにおいては、スケジューラーを使用することが、制御ビット入力及び出力端子を使用することを不必要なものとさせている。
メッセージパケットの自己経路付けの１つの結果は、ターゲット装置においてのメッセージパケットの受領の順番を可変のものとすることが可能であるということである。幾つかの実施例においては、メッセージセグメントの正しい順番はメッセージヘッダー内において順番情報を送給することにより順番付けされる。その他の実施例はメッセージパケットを順番付けするために光学的なソーター即ち分類器を使用する。
メッセージの経路付けを制御するために、ヘッダーにおける制御ビットではなく、タイミング特性を使用する制御構成及び通信方法を介して多くの利点が実現されるものであるが、幾つかの相互接続ノード技術は、タイミング成分を使用することなしに経路付けシステムにおいてより適切に動作する。従って、これらの技術においては、そのメッセージが予め設定した宛先に到着するように所定の時間においてメッセージを導入する代わりに、経路付け情報が付加的なヘッダービット内に収容されている。従って、指定したターゲット装置位置が、例えば、指定したターゲットリング位置に続くビット等のヘッダービット内に含まれる。
１実施例においては、ターゲット装置のラベルが論理０のストリングにおける単一の論理１として表わされる。従って、メッセージが装置Ｎに到着する場合に、該装置は該ヘッダーの装置要素のＮ番目のビットをサンプルし（リング要素から区別されるものとして）且つそのＮ番目のビットが論理１である場合にそのメッセージを受付ける。この技術は、光学的ノード実施例に対して高度に適している。
ノード
ノードＮ（r,q,z）は、データを別のデータ経路へ指向させるための種々のデータ通信スイッチを参照するために一般的な用語で説明した。現在使用可能なノード構成体は、電子的ノード、光学的ノード、混合光学的／電子的ノードを包含している。請求の範囲に記載しているものは、例えば、相互接続及びタイミング方法、相互接続装置及び相互接続トポロジィを包含している。これらの方法及び装置は、一般的な意味におけるノードを包含している。従って、請求の範囲は、本明細書において記載する特定のタイプのノードによって制限されるものではなく、且つ本明細書において記載するノードの機能を実行する現在公知の又は将来における任意のノードへ拡張すべきものである。
図19を参照すると、ノード1300の１例が示されており、それはニオブ酸リチウム（LiNbO3）ゲート1302を包含している。ニオブ酸リチウムゲート1302は、２つのゲート入力端子1310及び1312、２つの出力データ出力端子1320及び1322、１つの制御入力端子1330を有している。ノード1300の制御出力端子1332を形成するために、種々の制御回路1340がニオブ酸リチウムゲート1302へ付加されている。ノード1300は、更に、光学的・電子的変換器1354,1356,1358を包含している。ニオブ酸リチウムゲート1302は２×２クロスバーを形成している。データ経路1342及び1344は光学的であり且つノード1300の制御は電子的である。ニオブ酸リチウムゲート1302は光検知器1350及び1352と２・３の電子的論理構成要素と結合されて相互接続構成体の種々の実施例に対するノード1300を形成している。
動作について説明すると、メッセージパケット1360がノード1300に近づくと、メッセージパケット信号1360の一部が分離され且つ以下の説明に従って宛先リングの二進表示の１ビットを指定するメッセージパケットヘッダー（図18に示す）の同期ビット914が光検知器1350によって読取られる。このビットは光学的形態から電子的信号へ変換される。このビット、ノード1300が存在している円筒高さを指定するビット、次のレベル上の宛先ノードがブロックされるか否かを指定するビットが、電子的に処理され、且つこれらのビットの論理テストの結果がニオブ酸リチウムゲーム1302の制御入力端子1330へ指向される。第一タイプのニオブ酸リチウムゲート技術においては、その結果信号が論理０である場合には、該ゲートはクロス状態でスイッチする。第二タイプのニオブ酸リチウムゲート技術においては、論理０の結果信号が該ゲートをバー（直線的に通過）状態でスイッチする。
図20を参照すると、ノード1400の付加的な例が示されている。ノード1400はスイッチング機能を実施するために非線形光学的ループミラー（NOLM）1410を使用している。非線形光学的ループミラーは、極めて高速である完全に光学的なスイッチを形成するために物質の屈折率を利用する装置である。NOLMスイッチの１例は、データ入力端子1412及び制御入力端子1414を包含している。制御入力端子1414における信号に依存して、データは、そのデータがエンターした同一のデータ入力端子1412を介してNOLM1410を出る（従って、ミラーという用語が使用される）か、又は該データはデータ出力端子1416を介して出る。データは分極され且つ等しい強度の２つの信号「半割り」に分割される。制御パルスが存在しない場合には、該信号のこれら２つの半割りは再結合し且つデータ入力端子1414を介してNOLM1410から出る。制御パルスが制御入力端子1414へ印加される場合には、該制御パルスが該データパルスに対して直角に分極され且つNOLM1410内に挿入され、従って該制御パルスは該データパルスの半分と共に進行する。該制御パルスは該データパルスよりもより強力であり、且つ該データパルスと該制御パルスの結合された最初の半分が該データパルスの２番目の半分を迅速に通過し、従って該データパルスの２番目の半分は僅かに加速されるに過ぎない。従って、該データパルスのこれら２つの半割りは僅かに異なった速度で進行し且つこれら２つの半割りが再結合される場合に180度位相がずれている。この位相差は、該結合されたデータパルス信号をしてデータ出力端子1416を介して通過させる。NOLM1410の１つの欠点は、長尺の光学的伝送ループが使用される場合にのみスイッチングが動作可能であり、従って待ち時間が問題であるという点である。
図21を参照すると、ノード1500の別の例が示されており、それはテラヘルツ光学的非対称デマルチプレクサ（TOAD）スイッチ1510を使用している。TOADスイッチ1510はNOLMスイッチ1410の変形例である。TOAD1510は、オプチカルファイバーループ1512及び半導体要素1514、例えば、非線形要素（NLE）又は半導体光学的増幅器を包含している。TOADスイッチ1510は入力データ端子1520を有しており、それはある条件下において出力データポートとしても作用する。TOADスイッチ1510は、更に、別個の第二出力データ端子1522を有している。半導体要素1514はオプチカルファイバーループ1512の中心1516に関して非対称的に配置されている。半導体要素1514からオプチカルファイバーループ1512の中心1516への距離1518は、１ビットのデータを送信するための距離である。TOAD1510は、高いデータレートを有する信号から単一のビットを除去することによって機能する。TOAD1510は、半導体要素1514を介して一定の電流を通過させることによってスイッチされる。該半導体物質にエンターする光学的信号が、該物質の屈折率をすぐさま変化させる。該光学的信号が終了した後に、該屈折率は該光学的信号の印加前のレベルへゆっくりと（数ビットのタイムスパン）復帰する。制御パルスは光学的データ信号のものよりもより大きな強度を有すると共に光学的データ信号に対して直角の分極即ち偏光を有する光学的信号である。光学的データ入力信号が分極され且つ等しい強度の２つの信号「半割り」へ分割される。該制御パルスは除去されるべきビットの直接上側をオプチカルファイバーループ1512を介して移動する態様で注入される。距離1518は正確に１ビットの長さであるので、１ビットに対応する分割された光学的データ信号の半分が、丁度該ビットの他の半分が半導体要素1514へエンターする時に半導体要素1514から出る。該制御パルスは該光学的データ信号ビットの半分と結合するに過ぎず、従ってこれらの２つの半割りの速度は異なる。結合されたデータ及び制御信号ビットは入力データ端子1520においてTOAD1510を出る。従って、この第１ビットは該データ経路から除去される。次の光学的信号ビットが分割され且つ反対の方向に移動する第一の半割りと第二の半割りとが、半導体要素1514の屈折率が次第に変化するに従いほぼ同一の量遅延され、従ってこのビットは除去されない。数ビットが半導体要素1514を介して通過した後に、該半導体物質は緩和し且つ該光学的データ信号から別のビットをマルチプレクスする準備がなされる。効果的に、TOAD1510は非常に短い光学的伝送ループ1512を有している。
再生器
メッセージがノードを介して伝搬するに従い強度を喪失し且つノイズをピックアップすることがあるノードの特性である。種々のその他のノードを使用して、メッセージ信号は強度を喪失することはないが、メッセージ伝送期間中にノイズが蓄積する。従って、本相互接続構成体の種々の実施例において、信号再生器又は増幅器を使用して、メッセージが多数のノードを通過した後にメッセージの信号忠実性を改善させる。
図22を参照すると、再生器1600の１実施例が示されており、それはニオブ酸リチウムゲート1602を使用して構成されている。ニオブ酸リチウムゲート1602は2.5ギガビットの程度の伝送速度を有するメッセージデータを再生する。ニオブ酸リチウムゲート1602は光学的メッセージ信号を検知し且つそれを電子的信号へ変換し、該電子的信号はニオブ酸リチウムゲート1602の電子的入力ポート1604を駆動する。ニオブ酸リチウムゲート1602はゲート1602の２つの光学的データポート1606及び1608のうちの１つへ印加されるクロック信号を使用してクロック動作される。該クロック信号は電子的制御パルスによってスイッチ動作され且つ高忠実度の再生された信号がニオブ酸リチウムゲート1602から射出される。
典型的に、再生器1600においてニオブ酸リチウムゲート1602を使用する相互接続構成体もゲートを構成するためにニオブ酸リチウムゲートを使用している。１つの大型のパワーレーザー（不図示）が高忠実度のタイミングパルスを相互接続構成体における全ての再生器へ供給する。例示的な再生器1600及びノード1650の組合わせは、光学的結合器1620を包含しており、それは、ノード1650と同一のレベルＣ上のノードへの第一データ入力接続を有すると共に上側に存在するレベルＣ＋１上のノードへの第二データ入力接続を有している。例示的な再生器1600は、更に、光学的結合器1620の出力端子へ接続している光検知器1622と、光検知器1622を介して光学的結合器1620へ接続している入力端子を具備する光学的・電子的変換器1624と、ニオブ酸リチウムゲート1602に接続している出力端子とを包含している。ニオブ酸リチウムゲート1602の出力端子はノード（不図示）の第二ニオブ酸リチウムゲート（不図示）へ接続している。該ニオブ酸リチウムゲート（不図示）の２つの信号線が結合され、再生され且つスイッチされる。
再生器又は増幅器が信号忠実度を改善するために組込まれており且つ再生器又は増幅器によってメッセージ信号を再調整するために使用される時間が時間ａ−ｂを超える場合には、該再生器又は増幅器は、該ノードの入力端子の前に配置され且つその遅延を受付けるためにタイミングが修正される。
その他の実施例
図１乃至16に示した相互接続構成体は本発明の原理を容易に理解することを意図した簡単化した構成体である。基本的な構成体に対して多数の変形例が可能である。別の相互接続構成体の種々の例について、これらの変形構成体によって得られる利点と共に以下に説明する。
図23を参照すると、相互接続構成体の別の実施例1000が、最も外側のレベルＪの複数個のノード1002へメッセージパケットを発生する装置1030を包含している。図１乃至16に示した相互接続装置100においては、装置CU（q,z）が、ノードＮ（J,q,z）に対してメッセージパケットを送ることによりメッセージ伝送動作を開始させる。別の相互接続構成体1000においては、装置CU（q,z）が、ノードＮ（J,q,z）へメッセージパケットを送ることによってメッセージ伝送動作を開始させるが、更に、付加的な複数個のノードＮ（Ｊ′,q′,z′）への相互接続を包含しており、その場合にｚは最も外側のレベルＪの高さ０乃至2Jから選択した円筒高さを指定し且つｑは高さｚの角度０乃至Ｋから選択したノード角度を指定する。装置が最も外側のレベルにおける１つを超えるレベルへメッセージを送る場合には、開示したタイミング技術が、時間０係数Ｋにおいてターゲットノードにメッセージが到着する特性を維持する。
装置は集束するデータ経路を有するノードへ高い割合で一連のメッセージを複数個の装置が送ることによって発生される相互接続構成体へのエントリ時の渋滞を回避するために、最も外側のレベルＪにおける多数のノードへ接続されている。幾つかの実施例においては、装置が接続されているノードがランダムに選択される。その他の実施例においては、１つの装置の幾つかのノードへの複数個の相互接続が所定の態様で選択される。１つの装置を幾つかのノードへ接続させることから発生する付加的な利点は、通信ネットワークの入力帯域幅を増加させることである。
図24を参照すると、相互接続構成体の別の実施例1100が、最も内側のレベル０の複数個のノード1102からメッセージパケットを受取る装置1130を包含している。この例においては、特定の高さｚにおけるノード数Ｋは９であり且つ各装置1130はレベル０上の３個のノードからメッセージを受取るべく接続されている。相互接続構成体1100は、特定の高さにおけるノード数Ｋが大きい場合にネットワーク出口帯域幅を改善するために効果的である。
高さｚ上のノード数Ｋが９であり且つ各装置がレベル０上の３個のノードからメッセージを受取る例においては、リング０上の各ノードが３個のレベルを有するバッファへ接続している。時間０において、メッセージデータがレベル０バッファ内へ注入される。時間３において、データがレベル１バッファ内へ注入される。時間６において、データがレベル２バッファ内へ注入される。装置CU（q,0）がノードＮ（0,q,0）におけるレベル０バッファから読取り、ノードＮ（0,（ｑ＋３）mod9,0）におけるレベル１バッファから読取り、且つノードＮ（0,（ｑ＋６）mod9,0）におけるレベル２バッファから読取る。このメッセージデータの読取りは、同期的または非同期的な態様で達成される。同期的モードにおいては、時間ｔが、該バッファから該装置へデータを転送するものと予測される。この場合においては、装置CU（q,0）が時間ｔにおいてレベル０バッファから読取り、時間３＋ｔにおいてレベル３バッファから読取り、且つ時間６＋ｔにおいてレベル６バッファから読取る。非同期モードにおいては、装置CU（q,0）が以下に記載するように３個のバッファへ相互接続し且つデータが使用可能であることをバッファが知らせる場合にメッセージデータを読取る。
図25を参照すると、相互接続構成体の別の実施例1200が、最も外側のレベルＪにおいてのみならずその他のレベルにおいても複数個のノード1202へメッセージパケットを発生する装置1230を包含している。別の相互接続構成体1200においては、装置CU（q,z）が、ノードＮ（J,q,z）へメッセージパケットを送ることによってメッセージ伝送動作を開始させるが、更に、付加的な複数個のノードＮ（T,q,z）への相互接続を包含しており、尚Ｔは相互接続構成体1200のレベルを指定し、ｚは最も外側のレベルＪの高さ０乃至2Jから選択した円筒高さを指定し、且つｑは高さｚの角度０乃至Ｋから選択したノード角度を指定する。装置がレベルを超えてノードへメッセージを送給する場合には、メッセージ通信は以下の如く優先度に従って制御される。第一に、同一のレベルＴからノードＮ（r,q,z）へエンター即ち入るメッセージが第一優先度を有している。第二に、高さレベルＴ＋１からのノードＮ（r,q,z）へエンターするメッセージは第二優先度を有している。装置CU（q,z）からノードＮ（r,q,z）へエンターするメッセージは最後の優先度を有している。相互接続構成体の別の実施例1200は装置が隣りの装置へより迅速にメッセージを送ることを可能とさせる。開示したタイミング技術は、時間０係数（即ち、modulus）Ｋにおいてメッセージがメッセージヘッダーにおいて指定されているノードに到着する特性を維持する。
これらの種々の実施例において、装置は種々の所定の技術のうちの１つを使用してレベル０ノードからのデータを受付ける。幾つかの実施例は該装置がデータを受付け従って装置が時間０係数Ｋにおいてデータを受付ける時を決定するために専らタイミングに依存する。幾つかの実施例は、係数（即ち、modulus）Ｋタイミングに関して種々の所定の時間でメッセージデータを受付ける装置を包含している。更にその他の実施例は、バッファがデータを受付ける準備がされている場合にデータを受付ける装置を有している。
波分割多重化実施例
相互接続構成体の別の実施例において、メッセージ信号帯域幅が波分割多重化を使用して増加されている。複数個のＫ個のカラー（色）が定義され且つ円筒高さにおいてＫ個の装置を有する相互接続構成体を使用して伝送されるメッセージ信号において発生される。従って、各装置は特定のカラー即ち色が割り当てられている。メッセージパケットは単一波長相互接続システムに対し前述した態様で予め選択したターゲットリングへ進行する。メッセージパケットはそのメッセージパケットへ割り当てられているカラーに依存して、レベル０から適宜の装置へ通過する。
メッセージはヘッダーとペイロードとを包含している。該ヘッダー及びペイロードは異なるカラーを有することによって区別される。同様に、ペイロードは異なるカラーを使用してマルチプレクサ即ち多重化され、それらは、更に、該ヘッダーのカラーとも異なっている。メッセージ帯域幅は、更に、該メッセージの同時的伝送のために異なるカラーの異なるメッセージを結合させることによって増加される。更に、異なるカラーの異なるメッセージは同一のターゲットリング上で束縛され、結合され且つ同時的に伝送される。全てのメッセージはノードの全てにおいてデマルチプレクスされるものではないが、該装置への入力バッファにおいてデマルチプレクスされる。
可変ベースiJ高さ構成体実施例
更なる付加的な実施例において、相互接続構成体はＪ＋１個のレベルの各々に対する１つのレベル上にiJ個の円筒高さを有しており、尚ｉは例えば２（前述した実施例）、3,4又はそれ以上の適宜の整数である。前述したように、各高さはＫ個のノードを有しており、且つ各ノードは２個のデータ入力端子と、２個のデータ出力端子と、１個の制御入力端子と、１個の制御出力端子とを有している。
例えば、相互接続構成体はレベル当たり3J個の高さを有することが可能である。レベル１上において、メッセージデータは３つのレベル０高さのうちの１つへ通信される。レベル２上において、メッセージデータは９個のレベル０高さのうちの１つへ通信され、以下同様である。この結果は以下の如くにして達成される。第一に、ノードＮ（r,q,z）の２つの出力データ端子が前述した態様でノードＮ（Ｔ−1,q＋1,z）及びノードＮ（T,q＋1,hT（ｚ））の入力データ端子へ接続している。然しながら、この異なる実施例においては、２番目の高さ変換hT（hT（ｚ））ではなく３番目の高さ変換hT（hT（hT（ｚ）））が元の高さ指定ｚと等しい。このような態様で相互接続されたノードの場合には、ターゲットリングがレベル１上の３つ目のステップ毎にメッセージデータへアクセス可能である。この形態を有する相互接続構成体においては、２つの出力データ端子を具備するノードが適切なものであるが、出力データ端子の数を３へ増加させることによって利点が得られる。従って、与えられたレベル上の１つのノードの１つのデータ出力端子がそのレベル上の２つのノードへ接続され且つ後続のレベル上の１つのノードへ接続される。従って、各レベルは3J個の高さ及び１個のメッセージパケットを有しており且つメッセージは１つおきのステップ毎により低いレベルへ下降することが可能である。
このように、種々の数ｉに対しレベル当たりiJ個の高さを使用することによって多数の異なる相互接続構成体が形成される。ｉが４に等しい場合には、４番目の高さ変換hT（hT（hT（hT（ｚ））））が元の高さ指定ｚに等しい。ｉが５である場合には、５番目の高さ変換hT（hT（hT（hT（hT（ｚ）））））は元の高さｚと同じであり、且つ以下同様である。
可変ベースiJ高さ構成体実施例においては、ターゲットリングが特定のノードからアクセス可能であるか否かは、そのターゲットリングを指定するコードの１つを超えるビットをテストすることによって決定される。
可変ベース変換技術実施例
相互接続構成体の更に別の実施例においては、前に概観を示した高さ変換技術が以下の如くに修正される。この実施例においては、前述した二進高さ変換技術ではなく、ベース３表記法高さ変換技術が使用される。ベース３変換技術においては、ターゲットリングはベース３の数のシーケンスによって指定される。従って、レベルｎ上において、高さ指定のｎ個の低次ベース３数字は順番が反転され、低次ビットの反転された高さ指定は１だけインクリメントされ、且つ該ｎ個の低次ベース３数字は再度反転される。例示的な相互接続構成体は４個のレベル（Ｊ＝３＋１）、レベル当たり９個の高さ（3J＝33）、及び高さ当たり５個のノード（Ｋ＝５）を有している。このベース３高さ変換技術によれば、レベル２上のノードN23(201)は、レベル３上のノードN32(201)のデータ出力端子へ出力している第一データ入力端子と、レベル２上のノードN22(220)のデータ出力端子へ接続している第二データ入力端子とを有している。ノードN23(201)は、更に、レベル１上のノードN14(201)のデータ入力端子へ接続している第一データ出力端子と、ノードN24(211)のデータ入力端子へ接続している第二データ出力端子とを有している。ノードN23(201)は、更に、ノードN13(200)の制御出力ビットへ接続している制御入力ビットと、ノードN33(211)の制御入力ビットへ接続している制御出力ビットとを有している。この実施例においては、該ヘッダーは同期ビットと、それに続くベース３においてのターゲットリングのアドレスとを包含している。例えば、ベース３の数字は00,01,10として二進形態において、又は001,010,100の形態で３個のビットを使用して記号化される。
例えばベース５又はベース７演算等の種々の数値的ベース即ち基数を使用し、且つ前述した数字反転、インクリメント、再反転方法を使用して、更なる付加的な高さ変換技術が可能である。
マルチレベルステップ実施例
別の実施例においては、ノードの相互接続構成体は、５個の入力端子と５個の出力端子とを包含する10個の端子を有している。該入力端子は、３個のデータ入力端子と２個の制御入力端子とを包含している。該出力端子は、３個のデータ出力端子と２個の制御出力端子とを包含している。この相互接続構成体においては、ノードは、通常、５個の隣接する円筒レベル間に接続されている。特に、Ｔ円筒レベルにおけるノードＮ（T,q,z）は、T,T＋1,T＋2,T−1,T−２レベル上のノードへ接続されている端子を有している。これらの接続は、ノードＮ（T,q,z）が同一のレベルＴ、次の外側のレベルＴ＋１、前の外側のレベルＴ＋２上のノードへ接続しているデータ入力端子を有している。特に、ノードＮ（T,q,z）はノードＮ（T,q−1,hT（ｚ））,N（Ｔ＋1,q−1,z）,N（Ｔ＋2,q−1,z）のデータ出力端子へ接続しているデータ入力端子を有している。ノードＮ（T,q,z）は、更に、次の外側のレベルＴ＋１及び前の外側のレベルＴ＋２上のノードへ接続しており、データ入力端子に対応する、制御出力端子を有している。ノードＮ（T,q,z）はノードＮ（Ｔ＋1,q−1,z）及びＮ（Ｔ＋2,q−1,z）の制御入力端子へ接続している制御出力端子を有している。ノードＮ（T,q,z）は、更に、同一のレベルＴ、次の内側のレベルＴ−１、爾後の内側のレベルＴ−２上のノードへ接続しているデータ出力端子を有している。特に、ノードＮ（T,q,z）は、ノードＮ（T,q＋1,HT（ｚ））,N（Ｔ−1,q＋1,z）,N（Ｔ−2,q＋1,z）のデータ出力端子へ接続しているデータ出力端子を有している。ノードＮ（T,q,z）は、更に、次の内側のレベルＴ−１及び爾後の内側のレベルＴ−２上のノードへ接続しており、データ出力端子へ対応している、制御入力端子を有している。ノードＮ（T,q,z）は、ノードＮ（Ｔ−1,q＋1,z）及びＮ（Ｔ−2,q＋1,z）の制御出力端子へ接続している制御入力端子を有している。
この10端子構成体は、中間レベル２乃至Ｊ−２におけるノードにのみ適用される。何故ならば、外側レベルＪ及びＪ−１におけるノード及び内側レベル１及び０におけるノードはスタンダードの６端子ノードと同一の接続を有しているからである。
この10端子構成体は、可能である場合にメッセージがレベルをスキップして通過することを可能とし、その際に、ノードにおける論理が増加するという犠牲の下でより少ないノードを介して通過することを可能としている。１個のメッセージのみが一度に１つのノードにエンター即ち入ることが許容される。ノードへのメッセージアクセスの優先度は、同一のレベル上のメッセージが最も高い優先度を有しており、１つのレベル離れたノードからのメッセージが２番目の優先度を有しており且つ２つのレベル離れたノードからのメッセージが最後の優先度を有している、というものである。メッセージは、可能である場合にはいつでも、２つのレベル下降する。10個の端子を有する相互接続構成体に対するタイミング規制は６端子ノードを使用するタイミング規制と同一である。10端子ノード相互接続構成体の利点は、メッセージがレベルを介してより迅速に通過するということである。
その他の相互接続構成体実施例は、10個を超える数の端子を有するノードを包含しており、従ってデータ及び制御端子は付加的なレベル上の付加的なノードへ接続される。例えば、種々のノードＮ（T,q,z）は、更に、関連する制御入力端子及びデータ出力端子を有しており、それらは内側のレベルＴ−3,T−４以下同様のレベル上のノードへ接続されている。その他の例においては、種々のノードＮ（T,q,z）は、更に、関連する制御出力端子及びデータ入力端子を有しており、それらは外側のレベルＴ＋3,T＋４以下同様のレベル上のノードへ接続している。種々の相互接続構成体実施例において、ノードは全てのレベル又は選択したレベル間において接続させることが可能である。
同一レベル実施例へのマルチ相互接続
付加的な相互接続構成体実施例は同一レベル上のノード間で付加的な相互接続を利用する。特に、レベルＴ上のノードＮ（T,q,z）は、（１）ノード（T,q＋1,hT（ｚ））の入力データ端子へ接続している出力データ端子及び（２）ノードＮ（T,q−1,HT（ｚ））の出力データ端子へ接続している入力データ端子の接続に加えて、相互接続を有している。従って、レベルＴ上のノードＮ（T,q,z）は、（１）ノードＮ（T,q＋1,gT（ｚ））の入力データ端子へ接続している出力データ端子及び（２）ノードＮ（T,q−1,hT（ｚ））の出力データ端子へ接続している入力データ端子の接続を含む相互接続を有している。円筒高さhT（ｚ）と同様に、高さgT（ｚ）は高さｚの位置と反対のレベルＴの相互接続構成体の半分に関するものである（即ち、二進コードにビットＴが高さhT（ｚ）を記述し且つgT（ｚ）が高さｚのビットＴに対して相補的である）。
次のレベル実施例へのマルチ相互接続
次のレベル実施例へのマルチ相互接続は、ノードＮ（T,q,z）がレベルＴ上の１つのノードＮ（T,q＋1,hT（ｚ））へ接続している１つの出力データ端子を有すると共にレベルＴ−１上の２つのノードＮ（Ｔ−1,q＋1,z）及びＮ（Ｔ−1,q＋1,gT-1（ｚ））へ接続している２つの出力データ端子を有するという点を除いて、前記同一レベル実施例に対するマルチ相互接続と同様である。従って、１つのデータ出力相互接続が同一のレベルをトラバースし、２番目の相互接続が１つのレベル前進し且つ３番目の相互接続が１つのレベル前進すると共にトラバースを行なう。高さhT（ｚ）と同様に、高さgT（ｚ）は高さｚの位置と反対のレベルＴの相互接続構成体の半分に関するものである。ノードアクセス間の競合は、同一のレベル上を移動するメッセージに対して第一優先度を付与し、１つのレベル前進するメッセージに対して２番目の優先度を付与し、且つ１つのレベル前進すると共にトラバースするメッセージに対して３番目の優先度を付与することによって解決される。
本発明のある実施例の説明は例示的なものであって制限的なものを意図したものではない。多数のその他の実施例が当業者にとって自明なものであり、それらは全て本発明の広い範囲内に含まれるものである。例えば、多数の異なるタイプの装置を、これらに制限するわけではないが、ワークステーション、コンピュータ、ターミナル、ATMマシン、全国飛行制御システムの要素等を包含する相互接続構成体を使用して接続させることが可能である。更に、hT及びHT以外のその他の相互接続変換を実施してノード間の相互接続を記述することが可能である。
本説明及び請求範囲は、時折、マルチ即ち複数の次元で配列された相互接続構成体について言及している。この次元に対する言及は相互接続構成体のトポロジィを理解するのに有用なものである。然しながら、これらの次元は空間的次元に制限されるべきものではなく、一般的に、特定の態様で相互接続されているノードのグループを言及するものである。
【図１７】
0003594198.tif 000002
【図１Ａ】
0003594198.tif 000003
【図１８】
0003594198.tif 000004
【図１Ｂ】
0003594198.tif 000005
【図１Ｃ】
0003594198.tif 000006
【図１Ｄ】
0003594198.tif 000007
【図２】
0003594198.tif 000008
【図３Ａ】
0003594198.tif 000009
【図３Ｂ】
0003594198.tif 000010
【図３Ｃ】
0003594198.tif 000011
【図４】
0003594198.tif 000012
【図５】
0003594198.tif 000013
【図６】
0003594198.tif 000014
【図７】
0003594198.tif 000015
【図８】
0003594198.tif 000016
【図９】
0003594198.tif 000017
【図１０】
0003594198.tif 000018
【図１１】
0003594198.tif 000019
【図１２】
0003594198.tif 000020
【図１３】
0003594198.tif 000021
【図１４】
0003594198.tif 000022
【図１５】
0003594198.tif 000023
【図１６】
0003594198.tif 000024
【図１９】
0003594198.tif 000025
【図２０】
0003594198.tif 000026
【図２１】
0003594198.tif 000027
【図２２】
0003594198.tif 000028
【図２３】
0003594198.tif 000029
【図２４】
0003594198.tif 000030
【図２５】
0003594198.tif 000031