Top > Search of Japanese Patents > (In Japanese)マルチスレッド中央演算装置および同時マルチスレッディング制御方法

(In Japanese)マルチスレッド中央演算装置および同時マルチスレッディング制御方法 meetings

Patent code P09S000296
Posted date Jan 22, 2010
Application number P2007-519071
Patent number P5145936
Date of filing Jun 1, 2006
Date of registration Dec 7, 2012
International application number JP2006311022
International publication number WO2006129767
Date of international filing Jun 1, 2006
Date of international publication Dec 7, 2006
Priority data
  • P2005-162549 (Jun 2, 2005) JP
  • P2005-167427 (Jun 7, 2005) JP
Inventor
  • (In Japanese)山崎 信行
Applicant
  • (In Japanese)学校法人慶應義塾
Title (In Japanese)マルチスレッド中央演算装置および同時マルチスレッディング制御方法 meetings
Abstract (In Japanese)
同時マルチスレッディングを行なうCPUによるスレッド実行時間の予測精度が向上される。CPU内で、各スレッドの優先度が設定され、原則として上位優先度のスレッドが下位優先度のスレッドより優先的に処理されるよう、複数スレッドの命令の処理順序/頻度が制御される。それにより、同時処理されるスレッド間の資源の競合が調停される。加えて、CPU内で各スレッドの実行命令数の目標値が設定され、一定周期で各スレッドの周期当たり実行命令数がカウントされ、そして、実行命令数と目標値との比較に基づくフィードバック制御動作により、優先度を用いた命令処理順序/頻度が修正される。それにより、どのようなスレッドの組み合わせで複数スレッドの同時処理が行われても、各スレッドの実行時間(またはIPC)が所望値近傍に安定して保たれる。
Outline of related art and contending technology (In Japanese)


実時間処理を行うリアルタイムシステムでは、各スレッドの時間制約を守るために、オペレーティングシステム(OS)のスケジューラは各スレッドの実行周期や時間制約により、各スレッドに優先度を付与する。そして、付与された優先度を基に、優先度の高いスレッドから順番に演算資源を割り当てて実行を行う。ここで、「スレッド」とは、プログラムの実行単位であり、通常、一つのアプリケーションプログラムは多数のスレッドから構成される。



図1に、一時に1スレッドのみを実行する従来のシングルスレッドプロセッサを用いて実時間処理を行った場合の例を示す。この例では、スレッド#0の優先度が最も高く、スレッド#7の優先度が最も低いとする。また、リリース時刻はそのスレッドが実行可能になる時刻、期限はそのスレッドの時間制約(その実行が完了されるべき最終期限)を示す。



図1に示された例では、最初にスレッド#1、スレッド#2およびスレッド#3が実行可能になる。これら実行可能なスレッド#1、#2および#3の中で最も優先度の高いスレッド#1にプロセッサ資源が与えられ、スレッド#1が実行される。スレッド#1の実行が完了すると、次に優先度の高いスレッド#2の実行を行うために、プロセッサ外のメモリとプロセッサとの間でコンテキストスイッチが起こる。コンテキストスイッチでは、現在実行しているスレッド#1のコンテキスト(すなわち、そのスレッドを実行するために必要なプロセッサ内のプログラムカウンタ、レジスタファイル、ステータスレジスタ等の各種資源)をプロセッサ外のメモリに退避させ、次に実行するスレッド#2のコンテキストをメモリからプロセッサ内に復帰させる。その後、プロセッサはスレッド#2の実行を開始する。スレッド#2の実行が完了すると、コンテキストスイッチが起こり、スレッド#2のコンテキストがメモリに退避し、スレッド#3のコンテキストがメモリからプロセッサ内に復帰した後、スレッド#3の実行が開始される。スレッド#3の実行中に、より優先度の高いスレッド#0が実行可能になると、スレッド#3の実行が中断され、コンテキストスイッチが起こり、スレッド#3のコンテキストがメモリに退避し、スレッド#0のコンテキストがプロセッサ内に復帰して、スレッド#0の実行が先に行われる。スレッド#0の実行が完了すると、コンテキストスイッチにより、スレッド#0のコンテキストがメモリに退避し、スレッド#3のコンテキストがプロセッサ内に復帰することにより、中断していたスレッド#3の実行が再開する。



