(57)【特許請求の範囲】
【請求項１】
配列Ｆに対して別の配列Ａの要素を加算するときに、その加算要素の位置を決定する中間配列ｉｎｄｅｘが存在し、
【数１】
0003845710.tif 000005
の式であって、Ｉは１からＮ（ここで、Ｎは２以上の任意の整数）までの範囲を全て昇順に網羅する上記式により表される間接アドレス参照を含む加算をベクトル計算機上で高速処理する方法において、
配列Ｆ、Ａ及びｉｎｄｅｘが記憶手段に設けられており、
（１）中間配列ｉｎｄｅｘの定義域である１からＮまでの値を格納するリストとして配列ｌｉｓｔを前記記憶手段に設けるステップと、
（２）中間配列ｉｎｄｅｘから第一要素（ｌｉｓｔ（１））を取り出し変数ＬとしてＬレジスタに格納するステップと、
（３）配列ｌｉｓｔから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納するステップと、
（４）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致するレジスタ・インデックスを第２のレジスタに格納するステップと、
（５）第２のレジスタに格納されたレジスタ・インデックスに対応する配列Ａの要素を第３のレジスタに読み込むステップと、
（６）第３のレジスタに読み込まれた配列Ａの総和を計算し、当該計算された総和をＦ（ｉｎｄｅｘ（Ｌ））に加えるステップと、
（７）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在する場合そのレジスタ・インデックスを配列ｌｉｓｔに格納するステップと、
（８）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在しなくなるまでステップ（２）から（７）を繰り返すステップと
を備える方法。
【請求項２】
ステップ（３）は、配列ｌｉｓｔを第４のレジスタに読込むステップと、その第４のレジスタから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納するステップとから成り、
ステップ（６）は、計算された総和を第５のレジスタに格納するステップと、Ｆ（ｉｎｄｅｘ（Ｌ））に第５のレジスタの値を加えるステップとから成り、
ステップ（７）は、第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスを第６のレジスタに格納するステップと、第６のレジスタに格納されたレジスタ・インデックスを配列ｌｉｓｔに格納するステップとから成る
請求項１記載の方法。
【請求項３】
配列Ｆに対して別の配列Ａの要素を加算するときに、その加算要素の位置を決定する中間配列ｉｎｄｅｘが存在し、
【数２】
0003845710.tif 000006
の式であって、Ｉは１からＮ（ここで、Ｎは２以上の任意の整数）までの範囲を全て昇順に網羅する上記式により表される間接アドレス参照を含む加算を高速処理するベクトル計算機において、
配列Ｆ、Ａ及びｉｎｄｅｘを格納する記憶手段、Ｌレジスタ、及び第１、第２、第３のレジスタを設け、
（１）中間配列ｉｎｄｅｘの定義域である１からＮまでの値を格納するリストとして配列ｌｉｓｔを前記記憶手段に生成し、
（２）中間配列ｉｎｄｅｘから第一要素（ｌｉｓｔ（１））を取り出し変数ＬとしてＬレジスタに格納し、
（３）配列ｌｉｓｔから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納し、
（４）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致するレジスタ・インデックスを第２のレジスタに格納し、
（５）第２のレジスタに格納されたレジスタ・インデックスに対応する配列Ａの要素を読み出し第３のレジスタに格納し、
（６）第３のレジスタに読み込まれた配列Ａの総和を計算し、当該計算された総和をＦ（ｉｎｄｅｘ（Ｌ））に加え、
（７）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在する場合そのレジスタ・インデックスを配列ｌｉｓｔに格納し、
（８）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在しなくなるまで上記（２）から（７）を繰り返す演算制御手段を備えるベクトル計算機。
【請求項４】
第４、第５及び第６のレジスタを更に備え、
前記演算制御手段は、
配列ｌｉｓｔから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納する際に、配列ｌｉｓｔを第４のレジスタに読込み、その第４のレジスタから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納し、
第３のレジスタに読み込まれた配列Ａの総和を計算し、当該計算された総和をＦ（ｉｎｄｅｘ（Ｌ））に加える際に、計算された総和を第５のレジスタに格納し、且つＦ（ｉｎｄｅｘ（Ｌ））に第５のレジスタの値を加え、
第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在する場合そのレジスタ・インデックスを配列ｌｉｓｔに格納する際に、第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスを第６のレジスタに格納し、且つ第６のレジスタに格納されたレジスタ・インデックスを配列ｌｉｓｔに格納する
請求項３記載のベクトル計算機。
【請求項５】
配列Ｆに対して別の配列Ａの要素を加算するときに、その加算要素の位置を決定する中間配列ｉｎｄｅｘが存在し、
【数３】
0003845710.tif 000007
の式であって、Ｉは１からＮ（ここで、Ｎは２以上の任意の整数）までの範囲を全て昇順に網羅する上記式により表される間接アドレス参照を含む加算をベクトル計算機上で高速処理するためのプログラムにおいて、
前記ベクトル計算機に、
（１）中間配列ｉｎｄｅｘの定義域である１からＮまでの値を格納するリストとして配列ｌｉｓｔを記憶手段に生成する手順と、
（２）前記記憶手段に設けられた中間配列ｉｎｄｅｘから第一要素（ｌｉｓｔ（１））を取り出し変数ＬとしてＬレジスタに格納する手順と、
（３）前記記憶手段に設けられた配列ｌｉｓｔから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納する手順と、
（４）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致するレジスタ・インデックスを第２のレジスタに格納する手順と、
（５）第２のレジスタに格納されたレジスタ・インデックスに対応する配列Ａの要素を第３のレジスタに読み込む手順と、
（６）第３のレジスタに読み込まれた配列Ａの総和を計算し、当該計算された総和を前記記憶手段に設けられたＦ（ｉｎｄｅｘ（Ｌ））に加える手順と、
（７）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在する場合そのレジスタ・インデックスを配列ｌｉｓｔに格納する手順と、
（８）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在しなくなるまで手順（２）から（７）を繰り返す手順と
を実行させるためのプログラム。
【請求項６】
手順（３）は、配列ｌｉｓｔを第４のレジスタに読込む手順と、その第４のレジスタから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納する手順とから成り、
手順（６）は、計算された総和を第５のレジスタに格納する手順と、Ｆ（ｉｎｄｅｘ（Ｌ））に第５のレジスタの値を加える手順とから成り、
手順（７）は、第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスを第６のレジスタに格納する手順と、第６のレジスタに格納されたレジスタ・インデックスを配列ｌｉｓｔに格納する手順とから成る
請求項５記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、科学技術計算において用いられる数値シミュレーションを高速化するものであり、具体的にはベクトル計算機上での間接アドレス参照を含む加算の高速処理方法、プログラム及びそれを用いたベクトル計算機に関する。特に、本発明は、それが対象とする間接アドレス参照による加算を含む問題をベクトル計算機を用いて計算する場合に有効である。対象となる問題は、科学技術計算では極めて広範囲に存在する。
【０００２】
【従来の技術】
最初に従来のベクトル計算機における間接アドレス参照による加算を含む問題について説明する。配列Ｆに対して別の配列Ａの要素を加算するときに、その加算要素の位置を決定する中間配列ｉｎｄｅｘが存在し、次の式の様に加算がなされる場合を想定する。
【０００３】
【数４】
Ｆ（ｉｎｄｅｘ（Ｉ））：＝Ｆ（ｉｎｄｅｘ（Ｉ））＋Ａ（Ｉ）    （１）ここで、Ｉは１からＮ（Ｎは２以上の整数）までの範囲を全て昇順（Ｉ＝１，２，３，…，Ｎ）に網羅する。Ｆの様に中間配列ｉｎｄｅｘを媒介して配列の値を参照することを一般に間接アドレス参照と呼ぶ。
【０００４】
式（１）が登場する代表的な例として、
（１）バケッツソートにおけるヒストグラム計算
（２）粒子問題における粒子の場への寄与計算
（３）積分計算一般
などがあげられる。（２）の例において、ＰＩＣ（Ｐａｒｔｉｃｌｅ−Ｉｎ−Ｃｅｌｌ）法を用いる粒子問題ではこの計算をＣｈａｒｇｅ  Ｄｅｐｏｓｉｔと呼び、粒子相互間の作用を場を経由して計算する際に用いられる。式（１）を回帰式と呼ぶこともあるが、本明細書においてはＰＩＣ法でのＣｈａｒｇｅ  Ｄｅｐｏｓｉｔに由来させてｄｅｐｏｓｉｔ式とも呼ぶ。多粒子系の問題ではｄｅｐｏｓｉｔ式の計算コストが極めて大きく、その高速化が常に望まれている。
【０００５】
強力な計算能力を有するベクトル計算機では、これまでの手法によるベクトル処理では次に説明するようにアドレス衝突の問題が避けられないため、一般的には不可能であった。ただし、間接アドレスのリストの内容に重複がないなどの特殊な条件下のもとでのみ、コンパイラに対して指示を行い強制ベクトル処理をすることができていた。
【０００６】
今、ベクトル計算機上での式（１）の計算をＩに対して１からＮの順に行うとき、ベクトル計算機の計算システム内部にはＫ個単位で同時に計算する演算機構があり、式（１）の計算もＫ個同時に処理される。今、Ｋ＝４でｉｎｄｅｘの値が１，１，２，３であるとすると、まず演算機構が持つ記憶装置（レジスタ）にＦ（ｉｎｄｅｘ（１）），Ｆ（ｉｎｄｅｘ（２）），Ｆ（ｉｎｄｅｘ（３）），Ｆ（ｉｎｄｅｘ（４））が主記憶装置（以下「メモリ」）から読み込まれる。つまり、｛Ｆ（１），Ｆ（１），Ｆ（２），Ｆ（３）｝がレジスタに格納されている。次にＡの値がＫ個同時に加算される、つまり演算の結果、レジスタの値は｛Ｆ（１）＋Ａ（１），Ｆ（１）＋Ａ（２），Ｆ（２）＋Ａ（３），Ｆ（３）＋Ａ（４）｝となる。次に、このレジスタの内容がメモリに戻されるのであるが、それぞれの要素がその並び順にメモリＦ（ｉｎｄｅｘ（１）），Ｆ（ｉｎｄｅｘ（２）），Ｆ（ｉｎｄｅｘ（３）），Ｆ（ｉｎｄｅｘ（４））に記録されるため、ｉｎｄｅｘの値が一致する部分、つまりＦ（１）には最後に記録されたＦ（１）＋Ａ（２）が書き込まれることになる。
【０００７】
本来この式の計算意味上、計算結果は、Ｆ（１）にＦ（１）＋Ａ（１）＋Ａ（２）の値が格納されなくてはならない。従って、ベクトル計算機上での上式の計算は計算結果不正を伴うものであり、計算結果を正しくするための別の計算手法を導入する必要がある。
【０００８】
その１つとして、１次元の加算対象配列に対して、投機的なベクトル処理を行い、加算結果の不正となる項を検出し、再度同様の処理を繰り返す方式、いわゆるＲｅｔｒｙアルゴリズムが提案されている。これは、結果不正のリスクをも含めて、Ｆに対して直接のアドレスを利用して加算ベクトル処理を行い、結果不正項の修正を行うものである。例えば、下記文献を参照されたい。
【０００９】
Ａｂｅ，Ｙ．：Ｐｒｅｓｅｎｔ  Ｓｔａｔｕｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｉｍｕｌａｔｉｏｎ  ａｔ  ＩＰＰ，  Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ  ８８，Ｖｏｌ．ＩＩ，ｐ．７２（１９８８）、及び
村井均、末松謙二、妹尾義樹：共有メモリ型並列計算機上の高速整数ソーティングアルゴリズム、情報処理学会論文誌，Ｖｏｌ．３９，Ｎｏ．６，ｐ．１５９５（１９９８）。
【００１０】
また、プログラムの積極的な変更によりアドレス衝突を避ける方法として、配列Ｆに対して人工的なインデックス拡張を施すＷｏｒｋ  Ｖｅｃｔｏｒアルゴリズム（又は止まり木法）が提案されている（Ｎｉｓｈｉｇｕｃｈｉ，Ａ．，Ｏｒｉｉ，Ｓ．  ａｎｄ  Ｙａｂｅ，Ｔ．：Ｖｅｃｔｏｒ  Ｃａｌｃｕｌａｔｉｏｎｏｆ  Ｐａｒｔｉｃｌｅ  Ｃｏｄｅ，Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔａｉｏｎａｌ  Ｐｈｙｓｉｃｓ，Ｖｏｌ．６１，ｐ．５１９（１９８５）参照）。これは、Ｋ個の作業領域（配列ｗ（１：ｍ，１：Ｋ）を用意し、ベクトル長Ｋにストリップマイニングされた上記式（１）に対してｉｎｄｅｘ（ｉ）の形の単純なアドレス指定を、（ｉｎｄｅｘ（ｉ），ｊ）の様に次元拡張しアドレスの一致を完全に回避する方法である。つまり、２次元作業配列を導入し、アドレスの衝突を完全に回避する手法である。この方法は、ベクトル処理の単位となるベクトル長と拡張次元を一致させる方式であるため、加算不正項は発生しないが十分な性能を得るためには使用する作業配列の大きさが非常に大きくならざるを得なかった。
【００１１】
【発明が解決しようとする課題】
Ｒｅｔｒｙアルゴリズムは、Ｗｏｒｋ  Ｖｅｃｔｏｒアルゴリズム（又は止まり木法）に比べて必要とするメモリ量が少量で、更に間接アドレス参照が疎らなときには性能を発揮することがソーティング問題（上記（１）の例）への適用実験によって示されている（上記村井らの文献参照）。しかしながら、ｉｎｄｅｘの分布がある範囲に集中する際にはスカラ計算よりも遅くなるという欠点を有するため、極めて特異な問題では有効でない。また、結果不正項の出現は、ｉｎｄｅｘの値の重複度に依存しており、重複度が高くなった際に再試行加算の回数が増大し、性能劣化の原因となっていた。
【００１２】
村松、望月らの報告では、分子軌道計算における積分式が式（１）の形をしている場合、回避できない頻度で起こるｉｎｄｅｘ値（キー）の衝突のためＲｅｔｒｙアルゴリズムが有効でないことが示されている。また、Ｗｏｒｋ  Ｖｅｃｔｏｒアルゴリズムは有効な手法であるが、メモリ使用率が現実的な大規模問題への適用の障壁となることも併せて報告されている。詳細には、村松昌幸、望月祐志、与倉徹一、平原幸男、今村俊幸：相対論的分子軌道コードＤＩＲＡＣにおけるＤＨＦ計算のベクトル化，情処研報，Ｖｏｌ．２００１，Ｎｏ．４９，ｐ．４３（２００１）を参照されたい。
【００１３】
まとめると、上記の従来の計算手法では、間接アドレス指定の要素が非常に密集している場合に、ベクトル演算機構による加算の実行回数が増大する問題を有し、また、効率的に処理を行う場合に、作業領域が増大する問題を有していた。
【００１４】
本発明の課題は、ベクトル計算機上での間接アドレス参照を含む加算における計算誤りを回避し且つ加算を高速に行うことにある。
【００１５】
【課題を解決するための手段】
上記課題は、配列Ｆに対して別の配列Ａの要素を加算するときに、その加算要素の位置を決定する中間配列ｉｎｄｅｘが存在し、
【００１６】
【数５】
Ｆ（ｉｎｄｅｘ（Ｉ））：＝Ｆ（ｉｎｄｅｘ（Ｉ））＋Ａ（Ｉ）
の式であって、Ｉは１からＮ（ここで、Ｎは２以上の任意の整数）までの範囲を全て昇順に網羅する上記式により表される間接アドレス参照を含む加算をベクトル計算機上で高速処理する方法において、
配列Ｆ、Ａ及びｉｎｄｅｘが記憶手段に設けられており、
（１）中間配列ｉｎｄｅｘの定義域である１からＮまでの値を格納するリストとして配列ｌｉｓｔを前記記憶手段に設けるステップと、
（２）中間配列ｉｎｄｅｘから第一要素（ｌｉｓｔ（１））を取り出し変数ＬとしてＬレジスタに格納するステップと、
（３）配列ｌｉｓｔから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納するステップと、
（４）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致するレジスタ・インデックスを第２のレジスタに格納するステップと、
（５）第２のレジスタに格納されたレジスタ・インデックスに対応する配列Ａの要素を第３のレジスタに読み込むステップと、
（６）第３のレジスタに読み込まれた配列Ａの総和を計算し、当該計算された総和をＦ（ｉｎｄｅｘ（Ｌ））に加えるステップと、
（７）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在する場合そのレジスタ・インデックスを配列ｌｉｓｔに格納するステップと、
（８）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在しなくなるまでステップ（２）から（７）を繰り返すステップと
を備える本発明の方法及びベクトル計算機により実行されるプログラムにより解決される。
【００１７】
本発明の一局面においては、ステップ又は手順（３）は、配列ｌｉｓｔを第４のレジスタに読込むステップ又は手順と、その第４のレジスタから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納するステップ又は手順とから成り、
ステップ又は手順（６）は、計算された総和を第５のレジスタに格納するステップ又は手順と、Ｆ（ｉｎｄｅｘ（Ｌ））に第５のレジスタの値を加えるステップ又は手順とから成り、
ステップ又は手順（７）は、第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスを第６のレジスタに格納するステップ又は手順と、第６のレジスタに格納されたレジスタ・インデックスを配列ｌｉｓｔに格納するステップ又は手順とから成ることが好ましい。
【００１８】
上記課題はまた、配列Ｆに対して別の配列Ａの要素を加算するときに、その加算要素の位置を決定する中間配列ｉｎｄｅｘが存在し、
【００１９】
【数６】
Ｆ（ｉｎｄｅｘ（Ｉ））：＝Ｆ（ｉｎｄｅｘ（Ｉ））＋Ａ（Ｉ）
の式であって、Ｉは１からＮ（ここで、Ｎは２以上の任意の整数）までの範囲を全て昇順に網羅する上記式により表される間接アドレス参照を含む加算を高速処理するベクトル計算機において、
配列Ｆ、Ａ及びｉｎｄｅｘを格納する記憶手段、Ｌレジスタ、及び第１、第２、第３のレジスタを設け、
（１）中間配列ｉｎｄｅｘの定義域である１からＮまでの値を格納するリストとして配列ｌｉｓｔを前記記憶手段に生成し、
（２）中間配列ｉｎｄｅｘから第一要素（ｌｉｓｔ（１））を取り出し変数ＬとしてＬレジスタに格納し、
（３）配列ｌｉｓｔから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納し、
（４）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致するレジスタ・インデックスを第２のレジスタに格納し、
（５）第２のレジスタに格納されたレジスタ・インデックスに対応する配列Ａの要素を読み出し第３のレジスタに格納し、
（６）第３のレジスタに読み込まれた配列Ａの総和を計算し、当該計算された総和をＦ（ｉｎｄｅｘ（Ｌ））に加え、
（７）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在する場合そのレジスタ・インデックスを配列ｌｉｓｔに格納し、
（８）第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在しなくなるまで上記（２）から（７）を繰り返す演算制御手段を備える本発明のベクトル計算機により解決される。
【００２０】
本発明の別の局面においては、第４、第５及び第６のレジスタを更に備え、
前記演算制御手段は、
配列ｌｉｓｔから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納する際に、配列ｌｉｓｔを第４のレジスタに読込み、その第４のレジスタから間接に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値を第１のレジスタに格納し、
第３のレジスタに読み込まれた配列Ａの総和を計算し、当該計算された総和をＦ（ｉｎｄｅｘ（Ｌ））に加える際に、計算された総和を第５のレジスタに格納し、且つＦ（ｉｎｄｅｘ（Ｌ））に第５のレジスタの値を加え、
第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスが存在する場合そのレジスタ・インデックスを配列ｌｉｓｔに格納する際に、第１のレジスタの値とｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスを第６のレジスタに格納し、且つ第６のレジスタに格納されたレジスタ・インデックスを配列ｌｉｓｔに格納することが好ましい。
【００２１】
本発明は、上記のような構成により、密集していると考えられる候補を選択し、加算結果対象をベクトルの形でなくスカラにすることにより、実行回数を減少させるとともに作業領域も減少させる。
【００２２】
【発明の実施の形態】
初めに、従来の技術の欄におけるｄｅｐｏｓｉｔ式（１）が、表１に示されるプログラムで記述されるものとする。
【００２３】
【表１】
0003845710.tif 000002
【００２４】
ここで、ｎは加算要素（配列ａ）の総数、ｍはｆの定義域の上限であり、中間配列ｉｎｄｅｘの値域も［１：ｍ］に一致していると仮定する（ｎ，ｍ≧１）。また、中間配列ｉｎｄｅｘの値をキーと呼び、本明細書中ではこのキーが取り得る値の総数をｉｎｄｅｘの分布と呼び、またその総数を記号ｌ（アルファベットＬの小文字）で表す。ｌはｉｎｄｅｘ値の重複の平均値を意味しており、密度の逆数（ｍ／ｄｅｎｓｉｔｙ）に対応すると考えてよく、即ちインデックスの重複度合いと考えることができる。ベクトル処理をする際の、ハードウエア・ベクトル・レジスタ長は、ＮVと記述すると共に、プログラム中にベクトルを表現するために表記「／／」を使用する。特に、ｎからｍまでの要素を持つベクトルを／ｎ：ｍ／で表す。更に、ｄｅｐｏｓｉｔ式（１）の計算性能として、ｎをプログラム実行時間で割った値、つまり単位時間（秒）当たり加算可能な要素数を用い、ＥＰＳ（Ｅｌｅｍｅｎｔｓ  Ｐｅｒ  Ｓｅｃｏｎｄ）と表記する。
【００２５】
次に、従来の技術の欄におけるｄｅｐｏｓｉｔ式（１）の本発明による処理概念を説明する。従来のＲｅｔｒｙアルゴリズムでは、従来の技術の欄で述べたように、加算が配列と配列を対象としていたために、加算対象であるベクトルレジスタの内部要素に対応するアドレスが重複した場合にその不整合が起こっていた。一方、加算対象が一致していることが明白な場合、ｄｅｐｏｓｉｔ式（１）を次のように解釈できる。
【００２６】
【数７】
0003845710.tif 000003
この式（２）はスカラの加算であり、ベクトル化が可能である。
【００２７】
しかしながら、通常全てのｉｎｄｅｘ値が一致するわけでない。そこで、Ｒｅｔｒｙアルゴリズム同様、投機的に式（２）の計算を行い、且つ計算に該当しない要素を検出し再帰的に繰り返し計算する機構を組み上げることができればアルゴリズムとして完結させることができる。
【００２８】
今、中間配列ｉｎｄｅｘの適当な要素を取り出し、ｉｆ文により値が一致するもののみ式（２）を実施し、そうでないものでリストｌｉｓｔを構築する。リストｌｉｓｔの中から再度適当な要素を取りだし、同様の処理を実施していく。リストの内容がなくなるまで繰り返すことでアルゴリズムが完結する。以上の処理内容をまとめたものを表２に示す。ｉｆ文によるマスクが本アルゴリズムのコアを構成することにより、本アルゴリズムをＭａｓｋｉｎｇ（マスキング）アルゴリズムと呼ぶ。
【００２９】
【表２】
0003845710.tif 000004
【００３０】
図１は、Ｍａｓｋｉｎｇアルゴリズムの動作概念を示したものである。中間配列ｉｎｄｅｘ（図１に図示せず）とｉベクトル・レジスタ（図１に示されるように値が１，２，３，４と昇順に格納されている。なお、後述の事例のレジスタ１に対応）とを比較して一致・不一致を判定し、その結果がｉｎｄｅｘ（）マスク・ベクトル（後述の事例のレジスタ３に対応）により示されている。ｉｎｄｅｘ（）マスク・ベクトルでは、○は一致を、×は不一致を示す。配列Ａの要素のうちｉｎｄｅｘ（）マスク・ベクトルの○（一致）に対応するもののみがベクトル・レジスタ（後述の事例のレジスタ４に対応）に通される。ベクトル・レジスタに通された配列Ａの要素は、スカラ・レジスタ（後述の事例のレジスタ０に対応）で加算され、配列Ｆの対応する位置に格納される。一方、ｉｎｄｅｘ（）マスク・ベクトルに示された×（不一致）に対応するｉベクトル・レジスタの要素（図１では「４」）は、リストｌｉｓｔ（）に格納される。このリストｌｉｓｔ（）に格納されるものがなくなるまでこのような動作を繰り返すことにより、正しい処理がなされる。
【００３１】
本発明のＭａｓｋｉｎｇアルゴリズムは、Ｒｅｔｒｙアルゴリズムとは異なり、選択したｉｎｄｅｘと一致するものが計算対象となるため、ｉｎｄｅｘの分布数（ｌ）に計算時間が依存することが判る。ｌ＝１が最も性能が良く、ｌが増大するにつれて性能が劣化することになる。つまり、Ｒｅｔｒｙアルゴリズムで性能が出ない領域で威力を発揮するアルゴリズムである。
【００３２】
本発明の処理動作について、配列Ｆ及びＡ、及び中間配列ｉｎｄｅｘがメモリに格納されているとして説明する。
０）まず、中間配列ｉｎｄｅｘの定義域である１からＮまでの値を格納するリストとして新たに配列ｌｉｓｔを導入する。
【００３３】
１）中間配列ｉｎｄｅｘから第一要素（ｌｉｓｔ（１））を取り出し変数Ｌに代入する。
２）配列ｌｉｓｔをレジスタ１に読み込み、そのレジスタ１から間接的に決定される中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の値をレジスタ２に格納する。レジスタ２の値とｉｎｄｅｘ（Ｌ）に一致するレジスタ・インデックスをレジスタ３に格納し、そのインデックスに対応する配列Ａの要素をレジスタ４に格納する。
【００３４】
３）レジスタ４に読み込まれた配列Ａの総和を計算し、大きさが１即ちベクトル長が１のレジスタ０に格納する。
４）Ｆ（ｉｎｄｅｘ（Ｌ））にレジスタ０の値を加える。
【００３５】
５）レジスタ２と値ｉｎｄｅｘ（Ｌ）に一致しないレジスタ・インデックスをレジスタ５に格納する。そして、レジスタ５に格納されたレジスタ・インデックスを最終的に配列ｌｉｓｔに格納するのが好ましい。
【００３６】
６）配列ｌｉｓｔに格納されたデータが０でなければ、即ち配列ｌｉｓｔが「空（から）」でなければ項番１）に戻り、他方０であれば、即ち配列ｌｉｓｔが「空（から）」であれば終了する。この結果、配列Ｆには、もともとの間接アドレスを含んだ加算としての正しい結果が格納される。
【００３７】
なお、上記１）から６）の処理は、ベクトル計算機に含まれる演算制御装置により行われる。
次に、本発明の理解を容易にするため、図２から図１２を参照して具体的数値を用いて説明するが、この説明は単なる例示であって本発明を限定するものではない。なお、図２から図１２に示される処理はベクトル計算機の演算制御装置（図示せず）により実行される。
【００３８】
図２の（０）に示されるように、配列Ｆ及びＡ、及び中間配列ｉｎｄｅｘがメモリに設けられていて、配列Ｆの要素数ｍが４であり、配列Ａ及び中間配列ｉｎｄｅｘの要素数ｎが４であり、初期状態として各配列の要素に図示のような数値が格納されているとする。最初に、中間配列ｉｎｄｅｘの定義域である１から４までの値を格納するリストとして、図２の（０）に示されるようにｌｉｓｔ（）がメモリに形成される。
【００３９】
次いで、図２の（１）に示されるように、中間配列ｉｎｄｅｘ（ｌｉｓｔ（１））の変数Ｌへの読み込みが行われる。即ち、ここではｉｎｄｅｘ（１）の要素「１」が読み出されて、予め設けられているＬレジスタに格納される。
【００４０】
図３の（２）−１に示されるように、配列ｌｉｓｔ（）のレジスタ１への読込みが行われる。即ち、配列ｌｉｓｔ（）の各要素がその並び順に、予め設けられている可変長のレジスタ１に読み出される。
【００４１】
次いで、図３の（２）−２に示されるように、ｉｎｄｅｘ（ｌｉｓｔ（））の間接アドレス読み込みが行われる。レジスタ１に格納されている値に対応する位置のｉｎｄｅｘ（）の要素が読み出され、予め設けられている可変長のレジスタ２に位置的に対応して格納される。
【００４２】
図４の（２）−３に示されるように、変数Ｌに一致する中間配列ｉｎｄｅｘ（ｌｉｓｔ（））の検出が行われる。即ち、レジスタ２に格納されている各値とＬレジスタに格納されている「１」とが比較され、一致・不一致が判定され、その結果がその結果に対応する位置のレジスタ１の格納値と関連付けて、予め設けられている可変長のレジスタ３に格納される。図４の（２）−３の例では、レジスタ１の位置１から３に格納されている１から３が「一致」を表す○と関連付けられて、またレジスタ１の位置４に格納されている４が「不一致」を表す×と関連付けられてレジスタ３に格納されている。なお、一致を「１」、不一致を「０」として、あるいはその逆でレジスタ３に格納してもよく、要はベクトル計算機の演算制御装置（図示せず）が上記の関連が判断できればいずれの形式であってもよい。以下、本明細書において○及び×で表す比較結果のレジスタ等への格納形態についても同様である。
【００４３】
次いで、図４の（２）−４に示されるように、配列ａ（）のレジスタ４への読み込みが行われる。即ち、レジスタ３により一致として示されたレジスタ２の位置に対応する位置の配列ａ（）の要素が、予め設けられている可変長のレジスタ４に読み出される。この例では、配列ａ（）の位置１から３までの要素が図示のようにレジスタ４に読み出される。
【００４４】
図５の（３）に示されるように、レジスタ４に格納された値の総和が計算され、レジスタ０に格納される。
次いで、図５の（４）に示されるように、加算結果のｆ（Ｌ）への書き込みが行われる。即ち、ｆ（１）に格納されている「２」とレジスタ０に格納されている「９」が加算され、図示のようにｆ（１）に「１１」が格納される。
【００４５】
図６の（５）に示されるように、未加算項の検出と変数ｌｉｓｔ（）への格納が行われる。即ち、レジスタ３において不一致（×）と示されたレジスタ２の位置を示す値、この例では「４」が検出され、予め設けられている可変長のレジスタ５に格納される。なお、検出された値が複数あるときは、レジスタ３において示される位置の順番どおりレジスタ５に全て格納される。また、レジスタ５に格納された値は、その並び順でｌｉｓｔ（）の位置１から格納されることが好ましい。
【００４６】
次いで、ステップ（１）からｌｉｓｔが生成されなくなるまで再試行を繰り返す。以下、ステップ（１）から（５）までと類似の再試行については、ＩＩを各ステップの先頭に付して説明する。
【００４７】
図７に示されるように、ステップＩＩ−（１）において、図２のステップ（１）と同様にして、ｌｉｓｔ（１）の要素「４」に対応するｉｎｄｅｘ（４）の要素「２」がＬレジスタに読み込まれる。
【００４８】
次いで、図８のＩＩ−（２）−１に示されるように、配列ｌｉｓｔ（）がレジスタ１に読み込まれる。この例では、図３のステップ（２）−１と同様にして、ｌｉｓｔ（１）の要素「４」がレジスタ１に読み込まれ、従ってレジスタ１のベクトル長は１となる。
【００４９】
図８のＩＩ−（２）−２において、図３のステップ（２）−２と同様にして、レジスタ１に格納されている要素に対応する位置のｉｎｄｅｘ（）の要素がレジスタ１の位置に対応するレジスタ２の位置に格納される。この例では、レジスタ１の位置１の「４」に対応するｉｎｄｅｘ（４）の要素「２」がレジスタ２の位置１に格納される。なお、レジスタ１に格納されている値が１つあるので、レジスタ２のベクトル長は１となる。
【００５０】
次いで、図９のＩＩ−（２）−３に示されるように、図４のステップ（２）−３と同様にして、レジスタ２に格納された値とＬレジスタに格納された値とが比較され、一致・不一致が判定される。この例では、一致していて、その一致に対応する位置のレジスタ１の格納値「４」と一致の○が関連付けられてレジスタ３に格納される。比較対象数が１つであるので、レジスタ３のベクトル長は１となる。
【００５１】
図９のＩＩ−（２）−４において、図４のステップ（２）−４と同様にして、レジスタ３に、一致に対応して格納された値、ここでは「４」に対応するａ（４）の要素がレジスタ４に読み込まれる。なお、レジスタ３に、一致に対応して格納された値が複数ある場合は、値の全てについてａ（４）の要素がレジスタ４に読み込まれる。
【００５２】
次いで、図１０のＩＩ−（３）において、図５のステップ（３）と同様にして、レジスタ４に格納された全ての値（ここでは「７」のみ）の総和が計算され、レジスタ０に（ここでは、「７」が）格納される。
【００５３】
次いで、図１０のＩＩ−（４）において、図５のステップ（４）と同様にして、Ｌ＝２であることから、ｆ（２）に格納されている「５」とレジスタ０に格納されている「７」が加算され、図示のようにｆ（２）に「１２」が格納される。
【００５４】
図１１のＩＩ−（５）において、図６のステップ（５）と同様にして、未加算項の検出と変数ｌｉｓｔ（）への格納が行われる。即ち、図９のＩＩ−（２）−３で不一致が発生していないので、未加算項はなく、レジスタ５及びｌｉｓｔ（）は「空（から）」のままであり、即ち、ｌｉｓｔが生成されないことになり、再試行は終了する。
【００５５】
従って、図１２に示されるように、配列ｆ（）の正しい計算結果が得られる。なお、ｆ（３）及びｆ（４）については、加算される対象がないので初期状態における値のままである。
【００５６】
本発明を用いた場合の性能測定結果を以下に示す。測定時の条件として、配列Ｆのサイズを２14（＝１６，３８４）、加算要素数を２21（＝２，０９７，１５２）とした。ｉｎｄｅｘの分布（ｌ）を２のべき乗で変化させたときの、ＥＰＳ値（１秒当たりの加算可能要素数）をプロットした結果を図１３から図１５に示す。中間配列ｉｎｄｅｘの値は、ＮＰＢ（ＮＡＳ  Ｐａｒａｌｌｅｌ  Ｂｅｎｃｈｍａｒｋ）（Ｂａｉｌｅｙ，Ｄ．，Ｈａｒｒｉｓ，Ｔ．，Ｓａｐｈｉｒ，Ｗ．，Ｗｉｊｎｇａａｒｔ，Ｒ．，Ｗｏｏ，Ａ．，  ａｎｄ  Ｙａｒｒｏｗ，Ｍ．：ＮＡＳ  Ｐａｒａｌｌｅｌ  Ｂｅｎｃｈｍａｒｋｓ  ２．０，Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＮＡＳ−９５−０２０，（１９９５）参照）に含まれる問題ＩＳの疑似乱数生成ルーチンを用いて生成している。ＩＳ同様、連続する４個の一様乱数数列の平均をｉｎｄｅｘの値とした。なお、加算要素ａ（：）の値が性能を左右しないようにするためこの実験では簡単化して全て１としている。この設定により、この実験は、問題ＩＳと本質的に同一ヒストグラム計算を行うのと同等といえる。
【００５７】
それぞれのグラフには、Ｋ＝１６のＷｏｒｋ  Ｖｅｃｔｏｒアルゴリズム、Ｋ＝６４のＷｏｒｋ  Ｖｅｃｔｏｒアルゴリズム、Ｒｅｔｒｙアルゴリズム、本発明のＭａｓｋｉｎｇアルゴリズムの結果を示してある。ここで、各曲線の見出し部分の（）内に示した値がＫの値である。なお、Ｋ＝１６は、一般的な大規模アプリケーションで取得可能な作業配列の上限であり、Ｋ＝６４は、通常要求される性能を発揮する作業域の例である。
【００５８】
図１３は、ベクトル計算機ＳＸ−４（日本電気社製）での実験結果を示している。ＳＸ−４は比較的短いベクトル・レジスタ（ＮV＝２５６）を搭載するベクトル計算機である。間接アドレス方式のロード−ストアも高速の部類に入る。
【００５９】
図１４は、ベクトル計算機ＶＰＰ３００（富士通社製）での実験結果を示している。ＶＰＰ３００は、長ベクトル・レジスタ（ＮV＝２０４８）を搭載するベクトル計算機である。ただし、今回使用したマシンの内では間接アドレス方式のロード−ストアが遅い。
【００６０】
図１５は、ベクトル計算機ＶＰＰ５０００（富士通社製）での実験結果を示している。対象機は、長ベクトル・レジスタを搭載し、且つ間接アドレス方式のロード−ストアが高速なベクトル計算機である。
【００６１】
図１３、図１４及び図１５ではそれぞれキー・インデックスの数「ｌ」、即ちインデックスの重複度合いが約１０以下、約１０以下、及び約２０以下で、本発明のＭａｓｋｉｎｇアルゴリズムは、従来のＷｏｒｋ  Ｖｅｃｔｏｒアルゴリズム及びＲｅｔｒｙアルゴリズムより高い性能を示している。
【００６２】
【発明の効果】
本発明は以上説明したように構成されているので、間接アドレス指定の要素が非常に密集している場合に、加算回数を削減できるため、結果的に全体の処理時間を短縮化することができ、従って高速化することができる。また、作業領域を必要としないため大規模な問題に適用できる。
【００６３】
本発明では、ｉｎｄｅｘ値が重複することを想定して、重複候補をリストの先頭から選択しながら処理を進めるため、従来手法とは異なり、ｉｎｄｅｘ値の重複度が高くなるほど計算処理における全体の反復回数が減少し、結果的に処理性能が向上する。
【図面の簡単な説明】
【図１】図１は、本発明のＭａｓｋｉｎｇアルゴリズムの動作概念を示したものである。
【図２】図２は、本発明による処理を説明するための処理フロー例の部分である。
【図３】図３は、本発明による処理を説明するための処理フロー例の部分である。
【図４】図４は、本発明による処理を説明するための処理フロー例の部分である。
【図５】図５は、本発明による処理を説明するための処理フロー例の部分である。
【図６】図６は、本発明による処理を説明するための処理フロー例の部分である。
【図７】図７は、本発明による処理を説明するための処理フロー例の部分である。
【図８】図８は、本発明による処理を説明するための処理フロー例の部分である。
【図９】図９は、本発明による処理を説明するための処理フロー例の部分である。
【図１０】図１０は、本発明による処理を説明するための処理フロー例の部分である。
【図１１】図１１は、本発明による処理を説明するための処理フロー例の部分である。
【図１２】図１２は、本発明による処理を説明するための処理フロー例の部分である。
【図１３】図１３は、本発明を用いた場合の性能測定結果の一例を示す図である。
【図１４】図１４は、本発明を用いた場合の性能測定結果の一例を示す図である。
【図１５】図１５は、本発明を用いた場合の性能測定結果の一例を示す図である。
【図１】
0003845710.tif 000008
【図２】
0003845710.tif 000009
【図３】
0003845710.tif 000010
【図４】
0003845710.tif 000011
【図５】
0003845710.tif 000012
【図６】
0003845710.tif 000013
【図７】
0003845710.tif 000014
【図８】
0003845710.tif 000015
【図９】
0003845710.tif 000016
【図１０】
0003845710.tif 000017
【図１１】
0003845710.tif 000018
【図１２】
0003845710.tif 000019
【図１３】
0003845710.tif 000020
【図１４】
0003845710.tif 000021
【図１５】
0003845710.tif 000022