JPH063589B2 - アドレス置換装置 - Google Patents

Description

【発明の詳細な説明】 Ａ．産業上の利用分野 本発明は、一般に、電子データ処理システムにおける多
重資源管理の分野に関する。より具体的には、高度並行
処理環境にある、たとえばインタリーブ式大型共用メモ
リ・システムなどにおいて論理アドレスを物理アドレス
に１対１写像することにより、データ処理中の任意の瞬
間にかかる全資源を有効に利用することに関する。さら
に具体的には、様々な１対１写像を行なうことのでき
る、アドレス生成用ハードウェアに関する。

Ｂ．従来技術 現代の多くの高性能計算機システムでは、多重インタリ
ーブ式装置を用いて、メモリ及び入出力装置に対する帯
域幅を増大させることができる。インタリービングと
は、ほぼ同時に多くのアクセスができるようにする方法
である。ｎ＝２^d個のデバイス、Ｄ₀、Ｄ₂、…、Ｄ_n-1を
考えてみる。インタリービングを用いて、アドレスｍの
内容をＤ_qに記憶する。ただし、ｐ＝ｍｏｄ（ｍ，
ｎ）。このようにインタリービングを行なって、特に参
照が近接メモリ・アドレスに対するものである場合、同
時に最大ｎ個までの参照を満足させることができる。こ
れは、連続アドレスに対して同時に多数のプロセッサが
作用している場合、高度の並列式共用メモリ・システム
で大きな利益をもたらす。

アドレスが連続でなく、ｔとｎが公約数をもつ、すなわ
ちｇｃｄ（ｔ，ｎ）＞１のようなストライド（歩幅、間
隔）ｔで現われる場合には、このような状況で、問題が
発生する。たとえば、ある起点アドレスａに対して、
ａ、ａ＋ｋｎ、ａ＋２ｋｎ、ａ＋３ｋｎ、…、ａ＋（ｎ
−１）ｋｎで与えられるストライドｋｎ（ただし、ｋ≧
１かつｋ∈Ｉ）のアドレス列を考えてみる。上記インタ
リービングを用いる場合、これらの参照が、すべて、同
じデバイスＤ_mod(a,n)にアドレスされる。このようなス
トライドのアクセスは、アプリケーション・プログラム
で、たとえば配列（アレイ）の行または列にアクセスす
るとき、頻繁に行なわれる。このようなストライド・ア
クセスに起因する性能低下は、プロセッサの数が非常に
多くなるのに応じて悪化し、このようなハードウェアに
おける大きな問題点となり得る。

以下の考案では、通常のやり方で、大括弧［ ］を用い
て従来技術の刊行物を参照する。これらの刊行物のリス
トは、本節の直後に示す。

このようなメモリの「ホットスポット」は「ツリーの閉
塞(tree-blockage)」をもたらしかねないので、メモリ
・アクセスが不均一であるという問題は、高度の並列シ
ステムでは重大な問題である［１］。すなわち、ネット
ワークならびにメモリの争奪によって、システム全体の
性能が争奪中のデバイスによって決まる速度に制限され
る可能性がある。こうした参照は、通常、デバイス相互
間でインタリーブされ、その物理アドレスの２進表示の
形をとるフィールドによって相互接続ネットワークを介
して送られるので、このようなシステムは、特に、２の
べき乗ストライド・アクセス争奪に対して弱い。

ＩＬＬＩＡＣ IV［２］などのＤＩＭＤ並列システムで
は、メモリ・アクセスの衝突のために、すべてのプロセ
ッサが並列動作における最後のメモリ・アクセスを待た
される可能性がある。こうした理由から、ストライド・
アクセスに付随する争奪を解消または減少させるための
方式を求めて、多大な努力が払われてきた。

ＩＬＬＩＡＣ IV［２］、ＳＴＡＲＡＮ［３］、ＢＳＰ
［４］コンピュータについて、適用業務行列アレイの任
意の行、列、順方向対角線、逆方向対角線への無衝突ア
クセスを可能にするメモリ編成が開発されている。これ
らの論文の大部分では、同期されたＳＩＭＤマシンにつ
いて、決定論的無衝突方式でアレイがアクセスされる。

［２］及び［４］で、素数個のメモリ・モジュールを必
要とするハードウェア及びソフトウェアによる解決策が
提案されている。［６］では、Ｍ個のメモリ・モジュー
ルを有するシステムが提案されている。ただし、Ｍ＝２
Ｎで、Ｎは処理ノードの数である。これらの解決策はす
べて、Ｍとストライド・アクセスが互いに素となるよう
に考えられている。［３］及び［７］では、アレイのイ
ンデックスに排他的論理的（ＸＯＲ）を行なって個々の
メモリ単位に写像するスキュー方式が使用されている。
［８］及び［９］では、これらのスキュー方式の数学的
及び論理的限界が検討されている。

［６］ではアラインメント・ネットワークがさらに研究
され、適切に位置合せされたデータにアクセスし、それ
を記憶するために、費用のかかるＮ×Ｍのクロスバー・
スイッチを構築するのとは別の、［１０］のシャッフル
交換動作に基づく解決策が示されている。その他、［１
１］などでは、データの動的置換を可能にする、相互接
続ネットワーク用の制御パターン行列が設計されてい
る。

これらの方式には、いくつかの大きな弱点がある。それ
らは、主として専用の目的用に設計され、当初からアレ
イのサイズとメモリ・モジュールの個数に依存するの
で、より多様な制限を満足しなければならない汎用計算
環境には適していない。さらに、これらの設計のうちに
は、モジューロ演算及び整除用に高価で複雑なアドレッ
シング／位置合せハードウェアを必要とするものがあ
る。最後に、これらの方法によってアドレス空間中に
「ホール」ができるため、メモリ利用度が不十分になる
可能性がある。

参照文献 ［１］Ｇ．Ｆ．プフィスタ(Pfister)、Ｖ．Ａ．ノート
ン(Norton)、「多段相互接続ネットワークにおけるホッ
トスポットの争奪と結合(Hot Spot Contention and Com
bining in Multistage Interconnection Networks)」、
ＩＥＥＥコンピュータ紀要(IEEE Transaction on Compu
ters)、Ｃ−３４、第１０号、１９８５年１０月、ｐ
ｐ．９４３−９４８。

［２］Ｐ．ブドニク(Budnik)、Ｄ．Ｊ．クック(Kuck)、
“並列メモリの編成及び使用(The Organization and Us
e of Parallel Memories)”、ＩＥＥＥコンピュータ紀
要、１９７１年１２月、ｐｐ．１５６６−１５６９。

［３］Ｋ．Ｅ．バッチャー(Batcher)、“ＳＴＡＲＡＮ
中の多次元アクセス・メモリ(The Multidimensional Ac
cess Memory in STARAN)”、ＩＥＥＥコンピュータ紀
要、１９７７年２月、ｐｐ．１７４−１７７。

［４］Ｄ．Ｈ．ローリー(Lawrie)、Ｃ．Ｒ．ヴォーラ(V
ora)、“アレイ・アクセス用基本メモリ・システム(The
Prime Memory System for Array Access)”、ＩＥＥＥ
コンピュータ紀要、Ｃ−３１、第５号、１９８２年５
月、ｐｐ．４３５−４４２。

［５］Ｄ．Ｊ．クック、“ＩＬＬＩＡＣ IVのソフトウ
ェア及び適用業務プログラミング（ＩＬＬＩＡＣ IV
Ｓｏｆｔｗａｒｅ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ
Ｐｒｏｇｒａｍｍｉｎｇ）”、ＩＥＥＥコンピュータ紀
要、Ｃ−１７、１９６８年８月、ｐｐ．７５８−７７
０。

［６］Ｄ．Ｈ．ローリー、“アレイ・プロセッサにおけ
るデータのアクセスと整列(Access and Alignment of D
ata in an Array Processor)”、ＩＥＥＥコンピュータ
紀要、Ｃ−２４、第１２号、１９７５年１２月、ｐｐ．
１１４５−１１５０。

［７］Ｊ．Ｍ．フレイロン(Frailong)、Ｊ．ランファン
(Lenfant)、“排他的論理和方式：並列メモリにおける
柔軟なデータ編成(XOR-Schemes:A Flexible Data Organ
ization in Parallel Memories)”、国際並列処理会議
発表要旨集(Proceedings,Internat Conf on Parallel P
rocessing)、１９８５年８月、ｐｐ．２７６−２８３。

