JPH037976B2 - - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、大規模な数値計算を支援するための
高性能な外部メモリ装置の方式に係る。

（従来技術とその問題点） いわゆるスーパーコンピユータでは、大規模な
数値計算をサポートするために高速の外部メモリ
が提供されている。

提供されている外部メモリのアーキテクチヤ
は、通常、デイスクデバイスと同様、ブロツクラ
ンダムアクセスを採用している。ブロツクランダ
ムアクセスとは、例えばベクトル｛v_i｝は、ブロ
ツクに分けられ、v₀v₁…v_o-1，v_ov_o+1…v_2o-1，v_3o
…というように長さｎのブロツクとして、外部メ
モリに格納される。このアーキテクチヤの採用
は、従来のプログラムの書き換えやオペレーシヨ
ンシステムの大幅な変更を避けることを目的とし
ている。

しかし、ブロツクランダムアーキテクチヤは、
数値計算では、不適当なケースがある。例えば、
２次元アレイ｛A_ij｝を考えよう。このアレイが
A₀₀A₀₁…A_0o-1，A_0o…，A₁₀A₁₁…というように
（ｉ，ｊ）の順でブロツクに分けられ、格納され
ているとする。いま｛A_ij｜ｊ∈〔０，ｍ〕｝ｉ、
すなわち、ｉを固定し、ｊだけ０，１，２…と変
えて得られるベクトルA_i0，A_i1，…A_io-1，A_io…
を入出力する場合、ブロツク単位に転送すること
で、効率の良い入力、出力を行うことができる。
しかし、一方、｛A_ij｜ｉ∈〔０，ｍ〕｝ｉで表わ
されるベクトルA_0j，A_1j，A_2j…については、そ
れぞれの要素を入出力する場合、それぞれ別のブ
ロツクを参照する必要があり、長さｍのベクトル
の入力又は出力にともなつて、最悪で、ｍブロツ
クの入力または出力を必要とする。このようなア
クセスパターンは、例えば、偏微分方程式の差分
解法の１つである陰解法では、異なつた軸による
スキヤンが必要なため、必然的に存在する。その
他にも多次元FETや行列の積にも現われる。す
なわち、数値計算では、このようなアクセスパタ
ーンは、ごく普通に現われると考えてよい。した
がつて、ブロツクランダムアクセスの外部メモリ
を、効率良く使用するには、プログラムを工夫す
る努力が必要で、また、そうした努力によつても
高い性能を引き出せないことがある。

（発明の目的） 本発明の目的は、語単位の処理を可能にするこ
とにより、きわめて高性能で、かつ柔軟なアクセ
スを実現する外部メモリ装置を提供することにあ
る。

（発明の構成） 本発明によれば、計算システムからの指令にも
とずきデータの転送を行なう外部メモリ装置であ
つて、素数個のメモリモジユールと前記計算シス
テムからのベクトルデータを保持する入力バツフ
アと、前記計算システムからのベクトルデータを
保持する出力バツフアと、前記メモリモジユール
の出力を線形置換し前記出力バツフアに送る線形
置換手段と、前記入力バツフアの出力を逆線形置
換し前記メモリモジユールに送る逆線形置換手段
と、前記計算システムからの指令を解釈し、前記
メモリモジユールへのアドレスは書き込み読み出
し指令の生成を行うとともに、前記線形置換手段
と前記逆線形置換手段に対して制御パラメータを
送る制御部とから構成されることを特徴とする外
部メモリ装置が得られる。

（発明の原理） つぎに、本発明の原理について説明する。ま
ず、２次元アレイ｛A_ij｝を考える。このアレイ
の要素へのアクセスは、計算アルゴリズムに依存
するが、代表的なアクセスは、列方向か行方向、
あるいは対角方向が想定される。簡単のため、こ
のアレイのサイズをＡ（４，４）とする。メモリ
には次のように格納されているとする。

