JPH037977B2 - - Google Patents
Info
- Publication number
- JPH037977B2 JPH037977B2 JP59157159A JP15715984A JPH037977B2 JP H037977 B2 JPH037977 B2 JP H037977B2 JP 59157159 A JP59157159 A JP 59157159A JP 15715984 A JP15715984 A JP 15715984A JP H037977 B2 JPH037977 B2 JP H037977B2
- Authority
- JP
- Japan
- Prior art keywords
- vector
- data
- sent
- permutation
- transfer line
- 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
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
- G06F15/76—Architectures of general purpose stored program computers
- G06F15/80—Architectures of general purpose stored program computers comprising an array of processing units with common control, e.g. single instruction multiple data processors
- G06F15/8053—Vector processors
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Complex Calculations (AREA)
- Memory System (AREA)
Description
【発明の詳細な説明】
（産業上の利用分野）
本発明は、大規模な数値計算を支援するための
高性能な外部メモリ装置の方式に係る。
高性能な外部メモリ装置の方式に係る。
（従来技術とその問題点）
いわゆるスーパーコンピユータでは、大規模な
数値計算をサポートするために高速の外部メモリ
が提供されている。
数値計算をサポートするために高速の外部メモリ
が提供されている。
提供されている外部メモリのアーキテクチヤ
は、通常、デイスクデパイスと同様、ブロツクラ
ンダムアクセスを採用している。ブロツクランダ
ムアクセスとは、例えばベクトル｛vi｝は、ブロ
ツクに分けられ、v0v1…vo-1，vo，vo+1…v2o-1，
v2o…というように長さｎのブロツクとして、外
部メモリに格納される。このアーキテクチヤの採
用は、従来のプログラムの書き換えやオペレーシ
ヨンシステムの大幅な変更を避けることを目的と
している。
は、通常、デイスクデパイスと同様、ブロツクラ
ンダムアクセスを採用している。ブロツクランダ
ムアクセスとは、例えばベクトル｛vi｝は、ブロ
ツクに分けられ、v0v1…vo-1，vo，vo+1…v2o-1，
v2o…というように長さｎのブロツクとして、外
部メモリに格納される。このアーキテクチヤの採
用は、従来のプログラムの書き換えやオペレーシ
ヨンシステムの大幅な変更を避けることを目的と
している。
しかし、ブロツクランダムアーキテクチヤは、
数値計算では、不適なケースがある。例えば、２
次元アレイ｛Aij｝を考えよう。このアレイが
A00A01…A0o-1，A0o…，A10A11…というように
（ｉ，ｊ）の順でブロツクに分けられ、格納され
ているとする。いま｛Aij｜∈〔０，ｍ〕｝ｉ、す
なわち、ｉを固定し、ｊだけ０，１，２…と変え
て得られるベクトルAi0，Ai1，…Aio-1，Aio…を
入出力する場合、ブロツク単位に転送すること
で、効率の良い入力、出力を行うことができる。
しかし、一方、｛Aij｜ｉ∈〔０，ｍ〕｝ｊで表わ
されるベクトルA0j，A1j，A2j…については、そ
れぞれの要素を入出力する場合、それぞれ別のブ
ロツクを参照する必要があり、長さｍのベクトル
の入力または出力にともなつて、最悪で、ｍブロ
ツクの入力または出力を必要とする。このような
アクセスパターンは、例えば、偏微分方程式の差
分解法の１つである陰解法では、異つた軸による
スキヤンが必要なため、必然的に存在する。その
他にも多次元FFTや行列の積にも現われる。す
なわち、数値計算では、このようなアクセスパタ
ーンは、ごく普通に現われると考えてよい。した
がつて、ブロツクランダムアクセスの外部メモリ
を、効率良く使用するには、プログラムを工夫す
る努力が必要で、また、そうした努力によつても
高い性能を引き出せないことがある。
数値計算では、不適なケースがある。例えば、２
次元アレイ｛Aij｝を考えよう。このアレイが
A00A01…A0o-1，A0o…，A10A11…というように
（ｉ，ｊ）の順でブロツクに分けられ、格納され
ているとする。いま｛Aij｜∈〔０，ｍ〕｝ｉ、す
なわち、ｉを固定し、ｊだけ０，１，２…と変え
て得られるベクトルAi0，Ai1，…Aio-1，Aio…を
入出力する場合、ブロツク単位に転送すること
で、効率の良い入力、出力を行うことができる。
しかし、一方、｛Aij｜ｉ∈〔０，ｍ〕｝ｊで表わ
されるベクトルA0j，A1j，A2j…については、そ
れぞれの要素を入出力する場合、それぞれ別のブ
ロツクを参照する必要があり、長さｍのベクトル
の入力または出力にともなつて、最悪で、ｍブロ
ツクの入力または出力を必要とする。このような
アクセスパターンは、例えば、偏微分方程式の差
分解法の１つである陰解法では、異つた軸による
スキヤンが必要なため、必然的に存在する。その
他にも多次元FFTや行列の積にも現われる。す
なわち、数値計算では、このようなアクセスパタ
ーンは、ごく普通に現われると考えてよい。した
がつて、ブロツクランダムアクセスの外部メモリ
を、効率良く使用するには、プログラムを工夫す
る努力が必要で、また、そうした努力によつても
高い性能を引き出せないことがある。
もう一つの問題は、プラズマ粒子コードのよう
にランダムな現象を計算しようとするとき、デー
タの構造として、ランダムな値を扱う場合が生ず
る。一般には、リストベクトル（間接アドレス）
が必要となる。この場合、通常ベクトルプロセツ
サはうまく動作しない。このため、データ集合を
値によつてソートすることが試みられる。計算シ
ステムを使つて、ソートすることも可能だが、一
般に負担はかなり大きくなり、Ｉ／Ｏを多発し、
実行速度の向上は期待できない。このため、外部
メモリ中でソートしてしまうことが望ましい。
にランダムな現象を計算しようとするとき、デー
タの構造として、ランダムな値を扱う場合が生ず
る。一般には、リストベクトル（間接アドレス）
が必要となる。この場合、通常ベクトルプロセツ
サはうまく動作しない。このため、データ集合を
値によつてソートすることが試みられる。計算シ
ステムを使つて、ソートすることも可能だが、一
般に負担はかなり大きくなり、Ｉ／Ｏを多発し、
実行速度の向上は期待できない。このため、外部
メモリ中でソートしてしまうことが望ましい。
（発明の目的）
本発明の目的は、高性能でかつ柔軟なアクセス
が可能で、さらにランダムシミユレーシヨンのサ
ポートも可能な外部メモリ装置を提供することに
ある。
が可能で、さらにランダムシミユレーシヨンのサ
ポートも可能な外部メモリ装置を提供することに
ある。
（発明の構成）
本発明によれば、計算システムからの指令にも
とずきデータの転送を行なう外部メモリであつて
素数個のメモリモジユールと、前記計算システム
からのベクトルデータを保持する入力バツフア
と、前記計算システムへのベクトルデータを保持
する出力バツフアと、前記入力バツフアからのベ
クトルデータを置換し前記メモリモジユールへ送
る逆線形置換手段と、前記メモリモジユールから
のベクトルデータを置換し前記出力バツフアへ送
る線形置換手段と、前記出力バツフアと前記入力
バツフアの間にあつて並列ソートの一部を実行す
る並列ソート手段と、前記計算システムからの指
令を解釈し前記メモリモジユールに対し読み出し
書き込み指令やアドレスの生成や前記第１および
第２の置換指令の生成や前記並列ソート手段を制
御する制御部とから構成されることを特徴とする
メモリ装置が得られる。
とずきデータの転送を行なう外部メモリであつて
素数個のメモリモジユールと、前記計算システム
からのベクトルデータを保持する入力バツフア
と、前記計算システムへのベクトルデータを保持
する出力バツフアと、前記入力バツフアからのベ
クトルデータを置換し前記メモリモジユールへ送
る逆線形置換手段と、前記メモリモジユールから
のベクトルデータを置換し前記出力バツフアへ送
る線形置換手段と、前記出力バツフアと前記入力
バツフアの間にあつて並列ソートの一部を実行す
る並列ソート手段と、前記計算システムからの指
令を解釈し前記メモリモジユールに対し読み出し
書き込み指令やアドレスの生成や前記第１および
第２の置換指令の生成や前記並列ソート手段を制
御する制御部とから構成されることを特徴とする
メモリ装置が得られる。
（発明の原理）
つぎに、本発明の原理について説明する。ま
ず、２次元アレイ｛Aij｝を考える。このアレイ
の要素へのアクセスは、計算アルゴリズムに依存
するが、代表的なアクセスは、列方向か行方向、
あるいは対角方向が想定される。簡単のため、こ
のアレイのサイズをＡ（４，４）とする。メモリ
には次のように格納されているとする。
ず、２次元アレイ｛Aij｝を考える。このアレイ
の要素へのアクセスは、計算アルゴリズムに依存
するが、代表的なアクセスは、列方向か行方向、
あるいは対角方向が想定される。簡単のため、こ
のアレイのサイズをＡ（４，４）とする。メモリ
には次のように格納されているとする。
A00 A01 A02 A03
A10 A11 A12 A13
A20 A21 A22 A23
A30 A31 A32 A33
このアレイの列方向のデータ要素は隣り合つて
格納されている。この場合を１−順序ベクトル形
式、または簡単に順序ベクトルと呼ぶ。一方行方
向のデータ要素A00，A10，A20，A30やA01，A11，
A21，A31といつたベクトルは、４要素はなれた
要素に対するアクセスとなる。また、対向要素
A00，A11，A22，A33は、５要素はなれた要素に
対するアクセスとなる。それらを各々４−順序ベ
クトル、５−順序ペクトルに対するアクセスと呼
ぶ。
格納されている。この場合を１−順序ベクトル形
式、または簡単に順序ベクトルと呼ぶ。一方行方
向のデータ要素A00，A10，A20，A30やA01，A11，
A21，A31といつたベクトルは、４要素はなれた
要素に対するアクセスとなる。また、対向要素
A00，A11，A22，A33は、５要素はなれた要素に
対するアクセスとなる。それらを各々４−順序ベ
クトル、５−順序ペクトルに対するアクセスと呼
ぶ。
３次元データアレイについても同様、Ａ（n1，
n2，n3）について、（ここでn1，n2，n3はサイズ
を表わす）AijkのＫを０，１，２，…と変えて得
られるベクトルは順序ベクトルであり、ｊを変え
て得られるベクトルはn3−順序ベクトル、ｉを変
えて得られるベクトルは、n2・n3−順序ベクトル
である。
n2，n3）について、（ここでn1，n2，n3はサイズ
を表わす）AijkのＫを０，１，２，…と変えて得
られるベクトルは順序ベクトルであり、ｊを変え
て得られるベクトルはn3−順序ベクトル、ｉを変
えて得られるベクトルは、n2・n3−順序ベクトル
である。
一般的には、外部メモリから計算システムへの
データの転送はｎ−順序ベクトルを順序ベクトル
に置換し転送することであり、外部メモリへの書
き込みは、順序ベクトルをｎ−順序ベクトルに置
換し、転送することに対応する。もう少し具体的
に説明するため、線形置換Ldを次のように定義
する。
データの転送はｎ−順序ベクトルを順序ベクトル
に置換し転送することであり、外部メモリへの書
き込みは、順序ベクトルをｎ−順序ベクトルに置
換し、転送することに対応する。もう少し具体的
に説明するため、線形置換Ldを次のように定義
する。
Ld：ｂ＋ｄ・ｉ→ｉ （modM），
また、その逆置換L-1 dは
L-1 d：ｉ→ｂ＋ｄ・ｉ （modM），
ここで、ｂとｄは定数であり、ｄはｄ−順序ベ
クトルに対応する定数である。
クトルに対応する定数である。
ｂとｄはつぎのように与えられる。あるプログ
ラムを例として考える。以下の例で、添字i1，i2，
i3は０から始まり、各々n1−１，n2−１，n3−１
で終るものとする。
ラムを例として考える。以下の例で、添字i1，i2，
i3は０から始まり、各々n1−１，n2−１，n3−１
で終るものとする。
ここで、i1，i2，i3は定数であり、ｋはindex変
数である。アレイＡがアドレスａから格納されて
いるとすると、Ａ（i1，i2，ｋ）はａ＋n2n3i1＋
n3i2＋ｋ、すなわちｂ＝ａ＋n2−n3・i1＋n3・i2で
あり、ｄ＝１である。同様にＡ（i1，ｋ，i3）につ
いてはｂ＝ａ＋n2・n3・i1＋i3，ｄ＝n3である。
数である。アレイＡがアドレスａから格納されて
いるとすると、Ａ（i1，i2，ｋ）はａ＋n2n3i1＋
n3i2＋ｋ、すなわちｂ＝ａ＋n2−n3・i1＋n3・i2で
あり、ｄ＝１である。同様にＡ（i1，ｋ，i3）につ
いてはｂ＝ａ＋n2・n3・i1＋i3，ｄ＝n3である。
つぎに、メモリへの格納を説明する。高速の転
送を行うには、並列処理が本質的であり、メモリ
は複数のメモリモジユールに分けられる。アレイ
データはメモリモジユールに沿つてベクトルとし
て格納される。例えば、Aijは、メモリモジユー
ル０にA11，１にA12，２にA13，…というように
格納される。
送を行うには、並列処理が本質的であり、メモリ
は複数のメモリモジユールに分けられる。アレイ
データはメモリモジユールに沿つてベクトルとし
て格納される。例えば、Aijは、メモリモジユー
ル０にA11，１にA12，２にA13，…というように
格納される。
メモリモジユールがＭ個あるとすると、アドレ
スAddのモジユール番号、モジユール内アドレス
は、それぞれ、 Add mod Ｍ，〔Add／Ｍ〕 である。
スAddのモジユール番号、モジユール内アドレス
は、それぞれ、 Add mod Ｍ，〔Add／Ｍ〕 である。
また、転送すべきベクトル要素のアドレスは、
第ｉ番目のアドレスについて書けば、ｂ＋ｄ・ｉ
であり、モジユール番号、モジユール内アドレス
はそれぞれ、 （ｂ＋ｄ・ｉ）modM，〔ｂ＋ｄ−ｉ）／Ｍ〕 と表わされる。ここで〔ｘ〕はｘより小さくかつ
最大の整数を表わす。
第ｉ番目のアドレスについて書けば、ｂ＋ｄ・ｉ
であり、モジユール番号、モジユール内アドレス
はそれぞれ、 （ｂ＋ｄ・ｉ）modM，〔ｂ＋ｄ−ｉ）／Ｍ〕 と表わされる。ここで〔ｘ〕はｘより小さくかつ
最大の整数を表わす。
ここで、＝ｂ（modM），＝ｄ（modM）と
すれば第ｉ番目のモジユール番号は （＋・ｉ）modM と表わすことができる（整数論より既知）。
すれば第ｉ番目のモジユール番号は （＋・ｉ）modM と表わすことができる（整数論より既知）。
線形置換は
（＋・ｉ）→ｉ（modM）
であり、この置換は、（，Ｍ）＝１、すなわち、
ｂとＭが互いに素であるとき、競合なしに行われ
る。したがつて、Ｍは素数から選ばれることが望
ましいが、競合を解決する手段を用いれば、素数
に限定することもない。
ｂとＭが互いに素であるとき、競合なしに行われ
る。したがつて、Ｍは素数から選ばれることが望
ましいが、競合を解決する手段を用いれば、素数
に限定することもない。
線形置換はつぎのように実行される。まずに
対応し、−順序ベクトルを順序ベクトルに変換
し、つぎにに対応し、得られた順序ベクトルを
回転置換する。この置換を例で説明する。いま、
メモリモジユールが５つあるとし、アレイＡのサ
イズが８×８であるとしアドレス０から格納され
ているとする。Ａ（１，２），Ａ（２，２），Ａ（３，
２），Ａ（４，２）というベクトルはｂ＝（Ａ（１，
２）のアドレス）とし、ｄ＝８とすることで要素
のアドレスが得られる。Ａ（１，２）のアドレス
は10であり、＝10mod5＝０，＝8mod5＝３
である。各要素のアドレスはＡ（１，２），Ａ（２，
２）の順で 10，18，26，34 であり、それぞれ、メモリモジユール０，３，
１，４に入つている。
対応し、−順序ベクトルを順序ベクトルに変換
し、つぎにに対応し、得られた順序ベクトルを
回転置換する。この置換を例で説明する。いま、
メモリモジユールが５つあるとし、アレイＡのサ
イズが８×８であるとしアドレス０から格納され
ているとする。Ａ（１，２），Ａ（２，２），Ａ（３，
２），Ａ（４，２）というベクトルはｂ＝（Ａ（１，
２）のアドレス）とし、ｄ＝８とすることで要素
のアドレスが得られる。Ａ（１，２）のアドレス
は10であり、＝10mod5＝０，＝8mod5＝３
である。各要素のアドレスはＡ（１，２），Ａ（２，
２）の順で 10，18，26，34 であり、それぞれ、メモリモジユール０，３，
１，４に入つている。
各モジユールから読み出されたベクトルはＡ
（１，２），Ａ（３，２），−，Ａ（２，２），Ａ（４
，
２）の順であり、 ０，３，１，４ ０ １ ２ ３ の置換が行なわれなければならない。このため、
ｂ＝０すなわち、回転置換を０ポジシヨン行な
う。得られるベクトルは Ａ（１，２），Ａ（３，２），−，Ａ（２，２），Ａ
（４，２） である。このベクトル要素を３要素飛びに集める
と Ａ（１，２），Ａ（２，２），Ａ（３，２），Ａ（４
，
２），−， となり、順序ベクトルが得られる。この置換をス
キツプ置換という。
（１，２），Ａ（３，２），−，Ａ（２，２），Ａ（４
，
２）の順であり、 ０，３，１，４ ０ １ ２ ３ の置換が行なわれなければならない。このため、
ｂ＝０すなわち、回転置換を０ポジシヨン行な
う。得られるベクトルは Ａ（１，２），Ａ（３，２），−，Ａ（２，２），Ａ
（４，２） である。このベクトル要素を３要素飛びに集める
と Ａ（１，２），Ａ（２，２），Ａ（３，２），Ａ（４
，
２），−， となり、順序ベクトルが得られる。この置換をス
キツプ置換という。
このように、回転置換と、スキツプ置換を組み
合せることで線形置換を実現できる。
合せることで線形置換を実現できる。
一方逆置換L-1 dは、以上述べた線形置換の逆置
換であり、まず、スキツプ置換を行い、ついて回
転置換を行うことで達成される。この場合のスキ
ツプ置換、回転置換に与えれるパラメータb′，
d′は b′＝Ｍ−ｂ（modM） d′・ｄ＝１（modM） から得られる。
換であり、まず、スキツプ置換を行い、ついて回
転置換を行うことで達成される。この場合のスキ
ツプ置換、回転置換に与えれるパラメータb′，
d′は b′＝Ｍ−ｂ（modM） d′・ｄ＝１（modM） から得られる。
以上のようにして線形置換が行われる。この線
形置換を使用して、指定されたデータの集合を値
によりソートする方法をつぎに述べる。このソー
トは並列ソートであり、基本的にはBatcher′s
sortアルゴリズムをベースにしている。
形置換を使用して、指定されたデータの集合を値
によりソートする方法をつぎに述べる。このソー
トは並列ソートであり、基本的にはBatcher′s
sortアルゴリズムをベースにしている。
Batcher′s sortアルゴリズムはBitonic sortで
あり、長さｎのbitonicから長さ2nのbitonic列を
作成していく方法である。ソートの手間は要素数
をＮとするとＮ log2Nかかり、heap sortとく
らべて手間は大きいが、処理が簡単なことと、並
列処理が可能な点で有利である。
あり、長さｎのbitonicから長さ2nのbitonic列を
作成していく方法である。ソートの手間は要素数
をＮとするとＮ log2Nかかり、heap sortとく
らべて手間は大きいが、処理が簡単なことと、並
列処理が可能な点で有利である。
はじめにbitonic sortの処理手順について説明
し、つぎに線形置換によるbitonic sortのサポー
トについて説明する。
し、つぎに線形置換によるbitonic sortのサポー
トについて説明する。
長さ2nのbitonic列は次のように表わされる
a1a2…aoao+1…a2o
において
｛ｉｎ ならば ai-1＜ai
ｉ＞ｎ ならば ai-1＞ai｝
である。
このソートは（log2n＋１）段のシヤツフル交
換と比較によつて達成される。第４図は、ｎ＝４
の場合についての説明図である。図に示すように
シヤツフル交換は各段とも同じスキームであり、
シヤツフル交換により選ばれたデータのペアが互
いに比較され大小関係により、小さい方を左へ、
大きい方を右へ出力する。
換と比較によつて達成される。第４図は、ｎ＝４
の場合についての説明図である。図に示すように
シヤツフル交換は各段とも同じスキームであり、
シヤツフル交換により選ばれたデータのペアが互
いに比較され大小関係により、小さい方を左へ、
大きい方を右へ出力する。
このシヤツフル交換はそれぞれ左から順に比較
の番号C0，C1，C2，C3とすると、Ciについて
（ｉ，ｎ＋ｉ）のペアを作る。したがつて、長さ
2nのbitonic列をソートするには、まずベクトル
要素ｉをｉに、ベクトル要素（ｎ＋ｉ）をｉに送
り、そのペアについてそれぞれ比較することで行
われる。
の番号C0，C1，C2，C3とすると、Ciについて
（ｉ，ｎ＋ｉ）のペアを作る。したがつて、長さ
2nのbitonic列をソートするには、まずベクトル
要素ｉをｉに、ベクトル要素（ｎ＋ｉ）をｉに送
り、そのペアについてそれぞれ比較することで行
われる。
線形置換を行なえば以上のペアは容易に得るこ
とができる（回転置換のみで実行できる）。
とができる（回転置換のみで実行できる）。
以上に説明したように線形置換を用いることで
数値計算で現われる大規模なアレイを柔軟にアク
セスでき、また並列ソートを導入し、線形置換に
よりサポートすることでランダムシミユレーシヨ
ンを効果的に実行できるような外部メモリ装置が
可能となる。
数値計算で現われる大規模なアレイを柔軟にアク
セスでき、また並列ソートを導入し、線形置換に
よりサポートすることでランダムシミユレーシヨ
ンを効果的に実行できるような外部メモリ装置が
可能となる。
（実施例）
つぎに図面を参照して本発明を詳細に説明す
る。第１図は本発明の一実施例を示す、システム
構成図である。計算システム１（図示せず）は、
外部メモリ装置２に、転送線１８を介して指令
を、転送バス１３1〜１３n，７１1〜７１nを介し
てベクトルデータの入出力を行う。計算システム
１は次の形式のコマンド（指令）を制御プロセツ
サ８に送る。
る。第１図は本発明の一実施例を示す、システム
構成図である。計算システム１（図示せず）は、
外部メモリ装置２に、転送線１８を介して指令
を、転送バス１３1〜１３n，７１1〜７１nを介し
てベクトルデータの入出力を行う。計算システム
１は次の形式のコマンド（指令）を制御プロセツ
サ８に送る。
command（ｂ，ｄ，ｎ）
ここでcommandはreadかwriteであり、ｂは
ベクトルのベースアドレス、ｄはスキツプ距離、
ｎは転送すべきベクトル長である。
ベクトルのベースアドレス、ｄはスキツプ距離、
ｎは転送すべきベクトル長である。
まず、ベクトルデータの書き込みについて説明
する。転送線１８を介してwrite（ｂ，ｄ，ｎ）の
コマンドが制御プロセツサ８に送られる。制御プ
ロセツサ８は（ｂ，ｄ）にもとづいて、前述の
b′，d′を計算する。（この計算は原理の説明で説
明した）。計算されたb′，d′は転送線８４を介し
て、逆線形置換手段４に送られ、入力バツフア３
とメモリモジユール５1〜５nの間のデータの転送
パスが確立される。また、制御プロセツサ８は
〔（ｂ＋ｄ・ｉ）／Ｍ〕の計算を行い、各モジユー
ル内アドレスを計算し、計算されたアドレスは転
送線８３と介して、入力バツフア３に送られ、転
送線３４1〜３４o、逆線形置換手段４、転送線４
５1〜４５nをへてメモリモジユール５1〜５nに送
られる。制御プロセツサ８はメモリモジユール５
１〜５nにwrite指定を転送線８５を介して送る。
これでアドレスの設定がされる。つぎに計算シス
テム１から送られてきたベクトルデータを入力バ
ツフアに取り込み、転送線３４1〜３４n、逆線形
置換手段４、転送線４５1〜４５nを介してメモリ
モジユール５1〜５nに送られ書き込まれる。ベク
トル長ｎは、書き込みべきベクトルの範囲を示す
もので、入力バツフア３において、この情報によ
り、マスクビツトが生成され、不正な書き込みを
防止する（図示していない）。
する。転送線１８を介してwrite（ｂ，ｄ，ｎ）の
コマンドが制御プロセツサ８に送られる。制御プ
ロセツサ８は（ｂ，ｄ）にもとづいて、前述の
b′，d′を計算する。（この計算は原理の説明で説
明した）。計算されたb′，d′は転送線８４を介し
て、逆線形置換手段４に送られ、入力バツフア３
とメモリモジユール５1〜５nの間のデータの転送
パスが確立される。また、制御プロセツサ８は
〔（ｂ＋ｄ・ｉ）／Ｍ〕の計算を行い、各モジユー
ル内アドレスを計算し、計算されたアドレスは転
送線８３と介して、入力バツフア３に送られ、転
送線３４1〜３４o、逆線形置換手段４、転送線４
５1〜４５nをへてメモリモジユール５1〜５nに送
られる。制御プロセツサ８はメモリモジユール５
１〜５nにwrite指定を転送線８５を介して送る。
これでアドレスの設定がされる。つぎに計算シス
テム１から送られてきたベクトルデータを入力バ
ツフアに取り込み、転送線３４1〜３４n、逆線形
置換手段４、転送線４５1〜４５nを介してメモリ
モジユール５1〜５nに送られ書き込まれる。ベク
トル長ｎは、書き込みべきベクトルの範囲を示す
もので、入力バツフア３において、この情報によ
り、マスクビツトが生成され、不正な書き込みを
防止する（図示していない）。
つぎに読み出しについて説明する。計算システ
ム１からはread（ｂ，ｄ，ｎ）のコマンドが送ら
れてくる。制御プロセツサ８は書き込みと同様に
して、各メモリモジユール５1〜５nにアドレスを
生成し送る。そして転送線８５を介して各メモリ
モジユール５1〜５nに読み出し指令を送り、ベク
トルデータとして、読み出されたデータと転送線
５６1〜５６nを介して線形置換手段６に送る。こ
の前に制御プロセツサ８は転送線８６を介し、第
１の置換手段６に（ｂ，ｄ）から（，）を生
成し、転送バスを確立している。第１の置換手段
６によりデータベクトルの置換が行われ、転送線
６７1〜６７nを介して出力バツフア７にデータは
送られる。ベクトル長ｎは、有効なベクトルの範
囲を示すために用いられる（図示せず）。出力バ
ツフア７の内容は転送バス７１を介し、計算シス
テムに送られる。
ム１からはread（ｂ，ｄ，ｎ）のコマンドが送ら
れてくる。制御プロセツサ８は書き込みと同様に
して、各メモリモジユール５1〜５nにアドレスを
生成し送る。そして転送線８５を介して各メモリ
モジユール５1〜５nに読み出し指令を送り、ベク
トルデータとして、読み出されたデータと転送線
５６1〜５６nを介して線形置換手段６に送る。こ
の前に制御プロセツサ８は転送線８６を介し、第
１の置換手段６に（ｂ，ｄ）から（，）を生
成し、転送バスを確立している。第１の置換手段
６によりデータベクトルの置換が行われ、転送線
６７1〜６７nを介して出力バツフア７にデータは
送られる。ベクトル長ｎは、有効なベクトルの範
囲を示すために用いられる（図示せず）。出力バ
ツフア７の内容は転送バス７１を介し、計算シス
テムに送られる。
以上のように計算システムと外部メモリの間で
データの交換が行われる。
データの交換が行われる。
つぎに、第２図に線形置換手段の構成例をブロ
ツク図で示す。回転置換手段６1は転送線８６を
介して送られてくる（，）のうち、に対応
して、ｂポジシヨン回転置換を実行するものでシ
フトレジスタにより実現される。出力は、転送線
６11〜６1nを介してスキツプ置換手段６2に送ら
れる。スキツプ置換手段６2は（，）のうち、
ｄに対応して、−飛びのスキツプ置換を行う。
このスキツプ置換は、Swanson，R.C.
（“Interconnections for Parallel Memories to
Unscramble ｐ−ordered Vectors，”IEEE，
Trans on Comput.，Vol.C−23，NO.11，
pp1105〜1115（1974））に述べられているｋ−
apart interconnection（ｋ−飛び相互結合）によ
り容易に実現できる。
ツク図で示す。回転置換手段６1は転送線８６を
介して送られてくる（，）のうち、に対応
して、ｂポジシヨン回転置換を実行するものでシ
フトレジスタにより実現される。出力は、転送線
６11〜６1nを介してスキツプ置換手段６2に送ら
れる。スキツプ置換手段６2は（，）のうち、
ｄに対応して、−飛びのスキツプ置換を行う。
このスキツプ置換は、Swanson，R.C.
（“Interconnections for Parallel Memories to
Unscramble ｐ−ordered Vectors，”IEEE，
Trans on Comput.，Vol.C−23，NO.11，
pp1105〜1115（1974））に述べられているｋ−
apart interconnection（ｋ−飛び相互結合）によ
り容易に実現できる。
一方、ソートの指令は、計算システム１から次
の形式で行われる。
の形式で行われる。
sort（ａ，ｎ）
ａはソートすべきデータベクトルのスタートア
ドレス、ｎは要素数である。いまデータベクトル
が長さｎのbitonic列であるとする。制御プロセ
ツサ８は、並列ソート９1〜９nへのパス７９1〜
７９nを開き、ソートの準備を行う。
ドレス、ｎは要素数である。いまデータベクトル
が長さｎのbitonic列であるとする。制御プロセ
ツサ８は、並列ソート９1〜９nへのパス７９1〜
７９nを開き、ソートの準備を行う。
bitonic sortでは発明の原理の項で説明したよ
うにペア（ｉ，ｎ＋ｉ）を比較器９1〜９nに送る
必要があり、このためまず要素ｉを比較器９1〜
９nに送る。線形置換６には（，）が送られ
るが、ここで＝ｉ＋ａ（modM），＝１であ
る。メモリモジユールから読み出された長さｍの
データベクトルは読み出し時と同様に出力バツフ
ア７に送られ、転送線７９1〜７９nを介して比較
器９1〜９nに送られる。つぎに制御プロセツサ８
は、線形置換手段６に対して＝ａ＋ｉ＋ｎ
（modM），＝１をセツトし、ペアのもう一方の
データを同様にして、比較器９1〜９nに送る。比
較器９1〜９nはこの２つのデータの大小を比較
し、転送線８９を介して供給され制御プロセツサ
８からの指令にもとづき、データの交換を行な
い、その結果を転送線９３1〜９３nにおく。そし
て書き込み時と同様にして、入力バツフア３から
逆線形置換手段４を介し、メモリモジユール５1
〜５nに書き込まれる。このときのアドレスは第
４図に示したbitonic sortのスキームから得られ
る。
うにペア（ｉ，ｎ＋ｉ）を比較器９1〜９nに送る
必要があり、このためまず要素ｉを比較器９1〜
９nに送る。線形置換６には（，）が送られ
るが、ここで＝ｉ＋ａ（modM），＝１であ
る。メモリモジユールから読み出された長さｍの
データベクトルは読み出し時と同様に出力バツフ
ア７に送られ、転送線７９1〜７９nを介して比較
器９1〜９nに送られる。つぎに制御プロセツサ８
は、線形置換手段６に対して＝ａ＋ｉ＋ｎ
（modM），＝１をセツトし、ペアのもう一方の
データを同様にして、比較器９1〜９nに送る。比
較器９1〜９nはこの２つのデータの大小を比較
し、転送線８９を介して供給され制御プロセツサ
８からの指令にもとづき、データの交換を行な
い、その結果を転送線９３1〜９３nにおく。そし
て書き込み時と同様にして、入力バツフア３から
逆線形置換手段４を介し、メモリモジユール５1
〜５nに書き込まれる。このときのアドレスは第
４図に示したbitonic sortのスキームから得られ
る。
第３図に比較器９1〜９nのうちの１つのブロツ
ク図を示す。転送線７９i（ｉ＝１，２，…，ｍ）
を介して送られてくる第１のデータは、ゲート９
１１によつて、転送線９１７に送られレジスタ９
１２に送られる。第２のデータは、ゲート９１１
により転送線９１８を介し、レジスタ９１３に送
られる。大小比較器９１４はレジスタ９１２と９
１３の内容と比べ、制御プロセツサからの転送線
８９の内容にしたがい、結果を転送線９２１を介
して交換器９１５に送る。交換器９１５は通常の
セレクタで構成されるデータの交換器であり、転
送線９１８，９２０のデータを転送線９２１の内
容にしたがい交換するかあるいはそのままの順
で、出力線９２２と９２３に送る。ゲート９１６
はまず転送線９２２の内容を転送線９３iに送り、
つで転送線９２３の内容を転送線９３iに送り出
す。
ク図を示す。転送線７９i（ｉ＝１，２，…，ｍ）
を介して送られてくる第１のデータは、ゲート９
１１によつて、転送線９１７に送られレジスタ９
１２に送られる。第２のデータは、ゲート９１１
により転送線９１８を介し、レジスタ９１３に送
られる。大小比較器９１４はレジスタ９１２と９
１３の内容と比べ、制御プロセツサからの転送線
８９の内容にしたがい、結果を転送線９２１を介
して交換器９１５に送る。交換器９１５は通常の
セレクタで構成されるデータの交換器であり、転
送線９１８，９２０のデータを転送線９２１の内
容にしたがい交換するかあるいはそのままの順
で、出力線９２２と９２３に送る。ゲート９１６
はまず転送線９２２の内容を転送線９３iに送り、
つで転送線９２３の内容を転送線９３iに送り出
す。
（発明の効果）
以上説明したように本発明によれば、通常数値
計算で現われる大規模な行列やアレイを高速にか
つ柔軟に計算システムとの間でデータ交換できる
とともにランダムシミユレーシヨンのサポートを
並列ソートで支援することのできる外部メモリ装
置が提供できる。
計算で現われる大規模な行列やアレイを高速にか
つ柔軟に計算システムとの間でデータ交換できる
とともにランダムシミユレーシヨンのサポートを
並列ソートで支援することのできる外部メモリ装
置が提供できる。
第１図は本発明の一実施例を示す外部メモリ装
置のブロツク図、第２図は線形置換手段のブロツ
ク図、第３図は並列ソートの一つのコンポーネン
トのブロツク図、第４図はバイトニツクソートの
説明図である。 図において、２……外部メモリ装置、３……入
力バツフア、４……逆線形置換手段、５1〜５n…
…メモリモジユール、６……線形置換手段、７…
…出力バツフア、８……制御プロセツサ、９1〜
９n……比較器をそれぞれ示す。
置のブロツク図、第２図は線形置換手段のブロツ
ク図、第３図は並列ソートの一つのコンポーネン
トのブロツク図、第４図はバイトニツクソートの
説明図である。 図において、２……外部メモリ装置、３……入
力バツフア、４……逆線形置換手段、５1〜５n…
…メモリモジユール、６……線形置換手段、７…
…出力バツフア、８……制御プロセツサ、９1〜
９n……比較器をそれぞれ示す。
Claims (1)
- １ 素数個のメモリモジユールと、計算システム
からのベクトルデータを保持する入力バツフア
と、前記計算システムへのベクトルデータを保持
する出力バツフアと、前記入力バツフアからのベ
クトルデータを置換し前記メモリモジユールへ送
る逆線形置換手段と、前記メモリモジユールから
のベクトルデータを置換し前記出力バツフアへ送
る線形置換手段と、前記出力バツフアと前記入力
バツフアの間にあつて並列ソートの一部を実行す
る並列ソート手段と、前記計算システムからの指
令を解釈し前記メモリモジユールに対し読み出し
書き込み指令やアドレスの生成や前記第１および
第２の置換指令の生成や前記並列ソート手段を制
御する制御部とから構成されることを特徴とする
メモリ装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP15715984A JPS6136866A (ja) | 1984-07-30 | 1984-07-30 | メモリ装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP15715984A JPS6136866A (ja) | 1984-07-30 | 1984-07-30 | メモリ装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6136866A JPS6136866A (ja) | 1986-02-21 |
| JPH037977B2 true JPH037977B2 (ja) | 1991-02-04 |
Family
ID=15643470
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP15715984A Granted JPS6136866A (ja) | 1984-07-30 | 1984-07-30 | メモリ装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6136866A (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2515884B2 (ja) * | 1989-06-06 | 1996-07-10 | 東レ株式会社 | プロピレン系重合体フィルム |
| JP7163070B2 (ja) * | 2017-05-30 | 2022-10-31 | 大阪ガスケミカル株式会社 | 化粧料添加剤、及びこれを含む化粧料 |
-
1984
- 1984-07-30 JP JP15715984A patent/JPS6136866A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS6136866A (ja) | 1986-02-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR0125623B1 (ko) | 데이타 프로세서 및 데이타 처리방법 | |
| US5410727A (en) | Input/output system for a massively parallel, single instruction, multiple data (SIMD) computer providing for the simultaneous transfer of data between a host computer input/output system and all SIMD memory devices | |
| US5956274A (en) | Memory device with multiple processors having parallel access to the same memory area | |
| Siegel et al. | A survey of interconnection methods for reconfigurable parallel processing systems | |
| EP0248906A1 (en) | Multi-port memory system | |
| US5586256A (en) | Computer system using multidimensional addressing between multiple processors having independently addressable internal memory for efficient reordering and redistribution of data arrays between the processors | |
| US5247613A (en) | Massively parallel processor including transpose arrangement for serially transmitting bits of data words stored in parallel | |
| US5367692A (en) | Parallel computer system including efficient arrangement for performing communications among processing node to effect an array transposition operation | |
| JP2002518730A (ja) | 単一命令複数データシステムに使用するレジスタにアクセスするレジスタおよびアクセス方法 | |
| JPS62264357A (ja) | 並列プロセツサ・アレイにおけるプロセツサ付加のシミユレ−シヨン方法 | |
| JPS62208158A (ja) | マルチプロセツサシステム | |
| JPH05508044A (ja) | 多重プロセッサシステム用通信交換システム | |
| US5394553A (en) | High performance array processor with nonlinear skewing of elements | |
| JPH07120312B2 (ja) | バッファメモリ制御装置 | |
| WO2002019129A2 (en) | Method and apparatus for connecting a massively parallel processor array to a memory array in a bit serial manner | |
| US5603046A (en) | Method for complex data movement in a multi-processor data processing system | |
| JPH037977B2 (ja) | ||
| JPH04295953A (ja) | 要素プロセッサの２次元アレイを内蔵する並列データ処理装置および要素プロセッサのサブアレイユニット | |
| EP0373299A2 (en) | Method and apparatus for memory routing scheme | |
| JP2503702B2 (ja) | アドレス変換装置 | |
| JPH037976B2 (ja) | ||
| CN119301679A (zh) | 存储器架构 | |
| JP2839597B2 (ja) | 荷電ビーム描画用データの作成装置 | |
| JP3209630B2 (ja) | データ転送装置及びマルチプロセッサシステム | |
| JP2025502112A (ja) | データ処理 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |