JPH05108699A - 共有データのベクトル処理方法 - Google Patents

Abstract

(57)【要約】 【目的】 本発明の目的は、共有部分がある複数データ
の SIMD 並列計算機またはパイプライン型ベクトル計算
機によるベクトル処理方法を提供することにある。 【構成】 複数のデータからなる集合をそれぞれ並列処
理可能な複数のデータ集合 051 に並列処理によって分
割し (ステップ 052) 、分割後の一集合に属するデータ
は並列処理し (ステップ 072、073)、ことなるデータ集
合に属するデータどうしは逐次に処理する。 【効果】 従来はできなかった共有部分がある複数デー
タのベクトル処理を可能にし、また資源のロックという
高価な手段を使用せずに共有資源の排他的アクセスを可
能にする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、大規模データの並列処
理において、複数プロセス間で共有されたデータをパイ
プライン型ベクトル計算機または SIMD 型並列計算機に
よって効率よく処理する方法をあたえることを目的とす
る。

【０００２】

【従来の技術】従来、共有部分がある複数データの処理
は逐次計算機または MIMD 型並列計算機によっておこな
われた。このような処理の方法に関しては、つぎの文献
に記されている。

【０００３】E. Dijkstra : Cooperating Sequential
Processes, in Programming Languages, F. Genuys, E
d., Academic Press, New York, 1968. ここで共有部分がある複数データとは、それぞれ複数個
の要素をふくむ複数のデータであって、各データが部分
的に同一の要素を共有しているもののことをいう。図 1
に共有部分がある複数データの例をあげる。図 1 a は
共有部分がある複数のリストの例である。リスト頭部 0
01 およびリスト頭部 003 はそれぞれリストの先頭要素
である。これらのリストは要素 004 および 005 を共有
している。

【０００４】共有部分がある複数データの、複数プロセ
スによる並列処理を逐次計算機または MIMD 型並列計算
機によっておこなう場合には、セマフォまたはそれを高
度化した方法が使用される。これらの方法は、前記の複
数のプロセスがまったく独立に動作することを前提とし
ている。MIMD 並列計算機の場合には、もともと独立に
動作することができる複数のプロセッサをそなえている
ため、プロセスの独立動作は容易に実現することができ
る。また逐次計算機の場合には、プロセスのきりかえ
(スウィッチング) という方法によって、独立に動作す
るプロセスを実現することができる。

【０００５】しかしながら、共有部分がある複数データ
の処理は、従来は SIMD 型あるいはベクトル計算機にお
いては処理できなかった。処理できなかった理由は、こ
れらの計算機においては複数のデータの処理をおこなう
場合にも、それらを 1 個の命令によって処理するよう
に構成されており、セマフォの使用の前提となる各プロ
セスの独立動作が効率よく実現できないからである。

【０００６】

【発明が解決しようとする課題】本発明の第 1 の課題
は、SIMD 型並列計算機あるいはパイプライン型ベクト
ル計算機 (以下、両者をあわせて単に「ベクトル計算
機」とよぶ) において、共有部分がある複数データの高
速な処理を可能にすることである。いいかえれば、複数
のプロセスが共有資源を排他的にアクセスすることによ
って成し遂げられる仕事をベクトル計算機によって高速
に処理することを可能にする方法を開発することであ
る。とくに、複数のプロセスが 1 個の共有資源をアク
セスする場合だけではなく、複数の共有資源をアクセス
しながら成し遂げるべき仕事を、ベクトル計算機によっ
て効率よく処理できるようにすることがおおきな課題で
ある。

【０００７】本発明の第 2 の課題は、共有資源を排他
的にアクセスする必要がある処理を、資源のロックとい
うコストが高い方法をつかわずに並列処理することを可
能にすることである。逐次計算機や MIMD 型並列計算機
においてはセマフォに対する演算によって資源を他のプ
ロセスからアクセスできないようにロックをかけてから
使用し、使用がおわるとふたたびセマフォに対する演算
によってロックを解除する。実際にはロックがかかって
いる全時間のあいだ他のプロセスが資源をアクセスして
はならないとはかぎらないにもかかわらず、ロックがか
かっているあいだは他のプロセスはいっさい当該資源を
アクセスすることができない。また、セマフォに対する
演算じたいが、パイプライン計算機においては相対的に
コストが高い。なぜなら、これらの演算はパイプライン
的に実行することができず、プロセッサおよび主記憶の
一部の領域をひとつのプロセスが数〜 10 数マシン・サ
イクル占有することになるからである。すなわち、資源
を占有することなく、パイプラインをつかって排他的ア
クセスすることを可能にすることが課題である。