A₀₀ A₀₁ A₀₂ A₀₃ A₁₀ A₁₁ A₁₂ A₁₃ A₂₀ A₂₁ A₂₂ A₂₃ A₃₀ A₃₁ A₃₂ A₃₃ このアレイの列方向のデータ要素は隣り合つて
格納されている。この場合を１−順序ベクトル形
式、または簡単に順序ベクトルと呼ぶ。一方行方
向のデータ要素A₀₀，A₁₀，A₂₀，A₃₀やA₀₁，A₁₁，
A₂₁，A₃₁といつたベクトルは、４要素はなれた
要素に対するアクセスとなる。また、対向要素
A₀₀，A₁₁，A₂₂，A₃₃は、５要素はなれた要素に
対するアクセスとなる。それらを各々４−順序ベ
クトル、５−順序ベクトルに対するアクセスと呼
ぶ。

３次元データアレイについても同様、Ａ（n₁，
n₂，n₃）について（ここでn₁，n₂，n₃はサイズを
表わす）A_ijkのｋを０，１，２，…と変えて得ら
れるベクトルは順序ベクトルであり、ｊを変えて
得られるベクトルはn₃−順序ベクトル、ｉを変え
て得られるベクトルは、n₂・n₃−順序ベクトルで
ある。

一般的には、外部メモリから計算システムへの
データの転送はｎ−順序ベクトルを順序ベクトル
に置換し転送することであり、外部メモリへの書
き込みは、順序ベクトルをｎ−順序ベクトルに置
換し、転送することに対応する。もう少し具体的
に説明するため、線形置換L_dを次のように定義
する。

L_d：ｂ＋ｄ・ｉ→ｉ （mod Ｍ） また、その逆置換L^-1 _dは L^-1 _d：ｉ→ｂ＋ｄ・ｉ （mod Ｍ） ここで、ｂとｄは定数であり、ｄはｄ−順序ベ
クトルに対応する定数である。

ｂとｄはつぎのように与えられる。あるプログ
ラムを例として考える。以下の例において、添字
i₁，i₂，i₃は０から始まり、各々n₁−１，n₂−１，
n₃−１で終るものとする。

ここで、i₁，i₂，i₃は定数であり、ｋはindex変
数である。アレイＡがアドレスａから格納されて
いるとすると、Ａ（i₁，i₂，ｋ）のアドレスはａ＋
n₂・n₃・i₁＋n₃・i₂＋ｋであるから、ｂ＝ａ＋
n₂・n₃・i₁＋n₃・i₂，ｄ＝１である。同様にＡ（i₁，
ｋ，i₃）についてはｂ＝ａ＋n₂・n₃・i₁＋i₃，ｄ＝
n₃である。

つぎに、メモリへの格納を説明する。高速の転
送を行うには、並列処理が本質的であり、メモリ
は複数のメモリモジユールに分けられる。アレイ
データはメモリモジユールに沿つてベクトルとし
て格納される。例えば、A_ijは、メモリモジユー
ル０にA₁₁、モジユール１にA₁₂、モジユール２
にA₁₃，…というように格納される。

メモリモジユールがＭ個あるとすると、アドレ
スAddのモジユール番号、モジユール内アドレス
は、それぞれ Add mod Ｍ，〔Add／Ｍ〕 である。

また、転送すべきベクトル要素のアドレスは、
第ｉ番目のアドレスについて書けば、ｂ＋ｄ・ｉ
であり、モジユール番号、モジユール内アドレス
はそれぞれ、 （ｂ＋ｄ・ｉ）mod Ｍ，〔（ｂ＋ｄ・ｉ）／
Ｍ〕 と表わされる。ここで〔ｘ〕はｘより小さくかつ
最大の整数を表わす。

ここで、＝ｂ（mod Ｍ），＝ｄ（mod Ｍ）
とすれば第ｉ番目のモジユール番号は （＋・ｉ）mod Ｍ と表わすことができる（整数論より既知）。