このように従来のシングルスレッドプロセッサを用いた処理では、優先度の高いスレッドの実行が完了した場合や、現在実行しているスレッドよりもより優先度の高いスレッドが実行可能になった場合は、コンテキストスイッチが発生する。OSは、現在実行しているスレッドのコンテキストをメモリに退避し、次に実行するスレッドのコンテキストをプロセッサ内に復帰させなければならない。リアルタイムシステムでは、このコンテキストスイッチが大きなオーバヘッドとなる。一方、コンテキストスイッチのオーバヘッドを削減する技術として、プロセッサ内で複数のスレッドを並列処理するマルチスレッドプロセッサがある。マルチスレッドプロセッサは、プロセッサ内に複数スレッド分のコンテキストを保持し、これらをプロセッサ内のハードウェアで切り替えながらそれぞれのスレッドを実行するため、コンテキストスイッチを行わずに複数のスレッドを実行することが可能である(例えば、特許文献1参照)。



また、実時間処理に適したマルチスレッドプロセッサのスループット向上のための別の制御技術として、各スレッドに割り当てられた優先度に応じて、複数のスレッドの命令の実行順序をリザベーションステーションにて入れ替える技術が知られている(例えば、特許文献2参照)。




【特許文献1】特開2004-220070号公報

【特許文献2】特開2004-295195号公報

Field of industrial application (In Japanese)


本発明は、一般的には中央演算装置(CPUまたはMPU)(以下、単に「プロセッサ」と呼ぶ)に関わり、特に、プロセッサ内で複数のスレッドを並列処理できるマルチスレッドプロセッサおよび同時マルチスレッディングを制御するための方法に関する。



本発明は、特に、各種ロボット、自動車、プラント、ホームオートメーション等の実時間処理を行うアプリケーションにおいて、各スレッドに課された時間制約を守りつつプロセッサのスループットを向上するために好適なマルチスレッドプロセッサに関する。

Scope of claims (In Japanese)
【請求項1】
  複数のスレッドを並列的に処理するマルチスレッド中央演算装置において、
各スレッドの優先度を記憶する優先度記憶手段と、
前記各スレッドの優先度を用いて、前記複数のスレッドの命令の処理の順序または頻度を制御する第1の制御手段と、
各スレッドの一定の繰り返し周期あたりの実行命令数の目標値を記憶する目標記憶手段と、
前記各スレッドの命令実行状態を監視し、前記繰り返し周期あたりの実際の実行命令数と前記目標値を用いたフィードバック制御動作により、前記第1の制御手段により制御される前記複数のスレッドの命令の処理の順序または頻度に対して調整を加える第2の制御手段と
を備え、
前記第1の制御手段が、前記装置内の所定の資源の前記複数のスレッドへの割当量を監視し、前記複数のスレッドへの割当量が前記複数のスレッドの優先度に従うように、前記複数のスレッドの命令のフェッチ、発行または実行のそれぞれの順序または頻度を制御するマルチスレッド中央演算装置。
【請求項2】
  請求項1記載の装置において、
前記第1の制御手段が、第1の優先度をもつ1以上の第1のスレッドへの前記資源の割当量が、前記第1の優先度より下位の第2の優先度をもつ1以上の第2のスレッドへのそれ以下であるとき、前記第1のスレッド中の少なくとも一つのスレッドの命令のフェッチ、発行または実行を促進し、または、前記第2のスレッドの命令のフェッチ、発行または実行を抑制するマルチスレッド中央演算装置。
【請求項3】
  請求項1記載の装置において、
前記第1の制御手段が、各スレッドへの前記資源の割当量が少なくて所定の下限条件を満たさないとき、前記各スレッドの命令のフェッチ、発行または実行を促進し、または、前記各スレッドの命令のフェッチ、発行または実行の抑制を解除するマルチスレッド中央演算装置。
【請求項4】
  請求項2又は3のいずれか一項記載の装置において、
前記第1のスレッド中の前記少なくとも一つのスレッドには、前記資源の占有量が前記第1のスレッド中で最小であるスレッドが含まれるマルチスレッド中央演算装置。
【請求項5】
  請求項1~4のいずれか一項記載の装置において、
前記所定の資源には、フェッチされた前記複数のスレッドの命令をそれが発行されるまで保持する命令バッファが含まれる、マルチスレッド中央演算装置。
【請求項6】
  請求項5記載の装置において、
前記所定の資源には、前記命令バッファから発行された前記複数のスレッドの命令をそれが実行されるまで保持する1以上のリザベーションステーションが含まれる、マルチスレッド中央演算装置。
【請求項7】
  請求項1~6のいずれか一項記載の装置において、
前記第2の制御手段が、前記各スレッドの前記実際の実行命令数が前記各スレッドの前記目標値に近づくように、或るスレッドの前記実際の実行命令数が前記目標値を満たさない場合、前記或るスレッドの命令のフェッチまたは発行を促進し、または、前記或るスレッドより下位の優先度をもつ他のスレッドの命令のフェッチまたは発行を抑制するマルチスレッド中央演算装置。
【請求項8】
  請求項1~7のいずれか一項記載の装置において、