【０００８】本発明の目的は、大規模データの並列処理
において、共有部分がある複数データあるいは複数プロ
セス間で共有されたデータや資源をパイプライン型ベク
トル計算機または SIMD 型並列計算機によって効率よく
処理する方法を提供することにある。

【０００９】

【課題を解決するための手段】前記の 2 個の課題は、
つぎのような手段によって解決することができる。すな
わち、並列処理すべき複数のデータからなる第 1 のデ
ータ集合をデータ分割処理によってそれぞれ並列処理可
能な複数の第 2 のデータ集合に分割する。分割された
結果えられた第 2のデータ集合のうちのひとつに属する
複数のデータは並列処理する。また、複数のことなる第
2 のデータ集合に属するデータどうしは逐次に処理す
る。

【００１０】ここで、データ分割処理はつぎのように実
行される。まず、前記の第 1 のベクトルの要素に対し
て一意にわりあてられたラベルを、第 1 のベクトルの
各要素からさされた第 1 のデータ集合に属する各デー
タ内にわりあてられた作業領域にかきこむ「ラベルかき
こみ処理」をおこなう。つぎに、ベクトルの各要素から
指された第 1 のデータ集合に属する各データの作業領
域からラベルをよみだして、よみだしたラベルとかきこ
んだラベルとを比較する「ラベルよみだし処理」をおこ
なう。さらに、前記のよみだしたラベルと前記のかきこ
んだラベルが一致しないベクトル要素だけからなる第 2
のベクトルをつくる「不一致ラベル収集処理」をおこ
なう。そして、それが空でないかぎり第 2 のベクトル
を第 1 のベクトルとみなして「ラベルかきこみ処
理」、「ラベルよみだし処理」、「不一致ラベル収集処
理」をくりかえし実行する。

【００１１】

【作用】前記の各処理ステップは、つぎのように作用す
る。データ分割処理においては、前記の第 1 のデータ
集合にふくまれるデータのうち、記憶領域を共有してい
るために並列処理できない複数のデータは、「不一致ラ
ベル収集処理」においてそのうちのちょうど 1 個をの
ぞいて「不一致」と判定される。そのため、前記のくり
かえし実行における 1 回のくりかえしごとに 1 個の第
2 のデータ集合が出力される。その結果、前記の並列
処理できない複数のデータはことなる第 2のデータ集合
に属させられる。すなわち、データ分割処理において
は、分割された結果えられたひとつの集合に属するすべ
てのデータは並列処理可能になるように実行される。そ
のため、第1 の課題が解決される。すなわち第 2 のデ
ータ集合のそれぞれをSIMD 型並列計算機またはパイプ
ライン型ベクトル計算機によって並列処理することがで
きる。

【００１２】また、前記の並列処理においては、同時に
第 2 の課題が解決されている。すなわち、SIMD 型並列
計算機またはパイプライン型ベクトル計算機においては
自動的に同期がとられるため、本発明の方法においては
資源をロックすることなく、ラベルよみだし処理を開始
するまえにラベルかきこみ処理が終了していることを保
証することができ、したがって資源のロックというコス
トが高い方法を使用せずに共有資源の排他的アクセスを
ふくむ処理を並列処理することができる。

【００１３】

【実施例】以下、本発明の 2 個の実施例を順に説明す
るが、そのまえに 2 個の実施例に共通な部分につい
て、図 2 を使用して説明する。図 2 は前記の実施例に
おける処理の全体を示したものである。この処理の入力
は並列処理すべき複数のデータからなる集合 051 であ
る。前記の実施例においては、まずこのデータ 051 を
データ分割処理 052 によってそれぞれ並列処理可能な
複数のデータ集合 062, 063などに分割する。すなわ
ち、集合 051 にふくまれるデータのうち、記憶領域を
共有しているために並列処理できない複数のデータは、
ことなるデータ集合たとえば 062 と 063 とに属させら
れる。データ分割処理 052 は、分割された結果えられ
たひとつの集合に属するすべてのデータは並列処理可能
になるように実行される。すなわち、データ分割処理05
2 の結果として、データ集合 062 に属するすべてのデ
ータはたがいに並列に処理することができ、データ集合
063 に属するすべてのデータはたがいに並列に処理す
ることができるようになる。