［８］Ｈ．Ａ．ヴェイスホフ(Wijstoff)、Ｊ．レーヴェ
ン(Leeuwen)、“並列メモリ用周期的記憶方式の構造(Th
e Structure of Periodic Storage Schemes for Parall
el Memories)”、ＩＥＥＥコンピュータ紀要、Ｃ−３
４、第６号、１９８５年６月、ｐｐ．５０１−５０５。

［９］Ｈ．Ｄ．シャピーロ(Shapiro)、“並列メモリの
効率的使用における理論的限界(Theoretical Limitatio
ns on the Efficient Use of Parallel Memories)”、
ＩＥＥＥコンピュータ紀要、Ｃ−２７、第５号、１９７
８年５月、ｐｐ．４２１−４２８。

［１０］Ｈ．Ｓ．ストーン(Stone)、“完全シャッフル
による並列処理(Parallel Processing with the Perfec
t Shuffle)”、ＩＥＥＥコンピュータ紀要、Ｃ−２０、
１９７１年２月、ｐｐ．１５３−１６１。

［１１］Ｊ．ランファン、“データの並列置換：頻繁に
使用される置換用のベネスネットワーク制御アルゴリズ
ム(Parallel Permutations of Data:A Benes Network C
ontrol Algorithm for Frequently Used Permutation
s)”、ＩＥＥＥコンピュータ紀要、Ｃ−２７、第７号、
１９７８年７月、ｐｐ．６３７−６４７。

［１２］Ｇ．Ｆ．プフィスタ、Ｗ．Ｃ．ブラントリー(B
rantley)、Ｄ．Ａ．ジョージ(George)、Ｓ．Ｌ．ハーヴ
ェイ(Harvey)、Ｗ．Ｊ．クラインフェルダ(Kleinfelde
r)、Ｋ．Ｐ．マコーリフ(McAuliffe)、Ｅ．Ａ．メルト
ン(Melton)、Ｖ．Ａ．ノートン、Ｊ．ワイス(Weiss)、
“ＩＢＭ研究用並列プロセッサ試作品（ＲＰ３）：紹介
及びアーキテクチャ(The IBM Research Parallel Proce
ssor Prototype（ＲＰ３）：Introduction and Archite
cture)”、国際並列処理会議発表要旨集、１９８５年、
ｐｐ．７６４−７７１。

［１３］Ｅ．Ｄ．ブルックス(Brooks)、“ベクトル環境
での蝶形プロセッサ・メモリ相互接続の性能(Performan
ce of the Butterfly Processor-Memory Interconnecti
on in a Vector Environment)”、国際並列処理会議発
表要旨集、１９８５年、ｐｐ．２１−２５。

［１４］Ｂ．Ｂ．マンデルブロト(Mandelbrot)、“自然
のフラクタル幾何学(The Fractal Geometry of Natur
e)”、Ｗ．Ｈ．フリーマン社(Freeman)、ニューヨー
ク、１９８３年刊。

上記の参照刊行物の他に、以下のものは、本発明に関係
するが、本発明に先行するものではないと見なされる、
本発明者にとって既知のその他の現況技術の議論であ
る。

サリヴァン(Sullivan)等の米国特許第４４８４２６２号
明細書は、関連するすべてのメモリ・モジュールに向か
う、アドレスを「スクランブル」するための、乱数発生
ルーチンの形のメモリ管理プログラムを開示している。
このメモリ管理プログラムは、ひとつの中心手順として
も、または手順の階層としても実施できる。後者で手順
をシステム中に分散させる場合、異なる論理アドレスが
同一の物理アドレスに対応しないようにするための何ら
かの形の調整が可能でなければならない。これをコンピ
ュータ・システムで実施するには、かなりの量のハード
ウェア及び（ネットワーク・メモリ管理プログラムによ
りパケット・サイズが増大するという形の）オーバヘッ
ドが必要である。これは、高度の並列システムでメモリ
帯域幅を増大させるための解決策としては非常に高価に
つく。高度の並列コンピュータ・システムでシステム構
成ならびにソースとメモリ・ユニットの個数を変更する
場合、本特許明細書中で提案するハードウェアは、スゲ
ーリングし直すために完全に構築し直す必要がある。

本発明の基礎となるアドレス変換機構は、並列デバイス
のアドレスの置換を行なうように設計されている。この
ような行列の特性により、異なる論理アドレスが同一の
物理アドレスに対応しないことが保証される。さらに、
本発明は、普通ならハッシングやランダム化といった他
の方法を用いてデータを利用可能なメモリ・モジュール
全体のサブセットにグループ分けする、２のべき乗のス
トライド・アクセスを解決するように、特別に設計され
ている。

Ｒ．Ｎ．ラングメイド(Langmaid)の論文、“汎用プログ
ラマブル論理アレイ(Versatile Programmable Logic Ar
ray)”、ＩＢＭテクニカル・ディスクロージャ・ブルテ
ン、第２５巻、第８号、１９８３年１月、ｐｐ．４４４
５−４４４９では、ハッシングに使用できると称する
（ｐ．４４４８）論理アレイすなわち行列が開示されて
いる。ただし、インタリーブ式大型共有メモリ編成を有
する並列処理コンピュータ・システムで、それをどのよ
うに使ってアドレスをハッシュするかについては、何も
示唆されていない。

この他にも多数の参照資料が発明者等にわかっている
が、背景的な性格のものにすぎないと考えられる。その
大多数は、アドレス変換機能にハッシングを利用する仮
想記憶システムを開示したものである。それらの米国特
許明細書の参照番号を、以下にリストしておく。

３６９１５３１ ４４３３３８９ ４１５７５８７ ４４８４２７２ ４１６７７８２ ４５５０３６７ ４２４９２４２ ４５８７６１０ ４３９５７５７ ４５８８９８５ 下記の参照文献は、一般に、ある形式の乗法または論理
行列を開示したものであるが、ビット行列の乗法やその
メモリ写像手順への適用を開示も示唆もしていない。

１．マチアス(Matyas)等、“データ暗号化標準用の電子
署名(Electronic Signature for Use with Data Encryp
tion Standard)”、ＩＢＭテクニカル・ディスクロージ
ャ・ブルテン、第２４巻、第５号、１９８１年１０月、
ｐｐ．２３３５−２３３６。

２．ルボルト(Lubold)等、“データ暗号化アルゴリスム
用の行列デジタル署名(Matrix Digital Signature for
Use with the Data Encryption Algorithm)”、ＩＢＭ
テクニカル・ディスクロージャ・ブルテン、第２８巻、
第２号、１９８５年７月、ｐｐ．６０３−６０４。

３．アングリン(Anglin)等、“情報検索法(Information
Retrieval Technique)”、ＩＢＭテクニカル・ディス
クロージャ・ブルテン、第１６巻、第７号、１９７３年
１２月、ｐｐ．２２２３−２２３４。

４．マチアス等、“データ暗号化標準用電子署名(Elect
ronic Signature for Data Encryption Atandard)”、
ＩＢＭテクニカル・ディスクロージャ・ブルテン、第２
４巻、第５号、１９８１年１０月、ｐｐ．２２３２−２
２３４。

Ｃ．発明が解決しようとする課題 本発明の主目的は、特に、大型高度並列処理システムで
サーバの利用効率を改善するためのハードウェア機構を
提供することにある。

本発明のもう一つの目的は、多数のインタリーブ式ラン
ダム・アクセス・デバイスを備えた任意の計算システム
で有用性を発揮するこのような機構を提供することにあ
る。そのようなデバイスとしては、大型ＤＡＳＤシステ
ム、ＳＩＭＤまたはＭＩＭＤ高度並列処理システムのラ
ンダム・アクセス・メモリ・モジュールなどの入出力デ
バイスを含む同時アクセス可能なサーバがあり、事実、
ランダム・アクセス可能な階層的１次または２次メモリ
・システムが、すべて適用可能である。

本発明のもう一つの目的は、個々のメモリ・モジュール
の利用度をいつでもシステム全体にわたって高度に最適
化させるという全般的効果を有する、メモリ管理システ
ムに提示された論理アドレスを物理アドレスに置換する
このような機構、とりわけ、２のべき乗のストライド・
アクセスの行なわれる論理アドレス用の機構を提供する
ことにある。

本発明のもう一つの目的は、所与の行列を用いて論理ア
ドレスのビット行列乗法によって置換(permutation)を
行ない、一意的な物理アドレスを生成するというこのよ
うな機構を提供することにある。

本発明のもう一つの目的は、それぞれアドレス写像に対
する効果が異なり、異なるシステム構成またはデータ・
アクセス・パターン特性に対応できる、置換手順用の複
数の異なる行列のどれにでもアクセスすることのでき
る、このようなシステムを提供することにある。

