Japan Advanced Institute of Science and Technology

(1)

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

コンテクストバッファを用いたマルチスレッド実行方

式に関する研究

Author(s)

上田, 憲吾

Citation

Issue Date

2005‑03

Type

Thesis or Dissertation

Text version

author

URL

http://hdl.handle.net/10119/1856

Rights

Description

Supervisor:田中清史, 情報科学研究科, 修士

(2)

修士論文

コンテクストバッファを用いたマルチスレッド実行方式に関する研究

北陸先端科学技術大学院大学情報科学研究科情報システム学専攻

上田憲吾

年月

(3)

修士論文

コンテクストバッファを用いたマルチスレッド実行方式に関する研究

指導教官

田中清史助教授

審査委員主査

田中清史助教授

審査委員

日比野靖教授

審査委員

井口寧助教授

北陸先端科学技術大学院大学情報科学研究科情報システム学専攻

¿½¼¼½¿

上田憲吾

提出年月年月

(4)

概要

マルチスレッドアーキテクチャはパイプライン実行のためのハードウェア資源を効率よく使用することが可能である。しかし、従来のマルチスレッドアーキテクチャではプロセッサ内のスレッド数が限られているため、全てのスレッドがキャッシュミスを起こす状況が発生した場合、パイプラインストールは不可避である。

本論文ではプロセッサコンテクストバッファを用い、実行スレッドのバックグラウンドでコンテクストをスワップする。これによりプロセッサ内蔵コンテクストの数を仮想的に増やし、シームレスなコンテクスト切り替えを実現する手法を提案し、評価を行う。

シミュレーションにより、プロセッサコンテクストバッファを用いることで、プロセッサ内のコンテクスト格納領域であるプロセッサコンテクストセット数削減の可能性を示した。

(5)

第章序論

研究の背景

近年のプロセッサは、パイプラインやスーパースカラなどのアーキテクチャ的技術と半導体の微細化高集積度により高速化が達成されてきた。しかし、メモリアクセスの速度は比較的低いため、キャッシュミス等の要因によりプロセッサ内のハードウェア資源が有効利用されない。メモリアクセスによるレイテンシを隠蔽しハードウェア資源利用の効率化を図る技術として、マルチスレッドアーキテクチャがある。

マルチスレッドアーキテクチャでは、プロセッサ内に複数のスレッドコンテクスト格納用レジスタを用意することで、実行スレッドを高速に切り替えることを可能としている。

レイテンシの大きな操作が必要な場合には、他のスレッドへ実行を切り替え、パイプラインをストールすることなくハードウェア資源を有効活用することが可能となる。

しかし、従来のマルチスレッドアーキテクチャではプロセッサ内の全てのスレッドがキャッシュミスを起こす状況が発生した場合、パイプラインストールは不可避である。プロセッサ内のコンテクストを増やすことで、このような状況を減らすことは可能であるが、ハードウェア的コストが大きく現実的ではない。

研究の目的

マルチスレッドアーキテクチャによって、パイプラインストールの回避が効果的になされるためには、プロセッサ内に実行可能なスレッドが待機している必要がある。本研究では、プロセッサの内蔵コンテクストの数を仮想的に増やすコンテクストバッファを使用する。キャッシュミス等の要因で待ち状態となったコンテクストと、コンテクストバッファ内のコンテクストを、アクティブな実行スレッドのバックグラウンドでスワップすることにより、常に実行可能なスレッドをプロセッサ内に待機させシームレスなコンテクスト切り替えを実現する方式を提案する。本提案方式の評価をシミュレーションによって行い有効性を示す。

(8)

本論文の構成

本論文は５章からなる。第２章では従来のマルチスレッドアーキテクチャについて述べる。第３章ではプロセッサコンテクストバッファを用いた拡張マルチスレッドアーキテクチャについて述べる。第４章でその有効性をシミュレーションによって示す。最後に第５章で本論文の結論を述べる。

(9)

第

章マルチスレッド実行方式

マルチスレッドアーキテクチャ

今日のコンピュータはステートが遷移することで動作している。ステートは、プログラムメモリやデータメモリなどのメモリステート、プログラムカウンタやスタックポインタなどの実行履歴を意味するプロセッサステート、そしてレジスタセットによって決定付けられる。このプロセッサステートとレジスタセットはコンテクストと呼ばれる。

今日のプロセッサの大半はシングルスレッドプロセッサアーキテクチャを採用しており、単一のコンテクストをプロセッサ内に有する。一方マルチスレッドアーキテクチャは、

複数のスレッド^½に対応したコンテクストをプロセッサ内に有する点でシングルスレッドアーキテクチャとは異なる。複数のコンテクストはプロセッサ内の複数の^¾に格納される（図）。参照するコンテクストを切り替えることで、実行スレッドの高速切り替えが可能となる。

