(57)【要約】【課題】本発明の目的は、マルチ・プロセッサ・システムのスループットを最大化するためのプログラムおよびディスパッチ方法を提供することにある。【解決手段】本発明のプログラムは、マルチ・プロセッサ・システム４０を、複数のプロセッサ２８にそれぞれプロセス３８のスレッドを割り当てるたときのプロセス３８の処理効率を判定する判定手段１２、判定手段１２の結果に基づいて、プロセス３８を１つのプロセッサ２６または複数のプロセッサ３８で実行させるかを選択する選択手段１４、として機能させるためのプログラムである。【選択図】　　図１
2004133753.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサを含むマルチ・プロセッサ・システムで実行されるプロセスのスレッドをディスパッチするプログラムであって、
前記マルチ・プロセッサ・システムを、
前記複数のプロセッサにそれぞれプロセスのスレッドを割り当てるときの該プロセスの処理効率を判定する手段、
前記判定する手段の結果に基づいて、前記プロセスを１つのプロセッサまたは複数のプロセッサで実行させることを選択する手段、
として機能させるためのプログラム。
【請求項２】
前記判定する手段が、
前記プロセスの実行時間をプロセッサでの処理の時間およびＩ／Ｏ待ちの時間とに分割する手段と、
前記処理の時間とＩ／Ｏ待ちの時間との長さを比較する手段と、
を含む請求項１に記載のプログラム。
【請求項３】
前記１つのプロセッサで実行されているプロセスが処理するデータに他のプロセッサからアクセスするとき、該アクセスを該１つのプロセッサでおこなうように変更する手段を含む請求項１または２に記載のプログラム。
【請求項４】
前記１つのプロセッサで実行されているプロセスが処理するデータに対して、該１つのプロセッサが該データの読み書きをおこない、前記他のプロセッサに対して該データの読み書きを禁止する手段を含む請求項３に記載のプログラム。
【請求項５】
複数のプロセッサを含むマルチ・プロセッサ・システムで実行されるプロセスのスレッドをディスパッチする方法であって、
前記複数のプロセッサにそれぞれプロセスのスレッドを割り当てたときの該プロセスの処理効率を判定するステップと、
前記プロセスを１つのプロセッサまたは複数のプロセッサで実行させるかを選択するステップと、
を含むディスパッチ方法。
【請求項６】
前記判定するステップが、
前記プロセスの実行時間をプロセッサでの処理の時間およびＩ／Ｏ待ちの時間とに分割するステップと、
前記処理の時間とＩ／Ｏ待ちの時間とを比較するステップと、
を含む請求項５に記載のディスパッチ方法。
【請求項７】
前記比較するステップにおいてＩ／Ｏ待ちの時間が処理の時間よりも多く、前記選択するステップにおいて１つのプロセッサでの実行を選択する請求項６に記載のディスパッチ方法。
【請求項８】
前記マルチ・プロセッサ・システムのオペレーティング・システムがマルチ・スレッド・プログラムを含み、
該マルチ・プロセッサ・システムで実行される応用プログラムがシングル・スレッド・プログラムを含み、
前記選択するステップにおいて、１つのプロセッサでの実行を選択する請求項５に記載のディスパッチ方法。
【請求項９】
前記判定するステップで、複数のプロセスにおいて個々のプロセスが複数のプロセッサでの実行が適していると判定し、
前記選択するステップが、該複数のプロセスの実行において１つのプロセッサでの実行を選択する請求項５に記載のディスパッチ方法。
【請求項１０】
前記１つのプロセッサで実行されているプロセスが処理するデータに他のプロセッサからアクセスするとき、該アクセスを該１つのプロセッサに変更するステップを含む請求項５乃至９に記載のディスパッチ方法。
【請求項１１】
前記１つのプロセッサで実行されているプロセスが処理するデータに対して、該１つのプロセッサが該データの読み書きをおこない、前記他のプロセッサに対して該データの読み書きを禁止するステップを含む請求項１０に記載のディスパッチ方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチ・プロセッサ・システムで複数のプロセス（またはプログラムと言う）のスレッドをディスパッチするためのプログラムおよびディスパッチ方法に関する。
【０００２】
【従来の技術】
従来、マルチ・スレッド・プログラムの実行環境として、マルチ・プロセッサ・システムはＷＥＢサーバの応用で特に成功を収めている。この場合、システムで実行されるプロセスは、プロキシやファイアーウォールなどのサーバ・プログラムである。分散処理をおこなう場合、１つのシステムで１つのサーバ・プログラムが実行されることもしばしばである。
【０００３】
ＷＥＢサーバのマルチ・スレッド・プログラムは、非同期な複数のクライアントからのリクエストに応じて、ジョブの生成・消滅を繰り返す。これに対してＣＰＵ（ｃｅｎｔｒａｌ　ｐｒｏｃｅｓｓｉｎｇ　ｕｎｉｔ）サーバあるいはＣＰＵ　Ｆａｒｍと呼ばれるサーバ用途では、性質の異なる複数のプログラム、例えば計算やＣＡＤ（ｃｏｍｐｕｔｅｒ　ａｉｄｅｄ　ｄｅｓｉｇｎ）などが実行される。
【０００４】
マルチ・スレッド・プログラムを含むプロセスを１つ実行する場合、割り当て可能なプロセッサにプロセスのスレッドを全て割り当てることが最もプロセスの実行速度を高める。しかし、複数のプロセスが存在する場合、システムのスループットを最適化する方法でスレッドの割り当てをおこなう必要がある。
【０００５】
例えば、８個のプロセスを同時に処理できるマルチ・プロセッサ・システムで、独立な８個のプロセスを実行する場合、１個のプロセスを処理するシングル・プロセッサ８台で実行したときと比較してスループットが著しく劣ることがある。これは、ユーザ空間の共有の結果生じた競合が効率を落とす原因と考えられている。
【０００６】
マルチ・スレッド・プログラムは、スレッドの切り替えがプログラムの切り替えと比較して高速である。さらに異なるスレッド間で同じユーザ空間を共有しているため、スレッド間でのデータの受け渡しがポインタ渡しにできる。したがって、スレッド間のデータの受け渡しはコピー操作の必要なプログラム間のデータの受け渡しに比べて高速である。マルチ・スレッド・プログラムをマルチ・プロセッサ・システムで実行する場合、システムはキャッシュ・コヒーレントな共有メモリを有することが望ましい。なぜなら、異なるプロセッサで実行中のスレッド同士でデータの受け渡しをポインタ渡しでおこなうとき、ハードウェア・レベルでコピー操作が発生しないからである。
【０００７】
マルチ・プロセッサ・システムは、マルチ・スレッド・プログラムの実行に最適化された結果、ハードウェア・レベルでのキャッシュ・コヒーレンシなサポートを加えられている。キャッシュ・コヒーレンシをハードウェアでサポートすることは、頻繁に起きるスレッド間のデータの受け渡し、すなわちスレッド間の通信に適している。
【０００８】
しかし、スレッド間通信の頻度の低い独立したプログラム間でのデータの受け渡しに備えて、常にキャッシュ・コヒーレンシ・プロトコルを用いたデータ・アクセスを用いると、速度面で不要な処理が多くなる。ＣＣ−ＮＵＭＡ（ｃａｃｈｅ　ｃｏｈｅｒｅｎｃｅ−ｎｏｎ　ｕｎｉｆｏｒｍ　ｍｅｍｏｒｙ　ａｃｃｅｓｓ）型マルチ・プロセッサ・システムの例では、Ｌ２（レベル２）キャッシュ・ミスをした場合、ソフトウェアの介在なしに、データの所属するメモリを管理するホーム・ノードに属するタグ・メモリがアクセスされ、最新のデータを保持しているオーナ・ノードが自動的に照会される。また、スヌープ・キャッシュを用いた場合、常にアドレスを全キャッシュにブロードキャストする必要があるため、アドレスバスが１セットしかないと、スヌープを必要とするメモリ・アクセスを同時に複数発生させることができない。なお、タグ・メモリは、データをキャッシュしている状態を管理するメモリである。スヌープ・キャッシュは、コヒーレンシをハードウェアで自動管理するために使用するメモリである。Ｌ２キャッシュ・ミスは、キャッシュ・メモリが２層構造であり、１層に次いで２層でもキャッシュ・ミスをすることを言う。
【０００９】
したがって、キャッシュ・コヒーレンシのハードウェアでのサポートは、マルチ・スレッド・プログラムを効率よくサポートするために適しているが、独立した複数のプログラムを実行する場合には却って不要なサポートである。
【００１０】
【発明が解決しようとする課題】
本発明の目的は、マルチ・プロセッサ・システムで複数のプログラムを実行する場合、システムのスループットを最大化するように制御するプログラムおよびディスパッチ方法を提供することにある。
【００１１】
【課題を解決するための手段】
本発明のプログラムの要旨は、複数のプロセッサを含むマルチ・プロセッサ・システムで実行されるプロセスのスレッドをディスパッチするプログラムであって、前記マルチ・プロセッサ・システムを、前記複数のプロセッサにそれぞれプロセスのスレッドを割り当てたときの該プロセスの処理効率を判定する手段、前記判定する手段の結果に基づいて、前記プロセスを１つのプロセッサまたは複数のプロセッサで実行させるかを選択する手段、として機能させるためのプログラムである。
【００１２】
本発明のディスパッチ方法の要旨は、複数のプロセッサを含むマルチ・プロセッサ・システムで実行されるプロセスのスレッドをディスパッチする方法であって、前記複数のプロセッサにそれぞれプロセスのスレッドを割り当てたときの該プロセスの処理効率を判定するステップと、前記プロセスを１つのプロセッサまたは複数のプロセッサで実行させるかを選択するステップと、を含む。
【００１３】
【発明の実施の形態】
本発明のプログラムおよびディスパッチ方法の実施の形態について図面を用いて説明する。なお、本明細書、図面１、２および４において、符号３８は、符号３８ａ，３８ｂ，Ｐ１，Ｐ２，Ｐ３を総括的に示す。
【００１４】
本発明のプログラムは、図１に示すスレッドのディスパッチをおこなうプログラムである。言い換えると、本発明は、マルチ・プロセッサ・システムにおけるオペレーティング・システムのスケジューラの発明である。先ず、システムのスループットを最大化するための方法を説明する。
【００１５】
図２は、オペレーティング・システム３２とプロセス３８を表したものである。Ｔ０からＴ４はプロセス３８のスレッドを示し、これらのスレッドＴ０，Ｔ１，Ｔ２，Ｔ３，Ｔ４の位置がマルチ・プロセッサ・システム４０における実行ポイントを示す。図２の例では、スレッドＴ０はスレッドＴ１，Ｔ２，Ｔ３，Ｔ４と同時実行可能なユーザ空間３６のスレッドである。スレッドＴ１はシステム・コールによってスレッドＴ２，Ｔ３へとサービスを受けた後、スレッドＴ４にリターンする。
【００１６】
なお、本明細書において、例えば図２のスレッドＴ０，Ｔ２，Ｔ３を異なるプロセッサに割り当てれば、最大３の並行度が得られるプロセス３８であっても、１つのプロセッサ（シングル・プロセッサ）に割り当てることを、シングル・プロセッサ実行状態にすると言う。
【００１７】
従来、例えばスレッドＴ０，Ｔ２，Ｔ３を異なるプロセッサにて並列実行する場合、データが共有されるため、キャッシュ・コヒーレンシ・プロトコルが必要である。スレッドＴ０からＴ４をシングル・プロセッサ実行する場合は、キャッシュ・コヒーレンシ・プロトコルは不要である。そこで、ユーザ空間３６のデータは、対応するページテーブルにてコヒーレンシ不要とマークする。なお、ページテーブルは、メモリの記憶域をページ単位で管理するための表であり、仮想アドレスと物理アドレスの対応関係が格納される。この表を用いてキャッシュ制御、キャッシュ・コヒーレンシ制御を管理することができる。また、ページは、プログラムを等しい長さに分割した場合の分割された各部分である。
【００１８】
キャッシュ・コヒーレンシ不要とマークする場合、例えば、図３のページテーブル４２では、ＷＩＭビット・フィールドにて指定する。マルチ・プロセッサ・システム４０に含まれるＭＭＵ（ｍｅｍｏｒｙ　ｍａｎａｇｅｍｅｎｔ　ｕｎｉｔ）の機能が働いて、このユーザ空間３６へのデータ・アクセスに関してハードウェア３０はキャッシュ・コヒーレンシ・プロトコルを発生しない。
【００１９】
ただし、このままでは他のプロセッサで実行されたプログラムとのデータ受け渡しの時に、キャッシュ・コヒーレンシが保たれない可能性がある。例えば、図２のスレッドＴ５が、図４のプロセッサｕＰ２にて実行されている場合に、スレッドＴ５がキャッシュ・コヒーレンシ不要としたプロセスを有するユーザ空間３６ａを参照した場合、キャッシュ・コヒーレンシが保たれなくなる。
【００２０】
上記の場合に、プロセッサへのディスパッチを変更して、スレッドＴ５も加えてシングル・プロセッサ実行状態にして、キャッシュ・コヒーレンシを保つ。ディスパッチを変更するイベントを発生するために、ＭＭＵのアシストを利用する。ページテーブル４２において、このユーザ空間３６を実行中の唯一のプロセッサからのみ読み書き可能とし、他のプロセッサからは読み書き不可能とする。スレッドＴ５に対しキャッシュ・コヒーレンシを破るデータの参照をおこなう前に割り込が発生し、スレッドＴ０，Ｔ１，Ｔ２，Ｔ３，Ｔ４と同じプロセッサへディスパッチさせる。
【００２１】
ページに対する読み書きの属性は、図３のページテーブル４２の例では、ＰＰビット・フィールドで指定することによって、キャッシュ・コヒーレンシ・プロトコルを省略することが可能となる。
【００２２】
ページテーブル４２に記録された読み書きの属性の内容が、プロセッサによって異なって見えるが、これは、ＤＳＭ（ｄｉｓｔｒｉｂｕｔｅｄ　ｓｈａｒｅｄ　ｍｅｍｏｒｙ）にてソフトウェア・キャッシュを実装する場合にも用いられる技術である。ＤＳＭのソフトウェア・キャッシュでは、ページ・フォルトを起こしたページをノード間で移動させることによってキャッシュ効果を得るのに対して、本発明では、ページ・フォルトを起こしたスレッドをノード間で移動させる点が異なる。なお、ページ・フォルトは、メモリに存在しないページに対するアクセスが起こったときに発生する割り込みである。
【００２３】
全てのプロセス３８をシングル・プロセッサ実行状態にしてしまうと、マルチ・プロセッサ・システム４０の意味が失われる。そこで、本発明のプログラムは、下記のような構成にし、シングル・プロセッサ実行状態にすべきプロセス３８を選択する。
【００２４】
図１に示す本発明のプログラム１０は、マルチ・プロセッサ・システム４０を、複数のプロセッサ（マルチ・プロセッサ）２８にそれぞれプロセス３８ａ，３８ｂのスレッドを割り当てたときのプロセス３８ａ，３８ｂの処理効率を判定する判定手段１２、判定手段１２の結果に基づいて、プロセス３８ａ，３８ｂをシングル・プロセッサ２６またはマルチ・プロセッサ２８で実行させるかを選択する選択手段１４、として機能させるためのプログラムである。
【００２５】
判定手段１２は、プロセス３８ａ，３８ｂの実行状態を観測する観測部１６と、プロセス３８ａ，３８ｂの処理効率を判定する判定部１８とを含む。観測部１６は、プロセス３８ａ，３８ｂの実行時間をプロセッサ２６，２８での処理の時間およびＩ／Ｏ（ｉｎｐｕｔ／ｏｕｔｐｕｔ）待ちの時間とに分割する分割手段（図示せず）と、処理の時間とＩ／Ｏ待ちの時間とを比較する比較手段（図示せず）と、を含む。比較手段の比較結果を用いて、判定部１８がプロセス３８ａ，３８ｂの処理効率を判定する。
【００２６】
選択手段１４は、メモリ管理部２０とタスク・ディスパッチャ２２とを含む。メモリ管理部２０は、メモリ２４にあるプロセス３８ａ，３８ｂに対して、キャッシュ・コヒーレンシをオンにするかオフにするかをおこなう。タスク・ディスパッチャ２２は、マルチ・プロセッサ実行かシングル・プロセッサ実行を選択する。
【００２７】
本発明は、判定手段１２と選択手段１４によって、シングル・プロセッサ２６で実行されているプロセス３８ａが処理するデータに他のプロセッサからのアクセスするとき、そのアクセスを中止し、そのアクセスを上記シングル・プロセッサ２６に変更する。すなわち、他のプロセッサからのアクセスに対して割り込みを発生させ、シングル・プロセッサ２６にそのアクセスを変更する。
【００２８】
本発明は、判定手段１２と選択手段１４によって、シングル・プロセッサ２６で実行されているプロセス３８ａが処理するデータに対して、シングル・プロセッサ２６がデータの読み書きをおこない、他のプロセッサに対してデータの読み書きを禁止する。
【００２９】
次に、上記のプログラム１０によるディスパッチ方法について説明する。プログラム１０は、マルチ・プロセッサ２８にそれぞれプロセス３８ａ，３８ｂのスレッドを割り当てたときの処理効率を判定し、シングル・プロセッサ実行またはマルチ・プロセッサ実行を選択する。
【００３０】
判定をおこなうとき、▲１▼Ｉ／Ｏバウンドが発生する処理の場合、ＣＰＵで消費されるわずかな時間でプロセスを並列処理したとしても、その効果は限られている。そこで、プロセス３８ａ，３８ｂの実行時間をプロセッサ２８での処理時間とＩ／Ｏ待ちの時間とに分割し、処理時間とＩ／Ｏ待ちの時間とを比較する。比較の結果、Ｉ／Ｏ待ちの時間の方が長い場合、シングル・プロセッサ実行する。図１ではプロセス３８ａがシングル・プロセッサ実行となっている。Ｉ／Ｏバウンドは、データの処理おいてハードディスク上の仮想記憶領域を使用すること、すなわちスワップファイルを生成することをいう。
【００３１】
▲２▼プログラム１０を含むオペレーティング・システム４２上で動作するアプリケーション・プログラムがシングル・スレッド・プログラムである場合もシングル・プロセッサ実行の候補となる。この場合は、オペレーティング・システム３２がマルチ・スレッド・プログラムであれば、アプリケーション・プログラムはマルチ・スレッド・プログラムのように振る舞う。しかし、Ｉ／Ｏバウンドの発生が予想されるため、オペレーティング・システム３２は、アプリケーション・プログラムがプロセス処理の並行性を持たない場合は、シングル・プロセッサ実行の候補とする。すなわち、本発明のプログラムは、上記の場合に、選択手段１４がシングル・プロセッサ実行を選択する。
【００３２】
▲３▼単独で実行されるときにマルチ・プロセッサ実行に適しているプロセス３８でも、複数のプロセス３８が実行される場合には処理効率が悪いという場合がある。この様な処理もシングル・プロセッサ実行の候補とする。すなわち、本発明のプログラム１０は、判定手段１２が個々のプロセス３８ａ，３８ｂにおけるマルチ・プロセッサ実行の処理効率を判定し、判定の結果が上記のような場合に、選択手段１４がシングル・プロセッサ実行を選択する。例えば、図１でプロセス３８ａがマルチ・プロセッサ実行に適していても、選択手段１４によってシングル・プロセッサ実行となる。
【００３３】
本発明のプログラム１０を有するマルチ・プロセッサ・システム４０において、マルチ・プロセッサ実行に適したマルチ・スレッド・プログラムを持つプロセス３８は、ハードウェア・レベルでのキャッシュ・コヒーレンシ・サポートを与えられたマルチ・プロセッサ２８にて並行処理する。
【００３４】
図４において、プロセスＰ３は２つのプロセッサｕＰ３，ｕＰ４で処理される。プロセッサｕＰ３，ｕＰ４で発生するデータ・アクセスは、キャッシュ・コヒーレンシ・プロトコルを発生する。
【００３５】
マルチ・プロセッサ実行に適さないプロセス３８は、シングル・プロセッサ実行され、他のプロセッサとのキャッシュ・コヒーレンシは、ＭＭＵのアシストなどを使ったソフトウェア制御方法のみ保たれる。図４のプロセスＰ１，Ｐ２をそれぞれ実行するプロセッサｕＰ１，ｕＰ２の発生するユーザ空間３６ａ，３６ｂに対するデータ・アクセスはキャッシュ・コヒーレンシ・プロトコルを発生しない。この結果、キャッシュ・コヒーレンシ・プロトコルのバンド幅は緩和され、システム４０のスループットは向上する。
【００３６】
キャッシュ・コヒーレンシ・プロトコルを発生しないため、プロセスＰ１に対して、プロセッサｕＰ２からのアクセスをおこなうとき、上記の割り込み手段がそのアクセスに対して割り込みを発生させる。そして、割り込みの発生後、プロセッサｕＰ２からプロセッサｕＰ１にスレッドを割り当てて、アクセスをおこなう。
【００３７】
また、ＭＭＵによって、あるプロセッサで実行されているプロセス３８が処理するデータに対して、そのプロセッサがデータの読み書きをおこない、他のプロセッサに対してデータの読み書きを禁止するようにシステム４０を制御する。
【００３８】
以上、本発明の実施の形態を説明したが、本発明は上記の形態に限定されることはない。上記の説明はキャッシュをＬ１（レベル１）キャッシュを前提に説明をおこなっており、シングル・プロセッサ実行状態とは、シングル・プロセッサでスレッドを実行することであった。同じアイデアをＬ２キャッシュに応用することができる。この場合、シングル・プロセッサ・ノード実行状態にする。シングル・プロセッサ・ノード実行状態とは、同じノードに属する複数のプロセッサが１つのプロセスに属する複数のタスクを処理する状態を言う。
【００３９】
キャッシュ・コヒーレンシ・プロトコルを省略する空間を、実装が容易で、効果の高いユーザ空間としたが、システム空間の一部に応用することは可能である。すなわち、システム空間の用途を分類し、分類された中でキャッシュ・コヒーレンシ・プロトコルを省略できる部分に適用する。
【００４０】
その他、本発明は、主旨を逸脱しない範囲で当業者の知識に基づき種々の改良、修正、変更を加えた態様で実施できるものである。
【００４１】
【発明の効果】
本発明によると、マルチ・プロセッサ・システムにおいて、プロセスのディスパッチを最適におこなうため、システムのスループットを下げることなく、全てのプロセスを処理することができる。
【図面の簡単な説明】
【図１】本発明のプログラムの構成およびディスパッチの様子を示す図である。
【図２】プロセスのスレッドの実行状態を示す図である。
【図３】キャッシュ・コヒーレンシを保つためのページテーブルの例を示す図である。
【図４】マルチ・プロセッサ・システムの例を示す図である。
【符号の説明】
１０：プログラム
１２：判定手段
１４：選択手段
１６：観測部
１８：判定部
２０：メモリ管理部
２２：タスク・ディスパッチャ
２４：メモリ
２６：シングル・プロセッサ
２８：マルチ・プロセッサ
３０：ハードウェア
３２：オペレーティング・システム
３４，３４ａ，３４ｂ，３４ｃ：システム空間
３６，３６ａ，３６ｂ，３６ｃ：ユーザ空間
３８：プロセス
４０：マルチ・プロセッサ・システム
４２：ページテーブル
【図１】
2004133753.tif 000003
【図２】
2004133753.tif 000004
【図３】
2004133753.tif 000005
【図４】
2004133753.tif 000006