本発明のもう一つの目的は、容易にアクセス可能な記憶
媒体中に複数の行列が記憶されており、所定の次元のア
ドレスを同じ次元の行列を用いて置換するための汎用ハ
ードウェア機構が設けられている、このような機構を提
供することにある。

本発明のもう一つの目的は、ただ１個の命令で適切な行
列がアクセスされ、置換手順で使用される、このような
機構を提供することにある。

Ｄ．課題を解決するための手段 本発明の目的は、一般に、アドレス写像を生成するアド
レス置換行列族のうち任意の行列を選択できる機能を備
え、このためストライド・アクセスに関連するメモリ及
びネットワークの争奪が減少する、論理アドレスを物理
デバイス・アドレスに写像するための多目的汎用ハード
ウェア・アドレス置換システムによって実現される。こ
のシステムを使うと、どんな２のべき乗ストライドでも
均一なアクセスが可能となり、他のストライド・アクセ
スで争奪の問題が起こらない。行列及びそれによる写像
は、ブール体ＧＦ（２）上で線形である変換に基づき、
目標アドレスと行列の逐次行とのビット行列乗算を行な
うものである。

ＳＩＭＤマシンやＭＩＭＤマシンの１次または２次メモ
リ・システムでは、ハードウェア・システムは重要な価
値を有し、アプリケーションのストライド・アクセス・
パターンに付随するメモリ・ホットスポットという問題
を解消することができる。必要なハードウェアは、ホス
ト・コンピュータのアドレス変換ユニットに組み込むこ
とができ、これは、複数の異なる行列と、ビット行列乗
法モジュールと、置換されたアドレスの記憶手段と、シ
ステムの制御下で所定の行列にアクセスして、その行列
及び置換すべきアドレスのＮビット・フィールドをビッ
ト行列乗法モジュールに転送する制御ユニットとから構
成される。ビット行列乗法モジュール中では、そのアド
レスを上記行列の連続するＮ行とビット行列乗算するこ
とにより、アドレスのＮ個の置換されたビットが生成さ
れる。本明細書に記載する手順は、ハードウェアまたは
ソフトウェアで容易に実施できる。本明細書では、高度
並列処理システムのメモリ写像ユニット中にこのような
変換を取り込む方法を記載する。

本発明は、主としてインタリーブ式大型ランダム・アク
セス・メモリ・システムに効用があるが、データベース
適用業務用に高速データ検索を必要とする直接アクセス
記憶装置などの大型入出力システムにも適用できる。

Ｅ．実施例 置換(permutation)の概念の説明 基礎となるアドレス置換手順の価値を拡張し増強する本
発明の価値を理解し評価するには、基礎となる置換方法
を明確に理解することが必要である。この方法では、ブ
ール（すなわち２進）行列乗法を行なうことにより、ア
ドレス空間を置換する。デバイス数が２のべき乗である
システムで、２のべき乗ストライド・アクセス争奪を解
消するように行列を選べることが、はっきりと実証され
る。このような写像は、たとえば、２を基数とする並列
高速フーリエ変換でメモリ・アクセスに関連する争奪を
解消するために使用できる。この技法は特にすべての２
のべき乗ストライド・アクセスでネットワークとメモリ
の争奪を解消するのに使われるものであるが、２のべき
乗でないその他のあらゆるストライド・アクセスの場合
でも過剰争奪という問題を引き起こすことはない。

ＳＩＭＤマシンなどの同期システムで性能の利点は最大
となり、普通ならいつもボトルネックとなるはずの所
で、２のべき乗の行と列の争奪がすべて本方法で完全に
解消できる。非同期ＭＩＭＤシステムまたは入出力アク
セスでは、改善はそれほど目ざましくはないが、性能を
損なうものとしてのストライド・アクセスを解消するに
は十分である。

この方法は、ハードウェア中で有効に実施することがで
き、並列システム中の個々のプロセッサのメモリ写像ま
たはアドレッシング用ハードウェアに組み込むのが適当
である。後節で説明するように、このようなハードウェ
アがＲＰ３設計［１２］に含まれている。マルチプロセ
ッサ環境で、各処理要素中のメモリ写像ユニットの設計
にこのようなハードウェアを含めると好都合である。

まず２のべき乗ストライド・アクセスの改善を得るため
の一般的方法について説明する。代数的条件を誘導し、
メモリに対する２のべき乗ストライド・アクセスの衝突
を解消するのに十分であることを示す。この条件の変形
が、ネットワークの衝突を解消するのにも十分なことを
示す。

指定条件を満足するビット行列の作成手順を示す。１つ
のこのような行列について、様々のストライドに関連す
るアクセス衝突を示す、性能分析の結果を提出する。最
後に、この方法をどのようにすれば上記で参照した試験
的ＲＰ３システムなどインタリーブ式大型共用メモリ・
システムで、ハードウェアまたはソフトウェアとして具
体化したハードウェア・アドレス変換機構の一部として
組み込めるかを示す。

ブールｒ×ｓ行列は、ｒ行及びｓ列に配列された２進ビ
ットの矩形アレイである。このような行列は、ｓ−ｔｕ
ｐｌｅ（ｓ組）ビットのベクトル空間Ｆ^sからｒ−ｔｕ
ｐｌｅ（ｒ組）ビットのベクトル空間Ｆ^rへの線形写像
を記述する。これらは２要素｛０，１｝の体Ｆ＝ＧＦ
（２）上のベクトル空間である。この体中での加法と乗
法が、それぞれ「排他的論理和」及び「論理積」の論理
（ブール）演算であることに注意されたい。

ブール行列Ｍ＝（ｍ_ij）にブールｓ×１ベクトルＶを乗
じる線形変換は、行列に整数を乗じるのと同じように実
行される。すなわち、積ＭＶのｉ番目の要素は、Ｍのｉ
行目とベクトルＶとの「ドット」積（内積）である。こ
のドット積は、各項目ｍ_ijにｖ_jを乗じる（論理積をと
る）ことによって得られるｓビットの和（排他的論理
和）である。

本明細書に記載する方法は、ブール行列乗法を用いて、
アドレス空間に対して置換を行なうことに基づいてい
る。行列Ｍを正方可逆ｓ×ｓ行列とすると、Ｍを乗じる
ことにより、ｓ−ｔｕｐｌｅのビットに施す置換が定義
される。ｓビットのアドレスをｓ成分ベクトルと見なす
ことにより、２^sアドレスの空間に対する置換写像を定
義する。

この議論の大部分では、これらのアドレスをメモリ・ア
ドレスと見なすこととし、論理アドレスから物理アドレ
スへの写像に行列乗法を用いることにする。ただし、こ
の同じ方法が、直接アクセス記憶媒体や高速ランダム・
アクセス・ディスク駆動機構などその他様々な物理デバ
イスにアクセスするのにも適用できる。

明確にするため、２^d個の物理デバイスからなるシステ
ムを仮定する。このシステム中の物理アドレスは、ｓビ
ットからなる（ただし、ｄ＜ｓ）。最初のｄビットはデ
バイス番号を識別し、あとのｓ−ｄ個のビットはデバイ
ス内の様々なアドレスを識別する。論理アドレスはｓ×
１ベクトルとして定義される。アドレスの最下位ビット
はビット・ストリング中の最終（「最下部」）要素であ
り、最上位ビットはビット・ストリング中の第１（「最
上部」）要素である。

次に、ある２のべき乗ストライドに及ぼす行列の作用結
果を決定する代数的制約について説明することにする。
ある整数ｔ≧０に対して、２^d個の物理デバイス全体に
わたって、２^tストライドの無衝突アクセスが望まし
い。２^d個のデバイスがそれぞれ１回参照されるまで、
同じデバイスが二度参照されることはないように、異な
るデバイスを連続的に参照するのが最適である。これ
は、２^d個のアドレス０、２^t、２×２^t、３×２^t、…、
（２^d−１）×２^tがすべて異なる物理デバイスに写像さ
れなければならないことを意味している。

論理アドレス空間を体Ｆ上のブール・ベクトル空間と見
なすと、上記アドレスの列はアドレス空間の線形部分空
間Ｓを形成している。この空間を物理メモリ・デバイス
全体に一様に写像するために、行列Ｍの最初のｄ行を考
える。これらの行が、論理アドレスに関連する物理デバ
イスを決定するためである。Ｍの最初のｄ行からなるｄ
×ｓ行列をＭ′と置く。