PCS PCS PCS PCS

実行ユニット

コンテクスト参照

図マルチスレッドアーキテクチャ

マルチスレッド実行方式は、実行中に生じるレイテンシを他のスレッドの実行で隠蔽

½スレッドとは粒度の粗い逐次命令ブロックのことである。

¾本論文ではコンテクストを格納するハードウェア領域をプロセッサコンテクストセット（）と呼ぶこととする。

(10)

し、複数スレッド全体での実行性能を改善する。単一スレッド実行の性能改善を目的とし、アイドルが頻繁に起こる傾向のあるスーパースカラプロセッサとは対照的である。

スレッド切り替え方式

マルチスレッド実行方式を実現するにあたり最も重要となる点は、コンテクストを切り替え手法である。コンテクスト切り替えによるオーバヘッドは非常に小さく、０から数サイクルでなければならない。マルチスレッド実行方式はコンテクストの切り替え手法によって、大きく三つに分類される。

サイクルバイサイクルマルチスレッディング

サイクルごとに異なったスレッドの命令がフェッチされ実行パイプラインに投入される。

ブロックマルチスレッディング

実行中のスレッドがレイテンシを生じるようなイベントが起こるまで連続的に実行される。このイベントがコンテクスト切り替えを起こす。

サイマルテイニアスマルチスレッディング

複数の命令が複数のスレッドから同時に発行され、スーパースカラプロセッサのパイプラインに投入される。

以降、本論文に関連の深いサイクルバイサイクルマルチスレッディングとブロックマルチスレッディングについて説明する。

サイクルバイサイクルマルチスレッディング

サイクルバイサイクルマルチスレッディング方式では命令のフェッチが完了するたびにコンテクストが切り替えられる。パイプラインは常に異なったスレッドの命令で満たされ、パイプライン中の命令間での依存が生じない。パイプラインハザードが起こることは無く、フォワーディング回路を用意することなく非常に単純なパイプラインの設計が可能である。これは高クロックでの駆動可能性を示す。更にサイクル毎にコンテクストを切り替えることを前提としているので、切り替えによるオーバヘッドは全く無い。

図はシングルスレッド方式とサイクルバイサイクルマルチスレッディング方式での実行を表したものである。四つのスレッドがあり、スレッドは実行中にキャッシュミスに遭遇する。シングルスレッド実行方式では、一つのスレッドの実行が完了すると新たなスレッドが起動される。新たなスレッドの起動にはオーバヘッドを伴う。キャッシュミスの際にはキャッシュの充填が完了するまで実行は中断される。サイクルバイサイクルマルチスレッディング方式では、サイクル毎に実行スレッドが切り替わり、一つのス

(11)

キャッシュミス

キャッシュの充填

時間

切り替えオーバヘッド

A B

A idle C D

B,C,D のバックグラウンドでキャッシュの充填

Thread A がキャッシュミス (A)

(B)

図サイクルバイサイクルマルチスレッディング実行シングルスレッドプロセッサによる実行サイクルバイサイクルマルチスレッドプロセッサによる実行

レッドは４サイクルに一度実行される。また切り替えによるオーバヘッドは完全に取り除かれる。キャッシュミス時には、ミスを起こしたスレッド以外は実行を継続し、キャッシュの充填によるレイテンシの大部分が隠蔽されている。

サイクルバイサイクル方式は、パイプライン段数と同数のがプロセッサ内になければならない。のハードウェア的コストは大きく、また最近のプロセッサのパイプライン段数は増加傾向にあるので、パイプライン段数と同等のをプロセッサ内に設けることは難しい。更に、プロセッサ内に十分ながある場合にも、スレッドの数が十分でない場合には、十分な性能を発揮できないという問題がある。

図は実行すべきスレッドが一つしかない場合である。サイクルバイサイクルマルチスレッディング方式で実行した場合には、数サイクルに一度しか命令が実行されないため、シングルスレッド実行方式よりも時間がかかる。

(12)

時間 (A)

(B)

図サイクルバイサイクルでの単一スレッドの実行シングルスレッドプロセッサによる実行サイクルバイサイクルマルチスレッドプロセッサによる実行

ブロックマルチスレッディング

ブロックマルチスレッディング方式では特定のイベントが起こるまでコンテクスト切り替えは起こらない。コンテクスト切り替えが起こるまでは一つのスレッドが連続的に実行される。サイクルバイサイクル方式と比べると、スレッドの数は少なくてよい。単一スレッドの実行はシングルスレッドプロセッサと同等な性能をもつ。切り替えを起こすイベントとして次のようなものが考えられる。

静的イベント