【００１４】つづいて、各データ集合に対して並列処理
がおこなわれる。すなわち、データ集合 062 に属する
各データに対しては並列に処理 072 が実行され、デー
タ集合063 属する各データに対しては並列に処理 073
が実行される。ただし、各並列処理どうしは逐次に実行
される。すなわち、並列処理 073 は並列処理 072 が完
了してから実行される。

【００１５】以下の各実施例の説明は、データ分割処理
052 の実現方法に関する。まず、本発明の第 1 の実施
例について説明する。この実施例は、並列に実行すべき
処理 072, 073 などにおいて、それぞれ 1 個ずつの共
有データを使用する場合に関する。

【００１６】まず、本実施例における入出力について説
明する。本実施例においては、ベクトル V を入力す
る。V の各要素は並列処理すべきデータ d1, d2, …, d
N のそれぞれをふくむ記憶領域へのポインタまたはイン
デクスである。d1, d2, …, dNのなかには重複があって
もよい。すなわち、ひとつのデータが列 d1, d2, …,dN
のなかに複数回あらわれてもよい。このように複数回
あらわれるデータが並列処理できないデータであり、し
たがってデータ分割処理 052の結果としてことなるデー
タ集合に属させるべきデータである。V の要素 v がさ
す記憶領域をv→ とあらわし、そこに格納されたデータ
の値は v→d とあらわす。

【００１７】また、本実施例においては、並列処理可能
なデータからなる集合S1, S2, …,SM を出力する。ただ
し、集合 S1, S2, …, SM の和集合はちょうど本実施例
における入力データの集合にひとしく、これらの集合に
は要素の重複がない。集合の個数 M は本実施例のステ
ップ 121 においてもとめられる。

【００１８】本実施例における処理 052a は、データ分
割処理 052 の実現方法をしめしたものである。本処理
が終了したあとに、本実施例において出力された前記の
集合のそれぞれを並列処理する。すなわち、本実施例に
おいてはこのような並列処理が可能なように、データを
複数の集合に分割する。

【００１９】つぎに、本処理の実行にさきだっておこな
うべき準備処理 100 について説明する。まず、本実施
例における処理において使用するために、V のすべての
要素について、要素 v がさす記憶領域 v→ 内に作業領
域をわりあてておく。この作業領域を v→w とあらわ
す。記憶領域内にとるということは、v1→ と v2→ と
が同一の記憶領域であれば v1→w とv2→w とも同一で
あることを意味する。

【００２０】また、ベクトル V の各要素に重複のない
ようにつけることができる整数などのラベルをさだめて
おく。ラベルは実行時より前にきめておくことも可能で
ある。V の第 i 要素 vi のラベルとしてもっともかん
たんに計算できるものは、Vのなかでの vi のインデク
スすなわち要素番号 i または先頭からの変位すなわち
バイト数などである。

【００２１】つづいて、本実施例における処理 052a の
手順について、図 3 を使用して説明する。まずステッ
プ 101 において、変数 j の値を 1 とする。そしてス
テップ 111 において、ベクトル V が空になるまでステ
ップ 112 から 118 までの処理をくりかえし実行する。

【００２２】ステップ 112 においては、すべての作業
領域 v1→w, v2→w, …, vn→w に Vの要素 v1, v2,
…, vn のラベルをかきこむ。ステップ 114において
は、すべての作業領域 v1→w, v2→w, …, vn→w から
ラベルをよみだし、V の要素 v1,v2, …, vn のラベル
と一致するかどうかを判定する。ただし、ラベルのよみ
だしのまえにステップ 112 のすべての処理が完了して
いなければならない。

【００２３】ステップ 116 においては V の要素からさ
されるデータのうち不一致が生じたと判定されたデータ
をのぞいたものからなる集合をもとめて S1 とする。す
なわち、V の要素 uk (k = 1, 2, …, m) のラベルを l
k とするとき、uk→w = lkという関係がなりたつような
V のすべての要素 u1, u2, …, um をもとめ、Sjを u1
→d, u2→d, …, um→dを要素からなる集合とする。こ
れにより、並列処理可能なデータの集合がひとつえられ
たことになる。