２^tのストライドの場合、Ｍ′のｄ個の隣接する列、す
なわち列ｓ−ｔ−ｄ＋１、ｓ−ｔ−ｄ＋２、…、ｓ−ｔ
から構成されるＭ′のｄ×ｄ部分行列によって、部分空
間Ｓの物理デバイスへの写像が決定される。この部分行
列が最大の階数を有する（階数＝ｄ）場合、部分空間Ｓ
は２^d個の異なるデバイスに写像される。そうでない場
合には、ＳはＦ^dより小さな部分空間に写像され、これ
は２^k個のメモリ・モジュールに写像される。ただし、
ｋ≦ｄ−１。

様々な２のべき乗ストライド２^t、ｔ＝０、１、２、…
を考えると、このようなストライド・アクセスを２^d個
のデバイスに一様にアクセスさせるには、次の条件を満
足する必要がある。

●（Ａ）Ｍ′の連続するｄ行列からなるすべてのｄ×ｄ
部分行列が正則である。ただし、行列式がゼロでない、
または行列が可逆行列の場合にだけ、行列が正則である
と定義する。

アドレス０から始まる２^d個の連続する２のべき乗スト
ライド・アクセスを考えることから条件（Ａ）が誘導さ
れたことに注意されたい。これは、その他の起点アドレ
スからのアクセスが一様なことを意味するものではな
い。ただし、２^d個のアクセスが別のアドレスａから開
始するとしても、結果はほとんど同じである。つまり、
２^d個のアクセスは、どのデバイスをも２回以上参照す
ることはない。写像ＭがＳ上だけでなく、Ｓの任意の剰
余系ａＳ上でも無衝突であることに留意されたい。ａ
≠０から始まるストライド・アクセスの場合、高々２個
のこのような剰余系、すなわちａＳ及び（ａ＋
２^t+d）Ｓと交差することになる。は、論理的なビ
ットごとの排他的論理和演算を表わす。

条件（Ａ）を満足する行列の１例を、第１表に示す。

上記の条件（Ａ）は、２のべき乗ストライド・アクセス
の下でメモリ争奪が減少することを意味している。多く
の並列システムでは、プロセッサとメモリとの間での争
奪に出会うこともあり得る。たとえば、第６図に示す反
転ベースライン・ネットワークを考えられたい。プロセ
ッサがあるメモリ・モジュールを参照するには、ネット
ワークを介して指定モジュールにまでメッセージを送ら
なければならない。２つのメッセージが異なる宛先に向
かう場合でも、それらの宛先の途中のスイッチで「衝
突」するかもしれない。アドレス変換行列を適当に選ぶ
ことにより、このような衝突も、解消または減少させる
ことができる。

どのようにすれば適当な行列を選ぶことができるかを示
すのに、第６図に示すような反転ベースライン・ネット
ワークを利用する。その他のネットワークも、同様に選
んだ行列を用いることができる。途中にある様々なスイ
ッチで行なわれた１組の２進選択によって、プロセッサ
からメモリに達する一意的な経路が与えられることに留
意されたい。さらに、この経路指定に使うビットは宛先
メモリ・モジュールにだけ依存し、指定された経路が異
なることがあっても、発信元のプロセッサには依存しな
い。

ネットワーク中で２のべき乗ストライド・アクセスの衝
突を解消する場合には、メモリへの様々の経路が一様に
アクセスされるようにすれば十分である。こうするた
め、アクセスのための経路に応じて様々なメモリ・モジ
ュールを番号付けする。つまり、第１（最上位）ビット
は第１ネットワーク段用の経路指定ビットであり、第２
ビットは第２段用の経路指定ビット、以下同様である。
この結果、第６図に示す番号付けが得られる。ここで使
用する物理的アドレッシング方式によれば、これらはま
た、記憶位置の物理アドレスの最上位ビットでもある。

ここで、Ｍ′の２^d正方部分行列すべてに対してだけで
はなく、あらゆるｊ≦ｄについて、サイズ２^jの部分行
列に対しても条件（Ａ）が満足されるものと仮定する。
言い換えれば、 ●（Ｂ）Ｍ′の最上部と境を接するＭ′のあらゆる正方
部分行列は正則である。

この条件（Ｂ）は、Ｓ＆ａ＝０となるような任意のアド
レスａから始まるどのような２のべき乗ストライド・ア
クセスも、アドレスの最初のｊビットで定義される物理
アドレス空間のどの部分空間にも一様なアクセスをもた
らすことを意味している。ただし、＆は論理的なビット
ごとの論理積演算を表わす。条件（Ｂ）を満足する行列
の例は、第２表を参照されたい。

この事実を使って、同じストライドで連続する要素にす
べてのプロセッサが同時にアクセスする（ｉ番目のプロ
セッサがデータｉ×２^Iにアクセスする）場合、ネット
ワークまたはメモリで衝突が起こらないことを示すこと
にする。

また、２×２スイッチのｄ段の反転ベースライン・ネッ
トワークにより、２^d個のメモリ・モジュールがアクセ
スされると仮定する。

ネットワークの第１段にある任意のスイッチを考える。
このスイッチの出力は、アドレスの最上位ビットによっ
てアドレスされる。行列の第１行について条件（Ａ）が
満足されているので、データ項ｉ×２^I及び（ｉ＋１）
×２^Iにアドレスされたこのスイッチ中の２つの参照が
そのビット中で必ず異なっていなければならないと結論
できる。

同様に、ネットワークの第ｋ段で、第ｋ段にある様々な
スイッチの入力ポートに２^d個のメッセージが同時に到
着すると仮定する。この段の最初の２^k個のスイッチを
考える。行列の第ｋ行（ｋ≦ｄ）で条件（Ｂ）が成立す
るので、この行に到達する２^k個の参照は争奪なしに異
なる出力ポートに必ず向かわなければならないことがわ
かる。同様の議論が、第ｋ行にある２^k個のスイッチの
次のグループにも当てはまる。２^d個の参照がすべて衝
突することなくネットワーク中を通過するものと結論で
きる。

ネットワークへのストライド・アクセスが（上記証明で
仮定したように）完全には同期されていなくても、この
方法には、かなりの利点がある。このようなネットワー
クでの争奪による遅延によって、ストライド１のベクト
ル・アクセスにおけるわずかの同期誤差が補正されるこ
とが観察されている［１３］。条件（Ｂ）を満足する行
列メモリの写像を利用すると、２のべき乗ストライド・
アクセスで同様の利益が生じるものと予期される。

適当なブール行列を決定するための前記の判定基準
（Ａ）及び（Ｂ）は、このような行列の特性を与えるの
で非常に重要である。次に、（Ｂ）を満足するすべての
行列を作成するための一般的な手順について説明する。

定理：ｄ行及びｓ列の行列が与えられているものとする
と、条件（Ｂ）を満足する行列Ｍが存在する。事実、下
部対角ビット｛ｍ_ij｜ｉ＞ｊ｝をどのように選んでも、
こうした下部対角要素を有し、（Ｂ）を満足する一意的
なブール行列Ｍが存在する。

証明：（Ｂ）を満足する行列を得るために、行列の行に
ついて数学的帰納法で証明する。（Ｂ）を満足する最初
のｋ行（１≦ｋ≦ｓ−１）を選ぶと、可逆行列Ｍとなる
残りのｓ−ｋ行は、どのように選択することもできる。

第１列で条件（Ｂ）が成立するということは、この行の
要素がちょうど１×１部分行列となるので、この行中の
あらゆる要素が１にならなければならないことを意味し
ている。

ここで、最初のｋ−１個の行を選び、その結果得られる
（ｋ−１）×ｓ行列の隣接する列によって形成されるす
べての（ｋ−１）×（ｋ−１）正方部分行列が可逆行列
であるものと仮定する。第ｋ行における最初のｋ−１個
の項目に対して、任意のｋ−１個の値（０または１）を
選ぶ。要素ｍ_kkに対して、その結果得られるｋ×ｋ隅部
分行列が正則となるような値（０または１）が存在す
る。これを証明するため、この部分行列の行列式Ｄをそ
の最下行に沿って展開する。次式が得られる。

Ｄ＝ｍ_k1Ｄ_k1＋ｍ_k2Ｄ_k2＋…＋ｍ_kkＤ_kk ただし、上式で、Ｄ_ijは行列要素ｍ_ijの余因子を表わ
す。

帰納的仮定により、行列式Ｄ_kkがゼロでない、したがっ
て１であることに注意されたい。ここで、ｍ_kkを選ぶこ
とが可能である。最初のｋ−１個の項の和がゼロになる
場合には、ｍ_kkは１に選ぶ。そうでない場合には、ｍ_kk
を０に選ぶ。どちらの場合にも、正方隅部分行列を正則
となるように選ぶことができる。

第ｋ行に沿って進み、同様の議論を適用して、ｍ_k1をそ
の右下隅に有する正方部分行列が反転可能となるような
ｍ_k1（ただし１＞ｋ）を選ぶことができる。以上で証明
を終わる。