ロード、ストア、ブランチ命令、または明示的な切り替え命令がフェッチおよびデコードされた時

動的イベント

キャッシュミスや割り込みなどの動的に発生するイベント時

静的なイベントによる切り替えは、命令のフェッチおよびデコードによって起こる。この命令はフラッシュされるため結果的にパイプライン中に１サイクルのバブルが発生する。これが切り替えオーバヘッドとなる。動的なイベントによる切り替えは更に数サイクル分の切り替えオーバヘッドを必要とする場合がある。データキャッシュミスなどの動的イベントはパイプラインの比較的遅いステージで検出されるため、検出された時点では後続の数命令がすでにパイプラインに投入済みである。これらの命令はフラッシュされ切り替えオーバヘッドとなる。

図はキャッシュミスが引き金となり切り替えが起こるブロックマルチスレッディングによる実行を表したものである。二つのスレッドがあり、スレッドは実行中にキャッシュミスに遭遇する。シングルスレッド実行方式では、キャッシュミスの際にはキャッシュの充填が完了するまで実行は中断される。スレッドの実行が完了するとスレッド

(13)

時間

(A)

(B)

キャッシュミス

キャッシュの充填切り替えオーバヘッド A

A idle B

A B A

Bのバックグラウンドでキャッシュの充填

図ブロックマルチスレッディング実行シングルスレッドプロセッサによる実行

ブロックマルチスレッドプロセッサによる実行

が起動される。この時オーバヘッドを伴う。ブロックマルチスレッディング方式では、

キャッシュミスに遭遇するまでが実行される。キャッシュミスが発生するとスレッドが切り替えられる。この時に数サイクルのオーバヘッドを伴う。この後キャッシュの充填はスレッドの実行のバックグラウンドで行われ、キャッシュの充填によるレイテンシは隠蔽される。

従来型マルチスレッド実行方式の問題点

マルチスレッド実行方式を用いると、メモリアクセスによる比較的大きいレイテンシを隠蔽可能である。しかし、これはプロセッサ内に実行可能なスレッドが十分に待機している場合に限られる。

は主にレジスタファイルで構成さる。現在のプロセッサは、スーパースカラ実行やアウトオブオーダー実行を行うものが主流である。これらのプロセッサではレジスタファイルへの読み出し書き込みポートが増大する傾向があり、のハードウェア的コストは増大する。プロセッサ内に配置可能な数には限りがあり、プロセッサ内のスレッドが全てがキャッシュミスを起こす場合にはレイテンシの隠蔽は効果的には行われない。

図はキャッシュミスが頻発する状況を表している。）はシングルスレッド方式での実行であり、（）はブロックマルチスレッド方式での実行である。（）ではスレッド

(14)

がキャッシュミスを起こすとスレッドへと実行が切り替わるが、すぐにスレッドもキャッシュミスを起こしている。この時スレッドのキャッシュラインの充填は完了しておらず、他に切り替わるべきスレッドが存在しない。またスレッドのキャッシュの充填はスレッドのキャッシュ充填が終了するまで開始されない。

マルチスレッドプロセッサはプロセッサ内にある全てのスレッドが一つのキャッシュを共用するので、限られたキャッシュの容量が圧迫され競合性ミスの発生頻度を増加させる傾向がある。よってプロセッサ内のスレッドがキャッシュミスを頻発する状況が簡単に起こりえる。

ミス１ (A)

(B)

ミス１

時間

A B

A idle idle A idle B

A B idle A B A

ミス２ミス３

ミス３ミス２

idle idle

充填１充填２充填３

図キャッシュミスが頻発する状況

(15)

第

章コンテクストバッファによる拡張マルチスレッドアーキテクチャ

プロセッサコンテクストバッファ

一般的に一次キャッシュは用途に合わせて、データキャッシュと命令キャッシュに分割される。スレッドコンテクストはスワップハンドラにとってのデータではあるが、スレッド実行データとは性質が異なる。スレッドコンテクスト専用の記憶領域であるプロセッサコンテクストバッファ（以降と表記する）を新たに設けからあふれたコンテクストを内に配置する研究が行われている。複数のスレッドコンテクストは優先度の高いものから内に配置され、からあふれたコンテクストはに配置、更に

からあふれたものはメインメモリ内のコンテクストストレージバッファ（）領域に配置される（図）。

本論文ではこのプロセッサコンテクストバッファを用いる。

PCS PCS PCS PCS

実行ユニット

PCB

CSB

プロセッサメインメモリバックグラウンドでスワップ実行スレッド

図コンテクストバッファを用いた拡張マルチスレッドアーキテクチャ