線形置換は （＋・ｉ）→ｉ（mod Ｍ） であり、この置換は、（，Ｍ）＝１、すなわち、
ｂとＭが互いに素であるとき、競合なしに行われ
る。したがつて、Ｍは素数から選ばれることが望
ましいが、競合を解決する手段を併用すれば、素
数に限定する必要はない。

線形置換はつぎのように実行される。まずに
対応し、−順序ベクトルを順序ベクトルに変換
し、つぎにに対応し、得られた順序ベクトルを
回転置換する。この置換を例で説明する。いま、
メモリモジユールが５つあるとし、アレイＡのサ
イズが８×８であり、アドレス０から格納されて
いるとする。Ａ（１，２），Ａ（２，２），Ａ（３，
２），Ａ（４，２）というベクトルはｂ＝（A1，
２）のアドレス）とし、ｄ＝８とすることで要素
のアドレスが得られる。Ａ（１，２）のアドレス
は10であり、＝10mod5＝０，＝8mod5＝３
である。各要素のアドレスはＡ（１，２），Ａ（２，
２）の順で 10，18，26，34 であり、それぞれ、メモリモジユール０，３，
１，４に入つている。

各モジユールから読み出されたベクトルはＡ
（１，２），Ａ（３，２），−，Ａ（２，２），Ａ（４
，
２）の順であり、 ０ ３ １ ４ ０ １ ２ ３ の置換が行われなければならない。このため、
＝０すなわち、回転置換を０ポジシヨン行う。得
られるベクトルは Ａ（１，２），Ａ（３，２），−，Ａ（２，２），Ａ
（４，２） である。このベクトル要素を３要素飛びに集める
と Ａ（１，２），Ａ（２，２），Ａ（３，２），Ａ（４
，
２），− となり、順序ベクトルが得られる。この置換をス
キツプ置換という。

このように、回転置換と、スキツプ置換を組み
合せることで線形置換を実現できる。

一方逆置換L^-1 _dは、以上述べた線形置換の逆置
換であり、まず、スキツプ置換を行い、ついて回
転置換を行うことで達成される。この場合のスキ
ツプ置換、回転置換に与えられるパラメータb′，
d′は b′＝Ｍ−ｂ（mod Ｍ） d′・ｄ＝１（mod Ｍ） から得られる。

（実施例） つぎに図面を用いて詳細に説明する。第１図は
本発明の一実施例を示すシステム構成図である。
計算システム１は、外部メモリ装置２に、転送線
１８を介して指令を、転送バス１３，７１を介し
てベクトルデータの入出力を行う。計算システム
１は次の形式のコマンド（指令）を制御プロセツ
サ８に送る。

command（ｂ，ｄ，ｎ） ここでcommandはreadかwriteであり、ｂは
ベクトルのベースアドレス、ｄはスキツプ距離、
ｎは転送すべきベクトル長である。

まず、ベクトルデータの書き込みについて説明
する。転送線１８を介してwrite（ｂ，ｄ，ｎ）の
指令が制御プロセツサ８に送られる。制御プロセ
ツサ８は（ｂ，ｄ）にもとづいて、b′，d′を計算
する。（この計算は原理の説明で説明した）。計算
されたb′，d′は転送線８４を介して、逆線形置換
手段４に送られ、入力バツフア３とメモリモジユ
ール５₁〜５_nの間のデータの転送パスが確立され
る。また、制御プロセツサは〔（ｂ＋ｄ・ｉ）／
Ｍ〕の計算を行い、各モジユール内アドレスを計
算し、計算されたアドレスは転送線８３を介し
て、入力バツフア３に送られ、転送線３４₁〜３
４_n、逆線形置換手段４、転送線４５₁〜４５_nを
へてメモリモジユール５₁〜５_nに送られるととも
に、制御プロセツサ８はメモリモジユール５₁〜
５_nにwrite指令を転送線８５を介して送る。これ
でアドレスの設定がされる。つぎに計算システム
１から送られてきたベクトルデータを入力バツフ
アに取り込み、転送線３４₁〜３４_n、逆線形置換
手段４、転送線４５₁〜４５_nを介してメモリモジ
ユール５₁〜５_nに送られ書き込まれる。ベクトル
長ｎは、書き込むべきベクトルの範囲を示すもの
で、入力バツフア３において、この情報により、
マスクビツトが生成され、不正な書込みを防止す
る方式（図示せず）がとられる。

