(57)【要約】  依存関係のある手続（プログラムユニット）を実行する場合に、順番待ちによる無駄な待ち時間を削減できるマルチプロセッシング方法及びマルチプロセッサシステムが記載されており、逐次実行プログラムにおける複数のプログラムユニットの実行順及び複数のプログラムユニットの依存関係を登録し、登録した依存関係に基づいて複数のプログラムユニットの実行状態を管理し、実行可能なプログラムユニットを判定して、順次サーバプロセッサに割当てて実行する。
2007108133.tif 000002
【特許請求の範囲】
【請求項１】
クライアントプロセッサと、複数のサーバプロセッサと、前記クライアントプロセッサと前記複数のサーバプロセッサ間のデータ通信が可能なように接続する通信経路と、を備えるマルチプロセッサシステムにおいて、前記クライアントプロセッサが、複数のプログラムユニットを順に記憶した逐次実行プログラムの前記プログラムユニットを前記サーバプロセッサに割当てることにより、実行するマルチプロセッシング方法であって、
前記逐次実行プログラムにおける、前記複数のプログラムユニットの実行順及び前記複数のプログラムユニットの依存関係を登録し、
登録した前記依存関係に基づいて前記複数のプログラムユニットの実行状態を管理し、実行可能なプログラムユニットを判定して、順次サーバプロセッサに割当てて実行することを特徴とするマルチプロセッシング方法。
【請求項２】
前記クライアントプロセッサは、前記サーバプロセッサに前記プログラムユニットを割当てる処理を行う手続要求プログラムを実行し、
前記サーバプロセッサは、前記プログラムユニットを実行するために呼び出す処理を行う手続呼出プログラムを実行する請求項１に記載のマルチプロセッシング方法。
【請求項３】
前記手続要求プログラムは、前記複数のプログラムユニットの実行順及び前記依存関係を登録する実行キューを生成し、
前記手続要求プログラムは、前記実行キューに基づいて前記複数のプログラムユニットの実行状態を管理し、実行可能なプログラムユニットを判定して、順次サーバプロセッサを呼び出し、
前記手続呼出プログラムは、割当てられたプログラムユニットの実行完了を前記手続要求プログラムに通知する請求項２に記載のマルチプロセッシング方法。
【請求項４】
前記実行キューは、各プログラムユニットの実行を割当てるサーバプロセッサに関するサーバ割当情報を有し、
前記手続要求プログラムは、前記実行キューに従って、実行可能なプログラムユニットを前記サーバプロセッサに割当てる請求項３に記載のマルチプロセッシング方法。
【請求項５】
前記実行キューは、各サーバプロセッサに対応して生成される請求項４に記載のマルチプロセッシング方法。
【請求項６】
前記手続要求プログラムは、前記複数のサーバクライアントの空き状態を管理し、実行可能なプログラムユニットを空き状態のサーバクライアントに割当てる請求項３に記載のマルチプロセッシング方法。
【請求項７】
前記手続呼出プログラムは、当該クライアントプロセッサに割当てられたプログラムユニットの実行順及び前記依存関係情報を含む実行キューを生成し、前記実行キューに基づいて前記プログラムユニットの実行状態を管理し、実行可能なプログラムユニットを判定して、順次プログラムユニットを実行する請求項２に記載のマルチプロセッシング方法。
【請求項８】
前記手続呼出プログラムは、前記プログラムユニットの実行完了を他のクライアントプロセッサに通知する請求項７に記載のマルチプロセッシング方法。
【請求項９】
前記手続呼出プログラムは、前記プログラムユニットの実行完了を、当該プログラムユニットに依存関係のあるプログラムユニットを実行する他のクライアントプロセッサに通知する請求項７に記載のマルチプロセッシング方法。
【請求項１０】
クライアントプロセッサと、複数のサーバプロセッサと、前記クライアントプロセッサと前記複数のサーバプロセッサ間のデータ通信が可能なように接続する通信経路と、を備え、複数の手続プログラムユニットを順に記憶した逐次実行プログラムを、前記クライアントプロセッサが、前記サーバプロセッサを非同期に呼び出す呼出手続を行なって前記プログラムユニットをサーバプロセッサに割当てることにより、実行するマルチプロセッサシステムであって、
前記逐次実行プログラムから、前記複数のプログラムユニットの実行順及び前記複数のプログラムユニットの依存関係を登録する実行キューを備え、
前記実行キューに登録された前記依存関係に基づいて前記複数のプログラムユニットの実行状態を管理し、実行可能なプログラムユニットを判定して、順次サーバプロセッサに割当てて実行することを特徴とするマルチプロセッサシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチプロセッシング方法及びマルチプロセッサシステムに関し、特にクライアントプロセッサが、逐次実行プログラムに順に記憶された複数のプログラムユニットを、サーバプロセッサに割当てることにより、実行するマルチプロセッシング方法及びマルチプロセッサシステムに関する。
【背景技術】
【０００２】
複数のプロセッサを通信経路で相互に接続し、処理を分担して実行するマルチプロセッサシステムが知られている。マルチプロセッサシステムには、各プロセッサが対等であるシステムと、プロセッサの１つがクライアントプロセッサ（マシン）で、他のプロセッサがサーバプロセッサ（マシン）で、クライアントプロセッサが各サーバプロセッサに処理を割当て、その結果をまとめる処理を行うクライアント・サーバ方式のシステムとがある。本発明は、クライアント・サーバ方式のマルチプロセッサシステムに関する。【０００３】
マルチプロセッサシステムにおけるプロセッサ間の通信方式として各種の方式が提案されているが、代表的なものに共有メモリ方式がある。図１は、共有メモリ方式のマルチプロセッサシステムの概略構成を示す図である。図１に示すように、このシステムは、共有バス２と、供給バス２に接続される複数のプロセッサ１−０、１−１、１−２、…、１−Ｎ及び共有メモリ３とを有する。データを送信する時には、各プロセッサは、送信するデータを共有メモリ３に書き込み、書き込み位置などの情報を送信先のプロセッサに通知する。通知を受けたプロセッサは共有メモリ３にアクセスして書き込まれたデータを得る。本発明は、図１に示したような共有メモリを有する方式に限定されず、プロセッサ間で通信を行えるシステムであればどのようなマルチプロセッサシステムにも適用可能である。【０００４】
また、マルチプロセッサシステムで実行するプログラムの形式も各種あるが、本発明は、実行するプログラムユニットを順に記憶した逐次実行プログラムを処理するマルチプロセッサシステムを対象とする。【０００５】
クライアント・サーバ方式のマルチプロセッサシステムでは、クライアントプロセッサからサーバプロセッサに対して手続呼出の形式で処理を依頼する。この手法を遠隔手続呼出と称する。【０００６】
遠隔手続呼出では、クライアントプロセッサは、サーバプロセッサに処理を依頼した後、サーバプロセッサでの処理が終了し、それが通知されるまで待つ必要があるが、クライアントプロセッサがサーバプロセッサでの処理の終了を待たずに他の処理を継続できる方法として非同期の遠隔手続呼出がある。【０００７】
マルチプロセッサシステムでは、この非同期の遠隔手続呼出を利用して、クライアントプロセッサから複数のサーバプロセッサに対して非同期の遠隔手続呼出を行うことにより並列処理を行う。図２は、非同期の遠隔手続呼出を使った並列処理を説明する図である。ここで、クライアントプロセッサは、”ｓｔａｒｔ”で手続（プログラムユニット）を実行する側のサーバプロセッサに対して指定された手続の起動を指示し、”ｗａｉｔ”で指定した手続の完了を待つ。図２では、サーバプロセッサ１−１に手続（プログラムユニット）Ａを、サーバプロセッサ１−２に手続（プログラムユニット）Ｂを、サーバプロセッサ１−３に手続（プログラムユニット）Ｃを、非同期の遠隔手続呼出を利用して割当てて実行させ、この間に手続要求側のクライアントプロセッサ１−０は、手続（プログラムユニット）Ｄを実行する。これにより、４つの処理を並列に行うことができる。【０００８】
非同期の遠隔手続呼出を利用して並列処理を行った場合に問題になるのが、順番待ちの問題である。図３はこの問題を説明する図である。図３では、サーバプロセッサ１−１で手続ＡとＣを、サーバプロセッサ１−２で手続ＢとＤを実行する。この際、手続呼出側のクライアントプロセッサ１−０では、手続Ａが先に完了すると想定して手続ＡとＢを起動した後、先に手続Ａの完了を待って手続Ｃを起動し、その後手続Ｂの完了を待って手続Ｄを起動する。しかし、実際に実行したところ、手続Ｂが先に完了した場合、手続Ｂが完了しても手続Ａが完了するまで手続Ｄを起動できず、この間サーバプロセッサ１−２に無駄な待ち時間が生じる。【０００９】
上記のような問題を解決するために、図４に示すようなキューイングによる解決法が考えられている。図４に示した構成によれば、手続要求側のクライアントプロセッサ１−０は、逐次実行プログラムから実行するプログラムユニットＡ、Ｂ、Ｃ、Ｄを順次実行リスト５に読み出す。クライアントプロセッサ１−０は、実行リスト５に読み出された手続（プログラムユニット）をサーバプロセッサに割当てる処理を行う手続要求プログラム６を有する。手続実行側のサーバプロセッサ１−１、１−２は、手続（プログラムユニット）を実行するために呼び出す処理を行う手続呼出プログラム７−１、７−２を有する。手続実行側のサーバプロセッサ１−１、１−２は、手続要求側のクライアントプロセッサ１−０から指定された手続を実行するための手続呼出プログラム７−１、７−２内に実行キュー８−１、８−２を有するため、ここで手続呼出の要求をキューイングすることで、手続要求側のクライアントプロセッサ１−０は先行の手続の完了を待たずに次の手続の呼出を要求できるようになる。これにより、順番待ちの問題が解消され、無駄な待ち時間を削減できる。【００１０】
特許文献１：特開平５−２９０００３号公報
非特許文献１："Communication in the Mercury System" IEEE TH0212-1/88/0000/0178$01.00
非特許文献２："Asynchronous Remote Operation Execution in Distributed Systems" IEEE CH2878-7/90/0000/0253$01.00
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、図４に示すように単純にキューイングしただけでは、図５に示したような手続間で依存があるプログラムユニットを異なるプロセッサに割当てた場合、手続の完了を待つ必要があり、順番待ちの問題により無駄な待ち時間が発生する。図６は、この問題を説明する図であり、図５に示したプログラムユニットを実行する場合を示す。【００１２】
図６では、図５に示したプログラムユニットを非同期の手続呼出を利用して並列化している。ここで、手続Ａ、Ｂ、Ｃの間には依存関係がないため、３つのサーバプロセッサ１−１〜１−３で並列に実行することが可能である。手続Ｄは手続Ａのみに依存関係があるため、サーバプロセッサ１−１にキューイングすればよい。手続Ｅは手続ＡとＢに依存関係があるため、手続Ｂが完了した後さらに手続Ａの完了を待ってからサーバプロセッサ１−２にキューイングする必要がある。同様に、手続Ｆは手続Ｂの完了を待ってからサーバプロセッサ１−３にキューイングする。ここで、手続ＡとＢの完了待ちの順番が問題になる。図６では、手続Ａが手続Ｂよりも先に完了すると仮定して先に手続Ａの完了を待っているが、実際には手続Ｂが先に完了してしまったため、手続Ｆの実行時に無駄な待ち時間が発生する。【００１３】
本発明は、上記のような依存関係のある手続（プログラムユニット）を実行する場合に、順番待ちによる無駄な待ち時間を削減できるマルチプロセッシング方法及びマルチプロセッサシステムの実現を目的とする。
【課題を解決するための手段】
【００１４】
本発明によれば、逐次実行プログラムにおける複数のプログラムユニットの実行順及び複数のプログラムユニットの依存関係を登録し、登録した依存関係に基づいて複数のプログラムユニットの実行状態を管理し、実行可能なプログラムユニットを判定して、順次サーバプロセッサに割当てて実行する。【００１５】
具体的には、手続（プログラムユニット）の呼出をキューイングしておく実行キューを拡張して、実行キューが手続とその手続に対する依存関係を保持するようにし、保持している依存関係を参照して実行可能な手続を判定して実行する。【００１６】
実行キューは、クライアントプロセッサの手続要求プログラム内に生成することも、サーバプロセッサの手続呼出プログラム内に生成することもできる。【００１７】
クライアントプロセッサの手続要求プログラムが実行キューを有する場合には、サーバプロセッサの手続呼出プログラムは、割当てられた手続の完了を手続要求プログラムに通知する。【００１８】
サーバプロセッサの手続呼出プログラムが実行キューを有する場合には、手続呼出プログラムは、割当てられた手続の完了を、他のすべてのクライアントプロセッサ又は依存関係のある手続を実行する他のクライアントプロセッサに通知する。なお、複数の手続（プログラムユニット）の実行状態を管理する手続実行状態テーブルを設けて、手続呼出プログラムは、プログラムユニットの実行完了に応じて手続実行状態テーブルを更新し、さらに手続実行状態テーブルを参照して実行可能なプログラムユニットを判定することも可能である。【００１９】
本発明によれば、マルチプロセッシング方法及びマルチプロセッサシステムにおいて、依存関係のある手続（プログラムユニット）を実行する場合に、順番待ちによる無駄な待ち時間を削減できる。
【図面の簡単な説明】
【００２０】
【図１】図１は、本発明が対象とするマルチプロセッサシステムの一例の概略構成を示す図である。
【図２】図２は、非同期呼出を使った並列処理を示す図である。
【図３】図３は、並列処理における順番待ちの問題を説明する図である。
【図４】図４は、図３の順番待ちの問題のキューイングによる解決法を示す図である。
【図５】図５は、依存関係のある手続（プログラムユニット）を示す図である。
【図６】図６は、従来手法での問題を説明する図である。
【図７】図７は、本発明の第１実施例の並列処理を示す図である。
【図８】図８は、第１実施例の並列処理における手続起動要求 (dispatch)後の手続要求処理を示すフローチャートである。
【図９】図９は、第１実施例の手続呼出処理を示すフローチャートである。
【図１０】図１０は、第１実施例の手続要求側の終了通知処理を示すフローチャートである。
【図１１】図１１は、本発明の第２実施例の並列処理を示す図である。
【図１２】図１２は、第２実施例の並列処理における手続起動要求 (dispatch)後の手続要求処理を示すフローチャートである。
【図１３】図１３は、本発明の第３実施例の並列処理を示す図である。
【図１４】図１４は、第３実施例の並列処理における手続起動要求 (dispatch)後の手続要求処理を示すフローチャートである。
【図１５】図１５は、本発明の第４実施例の並列処理を示す図である。
【図１６】図１６は、第４実施例の並列処理における手続起動要求 (dispatch)後の手続要求処理を示すフローチャートである。
【図１７】図１７は、第４実施例の並列処理における手続呼出処理を示すフローチャートである。
【図１８】図１８は、第４実施例の並列処理における終了通知処理を示すフローチャートである。
【図１９】図１９は、本発明の第５実施例の並列処理を示す図である。
【図２０】図２０は、本発明の第６実施例の並列処理における手続起動要求 (dispatch)後の手続要求処理を示すフローチャートである。
【図２１】図２１は、第６実施例の並列処理における手続呼出処理を示すフローチャートである。
【図２２】図２２は、本発明の第７実施例の並列処理を示す図である。
【図２３】図２３は、第７実施例の並列処理における手続起動要求 (dispatch)後の手続要求処理を示すフローチャートである。
【図２４】図２４は、本発明の第８実施例の並列処理を示す図である。
【符号の説明】
【００２１】
１−０    クライアントプロセッサ
１−１、１−２、１−３、１−ｎ    サーバプロセッサ
６    手続要求プログラム
７−１、７−２、７−３    手続呼出プログラム
８−０、８−１、８−２、８−３    実行キュー
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施例を説明する。以下の実施例では、図５のプログラムユニットを有する逐次実行プログラムを、図６の１個のクライアントプロセッサと３個のサーバプロセッサで構成されるマルチプロセッサシステムで実行するものとする。【００２３】
図７は、本発明の第１実施例のマルチプロセッサシステムにおける並列処理を説明する図である。第１実施例のマルチプロセッサシステムは、例えば、図１に示すような共有メモリを有するシステムであるが、クライアント・サーバ方式で、逐次実行プログラムを実行するマルチプロセッサシステムであれば、どのようなシステムでもよい。【００２４】
図７に示すように、第１実施例のマルチプロセッサシステムは、クライアントプロセッサ１−０と、３個のサーバプロセッサ１−１、１−２、１−３と、を備えるが、サーバプロセッサの個数は２個以上であればよい。手続要求側のクライアントプロセッサ１−０は、逐次実行プログラムから実行するプログラムユニット（手続）Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆを実行リスト５に読み出す。逐次実行プログラムには、手続の依存関係も記載されており、それらも合わせて実行リスト５に読み出す。【００２５】
手続要求側のクライアントプロセッサ１−０は、サーバプロセッサに手続を割当てる処理を行う手続要求プログラム６を有する。手続実行側のサーバプロセッサ１−１、１−２、１−３は、クライアントプロセッサ１−０から指定された手続（プログラムユニット）を実行するために呼び出す処理を行う手続呼出プログラム７−１、７−２、７−３を有する。【００２６】
実行リスト５では、実行する手続を順番に読み出し”ｓｔａｒｔ”が付加され、依存関係がある場合には、その後に”ｄｅｐ”で依存関係を記載する。図示の例では、手続Ａ、Ｂ、Ｃは依存関係はないが、手続Ｄは手続Ａの処理結果を使用する依存関係があり、手続Ｅは手続ＡとＢの処理結果を使用する依存関係があり、手続Ｆは手続ＢとＣの処理結果を使用する依存関係がある。実行リスト５の作成が完了すると、”ｄｉｓｐａｔｃｈ”で実行開始を指示する。従来は、”ｓｔａｒｔ”で手続の記載を行うと、直ちに実行開始が指示されたが、本実施例では、手続を記載しただけでは依存関係が記載されないため、”ｓｔａｒｔ”及び”ｄｅｐ”の記載がすべて完了した後、”ｄｉｓｐａｔｃｈ”で実行開始を指示する。【００２７】
クライアントプロセッサ１−０の手続要求プログラム６は、１つの実行キュー８−０を有する。手続要求プログラム６は、実行リスト５に、実行する手続（プログラムユニット）及びその依存関係が記載されると、実行キュー８−０にそれらの情報を登録すると共に、さらに各手続を実行するサーバプロセッサを決定して、それらの情報を実行キュー８−０に登録する。図示の例では、実行する手続、その依存関係に加えて、手続Ａ及びＤはサーバプロセッサ１−１で、手続ＢとＥはサーバプロセッサ１−２で、手続ＣとＦはサーバプロセッサ１−３で実行されることが登録される。【００２８】
手続要求プログラム６は、実行リスト５に”ｄｉｓｐａｔｃｈ”が入ると、実行キュー８−０も登録された手続を各サーバプロセッサ１−１、１−２、１−３に割当てる処理を行う。【００２９】
図８は、”ｄｉｓｐａｔｃｈ”が出された後の手続要求プログラム６の処理（以下ｄｉｓｐａｔｃｈ後処理）を示すフローチャートである。また、図９は手続要求プログラム６から手続起動要求がされた後のサーバプロセッサ１−１、１−２、１−３の手続呼出プログラム７−１、７−２、７−３の処理を示すフローチャートであり、図１０は手続呼出プログラム７−１、７−２、７−３から手続完了の通知を受けた後の手続要求プログラム６の処理を示すフローチャートである。【００３０】
手続要求プログラム６は、ステップ１０１で、実行キュー８−０から実行可能な手続を探す。ステップ１０２で、実行可能な手続が無いかを判定し、無ければ終了する。終了した後は、ここに記載していない他の処理を行うことができる。実行可能な手続がある時には、ステップ１０３で、実行キュー８−０において実行可能な手続を行うことが規定されている対象サーバプロセッサが手続を実行中であるかを判定する。実行中であれば、ステップ１０１に戻り、実行中でなければ、ステップ１０４に進み、対象サーバプロセッサにその手続の起動を指示する。そして、ステップ１０５で、対象サーバプロセッサの状態を実行中に変更してステップ１０１に戻る。【００３１】
最初の手続Ａであれば、対象サーバプロセッサ１−１は実行中でないので、サーバプロセッサ１−１に手続Ａの起動を指示する。以下、サーバプロセッサ１−２に手続Ｂの起動を、サーバプロセッサ１−３に手続Ｃの起動を指示する。【００３２】
手続Ｃの起動指示を行った後は、３つのサーバプロセッサはすべて手続を実行中であるので、ステップ１０３での判定がＹｅｓとなり、ステップ１０１に戻った後、ステップ１０２で実行可能な手続無し、と判定されるので、終了する。クライアントプロセッサ１−０は、後述するように終了通知を割り込みで受けるので、それまで他の処理を行う。【００３３】
一方、手続起動要求を受けたサーバプロセッサ１−１、１−２、１−３は、その手続呼出プログラム７−１、７−２、７−３がそれぞれ図９の処理を行う。手続起動要求を受けると、ステップ１１１で、要求された手続を起動し、ステップ１１２で手続を実行する。手続の完了を待ち、手続が完了すると、ステップ１１３で手続要求側のクライアントプロセッサ１−０の手続要求プログラム６に手続完了を通知する。そして、次の起動要求が来るのを待つ。【００３４】
手続要求プログラム６は、手続呼出プログラムから手続完了の通知を割込み処理により受けると、図１０に示すように、ステップ１２１で、完了した手続を実行状態から完了に変更するように実行キュー８−０を更新する。そして、ステップ１２２で、その手続を実行したサーバプロセッサの状態を実行完了、すなわち空き状態に変更する。ステップ１２３では、図８の”ｄｉｓｐａｔｃｈ”処理を行う。もし、図８の”ｄｉｓｐａｔｃｈ”処理が終了すると、割り込み前の状態に復帰する。【００３５】
図７及び図８に戻ると、手続要求プログラム６は、手続Ａ、Ｂ、Ｃの起動要求を指示した後、ステップ１０１と１０３の間をループしている。３つの手続のうち、最初にサーバプロセッサ１−２の手続Ｂの処理が完了して、完了通知を受け、図１０の処理を行う。残っている手続Ｄは手続Ａに依存し、手続Ｅは手続Ａ、Ｂに依存し、手続Ｆは手続Ｂ、Ｃに依存しているので、図８のステップ１０２では実行できる手続はないと判定される。次に、サーバプロセッサ１−３の手続Ｃの処理が完了して、完了通知を受ける。同様に図１０の処理を行い、手続Ｆが実行可能になり、サーバプロセッサ１−３が空き状態になるので、サーバプロセッサ１−３に対して手続Ｆの起動要求を行う。さらに、サーバプロセッサ１−１の手続Ａの処理が完了して、完了通知を受けると、同様に手続Ｄ及びＥが実行可能になり、サーバプロセッサ１−１が空き状態になり、サーバプロセッサ１−２は既に空き状態であるので、サーバプロセッサ１−１に対して手続Ｄの起動要求を、サーバプロセッサ１−２に対して手続Ｅの起動要求を行う。【００３６】
手続Ｄ及びＥの起動要求を行うと、実行する手続が残っていないので、図８のステップ１０２で、実行可能な手続は無い、と判定されるので、終了する。以下、手続Ｄ、Ｅ、Ｆの処理が完了すると、同様に図１０の処理を行い、実行する手続が残っていないので終了する。【００３７】
図６と図７を比較して明らかなように、従来例では、サーバプロセッサ１−３において、手続Ｃが完了した後、手続Ｆを起動するまで無駄な待ち時間ＷＴがあったが、第１実施例では、手続Ｃが完了した後、手続Ｆが直ぐに起動されている。【００３８】
図１１は、本発明の第２実施例のマルチプロセッサシステムにおける並列処理を説明する図である。第２実施例のマルチプロセッサシステムは、手続要求プログラム６の実行キュー８−０で、各手続を実行するサーバプロセッサが規定されておらず、処理状況に応じて各手続を実行するサーバプロセッサが動的に決定される点が、第１実施例と異なり、他は第１実施例と同じである。各手続を実行するサーバプロセッサを動的に決定するため、手続要求プログラム６が、図８の処理の代わりに、図１２のｄｉｓｐａｔｃｈ後処理を行う。【００３９】
図１２の第２実施例のｄｉｓｐａｔｃｈ後処理は、第１実施例のステップ１０１及び１０２と同じステップ１３１及び１３２を行う。ステップ１３２で、実行可能な手続があると判定されると、ステップ１３３で、実行可能なサーバプロセッサを探し、ステップ１３４で、実行可能なサーバプロセッサが無いかを判定し、無ければ終了し、あればステップ１３５に進む。ステップ１３５及び１３６は、第１実施例のステップ１０４及び１０５と同じである。【００４０】
図１１に示すように、第２実施例では、手続ＢとＣが完了すると、手続Ｆが実行可能であり、サーバプロセッサ１−２と１−３が空き状態にあるので、サーバプロセッサ１−２に対して手続Ｆを起動する。【００４１】
図１３は、本発明の第３実施例のマルチプロセッサシステムにおける並列処理を説明する図である。第３実施例のマルチプロセッサシステムは、手続要求プログラム６が、３個のサーバプロセッサに対応して３個の実行キュー８−０−１、８−０−２、８−０−３を有する点が第１実施例と異なり、他は第１実施例と同じである。手続要求プログラム６は、図８の処理の代わりに、図１４のｄｉｓｐａｔｃｈ後処理を行う。【００４２】
図１４の第３実施例のｄｉｓｐａｔｃｈ後処理によれば、”ｄｉｓｐａｔｃｈ”を受けると、ステップ１４１で、実行可能なサーバプロセッサ、すなわち空き状態のサーバプロセッサを探す。ステップ１４２で、実行可能なサーバプロセッサが無いかを判定する。実行可能なサーバプロセッサが無ければ、新たに手続の起動は行えないので、終了する。実行可能なサーバプロセッサがあれば、ステップ１４３で、実行キュー８−０−１、８−０−２、８−０−３のうちそのサーバプロセッサに対応する実行キューから実行可能な手続を探す。ステップ１４４で、実行可能な手続が無いか判定し、無ければステップ１４１に戻り、あればステップ１４５に進む。ステップ１４５及び１４６は、第１実施例のステップ１０４及び１０５と同じである。【００４３】
図１５は、本発明の第４実施例のマルチプロセッサシステムにおける並列処理を説明する図である。第４実施例のマルチプロセッサシステムは、サーバプロセッサの手続呼出プログラム７−１、７−２、７−３がそれぞれ実行キュー８−１、８−２、８−３を有する点が第１実施例と異なり、他は同じである。なお、クライアントプロセッサ１−０の手続要求プログラム６は、実行する手続及びそれを実行するサーバプロセッサを記載した実行キュー８−０を有し、全体の実行状態を管理する。【００４４】
この実施例では、逐次実行プログラムに、各手続（プログラムユニット）にどのサーバプロセッサで実行するかが規定されており、実行リスト５に実行する手続、実行するサーバプロセッサ及び依存関係が記載されると、クライアントプロセッサ１−０の手続要求プログラム６は、対応するサーバプロセッサにその情報を通知する。これに応じて、各サーバプロセッサは、実行する手続及び依存関係を各実行キューに登録する。【００４５】
図１６は、第４実施例のｄｉｓｐａｔｃｈ後処理を示す図である。クライアントプロセッサ１−０の手続要求プログラム６は、”ｄｉｓｐａｔｃｈ”を受けると、すべてのサーバプロセッサ１−１、１−２、１−３に”ｄｉｓｐａｔｃｈ”を通知する。【００４６】
図１７は、”ｄｉｓｐａｔｃｈ”通知を受けた後のサーバプロセッサの手続呼出プログラムの処理を示す図である。各手続呼出プログラムは、”ｄｉｓｐａｔｃｈ”通知を受けた後、ステップ１６１で、各実行キューから実行可能な手続を探し、ステップ１６２で、実行可能な手続が無いか判定する。実行可能な手続があれば、ステップ１６３に進んで手続を実行する。そして、手続の実行が完了すると、ステップ１６４で、すべてのサーバプロセッサ１−１、１−２、１−３に完了を通知し、ステップ１６５で、実行キューの手続の実行状態を完了に変更して更新し、ステップ１６１に戻る。【００４７】
ステップ１６２で、実行可能な手続が無いと判定された場合には、ステップ１６６で、実行キューに実行する手続が残っているかを判定し、残っていればステップ１６１に戻る。残っていなければ、ステップ１６７に進んで、クライアントプロセッサ１−０の手続要求プログラム６に起動の要求された、すなわち割当てられた手続が完了したことを通知し、次のｄｉｓｐａｔｃｈを待つ状態になる。【００４８】
図１８は、クライアントプロセッサ１−０の手続要求プログラム６が、サーバプロセッサの手続呼出プログラムから手続が完了したことを通知された時の処理を示す図である。完了通知を受けると、ステップ１７１で、実行キュー８−０において完了した手続に対して実行状態を完了に更新する。【００４９】
図１９は、本発明の第５実施例のマルチプロセッサシステムにおける並列処理を説明する図である。第５実施例のマルチプロセッサシステムは、手続呼出プログラム７−１、７−２、７−３の実行キュー８−１、８−２、８−３に、実行する手続の結果に影響され且つ他のサーバプロセッサで実行される手続については、他のサーバプロセッサの情報を登録する点が第４実施例と異なり、他は同じである。【００５０】
実行した手続の結果に影響され且つ他のサーバプロセッサで実行される手続が分かるので、そのサーバプロセッサに実行の完了を通知すればよい。【００５１】
第１実施例のマルチプロセッサシステムでは、サーバプロセッサからの手続の完了通知を割り込みで受信していたが、これをポーリングで行うことも可能である。本発明の第６実施例のマルチプロセッサシステムは、第１実施例のマルチプロセッサシステムにおいて、手続の完了通知の受信をポーリングで行うようにした点が異なり、他は同じである。【００５２】
手続の完了通知の受信をポーリングで行うために、第６実施例のマルチプロセッサシステムでは、クライアントプロセッサの手続要求プログラムが図２０のｄｉｓｐａｔｃｈ後処理を行い、サーバプロセッサの手続呼出プログラムが図２１の手続呼出処理を行う。【００５３】
図２０のｄｉｓｐａｔｃｈ後処理は、” ｄｉｓｐａｔｃｈ”を受けた後、ステップ１８１で、実行キュー８−０から実行可能な手続を探す。ステップ１８２で、実行可能な手続が無いかを判定する。実行可能な手続がある時には、ステップ１８３で、対象サーバプロセッサが手続を実行中であるかを判定する。実行中であれば、ステップ１８１に戻り、実行中でなければ、ステップ１８４に進み、対象サーバプロセッサにその手続の起動を指示する。そして、ステップ１８５で、対象サーバプロセッサの状態を実行中に変更してステップ１８１に戻る。【００５４】
ステップ１８２で、実行可能な手続が無いと判定された時には、ステップ１８６で、すべてのサーバプロセッサ１−１、１−２、１−３の実行状況を調査し、ステップ１８７で、手続が完了したサーバプロセッサがあるかを判定する。無ければステップ１８６に戻り、いずれかのサーバプロセッサが手続を完了するまでステップ１８６と１８７を繰り返す。手続が完了したサーバプロセッサがある時には、ステップ１８８で、実行キュー８−０の待ち状態を変更し、ステップ１８９で、そのサーバプロセッサの状態を終了に変更して、ステップ１９０で、すべての登録された手続が完了したかを判定する。完了していれば終了し、完了していなければステップステップ１８１に戻る。【００５５】
図２１の手続呼出処理では、クライアントプロセッサ１−０から手続起動要求を受けると、サーバプロセッサの手続呼出プログラムは、ステップ２０１で、要求された手続を起動し、ステップ２０２で手続を実行する。手続が完了しても完了の通知は行わず、ステップ２０３で、クライアントプロセッサ１−０の手続要求プログラム６からの完了確認要求が来るまで待ち、完了確認要求が来たら完了を通知して、次の起動要求を待つ。【００５６】
なお、第６実施例のポーリング処理の利用は、第２及び第３実施例にも適用可能である。【００５７】
図２２は、本発明の第７実施例のマルチプロセッサシステムにおける並列処理を説明する図である。第７実施例のマルチプロセッサシステムは、第４実施例のように手続完了後に他のサーバプロセッサに対して割込みで完了を通知するのではなく、プロセッサ同士が、共有メモリ３内に互いに読み出し及び書き込み可能な領域を有しており、その領域に手続の実行状態を記載した実行状態テーブル９を設ける点が、第４実施例と異なる。各サーバプロセッサは、割当てられた手続が完了すると、実行状態テーブル９を更新する。各サーバプロセッサは、実行状態テーブル９を参照することで、どの手続が完了したかを知ることができる。【００５８】
実行状態テーブル９事態は、クライアントプロセッサ１−０の手続要求プログラム６により用意される。手続要求プログラム６は、手続呼出プログラム７−１、７−２、７−３での手続の登録を行って実行キュー８−１、８−２、８−３を作成する時に、手続が完了した時に更新する実行状態テーブル９の位置を指定する。このため、手続要求プログラム６は、図１６のｄｉｓｐａｔｃｈ後処理を実行する。【００５９】
また、手続呼出プログラムは、図２３に示す手続呼出処理を実行する。図２３の手続呼出処理は、図１７の処理に類似しており、図１７の処理でステップ１６４を削除した処理である。【００６０】
図２４は、本発明の第８実施例のマルチプロセッサシステムにおける並列処理を説明する図である。第８実施例のマルチプロセッサシステムは、逐次実行プログラムに依存関係も一緒に記載されており、実行リスト５を作成すると依存関係も一緒に含まれ、実行キュー８−０に実行する手続を登録すると、自動的に依存関係も一緒に登録される点が第１実施例と異なり、他は第１実施例と同じである。従って、依存関係を登録するまで待つ必要はなく、”ｄｉｓｐａｔｃｈ”は不要であり、実行キュー８−０に手続と依存関係を登録する時に、”ｄｉｓｐａｔｃｈ”と同様の処理を行う。この処理方法は、第２から第５実施例にも適用可能である。【００６１】
以上、本発明の実施例を説明したが、各種の変形例が可能であるのはいうまでもない。
【図１】
2007108133.tif 000003
【図２】
2007108133.tif 000004
【図３】
2007108133.tif 000005
【図４】
2007108133.tif 000006
【図５】
2007108133.tif 000007
【図６】
2007108133.tif 000008
【図７】
2007108133.tif 000009
【図８】
2007108133.tif 000010
【図９】
2007108133.tif 000011
【図１０】
2007108133.tif 000012
【図１１】
2007108133.tif 000013
【図１２】
2007108133.tif 000014
【図１３】
2007108133.tif 000015
【図１４】
2007108133.tif 000016
【図１５】
2007108133.tif 000017
【図１６】
2007108133.tif 000018
【図１７】
2007108133.tif 000019
【図１８】
2007108133.tif 000020
【図１９】
2007108133.tif 000021
【図２０】
2007108133.tif 000022
【図２１】
2007108133.tif 000023
【図２２】
2007108133.tif 000024
【図２３】
2007108133.tif 000025
【図２４】
2007108133.tif 000026
【国際調査報告】
2007108133.tif 000027
2007108133.tif 000028
2007108133.tif 000029