はプロセッサ内の全てのと直接接続され、と間でのコンテクストのスワップはハードウェアによって行われる。スワップをハードウェアで行うことによる利点はスワップによるオーバヘッドを隠蔽可能である点である。プロセッサ内の実行スレッドがキャッシュミス等の原因により待ち状態に陥った場合、コンテクストバッファに

(16)

対してスワップ要求を出す。コンテクストのスワップが行われている間もプロセッサ内にある他の実行可能なスレッドが実行されスワップによるオーバヘッドが隠蔽される。

マルチスレッド実行方式で重要となる点は、実行可能なスレッドのコンテクストがプロセッサ内に待機しているかどうかである。本研究では、可能な限りプロセッサ内のには実行可能なスレッドのコンテクストのみを配置し、実行不可能なスレッドのコンテクストはプロセッサ外のに配置する。プロセッサ内で実行中のコンテクストがキャッシュミスを起こすと、プロセッサはに対してスワップ要求を出し、キャッシュミスを起こしたコンテクストはに退避される。この際、内でスワップの対象となるコンテクストは実行可能なコンテクストに限定する。実行可能なコンテクストが存在しない場合には、実行可能なコンテクストが発生するまでスワップを保留する。

コンテクストバッファの従来型マルチスレッド方式への適用

本論文ではコンテクストバッファを従来のブロックマルチスレッドとサイクルバイサイクルマルチスレッドに適用する手法を提案する。

ブロックマルチスレッドへの適用

プロセッサ内でのコンテクスト切り替え方針は従来のブロックマルチスレッド方式と同様とし、によってブロックマルチスレッドアーキテクチャを拡張する。の基本動作に基づいて、プロセッサ内の実行継続不可能なコンテクストは速やかに内の実行可能なコンテクストとスワップされる。拡張において注意すべきことは、スワップ中の

に対してコンテクストの参照が行われないようにロックをかける点のみである。

(17)

時間

A

充填１充填２

A

idle A B idle B C

A B idle B C A

B C B A

充填３

充填１充填２

ミス１ミス２

ミス１ミス３ミス２

ミス１ミス２

充填１充填２

スワップハンドラ (A)

(B)

(C)

図コンテクストバッファを用いたコンテクストスワップシングルスレッドプロセッサによる実行ブロックマルチスレッドプロセッサによる実行コンテクストバッファによる拡張ブロックマルチスレッドプロセッサによる実行

図にで拡張されたブロックマルチスレッド方式の動作例を示す。コンテクストバッファによるスワップオーバヘッドは、キャッシュミスが起こる頻度に比べて、十分小さいと仮定している。

スレッドは、、の三つがある。シングルスレッド方式では一つのスレッドが完了すると次のスレッドが起動される。ブロックマルチスレッド方式では、二つのスレッドは

に配置され、残りの一つはに配置される。による拡張ブロックマルチスレッド方式では、二つは、残りの一つはに配置される。

）ではプロセッサ内の全てのコンテクストが実行不可能になった時点で、スワップハンドラが呼び出され、スワップによるキャッシュミスが起こっている。ではスワップは全て他のスレッドの実行のバックグラウンドで行われている。このようにコンテクス

(18)

トバッファを用いることで、スワップの際のロードやストア命令にかかるオーバヘッド、

それによって起こるキャッシュミスを取り除くことができる。また、スワップが有効に動作することでプロセッサ内のの数が仮想的に増え、キャッシュミスレイテンシをより効果的に隠蔽可能である。を用いることによる仮想的数の増加により、プロセッサ内の数を削減することが可能となる。

サイクルバイサイクルマルチスレッドへの適用

サイクルバイサイクルマルチスレッドへの適応の場合にも、ブロックマルチスレッドの場合と同じ注意点が必要となる。更にサイクルバイサイクルの場合には、の最小数はパイプライン段数によって決定されるため、はの数を仮想的に増やす効果を持つという理由に基づく数削減には限界がある。

スワップにかかるオーバヘッドの削減、キャッシュミスレイテンシの効果的な隠蔽が可能という利点はブロックマルチスレッドと同じである。

アーキテクチャ詳細

コンテクスト切り替え

それぞれのコンテクストは汎用レジスタ、プロセッサステートレジスタ、Ｙレジスタ^½、プログラムカウンタ（ＰＣ）、次のプログラムカウンタ（ｎＰＣ）、更にコンテクストが実行可能状態であるか否かの情報を持つ。実行不可能状態には二つの種類がある。スレッド実行に必要な値がキャッシュ内に無い場合と、コンテクストがと間でスワップ中である場合である。

