JPH04321158A - 配列データの分配／収集処理装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は，並列計算機で配列デー
タを複数のプロセッサに分割割付けする装置に係り，特
に任意の転送パターンによりデータを自動分配または自
動収集する配列データの分配／収集処理装置に関する。

【０００２】巨大な配列データを処理するにあたって，
複数のプロセッサにデータを分割して割り付け，並列に
処理するシステムが用いられている。このようなデータ
の分割のしかたを任意に動的に切り替えて処理できるよ
うにするために，効率よくデータを再配置する技術が必
要とされる。

【０００３】

【従来の技術】並列計算機では，配列データを効率よく
扱うために，次元に沿った超直方体領域にブロック化し
，各ブロックのメモリ割付けを分離し，それぞれをプロ
セッサごとに担当して管理することが多い。

【０００４】図１３はそのような配列データの分割例を
示している。図１３に示す例では，３次元配列Ａ（１０
０，１００，１００）を分割している。（イ）は１次元
分割，（ロ）は多次元分割，（ハ）は多次元の不均等分
割の例を示しているが，（イ）に示すような板状分割は
，ｋ方向に４分割すると同時に，ｉ方向とｊ方向に対し
て１分割していると解釈することもできる。

【０００５】一般には，ｎ次元配列Ａ（Ｍ１，Ｍ２，…
，　Ｍｎ）を，各次元に対してそれぞれ，ｐ１，ｐ２，
…，ｐｎ　部分（それぞれ１以上の整数）に切るなら，
（ｐ１　×…×ｐｎ）個の超直方体ブロックに分割する
ことができる。分散メモリ型の並列計算機であれば，各
プロセッサの処理手続きに都合のよいように，データを
分割配置することにより，計算中のデータ転送量を減ら
して効率の向上を図ることができる。共用メモリ型の並
列計算機の場合にも，同様の分割を行えば，メモリの競
合を減らして効率よく処理を進めることができる。

【０００６】また，ブロックごとに物理アドレスを分割
することにより，各プロセッサの担当データを物理的に
連続なアドレスに集めることができるため，ページ切り
替えやキャッシュメモリのミスヒットが少なくなるとか
，１プロセッサのアドレス空間に入り切らないような巨
大な配列データにもアドレス付けできるなどの効果があ
る。

【０００７】このように，配列の分割割付けは重要であ
るが，実際のアプリケーションプログラムでは，データ
の分割のしかたが固定的であることは稀であり，実行処
理中にデータ転送処理を伴う再分割割付けが頻繁に必要
となる。それは例えば次のような場合である。

【０００８】（ａ）　データ相関方向の変化特に，ＡＤ
Ｅ（交互方向編集）がよく知られている。これは，ある
次元での板状分割から，別の次元での板状分割へと変更
する編集である。ＬＵ分解などの行列計算や多次元ＦＥ
Ｔなどで必要となるため，連続系の数値計算では多用さ
れる。プロセッサ数が多くなれば，多次元分割にせざる
を得なくなり，より複雑な転送パターンとなることは必
至である。例えば，配列Ａ（１００，１００，１００）
を，２００プロセッサに割り付けるには，２次元以上で
分割するしかなく，その場合のＡＤＥ転送はかなり複雑
になる。

【０００９】（ｂ）　細分化などの再分割割付け一般に
並列度が上がるほど，データ転送や同期などのオーバヘ
ッドが増えるため，手続きによって使用プロセッサ数の
最適値がある。それに伴って，並列効果の異なる手続き
の境界で，データ分割割付けの変更が必要になる場合が
ある。

【００１０】（ｃ）　計算機の運用上の理由一部のプロ
セッサの故障，同時利用者数の変化などで，分割の変更
を伴うプロセッサ間データ移動が必要になることがある
。

【００１１】従来，ユーザがＦＯＲＴＲＡＮやＣ言語な
どの計算機用記述言語を使って記述する場合，配列の添
字の計算には大変な手間がかかる上に，煩雑であるため
ミスが生じやすく，検証も難しかった。また，データ転
送のタイミングはユーザには予想しきれないことが多く
，効率化は困難であるという問題があった。