【００２４】ステップ 111 におけるつぎのくりかえし
の準備のため、まずステップ 117 においては変数 j に
1 をくわえる。またステップ 118 においては、Sj に
ふくまれるデータへのポインタを V から削除して、要
素をつめあわせることによってえられたベクトルをあら
たな V とする。これにより、V の要素数は減少する。

【００２５】ベクトル V が空すなわち要素をもたなく
なって、ステップ 111 が終了すると、ステップ 121 に
おいて、変数 M に j−1 を代入する。以上で、第 1 の
実施例におけるデータ分割処理は終了する。

【００２６】つぎに、本発明の第 2 の実施例について
説明する。この実施例は、並列に実行すべき処理 072,
073 などにおいて、それぞれ複数個ずつの共有データを
使用する場合に関する。

【００２７】まず、本実施例におけるデータ分割処理 0
52a の入出力について説明する。本実施例においては、
ベクトル V1, V2, …, VL を入力する。V の第 i 要素
はデータ di1, di2, …, diN をふくむ記憶領域へのポ
インタまたはインデクスである。データ d1j, d2j, …,
dLj がたがいに並列処理すべき複数の処理のなかのj
番目の処理において使用されるデータである。 これら
のデータのなかには重複があってもよい。すなわち、ひ
とつのデータが列 di1, di2, …, diN のなかに複数回
あらわれてもよい。ベクトル Vk の要素 v がさす記憶
領域をv→ とあらわし、そこに格納されたデータの値は
v→d とあらわす。

【００２８】また、本実施例においては並列処理可能な
データの組 < di1, di2, …, diL >からなる集合 S1, S
2, …, SM を出力する。ただし、集合 S1, S2, …, SM
の和集合はちょうど本実施例における入力データすべて
からなる列をふくんでいる。また、これらの集合には要
素の重複がない。集合の個数 M は本処理においてもと
められる。

【００２９】本実施例における処理 052b は、052a と
同様にデータ分割処理 052 を詳細化したものである。
本処理が終了したあとに、本処理において出力された前
記の集合のそれぞれを並列処理する。すなわち、本処理
はこのような並列処理が可能なように、データを複数の
集合に分割する。

【００３０】つぎに、本処理の実行にさきだっておこな
うべき準備処理 200 について説明する。まず、本処理
において使用するために、すべてのベクトル Vk のすべ
ての要素について、要素 v がさす記憶領域 v→ 内に作
業領域をわりあてておく。この作業領域を v→w とあら
わす。記憶領域内にとるということは、v1→ と v2→と
が同一の記憶領域であれば v1→w とv2→w とも同一で
あることを意味する。

【００３１】また、ベクトル V1, V2, …, VL の各要素
に重複のないようにつけることができる整数などのラベ
ルをさだめておく。ラベルは実行時より前にきめておく
ことも可能である。Vk の第 i 要素 vi のラベルとして
もっともかんたんに計算できるものは、Vk のなかでの
vi のインデクスすなわち要素番号 i または先頭からの
変位すなわちバイト数などである。本実施例においては
V10, V11, V20 などのラベルを使用する。

【００３２】つづいて、本実施例における処理 052b の
手順について、図 2 を使用して説明する。まずステッ
プ 201 において、変数 j の値を 1 とする。そしてス
テップ 211 において、ベクトル V1, V2, …, VL が空
になるまでステップ212 から216 までの処理をくりかえ
し実行する。

【００３３】ステップ 212 においては、k の値を 1,
2, …, L の範囲でかえながら、ステップ 213 の処理を
くりかえし実行する。ステップ 213 においては、作業
領域 vk1→w, vk2→w, …, vkn→w に Vk の要素 vk1,
vk2, …, vkn のラベルをかきこむ。

【００３４】ステップ 214 においては、k の値を 1,
2, …, L の範囲でかえながら、ステップ 215 の処理を
くりかえし実行する。ステップ 215 においては、すべ
ての作業領域 vk1→w, vk2→w, …, vkn→w からラベル
をよみだし、Vk の要素 vk1, vk2, …, vkn のラベルと
一致するかどうかをしらべる。ただし、ラベルのよみだ
しのまえにステップ 212 のすべての処理が完了してい
なければならない。