コンテクストはプロセッサ内ではに格納され、それぞれのは識別子として０から順番に番号が割り振られる。実行ユニットは実行中のの識別子情報を持ち、対応する内のコンテクストを使用して実行を行う。実行ユニット内の識別子情報はサイクルバイサイクル方式ではサイクル毎に更新され、ブロックマルチスレッド方式では実行スレッドがキャッシュミスを起こした場合に更新を試みる。更新の際、サイクルバイサイクル方式では単純に識別子情報がカウントアップされる。ブロックマルチスレッド方式では次のが実行可能状態である場合のみカウントアップされる。ブロックマルチスレッド方式で更新を試み失敗した場合には次サイクルから更新が成功するまでフェッチがストールされる。両方式ともカウントアップの結果がオーバーフローした場合には値はリセットされ０へ戻る。

½本研究ではアーキテクチャをベースとする。Ｙレジスタは乗除算の上位ビットが格納されるレジスタである。

(19)

コンテクストスワップ

実行スレッドがキャッシュミスを起こした場合にはプロセッサはに対してスワップ要求を発行する。はキューを持ち、プロセッサから発行されたスワップ要求はキュー内に投入され、はキュー内の要求を順番に処理する。

本論文ではスワップの際、内の対象コンテクストの決定方法として二つの方法を提案する。内に最も古く挿入されたコンテクストを選択する方法、内で最も優先度の高いコンテクストを選択する方法の二つである。

最も古いコンテクストを選択

この方法はを単純な構成とすることで実現される。スワップの際、から追い出されたコンテクストはの末尾に付け加えられ、の先頭にあるコンテクストがに格納される。

最も優先度の高いコンテクストを選択

この方法はコンテクストとの構成に変更を加える必要がある。まずコンテクストに優先度情報を追加する。そして内で、先頭エントリから順番に次エントリと比較する。次エントリに格納されているコンテクストが実行可能状態であり、優先度が高ければ次エントリを優先する。この操作を全エントリ対して繰り返す。（図）優先度を格納する数ビット程度のハードウェア領域を全と全のエントリに対して追加し、優先度の比較専用ハードウェアをに追加する必要がある。この構成ではの全エントリに対して比較を行うので、スワップを開始するまでにオーバヘッドをともなう。またオーバヘッドはのエントリ数に応じて大きくなる。

(20)

mux PCB

ｐｒｉｃｏｎｔｅｘｔ

全エントリに対して比較

PCS

図優先度を考慮したプロセッサコンテクストバッファ

(21)

第

章評価

評価環境

本論文で提案するによる拡張マルチスレッドアーキテクチャの評価はシミュレータによって行う。シミュレータはバイナリコードを入力とし、クロックベースで実行を行う。

シミュレーション

ここではによる拡張マルチスレッドアーキテクチャによる実行シミュレータについて説明する。また比較対照とする従来型マルチスレッドアーキテクチャでの実行、スワップハンドラを用いたコンテクストスワップを行う実行のシミュレータについても説明する。

による拡張マルチスレッドアーキテクチャ

マルチスレッド実行を行うアーキテクチャとして、複数のを備えるマルチスレッドプロセッサを仮定する。各スレッドのコンテクストは、に格納され、からあふれたコンテクストはに格納される。のサイズは十分大きいと仮定し、全てのコンテクストはまたはに格納される。コンテクストスワップの際に必要となるオーバヘッドは、優先度を考慮しない形式のを用いる場合サイクル、優先度を考慮するを用いる場合はサイクルとする。

従来型マルチスレッドアーキテクチャ

各スレッドのコンテクストはに格納され、から溢れたコンテクストはメインメモリ内のコンテクストストレージバッファ領域（）に格納される。コンテクストのスワップは一切行われず、中のコンテクストが終了した時のみ、そのコンテクストが切り捨てられ、新たなスレッドのコンテクストがから呼び出される。この時必要となるオーバヘッドはサイクルとする。

(22)

スワップハンドラによるコンテクストスワップ

本論文では、従来型マルチスレッド実行中に、管理の下でメモリやキャッシュ内のコンテクストとスワップする方式も比較対照とする。管理の下で行われるロードやストアによるコンテクストのスワップはキャッシュミスを引き起こす可能性がある。

時間ミス１

A B idle C

充填１充填２充填３

ミス４

スワップハンドラミス２

A ミス３

図スワップハンドラによるキャッシュミス

図はスワップハンドラによるキャッシュミスの例である。セット数はとし、

に内蔵されているスレッド、のコンテクスト以外にもメインメモリ内のにスレッドのコンテクストがある。スワップハンドラはプロセッサ内のコンテクストがキャッシュミスを起こした時、割り込みにより起動する。