【００１２】分割の形状や分割数などを制約すれば，比
較的簡単に実現できる可能性があり，特定の転送パター
ンの効率化を狙ったハードウェアを持つ計算機も考えら
れているが，アプリケーションの幅や運用形態で大きな
制約を受けることになる。特に，汎用性の高い計算機を
提供するためには，ユーザがどのような分割形状や転送
パターンを必要としても，それに対応できなければなら
ない。しかし，従来，任意の分割形状や転送パターンに
柔軟に対応できるような手段はなかった。

【００１３】

【発明が解決しようとする課題】本発明は上記問題点の
解決を図り，配列データの任意の分割割付けを，手軽に
効率よく実現する手段を提供することを目的とする。す
なわち，ユーザはデータ転送の詳細な内容を明示的に意
識する必要がなく，分割形状と配列の範囲を指定するだ
けで，配列の分割割付けや分割の変更が可能になるよう
にすることを目的とする。

【００１４】また，本発明は，配列の次数や大きさ，分
割次元数や分割幅が均等か否かなどによる制約がなく，
広い範囲に適用できるデータの分配手段および収集手段
を提供することを目的とする。

【００１５】

【課題を解決するための手段】図１は本発明の原理構成
図である。図１において，１０ａ，１０ｂ，…，１０ｃ
は各々独立したデータ処理機能を有するプロセッサ，１
１は転送テーブル作成手段，１２はデータを分配または
収集するデータ転送手段，１３は分割または収集するブ
ロックの分割区間番号を指定する分割区間番号指定手段
，１４は各ブロックの分割区間上下限を指定する分割区
間上下限指定手段，１５は各プロセッサからアクセス可
能となっている共用メモリ，１６はデータの分配または
収集に用いる転送テーブル，１７は分配するデータが格
納されている分配データ格納域，１８は各プロセッサが
処理するデータを格納する転送先データ格納域，１９は
収集したデータを格納する収集データ格納域，２０は収
集対象となるデータが格納されている転送元データ格納
域を表す。

【００１６】請求項１記載の発明は，例えば（イ）に示
すような構成になっている。ある分割法で１ブロック内
に割り付けられている任意の部分配列を，別の分割法に
従って分割割付けする。そのため，プロセッサ１０ａは
，分割区間番号指定手段１３から分割対象となるブロッ
クの分割区間番号を得て，その各分割区間番号に対応す
る分割ブロックの上下限の範囲を，分割区間上下限指定
手段１４から得る。分割区間番号指定手段１３および分
割区間上下限指定手段１４は，入出力装置，外部記憶装
置またはプログラムなどのいずれの手段でもよい。

【００１７】転送テーブル作成手段１１は，分割区間番
号指定手段１３および分割区間上下限指定手段１４から
得た情報に基づいて，共用メモリ１５における各転送先
データ格納域１８への割り付け対象となる１以上の任意
の次元方向で分割した分割ブロックに対応して，各次元
ごとの範囲に関する情報を持つ転送テーブル１６を作成
する。

【００１８】データ転送手段１２は，作成した転送テー
ブル１６に基づいて，各分割ブロックごとにデータを各
記憶空間に転送する。すなわち，転送テーブル１６に基
づいて分配データ格納域１７のデータを各プロセッサに
対応して指定された転送先データ格納域１８へ分配する
。

【００１９】図１の（イ）に示す例は，共用メモリ１５
上でデータの分配を行っているが，分散メモリ型の計算
機では，各プロセッサが持つローカルメモリに対してそ
れぞれデータを転送する。請求項２記載の発明は，例え
ば（ロ）に示すような構成になっている。

【００２０】ある分割法で分散して割り付けられている
配列からデータを収集し，別の分割法に基づく１ブロッ
ク内に属する任意の部分配列を収集する。そのため，プ
ロセッサ１０ａは，分割区間番号指定手段１３から収集
対象となるブロックの分割区間番号を得て，その各分割
区間番号に対応する分割ブロックの上下限の範囲を，分
割区間上下限指定手段１４から得る。

