JPH0612395A - マルチプロセサシステムにおけるタスク割り付け方法 - Google Patents

Abstract

(57)【要約】 【目的】 マルチプロセサシステムにおいて、発生した
タスクをプロセサに割り付ける際にプロセサによる処理
効率が良い様に割り付けるプロセサを決定する。 【構成】 ＣＰＵ８が処理を行っている際、キャッシュ
メモリ９にアクセスすると、アクセスカウンタ１０によ
りアクセスの発生した回数が数えられる。また、発生し
たアクセスのうちで、所望の情報がキャッシュメモリ９
内に存在していた回数をヒットカウンタ１１で数える。
アクセスカウンタ及びヒットカウンタの値から、キャッ
シュメモリ９に所望の情報があった割合を求める。以上
の手順をシステムを構成するＣＰＵすべてについて行
い、前記割合の最も低いＣＰＵに新たに発生したタスク
を割り付ける。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、例えばＣＰＵの動作状
態を考慮してタスクの割り付けを行なうマルチプロセサ
システムに関するものである。

【０００２】

【従来の技術】従来、複数のＣＰＵを有するコンピユー
タシステム（以下マルチプロセサシステムと呼ぶ）で
は、１つのマスタとなるＣＰＵとそれに従属するスレー
ブのＣＰＵとから構成されている場合には、各ＣＰＵの
処理内容が決められていた。また、各ＣＰＵが同格の場
合には、空いているＣＰＵがあれば新たに実行すべきタ
スクをそこに割り付けていた。このとき、もし全ＣＰＵ
が処理中であれば、新規に処理すべきタスクの優先順位
と実行中のタスクの優先順位との比較結果から実行タス
クを切り替えたり、比較したタスクの優先順位が同じ場
合には、強制的にいずれかのＣＰＵに割り当て、タイム
シェア方式により複数のタスクを切り替えながら実行す
る様に構成されていた。

【０００３】

【発明が解決しようとする課題】しかしながら、上記従
来例のマスタスレーブ構成のマルチプロセサシステムで
は、あるタスクを実行する場合に、処理内容によるＣＰ
Ｕの割り当てのために、空いているＣＰＵがあったとし
ても、必ず特定のＣＰＵで実行せねばならないことがあ
る。例えばインタラプト処理のようなタスクの場合に
は、スレーブＣＰＵが空いていても必ずマスタＣＰＵで
処理せねばならず、マスタＣＰＵの負荷が増して、シス
テム全体のスループットが落ちると言う欠点があった。

【０００４】一方、各ＣＰＵが同格なマルチプロセサシ
ステムにおいて、全ＣＰＵが処理を行なっている時に別
のタスクの実行を新たに要求された場合には、実行中の
タスクの優先順位と新規のタスクの優先順位とが同じで
あると、例えば各ＣＰＵについているデバイス番号の順
序といった所定の規則に従ってＣＰＵを割り当てる。新
規のタスクは割り当てられたＣＰＵ上で既に実行してい
るタスクとタイムシェアして実行される。このため、Ｃ
ＰＵの動作状態に関係なく割り当ててしまい、タイムシ
ェア方式によるタスク制御を行なうので、新規タスクの
ＣＰＵへの割り付けは処理効率についての考慮がなく、
非効率的な割り当てがなされる得るという欠点があっ
た。

【０００５】本発明は上記従来例に鑑みてなされたもの
で、ＣＰＵの動作状態を参照して、ＣＰＵを効率よく使
用できる様にタスクの割りつけを決定できるタスク割り
付け方法を提供することを目的とする。

【０００６】

【課題を解決するための手段】上記目的を達成するため
に、本発明のマルチプロセサシステムにおけるタスク割
り付け方法は次のような構成からなる。

【０００７】システムを構成するプロセサ各々について
対となるキャッシュ記憶を備えたマルチプロセサシステ
ムにおいて発生したタスクを前記プロセサに割りつける
タスク割り付け方法であって、前記各プロセサが、前記
対となるキャッシュ記憶へアクセスした回数を数える第
１の計数行程と、前記アクセスにより所望される情報
が、前記対となるキャッシュ記憶に存在している回数を
数える第２の計数行程と、前記第１の計数工程による回
数と前記第２の計数行程による回数とを基に、所望の情
報がキャッシュ記憶に存在しているヒット率を算出する
算出行程と、前記ヒット率を基に前記発生したタスクを
実行するプロセサを選択する選択行程とを備える。