スレッドがキャッシュミスを起こした時、割り込みによりスワップハンドラが起動される。スレッドのコンテクストとメインメモリ内にあるスレッドのコンテクストのスワップを試み、そのスワップハンドラが更にキャッシュミスを起こし、実行がプロセッサ内の実行可能なスレッドへ移る。その後スレッドの充填が完了するが（図中の充填１）スレッドのコンテクストはスワップ中であるため、スレッドの実行はロックされている。スレッドがキャッシュミスを起こした時点で、スレッドのキャッシュは充填されているにもかかわらずプロセッサはアイドル状態のままである。この方法に基づいたシミュレーションを行う。ハンドラによるコンテクストスワップに必要とされるオーバヘッドは、キャッシュミスが起こらない場合サイクル、スワップ中にキャッシュミスが発生した場合はキャッシュミスペナルティを付加したサイクル数とする。

共通事項

上記の三つの構成全ての場合において、全ての命令の実行に必要とされるレイテンシは

サイクルとする。プロセッサの持つキャッシュは、ウェイセットアソシアティブ方式とし、ブロックサイズ、全体容量はとする。キャッシュミス時のペナルティは

サイクルとする。

(23)

ベンチマークプログラム

シミュレーションの対象プログラムとして、^!"^#$を用いる。これらのプログラムは、専用コンパイラによってコンパイル時にスレッド分割処理が行われ、実行バイナリ中の適切な位置にスレッドスタート命令が挿入されるアーキテクチャを仮定する。

それぞれのプログラムをシングルプロセッサで逐次実行した場合の実行命令数を表にしめす。

表各ベンチマークプログラムとその実行命令数

ベンチマークプログラム実行命令数

#$ %&'( ") *+!#,

#$ %-. /0 1, #0"!1$, &"$23' "#45+*, . *(#,

#$ %## 1 "(50,

#$ %6*#(( $#* 05 #0

#$ %, %(*+"#*$$!#*,"# 6$"7(*+"#*$

#$ %+# *$$#* 05 #0 85*,"#

#$ %85*,"#") 2,*, ) *+!#,

#$ %#,+ *,"#

#$ %#,+ *,1 (0," 2

#$ %(9 #0 1 (0," 2

#$ %: 2, 25!

#$ %: 2, (9 #0

#$ % % * ,0$# $$

#$ %% * ,0$# $$

#$ %*25*$" , *# $"1!#, 2"#

#$ %;"#,* $" 2* 0&$""1

#$ %!1$0,0"#(,"#*$ 0"!15,*,"#

#$ % % /1$0,&'(" "('#*!02) *+!#,

#$ %+# *$$#* 05 #0 85*,"#2

#$ %20 , " (#*,2 , *#21" , 0"#(,"#*$ 05 #0 "#//

#$ %!*, /<!*, /1 "(50,

#$ %$*#03*# (2, 65,"#

#$ % % !1$0,&'(" "('#*!02 ) *+!#,

#$ %:#( $"0*,"# ") : 2, !#!5! # * *'

評価はスレッド化された^!" ^#$のバイナリコードをシミュレータに対して

スレッド入力することで行う。^#$ それぞれの場合において全く同じ^#$

(24)

のみをスレッド入力する。この評価は、特定の処理のみを繰り返すアプリケーションの評価と考えることができる。

一般的なアプリケーションはさまざまな処理によって成り立っている。よって^#$

からランダムに選んだスレッドを入力とするシミュレートも行う。ランダムに選ぶスレッドのパターンはパターンとしそれらの結果の平均をとることで一般的なアプリケーションの評価とする。

(25)

による拡張ブロックマルチスレッド方式の評価と結果

による拡張マルチスレッドアーキテクチャによる実行はのセット数を、、

、と変化させた場合の評価を行う。また、は優先度を考慮しない形式を用い、スワップオーバヘッドはサイクルとする。従来型マルチスレッドアーキテクチャによる実行の評価はのセット数を^½、、、、と変化させた場合の評価を行う。

スワップハンドラによるコンテクストスワップを行う実行はのセット数を、、と変化させた場合の評価を行う。

評価の基準としてを用いた。これは有効実行命令数をプログラムの実行に要したサイクル数で割った実効である。スワップハンドラによるコンテクストスワップ命令は有効命令に含まないものとする。また、参考としてキャッシュミス率の計測も行った。

キャッシュミス率は全ミス数を全メモリアクセス数で割ることにより算出する。

図に特徴的であったブロックマルチスレッド実行結果を示す。また、ランダムに入力を行ったパターンでの結果の平均を図、示す。

本論文の提案するを用いた拡張マルチスレッドアーキテクチャの利点は、を用いることで、少ないセット数でも多くのコンテクストを同時に扱うことが可能となる点である。図は少ないセット数で、十分な効果を発揮した例である。

これらの図中の拡張マルチスレッド実行では、セット数で、セット数の従来型マルチスレッド実行と同等の性能を出している。