【００３５】ステップ 216 においては V1, V2, …,VL
の要素からさされるデータの組 <di1, di2, …, diL >
(i = 1, 2, …, N) のうち、いずれかのk (k = 1, 2,
…, L) に関して Vk の第 i 要素からさされるデータの
うち不一致が生じたデータをふくまない組からなる集合
をもとめて Sj とする。すなわち、つぎのようにして集
合 Sj をさだめる。V1, V2, …, VL の第 i 要素をそれ
ぞれ v1i, v2i, …, vLi とし、これらの要素に対して
さだめられたラベルをそれぞれ l1i, l2i,…, lLi とす
るとき、v1i→w = l1i かつ v2i→w = l2i かつ … か
つ vLi→w =lLi という関係がなりたつような要素 v1i,
v2i, …, vLiからさされるデータによって構成される
すべての組 < di1, di2, …, diL > (i = i1, i2, …,
im)を要素とする集合をつくって Sj とする。これによ
り、並列処理可能なデータの組からなる集合がひとつえ
られたことになる。

【００３６】ステップ 211 におけるつぎのくりかえし
の準備のため、まずステップ 217 においては変数 j に
1 をくわえる。またステップ 218 においては、Sj に
ふくまれるデータへのポインタを V1, V2, …, VL のそ
れぞれから削除して、要素をつめあわせることによって
えられたベクトルをあらたな V1, V2, …, VL とする。
これにより、V の要素数は減少する。

【００３７】ベクトル V1, V2, …, VL が空すなわち要
素をもたなくなってステップ 211が終了すると、ステッ
プ 221 において、変数 M に j−1 を代入する。以上で
第2 の実施例におけるデータ分割処理は終了する。

【００３８】以上の説明においては処理 210 すなわち
ラベルのかきこみ処理におけるかきこみ順序が十分に詳
細化されていなかったので、つづいて、処理 210 を詳
細化した手順を、図 5 を使用して説明する。図 5 の手
順 210a においては、図 4のステップ 212 における最
後のくりかえしを分離してあつかっている。すなわち、
ステップ 212 はステップ 212a とステップ 212b とに
分割されている。ステップ 212a においては、k の値を
1, 2, …, L−1 の範囲でかえながら、ステップ 213a
の処理をくりかえし実行する。ステップ 213a において
は、作業領域vk1→w, vk2→w, …, vkn→w にベクトル
Vk の要素 vk1, vk2, …, vkn のラベルをかきこむ。こ
のかきこみは並列に実行することができる。すなわち、
任意の 1 個のラベルかきこみは、他の任意のラベルの
かきこみより前に実行されてもかまわないし、後に実行
されてもかまわない。また、同一の記憶領域に同時にか
きこみがおこなわれた場合に、かきこまれた複数の値の
うちのいずれかがただしく格納されることが保証されて
いれば、同時にかきこむこともできる。

【００３９】つぎに、作業領域 vL1→w, vL2→w, …, v
Ln→w にベクトル VL の要素 vL1,vL2, …, vLn のラベ
ルをかきこむ。この処理は、この順に逐次に実行する。
このように、すべてのくりかえしを並列に実行するので
はなく最後のくりかえしだけを分離して実行するのは、
デッドロックをふせぐためである。以上で処理 220を詳
細化した処理 210a についての説明をおわる。

【００４０】以上の手順 210a によって、ベクトル V1,
V2, …, VL からさされるすべての作業領域にラベルが
かきこまれた。2 個以上のベクトル要素からさされてい
る作業領域には重複してラベルがかきこまれ、そのうち
のひとつのラベルがただしくかきこまれ、他のラベルは
前記のひとつのラベルによって上書きされて消去され
た。

【００４１】つづいて、本第 2 の実施例におけるデー
タ集合の分割法を、「食事をする哲学者」の問題に適用
した例を説明する。まず、図 6 を使用して「食事をす
る哲学者」の問題について説明する。この問題はそれじ
たいが実用的な問題ではないが、並列処理法の能力をた
めすための問題である。この問題は、思索と食事を交互
におこなう 5 人の哲学者のふるまいをシミュレートす
るものである。図 6 において、テーブル中央にはスパ
ゲティの山があり、その周囲に 5 本のフォークすなわ
ち Fork0, Fork1, Fork2, Fork3, Fork4 がおかれてい
る。テーブルの周囲には 5 人の哲学者 Philosopher0,
Philosopher1, Philosopher2, Philosopher3, Philosop
her4 のための席が用意されている。哲学者はこの席か
らはなれて思索し、空腹になると席について食事をす
る。スパゲティを食べるためには、哲学者はその両側の
フォークを必要とする。フォークが片側だけしか確保さ
れなければ、食べることができない。したがって、席が
隣接する哲学者は同時に食事をすることができないし、
最悪の場合は Philosopher0 が Fork0, Philosopher1が
Fork1, Philosopher2 が Fork2, Philosopher3 が For
k3, Philosopher4 がFork4 をとりあげて、だれもが食
事をすることができない状態になりうる。この問題にお
いては、並列処理すべき共有データはフォーク Fork0,
Fork1, Fork2,Fork3, Fork4 であり、並列処理 (072, 0
73 など) の内容は「食事」である。