【００２１】転送テーブル作成手段１１は，分割区間番
号指定手段１３および分割区間上下限指定手段１４から
得た情報に基づいて，共用メモリ１５における転送元デ
ータ格納域２０へ分散して配置されている１以上の任意
の次元方向で分割した分割ブロックに対応して，収集す
べきデータの各次元ごとの範囲に関する情報を持つ転送
テーブル１６を作成する。

【００２２】データ転送手段１２は，作成した転送テー
ブル１６に基づいて，各分割ブロックごとの収集データ
を，各転送元データ格納域２０から収集データ格納域１
９へ転送する。図１の（ロ）に示す例は，共用メモリ１
５上でデータの収集を行っているが，分散メモリ型の計
算機では，各プロセッサが持つローカルメモリから，そ
れぞれ収集するプロセッサのローカルメモリへデータを
転送する。

【００２３】

【作用】請求項１記載の発明では，例えばｎ次元配列Ａ
（Ｍ１，Ｍ２，…，　Ｍｎ）　　（ｎ≧１，Ｍｄ　は次
元ｄの寸法）の超直方体の部分配列 Ａ（ｉ１：ｊ１，　ｉ２：ｊ２，　…，　ｉｎ：ｊｎ　
）（ｉｄ，　ｊｄはそれぞれ次元ｄのインデックスの下
限，上限。０≦ｉｄ≦ｊｄ≦Ｍｄ−１）が１分割ブロッ
ク内にあるとき，これを別の分割法に従って分割割付け
する。

【００２４】請求項２記載の発明では，逆に分割割付け
されている部分配列を別の分割法に従って１分割ブロッ
クに収集する。部分配列は，配列全体であってもよい。 説明の簡単化のため，各次元の配列のインデックスおよ
び分割区間番号は，０から数えるものとする。他の場合
（例えば１から数える場合）には，シフトさせて本発明
を適用すればよい。また，分割ブロックごとに，配列要
素Ａ（ｋ１，…　，ｋｎ）のメモリ割付けは，次式で示
されるアドレスに置くこととする。

【００２５】 　　（ベースアドレス）＋（ワード長）×　　　　　　
　　　　　　　　　　（ｋ１＋ｍ１×（ｋ２＋ｍ２×（
　…ｍ（ｎ−１）×ｋｎ…）））　　　　　　　（式１
）分散メモリ型計算機では，分散ブロックとプロセッサ
の対応をテーブル等で管理する。

【００２６】この係数ｍｄ（ｄ＝１，２，…，ｎ−１）
　を，その分割ブロックの次元ｄの分割係数と呼ぶ。分
割係数は，その次元方向の分割幅（インデックス数）以
上の定数である。分割幅と等しい場合，ブロック内の配
列要素は連続アドレスに割り付けられる。

【００２７】［１］共用メモリ型計算機の場合，ある分
割法Ａで１ブロック内に割り付けられている任意の部分
配列を，他の分割法Ｂに従って分割割付けするときの分
配の手順は以下のようになる。 ■　　プロセッサ１０ａは，分割区間番号指定手段１３
により，すべての次元ｄ＝１，…，ｎについて，分割法
Ｂでｉｄ　に対応する分割区間番号ｐｄ　と，ｊｄ　に
対応する分割区間番号ｑｄ　を得る。これによって，分
割法Ｂの分割ブロックの範囲は，（ｐ１：ｑ１，…，　
ｐｎ：ｑｎ）であることがわかる。

【００２８】■　　転送テーブル１６の領域を，分割法
Ｂの分割ブロックに対応して，（ｑ１−ｐ１　＋１）×
…×　（ｑｎ　−ｐｎ　＋１）個確保する。 ■　　プロセッサ１０ａは，分割ブロック（ｒ１，…ｒ
ｎ）　（ｒｄ　＝ｐｄ，…ｑｄ；ｄ＝１，…，ｎ）に対
応して，すべての転送テーブル１６を，次のように完成
させる。

【００２９】 次元ｄの下限値は，ｒｄ　＝ｐｄ　のとき，ｉｄ　。 ｒｄ　≧ｐｄ　のとき，分割区間ｒｄ　の下限。 次元ｄの上限値は，ｒｄ　＝ｑｄ　のとき，ｊｄ　。 ｒｄ　≧ｑｄ　のとき，分割区間ｒｄ　の上限。

