(57)【要約】  本発明にかかるデータ処理方法は、入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる。これにより、データの依存関係を有するスレッドを実行する場合に、データのロック／アンロックをすることなく、排他的なデータアクセスを保証でき、かつ、データ転送コストを削減することができる。
2012049791.tif 000002
【特許請求の範囲】
【請求項１】
入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる、
ことを特徴とする、データ処理方法。
【請求項２】
前記第一のスレッドおよび前記第二のスレッドは、それぞれ別のスレッドであり、
前記第一のスレッドが、当該第一のスレッドに入力データを供給するスレッドから送信された制御信号を受信したのちに、当該入力データを使って演算を実行し、当該演算の結果を前記第三のスレッドに供給する入力データとして当該制御信号が指定するデータ領域に格納し、前記第三のスレッドへ当該制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行うか、又は、前記第二のスレッドが、前記第三のスレッドから送信された制御信号を受信したのちに、当該制御信号が指定するデータ領域に格納された演算の結果を入力データとして使って演算を実行し、当該演算の結果を当該制御信号が指定するデータ領域に格納し、当該結果を使用するスレッドへ当該制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う、
ことを特徴とする、請求項１に記載のデータ処理方法。
【請求項３】
前記第三のスレッドは、前記制御信号の送信において、前記第二のスレッドが前記制御信号を受信するまで待ち合わせる、
ことを特徴とする、請求項２に記載のデータ処理方法。
【請求項４】
前記第一のスレッドが前記第三のスレッドへ送信する前記制御信号の値を切り替えることによって、前記第三のスレッドが少なくとも二つのデータ領域へ演算結果を書き込むようにする、
ことを特徴とする、請求項３に記載のデータ処理方法。
【請求項５】
データを記憶するためのデータ領域をもつ記憶手段と、
入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる実行手段と、
を備えることを特徴とする、データ処理装置。
【請求項６】
データを記憶するためのデータ領域をもつコンピュータを、
入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる手段、
として機能させることを特徴とする、データ処理プログラムが格納された非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理方法、データ処理装置及びデータ処理プログラムが格納された非一時的なコンピュータ可読媒体に関し、特に、データの依存関係をもつ複数のスレッドを並列実行する技術に関する。
【背景技術】
【０００２】
並列プログラムにおける処理の単位はスレッドである。並列プログラムでは複数のスレッドが同時に並行的に動作する。それらのスレッドが連携して処理を行うことにより並列プログラムが動作する。スレッドは、他のスレッドと連携して動作するために、それぞれのスレッドからアクセス可能な共有メモリにおける共有データを使用する。共有データは、全てのスレッドがアクセス可能な共有メモリに配置される。複数のスレッドが同じメモリ領域をアクセスする場合には、一般的には、排他的なデータアクセスを保証するためにロック／アンロック機構が使われる。しかし、ロック／アンロックには二つの問題がある。【０００３】
まず、ロック／アンロックは並列性を損なう処理である。ロック／アンロックは、変数や配列などの複数のデータを含む所定のデータ領域に対して行われるのが一般的である。あるデータ領域にロックをかけると、そのデータ領域にはロックをかけたスレッドだけがアクセス可能で、他のスレッドはアクセスできない。ロック／アンロックによって一部のデータアクセスの並列性が失われるのはしかたがないが、ロック／アンロックが多用されると多くのデータアクセスにおいて並列性が失われてしまう。その結果、ロック／アンロックの多用はパフォーマンス低下につながる。【０００４】
次に、ロック／アンロックはうまく使うのが難しい処理である。複数のデータを扱う複数のスレッドがある場合に、各データに個別にロックをかけると、簡単にデッドロックが発生する。デッドロックとは、複数のスレッドが互いに獲得済みのロックを奪い合おうとして、処理が先に進まなくなってしまう状況のことである。デッドロックを避けるには、データの使い方に合わせて、どのようにロック／アンロック機構を使うかを慎重に決める必要がある。 【０００５】
ロック／アンロックを避けるための方法として、スレッドが使用するデータにもとづいてデータフローを考え、そのデータフローにもとづいてスレッドの実行順序を決める、という方法がある。この方法では、データフローが示すデータの依存関係にもとづいてスレッドの実行順序を制御する。つまり、あるスレッドが演算を実行した後に、そのスレッドの演算結果を使用して演算を行うスレッドを実行するように、スレッドの実行順序を制御する。このスレッドの実行順序制御のおかげで、スレッドはデータに安全にアクセスでき、データのロック／アンロックが不要となる。【０００６】
データフローにもとづいてスレッドの実行順序を決めるという方法は、スレッドの実行順序制御が必要になるものの、不具合を起こす可能性がある危険なロック／アンロックを使わなくて済む。そのため、ロック／アンロックでデータアクセスを排他制御する方法よりも不具合を起こしにくいと言える。【０００７】
しかし、データフローにもとづいた方法にも課題がある。その課題とは、データの受け渡し方法である。【０００８】
データフローにもとづいてスレッドの実行順序を決める場合には、メッセージパッシングなどのスレッド間通信を使ってデータを直接スレッドからスレッドへ渡すことが一般的である。しかしながら、スレッド間でデータを直接転送するよりも、共有メモリを使ってスレッド間でデータを共有した方がデータ転送時間を小さくできる。共有メモリを使ったデータ受け渡しは確かに転送時間を小さくできるが、共有データへの排他的アクセスに問題が発生してしまう。なぜなら、共有データを読もうとするスレッドと、共有データを変更しようとするスレッドのふたつが同時に共有データへアクセスする可能性があるからである。スレッド間通信によるデータ受け渡しでは、データがコピーされるため、各スレッドはデータに排他的にアクセスできる。一方、共有メモリによるデータ受け渡しでは、データがコピーされないため、各スレッドはデータに排他的にアクセスできない。データをコピーすることは、転送時間と記憶領域の二つに関してデータ転送コストが大きい。共有メモリを利用して、かつデータをコピーせずに、効率よくスレッドからスレッドへデータを受け渡しする方法が必要となる。【０００９】
特許文献１には、共有メモリ領域をプロセスの仮想アドレスの一部として割り当て、割り当てた領域の先頭アドレスを、スレッドが使用するスタックの開始アドレスとしてスレッドを確立するプロセス間通信プログラムが開示されている。これによって、プロセス間通信を行うためのコピー処理を行わずに、他のプロセスからデータを参照することができるようにして、高速なプロセス間通信を行うことができるようにしている。しかし、特許文献１は、共有メモリ領域における排他的なデータアクセスを保証する技術を開示したものではない。つまり、特許文献１は、排他的なデータアクセスを保証でき、かつ、データ転送コストを削減することができる技術を開示したものではない。【００１０】
特許文献２には、到着したトークンがデータ値を含むデータトークンである場合は、データ値を予め定められた記憶装置中の領域に格納するトークンマッチング・ユニットと、他のタスクからのデータが全て揃って実行可能になったタスクをキューに格納する処理装置及び記憶装置と、他のタスクにトークンを送るファンアウト・ユニットと、からなるタスクレベルデータ駆動型計算機が開示されている。このデータ駆動型計算機によって、相互結合ネットワークにおける情報交換をタスク間の情報交換だけに限定して、ネットワークやメモリアクセスの負荷を低減している。このデータ駆動型計算機は、タスク間のデータと制御の流れをグラフで表現してタスクフロー図に変換しておき、トークンをグラフ上の枝に流すものである。しかし、データ値を含むデータトークンを送信しており、上述した内容と同様に、データ転送コストが多くなってしまっているという問題がある。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００３−２８０９３０号公報
【特許文献２】特開平０１−１０２６４５号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
背景技術として説明したように、データ共有のためスレッド間通信やコピーを行うとデータ転送に時間がかかる、という課題がある。【００１３】
本発明の目的は、上述した課題を解決するために、データの依存関係を有するスレッドを実行する場合に、データをロック／アンロックすることなく、排他的なデータアクセスを保証でき、かつ、データ転送コストを削減することができるデータ処理方法、データ処理装置及びデータ処理プログラムが格納された非一時的なコンピュータ可読媒体を提供することにある。
【課題を解決するための手段】
【００１４】
本発明の第１の態様にかかるデータ処理方法は、入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる、ことを特徴とするものである。【００１５】
本発明の第２の態様にかかるデータ処理装置は、データを記憶するためのデータ領域をもつ記憶部と、入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる実行部と、を備えることを特徴とするものである。【００１６】
本発明の第３の態様にかかるデータ処理プログラムが格納された非一時的なコンピュータ可読媒体は、データを記憶するためのデータ領域をもつコンピュータを、入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる手段、として機能させることを特徴とするものである。
【発明の効果】
【００１７】
上述した本発明の各態様により、データの依存関係を有するスレッドを実行する場合に、データをロック／アンロックすることなく、排他的なデータアクセスを保証でき、かつ、データ転送コストを削減することができるデータ処理方法、データ処理装置及びデータ処理プログラムが格納された非一時的なコンピュータ可読媒体を提供することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施の形態にかかるデータ処理装置の概要構成図である。
【図２】本発明の実施の形態にかかるデータ処理装置１の構成図である。
【図３】本発明の実施の形態における、スレッドの並列実行の概念を表す図である。
【図４】本発明の実施の形態において、スレッドの起動から終了までの流れを表す図である。
【図５】スレッドがシグナルの送受信に使用するチャネルのパラメータを表す図である。
【図６】スレッドがシグナルを別のスレッドへ送信する手順を表す図である。
【図７】スレッドがシグナルを別のスレッドから受信する手順を表す図である。
【図８】シグナルが複数のスレッドを伝搬していく様子を表す図である。
【図９Ａ】本発明の実施の形態にかかるデータ処理装置を使用して、複数のスレッドをパイプライン的に並列動作させる様子を表す図である。
【図９Ｂ】本発明の実施の形態にかかるデータ処理装置を使用して、複数のスレッドをパイプライン的に並列動作させる様子を表す図である。
【図９Ｃ】本発明の実施の形態にかかるデータ処理装置を使用して、複数のスレッドをパイプライン的に並列動作させる様子を表す図である。
【発明を実施するための形態】
【００１９】
まず、図１を参照して、本発明の実施の形態にかかるデータ処理装置１の概要について説明する。図１は、本発明の実施の形態にかかるデータ処理装置１の概要構成図である。
【００２０】
データ処理装置５は、記憶部５０及び実行部５１を有する。
記憶部５０は、データが格納される複数の領域を含む。
実行部５１は、複数のスレッドを実行する。複数のスレッドはデータ依存関係をもつ。例えば、スレッド５２の演算結果をスレッド５３が使用する、という関係が存在する。このようなデータ依存関係にもとづいて、実行部５１はスレッドの実行順序を決定する。
【００２１】
続いて、本発明の実施の形態にかかるデータ処理装置５の処理について説明する。
この説明では、データ依存関係をもつ二つのスレッドの一方を第１のスレッド、もう一方を第２のスレッド、と呼ぶことにする。この二つのスレッドは、第１のスレッドの演算結果を第２のスレッドが使用する、という関係をもつ。
第１のスレッド５２は、演算を行って、その演算結果となるデータを、記憶部５０に含まれる複数の領域のうち、特定の領域に格納する。そして、第１のスレッド５２は、記憶部５０へのデータの格納を通知する格納通知情報と、記憶部５０において、そのデータが格納された領域を示す格納領域情報と、を第２のスレッド５３に送信する。
第２のスレッド５３は、第１のスレッドからの格納通知情報に応じて、第１のスレッド５２からの格納領域情報が示す領域に格納されたデータを使用して演算を行う。
【００２２】
続いて、本発明の実施の形態について図面を参照して詳細に説明する。まず、図２を参照して、本発明の実施の形態にかかるデータ処理装置１の構成について説明する。図２は、本発明の実施の形態にかかるデータ処理装置１の構成図である。
【００２３】
データ処理装置１は、記憶ユニット１０及びプロセッサ１１〜１８を有する。なお、プロセッサ１３〜１６については、図示を省略する。
【００２４】
記憶ユニット１０は、プロセッサ１１〜１８を駆動するためのプログラムやプロセッサ１１〜１８が使用する各種のデータを保持する記憶装置である。記憶ユニット１０の実施形態は、例えば、メモリやハードディスクドライブ等である。記憶ユニット１０は、記憶部５０に対応する。
【００２５】
プロセッサ１１〜１８は、スレッドｔｈ１〜ｔｈ８を実行する。具体的には、プロセッサ１Ｎは、スレッドｔｈＮを実行する(Ｎは、１〜８の正整数)。プロセッサ１１〜１８は、実行部５１に対応する。図２ではひとつのプロセッサにひとつのスレッドが割り当てられているが、ひとつのプロセッサに複数のスレッドを割り当ててもよい。プロセッサ１１〜１８はそれぞれ独立して動作するとともに、記憶ユニット１０を介してデータを受け渡しする。
【００２６】
本発明の模範的な実施形態における並列処理の概念を説明する。本実施形態は、並列処理の対象となるタスクをいくつかのサブタスクに分解し、サブタスクをスレッドに割り当て、スレッドを並列実行する。スレッドは、サブタスクを実行するプログラムである。本実施形態は、スレッドを並列実行する際に、スレッドの依存関係にもとづいて、実行順序を決定する。依存関係のないスレッドは並列に実行され、依存関係があるスレッドは依存関係にもとづいて順番に実行される。
【００２７】
スレッドの依存関係は、スレッドに割り当てられたサブタスクの依存関係と等価である。そして、サブタスクの依存関係はサブタスクが扱うデータの依存関係と等価である。
本実施形態は、サブタスクが使用するデータにもとづいてサブタスクの依存関係を決定する。例えば、サブタスクＴ１の演算結果Ｒ１をサブタスクＴ２が使用するなら、サブタスクＴ２はサブタスクＴ１に依存しており、サブタスクＴ２はサブタスクＴ１の後で実行されなければならない。こうしたデータフローにもとづいてサブタスクの依存関係が決定される。サブタスクの依存関係は、そのままスレッドの依存関係を表す。
【００２８】
図３は、本実施形態におけるスレッドの並列実行の概念を表す図である。図３において、スレッドの実行順序はデータ依存関係を表すグラフ構造にもとづいて予め決定される。このグラフ構造は、スレッドが扱うデータの依存関係を表しており、複数のサブタスクで構成されたタスクのデータフローと同じ構造をもつ。つまり、タスクに含まれる複数のサブタスク間のデータの依存関係を表すグラフ構造は、それぞれのサブタスクを実行する複数のスレッド間のデータの依存関係を表すグラフ構造となる。
【００２９】
図３のようなスレッド依存関係のグラフ構造から、各スレッドが使用するデータはどのスレッドの演算結果か、各スレッドの演算結果はどのスレッドに使われるか、がわかる。図３では、スレッドｔｈ１の演算結果をスレッドｔｈ２〜ｔｈ４が使用し、スレッドｔｈ２の演算結果をスレッドｔｈ５が使用し、スレッドｔｈ３の演算結果をスレッド６が使用し、スレッドｔｈ４〜ｔｈ５の演算結果をスレッドｔｈ７が使用し、スレッドｔｈ７の演算結果をスレッドｔｈ８が使用することを示している。
【００３０】
図３において、二つのスレッドを結ぶ線はチャネルである。チャネルは、依存関係がある２つのスレッドの間の単方向のバッファレスのハンドシェイク型通信路である。図３において、スレッドｔｈ１からスレッドｔｈ４に矢印が向いている。これは、スレッドｔｈ１の演算結果をスレッドｔｈ４が使用すること、及び、スレッドｔｈ１からスレッドｔｈ４にシグナルが送信されること、を示している。また、ハンドシェイク型通信路は、送信側スレッドから送信された情報を受信側スレッドが受信したことを送信側スレッドが確認してから送信完了となる通信路である。本実施形態は、サブタスクの実行開始および終了をスレッドへ知らせるためにチャネルを使用する。
【００３１】
スレッドは、サブタスクの実行が終わると、チャネルを通してシグナルを別のスレッドに送信する。シグナルは、スレッドからスレッドへ送信される情報である。シグナル送信はサブタスクの実行完了を他のスレッドへ通知する手段である。受信側スレッドがシグナルを受信することは、受信側スレッドがサブタスクの実行を開始して良いことを意味する。スレッド間でシグナルを送受信する際には、シグナルが受信側スレッドで受信されたことを送信側スレッドが確認できて始めて送信完了となる。つまり、スレッドは、他スレッドからシグナルを受けることによって処理を開始し、処理が終わると別スレッドへシグナルを送信する。
【００３２】
シグナルは、スレッドに割り当てられたサブタスクが使用する記憶ユニット１０のデータ領域番号を含んでいる。記憶ユニット１０は、いくつかのデータ領域をもつ。各データ領域は、スレッドｔｈ１〜ｔｈ８のサブタスクの入出力データとなる複数のデータを格納する領域である。データは、変数や配列等である。そして、各データ領域は同じデータ構造をもっている。例えば、ひとつのデータ領域は、１つの構造体として定義される。また、複数のデータ領域は構造体の配列として定義される。その配列の要素番号がシグナルに含まれるデータ領域番号となる。サブタスクの入出力データは、記憶ユニット１０の中の複数のデータ領域のうち、シグナルに含まれるデータ領域番号が示すデータ領域に配置される。スレッドは、サブタスクが必要とするデータをそのデータ領域から取得し、取得したデータを使用して演算を行う。スレッドは、サブタスクの演算結果をそのデータ領域へ書き込む。
【００３３】
スレッドは、受信したシグナルに含まれるデータ領域番号を、別のスレッドへのシグナルに含めて送信する。したがって、図３の起点となるスレッドｔｈ１に与えられたシグナルのデータ領域番号が、他のスレッドｔｈ２〜ｔｈ８にも送信されることになる。そして、本実施形態は、後述するように、起点となるスレッドｔｈ１に与えるデータ領域番号を切り替えることによって、複数のデータ領域を使用して、パイプライン的にスレッドを並列動作させる。データ領域が少なくとも二つあれば、パイプライン的なスレッド並列動作が可能である。
【００３４】
＜スレッドの起動から終了まで＞
次に、図４を参照しながら、スレッドの起動から終了までの流れを説明する。
プロセッサ(プロセッサ１１〜１８のいずれか)は、スレッドを作成し、起動する(Ｓ１００)。起動されたスレッドをｔｈＮとする。以下、スレッドｔｈＮが実行する処理は、実際にはプロセッサによって実行される。
【００３５】
スレッドｔｈＮは、依存関係がある別スレッドからシグナルを受信するまで待ち合わせる(Ｓ２００)。スレッドｔｈＮが複数のスレッドに依存している場合には、それら全てのスレッドからシグナルを受信するまで待ち合わせる。スレッドｔｈＮが、依存する全てのスレッドからシグナルを受信したら、次のステップＳ３００に進む。
【００３６】
スレッドｔｈＮは、受信したシグナルのいずれかに終了コードが含まれているか否かを確認する(Ｓ３００)。もし、終了コードが含まれているならば(Ｓ３００：Ｙｅｓ)、スレッドｔｈＮはステップＳ６００へ進む。そうでないならば(Ｓ３００：Ｎｏ)、スレッドｔｈＮはステップＳ４００へ進む。 
【００３７】
スレッドｔｈＮは、受信したシグナルからデータ領域番号Ｄｉｄｘを読取り、番号Ｄｉｄｘのデータ領域のデータを使用して、サブタスクを実行する(Ｓ４００)。スレッドｔｈＮは、サブタスクの実行結果を、番号Ｄｉｄｘのデータ領域に書き込む。サブタスクの実行が終わると、スレッドｔｈＮは、ステップＳ５００に進む。
【００３８】
スレッドｔｈＮは、スレッドｔｈＮの演算結果を使用する全てのスレッドへシグナルを送信する(Ｓ５００)。つまり、スレッドｔｈＮは、依存関係がある他スレッドへシグナルを送信する。スレッドｔｈＮの演算結果を使用する全てのスレッドに対してシグナルを送信できたら、スレッドｔｈＮは、ステップＳ２００へ戻る。
ステップＳ２００で受信したシグナルのいずれかに終了コードがふくまれている場合(Ｓ３００：Ｙｅｓ)、スレッドｔｈＮは、実行を終了する(Ｓ６００)。
【００３９】
以降では、ステップＳ２００のシグナル受信と、ステップＳ５００のシグナル送信、について詳しく説明する。 
【００４０】
＜シグナルの送受信＞
スレッドがシグナルをどのように送受信するかについて説明する。図４のステップＳ２００においてスレッドはシグナルを受信する。図４のステップＳ５００においてスレッドはシグナルを送信する。ステップＳ２００およびＳ５００のシグナル送受信において、 受信側スレッドが受信可能な状態になっていることを確認してから送信側スレッドはシグナルを送信する。そして受信側スレッドがシグナルを受信したことを確認してから送信側スレッドはシグナル送信を完了する。これが、本実施形態におけるシグナル送受信の基本的な手順である。以降では、ステップＳ２００およびＳ５００のひとつの実現例として、ポーリングを使用したシグナル送受信について説明する。 
【００４１】
スレッドは、シグナルを送受信する際に、図５に示すチャネルのパラメータを使って、送受信の手順を制御する。チャネルのパラメータは以下の四つを含む。
【００４２】
・送信待機フラグ
シグナルを送信するスレッドが送信準備できているか否かを表すフラグである。フラグの値が０の場合は、送信側スレッドが送信準備できていないことを表す。フラグの値が１の場合は、送信側スレッドが送信準備できていることを表す。
・受信待機フラグ
シグナルを受信するスレッドが受信準備できているか否かを表すフラグである。フラグの値が０の場合は、受信側スレッドが受信準備できていないことを表す。フラグの値が１の場合は、受信側スレッドが受信準備できていることを表す。
・受信完了フラグ
シグナルを受信するスレッドがシグナルを受信したか否かを表すフラグである。フラグの値が０の場合は、受信側スレッドはシグナルを受信していないことを表す。フラグの値が１の場合は、受信側スレッドはシグナルを受信したことを表す。
・シグナル
スレッドが送信する値である。値が−１のシグナルは、終了コードであり、これを受け取ったスレッドは終了することを表す。値が非負整数のシグナルは、スレッドが使用するべきデータ領域の番号を表す。 
【００４３】
チャネルのパラメータは記憶ユニット１０に格納される。例えば、記憶ユニット１０は、それぞれが各チャネルに対応する複数の領域を有する。複数の領域のそれぞれは、その領域に対応したチャネルのパラメータが格納される。スレッドは、後述するように、記憶ユニット１０に格納されたチャネルのパラメータの変化に応じて、シグナルを送受信する。
【００４４】
＜ポーリングを使用したシグナル送信＞
図６を参照して、ポーリングを使用したシグナル送信の手順について説明する。以降の説明では、送信側スレッドをスレッドＳ、受信側スレッドをスレッドＲ、スレッドＳからスレッドＲへのチャネルをチャネルＣ、と呼ぶことにする。
【００４５】
送信側スレッドＳは、受信側スレッドＲが受信待機中かどうかを調べる(Ｓ５１１)。チャネルＣの受信待機フラグが１であれば、スレッドＲが受信待機中であると判断できる。もし、スレッドＲが受信待機中でなければ(Ｓ５１１：Ｎｏ)、スレッドＳはステップＳ５１２へ進む。そして、スレッドＳは、短時間待ち合わせた後で、再びステップＳ５１１へ戻る(Ｓ５１２)。つまり、スレッドＳは、受信側スレッドＲが受信待機中になるまで、ステップＳ５１１とステップＳ５１２を繰り返す。言い換えると、スレッドＳは、スレッドＳとスレッドＲを関連付けるチャネルの受信待機フラグに１がセットされるまで、ポーリングをする。もし、ステップＳ５１１において、受信側スレッドＲが受信待機中であれば(Ｓ５１１：Ｙｅｓ)、スレッドＳは、ステップＳ５１３へ進む。
【００４６】
スレッドＳは、スレッドＲへ送信したいシグナルをチャネルＣに書き込む(Ｓ５１３)。スレッドＳは、チャネルＣの送信待機フラグに１をセットする(Ｓ５１４)。
【００４７】
スレッドＳは、受信側スレッドＲが受信完了したかどうかを調べる(Ｓ５１５)。チャネルＣの受信完了フラグが１であれば、スレッドＲは受信完了したと判断できる。もし、スレッドＲが受信完了していなければ(Ｓ５１５：Ｎｏ)、スレッドＳはステップＳ５１６へ進む。そして、スレッドＳは、短時間待ち合わせ後で、再びステップＳ５１５へ戻る(Ｓ５１６)。つまり、スレッドＳは、受信側スレッドＲが受信完了するまで、ステップＳ５１５とステップＳ５１６とを繰り返す。言い換えると、スレッドＳは、スレッドＳとスレッドＲとを関連付けるチャネルの受信完了フラグに１がセットされるまで、ポーリングをする。もし、ステップＳ５１５において、受信側スレッドＲが受信完了していれば(Ｓ５１５：Ｙｅｓ)、スレッドＳは、ステップＳ５１７へ進む。
【００４８】
スレッドＳは、チャネルＣの送信待機フラグを０にクリアする (Ｓ５１７)。以上のようにして、スレッドＳは、チャネルＣを使用して、スレッドＲへシグナルを送信する。
本実施形態においては、一対一で、スレッドＳからスレッドＲへシグナルを送信する。 スレッドＳが複数のスレッドへシグナルを送信する場合には、スレッドＳは、上記の一対一のシグナル送信を複数回繰り返す。 
【００４９】
＜ポーリングを使用したシグナル受信＞
図７を参照して、ポーリングを使用したシグナル受信の手順について説明する。以降の説明では、送信側スレッドをスレッドＳ、受信側スレッドをスレッドＲ、スレッドＳからスレッドＲへのチャネルをチャネルＣ、と呼ぶことにする。
受信側スレッドＲは、チャネルＣの受信待機フラグに１をセットする(Ｓ２１１)。 
【００５０】
受信側スレッドＲは、送信側スレッドＳが送信待機中かどうかを調べる(Ｓ２１２)。チャネルＣの送信待機フラグが１であれば、スレッドＳは送信待機中であると判断できる。もし、スレッドＳが送信待機中でなければ(Ｓ２１２：Ｎｏ)、スレッドＲはステップＳ２１３へ進む。そして、スレッドＲは、短時間待ち合わせた後で、再びステップＳ２１２へ戻る(Ｓ２１３)。つまり、スレッドＲは、送信側スレッドＳが送信待機状態になるまで、ステップＳ２１２とステップＳ２１３を繰り返す。言い換えると、スレッドＲは、スレッドＲとスレッドＳを関連付けるチャネルの送信待機フラグに１がセットされるまで、ポーリングをする。もし、ステップＳ２１２において、送信側スレッドＳが送信待機中であれば(Ｓ２１２：Ｙｅｓ)、スレッドＲは、ステップＳ２１４へ進む。
【００５１】
スレッドＲは、チャネルＣからシグナルを読取る(Ｓ２１４)。
スレッドＲは、チャネルＣに受信完了フラグに１をセットする(Ｓ２１５)。
スレッドＲは、チャネルＣの受信待機フラグを０にクリアする(Ｓ２１６)。 
【００５２】
スレッドＲは、送信側スレッドＳが依然として送信待機中かどうかを調べる(Ｓ２１７)。チャネルＣの送信待機フラグが１であれば、スレッドＳが送信待機中であると判断できる。もし、ステップＳ２１７において、送信側スレッドＳが送信待機中であれば(Ｓ２１７：Ｙｅｓ)、スレッドＲは、ステップＳ２１８へ進む。そして、スレッドＲは、短時間待ち合わせた後で、再びステップＳ２１７へ戻る(Ｓ２１８)。つまり、スレッドＲは、送信側スレッドＳが送信待機中でなくなるまで、ステップＳ２１７とステップＳ２１８を繰り返す。言い換えると、スレッドＲは、スレッドＲとスレッドＳを関連付けるチャネルの送信待機フラグが０にクリアされるまで、ポーリングをする。もし、ステップＳ２１７において、送信側スレッドＳが送信待機中でなければ(Ｓ２１７：Ｎｏ)、スレッドＲは、ステップＳ２１９へ進む。
【００５３】
スレッドＲがステップＳ２１５を実行した後に、スレッドＲが受信完了したことを送信側スレッドＳが知る。すると、スレッドＳは、チャネルＣの送信待機フラグを０にクリアする(Ｓ５１７)。これによって、スレッドＲは、スレッドＳが送信待機状態から抜けたことを知る。このようにして、スレッドＲはステップＳ２１７を実行する。
ステップＳ２１７で送信側スレッドＳが送信待機中でない場合（Ｓ２１７：Ｎｏ）、スレッドＲはチャネルＣの受信完了フラグを０にクリアする(Ｓ２１９)。以上のようにして、スレッドＲは、チャネルＣを使用して、スレッドＳからシグナルを受信する。
【００５４】
本実施形態においては、一対一で、スレッドＲはスレッドＳからシグナルを受信する。 スレッドＲが複数のスレッドからシグナルを受信する場合には、スレッドＲは、上記の一対一のシグナル受信を複数回繰り返す。
【００５５】
以上のように、ステップＳ２００およびＳ５００の実現例として、ポーリングを使用したシグナル送受信を説明した。ステップＳ２００およびＳ５００の実現方法はこれに限らず、先に述べた本実施形態のシグナル送受信の基本的な考え方にもとづいていれば、ここで説明した以外の方法でも実現可能である。つまり、受信側スレッドが受信可能な状態になっていることを確認してから送信側スレッドがシグナルを送信し、受信側スレッドがシグナルを受信したことを確認してから送信側スレッドがシグナル送信を完了する、という考え方に基づいていれば、ここで説明した方法に限られない。
【００５６】
＜シグナル伝搬＞
図８を参照して、スレッドからスレッドへシグナルが伝搬しながら、スレッドに割り当てられたサブタスクが実行される様子を説明する。図８には、スレッドｔｈ１からｔｈ８までの８個のスレッドがある。それぞれのスレッドｔｈ１〜ｔｈ８には、サブタスクが割り当てられている。説明を簡単にするため、各サブタスクの処理時間は同じとする。
【００５７】
８個のスレッドｔｈ１〜ｔｈ８のなかで、スレッドｔｈ１が起点となるスレッドであり、ｔｈ８が終点となるスレッドである。図８には示されていないが、８個のスレッドの開始や終了を制御するために、もうひとつのスレッドが存在する。このスレッドをメインスレッドと呼ぶことにする。メインスレッドは、プロセッサ１１〜１８のいずれかによって実行されるようにしてもよく、プロセッサ１１〜１８以外の図示しないプロセッサによって実行されるようにしてもよい。メインスレッドと起点となるスレッドｔｈ１間及びメインスレッドと終点となるスレッドｔｈ８間のそれぞれにも、チャネルが存在する。メインスレッドは、スレッドｔｈ１〜ｔｈ８が使用するデータ領域とは別の記憶装置の領域を使用して、スレッドｔｈ１〜ｔｈ８と並列に動作する。
【００５８】
まず、ステップ（１）において、起点となるスレッドｔｈ１へ、メインスレッドがシグナルを送信する。このとき、メインスレッドは、シグナルにデータ領域番号０を含めているものとする。スレッドｔｈ１はシグナルを受信して、データ領域番号０のデータ領域を使用してサブタスクを実行する。つまり、スレッドｔｈ１は、演算を行い、その演算結果を、データ領域番号０のデータ領域に格納する。
【００５９】
つづいて、ステップ（２）において、スレッドｔｈ１は、自身が受信したシグナルのコピーをスレッドｔｈ２、ｔｈ３、ｔｈ４へ送信する。そのシグナルを受信したスレッドｔｈ２、ｔｈ３、ｔｈ４のそれぞれは、データ領域番号０のデータ領域を使用してそれぞれのサブタスクを実行する。つまり、スレッドｔｈ２〜ｔｈ４のそれぞれは、データ領域番号０のデータ領域に格納されるスレッドｔｈ１の演算結果を取得する。そして、スレッドｔｈ２〜ｔｈ４のそれぞれは、取得したデータを利用して演算を行い、その演算結果を、データ領域番号０のデータ領域に格納する。
【００６０】
つづいて、ステップ（３）において、スレッドｔｈ２、ｔｈ３、ｔｈ４のそれぞれは、自身が受信したシグナルのコピーを、スレッドｔｈ５、ｔｈ６、ｔｈ７のそれぞれへ送信する。そして、そのシグナルを受信したスレッドｔｈ５、ｔｈ６のそれぞれは、データ領域番号０のデータ領域を使用してそれぞれのサブタスクを実行する。つまり、スレッドｔｈ５は、データ領域番号０のデータ領域に格納されるスレッドｔｈ２の演算結果を取得する。そして、スレッドｔｈ５は、取得したデータを利用して演算を行い、その演算結果を、データ領域番号０のデータ領域に格納する。また、スレッドｔｈ６は、データ領域番号０のデータ領域に格納されるスレッドｔｈ３の演算結果を取得する。そして、スレッドｔｈ６は、取得したデータを利用して演算を行い、その演算結果を、データ領域番号０のデータ領域に格納する。一方、スレッドｔｈ７は、スレッドｔｈ４だけではなくスレッドｔｈ５、ｔｈ６のシグナルも受信する必要があるため、 スレッドｔｈ５、ｔｈ６のシグナルを待ち続ける。
【００６１】
つづいて、ステップ（４）において、スレッドｔｈ５、ｔｈ６のそれぞれは、自身が受信したシグナルのコピーをともにスレッドｔｈ７へ送信する。そして、そのシグナルを受信したスレッドｔｈ７は、依存しているスレッドｔｈ４、ｔｈ５、ｔｈ６からのシグナルを全て受信できたことになるので、データ領域番号０のデータ領域を使用してサブタスクの実行を開始する。つまり、スレッドｔｈ７は、データ領域番号０のデータ領域に格納されるスレッドｔｈ４〜ｔｈ６の演算結果を取得する。そして、スレッドｔｈ７は、取得したデータを利用して演算を行い、その演算結果を、データ領域番号０のデータ領域に格納する。
【００６２】
つづいて、ステップ（５）において、スレッドｔｈ７は自身が受信したシグナルのコピーをスレッドｔｈ８へ送信する。そして、そのシグナルを受信したスレッドｔｈ８は、 番号０のデータ領域を使用してサブタスクの実行を開始する。つまり、スレッドｔｈ８は、データ領域番号０のデータ領域に格納されるスレッドｔｈ７の演算結果を取得する。そして、スレッドｔｈ８は、取得したデータを利用して演算を行い、その演算結果を、データ領域番号０のデータ領域に格納する。やがて、そのサブタスクが実行完了し、スレッドｔｈ８は自身が受信したシグナルのコピーをメインスレッドへ送信する。メインスレッドは、終点スレッドであるスレッドｔｈ８からのシグナルを受信することによって、全てのサブタスクが実行完了したことを知る。
【００６３】
図８の例では、各サブタスクの実行時間は同じだと仮定して説明したが、一般にはサブタスクの実行時間は異なる。サブタスクの実行時間が異なると、複数のスレッドからのシグナルを受信するスレッドにおいて、シグナルの受信時刻にズレが生じる。しかし、本実施形態においては、ハンドシェイク型のシグナル送受信を使うことによって、そのズレを許容することができる。
【００６４】
ハンドシェイク型のシグナル送受信においては、受信側スレッドが受信可能な状態になっていることを確認してから送信側スレッドがシグナルを送信し、受信側スレッドがシグナルを受信したことを確認してから送信側スレッドがシグナル送信を完了する、という考え方に基づいている。つまり、シグナル送受信の手順の中に待ち合わせが含まれている。したがって、サブタスクの実行時間やシグナル受信時間が異なったとしても、その違いを許容できるのである。
【００６５】
＜パイプライン的並列動作＞
図９Ａ、９Ｂ、９Ｃを参照して、本実施形態が、パイプライン的にスレッドを並列動作させることができること、説明する。 図９Ａ、９Ｂ、９Ｃは、図８と同じ８個のスレッドがパイプライン的に並列動作する様子を表した図である。図９Ａ、９Ｂ、９Ｃにおいて、各スレッドを並列に動作させるために、シグナルを使用して、各スレッドに使わせるデータ領域を交互に切り替えていく。以下の説明において、データ領域を切り替える様子を説明する。
【００６６】
まず、図９Ａのステップ（１）から（４）を説明する。ステップ（１）において、メインスレッドは、起点となるスレッドｔｈ１へシグナルを送信する。このとき、メインスレッドは、シグナルにデータ領域番号０を含めているものとする。スレッドｔｈ１はシグナルを受信して、データ領域番号０のデータ領域を使用してサブタスクを実行する。
【００６７】
つづいて、ステップ（２）において、スレッドｔｈ１はシグナル(データ領域番号０)をスレッドｔｈ２、ｔｈ３、ｔｈ４へそれぞれ送信する。スレッドｔｈ２、ｔｈ３、ｔｈ４のそれぞれは、データ領域番号０のデータ領域を使用してそれぞれのサブタスクを実行する。さらに、メインスレッドは、データ領域番号を０から１に切り替えたシグナル(データ領域番号１)をスレッドｔｈ１へ送信する。スレッドｔｈ１はそのシグナルを受信して、データ領域番号１のデータ領域を使用してサブタスクを実行する。
【００６８】
つづいて、ステップ（３）において、スレッドｔｈ２、ｔｈ３、ｔｈ４のそれぞれは、シグナル(データ領域番号０)をスレッドｔｈ５、ｔｈ６、ｔｈ７のそれぞれへ送信する。そして、スレッドｔｈ５、ｔｈ６のそれぞれは、データ領域番号０のデータ領域を使用してそれぞれのサブタスクを実行する。一方、スレッドｔｈ７は、スレッドｔｈ５、ｔｈ６からのシグナルを待ち続ける。さらに、スレッドｔｈ１はシグナル(データ領域番号１)をスレッドｔｈ２、ｔｈ３、ｔｈ４へ送信する。スレッドｔｈ２、ｔｈ３、ｔｈ４のそれぞれは、データ領域番号１のデータ領域を使用してそれぞれのサブタスクを実行する。さらに、メインスレッドはシグナル(データ領域番号０)をスレッドｔｈ１へ送信する。スレッドｔｈ１は、データ領域番号０のデータ領域を使用してサブタスクを実行する。
【００６９】
つづいて、ステップ（４）において、スレッドｔｈ５、ｔｈ６のそれぞれは、シグナル(データ領域番号０)をスレッドｔｈ７へ送信する。そして、スレッドｔｈ７は、必要なシグナルがそろったので、データ領域番号０のデータ領域を使用してサブタスクを実行する。さらに、スレッドｔｈ２、ｔｈ３、ｔｈ５、ｔｈ６は、シグナルの送信、シグナルの受信、サブタスク実行、をそれぞれ行う。スレッドｔｈ５、ｔｈ６のそれぞれは、シグナル(データ領域番号１)を受信してサブタスクを実行する。また、スレッドｔｈ２、ｔｈ３のそれぞれは、シグナル(データ領域番号０)を受信してサブタスクを実行する。
【００７０】
スレッドｔｈ４は、スレッドｔｈ７がまだデータ領域番号０のデータ領域を使用したサブタスクを実行しているところなので、新たなシグナル(データ領域番号１)をスレッドｔｈ７に送信することができず、待ち合わせ状態にある。つまり、スレッドｔｈ７は、スレッドｔｈ４とスレッドｔｈ７を関連付けるチャネルの受信待機フラグを０にしたままとする。スレッドｔｈ７がデータ領域番号０のデータ領域を使用したサブタスクの実行を完了し、新たなシグナルを受信可能な状態になれば、スレッドｔｈ４はシグナル(データ領域番号１)をスレッドｔｈ７に送信可能になる。
【００７１】
また、スレッドｔｈ１は、スレッドｔｈ４が待ち合わせ状態にあるため、シグナル(データ領域番号０)をスレッドｔｈ４に送信することができない。つまり、スレッドｔｈ４は、スレッドｔｈ１とスレッドｔｈ４を関連付けるチャネルの受信待機フラグを０にしたままとする。また、スレッドｔｈ１は、スレッドｔｈ１とスレッドｔｈ４を関連付けるチャネルの受信待機フラグが１にセットされるまで待つ。そのため、スレッドｔｈ１は、メインスレッドとスレッドｔｈ１を関連付けるチャネルの受信待機フラグを０にしたままとなる。
【００７２】
つづいて、図９Ｂのステップ（５）から（８）を説明する。ステップ（５）において、スレッドｔｈ７は、データ領域番号０のデータ領域を使用したサブタスクの実行が完了するので、新たなシグナル(データ領域番号１)を受信してサブタスクを実行できるようになる。よって、スレッドｔｈ７は、スレッドｔｈ４〜ｔｈ６のそれぞれと、スレッドｔｈ７とを関連付けるチャネルのそれぞれにおける受信待機フラグを１にする。そして、スレッドｔｈ７は、スレッドｔｈ４〜ｔｈ６から、シグナル(データ領域番号１)を受信してサブタスクを実行する。これによって、スレッドｔｈ４は、待ち合わせ状態が解除される。
【００７３】
スレッドｔｈ８は、スレッド７から、シグナル(データ領域番号０)を受信してサブタスクを実行する。一方、ステップ（４）において待ち状態にあったスレッドｔｈ４は、ステップ（５）において、待ち合わせ状態が解除されるため、スレッドｔｈ１とスレッドｔｈ４を関連付けるチャネルの受信待機フラグを１にする。そして、スレッドｔｈ４は、スレッドｔｈ１からシグナル(データ領域番号０)を受信し、サブタスクを実行する。そして、スレッドｔｈ１は、スレッドｔｈ４がシグナル(データ領域番号０)を受信するまで待ち合わせてから、メインスレッドからシグナル(データ領域番号１)を受信して、サブタスクを実行する。スレッドｔｈ２、ｔｈ３のそれぞれは、スレッドｔｈ１から新たなシグナル(データ領域番号１)が送信されるのを待つ。スレッドｔｈ５、ｔｈ６のそれぞれは、スレッドｔｈ２、ｔｈ３のそれぞれから、シグナル(データ領域番号０)を受信してサブタスクを実行する。
【００７４】
つづいて、ステップ（６）において、スレッドｔｈ１、ｔｈ２、ｔｈ３、ｔｈ４、ｔｈ７、ｔｈ８のそれぞれは、シグナルの送信、シグナルの受信、サブタスク実行、をそれぞれ行う。スレッドｔｈ１に対しては、メインスレッドがシグナル(データ領域番号０)を送信する。スレッドｔｈ１、ｔｈ７のそれぞれは、データ領域番号０のシグナルを受信してサブタスクを実行する。スレッドｔｈ２、ｔｈ３、ｔｈ４、ｔｈ８のそれぞれは、データ領域番号１のシグナルを受信してサブタスクを実行する。一方、スレッドｔｈ５はスレッドｔｈ２から、新たなシグナル(データ領域番号１)が送信されるのを待ち、スレッドｔｈ６はスレッドｔｈ３から、新たなシグナル(データ領域番号１)が送信されるのを待つ。
【００７５】
つづいて、ステップ（７）において、スレッドｔｈ７以外のスレッドは、シグナルの送信(スレッドｔｈ５、６を除く)、シグナルの受信、サブタスク実行、をそれぞれ行う。つまり、スレッドｔｈ１、ｔｈ５、ｔｈ６のそれぞれは、シグナル(データ領域番号１)を受信してサブタスクを実行する。また、スレッドｔｈ２、ｔｈ３、ｔｈ４、ｔｈ８のそれぞれは、データ領域番号０のシグナルを受信してサブタスクを実行する。スレッドｔｈ１に対しては、メインスレッドがシグナル(データ領域番号１)を送信する。一方、スレッドｔｈ７は、スレッドｔｈ４からシグナル(データ領域番号１)を受信しているものの、 スレッドｔｈ５、ｔｈ６からシグナルを受信できるまで待つ。
【００７６】
つづいて、ステップ（８）において、スレッドｔｈ１、ｔｈ４、ｔｈ８以外のスレッドは、シグナルの送信(スレッドｔｈ７を除く)、シグナルの受信、サブタスク実行、をそれぞれ行う。つまり、スレッドｔｈ５、ｔｈ６のそれぞれは、シグナル(データ領域番号０)を受信してサブタスクを実行する。また、スレッドｔｈ２、ｔｈ３、ｔｈ７のそれぞれは、シグナル(データ領域番号１)を受信してサブタスクを実行する。スレッドｔｈ１に対しては、メインスレッドがシグナル(データ領域番号１)を送信する。一方、スレッドｔｈ８は、スレッドｔｈ７から新たなシグナルが送信されるのを待ち、スレッドｔｈ１、ｔｈ４は、ステップ（４）と同じような状態にある。つまり、スレッドｔｈ４が直前に送信したシグナル(データ領域番号１)を使用してスレッドｔｈ７がサブタスクを実行中なので、スレッドｔｈ４はスレッドｔｈ７に新たなシグナル(データ領域番号０)を送信できず、待ち合わせ状態にある。また、スレッドｔｈ１もスレッドｔｈ４にシグナル(データ領域番号１)を送信することができない。スレッドｔｈ７がシグナル(データ領域番号１)を使用したサブタスクを実行完了すれば、スレッドｔｈ４はシグナル(データ領域番号０)をスレッドｔｈ７に送信可能になる。
【００７７】
つづいて、図９Ｃのステップ（９）から（１２）を説明する。ステップ（９）において、スレッドｔｈ７は新たなシグナル（データ領域番号０）を受信してサブタスクを実行する。スレッドｔｈ８は、シグナル（データ領域番号１）を受信してサブタスクを実行する。一方、ステップ（８）において待ち状態にあったスレッドｔｈ４は、ステップ（９）においてスレッドｔｈ１からシグナル（データ領域番号１）を受信し、サブタスクを実行する。そして、スレッドｔｈ１は、スレッドｔｈ４がシグナル（データ領域番号１）を受信するまで待ち合わせてから、スメインスレッドからシグナル（データ領域番号０）を受信して、サブタスクを実行する。その間、スレッドｔｈ２、ｔｈ３のそれぞれは、スレッドｔｈ１から新たなシグナル（データ領域番号０）が送信されるのを待つ。スレッドｔｈ５、ｔｈ６のそれぞれは、シグナル(データ領域番号１)を受信してサブタスクを実行する。
【００７８】
ステップ（９）は、ステップ（５）においてシグナルの番号を入れ替えたものである（０を１へ、１を０へ）。同様の関係は、ステップ（１０）とステップ（６）、ステップ（１１）とステップ（７）、ステップ（１２）とステップ（８）、のそれぞれに当てはまる。ステップ（１２）の次は、ステップ（５）にもどって、動作を繰り返す。そのため、ステップ（１０）以降については、詳細な説明は省略する。以上述べたように、本実施形態を使うことにより、複数のスレッドをパイプライン的に並列動作させることができる。
【００７９】
以上説明したように，本発明を使用すれば、共有メモリ環境において、複数のスレッドが共有メモリ上のデータを共有し、メッセージパッシングによってスレッド間で直接データを転送することなく、複数のスレッドをパイプライン的に並列動作させることができる。本発明は、組込み向けのマルチプロセッサから汎用のマルチコアＰＣなど、共有メモリ環境で複数のスレッドが動作するような計算機で幅広く応用可能である。
【００８０】
以上に説明したように、本実施の形態では、演算を行う第１のスレッドと、第１のスレッドの演算結果を使用して演算を行う第２のスレッドと、を実行する場合に、第１のスレッドが、演算を行って演算結果を示すデータを記憶ユニット１０に含まれる複数のデータ領域のうち、特定のデータ領域に格納するようにしている。次に、第１のスレッドが、記憶ユニット１０へのデータの格納を通知するシグナルを第２のスレッドに送信するようにしている。そして、第２のスレッドが第１のスレッドからのシグナルに応じて、シグナルに含まれるデータ領域番号が示すデータ領域に格納されたデータを使用して演算を行うようにしている。
【００８１】
これによれば、第１のスレッドが記憶ユニット１０にデータを格納した後に、第２のスレッドが記憶ユニット１０に格納されたそのデータを使用することになるため、第１のスレッドと第２のスレッドから、記憶ユニット１０のデータへのアクセスが競合することがなくなる。そのため、ロック／アンロックをすることなく、排他的なデータアクセスを保証できる。
【００８２】
また、第１のスレッドから第２のスレッドに、データが格納されたデータ領域を示す情報のみを送信するだけで、第２のスレッドが第１のスレッドの演算結果を取得することができる。つまり、演算結果を示すデータそのものを送信する必要がなくなる。そのため、データ転送コストを削減することができる。
【００８３】
また、本実施の形態では、さらに、あるステップで、第１のスレッドが、演算を行って演算結果を示すデータを、記憶ユニット１０に含まれるデータ領域０に格納するようにしている。そして、次のステップで、第１のスレッドが、演算を行って演算結果を示すデータを、データ領域０とは異なるデータ領域１に格納するとともに、第２のスレッドが、第１のスレッドからのシグナルが示すデータ領域０に格納されたデータを使用して演算を行っている。
【００８４】
これによれば、第２のスレッドによるデータ領域０のデータの使用と、第１のスレッドによるがデータ領域０のデータの更新とが競合することがない。そのため、スレッドをパイプライン的に並列動作させることが可能となる。なお、データ領域０とデータ領域１が逆であっても同様となる。
【００８５】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記によって限定されるものではない。本願発明の構成や詳細には、発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００８６】
本実施の形態では、スレッドが演算結果を示すデータが格納されたデータ領域を示すデータ領域番号をシグナルに含めて送信し、そのスレッドに依存するスレッドがシグナルの受信に応じて、シグナルに含まれるデータ領域番号のデータ領域に格納されたデータを利用するようにしているが、これに限られない。つまり、本実施の形態では、データ領域にデータを格納したことを通知する情報に、データが格納された領域を示す情報を含めて送信しているが、それらの情報を１つの情報として送信するようにしなくてもよい。
【００８７】
本実施の形態では、メインスレッドが、データ領域番号０のシグナルとデータ領域番号１のシグナルを交互に送信する場合について例示したが、これに限られない。例えば、記憶ユニット１０がデータ領域番号を３つ以上有するようにして、２よりも大きいデータ領域番号のシグナルを送信するようにしてもよい。また、本実施の形態では、メインスレッドが、送信するシグナルのデータ領域番号をサイクリックに切り替える場合について例示したが、これに限られない。メインスレッドは、複数のスレッドによる同一のデータの使用及び更新が競合しなければ、データ領域番号をどのように切り替えるようにしてもよい。
【００８８】
本実施の形態では、１つのプロセッサが１つのスレッドを実行する場合について例示したが、これに限られない。例えば、１つのプロセッサが複数のスレッドを実行するようにしてもよい。つまり、複数のスレッドを１以上の任意の数のプロセッサで実行するようにしてもよい。
【００８９】
以上に説明した本発明にかかるデータ処理装置は、上述の実施の形態の機能を実現するプログラムを、コンピュータ又はコンピュータが有するＣＰＵ(Central Processing Unit)、ＭＰＵ(Micro Processing Unit)等のプロセッサが実行することによって、構成することが可能である。
【００９０】
また、このプログラムは、様々なタイプの非一時的なコンピュータ可読媒体(non-transitory computer readable medium)を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体(tangible storage medium)を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体(例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ)、光磁気記録媒体(例えば光磁気ディスク)、ＣＤ−ＲＯＭ(Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ(例えば、マスクＲＯＭ、ＰＲＯＭ(Programmable ROM）、ＥＰＲＯＭ(Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ(Random Access Memory））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体(transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００９１】
また、コンピュータ又はプロセッサが上述の実施の形態の機能を実現するプログラムを実行することにより、上述の実施の形態の機能が実現される場合のみに限定されない。このプログラムが、コンピュータ又はプロセッサ上で稼動しているＯＳ(Operating System)もしくはアプリケーションソフトウェアと共同して、上述の実施の形態の機能を実現する場合も、本発明の実施の形態に含まれる。さらに、このプログラムの処理の全てもしくは一部がコンピュータに挿入された機能拡張ボードや、コンピュータに接続された機能拡張ユニットによって行われて、上述の実施の形態の機能が実現される場合も、本発明の実施の形態に含まれる。
【００９２】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００９３】
(付記１)演算を行う第１のスレッドと、前記第１のスレッドの演算結果を使用して演算を行う第２のスレッドと、を実行するデータ処理方法であって、前記第１のスレッドが、演算を行って当該演算結果を示すデータを、前記記憶部に含まれる複数の領域のうち、特定の領域に格納する第１の演算ステップと、前記第１のスレッドが、前記記憶部へのデータの格納を通知する格納通知情報と、前記記憶部において当該データが格納された領域を示す格納領域情報と、を前記第２のスレッドに送信する送信ステップと、前記第２のスレッドが、前記第１のスレッドからの格納通知情報に応じて、前記第１のスレッドからの格納領域情報が示す領域に格納されたデータを使用して演算を行う第２の演算ステップと、  を備えたデータ処理方法。
【００９４】
(付記２)前記第１の演算ステップでは、前記第１のスレッドが、第１の演算を行って当該第１の演算結果を示す第１のデータを、前記記憶部に含まれる第１の領域に格納し、前記第２の演算ステップでは、前記第１のスレッドが、第２の演算を行って当該第２の演算結果を示す第２のデータを、前記記憶部に含まれ、前記第１の領域とは異なる第２の領域に格納するとともに、前記第２のスレッドが、前記第１のスレッドからの格納領域情報が示す第１の領域に格納された第１のデータを使用して演算を行う付記１に記載のデータ処理方法。
【００９５】
(付記３)前記データ処理方法は、さらにメインスレッドを実行するデータ処理方法であって、前記メインスレッドが、前記第１の領域を示す格納領域情報を前記第１のスレッドに送信するステップをさらに備え、前記第１の演算ステップでは、前記第１のスレッドが、前記第１のデータを、前記メインスレッドからの格納領域情報が示す第１の領域に格納し、前記送信ステップでは、前記メインスレッドが、前記第２の領域を示す格納領域情報を前記第１のスレッドに送信し、前記第２の演算ステップでは、前記第１のスレッドが、前記第２のデータを、前記メインスレッドからの格納領域情報が示す第２の領域に格納する付記２に記載のデータ処理方法。
【００９６】
(付記４)前記データ処理方法は、前記第１のスレッドを複数実行し、前記第２のスレッドは、前記複数の第１のスレッドによる複数の演算結果を使用して演算を行い、前記送信ステップは、前記第１のスレッドが、前記格納通知情報及び前記格納領域情報を第２のスレッドに送信する場合に、当該格納通知情報及び当該格納領域情報を送信することを示す送信実行情報を、当該第１のスレッドに対応する送受信情報記憶部に格納するステップと、前記第２のスレッドが、前記送受信情報記憶部に送信実行情報が格納された場合に、当該送受信情報記憶部に対応する第１のスレッドからの前記格納通知情報及び前記格納領域情報を受信するステップと、を含み、前記第２の演算ステップでは、前記第２のスレッドが、前記複数の第１のスレッドからの格納通知情報を全て受信した場合に、前記第１のスレッドからの格納領域情報が示す領域に格納されたデータを使用して演算を行う付記１乃至３のいずれか１項に記載のデータ処理方法。
【００９７】
(付記５)前記送信実行情報を格納するステップでは、前記第１のスレッドが、前記格納通知情報及び前記格納領域情報を送受信情報記憶部に格納して、前記送信実行情報を前記送受信情報記憶部に格納し、前記格納領域情報を受信するステップでは、前記第２のスレッドが、前記送受信情報記憶部に送信実行情報が格納された場合に、前記送受信情報記憶部に格納された前記格納通知情報及び前記格納領域情報を取得する付記４に記載のデータ処理方法。
【００９８】
(付記６)前記記憶部に含まれる領域は、それぞれに前記データが格納され、第１のデータ格納領域及び第２のデータ格納領域を含む複数のデータ格納領域を含み、前記第１の演算ステップでは、前記第１のスレッドが、前記データを、前記特定の領域に含まれる第１のデータ格納領域に格納し、前記第２の演算ステップでは、前記第２のスレッドが、前記演算結果を示すデータを、前記第１のスレッドからの格納領域情報が示す領域に含まれる第２のデータ格納領域に格納する付記１乃至５のいずれか１項に記載のデータ処理方法。
【００９９】
(付記７)前記格納通知情報は、前記格納領域情報を含む付記１乃至６のいずれか１項に記載のデータ処理方法。
【０１００】
(付記８)前記第１のスレッド及び前記第２のスレッドは、１以上のプロセッサによって実行される付記１乃至７のいずれか１項に記載のデータ処理方法。
【０１０１】
(付記９)データが格納される複数の領域を含む記憶部と、演算を行う第１のスレッドと、前記第１のスレッドの演算結果を使用して演算を行う第２のスレッドと、を実行する実行部と、を備え、前記第１のスレッドは、演算を行って当該演算結果を示すデータを、前記記憶部に含まれる複数の領域のうち、特定の領域に格納し、前記記憶部へのデータの格納を通知する格納通知情報と、前記記憶部において当該データが格納された領域を示す格納領域情報と、を前記第２のスレッドに送信し、前記第２のスレッドは、前記第１のスレッドからの格納通知情報に応じて、前記第１のスレッドからの格納領域情報が示す領域に格納されたデータを使用して演算を行うデータ処理装置。
【０１０２】
(付記１０)演算を行う第１のスレッドと、前記第１のスレッドの演算結果を使用して演算を行う第２のスレッドと、を実行するデータ処理方法であって、前記第１のスレッドが、演算を行って当該演算結果を示すデータを、前記記憶部に含まれる複数の領域のうち、特定の領域に格納する第１の演算ステップと、前記第１のスレッドが、前記記憶部へのデータの格納を通知する格納通知情報と、前記記憶部において当該データが格納された領域を示す格納領域情報と、を前記第２のスレッドに送信する送信ステップと、前記第２のスレッドが、前記第１のスレッドからの格納通知情報に応じて、前記第１のスレッドからの格納領域情報が示す領域に格納されたデータを使用して演算を行う第２の演算ステップと、をプロセッサに実行させるデータ処理プログラム。
【０１０３】
この出願は、２０１０年１０月１２日に出願された日本出願特願２０１０−２２９７８４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１０４】
１、５      データ処理装置
１０        記憶ユニット
１１、１２、１３、１４、１５、１６、１７、１８    プロセッサ
５０        記憶部
５１        実行部
５２、５３、ｔｈ１、ｔｈ２、ｔｈ３、ｔｈ４、ｔｈ５、ｔｈ６、ｔｈ７、ｔｈ８    スレッド
【図１】
2012049791.tif 000003
【図２】
2012049791.tif 000004
【図３】
2012049791.tif 000005
【図４】
2012049791.tif 000006
【図５】
2012049791.tif 000007
【図６】
2012049791.tif 000008
【図７】
2012049791.tif 000009
【図８】
2012049791.tif 000010
【図９Ａ】
2012049791.tif 000011
【図９Ｂ】
2012049791.tif 000012
【図９Ｃ】
2012049791.tif 000013
【手続補正書】
【提出日】平成25年3月13日(2013.3.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる、
ことを特徴とする、データ処理方法。
【請求項２】
前記第一のスレッドおよび前記第二のスレッドは、それぞれ別のスレッドであり、
前記第一のスレッドが、当該第一のスレッドに入力データを供給するスレッドから送信された制御信号を受信したのちに、当該入力データを使って演算を実行し、当該演算の結果を前記第三のスレッドに供給する入力データとして当該制御信号が指定するデータ領域に格納し、前記第三のスレッドへ当該制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行うか、又は、前記第二のスレッドが、前記第三のスレッドから送信された制御信号を受信したのちに、当該制御信号が指定するデータ領域に格納された演算の結果を入力データとして使って演算を実行し、当該演算の結果を当該制御信号が指定するデータ領域に格納し、当該結果を使用するスレッドへ当該制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う、
ことを特徴とする、請求項１に記載のデータ処理方法。
【請求項３】
前記第三のスレッドは、前記制御信号の送信において、前記第二のスレッドが前記制御信号を受信するまで待ち合わせる、
ことを特徴とする、請求項２に記載のデータ処理方法。
【請求項４】
前記第一のスレッドが前記第三のスレッドへ送信する前記制御信号の値を切り替えることによって、前記第三のスレッドが少なくとも二つのデータ領域へ演算結果を書き込むようにする、
ことを特徴とする、請求項３に記載のデータ処理方法。
【請求項５】
データを記憶するためのデータ領域をもつ記憶手段と、
入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる実行手段と、
を備えることを特徴とする、データ処理装置。
【請求項６】
データを記憶するためのデータ領域をもつコンピュータを、
入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる手段、
として機能させることを特徴とする、データ処理プログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、データ処理方法、データ処理装置及びデータ処理プログラムに関し、特に、データの依存関係をもつ複数のスレッドを並列実行する技術に関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
本発明の目的は、上述した課題を解決するために、データの依存関係を有するスレッドを実行する場合に、データをロック／アンロックすることなく、排他的なデータアクセスを保証でき、かつ、データ転送コストを削減することができるデータ処理方法、データ処理装置及びデータ処理プログラムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
本発明の第３の態様にかかるデータ処理プログラムは、データを記憶するためのデータ領域をもつコンピュータを、入力データを供給する第一のスレッドから送信された制御信号を受信したのちに、前記入力データを使って演算を実行し、前記演算の結果を前記制御信号が指定するデータ領域に格納し、前記結果を使用する第二のスレッドへ前記制御信号を送信する、という一連の手順（受信、演算、格納、送信）を行う第三のスレッドを動作させる手段、として機能させることを特徴とするものである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
上述した本発明の各態様により、データの依存関係を有するスレッドを実行する場合に、データをロック／アンロックすることなく、排他的なデータアクセスを保証でき、かつ、データ転送コストを削減することができるデータ処理方法、データ処理装置及びデータ処理プログラムを提供することができる。
【国際調査報告】
2012049791.tif 000014
2012049791.tif 000015
2012049791.tif 000016