【００４２】つづいて、図 7 から図 15 を使用して、
本発明の第 2 の実施例を「食事をする哲学者」の問題
に適用した場合のデータの変化を説明する。データとし
ては、図 7 に図示したつぎのようなものを用意する。
各フォークをあらわすデータ 501、各哲学者が左手でも
つべきフォークへのポインタをふくむベクトル V1 51
1、各哲学者が右手でもつべきフォークへのポインタを
ふくむベクトル V2 512。ベクトル V1 および V2 の第
0 要素は哲学者 Philosopher0 が左手でもつべきフォー
クと右手でもつべきフォークとをあらわしている。第 1
〜 4 要素も同様に、それぞれ哲学者 Philosopher1 〜
Philosopher4 が左手でもつべきフォークと右手でもつ
べきフォークとをあらわしている。フォークをあらわす
データ 501のそれぞれは共有されている。また、これら
の内部には、第 2 の実施例における準備処理が適用さ
れ、作業領域 w が確保されている。

【００４３】図 8 は、ステップ 212a を実行した直後
のデータの状態をあらわしている。ベクトル V1 の第 0
要素〜第 3 要素、ベクトル V2 の第 0 要素〜第 3 要
素が作業領域にかきこまれている。これにより、すべて
の作業領域の内容がかきかえられている。これらは並列
にかきこまれるため、2 個ずつラベルがかきこまれる作
業領域にいずれのラベルが他方によって上書きされ、い
ずれのラベルがのこるかは不確定である。しかし、図 8
においては V1 の第 1 要素のラベルと V2 の第 0 要
素のラベルのうちでは後者、V1 の第 2 要素のラベルと
V2 の第 1 要素のラベルのうちでは前者、V1 の第 3
要素のラベルと V2 の第 2 要素のラベルのうちでは後
者がのこることを仮定している。しかし、他の任意の場
合にもデータ分割処理 052a はただしく動作する。すな
わち、他の場合には分割はかわるが、分割によってえら
れる各データ集合が並列処理できることにはかわりがな
く、したがって分割のただしさは保証される。

【００４４】図 9 は、ステップ 212b を実行した直後
のデータの状態をあらわしている。ベクトル V1 の第 4
要素、ベクトル V2 の第 4 要素が作業領域にかきこま
れている。これにより、Fork0 と Fork4 の作業領域の
内容がかきかえられている。

【００４５】図 10 は、ステップ 214 を実行した直後
のデータの状態およびその実行の過程で使用されたデー
タをあらわしている。まず、ベクトル 521 はベクトル
V1の各要素のラベルと、各作業領域からよみだしたラベ
ルとを比較して、同一である場合には true、同一でな
い場合には false を、同一添字の要素に格納すること
によってえられたベクトルである。すなわち、ベクトル
521 は、ベクトル V1の各要素のラベルのうち、第 2
要素と第 4 要素のラベルが上書きされずに作業領域に
のこっており、他の要素のラベルは上書きされたことを
あらわしている。また、ベクトル 522 ははベクトル V2
の各要素のラベルと、各作業領域からよみだしたラベ
ルとを比較して、同一である場合には true、同一でな
い場合には false を、同一添字の要素に格納すること
によってえられたベクトルである。すなわち、ベクトル
522 は、ベクトル V2 の各要素のラベルのうち、第 0
要素、第 2 要素、第 4 要素のラベルが上書きされずに
作業領域にのこっており、他の要素のラベルは上書きさ
れたことをあらわしている。ベクトル 521 とベクトル
522 の要素ごとの論理積をとることによってえられたの
がベクトル 523 である。ベクトル 523 は、処理 216
においてデータの組が集合 S1 にふくめられるかどうか
をあらわしている。すなわち、ベクトル 523 の第 0 要
素は falseであるから、V1 の第 0 要素と V2 の第 0
要素がさすデータからなる組すなわち <Fork0, Fork1>
は集合 S1 にふくまれない。また、ベクトル 523の第 2
要素は true であるから、V1 の第 2 要素と V2 の第
2 要素がさすデータからなる組すなわち <Fork2, Fork3
> は集合 S1 にふくまれる。