上記の議論から、条件（Ｂ）を満足するすべての行列Ｍ
が構成される。行列Ｍの各第ｋ行について、最初のｋ−
１ビットは選ぶことが可能であり、その行の残りの項目
はそれから決定される。（Ｂ）を満足するｄ行の行列Ｍ
は正確に２^(d-1)d/2個存在する。

対照的なパターンを示すこれらの行列の１つを、第２表
に示す。今、この行列中の１が三角形が繰り返し現われ
る反復パターンをなすことに留意されたい。このフラク
タル模様は「シェルピンスキー(Sierpinsky)ガスケッ
ト」と言われる［１４］。結果がわかってみると、この
行列を生成するより容易な手順を知ることができる。つ
まり、各要素は、すべてその右隣りと上隣りとの排他的
論理和である。こうしたビット配列は、パスカルの三角
形の２進等価配列である。

条件（Ａ）及び条件（Ｂ）が満足されると、２のべき乗
ストライドでメモリにアクセスするとき、無衝突アクセ
スが保証される。他のストライドも重要であり、このよ
うなストライドでも同様に衝突を解消させることが望ま
しい。しかし、すべてのストライド・アクセス衝突を解
消することは可能でない。

このシステムを汎用コンピュータ・システムで使用する
場合、ストライド・アクセスがメモリ・ホットスポット
を生じないということが重要である。あるいは、少なく
とも、ストライド・アクセスから生じるメモリ争奪問題
は、極めて稀である。

この問題に対処するために、所与の置換が様々なストラ
イド・アクセスをどれほどうまく処理できるかを示す目
安を定義する。ｓビット・アドレス空間Ｆ^sを写像する
ｄ×ｓ行列をＭとし、ｄ個のデバイスからなるシステム
を仮定する。すなわち、Ｍは集合Ｆ^sから集合｛０，
１，２，…，ｄ−１｝への写像である。ｔとａを整数で
あるとする。ただし、ｔはストライドであり、ａはスト
ライドの起点アドレスであると定義する。

ストライド中のアドレス、すなわちａ、ａ＋ｔ、ａ＋２
ｔ、…、ａ＋（ｄ−１）ｔからなる集合Ｖを考える。Ｍ
によってデバイスｉに写像されるＶの部分集合をＣ_iと
定義する。すなわち、 Ｃ_i＝｛ｘεＶ｜Ｍ（ｘ）＝ｉ｝ （ａ，ｔ）に関するＭの非一様性を、最大のＣ_i中の要
素数であると定義する。

Ｍ_a,t＝^ｍａｘ _{０≦ｉ≦ｄ−１}｜Ｃ_i｜ これは、ｄ個のアドレス、ａ、ａ＋ｔ、ａ＋２ｔ、…、
ａ＋（ｄ−１）ｔに対するストライド・アクセス中に任
意の１個のデバイスがアクセスされる回数の最大数を示
す。少なくとも、無衝突アクセスの場合、非一様性は１
であり、多くてもｄである。条件（Ａ）を満足する置換
を利用する、どの２のべき乗ストライド・アクセスで
も、非一様性は１または２である。

５１２個のメモリ・モジュールからなるシステムを仮定
し、第２表に定義するような９×２９行列を使って、様
々な起点アドレスａとストライドｔに対して、これらの
関数の非一様性（最大衝突数）を測定した。このような
システムで、乱数化関数を使ってデバイス番号を求める
と、非一様性は約５．１６となる。比較のため、この値
を第７、８、９及び１０図に含めた。「単純な」インタ
リービングも、このようなメモリ編成が不適当なことを
示すために含めてある。ランダムに発生させた１０，０
００個の異なる起点アドレスａ_iを使って、各ストライ
ドごとに、起点アドレスａとストライドｔに関連する非
一様性Ｍａ_i,tを計算した。すべてのｉについてのＭａ
_i,tの平均を、ストライドｔに対してプロットしてあ
る。

その他の行列 第２表に具体的に図示し上記に説明した、条件（Ａ）及
び（Ｂ）の制約を満足している行列の他に、第３表に示
す次の行列も条件（Ａ）及び（Ｂ）を満足する。

第２表でも第３表でも行列の最上行はすべて「１」であ
るが、第３表ではすべて「１」となる列がＳ²⁸からＳ⁰
にシフトされていることに留意されたい。第３表では、
その他のすべてのビット位置は、上隣りのビットと左隣
りのビットの排他的論理和によって決まる。行ｒ₀では
なく行ｒ₈がすべて「１」となった、別の１組の表を作
成することもできる。すなわち、すべて「１」である端
の行及び端の列以外の行列のビットを埋める一般法則を
一般化して、すべて「１」（ユニタリ）である行列の両
端部に最も近い側の以前に生成された２個のビットか
ら、各ビットの値が決定されるということができる。

本技法の有効性を示すために、２⁰から２¹⁰までの２の
べき乗ストライド・アクセスをすべて測定した。予想通
り、すべてのＭａ_i,jは２より小さいかまたは２に等し
い。他方、ストライドと最大５１２までの並列メモリの
数との最大公約数に応じて、純粋のインタリービングで
の衝突は着実に増加する。第７図のグラフは、ビット行
列乗算法を、純粋のインタリービング及びランダム化と
比較して示したものである。

１から１００までのストライドの場合に、同様のサンプ
ルを収集した。第８図及び第９図のグラフは、「純粋
の」インタリービングと「純粋の」インタリービングを
伴うビット行列乗算法の一般的挙動の比較を示したもの
である。第８図で、「純粋の」インタリービング関数を
使用する場合、０、２、４、８、１６、３２などのスト
ライドで高いピークを生じることに注意されたい。第９
図に示すように、本ビット行列乗法置換を使うと、これ
らのピークはかなり滑らかになる。本方法の挙動は、１
ないし１００のストライドの場合、「純粋の」インタリ
ービングよりもランダム関数の挙動に「より近い」挙動
を示すことを実証している。

ただし、「平均」よりも多くの争奪を引き起こすストラ
イドのあることを示唆するいくつかの鋭いピークが依然
として残っていることが注目される。制約条件（Ｂ）を
緩和することにより、これらのピークを滑らかにするこ
とができる。このような挙動を示す例を次節で示すこと
にする。

制約条件（Ｂ）を緩和することにより、２のべき乗でな
いストライドでの衝突をかなり減少させることができる
ことを示す。

第４表に示した９×２９行列は、制約条件（Ａ）に合う
ように作成したものであるが、制約条件（Ｂ）は緩和し
て、３≦Ｋ≦９ですべてのＫ×Ｋ部分行列が正則になる
ようにしてある。

第４表は制約条件（Ａ）を満足しているので、その２の
べき乗ストライドの場合の性能曲線は（第１図を参照し
て先に述べたように）第２表及び第３表の行列の場合の
と同じになるはずである。したがって、１ないし１００
のストライドの場合の性能だけを示すことにする。これ
を、第１０図に示す。この曲線の挙動は、ランダムに生
成させたメモリ・アクセス・パターンの挙動に接近して
いる。ある特定の動作環境に最適な行列を生成するある
種の一般的指針と方法論を提供するには、今後も研究が
必要となる。

ハードウェア実施例の説明 ストライドなどに関連する潜在的衝突を減少させるテス
トの上記の結果は、上記の写像手順のソフトウェア・シ
ミュレーションを使って得たものである。以下に、本発
明の好ましいハードウェア実施例を詳しく記載すると共
に、本発明の特徴を組み込んだアドレス置換ユニットの
好ましい設計に独自の貢献をする、本発明のある特徴に
ついて簡潔に論じる。本発明のそうした特徴とは、アド
レス写像用のビット行列乗算器で使用する装置と回路レ
ベルの数が最小であり、そのために動作速度が著しく改
善されるというものである。また、プログラム実行時間
中に動的に発生させ記憶装置にロードさせることのでき
る、異なる置換行列を用いることにより、様々な異なる
置換を容易に生成することができる。

ブール行列Ｍと論理アドレス・ベクトルＶが与えられて
いるものとすると、ブール・ビット行列乗算過程の論理
的深さは行列の列数ｓの対数となる。積ベクトル中のす
べての要素が、並行して計算できる。積ベクトルの各要
素は、対応するＭの要素が１となるＶの要素の排他的論
理和である。この計算は、まずＶの各要素とＭの対応す
る要素との論理積を算出し、次にｓ個の結果を排他的論
理和の２進ツリーで組み合わせることにより、ハードウ
ェア内で実行できる。事実、その結果得られる各ビット
は、Ｍの当該行とベクトルＶのビットごとの論理積演算
の結果のパリティである。