つぎに読み出しについて説明する。計算システ
ム１からはread（ｂ，ｄ，ｎ）のコマンドが送ら
れてくる。制御プロセツサ８は書き込みと同様に
して、各メモリモジユール５₁〜５_nにアドレスを
生成し送る。そして転送線８５を介して各メモリ
モジユール５₁〜５_nに読み出し指令を送り、ベク
トルデータとして、読み出されたデータを転送線
５６₁〜５６_nを介して線形置換手段６に送る。こ
の前に制御プロセツサ８は転送線８６を介し、線
形置換手段６に（ｂ，ｄ）から（，）を生成
し、転送パスを確立している。線形置換手段６に
よりデータベクトルの置換が行われ、転送線６７
_１〜６７_nを介して出力バツフア７にデータは送ら
れる。ベクトル長ｎは、有効なベクトルの範囲を
示すために用いられる（図示せず）。出力バツフ
ア７の内容は転送バス７１を介し、計算システム
に送られる。

以上のように計算システムと外部メモリの間で
データの転送が行われる。

つぎに、第２図に線形置換手段の構成例をブロ
ツク図で示す。回転置換手段６₁は転送線８６を
介して送られてくる（，）のうち、に対応
して、ｂポジシヨン回転置換を実行するものでシ
フトレジスタにより実現される。出力は、転送線
６₁₁〜６_1nを介してスキツプ置換手段６₂に送ら
れる。スキツプ置換手段６₂は（，）のうち、
ｄに対応して、−飛びのスキツプ置換を行う。
このスキツプ置換は、Swanson，R.C.
（“Interconnections for Parallel Memories to
Unscramblep−ordered Vectors，”IEEE，
Trans on Comput，Vol.C−23，NO.11，
pp1105〜1115（1974））に述べられているｋ−
apart interconnection（ｋ−飛び相互結合）によ
り容易に実現できる。

（発明の効果） 以上に述べたように、本発明によれば、数値計
算で現われる大規模なデータ構造（主として行列
やアレイ）に対する柔軟アクセスが可能になり、
さらに並列処理により高速の処理が可能となる。

また、メモリモジユールの数を素数としたこと
でメモリの競合をなくすことができ、非常に簡単
な制御で、また簡素なシステム構成で高性能な外
部メモリ装置を可能にしている。

【図面の簡単な説明】

第１図は本発明の一実施例を示す外部メモリ装
置のシステム構成図、第２図は外部メモリ装置の
一部である線形置換手段のブロツク図である。 図において、１……計算システム、２……外部
メモリ装置、３……入力バツフア、４……逆線形
置換手段、５₁〜５_n……メモリモジユール、６…
…線形置換手段、７……出力バツフア、８……制
御プロセツサ、をそれぞれ示す。

Claims (1)

【特許請求の範囲】
1. １ 素数個のメモリモジユールと、計算システム
   からのベクトルデータを保持する入力バツフア
   と、前記計算システムからのベクトルデータを保
   持する出力バツフアと、前記メモリモジユールの
   出力を線形置換し前記出力バツフアに送る線形置
   換手段と、前記入力バツフアの出力を逆線形置換
   し前記メモリモジユールに送る逆線形置換手段
   と、前記計算システムからの指令を解読し、前記
   メモリモジユールへのアドレスや書き込み読み出
   し指令の生成を行なうとともに、前記線形置換手
   段と前記逆線形置換手段に対して制御パラメータ
   を送る制御部とから構成されることを特徴とする
   外部メモリ装置。