前記第2の制御手段が、前記各スレッドの前記実際の実行命令数が前記各スレッドの前記目標値に近づくようにするために、或るスレッドの前記実際の実行命令数が前記目標値を満たさない場合、前記或るスレッドの命令の処理の頻度を増加させるための調整を、前記第1の制御手段の制御に加え、そして、前記調整を加えても前記或るスレッドの前記実際の実行命令数に所定条件を満たす改善が現れない場合、前記加えられた調整を解除するマルチスレッド中央演算装置。
【請求項9】
  請求項1~8のいずれか一項記載の装置において、
前記第2の制御手段が、
監視周期毎に、スレッド毎に実行された命令数をカウントする監視部と、
スレッド毎に、現在の監視周期における前記実際の実行命令数が、予め設定されている目標値を満たすかチェックする第1の比較を行い、且つ、スレッド毎に、前回の監視周期における実行命令数の不足分と前記目標値との加算である繰越残値を求め、前記現在の監視周期における前記実際の実行命令数が前記繰越残値を満たすかチェックする第2の比較を行う比較部と、
スレッド毎に、前記第1と第2の比較の結果に基づいて命令フェッチ又は命令発行の頻度を可変する制御部と
を有するマルチスレッド中央演算装置。
【請求項10】
  請求項9記載の装置において、
前記制御部が、
スレッド毎に、前記命令実行状態が、前記第1と第2の比較結果の双方が肯定的である第1状態、前記第1の比較結果は肯定的であるが前記第2の比較結果が否定的である第2状態、および、前記第1と第2の比較結果の双方が否定的である第3状態のいずれに該当するかを判断する手段と、
スレッド毎に、所定の第1時間長にわたり前記第1状態が続く場合、前記命令フェッチ又は前記命令発行の頻度を減少させる手段と、
スレッド毎に、所定の第2時間長にわたり前記第2状態が続く場合、前記命令フェッチ又は前記命令発行の頻度を増加させる手段と、
スレッド毎に、所定の第3時間長にわたり前記第3状態が続く場合、前記命令フェッチ又は前記命令発行の頻度を増加させる手段と、
スレッド毎に、前記命令フェッチ又は前記命令発行の頻度を増加させた場合、前記実行命令数に所定程度以上の増加が生じたかチェックするリソースアップチェックを行う手段と、
スレッド毎に、前記リソースアップチェックの結果が否定的である場合、前記命令フェッチ又は前記命令発行の頻度を減少させる手段と
を有するマルチスレッド中央演算装置。
【請求項11】
  請求項1記載の装置において、
前記第1の制御手段が、通常の状況下では上位優先度のスレッドの命令が下位優先度のスレッドの命令より先に処理され、前記上位優先度のスレッドが前記装置内の所定の資源を無駄にするか非効率的に使用するような所定状況下では、前記下位優先度のスレッドの命令が前記上位優先度のスレッドの命令より先に処理されるように制御を行うマルチスレッド中央演算装置。
【請求項12】
  請求項1記載の装置において、
前記第2の制御手段が、前記各スレッドの前記実際の実行命令数が前記各スレッドの前記目標値に近づくように、前記複数のスレッドの命令のフェッチまたは発行の順序または頻度を制御するマルチスレッド中央演算装置。
【請求項13】
  請求項1記載の装置において
前記第2の制御手段が、前記各スレッドの前記実際の実行命令数が前記各スレッドの前記目標値に近づくようにするための調整を、前記第1の制御手段の制御に加えるマルチスレッド中央演算装置。
【請求項14】
  複数のスレッドを並列的に処理するマルチスレッド中央演算装置における同時マルチスレッディング制御方法であって、
優先度記憶手段が各スレッドの優先度を記憶するステップと、
第1の制御手段が、前記各スレッドの優先度を用いて、前記複数のスレッドの命令の処理の順序または頻度を制御するステップと、
目標記憶手段が、各スレッドの一定の繰り返し周期あたりの実行命令数の目標値を記憶するステップと、
第2の制御手段が、前記各スレッドの命令実行状態を監視し、前記繰り返し周期あたりの実際の実行命令数と前記目標値を用いたフィードバック制御動作により、前記第1の制御手段により制御される前記複数のスレッドの命令の処理の順序または頻度に対して調整を加えるステップと有し、
前記第1の制御手段が、前記装置内の所定の資源の前記複数のスレッドへの割当量を監視し、前記複数のスレッドへの割当量が前記複数のスレッドの優先度に従うように、前記複数のスレッドの命令のフェッチ、発行または実行のそれぞれの順序または頻度を制御する、同時マルチスレッディング制御方法。
Industrial division
  • Computation controlling device
  • Automobile
  • Industrial robot
IPC(International Patent Classification)
Drawing

※Click image to enlarge.

24692_01SUM.gif
State of application right Right is in force
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close