【０００８】

【作用】上記構成により、マルチプロセサシステムを構
成する各プロセサがキャッシュメモリをアクセスした際
の、所望の情報がキャッシュメモリ上に存在している率
を算出し、新たに発生したタスクを割りつけるプロセサ
をその率に応じて決定する。

【０００９】

【実施例】

［実施例１］本発明の第１の実施例の構成を図１に示
す。本実施例では、説明を簡単にするために、ＣＰＵ部
を２個持ったマルチプロセサシステムを説明する。

【００１０】＜構成＞図中１はシステム内のＣＰＵやメ
モリ等の資源を接続するためのシステムバスであり、２
はＣＰＵ部Ａ、３はＣＰＵ部Ｂである。４は各ＣＰＵ部
から共通にアクセスできるメモリ部、５はコマンド等を
入力するためのキーボード、６は同じく入力のためのマ
ウス、７はプログラムやデータを格納するためのディス
ク、１５は表示部である。ＣＰＵ部ＡとＣＰＵ部Ｂとは
同じ構成をしており、図中、同じ構成要素には同じ番号
をつけてある。ＣＰＵ部Ａについてその構成を説明す
る。

【００１１】ＣＰＵ部Ａは、ＣＰＵ８と、メモリアクセ
スを高速に行なうためにＣＰＵ８のローカルなデータを
格納しておくキャッシュメモリ９と、ＣＰＵ８からのメ
モリアクセス信号１６によってキャッシュメモリへのア
クセス回数をカウントするアクセスカウンタ１０と、Ｃ
ＰＵ８からのメモリアクセス要求に対してキャッシュメ
モリ９内に該当データがあったことを意味するヒット信
号１２をとり、キャッシュ・ヒット回数をカウントする
ヒットカウンタ１１とから構成される。カウンタ１０の
値とカウンタ１１の値とはシステムバス１上にマッピン
グされ、各ＣＰＵからアクセスできる様にされている。
キャッシュメモリ９は、ＣＰＵ８からのメモリアクセス
要求に対してデータが存在していればヒット信号１２を
出し、その値をＣＰＵ１に出力する。もし存在していな
ければキャッシュメモリ９はヒット信号１２を出さず、
メモリ４またはディスク７から該当するデータをキャッ
シュメモリ９にローディングし、ＣＰＵ８に求められた
データを返す。またアクセスカウンタ１０とヒットカウ
ンタ１１とは、ＣＰＵに新しいタスクを割り付けた時に
共に０にクリアされ、図示していない各ＣＰＵ部のタイ
マ等の手段により、所定時間経過ごとに０クリアされ
る。

【００１２】＜タスクの割り付け＞以上のような構成の
マルチプロセサシステムにおいて、ＣＰＵ部Ａでタスク
Ａが、ＣＰＵ部ＢでタスクＢが実行されている時に、キ
ーボード５やマウス６からの入力でユーザが要求によ
り、あるいは、図示しない外部からの割込みにより新た
にタスクＣを実行しなければならない場合を考える。

【００１３】図２にタスクＡとタスクＢの各カウンタの
変化例を示す。図２によれば、２０は、時刻ｔ₁ におけ
るＣＰＵ部Ａのアクセスカウンタ１０が１００、ヒット
カウンタ１１が５０であることを示し、ヒット率は５０
／１００＝５０％であることが分かる。同様にＣＰＵ部
Ｂのヒット率は５０／１５０≒３３％である。更に時間
が経過し、新たなタスクＣの実行要求が発生した時の処
理を、図６のフローチャートを参照して説明する。

【００１４】時刻ｔ₂ にタスクＣの実行要求が発生する
と、まずその時点で遊んでいるＣＰＵの有無をテスト
し、空いているＣＰＵがあればそのＣＰＵで新たに発生
したタスクを実行する。すべてのＣＰＵ（この場合ＣＰ
Ｕ部ＡとＣＰＵ部Ｂ）で何らかのタスクが処理されてい
るなら、それらの中から最適なＣＰＵを選び出さねばな
らない。