【００３０】■　　プロセッサ１０ａは，すべての転送
テーブル１６に従って，分配データ格納域１７から指定
される配列要素を読み出し，転送先データ格納域１８へ
書き込む。分割法Ａ，分割法Ｂとも，アドレス計算は上
記（式１）による。転送テーブル１６は，配列全体に対
応する数だけ，あらかじめ確保しておいてもよい。その
場合には，手順■は不要となる。

【００３１】［２］同じ処理を分散メモリ型計算機で実
現する場合，分割ブロックに対応するプロセッサ１０ｂ
，…１０ｃへのデータ送信となる。最初の手順■〜■は
共用メモリ型と同様である。■では以下の処理を行う。 ■　　データ転送手段１２により，転送テーブル１６ご
とにデータ転送を実行する。１ワード長ずつしか転送で
きない機構であれば，全次元について反復実行しながら
１配列要素ずつ転送する。連続アドレスが一度に転送で
きる機構であれば，第２次元以降について反復実行しな
がら第１次元の連続配列要素を一度に転送することが可
能である。インターバル付きアドレス指定が可能な機構
であれば，第３次元以降について反復実行しながら第１
，２次元の長方形領域の配列要素を一度に転送すること
が可能である。複数次元のインターバルが可能ならば，
さらに多くの配列要素を一度に転送できる。

【００３２】［３］共用メモリ型計算機において，分割
法Ｂによる１ブロック内に属する任意の部分配列を，分
割法Ａで割り付けられている配列から収集し，分割法Ｂ
で割り付ける収集の手順は以下のようになる。 ■　　プロセッサ１０ａは，分割区間番号指定手段１３
により，すべての次元ｄ＝１，…，ｎについて，分割法
Ａでｉｄ　に対応する分割区間番号ｐｄ　と，ｊｄ　に
対応する分割区間番号ｑｄ　を得る。これによって，分
割法Ａの分割ブロックの範囲は，（ｐ１：ｑ１，…，　
ｐｎ：ｑｎ）であることがわかる。

【００３３】■　　転送テーブル１６の領域を，分割法
Ａの分割ブロックに対応して，（ｑ１−ｐ１　＋１）×
…×　（ｑｎ　−ｐｎ　＋１）個確保する。 ■　　［１］の分配の場合と同様に，分割ブロックに対
応するすべての転送テーブル１６を完成させる。

【００３４】■　　プロセッサ１０ａは，すべての転送
テーブル１６に従って，転送元データ格納域２０から指
定される配列要素を読み出し，収集データ格納域１９へ
書き込む。分割法Ａ，分割法Ｂとも，アドレス計算は上
記（式１）による。 ［４］分散メモリ型計算機において収集を行う場合には
，分割ブロックを担当する各プロセッサ１０ｂ，…１０
ｃからのデータ受信となる。

【００３５】

【実施例】図２は，分散メモリ型並列計算機に適用した
本発明の構成例を示している。図１に示す例では，各プ
ロセッサ１０ａ〜１０ｃがそれぞれ処理するデータを共
用メモリ１５に分割して格納しているのに対し，図２に
示す例では，各プロセッサ１０ａ〜１０ｃ対応に設けら
れている分散メモリ３０のデータ格納域３１に，データ
を分散させて格納する。この場合，データ転送手段１２
は，各プロセッサの分散メモリ３０間でデータを送受信
するバスまたは転送装置等で構成される。他の構成につ
いては，図１に示すものとほぼ同様である。

【００３６】図３は，本発明の実施例で用いる転送テー
ブルの構成例を示す。転送テーブル１６は，最大の場合
，分割ブロック数まで必要であり，それぞれ図３に示す
ように，配列の各次元ごとにインデックスの下限を示す
整数値と，上限を示す整数値とを持つことにより，分割
割付けの範囲を示す。

【００３７】ＡＤＥ転送に関する実施例として，１０台
のプロセッサを持つ分散メモリ型並列計算機で，２次元
配列Ａ（３０，５０）およびＢ（３０，５０）が使われ
，図４に示すように分割配置されている具体的な例につ
いて説明する。配列Ａから配列Ｂへ全要素を代入する。

