二項順序関係により投機的メモリアクセスを制御するキャッシュシステム

全文

(1)計算機アーキテクチャ 150−８（２００２．１１．２８）. 二項順序関係により投機的メモリアクセスを制御するキャッシュシステム中村誠∗. 平木敬†. マルチプロセッサ上でスレッドを投機実行するシステムにおいて、プロセッサ間でスレッドの依存関係を満たしつつメモリアクセスを効率良く投機的に実行する機構がプログラムの高速化にとって重要である．本稿では，投機的データの二項順序関係を各キャッシュにおいて分散的に管理すれば，スレッド間の依存関係を解決できる事を示し，投機的データの順序関係をメモリアクセス時に各プロセッサが定数時間で判定でき，依存関係の投機的データによる解消および投機的データの書き戻しの遅延を実現した投機的メモリアクセスを処理する一貫性プロトコルを拡張したキャッシュ機構およびその実装方法を提案する．. Cache Mechanism supporting speculative memory access using binary relationship Makoto Nakamura‡ and. Kei Hiraki§. Efficient speculative memory access is the key for the Thread-Level Speculation on multiprocessor system while the thread dependency is preserved among processors. We show that managing binary relationship for the speculative data in each cache is sufficient to resolve thread dependency, and have proposed a cache mechanism with extended coherence protocol and the implementation that supports speculative memory access and is able to resolve dependency by speculative data and to delay the writeback of speculative data.. 1. はじめに. 昨今の半導体の製造技術の進歩に伴い，チップマルチプロセッサ (CMP) や Simultaneous Multithreading(SMT) プロセッサが実装され，1 チップ内で複数のスレッドが並列実行されるようになった．CMP や SMT プロセッサ上で実行されるスレッドは，複数チップで構成されたマルチプロセッサシステム上で実行されるスレッドよりも高速にスレッド間で通信する事が可能である．この特徴を生かし CMP 上で逐次プログラムの実行を高速化するために，動的なスレッドの並列性が注目されている．動的なスレッド解析により，コンパイラによる静的な解析だけでは並列化が困難なプログラムの並列化が可能となり，スレッドを投機的に並列実行するプロセッサアーキテクチャが提案されている [4, 9, 7, 6, 11, 10, 1] ．今日主流の命令の並列性を利用するプロセッサアーキテクチャでは，資源を有効活用するために命令の投機実行を行っているが，単一プロセッサ内で実行される命令，主に分岐命令とメモリアクセス命令の依存関係を予測し投機している．一方，逐次プログラムからスレッドを抽出し並列実行するプロセッサアーキテクチャでは，異なるプロセッサで実行されるスレッド間の依存関係の予測し投機を行うため新たな手法が必要である．スレッド間のレジスタ上での依存関係は命令列の解析により解決できる．一方，スレッド間のメモリ上での依存関係については，アドレス空間全体を対象とする解析が困難であるため，依存関係がないと予測しメモリアクセスを投機的に実行し，スレッドの並列性を最大限抽出しようとして ∗ † ‡ §. 東京大学情報基盤センター東京大学大学院情報理工学系研究科. Information Technology Center, the University of Tokyo Graduate School of Information Science and Technology, the University of Tokyo. いる．この時，投機的なメモリアクセスを効率良く処理する事がマルチスレッドのプロセッサ高速化の鍵となる．本稿では，投機的に実行されるメモリアクセスを既存のプロセッサアーキテクチャ，特にキャッシュ機構を拡張する事で効率的に処理する方法を提案し，シミュレータを用いて評価する．. 2. スレッドの投機実行モデル. 逐次プログラムからの動的なスレッドの投機並列実行を行うプロセッサアーキテクチャでは，逐次のプログラムのループやサブルーチン呼出しのように，制御が分岐命令の分岐先に移った後，分岐命令の後続命令に復帰する構造に着目し，分岐先命令ブロックと後続命令ブロックをスレッドとして抽出する．抽出されたスレッドは本来逐次に実行されると仮定して生成されたコードであるため，依存関係にある命令が別のスレッドに含まれている可能性がある．抽出されたスレッドには，実行が確定した時点では逐次プログラムにおける分岐依存関係に従って実行時に全順序が付けられる．この順序関係が実行時の動的依存関係に対応し，スレッド間でのデータ依存関係の判定の基礎関係になる．以後，あるスレッドに対して先に実行されるべきスレッドを先行スレッド，後に実行されるべきスレッドを後続スレッドと呼ぶ．また，スレッドの全順序関係に従って付けられる番号を” スレッド番号” と呼ぶ．マルチプロセッサ上でスレッドは複数のプロセッサに分配され投機実行される．実効サイズがプロセッサの命令ウィンドウよりも大きなスレッドを投機の対象とするため，プロセッサは投機状態にあるスレッドに含まれる命令の実行を内部的に確定する必要がある．プロセッサはレジスタやキャッシュの値を投機的に扱う必要がある．さらに，スレッドの並列度を上げるために，個々のプロセッサは同時に複数のスレッドを投機実行する．. −35− 1.

