(57)【要約】【課題】スレッドの動作にずれを生じさせないアプリケーションの並列処理方法を得る。【解決手段】並列化ループの入口のアドレスａとより若いアドレスｂとの関係において、アドレスの差（ｂ−ａ）のアドレス間距離と、所要時間（ｔ）の対応を順次記録してゆく。あるスレッドが、最初にｌｏｏｐｎの先頭アドレスａに到達する。この時に、他の各スレッドｉが実行しているアドレスｂとアドレスａとの差を、アドレス間距離（ｂ−ａ）欄に記入する。なお、その時の時刻を時刻ｔ１とする。そして、同じスレッドｉでの処理が進行し、アドレスａに到達した時刻を時刻ｔ２とし、時刻間差ｔ２−ｔ１を、先程記録したｂ−ａ欄に対応する所要時間（ｔ）欄に記入する。本表を基に、複数のＣＰＵを有する共有メモリモデルのコンピュータにおいて、メモリに配置されたプログラムを並列に実行するにあたって、並列化されたループの実行スケジュールを動的に最適化する。【選択図】　　　　図１
2004078617.tif 000002
【特許請求の範囲】
【請求項１】
１つのアプリケーションの処理を複数に分割して並列的に実行するスレッド処理に係わり、共有メモリにおいて実行されるアプリケーションの並列処理方法において、
並列化したループの入口のアドレスであるアドレスａに、より早く到達したスレッドＡには、より多くの仕事を割り当てる仕事割り当て工程Ａと、
より遅く到達したスレッドＢには、より少ない仕事を割り当てる仕事割り当て工程Ｂと、
少なくとも前記仕事割り当て工程Ａと前記仕事割り当て工程Ｂとに基づき、処理を実行するためのスケジューリングを動的に実行する、動的スケジューリング工程とを有し、
前記スレッドＡと前記スレッドＢの並列処理における、前記ループの出口での進行時間の統一化を図ったことを特徴とするアプリケーションの並列処理方法。
【請求項２】
前記動的スケジューリング工程において、前記並列化した各ループのループ名と、前記各ループの実行時間との関係を検索することを特徴とする請求項１記載のアプリケーションの並列処理方法。
【請求項３】
前記各ループの実行時間との関係の検索は、各スレッドがループ入口に到着した時刻と実行中のアドレスとの組を対応づけて、それらのデータの蓄積から、各スレッドが分担すべきループ実行仕事量を推定するものであることを特徴とする請求項２記載のアプリケーションの並列処理方法。
【請求項４】
前記各ループの実行時間との関係の検索において、
並列化ループの前記入口のアドレスａより若いアドレスをアドレスｂとし、
所定のプログラムの実行がアドレスｂを通過してからアドレスａに到達するまでの所要時間を時間ｔとし、
アドレス間距離（ｂ−ａ）と、所要時間（ｔ）との対応関係を検索し、
前記所定のプログラムの実行前に前記メモリ内に準備しておく表を構成することを特徴とする請求項３記載のアプリケーションの並列処理方法。
【請求項５】
前記表には「ループ名」と「実行時間」が示され、前記プログラム内に存在する各並列ループと、ループ本体の実行時間（並列化しない場合）の対応が表記されていることを特徴とする請求項４記載のアプリケーションの並列処理方法。
【請求項６】
前記表は、プログラムの実行時に動的に作成される表であり、前記「実行時間」が事前に分からない場合には、前記プログラムの実行中に値を記入してもよいことを特徴とする請求項５記載のアプリケーションの並列処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、アプリケーションの並列処理方法に関し、特に、ＯＳが１つのアプリケーションの処理を複数に分割して実行するスレッド（ｔｈｒｅａｄ）処理に係わる、アプリケーションの並列処理方法に関する。
【０００２】
【従来の技術】
従来、アプリケーションの並列処理方法は、たとえば、複数のＣＰＵを有する共有メモリモデルのコンピュータ処理に適用され用いられる。
この方法では、ループを並列実行するスケジュール方式が、プログラミング言語で記述されたソース・コードを、コンピュータが直接実行できる機械語に一括変換する、コンパイル（Ｃｏｍｐｉｌｅ　）時に決定されている。このため、実行時に各スレッド（ｔｈｒｅａｄ）がループの入口に到着する時刻に大差がある場合にも、既に決定しているスケジュール方式に従って処理が行われる。
【０００３】
本発明と技術分野の類似する先願発明例１として、特開平０４−２９３１５０号公報の「コンパイル方法」がある。本先願発明例１では、ソースプログラムを最も早く処理できるオブジェクトコードを生成し、ベクトル計算機システムの最大性能の発揮を図っている。つまり、共有メモリモデルのコンピュータでの、プログラム並列化の最適化方法について、述べられている。
【０００４】
先願発明例２としての特開２００２−０４９６０３号公報の「動的負荷分散方法及び動的負荷分散装置」では、例えば、線形または非線型最適化問題を解くような反復法を用いたアプリケーションプログラムを並列計算機で実行する場合に、各プロセッサの負荷を効率的に分散させ、より良い計算効率を得ることを図っている。
【０００５】
先願発明例３としての特許第２８１８０１６号（特開平４−９８３２３号公報）の「プロセス並列実行方法および装置」では、並列実行可能なループ処理を並列プロセス処理により実行する場合に、ループの演算量にかかる実行コスト値を基に並列プロセスの生成個数を決定する。これにより、並列実行可能なループの処理実行に対して効率的な並列実行を実現できる、としている。
【０００６】
【発明が解決しようとする課題】
しかしながら、上記従来の技術では、ＯＳ（Ｏｐｅｒａｔｉｎｇ　ｓｙｓｔｅｍ）が１つのアプリケーションの処理を複数に分割して実行するスレッドの動作に、ずれが生じたまま以後の処理に進んでしまう恐れがある問題点を伴う。その結果、以降の処理に錯綜を生じ、正しく処理がされない恐れを生じさせる。これは、ループを実行するときの各スレッドの進行状況（実行箇所、所要時間）の情報を、以後の実行に活用していないためである。
【０００７】
本発明は、スレッドの動作にずれを生じさせないアプリケーションの並列処理方法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
かかる目的を達成するため、本発明のアプリケーションの並列処理方法は、１つのアプリケーションの処理を複数に分割して並列的に実行するスレッド処理に係わり、共有メモリにおいて実行されるアプリケーションの並列処理方法において、並列化したループの入口のアドレスであるアドレスａに、より早く到達したスレッドＡには、より多くの仕事を割り当てる仕事割り当て工程Ａと、より遅く到達したスレッドＢには、より少ない仕事を割り当てる仕事割り当て工程Ｂと、少なくとも仕事割り当て工程Ａと仕事割り当て工程Ｂとに基づき、処理を実行するためのスケジューリングを動的に実行する、動的スケジューリング工程とを有し、スレッドＡとスレッドＢの並列処理における、ループの出口での進行時間の統一化を図ったことを特徴としている。
【０００９】
また、上記の動的スケジューリング工程において、並列化した各ループのループ名と、各ループの実行時間との関係を検索し、各ループの実行時間との関係の検索は、各スレッドがループ入口に到着した時刻と実行中のアドレスとの組を対応づけて、それらのデータの蓄積から、各スレッドが分担すべきループ実行仕事量を推定するものであるとよい。
【００１０】
さらに、上記の各ループの実行時間との関係の検索において、並列化ループの入口のアドレスａより若いアドレスをアドレスｂとし、所定のプログラムの実行がアドレスｂを通過してからアドレスａに到達するまでの所要時間を時間ｔとし、アドレス間距離（ｂ−ａ）と、所要時間（ｔ）との対応関係を検索し、所定のプログラムの実行前にメモリ内に準備しておく表を構成し、表には「ループ名」と「実行時間」が示され、プログラム内に存在する各並列ループと、ループ本体の実行時間（並列化しない場合）の対応が表記され、表は、プログラムの実行時に動的に作成される表であり、「実行時間」が事前に分からない場合には、プログラムの実行中に値を記入してもよい。
【００１１】
【発明の実施の形態】
次に、添付図面を参照して本発明によるアプリケーションの並列処理方法の実施の形態を詳細に説明する。図１から図３を参照すると、本発明のアプリケーションの並列処理方法の一実施形態が示されている。
【００１２】
本発明は、複数のＣＰＵを有する共有メモリモデルのコンピュータにおいて、メモリに配置されたプログラムを並列に実行するにあたって、並列化されたループの実行スケジュール方式を動的に最適化するものである。
【００１３】
その方法は、各スレッドがループ入口に到着した時刻と実行中のアドレスとの組を対応づけて、それらのデータの蓄積から、各スレッドが分担すべきループ実行仕事量を推定するものである。なお、データの蓄積を行う表をループ毎に持つ必要がなく、全体を管理するための一つでよいため効率的である。本発明の構成内容を、以下に詳述する。
【００１４】
（構成例）
図１に、プログラム内の一つの並列化ループ周辺のメモリマップの構成例を示す。ここで、並列化ループの入口のアドレスを、アドレスａとする。また、アドレスｂは、並列化ループの入口のアドレスａより若いアドレスである。なお、プログラムの実行がアドレスｂを通過してからアドレスａに到達するまでの所要時間を、時間ｔとする。
【００１５】
図２は、プログラムの実行前にメモリ内に準備しておく表の構成例を示している。本表２には、「ループ名」と「実行時間」が示され、プログラム内に存在する各並列ループと、ループ本体の実行時間（並列化しない場合）の対応が表記されている。なお、実行時間が事前に分からない場合は、プログラムの実行中に値を記入してもよい。
【００１６】
図３は、プログラムの実行中に作成される表の構成例を示している。本表は、アドレス間距離（ｂ−ａ）と、所要時間（ｔ）との対応表として構成される。
上記構成表は、プログラムの実行時に動的に作成される表であり、アドレスｂとアドレスａの差（ｂ−ａ）／（これをアドレス間距離と呼ぶ）と、所要時間（ｔ）の対応を順次記録してゆくことにより得られる表である。
【００１７】
（動作例）
本実施形態の動作例を、プログラム内の、あるループｌｏｏｐｎ　を例に採って説明する。実行時にあるスレッドが、最初にｌｏｏｐｎ　の先頭アドレスａに到達する。この時に、他の各スレッドｉについて次の処理を行う。
すなわち、スレッドｉが実行しているアドレスｂとアドレスａとの差を、図３の表のアドレス間距離（ｂ−ａ）欄に記入する。なお、その時の時刻を時刻ｔ１　とする。
【００１８】
そして、同じスレッドｉでの処理が進行し、アドレスａに到達した時刻を時刻ｔ２　とし、時刻間差ｔ２　−ｔ１　を、図３の先程記録したｂ−ａ欄に対応する所要時間（ｔ）欄に記入する。この処理は、スレッド数をｍとすると、０　≦ｉ＜ｍなるスレッドｉに対してそれぞれ行う。
【００１９】
このようにして、アドレス間距離（ｂ−ａ）と所要時間（ｔ）の組を採取してゆくと、両者は比例する傾向を示す。そこで、最小二乗法によってアドレス間距離から所要時間を算出する一次関数を求め、これを関数ｆ（ｔ）とする。
【００２０】
プログラムの実行が更に進行し、再び同じループｌｏｏｐｎ　を実行する際に、各スレッドに割り当てるループの最適の仕事量を算出するには、次のようにする。
並列処理を行っているｍ個のスレッドのうち、いずれか一つがアドレスａに到達した時のスレッドｉ（０≦ｉ＜ｍ）におけるスレッド間距離（ｂ−ａ）を求め、これをｄ　ｉ　とする。この場合、最初にアドレスａに到達したスレッドについては、ｄ　ｉ　＝０であり、他のスレッドについては、ｄ　ｉ　＞０である。また、当該ループの実行時間を図２から求め、この値を時間ｔｓ　とする。
【００２１】
値ｇ　ｉ　＝（　ｔｓ　＋（ｆ（ｄ０）＋ｆ（ｄ１）　＋…＋ｆ（ｄ　ｍ−１））−ｍｆ（ｄ　ｉ　））／ｍを考え、これをスレッドｉに割り当てる仕事量とする。ここで、ｇ０＋ｇ１＋…＋ｇ　ｍ−１　＝ｔｓ　が成り立っている。このように割り当てると、アドレスａに早く到達したスレッドには多くの仕事が、また、遅く到達したスレッドには少ない仕事がそれぞれ割り当てられ、ループの出口でスレッドの進行を揃えることが出来る。
【００２２】
（効果）
プログラム実行時に、ループの入口に到達した時の各スレッドの進行状況に応じて動的にループ実行分担の最適化が行われる。このため、コンパイル時にスケジューリングを行う方法に比べて柔軟性が高い。
【００２３】
また、各スレッドの処理が揃えるに際し、ループ出入口で同期をとる必要がなく、実行性能上有利である。
【００２４】
（他の実施例）
上記発明の実施例の動作の説明で記した方法は、関数ｆ（ｔ）の生成に用いるループと最適化対象のループが同一である。
【００２５】
しかし、アドレス間距離（ｂ−ａ）と所要時間（ｔ）の関係は、ハードウェアの性質によってのみ決まり、ループの種類とは無関係である。このため、関数ｆ（ｔ）の生成に用いたループと最適化対象のループは、異なっていても構わない。つまり、図２の表に追記するデータは、特定のループに依存せず、プログラム内の全ループ共通に使うことができる。
【００２６】
なお、上述の実施形態は本発明の好適な実施の一例である。ただし、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施が可能である。
【００２７】
【発明の効果】
以上の説明より明らかなように、本発明のアプリケーションの並列処理方法は、１つのアプリケーションの処理を複数に分割して並列的に実行するスレッド処理に係わり、並列化したループの入口のアドレスであるアドレスａに、より早く到達したスレッドＡにはより多くの仕事を割り当て、より遅く到達したスレッドＢにはより少ない仕事を割り当て、処理を実行するためのスケジューリングを動的に実行する。これにより、スレッドＡとスレッドＢの並列処理における、ループの出口での進行時間の統一化を図ることができる。
【図面の簡単な説明】
【図１】本発明のアプリケーションの並列処理方法の実施形態が適用されるプログラム内の一つの並列化ループ周辺のメモリマップの構成例を示す。
【図２】プログラムの実行前にメモリ内に準備しておく表の構成例を示している。
【図３】プログラムの実行中に作成される表の構成例を示している。
【符号の説明】
ａ　並列化ループの入口のアドレス
ｂ　アドレスａより若いアドレス
ｔ　所要時間
【図１】
2004078617.tif 000003
【図２】
2004078617.tif 000004
【図３】
2004078617.tif 000005