【００３８】各プロセッサは担当するＡの部分配列全域
を，Ｂへ分配する。例えばプロセッサＰ０は，Ａ（０：
２９，　０：４）を，次の手順でＢの対応する要素へ送
信する。 ■　　配列Ａ，Ｂについて，インデックスと分割区間番
号の対に関する情報を，例えば図５に示す分割情報テー
ブルを使って保持する。または計算式の形で保持する。 これをプロセッサで参照または計算することにより，分
割区間の範囲を認識する。図１に示す分割区間番号指定
手段１３および分割区間上下限指定手段１４は，このよ
うな分割情報テーブル等を得る手段である。

【００３９】■　　次元１の区間０：２９，次元２の区
間０：４から，転送先となる配列Ｂの部分は，分割ブロ
ック（０，０）から（９，０）までの１０ブロックにま
たがっていることがわかる。 ■　　分割ブロックに対応して，転送テーブル１６を１
０個用意する。

【００４０】■　　転送テーブル１６を，図６に示す転
送テーブル１６−０，…，１６−９のように完成させる
。 ■　　転送装置に対し，必要なパラメータを与えて起動
する。例えば自プロセッサのインターバル付きアドレス
区間から，他プロセッサのインターバル付きアドレス区
間へ送受信するハードウェアを用いるなら，ｂｌｏｃｋ
（１，０）に関しては，次のようなパラメータをセット
し起動する。

【００４１】 （ａ）　転送データ数　　　　Ｎ　　　　（５−３＋１
）×（４−０＋１）＝１５（ｂ）　転送先プロセッサＰ
　　　　プロセッサＰ１（ｃ）　転送元 先頭アドレスｂ１　　　　Ａ（３，０）のアドレス連続
データ数ｗ１　　　　５−３＋１＝３　　　　　　イン
ターバルｉ１　　　　３０（ｄ）　転送先 先頭アドレスｂ２　　　　Ｂ（３，０）のアドレス連続
データ数ｗ２　　　　５−３＋１＝３インターバルｉ２
　　　　３ 転送データ数Ｎは，図６に示す転送テーブル１６−１か
ら計算できる。転送元の先頭アドレスｂ１は，転送テー
ブル１６−１の下限値から決める。連続データ数ｗ１と
インターバルｉ１は，それぞれ転送テーブル１６−１の
次元１方向の連続長と，図５に示すテーブルの次元１方
向の分割幅から決める。転送先についても同様である。

【００４２】パラメータを受け取った転送装置は，例え
ば図１０に従って後述する手順により，転送元アドレス
を得ながらＮ個のデータをメモリから読み，パラメータ
Ｎ，ｂ２，ｗ２，ｉ２とともにプロセッサＰ１等の受信
装置へ送信する。プロセッサＰ１等の受信装置は，同様
に図１０に示す手順で転送先アドレスを得ながらＮ個の
データを順次書き込む。

【００４３】この結果，図７の配列Ａのように各プロセ
ッサＰ０〜Ｐ９に分割割付けされていたデータは，配列
Ｂのように再配置されることになる。以上の例では，分
配によって配列Ａのデータを配列Ｂのように再配置して
いるが，分散配置されているデータを収集することによ
って，同様に再配置することも可能である。この場合，
各プロセッサＰ０〜Ｐ９は，担当する配列Ｂの部分配列
全体を，配列Ａから収集する。例えばプロセッサＰ０は
，部分配列Ｂ（０：２，０：４９）を，配列Ａの対応す
る要素から受信する。その手順は以下のとおりである。

【００４４】■　　上記分配のときの■と同様である。 ■　　転送元となる配列Ａの部分は，分割ブロック（０
，０）から（０，９）までまたがっている。 ■　　分割ブロックに対応して転送テーブル１６を１０
個用意する。

【００４５】■　　転送テーブルを，図８および図９に
示す手順により埋める。 ■　　上記分配の場合と同様であるが，各プロセッサに
対して自分へのデータ転送を要求し，応答を待つ。 以上の手順における転送テーブル１６の作成処理は，図
８および図９に示すように行う。なお，この例は３次元
配列のデータを分割する場合の例である。以下の説明に
おける（ａ）　〜（ｚ）　は，図８および図９に示す（
ａ）　〜（ｚ）　に対応する。