(2) スレッドの投機実行時にはメモリアクセスの実行に対して次の 3 つの拡張をそれぞれ施す事で，これらの条件を満たす事ができる．. Processor. ld A. ld A st buf $. st buf. st buf. IPC1. $. i.（a）依存関係の検出のため，プロセッサはロードのアドレスを記録し，ストアのアドレスを他のプロセッサに通知する．依存関係の違反は，記録したロードアドレスに対して，先行スレッドから通知が来た場合として検出でき，スレッドの相対的な順序関係で判定が可能である．（b）依存関係の解決のため，プロセッサはストアのアドレスを記録し，後続スレッドでロードが実行された場合には，依存関係を満たすために次項で説明するキャッシュにコミットされた結果をフォワードする．この時，ストアされたデータを持つ先行スレッドのうちロードに対して最新のデータを有しているスレッドを判定する必要がある． ii. ストアは結果をキャッシュにのみコミットし，投機が失敗した場合には，キャッシュ上のデータを無効にする事で，実行を取り消す事ができる． iii. 投機が成功した後にキャッシュにコミットされている結果をメモリにコミットする．生成依存関係を満たすためには次の 2 つの方法が考えられる．（a）投機の成功が確認された時にスレッド単位で逐次にストアの結果を反映する [4, 7, 6]．逐次にデータをメモリに書き戻す事で生成依存関係を満たす事はできるが，オーバヘッドが大きく，この操作によってバスが占有され，他のスレッドの実行を阻害する．（b）投機が成功した後初めてアクセスされた時に最新のデータであるかを確認する．データのメモリへの書き戻しをアクセス時に遅延および分散させる事ができるため，他のスレッドの実行を妨げず，投機の成功時にメモリ操作に伴うオーバヘッドをなくす事ができる．本稿では上記方法を実現する方式を提案する．. $ IPC2. (a). (b). Shared Bus. 図 1: 依存関係の解決. 我々は，この節で述べたスレッドの投機実行モデルを用いたプロセッサにおいて，メモリアクセスを投機的に行う事を可能とするキャッシュ機構を実現する． 2.1 スレッドの投機実行における問題点マルチプロセッサの各プロセッサにスレッドを分配し，投機に並列実行するシステムでは，各プロセッサで実行されるスレッド間の依存関係を解決するために，プロセッサを跨いだ依存関係の検出および解決機構が必要である．レジスタ値に関する依存関係の解決には，プログラムを解析し命令列を生成する方法 [1] および値予測を用いる方法が用いられている．一方，メモリに関しては実行時にハードウェアによる依存関係の検出および解決をする方法が用いられている [3, 2, 7, 5, 8]．命令の投機実行では一般に，プロセッサはスケジュール制御の一部としてキュー構造をしたストアバッファを用いて，メモリアクセス命令のコミット前の依存関係を管理している (図 1(a))．しかし，スレッドの投機実行では投機の確定までの時間が長く，さらにキュー構造を用いた依存関係の検出には full-associative な検索が必要であるため，実装には大量のハードウェア資源が必要であり，処理の遅延が大きい．また，ストアバッファは各プロセッサで独立に使用され，プロセッサ間で情報を共有する事はない．そのため，スレッド間の依存関係を検出するためには図 1(b) の IPC1 で示した各プロセッサのストアバッファ間に専用の通信機構を追加する必要がある．一方，従来のマルチプロセッサでは IPC2 で示した共有バス上で通信する事によってキャッシュ間でデータの一貫性を保っている．そのため，投機的実行によるプロセッサを跨ぐメモリデータの依存関係の検出および解消を実現するためには，ストアバッファを拡張するよりも，共有バス上の通信を拡張した方が，ハードウェアの追加量が少なく，命令の実行時間に与える影響が少ない． 2.2 投機的メモリアクセススレッドの投機実行がプログラムを逐次実行した場合と同じ結果を得るためには，プロセッサでのメモリアクセスの実行時には次の 3 つの条件を満たす必要がある．. 1. ロードはスレッドを逐次実行した場合に同一のアドレスに対して直前に実行されたストア値を読む．つまり，プロセッサは実行時にスレッド間の依存関係を (a) 検出および (b) 解決する必要がある． 2. 投機が失敗した場合にはストアの実行結果が取り消せる． 3. 投機が成功した場合にはストアの実行結果をメモリに反映する．この時，生成依存関係を満たすために，後続スレッドによる結果を上書きしてはいけない．. 3. 提案方式. 前節で述べたように，並列に投機実行されるスレッド間のメモリに関する依存関係を効率良く処理するためにはキャッシュおよびキャッシュの一貫性維持のための通信プロトコルを拡張する必要がある．これまでにマルチプロセッサのキャッシュ一貫性プロトコルを拡張してスレッドの投機実行に伴うメモリアクセスを処理する方法が提案された [2, 7, 5, 8] ．しかし，集中的制御機構によるリンクリストを用いた投機的データの管理 [2, 7, 8] や，スレッドの投機成功時の投機的データのバーストな書き戻し [5, 8] という問題点がある．我々は，キャッシュ間の投機的データの全順序関係を集中的に管理するのは冗長であり，2 つのキャッシュ間の投機的データの順序関係を把握すれば十分である事に注目した．投機的データの二項順序関係を個々のキャッシュにおいて分散的に管理する事により，投機的データの順序関係を定数時間で判定可能という特徴を持ったキャッシュ機構を提案する．この方式は，集中的な管理機構を用いる場合に比べ実装に必要なハードウェア量が少なく，処理にかかる遅延が小さい．また，投機的データのキャッシュ間でのフォワードによりスレッド間の依存関係の投機的解消が実現でき，投機成功時に投機的データの書き戻しを必要としない特徴を持つ．. 2 −36−.