本発明のハードウェア実施例で必要な機能は直接的なも
のであるため、並列処理システムの個々の処理要素内部
のアドレス変換ハードウェアの一部としてブール行列乗
算を実施することが可能である。たとえば、前記で参照
した研究用並列処理システム（ＲＰ３）［１２］では、
すべてのインタリーブ式メモリが、デフォルトにより、
このような変換を受けるように設計されている。

上記の特徴を有する適当なハードウェア実施例の設計
が、図面に示されている。この実施例は、主としてアド
レス変換用に設計されているものの、ビット行列乗算に
よりアドレスまたはその他のデータの置換を行なうとい
うコンセプトを利用できる一般的能力を備えている。

第１図は、上記参照のＲＰ３［１２］など高度並列処理
共用メモリ・システムの高水準機能構成図である。この
システムは、ネットワーク１８を介して相互接続された
複数個（最大５１２個）の処理メモリ要素１０を含んで
いる。各処理メモリ要素（ＰＭＥ）は、ほぼ同じものと
見なされ、マイクロプロセッサ１２、アドレス変換ユニ
ット１４、ネットワークインターフェース１６、メモリ
２２から構成される。マイクロプロセッサ１２は、もっ
とも広く使われている通常のマイクロプロセッサの機能
を有し、必要なとき命令用またはデータ用あるいはその
両方用のシステム・メモリにアクセスする。アドレス変
換ユニット１４は、プロセッサが発行した論理アドレス
を、メモリ中の物理位置に直接写像可能な物理アドレス
に変換する。ネットワーク・インターフェース１６は、
特定の物理アドレスがローカル・メモリ２２にあるか、
それとも別の遠隔ＰＭＥにある別のメモリ要素２２から
アクセスしなければならないかを決定する。別のＰＭＥ
中の遠隔メモリ２２へのアクセスはネットワーク１８を
介して行なわれる。ＲＰ３は、すべてのメモリがすべて
のプロセッサに物理的にアクセスできる、緊密に結合さ
れたマルチプロセッサ・システムであることを想起され
たい。さらに、ＲＰ３では、各メモリ２２は、共用され
る上に、特定のプロセッサに局部的に隣接しており、ネ
ットワーク１８を経なくてもローカル・メモリにアクセ
スできる。

本発明の詳細部分は、アドレス変換ユニット１４中にあ
る。このユニットに関する機能構成図及びデータ流れ
を、第２図に示す。第２図に示すように、２９ビットの
仮想アドレス（０，２８）が、セグメント／ページ・テ
ーブル変換ユニット３２の入力線３０上に現われる。こ
のような仮想アドレッシング・システムでよく知られて
いるように、仮想アドレスは、最も通常の仮想メモリ・
システムの場合と同様に装置３２内のページ及びセグメ
ントのテーブル・ルックアップを介して、実アドレスに
変換される。その結果、線３４上に実アドレスが生じ
る。このアドレスの第９ないし第２８ビットは実アドレ
スのページに入るためのオフセットであり、第０ないし
第８ビットは実アドレスのセグメント及びページを指示
する。行列乗算ユニットによって、第０ないし第８ビッ
トを置換してノード番号とする。言い換えれば、特定の
アドレスがシステム全体のどのメモリに入っているかを
指定する。しかし、実アドレスの２９個のビットはすべ
て、行列乗算ユニット３４に入力される。この場合も、
システムは５１２個の異なるＰＭＥ及び関連する分離メ
モリ２２を含んでいると仮定する。したがって、このよ
うなノード・アドレスを指定するのに、９個のビット
（０，８）が必要である。ノード・アドレスを決定する
ためのビットの実際の数、及びオフセット・ビットの数
は、ある特定システム構成に対して指定されたインタリ
ーブ量に依存する。すなわち、特定のシステムがたとえ
ば２５６個のＰＭＥだけを含む場合、ノード番号を指定
するのに８ビットしか必要でなく、行列乗算ユニット３
４は８ビットだけを生成する。図の線３６上にこれらの
指定インタリーブ量が現われ、これが、置換した出力の
ビットがどれだけ生成されたかを制御する（特に示さ
ず）。実際の置換行列が記憶され、または行列乗算ユニ
ット３４がそれを利用できるものと仮定する。行列乗算
ユニット３４は、単に行列乗算ユニット内部の読み書き
メモリでもよい。

置換アドレスの９ビットがシステムによって生成された
と仮定すると、２９ビットの実アドレス全体が置換行列
の２９ビットの行の最初の９行と次々に（９回）乗じら
れ、したがって線３８上に９ビットのノード・アドレス
を生成することが理解できる。この９ビットのノード番
号またはアドレスが、線４０上の第９ないし第２８ビッ
トと組み合わされ線４２上に２９ビットの物理アドレス
を生成する。

次に、第３図には、多数の異なるハッシング関数演算を
行なう汎用ハードウェアの全般的機能構成図を示す。ブ
ロック１０は、任意の大型システム記憶装置を指し、Ｒ
ＡＭまたは任意の周知のメモリ・システムでよい。必要
な特性を有する複数の行列がその中に記載され、システ
ム制御下でそれにアクセスできる。アドレスがハッシュ
されるものと仮定すると、入力アドレスＳ（０：２８）
が入力線１２を介してブロック１４に指示される。ブロ
ック１４は、実際のビット行列乗算機能を実行して、ハ
ッシュ処理された出力アドレスを蓄積する。そのアドレ
スは線１６上にアドレスＳ（０：２８）として現われ、
それが計算システム全体のメモリ・アクセス部分に提示
される。

やはり自明なように、この特定システム中で２９ビット
のアドレスが用いられる。しかし、同様に自明なよう
に、異なるアドレス空間やアドレス・サイズも利用で
き、本発明の教示に従って、それに適当なハッシング機
能をこれに適用することができる。

次に、第４図には、第３図で非常に一般的に開示したシ
ステムの機能構成図を示す。この図には、本発明の好ま
しい実施例の機能編成とデータ流れが開示されている。
主要な機能的構成要素のすべてと好ましいデータ流れが
示されている。この図は、所望のハッシング機能を実施
するために行なわれなければならない一連の動作の説明
と共に、本発明の原則を明確に示している。様々の要素
への個々の制御線は、コンピュータ技術に熟練したどの
ディジタル技術者にとっても明白のはずなので、図示し
ていないことに留意されたい。

次に第４図を参照すると、第３図と同様に、入力アドレ
スＳが線１２上に現われ、行列がブロック１０内に記憶
され、ハッシング操作が完了した後に、ハッシュ処理さ
れた出力アドレスＳ′（０：２８）が線１６上に現われ
ることが注目される。レジスタ、内積ボックスなどを含
めて、回路の残りの部分は、行列ハッシング機能１４の
必要な操作を実行するものである。

この実施例では、上記で一般的に示したように、入力ア
ドレスの９個のビットが大型共用メモリ・システムでメ
モリ・モジュールの選択を実行する高位ビットなので、
それらのビットだけをハッシングすればよいと仮定した
ことにも留意すべきである。この状況では、完全な２９
ビットのハッシング行列を生成する必要がある。ただ
し、高位ビット、たとえば０：８ビットだけをハッシン
グすればよいので、行列の最初の９行だけをハッシング
操作に投入すればよい。９：２８ビットは変化しないの
で、図に示すように、入力レジスタ２０から出力レジス
タ２２に直接転送してよい。別法として、システム内部
で完全な一様性を得るために、２９個のハッシュ処理出
力ビットすべてを生成し、それによりハッシング機能で
完全な２９×２９行列を用いることが望ましい場合、行
列の第９行ないし第２８行を修正して、行列の第９列な
いし第２８列の第９行ないし第２８行に恒等部分行列が
現われるようにすることができる。残りの９列は、すべ
てゼロとなる。こうすると、入力アドレスの第９ないし
第２８ビットはハッシング操作の影響を受けないように
なることを理解されたい。ただし、本実施例で前述した
ように、ハッシング機能をアドレス生成専用、より詳し
くはメモリ・モジュール選択専用とし、最初の高位９ビ
ットだけでハッシュ処理が必要になると仮定する。

ここで、特にシステムの連続操作を参照する。まず、必
要な９行全部がレジスタ・アレイ２６にロードされるま
で、行列記憶機構１０からマルチプレクサ２４のＡポー
トを介して、先入れ先出しレジスタ・アレイ２６に一度
に２９ビットの行を１行ずつ、所望の行列をロードす
る。上記のように、全部で２９ビットのアドレスのうち
９ビットだけを置換すればよいので、２９ビットの行を
９行だけシステムに入力すればよい。