【００４６】（ａ）　部分配列の次元１のインデックス
の下限と上限を変数ｉ１，ｊ１にセットする。同様に，
次元２のインデックスの下限と上限を変数ｉ２，ｊ２に
，次元３のインデックスの下限と上限を変数ｉ３，ｊ３
にセットする。また，ｐ１，ｑ１，ｐ２，ｑ２，ｐ３，
ｑ３に，それぞれｉ１，ｊ１，ｉ２，ｊ２，ｉ３，ｊ３
に対応する分割区間番号をセットする。

【００４７】（ｂ）　変数ｒ１にｐ１をセットする。 （ｃ）　すべてのｒ２＝ｐ２，…，ｑ２；ｒ３＝ｐ３，
…，ｑ３について，転送テーブル　ｔａｂｌｅ（ｒ１，
ｒ２，ｒ３）の次元１の下限値として，ｉ１の値を設定
する。

【００４８】（ｄ）　ｒ１＝ｑ１ならば，処理（ｉ）　
へ進む。 （ｅ）　次元１の分割区間ｒ１の上限値を，変数ｔｏｐ
に設定する。 （ｆ）　すべてのｒ２＝ｐ２，…，ｑ２；ｒ３＝ｐ３，
…，ｑ３について，転送テーブル　ｔａｂｌｅ（ｒ１，
ｒ２，ｒ３）の次元１の上限値として，ｔｏｐの値を設
定する。

【００４９】（ｇ）　ｒ１に１を加算する（ｈ）　すべ
てのｒ２＝ｐ２，…，ｑ２；ｒ３＝ｐ３，…，ｑ３につ
いて，転送テーブル　ｔａｂｌｅ（ｒ１，ｒ２，ｒ３）
の次元１の上限値として，ｔｏｐ＋１の値を設定する。 その後，処理（ｄ）　へ戻る。

【００５０】（ｉ）　すべてのｒ２＝ｐ２，…，ｑ２；
ｒ３＝ｐ３，…，ｑ３について，転送テーブル　ｔａｂ
ｌｅ（ｒ１，ｒ２，ｒ３）の次元１の上限値として，ｊ
１の値を設定する。 （ｊ）　変数ｒ２にｐ２をセットする。

【００５１】（ｋ）　すべてのｒ１＝ｐ１，…，ｑ１；
ｒ３＝ｐ３，…，ｑ３について，転送テーブル　ｔａｂ
ｌｅ（ｒ１，ｒ２，ｒ３）の次元２の下限値として，ｉ
２の値を設定する。 （ｌ）　ｒ２＝ｑ２ならば，処理（ｑ）　へ進む。

【００５２】（ｍ）　次元２の分割区間ｒ２の上限値を
，変数ｔｏｐに設定する。 （ｎ）　すべてのｒ１＝ｐ１，…，ｑ１；ｒ３＝ｐ３，
…，ｑ３について，転送テーブル　ｔａｂｌｅ（ｒ１，
ｒ２，ｒ３）の次元２の上限値として，ｔｏｐの値を設
定する。

【００５３】（ｏ）　ｒ２に１を加算する（ｐ）　すべ
てのｒ１＝ｐ１，…，ｑ１；ｒ３＝ｐ３，…，ｑ３につ
いて，転送テーブル　ｔａｂｌｅ（ｒ１，ｒ２，ｒ３）
の次元２の上限値として，ｔｏｐ＋１の値を設定する。 その後，処理（ｌ）　へ戻る。

【００５４】（ｑ）　すべてのｒ１＝ｐ１，…，ｑ１；
ｒ３＝ｐ３，…，ｑ３について，転送テーブル　ｔａｂ
ｌｅ（ｒ１，ｒ２，ｒ３）の次元２の上限値として，ｊ
２の値を設定する。 （ｒ）　変数ｒ３にｐ３をセットする。

【００５５】（ｓ）　すべてのｒ１＝ｐ１，…，ｑ１；
ｒ２＝ｐ２，…，ｑ２について，転送テーブル　ｔａｂ
ｌｅ（ｒ１，ｒ２，ｒ３）の次元３の下限値として，ｉ
３の値を設定する。 （ｔ）　ｒ３＝ｑ３ならば，処理（ｙ）　へ進む。