(3) 3.1 基本アイディアストアバッファでの依存関係の検出および解決の機能と共有バス上の通信によるキャッシュ一貫性維持の機能を融合させ，スレッドの投機実行時の依存関係の検出および解決をするため，キャッシュおよびスヌープ型のキャッシュ一貫性プロトコルを拡張する．2.2 節で述べた投機的メモリアクセスの拡張を次のようにキャッシュ機構に対して適用する．. Time. T1. T2. ld A (a). 態を拡張してロードを記録する．先行スレッドからの通知としては invalidation 要求を利用する．（b）プロセッサの private キャッシュのブロック状態を拡張してストアを記録する．後続スレッドからのリード要求に対してキャッシュにのみコミットされた結果をフォワードする．この時メモリを更新しない． 2. 投機の成功が確定するまで変更されたブロックをメモリに書き戻さない． 3.（a）投機の成功が確認された時にキャッシュにコミットされていたストアの結果をすべてメモリに書き戻す．この操作をスレッド単位で逐次に行う．（b）投機時のデータの順序関係を記録しておき，投機が成功した後初めてアクセスされた時にバス要求を送る事で最新のデータを判定する．. 1. Pk がリード要求を出す． 2. P j は T ID j < T IDk ならば acknowledge を返す． 3. (2) で acknowledge を返したプロセッサ数を n とし，その m 番目のプロセッサを Pkm とする．（a）n = 0 の場合，Pk がメモリからデータを読み込む．. T4. st A. 1.（a）プロセッサの private キャッシュのブロック状. 3.2 二項関係を用いた依存関係の判定投機的メモリアクセスをキャッシュ一貫性プロトコルを拡張して処理する場合，スレッドおよびスレッドからのメモリアクセスの順序関係をバス要求時を効率良く判定する必要がある．スレッドの投機実行では分岐依存関係によりスレッドに全順序関係が存在し，メモリアクセスについても実行時にスレッド単位で全順序関係を把握する事によって依存関係を検出できる．しかし，実行時に順不同で実行されるメモリアクセスの全順序関係を更新するには，ベクトルを用いて管理した場合には更新を行うため，リストを用いて管理した場合には検索を行うためにプロセッサ台数に比例した回数の操作が必要である．全順序を管理するには情報を集中的に処理する必要があるが，中央主権的な機構では処理が集中しボトルネックとなり，各プロセッサで情報を管理するとプロセッサ台数の記憶容量が必要である． 2.2 節で述べたように投機実行されるスレッド間の依存関係を解決するためには，あるスレッドからのバス要求に対して最新のデータを持っているスレッドのみを判定する事ができればよい．バス要求時にバス要求とキャッシュブロックの順序関係を判定するため，投機的メモリアクセスに伴うバス要求および acknowledge にはスレッド番号を付加し，キャッシュブロックのスレッド番号と比較する．システムが N 個のプロセッサ Pi (1 ≤ i ≤ N) で構成され，Pi で投機実行しているスレッド番号を T IDi とする．バス要求に対してデータを供給するためのアルゴリズムを以下に示す：. T3. st A. P1. P4. P3. P2. State TID Data. O 1 d1 Time. O 3 d3. I. I. 5JCTGF$WU. 1.Req4 2.Ack1. 2.Ack3 3.Effective (b). 4.Forward3. 図 2: 投機的な依存関係の解決. （b）n = 1 の場合，Pk1 が Pk にデータをフォワードする．（c）n ≥ 2 の場合，Pkm は k0 = k1 , k2 , ..., km−1 , km+1 , ..., kn に対して T IDkm > T IDk0 ならば， Pkm が Pk にデータをフォワードする．図 2 では，P1 , P3 が acknowledge を返し，(3c) の判定によって P3 がデータを P4 に供給する．上記アルゴリズムにおいて，各プロセッサ Pi は T IDi < T ID j または，T IDi > T ID j の比較のみを行う．すなわち，他のスレッドとの相対的な順序関係のみを判定する．従って，各プロセッサでは他のプロセッサで実行されているスレッドとの二項順序関係を記録すれば，メモリアクセスの依存関係を解決できる． 3.3 キャッシュ一貫性スキームの拡張依存関係を検出するために，キャッシュブロックの状態を拡張して投機的メモリアクセスのロードとストアを別々に記録する．また，通常のメモリアクセスに対するバス要求とは区別するため，投機的メモリアクセスに対しては別の種類のバス要求を用いる．依存関係検出のため，各プロセッサは invalidation 要求に対して要求が先行スレッドからの要求であるかを判定する．スヌープが投機的にロードしたと記録されたブロックにヒットした場合には，プロセッサは依存関係に違反してロードを実行した事になり，スレッドの投機実行を取り消す．投機的に依存関係を解消するため，各プロセッサはリード要求に対して前節で述べた方法によって要求に対して最新のデータを持っているか判定する．要求に対する最新のデータを持っていると判定したプロセッサは，データを要求元のプロセッサにフォワードする．この時，フォワードされるデータでメモリを更新できないので，フォワード元のプロセッサは該当ブロックの状態を shared dirty にする．フォワード元のスレッドの投機が失敗した場合には，フォワード元のデータに加え，フォワードされたデータを無効化する必要がある．要求元のプロセッサは該当ブロックをローカルに投機的に変更されたと同様に扱い，フォワード元のスレッドが投機に失敗した事が通知され. 3 −37−.