次に新しいアドレスＳ（０：２８）を線１２を介して入
力レジスタ２０の指示したビット位置へロードする。

次に、指示されているように、入力レジスタ及びハッシ
ュ処理すべき新アドレスの第９ないし第２８ビットを、
直接出力レジスタ２２の第９ないし第２８ビット位置に
ゲートする。上記のように、こうすると、結局のところ
第９ないし第２８ビットが、この特定アプリケーション
に望まれるハッシュ処理された出力アドレスＳ′の一部
として形を変えずに現われることが可能となる。

次に、システム制御装置内のループ・カウンタを、８に
等しい値ｉに設定する。このカウンタは図示されていな
いが、このような先入れ先出しレジスタ・アレイでまっ
たく常用のものである。このカウンタまたはその他のカ
ウンタの制御により、レジスタ・アレイを先入れ先出し
または後入れ先出しレジスタとして、あるいは何か他の
ランダム・アクセス方式で動作させることができる。

ループ・カウンタの制御下で、行列の第ｉ行、Ａ（ｉ）
を先入れ先出しレジスタ２６の出力にゲートする。同時
に、この行がマルチプレクサ２４のＢポートを介して先
入れ先出しレジスタの入力に使用できるようにする。こ
のデータ経路が設けられているのは、先入れ先出しレジ
スタが一連の９個の２９ビット・シフトレジスタになっ
ており、カウンタを特定の行にアクセスするのに使うの
でなく、シフト数と比較して点検する場合であることに
留意されたい。ただし、この設計の詳細は任意選択であ
ることを理解されたい。主要な用件は、行列の様々な行
が先入れ先出しレジスタの出力に、したがって、ビット
行列乗法演算が実際に実行される内積機能ブロック２８
への入力に順次使用できるようにすることである。

入力レジスタ２０の第０ないし第２９ビットが、常に内
積機能ブロック２８への２次入力として利用可能なこと
にも留意されたい。すなわち、２９ビットを含む行列の
ある行で、２９ビットを含む入力アドレスとの内積乗算
を実行すると、最終的に、単一ビットが生成され、それ
が出力レジスタ２２の適当な記憶位置にゲートされる。

こうして、線２７上の１ビット出力ＩＰＯＵＴが、出力
レジスタ２２の上方の位置にシフトされる。レジスタ２
２の上位９ビット位置（０：８）は、９ビットの直列入
力並列出力シフト・レジスタとして機能する。すなわ
ち、レジスタの最上部に新しいビットをロードするごと
に、現在の内容全体が１ビット位置ずつ下方へシフトす
る（もちろん第８位置で終わる）。当技術の専門家には
明らかなように、出力レジスタ２２の上位９ビット位置
が新しい置換されたアドレス・ビットでロードされる
と、レジスタの内容全体（０：２８）がシフトされて、
新しい置換出力アドレスＳ′を形成する。

システムの操作の次のステップに進むと、制御カウンタ
またはループ・カウンタをテストして、内積生成が９回
反復して行なわれたかどうか、及びカウンタｉが１だけ
減分されていないかどうかを調べる。さらに、行列内に
新しい行をロードして内積生成を実行する上記ステップ
を繰り返し、新しいビットを出力レジスタ２２にゲート
させる。

必要な反復を実行し終えると、ビット行列乗算ユニット
からメモリ・システムに新たな出力アドレスＳ′をゲー
トし、次の３つのうちどれかを行なうことを、システム
制御装置が指示する。手順を終了する；次のアドレス置
換を実行する前に新しい行列をシステムにロードする；
あるいは現在の行列によってハッシュ処理すべき新しい
アドレスを入力レジスタにロードする。

ハードウェアの上記操作の簡潔で完全な記述を第５表に
示す。またやや記述的な形で第６表に示す。当業者の理
解できる範囲内であると考えられる、シフト線、減分
線、ゲート線、パリティ・チェック回路、初期接続の手
順と操作など、このシステムの操作の細かい詳細の多く
は具体的に示していないことに留意されたい。こうした
ものを含めると、本明細書に記載する本発明の全般的な
コンセプトが理解しにくくなるためである。

第６表 １．所期の行列（９行、１行２９ビット）を行列記憶機
構から先入れ先出しレジスタにロードする。

２．新しいアドレスを入力レジスタにロードする。

３．第９ないし第２８ビットを入力レジスタから出力レ
ジスタにコピーする。

４．ループ・カウンタを設定する：ｉ＝８ ５．行列の第ｉ行Ｍ（ｉ）を先入れ先出しカウンタの出
力に入れる。そのコピーを先入れ先出しレジスタの入力
に書き込む。

６．内積機能ボックスの出力ＩＰＯＵＴは、先入れ先出
し出力（ＦＦＯＵＴ）と入力レジスタの内容［Ｓ（０：
２８）］の１ビット内積である。

７．１ビット出力ＩＰＯＵＴを、（第２図で下方へ）出
力レジスタの９ビット・シフト・レジスタ部分へ、すな
わち出力レジスタ（０：８）へシフトする。

８．カウンタをテストして、ステップ５ないしステップ
７を９回反復し終わったかどうかを調べる（終了してい
ない場合は、カウンタｉの値を減分してステップ５に戻
る。終了した場合には、（次のステップへ）進む）。

９．出力が有効だという信号を宛先に送る。

１０．ステップ１またはステップ２に戻る。

さらに、本発明を実施するためのハードウェア設計は、
多数の異なる形をとることができ、本実施例で採用した
手法は、空間すなわちハードウェアの反復ではなく時間
上の反復であることに留意されたい。すなわち、最小量
のハードウェアを反復して使い、出力ビットＳ′を１つ
１つ生成する。別法は、９個のハッシュ処理された出力
ビットＳ′（０：８）を並列的に計算するために、内積
ハードウェアを複製して９個の別々の機能ユニットを設
けるという犠牲を払って、アドレスを完全にハッシュ処
理するための時間を最小にするものである。したがっ
て、ここに開示した好ましい実施例は、操作を完了する
ための時間が最小というのではなく、ハードウェア全体
のコストの点で好ましいものであると理解されたい。

第５図は、第４図に示した内積ブロック２８をどのよう
にすれば具体化できるかの詳細な論理的概略図である。
第５図は、入力として下記のものを使って上位第ｉビッ
トＳ′（ｉ）を生成する回路を特に示したものである。

１．線７２を介してレジスタ２０からブロックに供給さ
れる２９ビットの実アドレスＳ_(0,28) ２．線７０を介してレジスタ２６からブロックに供給さ
れる行列Ａの２９ビットの第ｉ行 アドレス及び行ビットが２９個のＡＮＤ回路７４に供給
され、その際に、最上部のＡＮＤゲートにはＳ０及びＡ
（ｉ，０）が供給され、最下部のＡＮＤゲートにはＳ２
８及びＡ（ｉ，２８）が供給される。線７６上に現われ
る２９個の出力が全体でモジューロ２加算器７８への入
力を形成し、ここで論理的モジューロ２の加算機能によ
りこれらの２９個の入力が組み合わされて単一の出力ビ
ットとなる。当業者なら理解できるように、これは「排
他的論理和」によって行なうことができる。もちろん、
内積機能は、多数の異なる論理回路構成によって実行で
きることを理解されたい。出力Ｓ′（ｉ）は、レジスタ
２２への入力線である線２７上に現われる。

上記のように、この回路は、必要とされる、アドレスの
個々のビットとハッシング行列から現に供給される行と
のビット行列乗算を実行する。

これで、本発明の好ましい実施例の説明を終える。行列
記憶ブロック１０に適当な行列を供給することにより、
ここに開示したハードウェアによって複数の異なる置換
機能を実行し、大型共用メモリの操作を改善できること
は明らかである。２のべき乗ストライド・アクセス問題
の解消または軽減は、本発明を用いて軽減できるタイプ
の問題の一例にすぎない。さらに、本発明を利用する
と、データの特徴が異常なために上記のようにメモリ空
間全体の利用が不十分な、別のタイプのメモリ・システ
ム中でのデータ分布が改善されるはずである。さらに、
特にこの目的用に設計されたハッシング行列を利用す
る、ここに開示した発明を用いて選択（アドレッシン
グ）をハッシュすることにより、多重入出力装置の利用
を改善することができる。このような行列は正則でなけ
ればならないことに留意されたい。

以上、好ましい実施例に関して本発明を説明してきた
が、当業者なら、頭記の特許請求の範囲に記載されてい
る本発明の精神及び範囲から逸脱せずに、上記以外の特
定ハードウェアに対する変更や修正を行なえることは明
らかである。