図はを用いることでの利点が、現れなかった例である。図はをセットのみ持つシングルスレッド実行が高いを示しており、マルチスレッド実行する必要がない。その他の図はマルチスレッド実行が潜在的に持つセット数の増加に伴うキャッシュ効率の低下という問題点により、十分な性能が発揮できなかった例である。これらの例では従来型マルチスレッド実行においてもセット数が増えると性能が低下している。キャッシュミス率の全ての図から、拡張マルチスレッド実行はセット数が１でセット数の従来型マルチスレッド実行と同等のキャッシュミス率を示している。そのため拡張マルチスレッド実行がセット数の従来型マルチスレッド実行を超えることはなく、最終的にセット数の従来型マルチスレッド実行と同等の結果へと収束する。これらの例の中でも図はセット数が少ない場合にセット数の従来型マルチスレッドと同等の性能へと収束している。

図ではセット数の従来型マルチスレッドと同等の結果を得るために、

セット数を必要としている。本論文で提案するを用いた拡張マルチスレッド実行方式が効果をもたらすためには、キャッシュミスの起こる頻度が、コンテクストスワップのオーバヘッドよりも小さくなければならない。複数のコンテクストスワップを同時に行うことは不可能であり、コンテクストスワップ中にプロセッサ内の他のコンテクストがキャッシュミスを起こした場合は、そのコンテクストはしばらくの間、内に留まる。

に留まるコンテクストが増え、プロセッサ内のコンテクスト全てが実行不可能となっ

½これはシングルスレッド実行に相当

(26)

た場合には、プロセッサは実行を停止する。図ではこのような状況が頻発したため、

性能低下を招いている。

全ての図において、スワップハンドラによるコンテクストスワップを行う実行の結果は、同等のセット数を持つ拡張マルチスレッド方式に勝ることは無かった。スワップハンドラによるスワップオーバヘッドはによるスワップオーバヘッドよりも大きく、また、コンテクストがメモリ内のにコンテクストを格納することにより、

キャッシュミス率を増加させる傾向があるためである。

上記をまとめると、拡張ブロックマルチスレッド方式では、、両方に格納されているコンテクスト数と同等のセット数を持つ従来型ブロックマルチ方式に近い性能を持ち、キャッシュミス率が低い場合、少ないセット数で従来型マルチスレッド方式と近い性能を持つ。図にもこの傾向は示されている。この図ではセット数、またはで十分な性能が確認できる。