(4) た場合には，プロセッサは要求元のスレッドの投機失敗と判定する． 3.4 生成依存関係の回避生成依存関係を満たすため，スレッドの依存関係の順序に従ってスレッド順に投機的なストアの結果をメモリに反映させる．しかし，この方法では 2.2 の (3a) で述べたように，投機成功時のバスが占有され処理のオーバヘッドが大きい．成依存関係を満たしながら投機的データの書き戻しを遅延させメモリを更新すれば問題を解決できる．しかし，投機時にはデータの順序関係に関する情報は保持しているが，投機が成功すると，その情報を消去するため，単純には遅延させられない．プロセッサは，保持する投機的データの別のインスタンスを他のプロセッサが生成した場合には，投機的データの順序関係を Versioning Bufffer と呼ぶバッファに保持しておく．投機の成功後に初めてアクセスされた時に Versioning Buffer を読み，他のプロセッサの投機が成功したか確認し，当該ブロックのデータが最新であるか判定する．後続スレッドにより投機的データが他に生成された場合で，そのスレッドの投機が成功していた場合には，当該ブロックを無効にし，データをフォワードあるいはメモリから読み込む．後続スレッドの投機が失敗していた場合や先行スレッドにより投機的データが他に生成された場合には，該当ブロックは最新であり，プロセッサは所有権を有する．. 4. 実装. 4.1 スレッド操作と二項関係のマスクによる管理各プロセッサで実行されているスレッドの順序関係および投機の成否を把握するため，プロセッサはスレッド操作時に，次の 3 つの通信を行う．. • スレッドの投機開始時に他のプロセッサにスレッド番号を通知する．. • すべての先行スレッドの投機が成功し，さらに自. Processor1 Processor2. #1. #3. #4. ]. ACK✢. Shared Bus 図 3: acknowkedge 信号線の構成. レッドであるか判定できる． 4.2 共有バスの構成とバス要求の拡張共有バスはアドレスバスとデータバス，さらに調停，スヌープ結果，acknowledge，negative acknowledge 用の信号線から構成される．3.2 節で述べたように複数の acknowledge が単一の要求に対して返される可能性があるため，図 3 のように acknowledge 信号線は複数本とし各線に異なるプロセッサを割り当てて使用する．複数の acknowledge をビットベクトルとして扱う事が可能である．投機的メモリアクセス時には，通常のバス要求とは別のバス要求を使用するが，スレッドの開始時にプロセッサと実行中のスレッドの対応を Thread Mask に記録したため，投機的メモリアクセスに伴うバス要求にスレッド番号を付加する事なく，メモリアクセスと投機的データの依存関係を判定できる．また，投機成功後のアクセス時に投機的データがまだ有効か確認するためのバス要求を追加し，Versioning Buffer にエントリがあった場合に使用する． 4.3 キャッシュブロックの状態の拡張投機的データのフォワードを行なうためキャッシュの状態は MOESI 方式を拡張し，以下の MOESI と直交する状態ビットを追加する．. スレッドの実行が終了した時，つまり，投機の成功が確定した時に，他のプロセッサにスレッド番号を通知する． • スレッドの投機が失敗した時に他のプロセッサにスレッド番号を通知する．バス要求にスレッド番号を付加するのではなく，スレッドの投機開始時にプロセッサとスレッドの対応関係を記憶する．さらに，他のプロセッサでのスレッドの投機開始時に自スレッドとの二項順序関係を予め計算し記憶する．スレッドの二項順序関係の記録には，ビットマスク構造をした Thread Mask を用いる．Thread Mask の各ビットは他のプロセッサで実行されているスレッドとの順序関係を示している．具体的には，システムが N 個のプロセッサ Pi (1 ≤ i ≤ N) で構成され，Pi で投機実行しているスレッド番号を T IDi とすると，P j の Thread Mask(b1 b2 ...bN ) のビット bi は，T ID j < T IDi ならばセットされる．従ってスヌープ操作時は，バス要求を出したプロセッサに対応する Thread Mask のビットを読むだけで順序関係の判定ができる．また，投機的データのフォワードにより依存関係を解消した場合には，フォワード元のスレッドの投機の失敗をフォワード先のスレッドの投機の失敗の原因と判定する必要があり，ビットマスク構造をした Forward Mask を用いる．Forward Mask の各ビットは他のプロセッサで実行されているスレッドがフォワード元のスレッドである事を示している．他のプロセッサからスレッドの投機の失敗が通知されたときには，そのプロセッサに対応する Forward Mask のビットを読むだけでフォワード元のス. #2. Processor3 Processor4. • SpL は該当ブロックに対して投機的に読んだ事を示す状態ビットで，投機的ロードを行なった時にセットする．スレッドの投機が成功した時および投機が失敗した時にリセットする． • SpM は該当ブロックに対して投機的に変更されたことを示す状態ビットで，投機的ストアが行なわれた時および投機的データがフォワードされた時にセットする．スレッドの投機が成功した時にリセットする．投機が失敗した時に，SpM がセットされたブロックをすべて invalidate する． • Stale は実行中のスレッドの投機が成功した時に invalidate すべき事を示す状態ビットで，より投機的なスレッドがストアを行なった時にセットする．つまり，Stale は現在実行中のスレッドに対しては有効であるが，同一プロセッサ上で次に実行されるスレッドに対しては有効ではない可能性がある事を示している．投機の失敗を検出するために SpL がセットされたブロックの invalidation を投機が成功するまで遅らせるために使用する． • Commit と Squash はオプションの状態ビットで， Commit は投機が成功した時にセットされ，Squash は投機が失敗した時にセットされる．ただし， Commit と Squash は相互排他的にセットされ，投機の成功や失敗時に行なわれる状態の遷移を投機後のアクセス時に遅延するために使用する．. 4.4. Versioning Buffer. Versioning Buffer は複数のキャッシュに同時に存在する投機的データを管理するために使用される．Versioning. 4 −38−.

