(57)【特許請求の範囲】
【請求項１】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行する計算機において、
インデックスの基数に対する剰余を求めて、インデックスと該剰余の規定する数値との対応関係を管理する第１の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第２の作業配列を作成する作成手段と、
上記算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、上記作成手段の作成する上記第１及び第２の作業配列の配列データに基づいてメモリバンクにアクセスすることで上記算出式を計算する計算手段とを備えることを、
特徴とする計算機。
【請求項２】
請求項１記載の計算機において、
上記作成手段は、メモリバンク数を基数として用いるか、メモリバンク数よりも小さな２の巾乗の値を基数として用いることを、
特徴とする計算機。
【請求項３】
請求項１又は２記載の計算機において、
上記作成手段は、論理演算に従って、インデックスの基数に対する剰余を求めることを、
特徴とする計算機。
【請求項４】
請求項１〜３のいずれかに記載の計算機において、
上記計算手段は、上記作成手段の作成する上記第１及び第２の作業配列の持つ空白部分を飛ばしつつ計算処理を実行することを、
特徴とする計算機。
【請求項５】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行する計算機において、
インデックスとインデックスの出現回数との対応関係を管理する第１の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第２の作業配列を作成する作成手段と、
上記算出式の演算を、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、スカラー演算を用いる形式で再構成して、上記作成手段の作成する上記第１及び第２の作業配列の配列データに基づいて該スカラー演算を繰り返すことで上記算出式を計算する計算手段とを備えることを、
特徴とする計算機。
【請求項６】
請求項５記載の計算機において、
上記作成手段は、ソーティング手法を用いて、インデックスとインデックスの出現回数との対応関係を管理する上記第１の作業配列を作成することを、
特徴とする計算機。
【請求項７】
請求項１〜６のいずれかに記載の計算機において、
上記作成手段は、上記算出式が反復計算されるときにあって、リストに変更がない場合には、既作成の上記第１及び第２の作業配列を有効なものと扱って該作業配列を作成しないように処理することを、
特徴とする計算機。
【請求項８】
請求項１〜７のいずれかに記載の計算機において、
上記作成手段は、上記第１及び第２の作業配列の作成に先立って、該作業配列の大きさを求めて、それに応じて該作業配列の領域を確保することを、
特徴とする計算機。
【請求項９】
請求項１〜８のいずれかに記載の計算機において、
計算機が複数のプロセッサで構成されるときに、上記作成手段の作成する上記第１及び第２の作業配列が各プロセッサに分割されて配分されるように構成されることを、
特徴とする計算機。
【請求項１０】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行する計算機において、
インデックスとインデックスの出現回数との対応関係を管理する第１の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第２の作業配列を作成する第１の作成手段と、
インデックスの基数に対する剰余を求めて、インデックスと該剰余の規定する数値との対応関係を管理する第３の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第４の作業配列を作成する第２の作成手段と、
上記第１の作成手段の作成する上記第１及び第２の作業配列に対応付けて設けられて、上記算出式の演算を、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、スカラー演算を用いる形式で再構成して、該作業配列の配列データに基づいて該スカラー演算を繰り返すことで上記算出式を計算する第１の計算手段と、
上記第２の作成手段の作成する上記第３及び第４の作業配列に対応付けて設けられて、上記算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、該作業配列の配列データに基づいてメモリバンクにアクセスすることで上記算出式を計算する第２の計算手段と、
上記第１の作成手段の作成する上記第１の作業配列の配列データに従って、上記第１の計算手段か上記第２の計算手段のいずれか一方を選択して起動する起動手段とを備えることを、
特徴とする計算機。
【請求項１１】
請求項１０記載の計算機において、
上記第２の作成手段は、上記第２の計算手段が上記起動手段により起動される条件が成立するときに、上記第３及び第４の作業配列を作成するように処理することを、
特徴とする計算機。
【請求項１２】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行する計算機において、
出現回数の多いインデックスを管理対象として、インデックスとインデックスの出現回数との対応関係を管理する第１の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第２の作業配列を作成する第１の作成手段と、
上記第１の作成手段の作成する上記第１及び第２の作業配列に管理されるインデックス以外のインデックスを管理対象として、インデックスの基数に対する剰余を求めて、インデックスと該剰余の規定する数値との対応関係を管理する第３の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第４の作業配列を作成する第２の作成手段と、
上記第１の作成手段の作成する上記第１及び第２の作業配列に管理されるインデックスを処理対象として、上記算出式の演算を、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、スカラー演算を用いる形式で再構成して、該作業配列の配列データに基づいて該スカラー演算を繰り返すことで上記算出式を計算する第１の計算手段と、
上記第２の作成手段の作成する上記第３及び第４の作業配列に管理されるインデックスを処理対象として、上記算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、該作業配列の配列データに基づいてメモリバンクにアクセスすることで上記算出式を計算する第２の計算手段とを備えることを、
特徴とする計算機。
【請求項１３】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するプログラムをコンパイル又は変換するプログラム変換装置であって、
インデックスの基数に対する剰余を求めて、インデックスと該剰余の規定する数値との対応関係を管理する第１の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第２の作業配列を作成する処理を行うプログラムを生成する第１の生成手段と、
上記算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、上記作成手段の作成する上記第１及び第２の作業配列の配列データに基づいてメモリバンクにアクセスすることで上記算出式を計算する処理を行うプログラムを生成する第２の生成手段とを備えることを、
特徴とするプログラム変換装置。
【請求項１４】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するプログラムをコンパイル又は変換するプログラム変換装置であって、
インデックスとインデックスの出現回数との対応関係を管理する第１の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第２の作業配列を作成する処理を行うプログラムを生成する第１の生成手段と、
上記算出式の演算を、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、スカラー演算を用いる形式で再構成して、上記作成手段の作成する上記第１及び第２の作業配列の配列データに基づいて該スカラー演算を繰り返すことで上記算出式を計算する処理を行うプログラムを生成する第２の生成手段とを備えることを、
特徴とするプログラム変換装置。
【請求項１５】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行する計算機の実現に用いられるプログラムが格納されるプログラム記録媒体であって、
インデックスの基数に対する剰余を求めて、インデックスと該剰余の規定する数値との対応関係を管理する第１の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第２の作業配列を作成する作成処理と、
上記算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、上記作成処理の作成する上記第１及び第２の作業配列の配列データに基づいてメモリバンクにアクセスすることで上記算出式を計算する計算処理とをコンピュータに実行させるプログラムが格納されることを、
特徴とするプログラム記録媒体。
【請求項１６】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行する計算機の実現に用いられるプログラムが格納されるプログラム記録媒体であって、
インデックスとインデックスの出現回数との対応関係を管理する第１の作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する第２の作業配列を作成する作成処理と、
上記算出式の演算を、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、スカラー演算を用いる形式で再構成して、上記作成処理の作成する上記第１及び第２の作業配列の配列データに基づいて該スカラー演算を繰り返すことで上記算出式を計算する計算処理とをコンピュータに実行させるプログラムが格納されることを、
特徴とするプログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、リストに配列されるインデックスの指すメモリバンクにアクセスすることで規定の算出式の計算処理を実行する計算機と、その計算処理を行うプログラムを生成するプログラム変換装置と、その計算機の実現に用いられるプログラムが格納されるプログラム記録媒体とに関し、特に、算出式の計算処理を高速に実行できるようにする計算機と、その計算処理を行うプログラムを生成するプログラム変換装置と、その計算機の実現に用いられるプログラムが格納されるプログラム記録媒体とに関する。
【０００２】
科学技術計算では反復計算が多く現れる。ここでは、リスト参照によるメモリアクセスがネックとなり、十分な性能を発揮できない場合が多い。これは、一度アクセスされたメモリバンクは規定時間の間ビジー状態となることで、このバンク内のデータに対してアクセスできない状態となるからである。また、反復計算中に同一リストが再現する計算（回帰参照）では、ベクトル処理ができないために、ベクトル計算機での処理性能を大きく低下させることになる。これから、これらの問題点の解決を図る技術の構築が叫ばれている。
【０００３】
【従来の技術】
リストに配列されるインデックスの指すメモリバンクにアクセスすることで規定の算出式の計算処理を実行することが行われている。
【０００４】
この場合、従来では、リストの指定に従って、そのままメモリバンクにアクセスすることで算出式の計算処理を実行するという構成を採っている。
すなわち、例えば、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という算出式に対して、図３５（ａ）に示すようなインデックス「ｉｎｄｅｘ(j）」の配列順序を持つリストが与えられる場合にあって、メモリバンク数が８であるときには、計算順序「ｊ」の指すメモリバンクとともに、図３５（ｂ）に示すようなインデックス「ｉｎｄｅｘ(j）」の指すメモリバンクを使用する。そして、リストの指定に従って、図３６に示すような計算順序により、これらのメモリバンクを用いて算出式の計算処理を実行するという構成を採っている。
【０００５】
なお、計算順序「ｊ」やインデックス「ｉｎｄｅｘ(j）」の指すメモリバンクは、それらの値のメモリバンク数に対する剰余で定義されている。
また、図３７に示すようなメモリバンク数に収まるインデックス「ｉｎｄｅｘ(j）」の配列順序を持つリストが与えられる場合には、計算順序「ｊ」の指すメモリバンクと、「ｉｎｄｅｘ(j）」の指すメモリバンクとを使用して、図３８に示すような計算順序により算出式の計算処理を実行するという構成を採っている。
【０００６】
【発明が解決しようとする課題】
しかしながら、このような従来技術に従っていると、リストに配列されるインデックスの指すメモリバンクにアクセスすることで規定の算出式の計算処理を実行するときに、メモリビジーによるアイドル時間が発生することで、計算処理を高速に実行できないという問題点がある。
【０００７】
すなわち、一度アクセスされたメモリバンクは規定時間の間ビジー状態となるので、同一のメモリバンクへのアクセスが続く場合には、メモリビジーによるアイドル時間が発生することで、その計算処理を高速に実行できないという問題点がある。
【０００８】
上述の具体例において、メモリバス数として４（メモリバンク１,5にメモリバス１、メモリバンク２,6にメモリバス２、メモリバンク３,7にメモリバス３、メモリバンク４,8にメモリバス４を割り付ける）を想定し、一度アクセスされたメモリバンクは２クロックの間ビジー状態になることを想定すると、図３６の算出式の計算処理は具体的には図３９に示すような演算形態で実行され、図３８の算出式の計算処理は具体的には図４０に示すような演算形態で実行され、その演算密度が非常に低いことが分かる。
【０００９】
本発明はかかる事情に鑑みてなされたものであって、リストに配列されるインデックスの指すメモリバンクにアクセスすることで規定の算出式の計算処理を実行するときにあって、算出式の計算処理を高速に実行できるようにする新たな計算機の提供と、その計算処理を行うプログラムを生成する新たなプログラム変換装置の提供と、その計算機の実現に用いられるプログラムが格納される新たなプログラム記録媒体の提供とを目的とする。
【００１０】
【課題を解決するための手段】
図１及び図２に本発明の原理構成を図示する。
図中、１は本発明を具備する計算機であって、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するもの、２は本発明を具備するプログラム変換装置であって、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するプログラムをコンパイル又は変換して計算機１に展開するものである。
【００１１】
ここで、本発明の計算機１や本発明のプログラム変換装置２の持つ機能は具体的にはプログラムで実現されるものであり、このプログラムはメモリ上で動作することで、本発明を実現することになる。
【００１２】
図１（ａ）に原理構成を図示する計算機１は、作成手段１０ａと、計算手段１１ａとを備え、プログラム変換装置２は、第１の生成手段２０ａと、第２の生成手段２１ａとを備える。
【００１３】
この作成手段１０ａは、インデックスの基数に対する剰余を求めて、インデックスとその剰余の規定する数値との対応関係を管理する作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する作業配列を作成する。
【００１４】
計算手段１１ａは、計算対象となる算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、作成手段１０ａの作成する作業配列の配列データに基づいてメモリバンクにアクセスすることで、その算出式を計算する。
【００１５】
第１の生成手段２０ａは、作成手段１０ａを実現するプログラムを生成して、計算機１に展開する。
第２の生成手段２１ａは、計算対象となる算出式に応じて計算手段１１ａを実現するプログラムを生成して、計算機１に展開する。
【００１６】
このように構成される図１（ａ）に原理構成を図示する計算機１では、基数としてメモリバンク数を用いる例で説明するならば、作成手段１０ａは、図３５（ａ）に示したリストが与えられると、インデックスとインデックスの基数に対する剰余の規定する数値との対応関係を管理する図３（ａ）に示すような作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する図３（ｂ）に示すような作業配列を作成する。
【００１７】
この図３（ａ）に示す作業配列は、図３５（ａ）に示したリストでは、例えば、４番目のメモリバンクを指すインデックスは、「６０→６８→７６」という順序で出現することを示し、この図３（ｂ）に示す作業配列は、その６０／６８／７６というインデックスは、リストの２１／２６／２９番目に出現することを示している。
【００１８】
この作業配列を受けて、計算手段１１ａは、例えば、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という算出式の演算を、
do j=1,kmax-v
!ocl novrec
do i=1,maxcnt
if(kkxx-v(i,j).gt.0)then
a(kkxx-v(i,j))=a(kkxx-v(i,j))+b(kkxx-v(i,j))*c(llxx-v(i,j))
end if
end do
end do
kmax-v：作業配列の行数    maxcnt：メモリバンク数
kkxx-v(i,j) ：図３（ａ）の作業配列の値
llxx-v(i,j) ：図３（ｂ）の作業配列の値
というように、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、作成手段１０ａの作成する作業配列の指定する計算順序に従ってメモリバンクにアクセスすることで、その算出式を計算する。
【００１９】
すなわち、図３５（ａ）に示したリストを図４に示すようなインデックスの並びに変換し、それに従って、図５に示すような計算順序により算出式の計算処理を実行する。これにより、図６に示すような演算形態で実行され、図３６の従来技術に従う場合に比べて非常に高い演算密度を実現できるようになる。
【００２０】
このようにして、図１（ａ）に原理構成を図示する計算機１によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更するので、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【００２１】
図１（ｂ）に原理構成を図示する計算機１は、作成手段１０ｂと、計算手段１１ｂとを備え、プログラム変換装置２は、第１の生成手段２０ｂと、第２の生成手段２１ｂとを備える。
【００２２】
この作成手段１０ｂは、インデックスとインデックスの出現回数との対応関係を管理する作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する作業配列を作成する。
【００２３】
計算手段１１ｂは、計算対象となる算出式の演算を、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、スカラー演算を用いる形式で再構成して、作成手段１０ｂの作成する作業配列の配列データに基づいてそのスカラー演算を繰り返すことで、その算出式を計算する。
【００２４】
第１の生成手段２０ｂは、作成手段１０ｂを実現するプログラムを生成して、計算機１に展開する。
第２の生成手段２１ｂは、計算対象となる算出式に応じて計算手段１１ｂを実現するプログラムを生成して、計算機１に展開する。
【００２５】
このように構成される図１（ｂ）に原理構成を図示する計算機１では、作成手段１０ｂは、図３７に示したリストが与えられると、インデックスとインデックスの出現回数との対応関係を管理する図７（ａ）に示すような作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する図７（ｂ）に示すような作業配列を作成する。
【００２６】
この図７（ａ）に示す作業配列は、図３７に示したリストでは、インデックスの１が１１回出現し、インデックスの２が８回出現し、インデックスの３が８回出現し、インデックス４の４が４回出現することを示し、この図７（ｂ）に示す作業配列は、例えば、その１というインデックスは、リストの１／２／３／４／５／６／７／２９／３０／３１番目に出現することを示している。
【００２７】
この作業配列を受けて、計算手段１１ｂは、例えば、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という算出式の演算を、
n=0
do n1=1,kxmax
akkx1n=a(index(n1))
bkkx1n=b(index(n1))
do n2=1,index-new(n1)
if(index-new(n1).ne.0)then
n=n+1
a(n1)=akkx1n+bkkx1n*c(llx(n))
end if
end do
kxmax ：作業配列の行数
llxx：図７（ｂ）の作業配列の値
index-new ：各インデックス毎の出現回数
akkx1n：変数    bkkx1n：変数
というように、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、インデックスの指すメモリバンクのデータを定数とするスカラー演算を用いる形式で再構成して、作成手段１０ｂの作成する作業配列の指定する出現回数に従ってそのスカラー演算を繰り返すことで、その算出式を計算する。
【００２８】
すなわち、図３７に示したリストを図８に示すようなインデックスの並びに変換し、それに従って、図９に示すような計算順序により算出式の計算処理を実行するイメージに従い、この計算処理を、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行する。これにより、図１０に示すような演算形態で実行され、図３９の従来技術に従う場合に比べて非常に高い演算密度を実現できるようになる。ここで、図１０では、１クロックの間に、「a(n1)=akkx1n+bkkx1n*c(llx(n)) 」の計算処理を４回実行することを想定している。
【００２９】
このようにして、図１（ｂ）に原理構成を図示する計算機１によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行するので、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになる。
【００３０】
図２（ａ）に原理構成を図示する計算機１は、第１の作成手段１２ｂと、第２の作成手段１２ａと、第１の計算手段１３ｂと、第２の計算手段１３ａと、起動手段１４とを備える。
【００３１】
この第１の作成手段１２ｂは、図１（ｂ）に原理構成を図示する計算機１の備える作成手段１０ｂに相当し、第２の作成手段１２ａは、図１（ａ）に原理構成を図示する計算機１の備える作成手段１０ａに相当し、第１の計算手段１３ｂは、図１（ｂ）に原理構成を図示する計算機１の備える計算手段１１ｂに相当し、第２の計算手段１３ａは、図１（ａ）に原理構成を図示する計算機１の備える計算手段１１ａに相当する。
【００３２】
起動手段１４は、第１の作成手段１２ｂの作成する作業配列の配列形式に従って、第１の計算手段１３ｂか第２の計算手段１３ａのいずれか一方を選択して起動する。
【００３３】
このように構成される図２（ａ）に原理構成を図示する計算機１では、第１の作成手段１２ｂは、リストが与えられると、インデックスとインデックスの出現回数との対応関係を管理する作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する作業配列を作成する。
【００３４】
一方、第２の作成手段１２ａは、無条件に起動されたり、起動手段１４が第２の計算手段１３ａを起動する条件が成立するときに起動されて、リストが与えられると、インデックスの基数に対する剰余を求めて、インデックスとその剰余の規定する数値との対応関係を管理する作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する作業配列を作成する。
【００３５】
この第１の作成手段１２ｂの作成する作業配列を受けて、起動手段１４は、この作業配列が同一のインデックスの出現回数が多い配列形式（配列データの形式）を示すときには、第１の計算手段１３ｂを起動し、そうでないときには、第２の計算手段１３ａを起動する。
【００３６】
このようにして起動されると、第１の計算手段１３ｂは、計算対象となる算出式の演算を、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、スカラー演算を用いる形式で再構成して、第１の作成手段１２ｂの作成する作業配列の指定する出現回数に従ってそのスカラー演算を繰り返すことで、その算出式を計算する。
【００３７】
一方、このようにして起動されると、第２の計算手段１３ａは、計算対象となる算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、第２の作成手段１２ａの作成する作業配列の指定する計算順序に従ってメモリバンクにアクセスすることで、その算出式を計算する。
【００３８】
このようにして、図２（ａ）に原理構成を図示する計算機１によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のインデックスの出現回数が多いときには、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行することで、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになるとともに、同一のインデックスの出現頻回数が多くないときには、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更することで、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【００３９】
図２（ｂ）に原理構成を図示する計算機１は、第１の作成手段１５ｂと、第２の作成手段１５ａと、第１の計算手段１６ｂと、第２の計算手段１６ａとを備える。
【００４０】
この第１の作成手段１５ｂは、図１（ｂ）に原理構成を図示する計算機１の備える作成手段１０ｂに相当し、第２の作成手段１５ａは、第１の作成手段１５ｂの作成する作業配列に管理されるインデックス以外のインデックスを管理対象とする点を除き、図１（ａ）に原理構成を図示する計算機１の備える作成手段１０ａに相当し、第１の計算手段１６ｂは、図１（ｂ）に原理構成を図示する計算機１の備える計算手段１１ｂに相当し、第２の計算手段１６ａは、図１（ａ）に原理構成を図示する計算機１の備える計算手段１１ａに相当する。
【００４１】
このように構成される図２（ｂ）に原理構成を図示する計算機１では、第１の作成手段１５ｂは、リストが与えられると、出現回数の多いインデックスを管理対象として、インデックスとインデックスの出現回数との対応関係を管理する作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する作業配列を作成する。
【００４２】
一方、第２の作成手段１５ａは、リストが与えられると、第１の作成手段１５ｂの作成する作業配列に管理されるインデックス以外のインデックスを管理対象としつつ、インデックスの基数に対する剰余を求めて、インデックスとその剰余の規定する数値との対応関係を管理する作業配列を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する作業配列を作成する。
【００４３】
この第１の作成手段１５ｂの作成する作業配列の作成を受けて、第１の計算手段１６ｂは、その作業配列に管理されるインデックスを処理対象として、計算対象となる算出式の演算を、インデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、スカラー演算を用いる形式で再構成して、その作業配列の指定する出現回数に従ってスカラー演算を繰り返すことで、その算出式を計算する。
【００４４】
一方、この第２の作成手段１５ａの作成する作業配列の作成を受けて、第２の計算手段１６ａは、その作業配列に管理されるインデックスを処理対象として、計算対象となる算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成して、その作業配列の指定する計算順序に従ってメモリバンクにアクセスすることで、その算出式を計算する。
【００４５】
このようにして、図２（ｂ）に原理構成を図示する計算機１によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、出現回数の多いインデックスについては、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行することで、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになるとともに、出現回数の少ないインデックスについては、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更することで、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【００４６】
【発明の実施の形態】
以下、実施の形態に従って本発明を詳細に説明する。
図１１に、本発明を具備する計算機１の一実施例を図示する。
【００４７】
この実施例に従う本発明の計算機１は、図１に原理構成を図示した本発明の計算機１を実現するものであって、計算対象となる算出式の計算処理に必要となる作業配列を作成する作業配列作成プログラム２０と、計算対象となる算出式のプログラム形式を変更する計算変更プログラム２１と、計算変更プログラム２１により作成される計算実行プログラム２２と、作業配列作成プログラム２０により作成されるインデックス用作業配列２３と、作業配列作成プログラム２０により作成されるオーダ用作業配列２４とを備える。
【００４８】
ここで、計算実行プログラム２２は、計算変更プログラム２１により作成されることになるが、このとき、それに合わせて、図示しないプログラムが、作業配列作成プログラム２０を作成することになる。
【００４９】
この作業配列作成プログラム２０を作成する機能を持つプログラムや計算変更プログラム２１は、プログラム変換ツールやコンパイラの機能により実現されることになるが、プログラマが手作業によりコーディングしていくこともある。
【００５０】
図１２に、図１（ａ）に原理構成を図示する本発明の計算機１を実現するために作業配列作成プログラム２０が実行する処理フローの一実施例、図１３に、図１（ａ）に原理構成を図示する本発明の計算機１を実現するために計算変更プログラム２１が実行する処理フローの一実施例を図示する。
【００５１】
次に、この処理フローに従って、図１１のように構成される本発明の計算機１の処理について説明する。
作業配列作成プログラム２０は、起動されると、図１２の処理フローに示すように、先ず最初に、ステップ１で、インデックス用作業配列２３及びオーダ用作業配列２４を定義する。この作業配列の定義は、「メモリバンク数×十分なサイズ」の大きさを持つ作業配列を定義することで行う。
【００５２】
続いて、ステップ２で、定義した作業配列を０クリアする。続いて、ステップ３で、リストに配列されるインデックスから次のインデックス（最初に処理に入るときには先頭のインデックス）を取り出す。すなわち、図３５（ａ）に示したようなリストの持つインデックスの中から、配列の順番に従って未処理のインデックスを１つ取り出すのである。
【００５３】
続いて、ステップ４で、全てのインデックスを取り出したのか否かを判断して、全てのインデックスを取り出していないことを判断するときには、ステップ５に進んで、ステップ３で取り出したインデックスのメモリバンク数に対する剰余を求めることで、ステップ３で取り出したインデックスの指すメモリバンクを特定する。
【００５４】
続いて、ステップ６で、ステップ３で取り出したインデックスのリストにおける配列順序を特定する。続いて、ステップ７で、ステップ５で特定したメモリバンクの指すインデックス用作業配列２３の領域に、ステップ３で取り出したインデックスを出現順に格納するとともに、ステップ６で特定したリスト配列順序を対応するオーダ用作業配列２４の領域に格納してから、ステップ３に戻る。
【００５５】
一方、ステップ４で、全てのインデックスを取り出したことを判断するときには、ステップ８に進んで、最もインデックスの出現したメモリバンクを探して出し、その出現回数を特定してから処理を終了する。
【００５６】
このように、作業配列作成プログラム２０は、リストから配列の順番に従ってインデックスindex(i)を取り出すと、そのインデックスindex(i)のメモリバンク数ｂに対する剰余mod-b を求めることで、そのインデックスindex(i)の指すメモリバンクを求めるとともに、そのメモリバンクの出現回数cnt-b を求めて、図１４（ａ）に示すように、そのメモリバンク／出現回数の指すインデックス用作業配列２３の領域に、そのインデックスindex(i)を格納するとともに、図１４（ｂ）に示すように、そのメモリバンク／出現回数の指すオーダ用作業配列２４の領域に、そのインデックスindex(i)のリスト配列順序ｉを格納する処理を実行する。
【００５７】
なお、この処理にあたって、フォートランでは１次元配列が１から始まることを考慮して、作業配列作成プログラム２０は、「ｍｏｄ ｂ＝０」のときには、それを「ｍｏｄ ｂ＝ｎ（ｎ：メモリバンク数）」に置き換えるように処理している。
【００５８】
このようにして、作業配列作成プログラム２０は、図３５（ａ）に示したリストが与えられると、インデックスとインデックスの指すメモリバンクとの対応関係を管理する図３（ａ）に示すようなインデックス用作業配列２３を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する図３（ｂ）に示すようなオーダ用作業配列２４を作成するのである。
【００５９】
この図３（ａ）に示すインデックス用作業配列２３は、図３５（ａ）に示したリストでは、例えば、４番目のメモリバンクを指すインデックスが、「６０→６８→７６」という順序で出現することを示し、この図３（ｂ）に示すオーダ用作業配列２４は、その６０／６８／７６というインデックスが、リストの２１／２６／２９番目に出現することを示している。
【００６０】
一方、計算変更プログラム２１は、起動されると、図１３の処理フローに示すように、先ず最初に、ステップ１で、計算対象となる算出式のループを、内側をメモリバンク数、外側を全メモリバンクでのインデックスの最大出現回数に従って分割する。
【００６１】
続いて、ステップ２で、インデックス用作業配列２３（オーダ用作業配列２４）の空白部の計算を回避するＩＦ文を挿入し、続くステップ３で、使用するインデックス及び添え字を変更し、最後に、ステップ４で、内側ループのベクトル化のためにベクトル化指示行（!ocl novrec)を挿入することで、計算実行プログラム２２を作成する。
【００６２】
例えば、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という計算対象の算出式の演算を、
do j=1,kmax-v
!ocl novrec
do i=1,maxcnt
if(kkxx-v(i,j).gt.0)then
a(kkxx-v(i,j))=a(kkxx-v(i,j))+b(kkxx-v(i,j))*c(llxx-v(i,j))
end if
end do
end do
kmax-v：作業配列の行数    maxcnt：メモリバンク数
kkxx-v(i,j) ：インデックス用作業配列２３の値
llxx-v(i,j) ：オーダ用作業配列２４の値
というように変更することで、計算対象の算出式のプログラム形式を変更した形で定義される計算実行プログラム２２を作成するのである。
【００６３】
これから、計算実行プログラム２２は、計算対象となる算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成されて、インデックス用作業配列２３（オーダ用作業配列２４）の指定する計算順序に従ってメモリバンクにアクセスすることで、その算出式を計算する。
【００６４】
例えば、図３５（ａ）に示したリストを図４に示すようなインデックスの並びに変換し、それに従って、図５に示すような計算順序により算出式の計算処理を実行するのである。
【００６５】
このようにして、図１２及び図１３の処理フローに従う場合、本発明の計算機１では、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更する構成を採る。これにより、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
図１２の処理フローでは、作業配列作成プログラム２０は、インデックスのメモリバンク数に対する剰余を求めることでインデックス用作業配列２３を作成する構成を採ったが、メモリバンク数よりも小さな２の巾乗の値を基数として設定して、インデックスのその基数に対する剰余を求めることで、インデックス用作業配列２３を作成する構成を採ることも可能である。
【００６６】
例えば、図３５（ａ）に示したリストが与えられるときに、４を基数として設定して、インデックスのその基数に対する剰余を求めることで、インデックス用作業配列２３を作成すると、図３（ａ）に示したインデックス用作業配列２３の代わりに、図１５に示すインデックス用作業配列２３が作成されることになるが、このインデックス用作業配列２３を用いても、図３（ａ）に示したインデックス用作業配列２３を用いる場合と同様に、図４に示したインデックスの並びに変換できることになるからである。
【００６７】
また、図１２の処理フローでは剰余の求めた方について特に説明しなかったが、基数として２の巾乗の値を用いると、インデックスのその基数に対する剰余をビットシフト処理やビットマスク処理により求めることができるので、簡単に剰余を求めることができるようになる。
【００６８】
例えば、２９というインデックスは２進表示で「０００１１１０１」と表されることになるが、この２９の８に対する剰余は、その下位３ビットである「１０１」となるので、この下位３ビットを抽出するビットシフト処理やビットマスク処理を用いることで、簡単に剰余を求めることができるのである。
【００６９】
また、図１３の処理フローでは、インデックス用作業配列２３（オーダ用作業配列２４）の空白部の計算を回避するＩＦ文を挿入する構成を採ったが、この空白部を詰める形で計算を行うようにすれば、このＩＦ文を省略することができる。すなわち、図４に示したインデックスの並びに変更するときに、それが持つ空白部を詰める形で計算を行うようにすれば、このＩＦ文を省略することができるのである。
【００７０】
また、図１２の処理フローでは、「メモリバンク数（剰余の数）×十分なサイズ」という方法でインデックス用作業配列２３及びオーダ用作業配列２４を定義する構成を採ったが、基数を設定してから、各剰余毎にインデックスの出現回数を求めるとともに、出現回数が０とならない剰余の数を求めて、「出現回数が０とならない剰余の数×最大の出現回数」という方法でインデックス用作業配列２３及びオーダ用作業配列２４を定義する構成を採ると、必要最小限のメモリ容量でインデックス用作業配列２３及びオーダ用作業配列２４を定義できるようになる。
【００７１】
また、図１２の処理フローでは説明しなかったが、長い科学計算を行う場合、計算実行プログラム２２で記述する算出式が何回も呼び出されて計算されるということが起こる。
【００７２】
このようなときには、作業配列作成プログラム２０は、その都度、インデックス用作業配列２３及びオーダ用作業配列２４を生成する構成を採るのではなくて、前回の計算のときに指定されたリストが変更されているのか否かをチェックして、変更されているときのみ、その変更に合わせてインデックス用作業配列２３及びオーダ用作業配列２４を生成するように処理することが好ましい。
【００７３】
図１６に、図１（ｂ）に原理構成を図示する本発明の計算機１を実現するために作業配列作成プログラム２０が実行する処理フローの一実施例、図１７に、図１（ｂ）に原理構成を図示する本発明の計算機１を実現するために計算変更プログラム２１が実行する処理フローの一実施例を図示する。
【００７４】
次に、この処理フローに従って、図１１のように構成される本発明の計算機１の処理について説明する。
作業配列作成プログラム２０は、起動されると、図１６の処理フローに示すように、先ず最初に、ステップ１で、リストに出現する最大のインデックスを特定する。続いて、ステップ２で、インデックス用作業配列２３及びオーダ用作業配列２４を定義する。この作業配列の定義は、「最大のインデックス値×十分なサイズ」の大きさを持つ作業配列を定義することで行う。
【００７５】
続いて、ステップ３で、定義した作業配列を０クリアする。続いて、ステップ４で、リストに配列されるインデックスから次のインデックス（最初に処理に入るときには先頭のインデックス）を取り出す。すなわち、図３７に示したようなリストの持つインデックスの中から、配列の順番に従って未処理のインデックスを１つ取り出すのである。
【００７６】
続いて、ステップ５で、全てのインデックスを取り出したのか否かを判断して、全てのインデックスを取り出していないことを判断するときには、ステップ６に進んで、ステップ４で取り出したインデックスのリストにおける配列順序を特定する。続いて、ステップ７で、ステップ４で取り出したインデックスの指すインデックス用作業配列２３の領域に、ステップ４で取り出したインデックスを格納するとともに、ステップ６で特定したリスト配列順序を対応するオーダ用作業配列２４の領域に格納してから、ステップ４に戻る。
【００７７】
一方、ステップ４で、全てのインデックスを取り出したことを判断するときには、ステップ８に進んで、最も出現したインデックスを探して出して、その出現回数を特定してから処理を終了する。
【００７８】
このように、作業配列作成プログラム２０は、リストから配列の順番に従ってインデックスindex(i)を取り出すと、図１８（ａ）に示すように、そのインデックスindex(i)とそのインデックスindex(i)の出現回数cnt-m の指すインデックス用作業配列２３の領域に、そのインデックスindex(i)を格納するとともに、図１８（ｂ）に示すように、そのインデックスindex(i)とそのインデックスindex(i)の出現回数cnt-m の指すオーダ用作業配列２４の領域に、そのインデックスindex(i)のリスト配列順序ｉを格納する処理を実行する。
【００７９】
このようにして、作業配列作成プログラム２０は、図３７に示したリストが与えられると、インデックスとインデックスの出現回数との対応関係を管理する図７（ａ）に示すようなインデックス用作業配列２３を作成するとともに、インデックスとインデックスのリスト配列順序との対応関係を管理する図７（ｂ）に示すようなオーダ用作業配列２４を作成するのである。
【００８０】
この図７（ａ）に示す作業配列は、図３７に示したリストでは、インデックスの１が１１回出現し、インデックスの２が８回出現し、インデックスの３が８回出現し、インデックス４の４が４回出現することを示し、この図７（ｂ）に示す作業配列は、例えば、その１というインデックスは、リストの１／２／３／４／５／６／７／２９／３０／３１番目に出現することを示している。
【００８１】
一方、計算変更プログラム２１は、起動されると、図１７の処理フローに示すように、先ず最初に、ステップ１で、計算対象となる算出式のループを、内側をインデックス数、外側を各インデックスの出現回数に従って分割する。
【００８２】
続いて、ステップ２で、インデックス用作業配列２３（オーダ用作業配列２４）の空白部の計算を回避するＩＦ文を挿入し、続くステップ３で、使用するインデックス及び添え字を変更することで、スカラー演算の形態に従う計算実行プログラム２２を作成する。
【００８３】
例えば、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という計算対象の算出式の演算を、
n=0
do n1=1,kxmax
akkx1n=a(index(n1))
bkkx1n=b(index(n1))
do n2=1,index-new(n1)
if(index-new(n1).ne.0)then
n=n+1
a(n1)=akkx1n+bkkx1n*c(llx(n))
end if
end do
kxmax ：作業配列の行数
llxx：図７（ｂ）の作業配列の値
index-new ：各インデックス毎の出現回数
akkx1n：変数    bkkx1n：変数
というように変更することで、計算対象の算出式のプログラム形式を変更した形で定義される計算実行プログラム２２を作成するのである。
【００８４】
これから、計算実行プログラム２２は、計算対象となるインデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、インデックスの指すメモリバンクのデータを定数とするスカラー演算を用いる形式で再構成されて、インデックス用作業配列２３（オーダ用作業配列２４）の指定する出現回数に従ってそのスカラー演算を繰り返すことで、その算出式を計算する。
【００８５】
例えば、図３７に示したリストを図８に示すようなインデックスの並びに変換し、それに従って、図９に示すような計算順序により算出式の計算処理を実行するのである。
【００８６】
このようにして、図１６及び図１７の処理フローに従う場合、本発明の計算機１では、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行する構成を採る。これにより、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになる。
【００８７】
図１６の処理フローで作成するインデックス用作業配列２３については、リスト中の各インデックスを前に位置するインデックスと比較する構成を採って、小さい場合にはその順序を前に移動させていくという公知のソーティング手法（ダイヤモンドソート手法）を用いることで作成することも可能である。
【００８９】
また、図１６の処理フローでは、「最大のインデックス値×十分なサイズ」という方法でインデックス用作業配列２３及びオーダ用作業配列２４を定義する構成を採ったが、各インデックスの出現回数を求めて、「出現回数が０とならないインデックスの数×最大の出現回数」という方法でインデックス用作業配列２３及びオーダ用作業配列２４を定義する構成を採ると、必要最小限のメモリ容量でインデックス用作業配列２３及びオーダ用作業配列２４を定義できるようになる。
【００９０】
また、図１６の処理フローでは説明しなかったが、長い科学計算を行う場合、計算実行プログラム２２で記述する算出式が何回も呼び出されて計算されるということが起こる。
【００９１】
このようなときは、作業配列作成プログラム２０は、その都度、インデックス用作業配列２３及びオーダ用作業配列２４を生成する構成を採るのではなくて、前回の計算のときに指定されたリストが変更されているのか否かをチェックして、変更されているときのみ、その変更に合わせてインデックス用作業配列２３及びオーダ用作業配列２４を生成するように処理することが好ましい。
【００９２】
図１９に、本発明を具備する計算機１の他の実施例を図示する。
この実施例に従う本発明の計算機１は、図２に原理構成を図示した本発明の計算機１を実現するものであって、計算対象となる算出式の計算処理に必要となる作業配列を作成する作業配列作成プログラム３０と、計算対象となる算出式のプログラム形式を変更する計算変更プログラム３１と、計算実行プログラム２２ａ，ｂを起動する起動プログラム３２と、計算変更プログラム３１により作成される計算実行プログラム２２ａ，ｂと、作業配列作成プログラム３０により作成されるインデックス用作業配列２３ａ，ｂと、作業配列作成プログラム３０により作成されるオーダ用作業配列２４ａ，ｂとを備える。
【００９３】
ここで、計算実行プログラム２２ａ，ｂは、計算変更プログラム３１により作成されることになるが、このとき、それに合わせて、図示しないプログラムが、作業配列作成プログラム３０を作成することになる。
【００９４】
この作業配列作成プログラム３０を作成する機能を持つプログラムや計算変更プログラム３１は、プログラム変換ツールやコンパイラの機能により実現されることになるが、プログラマが手作業によりコーディングしていくこともある。
【００９５】
図２０に、図２（ａ）に原理構成を図示する本発明の計算機１を実現するために作業配列作成プログラム３０が実行する処理フローの一実施例、図２１に、図２（ａ）に原理構成を図示する本発明の計算機１を実現するために計算変更プログラム３１が実行する処理フローの一実施例、図２２に、図２（ａ）に原理構成を図示する本発明の計算機１を実現するために起動プログラム３２が実行する処理フローの一実施例を図示する。
【００９６】
次に、この処理フローに従って、図１９のように構成される本発明の計算機１の処理について説明する。
作業配列作成プログラム３０は、起動されると、図２０の処理フローに示すように、先ず最初に、ステップ１で、図１２の処理フローに従って、リストから配列の順番に従ってインデックスindex(i)を取り出すと、そのインデックスindex(i)のメモリバンク数ｂに対する剰余mod-b を求めることで、そのインデックスindex(i)の指すメモリバンクを求めるとともに、そのメモリバンクの出現回数cnt-b を求めて、図１４（ａ）に示すように、そのメモリバンク／出現回数の指すインデックス用作業配列２３の領域に、そのインデックスindex(i)を格納するとともに、図１４（ｂ）に示すように、そのメモリバンク／出現回数の指すオーダ用作業配列２４の領域に、そのインデックスindex(i)のリスト配列順序ｉを格納することで、インデックス用作業配列２３ａ及びオーダ用作業配列２４ａを作成する。
【００９７】
続いて、ステップ２で、図１６の処理フローに従って、リストから配列の順番に従ってインデックスindex(i)を取り出すと、図１８（ａ）に示すように、そのインデックスindex(i)とそのインデックスindex(i)の出現回数cnt-m の指すインデックス用作業配列２３の領域に、そのインデックスindex(i)を格納するとともに、図１８（ｂ）に示すように、そのインデックスindex(i)とそのインデックスindex(i)の出現回数cnt-m の指すオーダ用作業配列２４の領域に、そのインデックスindex(i)のリスト配列順序ｉを格納することで、インデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂを作成する。
【００９８】
一方、計算変更プログラム３１は、図２１の処理フローに示すように、先ず最初に、ステップ１で、図１３の処理フローに従って、例えば、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という計算対象の算出式の演算を、
do j=1,kmax-v
!ocl novrec
do i=1,maxcnt
if(kkxx-v(i,j).gt.0)then
a(kkxx-v(i,j))=a(kkxx-v(i,j))+b(kkxx-v(i,j))*c(llxx-v(i,j))
end if
end do
end do
kmax-v：作業配列の行数    maxcnt：メモリバンク数
kkxx-v(i,j) ：インデックス用作業配列２３ａの値
llxx-v(i,j) ：オーダ用作業配列２４ａの値
というように変更することで、計算対象の算出式のプログラム形式を変更した形で定義される計算実行プログラム２２ａを作成する。
【００９９】
続いて、ステップ２で、図１３の処理フローに従って、例えば、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という計算対象の算出式の演算を、
n=0
do n1=1,kxmax
akkx1n=a(index(n1))
bkkx1n=b(index(n1))
do n2=1,index-new(n1)
if(index-new(n1).ne.0)then
n=n+1
a(n1)=akkx1n+bkkx1n*c(llx(n))
end if
end do
kxmax ：作業配列の行数
llxx：図７（ｂ）の作業配列の値
index-new ：各インデックス毎の出現回数
akkx1n：変数    bkkx1n：変数
というように変更することで、計算対象の算出式のプログラム形式を変更した形で定義される計算実行プログラム２２ｂを作成する。
【０１００】
一方、起動プログラム３２は、起動されると、図２２の処理フローに示すように、先ず最初に、ステップ１で、作業配列作成プログラム３０により作成されたインデックス用作業配列２３ｂが同一のインデックスの出現回数の多い配列形式を示しているのか否かを判断する。
【０１０１】
この判断処理は、例えば、図２３に示すように、インデックス用作業配列２３ｂに登録されるインデックス数ｍと、インデックス用作業配列２３ｂに登録されるインデックスの最大出現回数ｎとを比較して、「ｎ＞ｍ」のときには、インデックス用作業配列２３ｂが同一のインデックスの出現回数の多い配列形式を示していると判断し、「ｍ＞ｎ」のときには、そうでないと判断することで行う。
【０１０２】
このステップ１で、インデックス用作業配列２３ｂが同一のインデックスの出現回数の多い配列形式を示していることを判断するときには、ステップ２に進んで、計算実行プログラム２２ｂを起動する。
【０１０３】
このようにして起動されると、計算実行プログラム２２ｂは、計算対象となるインデックスの出現回数を内側ループとし、インデックス系を外側ループとするとともに、インデックスの指すメモリバンクのデータを定数とするスカラー演算を用いる形式で再構成されて、インデックス用作業配列２３ｂ（オーダ用作業配列２４ｂ）の指定する出現回数に従ってそのスカラー演算を繰り返すことで、その算出式を計算する。
【０１０４】
例えば、図３７に示したリストを図８に示すようなインデックスの並びに変換し、それに従って、図９に示すような計算順序により算出式の計算処理を実行するのである。
【０１０５】
これに対して、ステップ１で、インデックス用作業配列２３ｂが同一のインデックスの出現回数の多い配列形式を示していないことを判断するときには、ステップ３に進んで、計算実行プログラム２２ａを起動する。
【０１０６】
このようにして起動されると、計算実行プログラム２２ａは、計算対象となる算出式の演算を、剰余系を内側ループとし、剰余の規定する数値の出現回数を外側ループとする形式で再構成されて、インデックス用作業配列２３ａ（オーダ用作業配列２４ａ）の指定する計算順序に従ってメモリバンクにアクセスすることで、その算出式を計算する。
【０１０７】
例えば、図３５（ａ）に示したリストを図４に示すようなインデックスの並びに変換し、それに従って、図５に示すような計算順序により算出式の計算処理を実行するのである。
【０１０８】
このようにして、図１９に示す本発明を具備する計算機１では、同一のインデックスが多く出現するリストである場合には、インデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂを使って算出式の計算処理を実行し、同一のインデックスが多く出現しないリストである場合には、インデックス用作業配列２３ａ及びオーダ用作業配列２４ａを使って算出式の計算処理を実行することで、算出式を高速に算出するように処理するのである。
【０１０９】
図１９の実施例では、予めインデックス用作業配列２３ａ，ｂ及びオーダ用作業配列２４ａ，ｂを作成するという構成を採ったが、先ず最初に、インデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂを作成し、その作成した配列形式に従って、インデックス用作業配列２３ａ及びオーダ用作業配列２４ａを作成するのか否かを決定するという方法を採ることも可能である。
【０１１０】
この方法に従うと、インデックス用作業配列２３ａ及びオーダ用作業配列２４ａを作成する必要がないときには、それを作成しないで済むようになる。
図２４に、この方法を実現するための本発明を具備する計算機１の実施例を図示する。
【０１１１】
この方法を実現するためには、図１９の実施例で用意した起動プログラム３２を省略するとともに、作業配列作成プログラム３０が図２５に示す処理フローを実行する構成を採る。
【０１１２】
すなわち、作業配列作成プログラム３０は、この方法を実現するために、図２５の処理フローに示すように、先ず最初に、ステップ１で、図１６の処理フローに従って、インデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂを作成し、続いて、ステップ２で、作成したインデックス用作業配列２３ｂが同一のインデックスの出現回数の多い配列形式を示しているのか否かを判断する。
【０１１３】
そして、この判断処理で、同一のインデックスの出現回数の多い配列形式を示していないことを判断するときには、ステップ３に進んで、図１２の処理フローに従って、インデックス用作業配列２３ａ及びオーダ用作業配列２４ａを作成し、続くステップ４で、計算実行プログラム２２ａを起動し、これに対して、同一のインデックスの出現回数の多い配列形式を示していることを判断するときには、ステップ５に進んで、インデックス用作業配列２３ａ及びオーダ用作業配列２４ａを作成することなく、計算実行プログラム２２ｂを起動していくように処理することになる。
【０１１４】
上述した図１９及び図２４の実施例では、計算実行プログラム２２ａか計算実行プログラム２２ｂのいずれか一方を起動していくという構成を採ったが、リストに配列されるインデックスを出現回数の多いものと少ないものとに分け、出現回数の多いインデックスを管理対象としてインデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂを作成し、出現回数の少ないインデックスを管理対象としてインデックス用作業配列２３ａ及びオーダ用作業配列２４ａを作成する構成を採って、出現回数の少ないインデックスについては、計算実行プログラム２２ａがインデックス用作業配列２３ａ及びオーダ用作業配列２４ａに従って算出式の計算処理を実行し、出現回数の多いインデックスについては、計算実行プログラム２２ｂがインデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂに従って算出式の計算処理を実行するという、図２（ｂ）に原理構成を図示する方法を採ることも可能である。
【０１１５】
この方法に従うと、出現回数の多いインデックスと出現回数の少ないインデックスとが混在している場合に、算出式の計算処理を高速に実行できるようになる。
【０１１６】
図２６に、この方法を実現するために作業配列作成プログラム３０が実行する処理フローの一実施例を図示する。
作業配列作成プログラム３０は、この方法を実現する場合には、図２６の処理フローに示すように、先ず最初に、ステップ１で、図１６の処理フローに従って、インデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂを作成する。
【０１１７】
続いて、ステップ２で、作成したインデックス用作業配列２３ｂに従って、出現回数の少ないインデックスを特定して、作成したインデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂから、その特定したインデックスのデータを削除することで、出現回数の多いインデックスについてのインデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂを作成する。
【０１１８】
続いて、ステップ３で、削除したインデックスを管理対象として、図１２の処理フローに従って、インデックス用作業配列２３ａ及びオーダ用作業配列２４ａを作成することで、出現回数の少ないインデックスについてのインデックス用作業配列２３ａ及びオーダ用作業配列２４ａを作成する。
【０１１９】
このようにして、図２６の処理フローに従う場合、作業配列作成プログラム３０は、例えば、図２７に示すようなリストが与えられると、出現回数の多いインデックスについては、図２８（ａ）に示すように、図７（ａ）に示した配列形式に従うインデックス用作業配列２３ｂを作成するとともに、図７（ｂ）に示した配列形式に従うオーダ用作業配列２４ｂを作成し、出現回数の少ないインデックスについては、図２８（ｂ）に示すように、図３（ａ）に示した配列形式に従うインデックス用作業配列２３ａを作成するとともに、図３（ｂ）に示した配列形式に従うオーダ用作業配列２４ａを作成するのである。
【０１２０】
この作業配列作成プログラム３０の作成する作業配列を受けて、例えば、
0003686261.tif 000002
というように記述される計算実行プログラム２２ａは、出現回数の少ないインデックスについてのインデックス用作業配列２３ａ及びオーダ用作業配列２４ａに従って算出式の計算処理を実行する。
【０１２１】
そして、この作業配列作成プログラム３０の作成する作業配列を受けて、例えば、
n=0
do n1=1,kxmax
akkx1n=a(index(n1))
bkkx1n=b(index(n1))
do n2=1,index-new(n1)
if(index-new(n1).ne.0)then
n=n+1
a(n1)=akkx1n+bkkx1n*c(llx(n))
end if
end do
kxmax ：作業配列の行数
llxx：図７（ｂ）の作業配列の値
index-new ：各インデックス毎の出現回数
akkx1n：変数    bkkx1n：変数
というように記述される計算実行プログラム２２ｂは、出現回数の多いインデックスについてのインデックス用作業配列２３ｂ及びオーダ用作業配列２４ｂに従って算出式の計算処理を実行する。
【０１２２】
最終的には、この２つの算出式の計算処理の処理結果を加算することで、算出式の計算結果を得ることになる。
最後に、並列システムへの適用について説明する。
【０１２３】
本発明は、単一プロセッサ構成の計算機にその適用が限られるものではなく、並列プロセッサ構成の計算機にもそのまま適用できる。
並列システムには、図２９（ａ）に示す構成を採る分散メモリ方式のものと、図２９（ｂ）に示す構成を採る共用メモリ方式のものとがあるが、本発明は、そのいずれに対しても適用可能である。
【０１２４】
但し、本発明を分散メモリ方式の並列システムに適用する場合、例えば、プロセッサｉ（ｉ＝０〜ｎ）の実バンクアドレスが「０〜ｍ−１」で説明するならば、プロセッサ０には「０〜ｍ−１」、プロセッサ１には「ｍ〜２×ｍ−１」、プロセッサ２には「２×ｍ〜３×ｍ−１」というように、システム全体に対するアドレスを設定することになる。
【０１２５】
本発明を並列システムに適用する場合、図３に示すインデックス用作業配列２３及びオーダ用作業配列２４の例で説明するならば、図３０に示すように、インデックス用作業配列２３及びオーダ用作業配列２４をプロセッサ数に応じて分割して、それを各プロセッサに配分する構成を採ることになる。また、図３１に示すリストを受けて、図３２に示すようなインデックス用作業配列２３及びオーダ用作業配列２４を作成するときの例で説明するならば、この図３２に示すように、インデックス用作業配列２３及びオーダ用作業配列２４をプロセッサ数に応じて分割して、それを各プロセッサに配分する構成を採ることになる。
【０１２６】
このとき、各プロセッサの負荷の均等化を図るために、図３３に示すように、各プロセッサに配分するインデックスの数が概略均等になるようにと、インデックス用作業配列２３及びオーダ用作業配列２４を分割することが好ましい。ここで、この図３３では、図３４に示すインデックスの並びを持つリストを想定している。
【０１２７】
図示実施例に従って本発明を説明したが、本発明はこれに限定されるものではない。例えば、実施例では、
do j=1,n
a(index(j))=a(index(j))+b(index(j))*c(j)
end do
という算出式を具体例にして本発明を説明したが、本発明の適用対象となる算出式は如何なるものであってもよい。
【０１２８】
【発明の効果】
以上説明したように、本発明によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更することで、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【０１２９】
そして、本発明によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行することで、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになる。
【０１３０】
そして、本発明によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、同一のインデックスの出現回数が多いときには、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行することで、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになるとともに、同一のインデックスの出現回数が多くないときには、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更することで、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【０１３１】
そして、本発明によれば、リストに配列されるインデックスの指すメモリバンクにアクセスすることで、規定の算出式の計算処理を実行するときにあって、出現回数の多いインデックスについては、同一のインデックスの指すメモリバンクのデータを定数として設定しつつスカラー演算に従って実行することで、ベクトルメモリアクセスが減少し、その計算処理を高速に実行できるようになるとともに、出現回数の少ないインデックスについては、同一のメモリバンクに対するアクセスが連続しないようにとリストのインデックスの並びを変更することで、メモリビジーが回避され、その計算処理を高速に実行できるようになる。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明の原理構成図である。
【図３】本発明の説明図である。
【図４】本発明の説明図である。
【図５】本発明の説明図である。
【図６】本発明の説明図である。
【図７】本発明の説明図である。
【図８】本発明の説明図である。
【図９】本発明の説明図である。
【図１０】本発明の説明図である。
【図１１】本発明の一実施例である。
【図１２】作業配列作成プログラムの処理フローである。
【図１３】計算変更プログラムの処理フローである。
【図１４】作業配列作成プログラムの処理説明図である。
【図１５】作業配列作成プログラムの処理説明図である。
【図１６】作業配列作成プログラムの処理フローである。
【図１７】計算変更プログラムの処理フローである。
【図１８】作業配列作成プログラムの処理説明図である。
【図１９】本発明の他の実施例である。
【図２０】作業配列作成プログラムの処理フローである。
【図２１】計算変更プログラムの処理フローである。
【図２２】起動プログラムの処理フローである。
【図２３】起動プログラムの処理説明図である。
【図２４】本発明の他の実施例である。
【図２５】作業配列作成プログラムの処理フローである。
【図２６】作業配列作成プログラムの処理フローである。
【図２７】リストの説明図である。
【図２８】作業配列の説明図である。
【図２９】並列システムの説明図である。
【図３０】並列システムへの適用説明図である。
【図３１】リストの説明図である。
【図３２】並列システムへの適用説明図である。
【図３３】並列システムへの適用説明図である。
【図３４】リストの説明図である。
【図３５】従来技術の説明図である。
【図３６】従来技術の説明図である。
【図３７】従来技術の説明図である。
【図３８】従来技術の説明図である。
【図３９】従来技術の説明図である。
【図４０】従来技術の説明図である。
【符号の説明】
１      計算機
２      プログラム変換装置
１０ａ  作成手段
１１ａ  計算手段
２０ａ  第１の生成手段
２１ａ  第２の生成手段
１０ｂ  作成手段
１１ｂ  計算手段
２０ｂ  第１の生成手段
２１ｂ  第２の生成手段
１２ｂ  第１の作成手段
１２ａ  第２の作成手段
１３ｂ  第１の計算手段
１３ａ  第２の計算手段
１４    起動手段
１５ｂ  第１の作成手段
１５ａ  第２の作成手段
１６ｂ  第１の計算手段
１６ａ  第２の計算手段
【図１】
0003686261.tif 000003
【図２】
0003686261.tif 000004
【図３】
0003686261.tif 000005
【図４】
0003686261.tif 000006
【図５】
0003686261.tif 000007
【図６】
0003686261.tif 000008
【図７】
0003686261.tif 000009
【図８】
0003686261.tif 000010
【図９】
0003686261.tif 000011
【図１０】
0003686261.tif 000012
【図１１】
0003686261.tif 000013
【図１２】
0003686261.tif 000014
【図１３】
0003686261.tif 000015
【図１４】
0003686261.tif 000016
【図１５】
0003686261.tif 000017
【図１６】
0003686261.tif 000018
【図１７】
0003686261.tif 000019
【図１８】
0003686261.tif 000020
【図１９】
0003686261.tif 000021
【図２０】
0003686261.tif 000022
【図２１】
0003686261.tif 000023
【図２２】
0003686261.tif 000024
【図２３】
0003686261.tif 000025
【図２４】
0003686261.tif 000026
【図２５】
0003686261.tif 000027
【図２６】
0003686261.tif 000028
【図２７】
0003686261.tif 000029
【図２８】
0003686261.tif 000030
【図２９】
0003686261.tif 000031
【図３０】
0003686261.tif 000032
【図３１】
0003686261.tif 000033
【図３２】
0003686261.tif 000034
【図３３】
0003686261.tif 000035
【図３４】
0003686261.tif 000036
【図３５】
0003686261.tif 000037
【図３６】
0003686261.tif 000038
【図３７】
0003686261.tif 000039
【図３８】
0003686261.tif 000040
【図３９】
0003686261.tif 000041
【図４０】
0003686261.tif 000042