(27)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03;5$,,& *(#+ #$%

1 10 100

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs + csb pcs + pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(28)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03;5$,,& *(#+ #$%

1 10

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs + csb pcs + pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(29)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03;5$,,& *(#+ #$ %

1 10

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs+csb pcs+pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(30)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03;5$,,& *(#+ #$ %

1 10

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs+csb pcs+pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(31)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03 ;5$,,& *(#+ #$ %

0.001 0.01 0.1 1 10

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs + csb pcs + pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(32)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03 ;5$,,& *(#+ #$ %

1 10 100

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs + csb pcs + pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(33)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03 ;5$,,& *(#+ #$ %

1 10

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs+csb pcs+pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(34)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03 ;5$,,& *(#+ #$ %

0.001 0.01 0.1 1 10

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs + csb pcs + pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(35)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03 ;5$,,& *(#+ #$ %

0.001 0.01 0.1 1 10

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs + csb pcs + pcb

図 ^$"03 ;5$,,& *(#+ #$ %

!22 *,

(36)

0 0.2 0.4 0.6 0.8 1 1.2

1p cs 2p cs 4p cs 8p cs 16 pc s

2p cs +c sb 4p cs +c sb

8p cs +c sb 1p cs +pc b

2p cs +pc b 4p cs +pc b

8p cs +pc b IP C

図 ^$"03 ;5$,,& *(#+ *+ ") *#(*!#15, %

1 10

1pcs 2pcs 4pcs 8pcs 16pcs

m is s ra

te pcs

pcs+csb pcs+pcb

図 ^$"03 ;5$,,& *(#+ *+ ") *#(*!#15, % !22 *,

(37)

te pcs

pcs+pcb

図 '0$%6'%0'0$ ;5$,,& *(#+ #$

% !22 *,

(47)

0 0.2 0.4 0.6 0.8 1 1.2

4pcs 8pcs 16pcs 4pcs + pcb 8pcs + pcb

IP C

図 '0$%6'%0'0$;5$,,& *(#+ *+ ") *#(*! #15, %

1 10

4pcs 8pcs 16pcs

m is s ra

te pcs

pcs+pcb

図 '0$%6'%0'0$ ;5$,,& *(#+ *+ ") *#(*! #15,% !22 *,

(48)

優先度を考慮する機構を持つ

の評価と結果

#$ を入力とし、で構成されるによる拡張ブロックマルチスレッド（セット数）、優先度を考慮するによる拡張ブロックマルチスレッド（セット数、セット数、セット数）による実行を行った。入力^#$中に含まれる二つの^#$を他のスレッドよりも優先度を高く設定しシミュレートした結果をに示す。

21 503349400

21 503121322

10 430798221

10 430745023

07 423407385

14 421395755

09 413825716

18 395979871

18 391135663

08 388051835

18 386773206

17 374145199

04 360332175

02 339396539

02 338968326

12 321383881

Kernel 終了クロック

21 517136020

21 516976571

14 439569047

07 438870331

09 435290075

18 418105898

18 417976841

08 414821871

18 408202888

17 401068082

02 381462321

02 380514386

04 371209136

12 346634945

10 213407338

10 213378672

Kernel 終了クロック

21 487313817

21 487193050

07 408462855

09 406820109

14 406818262

08 386266665

18 384760479

18 380723150

18 376694569

17 371031499

04 357417672

02 344063679

02 343234224

10 340214231

10 340185901

12 326956240

Kernel 終了クロック

21 483110895

21 482907500

07 406139887

10 405645701

10 405605049

14 400920996

09 399571040

18 376053865

18 374663808

08 374549068

18 366915847

17 356709556

04 354626342

02 328981721

02 328706080

12 313677070

Kernel 終了クロック

8PCS +

優先度 PCB 4PCS +

優先度 PCB 2PCS + 優先度 PCB 2PCS +

FIFO PCB

図優先度を考慮する

キャッシュミスを起こしたコンテクストがに退避され、内で優先度を考慮した処理を行う場合、と間のコンテクストスワップが多いほど優先度順に実行される。のセット数が少ないほどコンテクストスワップは頻繁に起こり、セット数の時に^#$の実行が最も早く終了する結果となった。

(49)

第

章結論

まとめ

本論文では、最初にマルチスレッド実行方式の有効性と問題点を述べた。次にコンテクストバッファによりマルチスレッドアーキテクチャを拡張する方法を述べ、コンテクストバッファを用いたコンテクストスワップ手法を提案した。最後にシミュレーションによる評価と提案手法の有効性を示し、考察を行った。

今後の課題

今後の課題として挙げられる点は、シミュレーションの高精度化である。現在のシミュレーション環境では全ての命令レイテンシを１サイクルとしており、浮動小数点演算命令等、実際には数サイクルを要する命令も１サイクルで実行している。またキャッシュメモリはデータキャッシュのみをシミュレートしており命令キャッシュのシミュレートは行っていない。更にコンテクストスワップのオーバヘッドは現段階では大まかな見積もりで決定しており、の実設計に基づいた厳密なスワップオーバヘッドの決定が必要である。

(50)

謝辞

本研究を行うにあたり御指導、御鞭撻を頂いた北陸先端科学技術大学院大学情報科学研究科田中清史助教授に深く感謝するとともに、ここに御礼申し上げます。

適切な御意見、御助言を頂きました本学の日比野靖教授、井口寧助教授に誠に深く感謝いたします。

多種多様な疑問や問題に対して親切なアドバイスをして頂いた請園智玲氏、今井俊晴氏、島田信行氏、高橋礼彦氏、南里洋亮氏、森田充氏、その他貴重なご意見、討論を頂きました田中研究室の皆様をはじめ多くの方々に対して厚く御礼申し上げます。

(51)

参考文献

+* 7*$=! *#>*#(?56*,"70>- "022" 0&,0,5

)" ;5$,1 "022"#+ # "0") ,& ,& 1*+2%?5#

?!,& 0&,0,5 *#( 11$0*,"#2 ") ,& =@ ;5$,1 "022" "!15,

'2,! # "0") @ "$5! 1*+2 % 5+

;A5$$2# ?@++ 2 *#( =;' !5$,*#"52 ;5$,,& *(#+ ;*/!>#+

#%&1 * *$$$2! # "0") ,& #( 1*+2 % ?5#

A*#*3* *2, "#,/, 7,0&#+ 6' = * 0&0*$ A*23 $$"0*,"# *#( -0"#:+%

5 *6$ *0& # "0 ") #, #*,"#*$ B" 32&"1 "# ##"*, 0&,0,5 )"

5,5 .# *,"# =+&% )" !*#0 "022" *#( '2,!2 1*+ % ?5$'

- #, #*,"#*$ #0 A& - 0&,0,5 ;*#5*$ #,0 =*$$ C11

*(($ - D?

;0;"&*# A& !" " , *# 3 #$2 0"!15, ,2, ") ,& !5! %

0*$ 1 )" !*#0 *+ *7 #0 !" D*,"#*$ *6" *," ' !"

A0& 1C-% 0

Japan Advanced Institute of Science and Technology