(5) Buffer のエントリはアドレスタグとスレッド番号と後続. 資源. パラメータ. スレッドによる投機的データが他のプロセッサに存在する事を示すビットマスクにより構成される．後続スレッドからの投機的ストアに伴うバス要求により snoop されたブロックが投機的に変更されている場合，Versioning Buffer にそのブロックのためのエントリを割り当て，要求を出したスレッドに対応するビットをセットする．投機的ストアに伴うバス要求に対して投機的フォワードにより fill された場合にも Versioning Buffer にエントリを割り当てる．投機が成功した後にはじめてアクセスされる時に update 要求をバスに出し，より投機的であったデータからの acknowledge があった場合には invalidate する． 4.5 複数のスレッドを同時に投機実行するプロセッサに対する拡張プロセッサが M 個のスレッドを同時に投機実行する場合，キャッシュブロックの状態ビット SpL, SpM, Commit, Squashed をブロック毎に M 組ずつ (S pLi , S pMi , Commiti , S quashedi ) 用意し，プロセッサが内部で i 番目のスレッドを実行している時は，S pLi , S pMi をブロックの状態ビットとして使用する．また，Thread Mask を (b11 b12 ..bi j ..bN M ) と拡張し，bi j はプロセッサ Pi の j 番目のスレッドとの順序関係を示すビットとする．そして，バス要求にプロセッサ内部でのスレッドの番号を付加する事で対応する．同一プロセッサ内で投機実行されたスレッドが同じアドレスに対してストアをしようとした場合，異なるデータとして処理しなければならない．しかし，従来のキャッシュは 1 つのアドレスに対して単一のブロックしか保持しない．そこでプロセッサは，スレッドがストアしようとした時に，同一ブロックが先行スレッドにより変更されていた場合にはスレッドをサスペンドし，後続スレッドにより変更されていた場合には該当ブロックを無効とし，後続スレッドの実行を取り消し，実行中のスレッドの実行を続ける．このようにする事によって，キャッシュのブロックの割当方針を変更しないで対処する事が可能である．. Reorder Buffer. 64 エントリ 32KB, 2-way 32KB, 2-way, 2 バンク, 1 cycle 8 バンク, 10 cycle. 性能評価. 任意個の要素プロセッサとメモリコントローラがバスを共有している CMP アーキテクチャをモデル化したシミュレータを用い性能を評価した．要素プロセッサは MIPS-II に準拠した命令セットを持ち，private な 1 次キャッシュを備える．アーキテクチャは R10000 [12] と同様 1 サイクルに 4 命令まで同時に発行できる out-oforder なスーパースカラを用いた．表 1 にハードウェア資源の設定を示す．実行時ループ再構成方式 [1] に基づいてスレッド (ブロック) を投機実行する機能を持ち，各プロセッサは同時に 4 スレッドまで投機実行可能である．実行時ループ再構成方式は逐次プログラムを実行時にループ部分を投機並列実行する投機的 SPMD 形式のスレッドに再構成するため，各イテレーションは規則的にスレッドに割当てられる．メモリアクセスは投機的に行われ，提案したキャッシュ機構を用いて処理する．シミュレーションでは共有バスはスプリット・トランザクションを用い，使用の競合をモデル化した．バスアクセス用のバッファと Versioning Buffer のエントリ数は任意個である． SPEC CPU95 ベンチマークの中から compress∗1 , go∗2 ,. 表 1: Configuration Parameter. ታⴕᤨ㑆 E[ENG. /. . /. . /. . EQORTGUU. IQ. VQOECVX. 図 4: 実行時間. tomcatv∗3 を実行し性能を評価した．図 4 にプロセッサ台数を変化させた時の実行時間を示す．明かに，プロセッサ台数の増加に伴い性能が低下する．バスの使用率の時間による変化を compress は図 5，go は図 6，tomcatv は図 7 にそれぞれ示す．スレッドの投機実行を行う事によってバスの使用が著しく増加している事が判る．しかし，今回用いたプログラムの投機実行の対象となったループの隣合うイテレーション間で同一のキャッシュラインに対してストアを実行するために false sharing が発生し投機が失敗し，投機が失敗したスレッドによるバスの使用によってプログラム全体の実行が遅くなったと考えられる．. 関連研究. 6. Multiscalar の ARB [3] ではプロセッサが multi-value の共有キャッシュを用いて投機的メモリアクセスの履歴を記録するが，メモリアクセスの latency が長く，バンド幅が必要で，スレッドの投機成功時に投機的データを書き戻す必要があり，高速化の実現が不可能である． Multiscalar の SVC [2] は private キャッシュを用いて投機的メモリアクセスの履歴を記録し，キャッシュ一貫性 100 1 50 0 100 2 ࡃࠬ૶↪₸ . 5. 命令キャッシュデータキャッシュメモリ. 50 0 100 4 50 0 100 8 50 0 0. 0.5M. 1M 1.5M ᤨ㑆 E[ENG. 2M. 図 5: compress 実行時のバス使用率. ∗1. 入力データは”100 q 2131” で圧縮/ 解凍は 3 回実行 ∗2 入力データは”5 5”. ∗3. 5 −39−. 入力データのサイズは 64x64. 2.5M.

(6) 100. 本稿で述べた実装法を用いる事により，遅延が少なく定数時間の判定を可能とした．さらに，提案した方式では投機的データのフォワードによる依存関係の解決，投機的データの書き戻しの遅延を実現できるため，スレッド並列実行の高速化が実現できる．しかし性能測定の結果，従来の逐次プログラムを用いた場合，プロセッサ台数を増加させ並列度を上げると性能が低下する事が判った．対象としたプログラムのループで隣合うイテレーションが投機的データの生成位置に関して false sharing の状況にある事が性能低下の原因である．投機的メモリ共有の実現に向けて，今後は投機的に生成されたデータの管理単位を小さくする事を検討し，その場合のキャッシュ機構への副作用を検証する．. 1 50 0 100. ࡃࠬ૶↪₸ . 2 50. 0 100 4 50. 0 100 8 50. 参考文献 0 0. 0.5M. 1M ᤨ㑆 E[ENG. 1.5M. 2M. 図 6: go 実行時のバス使用率 100 1 50 0 100. ࡃࠬ૶↪₸ . 2 50. 0 100 4 50. 0 100 8 50 0 0. 2M. 4M 6M ᤨ㑆 E[ENG. 8M. 10M. 図 7: tomcatv 実行時のバス使用率. プロトコルを利用して集中的機構が投機的データの全順序関係をリンクリストを用い管理するため，依存関係判定の latency が長く高速化が不可能である． Hydra [7] は private キャッシュを write-through にし，共有バスと L2 キャッシュの間にスレッド単位に割当てたバッファに投機的データを記録する．この方式では Write 共有バスの競合とバンド幅が問題である． TLDS [5] は invalidation 方式のキャッシュ一貫性プロトコルを拡張したが，投機的データのフォワードが不可能であり，スレッドの投機成功時に shared な状態の投機的データの書き戻しが必要であり，高速化の実現に問題がある． I-ACOMA の MDT [8] は共有テーブルで投機的データの管理をするため，メモリアクセスの平均 latency が長く，スレッドの投機成功時に投機的データを書き戻す必要があり，高速化が不可能である．. 7. おわりに. 本稿では，二項関係を用いて順序関係を管理する手法を用い，マルチプロセッサ上でスレッドの投機実行にともなう投機的メモリアクセスを実現するキャッシュ機構を提案した．二項関係を用いる事により，個々のキャッシュにおいて順序関係の判定を分散して実現可能であり，. [1] J. Tamatsukuri, T. Matsumoto, and K. Hiraki. “An Architecture for Speculative Parallel Execution with Loop Analyzer”. IPSJ SIGNotes ARC-119-011. August 1996. [2] S. Gopal, T.N. Vijaykumar, J. E. Smith and G. S. Sohi. “Speculative Versioning Cache”. Proc. of the 4th Int. Symp. on High-Performance Computer Architecture (HPCA4), Feb 1998. [3] M. Franklin and G. S. Sohi. “ARB: A Hardware Mechanism for Dynamic Reordering of Memory References”. IEEE Transactions on Computers, Vol. 45, No. 5, May 1996. [4] G. S. Sohi, S. Breach, and T. N. Vijaykumar. “Multiscalar Processors”. Proc. of the 22nd Int. Symp. on Computer Architecture (ISCA’95), June 1995. [5] J. G. Steffan, C. B. Colohan, A. Zhai and T. C. Mowry. “A Scalable Approach to Thread-Level Speculation”. Proc. of the 27th Int. Symp. on Computer Architecture (ISCA’00), June 2000. [6] J. G. Steffan and T. C. Mowry. “Architectural Support for Thread-Level Data Speculation”. Technical Report CSRI-TR-350, Computer Science Research Institute, University of Toronto, February 1997. [7] L. Hammond, M. Willey, and K. Olukotun. “Data Speculation Support for a Chip Multiprocessor”. Proc. of the 8th Int. Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VIII), October 1998. [8] M. Cintra, J. Martinez and J. Torrellas. “Architectural Support for Scalable Speculative Parallelization in Shared-Memory Systems”. Proc. of the 27th Int. Symp. on Computer Architecture (ISCA’00), June 2000. [9] V. Krishnan and J. Torrellas. “A Chip Multiprocessor Architecture with Speculative Multithreading”. IEEE Transactions on Computers, Vol. C-48, No. 9, September 1999. [10] P. Marcuello and A. Gonzalez. “Clustered Speculative Multithreaded Processors”. Proc. of the 1999 Int. Conference on Supercomputing (ICS’99), June 1999. [11] H. Akkary and M.A. Driscoll. “A Dynamic Multithreading Processor”. Proc. of the 31st Int. Symp. on Microarchitecture (MICRO31), November 1998. [12] K. C. Yeager. “The Mips R10000 Superscalar Microprocessor”. IEEE Micro, Vol. 16, No. 2, April 1996.. 6-E −40−.

(7)