【００５６】（ｕ）　次元３の分割区間ｒ３の上限値を
，変数ｔｏｐに設定する。 （ｖ）　すべてのｒ１＝ｐ１，…，ｑ１；ｒ２＝ｐ２，
…，ｑ２について，転送テーブル　ｔａｂｌｅ（ｒ１，
ｒ２，ｒ３）の次元３の上限値として，ｔｏｐの値を設
定する。

【００５７】（ｗ）　ｒ３に１を加算する（ｘ）　すべ
てのｒ１＝ｐ１，…，ｑ１；ｒ２＝ｐ２，…，ｑ２につ
いて，転送テーブル　ｔａｂｌｅ（ｒ１，ｒ２，ｒ３）
の次元２の上限値として，ｔｏｐ＋１の値を設定する。 その後，処理（ｔ）　へ戻る。

【００５８】（ｙ）　すべてのｒ１＝ｐ１，…，ｑ１；
ｒ２＝ｐ２，…，ｑ２について，転送テーブル　ｔａｂ
ｌｅ（ｒ１，ｒ２，ｒ３）の次元３の上限値として，ｊ
３の値を設定し，転送テーブルの作成を完了する。デー
タを転送する転送装置は，図１０に示す処理論理■〜■
により転送元または転送先のアドレスを決定する。

【００５９】■　　データ数をＮ，先頭アドレスをｂ，
連続データ数をｗ，インターバルをｉとする。 ■　　変数ｋ０に０，変数ｄに（ｉ−ｗ），アドレスａ
ｄｄｒにｂを設定する。 ■　　変数ｋ１に０を設定する。

【００６０】■　　変数ｋ０がＮになったならば，処理
を終了する。 ■　　アドレスａｄｄｒをアクセスする。転送元の場合
，読み出し（Ｒｅａｄ），転送先の場合，書き込み（Ｗ
ｒｉｔｅ）を行う。 ■　　アドレスａｄｄｒを１歩進する。変数ｋ０，ｋ１
にそれぞれ１を加算する。

【００６１】■　　変数ｋ１がｗになるまで，■へ戻っ
て処理を繰り返す。 ■　　変数ｋ１がｗになったならば，アドレスａｄｄｒ
にｄを加えた後，■へ戻って同様に処理を繰り返す。デ
ータを転送する転送装置は，以上の処理論理によってア
ドレスを決定するハードウェアによって容易に構成でき
る。または，各プロセッサにおけるソフトウェアによっ
て構成することも可能である。

【００６２】分割配列の初期化に本発明を適用する場合
，以下のように行う。ファイルやオブジェクトコードに
書かれている値での分割配列の初期化は，これらの初期
化データ列を１×…×１に分割された配列とみなし，各
プロセッサによる分配または収集を行うことで実現する
ことができる。ただし，シーケンシャルファイルからの
入力の場合には，プロセッサ間で逐次化の処理が必要で
ある。排他処理が必要な場合もある。

【００６３】分割配列の出力に本発明を適用する場合，
以下のように行う。ファイルやプリンタへの分割配列の
出力は，これらの出力先を１×…×１に分割された配列
とみなし，各プロセッサで本発明による分配を適用する
ことで実現することができる。ただし，シーケンシャル
ファイルへの出力や，出力順序に意味のあるプリンタ出
力の場合には，プロセッサ間で逐次化の処理が必要であ
る。排他処理が必要な場合もある。

【００６４】図１１および図１２は，本発明の適用対象
となる分割割付けの例と実際のメモリにおけるデータの
配置例を示している。例えば図１１の（イ）に示す２次
元配列Ｘ（８，１２）の長方形型の部分配列Ｘ（１：６
，１：７）を，第１次元方向に順に区間幅２，３，３，
第２次元方向に順に区間幅４，４，４で分割すると，そ
の分割イメージは，図１１の（ロ）に示すようになる。

