(57)【要約】プライベート・メモリを参照する際に達成される典型的効率に相当する効率で共有メモリスペースにおいて並行してランダムなアドレスを参照する能力を有する何十もの処理コアまたはそれ以上に供給される相互接続ネットワークを利用するマルチコア・コンピュータシステムのための共有メモリ・システムが開示される。相互接続ネットワークは、一般に書き込みのためのサブネットワークと、読み込みのための分離したマルチキャスティング・サブネットワークとから構成される。共有メモリ・システムは、再配置なしですべてのクロックサイクルで新たに処理コアとメモリバンクとの間の経路を計算する。それは、メモリにアクセスする取組みが経路の確立の成功につながりそれが達成される承認応答をすべてのコアに、または、取組みが達成されないすべてのコアに拒絶応答を返す。【選択図】図２
2011503710.tif 000002
【特許請求の範囲】
【請求項１】
その複数のポートを経てアクセスできる、情報を記憶・検索するためのシステムであって、複数のメモリバンクであって、メモリ・アドレスのスペースを提供している前記バンクと；相互接続ネットワークであって、該ポートと該メモリバンクとの間のアクセス経路を提供しているネットワークと；を含むシステムにおいて、
該システムは、時間がクロックサイクルに分割される時間制度において操作されていて、該システムは、すべてのクロックサイクルで、通常運転の間、その該ポートで受信される複数のメモリ・アクセス処理の取組みを認め、該システムへの処理の取組みの入力が単一のクロックサイクル内で実行されるように該処理の取組みを取り扱うことができ、該入力は該メモリ・アドレスのスペースにおいて記憶される内容を変更する際に使われる意図を有する内容を含み、該相互接続ネットワークは、処理取組みに応答して、前記システムのポートとその中で含まれるメモリバンクとの間のアクセス経路の確立を試み、そこにおいて、実行される場合、該経路を確立する該試みが単一のクロックサイクル内で実行され、該経路の成功した確立および承認応答の発行を含む該処理の取組みの遂行である第１の可能な結果と、該処理の取組みの取消を知らせる拒絶応答の発行を含む該経路を確立の失敗である第２の可能な結果との２つの可能な結果の１つにつながり、該第１の可能な結果が発生する場合、該メモリ・アドレスのスペースから検索されるいかなる内容の該システムによる送達が単一のクロックサイクル内で実行されるシステム。
【請求項２】
前記相互接続ネットワークが、純粋な組合せの回路とパイプライン・レジスタとのみを含み、該純粋な組合せの回路は再生する回路が生成されないように配置され、該パイプライン・レジスタは、１つのレジスタが、１つのクロックサイクルのみの間いかなる与えられたメモリ・アクセス処理にも役に立つように操作される、請求項１のシステム。
【請求項３】
前記相互接続ネットワークがパイプライン・レジスタの使用なしで組合せの回路のみを含む、請求項２のシステム。
【請求項４】
前記処理の取組みが読み込みおよび書き込み処理のみを含み、読み込まれた処理が意図されたメモリ・アドレスの内容のみを検索しかつ該読み込まれた処理を始める際に用いられる前記システムのポートを経て該内容を変更させずに転送し、書き込み処理が意図されたメモリ・アドレスで変更なく該システムのポートを経て受信された内容のみを蓄積する、請求項１のシステム。
【請求項５】
前記相互接続ネットワークが読み込み処理のみに役に立つ、請求項４のシステム。
【請求項６】
前記相互接続ネットワークが、読み込み処理のみに役に立つ第１の部分と、書き込み処理のみに役に立つ第２の部分と、前記システムと前記メモリバンクのポートとの間で互いに並列して該第１および第２の部分の連結を容易にする第３の部分とに分割される、請求項４のシステム。
【請求項７】
前記相互接続ネットワークの前記第１の部分が、特定のクロックサイクルの間前記同じメモリ・アドレスから同時に内容の検索をリクエストする複数の読み込み処理を達成するため、メモリ・アドレスから読み込まれた内容のマルチキャスティングをサポートする読み込み処理のみに役に立つ、請求項６のシステム。
【請求項８】
前記相互接続ネットワークの前記第１の部分は読み込み処理のみの役に立ち、前記第２の部分は書き込み処理のみの役に立ち、互いに並列に配置される少なくとも１つのサブネットワークを各々含み、該サブネットワークは情報を記憶および検索する前記システムのポートに面しているポートと、前記メモリバンクに面している他のポートとを有していて、少なくとも１つの該サブネットワークは対数関数的マルチステージ・ネットワークである、請求項６のシステム。
【請求項９】
情報を記憶および検索するための前記システムのポートに面している前記サブネットワークの前記ポートの全体の数が、情報を記憶および検索するための該システムのポートの全体の数を上回り、該サブネットワークの該ポートは仲介回路により情報を記憶および検索するための該システムのポートに連結されている、請求項８のシステム。
【請求項１０】
前記メモリバンクに面している前記サブネットワークの前記ポートの全体の数が、該メモリバンクのポートの全体の数を上回り、該サブネットワークの該ポートは仲介回路により該メモリバンクのポートに連結されている、請求項８のシステム。
【請求項１１】
少なくとも１つの対数関数的マルチステージ・ネットワークがベースライン・ネットワークである、請求項８のシステム。
【請求項１２】
前記メモリ・アドレスのスペースに属しているアドレスを含むメモリバンクの識別が、該アドレスの一群の最小有効数字によって決定される請求項１のシステム。
【請求項１３】
経路が処理の遂行において確立されるサブネットワークの識別が、該処理によって参照されるメモリ・アドレスの一群の最小有効数字によって決定される、請求項８のシステム。
【請求項１４】
ベースライン・ネットワーク内で確立される経路が前記経路によって役に立つ処理によって参照される一部のメモリ・アドレスの一群の最小有効数字によって決定され、該メモリ・アドレスの部分は、該群においてより重要性が低い数字が、情報を記憶および検索するための前記システムのポートに近くの該ベースライン・ネットワークのステージで該経路を決定する際に使用されるように該ベースライン・ネットワークの識別を決定する際に役に立つ数字を除いて該メモリ・アドレスのすべての数字を含む、請求項１１のシステム。
【請求項１５】
前記相互接続ネットワーク内の前記経路が該経路によって役に立つ処理によって参照されるメモリ・アドレスのみに基づいて計算される、請求項１のシステム。
【請求項１６】
前記対数関数的マルチステージ・ネットワークがスイッチを含み、該スイッチは情報を記憶および検索するための前記システムの前記ポートに面してその側でポートを有し、該スイッチはまた他の側で前記他のメモリバンクに面しているポートを有し、そこにおいて、異なる処理の取組みによってリクエストされる異なる経路に位置する前記スイッチのうちの１つのポートで発生する衝突は、該衝突が、該リクエストされた経路へのアクセスを与えられた該スイッチのポートの識別のみに基づき該スイッチで局所的に解決されるように解決され、該システムの該ポートは情報を記憶および検索するため該与えられたポートに面している、請求項８のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマルチコア・コンピュータとしても知られるマルチプロセッサ・コンピュータに関し、特に、何十もの処理コアまたはそれ以上のコアが並行してかつ効率的に共有メモリ内のランダムなアドレスにアクセスするのを可能にする共有メモリ・システムを有するマルチプロセッサ・コンピュータに関するものである。
【背景技術】
【０００２】
用語「処理コア」がマルチプロセッサにおいて含まれる１つのプロセッサを指すような所望の数ｎの処理コアを含むマルチプロセッサにおいて、１以上の共有メモリスペースを用いることは公知である。実際には、これらの共有メモリスペースを構成する１以上の装置を実施する必要性がある。従来技術の図１に示すように、共有メモリスペースを実施する公知の技術は、スペースを所望の数ｋの部分的なバンクで分け、相互接続ネットワークによりｎ処理コアをｋメモリバンクに連結することである。
【０００３】
図１の従来技術の共有メモリ・システムは、相互接続ネットワーク２０と、取り付けられた処理コア２４と一緒に表される一まとまりのメモリバンク２２とを含む。図１においてＰ１、Ｐ２、・・・Ｐｎで表される処理コア２４は、Ｂ１、Ｂ２、・・・Ｂｋで表されるメモリバンク２２に相互接続ネットワーク２０により連結される。これらのバンクによって具体化される個々のメモリスペースの結合は、共有メモリスペースを構成する。
【０００４】
図１に示されている相互接続ネットワークの多くの異なる実施態様は、従来技術において公知である。それにもかかわらず、従来技術によれば、ローカルプライベート・メモリにアクセスする単一の処理コアによって達成される程度に相当するある程度の効率で、何十もの処理コアまたはそれ以上のコアが共有メモリ内で並行してランダムなアドレスにアクセスすることができる共有メモリ・システムを構築することはできないとみなされる。
【０００５】
従来技術の代表的な概要は、１９９６年サンフランシスコ、モーガン・カウフマン出版社のジョン・Ｌ・ヘネシーおよびデイビッド・Ａ・パターソンによる「コンピュータアーキテクチャ‐定量的アプローチ」第二版の６３８ページの記載において見ることができる。
記載は、以下の通りである：「より大きいプロセッサ・カウントをサポートするためには、メモリは集中化されるよりもむしろ、プロセッサの中で分配されなければならない；そうしないと、メモリ・システムは、より大きい数のプロセッサのバンド幅の要求をサポートすることができない」。
【０００６】
従来技術によれば、相互接続ネットワークは、十分高いバンド幅を提供することができず、同時に、ローカル・メモリのそれに相当する効率でランダムなアドレスにアクセスするのに十分低い待ち時間にとどまる難しくかつ扱いにくい装置であると考えられる。この欠点は、マルチコア・コンピュータの同期およびスケジューリング活動が通常共有メモリによって実行されるマルチプロセッサ（「マルチコア」とも呼ばれている）コンピュータ構造の従来技術に関するさらにもう１つの事実に関連する。
【０００７】
したがって、概して処理能力の障害につながる従来技術のマルチプロセッサに特徴的な１つの共通の設計は、共有メモリ・システム上の同期およびスケジューリング活動から生じる多くの負荷を課されている。この活動は、すべてのマルチプロセッサにおいて何らかの方法で実行されなければならない。共有メモリ・システムにより同期およびスケジューリングを実行することにより、負荷を課す他にこのシステムの効率も損なわれてしまう。これは、特に「ホットスポット」として当業者によって公知であることの発達による；この場合、同期およびスケジューリングに関連するものである。また、共有メモリ・システムの複雑化は、Ｔｅｓｔ＆Ｓｅｔ、Ｆｅｔｃｈ＆Ａｄｄまたはその他のような特別な同期基本命令をサポートする要求から起こる。そのような基本命令は概して、互いに分離できず、「原子的な」方法として当業者によって公知であるものにおいて実行される読み込みおよび更新操作を必要とする。
【０００８】
処理能力の障害につながる従来技術のマルチプロセッサに他の設計の特徴は、単純な読み込みおよび書き込みをサポートするよりもむしろ共有メモリ・システムが読み込み‐修正処理をサポートするのを要求していることである。
【０００９】
一般に、同期およびスケジューリング活動が共有メモリによって実行されるように設計される従来技術のマルチコア・コンピュータは、共有メモリにアクセスする効率がローカル・メモリにアクセスする効率に相当するような意図で構築されない。その理由は、そのようなコンピュータが細かい計算型の粒度をサポートすることができないためである。この問題は、次のように言い換えることができる：与えられたアルゴリズムをより細かい粒度レベルに分解することにより、同期速度の要求の増加、および、生産的な計算に対する総活動のより大きい比率が生じる。
【００１０】
マルチコア・コンピュータが初めから限定された粒度のレベルで並列した計算の実行が意図される場合、この制限は概して、処理コアがそれ自身のローカル・メモリに逆らって主に作用するような方法でコンピュータを構成することにつながる。
【００１１】
したがって、従来技術（前述のヘネシーおよびパターソン参照）によれば、ローカルプライベート・メモリにアクセスする単一の処理コアによって達成される程度に相当するある程度の効率で、何十もの処理コアまたはそれ以上のコアが共有メモリ内で並行してランダムなアドレスにアクセスすることができる共有メモリ・システムを構築することはできないとみなされる。
【００１２】
同期およびスケジューリング活動と関連する問題を解決する従来技術での試みは、引用された特許の共同発明者でもあった本発明の共同発明者の１人へ付与された米国特許第５，２０２，９８７号に記載されていた。その特許は、同期およびスケジューリングのための専用の装置を備えているマルチコア・コンピュータ設計を記載している。ローカル・メモリのそれに相当する効率を有するアクセスを可能にする共有メモリ・システムを構築する必要性は、米国特許第５，２０２，９８７号に記載された装置に関して起こる。
【００１３】
米国特許第５，２０２，９８７号の公表の前に、マルチコア・コンピュータのローカル・メモリのそれに相当する効率を有するアクセスを可能にする共有メモリ・システムを提供する実現可能性および必要性の両方は、まだ確立されていなかった。それゆえに、参照としてここに組み込まれる本発明の共同発明者の１人であるバイエルその他への米国特許第５，２０２，９８７号において開示される発明と連動して本発明を実施することによりそのような効率を可能にする共有メモリ・システムを提供することは望ましい。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】米国特許第５，２０２，９８７号公報
【非特許文献】
【００１５】
【非特許文献１】１９９６年サンフランシスコ、モーガン・カウフマン出版社  ジョン・Ｌ・ヘネシーおよびデイビッド・Ａ・パターソンによる「コンピュータアーキテクチャ‐定量的アプローチ」第二版の６３８ページ
【発明の概要】
【発明が解決しようとする課題】
【００１６】
したがって、本発明の主要な目的は、従来技術のシステムの設計の不都合および障害を克服し、当業者に公知であるように以下にマルチコア・コンピュータと呼ばれるマルチプロセッサ・コンピュータにおいて共有メモリ・システムまたはいくつかのそのようなシステムを提供することである。共有メモリ・システムは、相互接続ネットワークと一まとまりのメモリバンクＢ１、Ｂ２、・・・Ｂｋとを含む。このシステムは、並行して共有メモリへの参照を始める一まとまりの処理コアＰ１、Ｐ２、・・・Ｐｎに役立つ。
【００１７】
本発明は、ローカルプライベート・メモリを参照する場合に達成される典型的効率に相当する効率で共有メモリスペースのランダムなアドレスを参照する能力により、処理コアを供給する相互接続ネットワークを利用して共有メモリ・システムをマルチコア・コンピュータに提供する。複数のそのようなメモリスペースは、本発明を複数回適用することによって同じマルチコア・コンピュータ内で実施することができる。所望の能力は、メモリ・システム、および、マルチコア・コンピュータ全体の特色または特徴の組合せのおかげで達成される。
【００１８】
プライベート・メモリのそれに相当する効率でアクセスすることができる本発明の共有メモリ・システムを構成するため、従来技術に存在する様々な障害を克服する必要性および実現可能性の両方は、高フローレートのシンクロナイザ／スケジューラを備えたマルチコア・コンピュータにおいて生じる。そのようなコンピュータは、大規模に並列かつ細かい粒の計算の効率的サポートを意図される。それは、共有メモリを経た、および、シンクロナイザ／スケジューラを経た処理コア間の高密度かつ強力な協働を可能にするという意味において、しっかりと連結されたと言うことができる。
【００１９】
本発明の共有メモリ・システムに含まれる相互接続ネットワークは、読み込みの役に立つネットワークから、書き込みの役に立つ分離したネットワークと同様に構成される。しかしながら、メモリ・システムが読み込み操作のみを意図する場合、後者は省かれる。読み込みネットワークおよび書き込みネットワークは、互いに平行して連結される。読み込みネットワークおよび書き込みネットワークのトポロジは、平行に連結される複数の対数関数的マルチステージ・ネットワークに基づく。
【００２０】
ここでさらに記載されるように、対数関数的マルチステージ・ネットワークの１つの実行可能なタイプは、ベースライン・ネットワークである。対数関数的マルチステージ・ネットワークにおいて含まれるスイッチに加えて、内部連絡ネットワークは、ルーティング、連結または橋絡の役に立つ他の基本的な要素を含む。そのような要素の１つの使用法は、メモリバンクに面している側での読み込みまたは書き込みネットワークのポート数の減少である；そのような減少は、（読み込みまたは書き込みネットワークに含まれる）対数関数的マルチステージ・ネットワークの全体的なポート数よりもメモリバンクの数がより少ない場合、および、その場合のみに実行される。
【００２１】
本発明の共有メモリ・システムは、すべてのクロックサイクルで新たになる処理コアとメモリバンクとの間の経路を計算する。それは、すべての処理コアに、そのメモリにアクセスする取組みが経路の配分につながって達成されるような承認応答と、その主導権が成し遂げられないすべてのコアへの拒絶応答とを返す。拒絶応答を受信する処理コアは、後のクロックサイクルでその取組みを再提出する。経路の計算は、提出されたメモリ・アドレスのみに基づく単純な方法で実行される。この計算において、拒絶につながる競合の検出以外、異なる取組みの間に相互作用はない。経路の再配置は存在しない。
【００２２】
相互接続ネットワークは、‐おそらくパイプライン・レジスタを除いては、いかなる内部バッファリングまたは情報記憶も実行しない。これらのレジスタは、最高でも以下の３つのパイプライン段階を生成するために役に立つ：（ａ）経路の定義、および、処理コアからメモリバンクへの伝達、（ｂ）メモリバンク内部の固有の活動、および、（ｃ）メモリバンクから処理コアへの伝達。承認および拒絶応答の送達は、これらの段階のいずれかに割り当てることができる。段階（ａ）および（ｂ）、または（ｂ）および（ｃ）、または、３つの段階（ａ）（ｂ）および（ｃ）のすべては、統一することができる。後者の場合、パイプラインでの転送は全体で廃止され、それにより相互接続ネットワークが単に組合せのシステムにされる。２つまたは３つのパイプライン段階がある他の場合には、パイプライン・レジスタがネットワークを多少の片の組合せに分けるので、相互接続ネットワークは本質的にまだ組合せのままである。
【００２３】
読み込みネットワークは、同じクロックサイクルで複数の処理コアによってリクエストされるメモリ内容のマルチキャストをサポートする。
【００２４】
メモリ・システムは、３つの異なるインターリービング効果を利用することによってバンド幅を増やすためにメモリ参照のローカリティの現象を活用する。第１のインターリービング効果は、メモリバンクのインデックス、および、そのバンク内の内部アドレスへのメモリ・アドレスの分解に関連する。第２のインターリービング効果は、横断する対数関数的マルチステージ・ネットワークの選択に関連する。第３のインターリービング効果は、これがベースライン・ネットワークである場合の対数関数的マルチステージ・ネットワークの中での内部経路の定義に関連する。
【００２５】
パイプライン段階の数に次第で、処理コアは、同じクロックサイクル、または次のクロックサイクル、またはその次のクロックサイクルでそれらのメモリ・アクセスの取組みの結果を受信する。
【００２６】
先に記載したように、本発明の特徴は、相互接続ネットワークがパイプラインでの転送に関した限定されたバッファリング以外の内部バッファリングまたは情報の記憶を実行しないということである。それゆえに、この相互接続ネットワークは、デジタルシステムの基本的理論において公知である「組合せのシステム」の概念に本質的に対応する。これは、相互接続ネットワークを単純に、効率的におよび軽量にするのに貢献する。
【００２７】
さらに以下に記載するように、パイプラインでの転送が加えられる本発明の好ましい実施態様のみで「メモリ・システムのタイミング制度」と名付けられる部分において、相互接続ネットワークは、もはや単に組合せのシステムでなく；その基本的な性質を通して、パイプラインでの転送が加えられない好ましい実施態様と関連して変化しない。
【００２８】
他の本発明の特徴は、処理コアとメモリバンクとの間で形成される経路を計算する単純性である。
【００２９】
他の本発明の特徴は、相互接続ネットワークが同期基本命令をサポートせず、単純な読み込みおよび単純な書き込み操作のみに基づくメモリ・アクセスをサポートするように設計されることである。
【００３０】
他の本発明の特徴は、相互接続ネットワークが１以上の対数関数的マルチステージ・ネットワークを含み、処理コアとメモリバンクとの間の所望の数の経路を提供するように正確な量が選択されることである。
【００３１】
他の本発明の特徴は、処理コアとメモリバンクとの間の経路が長くないという事実において表され、それらの関連した遅延は長くない。上記したように、相互接続ネットワークが本質的に組合せのシステムであるので、いかなる組合せのシステムの機能を安定させる遅延について論じるように、同じ意味においてこれらの遅れについて論じることができる。
【００３２】
他の本発明の特徴は、メモリからの読み込みに役立つ装置とメモリへの書き込みに役立つ装置との間の分離である。この分離は、これらの２つの専用の装置をより効率的かつ単純にするのを促進し、それらは並行して操作することができる。
【００３３】
他の本発明の特徴は、読み込みに関連した「メモリ・ホットスポット」として従来技術において周知のものを効率的に収容するための発明の共有メモリ・システム設計の能力である。これを達成するため、メモリから読み込み操作を可能にする装置は、マルチキャストをサポートする。
【００３４】
読み込みに関連したホットスポットに加えて、２つの他の種類のホットスポットが存在する：１）同期およびスケジューリングに関連したホットスポット。共有メモリ・システムは、マルチコア・コンピュータが専用の高フローレートのシンクロナイザ／スケジューラを備えている場合、これらのホットスポットを収容する負荷が軽減される；および、２）読み込みに関するものとは別であり、同期／スケジューリングに関連しない主に書き込みに関するホットスポット。これらのホットスポットは、広範囲にわたらない。
【００３５】
本発明のフレームワークに記載されるメモリ・システムは、単純、効率的かつ軽量の相互接続ネットワークに基づく。ネットワークの遅延は小さく、それが提供する経路の数は適切である。
【００３６】
このメモリ・システムは、２次元技術（そのような技術に限定されないが）を用いた生産に適している。したがって、シリコン基板上に本発明を適用するマルチコア・コンピュータを製造することができる。さらに、２次元技術を用いて製造されるマルチコア・コンピュータは、本発明によって構築される複数の共有メモリ・システムを含む。特に、それは、命令を保つのに役立つ他の共有メモリ・システムと同様にデータを保つのに役立つ共有メモリ・システムを含む。
【００３７】
単離された処理コアがローカルプライベート・メモリにアクセスする場合に達成される効率の程度に相当するある程度の効率で共有メモリスペースにアクセスする処理コアの能力は、しっかりと互いに協同するコアの能力の１つの成分である。この同じ能力の相補的成分は、処理コアによって実行され、先に参照された米国特許第５，２０２，９８７号に記載されるようにマルチコア・コンピュータが高フローレートのシンクロナイザ／スケジューラを備える場合に達成される並列作業の効果的な管理である。両方の成分が達成される場合、処理コアは互いにしっかりと協同する能力を与えられ、これにより、マルチコア・コンピュータが効率的に細かい粒度の並列処理を収容することができるようになる。それで、マルチコア・コンピュータ（または同義的にマルチプロセッサ）はしっかりと連結すると言うことができる。
【００３８】
上に記載され、詳述された特徴、特性、特色および原理の完全性のために、本発明によって構築される共有メモリ・システムは、上記に定義された意味においてしっかりと連結したマルチコア・コンピュータにおいて役立つために適切である。これにおいて、本発明は、従来技術によって満たされなかった必要性を満たす。
【００３９】
本発明の追加の特徴および効果は、以下の図面および説明から明らかになる。
【図面の簡単な説明】
【００４０】
その実施態様に関して本発明のより良い理解のため、類似した数字が全体にわたって対応する要素または部分を指す添付の図面をここで参照する。そこで：
【図１】図１は、相互接続ネットワークとメモリバンクとを含み、複数の処理コアに連結される従来技術の共有メモリ・システムの一般化された例を示す；
【図２】図２は、共有メモリ・システムのための相互接続ネットワークを形成し、本発明の原理により構成されかつ操作される読み込みネットワークおよび書き込みネットワークの概略線図を示す；
【図３】図３は、本発明の原理により両側で８つのポートを有するベースライン・ネットワークとして構成される相互接続ネットワークの公知のタイプのトポロジを示す；
【図４】図４は、対数関数的マルチステージ・ネットワークに基づいた読み込みネットワークおよび書き込みネットワークの共通のトポロジの例を示す；
【図５】図５は、相互接続ネットワークへの入力である集計された変数と、これらの変数の関数として計算される集計された値とを示し、そこにおいて、ネットワークは、本発明の好ましい実施態様による組合せのシステムの概念に対応する；
【図６】図６は、変数を生じ、これらの変数の関数として計算された値を使用する処理コアおよびメモリバンクと共に図５の組合せの相互接続ネットワークを示す；
【図７】図７は、図５の組合せの相互接続ネットワークを示すが、組合せのシステム全体が組合せのサブブロックへ分解されたものである；
【図８】図８は、パイプライン・レジスタを加えることによってパイプラインでの転送に基づく本発明の好ましい実施態様がどのように得られるかについて示す；
【図９】図９は、パイプラインでの転送に基づいた他の好ましい実施態様を示す；
【図１０】図１０は、パイプラインでの転送に基づいたさらに他の好ましい実施態様を示す；
【図１１】図１１は、処理コア発行のメモリ・アドレスのバイナリ表現を示す；
【図１２】図１２は、メモリ・アドレスの内容のマルチキャストがある場合、読み込みネットワーク内で形成されるツリートポロジのマルチ経路の例を示す；
【発明を実施するための形態】
【００４１】
以下の説明では、本発明の原則によりしっかりと連結されたマルチプロセッサのための共有メモリ・システムの好ましい実施態様を示すため、最初に、相互接続ネットワークのトポロジが記載される。その後で、メモリ・システムのタイミング制度が記載される。それから、処理コアとメモリバンクとの間で形成される経路が記載される。
【００４２】
相互接続ネットワークのトポロジ
図１は、相互接続ネットワークとメモリバンクとを含み、複数の処理コアに連結される従来技術の共有メモリ・システムの一般化された例を示す。
【００４３】
以前の「発明の背景」において記載されたように、図１の相互接続ネットワーク２０は、十分高いバンド幅を提供することができず、同時に、ローカル・メモリのそれに相当する効率でランダムなアドレスにアクセスするのに十分低い待ち時間にとどまる難しくかつ扱いにくい装置であると考えられる。
【００４４】
当業者に公知であるように関連した技術において、与えられた一連の構成要素からシステムを構成するコンテキスト内で言及される場合、用語「トポロジ」は、これらの構成要素間の一連の静的連結を指す。直接の、固定した、物理的な連結によってそれに取り付けられる他の構成要素である各々の構成要素のために、トポロジが決定する。トポロジはまた、連結に役立つ構成要素のポートを決定する。相互接続ネットワークを処理する場合、関連した一組の構成要素は、ネットワーク自体の基本的な基礎単位、すなわち、スイッチと、ネットワークの外部ポートに取り付けられる要素と同様にルーティング、連結または橋絡の役に立つ他の基本的な要素とを含む。図１（従来技術）で示されるコンテキストにおいて、これらの外部の要素はネットワークの片側で連結される処理コア２４（Ｐ１、Ｐ２・・・Ｐｎで分類された）、および、反対側で連結されるメモリバンク２２（Ｂ１、Ｂ２・・・Ｂｋで分類された）である。
【００４５】
図２は、共有メモリ・システムのための相互接続ネットワークを形成し、本発明の原理により構成されかつ操作される読み込みネットワークおよび書き込みネットワークの概略線図を示す。
【００４６】
相互接続ネットワーク２０の総合的なトポロジの表現は、２つのレベルを有し、階層的である。第１のレベルで、図２に示すように、相互接続ネットワーク２０は、本発明の実施態様において、２つのより小さいサブネットワーク：メモリからの読み込みの役に立つ読み込みネットワーク３０と、並列に連結されるメモリへの書き込みの役に立つ書き込みネットワーク３２とから構成されて示される。
【００４７】
以下に、階層的な表現の第２のレベルで、そのトポロジが当業者によって公知であるもっとより小さいサブネットワークからこれらの２つのサブネットワークの各々が構成される方法が記載される。
【００４８】
読み込みネットワークおよび書き込みネットワークからの相互接続ネットワークの構造
ここで詳細に図２を参照すると、相互接続ネットワーク２０は外側のボックスによって表され、従来技術のように図１の「相互接続ネットワーク」ボックス（２０）に対応する。図２はまた総合的なネットワークの外側ポート２６、２８を示し、図２の上部で記載されるポート２６は処理コア２４に連結されるように意図され、下部で記載されるポート２８はメモリバンク２２に連結されるように意図される。２つの内側のボックス３０、３２は、読み込みネットワーク３０、および、書き込みネットワーク３２をそれぞれ表す。読み込みネットワーク３０はメモリから読み込み操作の役に立ち、書き込みネットワーク３２はメモリに書く操作の役に立つ。読み込みネットワーク３０のポート２６と書き込みネットワーク３２のそれとの間の交差する点の黒い四角形は、ルーティング、連結または橋絡する要素３４を表す。これらの要素３４は、必要である場合、相互接続ネットワークの基本的な基礎単位の１つである。
【００４９】
上記のように並列に連結される分離した読み込みおよび書き込みネットワーク３０、３２からの相互接続ネットワーク２０の構造は、以下の利点を有する：総合的な相互接続ネットワーク２０が提供することができる処理コア２４とメモリバンク２２との間の経路の数は、読み込み操作と書き込み操作との両方を行う単一のネットワークと比較して増加する。他方で、一方向へデータを移すことのみを意図されることによって、２つのサブネットワークの各々は、両方向にデータを移す代替の単一のネットワークよりも単純かつ効率的であるので、２つのサブネットワークを実施するために必要であるリソースの全体的な量は、同じ割合で増加しない。
【００５０】
時に、読み込みの用途にだけ役に立つ共有メモリ・システムを構築することが必要とされる。例えば、命令をデータから切り離すハーバード・アーキテクチャとして当業者によって公知のものに基づきコンピュータに命令メモリを構築する場合にこれは生じる。そのような場合、相互接続ネットワーク２０は、読み込みネットワーク３０のみを含み、書き込みネットワーク３２を含まない。
【００５１】
読み込みネットワークおよび書き込みネットワークのトポロジ
本発明の原則によると、相互接続ネットワーク２０のトポロジの階層的な表現の第２のレベルが存在する。読み込みネットワーク３０および書き込みネットワーク３２は、もっとより小さいサブネットワークから構成される（そのトポロジは当業者によって公知である）。読み込みネットワーク３０および書き込みネットワーク３２の識別は、以下に説明されるように経路の形成だけに関係する。トポロジに関する限り、読み込みネットワーク３０および書き込みネットワーク３２の識別はないが、これは、２つのネットワークが同一でなければならないことを意味しない：いくつかのパラメータおよび選択肢は、後述するように異なって設定することができる。
【００５２】
読み込みネットワーク３０および書き込みネットワーク３２の共通のトポロジは、並列にサブネットワークの所望の数ｍを連結することに基づく。数ｍは、後に「重複要素」と呼ばれる。サブネットワークは、「対数関数的マルチステージ・ネットワーク」（図４参照）として当業者に公知のタイプであり、各々の２つの側でそれらが所有するポートの数は、処理コアの数のｎである。
【００５３】
好ましい実施態様において、これらの対数関数的マルチステージ・ネットワークは、均一のスイッチから構成される。そのようなネットワークの片側から反対側へのすべての経路は、ｎの基数ｂによる対数に等しい一連の長さのスイッチを通過し、そこで、ｂはスイッチの各々の２つの側のポートの数である。当業者によって公知である対数関数的マルチステージ・ネットワークの２つの例は、オメガ・ネットワークおよびベースライン・ネットワークである。
【００５４】
ベースライン・ネットワークは、従来技術で認識される一般化した概念である。各々の側のポートの数がまた与えられるスイッチで構成される各々の側において与えられたポートの数でベースライン・ネットワークを構成する方法は、当業者にとって公知である。各々の側でｎ＝  ８のポートを所有し、各々の側でｂ＝２ポートを有するスイッチから構成されるベースライン・ネットワークのトポロジは図３に示される。
【００５５】
図３において、８つのポート４２を有するベースライン・ネットワーク４０のトポロジは、各々の側４８でそれぞれ２つのポート４７を有するスイッチ４６から構成される各々の側４３、４４で示される。ネットワークの片側４３のポートはＩｎ＿０からＩｎ＿７まで分類され、向かい側４４のそれらはＯｕｔ＿０からＯｕｔ＿７まで分類される。数０から７は、インデックスとしてここで役に立つ。ネットワークはその基本的ビルディングブロックを構成する３列のスイッチ４６を含む。ネットワークの向かい側でＩｎ＿０からＩｎ＿７まで分類された外部ポートの１つからＯｕｔ＿０からＯｕｔ＿７まで分類された外部ポート１つまでのすべての経路は、各々のこれらの３列に帰属している唯一の一つのスイッチ４６を経て通過する。
【００５６】
従来技術で一般的な用語によれば、３つの列は、ネットワークの３つのステージと呼ばれる。以下の規則が、この図において採用される：処理コア２４で起こった取組みが入るポートは用語「Ｉｎ」を含む名前によって分類され、一方で、これらの取組みがメモリバンク２２の方への途中に出るポートは用語「Ｏｕｔ」を含む名前によって分類される；これは、ネットワーク自体のポート、および、そのビルディングブロックのポートも同様に適用される。コアの取組みに対する反応は、その名前が概して入力および出力信号を含む用語「Ｉｎ」または「Ｏｕｔ」を含むかどうかに関わらず、対向する方向において、したがって、各々のポートを通じて移動する。
【００５７】
一般に、ベースライン・ネットワークが物理的に幾何学的に、図３に対応する方法で２次元表面上へ伸びる場合、以下のことが有効である：ベースライン・ネットワークが長方形で拘束される場合、ベースライン・ネットワークの片側のポートから向こう側のポートへのいかなる経路の最大限の幾何学的な全長は、囲んでいる長方形の対角線の長さを上回らない。これは、ベースライン・ネットワークの有用な特性である。
【００５８】
先に記載されたように、読み込みネットワーク３０および書き込みネットワーク３２（図２参照）の共通のトポロジは、各々の側でｎポートを所有している各々のこれらのｍネットワークでのｍ対数関数的マルチステージ・ネットワークの並列な連結に基づく。ここでおよび以下に「重複要素」として呼ばれるパラメータｍは、１以上である（ｍ≧１）目標値を呈し、ｎは処理コア２４（図２参照）の数である。
【００５９】
図４は、対数関数的マルチステージ・ネットワークに基づいた読み込みネットワークおよび書き込みネットワークの共通のトポロジの例を示す。
【００６０】
図４を参照すると、この例では、処理コア２４（図２参照）の数ｎは８であり、メモリバンク２２（図２参照）の数ｋは１６である。したがって、対数関数的なマルチステージ・ネットワーク５４は、片側５０（処理コア２４に面している側）で０から７までインデックスを付けられる８つのポートを所有し、向こう側５２（メモリバンク２２に面している側で）０から１５までインデックスを付けられる１６のポートを所有する。４つの対数関数的マルチステージ・ネットワーク５４は、この例で並列に連結される、すなわち、重複要素ｍは４である。４つの対数関数的マルチステージ・ネットワーク５４すべては、各々の側でｎポートを有する。図の下部と同様に図の上部の黒い四角形は、相互接続ネットワークの基本的なビルディングブロックの１つであるルーティング、連結または橋絡要素３４ａを表す。
【００６１】
０からｎ‐１へのインデックスを有し、図４の上部で記載されたもののネットワークのすべての外部ポートは、ルーティング、連結または橋絡要素３４ａにより、存在する場合、対数関数的マルチステージ・ネットワーク５４のそれぞれの対応するポート（同じインデックスを有する）に連結される。また、０からｋ‐１へのインデックスを有し、図の下部で記載されたもののネットワークのすべての外部ポートは、対数関数的マルチステージ・ネットワーク５４の連続したインデックスを有し、要素３４ａから（ｍ×ｎ）／ｋポートに連結される；この例では、図４の下部で記載される１６の外部ポートのそれぞれは、対数関数的マルチステージ・ネットワーク５４の連続したインデックスを有する２つのポートに連結される。
【００６２】
ｎ＝８処理コアの図４において例証されるトポロジで、ｋ＝１６のメモリバンク、および、重複要素ｍ＝４は、パラメータの値が異なる場合に適用する一般的な概念として明白である。対数関数的マルチステージ・ネットワークのタイプもまた、異なってもよい。さらにトポロジをふさわしくするため、ｎおよびｍの積はｋに等しいまたはｋより大きい必要がある、すなわち、一般的な数学的表記法ではｋ≦ｎ×ｍである。本発明の好ましい実施態様をまた表すパラメータの可能な一連の値の１つの他の例は、以下の通りである：処理コアの数ｎは２５６であり、重複要素ｍの値は８であり、メモリバンクの数ｋは５１２である。
【００６３】
トポロジを明確にするため、対数関数的マルチステージ・ネットワークのポートの指数化が明確である必要がある。この指数化は確かに定められ、当業者によって公知であるオメガ・ネットワークおよびベースライン・ネットワークの記載に適する。
【００６４】
すべての処理コア２４（図２参照）が同時にメモリバンク２２（図２参照）にアクセスすることを可能にするため、本発明の実施態様では、メモリバンク２２の数ｋが処理コア２４の数ｎより小さくない、すなわちｎ≦ｋである必要がある。
【００６５】
好ましい実施態様のある種類において、処理コア２４の数ｎ、メモリバンク２２、および、重複要素ｍの数ｋは、すべて２のべき乗である。
【００６６】
他の種類の好ましい実施態様は、ｎより少ない処理コア２４（図２参照）を実際にメモリ・システムに連結することにより、そのサイズがすべて２のべき乗ではない一まとまりの処理コア２４を残し、一方でメモリバンク２２（図２参照）の数ｋおよび重複要素ｍの最初の値を保持して、前のクラスから得られる。処理コア２４の数のこの減少は、同様に相互接続ネットワーク２０（図２参照）の限定された減少を可能にする。しかしながら、メモリバンク２２に近い側において各々の対数関数的マルチステージ・ネットワーク５４のポートの数が最初の数ｎのままであるので、メモリ・システムおよびそのパラメータは基本的な変化を受けない。
【００６７】
重複要素ｍのより大きな値を有する利点は、処理コア２４とメモリバンク２２との間の経路の数もまた増加することである。
【００６８】
読み込みネットワーク３０と書き込みネットワーク３２（図２参照）との間の重複要素ｍの値が異なるにも関わらず、同一の値を選ぶことは以下の利点を有する：相互接続ネットワーク２０の物理的な幾何学的な実施態様において、読み込みネットワーク３０および書き込みネットワーク３２は、スイッチ４６（図３参照）のようなすべてのビルディングブロック、および、書き込みネットワーク３２の対応したビルディングブロックまたは連結の次に配置される読み込みネットワーク３０内部のすべての連結で互いに並列して置くことができる。そのようなレイアウトは、設計するのにより単純であるのと同様に、より領域が効率的でありかつ配線が効率的である。
【００６９】
メモリ・システムのタイミング制度
クロックサイクル
ここで示されるメモリ・システムは、「クロックサイクル」として当業者によって公知の間隔またはスライスへの時間の分割に基づく。与えられたメモリ・システムのコンテキストの範囲内での時間の同じ共通の分割はメモリ・システム内のいかなる時限式のリソースとも同じく、メモリ・システムに連結されるすべての処理コア２４（図２参照）に適用する。
【００７０】
すべての処理コア２４は、すべてのクロックサイクルで、与えられたメモリ・システムによって具体化されるメモリスペースに属する、メモリ・アドレスへのアクセスを始めるのに好適である。処理コア２４による取組みは、相互接続ネットワーク２０を経た処理コア２４とメモリバンク２２との間の経路を定める工程につながる。この経路定義工程は、すべてのクロックサイクルで新たに、一度実行される。したがって定められる経路は部分的ではなく、処理コア２４において開始し、相互接続ネットワーク２０を移動し、メモリバンク２２で終了するむしろ完全な経路である。
【００７１】
処理コアの取組みの承認および拒絶
一般に、スイッチのポートと相互接続ネットワークの他の基本的な要素とのコンテストの競合の結果として、メモリ・システムは、与えられたクロックサイクルでの処理コアにより提出されたすべての取組みを果たすことができない。本発明によると、その取組みが確かに果たされる処理コア２４（図２参照）は承認応答を受信し、一方で取組みが果たされない処理コア２４は拒絶応答を受信する。拒絶応答を受信する処理コア２４は、後のクロックサイクルでのその取組みの提出を概して再び試みる。再提出は、あたかもそれが全く起こらなかったかのように最初の提出と同じ方法で実行される。
【００７２】
メモリ・アクセスのパイプライン・ステージ
多数の処理コアによりメモリへの同時のアクセスを達成するために行われる活動は、ＡからＧに分類された以下の活動要素を含む：
要素Ａ：処理コアの取組みの提出；
要素Ｂ：データ、アドレスおよび制御を示している内容を運ぶ相互接続ネットワークにおける処理コアとメモリバンクとの間の経路の定義；
要素Ｃ：承認および拒絶応答のメモリ・アクセスを開始するそれらの処理コアへの転送；
要素Ｄ：読み込みの取組みに準じたメモリバンクからの読み込み；
要素Ｅ：読み込みを始めた処理コアへのメモリバンクから読み込まれた内容の転送；
要素Ｆ：書き込み操作を始めたそれらの処理コアからの書き込みが起こるべきであるメモリバンクへの内容の転送；
要素Ｇ：書き込みの取組みに準じたメモリバンクへの書き込み。
【００７３】
本発明の好ましい一実施態様によると、同じ一連の取組みから生じるすべての活動要素は、１つのクロックサイクルで実行される；言い換えると、活動要素Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、および、Ｇは、それらが生じる要素Ａと同じクロックサイクルで実行される。
【００７４】
第２の好ましい実施態様によると、活動要素Ｂ、Ｃ、Ｄ、Ｆ、および、Ｇは、それらが生じる要素Ａと同じクロックサイクルで実行される；しかしながら、新しい一連の取組みがすでに提出される続く周期で、要素Ｅは、実行される。この第２の好ましい実施態様は、「パイプライン」として当業者によって公知であるものに基づく。パイプラインで転送する利点は、クロックサイクルの継続期間の潜在的な短縮である。パイプライン・ステージの数は、以下の線図にて図示したように、この第２の本発明の好ましい実施態様において２である：
2011503710.tif 000003
【００７５】
第３の本発明の好ましい実施態様によると、活動要素Ｂ、Ｄ、Ｆ、および、Ｇは、それらが生じる要素Ａと同じクロックサイクルで実行される；しかしながら、２つの要素ＣおよびＥは、続いて起こるクロックサイクルで実行される。
【００７６】
先に記載された第２の好ましい実施態様のように、第３の好ましい実施態様もまた２つのパイプライン・ステージに基づき、その違いはパイプライン・ステージ間の活動の割当てである。これは、第３の好ましい実施態様に関係する以下の線図を用いて明確にされる：
2011503710.tif 000004
【００７７】
第４の本発明の好ましい実施態様によると、活動要素Ｂ、ＣおよびＦは、それらが生じる要素Ａと同じクロックサイクルで実行される；２つの要素ＤおよびＧは、続いて起こるサイクルで実行され、最後の要素Ｅは、１つ後のサイクルで実行された。以下の線図は、第４の好ましい実施態様の３つのパイプライン・ステージを示す：
2011503710.tif 000005
【００７８】
本発明の様々な好ましい実施態様が異なるパイプライン構成を特徴とすることは、上記の説明から明確である。これらの構成において、以下のものが含まれる：すべての活動が同じクロックサイクルで実行される上記した第１の好ましい実施態様がそれに基づき、実際、パイプラインが全くないもの；上の第２および第３の好ましい実施態様がそれに基づく２つのパイプライン・ステージを有する構成；および、上の第４の好ましい実施態様がそれに基づく３つのパイプライン・ステージを有する構成。活動要素ＡからＧがパイプライン・ステージの中で異なって割り当てられた追加のパイプライン構成が、本発明の追加の好ましい実施態様を生じさせる。
【００７９】
徹底的にこれを明らかにするため、以下の説明は、次の３つの一般的なステージ（ａ）、（ｂ）および（ｃ）を含む様々なパイプライン構成が共通の体系から引き出される方法を示す：（ａ）  処理コアからメモリバンクへの伝達のステージ；（ｂ）  メモリバンク内部の固有の活動のステージ；および（ｃ）メモリバンクから処理コアへの伝達のステージ。
【００８０】
異なるパイプライン構成は、３つのステージ（ａ）、（ｂ）および（ｃ）を共通の要素をもたないステージとして構成すること；または、全体で２つのステージが残るように（ａ）および（ｂ）を１つのステージに統一すること；または、ここでも全体で２つのステージが残るように（ｂ）および（ｃ）を１つのステージに統一すること；または、実際、パイプラインが残らないように３つのステージ（ａ）、（ｂ）および（ｃ）を１つのステージに統一すること；に依存する。この体系によると、活動要素Ａ、Ｂ、および、Ｆは常にステージ（ａ）に属する。要素ＤおよびＧは、常にステージ（ｂ）に属する。要素Ｅは、常にステージ（ｃ）に属する。最終的に、活動要素Ｃは、この体系によると３つのステージ（ａ）、（ｂ）および（ｃ）のいずれかに属する。
【００８１】
先に記載された本発明の好ましい実施態様とこの体系との間の関係を示すため、第２および第３の好ましい実施態様の説明がステージ（ａ）および（ｂ）を１つのステージに統一することに基づくことが指摘される。これらの２つの実施態様は、しかしながら活動要素Ｃが実行されるステージにおいて異なる：第２の好ましい実施態様においてそれはステージ（ａ）または（ｂ）であり、一方で、第３の好ましい実施態様においてそれはステージ（ｃ）である。
【００８２】
相互接続ネットワークの組合せの性質
相互接続ネットワーク２０（図２参照）は、入力変数としてメモリバンク２２によって生成される処理コア２４プラス信号の取組みを受け入れる。これらの変数から、相互接続ネットワーク２０は以下の関数ｆ１からｆ６を計算する：
ｆ１：処理コア２４とメモリバンク２２との間で定められるべきであり、相互接続ネットワーク２０が構築される基本的な要素の切換状態において表される経路；
ｆ２：様々なメモリバンク２２のポートに現れるべきであり、処理コア２４の書き込みの取組みから生じるデータ内容；
ｆ３：メモリバンク２２のアドレス・ポートに現れるべきである内部のアドレス；
ｆ４：それらに読み込み操作あるいは書込み操作を実行するように指示するため、メモリバンク２２の制御ラインに現れるべきである制御値；
ｆ５：処理コア２４の取組みに対する承認および拒絶応答；
および、ｆ６：これらの処理コア２４の読み込みの取組みに応答して、メモリバンク２２によって不要にされた様々な処理コア２４のポートに現れるべきであるデータ内容。
【００８３】
パイプラインでの転送に基づいていない本発明の好ましい実施態様において、上のｆ１からｆ６の関数の計算は、直前のクロックサイクルの相互接続ネットワーク２０（図２参照）の状態に依存しない。それゆえにそのような好ましい実施態様において、相互接続ネットワーク２０は、デジタルシステムの基本的な理論において公知である「組合せのシステム」の概念に対応する。
【００８４】
図５は、相互接続ネットワークに入力される集計された変数と、これらの変数の関数として相互接続によって計算される集計された値とを示し、そこにおいて、ネットワークは、パイプラインでの転送に基づいていない本発明の好ましい実施態様による組合せのシステムの概念に対応する。
【００８５】
ここで図５を参照すると、組合せの相互接続ネットワーク２０ａは、入力５８を受信し、出力６０を生成する単一のブロックとして表される。システムが安定するために十分な時間を動かされたと仮定するならば、ｆ１からｆ６によって示される出力６０は、入力５８の現在の値の関数、すなわち変数Ｘ１およびＸ２である。
【００８６】
図６は、情報の集合であり、それらの関数ｆ１からｆ６を使用する変数Ｘ１およびＸ２の値を生じる一まとまり６２の処理コア２４と一まとまり６４のメモリバンク２２とを有する、図５に記載の組合せの相互接続ネットワーク２０ａを一緒に表す。その意味が上で定められたｆ１からｆ６の値もまた、情報の集合である。変数Ｘ１は一まとまり６２の処理コア２４の取組みを構成し、変数Ｘ２は一まとまり６４のメモリバンク２２によって生成される信号を構成する。図６は、相互接続ネットワークそれ自体によってそれが内部で使われるのでｆ１を表さないことに留意するべきである。
【００８７】
組合せのシステムであることにより、組合せの相互接続ネットワーク２０ａを単純で、効率的かつ軽量にすることに貢献する。それはまた、この発明のネットワークを、データ、アドレス、および、制御値がそれらの処理コアからそれらのメモリバンクまたは後方へ複数のクロックサイクルの間続く行程を作成するように配置される従来技術の相互接続ネットワークと基本的に異なるようにする。
【００８８】
そのような他のネットワークにおいて、割り当てられた部分的なまたは完全な経路と同様に、これらのデータ、アドレス、および、制御値は、１つのクロックサイクルから次のサイクルまで記憶されていなければならない複雑な状態の一部である。概して、これは、バッファメモリの追加、および、複雑な制御メカニズムにつながる。
【００８９】
そのような他のネットワークとは対照的に、本発明のフレームワークに示される軽量の組合せの相互接続ネットワーク２０ａは、「キャリールックアヘッド」加算器として当業者によって公知であるものに類似して考えることができる：両方とも、信号伝播遅延が対数的に変数の数次第である組合せのシステムである。キャリールックアヘッド加算器は、非常にコンパクトかつ速いシステムと考えられる。
【００９０】
図６に示される本発明の組合せの相互接続ネットワーク２０ａの単純性およびコンパクトさは、すべてのメモリ・アクセスの実行が単一のクロックサイクル内で完成するという事実と同様、ローカルプライベート・メモリのそれに相当する効率でそれが処理コア２４に供給されることに貢献する。しかしながら、組合せの相互接続ネットワーク２０ａの遅延が十分に小さく、処理コア２４とメモリバンク２２との間でネットワークが提供することができる経路の数が十分に大きいこともまた必要である。本発明は、「相互接続ネットワークの遅延」と名付けられるサブセクション、よび、「メモリ・システムにおいて形成される経路」と名付けられるセクションでさらにここで記載されるように確かにこれらの必要条件を満たす。
【００９１】
パイプラインでの転送に基づいた本発明の好ましい実施態様において、当業者によって「パイプライン・レジスタ」として公知であるものを相互接続ネットワークに加える必要がある。
【００９２】
パイプライン・レジスタは別として、相互接続ネットワークのすべての残りは、組合せである。パイプライン・レジスタは、小さい断片にそれを分解せずにこの組合せのシステムに入れられる：先に定められた関数ｆ１は、単一のクロックサイクルで（相互接続がパイプラインでの転送に基づかない場合、同じサイクルである）、上で導入された変数ｘ１からその全体をさらに計算される。また関数ｆ２からｆ６のすべては、単一のクロックサイクルにおいて、ｘ１、上で導入された他の変数ｘ２、および、ｆ１（またはｘ１、ｘ２、および、ｆ１の部分集合）から計算される。
【００９３】
以下の表は、パイプラインでの転送に基づく様々な好ましい実施態様においてパイプライン・レジスタが必要であるものの詳細である。
2011503710.tif 000006
2011503710.tif 000007
【００９４】
ここで、再び「メモリ・アクセスのパイプライン・ステージ」と名付けられるサブセクションにおいて議論された４つの好ましい実施態様を参照する。
【００９５】
図７は、図５の組合せの相互接続ネットワークを示すが、組合せのシステム全体が組合せのサブブロックへ分解されたものである。言及された４つのうちのこの第１の好ましい実施態様はパイプラインに基づかないものであり、したがって、この実施態様の組合せの相互接続ネットワーク２０ａは、図５に対応する。
【００９６】
図７に示されるサブブロック６６、６８、７０および７２は、パイプラインでの転送に基づいていかなる本発明の好ましい実施態様においても完全なままである。それゆえに、相互接続ネットワーク２０ａの本質的に組合せの性質は、パイプラインでの転送に基づく好ましい実施態様においても無傷のままで保存される。
【００９７】
２つまたは３つのパイプライン・ステージに基づく他の３つの好ましい実施態様は、どの活動要素が各々のステージで実行されるかを特定する線図を用いて先に記載されている。ここで提供されるのは、図７において表される分解を用いて示される追加的な観点であり、そこでパイプライン・レジスタは、これらの線図に導入される第２、第３および第４の好ましい実施態様を得るために入れられる。
【００９８】
図８は、パイプライン・レジスタを加えることによってパイプラインでの転送に基づく本発明の好ましい実施態様がどのように得られるかについて示す。
【００９９】
第２の好ましい実施態様は、２つのパイプライン・ステージと（第１のステージは（ｂ）と一体になる（ａ）であり、第２のステージは（ｃ）である）、第１のステージの活動要素Ｃの実行とに基づく。この実施態様を得るため、パイプライン・レジスタ５６は図８に示すように入れられ、そこでそれらは黒い長方形によって象徴される。相互接続ネットワーク２０ｂはまた、サブブロック６６、６８、７０および７２を含む。
【０１００】
図１０は、パイプラインでの転送に基づいたさらに他の好ましい実施態様を示す。
【０１０１】
３つのパイプライン・ステージに基づく第４の好ましい実施態様を得るため、相互接続ネットワーク２０ｄはまた、図１０に示すようにサブブロック６６、６８、７０および７２で入れられるパイプライン・レジスタ５６を備える。
【０１０２】
サブブロック７２は、図７から１０において示される相互接続ネットワーク２０ａ、２０ｂ、２０ｃおよび２０ｄの各々の４つの好ましい実施態様において関数ｆ１を計算することに留意するべきである。
【０１０３】
パイプラインのシステムにおけるパイプライン・ステージの数は、「パイプライン深さ」として当業者によって公知である。本発明において、パイプライン深さは、２または３である。パイプラインでの転送の配置がない所で、パイプライン深さは１であると考えられる。本発明の最高３の小さいパイプライン深さは、障害を防ぐまたは障害の頻度を有意に減らすのを助け、それ以外は、メモリ・システムがパイプラインで転送される場合に発生する処理コア２４（図２参照）の操作の「機能停止」として公知である。これは、処理コア２４自体がパイプラインで転送されることができることが当業者によって周知であるからである。必要なものは、メモリ・システムのパイプライン・ステージとそれらの処理コア２４との間の適合である。すなわち、処理コア２４は、取組みが実行されたステージより１または２クロックサイクル後の適切なステージでそのメモリ・アクセス取組みの結果を求めるべきである。
【０１０４】
相互接続ネットワークの遅延
処理コア２４（図２参照）をローカル・メモリにアクセスする際に達成されるそれに相当するある程度の効率で共有メモリにアクセスさせるため、満たされなければならない１つの必要条件は、相互接続ネットワーク２０の遅延が十分に小さいということである。本発明は、以下の要因に基づいてこの必要条件を満たす：１）相互接続ネットワークの組合せの性質；２）処理コアの数ｎに対数的に依存した相互接続ネットワークを横切った経路に沿ったスイッチの数；３）それが長方形の範囲内で制限される場合、ベースライン・ネットワークの片側のポートから向こう側のポートへの経路の最大の幾何学的な全長が、制限用長方形の対角線の長さを上回らないように、図３に対応する方法で２次元表面上のその物理的な幾何学的レイアウトに関連したベースライン・ネットワークの役立つ特性。
【０１０５】
上記において定められた関数ｆ１、ｆ２、ｆ３およびｆ４の計算に伴う遅延時間は、次のように表される：
Ｔｆｏｒｗａｒｄ＝Ｔｂｒｉｄｇｅ１＋ｌｏｇｂｎ＊Ｔｉｎ＿ｔｏ＿ｏｕｔ＋Ｔｗｉｒｅ１
ここで、Ｔｂｒｉｄｇｅ１は、読み込みネットワーク３０と書き込みネットワーク３２との外側で図２に現れるルーティング、連結または橋絡の要素３４と、さらに対数関数的マルチステージ・ネットワーク５４の外側の図４の要素３４ａとによる遅延時間である；
Ｔｉｎ＿ｔｏ＿ｏｕｔは、対数関数的マルチステージ・ネットワーク５４（図４参照）が構成されるタイプの各々の側でｂポートを有するスイッチの遅延時間である；
Ｔｗｉｒｅ１は、ワイヤを通じた、これらのワイヤに沿って位置するアンプまたはリピータを含む信号伝搬時間である；
ｌｏｇｂｎは、処理コア２４（図２参照）の数ｎの基数ｂによる対数を表す。
【０１０６】
関数ｆ１、ｆ２、ｆ３およびｆ４がすでに計算され、関連した変数の値がすでにメモリバンク２２（図２参照）によって提供された後、上で定義された関数ｆ５およびｆ６の計算に伴う遅延時間は、次のように上記から制限される：
Ｔｂａｃｋｗａｒｄ＝Ｔｂｒｉｄｇｅ２＋ｌｏｇｂｎ＊Ｔｏｕｔ＿ｔｏ＿ｉｎ＋Ｔｗｉｒｅ２
ここで、Ｔｂｒｉｄｇｅ２は、読み込みネットワーク３０と書き込みネットワーク３２との外側で図２と、さらに対数関数的マルチステージ・ネットワーク５４の外側の図４とに現れるルーティング、連結または橋絡の要素による遅延時間である。２つの値Ｔｂｒｉｄｇｅ２とＴｂｒｉｄｇｅ１とは、必ずしも等しい必要はない；
Ｔｏｕｔ＿ｔｏ＿ｉｎは、対数関数的マルチステージ・ネットワーク５４が構成されるタイプの各々の側でｂポートを有するスイッチの遅延時間である。２つの値Ｔｏｕｔ＿ｔｏ＿ｉｎとＴｉｎ＿ｔｏ＿ｏｕｔとは、必ずしも等しい必要はない；
Ｔｗｉｒｅ２は、ワイヤを通じた、これらのワイヤに沿って位置するアンプまたはリピータを含む信号伝搬時間である。２つの値Ｔｗｉｒｅ２とＴｗｉｒｅ１とは、必ずしも等しい必要はない。
【０１０７】
遅延時間ＴｆｏｒｗａｒｄおよびＴｂａｃｋｗａｒｄは、確かに十分に小さい：構成要素Ｔｂｒｉｄｇｅ１とＴｂｒｉｄｇｅ２とは、処理コア２４の数ｎ、メモリバンク２２の数ｋ、および、重複要因ｍにわずかに依存するだけである。Ｔｉｎ＿ｔｏ＿ｏｕｔとＴｏｕｔ＿ｔｏ＿ｉｎとは、対数的に、要因ｌｏｇｂｎによりｎのみに依存する貢献を有する；この貢献はしたがって、非常にコンパクトかつ速いと考えられる組合せのシステムであるキャリールックアヘッド加算器の遅延と類似している。構成要素Ｔｗｉｒｅ１およびＴｗｉｒｅ２の遅延時間ＴｆｏｒｗａｒｄおよびＴｂａｃｋｗａｒｄへの貢献は、制限用長方形の対角線の長さを上回らないワイヤの累積的な長さに依存する。
【０１０８】
メモリ・システムにおいて形成される経路
処理コアとメモリバンクとの間の経路の定義
相互接続ネットワーク２０の経路は、すべてのクロックサイクルで新たに計算される。この計算において、以前のクロックサイクルで計算された経路を考慮する必要はない；すなわち、経路の「再配置」として当業者に周知のことを実行する必要はない。他の事実は、処理コア２４が参照を始める処理コア２４とメモリバンク２２との間の経路を決定する際、他の処理コアの取組みを考慮する必要がないことである。相互接続ネットワークのビルディングブロックのポートの競合の結果として経路間の衝突が発生する場合、拒絶応答を返す必要だけがある。これらの２つの事実は、経路の計算を非常に単純化し、このことにより、本発明の相互接続ネットワーク２０を単純で、効率的かつ軽量であるのを助ける。
【０１０９】
相互接続ネットワーク２０（図２参照）の経路は、処理コア２４（図２参照）が提出するメモリ・アドレス、さらにアクセスのタイプに関する情報‐それが読み込みまたは書き込むであってもから計算される。処理コア２４が共有メモリスペースのアドレスへのアクセスを始める場合、このアドレスは明白に以下の３つのアイテムを定める：（ｉ）  アクセスされているメモリバンク２２；（ｉｉ）  メモリバンク２２内の内部のアドレス、および、アクセスのタイプに関する情報とともに、そのアドレスはまた次のものを明白に定義する：（ｉｉｉ）  メモリへのアクセスが達成される相互接続ネットワーク２０の経路。
【０１１０】
２つの異なる処理コア２４が共有スペースにおいて同じアドレスを参照する（異なる時間に）場合、それらは、同じメモリバンク２２、および、そのメモリバンク２２内部の同じ内部のアドレスを参照する。しかしながら、単に経路の終点が同じではないので、それらが使用する経路は異なる。
【０１１１】
先に示されたように本発明の好ましい実施態様において、メモリバンク２２の数ｋおよび重複要因ｍと同様に処理コア２４の数ｎは、すべて２のべき乗である。また、関係式ｋ≦ｎｘｍ、または、同等にｌｏｇ２ｋ≦ｌｏｇ２ｎ＋ｌｏｇ２ｍは有効である。「アドレスの幅」として当業者によって公知である、メモリ・アドレスのバイナリの表現に含まれるビットの全体の数は、所望のサイズの共有メモリスペースによって決定される。この幅は、ｌｏｇ２ｎ＋ｌｏｇ２ｍの合計より概して大きい。重複要因ｍの値は、概してメモリバンク２２の数ｋの値より小さい。
【０１１２】
図１１は、処理コア２４により発行されるメモリ・アドレスのバイナリ表現を示す。上で定められるように、処理コア２４（図２の）により発行されるバイナリのメモリ・アドレス８０の表現の図１１の描写は、アイテム（ｉ）（ｉｉ）、および、（ｉｉｉ）の決定を説明するために用いられる。
【０１１３】
アドレスの最上位ビットは最も左のビットであり、最下位ビット最も右のビットである。ｋがメモリバンク２２（図２参照）の数であるｌｏｇ２ｋの最も右のビット８４はここでフィールドＡと示される。残りのビット８６は、フィールドＢと示される。また、ｍが重複要因であるｌｏｇ２ｍの最も右のビット８２は、フィールドＣと示され、ｎが処理コアの数であるフィールドＣと隣接したｌｏｇ２ｎのビット７８はフィールドＤと示される。上記の３つのアイテム（ｉ）、（ｉｉ）、（ｉｉｉ）がここで以下に詳細に記載される。
【０１１４】
（ｉ）‐参照が作成されるメモリバンクの決定
参照が作成されるメモリバンク２２のインデックスは、アドレスのフィールドＡ  ８４の内容によって決定される。隣接するまたは互いに十分に近いアドレスは、フィールドＡ  ８４の値のみにおいて異なり、したがって、そのようなアドレスは異なったメモリバンクにおいて実施される。
【０１１５】
概してマルチコア・コンピュータにより実行されるプログラムは、「参照の局所性の原理」として当業者によって公知であるものにより、それらの処理コアを近くのアドレスに次の参照を出すようにする傾向がある。それゆえに、そのような参照は、異なったメモリバンクの中で散乱する傾向がある。「インターリービング」として当業者によって公知であるこの現象は、競合および衝突を軽減する利点を有する。ここで関連する衝突は、相互接続ネットワーク２０（図２参照）の経路に関係せず、むしろ（図２の）メモリバンク２２に関連する；しかしながら、これらの衝突は、それにもかかわらず、「経路間の衝突の処理」と名付けられた部分でさらに説明されるように、その周辺部に位置するそれの要素３４、３４ａ（図２、４参照）において相互接続ネットワーク２０内で明らかにされ、検出される。
【０１１６】
（ｉｉ）‐メモリバンク内部のアドレスの決定
参照が作成されるそのメモリバンク２２（図２参照）内部のアドレスは、アドレスのフィールドＢ  ８６によって決定される。
【０１１７】
（ｉｉｉ）‐メモリへのアクセスが実行される相互接続ネットワークの経路の決定
上記のように相互接続ネットワーク２０のトポロジによって、経路の決定は、以下の構成を含む：上記のような相互接続ネットワーク２０のトポロジにしたがって、経路の決定は、以下の構成を含む：（ｉｉｉ．１）経路が読み込みネットワーク３０または書き込みネットワーク３２（図２参照）を通過するかどうかの決定；（ｉｉｉ．２）経路が通過する（図４参照）対数関数的マルチステージ・ネットワーク５４の決定；および、（ｉｉｉ．３）対数関数的マルチステージ・ネットワーク５４（図４参照）内での内部の経路の決定。
【０１１８】
３つの構成要素（ｉｉｉ．１）（ｉｉｉ．２）および（ｉｉｉ．３）は、メモリバンク２２への処理コア２４のアクセスが実行される相互接続ネットワーク２０内部で一緒に経路の完全かつ明確な定義を構成する。これらの３つの構成要素は、以下の表で詳述される。
2011503710.tif 000008
2011503710.tif 000009
【０１１９】
経路間の衝突の処理
各々の処理コア２４（図２参照）は、すべてのクロックサイクルで共有メモリにアクセスする取組みを実行する。与えられたクロックサイクルで提出した一連のすべての取組みは、処理コア２４とメモリバンク２２との間の対応した一連のリクエストされた経路を定める。
【０１２０】
この集合に属する異なる経路の間で、衝突は発生する。本発明の原則によると、メモリ・システムは、そのような衝突を検出し、読み込みネットワーク３０および書き込みネットワーク３２（図２参照）において異なって活動を実行することによってそれらに反応する。読み込みネットワーク３０は、衝突の数の減少に貢献するマルチキャストをサポートする際の書き込みネットワーク３２から区別される。読み込みネットワーク３０のマルチキャストのサポートは、「読み込みの関連するホットスポットを収容するためのマルチキャストのサポート」と名付けられた部分でさらに説明される。
【０１２１】
以下の説明は、読み込みネットワークを除外して相互接続ネットワークによって実行されるような、衝突の検出およびそれらへの反応の供給に関する。
【０１２２】
２つのリクエストされた経路間の衝突は、それら両方が同じスイッチ（４６のような−図３参照）または他の基本的なネットワーク要素を経て通過する場合、および、さらに−メモリバンク２２（図２参照）により近い側でそれら両方が同じポートを必要とする場合に存在する。
【０１２３】
相互接続ネットワーク２０（図２参照）のトポロジの上記の記述から、そのようなポートが以下の２つのタイプの１つに属することができることは明らかである：
（Ｉ）対数関数的マルチステージ・ネットワーク５４の内部のスイッチのポート。対数関数的マルチステージ・ネットワーク５４がベースライン・ネットワークである本発明の好ましい実施態様において、各々の側で２つのポートを有するスイッチ４６から作られる。これは、「Ｏｕｔ＿０」または「Ｏｕｔ＿１」ポート（図３参照）である。
（ＩＩ）例えば図２の下部でまたは図４の下部で表される３４、３４ａのようなルーティング、連結または橋絡の役に立つ要素のポート。
【０１２４】
競合が上のタイプ（Ｉ）のポート上にある場合、これは確かに相互接続リソースの上の競合である。競合が上のタイプ（ＩＩ）のポート上にある場合、これは、相反する経路の原因となる２つの取組みが同じメモリバンク２２（図２参照）に関係するので、実際にメモリ・リソースの上の競合である。しかしながら、衝突は、いずれの場合においても同じ方法で相互接続ネットワーク２０内において明らかにされかつ検出される。
【０１２５】
メモリバンク２２（図２参照）により近い側５２（図４参照）でその同じポートを得るための２またはそれ以上のリクエストが配置される場合、衝突はスイッチまたは他の基本的なネットワーク要素で局所的に検出される。これらのリクエストは、処理コア２４（図２参照）により近い側５０（図４参照）へ異なるポートを経て届く。例えば、関連した要素がベースライン・ネットワークに属するスイッチ４６であり、両側に２つのポートを有する場合、ポートＩｎ＿０およびＩｎ＿１を経て到着する２つのリクエストは衝突して、両方ともポートＯｕｔ＿０を必要とする時、または、両方ともポートＯｕｔ＿１（図３参照）を必要とする時に衝突を生成する。上の説明から、この例で発生するそのような衝突のため、アドレスのフィールドＤ  ７８の関連したビットがアクセスのターゲットとして役立つ２つのメモリ・アドレスで同一であることが必要である（しかし、十分でない）ことは明らかである。
【０１２６】
衝突がどのように検出されるかについては説明され、以下の説明は、相互接続ネットワーク２０がそれらに反応する方法に関する（読み込みに関連したホットスポットを収容するマルチキャストのサポートと名付けられた部分において別に議論される図２に示される読み込みネットワーク３０を除外する）。衝突を検出するスイッチまたは他のネットワーク要素は、競合したポートを付与するための相反した、入って来るリクエストの局所的な決定を実行する。
【０１２７】
本発明の実施態様では、この決定は、リクエストがそれを通じて到着する処理コア２４により近い側でポートに割り当てられる固定した優先順位のみに依存し；一方で、時間に関して固定され、これらの優先順位は、メモリバンク２２により近い側でリクエストされたポートの識別に依存する。これは、ネットワークの細長さに貢献する単純な決定メカニズムである。
【０１２８】
その決定に従って、スイッチまたは他のネットワーク要素は、獲得したリクエストの役に立つ（処理コア２４により近い側で）ポートを経て承認応答をエクスポートする。それはまた、競合に含まれる他のリクエストの役に立つ（また処理コア２４により近い側で）ポートを経た拒絶応答をエクスポートする。拒絶応答は、衝突を検出する場合のみにおいてネットワーク要素で局所的に生成されることができる。
【０１２９】
しかしながら拒絶応答はまた、局所的に生成された結果としてよりもむしろ、転送の結果としてエクスポートされることができる。転送された拒絶応答は、現在のネットワーク要素が生成したいかなる承認応答にも取って代わる。さらに、拒絶応答がリクエストに応答して付与されたメモリバンク２２の側でそのポートを経てネットワーク要素に到着する場合、この拒絶応答は転送されなければならない。そして、獲得リクエストが到来する向こう側（すなわち、処理コア２４の側面）のポートを経て転送されなければならない。衝突を検出し、局所的に拒絶応答を生成して、処理コア２４により近い他のネットワーク要素を通じて広がるネットワーク要素で始まる拒絶応答の痕跡は、したがって生成されることができる。最終的には、痕跡は取組みが拒絶されている処理コア２４に到達する。
【０１３０】
拒絶応答を受信する処理コア２４は、後のクロックサイクルでその取組みを概して再提出する。現在のクロックサイクルでの取組みの提出により、相互接続ネットワーク２０内部での不完全な経路の配分がもたらされる。この経路は、衝突を検出し、提出されたリクエストを拒否するという局所的な決定を下すネットワーク要素で切断される。相互接続ネットワーク２０のリソースを占めることによって、不完全なそのような経路は、他の経路の配分、および、他のリクエストの遂行を防ぐ。それにもかかわらず、経路の計算を単純かつ急速に保つために、リソースの取り戻しおよび経路の再配置は実行されない。
【０１３１】
可能な経路の数
ローカル・メモリにアクセスする際に達成されるそれに相当するある程度の効率で処理コア２４（図２参照）が共有メモリにアクセスすることを可能にするため、遅延に関して上に議論された必要条件に加えて、次の第２の必要条件が満たされなければならない：相互接続ネットワーク２０が提供することができる処理コア２４とメモリバンク２２との間の経路の数は、十分に大きくなければならない。あまりに多くの衝突が相互接続ネットワーク２０のリソース、および、メモリバンク２２の上の競合の結果として生成される場合、この必要条件は、満たされない。  
【０１３２】
しかしながら、以下において、経路の数に関する所望の目的は、並列に連結された対数関数的マルチステージ・ネットワーク５４（図４参照）の数およびメモリバンク２２（図２参照）の数に適切な値を設定することによって本発明の原則により構築されるメモリ・システムにおいて確かに遂げられることが指摘される。所望の目的を達成するための追加の手段は、後で示される読み込みネットワーク３０（図２参照）のマルチキャストのサポートである。マルチキャストのサポートが読み込みネットワーク３０に加えられる前の相互接続ネットワーク２０の経路の数の分析的結果が、ここで示される。
【０１３３】
クロックサイクルで形成される処理コア２４とメモリバンク２２との間の経路の平均数を分析的公式において示すことは、以下の３つの仮定条件により可能である：
●第１の仮定条件は、処理コア２４が互いに独立して操作するということである。
●第２の仮定条件は、いかなるクロックサイクルで処理コア２４がメモリ・アクセスを始めるという確率がすべての処理コア２４において均一の値ｐによって与えられることである。（それゆえに、処理コア２４がいかなる与えられたクロックサイクルでメモリ参照を始めないという確率は、相補的値１‐Ｐである）
●第３の仮定条件は、メモリにアクセスするいかなる取組みも同じ確率のいかなるメモリ・アドレスにも関係するということである。
【０１３４】
下で示される分析的公式は、読み込みおよび書き込み操作間の比率が、読み込みまたは書き込みのために役に立つかどうかに関わりなく、相互接続ネットワーク２０において含まれる対数関数的マルチステージ・ネットワーク５４のすべてが等しい頻度で使われる状況を意図したものである。これにより、分析の単純性のため、読み込みと書き込みとの間の識別と関連する複雑化が解消される。
【０１３５】
上の仮定条件から、いかなる与えられたクロックサイクルで処理コア２４が一緒にリクエストする経路の平均総数は、処理コア２４の数ｎとメモリ・アクセスを始める確率ｐとの間の積に等しいことがわかる。しかしながら、いくつかのリクエストに対する応答が相反する経路のために拒絶応答であるので、実際に生成される経路の平均総数はｎ×ｐよりも小さい。読み込みネットワーク３０と書き込みネットワーク３２（図２参照）の両方で含まれる対数関数的マルチステージ・ネットワーク５４（図４参照）が各々の側で２つのポートを有するスイッチから構成される場合、実際に生成される経路の平均数は、次の公式によって与えられる：
（経路の平均数）＝ｋ×｛１−［１−ｆｌｏｇ２ｎ（ｐ／ｍ）］ｎ×ｍ／ｋ｝
ここで、記号の意味は以下の通りである：
●記号ｎは、処理コアの数を表す。
●記号ｋは、メモリバンクの数を表す。
●記号ｍは、相互接続ネットワークにおいて含まれる対数関数的マルチステージ・ネットワークの数を表す（このコンテキストでは、読み込みネットワークに含まれる対数関数的マルチステージ・ネットワークと書き込みネットワークで含まれるものとの間に識別は作成されない）。
●記号ｐは、処理コアがいかなる与えられたクロックサイクルでメモリ参照を始める確率を表す。
●記号ｆは、式ｘ−ｘ２／４によって与えられる数ｆ（ｘ）にあらゆる現実の数ｘをマッピングする数学的マッピングを表す。
●上のインデックスとして生じる式ｌｏｇ２ｎは、ｌｏｇ２ｎ回のマッピングｆの反復呼出しを示す。
【０１３６】
上記の公式から、ｎおよびｐが固定して保たれる場合、ｎ×ｐに要求されるように近く実際に生成される経路の平均数をｍおよびｋの十分な増加により作成することが可能であることがわかる。すなわち、与えられた数の処理コア２４（図２の）、および、処理コア２４がメモリ・アクセスを始めるという与えられた確率によって、いかなる所望のレベル（絶対零度ではないが）にも衝突の量を減らすことができる；これは、対数関数的マルチステージ・ネットワーク５４（図４参照）の数と、一緒に共有メモリスペースを具体化する部分的なバンクの数とを適切に増やすことによって達成される。
【０１３７】
上記の公式を導く際、単純性のため、相互接続ネットワークにおいて含まれたすべての対数関数的マルチステージ・ネットワーク５４は、それらが読み込みまたは書き込みのために役に立つかどうかに関わらず、等しい頻度で使われると仮定された。この仮定条件を緩和することにより、読み込みおよび書き込み操作間と、読み込みおよび書込みネットワーク間との識別の分析の導入を必要とする。
【０１３８】
さらに読み込みネットワーク３０（図２参照）において、衝突の量を減らし、それによって実際に生成される経路の平均数を増やすための追加の手段が存在する。この手段は、マルチキャストのサポートである。処理コア２４の取組みの相互依存の傾向があり、さらに‐多くの処理コア２４が同じクロックサイクルで同じメモリ・アドレスから読み込みを実行したい状況が意図される。そのようなアドレスは、読み込みに関連したホットスポットを構成する。
【０１３９】
読み込みに関連したホットスポットを収容するためのマルチキャストのサポート
読み込みネットワーク３０を含まない相互接続ネットワーク２０の部分が経路間の衝突を検出してそれらに反応するかは、上で説明された。読み込みネットワーク３０は、衝突の量の減少に貢献するマルチキャストのそのサポートにおいて他の相互接続ネットワーク２０から区別される。これは、以下に説明される。
【０１４０】
衝突は、それはメモリバンク２２により近い側において、その同じポートを得る１以上のリクエストが存在することを識別するスイッチまたはネットワークの基本的な他の要素で局所的に検出される。読み込みネットワーク３０を含まない相互接続ネットワーク２０の部分で、ネットワーク要素は、競合したポートを付与する衝突しているリクエストに関して局所的に決定をする。読み込みネットワーク３０において、しかしながら、ネットワーク要素は、衝突している取組みが読み込みたいメモリ・アドレスの確認に基づいて異なるタイプの反応をする。２以上のアドレスが同一の場合、次のように明らかにされるマルチキャストが実行される：ネットワーク要素は、関連したメモリ・アドレスから読み込みたい取組みを運ぶメモリバンク２２の方向から到着した内容を競合するポートを経てその向こう側（すなわち、処理コア２４により近い側）のすべてのポートに移す。
【０１４１】
好ましい実施態様において、この関連したメモリ・アドレスは、最も高い優先順位を有するリクエストと関連したものであり、上記のように残りのネットワークにおいて同じ単純な選択体系によって選択されるものである。他の好ましい態様として、この関連したメモリ・アドレスは、衝突しているリクエストの最大数と関係しているものである。メモリ・アドレスの内容が複数の処理コアにマルチキャストされる場合、ツリートポロジを有するマルチ経路が読み込みネットワーク３０内で形成される（図１２の例参照）。
【０１４２】
図１２は、メモリ・アドレスの内容のマルチキャストがある場合の読み込みネットワーク内で形成されるツリートポロジを有するマルチ経路の一例を示す。
【０１４３】
この例では、マルチキャストは、３つの処理コア２４によって同じクロックサイクルで同じメモリ・アドレスの読み込みを可能にする。メモリ・アドレスは、図１２において表されるメモリバンク２２内に属する。マルチキャストは、「相互接続要素」と分類された２つの分離した基本的なビルディングブロック８８における読み込みネットワーク３０において発生する。ビルディングブロック８８は、上に記載されているスイッチ４６（図３参照）および基本的な要素３４ａ（図４の側５２の近くに生じる）のそれらに類似した関数を有する要素を表す。
【０１４４】
ビルディングブロック８８によって表される各々のこれらの２つの相互接続要素は、経路にこのポートを加えるために向こう側でその同じポートを得るような２つのリクエストを処理コア２４に近い側でのポートを経て受信する。衝突を検出する一方、各々の２つの相互接続要素８８はまた、２つの衝突しているリクエストが同じメモリ・アドレスに関係する読み込まれた取組みから導かれたことを確認して、見つける。それゆえに、マルチキャストによる相互接続要素８８は、処理コア２４により近い側で、競合するポートを経て１つのポートよりも、２つのポートにメモリバンク２２の方向から到着している内容を移す。マルチキャストは各々の相互接続要素８８で局所的に決定されるが、ツリートポロジを有するマルチ経路の全体像を生成する。
【０１４５】
１つのメモリ・アドレスにおいて蓄積された内容の複数の処理コアへの同じクロックサイクルでの転送を可能にすることによって、読み込みネットワーク３０のマルチキャストのサポートは、読み込みに関連したホットスポットを効率的に収容するためのサポートを構成する。
【０１４６】
その特定の実施態様に関して本発明を記載してきたが、この説明は、当業者によりさらなる変更が提案されるので、制限を意味するものではなく、添付の請求の範囲に入るものとしてそのような変更を含む意図を有すると理解される。
【図１】
2011503710.tif 000010
【図２】
2011503710.tif 000011
【図３】
2011503710.tif 000012
【図４】
2011503710.tif 000013
【図５】
2011503710.tif 000014
【図６】
2011503710.tif 000015
【図７】
2011503710.tif 000016
【図８】
2011503710.tif 000017
【図９】
2011503710.tif 000018
【図１０】
2011503710.tif 000019
【図１１】
2011503710.tif 000020
【図１２】
2011503710.tif 000021
【国際調査報告】
2011503710.tif 000022