(57)【特許請求の範囲】
【請求項１】
１のノードにおいて複数のプロシージャを並行に処理しながら、かつ、その処理結果のデータを１のノードから他のノードへ送信しながら、マルチノードにわたり分散して並行に処理されている複数のプロシージャと調和させる方法であって、
各ノードは、単数または複数のＣＰＵと、単数または複数のＣＰＵによって共有されるメモリと、他のノードとの間をインターコネクトする通信コントローラとを有していて、単数または複数のＣＰＵまたは通信コントローラが、各ノード内に用意された所定の数のスレッドから構成されるマルチスレッドの各々にわたって複数のプロシージャを並行なスケジューリングとして割り当てるものであって、前記方法は、
１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、１のプロシージャの処理結果のデータを、その１のスレッドからメモリ内に用意されている送信バッファ (send buffer) 内におけるスレッドＩＤに対応する位置に書き込み、保存するステップと、
１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、その１のスレッドからメモリ内に用意されている送信カウンタ (send counter) に完了の通知をするステップと、
完了の通知のたびに、送信カウンタにおけるカウントの数を増加するステップと、
送信カウンタにおけるカウントの数が、マルチスレッドを構成するスレッドの所定の数に達した場合には、マルチスレッドを構成しているスレッドのうちでも最後に完了の通知を行った１つのスレッドが、次のプロシージャを処理する前に、送信バッファに保存されているマルチスレッドにわたる処理結果のデータの全てを、他のノードに送信するステップとを有する、
方法。
【請求項２】
１のプロシージャにおいて、処理結果のデータを送信バッファに書き込みを完了し、かつ、送信カウンタに完了の通知をしたら、（全てのマルチスレッドとの間でのバリア同期を待つことなく、または、送信バッファにマルチスレッドにわたる処理結果のデータの全て書き込まれる前に）スケジューリングされている次のプロシージャが受信データに依存しない（非依存）プロシージャである場合には、次のプロシージャの処理を開始するステップとを有する、
請求項１に記載の方法。
【請求項３】
次のプロシージャが受信データに依存するプロシージャである場合には、当該受信データに依存するプロシージャのために必要となるデータの部分が受信バッファ (receive buffer) に現れるまで待つ（次の処理を開始しない）、
請求項１に記載の方法。
【請求項４】
１のプロシージャにおいて、処理結果のデータを送信バッファに書き込みを完了したら、（全てのマルチスレッドとの間でのバリア同期を待つことなく、または、送信バッファにマルチスレッドにわたる処理結果のデータの全て書き込まれる前に）次のプロシージャが受信データに依存しない（非依存）プロシージャである場合には、次のプロシージャの処理を開始するステップとを有する、
請求項１に記載の方法。
【請求項５】
１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、メモリ内に用意されているところのその１のスレッドのためのフェーズ・カウンタ (phase counter)におけるカウントの数を増加するステップと、
増加したカウントの数を、１のプロシージャの完了時点におけるカウントの数として、各スレッドに対応して用意されているところのローカル変数を保存する領域に書き込み保存するステップと、
あるスレッドにおいてローカル変数を保存する領域に書き込まれている値と、そのあるスレッドに依存するスレッドのフェーズ・カウンタの値とを比較するステップと、
比較の結果、フェーズ・カウンタの値と同じになるか、または、フェーズ・カウンタの値の方が大きくなるまで待つ、（そのあるスレッドにおいてスケジューリングされている次の処理を開始しない）、
請求項１に記載の方法。
【請求項６】
１のノードにおいて複数のプロシージャを並行に処理しながら、かつ、その処理結果のデータを１のノードから他のノードへ送信しながら、マルチノードにわたり分散して並行に処理されている複数のプロシージャと調和させるシステムであって、
各ノードは、単数または複数のＣＰＵと、単数または複数のＣＰＵによって共有されるメモリと、他のノードとの間をインターコネクトする通信コントローラとを有していて、単数または複数のＣＰＵまたは通信コントローラが、各ノード内に用意された所定の数のスレッドから構成されるマルチスレッドの各々にわたって複数のプロシージャを並行なスケジューリングとして割り当てるものであって、前記システムは、
１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、１のプロシージャの処理結果のデータを、その１のスレッドからメモリ内に用意されている送信バッファ (send buffer) 内におけるスレッドＩＤに対応する位置に書き込み、保存し、
１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、その１のスレッドからメモリ内に用意されている送信カウンタ (send counter) に完了の通知をし、
完了の通知のたびに、送信カウンタにおけるカウントの数を増加し、
送信カウンタにおけるカウントの数が、マルチスレッドを構成するスレッドの所定の数に達した場合には、マルチスレッドを構成しているスレッドのうちでも最後に完了の通知を行った１つのスレッドが、次のプロシージャを処理する前に、送信バッファに保存されているマルチスレッドにわたる処理結果のデータの全てを、他のノードに送信する、
システム。
【請求項７】
１のノードにおいて複数のプロシージャを並行に処理しながら、かつ、その処理結果のデータを１のノードから他のノードへ送信しながら、マルチノードにわたり分散して並行に処理されている複数のプロシージャと調和させる処理を、コンピュータに実行させるためのプログラムであって、
各ノードは、単数または複数のＣＰＵと、単数または複数のＣＰＵによって共有されるメモリと、他のノードとの間をインターコネクトする通信コントローラとを有していて、単数または複数のＣＰＵまたは通信コントローラが、各ノード内に用意された所定の数のスレッドから構成されるマルチスレッドの各々にわたって複数のプロシージャを並行なスケジューリングとして割り当てるものであって、前記プログラムは、
１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、１のプロシージャの処理結果のデータを、その１のスレッドからメモリ内に用意されている送信バッファ (send buffer) 内におけるスレッドＩＤに対応する位置に書き込み、保存するステップと、
１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、その１のスレッドからメモリ内に用意されている送信カウンタ (send counter) に完了の通知をするステップと、
完了の通知のたびに、送信カウンタにおけるカウントの数を増加するステップと、
送信カウンタにおけるカウントの数が、マルチスレッドを構成するスレッドの所定の数に達した場合には、マルチスレッドを構成しているスレッドのうちでも最後に完了の通知を行った１つのスレッドが、次のプロシージャを処理する前に、送信バッファに保存されているマルチスレッドにわたる処理結果のデータの全てを、他のノードに送信するステップとを、コンピュータに実行させる、
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチノードにわたるコンピュータ計算の並列処理に関し、より詳しくは、１のノードにおいて複数のプロシージャを並行に処理しながら、かつ、その処理結果のデータを１のノードから他のノードへ送信しながら、マルチノードにわたり分散して並行に処理されている複数のプロシージャとの間で調和を図ることに関する。
【背景技術】
【０００２】
図１は、各ノード間がインターコネクトされたマルチノードシステムを示す模式図である。各ノードは、単数または複数のＣＰＵ（ここでは、４つのＣＰＵ、例えば、４つのＭｕｌｔｉ−ｃｏｒｅ  Ｐｒｏｃｅｓｓｏｒｓ）と、単数または複数のＣＰＵによって共有されるメモリ（処理速度を速めるためにｄａｔａ  ｃａｃｈｅに分かれている場合を含む）と、他のノードとの間をインターコネクトする通信コントローラ（ＣＣ：Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｃｏｎｔｒｏｌｌｅｒ）とを有している。
【０００３】
マルチノードを形成している各ノード間は、通信コントローラ（ＣＣ）を介して接続されている。あるノードにおける処理結果のデータが、他のノードへと送信される。実際に送信を行う主体は、通信コントローラであってもよいし、複数のＣＰＵのうちの何れかのＣＰＵであってもよく、かかる場合には通信コントローラは必須の構成ではない。また、（何れかの）ＣＰＵは命令を発するだけで、その命令に通信コントローラが従うという構成にしてもよい。
【０００４】
図２は、ＣＰＵからの送信命令に従って、マルチノードにわたって１のノードから他のノードへデータの非同期送信を行うことを示す模式図である。ノ−ド１のＣＰＵから通信コントローラに対して「（ノード１の）メモリ中のアレイ１から、ノード２のメモリ中のアレイ２へ、データを送信せよ」という送信命令が発せられると、通信コントローラ１がその送信命令に従い、メモリ中のアレイ１から送信データを呼び出し、インターコネクトされている通信コントローラ１と通信コントローラ２を通じて、通信コントローラ２がノード２のメモリ中のアレイ２へ受信データを記憶する。
【０００５】
この際、ノード２の側では、ノード１から送信されてきたデータについて、受信したデータのバイト数を、または、データを受信した回数を、ノード２に用意されている受信カウンタがカウントすることができる。このように、マルチノードにわたり分散して並行に処理されながらも、適宜ノード間で送受信がされながら、調和が図られている。
【０００６】
図３は、従来技術における非同期送信を使った場合のノード間（１のノードと他のノードとの間）でデータの交換を行うＳＭＰ（Ｓｈａｒｅｄ  Ｍｅｍｏｒｙ  Ｍｕｌｔｉ−ｔｈｒｅａｄ／Ｍｕｌｔｉ−ｃｏｒｅ  Ｐｒｏｃｅｓｓｏｒｓ）プログラムの同期の方法の例を示す模式図である。
【０００７】
この図が示すように、１のノード内においては、そのノード内に用意されたマルチスレッドの各々にわたって複数のプロシージャが並行なスケジューリングとして割り当てられる。マルチスレッドを構成する各スレッドに分けて処理を並行に処理して、それらの処理結果のデータをまとめる。スレッド自体がそこにスケジューリングされているプロシージャを処理する主体、送受信する主体になり得る。
【０００８】
ここでは、マルチスレッド（Ｍｕｌｔｉ−ｔｈｒｅａｄ）として４つのスレッドであり、４つのＭｕｌｔｉ−ｃｏｒｅ  Ｐｒｏｃｅｓｓｏｒｓである、という例をもって説明する。しかし、ハードウエアとして複数のＣＰＵの数が４つであるからといって、マルチスレッドの数が同じ４つであるとは限らない。ハードウエアとソフトウエアとを組み合わせて利用した（仮想的な）ＣＰＵ利用の単位として、任意の所定の数のスレッドから構成されるマルチスレッドに設定することができることが知られている。
【０００９】
この図の例では、ベースとなるＣＰＵ動作クロック等のタイムステップにペースをあわせて、左から右へと処理が進んでいく。スレッド（Ｔｈｒｅａｄ）１〜４において、プロシージャ（Ｐｒｏｃｅｄｕｒｅ）１が、並行なスケジューリングとして割り当てられて処理が進行している状況にある。スレッド１〜４においてスケジューリングされているプロシージャ１は、データを作成する処理を行っているが、処理結果であるデータ（ｄａｔａ）１〜４は、送信バッファ（ｓｅｎｄ  ｂｕｆｆｅｒ）内におけるスレッドＩＤに対応する位置に書き込み保存される。
【００１０】
従来技術においては、すべてのスレッド１〜４が送信バッファにデータを書き込んだことを保証するために、すべてのマルチスレッドを構成するすべてのスレッド１〜４との間でのスレッド・バリア（ｔｈｒｅａｄ  ｂａｒｒｉｅｒ）を張るというバリア同期を行う。そして、この例では、スレッド１が、１のノードのスレッド１〜４を代表して、非同期通信を開始している。送信（Ｓｅｎｄ）の命令によって、送信バッファに保存されているマルチスレッドにわたる処理結果のデータの全てを、他のノードに送信する。送信（Ｓｅｎｄ）の命令を、スレッド１が自ら実行するにしても、その命令に通信コントローラを従わせるにしても、送信の処理のためには一定の時間がかかってしまう。
【００１１】
また、従来技術においては、他のノードにおける処理結果であるデータ（ｄａｔａ）１〜４が、他のノードから受信され、その受信が完了したことを各スレッド１〜４が知るために、スレッド１〜４との間でのスレッド・バリア（ｔｈｒｅａｄ  ｂａｒｒｉｅｒ）を張るというバリア同期を行っている。この図の例では、スレッド１がプロシージャ２の処理を最も早く終わっているので、データが受信されているかどうかの問い合わせを、スレッド１が実行している。この間、スレッド１は処理を待たなければならず、その待ち時間が受信待ち（Ｗａｉｔ  ｆｏｒ  Ｒｅｃｅｉｖｅ）として示されている。
【００１２】
このため、たとえ、他のスレッド２〜４がプロシージャ２の処理をし終わっていても、スレッド１においてはプロシージャ２の処理が終了していないという状況が起り得る。この図の例では、スレッド１が送信の処理を行う時間と、スレッド１が受信待ちをする時間とを足した分の時間だけ、他のスレッド２〜４には、アイドリングの状態（Ｔｈｒｅａｄｓ  ａｒｅ  ｉｄｌｉｎｇ）が生まれてしまい、並行処理を有効に活用できていない状況が生まれてしまっている。
【００１３】
また、この１のノードが他のノードから処理結果のデータを受信するという側の立場になる場合がある。例えば、プロシージャ３が他のノードから受信したデータを利用して計算を行うプロシージャである場合、すなわち、受信データに依存するプロシージャである場合には、必要となるデータ（の部分）が受信バッファ（ｒｅｃｅｉｖｅ  ｂｕｆｆｅｒ）に現れるまで待つ必要がある。このような依存（依存する）・非依存（依存しない）は、典型的には、次に説明するような計算の場合に現れる。
【００１４】
図４は、有限差分法（Ｆｉｎｉｔｅ  Ｄｉｆｆｅｒｅｎｃｅ  Ｍｅｔｈｏｄ）において、スレッド間同期を必要とする処理と、スレッド間同期を必要としない処理とを示す、計算例を示す図である。ここでは、Ｘ方向とＹ方向とに２次元に離散化された格子のうち、１つのノードに４（Ｘ方向）×４（Ｙ方向）の格子を割り当て、隣接する格子点間で差分を取る分散処理並列化を行うものとすると、図４（Ａ）のように、ノード１とノード２という隣接する２つのノード同士で、グレーの格子に相当する境界部分のデータを交換して利用しあう必要がある。グレー格子に相当する境界部分のデータが相互に依存関係にあるということになる。
【００１５】
図４（Ｂ）のように、Ｘ方向の処理とＹ方向の処理とを進めるものとする。Ｙ方向にデータを分割してＳＭＰ並列化を行うものとする。図３にあてはめて考えると、このときのＸ方向の処理は、図３におけるプロシージャ１が、境界データを送信バッファにコピーする処理に相当する。図３におけるプロシ−ジャ２が、白い格子点において差分をとる処理に相当する。図３におけるプロシージャ３が、隣のノード（他のノード）からのデータを受信する処理に相当し、他のノードから受信したデータを利用して計算を行うプロシージャとして、隣接する２つのノード同士での境界データの差分をとる処理に相当する。
【００１６】
このようにＸ方向で差分をとる処理は、スレッド１〜４の間でデータ独立であるので同期を取る必要はない。一方で、Ｙ方向で差分をとる処理は、スレッド１〜４の間でバリア同期をとらないと、同じ時間ステップのデータで正しく差分がとれている保証ができないことになる。この点、従来技術の手法では、通信のたびにバリア同期を行っているため、特に意識しなくても正しいタイムステップになっていたものである。
【００１７】
特許文献１は、並列処理でスレッド間のバリア同期を行う従来技術の一例である。この他にも、バリア同期を行う技術は数多い。
【００１８】
その他、従来技術には、スレッド・レベルにおける投機的（Ｓｐｅｃｕｌａｔｉｖｅ）な同期処理を行っている技術がある。しかし、マルチスレッドを構成する複数のスレッド全体でのスレッド間バリア同期に相当するものを完全に取り除くことを実現している技術は見当たらない。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特許第４４４８７８４号公報
【発明の概要】
【発明が解決しようとする課題】
【００２０】
本発明の目的は、マルチノードにわたり分散して並行に処理されている複数のプロシージャを調和させるにあたり、マルチスレッドを構成するスレッド間でのバリア同期を完全に取り除き、複数のノード間のデータの送受信（非同期通信）を実現することにある。
【課題を解決するための手段】
【００２１】
非同期送信前のバリア同期を取り除き、送信カウンタ (send counter) を導入し、カウンタの値が所定の値に達したときに、送信カウンタが準備完了とする。
【００２２】
受信待ち後のバリア同期を取り除き、マルチスレッドを構成するそれぞれのスレッドが自分の必要なデータが受信されるまで待つようにする。
【００２３】
マルチスレッドを構成するスレッドの間で依存性のある処理を行う場合に、整合性をとるためにフェーズ・カウンタ (phase counter) を導入し、依存しあうスレッド間でタイムステップを保証する。
【発明の効果】
【００２４】
あるスレッドにおいて非同期送信を開始させる処理のオーバーヘッドを、他のスレッドの処理時間の後ろに隠すことができる。
【００２５】
受信待ちの処理時間を、各スレッドに必要な最小限の時間に短縮することができる。
【００２６】
スレッド間で依存性のあるデータを参照する場合には、スレッドの全体でスレッド間バリア同期を取ることなく、必要な最小限のオーバーヘッドで済むようにすることができる。
【図面の簡単な説明】
【００２７】
【図１】図１は、各ノード間がインターコネクトされたマルチノードシステムを示す模式図である。
【図２】図２は、ＣＰＵからの送信命令に従って、マルチノードにわたって１のノードから他のノードへデータの非同期送信を行うことを示す模式図である。
【図３】図３は、従来技術における非同期送信を使った場合のノード間（１のノードと他のノードとの間）でデータの交換を行うＳＭＰ（Ｓｈａｒｅｄ  Ｍｅｍｏｒｙ  Ｍｕｌｔｉ−ｔｈｒｅａｄ／Ｍｕｌｔｉ−ｃｏｒｅ  Ｐｒｏｃｅｓｓｏｒｓ）プログラムの同期の方法の例を示す模式図である。
【図４】図４は、有限差分法（Ｆｉｎｉｔｅ  Ｄｉｆｆｅｒｅｎｃｅ  Ｍｅｔｈｏｄ）において、スレッド間同期を必要とする処理と、スレッド間同期を必要としない処理とを示す、計算例を示す図である。
【図５】図５は、本発明を実行するための、各ノード間がインターコネクトされたマルチノードシステムであって、メモリ内に用意されている記憶領域の構成を示す模式図である。
【図６】図６は、本発明の非同期送信を使った場合のノード間（１のノードと他のノードとの間）でデータの交換を行うＳＭＰプログラムの同期の方法を示す模式図である。
【図７】図７は、スレッド間依存データを処理するべく、依存しあうスレッド間でタイムステップを保証するための、フェーズ・カウンタを利用した同期の方法を示す模式図である。
【図８】図８は、データを送信する処理を示すフローチャートである。
【図９】図９は、受信データを待つ処理を示すフローチャートである。
【図１０】図１０は、フェーズ・カウンタを利用する処理を示すフローチャートである。
【図１１】図１１は、本発明の効果を示す実験例をまとめたものである。
【発明を実施するための形態】
【００２８】
図５は、本発明を実行するための、各ノード間がインターコネクトされたマルチノードシステムであって、メモリ内に用意されている記憶領域の構成を示す模式図である。
【００２９】
メモリ内には、送信カウンタ、受信カウンタ、フェーズ・カウンタ、ローカル変数を保存する領域、送信バッファ、受信バッファという構成が用意されている。本発明の全てにおいて、これら構成の全てが必要なわけではない。特許請求の範囲の各請求項における独立項、従属項、において、必要に応じて個別に記載されている。
【００３０】
図６は、本発明の非同期送信を使った場合のノード間（１のノードと他のノードとの間）でデータの交換を行うＳＭＰプログラムの同期の方法を示す模式図である。図３において説明した従来技術の内容から、スレッド・バリア（ｔｈｒｅａｄ  ｂａｒｒｉｅｒ）を張るバリア同期を取り除いたものであるため、図６の特徴を理解するにあたっては、図３と比較すると理解し易い。
【００３１】
処理結果であるデータ（ｄａｔａ）１〜４が、送信バッファ（ｓｅｎｄ  ｂｕｆｆｅｒ）内におけるスレッドＩＤに対応する位置に書き込み保存されることは、図３と同様である。１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、１のプロシージャの処理結果のデータを、その１のスレッドからメモリ内に用意されている送信バッファ (send buffer) 内におけるスレッドＩＤに対応する位置に書き込み、保存する。これらの構成は図３と同様であるので、煩雑さを回避するために、ここでは図解を省略する。
【００３２】
しかし、本発明の方法では、１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、その１のスレッドからメモリ内に用意されている送信カウンタ (send counter) に完了の通知をする、という構成を採用している。
【００３３】
また、本発明の方法では、さらに、各スレッドからの完了の通知によって、送信カウンタにおけるカウントの数を増加する、という構成を採用している。このような単純なカウンタを採用しなくても、マルチスレッドを構成するスレッドの全てのプロシージャが完了したことを把握できるようになっていればよく、当業者であれば、本発明の技術的思想の範囲内において、様々な変更を採用することができるであろう。
【００３４】
送信（Ｓｅｎｄ）の命令によって、送信バッファに保存されているマルチスレッドにわたる処理結果のデータの全てを、他のノードに送信することは、図３と同様であるので、ここでは図解を省略する。
【００３５】
しかし、本発明の方法では、マルチスレッドを構成しているスレッドのうちでも最後に完了の通知を行ったスレッドが、次のプロシージャを処理する前に、送信バッファに保存されているマルチスレッドにわたる処理結果のデータの全てを、他のノードに送信する、という構成を採用している。
【００３６】
本発明の方法では、１のプロシージャにおいて、処理結果のデータを送信バッファに書き込みを完了し、かつ、送信カウンタに完了の通知をしたら、（全てのマルチスレッドとの間での従来技術のようなバリア同期を待つことなく、または、送信バッファにマルチスレッドにわたる処理結果のデータの全てが書き込まれるという状態に至る前に）スケジューリングされている次のプロシージャが受信データに依存しない（非依存）プロシージャの場合には、そのプロシージャの処理を開始することができる。
【００３７】
この例では、スレッド１〜３は、プロシージャ１の処理について、処理結果のデータを送信バッファに書き込みを完了し、かつ、送信カウンタに完了の通知をしたら、直ちに、次の処理であるプロシージャ２の処理を開始することができる。
【００３８】
ただし、次のプロシージャが受信データに依存するプロシージャである場合には、他のノードから送信されてくる受信データを待つ（Ｗａｉｔ）必要がある。それぞれのスレッド１〜４が自分に必要なデータが受信バッファ (ｒｅｃｅｉｖｅ  ｂｕｆｆｅｒ） に現れるまで待つ（次の処理を開始しない）ことになる。この際、受信カウンタ（ｒｅｃｅｉｖｅ  ｃｏｕｎｔｅｒ）を利用して、受信バッファに受信したバイト数を知ることができるので、自分に必要なデータが現れているかどうかを把握することができる。
【００３９】
この例では、各スレッドにおいてプロシージャ３の処理が開始する箇所が、スレッド１〜４にわたって右斜め下に向かって階段状になっているが、スレッド１が最初に、スレッド２がその次に、スレッド３がその次に、スレッド４が最後に、受信バッファにおいて順にデータを受信するように設計されている一例を示しているにすぎない。スレッド１〜４が受信する方式は、スレッド１〜４がばらばらに分けて受信できるように設計にして、自分に必要なデータがいち早く現れるように設計してもよく、当業者であれば様々な方式を設計して採用することができる。
【００４０】
スレッド２におけるプロシージャ２が終了する箇所と、スレッド１におけるプロシージャ４が開始する箇所とは点線の矢印で結ばれている。さらには、スレッド４におけるプロシージャ２が終了する箇所と、スレッド１におけるプロシージャ４が開始する箇所とも点線の矢印で結ばれている。これらの点線は、スレッド間依存関係のあることを示すものである。
【００４１】
すなわち、この例では、プロシージャ４はスレッド間依存のデータであって、スレッド１におけるプロシージャ４は、スレッド２におけるプロシージャ２の結果を使用するため、続いて図７において説明するところの、フェーズ・カウンタ（ｐｈａｓｅ  ｃｏｕｎｔｅｒ）を利用して同期をとる。
【００４２】
図７は、スレッド間依存データを処理するべく、依存しあうスレッド間でタイムステップを保証するための、フェーズ・カウンタを利用した同期の方法を示す模式図である。ここでも「同期」という表現を用いるが、実際には、「同期」というよりも、確実に正しいデータが参照できるように整合性を保証するためのものである。このために、待ち時間やオーバーヘッドはほとんど発生しない。
【００４３】
これは、図４の（Ｂ）において既に説明したところの、有限差分法の例におけるＹ方向で差分をとる処理（隣接する上と隣接する下とを参照するような関係に相当する）に相当しており、スレッド１〜４の間で、同じ時間ステップのデータで正しく差分がとれている保証をするものである。
【００４４】
１のスレッドにおいてスケジューリングされている１のプロシージャが完了した場合には、まず、以降の時間の進行において、スレッド間でデータ依存のある処理で使うデータをメモリに保存する。次に、メモリ内に用意されているところの、その１のスレッドのためのフェーズ・カウンタ (phase counter)におけるカウントの数を増加する。ここでは、まずスレッド１がプロシージャ２を終了して、カウントの数を増加（＋１）する。次に、少し遅れてからスレッド２が、さらに遅れてからスレッド４がプロシージャ２を終了して、それぞれでカウントの数を増加（＋１）する。
【００４５】
スレッド１では、増加したカウントの数を、プロシージャ２の終了時点におけるカウントの数として、各スレッドに対応して用意されているローカル変数を保存する領域に書き込み保存する。
【００４６】
あるスレッドにおいて、ローカル変数を保存する領域に書き込まれている値と、そのあるスレッドに依存するスレッドのフェーズ・カウンタの値とを比較する。比較の結果、フェーズ・カウンタの値と同じになるか、または、フェーズ・カウンタの値の方が大きくなるまで待つ（そのあるスレッドにおいてスケジューリングされている次の処理を開始しない）。
【００４７】
図８は、データを送信する処理を示すフローチャートである。今までの処理をここにまとめておく。１００において、データを送信する処理に入る。１１０において、送信カウンタの値を増加する。１２０において、送信カウンタの値がマルチスレッドを構成するスレッドの所定の数に達したかどうかを判断する。もし、所定の数に達していた場合には、１３０において、送信命令を発して、送信バッファに保存されているデータを送信する。１５０において、次のプロシージャへ進む。
【００４８】
図９は、受信データを待つ処理を示すフローチャートである。２１０において、受信データを待つ処理を開始する。２２０において受信カウンタにおいて必要となるデータの部分が現れたかどうかを判断する。もし現れた場合には、２３０において、次のプロシージャへ進む。
【００４９】
図１０は、フェーズ・カウンタを利用する処理を示すフローチャートである。３１０において、フェーズ・カウンタを利用する処理を開始する。３２０において、スレッド間依存プロシージャの処理を行う。３３０において、このスレッドのフェーズ・カウンタの値を増加する。３４０において、フェーズ・カウンタの値をｔとしてローカル変数を保存する領域に書き込む。３５０において、スレッド間非依存プロシージャの処理を行う。３６０において、ある依存スレッドの数にわたってループを繰り返すことを始めるが、３７０において、依存するスレッドについてのフェーズ・カウンタの値ｉ≧ｔであるかどうかを判断し、そうである場合は、３８０において次の依存スレッドについて、３６０〜３８０のループを繰り返す。３９０において、次のプロシージャへ進む。
【００５０】
図１１は、本発明の効果を示す実験例をまとめたものである。条件としては、格子（ｌａｔｔｉｃｅ）ＱＣＤシミュレーションにおける反復計算の例（ＢｉＣＧ  Ｓｔａｂ  Ｓｏｌｖｅｒ）であり、４次元格子としてＸＹＺ方向を分散メモリ並列化して、Ｔ方向をＳＭＰ並列化している。並列計算機は、Ｂｌｕｅ  Ｇｅｎｅ／Ｐ（ＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標）の５１２ノードを使用した。ＸＹＺ方向に境界データを交換して、Ｔ方向の差分をとる場合にスレッド間のデータ依存性があるものである。バリア同期のある従来技術に比較して、本発明の手法を用いると、処理時間について、３０．６％、２０．１％という改善が図られている。
【図１】
0005623187.tif 000002
【図２】
0005623187.tif 000003
【図３】
0005623187.tif 000004
【図４】
0005623187.tif 000005
【図５】
0005623187.tif 000006
【図６】
0005623187.tif 000007
【図７】
0005623187.tif 000008
【図８】
0005623187.tif 000009
【図９】
0005623187.tif 000010
【図１０】
0005623187.tif 000011
【図１１】
0005623187.tif 000012