(57)【要約】【課題】データフローグラフで表現可能なプログラムを少ない回数の「待ち合わせ」で並列処理する。【解決手段】プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出する。抽出されたプロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、一致候補群に含まれる２以上のエッジのうち、一致に係る除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする。【選択図】図１
2014106643.tif 000002
【特許請求の範囲】
【請求項１】
プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成装置であって、
前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、
前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、
を備えることを特徴とするエッジ群生成装置。
【請求項２】
請求項１に記載のエッジ群生成装置であって、
前記除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第２ノードよりも先になおかつ第１ノードよりも後に実行される第３ノードと、第１ノードから第２ノードへの第１エッジと、をもつ、基本除去可能エッジ含有パターンを少なくとも含み、
前記基本除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【請求項３】
請求項１又は２に記載のエッジ群生成装置であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた１つの第１ノードと、第２プロセッサに割り当てられた複数の第２ノードとを含むと共に、何れの第２ノードも第１ノードを出発側ノードとするエッジをもつような、第１除去可能エッジ含有パターンを少なくとも含み、
第１除去可能エッジ含有パターン中の、最小の順序番号をもつ第２ノードへのエッジを除いて、第１ノードから複数の第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【請求項４】
請求項１乃至３の何れか１項に記載のエッジ群生成装置であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた複数の第１ノードと、第２プロセッサに割り当てられた１つの第２ノードとを含むと共に、何れの第１ノードも第２ノードを到着側ノードとするエッジをもつような、第２除去可能エッジ含有パターンを少なくとも含み、
第２除去可能エッジ含有パターン中の、最大の順序番号をもつ第１ノードからのエッジを除く、複数の第１ノードから第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【請求項５】
請求項１乃至４の何れか１項に記載のエッジ群生成装置であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第３プロセッサに割り当てられた第３ノードとを含むと共に、第１ノードから第２ノードへの第１エッジあるいは部分データフローグラフと、第２ノードから第３ノードへの第２エッジと、第１ノードから第３ノードへの第３エッジとをもち、前記部分データフローグラフは第１ノードを出発側ノードとして第２ノードを到着側ノードとするノードとエッジを含むデータフローグラフであるような、第３除去可能エッジ含有パターンを少なくとも含み、
第３除去可能エッジ含有パターン中の、第３エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【請求項６】
請求項１乃至５の何れか１項に記載のエッジ群生成装置であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードおよび第２ノードと、第２プロセッサに割り当てられた第３ノードおよび第４ノードとを含むと共に、第１ノードから第４ノードへの第１エッジと、第２ノードから第３ノードへの第２エッジをもち、さらに、トポロジカルソートにもとづく順序番号に関して、第１ノードの順序番号は第２ノードの順序番号よりも小さく、第３ノードの順序番号は第４ノードの順序番号よりも小さいような、第４除去可能エッジ含有パターンを少なくとも含み、
第４除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【請求項７】
プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を記録したコンピュータ読取り可能な記録媒体であって、
前記プロセッサ間待ち合わせエッジ群が、
前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、
前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、
により生成されたプロセッサ間待ち合わせエッジ群であることを特徴とするコンピュータ読取り可能な記録媒体。
【請求項８】
プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成方法であって、
前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出ステップと、
前記候補群抽出ステップにおいて抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去ステップと、
を有することを特徴とするエッジ群生成方法。
【請求項９】
プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成装置としてコンピュータを機能させるための待ち合わせエッジ群生成プログラムであって、
前記コンピュータを、
前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、
前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、
を備えるエッジ群生成装置として機能させることを特徴とする待ち合わせエッジ群生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データフローグラフとして表現可能な並列処理を複数プロセッサで実行する際に待ち合わせすべきポイントを決定する為の、プロセッサ間待ち合わせエッジ群生成装置、その方法、そのプログラム及びエッジ群を格納した記録媒体に関する。
【背景技術】
【０００２】
複数のＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）等のプロセッサが協働し、又は、一つのマルチコア（Multiple core）プロセッサ内に含まれる複数のコアが協働し、並列して演算処理を実行することにより、或るソフトウェアを並列処理するということが広く行われている。
【０００３】
このようなソフトウェアの並列処理手法の一つに、データフロー型並列処理方法と一般的に呼ばれる処理方法がある。
【０００４】
データフロー型並列処理方法では、ソフトウェアを構成する計算要素のデータ依存関係に基づいて、データ依存関係の無い計算要素に関しては並列に実行する一方で、データ依存関係がある計算要素に関してはそのデータ依存関係に基づいた順番で実行する、という処理が行われる。
【０００５】
このようなデータフロー型並列処理に関連する技術の一例が、例えば「特許文献１：マルチプロセッサシステム及びマルチグレイン並列化コンパイラ」及び「特許文献２：メモリ管理方法、情報処理装置、プログラムの作成方法及びプログラム」に記載されている。具体的には特許文献１及び特許文献２にはマクロタスクグラフが記載されており、このマクロタスクグラフは一種のデータフローグラフである。
【０００６】
より具体的には特許文献２の明細書段落［００４８］の記載によると、特許文献２におけるマルチグレイン並列処理は、以下の三段階の手順により並列処理可能なソフトウェアを得る。
【０００７】
手順１）ソースプログラムからマクロタスクを生成する。
【０００８】
手順２）マクロタスク間の制御フロー及びデータ依存を解析しマクロフローグラフを生成する。
【０００９】
手順３）最早実行可能条件解析によってマクロタスクグラフを生成する。
【００１０】
このようなデータフロー型並列処理においては通常、処理の実行単位を「タスク」と呼ぶ。そして、或るタスクについての計算を始める前に、この或るタスクが計算に使用するデータが利用可能な状態にあるか否かを確認する必要がある。
【００１１】
本明細書、本発明及び本図面等では、この確認のことを「待ち合わせ」と呼ぶことにする。「待ち合わせ」の実現手段は一般的には通信やフラグなどである。「待ち合わせ」は逐次処理を行う際には不要であり、並列処理を行う為に必要となるオーバーヘッドである。また、待ち合わせが生じた場合であって各タスクを処理するプロセッサが異なる場合には、待ち合わせている間、一方のプロセッサが他方のプロセッサの演算処理を待つこととなる。これによりプロセッサの稼働率が低下し、これに伴い演算処理の効率も低下してしまう。
【００１２】
従って、「待ち合わせ」に要する時間やその回数をできるだけ少なくすることが、並列処理の効率を高めることにつながる。
【００１３】
そこでこの点に鑑みた、「待ち合わせ」の回数を削減する技術が「特許文献３：並列処理装置」で開示されている。
【００１４】
特許文献３に記載の技術では、「待ち合わせ」回数を削減する方法として、タスク結合について述べている。結合されたタスクの間では「待ち合わせ」が不要となるため、特許文献３に記載の技術を用いれば確かに、「待ち合わせ」の回数を削減することができる。
【００１５】
一方、「特許文献４：プログラム繰り返し構造のブロック分割方法並びに同期処理位置決定方法及びプログラム変換装置」においても、タスク結合と同様な考え方によって、「待ち合わせ」の回数を削減する技術が記載されている。なお、特許文献４では、「待ち合わせ」は「同期」、「タスク結合」は「ブロック分割」、という言葉で説明されている。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特許第４０８２７０６号
【特許文献２】特開２００８−２１７１３４号公報
【特許文献３】特許第３０３９９５３号
【特許文献４】特開平２−１６３８３３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１７】
以上説明したように、データフロー型並列処理において、タスクの計算を開始可能か否かを確認する「待ち合わせ」に要する時間やその回数をできるだけ減らすべき、という課題がある。
【００１８】
その解決策の一つとして、上述したように特許文献３や特許文献４に記載の「タスク結合」という手段が知られているが、これらの技術を用いたとしても全てのタスクを結合できる訳では無い。よって、タスク結合は「待ち合わせ」の回数をある程度削減できるものの、依然として、結合されていないタスク間の「待ち合わせ」は残ることとなる。
【００１９】
従って、タスク結合以外にも、「待ち合わせ」の回数を更に削減する技術が求められている。
【００２０】
そこで本発明は、データフローグラフで表現可能なプログラムを少ない回数の「待ち合わせ」で並列処理するための、プロセッサ間待ち合わせエッジ群生成装置、その方法、そのプログラム及びエッジ群を格納した記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明の第１の観点によれば、プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成装置であって、前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、を備えることを特徴とするエッジ群生成装置が提供される。
【００２２】
本発明の第２の観点によれば、プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を記録したコンピュータ読取り可能な記録媒体であって、前記プロセッサ間待ち合わせエッジ群が、前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、により生成されたプロセッサ間待ち合わせエッジ群であることを特徴とするコンピュータ読取り可能な記録媒体が提供される。
【００２３】
本発明の第３の観点によれば、プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成方法であって、前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出ステップと、前記候補群抽出ステップにおいて抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去ステップと、を有することを特徴とするエッジ群生成方法が提供される。
【００２４】
本発明の第４の観点によれば、プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成装置としてコンピュータを機能させるための待ち合わせエッジ群生成プログラムであって、前記コンピュータを、前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、を備えるエッジ群生成装置として機能させることを特徴とする待ち合わせエッジ群生成プログラムが提供される。
【発明の効果】
【００２５】
本発明によれば、データフローグラフで表現可能なプログラムを少ない回数の「待ち合わせ」で並列処理させることが可能となる。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施形態の基本的構成を表すブロック図である。
【図２】本発明の実施形態における除去部の基本的構成を表すブロック図である。
【図３】本発明の実施形態における除去可能な待ち合わせエッジの第１のパターンを表す概念図である。
【図４】本発明の実施形態における除去可能な待ち合わせエッジの第２のパターンを表す概念図である。
【図５】本発明の実施形態における除去可能な待ち合わせエッジの第３のパターンを表す概念図である。
【図６】本発明の実施形態における除去可能な待ち合わせエッジの第４のパターンを表す概念図である。
【図７】本発明の実施形態における除去可能な待ち合わせエッジの基本除去可能エッジ含有パターンを表す概念図である。
【図８】本発明の実施形態の基本的動作を表すフローチャートである。
【図９】除去可能な待ち合わせエッジの第一および第二のパターンの具体例を表すためのデータフローグラフを表す概念図である。
【図１０】データフローグラフ図９に関して、トポロジカルソートに基づいた順序番号を付加したデータフローグラフを表す概念図である。
【図１１】データフローグラフ図９に関して、待ち合わせエッジ候補となるエッジを表す概念図である。
【図１２】データフローグラフ図９に関して、除去可能な待ち合わせエッジの第１および第２のパターンの具体例を表す概念図である。
【図１３】除去可能な待ち合わせエッジの第３および第４のパターンの具体例を表すためのデータフローグラフを表す概念図である。
【図１４】データフローグラフ図１３に関して、トポロジカルソートに基づいた順序番号を付加したデータフローグラフを表す概念図である。
【図１５】データフローグラフ図１３に関して、待ち合わせエッジ候補となるエッジを表す概念図である。
【図１６】データフローグラフ図１３に関して、除去可能な待ち合わせエッジの第３および第４のパターンの具体例を表す概念図である。
【図１７】本発明の実施形態を実装する場合の一例を表す概念図である。
【図１８】本発明の実施形態の一利用例を表すブロック図である。
【図１９】本発明の実施形態の一利用例の基本的動作を表すフローチャートである。
【図２０】本発明の実施形態を実現する場合のハードウェア構成の一例を表すブロック図である。
【発明を実施するための形態】
【００２７】
次に、本発明の実施形態について図面を参照して詳細に説明する。
【００２８】
まず、本実施形態の説明をするにあたり、本実施形態が処理対象とする並列処理モデル及びトポロジカルソートに関して説明をする。
【００２９】
＜本実施形態が対象とする並列処理モデル＞
本実施形態が扱う並列処理について説明する。本実施形態は、非循環型有向グラフ（ＤＡＧ：directed acyclic graph)に属するデータフローグラフで表現可能な並列処理を扱う。以降では、特に限定しない場合、「データフローグラフ」は非循環型有向グラフに属するものとする。
【００３０】
データフローグラフは、並列処理を構成する計算処理のデータ依存関係を表すグラフ構造である。並列処理を構成する計算処理をタスクと呼ぶことにする。また、データフローグラフにおいて、ノードはタスクを表し、ノード間のエッジはタスク間のデータ依存関係を表す。データフローグラフを使うことにより、対象となる並列処理を構成するタスクのデータ依存関係を簡単に表現することができる。
【００３１】
また、ここでいう「データ依存関係」とは、タスクが使用するデータに関してデータ供給タスクの役割を果たすタスクとデータ使用タスクの役割を果たすタスクとの間の依存関係である。
【００３２】
例えば、タスクＴ１の計算結果Ｒ１をタスクＴ２が使用する場合を想定する。この場合には、データＲ１に関して、タスクＴ１はデータ供給タスクであり、タスクＴ２はデータ使用タスクである。そして、このような場合にデータ供給タスクであるタスクＴ１からデータ使用タスクであるタスクＴ２に対してデータ依存関係が存在すると言える。そして、タスクＴ１からタスクＴ２に対してデータ依存関係が存在するなら、タスクＴ２はタスクＴ１の後で実行されなければならない。
【００３３】
さらに、本実施形態が扱う並列処理では、データフローグラフで表現可能な計算処理を複数のプロセッサ又は複数のコア（以下、プロセッサとコアとを含めて「プロセッサ」という。）で並列に計算するものとし、データフローグラフの各タスクをどのプロセッサが実行するかが予め決定されているものとする。どのプロセッサがどのタスクを実行するかという情報は、データフローグラフの付属情報とする。本実施形態は、このようなデータフローグラフで表現可能な計算処理の並列化を扱う。
【００３４】
＜トポロジカルソートについて＞
続いて、トポロジカルソート（topological sort）について説明する。ここで、以下の説明においては、各タスクを、それぞれ「ノード」と呼ぶ。また、データ供給タスクを表すノード、すなわちデータ供給ノードを「出発側ノード」と呼ぶ。同様に、データ使用タスクを表すノード、すなわちデータ使用ノードを「到着側ノード」と呼ぶ。
【００３５】
そして、トポロジカルソートとは、データフローグラフで表される各ノードを、どの出発側ノードも当該ノードにとっての到着側ノードよりも順序的に前に来るように順序付けし、並べかえることである。
【００３６】
トポロジカルソートの典型的な利用例は、タスクのスケジューリングや、コンパイラにおける命令スケジューリングである。つまり、データ依存関係をもつタスクセットをデータフローグラフで表現し、そのデータフローグラフをトポロジカルソートすることによって、タスクを実行すべき順序がわかることになる。トポロジカルソートで得られる順序は、一つだけとは限らず、複数の正しい順序が存在しうる。
【００３７】
＜本発明の実施形態＞
図１を参照して本発明の実施形態であるプロセッサ間待ち合わせエッジ群生成装置１００が含む機能ブロックについて説明する。
【００３８】
図１を参照するとプロセッサ間待ち合わせエッジ群生成装置１００は、入力受付部１０１、ソート部１０２、番号付与部１０３、候補群抽出部１０４、除去部１０５及び出力部１０６を含む。ここで、プロセッサ間待ち合わせエッジ群生成装置１００は、データフローグラフとして表現可能な並列処理を対象として、冗長な待ち合わせをしないことによって、対象とする並列処理においてプロセッサを効率よく活用することを目的とする装置である。なお、プロセッサ間待ち合わせエッジ群生成装置１００は本実施形態専用の装置であるか汎用の装置であるかを問わず任意の装置にて実現しうるが、この点に関しては後述する。
【００３９】
入力受付部１０１は、プロセッサ間待ち合わせエッジ群生成装置１００の外部よりデータフローグラフの入力を受け付け、受け付けたデータフローグラフをソート部１０２へ出力する部分である。このデータフローグラフは、ノードが表すタスクを、複数存在するプロセッサの内のどのプロセッサが実行するか、という付属情報を含むものとする。なお、今回の説明においてはデータフローグラフを受け付けることとしているが、例えば入力受付部１０１はソースプログラムの入力を受け付け、入力受付部１０１がこのソースプログラムをデータフローグラフへと変換処理するようにしても良い。
【００４０】
入力受付部１０１は例えば入力受付部１０１に接続された記憶装置からデータフローグラフを受け付けても良い。また、何らかのネットワークを介してデータフローグラフを受け付けても良い。更には、ユーザがキーボード等の入力装置にて入力したデータフローグラフを受け付けても良い。
【００４１】
ソート部１０２は、トポロジカルソートを実行する部分である。具体的には、入力受付部１０１から送信されたデータフローグラフに対してトポロジカルソートを実行する。トポロジカルソートの実行結果は番号付与部１０３に出力される。
【００４２】
番号付与部１０３は、ソート部１０２のトポロジカルソートの結果得られた順序番号をデータフローグラフの各ノードに付与する。また、データフローグラフの付属情報を参照し、ノードが表すタスクを実行するプロセッサ毎に、各ノードを分類する。番号付与部１０３の処理結果は候補群抽出部１０４に出力される。
【００４３】
候補群抽出部１０４は、番号付与部１０３の処理結果を参照し、或るプロセッサに割り当てられた出発側ノードと、この或るプロセッサとは異なる他のプロセッサに割り当てられた到着側ノードとをつなぐ１以上のエッジを”プロセッサ間の待ち合わせに係るエッジの候補群”（以下、「プロセッサ間待ち合わせエッジの候補群」という。）として抽出する。そして、候補群抽出部１０４は抽出したプロセッサ間待ち合わせエッジの候補群を除去部１０５に出力する。
【００４４】
除去部１０５は、候補群抽出部１０４から送信されてきた”プロセッサ間待ち合わせエッジの候補群“の中から、後述する除去可能エッジ含有パターンに該当するエッジを見つけ除去する。そして、除去されずに残ったエッジが含まれる”プロセッサ間待ち合わせエッジの候補群”（以下、「確定プロセッサ間待ち合わせエッジ群」という。）を出力部１０６へと送信する。
【００４５】
出力部１０６は、除去部１０５から送信されてきた“確定プロセッサ間待ち合わせエッジ群”を出力する。出力は所定の記録媒体に記録することにより行われても良いし、外部ネットワークに送出することにより行われても良いし、ディスプレイ等の表示装置に表示することにより行われても良い。
【００４６】
プロセッサ群は、実行時に、“確定プロセッサ間待ち合わせエッジ群”を記録媒体から読み込んで、それに含まれる各エッジについて、待ち合わせを行う。すなわち、この場合における「記録媒体」とは、各プロセッサの内部又は外部に設けられた主記憶装置や、各プロセッサが読み書き可能な補助記憶装置に相当する。
【００４７】
続いて、図２を参照して除去部１０５の詳細な内容について説明する。図２を参照すると除去部１０５は、第１の除去部１０５−１、第２の除去部１０５−２、第３の除去部１０５−３及び第４の除去部１０５−４を含む。
【００４８】
第１の除去部１０５−１、第２の除去部１０５−２、第３の除去部１０５−３及び第４の除去部１０５−４にはそれぞれに対して異なる除去可能エッジ含有パターンが割り当てられている。そして、第１の除去部１０５−１、第２の除去部１０５−２、第３の除去部１０５−３及び第４の除去部１０５−４は、候補群抽出部１０４又は前段の除去部１０５−ｉ（ｉ＝１、２、又は、３）より送信されてきた、プロセッサ間待ち合わせエッジの候補群に除去可能エッジ含有パターンに該当するプロセッサ間待ち合わせエッジの候補群が含まれているのかを確認する。そして、含まれていた場合には除去可能エッジ含有パターンに該当するプロセッサ間待ち合わせエッジの候補を除去し、後段の除去部１０５−ｉ（ｉ＝２、３、又は、４）又は出力部１０６へと送信する。
【００４９】
＜除去可能エッジ含有パターン＞
次に、第１の除去部１０５−１、第２の除去部１０５−２、第３の除去部１０５−３及び第４の除去部１０５−４に割り当てる４種類のパターンについて説明する。除去部１０５は、”プロセッサ間待ち合わせエッジの候補群”に含まれる或るエッジがこの４種類のパターンの何れかに一致した場合、当該或るエッジをその”プロセッサ間待ち合わせエッジの候補群”から除去する。当該或るエッジが”プロセッサ間待ち合わせエッジの候補群”から除去されるということは、当該或るエッジに係る待ち合せが不要となることを意味する。以降では、”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジを表すパターンのことを「除去可能エッジ含有パターン」と称することにする。
【００５０】
なお、除去部１０５は、４種類の除去可能エッジ含有パターンをあらゆる組み合わせや順序で適用することができる。例えば、何れか一つの除去可能エッジ含有パターンのみを採用する場合には、その採用した除去可能エッジ含有パターンを第１の除去部１０５−１に割当て、他の第２の除去部１０５−２、第３の除去部１０５−３及び第４の除去部１０５−４は省略するようにしても良い。また、第１の除去部１０５−１と第２の除去部１０５−２に、第１の除去可能エッジ含有パターンと第２の除去可能エッジ含有パターンとを、それぞれ、適用しても良いし、第３の除去可能エッジ含有パターンと第４の除去可能エッジ含有パターンとを、それぞれ、適用しても良い。第１の除去部１０５−１乃至第３の除去部１０５−３に、第１の除去可能エッジ含有パターン乃至第３の除去可能エッジ含有パターンを、任意の順序で、適用しても良いし、第２の除去可能エッジ含有パターン乃至第４の除去可能エッジ含有パターンを、任意の順序で、適用しても良い。
【００５１】
また、以下の説明においてはノード間の依存関係であるエッジを「−＞」を用いて表記する。例えばノードＮ１がデータ供給ノードであり、ノードＮ２がデータ使用ノードであるというエッジを、「エッジＮ１−＞Ｎ２」と表記する。また、このエッジをノードＮ１からのエッジ又はノードＮ２に対してのエッジとも呼ぶ。また、データ供給ノードは本発明の「出発側ノード」に相当し、データ使用ノードは本発明の「到着側ノード」に相当する。
【００５２】
また、図面においては例えば図３の上段に「Ｎ１」と表されているように各ノードを「Ｎ＊」と表記する。更に各ノードをそれぞれ丸で囲む。ここで、「＊」はトポロジカルソートによって付与されたノード番号（順序番号）に相当する。更に複数のノードが並んでいる場合にノードの処理は左側から右側へと順番に行われていくものとする。
【００５３】
また、エッジに関してはノード間を矢印にて接続することにより図示をする。例えば、ノードＮ１がデータ供給ノードであり、ノードＮ２がデータ使用ノードであるというエッジ、すなわち「エッジＮ１−＞Ｎ２」であれば図３のもっとも左に表されるように図示する。
【００５４】
更に、以降の説明では、簡単のために、プロセッサがノードに対応するタスクを実行することを、単に、プロセッサはノードを実行する、と表現する場合もある。この表現において、実行されるのはノードに対応するタスクである。
【００５５】
＜第１除去可能エッジ含有パターン＞
第１除去可能エッジ含有パターンは、第１プロセッサに割り当てられた１つの第１ノードと、第２プロセッサに割り当てられた複数の第２ノードを含むと共に、何れの第２ノードも第１ノードを出発側ノードとし、当該第２ノードを到着側ノードとするエッジをもつ。第１除去可能エッジ含有パターンにおいて、最小の順序番号をもつ第２ノードへのエッジを除いて、第１ノードから複数の第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする。
【００５６】
例えば、図３に示すように、プロセッサｍに割り当てられたノードＮ１と、プロセッサｎに割り当てられたノードＮ２、ノードＮ３、ノードＮｎがあり、ノードＮ２、ノードＮ３、．．．、ノードＮｎはノードＮ１を出発側ノードとしている場合、ノードＮ１、ノードＮ２、ノードＮ３、．．．、ノードＮｎとエッジＮ１−＞Ｎ２、エッジＮ１−＞Ｎ３、．．．、エッジＮ１−＞Ｎｎは第１除去可能エッジ含有パターンを構成する。このような場合、ノードＮ１を出発側ノードとする複数のエッジの到着側ノードの中で最小の順序番号を有するのはノードＮ２なので、ノードＮ２に対応するエッジＮ１−＞Ｎ２以外のエッジであるエッジＮ１−＞Ｎ３、．．．、及びエッジＮ１−＞Ｎｎを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする。
【００５７】
一方で、第１除去可能エッジ含有パターンを適用した場合には、エッジＮ１−＞Ｎ２は除去可能なエッジではない。そのため、図３においてエッジＮ１−＞Ｎ２については「除去可能」な旨が記載されていない。もっとも、これは図３において第１除去可能エッジ含有パターンのみを考慮しているからであり、以下において説明する他の除去可能エッジ含有パターンを考慮した場合にはエッジＮ１−＞Ｎ２が除去対象となることもあり得る。これは、図４乃至７の何れにおいても同様であり、各図において説明対象としている除去可能エッジ含有パターンを適用した場合についてのみ「除去可能」な旨を記載しているが、これは他の除去可能エッジ含有パターンを適用した場合であっても除去可能とはならない旨を意味するものではない。
【００５８】
第１除去可能エッジ含有パターンに基づいて一部のエッジ（図３の例ではエッジＮ１−＞Ｎ３、．．．、及びエッジＮ１−＞Ｎｎ）が”プロセッサ間待ち合わせエッジの候補群”から除去可能な理由は、以下の通りである。
【００５９】
まず、トポロジカルソートによって付与されたノード番号（順序番号）を使うと、ノードＮｊを出発側ノードとしてノードＮｋを到着側ノードとするエッジがある場合、ノード番号の大小関係はＮｊ＜Ｎｋである。そして、本実施形態では、プロセッサは、割り当てられたノードに対応するタスクをノード番号が小さい順に実行することとしている。例えば図３に表される例の場合であれば、この実行順序の考え方に基づいて、プロセッサｎは、ノードＮ２、ノードＮ３、．．．、ノードＮｎという順番で対応するタスクを実行する。つまり、エッジＮ１−＞Ｎ２で待ち合せる前にノードＮ２、ノードＮ３、．．．、ノードＮｎが実行されることはなく、エッジＮ１−＞Ｎ２で待ち合せた後に、ノードＮ２、ノードＮ３、．．．、ノードＮｎが順次実行される。従って、ノードＮ３からＮｎの実行開始時には既にノードＮ１は実行完了していることになり、改めてノードＮ３やＮｎでノードＮ１の完了を待ち合わせる必要は無い。
【００６０】
よって、ノードＮ１を共通の出発側ノードとして有し、ノードＮ３、．．．、ノードＮｎをそれぞれの到着側ノードとして有するエッジＮ１−＞Ｎ３、．．．、及びエッジＮ１−＞Ｎｎを”プロセッサ間待ち合わせエッジの候補群”から除去することにより、動作に支障を与えることなく、待ち合わせの数を削減することができる。
【００６１】
＜第２除去可能エッジ含有パターン＞
第２除去可能エッジ含有パターンは、第１プロセッサに割り当てられた複数の第１ノードと、第２プロセッサに割り当てられた１つの第２ノードを含むと共に、何れの第１ノードも当該第１ノードを出発側ノードとし、第２ノードを到着側ノードとするエッジをもつ。第２除去可能エッジ含有パターンにおいて、最大の順序番号をもつ第１ノードからのエッジを除く、複数の第１ノードから第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする。
【００６２】
例えば、図４に示すように、プロセッサｍに割り当てられたノードＮ１、ノードＮ２，．．．、ノードＮｍと、プロセッサｎに割り当てられたノードＮｎがあり、ノードＮ１、ノードＮ２、．．．、ノードＮｍはノードＮｎを到着側ノードとしている場合、ノードＮ１、ノードＮ２、．．．、ノードＮｍ、ノードＮｎとエッジＮ１−＞Ｎｎ、エッジＮ２−＞Ｎｎ、．．．、エッジＮｍ−＞Ｎｎは第２除去可能エッジ含有パターンを構成する。この場合、ノードＮｎを到着側ノードとする複数のエッジの出発側ノードの中で最大の順序番号を有するのはノードＮｍなので、ノードＮｍに対応するエッジＮｍ−＞Ｎｎ以外のエッジであるエッジＮ１−＞Ｎｎ、エッジＮ２−＞Ｎｎ、及びエッジ．．．−＞Ｎｎを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする。第２除去可能エッジ含有パターンに基づいて一部のエッジ（図４の例ではエッジＮ１−＞Ｎｎ、エッジＮ２−＞Ｎｎ、及びエッジ．．．−＞Ｎｎ）が除去可能な理由は、以下の通りである。
【００６３】
第１除去可能エッジ含有パターンと同様な仮定に基づき、ノードＮ１、ノードＮ２、．．．、ノードＮｍは、プロセッサｍによってノード番号が小さいものから順にノードＮ１、ノードＮ２、．．．、ノードＮｍという順番で実行される。そのため、ノードＮｍの実行が完了したときには、その他のノードＮ１、ノードＮ２、ノード．．．、の実行が完了していることは明らかである。従って、ノードＮｎは、エッジＮｍ−＞Ｎｎに関連してノードＮｍの実行完了さえ待ち合わせておけばよく、エッジＮ１−＞ＮｎやエッジＮ２−＞Ｎｎに関連してノードＮ１やノードＮ２の実行完了を確認する必要はない。
【００６４】
よって、ノードＮ１、ノードＮ２、ノード．．．、をそれぞれの出発側ノードとして有し、ノードＮｎを共通の到着側ノードとして有するエッジＮ１−＞Ｎｎ、エッジＮ２−＞Ｎｎ、エッジ．．．−＞Ｎｎを”プロセッサ間待ち合わせエッジの候補群”から除去することにより、動作に支障を与えることなく、待ち合わせの数を削減することができる。
【００６５】
＜第３除去可能エッジ含有パターン＞
第３除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第３プロセッサに割り当てられた第３ノードを含み、第１ノードから第２ノードへの第１エッジあるいは部分データフローグラフと、第２ノードから第３ノードへの第２エッジと、第１ノードから第３ノードへの第３エッジとをもつ。ここで、前記の「部分データフローグラフ」とは、第１ノードを出発側ノードとし、第２ノードを到着側ノードとするノードとエッジを含むデータフローグラフである。なお、部分データフローグラフに含まれるノードとエッジについては特に限定は無く、第１ノードを出発側ノード、第２ノードを到着側ノード、とするという条件を満たすのであればどのようなノードとエッジが含まれていて良い。第３除去可能エッジ含有パターンにおいて、第３エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする。
【００６６】
例えば、図５に示すように、プロセッサｍに割り当てられたノードＮｍと、プロセッサｎに割り当てられたノードＮｎと、プロセッサｚに割り当てられたＮｚと、エッジＮｍ−＞Ｎｚ、エッジＮｎ−＞Ｎｚがあり、ノードＮｍからノードＮｎへ至る部分データフローグラフ（図中では「ネットワークＮＷ」と表す。）が存在する場合、ノードＮｍ、ノードＮｎ、ノードＮｚとエッジＮｍ−＞Ｎｚ、エッジＮｎ−＞ＮｚとノードＮｍからノードＮｎへ至る部分データフローグラフは第３除去可能エッジ含有パターンを構成する。このような場合、エッジＮｍ−＞Ｎｚを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする。
【００６７】
第３除去可能エッジ含有パターンに基づいて第３エッジ（図５のエッジＮｍ−＞Ｎｚ）を”プロセッサ間待ち合わせエッジの候補群”から除去可能な理由は、以下の通りである。
【００６８】
それぞれが相互に異なるプロセッサに割り当てられたノードＮｍとノードＮｎに対して、ノードＮｍからノードＮｎへ至る経路（すなわち、エッジ又は部分データフローグラフ）が存在するということは、その経路のどこかにおいてノードＮｍの実行完了を確認（待ち合わせ）する必要があり、その確認はノードＮｎの実行開始前には終わっていることを意味する。ノードＮｍからノードＮｎへの経路が単なるエッジである場合には、プロセッサｎがノードＮｎを実行する前に、ノードＮｍの実行完了確認（待ち合せ）が行われることになる。もしその経路が部分データフローグラフである場合には、その部分データフローグラフの中のプロセッサｍ以外のプロセッサに割り当てられたいずれかのノードの実行前にノードＮｍの実行完了確認（待ち合わせ）が行われる。図５では、ノードＮｍの実行完了確認（待ち合わせ）が行われるノードをＰｍと名付けて、ノードＮｍからノードＮｎへ至る経路に部分データフローグラフ（ネットワークＮＷ）が存在し、このネットワーク内にノードＰｍが存在している場合について図示している。
【００６９】
一方、ノードＮｚに注目すると、ノードＮｎとＮｚは互いに異なるプロセッサｎとプロセッサｚに割り当てられており、エッジＮｎ−＞Ｎｚが存在するため、ノードＮｚの実行前に、ノードＮｎの実行完了確認（待ち合わせ）が必要となる。既に説明したように、ノードＮｎの実行前にはノードＮｍの実行完了確認（待ち合わせ）が完了している。つまり、ノードＮｎの実行完了が確認できれば、ノードＮｍの実行完了も確認できていることになる。従って、ノードＮｚの実行を担当するプロセッサｚは、ノードＮｚにおいて、エッジＮｍ−＞Ｎｚに関連したノードＮｍの実行完了を改めて待ち合わせる必要はない。
【００７０】
よって、第３除去可能エッジ含有パターン中の第３エッジ（図５におけるエッジＮｍ−＞Ｎｚ）を”プロセッサ間待ち合わせエッジの候補群”から除去することにより、動作に支障を与えることなく、待ち合わせの数を削減することができる。
【００７１】
＜第４除去可能エッジ含有パターン＞
第４除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノード及び第２ノードと、第２プロセッサに割り当てられた第３ノード及び第４ノードを含み、第１ノードから第４ノードへの第１エッジと、第２ノードから第３ノードへの第２エッジを持ち、更に、トポロジカルソートにもとづく順序番号に関して、第１ノードの順序番号は第２ノードの順序番号よりも小さく、第３ノードの順序番号は第４ノードの順序番号よりも小さい。第４除去可能エッジ含有パターンにおいて、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする。
【００７２】
例えば、図６に示すように、プロセッサｍに割り当てられたノードＮａ及びノードＮｍと、プロセッサｎに割り当てられたノードＮｎ及びノードＮｚと、エッジＮａ−＞Ｎｚ、エッジＮｍ−＞Ｎｎがあり、トポロジカルソートに基づいた順序番号に関して、ノードＮａの順序番号がノードＮｍの順序番号よりも小さく、ノードＮｎの順序番号がノードＮｚの順序番号よりも小さい場合には、ノードＮａ、Ｎｍ、ノードＮｎ、ノードＮｚとエッジＮａ−＞Ｎｚ、エッジＮｍ−＞Ｎｎは第４除去可能エッジ含有パターンを構成する。このような場合、エッジＮｍ−＞Ｎｎを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする。
【００７３】
第４除去可能エッジ含有パターンに基づいて第１エッジ（図６のエッジＮｍ−＞Ｎｎ）を”プロセッサ間待ち合わせエッジの候補群”から除去可能な理由は、以下の通りである。
【００７４】
第１除去可能エッジ含有パターンと同様な仮定に基づき、ノードＮａ、ノードＮｍは、ノード番号が小さいものから順にノードＮａ、ノードＮｍという順番でプロセッサｍにより実行される。また、ノードＮｎ、ノードＮｚは、ノード番号が小さいものから順にノードＮｎ、ノードＮｚという順番でプロセッサｎにより実行される。従って、ノードＮｎとノードＮｚの実行を担当するプロセッサｎは、ノードＮｎの実行前に、エッジＮｍ−＞Ｎｎに関してノードＮｍの実行完了を確認し、続いてノードＮｚの実行前に、エッジＮａ−＞Ｎｚに関してノードＮａの実行完了を確認する。この一連の流れにおいて、ノードＮａはノードＮｍよりも先に実行されるため、ノードＮｍの実行が完了したときにはノードＮａも実行完了している。そのため、エッジＮｍ−＞ＮｎでノードＮｍの実行完了を確認したならば、エッジＮａ−＞ＮｚでノードＮａの実行完了を改めて確認する必要はない。
【００７５】
よって、第４除去可能エッジ含有パターン中の第１エッジ（図６におけるエッジＮａ−＞Ｎｚ）を”プロセッサ間待ち合わせエッジの候補群”から除去することにより、動作に支障を与えることなく、待ち合わせの数を削減することができる。
【００７６】
＜基本除去可能エッジ含有パターン＞
また、本実施形態では除去可能エッジパターンを、上記説明した第１除去パターン、第２除去可能エッジ含有パターン、第３除去可能エッジ含有パターン及び第４除去可能エッジ含有パターンのそれぞれを内包する基本除去可能エッジ含有パターンとして捉えることもできる。
【００７７】
ここで基本除去可能エッジ含有パターンは、図７に示すように、例えば『第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第２ノードよりも先になおかつ第１ノードよりも後に実行される第３ノードと、第１ノードから第２ノードへの第１エッジと、を含むようなデータフローグラフ』は基本除去可能エッジ含有パターンである。このような基本除去可能エッジ含有パターンにおいては、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとすることができる。
【００７８】
例えば、上述した第１除去可能エッジ含有パターンを、仮に、上記で表す基本除去可能エッジ含有パターンとして捉えた場合には、基本除去可能エッジ含有パターンにおける、第１ノードは図３のノードＮ１に相当し、第２ノードは図３のノードＮ３、．．．、Ｎｎに相当し、第３ノードは図３のノードＮ２相当し、第１エッジは図３のエッジＮ１−＞Ｎ３、．．．Ｎ１−＞Ｎｎに相当することとなる。さらに、図３では、エッジＮ１−＞Ｎ２の存在によって、ノードＮ１（第１ノード）よりも後にノードＮ２（第３ノード）が実行され、プロセッサｎにおける実行順序によって、ノードＮ３、．．．、Ｎｎ（第２ノード）よりも先にノードＮ２（第３ノード）が実行されるため、図３のパターンを基本除去可能エッジ含有パターンとみなすことが可能である。
【００７９】
また、上述した第２除去可能エッジ含有パターンを、仮に、上記で表す基本除去可能エッジ含有パターンとして捉えた場合には、基本除去可能エッジ含有パターンにおける、第１ノードは図４のノードＮ１、ノードＮ２、．．．に相当し、第２ノードは図４のノードＮｎに相当し、第３ノードは図４のノードＮｍに相当し、第１エッジは図４のエッジＮ１−＞Ｎｎ、エッジＮ２−＞Ｎｎ、エッジ．．．−＞Ｎｎに相当することとなる。さらに、図４では、プロセッサｍにおける実行順序によって、ノードＮ１，Ｎ２、．．．（第１ノード）よりも後にノードＮｍ（第３ノード）が実行され、エッジＮｍ−＞Ｎｎの存在によって、ノードＮｎ（第２ノード）よりも先にノードＮｍ（第３ノード）が実行されるため、図４のパターンを基本除去可能エッジ含有パターンとみなすことが可能である。
【００８０】
更に、上述した第３除去可能エッジ含有パターンを、仮に、上記で表す基本除去可能エッジ含有パターンとして捉えた場合には、基本除去可能エッジ含有パターンにおける、第１ノードは図５のノードＮｍに相当し、第２ノードは図５のノードＮｚに相当し、第３ノードは図５のノードＮｎに相当し、第１エッジは図５のエッジＮｍ−＞Ｎｚに相当することとなる。さらに、図５では、ノードＮｍからノードＮｎへの経路であるネットワークＮＷの存在によって、ノードＮｍ（第１ノード）よりも後にノードＮｎ（第３ノード）が実行され、エッジＮｎ−＞Ｎｚの存在によって、ノードＮｚ（第２ノード）よりも先にノードＮｎ（第３ノード）が実行されるため、図５のパターンを基本除去可能エッジ含有パターンとみなすことが可能である。
【００８１】
更に、上述した第４除去可能エッジ含有パターンを、仮に、上記で表す基本除去可能エッジ含有パターンとして捉えた場合には、基本除去可能エッジ含有パターンにおける、第１ノードは図６のノードＮａに相当し、第２ノードは図６のノードＮｚに相当し、第３ノードは図６のノードＮｎに相当し、第１エッジは図６のエッジＮａ−＞Ｎｚに相当することとなる。さらに、図６では、プロセッサｍにおける実行順序およびエッジＮｍ−＞Ｎｎの存在によって、ノードＮａ（第１ノード）よりも後にノードＮｎ（第３ノード）が実行され、プロセッサｎにおける実行順序によって、ノードＮｚ（第２ノード）よりも先にノードＮｎ（第３ノード）が実行されるため、図６のパターンを基本除去可能エッジ含有パターンとみなすことが可能である。
【００８２】
＜フローチャートに基づいた基本動作の説明＞
続いて、図８に表されるフローチャートを参照して、本実施形態の基本的動作について説明する。
【００８３】
まず、入力受付部１０１が、本実施形態の処理対象となるデータフローグラフを受け付ける（ステップＳ１１）。
【００８４】
次に、ソート部１０２は、ステップＳ１１にて受け付けたデータフローグラフに対してトポロジカルソートを実行する（ステップＳ１３）。
【００８５】
続いて、番号付与部１０３は、ステップＳ１３におけるトポロジカルソートの実行結果に応じて、トポロジカルソートして得られる順序番号を各ノードに付与する（ステップＳ１５）。これにより、番号付与部１０３は、ノードの順序番号が小さいほど先に実行される、というデータフローグラフの実行順序を表す数値（順序番号）を各ノードに付与することとなる。また、番号付与部１０３は、ノードを実行するプロセッサ毎に各ノードを分類する（ステップＳ１５）。
【００８６】
候補群抽出部１０４は、ステップＳ１５の処理結果を参照し、プロセッサ間待ち合わせエッジの候補群をデータフローグラフから抽出する（ステップＳ１７）。プロセッサ間待ち合わせエッジの候補群の抽出基準は、それぞれが相互に異なるプロセッサに割り当てられたノードをつなぐエッジを、プロセッサ間待ち合わせエッジの候補群に含める、というものである。
【００８７】
本実施形態で、処理対象となるデータフローグラフでは、どのプロセッサがどのノードを実行するかということに対応したノード割当が予め設定されているものとしている。別々のプロセッサに割り当てられたノードの間に依存関係がもし存在する場合、一方のノードの実行が完了するまで、他方のノードは、前記一方のノードの実行の完了を待ち合せ、その完了の後に自ノードの実行を開始する必要がある。従って、これらのノードをつなぐエッジをタスク間待ち合わせエッジの候補群の１つとする。
【００８８】
続いて、除去部１０５は、ステップＳ１７において抽出されたプロセッサ間待ち合わせエッジの候補群の中から、本実施形態が規定する４つの除去可能エッジ含有パターン中の除去できる１以上のエッジにそれぞれ該当する１以上のエッジを除去する（ステップＳ１９）。このステップＳ１９における、該当するか否かの確認は４つの除去可能エッジ含有パターン全てに関して行われても良いし、効果は下がるものの、４つの除去可能エッジ含有パターンのうちの一部のみに関して行われても良い。また、一通りの除去が終了したならば、残ったエッジ群が構成するデータフローグラフのパターンが変化しており、新たに除去可能エッジ含有パターンが含まれることとなっている可能性があるので、除去するべきエッジがなくなるまで、ステップＳ１９を繰り返して実行してもよい。
【００８９】
最後に、出力部１０６は、ステップＳ１９においてプロセッサ間待ち合わせエッジの候補群から除去されなかった１以上のエッジより構成される確定プロセッサ間待ち合わせエッジ群を出力する（ステップＳ２１）。
【００９０】
以上により本実施形態の動作は終了する。
【００９１】
続いて、具体的なノード及びエッジの例を用いて本実施形態の処理に関しより具体的に説明を行う。今回の説明においては上述した除去可能エッジ含有パターンを幾つか組合せて処理を行うものとし、第１除去可能エッジ含有パターンと第２除去可能エッジ含有パターンとを用いた具体例と、第３除去可能エッジ含有パターンと第４除去可能エッジ含有パターンとを用いた具体例とについてそれぞれ説明する。
【００９２】
＜第１除去可能エッジ含有パターと第２除去可能エッジ含有パターンとを用いた具体的例＞
第１除去可能エッジ含有パターンと第２除去可能エッジ含有パターンとを用いた具体的例について、図３、図４、図９乃至図１２などを参照して説明する。
【００９３】
まず、待ち合わせポイント決定処理の対象となるデータフローグラフを図９に示す。図９に示すデータフローグラフにおいては８個のノードがあり、これらのノードが３個のプロセッサに割り当てられている。
【００９４】
まず、図９のデータフローグラフを対象として、番号付与部１０３は、ソート部１０２のトポロジカルソートの結果得られた順序番号をデータフローグラフの各ノードに付与する。
【００９５】
図１０は、番号付与部１０３がノード番号を割り当てた状態のデータフローグラフを示す。
【００９６】
続いて、候補群抽出部１０４は、図１０のデータフローグラフから、プロセッサ間待ち合わせエッジの候補の全て（すなわち、プロセッサ間待ち合わせエッジの候補群）を抽出する。図１１は、候補群抽出部１０４によって抽出されたプロセッサ間待ち合わせエッジの候補群を表す図である。図１１では、異なるプロセッサに割り当てられたノードを結ぶエッジの全てがプロセッサ間待ち合わせエッジの候補群に含まれている。
【００９７】
図１２は、図１１に示すプロセッサ間待ち合わせエッジの候補群に含まれているエッジのうち、除去部１０５が除去可能なエッジを破線で示し、除去不可能なエッジを太線で示す。図１２において、例えば、ノードＮ２、Ｎ５、Ｎ７とこれらを接続する３つのエッジＮ２−＞Ｎ５、エッジＮ５−＞Ｎ７、エッジＮ２−＞Ｎ７は、第２除去可能エッジ含有パターンに該当する。従って、第２除去可能エッジ含有パターンにおける除去可能エッジに該当するエッジＮ２−＞Ｎ７は除去可能である。同様に、ノードＮ３、Ｎ４、Ｎ７とこれらを接続する３つのエッジＮ３−＞Ｎ４、エッジＮ４−＞Ｎ７、エッジＮ３−＞Ｎ７は、第１除去可能エッジ含有パターンに該当する。従って、第１除去可能エッジ含有パターンにおける除去可能エッジに該当するエッジＮ３−＞Ｎ７は除去可能である。従って、除去部１０５は、エッジＮ２−＞Ｎ７と、エッジＮ３−＞Ｎ７を除去する。
【００９８】
除去部１０５による除去の結果、残ったエッジである確定プロセッサ間待ち合わせエッジ群は、エッジＮ１−＞Ｎ２、エッジＮ１−＞Ｎ３、エッジＮ３−＞Ｎ４、エッジＮ５−＞Ｎ７及びエッジＮ６−＞Ｎ８より構成される。
【００９９】
この確定プロセッサ間待ち合わせエッジ群に関する情報を、出力部１０６は、記録媒体に記録する。この確定プロセッサ間待ち合わせエッジ群に関する情報は、たとえば、図９のデータフローグラフで表現可能な並列処理のマルチプロセッサ用実行コードを作成するために、コード作成装置あるいはコンパイラによって使われる。コード作成装置あるいはコンパイラは、この確定プロセッサ間待ち合わせエッジ群に関する情報を参照して、マルチプロセッサに含まれる各プロセッサが適切な待ち合わせを行いつつ割り当てられたタスクを実行するようなコードを作成する。
【０１００】
具体的には、コード作成装置あるいはコンパイラは、データフローグラフに基づいてノードに対応するタスクを実行するコードを作成する際に、この確定プロセッサ間待ち合わせエッジ群を表す情報を記録媒体から読み出して参照し、以下に列挙する待ち合わせを含むコードを作成する。マルチプロセッサに含まれる各プロセッサは、作成されたコードにしたがって待ち合わせを行うことになる。
・エッジＮ１−＞Ｎ２にもとづいてプロセッサ１がノードＮ２の実行前にノードＮ１の実行完了を待ち合わせる
・エッジＮ１−＞Ｎ３にもとづいてプロセッサ２がノードＮ３の実行前にノードＮ１の実行完了を待ち合わせる
・エッジＮ３−＞Ｎ４にもとづいてプロセッサ０がノードＮ４の実行前にノードＮ３の実行完了を待ち合わせる
・エッジＮ５−＞Ｎ７にもとづいてプロセッサ０がノードＮ７の実行前にノードＮ５の実行完了を待ち合わせる
・エッジＮ６−＞Ｎ８にもとづいてプロセッサ０がノードＮ８の実行前にノードＮ６の実行完了を待ち合わせる
確定プロセッサ間待ち合わせエッジ群に関する情報の別の使用例は、マルチプロセッサに含まれる各プロセッサが、この情報を直接参照して待ち合わせを行う、というものである。具体的には、マルチプロセッサの各プロセッサがデータフローグラフに基づいてノードに対応するタスクを実行する際に、この確定プロセッサ間待ち合わせエッジ群を表す情報を記録媒体から読み出して参照し、前段落で列挙した待ち合わせを行う。
【０１０１】
＜第３除去可能エッジ含有パターンと第４除去可能エッジ含有パターンとを用いた具体的例＞
第３除去可能エッジ含有パターンと第４除去可能エッジ含有パターンを用いた具体的例について、図５、図６、図１３乃至図１６などを参照して説明する。
【０１０２】
まず、待ち合わせポイント決定処理の対象となるデータフローグラフを図１３に示す。図１３に示すデータフローグラフにおいては、８個のノードがあり、これらのノードが３個のプロセッサに割り当てられている。
【０１０３】
まず、図１３のデータフローグラフを対象として、番号付与部１０３は、トポロジカルソートして得られる順序番号を、各ノードに付与する。図１４は、番号付与部１０３がノード番号を割り当てた状態のデータフローグラフを示す。
【０１０４】
続いて候補群抽出部１０４は、図１４のデータフローグラフから、プロセッサ間待ち合わせエッジの候補群を抽出する。図１５は、候補群抽出部１０４によって抽出されたプロセッサ間待ち合わせエッジの候補群を表す図である。図１５では、異なるプロセッサに割り当てられたノードを結ぶエッジの全てがプロセッサ間待ち合わせエッジの候補群に含まれている。
【０１０５】
図１６は、図１５に示すプロセッサ間待ち合わせエッジの候補群に含まれているエッジのうち、除去部１０５が除去可能なエッジを破線で示し、除去不可能なエッジを太線で示す。図１６において、例えば、ノードＮ１、Ｎ３、Ｎ４、Ｎ５とこれらを接続する２つのエッジＮ１−＞Ｎ５、エッジＮ３−＞Ｎ４は、第４除去可能エッジ含有パターンに該当する。従って、第４除去可能エッジ含有パターンにおける除去可能エッジに該当するエッジＮ１−＞Ｎ５は除去可能である。同様に、ノードＮ５、Ｎ６、Ｎ７とこれらを接続する３つのエッジＮ５−＞Ｎ６、エッジＮ６−＞Ｎ７、エッジＮ５−＞Ｎ７は、第３除去可能エッジ含有パターンに該当する。従って、第３除去可能エッジ含有パターンにおける除去可能エッジに該当するエッジＮ５−＞Ｎ７は除去可能である。従って、除去部１０５は、エッジＮ１−＞Ｎ５と、エッジＮ５−＞Ｎ７を除去する。  除去部１０５による除去の結果、残ったエッジである確定プロセッサ間待ち合わせエッジ群は、エッジＮ１−＞Ｎ２、エッジＮ３−＞Ｎ４、エッジＮ５−＞Ｎ６、エッジＮ６−＞Ｎ７及びエッジＮ７−＞Ｎ８より構成される。
【０１０６】
この確定プロセッサ間待ち合わせエッジ群に関する情報を、出力部１０６は、記録媒体に記録する。既に説明した具体例＜第１除去可能エッジ含有パターと第２除去可能エッジ含有パターンとを用いた具体的例＞で述べたとおり、この確定プロセッサ間待ち合わせエッジ群に関する情報は、コード作成装置あるいはコンパイラによって使われたり、マルチプロセッサによって使われたりする。
【０１０７】
コード作成装置あるいはコンパイラは、たとえば、データフローグラフにもとづいてノードに対応するタスクを実行するコードを作成する際に、この確定プロセッサ間待ち合わせエッジ群を表す情報を記録媒体から読み出して参照し、以下に列挙する待ち合わせを含むコードを作成する。
・エッジＮ１−＞Ｎ２にもとづいてプロセッサ２がノードＮ２の実行前にノードＮ１の実行完了を待ち合わせる
・エッジＮ３−＞Ｎ４にもとづいてプロセッサ１がノードＮ４の実行前にノードＮ３の実行完了を待ち合わせる
・エッジＮ５−＞Ｎ６にもとづいてプロセッサ０がノードＮ６の実行前にノードＮ５の実行完了を待ち合わせる
・エッジＮ６−＞Ｎ７にもとづいてプロセッサ２がノードＮ７の実行前にノードＮ６の実行完了を待ち合わせる
・エッジＮ７−＞Ｎ８にもとづいてプロセッサ０がノードＮ８の実行前にノードＮ７の実行完了を待ち合わせる
マルチプロセッサに含まれる各プロセッサは、たとえば、データフローグラフに基づいてノードに対応するタスクを実行する際に、この確定プロセッサ間待ち合わせエッジ群を表す情報を記録媒体から読み出して参照し、前段落で列挙した待ち合わせを行う。
【０１０８】
以上説明した本実施形態によれば、データフローグラフで表現可能なプログラムに対して、データフローグラフで表現可能なプログラムを並列処理する際の「待ち合わせ」回数を一般的な技術に比べて少なくすることができるという効果を奏する。その理由は、所定の除去可能エッジ含有パターンを予め設定し、この除去可能エッジ含有パターン中の除去できるエッジに該当するエッジに係る不必要な待ち合わせを除去できるからである。
【０１０９】
並列処理において「待ち合わせ」を行うことは、並列処理のために支払う必要のある負荷であるが、できるだけ「待ち合わせ」の負荷を少なくすることが並列処理の性能向上につながる。本実施形態では上述したように並列処理における「待ち合わせ」回数を少なくすることができ、これを換言すると、並列処理の負荷を少なくすることができるとも言える。
【０１１０】
次に、プロセッサ間待ち合わせエッジ群生成装置の具体的な実装例について説明する。
【０１１１】
図１７にはプロセッサ間待ち合わせエッジ群生成装置を実装する際の概念図が表されている。図１７を参照すると、プロセッサ間待ち合わせエッジ群生成装置２００は計算ユニット２１０及び記憶ユニット２２０を含む。
【０１１２】
そして、記憶ユニット２２０からデータフローグラフ（処理前）を読み出し、並列処理のための選択後待ち合わせポイントを作成し、この作成した情報を記憶ユニット２２０に格納する。ここでデータフローグラフ（処理前）から並列処理のための選択後待ち合わせポイントを得る方法とは、実施形態として上述した方法である。また、並列処理のための選択後待ち合わせポイントとは、データフローグラフ（処理前）で表現可能なソフトウェアを並列処理する際に必要となる待ち合わせポイントに関する情報である。選択後待ち合わせポイントは、データフローグラフ（処理前）のどのエッジが待ち合わせポイントであるかを表すものである。
【０１１３】
計算ユニット２１０は、プロセッサ、ＦＰＧＡ（Field Programmable Gate Array）、半導体集積回路、などの計算能力を備えたユニットであり、上述した実施形態に記載の方法で必要となる計算を実行する。記憶ユニット２２０は、半導体メモリ、光学ディスク、あるいはハードディスク等の媒体に情報を記憶する機能を備えたユニットである。
【０１１４】
プロセッサ間待ち合わせエッジ群生成装置２００は、コンピュータおよび制御プログラムで実現されても良い。その場合には、上述した実施形態に記載の方法が制御プログラムとして表現され、当該制御プログラムをコンピュータの記憶ユニット２２０に格納しておき、コンピュータの計算ユニット２１０が制御プログラムをコンピュータの記憶ユニットから読みだして実行する。
【０１１５】
続いて、上述した実施形態及び上述した実施形態が生成した確定プロセッサ間待ち合わせエッジ群に関する情報の具体的な利用例について説明する。
【０１１６】
上述した確定プロセッサ間待ち合わせエッジ群に関する情報は、並列処理のための待ち合わせポイント情報として利用される。
【０１１７】
ここで、具体的な第１の利用例としては、入力されたソースコードから並列ソースコードを作成する装置により利用される例が挙げられる。たとえば、図９のデータフローグラフで表現可能な並列処理のマルチプロセッサ用実行コードを作成するために、コード作成装置あるいはコンパイラによって利用される。コード作成装置あるいはコンパイラは、この確定プロセッサ間待ち合わせエッジ群に関する情報を参照して、マルチプロセッサに含まれる各プロセッサが適切な待ち合わせを行いつつ割り当てられたタスクを実行するようなコードを作成することが可能となる。
【０１１８】
この第１の例を実現するためには、入力されたソースコードからデータフローグラフを抽出する処理や、データフローグラフの各ノードを複数のプロセッサに割り当てる処理が伴う。そして、これらの処理は任意の方法により実現することが可能である。
【０１１９】
例えば、背景技術の欄において説明した特許文献１や特許文献２に記載の技術と、上述した本実施形態とを組み合わせることにより実現することができる。また、特許文献１や特許文献２に記載の技術に代えて、又はこれらの技術共に、任意の他の技術を更に組み合わせるようにしても良い。
そして、本実施形態を利用することで不要な待ち合わせポイントを除去したコードを作成することが可能となる。
【０１２０】
また、この作成されたコードはデータフローグラフで表現可能な対象プログラムである（データフローグラフ処理前のソースコード）を並列処理する際に有益な情報である。
【０１２１】
そこで、具体的な第２の利用例としては、データフローグラフ処理前のソースコードを並列処理する装置が、上述した実施形態により生成されたコードに基づいて並列処理を行うという例が挙げられる。
【０１２２】
図１８を参照すると、本利用例である並列処理装置３００は、データフローグラフ生成部３０１、プロセッサ間待ち合わせエッジ群生成装置３０２、記録部３０３及び並列処理部３０４を含む。
【０１２３】
データフローグラフ生成部３０１は、ソースコードを入力され、このソースコードに対してデータフローグラフ処理を行うことによりデータフローグラフを生成する。生成されたデータフローグラフはプロセッサ間待ち合わせエッジ群生成装置３０２及び並列処理部３０４に対してそれぞれ出力される。
【０１２４】
プロセッサ間待ち合わせエッジ群生成装置３０２は、本発明の実施形態であるプロセッサ間待ち合わせエッジ群生成装置１００と同様の構成及び機能を含むので、その詳細な説明は省略する。プロセッサ間待ち合わせエッジ群生成装置３０２はデータフローグラフ生成部３０１から出力されたデータフローグラフに対して上述した実施形態同様の処理を行い、処理結果として確定プロセッサ間待ち合わせエッジ群を記録部３０３に対して出力する。
【０１２５】
記録部３０３は、プロセッサ間待ち合わせエッジ群生成装置３０２から出力された確定プロセッサ間待ち合わせエッジ群を記録する。
【０１２６】
並列処理部３０４は、記録部３０３から出力された確定プロセッサ間待ち合わせエッジ群に基づいて、マルチプロセッサに含まれる各プロセッサが適切な待ち合わせを行いつつ割り当てられたタスクを実行するようなコードを作成する。他方で、並列処理部３０４は、データフローグラフ生成部３０１から出力されたデータフローグラフを受け付け、このデータフローグラフをノード単位で演算処理し、処理結果を出力する。そして、この演算処理に際しては上記作成したコードに基づいた待ち合わせを行う。これにより、一般的な技術に比べ、より効率的に演算処理を実行することができる。なお、並列処理部３０４は複数のプロセッサにより実現され、これらのプロセッサがデータフローグラフを並列処理する。また、図１８においては機能ブロックとして分離されてはいるが、並列処理部３０４を実現する複数のプロセッサの一部又は全部が事前に演算処理を行うことによりデータフローグラフ生成部３０１をも実現するようにしても良い。また、並列処理部３０４等を実現する各プロセッサの内部又は外部に設けられた主記憶装置や、各プロセッサが読み書き可能な補助記憶装置が記録部３０３を実現する。
【０１２７】
並列処理部３０４による、処理結果の出力先は、例えばこの出力結果に応じて動作する何らかのハードウェアの制御部である。また、出力は、所定の記録媒体に記録することにより行われても良いし、外部ネットワークに送出することにより行われても良いし、ディスプレイ等の表示装置に表示することにより行われても良い。
【０１２８】
続いて図１９のフローチャートを参照して第２の利用例における並列処理部３０４の基本的動作について説明する。
【０１２９】
並列処理部３０４が確定プロセッサ間待ち合わせエッジ群に基づいて、マルチプロセッサに含まれる各プロセッサが適切な待ち合わせを行いつつ割り当てられたタスクを実行するようなコードを作成する。そして、この生成したコードを参照しながらデータフローグラフをノード単位で演算処理する（ステップＳ４０１）。
【０１３０】
そして、ステップＳ４０１における演算処理結果は並列処理部３０４により出力される（ステップＳ４０３）。
【０１３１】
以上により本利用例の動作は終了する。
【０１３２】
以上説明した本利用例では、選択後待ち合わせポイントを生成すると共に、この選択後待ち合わせポイントを同装置内で利用できることから並列処理装置全体としての処理の効率化を図ることができる。
【０１３３】
また、本利用例は、実際に並列処理を実行するプロセッサの種別を問うものではないため、本利用例は組み込み向けプロセッサ、汎用コンピュータ用プロセッサ、など、さまざまなプロセッサによる並列処理に適用可能である。
【０１３４】
次に図２０を参照してプロセッサ間待ち合わせエッジ群生成装置を実現するための具体的なハードウェア構成の一例について説明する。
【０１３５】
図２０を参照すると並列コンピュータ５００は、第１の主記憶装置５０１、第２の主記憶装置５０２、第Ｎの主記憶装置５０３、第１のプロセッサ５０４、第２のプロセッサ５０５、第Ｎのプロセッサ５０６、共有主記憶装置５０７、補助記憶装置５０８、入力装置５０９、通信インターフェース５１０、出力装置５１１及びデバイス接続インターフェース５１２を含む。
【０１３６】
第１のプロセッサ５０４、第２のプロセッサ５０５及び第Ｎのプロセッサ５０６は、演算処理を行うプロセッサであり、その種別は限定されない。また、その個数も限定されない。また、図２０では各プロセッサは物理的に分離しているが、複数のプロセッサコアが単一のパッケージ内に封入されたマルチコアにより第１のプロセッサ５０４、第２のプロセッサ５０５及び第Ｎのプロセッサ５０６を実現しても良い。
【０１３７】
第１の主記憶装置５０１、第２の主記憶装置５０２及び第Ｎの主記憶装置５０３は、第１のプロセッサ５０４、第２のプロセッサ５０５及び第Ｎのプロセッサ５０６がそれぞれ利用するローカルな主記憶装置であり、各プロセッサ専用のキャッシュメモリとして機能する。
【０１３８】
一方で、共有主記憶装置５０７は、第１のプロセッサ５０４、第２のプロセッサ５０５及び第Ｎのプロセッサ５０６の全てがアクセス可能な共有メモリである。各主記憶装置は、ＤＲＡＭ（Dynamic Random Access Memory）等により実現される。
【０１３９】
補助記憶装置５０８は、ハードディスクドライブやFlash  SSD（Solid State Drive）等により実現され、一般的には、主記憶装置に比べて低速ながら大容量な記憶装置である。補助記憶装置５０８には本実施形態特有のソフトウェアが格納されている。そして、第１のプロセッサ５０４、第２のプロセッサ５０５及び第Ｎのプロセッサ５０６は、この本実施形態特有のデータフローグラフを表す情報及び確定プロセッサ間待ち合わせエッジ群を表す情報などを読み込み、これらに基づいて演算処理を行い、各ハードウェアを制御することによってプロセッサ間待ち合わせエッジ群生成装置が含む各部が実現される。また、データフローグラフのもととなるソースプログラムが補助記憶装置５０８に格納されていても良い。
【０１４０】
入力装置５０９はユーザの操作を受け付ける機器である。また、出力装置５１１はユーザに対して情報を表示する機器である。
【０１４１】
通信インターフェース５１０は他の装置との通信を行うためのインターフェースである。データフローグラフのもととなるソースプログラムや、本実施形態の処理結果が、この通信インターフェース５１０を介して他の装置と送受信されるようにしても良い。
【０１４２】
デバイス接続インターフェース５１２は、何らかのデバイスを接続するためのインターフェースであり、例えば、ＵＳＢ（Universal Serial Bus）規格に準拠したインターフェースである。データフローグラフのもととなるソースプログラムがデバイス接続インターフェース５１２に接続した外部メモリに格納されていても良い。
【０１４３】
なお、上述した並列コンピュータ５００の構成は一例に過ぎない。例えば上記構成は一利用例である並列処理装置３００のデータフローグラフ生成部３０１、記録部３０３及び並列処理部３０４をも実現可能とした構成である。そのために上記構成には複数のプロセッサが含まれている。もっとも、本発明の実施形態であるプロセッサ間待ち合わせエッジ群生成装置１００を実現するのであれば複数のプロセッサは必須ではなく、単一のプロセッサが存在していればよい。なお、並列処理部３０４を実現する場合には、或るプロセッサがプロセッサ間待ち合わせエッジ群生成装置３０２等を実現するための処理を行い、他のプロセッサが協働して並列処理部３０４を実現するための処理を行っても良い。
【０１４４】
また、上記構成は各プロセッサにローカルの主記憶装置が存在すると共に、共有主記憶装置も存在するという、分散共有メモリ方式により実現されている。もっとも、これは単なる一例に過ぎず、ローカルの主記憶装置のみが存在していても良いし、共有主記憶装置のみが存在していても良い。
【０１４５】
また、他の構成要素を含んでいても良く、例えば光学ディスクの読み取り装置を含んでいても良い。
【０１４６】
更に、並列コンピュータ５００は物理的に単一の装置により実現しても良いが複数の装置が協働することにより実現しても良い。例えば、補助記憶装置が外部に存在しても良い。また、ユーザが直接操作する端末と、この端末とネットワークを介して接続されたサーバ装置とが協働して並列コンピュータ５００が実現されても良い。
【０１４７】
また、上述した実施形態は、本発明の好適な実施形態ではあるが、上記実施形態のみに本発明の範囲を限定するものではなく、本発明の要旨を逸脱しない範囲において種々の変更を施した形態での実施が可能である。
【０１４８】
なお、上記のプロセッサ間待ち合わせエッジ群生成装置は、ハードウェア、ソフトウェア又はこれらの組み合わせにより実現することができる。また、上記のプロセッサ間待ち合わせエッジ群生成装置により行なわれるデータフローグラフ処理方法も、ハードウェア、ソフトウェア又はこれらの組み合わせにより実現することができる。ここで、ソフトウェアによって実現されるとは、コンピュータがプログラムを読み込んで実行することにより実現されることを意味する。
【０１４９】
プロセッサ間待ち合わせエッジ群生成装置がコンピュータ及びプログラムで実現される場合には、この制御プログラムは処理対象のプログラムを並列化するようにコンピュータを制御するものであってよく、この制御プログラムの構成要素の１つとして本発明の実施形態に記載の方法に相当する要素を含んでいてもよい。
【０１５０】
プログラムは、様々なタイプの非一時的なコンピュータ可読媒体(non-transitory computer readable medium)を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体(tangible storage medium)を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えば、フレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば、光磁気ディスク）、ＣＤ−ＲＯＭ(Read Only Memory)、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ(Programmable ROM)、ＥＰＲＯＭ(Erasable PROM)、フラッシュＲＯＭ、ＲＡＭ(random access memory)）を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体(transitory computer readable medium)によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【０１５１】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１５２】
（付記１）  プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成装置であって、
前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、
前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、
を備えることを特徴とするエッジ群生成装置。
【０１５３】
（付記２）  付記１に記載のエッジ群生成装置であって、
前記除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第２ノードよりも先になおかつ第１ノードよりも後に実行される第３ノードと、第１ノードから第２ノードへの第１エッジと、をもつ、基本除去可能エッジ含有パターンを少なくとも含み、
前記基本除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【０１５４】
（付記３）  付記１又は２に記載のエッジ群生成装置であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた１つの第１ノードと、第２プロセッサに割り当てられた複数の第２ノードとを含むと共に、何れの第２ノードも第１ノードを出発側ノードとするエッジをもつような、第１除去可能エッジ含有パターンを少なくとも含み、
第１除去可能エッジ含有パターン中の、最小の順序番号をもつ第２ノードへのエッジを除いて、第１ノードから複数の第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【０１５５】
（付記４）  付記１乃至３の何れか１に記載のエッジ群生成装置であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた複数の第１ノードと、第２プロセッサに割り当てられた１つの第２ノードとを含むと共に、何れの第１ノードも第２ノードを到着側ノードとするエッジをもつような、第２除去可能エッジ含有パターンを少なくとも含み、
第２除去可能エッジ含有パターン中の、最大の順序番号をもつ第１ノードからのエッジを除く、複数の第１ノードから第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【０１５６】
（付記５）  付記１乃至４の何れか１に記載のエッジ群生成装置であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第３プロセッサに割り当てられた第３ノードとを含むと共に、第１ノードから第２ノードへの第１エッジあるいは部分データフローグラフと、第２ノードから第３ノードへの第２エッジと、第１ノードから第３ノードへの第３エッジとをもち、前記部分データフローグラフは第１ノードを出発側ノードとして第２ノードを到着側ノードとするノードとエッジを含むデータフローグラフであるような、第３除去可能エッジ含有パターンを少なくとも含み、
第３除去可能エッジ含有パターン中の、第３エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【０１５７】
（付記６）  付記１乃至５の何れか１に記載のエッジ群生成装置であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードおよび第２ノードと、第２プロセッサに割り当てられた第３ノードおよび第４ノードとを含むと共に、第１ノードから第４ノードへの第１エッジと、第２ノードから第３ノードへの第２エッジをもち、さらに、トポロジカルソートにもとづく順序番号に関して、第１ノードの順序番号は第２ノードの順序番号よりも小さく、第３ノードの順序番号は第４ノードの順序番号よりも小さいような、第４除去可能エッジ含有パターンを少なくとも含み、
第４除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成装置。
【０１５８】
（付記７）  プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を記録したコンピュータ読取り可能な記録媒体であって、
前記プロセッサ間待ち合わせエッジ群が、
前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、
前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、
により生成されたプロセッサ間待ち合わせエッジ群であることを特徴とするコンピュータ読取り可能な記録媒体。
【０１５９】
（付記８）  付記７に記載の記録媒体であって、
前記除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第２ノードよりも先になおかつ第１ノードよりも後に実行される第３ノードと、第１ノードから第２ノードへの第１エッジと、をもつ、基本除去可能エッジ含有パターンを少なくとも含み、
前記基本除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とする記録媒体。
【０１６０】
（付記９）  付記７又は８に記載の記録媒体であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた１つの第１ノードと、第２プロセッサに割り当てられた複数の第２ノードとを含むと共に、何れの第２ノードも第１ノードを出発側ノードとするエッジをもつような、第１除去可能エッジ含有パターンを少なくとも含み、
第１除去可能エッジ含有パターン中の、最小の順序番号をもつ第２ノードへのエッジを除いて、第１ノードから複数の第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とする記録媒体。
【０１６１】
（付記１０）  付記７乃至９の何れか１に記載の記録媒体であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた複数の第１ノードと、第２プロセッサに割り当てられた１つの第２ノードとを含むと共に、何れの第１ノードも第２ノードを到着側ノードとするエッジをもつような、第２除去可能エッジ含有パターンを少なくとも含み、
第２除去可能エッジ含有パターン中の、最大の順序番号をもつ第１ノードからのエッジを除く、複数の第１ノードから第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とする記録媒体。
【０１６２】
（付記１１）  付記７乃至１０の何れか１に記載の記録媒体であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第３プロセッサに割り当てられた第３ノードとを含むと共に、第１ノードから第２ノードへの第１エッジあるいは部分データフローグラフと、第２ノードから第３ノードへの第２エッジと、第１ノードから第３ノードへの第３エッジとをもち、前記部分データフローグラフは第１ノードを出発側ノードとして第２ノードを到着側ノードとするノードとエッジを含むデータフローグラフであるような、第３除去可能エッジ含有パターンを少なくとも含み、
第３除去可能エッジ含有パターン中の、第３エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とする記録媒体。
【０１６３】
（付記１２）  付記７乃至１１の何れか１に記載の記録媒体であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードおよび第２ノードと、第２プロセッサに割り当てられた第３ノードおよび第４ノードとを含むと共に、第１ノードから第４ノードへの第１エッジと、第２ノードから第３ノードへの第２エッジをもち、さらに、トポロジカルソートにもとづく順序番号に関して、第１ノードの順序番号は第２ノードの順序番号よりも小さく、第３ノードの順序番号は第４ノードの順序番号よりも小さいような、第４除去可能エッジ含有パターンを少なくとも含み、
第４除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とする記録媒体。
【０１６４】
（付記１３）  プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成方法であって、
前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出ステップと、
前記候補群抽出ステップにおいて抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去ステップと、
を有することを特徴とするエッジ群生成方法。
【０１６５】
（付記１４）  付記１３に記載のエッジ群生成方法であって、
前記除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第２ノードよりも先になおかつ第１ノードよりも後に実行される第３ノードと、第１ノードから第２ノードへの第１エッジと、をもつ、基本除去可能エッジ含有パターンを少なくとも含み、
前記基本除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成方法。
【０１６６】
（付記１５）  付記１３又は１４に記載のエッジ群生成方法であって、
前記除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第２ノードよりも先になおかつ第１ノードよりも後に実行される第３ノードと、第１ノードから第２ノードへの第１エッジと、をもつ、基本除去可能エッジ含有パターンを少なくとも含み、
前記基本除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成方法。
【０１６７】
（付記１６）  付記１３乃至１５の何れか１に記載のエッジ群生成方法であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた複数の第１ノードと、第２プロセッサに割り当てられた１つの第２ノードとを含むと共に、何れの第１ノードも第２ノードを到着側ノードとするエッジをもつような、第２除去可能エッジ含有パターンを少なくとも含み、
第２除去可能エッジ含有パターン中の、最大の順序番号をもつ第１ノードからのエッジを除く、複数の第１ノードから第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成方法。
【０１６８】
（付記１７）  付記１３乃至１６の何れか１に記載のエッジ群生成方法であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第３プロセッサに割り当てられた第３ノードとを含むと共に、第１ノードから第２ノードへの第１エッジあるいは部分データフローグラフと、第２ノードから第３ノードへの第２エッジと、第１ノードから第３ノードへの第３エッジとをもち、前記部分データフローグラフは第１ノードを出発側ノードとして第２ノードを到着側ノードとするノードとエッジを含むデータフローグラフであるような、第３除去可能エッジ含有パターンを少なくとも含み、
第３除去可能エッジ含有パターン中の、第３エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成方法。
【０１６９】
（付記１８）  付記１３乃至１７の何れか１に記載のエッジ群生成方法であって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードおよび第２ノードと、第２プロセッサに割り当てられた第３ノードおよび第４ノードとを含むと共に、第１ノードから第４ノードへの第１エッジと、第２ノードから第３ノードへの第２エッジをもち、さらに、トポロジカルソートにもとづく順序番号に関して、第１ノードの順序番号は第２ノードの順序番号よりも小さく、第３ノードの順序番号は第４ノードの順序番号よりも小さいような、第４除去可能エッジ含有パターンを少なくとも含み、
第４除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成方法。
【０１７０】
（付記１９）  プログラムに含まれる複数のタスクをマルチプロセッサが並列的に実行する際に、プロセッサ間で行うべきタスクの待ち合わせを示すプロセッサ間待ち合わせエッジ群を生成するプロセッサ間待ち合わせエッジ群生成装置としてコンピュータを機能させるための待ち合わせエッジ群生成プログラムであって、
前記コンピュータを、
前記プログラムに対応し、トポロジカルソートによって順序番号が付与されたデータフローグラフであって、前記複数のタスクのそれぞれをノードとして表し、ノード間のデータ依存関係をそのノード間を結ぶエッジにより表したデータフローグラフを参照して、相互に異なったプロセッサに割り当てられたノードを結ぶエッジをプロセッサ間待ち合わせエッジの候補として抽出し、それらの候補の集合をプロセッサ間待ち合わせエッジの候補群として抽出する候補群抽出手段と、
前記候補群抽出手段により抽出された前記プロセッサ間待ち合わせエッジの候補群の全部又は一部であって、１以上の除去可能エッジ含有パターンのうちの何れかと一致する一致候補群を探し、前記一致候補群に含まれる２以上のエッジのうち、一致に係る前記除去可能エッジ含有パターンに含まれる除去可能な１以上のエッジにそれぞれ対応する１以上のエッジを除去し、除去後に残った候補群を前記プロセッサ間待ち合わせエッジ群とする除去手段と、
を備えるエッジ群生成装置として機能させることを特徴とする待ち合わせエッジ群生成プログラム。
【０１７１】
（付記２０）  付記１９に記載のエッジ群生成プログラムであって、
前記除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第２ノードよりも先になおかつ第１ノードよりも後に実行される第３ノードと、第１ノードから第２ノードへの第１エッジと、をもつ、基本除去可能エッジ含有パターンを少なくとも含み、
前記基本除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成プログラム。
【０１７２】
（付記２１）  付記１９又は２０に記載のエッジ群生成プログラムであって、
前記除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第２ノードよりも先になおかつ第１ノードよりも後に実行される第３ノードと、第１ノードから第２ノードへの第１エッジと、をもつ、基本除去可能エッジ含有パターンを少なくとも含み、
前記基本除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成プログラム。
【０１７３】
（付記２２）  付記１９乃至２１の何れか１に記載のエッジ群生成プログラムであって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた複数の第１ノードと、第２プロセッサに割り当てられた１つの第２ノードとを含むと共に、何れの第１ノードも第２ノードを到着側ノードとするエッジをもつような、第２除去可能エッジ含有パターンを少なくとも含み、
第２除去可能エッジ含有パターン中の、最大の順序番号をもつ第１ノードからのエッジを除く、複数の第１ノードから第２ノードへのエッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成プログラム。
【０１７４】
（付記２３）  付記１９乃至２２の何れか１に記載のエッジ群生成プログラムであって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードと、第２プロセッサに割り当てられた第２ノードと、第３プロセッサに割り当てられた第３ノードとを含むと共に、第１ノードから第２ノードへの第１エッジあるいは部分データフローグラフと、第２ノードから第３ノードへの第２エッジと、第１ノードから第３ノードへの第３エッジとをもち、前記部分データフローグラフは第１ノードを出発側ノードとして第２ノードを到着側ノードとするノードとエッジを含むデータフローグラフであるような、第３除去可能エッジ含有パターンを少なくとも含み、
第３除去可能エッジ含有パターン中の、第３エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成プログラム。
【０１７５】
（付記２４）  付記１９乃至２３の何れか１に記載のエッジ群生成プログラムであって、
前記１以上の除去可能エッジ含有パターンは、第１プロセッサに割り当てられた第１ノードおよび第２ノードと、第２プロセッサに割り当てられた第３ノードおよび第４ノードとを含むと共に、第１ノードから第４ノードへの第１エッジと、第２ノードから第３ノードへの第２エッジをもち、さらに、トポロジカルソートにもとづく順序番号に関して、第１ノードの順序番号は第２ノードの順序番号よりも小さく、第３ノードの順序番号は第４ノードの順序番号よりも小さいような、第４除去可能エッジ含有パターンを少なくとも含み、
第４除去可能エッジ含有パターン中の、第１エッジを”プロセッサ間待ち合わせエッジの候補群”から除去可能なエッジとする、
ことを特徴とするエッジ群生成プログラム。
【産業上の利用可能性】
【０１７６】
本発明は、データフローグラフで表現可能なプログラムであればどのようなプログラムも対象とすることが可能であるため、並列処理する前段階としての待ち合わせポイントを選択するものであれば用途を問うことなく適用することが可能である。
【符号の説明】
【０１７７】
１００、２００、３０２  プロセッサ間待ち合わせエッジ群生成装置
１０１  入力受付部
１０２  ソート部
１０３  番号付与部
１０４  候補群抽出部
１０５  除去部
１０５−１  第１の除去部
１０５−２  第２の除去部
１０５−３  第３の除去部
１０５−４  第４の除去部
１０６  出力部
２１０  計算ユニット
２２０  記憶ユニット
３００  並列処理装置
３０１  データフローグラフ生成部
３０３  記録部
３０４  並列処理部
５００  並列コンピュータ
５０１  第１の主記憶装置
５０２  第２の主記憶装置
５０３  第Ｎの主記憶装置
５０４  第１のプロセッサ
５０５  第２のプロセッサ
５０６  第Ｎのプロセッサ
５０７  共有主記憶装置
５０８  補助記憶装置
５０９  入力装置
５１０  通信インターフェース
５１１  出力装置
５１２  デバイス接続インターフェース
【図１】
2014106643.tif 000003
【図２】
2014106643.tif 000004
【図３】
2014106643.tif 000005
【図４】
2014106643.tif 000006
【図５】
2014106643.tif 000007
【図６】
2014106643.tif 000008
【図７】
2014106643.tif 000009
【図８】
2014106643.tif 000010
【図９】
2014106643.tif 000011
【図１０】
2014106643.tif 000012
【図１１】
2014106643.tif 000013
【図１２】
2014106643.tif 000014
【図１３】
2014106643.tif 000015
【図１４】
2014106643.tif 000016
【図１５】
2014106643.tif 000017
【図１６】
2014106643.tif 000018
【図１７】
2014106643.tif 000019
【図１８】
2014106643.tif 000020
【図１９】
2014106643.tif 000021
【図２０】
2014106643.tif 000022