【００４６】したがって、集合 S1 は図 16 に図示した
データ集合 062a のようになる。すなわち、処理 216
が実行されると S1 は <Fork2, Fork3> と <Fork4, For
k0>という 2 個の要素からなる集合となる。

【００４７】図 11 は、ステップ 218 を実行した直後
のデータの状態およびその実行の過程で使用されたデー
タをあらわしている。すなわち、S1 にふくまれるデー
タへのポインタすなわち第 2 要素と第4 要素とを V1,
V2 から削除してつめあわせることによってえられたベ
クトルが、それぞれあらたな V1, V2 とされている。

【００４８】以上のステップにおいて、第 1 の並列処
理可能なデータ集合 S1 がえられたが、図 12 〜 15 に
しめしたように、ステップ 211 におけるくりかえしご
とに並列処理可能なデータ集合が 1 個ずつえられる。
したがって、集合 S2 は図 16に図示したデータ集合 06
3a のようになり、集合 S3 は図 16 に図示したデータ
集合 064a のようになる。すなわち、S2 は <Fork0, Fo
rk1> と <Fork3, Fork4> という 2 個の要素からなる集
合となる。また、S3 は <Fork1, Fork2> という 1 個の
要素からなる集合となる。

【００４９】手順 052b の実行が完了したところで、デ
ータ分割が完了する。分割によってえられた各集合内の
データについては並列に哲学者の食事の処理をおこな
い、各集合間は逐次に前記の処理をおこなえば、食事の
処理をただしく、かつすべての哲学者に対して公平に処
理することができる。

【００５０】したがって、本実施例においては、後述す
る発明の効果以外に本発明がつぎのような効果をもって
いるということができる。本実施例においては、共有資
源すなわちフォークを使用した処理を並列処理によって
並列に実行することが可能になっているうえ、そのスケ
ジュリングはすべてのプロセスすなわち哲学者につい
て、飢えのない公平なスケジュリングになっている。

【００５１】以上の実施例における哲学者の食事の問題
においては、すべてのデータが共有されているために処
理の並列度がひくくまたデータ個数もすくないため、ベ
クトル処理による利点はすくなかった。しかし、共有デ
ータがすくなくより多数のデータをあつかう問題におい
てはたかい並列度がえられ、したがってベクトル処理に
よって飛躍的な高速処理が可能になる。

【００５２】なお、本実施例においては、並列処理の対
象データは比較的単純な構造をしていたが、レコード、
木、グラフ、ネットワークなどの、共有部分をもつ複雑
な構造データあるいはポインタ・データに対しても、本
発明の方法によってまったく同様に並列処理をおこなう
ことができる。

【００５３】

【発明の効果】本発明のデータ分割方法を使用すれば、
第 1 に SIMD 型並列計算機あるいはパイプライン型ベ
クトル計算機において、共有部分がある複数データの高
速な処理が可能になる。また、第 2 に共有資源を排他
的にアクセスする必要がある処理を、資源のロックとい
うコストが高い方法をつかわずに並列処理することが可
能になる。

【図面の簡単な説明】

【図１】共有部分がある複数データの例を示す図。

【図２】本発明の実施例におけるデータの並列処理手順
を示す図。

【図３】本発明の第 1 の実施例におけるデータ分割処
理の手順を示す図。

【図４】本発明の第 2 の実施例におけるデータ分割処
理の手順を示す図。

【図５】本発明の第 2 の実施例におけるラベルかきこ
み処理の詳細手順を示す図。

【図６】本発明の第 2 の実施例の適用例である「哲学
者の食事」の問題の説明図。

【図７】本発明の第 2 の実施例を食事の問題の処理に
適用した場合の初期状態のデータを示す図。

【図８】本発明の第 2 の実施例を食事の問題の処理に
適用した場合の第 2 の状態のデータを示す図。

【図９】本発明の第 2 の実施例を食事の問題の処理に
適用した場合の第 3 の状態のデータを示す図。

