(57)【要約】【課題】プロセッサ間の通信時間を最小化することにより、マルチプロセッサの高性能化を達成する。【解決手段】第１処理（１５１）、第２処理（１５２）、第３処理（１５３）、第４処理（１５４）をコンピュータに実行させる。上記第１処理では所定の無閉路有向グラフを作成する。上記第２処理では所定の無向連結木を作成する。上記第３処理では、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ。上記第４処理では、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる。上記無閉路有向グラフに対して上記無向連結木を作成し、上記第３処理及び第４処理を実施することで、全体の通信時間を最小化する。【選択図】図１５
2011003122.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサ用プログラムによって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発方法であって、
上記プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１処理と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２処理と、
上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ第３処理と、
上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる第４処理と、をコンピュータに実行させることを特徴とするソフトウェア開発方法。
【請求項２】
プロセッサ用プログラムによって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発方法であって、
上記プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１処理と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２処理と、
上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ第３処理と、
上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを当該節点集合に割り当てる第４処理と、
複数のプロセッサの中から他のプロセッサとの間の通信速度の総和が大きい順にプロセッサを一つ選ぶ第５処理と、
上記第３処理で得られた節点集合と他の節点集合との間の通信時間の総和が大きい順に節点集合を一つ選び、当該節点集合に含まれるタスクを上記プロセッサに割り当てる第６処理と、をコンピュータに実行させることを特徴とするソフトウェア開発方法。
【請求項３】
上記第４処理は、上記プロセッサがタスクを実行するために要する時間に関する制約として与えられたプロセッサ実行時間制約に基づいて、上記節点集合に含まれるタスクの実行時の総和が、上記プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たすか否かを判別する処理を含む請求項１又は２記載のソフトウェア開発方法。
【請求項４】
任意のプロセッサが実行するタスクは、当該プロセッサが実行する他のタスクから実行結果を入力するか、又は当該プロセッサが実行する他のタスクに実行結果を出力する、請求項１又は２記載のソフトウェア開発方法。
【請求項５】
プロセッサ用プログラムによって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発方法であって、
上記プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１処理と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２処理と、
上記第２処理で得られた無向連結木において、重みの総和の小さい順に複数の無向枝についての組合せを列挙する第３処理と、
上記無向連結木から上記無向枝の組合せを削除すると得られる複数の節点集合において、各節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる第４処理と、をコンピュータに実行させることを特徴とするソフトウェア開発方法。
【請求項６】
プロセッサ用プログラムによって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発方法であって、
プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１処理と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２処理と、
上記第２処理による無向連結木において、実行時間に関する閾値を超えないタスクを表す節点を選ぶ第３処理と、
上記第３処理で選ばれた節点に接続される無向枝のうち、重みの最も大きい無向枝に接続される節点を選び、当該節点と上記第３処理で選ばれた節点とを併合する第４処理と、をコンピュータに実行させることを特徴とするソフトウェア開発方法。
【請求項７】
コンピュータを、
プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１手段と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２手段と、
上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ第３手段と、
上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる第４手段として機能させるためのソフトウェア開発プログラムが記録されたコンピュータ読み取り可能な記録媒体。
【請求項８】
コンピュータを、
プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１手段と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２手段と、
上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ第３手段と、
上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを当該節点集合に分類する第４手段と、
複数のプロセッサの中から他のプロセッサとの間の通信速度の総和が大きい順にプロセッサを一つ選ぶ第５手段と、
上記第３手段で得られた節点集合と他の節点集合との間の通信時間の総和が大きい順に節点集合を一つ選び、当該節点集合に含まれるタスクを上記プロセッサに割り当てる第６手段として機能させるためのソフトウェア開発プログラムが記録されたコンピュータ読み取り可能な記録媒体。
【請求項９】
コンピュータを、
プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１手段と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２手段と、
上記第２手段で得られた無向連結木において、重みの総和の小さい順に複数の無向枝についての組合せを列挙する第３手段と、
上記無向連結木から上記無向枝の組合せを削除すると得られる複数の節点集合において、各節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる第４手段として機能させるためのソフトウェア開発プログラムが記録されたコンピュータ読み取り可能な記録媒体。
【請求項１０】
コンピュータを、
プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１手段と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２手段と、
上記第２手段による無向連結木において、実行時間に関する閾値を超えないタスクを表す節点を選ぶ第３手段と、
上記第３手段によって選ばれた節点に接続される無向枝のうち、重みの最も大きい無向枝に接続される節点を選び、当該節点と上記第３手段によって選ばれた節点とを併合する第４手段として機能させるためのソフトウェア開発プログラムが記録されたコンピュータ読み取り可能な記録媒体。
【請求項１１】
ソフトウェア開発プログラムが格納される記憶装置と、
上記ソフトウェア開発プログラムを実行することで、プロセッサ用プログラムによって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発機能を実現する中央処理装置と、を含むソフトウェア開発装置であって、
上記ソフトウェア開発機能は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１機能と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２機能と、
上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ第３機能と、
上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる第４機能と、を含むことを特徴とするソフトウェア開発装置。
【請求項１２】
ソフトウェア開発プログラムが格納される記憶装置と、
上記ソフトウェア開発プログラムを実行することで、プロセッサ用プログラムによって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発機能を実現する中央処理装置と、を含むソフトウェア開発装置であって、
上記ソフトウェア開発機能は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１機能と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２機能と、
上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ第３手段と、
上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを当該節点集合に分類する第４機能と、
複数のプロセッサの中から他のプロセッサとの間の通信速度の総和が大きい順にプロセッサを一つ選ぶ第５機能と、
上記第３手段で得られた節点集合と他の節点集合との間の通信時間の総和が大きい順に節点集合を一つ選び、当該節点集合に含まれるタスクを上記プロセッサに割り当てる第６機能と、を含むことを特徴とするソフトウェア開発装置。
【請求項１３】
ソフトウェア開発プログラムが格納される記憶装置と、
上記ソフトウェア開発プログラムを実行することで、プロセッサ用プログラムによって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発機能を実現する中央処理装置と、を含むソフトウェア開発装置であって、
上記ソフトウェア開発機能は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１機能と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２機能と、
上記第２手段で得られた無向連結木において、重みの総和の小さい順に複数の無向枝についての組合せを列挙する第３機能と、
上記無向連結木から上記無向枝の組合せを削除すると得られる複数の節点集合において、各節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる第４機能と、を含むことを特徴とするソフトウェア開発装置。
【請求項１４】
ソフトウェア開発プログラムが格納される記憶装置と、
上記ソフトウェア開発プログラムを実行することで、プロセッサ用プログラムによって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発機能を実現する中央処理装置と、を含むソフトウェア開発装置であって、
上記ソフトウェア開発機能は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する第１機能と、
上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる無向連結木であり、かつ、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる無向連結木を作成する第２機能と、
上記第２手段による無向連結木において、実行時間に関する閾値を超えないタスクを表す節点を選ぶ第３機能と、
上記第３機能により選ばれた節点に接続される無向枝のうち、重みの最も大きい無向枝に接続される節点を選び、当該節点と上記第３機能により選ばれた節点とを併合する第４機能と、を含むことを特徴とするソフトウェア開発装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセッサで実行されるプログラム（プロセッサ用プログラム）によって規定されるタスクを解析して、上記タスクを実行するプロセッサを決定するためのソフトウェア開発方法、ソフトウェア開発プログラムが記録されたコンピュータ読み取り可能な記録媒体、及びソフトウェアを開発するためのソフトウェア開発装置に関する。
【背景技術】
【０００２】
携帯電話、ゲーム機器、車載ナビゲーション端末を始めとする組込み機器のキーデバイスであるマイクロプロセッサは、これまでに主に動作周波数の向上により高性能化を実現し続けてきた。しかし、近年では動作周波数のさらなる向上が困難な状況になりつつある。主な原因は、プロセッサに構成されるパイプラインのステージ数を増加させても、各ステージにおける信号伝搬時間を短縮できなくなってきたからである。また、信号伝搬時間を短縮するために、トランジスタを駆動する電流を増加させることも考えられるが、トランジスタを貫通する定常リーク電流が指数関数的に増大するため、発熱による異常動作を引き起こす虞れがある。
【０００３】
このような状況を背景として、マルチプロセッサが実用化されてきている。マルチプロセッサとは、プログラムによって規定される処理の単位（以下、タスク）を、複数のプロセッサを使用して実行する装置であり、これにより動作周波数を向上させずに高性能化が可能になる。各タスクの間には、一般には実行順序に関する制約（以下、先行制約）が存在する。また、タスクを実行する際には、先行する処理の実行結果が必要になることが多い。このためマルチプロセッサは、複数のプロセッサが各タスクを実行し、その実行結果をプロセッサ間で通信するという動作を繰り返す。
【０００４】
タスクを実行するプロセッサを決定するための最も代表的な方法として、ＬＰＴ（Ｌｏｎｇｅｓｔ  Ｐｒｏｃｅｓｓｉｎｇ  Ｔｉｍｅ）法が非特許文献１に記載されている。ＬＰＴ法は、実行時間の長いタスクから順に、開始可能時刻の最も早いプロセッサに割り当てる方法である。しかし、ＬＰＴ法はプロセッサ間の通信時間を考慮していないため、通信時間が増加するとマルチプロセッサの性能が低下してしまう。
【０００５】
通信時間を最小化するために、タスクとプロセッサについてのすべての組合せ（以下、タスク割り当て）を列挙する方法や、整数計画法が考えられる。しかし、これらの方法はタスクやプロセッサの数が大きくなると、実用的な時間内で最適なタスク割り当てを求めることが困難になってしまう。
【０００６】
実用的な時間内で通信時間の最小化を図る方法として、例えば特許文献１に示される方法がある。この方法は、タスクをプロセッサに割り当てる際に、すでに他のプロセッサに割り当てられたタスクとの間の通信時間が最小になるプロセッサを選ぶ方法である。しかし、この方法は後続のタスクとの間の通信時間を考慮していないため、通信時間の偏差が大きいと全体の通信時間を最小化することが困難になってしまう。また、タスクの実行時間を考慮していないため、多くのタスクが特定のプロセッサに偏って割り当てられるとマルチプロセッサの性能が低下してしまう。
【０００７】
また、リニアアレイ型プロセッサシステムにおける動的プロセス割当てによってシステム全体の能力を最大限引き出すために、サブプロセスの実行スケジュールを、予め静的スケジューリング手段によって求めておくことで、効率的な処理を可能にする技術として、特許文献２に示される技術が知られている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平０９−０９７２４３号
【特許文献２】特開平１１−２７２６２３号
【非特許文献】
【０００９】
【非特許文献１】「岩波講座情報科学１９  最適化（Ｐ．１２５−Ｐ１２７）」、岩波書店（１９８２年９月１０日発行）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記のように、ＬＰＴ法はプロセッサ間の通信時間を考慮していないため、通信時間が増加するとマルチプロセッサの性能が低下してしまう。通信時間を最小化するために、タスクとプロセッサについてのすべての組合せ（以下、タスク割り当て）を列挙する方法や、整数計画法が考えられるが、これらの方法はタスクやプロセッサの数が大きくなると、実用的な時間内で最適なタスク割り当てを求めることが困難になってしまう。特許文献１に示される方法では、後続のタスクとの間の通信時間を考慮していないため、通信時間の偏差が大きいと全体の通信時間を最小化することが困難になってしまう。また、タスクの実行時間を考慮していないため、多くのタスクが特定のプロセッサに偏って割り当てられるとマルチプロセッサの性能が低下してしまう。
【００１１】
今後、プロセッサの数が増加してくると、さらなる高性能化が困難になってくると考えられる。最大の原因は、プロセッサ間の距離が増加し、結果としてプロセッサ間の通信時間が増大してしまうからである。そこで、本願発明者は、複数のプロセッサにタスクを割り当てる処理において、プロセッサ間通信時間を最小化するために、無向連結木を作成してそれを用いることが有利であることを見いだした。この点について、上記特許文献１，２では一切考慮されていない。
【００１２】
本発明の目的は、プロセッサ間の通信時間を最小化することにより、マルチプロセッサの高性能化を達成するための技術を提供することである。
【００１３】
本発明の上記並びにその他の目的と新規な特徴は本明細書の記述及び添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１４】
本願において開示される発明のうち代表的なものの概要を簡単に説明すれば下記の通りである。
【００１５】
すなわち、本発明にかかるソフトウェア開発方法は、以下の第１処理と、第２処理と、第３処理と、第４処理とをコンピュータに実行させるものでる。上記第１処理は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。上記第２処理は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。上記第３処理は、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ。上記第４処理は、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる。
【００１６】
このように、上記無閉路有向グラフに対して上記無向連結木を作成し、上記第３処理及び上記第４処理を実施することで、全体の通信時間を最小化することができる。このことが、プロセッサ間の通信時間を最小化することにより、マルチプロセッサの高性能化を達成する。
【発明の効果】
【００１７】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば下記のとおりである。
【００１８】
すなわち、プロセッサ間の通信時間を最小化することにより、マルチプロセッサの高性能化を可能にするための技術を提供することができる。
【図面の簡単な説明】
【００１９】
【図１】マルチプロセッサの構成例ブロック図である。
【図２】本発明にかかるソフトウェア開発装置における主要機能の説明図である。
【図３】上記ソフトウェア開発装置で処理されるプロセッサ用プログラムの構成例説明図である。
【図４】図３に示されるプログラムに対応する無閉路有向グラフの説明図である。
【図５】上記無閉路有向グラフと同じ節点で作成される無向連結木の説明図である。
【図６】タスク実行時刻を示すガントチャートの説明図である。
【図７】本発明にかかるソフトウェア開発装置の全体的な構成例ブロック図である。
【図８】本発明にかかるソフトウェア開発装置における主要機能の説明図である。
【図９】四つのプロセッサ間の通信速度の説明図である。
【図１０】節点集合間の通信時間の説明図である。
【図１１】無向枝番号の説明図である。
【図１２】上記無向枝番号の組合せの説明図である。
【図１３】本発明にかかるソフトウェア開発装置における主要機能の説明図である。
【図１４】節点併合無向連結木の説明図である。
【図１５】実施の形態１における主要処理を示すフローチャートである。
【図１６】実施の形態２における主要処理を示すフローチャートである。
【図１７】実施の形態３における主要処理を示すフローチャートである。
【図１８】実施の形態４における主要処理を示すフローチャートである。
【発明を実施するための形態】
【００２０】
１．実施の形態の概要
先ず、本願において開示される発明の代表的な実施の形態について概要を説明する。代表的な実施の形態についての概要説明で括弧を付して参照する図面中の参照符号はそれが付された構成要素の概念に含まれるものを例示するに過ぎない。
【００２１】
〔１〕本発明の代表的な実施の形態に係るソフトウェア開発方法は、以下の第１処理（１５１）と、第２処理（１５２）と、第３処理（１５３）と、第４処理（１５４）とをコンピュータ（７０１）に実行させるものである。
【００２２】
上記第１処理（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する処理とされる。
【００２３】
上記第２処理（１５２）は、無向連結木を作成する処理とされる。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００２４】
上記第３処理（１５３）は、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ処理とされる。
【００２５】
上記第４処理（１５４）は、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる処理とされる。
【００２６】
上記の構成によれば、全体の通信時間を最小化するようにタスクを複数の集合に分割することにより、上記第１処理（１５１）で作成された無閉路有向グラフにおいて、有向枝の重みの総和が最小になるカットを求めることに帰着させることができる。また、第２処理（１５２）で得られた無向連結木は、任意の有向グラフに対して作成することができ、当該有向グラフにおけるカットを一つの無向枝に縮約して表現できる。このため、もとの有向グラフに対して予め当該無向連結木を作成しておくことにより、カットを繰り返し求める際にも実用的な時間内でタスク割り当てを求めることができる。さらに、上記第１処理（１５１）で得られた無閉路有向グラフに対して、上記第２処理（１５２）で無向連結木を作成し、上記第３処理（１５３）を実施することで、全体の通信時間を最小化することができる。そして、タスク実行時間の上限及び下限を適切に設定し、上記第４処理（１５４）を実施することで、多くのタスクが特定のプロセッサに偏らないようにすることができる。
【００２７】
〔２〕また、別のソフトウェア開発方法は、以下の第１処理（１５１）と、第２処理（１５２）と、第３処理（１６２）と、第４処理（１６３）、第５処理（１６５）、第６処理（１６６）とをコンピュータ（７０１）に実行させるものである。
【００２８】
上記第１処理（１６１）は、上記プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する処理とされる。
【００２９】
上記第２処理（１５１）は、無向連結木を作成する処理とされる。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００３０】
上記第３処理（１５２）は、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ処理とされる。
【００３１】
上記第４処理（１６３）は、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを当該節点集合に割り当てる処理とされる。
【００３２】
上記第５処理（１６５）は、複数のプロセッサの中から他のプロセッサとの間の通信速度の総和が大きい順にプロセッサを一つ選ぶ処理とされる。
【００３３】
上記第６処理（１６６）は、上記第３処理で得られた節点集合と他の節点集合との間の通信時間の総和が大きい順に節点集合を一つ選び、当該節点集合に含まれるタスクを上記プロセッサに割り当てる処理とされる。
【００３４】
〔３〕上記〔１〕又は〔２〕において、上記第４処理には、上記プロセッサがタスクを実行するために要する時間に関する制約として与えられたプロセッサ実行時間制約に基づいて、上記節点集合に含まれるタスクの実行時の総和が、上記プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たすか否かを判別する処理を含めることができる。
【００３５】
〔４〕上記〔１〕又は〔２〕において、任意のプロセッサが実行するタスクは、当該プロセッサが実行する他のタスクから実行結果を入力するか、又は当該プロセッサが実行する他のタスクに実行結果を出力する。
【００３６】
〔５〕さらに、別のソフトウェア開発方法は、以下の第１処理（１５１）と、第２処理（１５２）と、第３処理（１７２）と、第４処理（１７３）とをコンピュータ（７０１）に実行させるものである。
【００３７】
上記第１処理（１５１）は、上記プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する処理とされる。
【００３８】
上記第２処理（１５２）は、無向連結木を作成する処理とされる。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００３９】
上記第３処理（１７２）は、上記第２処理で得られた無向連結木において、重みの総和の小さい順に複数の無向枝についての組合せを列挙する処理とされる。
【００４０】
上記第４処理（１７３）は、上記無向連結木から上記無向枝の組合せを削除すると得られる複数の節点集合において、各節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる処理とされる。
【００４１】
〔６〕そして、別のソフトウェア開発方法は、以下の第１処理（１５１）と、第２処理（１５２）と、第３処理（１８２）と、第４処理（１８３）とをコンピュータ（７０１）に実行させるものである。
【００４２】
上記第１処理（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する処理とされる。
【００４３】
上記第２処理（１５２）は、無向連結木を作成する処理とされる。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００４４】
上記第３処理（１８２）は、上記第２処理による無向連結木において、実行時間に関する閾値を超えないタスクを表す節点を選ぶ処理とされる。
【００４５】
上記第４処理（１８３）は、上記節点に接続される無向枝のうち、重みの最も大きい無向枝に接続される節点を選び、当該節点と上記第３処理で選ばれた節点とを併合する処理とされる。
【００４６】
〔７〕本発明の代表的な実施の形態に係る記録媒体（７０６）には、コンピュータ（７０１）を、第１手段（１５１）と、第２手段（１５２）と、第３手段（１５３）と、第４手段（１５４）として機能させるためのソフトウェア開発プログラムが記録されている。
【００４７】
上記第１手段（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。
【００４８】
上記第２手段（１５２）は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００４９】
上記第３手段（１５３）は、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ。
【００５０】
上記第４手段（１５４）は、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる。
【００５１】
〔８〕本発明の代表的な実施の形態に係る別の記録媒体（７０６）には、コンピュータ（７０１）を、以下の第１手段（１５１）と、第２手段（１５２）と、第３手段（１６２）と、第４手段（１６３）、第５手段（１６５）と、第６手段（１６６）として機能させるためのソフトウェア開発プログラムが記録されている。
【００５２】
上記第１手段（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。
【００５３】
上記第２手段（１５２）は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００５４】
上記第３手段（１６２）は、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ。
【００５５】
上記第４手段（１６３）は、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを当該節点集合に分類する。
【００５６】
上記第５手段（１６５）は、複数のプロセッサの中から他のプロセッサとの間の通信速度の総和が大きい順にプロセッサを一つ選ぶ。
【００５７】
上記第６手段（１６６）は、上記第３手段で得られた節点集合と他の節点集合との間の通信時間の総和が大きい順に節点集合を一つ選び、当該節点集合に含まれるタスクを上記プロセッサに割り当てる。
【００５８】
〔９〕本発明の代表的な実施の形態に係る別の記録媒体（７０６）には、コンピュータ（７０１）を、以下の第１手段（１５１）と、第２手段（１５２）と、第３手段（１７２）と、第４手段（１７３）として機能させるためのソフトウェア開発プログラムが記録されている。
【００５９】
上記第１手段（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。
【００６０】
上記第２手段（１５２）は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００６１】
上記第３手段（１７２）は、上記第２手段で得られた無向連結木において、重みの総和の小さい順に複数の無向枝についての組合せを列挙する。
【００６２】
上記第４手段（１７３）は、上記無向連結木から上記無向枝の組合せを削除すると得られる複数の節点集合において、各節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる。
【００６３】
〔１０〕本発明の代表的な実施の形態に係る別の記録媒体（７０６）には、コンピュータ（７０１）を、以下の第１手段（１５１）と、第２手段（１５２）と、第３手段（１８２）と、第４手段（１８３）として機能させるためのソフトウェア開発プログラムが記録されている。
【００６４】
上記第１手段（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。
【００６５】
上記第２手段（１５２）は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００６６】
上記第３手段（１８２）は、上記第２手段による無向連結木において、実行時間に関する閾値を超えないタスクを表す節点を選ぶ。
【００６７】
上記第４手段（１８３）は、上記節点に接続される無向枝のうち、重みの最も大きい無向枝に接続される節点を選び、当該節点と上記第３手段によって選ばれた節点とを併合する。
【００６８】
〔１１〕本発明の代表的な実施の形態に係るソフトウェア開発装置（７００）は、ソフトウェア開発プログラムが格納される記憶装置（７３）と、上記ソフトウェア開発プログラムを実行することで、タスクを実行するプロセッサを決定するためのソフトウェア開発機能を実現する中央処理装置（７２）とを含む。
【００６９】
上記ソフトウェア開発機能には、以下の第１機能（１５１）と、第２機能（１５２）と、第３機能（１５３）と、第４機能（１５４）とを含めることができる。
【００７０】
上記第１機能（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。
【００７１】
上記第２機能（１５２）は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００７２】
上記第３機能（１５３）は、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ。
【００７３】
上記第４機能（１５４）は、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる。
【００７４】
〔１２〕上記ソフトウェア開発機能には、以下の第１機能（１５１）と、第２機能（１５２）と、第３機能（１６２）と、第４機能（１６３）、第５機能（１６５）と、第６機能（１６６）とを含めることができる。
【００７５】
上記第１機能（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。
【００７６】
上記第２機能（１５２）は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００７７】
上記第３機能（１６２）は、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合を選ぶ。
【００７８】
上記第４機能（１６３）は、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを当該節点集合に分類する。
【００７９】
上記第５機能（１６５）は、複数のプロセッサの中から他のプロセッサとの間の通信速度の総和が大きい順にプロセッサを一つ選ぶ。
【００８０】
上記第６機能（１６６）は、上記第３手段で得られた節点集合と他の節点集合との間の通信時間の総和が大きい順に節点集合を一つ選び、当該節点集合に含まれるタスクを上記プロセッサに割り当てる。
【００８１】
〔１３〕上記ソフトウェア開発機能には、以下の第１機能（１５１）と、第２機能（１５２）と、第３機能（１７２）と、第４機能（１７３）とを含めることができる。
【００８２】
上記第１機能（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。
【００８３】
上記第２機能（１５２）は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００８４】
上記第３機能（１７２）は、上記第２機能で得られた無向連結木において、重みの総和の小さい順に複数の無向枝についての組合せを列挙する。
【００８５】
上記第４機能（１７３）は、上記無向連結木から上記無向枝の組合せを削除すると得られる複数の節点集合において、各節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクを上記プロセッサに割り当てる。
【００８６】
〔１４〕上記ソフトウェア開発機能には、以下の第１機能（１５１）と、第２機能（１５２）と、第３機能（１７２）と、第４機能（１７３）とを含めることができる。
【００８７】
上記第１機能（１５１）は、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフを作成する。
【００８８】
上記第２機能（１５２）は、無向連結木を作成する。ここで、この無向連結木は、上記無閉路有向グラフと同じ節点で構成され、任意の二つの節点を分割するときの最小カットの重みの総和が、上記無閉路有向グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しくなる。しかも、この無向連結木は、任意の一つの無向枝を削除すると二つの節点集合に分割され、上記無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重みに等しくなる。
【００８９】
上記第３機能（１８２）は、上記第２手段による無向連結木において、実行時間に関する閾値を超えないタスクを表す節点を選ぶ。
【００９０】
上記第４機能（１８３）は、上記節点に接続される無向枝のうち、重みの最も大きい無向枝に接続される節点を選び、当該節点と上記第３機能によって選ばれた節点とを併合する。
【００９１】
２．実施の形態の詳細
実施の形態について更に詳述する。
【００９２】
＜実施の形態１＞
図７には、本発明にかかるソフトウェア開発装置の構成例が示される。
【００９３】
図７に示されるソフトウェア開発装置７００は、コンピュータ７０１を含み、このコンピュータ７０１に、情報表示のためのディスプレイ７０２、キーボード７０３やマウス７０４などの入力装置、磁気ディスク又は光ディスク７０６の読み書きを可能とするディスクドライブ７０５が結合されて成る。上記コンピュータ７０１は、特に制限されないが、ワークステーションとされ、メモリ７１、ＣＰＵ（中央処理装置）７２、ハードディスク７３、及び外部インタフェース７４を含み、それらがバス７５を介して互いに結合されて成る。ハードディスク７３には、プログラムや各種情報が格納される。上記プログラムには、上記ＣＰＵ７２で実行されるソフトウェア開発プログラムや、プロセッサ用プログラムが含まれる。また、上記各種情報には、タスク実行時間、プロセッサ間通信時間、プロセッサ間通信速度、タスク間先行制約、プロセッサ実行時間制約、タスク実行プロセッサ名、タスク実行時刻が含まれる。上記メモリ７１は、上記ＣＰＵ７２でプログラムが実行される際の作業領域などに利用される。上記外部インタフェース７４は、上記ディスプレイ７０２、キーボード７０３、マウス７０４、ディスクドライブ７０５との間で各種情報の入出力を可能とする。上記磁気ディスク又は光ディスク７０６は、本発明における記録媒体の一例とされる。この磁気ディスク又は光ディスク７０６には、プログラムや各種情報が格納され、それが必要に応じてコンピュータ７０１に読み込まれるようになっている。通常は、上記磁気ディスク又は光ディスク７０６内のプログラムや各種情報は、外部インタフェース７４を介してハードディスク７３に書き込まれる。
【００９４】
上記構成のソフトウェア開発装置７００でソフトウェア開発プログラムが実行されることにより、プロセッサで実行されるプログラム（プロセッサ用プログラム）によって規定されるタスクが複数のプロセッサに割り当てられる。
【００９５】
図１には、上記マルチプロセッサの構成例が示される。
【００９６】
上記マルチプロセッサは、それぞれ局所メモリを内蔵する複数のプロセッサと、それぞれコントローラを内蔵する複数の共有メモリとを含んで成る。複数のプロセッサ１０１と複数の共有メモリ１０２とは、ルータ（バス）によって結合される。マルチプロセッサの構成には、図１（Ａ）に示されるように、プロセッサ１０１と共有メモリ１０２とがバスによって結合される構成（バス構成）と、図１（Ｂ）に示されるように、プロセッサ１０１と共有メモリ１０２とが２次元メッシュ状に結合される構成（ネットワーク構成）とがある。各プロセッサの処理実行とプロセッサ間の通信は、並列に行うことができるものとする。各プロセッサの処理速度は同一とし、プロセッサ間の通信速度も同一とする。
【００９７】
図２には、図７に示されるソフトウェア開発装置７００における主要機能が示される。
【００９８】
ソフトウェア開発装置７００における上記ＣＰＵ７２によって上記ソフトウェア開発プログラムが実行され、それによってソフトウェア開発手段が実現される。このソフトウェア開発手段には、タスク解析手段２０１、タスク割り当て手段２０２、タスク実行時刻決定手段２０３が含まれる。タスク解析手段２０１は、プロセッサ用プログラムを取り込んで、タスク解析を行う。このタスク解析の結果、タスク実行時間、プロセッサ間通信時間、タスク間先行制約が求められる。上記タスク割り当て手段２０２は、プロセッサ実行時間制約、タスク実行時間、プロセッサ間通信時間、タスク間先行制約に基づいて、プロセッサに対するタスク割り当てを行う。このタスク割り当てによりタスク実行プロセッサ名が得られる。実行時刻決定手段２０３は、タスク実行プロセッサ名、タスク実行時間、プロセッサ間通信時間、タスク間先行制約に基づいて各タスクの実行時刻を決定する。
【００９９】
図３には、プロセッサ用プログラムの構成例が示される。
【０１００】
ここで、Ｔ１〜Ｔ９はタスクを示す。図３に示されるように、プロセッサ用プログラムでは、複数のタスクが規定されている。上記タスク解析手段２０１は、このようなプロセッサ用プログラムを入力し、当該プログラムによって規定されるタスクを解析することにより、タスク実行時間、プロセッサ間通信時間、タスク間先行制約を得る。尚、図３に示される例では、プログラムの各行を一つのタスクとして扱っているが、これに限定されるものではない。
【０１０１】
タスク割り当て手段２０２は、前述のタスク実行時間と、プロセッサ間通信時間と、タスク間先行制約に加え、プロセッサ実行時間制約を入力し、タスク実行プロセッサ名を出力する。プロセッサ実行時間制約は、プロセッサにおけるタスクの実行時間の上限と下限を表すもので、これが、上記タスク割り当て手段２０２での処理で参照される。
【０１０２】
次に、タスク割り当ての手順について説明する。
【０１０３】
図１５には、図２に示される主要機能によって行われるタスク割り当ての流れが示される。
【０１０４】
先ず、プロセッサ用プログラムによって規定されるタスクを節点で表し、タスク間の先行制約を対応する節点間の有向枝で表し、タスク間の通信時間を有向枝の重みで表す無閉路有向グラフが作成される（１５１）。
【０１０５】
図４には、図３に示したプログラムに対応する無閉路有向グラフが示される。
【０１０６】
この無閉路有向グラフにおける節点は、タスクを示している。節点の左側の値は、タスクの実行時間を示している。有向枝は、始点の処理と終点の処理の間の先行制約を示している。有向枝の傍の値は、始点の処理と終点の処理を異なるプロセッサが実行する際に、始点の処理の実行結果を当該プロセッサ間で通信するために要する通信時間を示している。
【０１０７】
次に、下記（１）〜（３）の性質を持つ無向連結木が作成される（１５２）。図５には、この無向連結木の一例が示される。
【０１０８】
（１）無閉路有向グラフと同じ節点で作成される。
【０１０９】
（２）任意の二つの節点を分割するときの最小カットの重みの総和が無閉路有効グラフにおいて同じ二つの節点を分割するときの最小カットの重みの総和に等しい。
【０１１０】
（３）任意の一つの無向枝を削除すると、二つの節点集合に分割されるが、無閉路有向グラフを同じ二つの節点集合に分割するときのカットの重みの総和が、当該無向枝の重み等しい。
【０１１１】
次に、上記無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除すると得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さいほうの節点集合が選ばれる（１５３）。
【０１１２】
そして、上記プロセッサ実行時間制約に基づいて、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たすか否かが判別され、上記制約を満たす場合、当該タスクがプロセッサに割り当てられる（１５４）。
【０１１３】
次に、全タスクを割り当てたか否かの判別が行われる（１５５）。この判別において、全タスクを割り当てたと判断された場合には、本フローチャートに従う処理が終了される。しかし、上記ステップ１５５の判別において、未だ全タスクを割り当てていないと判断された場合には、全無向枝を探索したか否かの判別が行われる（１５６）。この判別において、全無向枝を探索したと判断された場合には、タスク割り当て不可のメッセージを出力して本フローチャートに従う処理が終了される（１５７）。しかし、上記ステップ１５６の判別において、全無向枝を探索していないと判断された場合には、上記ステップ１５３の処理に戻される。このようにしてタスク割り当てが行われる。
【０１１４】
次に、上記ステップ１５３，１５４の処理により、図５に示される無向連結木が表すタスクが二つのプロセッサに割り当てられる様子について具体的に説明する。
【０１１５】
尚、プロセッサにおけるタスクの実行時間の上限を「１５０」、下限を「１００」とする。ステップ１５３の処理において、重みが１０と最も小さい節点Ｔ２とＴ４の間の無向枝が選ばれ、節点Ｔ２で構成される節点集合と、節点Ｔ１，Ｔ３，Ｔ４，Ｔ５，Ｔ６，Ｔ７，Ｔ８，Ｔ９で構成される節点集合に分割される。前者の節点集合に含まれるタスクの実行時間の総和は「３０」、後者は「２１５」であるため、総和の小さい前者の節点集合が選ばれる。上記ステップ１５４の処理において、前者の節点集合に含まれるタスクの実行時間の総和が下限を満たさないので、プロセッサに割り当てられずにステップ１５３の処理に戻る。再びステップ１５３の処理において、重みが「２０」と次に小さい節点Ｔ４とＴ７の間の無向枝が選ばれ、節点Ｔ１，Ｔ２，Ｔ４，Ｔ６で構成される節点集合と、節点Ｔ３，Ｔ５，Ｔ７，Ｔ８，Ｔ９で構成される節点集合に分割される。前者の節点集合に含まれるタスクの実行時間の総和は「９０」、後者は「１５５」であるため、総和の小さい前者の節点集合が選ばれる。そして、ステップ１５４の処理において、前者の節点集合に含まれるタスクの実行時間の総和が下限を満たさないので、プロセッサに割り当てられずに、ステップ１５５，１５６を介して、ステップ１５３の処理に戻る。再びステップ１５３の処理において、重みが「４０」と次に小さい節点Ｔ５とＴ７の間の無向枝が選ばれ、節点Ｔ１，Ｔ２，Ｔ４，Ｔ６，Ｔ７で構成される節点集合と、節点Ｔ３，Ｔ５，Ｔ８，Ｔ９で構成される節点集合に分割される。前者の節点集合に含まれるタスクの実行時間の総和は「１００」、後者は「１４５」であるため、総和の小さい前者の節点集合が選ばれる。ステップ１５４の処理において、前者の節点集合に含まれるタスクの実行時間の総和が上限と下限を満たすので、節点Ｔ１，Ｔ２，Ｔ４，Ｔ６，Ｔ７が表すタスクが一つのプロセッサに割り当てられ、前者の節点集合とそれに接続する無向枝が当該無向連結木から削除される。残りの当該無向連結木に含まれるタスクの実行時間の総和は「１４５」であり、上限と下限を満たすので、節点Ｔ３，Ｔ５，Ｔ８，Ｔ９が表すタスクがもう一つのプロセッサに割り当てられ、タスク割り当てが完了する。図６には、上記のようにタスクが割り当てられた場合のタスク実行時刻を示すガントチャートが示される。プロセッサ１には、節点Ｔ１，Ｔ２，Ｔ４，Ｔ６，Ｔ７によって表されるタスクが割り当てられ、プロセッサ２には、節点Ｔ３，Ｔ５，Ｔ８，Ｔ９によって表されるタスクが割り当てられる。
【０１１６】
尚、三つ以上のプロセッサに割り当てる場合には、残りの当該無向連結木をさらに分割するようにステップ１５３と１５４の処理が繰り返される。また、ステップ１５３の処理において、重みが同一の無向枝が複数ある場合には、いずれか一つが選ばれる。ステップ１５４の処理において、どの節点集合もタスクの実行時間の上限と下限を満たさない場合には、メッセージを出力して終了する。
【０１１７】
実施の形態１によれば以下の作用効果が得られる。
【０１１８】
（１）全体の通信時間を最小化するようにタスクを複数の集合に分割することは、上記ステップ１５１の処理で作成された無閉路有向グラフにおいて、有向枝の重みの総和が最小になるカットを求めることに帰着させることができる。
【０１１９】
（２）ステップ１５２の処理で得られた無向連結木は、任意の有向グラフに対して作成することができ、当該有向グラフにおけるカットを一つの無向枝に縮約して表現できる。このことは、例えば「組合せ最適化  理論とアルゴリズム（Ｐ．４６−Ｐ．４７，Ｐ１９６−Ｐ２０３）シュプリンガージャパン（２００５年）」に記載されている。このため、もとの有向グラフに対して予め当該無向連結木を作成しておくことにより、カットを繰り返し求める際にも実用的な時間内でタスク割り当てを求めることができる。
【０１２０】
（３）ステップ１５１の処理で得られた無閉路有向グラフに対して、ステップ１５２の処理で無向連結木を作成し、ステップ１５３の処理を実施することで、全体の通信時間を最小化することができ、また、実用的な時間内でタスク割り当てを求めることができる。
【０１２１】
（４）さらに、タスク実行時間の上限及び下限を適切に設定し、ステップ１５４の処理を実施することで、多くのタスクが特定のプロセッサに偏らないようにすることができる。
【０１２２】
＜実施の形態２＞
図８には、図７に示されるソフトウェア開発装置７００における主要機能が示される。
【０１２３】
図８に示される主要機能が、図２に示されるのと大きく相違するのは、タスク割り当て手段２０２にプロセッサ間通信速度が入力されている点である。タスク割り当てにおいて、このプロセッサ間通信速度が参照される。
【０１２４】
次に、タスク割り当ての手順について説明する。
【０１２５】
図１６には、図８に示される主要機能によって行われるタスク割り当ての流れが示される。
【０１２６】
先ず、無閉路有向グラフの作成、無向連結木の作成が行われる（１６１）が、これは、図１５におけるステップ１５１，１５２と同じであるため、ここではそれについての詳細な説明を省略する。
【０１２７】
次に、上記ステップ１６１で得られた無向連結木において、重みの小さい順に無向枝を一つ選び、当該無向枝を削除することで得られる二つの節点集合について、節点が表すタスクの実行時間の総和の小さい方の節点集合が選ばれる（１６２）。
【０１２８】
そして、プロセッサ実行時間制約に基づいて、上記節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たすか否かの判別が行われ、当該制約を満たす場合に、当該タスクが当該節点集合に分類される（１６３）。
【０１２９】
次に、全タスクを分類したか否かの判別が行われる（１６４）。この判別において、全タスクを分類していないと判断された場合、全無向枝を探索したか否かの判別が行われる（１６８）。この判別において、全無向枝を探索していないと判断された場合には、ステップ１６２の処理に戻される。また、上記ステップ１６８の判別において全無向枝を探索したと判断された場合には、タスク割り当て不可のメッセージを出力して、本フローチャートに従う処理が終了される。
【０１３０】
上記ステップ１６４の判別において、全タスクを分類したと判断された場合、複数のプロセッサにおいて、他のプロセッサとの間の通信速度の総和が大きい順にプロセッサが一つ選ばれる（１６５）。そして、上記節点集合において、他の節点集合との間の通信時間の総和が大きい順に節点集合が一つ選ばれ、当該節点集合に含まれるタスクが上記プロセッサに割り当てられる（１６６）。
【０１３１】
そして、全タスクを割り当てたか否かの判別が行われる（１６７）。この判別において、全タスクを割り当てていないと判断された場合には、上記ステップ１６５の処理に戻される。そして、上記ステップ１６７の判別において、全タスクを割り当てたと判断された場合には、本フローチャートに従う処理が終了される。
【０１３２】
ここで、上記ステップ１６５，１６６の処理により、タスクが四つのプロセッサに割り当てられる場合について具体的に説明する。
【０１３３】
図９には、四つのプロセッサＰ１〜Ｐ４間の通信速度が示される。
【０１３４】
図９において、例えばプロセッサＰ１，Ｐ２間の通信速度は「４０」である。上記ステップ１６５の処理においては、他のプロセッサとの間の通信速度の総和（合計）が「１３０」と最も大きいプロセッサＰ２が選ばれる。
【０１３５】
図１０には、節点集合間の通信時間が示される。
【０１３６】
例えば節点集合Ａ１，Ａ２間の通信時間は「１０」である。節点集合Ａ１にはタスクＴ１１が含まれ、節点集合Ａ２にはタスクＴ１２，Ｔ１４，Ｔ１５が含まれ、節点集合Ａ３にはタスクＴ１３，Ｔ１６が含まれ、節点集合Ａ４にはタスクＴ１７，Ｔ１８が含まれるものとする。上記ステップ１６６の処理において、他の節点集合との間の通信時間の総和が「８０」と最も大きい節点集合Ａ２が選ばれ、節点集合Ａ２に含まれるタスクＴ１２，Ｔ１４，Ｔ１５がプロセッサＰ２に割り当てられる。再びステップ１６５の処理において、プロセッサ間の通信速度の総和が「１１０」と次に大きいプロセッサ１が選ばれる。ステップ１６６の処理において、節点集合間の通信時間の総和が「５０」と次に大きい節点集合を探すと、節点集合Ａ３と節点集合Ａ４が見つかるが、通信時間の最大値が５０と大きい節点集合Ａ４が選ばれ、節点集合Ａ４に含まれるタスクＴ１７，Ｔ１８がプロセッサＰ１に割り当てられる。再びステップ１６５の処理において、プロセッサ間の通信速度の総和が「９０」と次に大きいプロセッサを探すと、プロセッサＰ３とプロセッサＰ４が見つかるが、通信速度の最大値が「６０」と大きいプロセッサＰ４が選ばれる。ステップ１６５の処理において、節点集合間の通信時間の総和が「５０」と次に大きい節点集合Ａ３が選ばれ、節点集合Ａ３に含まれるタスクＴ１３，Ｔ１６がプロセッサＰ４に割り当てられる。再びステップ１６５の処理において、残りのプロセッサＰ３が選ばれる。ステップ１６５の処理において、残りの節点集合Ａ１が選ばれ、ステップ１６６の処理において、節点集合Ａ１に含まれるタスクＴ１１がプロセッサＰ３に割り当てられる。
【０１３７】
このように実施の形態２によれば、通信時間の総和が大きい節点集合を選び、当該節点集合に含まれるタスクを通信速度が大きいプロセッサに割り当てるようにしているので、プロセッサ間の通信速度が同一でない場合でも、全体の通信時間を最小化することができる。
【０１３８】
＜実施の形態３＞
図１７には、図８に示される主要機能によって行われる別のタスク割り当ての流れが示される。
【０１３９】
先ず、無閉路有向グラフの作成、無向連結木の作成が行われる（１７１）が、これは、図１５におけるステップ１５１，１５２と同じであるため、ここではそれについての詳細な説明を省略する。
【０１４０】
次に、上記ステップ１７１で得られた無向連結木において、重みの総和の小さい順に複数の無向枝についての組み合わせが列挙される（１７２）。
【０１４１】
そして、上記無向連結木から上記無向枝の組み合わせを削除すると得られる複数の節点集合において、各節点集合に含まれるタスクの実行時間の総和が、プロセッサにおけるタスクの実行時間の上限と下限を表す制約を満たす場合に、当該タスクがプロセッサに割り当てられる（１７３）。
【０１４２】
次に、全タスクを割り当てたか否かの判別が行われる（１７４）。この判別において、全タスクを割り当てたと判断された場合には、本フローチャートに従う処理が終了される。しかし、上記ステップ１７４の判別において、未だ全タスクを割り当てていないと判断された場合には、全ての組み合わせを列挙したか否かの判別が行われる（１７５）。この判別において、全ての組み合わせを列挙したと判断された場合には、タスク割り当て不可のメッセージを出力して本フローチャートに従う処理が終了される（１７６）。しかし、上記ステップ１７５の判別において、全ての組み合わせを列挙していないと判断された場合には、上記ステップ１７２の処理に戻される。このようにしてタスク割り当てが行われる。
【０１４３】
図１１には、無向枝番号が示される。
【０１４４】
図１１に示される無向枝の番号は、図５に示される無向連結木を構成する無向枝について、重みの小さい順に付与したものである。重みが同一の無向枝が複数ある場合には、任意の順に番号が付与される。
【０１４５】
図１２には、無向枝番号の組合せが示される。
【０１４６】
この無向枝番号組合せは、図５に示した無向連結木を構成する無向枝のうちの三つを選ぶ組合せについて、図１１に示される無向枝番号の総和の小さい順に列挙したものである。無向枝番号の総和が同一の組合せが複数ある場合には、より大きい番号を含む組合せから順に列挙される。１からｎの無向枝番号のうちのｒ個を選ぶときに、無向枝番号の総和がｍになる組合せを効率よく列挙するには、ｒ個の無向枝番号をＡｋ（ｋは１からｒの自然数）として、下記に示す数式を満たすＡｋをｋ＝１の場合から昇順に求めればよい。
【０１４７】
【数１】
2011003122.tif 000003
【０１４８】
【数２】
2011003122.tif 000004
【０１４９】
次に、上記ステップ１７２，１７３の処理を実施することにより、タスクを四つのプロセッサに割り当てる様子について具体的に説明する。尚、プロセッサにおけるタスクの実行時間の上限を７５、下限を４０とする。
【０１５０】
先ず、ステップ１７２の処理において、図１１に示した無向枝の重みをもとに図１２の最初の行の［Ｔ２−Ｔ４，Ｔ４−Ｔ７，Ｔ１−Ｔ４］で表す無向枝の組合せが列挙される。
【０１５１】
次に、上記ステップ１７３の処理において、無向枝の組合せを削除するとタスクＴ２のみを含む節点集合が得られるが、タスクＴ２の実行時間は下限を満たさないので、プロセッサに割り当てられずに、ステップ１７２の処理に戻される。このような操作が繰り返された後に再びステップ１７２の処理において、図１２における第３７番目（Ｎｏ．３７）の［Ｔ１−Ｔ４，Ｔ５−Ｔ７，Ｔ３−Ｔ５］で表す無向枝の組合せが列挙される。
【０１５２】
上記ステップ１７３の処理において、無向枝の組合せを削除するとタスクＴ１，Ｔ６を含む節点集合と、タスクＴ２，Ｔ４，Ｔ７を含む節点集合と、タスクＴ５，Ｔ８を含む節点集合と、タスクＴ３，Ｔ９を含む節点集合が得られる。各節点集合に含まれるタスクの実行時間の総和は上限と下限を満たすので、タスクＴ１，Ｔ６がプロセッサ１に割り当てられ、タスクＴ２，Ｔ４，Ｔ７がプロセッサ２に割り当てられ、タスクＴ５，Ｔ８がプロセッサ３に割り当てられ、タスクＴ３，Ｔ９がプロセッサ４に割り当てられる。
【０１５３】
実施の形態３によれば、重みの総和の小さい順に複数の無向枝についての組合せが列挙されるので、上記の実用的な時間内でタスク割り当てを求めることができる。
【０１５４】
＜実施の形態４＞
図１３には、図７に示されるソフトウェア開発装置７００における主要機能が示される。
【０１５５】
図１３に示される主要機能が、図８に示されるのと大きく相違するのは、プロセッサ間通信速度に代えて、タスク実行時間閾値がタスク割り当て手段２０２に入力されている点である。タスク割り当て手段２０２におけるタスク割り当てにおいてタスク実行時間閾値が考慮される。
【０１５６】
次に、タスク割り当ての手順について説明する。
【０１５７】
図１８には、図１３に示される主要機能によって行われるタスク割り当ての流れが示される。
【０１５８】
先ず、無閉路有向グラフの作成、無向連結木の作成が行われる（１６１）が、これは、図１５におけるステップ１５１，１５２と同じであるため、ここではそれについての詳細な説明を省略する。
【０１５９】
次に、上記ステップ１６１で得られた無向連結木において、実行時間に関する閾値を超えないタスクを表す節点が選ばれる（１８２）。タスク実行時間に関する閾値は、実行時間をもとにタスクを選別するための基準値を表す。
【０１６０】
次に、上記ステップ１８２で選ばれた節点に接続される無向枝のうち、重みの最も大きい無向枝に接続される節点を選び、当該節点と上記ステップ１８２で選ばれた節点とが併合される（１８３）。
【０１６１】
そして、全ての節点を探索したか否かの判別が行われる（１８４）。この判別において、全ての節点を探索したと判断された場合には、本フローチャートに従う処理が終了される。しかし、上記ステップ１８４の判別において、全ての節点を探索していないと判断された場合には、上記ステップ１８２の処理に戻される。
【０１６２】
図１４は、節点併合無向連結木が示される。この節点併合無向連結木は、図５に示した無向連結木を構成する節点を併合したものである。
【０１６３】
ここで、上記ステップ１８２，１８３の処理を実施することにより、図５におけるステップ１５１，１５２の処理で得られた無向連結木を構成する節点を併合する様子について具体的に説明する。
【０１６４】
尚、タスク実行時間閾値は１５とする。
【０１６５】
ステップ１８２の処理において、上記ステップ１５２の処理で得られた無向連結木を構成する節点のうち、タスク実行時間閾値を超えないタスクＴ７を表す節点が選ばれる。次に、上記ステップ１８３の処理において、タスクＴ７を表す節点に接続される無向枝のうち、重みの最も大きい無向枝はタスクＴ５に接続される無向枝であるので、タスクＴ５を表す節点が選ばれる。そしてタスクＴ７とタスクＴ５とが併合されることにより、図１４に示される節点併合無向連結木が得られる。
【０１６６】
このように実施の形態４によれば、無向連結木を構成する節点と無向枝が減少するので、実用的な時間内でタスク割り当てを求めることができる。
【０１６７】
以上本発明者によってなされた発明を実施形態に基づいて具体的に説明したが、本発明はそれに限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは言うまでもない。
【符号の説明】
【０１６８】
７１  メモリ
７２  ＣＰＵ
７３  ハードディスク
７４  外部インタフェース
１０１  プロセッサ
１０２  共有メモリ
１０３  ルータ
１０４  局所メモリ
２０１  タスク解析手段
２０２  タスク割り当て手段
２０３  実行時刻決定手段
７００  ソフトウェア開発装置
７０１  コンピュータ
７０２  ディスプレイ
７０３  キーボード
７０４  マウス
７０５  ディスクドライブ
７０６  磁気ディスク又は光ディスク
【図１】
2011003122.tif 000005
【図２】
2011003122.tif 000006
【図３】
2011003122.tif 000007
【図４】
2011003122.tif 000008
【図５】
2011003122.tif 000009
【図６】
2011003122.tif 000010
【図７】
2011003122.tif 000011
【図８】
2011003122.tif 000012
【図９】
2011003122.tif 000013
【図１０】
2011003122.tif 000014
【図１１】
2011003122.tif 000015
【図１２】
2011003122.tif 000016
【図１３】
2011003122.tif 000017
【図１４】
2011003122.tif 000018
【図１５】
2011003122.tif 000019
【図１６】
2011003122.tif 000020
【図１７】
2011003122.tif 000021
【図１８】
2011003122.tif 000022