【００１５】まず、ＣＰＵ部ＡのＣＰＵ８がアクセスカ
ウンタ１０とヒットカウンタ１１の値を読み（Ｓ６０１
・Ｓ６０２）、ヒット率を計算する（Ｓ６０３）。ＣＰ
Ｕ部Ａでのキャッシュ・ヒット率は表より１５０／２０
０＝７５％となる。この値はキャッシュメモリ９に格納
しておき、次にＣＰＵ部Ｂについてヒット率を計算する
（Ｓ６０４−ＮＯ）。ＣＰＵ部Ａと同じ要領で計算する
と、ＣＰＵ部２のキャッシュヒット率は２７０／３００
＝９０％となり、これもキャッシュメモリ９に格納して
おく。これですべてのＣＰＵについてヒット率の計算が
済んだ（Ｓ６０４−ＹＥＳ）。次に各ＣＰＵ部のヒット
率７５％と９０％とを比較し、小さいヒット率の方を新
規タスクを割り当てるＣＰＵと決定する（Ｓ６０５）。
最後に小さいヒット率のＣＰＵすなわちＣＰＵ部Ａにタ
スクＣを割り付ける（Ｓ６０６）。これは、キャッシュ
ヒット率の高い方では、キャッシュメモリへの外部の記
憶装置からの読み込みが少なく、より高い効率でＣＰＵ
が稼働している。一方ヒット率の低い方ではキャッシュ
メモリへの外部記憶からのロードがより頻繁であるた
め、複数のタスクをタイムシェアして実行する際のオー
バーヘッドがヒット率のより高いものほどには全体の処
理効率に影響を与えない。このため、高効率の方を優先
して処理を進められるように、ヒット率の低いＣＰＵへ
と新たなタスクを割りつける。

【００１６】これにより、ＣＰＵ部ＡはタスクＡとタス
クＣを各タスクの優先順位によりタイムシェア方式によ
り実行し、ＣＰＵ部ＢはそのままタスクＢを実行する。

【００１７】

【他の実施例】第１の実施例では、各ＣＰＵ部がタスク
を１つずつ実行している場合を説明したが、本実施例で
は、各ＣＰＵ部が既に複数のタスクを実行している場合
を考えてみる。この場合には、ＣＰＵ部ＡでタスクＡと
タスクＢとが、ＣＰＵ部ＢでタスクＣとタスクＤとが実
行されているものとし、ここにタスクＥの実行要求が発
生した場合を説明する。

【００１８】［実施例２］第２の実施例では、各ＣＰＵ
部で現在いくつのタスクが実行中であるかを意識しない
で、各ＰＣＵ部ごとのキャッシュ・ヒット率に従って、
どのＣＰＵにタスクＥを割り付けるかを決定する方法を
説明する。この場合は、第１の実施例と同様に、図３の
表に示す様に各ＣＰＵ部毎のメモリアクセス回数と、キ
ャッシュ・ヒット回数とを図１に示す構成で記憶してい
けば良く、またタスクを割りつけるＣＰＵ部を決定する
方法も第１の実施例に示した方式で決定すれば良い。

【００１９】図３ではＣＰＵ部ＡとＣＰＵ部Ｂとについ
てアクセスカウンタとヒットカウンタとが記録されてお
り、ヒット率は実施例１と同じ手順で導くことができ、
タスクの割り付け先はＣＰＵ部Ａと決まる。

【００２０】［実施例３］第３の実施例では、各タスク
毎のキャッシュ・ヒット率を計算し、それから新しいタ
スクをどのＣＰＵ部に割り付けるかの方法を説明する。
図４に本実施例の構成図を示す。図４中で図１と同じ動
作をする構成要素には同じ番号をつけてある。３０のカ
ウンタ制御部は、各ＣＰＵ部にあるメモリアクセス回数
用カウンタであるアクセスカウンタ１０と、キャッシュ
・ヒットの回数用カウンタであるヒットカウンタ１１と
から出力されるカウント情報を各々信号線３３・信号線
３４から入力し、各ＣＰＵ部のカウント情報を記憶す
る。さらに各ＣＰＵから、各ＣＰＵで実行タスクを切り
替えたことを知らせる信号３５も入力する。カウンタメ
モリ３２は、各ＣＰＵで実行中の全タスクのメモリアク
セス回数とキャッシュヒット回数を蓄積するためのメモ
リである。