これで、本発明のビット行列乗算置換手順全体を実行で
きる、ここに開示した好ましいハードウェア実施例の説
明を終える。当業者なら他の構成も容易に設計できるは
ずである。

第６図は、高度並列共用メモリ・システムで使用される
タイプの相互接続ネットワークの代表である反転ベース
ライン・ネットワークを示す。このネットワークの構成
を用いると、経路指定に先立って本発明に基づいてこの
ようなアドレスを置換した場合にだけ、すべての２のべ
き乗ストライド・アクセスに対して無衝突データ経路決
定が可能となる。このシステムは、本発明の一部をなす
ものではなく、例示のために示したものにすぎない。当
業者には明らかなように、これは多段両面ブロッキング
・ネットワークである。ごく簡単に言うと、その動作は
次の通りである。アドレス・サブフィールドの設定に応
じて、Ａ、Ｂ、Ｃと記号を付けた３列のスイッチが２つ
の入力のどちらかを特定の出力に接続する。その際に、
フィールドが０の場合には、各スイッチの上側の出力が
活動状態となり、アドレスまたはサブフィールドが１の
場合には、各スイッチの下側の出力が活動状態となる。
左側の２進数の列は、ソースすなわちユーザのアドレス
を表わし、右側の３桁の２進数の列は、宛先すなわちサ
ーバのアドレスを表わす。両方の列の同じ行に同じ数が
現われている場合、ソースが宛先すなわちサーバでもあ
ることを示すことに留意されたい。つまり、この図で、
ソース０００が自分自身のメモリを利用したいと思う場
合には、宛先アドレスを０００とする。容易に理解され
るように、この結果、宛先アドレス０００がスイッチ制
御行列に与えられるので、３列全てで上側のスイッチが
上側の出力として選択される。さらにまた、図を検討す
ると気がつくように、図中の小さなサブフィールドａ、
ｂ、ｃがスイッチ列Ａ、Ｂ、Ｃを制御する特定のサブフ
ィールドを指定する。したがって、ソース０１１からア
ドレス１１１に接続したい場合、ソース０１１からアド
レス１１１が与えられ、３つのスイッチの下側の出力９
０、９２、９４を活動化させて、この接続が実現され
る。

第２の例として、この場合にソース００１を宛先１１０
に接続したいと仮定すると、ソース００１からネットワ
ーク用のスイッチ制御行列にアドレスまたは行列スイッ
チ・コマンド１１０が提示されるので、スイッチ・ブロ
ック９６及び９２の下側の出力が活動状態になり、ブロ
ック９４の上側の出力が活動状態になって、所望の経路
指定が実現される。すなわち、ソースと宛先の間のどの
ような所望の相互接続でも、このシステムによって実現
できる。もちろん、上記のように、スイッチ争奪、すな
わち同時に２つの要求が同じスイッチを通過すること
が、選択した行列を本明細書で開示するアドレス置換手
順中に記載したように利用することによって軽減できる
はずである。

Ｆ．発明の効果 インタリーブ式大型共用メモリ・システムなどある種の
物理装置の利用を改善するための本明細書に記載のアド
レス置換システムの説明を終えたので、何らかの結論を
出すことができる。本システムは、アドレスが２のべき
乗だけ離されたデータを多数のプロセッサが参照すると
きに現われるメモリまたは入出力のホットスポットを回
避する点で、特に価値がある。写像機能を適当に選択す
ることにより、ネットワークの争奪も回避できる。たと
えば、あらゆる２のべき乗ストライド・アクセスの場合
に、反転ベースライン・ネットワークでの争奪をすべて
回避できることを示した。この方法は、その他のストラ
イド・アクセスの争奪を全面的には解消できないもの
の、そのような争奪がランダムなメモリ参照に付随する
争奪と同程度になる。

ここに開示したアドレス置換法をハードウェアで実現す
る本発明を利用すると、実に様々な行列を容易にシステ
ムに記憶させ、自動的にそれを呼び出して、最小の努力
で様々な置換パターンを実現することができ、したがっ
て、異なる様々な条件で資源管理が改善される。このハ
ードウェアは、既知の技術で容易に実現でき、たとえば
全体的メモリ・アクセス時間を著しく増加させることな
く動作できる。

本明細書に記載した本発明の使用の特定の例は、この手
順の限られた数の応用例にすぎない。本発明を利用する
と、様々なネットワーク構成のアクセス方法の改善がも
たらされ、入出力システムの設計に役に立つものと考え
られる。ここに開示した、この手順のハードウェアによ
る実施例は、本発明の好ましい実施例を表わすものであ
るが、本発明の精神及び範囲から逸脱せずに、前述のよ
うにハードウェアに多くの変更を加えることが可能であ
ることをはっきりと理解されたい。

【図面の簡単な説明】

第１図は、共用メモリを有する高度の並列処理システム
の機能的構成図である。各プロセッサには、他のすべて
のプロセッサから多段相互接続ネットワークを介してア
クセスできるメモリ・モジュールが付随している。 第２図は、第１図のシステムで利用できる本発明の原理
を具体化した、アドレス変換ユニットの機能的構成図で
ある。 第３図は、本発明の特徴を組み込んだ、第２図に示す行
列乗算ユニットの単純化した高水準構成図である。 第４図は、第３図の行列乗算ユニットのデータ流れを示
す詳細な機能的構成図である。 第５図は、第４図に示したような内積ブロックの論理的
構成図である。 第６図は、この利用は本発明の利点を明快に示す、第１
図の並列処理共用メモリ・システムで多段相互接続ネッ
トワークとして使用できるような反転基線ネットワーク
の機能的構成図である。 第７図は、本発明に記載する行列乗算方法と、ハッシュ
処理のない純粋のインタリービングと、純粋なランダム
機能という異なる３つのインタリービング方法を比較し
たグラフである。このグラフは、ストライドのｌｏｇ₂
をｘ軸とし、最大衝突数（すなわち、各メモリ・モジュ
ールに対するアクセス合計の最大値）をｙ軸として、プ
ロットしてある。図に示した実験で使用したストライド
・アクセスは、様々な２のべき乗である。 第８図は、純粋のインタリービング法と、第６図で使用
したものと同じ純粋のランダム機能とを比較したグラフ
である。このグラフは、ストライドをｘ軸とし、最大衝
突数（すなわち、各メモリ・モジュールに対するアクセ
ス合計の最大値）をｙ軸として、プロットしてある。こ
の実験で使用したストライド・アクセスは、１から１０
０までである。 第９図は、本発明に記載する行列乗算方法と、第７図で
使用したものと同じ純粋なランダム機能とを比較したグ
ラフである。このグラフは、ストライドをｘ軸とし、最
大衝突数（すなわち、各メモリ・モジュールに対するア
クセス合計の最大値）をｙ軸として、プロットしてあ
る。この実験に使用したストライド・アクセスは、１か
ら１００までである。 第１０図は、制約条件（Ｂ）が緩和された行列をビット
行列乗算置換演算に利用した、第８図と類似のグラフで
ある。 １０‥‥処理メモリ要素、１２‥‥マイクロプロセッ
サ、１４‥‥アドレス変換ユニット、１６‥‥ネットワ
ーク・インターフェース、１８‥‥ネットワーク、２２
‥‥メモリ、３２‥‥セグメント／ページ変換ユニッ
ト、３４‥‥行列乗算ユニット。

Claims (2)

【特許請求の範囲】
1. 【請求項１】複数のアドレス可能なサーバー装置に対す
   る複数の利用装置のアクセス可能性を最適化するアドレ
   ス置換装置であって、 各々異なった置換を定義する複数の所定のｍ×ｎの置換
   行列を記憶する手段と、 上記記憶手段から所望の行列をアクセスする手段と、 置換すべきアドレスをアクセスする手段と、 上記アクセスされた行列のｍ個の連続したｎビット行と
   上記アドレスの選択されたｎビット・フィールドとのビ
   ット行列乗算を実行する手段と、 置換されたｍビットを特定のサーバー装置をアクセスす
   るために利用する手段とを含む アドレス置換装置。
2. 【請求項２】複数ユーザー複数サーバー・コンピュータ
   ・システムにおける論理アドレスを物理アドレスに変換
   するアドレス置換装置であって、 置換行列及びｎビットの論理アドレスにアクセスする手
   段と、上記ｎビット・アドレスに上記行列のｍ個のｎビ
   ット行をビット行列乗算してｍビットの物理アドレスを
   形成する手段と、上記ｍビットの物理アドレスを用いて
   上記マルチ・サーバー・システムをアクセスする手段と
   を含むアドレス置換装置。