【００６５】この３×３ブロックに分割された各ブロッ
ク内のデータを，メモリ上の連続アドレスに割り付ける
ようにすると，メモリ割付けは，図１２に示す（イ）〜
（ヘ）に示すような状態になる。部分配列は，６つのブ
ロックにまたがって，一見不規則なアドレスに分散配置
される形になる。しかし，分散メモリ型の場合などに，
各プロセッサは分割法に応じたメモリ割付けを意識し，
効率よくデータを処理することが可能である。

【００６６】

【発明の効果】以上説明したように，本発明によれば，
分割形状の異なる配列間の転送や，分割配列への入出力
処理を，統一的に簡単かつ効率よく行うことができる。 特に，分散メモリ型並列計算機でのデータ転送処理の効
率化も可能であり，ユーザプログラム等の負担軽減に大
きな効果がある。

【図面の簡単な説明】

【図１】本発明の原理構成図である。

【図２】本発明の他の構成例を示す図である。

【図３】本発明の実施例に係る転送テーブルの構成例を
示す図である。

【図４】本発明の一実施例による再分配説明図である。

【図５】本発明の一実施例で用いる分割情報テーブルの
例を示す図である。

【図６】本発明の一実施例に係る転送テーブルの例を示
す図である。

【図７】本発明の一実施例によるメモリ割付けの例を示
す図である。

【図８】本発明の一実施例による転送テーブル作成処理
説明図である。

【図９】本発明の一実施例による転送テーブル作成処理
説明図である。

【図１０】本発明の一実施例によるデータ転送制御説明
図である。

【図１１】本発明に関係する分割割付けの例を示す図で
ある。

【図１２】本発明に関係するメモリ割付けの例を示す図
である。

【図１３】並列計算機における配列データの分割例を示
す図である。

【符号の説明】

１０ａ〜１０ｃ　　プロセッサ １１　　　　　　転送テーブル作成手段１２　　　　　
　データ転送手段 １３　　　　　　分割区間番号指定手段１４　　　　　
　分割区間上下限指定手段１５　　　　　　共用メモリ １６　　　　　　転送テーブル １７　　　　　　分配データ格納域 １８　　　　　　転送先データ格納域 １９　　　　　　収集データ格納域 ２０　　　　　　転送元データ格納域

Claims (2)

【特許請求の範囲】
1. 【請求項１】　　複数のプロセッサ（１０）がそれぞれ
   自装置に割り付けられたデータを処理する計算機であっ
   て，入力装置から入力したデータまたは記憶装置に格納
   されている配列データの全部または一部を分割して各記
   憶空間または各プロセッサ（１０）に割り付ける配列デ
   ータの分配／収集処理装置において，各記憶空間または
   各プロセッサ（１０）への割り付け対象となる１以上の
   任意の次元方向で分割した分割ブロックに対応して，各
   次元ごとの範囲に関する情報を持つ転送テーブル（１６
   ）を作成する転送テーブル作成手段（１１）と，作成し
   た転送テーブル（１６）に基づいて，各分割ブロックご
   とにデータを各記憶空間または各プロセッサ（１０）に
   転送するデータ転送手段（１２）とを備え，任意の転送
   パターンによりデータを自動分配するようにしたことを
   特徴とする配列データの分配／収集処理装置。
2. 【請求項２】　　複数のプロセッサ（１０）がそれぞれ
   自装置に割り付けられたデータを処理する計算機であっ
   て，各記憶空間または各プロセッサ（１０）に分散して
   配置されているデータの全部または一部を，ある記憶空
   間または１つのプロセッサ（１０）に収集する配列デー
   タの分配／収集処理装置において，各記憶空間または各
   プロセッサ（１０）へ分散して配置されている１以上の
   任意の次元方向で分割した分割ブロックに対応して，収
   集すべきデータの各次元ごとの範囲に関する情報を持つ
   転送テーブル（１６）を作成する転送テーブル作成手段
   （１１）と，作成した転送テーブル（１６）に基づいて
   ，各分割ブロックごとの収集データを，ある記憶空間ま
   たは１つのプロセッサ（１０）に転送するデータ転送手
   段（１２）とを備え，任意の転送パターンによりデータ
   を自動収集するようにしたことを特徴とする配列データ
   の分配／収集処理装置。