【００２１】以下、詳細な説明をするが、説明のため、
ｕｎｉｘ等のＯＳで用いられているタスクを識別するた
めのユニークな識別子（以下タスクＩＤと呼ぶ）を用い
てタスクを識別する。実行中の４タスクについて、タス
クＡは１００、タスクＢは１０２、タスクＣは１０１、
タスクＤは１０３とする。カウンタコントローラ３１
は、システム起動時にはすべてのＣＰＵについて、各Ｃ
ＰＵからカウンタ情報が入力された時にはそのＣＰＵに
ついて、アクセスカウンタ１０、ヒットカウンタ１１を
０クリアする。タスクＡがＣＰＵ１で実行され、所定時
間経過すると、ＣＰＵ１はカウンタコントローラ３１に
対して自分のＣＰＵ番号と実行中のタスクＩＤ、カウン
ト情報であるアクセスカウンタ１０とヒットカウンタ１
１の値を送る。タスクＢ・Ｃ・Ｄについても同様な処理
を行う。そうすると、カウンタコントローラ３１は、カ
ウンタメモリ３２上に図５に示すような、或る時刻にお
けるカウンタを記録したテーブル情報を作成する。図４
のアクセスカウンタ１０、ヒットカウンタ１１のフィー
ルドの意味は第１の実施例と同じである。ここで図４の
状態で、タスクＥの実行要求が発生したとする。そうす
ると、カウンタコントローラは各タスク毎にキャッシュ
・ヒット率を計算する。すなわち、 タスク１００： ６０／１００＝６０％ … ＣＰＵ部
Ａ タスク１０２：１４０／２００＝７０％ … ＣＰＵ部
Ａ タスク１０１：２４０／３００＝８０％ … ＣＰＵ部
Ｂ タスク１０３： ６０／２００＝３０％ … ＣＰＵ部
Ｂ を求める。ここで、４つのキャッシュ・ヒット率の中で
１番高いもの、この場合タスク１０１の８０％を見つ
け、効率の良いタスクを先に実行するという観点から、
タスク１０１はＣＰＵ部Ｂで実行しているので、ＣＰＵ
部ＡにタスクＥを割り付ける旨を判断し、タスクＥをＣ
ＰＵ部Ａに割り付ける。これは、実施例１の手順をＣＰ
Ｕ単位からタスク単位へと変更したものである。従っ
て、図６のフローチャートのステップＳ６０５を「ヒッ
ト率の高いタスクを実行しているＣＰＵを順に除外し
て、最後に残ったＣＰＵを選ぶ」とすれば、本実施例の
適用できる。

【００２２】こうして実現されたタスク割り付け方法で
は、各ＣＰＵが実行中のタスクの実行状態として、ＣＰ
Ｕとキャッシュ間のキャッシュ・ヒット率をモニタする
手順を設けることにより、別タスクの実行要求が発生し
た時に、各ＣＰＵで実行中のタスクの優先順位が同じ場
合には、キャッシュ・ヒット率の一番低いＣＰＵに今回
のタスクを割り付けることに、キャッシュ・ヒット率の
高いタスクはそのまま高速に処理を続けることができ、
キャッシュ・ヒット率の低いＣＰＵでタイムシェア方式
等により処理することにより、このキャッシュ・ヒット
率の低いタスクは、もともとキャッシュメモリにあまり
ヒットしないメモリ・アクセスをしているためにタスク
スイッチによるキャッシュ・ヒット率の低下が少なく、
効率良くＣＰＵ等の資源を割り付けができる。また、キ
ャッシュ・ヒット率を求めるためのハード規模も小さく
すむ。

