4P{4レジスタウィンド ウを用いた高速マルチスレッド アーキテクチャの検討
高瀬 亮, 日高 康雄, 小池 汎平, 田中 英彦
ftakase, hidaka, koike, tanakag@mtl.t.u-tokyo.ac.jp
東京大学 工学部3

1 はじめにレジスタウィンド ウは, プロシジャコール時の引数渡しのオーバーヘッド を削減して, 高速なプロシジャコー

thread A

thread B(out)in......

ルを実現するために考えられた機構である. しかしな

thread C(out)
in

local

......

local

がら, レジスタウィンド ウ上でマルチスレッド 処理を行なおうとすると, スレッド のスイッチなどを行なう際の図 1: レジスタウィンド ウ上のマルチスレッドオーバーヘッド が大きくなり, 性能が低下してしまう.

り, 効率の良いマルチスレッデ ィングを実現することを

本稿では, プロシジャコールを高速に行なうというレジスタウィンド ウが目指した本来の目的を損なわないと目的とする (図 1).

同時に, スレッド ハンド リングも高速, かつ低いハード

3 管理アルゴリズム

ウェアコストで行なうことを目指した, レジスタウィン

3.1

ド ウ管理のアーキテクチャについて検討する.

スレッド ハンド リング

マルチスレッディングでは, スレッドの生成, スレッド2 レジスタウィンド ウを用いたマルチスレッ の終了, スレッド のスイッチ, という三つの処理に大別
ディング
レジスタウィンド ウとマルチスレッディングの両者を融合し, レジスタウィンド ウ上でマルチスレッド を実装する手法には,
1. 全ウィンド ウを一つのスレッド が使用

スレッドのスイッチの際に全レジスタウィンド ウのして考えることができる.

スレッドの生成では, スレッド をどのレジスタウィンド ウに割り当てるかということが問題となる. 例えば,既にレジスタウィンド ウ上がスレッドで一杯である場合,新たに生成するスレッド のために, スレッドを追い出す必要がある. このハンド リングは, FIFO, LRU などさまざまな手法が考えられるが, プロセッサ側からは, レジ退避・復元を行なうため, スイッチのオーバーヘッ スタウィンド ウの使用状況を表した管理レジスタにアクド が大きいセスする手立てを用意しておくだけに留め, 実際のハン2. 各スレッド に固定的にウィンド ウを割り付けレジスタウィンド ウ上へのスレッドスイッチが高速である反面, プロシジャコールの高速化というレジスタウィンド ウ本来の目的を失っている
3. T-windows [1] など, ハード ウェア指向の方法

ド リングはソフトウェアに任せる.
スレッドの終了時は, スレッド の管理情報から終了するスレッド の情報を削除する.
スレッドのスイッチは, 更にスイッチ先のスレッド がレジスタウィンド ウ上にある場合と, スイッチ先がレジスレッド のハンド リングが柔軟で, オーバヘッドもスタウィンド ウから退避してしまっている場合に分類す少ない反面, レジスタをヒープのように確保するたることができる.

め, 複雑なハード ウェアが必要となる

前者は, レジスタウィンド ウの管理レジスタから, 切りなどがあるが, スレッド ハンド リングまたはプロシジャ 替え先のレジスタのレジスタウィンド ウのトップにウィコールの高速性と, ハード ウェアコストという両方の点ンド ウを切り替えることで, 低コストで切り替えが行なから考えると, 一長一短である.

える. また, 後者の場合は, 新たにスレッド を生成するこ

そこで, 従来のレジスタウィンド ウの形態はそのままととほぼ同じ動作になる. 異なる点は, レジスタがメモにして, この上に複数のスレッド を共存させることによ

リ上に退避してあるので, これを復元する必要があるこ

3 \A Study of Fast Multithreading Architectureusing Register Windows"

Ryo TAKASE, Yasuo HIDAKA, Hanpei KOIKE
and Hidehiko TANAKA
Faculty of Engineering, the University of Tokyo
7{3{1 Hongo, Bunkyo-ku, Tokyo, 113, Japanとだけである.
3.2

プロシジャのハンド リング

スレッドにおけるレジスタウィンド ウのトップで, プロシジャコールが発生し, ウィンド ウをずらすと, 他のスレッド が使用しているウィンド ウを破壊してしまうこ

管理レジスタだけだと, どのスレッド が別のスレッド にとが起こり得る.

よって破壊される (=退避させられる) ことになるのか

この場合, 破壊されるウィンド ウが属するスレッドを特定して, そのウィンド ウをメモリ上に退避する動作が必要である. この動作は不可避であり, 退避にはオーバーヘッド がかかるが, スレッド 生成の際に, ある程度の大が判断できない. 従って, これとは別にスレッド毎にウィンド ウの使用範囲を示すテーブルを用意する (図 3).
Win. Num.
WIM......

きさのレジスタウィンド ウを確保しておくことによって,

3
400
thread ’1’

51

60 ......
thread ’2’

CWP

絶対的な退避回数を低減することが可能である.

loadsearch

この動作と同時に, ウィンド ウが属するスレッド も変

thread ID Win. bottom Win. top
12
42
58:::

更しておく必要がある.
なお, プロシジャからリターンする際に, ウィンド ウのボトムを検出した場合は, ウィンド ウの移動は行なわない. 従って, スレッド がウィンド ウのトップから破壊されることはない [2].
以上述べてきたように, レジスタウィンド ウ上に複数のスレッド を実装することを考えると, ウィンド ウ上のスレッドの干渉を, いかにうまく管理するかが鍵となる.
この管理を行なうのが, プロセッサのレジスタウィンドウ管理レジスタであり, このアーキテクチャとその動作をうまく実装することに帰着できる.

図 3: ウィンド ウ使用範囲のテーブル
あるスレッド におけるプロシジャのコールを考える.
スレッドの予約済みウィンド ウを越えて, 他のスレッドに干渉する事態になることがあるが, まず WIM によりスレッド の干渉の可能性がチェックされる. 干渉しない
場合は問題ないが, 干渉する場合 (WIM の対応ビットが1 の場合), テーブルのウィンド ウボトム値をサーチする.

ウィンド ウが他のスレッド によって使用されていれば,4 ハード ウェアアーキテクチャ

必ずこのテーブル内の 1 エントリにヒットし, 破壊され3 節で述べたようなレジスタウィンド ウ管理を行なうために必要な, ハード ウェアアーキテクチャについて, とくに管理レジスタに着目してみる.

るスレッド がわかる.
また, ウィンド ウトップの値は, スレッドスイッチの際に参照する. スレッド がスイッチする際, スイッチ先のまず, レジスタウィンド ウ上に同時に複数のスレッドウィンド ウは必ずウィンド ウトップであるので, この値が存在することになるため, 隣接したスレッド 間での干を CWP にロード することにより, スレッド をスイッチ渉が起きないようにする必要がある. このため, レジスすることができる.

タウィンド ウには WIM1 (Window Invalid Mask) を設

5 まとめける (図 2).

レジスタウィンド ウ上にマルチスレッドを実装する際

Register Windowsの管理アルゴリズムについて述べた. また, このような......

......

thread A......

WIM
100

CWP
10

ついて述べた.

thread B0

管理を行なうのに適したハード ウェアアーキテクチャに今後は, このようなアーキテクチャを, レジスタウィン

01......

図 2: WIM と CWP
この WIM は, 各スレッドの境界を示しており, 両境界に挟まれたレジスタウィンド ウが, そのスレッド が使用できるウィンド ウになる. また, 常に現在のウィンド ウ位置を示すポインタ CWP (Current Window Pointer)

ド ウを持った従来型プロセッサに付加することを考え,シミュレータを作成し, その評価をする予定である.

参考文献[1] D. J. Quammen and D. R. Miller. Flexible registermanagement for sequential programs. In Proc. of
18th Annual Intl. Symp. on Comp. Arch., pp. 320{329, 1991.

がある. この二つのレジスタにより, スレッド が, 使用可能なレジスタウィンド ウを越えて使用してしまうことを避けることができる.
WIM は, レジスタウィンド ウに存在する全スレッドに対して一つだけ存在するビットマップであるが, この1 SPARC アーキテクチャにおける WIM とほぼ同義である.

[2] Y. Hidaka, H. Koike, and H. Tanaka.

Multiplethreads in cyclic register windows. In Proc. of 20th
Annual Intl. Symp. on Comp. Arch., pp. 131{142,May 1993.