JPH077382B2 - 並列処理のための相互接続網、コンピュータ・システム及び方法 - Google Patents

並列処理のための相互接続網、コンピュータ・システム及び方法

Info

Publication number
JPH077382B2
JPH077382B2 JP4334578A JP33457892A JPH077382B2 JP H077382 B2 JPH077382 B2 JP H077382B2 JP 4334578 A JP4334578 A JP 4334578A JP 33457892 A JP33457892 A JP 33457892A JP H077382 B2 JPH077382 B2 JP H077382B2
Authority
JP
Japan
Prior art keywords
processor
integer
computer
processors
shuffle
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
JP4334578A
Other languages
English (en)
Other versions
JPH05324590A (ja
Inventor
ロバート・エドワード・サイファ
ホルヘ・エル・シー・サンス
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH05324590A publication Critical patent/JPH05324590A/ja
Publication of JPH077382B2 publication Critical patent/JPH077382B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • G06F15/17356—Indirect interconnection networks

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Data Mining & Analysis (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Computational Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • Algebra (AREA)
  • Multi Processors (AREA)

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、全般的には並列コンピ
ュータ用の相互接続網に関する。詳細に言うと、本発明
は、（１）プロセッサ間の大域通信が効率的にサポート
され、（２）並列コンピュータを分割して、任意の多数
のプロセッサを有する並列コンピュータを作成するのに
使用できる同一の構成要素（すなわち、チップ、基板ま
たはラック）にすることができ、（３）実装階層の各段
によって課される実装制約に適合するように並列コンピ
ュータをカストマイズすることができるように、並列コ
ンピュータ内のプロセッサを相互接続し実装する技法に
関する。
【０００２】より具体的に言えば、所望のプロセッサ数
がＮであるとし、（ａ）次段（level）の実装階層にお
いても単一の構成要素で配置することのできるような、
実装階層の各段での構成要素の最大数と、（ｂ）実装階
層の各段にある単一の構成要素から出すことのできる配
線の最大数とで表される１組の実装制約があるものとし
た場合、本発明の一態様は、（１）かかる実装制約がす
べて満足され、（２）実装階層の各段中の各構成要素
が、同一段中の他のすべての構成要素と同一であり、
（３）実装階層の各段の構成要素を再使用して、より多
くのプロセッサを有する並列計算機を作成でき、（４）
その結果得られる並列計算機が、高速フーリエ変換（Ｆ
ＦＴ）、バイトニック・ソート、Benes置換アルゴリズ
ム、ならびに昇順類および降順類のすべてのアルゴリズ
ムで必要とされるような大域通信を効率的にサポートす
るように、プロセッサを相互接続し実装する方法を教示
する。
【０００３】高速フーリエ変換は、プレパラータ（Prep
arata）他の論文"The Cube-Connected Cycles: A Versa
tile Network For Parallel Computation"、the Commun
ications of the ACM, 24(5): 300-309、（1981年5月）
に記載されている。バイトニック・ソートは、前述のプ
レパラータ他の論文と、K. E. バッチャー（Batcher）
の論文"Sorting Networks and Their Applications"、t
he Proceedings of the AFIPS Spring Joint Computer
Conference,pp.307〜314ページ（1968年）に記載されて
いる。Benes置換アルゴリズムは、前述のプレパラータ
他の論文、V. E.ベネシュ（Benes）の論文"Mathematica
l Theory Of Connecting Networks andTelephone Traff
ic"、the Academic Press刊（1965年）および"Optimal
Rearrangeable Multistage Connection Networks"、the
Bell System Technical Journal, 43:1641-1656（1964
年）、ならびにA. ワックスマン（Waksman）の論文"A P
ermutation Network"、the Journal of the ACM, 15
(1):159-163（1968年1月）に記載されている。昇順類お
よび降順類のアルゴリズムは、前述のプレパラータ他の
論文に記載されている。
【０００４】本発明のもう１つの態様によれば、昇順類
および降順類のすべてのアルゴリズムを含む様々な種類
の並列アルゴリズムを、上記のような並列コンピュータ
上で実施するための効率的な技法が教示される。
【０００５】
【従来の技術】多くの並列コンピュータは、それぞれが
それ自体に付随する記憶装置を有する多数のプロセッサ
と、プロセッサの特定の対を接続する通信リンクとから
なる。このような並列コンピュータを設計する上で鍵と
なる問題が、「相互接続網」と総称される、通信リンク
の配置構成である。相互接続網の設計は、並列計算機上
で実施されるアルゴリズムの通信要件と、技術的制限に
よって課される実装制約との間のトレードオフを表すも
のである。
【０００６】詳細に言うと、多くのアルゴリズムは、各
プロセッサが、並列計算機の物理的実施態様中で遠くに
あるものも含めて他の多数のプロセッサにメッセージを
送る、大域通信パターンを必要としている。ＦＦＴ、バ
イトニック・ソートならびに昇順類および降順類のアル
ゴリズム（上述）が、このような大域通信を必要とする
アルゴリズムの例である。したがって、各プロセッサと
他のすべて（または多数）のプロセッサの間の高帯域幅
接続を提供することによって、これらのアルゴリズムを
最も良くサポートできるはずである。
【０００７】その一方で、技術的制約のため、各プロセ
ッサと残りのすべてのプロセッサの間の高帯域幅接続を
提供することは不可能である。具体的に言うと、並列コ
ンピュータは、通常、２つ以上の段（level）からなる
実装階層（packaging hierarcy）を使用して実施され
る。たとえば、各プロセッサが単一のチップを占め、複
数のチップを単一の基板上に置き、複数の基板を組み合
わせてモジュールを作成し、複数のモジュールを組み合
わせてラックを作成し、複数のラックを組み合わせて完
全な並列コンピュータを作成することができる。この実
装階層の各段で、ピン制限と称する帯域幅の制約が課さ
れる。ピン制限とは、実装階層の所与の段にある各構成
要素から出すことのできる配線の数に対する制限であ
る。
【０００８】ピン制限に加えて、並列コンピュータの費
用効果の高い実施態様では、実装階層によって他のいく
つかの制約が課される。異なる構成要素の設計と製造に
はコストがかかるので、実装階層の各段にあるすべての
構成要素は、同一段中の他のすべての構成要素と同一で
あることが好ましい。このような実施態様を、均一な
（uniform）実施態様と称する。また、並列コンピュー
タは、通常はある範囲のサイズで製造される。所与の数
のプロセッサの実施態様が均一であっても、異なるサイ
ズの計算機には異なる構成要素が必要になることがあり
得る。異なる数のプロセッサを有する複数の計算機で同
一の構成要素を使用して均一に実施することのできる並
列コンピュータ・アーキテクチャを、本明細書では「ス
ケーラブル（scalable）」と称する。
【０００９】多数の異なる相互接続網が、並列コンピュ
ータ用に提案されている。しかし、以前に提案された網
のどれも、次の好ましい特徴のうちの１つまたは複数を
提供できない。（１）大域通信の効率的なサポート、
（２）必要なピンが少なく、実装階層の各段のピン制限
に合致すること、（３）所与の相互接続網を利用する並
列コンピュータの、均一かつスケーラブルな実施を可能
にする規則的な構造。
【００１０】たとえば、多くの並列コンピュータでは、
２次元網目相互接続網または３次元網目相互接続網が使
用される。２次元網目相互接続網を有する並列コンピュ
ータの例には、Goodyear Aerospace製の"ＭＰＰ"、MASP
AR製の"ＭＰ−１"およびIntel製の"Ｐａｒａｇｏｎ"が
含まれる。MIT（マサチューセッツ工科大学）で開発中
の"Ｊ−Ｍａｃｈｉｎｅ"は、３次元網目相互接続網を有
する。網目相互接続網を有する並列コンピュータは、効
率的に実装することができるが、その直径が大きいた
め、大域通信を効率的にサポートできない。具体的に言
うと、２次元網目相互接続網を有するＮプロセッサの並
列コンピュータは、Ｎ1/2に比例する直径を有し、３次
元網目相互接続網を有する同様のコンピュータは、Ｎ
1/3に比例する直径を有する。
【００１１】米国特許第４８４３５４０号明細書、米国
特許第４５９１９８１号明細書および米国特許第４５８
３１６４号明細書のどれにも、ツリー構造相互接続網が
記載されている。ツリー構造は、必要なピンが少ない
が、そのツリーのルートが、多数のメッセージが通過し
なければならない隘路となるので、大域通信を効率的に
サポートできない。
【００１２】もう１つの重要なタイプの相互接続網が、
ハイパーキューブである。ハイパーキューブ・トポロジ
に基づく商用並列計算機には、NCUBE, Inc.の"ＮＣＵＢ
Ｅ／１０"、Intelの"ｉＰＳＣ／２"およびThinking Mac
hinesの"ＣＭ−２"が含まれる。米国特許第４８０５０
９１号明細書には、ハイパーキューブ・トポロジを有す
る並列コンピュータを実装する技法が記載されている。
ハイパーキューブ技術に基づき２〜３千個のプロセッサ
を有する並列計算機が構築されているが、ピン制限のた
め、接続を非常に狭く（１ビット幅など）せざるを得
ず、したがって通信性能が制限されている。さらに、よ
り多くのプロセッサを有するハイパーキューブ・コンピ
ュータ（すなわち、ハイパーキューブ・トポロジに基づ
くコンピュータ）は、１実装構成要素当たりにより多く
のピンを必要とし、したがって、ピン制限のために、任
意の多数のプロセッサを有するハイパーキューブ・コン
ピュータが構築できない。また、異なる数のプロセッサ
を有する並列コンピュータには異なる構成要素を使用し
なければならないので、ハイパーキューブ・コンピュー
タは、スケーラブルでない。
【００１３】並列コンピュータ内で使用するため、ハイ
パーキューブに関係するいくつかのの相互接続網が提案
されている。これらには、（１）ナスィーミー（Nassim
i）他の論文"Data Broadcasting In SIMD Computers"、
IEEE Transactions On Computers, C-36(12):1450-1466
（1987年12月）、（２）J. T. シュワルツ（Schwartz）
の論文"Ultracomputers"、ACM Transactions On Progra
mming Languages andSystems, 2(4):484-521（1980年10
月）、および（３）H. S.ストーン（Stone）の論文"Par
allel Processing With The Perfect Shuffle"、IEEE T
ransactionsOn Computers, C-20(2):153-161（1971年2
月）に記載のシャフル・エクスチェンジ網、バーモンド
（Bermond）他の論文"de Bruijn and Kautz Networks:
A Competitor For The Hypercube?"、Hypercube and Di
stributed Computers、pp.279〜293、Elsevier Science
Publishers B.V.（北オランダ）刊（1989年）、および
サマタム（Samatham）他の論文"The de Bruijn Multipr
ocessor Network: A Versatile Parallel Processing a
nd Sorting Network For VLSI"、TransactionsOn Compu
ters, 38(4):567-581（1989年4月）に記載のde Bruijn
網、ならびに前述のプレパラータ他の論文に記載のキュ
ーブ接続サイクルが含まれる。
【００１４】シャフル・エクスチェンジ網とde Bruijn
網は、共に不規則な構造を有し、その結果、これらの網
のどちらかに基づく、必要なピンの少ない並列コンピュ
ータについての均一な実施態様は知られていない。キュ
ーブ接続サイクル網を有する並列コンピュータは、必要
なピンの少ない均一な形で実施できるが、この実施態様
はスケーラブルでない。また、ピン制限を考慮に入れる
時、これらの網はすべて、昇順類および降順類のアルゴ
リズムをサポートする際の効率が、本明細書に記載の新
型階層網より劣る。
【００１５】階層相互接続網を有するコンピュータは、
いくつか提案されている。上記で指摘したように、シュ
ワルツは、チップや基板など、複数の同一の構成要素か
らなる２段網を有する多層式シャフル交換コンピュータ
を提案した。多層式シャフル交換コンピュータは、均一
でありスケーラブルであるが、その直径は、使用される
実装構成要素（たとえばチップまたは基板）の数に比例
し、したがって、大型並列計算機内で大域通信を実施す
る時には非効率的である。R. サイファー（Cypher）の
論文"Theoretical Aspects of VLSI Pin Limitation
s"、Technical Report T.R. 89-02-01、University of
Washington, Department of Computer Science（1989年
2月）で定義されるシャフル・シフト・シャフル交換コ
ンピュータは、異なるプロセッサが異なる度数を有する
ので、均一でない。さらに、多層式シャフル交換コンピ
ュータとシャフル・シフト・シャフル交換コンピュータ
のどちらも、３段以上の実装階層によって課される制約
に合致するようにカストマイズすることができない。
【００１６】ダンダムディ（Dandamudi）他の論文"Hier
archical Interconnection Networks For Multicompute
r Systems"、IEEE Transactions On Computers, 39(6):
786-797（1990年6月）で提案された階層相互接続網は、
異なるプロセッサが異なる度数を有するので均一ではな
く、昇順類および降順類のアルゴリズムのような大域通
信パターンを有するアルゴリズムの実施のために最適化
されない。K. ゴーズ（Ghose）他の論文"The Design an
d Evaluation Of the Hierarchical Cubic Network"（t
he proceedings of the International Conference On
Parallel Processing、pp.355〜562（1990年、第１巻）
に記載の階層キューブ網を使用する並列コンピュータ
は、各ノードの度数がプロセッサ数に伴って増加するの
で、スケーラブルでない。J. ゴーシュ（Ghosh）他の論
文"Hypernet: A Communication-Efficient Architectur
e For Constructing Massively Parallel Computers"、
the IEEE Transactions On Computers, C-36(12):1450-
1466（1987年12月）で提案されたハイパーネット網は、
実装階層の各段に同一の帯域幅を有する固定した数の接
続を有し、したがって、任意の実装制約に合致するよう
に調節することができない。
【００１７】したがって、従来から既知の並列アーキテ
クチャには、（１）均一で、（２）スケーラブルで、
（３）任意の実装制約に対して調節可能で、（４）昇順
類および降順類のアルゴリズムなど大域通信を伴うアル
ゴリズムの実施に効率的である、という４つの条件を同
時に満たすものはない。
【００１８】
【発明が解決しようとする課題】本発明の一目的は、実
装制約に合致し、昇順類および降順類のアルゴリズムを
含めて大域通信を必要とするアルゴリズムの効率的な実
施をサポートする、並列コンピュータ内でプロセッサを
接続し実装するための効率的な方法を提供することであ
る。
【００１９】本発明の他の目的は、実装制約に合致する
ようにカストマイズすることのできる、均一かつスケー
ラブルな相互接続網を提供することである。
【００２０】本発明の他の目的は、所望のプロセッサ数
がＮであるとし、次段の実装階層においても単一の構成
要素で配置することのできるような、実装階層の各段で
の構成要素の最大数と、実装階層の各段にある単一の構
成要素から出ることのできる配線の最大数とで表される
１組の実装制約があるものとした場合に、（１）かかる
実装制約がすべて満足され、（２）実装階層の各段中の
各構成要素が、同一段中の他のすべての構成要素と同一
であり、（３）実装階層の各段の構成要素を再使用し
て、より多くのプロセッサを有する並列計算機を作成で
きるように、プロセッサを相互接続し実装するための手
段を提供することである。
【００２１】本発明の他の目的は、本明細書に提示の並
列コンピュータ上で、昇順類および降順類のアルゴリズ
ムを含めた大域通信を必要とするアルゴリズムの効率的
な実施を実現することである。
【００２２】
【課題を解決するための手段】本発明によれば、単一命
令ストリーム複数データ・ストリーム（ＳＩＭＤ）並列
コンピュータ（および、以下で論じる他の形式のコンピ
ュータ）用の新しい２種類の相互接続網が記述される。
本明細書では、この新しい種類の相互接続網を、階層シ
ャフル・エクスチェンジ（ＨＳＥ：hierarchical shuff
le-exchange）網および階層de Bruijn（ＨｄＢ：hierar
chical de Bruijn）網と称する。
【００２３】２n-m個の実装モジュール（ただしｎとｍ
は整数でｎ＞ｍ）を含む並列コンピュータにおいて、ｎ
個のビット（ｘn-1，…，ｘ0）による２n通りの組合せ
のうちの１つによってそれぞれが一意的に識別可能な２
n個のプロセッサを相互接続する相互接続網であって、
（ａ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
プロセッサ（ｘn-1，…，ｘ0）をそれぞれプロセッサ
（ｘn-1，…，ｘ1，ｃ［ｘ0］）、（ｘn-1，…，ｘm，
ｘm-2，…，ｘ0，ｘm-1）および（ｘn-1，…，
ｘm，ｘ 0，ｘm-1，…，ｘ1）（ただし"ｃ［ｘi］”はｘ
iの補数を表す）に接続する３本の両方向通信リンクの
組と、（ｂ）各プロセッサ（ｘn-1，…，ｘ0）に結合さ
れ、各プロセッサ（ｘn-1，…，ｘ0）をそれぞれプロセ
ッサ（ｘn-m-1，…，ｘ0，ｘn-1，…，ｘn-m）および
（ｘm-1，…，ｘ0，ｘn-1，．．．ｘm）にも接続する２
本の両方向通信リンクの組とを備える相互接続網が、本
発明で意図するＨＳＥ相互接続網の例である。
【００２４】２n-m個の実装モジュール（ただしｎとｍ
は整数でｎ＞ｍ）を含む並列コンピュータにおいて、ｎ
個のビット（ｘn-1，…，ｘ0）による２n通りの組合せ
のうちの１つによってそれぞれが一意的に識別可能な２
n個のプロセッサを相互接続する相互接続網であって、
（ａ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
プロセッサ（ｘn-1，…，ｘ0）をそれぞれプロセッサ
（ｘn-1，…，ｘm，ｘm-2，…，ｘ0，０）、（ｘn-1，
…，ｘm，ｘm-2，…，ｘ0，１）、（ｘn-1，…，ｘm，
０，ｘm-1，…，ｘ1）および（ｘn-1，…，ｘm，１，ｘ
m-1，…，ｘ1）に接続する４本の両方向通信リンクを含
む第１の組と、（ｂ）各プロセッサ（ｘn-1，…，ｘ0）
に結合され、各プロセッサ（ｘn-1，…，ｘ0）をそれぞ
れプロセッサ（ｘn-m-2，…，ｘ0，０，ｘn-1，…，ｘ
n-m）、（ｘn-m-2，…，ｘ0，１，ｘn-1，…，
ｘn-m）、（ｘm-1，…，ｘ0，０，ｘn-1，…，ｘm+1）
および（ｘm-1，…，ｘ0，１，ｘn-1，…，ｘm+1）に接
続する、４本の両方向通信リンクを含む第２の組とを備
える相互接続網が、本発明で意図するＨｄＢ相互接続網
の例である。
【００２５】新型のＨＳＥ網とＨｄＢ網は、高度に規則
的かつスケーラブルであり、したがって、ＶＬＳＩ実施
態様によく適している。さらに、これらは、どの１組の
実装制約にも合致するように調節することができる。ま
た、これらの新型網は、本発明の教示に従って組み立て
られた網のうちの１つを介してプロセッサが相互接続さ
れているコンピュータ上での、広範囲のアルゴリズムの
実行をサポートする際にも効率的である。このようなコ
ンピュータを、以下ではＨＳＥコンピュータまたはＨｄ
Ｂコンピュータと称する。
【００２６】したがって、新しい種類の網以外の本発明
のさらに２つの態様は、本明細書で教示される網（およ
び実装技法）を使用して構成することのできる階層形コ
ンピュータと、ＨＳＥコンピュータおよびＨｄＢコンピ
ュータ上でアルゴリズム、特に昇順形および降順形のア
ルゴリズムを実施する方法である。
【００２７】これら本発明のさらなる態様によれば、Ｈ
ＳＥコンピュータの好ましい実施例は、（ａ）０ないし
２n−１（ただしｎは整数）の範囲の整数のｎビット表
現によってそれぞれが一意的に定義される、２n個のプ
ロセッサと、（ｂ）０ないし２n-m−１（ただしｍは整
数でｎ＞ｍ）の範囲の整数の（ｎ−ｍ）ビット表現によ
ってそれぞれが一意的に識別でき、各プロセッサ（ｘ
n-1，…，ｘ0）が実装モジュール（ｘn-1，…，ｘm）に
含まれる、２n-m個の実装モジュールと、（ｃ）前記２n
個のプロセッサを相互接続するＨＳＥ相互接続網とを備
える。
【００２８】前述の本発明のさらなる態様によれば、Ｈ
ｄＢコンピュータの好ましい実施例は、（ａ）０ないし
２n−１（ただしｎは整数）の範囲の整数のｎビット表
現によってそれぞれが一意的に定義される、２n個のプ
ロセッサと、（ｂ）０ないし２n-m−１（ただしｍは整
数でｎ＞ｍ）の範囲の整数の（ｎ−ｍ）ビット表現によ
ってそれぞれが一意的に識別でき、各プロセッサ（ｘ
n-1，…，ｘ0）が実装モジュール（ｘn-1，…，ｘm）に
含まれる、２n-m個の実装モジュールと、（ｃ）前記２n
個のプロセッサを相互接続するＨｄＢ相互接続網とを備
える。
【００２９】この新型のＨＳＥ網は、周知のシャフル交
換網に基づく階層構造であり、新型のＨｄＢ網は、周知
のde Bruijn網に基づく階層構造である。これらの新型
網は、ピン制限が存在する時に昇順アルゴリズムまたは
降順アルゴリズムを実施する際の性能向上を実現する。
【００３０】階層の各段は、実装の１段（たとえば、チ
ップ・レベル、基板レベルまたはラック・レベル）に対
応する。これらは、階層的な性質を有するので、複数の
同一の構成要素（チップ、基板、ラックなど）に分割す
ることができる。これら同一構成要素の設計は、並列計
算機内のプロセッサ数に依存せず、したがって、これら
を組み合わせて任意の大きさの網を形成することができ
る。また、階層の各段が実装の１段に対応するので、階
層の各段での接続の幅を、対応する実装段によって課さ
れる制約に合致させることができる。したがって、これ
らの新型網は、広範囲のアルゴリズムを実施するのに効
率的である。
【００３１】たとえば、本発明の他の態様によれば、Ｈ
ＳＥコンピュータ上で昇順アルゴリズムを実施する方法
が記述される。具体的に言うと、本発明の１実施例は、
それぞれが０ないし２n−１（ただしｎは整数）の範囲
の一意的な整数の識別子（ＩＤ）を有する２n個のデー
タ項目を有し、０ないしｎ−１のｎ個の段階を有し、各
段階ｉ（ただし０≦ｉ≦ｎ−１）で、２進表現のビット
位置ｉだけが異なるＩＤを持つデータ項目の各対に対し
て処理を行う昇順アルゴリズムを、それぞれが０ないし
２n−１の範囲の一意的なＩＤを有する２n個のプロセッ
サを有し、２n-m個（ただしｍは整数でｎ＞ｍ）の実装
モジュールを含む、階層シャフル・エクスチェンジ（Ｈ
ＳＥ）コンピュータ上で実施する方法であって、（ａ）
各データ項目ｊ（ただしｊは０ないし２n−１の範囲の
整数）をプロセッサｊに記憶するステップと、（ｂ）前
記ＨＳＥコンピュータのエクスチェンジ接続と局所逆シ
ャフル接続とを使用して、前記昇順アルゴリズムの最初
のｍ個の段階を実行するステップと、（ｃ）前記ＨＳＥ
コンピュータの大域逆シャフル接続を使用して、データ
項目の位置変更を行うステップと、（ｄ）昇順アルゴリ
ズムのｎ個の段階がすべて完了するまで、ステップ
（ｂ）および（ｃ）を繰り返すステップとを含む方法を
対象とする。
【００３２】本発明のさらに別の諸態様は、ＨｄＢコン
ピュータ上で昇順アルゴリズムを実施する方法と、ＨＳ
Ｅコンピュータ上とＨｄＢコンピュータ上の両方で降順
アルゴリズムを実施する方法を対象とする。
【００３３】さらに、本発明では、前述のＨＳＥ網およ
びＨｄＢ網ならびにＨＳＥコンピュータおよびＨｄＢコ
ンピュータの代替実施例を企図している。具体的に言う
と、本発明では、マージＨＳＥ（ＭＨＳＥ）網もしくは
マージＨｄＢ（ＭＨｄＢ）網、またはマージＨＳＥ（Ｍ
ＨＳＥ）コンピュータもしくはマージＨｄＢ（ＭＨｄ
Ｂ）コンピュータと称するものを企図している。ＭＨＳ
Ｅ網およびＭＨｄＢ網（およびコンピュータ）は、プロ
セッサ間で使用される大域通信リンク（以下で詳細に説
明する）が上記のＨＳＥアーキテクチャおよびＨｄＢア
ーキテクチャと異なるが、それ以外の点では、昇順形お
よび降順形のアルゴリズムのサポートなどに関する限
り、上記のＨＳＥ網およびＨｄＢ網（またはコンピュー
タ）と同様に機能する。
【００３４】
【実施例】図面を参照し、本発明の詳細な説明に進む前
に、本明細書で使用する表記法、本明細書で論じる例示
的アーキテクチャ・モデルに関する仮定、ならびに昇順
アルゴリズムおよび降順アルゴリズムとして知られる周
知の種類の並列アルゴリズム（前掲のプレパラータ他の
論文に詳細に記載されている）の簡単な概括を示すこと
にする。
【００３５】また、完全を期して、ＨＳＥ網とＨｄＢ網
の性能を、周知のハイパーキューブ網、２次元網目網、
３次元網目網、シャフル・エクスチェンジ網、多層式シ
ャフル・エクスチェンジ網、ハイパーネット網、de Bru
ijn網およびキューブ接続サイクル網と、以下で（本発
明の意図する網とコンピュータの説明の後に）比較す
る。ＨＳＥ網とＨｄＢ網（ならびに、これらの網を中心
にして構築されるすべてのコンピュータ）は、規則性、
スケーラビリティおよび性能の点で有利であることを示
す。
【００３６】表記法に関しては、整数ｘのｎビット２進
表現を（ｘn-1，ｘn-2，…，ｘ0）と記し、ｘの第ｉビ
ット（０≦ｉ＜ｎ）をｘiと記す。ｘの第ｉビットの補
数をｃ［ｘi］と記す。
【００３７】アーキテクチャ・モデルに関しては、本明
細書に記載の並列コンピュータは、各プロセッサが関連
局所記憶装置を有し、大域共用記憶装置が存在しない、
分散記憶アーキテクチャである。特定のプロセッサ対
が、直接通信リンクによって接続される。すべての通信
リンクは、両方向半二重式（１度に１方向にのみ送信可
能）であると仮定する。
【００３８】本明細書で特記しない限り、各プロセッサ
は、１度に１本の通信リンクのみを介してデータを送信
可能であると仮定する。例示的なものにすぎないが、こ
れらのプロセッサは、同期ＳＩＭＤ方式で動作するもの
と仮定する。
【００３９】以下で論じるアルゴリズムは、上記のよう
に、昇順（Ascend）アルゴリズムおよび降順（Descen
d）アルゴリズムとして知られる種類の並列アルゴリズ
ムに属する。前述のＦＦＴ、Benesルーティングおよび
バイトニック・ソートを含む多数の並列アルゴリズム
（ならびに、行列転置、モノトニック・ルーティング、
シェアソート、並列前置演算など他のアルゴリズム）
は、昇順アルゴリズムまたは降順アルゴリズムのどちら
かであるか、あるいは昇順アルゴリズムまたは降順アル
ゴリズムであるサブルーチンだけから構成される。これ
らの動作はすべて周知であり、本発明自体の一部を構成
しない。
【００４０】昇順アルゴリズムでは、データ項目が、長
さＶの線形アレイを形成するものと見なされる。昇順ア
ルゴリズムは、０からｌｏｇ2Ｖ−１までの番号を付け
たｌｏｇ2Ｖ個の段階からなる。各段階ｉの間に、アレ
イ内でビット位置ｉが異なる位置にあるデータ項目の各
対に対して処理が行われる。したがって、段階０では、
偶数番目のアレイ位置にあるデータ項目とその直後のデ
ータ項目がそれぞれ処理される。後続の段階では、対の
項目同士の間隔を次々に広げながらデータ項目の対を処
理する。この処理の性質は、実施しようとする特定の昇
順アルゴリズムに依存する。降順アルゴリズムは、ビッ
ト位置が逆の順序で、すなわち最上位から最下位へ処理
される点を除き、同じである。
【００４１】昇順アルゴリズムと降順アルゴリズムは、
ごく自然にハイパーキューブ・コンピュータに写像され
る。Ｎ＝２n個のプロセッサを有するハイパーキューブ
・コンピュータでは、プロセッサに０からＮ−１までの
番号がつけられる。各プロセッサｘは、（ｘn-1，…，
ｘi+1，ｃ［ｘi］，ｘi-1，…，ｘ0）（ただし０≦ｉ≦
ｎ−１）の形のｎ個のプロセッサに接続される。したが
って、Ｖ＝Ｎ個のデータ項目を有する昇順アルゴリズム
は、各項目ｘをプロセッサｘに記憶させることによって
ハイパーキューブ上で実施できる。この記憶パターンを
使用すると、すべての通信が、通信リンクによって接続
されたプロセッサ対の間で行われる。
【００４２】昇順アルゴリズムと降順アルゴリズムが、
シャフル・エクスチェンジ網、de Bruijn網およびキュ
ーブ接続サイクル網にも効率的に写像されることは、当
業者には周知である。シャフル・エクスチェンジ網およ
びde Bruijn網では、まずアレイ内でビット０が異なる
位置にあるデータ項目同士を対にする。ビット位置０に
対する処理の実行後に、データ項目を置換し、ビット位
置１に従ってデータ項目を対にする。ビット位置１に対
する処理の完了後に、データ項目をもう一度置換し、ビ
ット位置２に従ってデータ項目を対にする。すべてのビ
ット位置に対する処理が完了するまで、このパターンを
繰り返す。
【００４３】キューブ接続サイクル網は、各段で異なる
ビット位置に従ってデータ項目を対にする、段式の（le
veled）網である。処理は、ビット位置０に関連する段
でのビット位置０に対する計算の実行から始まる。その
後、この段からのデータを次の段にシフトし、ビット位
置１に対する処理を実行する。この網の異なる段で始ま
るデータ項目は、同一シーケンスの段を介してパイプラ
イン式にシフトされる。
【００４４】本明細書で使用する表記法と、本発明の説
明で使用するアーキテクチャ・モデルに関連する仮定を
説明し、本発明によってサポートされる有用な種類のア
ルゴリズムの概括を終えたので、次に図面を参照して、
前に要約した本発明の様々な態様の詳細を説明する。
【００４５】まず、２つの新規の２段（two-level）階
層形コンピュータを説明する。それぞれの説明は、図１
および図４に示す例を参照して要約する。図からわかる
ように、これらのコンピュータは、新規の網によって相
互接続された１組のプロセッサを含む。
【００４６】新規の並列コンピュータである２段ＨＳＥ
コンピュータと２段ＨｄＢコンピュータは、それぞれ局
所接続と大域接続の２種類の接続を有する。３個以上の
段を有するＨＳＥコンピュータとＨｄＢコンピュータ
も、本明細書に記述する。
【００４７】この２段コンピュータは、実装階層の単一
の段（チップ・レベルや基板レベルなど）に厳密なピン
制限を課す実装技術用に設計されている。議論を簡単に
するため、実装階層のこのクリティカルなレベルでの実
装の単位を本明細書では「チップ」と称するが、この用
語「チップ」は、本明細書で実装モジュールと称するこ
ともある任意の実装単位を指すことに特に留意された
い。
【００４８】すべての局所接続は、単一のチップ内に留
まり、その結果、幅広の接続とすることができる。局所
接続は、１チップ上のプロセッサ群のシャフル交換網ま
たはde Bruijn網を形成する。大域接続は、（前述の局
所接続に比べて）相対的に狭い接続であり、チップ間に
またがることができる。
【００４９】昇順アルゴリズムを実施するには、まず局
所接続を使用して、そのチップにとって局所的なビット
位置の処理を実行する。その後、大域接続を使用して、
新しい１組のビット位置をそのチップに取り込む。すべ
てのビット位置が処理されるまで、この局所接続と大域
接続を交互に使用する処理を繰り返す。より狭い大域接
続の使用頻度が低いので、効率的な実施が得られる。こ
のコンピュータのより形式的な説明とその使用法を、以
下に示す。
【００５０】まず、２段ＨＳＥコンピュータを説明す
る。
【００５１】２段ＨＳＥコンピュータ ２ＨＳＥ（ｎ，
ｍ，ａ，ｂ）（ただしｎ＞ｍでａ≦ｂ）は、０，…，２
n−１の番号をつけた２n個のプロセッサを含んでいる。
これらのプロセッサは、１チップあたりプロセッサ２m
個ずつ、２n-m個のチップ上に置かれる。チップには
０，…，２n-m−１の番号がつけてあり、各プロセッサ
（ｘn-1，…，ｘ0）がチップ（ｘn-1，…，ｘm）上に置
かれる。したがって、プロセッサ番号（プロセッサＩ
Ｄ）の最初のｎ−ｍビットが、そのチップ番号（チップ
ＩＤ）を指定し、残りのｍビットが、そのチップ内での
そのプロセッサの役割を指定する。
【００５２】各プロセッサは、５本の両方向通信リンク
を有する。各プロセッサ（ｘn-1，…，ｘ0）は、エクス
チェンジ接続を介してプロセッサ（ｘn-1，…，ｘ1，ｃ
［ｘ0］）に、局所シャフル接続を介してプロセッサ
（ｘn-1，…，ｘm，ｘm-2，…，ｘ0，ｘm-1）に、局所
逆シャフル接続を介してプロセッサ（ｘn-1，…，ｘm，
ｘ0，ｘm-1，…，ｘ1）にそれぞれ接続される。これら
３種の接続をすべて、本明細書では「局所接続」と称す
る。
【００５３】また、各プロセッサ（ｘn-1，…，ｘ0）
は、大域シャフル接続を介してプロセッサ（ｘn-m-1，
…，ｘ0，ｘn-1，…，ｘn-m）に、大域逆シャフル接続
を介してプロセッサ（ｘm-1，…，ｘ0，ｘn-1，…，
ｘm）にそれぞれ接続される。これら２種の接続を、本
明細書では「大域接続」と称する。大域接続はすべてａ
ビット幅であり、局所接続はすべてｂビット幅である。
【００５４】この２段網は、局所接続の組と大域接続の
組からなる。
【００５５】Ｎ＝２n個のデータ項目を有する昇順アル
ゴリズムを実施するには、まずエクスチェンジ接続を使
用して、ビット位置０の計算を実行する。次に、各デー
タ項目をその局所逆シャフル接続に沿って送る。この時
点で、各データ項目（ｘn-1，…，ｘ0）はプロセッサ
（ｘn-1，…，ｘm，ｘ0，ｘm-1，…，ｘ1）に記憶され
る。次に、エクスチェンジ接続を使用して、ビット位置
１の計算を実行する。その後、各データ項目をその局所
逆シャフル接続に沿って送る。この時点で、各データ項
目（ｘn-1，…，ｘ0）はプロセッサ（ｘn-1，…，ｘm，
ｘ1，ｘ0，ｘm-1，…，ｘ2）に記憶される。最下位ｍビ
ットの処理を実行するため、エクスチェンジ接続と局所
逆シャフル接続を使用するこの処理をｍ回繰り返す。こ
の手順の後に、各データ項目（ｘn-1，…，ｘ0）をもう
一度プロセッサ（ｘn-1，…，ｘ0）に記憶させる。
【００５６】次に、各データ項目をその大域逆シャフル
接続に沿って送り、各データ項目（ｘn-1，…，ｘ0）を
プロセッサ（ｘm-1，…，ｘ0，ｘn-1，…，ｘm）に記憶
させる。その後、上記の手順を繰り返してｍ回の交換と
局所逆シャフルを実行する。これによって、ビット位置
ｍから２ｍ−１までの処理が完了する。この時点で、各
データ項目（ｘn-1，…，ｘ0）をもう一度プロセッサ
（ｘm-1，…，ｘ0，ｘn-1，…，ｘm）に記憶させる。次
に、各データ項目をその大域逆シャフル接続に沿って送
り、各データ項目（ｘn-1，…，ｘ0）をプロセッサ（ｘ
2m-1，…，ｘ0，ｘn-1，…，ｘ2m）に記憶させる。その
後、エクスチェンジ接続と局所逆シャフル接続を使用し
て、ビット位置２ｍから３ｍ−１までの処理を実行す
る。大域逆シャフル接続を使用して各チップにとって局
所的な新しい１組のｍビットを置き、その後、ｎビット
がすべて処理されるまで、エクスチェンジ接続と局所逆
シャフル接続を使用してこれらｍビットの処理を実行す
るというこの処理を繰り返す。
【００５７】ｎがｍの倍数である時、この手順の結果、
各データ項目（ｘn-1，…，ｘ0）はその元のプロセッサ
（ｘn-1，…，ｘ0）に記憶されている。たとえば、表１
は、ｎ＝９でｍ＝３の時に昇順アルゴリズムを２段ＨＳ
Ｅ網上で実施する方法を示す。第１列は、このアルゴリ
ズムの開始時と、その後の各局所逆シャフル動作または
大域逆シャフル動作の時点で、どのプロセッサが任意の
データ項目（ｘ8，…，ｘ0）を保持するのかを示す。第
１列の各項目に対応する第２列の項目は、どのビット位
置が処理されるのかを示す。
【００５８】
【表１】
【００５９】ｎがｍの倍数でない時は、上記の手順によ
って各データ項目がその元の位置に戻されることはな
い。その結果、局所シャフル動作または局所逆シャフル
動作のシーケンスを実行した後に、大域シャフル動作の
シーケンスを実行しなければならない。たとえば、表２
は、ｎ＝８でｍ＝３の時に２段ＨＳＥ網上で昇順アルゴ
リズムを実施する方法を示す。ビット７の処理に続い
て、１回の局所シャフル動作と２回の大域シャフル動作
を実行して、各データ項目をその元の位置に戻している
ことに留意されたい。一般に、局所シャフル動作または
局所逆シャフル動作とその後に続く大域シャフル動作か
らなるシーケンスのうち、データ項目を元の位置に戻す
最短のシーケンスが実行される。降順アルゴリズムは、
昇順アルゴリズムと同じ方式で実施されるが、その動作
は逆の順序で実行される。
【００６０】
【表２】
【００６１】図１は、８個のプロセッサ（２n個、ただ
しｎ＝３)を含む２段（すなわち、ｍ＝２の実装段）Ｈ
ＳＥコンピュータの例を示す図である。２つの段は、図
１のチップ０およびチップ１によって示され、８個のプ
ロセッサは、プロセッサ０００〜１１１（２進数）すな
わちプロセッサ０〜７（１０進数）として示される。し
たがって、各プロセッサがそれぞれ、０から２n−１ま
での範囲の整数のｎビット（すなわち３ビット）表現
（すなわち、０００、００１、０１０、０１１、１０
０、１０１、１１０または１１１）で一意に定義できる
ことが判る。さらに、図１を参照すると、２n-m個の実
装モジュール（ここでは、図１に示した２個のチップ）
がそれぞれ、０から２n-m−１までの範囲の整数の（ｎ
−ｍ）ビット（１ビット）表現（すなわち０または１）
によって識別できることが判る。また、各プロセッサ
（ｘn-1，…，ｘ0）が実装モジュール（ｘn-1，…，
ｘm）に含まれる。すなわち、図示の例では、プロセッ
サ０００、００１、０１０、０１１が、実装モジュール
（チップ）０に含まれ、プロセッサ１００、１０１、１
１０、１１１が実装モジュール（チップ）１に含まれ
る。
【００６２】図１に示した２n個のプロセッサを相互接
続する網は、ＨＳＥ相互接続網である。したがって、た
とえば、プロセッサ１１０は、図１に示したＨＳＥ網
（上の定義に従う）を介して、局所リンク１８０によっ
てプロセッサ１１１に、局所リンク１８１によってプロ
セッサ１０１に、局所リンク１８２によってプロセッサ
１０１にそれぞれ接続されることがわかる。プロセッサ
１１０の例では、２本の局所リンクが同一のプロセッサ
（１０１）に向かっていることに留意されたい。
【００６３】また、この例のプロセッサ１１０に関連す
る２つの大域リンクは、（チップ０上の）プロセッサ０
１１へのリンク１８５と、やはりチップ１上のプロセッ
サ１０１へのリンク１８６である。図１に示したＨＳＥ
コンピュータ内の他の局所接続と大域接続もすべて、前
に示した２段ＨＳＥコンピュータおよび２段ＨＳＥ網の
定義によるものである。
【００６４】図２は、図１に示した例示のＨＳＥコンピ
ュータなどのＨＳＥコンピュータ上で昇順アルゴリズム
を実施するための、本発明で企図する方法の１組のステ
ップを表す流れ図である。
【００６５】具体的に言うと、図２は、それぞれ０から
２n−１まで（ただしｎは整数）の範囲の一意な整数の
ＩＤを有する２n個のデータ項目を有し、０からｎ−１
までのｎ個の段階を有し、各段階ｉ（ただし０≦ｉ≦ｎ
−１）で、２進表現のビット位置ｉだけが異なるＩＤを
有するデータ項目の各対に対して処理を行う、昇順アル
ゴリズムを、それぞれ０から２n−１までの範囲の一意
なＩＤを有する２n個のプロセッサを有し、２n-m個（た
だしｍは整数でｎ＞ｍ）の実装モジュールを含む、階層
シャフル交換（ＨＳＥ）コンピュータ上で実施する方法
であって、（ａ）各データ項目ｊ（ただしｊは０から２
n−１までの範囲の整数）をプロセッサｊに記憶させる
ステップ（図２のブロック２１０）と、（ｂ）前記ＨＳ
Ｅコンピュータの交換接続と局所逆シャフル接続とを使
用して、前記昇順アルゴリズムの最初のｍ個の段階を実
行するステップ（図２のブロック２２０）と、（ｃ）前
記ＨＳＥコンピュータの大域逆シャフル接続を使用し
て、データ項目の位置変更を行うステップ（図２のブロ
ック２３０に示す）と、（ｄ）昇順アルゴリズムのｎ個
の段階がすべて完了するまで、ステップ（ｂ）および
（ｃ）を繰り返すステップ（図２のブロック２４０）と
を含む方法の主要なステップをまとめた図である。
【００６６】図３は、図１に示した例示のＨＳＥコンピ
ュータなどのＨＳＥコンピュータ上で降順アルゴリズム
を実施するための、本発明で企図する方法の１組のステ
ップを表す流れ図である。
【００６７】具体的に言うと、図３は、それぞれ０から
２n−１まで（ただしｎは整数）の範囲の一意な整数の
ＩＤを有する２n個のデータ項目を有し、０からｎ−１
までのｎ個の段階を有し、各段階ｉ（ただし０≦ｉ≦ｎ
−１）で、２進表現のビット位置ｉだけが異なるＩＤを
有するデータ項目の各対に対して処理を行う、昇順アル
ゴリズムを、それぞれ０から２n−１までの範囲の一意
なＩＤを有する２n個のプロセッサを有し、２n-m個（た
だしｍは整数でｎ＞ｍ）の実装モジュールを含む、ＨＳ
Ｅコンピュータ上で実施する方法であって、（ａ）各デ
ータ項目ｊ（ただしｊは０から２n−１までの範囲の整
数）をプロセッサｊに記憶させるステップ（図３のブロ
ック３１０）と、（ｂ）前記ＨＳＥコンピュータの大域
シャフル接続を使用して、データ項目の位置変更を行う
ステップ（図３のブロック３２０）と、（ｃ）前記ＨＳ
Ｅコンピュータの局所シャフル接続と交換接続とを使用
して、前記降順アルゴリズムの段階ｎ−１から段階ｎ−
ｍまでを実行するステップ（図３のブロック３３０）
と、（ｄ）降順アルゴリズムのｎ個の段階がすべて完了
するまで、ステップ（ｂ）および（ｃ）を繰り返すステ
ップ（図３のブロック３４０）とを含む方法の主要なス
テップをまとめた図である。
【００６８】次に、２段ＨｄＢコンピュータを説明す
る。
【００６９】２段ＨｄＢコンピュータ、２ＨｄＢ（ｎ，
ｍ，ａ，ｂ）（ただしｎ＞ｍでａ≦ｂ）は、０，…，２
n−１の番号をつけた２n個のプロセッサからなる。これ
らのプロセッサは、１チップあたりプロセッサ２m個ず
つ、２n-m個のチップ上に置かれる。チップには０，
…，２n-m−１の番号がつけてあり、各プロセッサ（ｘ
n-1，…，ｘ0）がチップ（ｘn-1，…，ｘm）上に置かれ
る。したがって、プロセッサ番号の最初のｎ−ｍビット
はそのチップ番号を指定し、残りのｍビットはそのチッ
プ内でのそのプロセッサの役割を指定する。
【００７０】各プロセッサは、８本の両方向通信リンク
を有する。各プロセッサ（ｘn-1，…，ｘ0）は、局所シ
ャフル置換０接続を介してプロセッサ（ｘn-1，…，
ｘm，ｘm-2，…，ｘ0，０）に、局所シャフル置換１接
続を介してプロセッサ（ｘn-1，…，ｘm，ｘm-2，…，
ｘ0，１）に、局所逆シャフル置換０接続を介してプロ
セッサ（ｘn-1，…，ｘm，０，ｘm-1，…，ｘ1）に、局
所逆シャフル置換１接続を介してプロセッサ（ｘn-1，
…，ｘm，１，ｘm-1，…，ｘ1）にそれぞれ接続され
る。これら４種の接続を局所接続と総称する。局所シャ
フル置換０接続と局所シャフル置換１接続を局所シャフ
ル接続と称し、局所逆シャフル置換０接続と局所逆シャ
フル置換１接続を局所逆シャフル接続と称する。また、
各プロセッサ（ｘn-1，…，ｘ0）は、大域シャフル置換
０接続を介してプロセッサ（ｘn-m-2，…，ｘ0，０，ｘ
n-1，…，ｘn-m）に、大域シャフル置換１接続を介して
プロセッサ（ｘn-m-2，…，ｘ0，１，ｘn-1，…，
ｘn-m）に、大域逆シャフル置換０接続を介してプロセ
ッサ（ｘm-1，…，ｘ0，０，ｘn-1，…，ｘm+1）に、大
域逆シャフル置換１接続を介してプロセッサ（ｘm-1，
…，ｘ0，１，ｘn-1，…，ｘm+1）にそれぞれ接続され
る。これら４種の接続を大域接続と総称する。大域シャ
フル置換０接続と大域シャフル置換１接続を大域シャフ
ル接続と称し、大域逆シャフル置換０接続と大域逆シャ
フル置換１接続を大域逆シャフル接続と称する。大域接
続はすべてａビット幅であり、局所接続はすべてｂビッ
ト幅である。
【００７１】シャフル・エクスチェンジ・コンピュータ
および２段ＨＳＥコンピュータでは、１プロセッサあた
り１データ項目を有する昇順アルゴリズムが自然に実施
されるが、de Bruijnコンピュータと２段ＨｄＢコンピ
ュータでは、１プロセッサあたり２データ項目を有する
昇順アルゴリズムが自然に実施される。各プロセッサ
は、０と１の番号をつけた２つのメモリ位置を有し、こ
のメモリ位置に、そのプロセッサのデータ項目の対が記
憶される。２Ｎ＝２n+1個のデータ項目を有する昇順ア
ルゴリズムをＮ＝２n個のプロセッサを有する２段Ｈｄ
Ｂ網上で実施するには、まず、各データ項目（ｘn，
…，ｘ0）をプロセッサ（ｘn，…，ｘ1）のメモリ位置
ｘ0に記憶させる。この昇順アルゴリズムは、ビット位
置０の計算を実行するために各プロセッサ内のデータ項
目の対にアクセスすることから始まる。このステップに
は通信が不要であることに留意されたい。
【００７２】次に、メモリ位置０の各データ項目をその
局所逆シャフル置換０接続に沿って送り、メモリ位置１
の各データ項目をその局所逆シャフル置換１接続に沿っ
て送る。この時点で、各データ項目（ｘn，…，ｘ0）が
プロセッサ（ｘn，…，ｘm+1，ｘ 0，ｘm，…，ｘ2）の
メモリ位置ｘ1に記憶される。次に、各プロセッサにと
って局所的なデータ項目の対にアクセスして、ビット位
置１の計算を実行する。その後、各データ項目（ｘn，
…，ｘ0）をプロセッサ（ｘn，…，ｘm+1，ｘ1，ｘ0，
ｘm，…，ｘ3）のメモリ位置ｘ2に置くために、もう一
度局所逆シャフル置換接続を使用する。最下位ｍ＋１ビ
ットの処理を実行するため、この局所逆シャフル置換接
続を使用する処理をｍ＋１回繰り返す。この手順の後、
各データ項目（ｘn，…，ｘ0）はもう一度プロセッサ
（ｘn，…，ｘ1）のメモリ位置ｘ0に記憶される。
【００７３】次に、メモリ位置０の各データ項目をその
大域逆シャフル置換０接続に沿って送り、メモリ位置１
の各データ項目をその大域逆シャフル置換１接続に沿っ
て送る。この時点で、各データ項目（ｘn，…，ｘ0）が
プロセッサ（ｘm，…，ｘ0，ｘn，…，ｘm+2）のメモリ
位置ｘm+1に記憶される。その後、ｍ＋１回の局所逆シ
ャフル置換を実行する上記の手順を繰り返す。これによ
って、ビット位置ｍ＋１から２ｍ＋１までの処理が完了
する。この時点で、各データ項目（ｘn，…，ｘ0）はも
う一度プロセッサ（ｘm，…，ｘ0，ｘn，…，ｘm+2）の
メモリ位置ｘm+1に記憶される。
【００７４】次に、各データ項目をそれに対応する大域
逆シャフル置換接続に沿って送り、各データ項目
（ｘn，…，ｘ0）をプロセッサ（ｘ2m+1，…，ｘ0，
ｘn，…，ｘ2m+3）のメモリ位置ｘ2m+2に記憶させる。
その後、ビット位置２ｍ＋２から３ｍ＋１までの処理を
実行するため、ｍ＋１回の逆シャフル置換を実行する上
記の手順を繰り返す。大域逆シャフル置換接続を使用し
て各チップにとって局所的なｍ＋１ビットの新しい組を
置き、その後、局所逆シャフル置換接続を使用してこれ
らｍ＋１ビットの処理を実行するというこの処理を、ｎ
ビットのすべてが処理されるまで繰り返す。
【００７５】ｎ＋１がｍ＋１の倍数の時、この手順の結
果、各データ項目（ｘn，…，ｘ0）はプロセッサ
（ｘn，…，ｘ1）の元のメモリ位置x0に記憶されてい
る。たとえば、表３は、ｎ＝８でｍ＝２の時に昇順アル
ゴリズムを２段ＨｄＢ網上で実施する方法を示す。最初
の２列は、このアルゴリズムの開始時とその後の各通信
動作の時点での任意のデータ項目（ｘ8，…，ｘ0）のプ
ロセッサとメモリ位置を示す。最初の２列の各項目に対
応する３列目の項目は、どのビット位置が処理されるの
かを示す。
【００７６】
【表３】
【００７７】ｎ＋１がｍ＋１の倍数でない時は、上記の
手順によって各データ項目がその元の位置に戻されるこ
とはない。その結果、局所シャフル置換動作または局所
逆シャフル置換動作のシーケンスを実行した後に、大域
シャフル置換動作のシーケンスを実行しなければならな
い。たとえば、表４は、ｎ＝７でｍ＝２の時に２段Ｈｄ
Ｂ網上で昇順アルゴリズムを実施する方法を示す。ビッ
ト７の処理に続いて、１回の局所シャフル置換動作と２
回の大域シャフル置換動作を実行して、各データ項目を
その元の位置に戻していることに留意されたい。降順ア
ルゴリズムは、昇順アルゴリズムと同じ方式で実施され
るが、その動作は逆の順序で実行される。
【００７８】
【表４】
【００７９】図４は、８個のプロセッサ（２n、ただし
ｎ＝３）を含む２段（すなわち、ｍ＝２の実装段）Ｈｄ
Ｂコンピュータの例を示す図である。２つの段は、図４
のチップ０およびチップ１によって示され、８個のプロ
セッサは、やはりプロセッサ０００〜１１１（２進数）
すなわちプロセッサ０〜７（１０進数）として示され
る。したがって、各プロセッサを０から２n−１までの
範囲の整数のｎビット（すなわち３ビット）表現（すな
わち、０００、００１、０１０、０１１、１００、１０
１、１１０または１１１）によって一意に定義できるこ
とが判る。さらに、図４を参照すると、２n-m個の実装
モジュール（たとえば、図４に示した２つのチップ）が
それぞれ０から２n-m−１までの範囲の整数のｎ−ｍビ
ット（１ビット）表現（すなわち０または１）によって
識別できることが判る。また、各プロセッサ（ｘn-1，
…，ｘ0）が実装モジュール（ｘn-1，…，ｘm）に含ま
れる、すなわち、図示の例では、プロセッサ０００、０
０１、０１０、０１１が実装モジュール（チップ）０に
含まれ、プロセッサ１００、１０１、１１０、１１１が
実装モジュール（チップ）１に含まれる。
【００８０】図４に示した２n個のプロセッサを相互接
続する網は、前に定義したＨｄＢ相互接続網である。し
たがって、たとえば、プロセッサ１１０は、図４に示し
たＨｄＢ網を介して、局所接続（リンク）４８０によっ
てプロセッサ１００に、局所接続４８１によってプロセ
ッサ１０１に、局所接続４８２によってプロセッサ１０
１に、局所接続４８３によってプロセッサ１１１にそれ
ぞれ接続されることがわかる。プロセッサ１１０の例で
は、４本の局所リンクのうちの２本が同一のプロセッサ
（１０１）に向かっていることに留意されたい。
【００８１】この例のプロセッサ１１０に関連する４本
の大域リンクは、リンク４８５〜４８８であり、これら
のリンクはそれぞれ、（チップ１上の）プロセッサ１１
０を、チップ０上のプロセッサ０１１と、チップ１上の
プロセッサ１００、１０１、１１１に接続する。図４に
示したＨｄＢコンピュータ内の他の局所接続と大域接続
もすべて、前に示した２段ＨｄＢコンピュータおよび２
段ＨｄＢ網の定義によるものである。
【００８２】図５は、図４に示した例示のＨｄＢコンピ
ュータなどのＨｄＢコンピュータ上で昇順アルゴリズム
を実施するための、本発明で企図する方法の１組のステ
ップを表す流れ図である。
【００８３】具体的に言うと、図５は、それぞれ０から
２n+1−１まで（ただしｎは整数）の範囲の一意な整数
のＩＤを有する２n+1個のデータ項目を有し、０からｎ
までのｎ＋１個の段階を有し、各段階ｉ（ただし０≦ｉ
≦ｎ）で、２進表現のビット位置ｉだけが異なるＩＤを
有するデータ項目の各対に対して処理を行う、昇順アル
ゴリズムを、それぞれ０から２n−１までの範囲の一意
なＩＤを有する２n個のプロセッサを有し、２n-m個（た
だしｍは整数でｎ＞ｍ）の実装モジュールを含む、階層
de Bruijn（ＨｄＢ）コンピュータ上で実施する方法で
あって、（ａ）各データ項目ｊ（ただしｊは０から２
n+1−１までの範囲の整数）を、ｊ／２以下で最大の整
数であるＩＤを有するプロセッサに記憶させるステップ
（図５のブロック５１０）と、（ｂ）前記ＨｄＢコンピ
ュータの局所逆シャフル置換接続を使用して、前記昇順
アルゴリズムの最初のｍ＋１段階を実行するステップ
（図５のブロック５２０）と、（ｃ）前記ＨｄＢコンピ
ュータの大域逆シャフル置換接続を使用して、データ項
目の位置変更を行うステップ（図５のブロック５３０）
と、（ｄ）昇順アルゴリズムのｎ＋１段階がすべて完了
するまで、ステップ（ｂ）および（ｃ）を繰り返すステ
ップ（図５のブロック５４０）とを含む方法の主要なス
テップをまとめた図である。
【００８４】図６は、図４に示した例示のＨｄＢコンピ
ュータなどのＨｄＢコンピュータ上で降順アルゴリズム
を実施するための、本発明で企図する方法の１組のステ
ップを表す流れ図である。
【００８５】具体的に言うと、図６は、それぞれ０から
２n+1−１まで（ただしｎは整数）の範囲の一意な整数
のＩＤを有する２n+1個のデータ項目を有し、０からｎ
までのｎ＋１個の段階を有し、各段階ｉ（ただし０≦ｉ
≦ｎ）で、２進表現のビット位置ｉだけが異なるＩＤを
有するデータ項目の各対に対して処理を行う、降順アル
ゴリズムを、それぞれ０から２n−１までの範囲の一意
なＩＤを有する２n個のプロセッサを有し、２n-m個（た
だしｍは整数でｎ＞ｍ）の実装モジュールを含む、階層
de Bruijn（ＨｄＢ）コンピュータ上で実施する方法で
あって、（ａ）各データ項目ｊ（ただしｊは０から２
n+1−１までの範囲の整数）を、ｊ／２以下で最大の整
数であるＩＤを有するプロセッサに記憶させるステップ
（図６のブロック６１０）と、（ｂ）前記ＨｄＢコンピ
ュータの大域シャフル置換接続を使用して、データ項目
の位置変更を行うステップ（図６のブロック６２０）
と、（ｃ）前記ＨｄＢコンピュータの局所シャフル置換
接続を使用して、前記降順アルゴリズムの段階ｎから段
階ｎ−ｍまでを実行するステップ（図６のブロック６３
０）と、（ｄ）降順アルゴリズムのｎ＋１段階がすべて
完了するまで、ステップ（ｂ）および（ｃ）を繰り返す
ステップ（図６のブロック６４０）とを含む方法の主要
なステップをまとめた図である。
【００８６】本発明のもう１つの態様によれば、上述の
２段ＨＳＥコンピュータ（および網）と２段ＨｄＢコン
ピュータ（および網）を拡張して３個以上の段を有する
アーキテクチャにし、特定の状況でより効率的に動作さ
せることのできるわずかに変更されたコンピュータ（お
よび網）にすることができる。
【００８７】本発明で企図する３段アーキテクチャと、
そのｘ段アーキテクチャへの拡張をまず説明し、その
後、変更されたシステムを説明する。
【００８８】３段のＨＳＥコンピュータとＨｄＢコンピ
ュータ（およびそれらに含まれる網）は、２段の実装階
層に厳密なピン制限を課す実装技術用に設計されてい
る。議論を簡単にするため、以下では、実装階層のこの
クリティカルなレベルでの実装の単位をそれぞれ「チッ
プ」および「基板」と称するが、これらの用語は、任意
の実装単位を指すことに特に留意されたい。
【００８９】３段のシャフル交換コンピュータおよびde
Bruijnコンピュータは、３種類の接続、すなわち局所
接続、中間接続および大域接続を含んでいる。局所接続
は中間接続より幅広で、中間接続は大域接続より幅広で
ある。局所接続は同一チップ上のプロセッサを接続し、
中間接続は同一基板上の異なるチップ上のプロセッサを
接続するのに使用でき、大域接続は異なる基板上のプロ
セッサを接続するのに使用できる。
【００９０】３段ＨＳＥコンピュータの各基板上のプロ
セッサは、２段ＨＳＥ網を使用して接続される。３段Ｈ
ｄＢコンピュータの各基板上のプロセッサは、２段Ｈｄ
Ｂ網を使用して接続される。３段コンピュータ（網部
分）の中間接続と局所接続は、２段網の大域接続と局所
接続に対応する。３段コンピュータ（網部分）の大域接
続は、１チップあたりのプロセッサ数が３段コンピュー
タの１基板あたりのプロセッサ数と同数の、２段コンピ
ュータの大域接続と同一である。
【００９１】より形式的に言えば、３段ＨＳＥコンピュ
ータ ３ＨＳＥ（ｎ，ｍ，ｋ，ａ，ｂ，ｃ）（ただし、
ｎ＞ｍ＞ｋでａ≦ｂ≦ｃ）は、０，…，２n−１の番号
をつけた２n個のプロセッサからなる。これらのプロセ
ッサは、１チップあたり２k個ずつ、２n-k個のチップ上
に置かれる。チップには０，…，２n-k−１の番号がつ
けてあり、各プロセッサ（ｘn-1，…，ｘ0）がチップ
（ｘn-1，…，ｘk）上に置かれる。これらのチップは、
１基板あたり２m-k個ずつ、２n-m個の基板上に置かれ
る。基板には０，…，２n-m−１の番号がつけてあり、
各チップ（ｘn-k-1，…，ｘ0）が基板（ｘn-k-1，…，
ｘm-k）上に置かれる。したがって、プロセッサ番号の
最初のｎ−ｍビットはその基板の番号を指定し、次のｍ
−ｋビットは基板内のそのチップの番号を指定し、残り
のｋビットはそのチップ内でのプロセッサの役割を指定
する。
【００９２】３段ＨＳＥコンピュータ内の各プロセッサ
は、７本の両方向通信リンクを有する。各プロセッサ
（ｘn-1，…，ｘ0）は、それぞれｃビット幅の局所接続
を介して、プロセッサ（ｘn-1，…，ｘ1，ｃ
［ｘ0］）、（ｘn-1，…，ｘk，ｘk-2，…，ｘ0，
ｘk-1）および（ｘn-1，…，ｘk，ｘ0，ｘk-1，…，
ｘ1）に接続される。また、各プロセッサ（ｘn-1，…，
ｘ0）は、それぞれｂビット幅の中間接続を介して、プ
ロセッサ（ｘn-1，…，ｘm，ｘm-k-1，…，ｘ0，
ｘm-1，…，ｘm-k）および（ｘn-1，…，ｘm，ｘk-1，
…，ｘ0，ｘm-1，…，ｘk）に接続される。最後に、各
プロセッサ（ｘn-1，…，ｘ0）は、それぞれａビット幅
の大域接続を介して、プロセッサ（ｘn-m-1，…，ｘ0，
ｘn-1，…，ｘn-m）および（ｘm-1，…，ｘ0，ｘn-1，
…，ｘm）に接続される。
【００９３】３段ＨｄＢコンピュータ ３ＨｄＢ（ｎ，
ｍ，ｋ，ａ，ｂ，ｃ）（ただし、ｎ＞ｍ＞ｋでａ≦ｂ≦
ｃ）は、０，…，２n−１の番号をつけた２n個のプロセ
ッサからなる。これらのプロセッサは、上記の３段ＨＳ
Ｅ網と同じ規則に従って、１チップあたり２k個、１基
板あたり２m個置かれる。
【００９４】３段ＨｄＢコンピュータの各プロセッサ
は、１２本の両方向通信リンクを有する。各プロセッサ
（ｘn-1，…，ｘ0）は、それぞれｃビット幅の局所接続
を介して、プロセッサ（ｘn-1，…，ｘk，ｘk-2，…，
ｘ0，０）、（ｘn-1，…，ｘk，ｘk-2，…，ｘ0，
１）、（ｘn-1，…，ｘk，０，ｘk-1，…，ｘ1）および
（ｘn-1，…，ｘk，１，ｘk-1，…，ｘ1）に接続され
る。また、各プロセッサ（ｘn-1，…，ｘ0）は、それぞ
れｂビット幅の中間接続を介して、プロセッサ
（ｘn-1，…，ｘm，ｘm-k-2，…，ｘ0，０，ｘm-1，
…，ｘm-k）、（ｘn-1，…，ｘm，ｘm-k-2，…，ｘ0，
１，ｘm-1，…，ｘm-k）、（ｘn-1，…，ｘm，ｘk-1，
…，ｘ0，０，ｘm-1，…，ｘk+1）および（ｘn-1，…，
ｘm，ｘk-1，…，ｘ0，１，ｘm-1，…，ｘk+1）に接続
される。最後に、各プロセッサ（ｘn-1，…，ｘ0）は、
それぞれａビット幅の大域接続を介して、プロセッサ
（ｘn-m-2，…，ｘ0，０，ｘn-1，…，ｘn-m）、（ｘ
n-m-2，…，ｘ0，１，ｘn-1，…，ｘn-m）、（ｘm-1，
…，ｘ0，０，ｘn-1，…，ｘm+1）および（ｘm-1，…，
ｘ0，１，ｘn-1，…，ｘm+1）に接続される。
【００９５】昇順アルゴリズムを実施するには、これら
の３段コンピュータ上で、まず中間接続と局所接続を、
２段網であるかのように使用する。その後、大域接続を
使用して、新しい１組のビットを各基板に移動する。中
間接続と局所接続を使用して基板にとって局所的なビッ
トをすべて処理し、その後、大域接続を使用して新しい
１組のビット位置を各基板に移動するというこの処理
を、すべてのビット位置が処理されるまで繰り返す。
【００９６】上記の３段アーキテクチャに類似の、４個
以上の段を有する網とコンピュータを定義できること
は、当業者には容易に理解されよう。ｘ段を有する各コ
ンピュータは、ｘ−１段を有するコンピュータおよび網
と１組の大域接続からなる。これらの大域接続は、１チ
ップあたりのプロセッサ数が、ｘ段コンピュータの最高
段の１実装あたりのプロセッサ数と同数の、２段コンピ
ュータの大域接続と同一である。
【００９７】上で示したように、上述のコンピュータお
よび網に小さな変更を加えて、多くの場合にその性能を
向上させることができる。
【００９８】例として、２段ＨＳＥコンピュータが定義
され、ｎがｍの倍数であると仮定する。昇順アルゴリズ
ムをこのコンピュータ上で実施する際には、各大域逆シ
ャフル動作の前に局所逆シャフル動作を行う。この局所
逆シャフル動作の目的は、最下位ｍビットを元の順序に
戻すことだけである。大域接続によって局所逆シャフル
動作の後に大域逆シャフル動作を実行する場合には、こ
の局所逆シャフル動作を省略することができる。
【００９９】詳細に言うと、大域逆シャフル接続の代り
に、各プロセッサ（ｘn-1，…，ｘ0）からプロセッサ
（ｘ0，ｘm-1，…，ｘ1，ｘn-1，…，ｘm）に向かう接
続を使用する。同様に、大域シャフル接続の代りに、各
プロセッサ（ｘn-1，…，ｘ0）からプロセッサ（ｘ
n-m-1，…，ｘ0，ｘn-2，…，ｘm-n，ｘn-1）に向かう
接続を使用する。本明細書では、この結果得られるコン
ピュータをマージＨＳＥ（ＭＨＳＥ）コンピュータと称
する。同様の変更を２段ＨｄＢコンピュータに加えて、
マージＨｄＢ（ＭＨｄＢ）コンピュータを得ることがで
き、同様の変更を３個以上の段を有する階層形コンピュ
ータ（および網）に加えることもできる。
【０１００】前に示した目標をすべて満たす本発明の様
々な態様を説明し終えたので、前に示したように、完全
を期して、次に２段のＨＳＥトポロジおよびＨｄＢトポ
ロジと既知のトポロジの性能の比較を示す。
【０１０１】公正な比較を行うため、すべてのトポロジ
に共通な１組の実装制約が存在するものと仮定する。昇
順アルゴリズムの性能を示す。
【０１０２】前述のように、昇順アルゴリズムでは、ビ
ット位置が、最下位から最上位の順にアクセスされる。
ビット位置ごとに、所与のビット位置が異なる位置にあ
るデータ項目同士を対にする。その後、これらデータ項
目の各対に対して計算を行う。またこの例示の比較で
は、この計算で２つの値が生じ、したがって、両方向の
通信が必要であると仮定する。バイトニック・マージ、
ＦＦＴおよびBenesルーティングを含めて多くの昇順ア
ルゴリズムおよび降順アルゴリズムで実際にそうなる。
【０１０３】この昇順アルゴリズムは、Ｎ＝２n個の項
目からなるアレイに対して作用する。ほとんどのコンピ
ュータでは、各プロセッサに１つのデータ項目を記憶さ
せることによって、昇順アルゴリズムを実施している。
しかし、de BruijnコンピュータとＨｄＢコンピュータ
では、各プロセッサに１対のデータ項目を記憶させるこ
とによって昇順アルゴリズムを実施している。したがっ
て、de BruijnコンピュータとＨｄＢコンピュータはＮ
／２個のプロセッサしか含まず、残りのコンピュータ
は、それぞれＮ個のプロセッサを含むものと仮定する。
【０１０４】これらのコンピュータの通信時間を正規化
するため、de BruijnコンピュータとＨｄＢコンピュー
タの各プロセッサは同時に２つのデータ項目を送出で
き、他のコンピュータの各プロセッサは１回に１つのデ
ータ項目だけを送出できるものと仮定する。こう仮定す
ることによって、各コンピュータでＮ個のデータ項目を
すべて１回で送出できるようになる。
【０１０５】パラメータＭは、単一のチップ上に置くこ
とのできるプロセッサの最大数を表す。de Bruijnコン
ピュータ（網）とＨｄＢコンピュータ（網）を使用する
時には、各チップがＭ／２個のプロセッサを含むものと
仮定する。他のすべてのコンピュータでは、１チップあ
たりＭ個のプロセッサがあるものと仮定する。この仮定
によって、どの場合でもＮ／Ｍ個のチップからなる並列
コンピュータがもたらされる。
【０１０６】さらに、プロセッサは３２ビットのワード
・サイズを有し、チップ上の通信リンクはすべて３２ビ
ット幅であると仮定する。また、昇順アルゴリズムは、
３２ビットのデータ項目に対して作用すると仮定する。
パラメータＰは、通信リンクに使用できる１チップ当た
りの最大ピン数を表す。トポロジ依存のパラメータＱ
は、規則的なチップ設計であると仮定して、各チップか
ら出る通信リンクの数を表す。従属パラメータＷは、チ
ップ外リンクの幅を表す。Ｑ≦Ｐ／３２の時、Ｗ＝３２
である。Ｑ＞Ｐ／３２の時は、ＷはＰ／Ｑ以下の最大の
整数である。
【０１０７】多層式シャフル・エクスチェンジは、各チ
ップ上のサイズＭのシャフル・エクスチェンジ網と、１
サイクル内に接続される異なるチップ上の対応するプロ
セッサからなる。ハイパーネットは、各チップ上のサイ
ズＭのハイパーキューブと、最小数の階層接続段からな
る。完全な１組の階層接続によって与えられるサイズ以
外のサイズを有するハイパーネットは、前述のGhosh他
の論文に記載のとおり、不完全ハイパーネットとして構
成される。
【０１０８】これらの並列計算機はすべて、同期ＳＩＭ
Ｄ方式で動作するものと仮定する。ここでは通信に必要
な時間だけを検討する。というのは、計算の実行に必要
な時間は、すべてのトポロジで同じだからである。これ
らの時間を導出した方法の詳細を、以下で示す。
【０１０９】検討する最初の例は、Ｍ＝１６でＰ＝２５
６の時である（表５参照）。表５の各行に、異なるトポ
ロジ上で昇順アルゴリズムの通信を実行するのに必要な
時間を示す。比較したトポロジは、多層式シャフル・エ
クスチェンジ、２次元網目、３次元網目、ハイパーキュ
ーブ、キューブ接続サイクル、シャフル・エクスチェン
ジ、de Bruijn、ハイパーネット、２段ＨＳＥおよび２
段ＨｄＢである。各列は、パラメータｎ＝ｌｏｇ2Ｎの
所与の値に対応する。Ｎ個のデータ項目が処理されるこ
と、およびde Bruijn網とＨｄＢ網はそれぞれＮ／２個
のプロセッサを有するが、残りの網はそれぞれＮ個のプ
ロセッサを有することを想起されたい。
【０１１０】
【表５】
【０１１１】多層式シャフル・エクスチェンジは、この
所与の１組のパラメータでは競争力のある網でないこと
が、当業者には容易に理解されよう。ｎのどの値につい
てもこれが最も低速の網であり、ｎ＝２０の時には、他
のすべてのトポロジの１／６０以下の速さである。チッ
プを接続するサイクルの長さはＮに比例して増加するの
で、これは予想される結果である。このトポロジは、元
来チップの数が非常に少ない場合のために設計されてお
り、その場合にはその性能が競争力をもつ。多層式シャ
フル・エクスチェンジの性能は、各チップ内でより小さ
なシャフル・エクスチェンジを使用することによって多
少は改善できるはずである。これによって、チップ外接
続の幅が増加するはずである。しかしながら、ほとんど
の場合、他のトポロジの方がまだ高速であるはずであ
る。
【０１１２】次に低速のトポロジは、２次元網目、３次
元網目およびハイパーキューブである。これら３つのト
ポロジのうちで、次元の高い構造（ハイパーキューブと
３次元網目）の方が、その直径が小さいので、一般によ
り良い性能を示す。しかしながら、高次元網ではＱの値
が増加するので、この傾向が弱められる。
【０１１３】ハイパーキューブに由来する網と階層式の
網が、常に最高速である。キューブ接続サイクルは、こ
れらの網のうちで最も低速であるが、これは、サイクル
内での処理に時間がかかるためである。シャフル・エク
スチェンジは、それよりかなり高速であり、de Bruijn
網は、シャフル・エクスチェンジのさらに１．５倍の速
さである。de Bruijn網がシャフル・エクスチェンジよ
り効率が高いのは、単一のプロセッサ内にデータ項目の
対を持ち込むための交換動作を必要としないからであ
る。ハイパーネットは、シャフル・エクスチェンジより
高速になることは決してなく、多くの場合これより低速
である。どの場合でも、ＨＳＥ網とＨｄＢ網は、ハイパ
ーネットより高速である。
【０１１４】ＨＳＥ網とＨｄＢ網は、それらの基礎とな
っている非階層式の網よりもかなり高速である。特に、
ＨｄＢ網は、常に最高速であり、多くの場合に、他のす
べての網の２倍の速さである。もちろん、de Bruijn網
とＨｄＢ網は、他の網の半分の数のプロセッサを有し、
１回で２つのデータ項目を送出できるので、基本的に異
なるタイプのアーキテクチャを表している。
【０１１５】次に検討する例は、Ｍ＝２５６でＰ＝４０
９６の時である（表６参照）。これらのパラメータは、
前の１組のパラメータと非常に類似した結果をもたら
す。ハイパーネットは、ｎの値が小さい場合にはＨＳＥ
より高速であるが、ｎの値が大きい場合にはＨＳＥより
低速である。この場合も、ＨＳＥ網とＨｄＢ網は、それ
らの基礎となっている非階層式の網よりもかなり高速で
ある。どの場合でも、ＨｄＢ網が最も高速の網である。
【０１１６】
【表６】
【０１１７】最後に検討する例は、Ｍ＝２５６でＰ＝１
０２４の時である（表７参照）。これらのパラメータ
も、同様の結果をもたらす。ただし、Ｐの値が小さい場
合には、実行されるチップ外通信の数が少ない網が有利
である。特に、ＨｄＢ網は、どの場合でも最高速であ
る。これらのパラメータでは、ＨＳＥは、de Bruijn網
の約２〜３倍の速さである。ハイパーネットの柔軟性の
なさが、この表に明瞭に示されている。ハイパーネット
は、ｎの値が小さい場合には良い性能を示すが、追加の
階層段が必要になると同時に（ｎ≧１６の時）、性能が
劇的に低下する。ｎ≧１４の時、これらのパラメータで
ハイパーキューブを構築することはできない。というの
は、チップ外通信リンクの幅を１ビット未満にしなけれ
ばならないからである。
【０１１８】
【表７】
【０１１９】表５、表６および表７に示した走行時間を
得るのに使用した計算を、以下に示す。パラメータの各
組ごとに、かつ各トポロジごとに、まずＱとＷの値を計
算する。その後、従属パラメータＲ（３２／Ｗ以上の最
小の整数）を計算して、チップ外リンクを介して単一の
３２ビット・ワードを送出するのに必要なサイクル数を
得る。ハイパーキューブとキューブ接続サイクル以外の
すべての網のＱ、ＷおよびＲの値を、表８、表９および
表１０に示す。このＱ、ＷおよびＲの値は、ｎに依存し
ない。
【０１２０】２次元網目（３次元網目）の各チップは、
ほぼ正方形（立方体）のプロセッサ・ブロックを含み、
そのブロックの側面の長さは、２のべき乗になってい
る。これらのブロックは、チップ内のラップ・アラウン
ド接続を有しておらず、したがって任意のサイズの計算
機に使用できる。シャフル・エクスチェンジは、エクス
チェンジ接続がチップ上にあり、シャフル接続と逆シャ
フル接続がチップ外にあるように区分される。de Bruij
n網のすべての接続は、チップ外に向かう。ハイパーネ
ットの各チップ上のすべてのプロセッサは、「キューブ
レット（小キューブ）」を形成する。ハイパーネット内
の各プロセッサは、１つのチップ外接続（スケーラブル
な設計に必要）を有し、部分的ハイパーネットは、前述
のGhosh他の論文の記載に従って構成される。Ghosh他の
論文では、キューブレットごとに１本の入出力リンクを
割り当てているが、ハイパーネットを競争力のあるもの
に関するため、すべてのリンクを通信リンクと見なすこ
とができる。Ｍの所与の値に対して、表８ないし１０の
Ｑの値を得るのに使用した区分は、ｎのすべての値に使
用可能な単一タイプのチップをもたらす。
【０１２１】
【表８】
【０１２２】
【表９】
【０１２３】
【表１０】
【０１２４】ハイパーキューブおよびキューブ接続サイ
クルでは、パラメータＱ、ＷおよびＲは、ｎに依存す
る。ｎの異なる値に対するＱの値を、表１１および表１
２に示す。ハイパーキューブは、各チップがより低次元
のサブキューブを形成するように区分される。Ｍ＝１６
の時、キューブ接続サイクルは４×４のアレイに区分さ
れる。
【０１２５】
【表１１】
【０１２６】
【表１２】
【０１２７】アレイの各行のプロセッサは、トポロジ全
体の中で１サイクル部を形成するので、これらのプロセ
ッサは、その先頭部と末尾部にチップ外接続を有する線
形アレイに接続する。側面の接続は、チップ内またはチ
ップ間の垂直接続として実施される。各チップは、チッ
プ内に留まる最高２個の垂直接続を有することができ
る。Ｍ＝２５６の時は、同様に３２×８のアレイに区分
される。８列のうちのせいぜい５列が、チップ内に留ま
る垂直接続を有することができる。１チップ内の列のあ
る垂直接続を必要としない時には、垂直接続のない列
が、そのチップ内の最後の列になるように選択される。
これによって、場合によっては走行時間がわずかに改善
される。ハイパーキューブとキューブ接続サイクルのど
ちらでも、Ｍとｎが所与の値の場合は、１タイプのチッ
プしか必要でない。しかし、Ｍは所与の値であるがｎの
値が異なる場合は、異なるチップが必要になる。
【０１２８】所与のトポロジのうちの１つ上での昇順ア
ルゴリズムの各実施態様はそれぞれ、チップ上リンクを
介する複数の通信と、チップ外リンクを介する複数の通
信からなる。パラメータＦ（高速を表す）はチップ上の
通信の数を示し、パラメータＳ（低速を表す）はチップ
外の通信の数を示す。この場合、昇順アルゴリズムに必
要な時間は式Ｆ＋ＲＳで与えられる。ＦとＳの値を表１
３、表１４、表１５および表１６に示す。これらの値
は、Ｐに依存しないことに留意されたい。ハイパーネッ
トでは、Ｓの値が、特定のチップ外接続を複数のプロセ
ッサが共用しなければならないことを反映している。
【０１２９】表１３ないし１６の値を計算する最にしば
しば生じる問題が、線形アレイまたは円形アレイ上で昇
順アルゴリズムを実行するのに必要な動作の数である。
長さ２nの線形アレイ上の昇順アルゴリズムでは、２n+1
−２回の通信動作が必要である。長さ２nの円形アレイ
上の昇順アルゴリズムでは、３（２n-1）−２回の通信
動作が必要である。
【０１３０】
【表１３】
【０１３１】
【表１４】
【０１３２】
【表１５】
【０１３３】
【表１６】
【０１３４】本発明の目標をすべて満たす方法と装置に
ついて説明した。本発明の特定の好ましい特徴だけを例
として示してきたが、当業者なら、本発明の技術範囲ま
たは技術思想から逸脱せずに、多くの変更態様と修正を
思いつくであろう。たとえば、当業者なら、ＳＩＭＤコ
ンピュータと同様に、多重命令ストリーム・多重データ
・ストリーム（ＭＩＭＤ）並列コンピュータに本発明の
教示を適用できるであろう。
【０１３５】
【発明の効果】本発明によれば、均一で、スケーラブル
で、任意の実装制約に対して調節可能で、大域通信を伴
うアルゴリズムの実施に効率的である、という４つの条
件を同時に満たす、並列アーキテクチャ（たとえば、Ｈ
ＳＥ網、ＨｄＢ網、ＭＨＳＥ網またはＭＨｄＢ網を中心
に製造された並列コンピュータ）が提供される。
【図面の簡単な説明】
【図１】ＨＳＥ網およびＨＳＥコンピュータが共に本発
明の教示に従って組み立てられている、ＨＳＥ網を介し
て相互接続された８個のプロセッサを含む２段ＨＳＥコ
ンピュータを示す図である。
【図２】図１に示した例示のＨＳＥコンピュータなどの
ＨＳＥコンピュータ上で昇順アルゴリズムを実施するた
めの、本発明で企図する方法の１組のステップを表す流
れ図である。
【図３】図１に示した例示のＨＳＥコンピュータなどの
ＨＳＥコンピュータ上で降順アルゴリズムを実施するた
めの、本発明で企図する方法の１組のステップを表す流
れ図である。
【図４】ＨｄＢ網とＨｄＢコンピュータが共に本発明の
教示に従って組み立てられている、ＨｄＢ網を介して相
互接続された８個のプロセッサを含む２段ＨｄＢコンピ
ュータを示す図である。
【図５】図４に示した例示のＨｄＢコンピュータなどの
ＨｄＢコンピュータ上で昇順アルゴリズムを実施するた
めの、本発明で企図する方法の１組のステップを表す流
れ図である。
【図６】図４に示した例示のＨｄＢコンピュータなどの
ＨｄＢコンピュータ上で降順アルゴリズムを実施するた
めの、本発明で企図する方法の１組のステップを表す流
れ図である。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ホルヘ・エル・シー・サンス アメリカ合衆国95032、カリフォルニア州 ロス・ガトス、フランク・アベニュー 16839

Claims (14)

    【特許請求の範囲】
  1. 【請求項１】２n-m個の実装モジュール（ただしｎとｍ
    は整数でｎ＞ｍ）を含む並列コンピュータにおいて、ｎ
    個のビット（ｘn-1，…，ｘ0）による２n通りの組合せ
    のうちの１つによってそれぞれが一意的に識別可能な、
    ２n個のプロセッサを相互接続する階層シャフル・エク
    スチェンジ（ＨＳＥ）相互接続網であって、 （ａ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
    プロセッサ（ｘn-1，…，ｘ0）をそれぞれプロセッサ
    （ｘn-1，…，ｘ1,ｃ［ｘ0］）、（ｘn-1，…，ｘm，ｘ
    m-2，…，ｘ0，ｘm-1）および（ｘn-1，…，ｘm，ｘ0，
    ｘm-1，…，ｘ1）（ただし"ｃ［ｘi］”はｘiの補数を
    表す）に接続する、３本の両方向通信リンクの組と、 （ｂ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
    プロセッサ（ｘn-1，…，ｘ0）をプロセッサ
    （ｘn-m-1，…，ｘ0，ｘn-1，…，ｘn-m）および（ｘ
    m-1，…，ｘ0，ｘn-1，．．．ｘm）にも接続する、２本
    の両方向通信リンクの組とを備える、ＨＳＥ相互接続
    網。
  2. 【請求項２】前記２本の通信リンクの組中の各通信リン
    クが、それぞれａビット幅（ただしａは整数）であり、
    前記３本の通信リンクの組中の各通信リンクが、それぞ
    れｂビット幅（ただしｂは整数で、ａ≦ｂ）である、請
    求項１に記載の相互接続網。
  3. 【請求項３】２n-m個の実装モジュール（ただしｎとｍ
    は整数でｎ＞ｍ）を含む並列コンピュータにおいて、ｎ
    個のビット（ｘn-1，…，ｘ0）による２n通りの組合せ
    のうちの１つによってそれぞれが一意的に識別可能な、
    ２n個のプロセッサを相互接続する階層de Bruijn（Ｈｄ
    Ｂ）相互接続網であって、 （ａ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
    プロセッサ（ｘn-1，…，ｘ0）をそれぞれプロセッサ
    （ｘn-1，…，ｘm，ｘm-2，…，ｘ0，０）、（ｘn-1，
    …，ｘm，ｘm-2，…，ｘ0，１）、（ｘn-1，…，ｘm，
    ０，ｘm-1，…，ｘ1）および（ｘn-1，…，ｘm，１，ｘ
    m-1，…，ｘ1）に接続する、４本の両方向通信リンクを
    含む第１の組と、 （ｂ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
    プロセッサ（ｘn-1，…，ｘ0）をプロセッサ
    （ｘn-m-2，…，ｘ0，０，ｘn-1，…，ｘn-m）、（ｘ
    n-m-2，…，ｘ 0，１，ｘn-1，…，ｘn-m）、（ｘm-1，
    …，ｘ0，０，ｘn-1，…，ｘm+1）および（ｘm-1，…，
    ｘ0，１，ｘn-1，…，ｘm+1）に接続する、４本の両方
    向通信リンクを含む第２の組とを備えるＨｄＢ相互接続
    網。
  4. 【請求項４】前記第２の組の通信リンクの各通信リンク
    が、それぞれａビット幅（ただしａは整数）であり、前
    記第１の組の通信リンクの各通信リンクが、それぞれｂ
    ビット幅（ただしｂは整数で、ａ≦ｂ）である、請求項
    ３に記載の相互接続網。
  5. 【請求項５】（ａ）０ないし２n−１（ただしｎは整
    数）の範囲の整数のｎビット表現によってそれぞれが一
    意的に定義される、２n個のプロセッサと、 （ｂ）０ないし２n-m−１（ただしｍは整数でｎ＞ｍ）
    の範囲の整数の（ｎ−ｍ）ビット表現によってそれぞれ
    が一意的に識別でき、各プロセッサ（ｘn-1，…，ｘ0）
    が実装モジュール（ｘn-1，…，ｘm）に含まれる、２
    n-m個の実装モジュールと、 （ｃ）前記２n個のプロセッサを相互接続する、請求項
    １または２記載の階層シャフル・エクスチェンジ（ＨＳ
    Ｅ）相互接続網とを備える、ＨＳＥコンピュータ・シス
    テム。
  6. 【請求項６】（ａ）０ないし２n−１（ただしｎは整
    数）の範囲の整数のｎビット表現によってそれぞれが一
    意的に定義される、２n個のプロセッサと、 （ｂ）０ないし２n-m−１（ただしｍは整数でｎ＞ｍ）
    の範囲の整数の（ｎ−ｍ）ビット表現によってそれぞれ
    が一意的に識別でき、各プロセッサ（ｘn-1，…，ｘ0）
    が実装モジュール（ｘn-1，…，ｘm）に含まれる、２
    n-m個の実装モジュールと、 （ｃ）前記２n個のプロセッサを相互接続する、請求項
    ３または４記載の階層deBruijn（ＨｄＢ）相互接続網と
    を備える、ＨｄＢコンピュータ・システム。
  7. 【請求項７】それぞれが０ないし２n−１（ただしｎは
    整数）の範囲の一意的な整数の識別子（ＩＤ）を有する
    ２n個のデータ項目を有し、０ないしｎ−１のｎ個の段
    階を有し、各段階ｉ（ただし０≦ｉ≦ｎ−１）で、２進
    表現のビット位置ｉだけが異なるＩＤを持つデータ項目
    の各対に対して処理を行う昇順アルゴリズムを、それぞ
    れが０ないし２n−１の範囲の一意的なＩＤを有する２n
    個のプロセッサを有し、２n-m個（ただしｍは整数でｎ
    ＞ｍ）の実装モジュールを含む、階層シャフル・エクス
    チェンジ（ＨＳＥ）コンピュータ上で実施する方法であ
    って、 （ａ）各データ項目ｊ（ただしｊは０ないし２n−１の
    範囲の整数）をプロセッサｊに記憶するステップと、 （ｂ）前記ＨＳＥコンピュータのエクスチェンジ接続と
    局所逆シャフル接続とを使用して、前記昇順アルゴリズ
    ムの最初のｍ個の段階を実行するステップと、 （ｃ）前記ＨＳＥコンピュータの大域逆シャフル接続を
    使用して、データ項目の位置変更を行うステップと、 （ｄ）昇順アルゴリズムのｎ個の段階がすべて完了する
    まで、ステップ（ｂ）および（ｃ）を繰り返すステップ
    とを含む方法。
  8. 【請求項８】それぞれが０ないし２n+1−１（ただしｎ
    は整数）の範囲の一意的な整数のＩＤを有する２n+1個
    のデータ項目を有し、０ないしｎのｎ＋１個の段階を有
    し、各段階ｉ（ただし０≦ｉ≦ｎ）で、２進表現のビッ
    ト位置ｉだけが異なるＩＤを有するデータ項目の各対に
    対して処理を行う昇順アルゴリズムを、それぞれが０な
    いし２n−１の範囲の一意的なＩＤを持つ２n個のプロセ
    ッサを有し、２n-m個（ただしｍは整数でｎ＞ｍ）の実
    装モジュールを含む、階層de Bruijn（ＨｄＢ）コンピ
    ュータ上で実施する方法であって、 （ａ）各データ項目ｊ（ただしｊは０ないし２n+1−１
    の範囲の整数）を、ｊ／２以下の最大の整数であるＩＤ
    を有するプロセッサに記憶するステップと、 （ｂ）前記ＨｄＢコンピュータの局所逆シャフル置換接
    続を使用して、前記昇順アルゴリズムの最初のｍ＋１個
    の段階を実行するステップと、 （ｃ）前記ＨｄＢコンピュータの大域逆シャフル置換接
    続を使用して、データ項目の位置変更を行うステップ
    と、 （ｄ）昇順アルゴリズムのｎ＋１個の段階がすべて完了
    するまで、ステップ（ｂ）および（ｃ）を繰り返すステ
    ップとを含む方法。
  9. 【請求項９】それぞれが０ないし２n−１（ただしｎは
    整数）の範囲の一意的な整数のＩＤを有する２n個のデ
    ータ項目を有し、０ないしｎ−１のｎ個の段階を有し、
    各段階ｉ（ただし０≦ｉ≦ｎ−１）で、２進表現のビッ
    ト位置ｉだけが異なるＩＤを持つデータ項目の各対に対
    して処理を行う降順アルゴリズムを、それぞれが０ない
    し２n−１の範囲の一意的なＩＤを有する２n個のプロセ
    ッサを有し、２n-m個（ただしｍは整数でｎ＞ｍ）の実
    装モジュールを含む、ＨＳＥコンピュータ上で実施する
    方法であって、 （ａ）各データ項目ｊ（ただしｊは０ないし２n−１の
    範囲の整数）をプロセッサｊに記憶するステップと、 （ｂ）前記ＨＳＥコンピュータの大域シャフル接続とを
    使用して、データ項目の位置変更を行うステップと、 （ｃ）前記ＨＳＥコンピュータの局所シャフル接続とエ
    クスチェンジ接続とを使用して、前記降順アルゴリズム
    の段階ｎ−１から段階ｎ−ｍまでを実行するステップ
    と、 （ｄ）降順アルゴリズムのｎ個の段階がすべて完了する
    まで、ステップ（ｂ）および（ｃ）を繰り返すステップ
    とを含む方法。
  10. 【請求項１０】それぞれが０ないし２n+1−１（ただし
    ｎは整数）の範囲の一意的な整数のＩＤを有する２n+1
    個のデータ項目を有し、０ないしｎのｎ＋１個の段階を
    有し、各段階ｉ（ただし０≦ｉ≦ｎ）で、２進表現のビ
    ット位置ｉだけが異なるＩＤを有するデータ項目の各対
    に対して処理を行う降順アルゴリズムを、それぞれが０
    ないし２n−１の範囲の一意的なＩＤを持つ２n個のプロ
    セッサを有し、２n-m個（ただしｍは整数でｎ＞ｍ）の
    実装モジュールを含む、階層de Bruijn（ＨｄＢ）コン
    ピュータ上で実施する方法であって、 （ａ）各データ項目ｊ（ただしｊは０ないし２n+1−１
    の範囲の整数）を、ｊ／２以下で最大の整数であるＩＤ
    を有するプロセッサに記憶するステップと、 （ｂ）前記ＨｄＢコンピュータの大域シャフル置換接続
    を使用して、データ項目の位置変更を行うステップと、 （ｃ）前記ＨｄＢコンピュータの局所シャフル置換接続
    を使用して、前記降順アルゴリズムの段階ｎから段階ｎ
    −ｍまでを実行するステップと、 （ｄ）降順アルゴリズムのｎ＋１個の段階がすべて完了
    するまで、ステップ（ｂ）および（ｃ）を繰り返すステ
    ップとを含む方法。
  11. 【請求項１１】２n-m個の実装モジュール（ただしｎと
    ｍは整数でｎ＞ｍ）を含む並列コンピュータにおいて、
    ｎ個のビット（ｘn-1，…，ｘ0）による２n通りの組合
    せのうちの１つによってそれぞれが一意的に識別可能
    な、２n個のプロセッサを相互接続するマージ階層シャ
    フル・エクスチェンジ（ＭＨＳＥ）相互接続網であっ
    て、 （ａ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
    プロセッサ（ｘn-1，…，ｘ0）をそれぞれプロセッサ
    （ｘn-1，…，ｘ1,ｃ［ｘ0］）、（ｘn-1，…，ｘm，ｘ
    m-2，…，ｘ0，ｘm-1）および（ｘn-1，…，ｘm，ｘ0，
    ｘm-1，…，ｘ1）（ただし"ｃ［ｘi］”はｘiの補数を
    表す）に接続する、３本の両方向通信リンクの組と、 （ｂ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
    プロセッサ（ｘn-1，…，ｘ0）をプロセッサ（ｘ0，ｘ
    m-1，…，ｘ1，ｘn-1，…，ｘm）および（ｘn-m- 1，
    …，ｘ0，ｘn-2，…，xn-m，ｘn-1）にも接続する、２
    本の両方向通信リンクの組とを備える、ＭＨＳＥ相互接
    続網。
  12. 【請求項１２】（ａ）０ないし２n−１（ただしｎは整
    数）の範囲の整数のｎビット表現によってそれぞれが一
    意的に定義される、２n個のプロセッサと、 （ｂ）０ないし２n-m−１（ただしｍは整数でｎ＞ｍ）
    の範囲の整数の（ｎ−ｍ）ビット表現によってそれぞれ
    が一意的に識別でき、各プロセッサ（ｘn-1，…，ｘ0）
    が実装モジュール（ｘn-1，…，ｘm）に含まれる、２
    n-m個の実装モジュールと、 （ｃ）前記２n個のプロセッサを相互接続する、請求項
    １１に記載のマージ階層シャフル・エクスチェンジ（Ｍ
    ＨＳＥ）相互接続網とを備える、ＭＨＳＥコンピュータ
    ・システム。
  13. 【請求項１３】２n-m個の実装モジュール（ただしｎと
    ｍは整数でｎ＞ｍ）を含む並列コンピュータにおいて、
    ｎ個のビット（ｘn-1，…，ｘ0）による２n通りの組合
    せのうちの１つによってそれぞれが一意的に識別可能
    な、２n個のプロセッサを相互接続するマージ階層de Br
    uijn（ＭＨｄＢ）相互接続網であって、 （ａ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
    プロセッサ（ｘn-1，…，ｘ0）をそれぞれプロセッサ
    （ｘn-1，…，ｘm，ｘm-2，…，ｘ0，０）、（ｘn-1，
    …，ｘm，ｘm-2，…，ｘ0，１）、（ｘn-1，…，ｘm，
    ０，ｘm-1，…，ｘ1）および（ｘn-1，…，ｘm，１，ｘ
    m-1，…，ｘ1）に接続する、４本の両方向通信リンクを
    含む第１の組と、 （ｂ）各プロセッサ（ｘn-1，…，ｘ0）に結合され、各
    プロセッサ（ｘn-1，…，ｘ0）をプロセッサ
    （ｘn-m-2，…，ｘ0，０，ｘn-2，…，ｘn-m-1）、（ｘ
    n-m-2，…，ｘ0，１，ｘn-2，…，ｘn-m-1）、（０，ｘ
    m-1，…，ｘ0，ｘn-1，…，ｘm+1）および（１，
    ｘm-1，…，ｘ0，ｘn-1，…，ｘm+1）に接続する、４本
    の両方向通信リンクを含む第２の組とを備えるＭＨｄＢ
    相互接続網。
  14. 【請求項１４】（ａ）０ないし２n−１（ただしｎは整
    数）の範囲の整数のｎビット表現によってそれぞれが一
    意的に定義される、２n個のプロセッサと、 （ｂ）０ないし２n-m−１（ただしｍは整数でｎ＞ｍ）
    の範囲の整数の（ｎ−ｍ）ビット表現によってそれぞれ
    が一意的に識別でき、各プロセッサ（ｘn-1，…，ｘ0）
    が実装モジュール（ｘn-1，…，ｘm）に含まれる、２
    n-m個の実装モジュールと、 （ｃ）前記２n個のプロセッサを相互接続する、請求項
    １３に記載のマージ階層de Bruijn（ＭＨｄＢ）相互接
    続網とを備える、ＭＨｄＢコンピュータ・システム。
JP4334578A 1992-01-07 1992-12-15 並列処理のための相互接続網、コンピュータ・システム及び方法 Expired - Lifetime JPH077382B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US81802892A 1992-01-07 1992-01-07
US818028 1992-01-07

Publications (2)

Publication Number Publication Date
JPH05324590A JPH05324590A (ja) 1993-12-07
JPH077382B2 true JPH077382B2 (ja) 1995-01-30

Family

ID=25224463

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4334578A Expired - Lifetime JPH077382B2 (ja) 1992-01-07 1992-12-15 並列処理のための相互接続網、コンピュータ・システム及び方法

Country Status (4)

Country Link
US (1) US5513371A (ja)
EP (1) EP0551188A2 (ja)
JP (1) JPH077382B2 (ja)
CA (1) CA2078912A1 (ja)

Families Citing this family (40)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6144986A (en) * 1997-03-27 2000-11-07 Cybersales, Inc. System for sorting in a multiprocessor environment
US6401189B1 (en) 1998-08-05 2002-06-04 Michael J. Corinthios General base state assignment for optimal massive parallelism
US6622233B1 (en) * 1999-03-31 2003-09-16 Star Bridge Systems, Inc. Hypercomputer
US6263415B1 (en) 1999-04-21 2001-07-17 Hewlett-Packard Co Backup redundant routing system crossbar switch architecture for multi-processor system interconnection networks
US6378029B1 (en) 1999-04-21 2002-04-23 Hewlett-Packard Company Scalable system control unit for distributed shared memory multi-processor systems
US6597692B1 (en) 1999-04-21 2003-07-22 Hewlett-Packard Development, L.P. Scalable, re-configurable crossbar switch architecture for multi-processor system interconnection networks
US7779177B2 (en) 2004-08-09 2010-08-17 Arches Computing Systems Multi-processor reconfigurable computing system
US20080022079A1 (en) * 2006-07-24 2008-01-24 Archer Charles J Executing an allgather operation with an alltoallv operation in a parallel computer
US7660270B2 (en) * 2006-11-08 2010-02-09 Sicortex, Inc. Computer system and method using efficient module and backplane tiling to interconnect computer nodes via a Kautz-like digraph
WO2008057828A2 (en) * 2006-11-08 2008-05-15 Sicortex, Inc. Computer system and method using efficient module and backplane tiling
US7752421B2 (en) * 2007-04-19 2010-07-06 International Business Machines Corporation Parallel-prefix broadcast for a parallel-prefix operation on a parallel computer
US8140826B2 (en) * 2007-05-29 2012-03-20 International Business Machines Corporation Executing a gather operation on a parallel computer
US8161480B2 (en) * 2007-05-29 2012-04-17 International Business Machines Corporation Performing an allreduce operation using shared memory
US20090006663A1 (en) * 2007-06-27 2009-01-01 Archer Charles J Direct Memory Access ('DMA') Engine Assisted Local Reduction
US8090704B2 (en) * 2007-07-30 2012-01-03 International Business Machines Corporation Database retrieval with a non-unique key on a parallel computer system
US7827385B2 (en) * 2007-08-02 2010-11-02 International Business Machines Corporation Effecting a broadcast with an allreduce operation on a parallel computer
US7734706B2 (en) * 2007-08-22 2010-06-08 International Business Machines Corporation Line-plane broadcasting in a data communications network of a parallel computer
US7840779B2 (en) * 2007-08-22 2010-11-23 International Business Machines Corporation Line-plane broadcasting in a data communications network of a parallel computer
US7991857B2 (en) * 2008-03-24 2011-08-02 International Business Machines Corporation Broadcasting a message in a parallel computer
US8122228B2 (en) * 2008-03-24 2012-02-21 International Business Machines Corporation Broadcasting collective operation contributions throughout a parallel computer
US8422402B2 (en) 2008-04-01 2013-04-16 International Business Machines Corporation Broadcasting a message in a parallel computer
US8375197B2 (en) * 2008-05-21 2013-02-12 International Business Machines Corporation Performing an allreduce operation on a plurality of compute nodes of a parallel computer
US8484440B2 (en) 2008-05-21 2013-07-09 International Business Machines Corporation Performing an allreduce operation on a plurality of compute nodes of a parallel computer
US8161268B2 (en) * 2008-05-21 2012-04-17 International Business Machines Corporation Performing an allreduce operation on a plurality of compute nodes of a parallel computer
US8281053B2 (en) * 2008-07-21 2012-10-02 International Business Machines Corporation Performing an all-to-all data exchange on a plurality of data buffers by performing swap operations
US8755515B1 (en) 2008-09-29 2014-06-17 Wai Wu Parallel signal processing system and method
US8565089B2 (en) * 2010-03-29 2013-10-22 International Business Machines Corporation Performing a scatterv operation on a hierarchical tree network optimized for collective operations
US8332460B2 (en) 2010-04-14 2012-12-11 International Business Machines Corporation Performing a local reduction operation on a parallel computer
US9424087B2 (en) 2010-04-29 2016-08-23 International Business Machines Corporation Optimizing collective operations
US8346883B2 (en) 2010-05-19 2013-01-01 International Business Machines Corporation Effecting hardware acceleration of broadcast operations in a parallel computer
US8949577B2 (en) 2010-05-28 2015-02-03 International Business Machines Corporation Performing a deterministic reduction operation in a parallel computer
US8489859B2 (en) 2010-05-28 2013-07-16 International Business Machines Corporation Performing a deterministic reduction operation in a compute node organized into a branched tree topology
US8776081B2 (en) 2010-09-14 2014-07-08 International Business Machines Corporation Send-side matching of data communications messages
US8566841B2 (en) 2010-11-10 2013-10-22 International Business Machines Corporation Processing communications events in parallel active messaging interface by awakening thread from wait state
US8893083B2 (en) 2011-08-09 2014-11-18 International Business Machines Coporation Collective operation protocol selection in a parallel computer
US8667501B2 (en) 2011-08-10 2014-03-04 International Business Machines Corporation Performing a local barrier operation
US8910178B2 (en) 2011-08-10 2014-12-09 International Business Machines Corporation Performing a global barrier operation in a parallel computer
US9495135B2 (en) 2012-02-09 2016-11-15 International Business Machines Corporation Developing collective operations for a parallel computer
US9690734B2 (en) 2014-09-10 2017-06-27 Arjun Kapoor Quasi-optimized interconnection network for, and method of, interconnecting nodes in large-scale, parallel systems
US10592468B2 (en) * 2016-07-13 2020-03-17 Qualcomm Incorporated Shuffler circuit for lane shuffle in SIMD architecture

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4583164A (en) * 1981-08-19 1986-04-15 Tolle Donald M Syntactically self-structuring cellular computer
BG35575A1 (en) * 1982-04-26 1984-05-15 Kasabov Multimicroprocessor system
US4622632A (en) * 1982-08-18 1986-11-11 Board Of Regents, University Of Washington Data processing system having a pyramidal array of processors
US4805091A (en) * 1985-06-04 1989-02-14 Thinking Machines Corporation Method and apparatus for interconnecting processors in a hyper-dimensional array
IT1184015B (it) * 1985-12-13 1987-10-22 Elsag Sistema multiprocessore a piu livelli gerarchici
US4843540A (en) * 1986-09-02 1989-06-27 The Trustees Of Columbia University In The City Of New York Parallel processing method
US4901360A (en) * 1987-10-23 1990-02-13 Hughes Aircraft Company Gated architecture for computer vision machine
US5020059A (en) * 1989-03-31 1991-05-28 At&T Bell Laboratories Reconfigurable signal processor
US5134690A (en) * 1989-06-26 1992-07-28 Samatham Maheswara R Augumented multiprocessor networks
US5173689A (en) * 1990-06-25 1992-12-22 Nec Corporation Self-distributed logical channel node failure restoring system

Also Published As

Publication number Publication date
CA2078912A1 (en) 1993-07-08
EP0551188A2 (en) 1993-07-14
EP0551188A3 (ja) 1995-06-07
US5513371A (en) 1996-04-30
JPH05324590A (ja) 1993-12-07

Similar Documents

Publication Publication Date Title
JPH077382B2 (ja) 並列処理のための相互接続網、コンピュータ・システム及び方法
JP2512661B2 (ja) 非バイナリ・ハイパ―キュ―ブ形式のコンピュ―タ・システムおよびネットワ―クにおける複数ノ―ドの接続方法
Bruck et al. Efficient algorithms for all-to-all communications in multi-port message-passing systems
Parhami Introduction to parallel processing: algorithms and architectures
Choi et al. Parallel matrix transpose algorithms on distributed memory concurrent computers
Chen et al. dBCube: a new class of hierarchical multiprocessor interconnection networks with area efficient layout
US20050044195A1 (en) Network topology having nodes interconnected by extended diagonal links
JPH06507744A (ja) 大量並列プロセッサ間の、階層的プロセッサ相互間通信ネットワークのための手順決定技術
EP1125216B1 (en) Digital processing device
Stojmenović Multiplicative circulant networks topological properties and communication algorithms
Finkel The lens interconnection strategy
Cypher et al. Cubesort: An optimal sorting algorithm for feasible parallel computers
JPH05204876A (ja) 階層型ネットワークおよび階層型ネットワークを用いたマルチプロセッサシステム
Sinha et al. OMULT: An optical interconnection system for parallel computing
JP3606922B2 (ja) ハイパキュ−ブマルチコンピュ−タ−のタスク割当方法および装置
Lee et al. New self-routing permutation networks
Wilkinson Overlapping connectivity interconnection networks for shared memory multiprocessor systems
Lin et al. A practical constant time sorting network
Latifi et al. Optimal simulation of linear array and ring architectures on multiply-twisted hypercube
Merry et al. A constant time algorithm for the channel assignment problem using the reconfigurable mesh
Mei et al. Hypercube computations on partitioned optical passive stars networks
Johnsson Ensemble architectures and their algorithms: an overview
CN116975065A (zh) 面向主从区块链的多级索引构建方法
Suri et al. BDG-torus union graph-an efficient algorithmically specialized parallel interconnect
Somani Design of efficient reconfigurable networks