【００２３】これまでの説明では、ＣＰＵのタイマ等に
より所定の単位時間を測定し、その単位時間内のキャッ
シュ・ヒット率を計算する様に説明してきたが、そのタ
スクの開始から終了まで通したキャッシュ・ヒット率を
求める方式でも良い。例えば、大容量の画像データを順
次処理して行くようなタスクの場合には、そのタスク全
体としてみればキャッシュ・ヒット率は小さいものと考
えられるし、また元々時間のかかる処理であるため、他
のタスクとタイムシェアして実行しても構わない。

【００２４】さらに、キャッシュ・ヒット率を第１・第
２の実施例ではＣＰＵ部Ａ２で、第３の実施例ではカウ
ンタ制御部３０で求めていたが、これに限るものでもな
い。

【００２５】また、これまでの実施例の説明ではＣＰＵ
部は２個で説明したが、これに限るものでもなく、更に
多くのＣＰＵを持った装置であっても良い。また、各Ｃ
ＰＵ上で実行しているタスク数が同じ場合を説明した
が、これに限るものでもなく、空いているＣＰＵがあれ
ば、そのＣＰＵに割り付けたりすることは容易に考えら
れる。また、これまではキャッシュ・ヒット率の高いタ
スクを優先的に実行する様に説明したが、これに限るも
のでもなく、キャッシュが余りヒットしないタスクは時
間がかかるためにそれを優先して実行するという、これ
まで説明した実施例とは逆の制御方式も容易に考えられ
る。

【００２６】尚、本発明は、複数の機器から構成される
システムに適用しても１つの機器から成る装置に適用し
ても良い。また、本発明は、システム或は装置にプログ
ラムを供給することによって達成される場合にも適用で
きることはいうまでもない。

【００２７】

【発明の効果】以上説明した様に本発明に係るタスク割
り付け方法は、ＣＰＵの動作状態を参照して、ＣＰＵを
効率よく使用できる様にタスクの割りつけを決定でき
る。

【図面の簡単な説明】

【図１】第１の実施例のブロック図である。

【図２】第１の実施例のキャッシュヒット率を算出する
ための表である。

【図３】第２の実施例のキャッシュヒット率を算出する
ための表である。

【図４】第３の実施例のブロック図である。

【図５】第３の実施例のキャッシュヒット率を算出する
ための表である。

【図６】第１の実施例のフローチャートである。

Claims (7)

【特許請求の範囲】
1. 【請求項１】 システムを構成するプロセサ各々につい
   て対となるキャッシュ記憶を備えたマルチプロセサシス
   テムにおいて発生したタスクを前記プロセサに割りつけ
   るタスク割り付け方法であって、 前記各プロセサが、前記対となるキャッシュ記憶へアク
   セスした回数を数える第１の計数行程と、 前記アクセスにより所望される情報が、前記対となるキ
   ャッシュ記憶に存在している回数を数える第２の計数行
   程と、 前記第１の計数工程による回数と前記第２の計数行程に
   よる回数とを基に、所望の情報がキャッシュ記憶に存在
   しているヒット率を算出する算出行程と、 前記ヒット率を基に前記発生したタスクを実行するプロ
   セサを選択する選択行程と、 を備えることを特徴とするタスク割り付け方法。
2. 【請求項２】 前記算出行程はタスクごとに前記ヒット
   率を算出することを特徴とする請求項１項記載のタスク
   割り付け方法。
3. 【請求項３】 前記選択行程は、前記各プロセサにおい
   て前記ヒット率の最も高いタスクのうち、前記ヒット率
   が最も低いタスクを実行するプロセサを選択することを
   特徴とする請求項２項記載のタスク割り付け方法。
4. 【請求項４】 前記算出行程はプロセサごとに前記ヒッ
   ト率を算出することを特徴とする請求項１項記載のタス
   ク割り付け方法。
5. 【請求項５】 前記選択行程は前記ヒット率が最も低い
   プロセサを選択することを特徴とする請求項４項記載の
   タスク割り付け方法。
6. 【請求項６】 前記ヒット率の算出はタスクの開始から
   終了までの時間内のアクセスを対象としてなされること
   を特徴とする請求項１項記載のタスク割り付け方法。
7. 【請求項７】 前記ヒット率の算出は適当に選ばれた一
   定の時間内のアクセスを対象としてなされることを特徴
   とする請求項１項記載のタスク割り付け方法。