【図１０】本発明の第 2 の実施例を食事の問題の処理
に適用した場合の第 4 の状態のデータを示す図。

【図１１】本発明の第 2 の実施例を食事の問題の処理
に適用した場合の第 5 の状態のデータを示す図。

【図１２】本発明の第 2 の実施例を食事の問題の処理
に適用した場合の第 6 の状態のデータを示す図。

【図１３】本発明の第 2 の実施例を食事の問題の処理
に適用した場合の第 7 の状態のデータを示す図。

【図１４】本発明の第 2 の実施例を食事の問題の処理
に適用した場合の第 8 の状態のデータを示す図。

【図１５】本発明の第 2 の実施例を食事の問題の処理
に適用した場合の第 9 の状態のデータを示す図。

【図１６】本発明の第 2 の実施例を食事の問題の処理
に適用した場合のデータ分割処理の出力を示す図。

【符号の説明】

052a … データ分割処理の一実現方法、052b … データ
分割処理の一実現方法、210 … ラベルかきこみ処理、2
10a … ラベルかきこみ処理の一実現方法、501… 哲学
者の食事の問題におけるフォークをあらわす複数のデー
タ、511 … 哲学者の食事の問題における哲学者が左手
にもつフォークをあらわすベクトル、512 … 哲学者の
食事の問題における哲学者が右手にもつフォークをあら
わすベクトル、511a … 哲学者の食事の問題における哲
学者が左手にもつフォークをあらわすベクトル、512a
… 哲学者の食事の問題における哲学者が右手にもつフ
ォークをあらわすベクトル、511b … 哲学者の食事の問
題における哲学者が左手にもつフォークをあらわすベク
トル、512b … 哲学者の食事の問題における哲学者が右
手にもつフォークをあらわすベクトル。

Claims (2)

【特許請求の範囲】
1. 【請求項１】パイプライン型ベクトル計算機または SIM
   D 型並列計算機において、共有部分がある複数の構造デ
   ータまたはポインタ・データのそれぞれの要素に特定の
   処理をおこなう場合であって、前記の複数のデータのう
   ちのどのデータとどのデータとのあいだに共有部分が生
   じるかがあらかじめわからないために前記の複数のデー
   タのすべてを並列処理することができない場合に、 (a) 前記の複数のデータからなる第 1 のデータ集合
   を、その要素の値またはアドレスを参照することによっ
   て各要素が並列処理可能であるかどうかを判定し、その
   結果にもとづいてそれぞれが並列処理可能な複数の第 2
   のデータ集合に分割し、 (b) 前記の複数の第 2 のデータ集合のうちのひとつに
   属する複数のデータに対しては前記の特定の処理を並列
   に実行し、複数のことなる第 2 のデータ集合に属する
   データどうしに対しては前記の特定の処理を逐次に実行
   する ことを特徴とする、共有データのベクトル処理方法。
2. 【請求項２】請求項１において、前記の第 1 のデータ
   集合のすべての要素が第 1 の 1 個または複数個のベク
   トルの要素からさされている場合に、ステップ (a) を (a1) 前記の第 1 のベクトルのすべての第 1 の要素に
   対して一意にわりあてられたラベルを、前記の第 1 の
   要素からさされている前記の第 1 のデータ集合に属す
   るデータ内にわりあてられた作業領域にかきこみ、 (a2) 前記の第 1 のベクトルの各要素からさされている
   第 1 のデータ集合に属する各データの作業領域からラ
   ベルをよみだして、前記の第 1 のベクトルの各要素に
   関してよみだしたラベルと、前記の第 1 のベクトルの
   各要素に関してかきこんだラベルとを比較し、 (a3) 前記のよみだしたラベルと前記のかきこんだラベ
   ルとが一致するベクトル要素に対応する 1 個または複
   数個のデータからなる集合を前記の第 2 のデータ集合
   のうちの 1 個とし、 (a4) 前記の第 1 のベクトル要素のうち、それがさす第
   1のデータ集合のうち第 2 のデータ集合にはふくまれ
   なかったベクトル要素だけからなる、0 個以上の要素か
   ら構成される第 2 のベクトルをつくり、 (a5) 前記の第 2 のベクトルの要素数が 0 でなけれ
   ば、これを前記の第 1 のベクトルとみなして (a1), (a
   2),(a3), (a4) をくりかえし実行する というサブ・ステップによって構成することを特徴とす
   る、共有データのベクトル処理方法。