CoreSymphonyにおける命令ステアリングの高性能化

東京工業大学工学部
学士論文
CoreSymphony における
命令ステアリングの高性能化
指導教員 吉瀬 謙二
准教授
平成 24 年 2 月
提出者
学科
情報工学科
学籍番号
08_03584
氏名
上野 貴廣
指導教員 印
学科長 認定印
平成 24 年度 学士論文内容梗概
CoreSymphony における
命令ステアリングの高性能化
指導教員
吉瀬 謙二
准教授
情報工学科
08_03584 上野貴廣
「半導体チップの集積度は、およそ 18 カ月で 2 倍になる」
ムーアの法則が提唱されて以来，法則通りではないものの，チップ上のトランジスタ数
は指数オーダーで増加を続け, それに伴い CPU の性能も飛躍的な成長を遂げた．しかし，
このまま増え続けるとすればいずれその大きさが原子の直径を割るため，この法則の破綻
は予想されていた．だが，それよりも先に CPU の発展において，問題が現れた．シング
ルコア・プロセッサと呼ばれる従来の CPU は，増加するトランジスタを 1 つのコアの機
能拡張に充てることで，性能向上を実現させてきた．そして 1 コアの集積度が高まるに伴
い，コアの発熱や配線遅延などによる性能向上の妨げが無視できなくなった．
シングルコアに代わって，今日，主流となっている CMP(Chip-Multi Processor) とは，1
つのチップ上に複数のコアを搭載する技術である．CMP では並列に実行できるスレッド
を複数のコアが並行して行うことで並列処理性能を高めている．しかし，各コアの逐次処
理性能の限界が全体の性能向上の妨げになる, という課題を抱えている．
その解の 1 つとして，CMP において複数のコアを必要に応じて融合させ，逐次処理性能
の向上を図る「コア融合型アーキテクチャ」というアプローチが提案されている．その 1
つとして,「コア間の通信を極力少なくする」というコンセプトの CoreSymphony アーキテ
クチャがある．
本論文では，CoreSymphony において，フェッチが完了した命令を各コアに割り振る「命
令ステアリング」と呼ばれるステージに着目する．現状の命令ステアリングでは無駄が生
じてしまう箇所を是正する構成を提案する．また，このアルゴリズムをシミュレータ上で
実装し, 従来の命令ステアリングと比較して評価する．シミュレータは独自開発のサイク
ルレベルシミュレータ「SimMIPS」上で CoreSymphony アーキテクチャを動作させる．ベ
ンチマークには SPEC CINT2006，CFP2006 などから 20 種を用いた．性能評価の結果，4
コア協調時で平均 1.3% の IPC が向上することがわかった．．
目次
第1章
緒論
1
1.1
研究の背景と目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Out-of-Order プロセッサ
3
命令レベル並列性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
第2章
2.1
2.2
第3章
2.1.1
依存とハザード . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.2
依存とデータハザード . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1.3
制御依存制約と分岐予測器 . . . . . . . . . . . . . . . . . . . . . .
5
2.1.4
資源制約とパイプライン . . . . . . . . . . . . . . . . . . . . . . . .
5
Out-of-Order プロセッサ . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2.1
分岐予測器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2.2
レジスタリネーミング . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2.3
命令スケジューリング . . . . . . . . . . . . . . . . . . . . . . . . .
9
CoreSymphony アーキテクチャ
10
3.1
コア融合アーキテクチャ . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.2
CoreSymphony アーキテクチャ . . . . . . . . . . . . . . . . . . . . . . .
11
3.3
リーフノードステアリング . . . . . . . . . . . . . . . . . . . . . . . . . .
12
第4章
4.1
3.3.1
従来のステアリング . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.3.2
リーフノードステアリングの振る舞い . . . . . . . . . . . . . . . .
15
3.3.3
課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
命令ステアリング BLNS の提案
19
提案手法の方針 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
i
4.2
提案手法のアルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.3
提案手法の性能向上の説明 . . . . . . . . . . . . . . . . . . . . . . . . . .
20
評価
24
5.1
評価環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
5.2
比較対象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
5.3
ベンチマーク . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
5.4
評価結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
5.5
考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
第5章
5.5.1
第6章
結論
命令数を考慮した考察 . . . . . . . . . . . . . . . . . . . . . . . . .
28
31
謝辞
32
参考文献
33
ii
図目次
2.1
パイプライン . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
パイプラインによる prog1 の実行例 . . . . . . . . . . . . . . . . . . . . .
7
2.3
OoO プロセッサのブロック図 . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1
CoreSymphony のフロントエンド . . . . . . . . . . . . . . . . . . . . . .
11
3.2
命令列のデータフローグラフ . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.3
Modulo-N ステアリングによる割り振り . . . . . . . . . . . . . . . . . . .
14
3.4
依存ベースステアリングによる割り振り . . . . . . . . . . . . . . . . . . .
15
3.5
LNS が生成する部分木 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.6
LNS による割り振り . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.7
LNS により偏りが生じる例 . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.8
偏りが改善された例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.1
既存手法により割り振られた結果:命令の重複を考慮する場合 . . . . . . .
21
4.2
提案手法により割り振られた結果:命令 10 の部分木までを割り振った状態
22
4.3
提案手法により割り振られた結果:命令の重複を考慮する場合 . . . . . . .
23
5.1
BLNS と LNS の IPC の比較と向上比 . . . . . . . . . . . . . . . . . . . .
26
5.2
整数演算ベンチマークの IPC の比較 . . . . . . . . . . . . . . . . . . . . .
27
5.3
浮動小数点演算ベンチマークの IPC の比較 . . . . . . . . . . . . . . . . .
27
5.4
mcf における FB 毎のコアの命令数の最大値の変化 . . . . . . . . . . . . .
29
5.5
gromacs における FB 毎のコアの命令数の最大値の変化 . . . . . . . . . .
29
5.6
FB1 つに含まれる命令数の平均と IPC の向上率 . . . . . . . . . . . . . .
30
iii
表目次
5.1
シミュレーションにおける主要なパラメータ． . . . . . . . . . . . . . . .
25
1
第1章
緒論
1.1
研究の背景と目的
1 つのの中に複数のコアを搭載するチップマルチプロセッサ(Chip-Multi Processor：以下
CMP と表記) は現在生産されている CPU のほとんどに用いられ，家庭用や業務用を問わ
ず広く普及しており今日の主流となっている．
1 つのチップに集積可能なトランジスタの数は今も年々増え続けている．CMP に対して
シングルコアプロセッサとも呼ばれる従来のプロセッサは，その増加するトランジスタを
その 1 つのコアの機能拡張に充てることで性能向上を実現させてきた．しかし，発熱や配
線遅延などの不可避な問題が生じたためそのアプローチに陰りが見えた．このため，1 チッ
プ上に複数コアを集積することにトランジスタを用いた CMP の手法が一般的となった．
CMP では依存しない並列に実行できるスレッド (スレッドレベル並列性) を複数の小規
模コアが並行して行うことで並列処理性能を高めている．しかし，依然として逐次処理性
能を求められる場面もあり，各コアの逐次処理性能の限界が全体の性能向上の妨げになる
場合があるという課題を抱えている．それを克服する試みとして，CMP において複数のコ
アを必要に応じて融合させ，逐次処理性能の向上を図るアプローチが提案されている．[1]
[2] [3] [4] [5] その一つとして「コア間の通信を極力少なくする」というコンセプトで提案
された CoreSymphony アーキテクチャ [6] がある．
本論文では CoreSymphony アーキテクチャのコアに命令を割り振る「命令ステアリン
グ」に着目する．CoreSymphony アーキテクチャで用いられている「リーフノードステア
リング」と呼ばれるステアリングで無駄が生じてしまう箇所を是正し，より効率的で性能
を向上させるステアリングを提案する.
第1章
1.2
緒論
2
本論文の構成
本論文の構成を述べる．第 2 章では本論文の前提となる Out-of-Order 実行とそれを実現
する Out-of-Order プロセッサを説明する．第 3 章では，CoreSymphony アーキテクチャの
説明，さらに着目する現状の命令ステアリング及びそれが孕む問題を説明する．第 4 章で
本論文の趣旨である効率的な命令ステアリングの構成を提案し，第 5 章にてその性能を評
価を行い分析する．最後に第 6 章で結論をまとめる．
3
第2章
Out-of-Order プロセッサ
本章では，本研究の前提となる命令レベル並列性 [7] やアウトオブオーダー実行の説明
をし，さらにアウトオブオーダープロセッサの構成を，フロントエンド中心に述べる．
2.1
命令レベル並列性
2.1.1 依存とハザード
以下のような命令列を持ったプログラムを考える.
prog1
prog2
I1 :
r1 = r1 + 1;
I1 :
r1 = r1 + 2;
I2 :
r2 = r2 + 2;
I2 :
r2 = r1 + 1;
I3 :
r3 = r3 + 2;
I3 :
r1 = r3 + 2;
I4 :
r4 = r4 + 1;
I4 :
r1 = r4 + 2;
この表記における,In とは n 番目の命令を，rn とは n 番目の論理レジスタを指す．また，
prog1 の I1 の命令の意味は「レジスタ 1 に 1 を加算し，レジスタ 1 に書き戻す」という意
味である．
プロセッサが命令を実行するとき，プログラム内の命令を出現した順序を変えることな
く，上から順に実行していく方式をインオーダー実行という．それに対してプログラム
の実行結果を変えない範囲で命令の順序を変えて実行することをアウトオブオーダー実
行(Out-of-Order:以下 OoO 実行) という．
第2章
Out-of-Order プロセッサ
4
prog1 は，実行する順番をどう変えても結果は変わらず，OoO 実行が可能である．また，
全ての命令を並列して実行することができる．それに対して prog2 はこのままでは並列し
て実行できる命令の組み合わせはない．この状態を prog1 は prog2 よりも「命令レベル並
列性(nstruction-level parallelism:ILP) が高い」という．
prog2 を OoO 実行しようと考えると生じる，ハザード(命令の実行順序を変えたために，
順序どおりに実行した場合と異なった実行結果になるという問題) について考える．
2.1.2 依存とデータハザード
真の依存と RAW ハザード
I1 と I2 に着目すると，I2 の実行に必要なレジスタ r1(「r1 は I2 のソースオペラン
ドである」という) は，I1 の命令によって書き戻されている (「r1 は I1 のデスティ
ネーションオペランドである」という)．I1 を実行する前に I2 を実行すると異なっ
た r1 の値が代入されてしまい，実行結果が変わってしまう．そのため I2 の実行は
I1 の完了を待たなければならない．
このように，ある命令のソースオペランドがそれより前の命令のデスティネーショ
ンオペランドであるとき，これを真の依存という．また，これによって発生するハ
ザードを RAW(read after write) ハザードという．
逆依存と WAR ハザード
I2 と I3 に着目すると，I2 のソースオペランドであるレジスタ r1 は，I3 のデスティ
ネーションオペランドになっている．
I2 を実行する前に I3 を実行すると，I1 によって得られた r1 の値を破壊してしまう
ため，実行結果が変わってしまう．そのため I3 の実行は I2 の完了を待たなければ
ならない．
このように，ある命令のデスティネーションオペランドがそれより前の命令のソー
スオペランドであるとき，これを逆依存という．また，これによって発生するハ
ザードを WAR(write after read) ハザードという．
出力依存と RAR ハザード
I3 と I4 に着目すると，I3 のデスティネーションオペランドであるレジスタ r1 が I4
のデスティネーションオペランドにもなっている．
このように，2 つ以上の命令がデスティネーションオペランドを共有しているとき，
これを出力依存という I3 を実行する前に I4 を実行すると，最終的に r1 に書き戻
2.1 命令レベル並列性
5
される値が I4 ではなく I3 になり，実行結果が変わってしまう．そのため I3 の実
行は I2 の完了を待たなければならない．また，これによって発生するハザードを
WAW(write after write) ハザードという．
これらのデータハザードは ILP を抽出する上での制約となる．そのうち真の依存だけは
解決することができない．しかし，逆依存と出力依存はレジスタの再利用により起こるハ
ザードであり，レジスタリネーミングにより解決できる．レジスタリネーミングとは，論
理レジスタを物理レジスタ (pn で表す) に置き換えることでハザードを回避する手法であ
る．prog2 の例で言うと，I2 と I3,I2 と I4,I3 と I4 はお互い依存の関係にあるが，
I2 :
r2 = r1 + 1;
I2 :
r2 = r1 + 2;
I3 :
r1 = r3 + 2;
→
I’3 :
p1 = r1 + 2;
I4 :
r1 = r4 + 2;
→
I’4 :
p2 = r1 + 2;
このように I3 の命令を p1,I4 の命令を p2 にマッピングすることで I2，I’3，I’4 間の依
存は全て解消され全て並列に実行できる．
2.1.3 制御依存制約と分岐予測器
prog3
I1 :
if(r1 == r2) goto L1;
I2 :
r1 = r2 + 2;
I3 :
r1 = r2 + 1;
L1:
上の命令で，I2 の命令が実行されるかどうかは，I1 の結果に依存している．そのため，
I2 は I1 が完了するまで実行できない．このように，分岐命令によって後続の命令の実行
が制限されることを制御依存制約といい，IPL 抽出の大きな妨げになる．この依存は分岐
予測器と呼ばれる機構を用いることで，ある程度緩和される．分岐予測器については 2.2.1
節にて説明する．
2.1.4 資源制約とパイプライン
prog1 の例をレジスタリネーミングを用いて実行する場合を考えてみる．
命令の実行には，IF(Instruction Fetch:命令の読み出し)，ID(Instruction Decode:命令の
第2章
Out-of-Order プロセッサ
6
解釈)，EX(Execute:演算の実行)，MA(Memory Access:ロード・ストアの実行)WB(Write
Back:レジスタに書き戻す) の 5 つのステージを経る．
このステージを流れ作業で複数ラインで行う手法をパイプラインといい，パイプライン
を持つプロセッサをスーパースカラプロセッサという．
図 2.1 でパイプラインの効率を説明する．前述の 5 つのステージが全て 1 サイクルを要
するとすると，パイプラインなし，演算器 1 つ (1-way) のプロセッサでは図 2.1 のように
5 サイクルを要して 1 命令を処理する．
パイプラインを持つ 1-way のプロセッサの場合では，最初の命令の IF ステージを終え
た後，次の命令の IF ステージを開始できる．並列に実行できる 2 命令なら 6 サイクル，3
命令なら 7 サイクルで処理できる．
さらにパイプラインを持つ 3-way のプロセッサの場合では最大でその 3 倍の命令を処理
できる．
ऩख
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲㻦㻌㻵㼚㼟㼠㼞㼡㼏㼠㼕㼛㼚㻌㻲㼑㼠㼏㼔
ঃॖউছॖথ
㻵㻰㻦㻌㻵㼚㼟㼠㼞㼡㼏㼠㼕㼛㼚㻌㻰㼑㼏㼛㼐㼑
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻱㼄㻦㻌㻱㼤㼑㼏㼡㼠㼑
㻹㻭㻦㻌㻹㼑㼙㼛㼞㼥㻌㻭㼏㼏㼑㼟㼟
ZD\
ঃॖউছॖথ
㼃㻮㻦㻌㼃㼞㼕㼠㼑㻌㻮㼍㼏㼗
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
図 2.1
パイプライン
実際に prog1 の 4 命令を処理した例が，図 2.2 である．パイプラインを持たない 1-way
のプロセッサでは図のように 20 サイクルを要する．
パイプラインを持つ 1-way のプロセッサの場合では，IF ステージを終えた直後に次の IF
ステージを開始できるので，8 サイクルで処理できる．
パイプラインを持つ 3-way のプロセッサでは，6 サイクルで終了する．1-way と比べて
最高で 3 倍の命令を処理できるが，3 倍の速さで終わる訳ではなく，必ずしもその性能を
発揮できるわけではない．
このように，同じ命令を処理する場合に，環境によって大きく実行時間が異なる．これ
を資源制約という．
2.2 Out-of-Order プロセッサ
7
ZD\
㻵㻲
㻵㻰
㻱㼄
㻵㻲
㻹㻭
㻵㻰
㼃㻮
㻱㼄
㻵㻲
㻹㻭
㻵㻰
㻱㼄
㼃㻮
㻵㻲
㻹㻭
㻵㻰
㼃㻮
㻱㼄
㻹㻭
㼃㻮
ZD\
ঃॖউছॖথ
㻵㻲
㻵㻰
㻵㻲
㻱㼄 㻹㻭 㼃㻮
㻵㻰 㻱㼄 㻹㻭 㼃㻮
㻵㻲 㻵㻰 㻱㼄 㻹㻭 㼃㻮
㻵㻲 㻵㻰 㻱㼄 㻹㻭 㼃㻮
ZD\
ঃॖউছॖথ
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
㼃㻮
㻵㻲
㻵㻰
㻱㼄
㻹㻭
図 2.2
㼃㻮
パイプラインによる prog1 の実行例
2.2 Out-of-Order プロセッサ
ここでは，OoO プロセッサの構成を説明する．OoO 実行の目的の 1 つは，ILP を抽出す
ることである．OoO 実行を実現するプロセッサには前節で説明した制約に対する解決策だ
けでなく，いくつかの機構が必要になる．
本研究の中心であるフロントエンド(プロセッサの 2 つに工程をわけたとき，命令を実行
するまでの準備などをする側の機構) の構成を説明する．
図 2.3 に OoO プロセッサのブロック図を示す．
2.2.1 分岐予測器
前説で説明したとおり，制御依存制約は ILP を制限する制約の中で占める所が大きい．
プログラムによっては全体の 4 分の 1 を占める場合もあり，[?] 分岐予測器は OoO プロ
セッサにとってほぼ必須の課題となっている．
具体的には，Gshare 方式 [8] などの分岐予測が広く用いられている．
Gshare とは，グローバル履歴(過去の分岐パターンを学習し，分岐を予測する) と分岐命
第2章
Out-of-Order プロセッサ
8
ROB: Re-order Buffer
RSs: Reservation Stations
FU: Functional Unit
GPR: Generic Purpose Register
Instrunction
I-cache
Data
Instruction Fetch
Map
Decode/aaaaaaaaaa
Assign
Table
Renameaaaaaaaaaa
Dispatch
Wakeup/Select
Operand Fetch
RSs
RSs
Instruction window
Issue
ROB
GPR
commit
FU
FU
Write back
図 2.3
OoO プロセッサのブロック図
令のアドレスとを用いる手法である．具体的には，二者の中位アドレスの排他的論理和を
とり，2bit の分岐予測テーブルを参照するというものである．グローバル履歴と比較する
と，単純な構造ではあるが平均 94% もの高い予測精度を実現している．また、後述する
CoreSymphony のフロントエンドにも用いられている．
2.2.2 レジスタリネーミング
逆依存と出力依存の解決策であるレジスタリネーミングは全てのオペランドが揃うまで
実行を待ち合わせるリザベーションステーションを用いる．具体的には，オペランドの値
が得られると，すぐにその値をリザベーションステーションに格納し，オペランドをレジ
スタから読み出す必要性を無くす．これにより，WAR ハザードを回避できる．また，いく
つかの命令のレジスタへの書き込みが衝突する際，最後のものだけがレジスタを更新でき
るようにする．これにより，WAW ハザードを回避できる．
2.2 Out-of-Order プロセッサ
9
2.2.3 命令スケジューリング
命令スケジューリングは
5 つの基本的なフェーズに分けることができる．
Rename フェーズ
論理レジスタと物理レジスタの対応を関係付けるマップ表を用いて，論理レジスタ
をリオーダーバッファ(命令を一時的に蓄えておくバッファ) の番号にリネームする．
Dispatch フェーズ
デコード，リネームが完了した命令と，リオーダーバッファ，レジスタからフェッ
チしたオペランドをリザベーションステーションに格納する．即値は immed フィー
ルドに格納される．
Wakeup フェーズ
新たに得られた計算結果により未解決オペランドがあったものを実行可能にする．
Select フェーズ
次に発行できるものをリザベーションステーションの中から選択する．
Issue フェーズ
選択された命令を発行する．
以上が大まかな CoreSymphony のベースである，OoO プロセッサのフロントエンドの
流れである．
10
第3章
CoreSymphony アーキテクチャ
本章では，CoreSymphony アーキテクチャを説明する．特に着目する命令ステアリング，
リーフノードステアリングの構造について述べ，その問題点に言及する．
3.1
コア融合アーキテクチャ
シングルコアプロセッサに代わり，CMP は現在の主流になっている．CMP に留まらず
コアの数が数十，数百に至るメニーコアプロセッサも現在広く研究されている．しかし，
複数個のコアを搭載したプロセッサは性能向上の妨げとなる深刻な課題を内包している．
それはプログラム内に存在する並列化できない箇所において大きく性能を制限されること
である．CMP ではスレッドレベル並列性を利用して各コアが並列にスレッドを実行して
スループットを向上させる．そのため並列処理を要求される場面においてはその性能を発
揮できるが，逐次処理性能が要求される場面ではコア数に見合うだけの並列性を常に抽出
できるとは限らない．この課題はプログラム内にそういった並列化できない箇所が多いほ
ど，コアの数が多くなるほどそれが顕著になる．
これを克服するには，必要に応じて逐次処理と並列処理とのどちらを優先するかを切り
替えられることが望ましい．こうした試みとして，複数のコアが仮想的に 1 つのコアとして
振る舞えるコア融合アーキテクチャと呼ばれるものがある．その一つである CoreFusion[1]
は，アウトオブオーダー実行できる 2 命令発行のコアをフロントエンドの集中的な制御に
より最大 4 個融合させるアーキテクチャである．しかし CoreFusion はコア間通信の機会
が多く，融合可能なコアの組が固定されているなど，柔軟性が低くなっている．対照的に
本論文の対象とする CoreSymphony は，フロントエンドを分散化することでコア間通信を
削減し，より柔軟な制御をすることをねらいとしたアーキテクチャである．
3.2 CoreSymphony アーキテクチャ
11
3.2 CoreSymphony アーキテクチャ
CoreSymphony は CoreFusion 同様，2 命令発行の OoO プロセッサをベースとしている．
最大 4 個のコアが融合して仮想的に最大 8 命令発行の 1 つのコアとして振る舞う．以下，
CoreSymphony の構成を，本研究の焦点であるフロントエンドに重きをおいて説明する．
図 3.1 に CoreSymphony アーキテクチャのフロントエンドを示す．
図 3.1
CoreSymphony のフロントエンド
フェッチブロック
CoreSymphony では，命令列をフェッチブロック (Fetch Block:以下 FB と表記) と
呼ばれるブロックに分割し，各命令を並列に実行している．FB1 単位の最大長は協
調コア数× 4 命令である．また，FB 内に含まれる分岐命令は協調コア数と同じ数
を上限とする，という制約がある．
ステアリング
CoreSymphony には，フェッチした命令列を分割して各コアに割り振るための，
「ステアリング (steering)」と呼ばれる追加のステージが存在する．各コアは自分
に割り振られた命令のみを実行する．ステアリングにはリーフノードステアリン
グ(Leaf-Node Steering:以下 LNS と表記) と呼ばれるアルゴリズムを用いる．(詳し
第3章
CoreSymphony アーキテクチャ
12
くは 3.3 説で述べる．) 割り振られた命令が早く実行を終えた場合は，次の FB に依
存する命令がないか実行を終えていれば，それらの実行を開始できる．しかし，そ
うしたケースは稀である．そのため，より多くの命令が割り振られるコアがボトル
ネックとなり，性能を低下させる可能性がある．性能向上には 1 つのコアに過剰に
命令が割り振られることを避け，なるべく命令を均等に割り振られることが求めら
れる．
ローカル命令キャッシュ
CoreSymphony では，従来と同じ命令キャッシュの他に各コアに「ローカル命令
キャッシュ」と呼ばれる命令トレースキャッシュ [9] を備えている．このローカル
命令キャッシュの 1 ラインは FB の 1 単位に対応し，ある FB の中でそのコア自身
に割り振られた命令と FB 間の依存関係を示す情報が格納される．
分岐予測器
CoreSymphony の分岐予測は協調動作中の全てのコアが全く同じ分岐履歴を用いて
同様の予測を行う．分岐予測器は Gshare 分岐予測器 [8] を用いるが，入力された
PC から 8 命令先までの命令の分岐予測をテーブルを 8 分割し，同時に行うことで 1
サイクルでの分岐予測を可能にしている．
3.3
リーフノードステアリング
ここでは LNS より先に考案された命令ステアリングの方式を，簡略化のため CoreSym-
phony と同様の FB 単位での振る舞いについて説明し，LNS を対比的に論じる．
3.3.1 従来のステアリング
以下では例として，次のような命令列からなる FB を，3 つのコアに割り振る場合を考
える．
I1:
r1 = r1 + 2
I2:
r2 = r2 + 4
I3:
r3 = r1 + r2
I4:
r4 = r3 + 2
I5:
r5 = r5 + r5
I6:
r6 = r4 + r5
3.3 リーフノードステアリング
13
I7:
r7 = r4 + 1
I8:
r8 = r3 + 3
I9:
r9 = r5 + 1
I10:
r10 = r5 + 2
I11:
r11 = r9 + 2
I12:
r12 = r12 + 3
この命令列をデータフローグラフで表すと図 3.2 のようになり，これらを以下のステア
リング方式で割り振る．
ϭ
Ϯ
ϯ
ϴ
ϰ
ϳ
ϲ
ϭϮ
ϱ
ϵ
ϭϬ
ϭϭ
図 3.2 命令列のデータフローグラフ
Modulo-N ステアリング
Modulo-N ステアリング [10][11](Modulo-N steering) は命令列を連続する N 個の命
令ずつに分け，それをラウンドロビン (あるコアから始めて全てのコアを選択した
らまた最初のコアに戻る) で割り振っていく．ここでは N = 2 として，2 個の命令に
分けてステアリングするものとする．この方式で割り振った結果が図 3.3 である．
Modulo-N ステアリングの場合，最も命令数が多いコアで 4，少ないコアで 2，とあ
る程度均等な命令振り分けが実現されている．しかし，コア同士をまたぐ複雑な依
存関係が存在し，コア間通信が頻繁に発生してしまう．そのため，コア間通信を極
力少なくすることが前提である CoreSymphony とは相性が悪い．
第3章
CoreSymphony アーキテクチャ
ϭ
14
Ϯ
ϱ
ϯ
ϵ
ϲ
ϰ
ϴ
ϭϬ
ϭϭ
ϭϮ
ϳ
ŽƌĞϬ
図 3.3
ŽƌĞϭ
ŽƌĞϮ
Modulo-N ステアリングによる割り振り
依存ベースステアリング
依存ベースステアリング [10][11](Dependency-Based Steering) はある命令が他の命
令に依存しているとき，それらを同じコアに割り当てる方式である．依存する命令
がない場合はその時点で最も割振られている命令が少ないコアに割り当てる．この
方式で割り振った結果が図 3.4 である．
依存ベースステアリングでは木がまるごと 1 つのコアに割り振られているので，コ
ア間通信が発生しないという点では優れている．しかし Core0 に割り振られた命令
が 11 個であるのに対して，Core1 に割り振られた命令が 1 個であり，Core2 には全
く命令が割り振られていない．この FB の命令が次以降の FB の依存元となってい
た場合，結局他のコアも Core0 に割り振られた命令の終了を待たなければいけない
ため効率が悪い．
このように，
「コア間の通信の抑制」と「命令の均等な振り分け」の CoreSymphony が要
求する２つのパラメータは，以上の 2 つのアルゴリズムではトレードオフの関係になって
しまっている．
LNS はこれら 2 つのパラメータの両立を実現する命令ステアリングである．
3.3 リーフノードステアリング
ϭ
15
Ϯ
ϯ
ϴ
ϰ
ϳ
ϲ
ϱ
ϭϮ
ϵ
ϭϬ
ϭϭ
ŽƌĞϬ
図 3.4
ŽƌĞϭ
ŽƌĞϮ
ŽƌĞϯ
依存ベースステアリングによる割り振り
3.3.2 リーフノードステアリングの振る舞い
リーフノードステアリング
LNS はまず，データフローグラフの葉 (Leaf-Node) にあたる命令を，出現が早い (図で
は番号が若い) 順にラウンドロビンにコアに振り分ける．次に同じ FB 内でその葉が依存し
ている命令全てを同じコアに割り振る．
前節の命令列を LNS によりステアリングする手順を示す．このグラフで葉にあたるの
は命令 6，7，8，10，11，12 である．まず最も若い番号の葉である命令 6 と，命令 6 が依
存する命令である命令 1，2，3，4，5 を含む部分木 a が生成される．次に命令 7 に対して，
命令 7 と命令 7 が依存する命令 1，2，3，4 が部分木 b を構成する．同様にすべての葉に
この操作を行い，図 3.2 から生成された部分木をまとめたものが図 3.5 である．
また，これらの命令をラウンドロビンで 3 コアに割り振った例が図 3.6 である．
図 3.6 と図 3.2 を比較すると，命令 1，2，3，4，5 が複数個のリーフノードの依存元に
なっているため実行する命令が複製されている．しかし，各コアに割り振られた命令数は
Core0 が 7 個，Core1 が 8 個，Core2 が 5 個であり，全体としては同程度の負荷になって
いることがわかる．また依存がコアをまたがないため，コア間通信も発生しない．
第3章
CoreSymphony アーキテクチャ
ϭ
Ϯ
ϭ
ϭ
Ϯ
ϯ
ϰ
16
ϱ
Ϯ
ϱ
ϯ
ϯ
ϵ
ϰ
ϴ
ϭϭ
Đ
Ğ
ϱ
ϭϮ
ϭϬ
Ĩ
ϲ
ϳ
Ă
ď
Ě
図 3.5
LNS が生成する部分木
LNS が生成する部分木，◎は葉を表す．
ϭ
Ϯ
ϭ
Ϯ
ϱ
ϯ
ϯ
ϱ
ϭ
Ϯ
ϵ
ϰ
ϱ
ϭϮ
ϯ
ϰ
ϭϬ
ϭϭ
ϲ
Ă
ϳ
Ě
ď
ŽƌĞϬ
ϴ
Ğ
ŽƌĞϭ
図 3.6
LNS による割り振り
Đ
ŽƌĞϮ
Ĩ
3.3 リーフノードステアリング
17
3.3.3 課題
従来の LNS の問題点について述べる．従来の LNS では，リーフノードを単純にラウン
ドロビンでコアに割り振っているが，その命令が依存する命令の数すなわち 3.5 で示した
部分木の大きさを一切考慮していないため，コアに割り振られる命令数に偏りが発生する
ことがある．
部分木の割り振りによりどれだけ差が出るかを説明する．なお，以下の例では説明の簡
略化の為，コアに同じ命令が 2 回以上割り当てられて命令が重複する場合は考慮しない．
図 3.5 の 6 つの部分木を 4 コアに割り振る場合を考える．従来手法では，リーフノード
を番号が若い順に割り振るだけなので，a，b，c…の順に割り振られ，図 3.7 のようになる．
ϭ Ϯ ϱ ϭ Ϯ
ϯ
ϵ
ϯ ϭϮ
ϰ ϱ ϭϭ ϰ
ϲ
Ğ
Ă
Ĩ
ϳ
ϭ
Ϯ
ϯ
ϱ
ϭϬ
ϴ
Đ
Ě
ď
ŽƌĞϬ
ŽƌĞϭ
ŽƌĞϮ
ŽƌĞϯ
命令数
命令数
命令数
命令数
ϵ
ϲ
ϰ
Ϯ
図 3.7
LNS により偏りが生じる例
LNS は FB 単位で処理を行うため，一つのコアに負荷が集中し別のコアが処理を早く終
えたとしても，その次の FB の命令は前の FB 内の命令に依存している可能性が高く，大き
な負荷を持ったコアがボトルネックになってしまう．こうしたボトルネックを避ける戦略
の 1 つは，コアに割り当てられた命令の最大値を最も小さくすることである．この例の場
合では図 3.8 のように，部分木 e，f を Core0，1 ではなく Core2，3 に割り振ると，コアに
割り当てられた命令の最大値を 9 から 6 へと削減できる．
第3章
CoreSymphony アーキテクチャ
ϭ
Ϯ
ϯ
ϭ
18
ϭ
Ϯ
Ϯ
ϯ
ϯ
ϭϮ
ϰ
ϱ
ϰ
ϳ
Ă
ď
ŽƌĞϬ
命令数
ϲ
ϱ
図 3.8
ϭϬ
ϵ
ϭϭ
Ě
Ğ
Ĩ
ŽƌĞϭ
命令数
ϱ
ϴ
Đ
ϲ
ϱ
ŽƌĞϮ
ŽƌĞϯ
命令数
命令数
ϱ
ϱ
偏りが改善された例
ただし，実際には同じ命令が 1 つのコアの中で 2 回以上割り振られても二重には実行さ
れないため，重複を考慮して割り当てを行う必要がある．
19
第4章
命令ステアリング BLNS の提案
本章では，前章で述べた LNS の問題を改善した命令ステアリングであるバランス・リー
フノードステアリング(Balanced Leaf-Node Steering:BLNS) の構成を提案し，この方法に
ついて検討する．
4.1
提案手法の方針
前述したとおり，CoreSymphony ではコア間通信を極力行わない，という前提がある．
もし前章で述べた部分木を分割して別のコアに割り振ってしまうと，コア間にまたがる依
存関係が FB 内に発生してしまう．これは先の前提から望ましくない．したがって，部分
木は CoreSymphony のステアリングの最小単位であるといえる．
そのため，従来の LNS における部分木の作成までのプロセスには変更を加えない．変更
を加えるのは，生成された部分木をコアに割り振る部分である．割り振りを単にラウンド
ロビンで行うのではなく，その時点ですでに割り当てられた命令の数が最も少ないコアを
探索し，そのコアに割り当てる，という改良を加える．
4.2
提案手法のアルゴリズム
以下に，BLNS のアルゴリズムを示す．ただし，Ancestor[I] とは命令 I と FB 内で命令
I が依存する命令の集合である．これは部分木の作成プロセスによって生成される．
入力:協調コアの数 n
FB 内の命令 I1 ， I2 ， … ， Im
出力:各コアの実行すべき命令の集合 S 1 ， S 2 ， … ， S n
第4章
命令ステアリング BLNS の提案
20
$1 algorithm BLNS
$2
S 1， S 2， … ， S n ← { }
S 1 ， S 2 ， … ， S n を初期化
$3
NumInst[1]， NumInst[2]， … ， NumInst[n] ← 0
NumInst[1]， NumInst[2]， … ， NumInst[n] を 0 で初期化
(NumInst[n] は Coren に割り当てられた命令数)
$4
$5
$6
for i = 1 to m
if Ii がリーフノード then
index ← NumInst[j] が最小となる j
その時点で割り当てられた命令数が最小であるコア index を探索
$7
S index ← S index ∪ Ancestor[Ii ]
コア index に命令 i を含む部分木を割り当てる
$8
NumInst[index] ← NumInst[index] + Ancestor[Ii ] の要素数
コア index に割り当てられた命令数に i を含む部分木の命令数を足す
$9
end if
$10
end for
$11
return with S 1 ， S 2 ， … ， S n
4.3
提案手法の性能向上の説明
BLNS が予想通りの振る舞いをすることを説明する．
前章と同じ命令列を 4 コアに割り振った場合を想定し，LNS と BLNS との振る舞い方
の違いを論じる．また，今回は命令の重複を考慮し，二重にカウントしないものとする．
まず LNS の場合を説明する．LNS を用いた場合，前回同様図 3.5 のような部分木が生
成される．部分木は葉の番号が若い順にコアに割り振られていくので図 4.1 のようになる．
その時の Core0 では，葉である命令 6 と命令 11 が命令 5 に依存しているので命令 5 は重
複する．そのため，Core0 で実行される命令は 9 個になる．Core1，Core2，Core3 では命
令は重複していないので命令数はそのまま 6，4，2 となる．
次に BLNS の場合を説明する．図 3.2 の命令を前節で示したアルゴリズムを適用し，実
行順に追っていく．
$4 for i = 1 to m
(1)
4.3 提案手法の性能向上の説明
21
ϭ Ϯ ϱ ϭ Ϯ
ϯ
ϵ
ϯ ϭϮ
ϰ ϱ ϭϭ ϰ
ϲ
Ă
Ğ
Ϯ
ϯ
ϱ
ϭϬ
ϴ
Đ
Ě
ď
ŽƌĞϬ
ŽƌĞϭ
ŽƌĞϮ
ŽƌĞϯ
命令数
命令数
命令数
命令数
ϲ
ϰ
Ϯ
ϴ;䐣䛜㔜」Ϳ
図 4.1
Ĩ
ϳ
ϭ
既存手法により割り振られた結果:命令の重複を考慮する場合
$5 まず最初に命令 6 が葉なので if 文の条件を満たす．
$6 NumInst は全て 0 なので NumInst が最小となる j はどれでも良いが，ここでは j = 0
を選択する．
$7 S [ 0] に Ancestor[I6 ](=命令 1，2，3，4，5，6) が入る．
$8 NumInst[0] に Ancestor[I6 ] の要素数 (=6) が入る．
$9 i をインクリメントして$5 に戻る
(2) 命令 7，8，10 の部分木は (1) と同様の手順でそれぞれ Core1，Core2，Core3 に入り.
NumInst[1] = 6， NumInst[2] = 4， NumInst[3] = 2，となる.
(3)
$5 次に命令 11 が葉なので if 文の条件を満たす．
$6 NumInst[j] は j = 3 で最小値 2
$7 右辺の S index は命令 5，10，Ancestor[I11 ](=命令 5，9，11) となり，命令 5 が重複す
るので S [ 3] = 命令 5，9，10，11 となる．
$8 右辺の NumInst[3] = 2，Ancestor[I11 ] = 3．よって NumInst[3] には 5 が入る．(実際
の命令数は 4)
第4章
命令ステアリング BLNS の提案
ϭ
Ϯ
ϯ
ϰ
ϱ
Ϯ
ϰ
ϴ
Ă
ď
ϲ
Ϯ
ϯ
ϳ
命令数
ϭ
ϯ
ϲ
ŽƌĞϬ
図 4.2
ϭ
22
ŽƌĞϭ
命令数
ϱ
ϱ
ϭϬ
Đ
Ě
ŽƌĞϮ
ŽƌĞϯ
命令数
命令数
ϰ
Ϯ
提案手法により割り振られた結果:命令 10 の部分木までを割り振った状態
$9 i をインクリメントして$5 に戻る
(4) 命令 12 も 11 と同様の手順で Core2 に入る. NumInstCore[2] には 5 が入る.
$10 end for
$11 return with S 1 ， S 2 ， … ， S n
以上から得られた S 1 ， S 2 ， … ， S n をフローグラフに表すと図 4.2 のようになる．
Core0 が命令数最大で 6，Core3 が命令数最小で 4 と，全体にほぼ均等に割り振られるこ
とがわかる．また，このステアリング結果は図 3.8 とほぼ同じ状態になる．
このように，BLNS は LNS よりも効率の良いステアリングを行なっていることが確認で
きる．
4.3 提案手法の性能向上の説明
ϭ
Ϯ
ϯ
23
ϭ
Ϯ
ϯ
ϭ
Ϯ
ϯ
ϭϮ
ϰ
ϱ
ϳ
Ă
ď
命令数
ϲ
ŽƌĞϭ
命令数
ϱ
ϱ
ϭϬ
ϵ
ϴ
ϭϭ
Đ
ϲ
ŽƌĞϬ
図 4.3
ϰ
ϱ
Ě
Ĩ
Ğ
ŽƌĞϮ
ŽƌĞϯ
命令数
命令数
ϱ
ϰ;䐣䛜㔜」Ϳ
提案手法により割り振られた結果:命令の重複を考慮する場合
24
第5章
評価
本章ではシミュレーションにより求められた IPC(Instruction Per Cycle:サイクルあたり
に実行した命令数) により，提案する LNS の性能を評価する．
5.1
評価環境
評価環境を示す．本研究に用いたシミュレータは MIPS システムレベルシミュレータ
SimMips[12] を CoreSymphony 向けに拡張したサイクルレベルシミュレータである．前章
で述べた BLNS 以外の箇所は従来の CoreSymphony と同様のものを用いる．協調するコ
アの数を 4 とした場合の CoreSymphony の IPC(Ins) を計測する．
シミュレーションにおける主要なパラメータを以下に示す．
5.2
比較対象
評価は，LNS と BLNS を同じ 5.1 の条件で比較して行う．具体的には，IPC の観点から
性能向上を論ずる．
5.3
ベンチマーク
ベンチマークには，整数ベンチマークとして dhrystone と CINT2006(Integer Component
of SPEC CPU2006) から aster，gcc，gobmk，h264ref， hmmer，libquantum，mcf，omnetpp
の 9 種を，浮動小数ベンチマークとして whetstone と CFP2006(Floating Point Component
of SPEC CPU2006) から bwaves，cactusADM，calcuix，GemsFDTD，gromacs，leslie3d，
5.4 評価結果
25
表 5.1
シミュレーションにおける主要なパラメータ．
L1-I$ (Local)
16KB， 4-way set assoc.， 2 cycle
L1-I$ (Convent.)
8KB， 2-way set assoc.， 1 cycle
L1-D$
16KB， 2-way set assoc.， 1 cycle
Shared L2$
2MB， 4-way set assoc.， 10 cycle
BTB
8KB， 2-way set assoc.
GHR
6bit
Instruction Window
24/24 entries (INT/FP)
PRF
32/32 entries (INT/FP)
NRP[6]
12/12 entries (INT/FP)
LSQ
96 entries
ROB
96 entries
LWT
1K entries
Main Memory
100 cycle
milc，namd，povraysoplex，11 種，合計 20 種を選択した．
基本的にはどのベンチマークも先頭の 2G 命令をスキップした後，そこから 100M 命令
を実行する．命令数が 2G に満たない gobmk は 1500M をスキップし，そこから 100M 命
令を実行した．dhrystone， wetstone，leslie3d，soplex は命令数が少ないので，全ての命令
を実行する，
以上のように実行する命令を選択し，各ベンチマークにおける CoreSymphony の IPC を
測定する．
5.4
評価結果
図 5.2 に整数ベンチマークの実行結果を，図 5.3 に浮動小数ベンチマークの実行結果を
示す．縦軸は IPC を表す．横軸は使用したベンチマークの他に，全ベンチマークの IPC の
調和平均を"ALL"として，図 5.2 には整数ベンチマークのみの IPC の調和平均を"INT"と
して，図 5.3 には浮動小数ベンチマークのみの IPC の調和平均を"FP"として加えている．
第5章
26
評価
䝧䞁䝏䝬䞊䜽
㼐㼔㼞㼥㼟㼠㼛㼚㼑
㼍㼟㼠㼍㼞
㼓㼏㼏
㼓㼛㼎㼙㼗
㼔㻞㻢㻠㼞㼑㼒
㼔㼙㼙㼑㼞
㼘㼕㼎㼝㼡㼍㼚㼠㼡㼙
㼙㼏㼒
㼛㼙㼚㼑㼠㼜㼜
㼣㼔㼑㼠㼟㼠㼛㼚㼑
㼎㼣㼍㼢㼑㼟
㼏㼍㼏㼠㼡㼟㻭㻰㻹
㼏㼍㼘㼏㼡㼕㼤
㻳㼑㼙㼟㻲㻰㼀㻰
㼓㼞㼛㼙㼍㼏㼟
㼘㼑㼟㼘㼕㼑㻟㼐
㼙㼕㼘㼏
㼚㼍㼙㼐
㼜㼛㼢㼞㼍㼥
㼟㼛㼜㼘㼑㼤
$//
,17
)3
/16
㻝㻚㻣㻤㻞
㻜㻚㻤㻥㻝
㻝㻚㻞㻜㻞
㻟㻚㻤㻥㻟
㻝㻚㻢㻠㻝
㻝㻚㻢㻢㻠
㻞㻚㻤㻢㻡
㻞㻚㻜㻜㻜
㻜㻚㻣㻞㻝
㻝㻚㻟㻝㻥
㻜㻚㻣㻢㻡
㻜㻚㻤㻠㻣
㻞㻚㻜㻜㻜
㻝㻚㻠㻥㻥
㻞㻚㻟㻤㻣
㻝㻚㻜㻟㻢
㻝㻚㻠㻟㻞
㻝㻚㻡㻟㻜
㻝㻚㻞㻝㻟
㻝㻚㻜㻠㻞
㻝㻚㻟㻞㻜
㻝㻚㻠㻠㻣
㻝㻚㻞㻟㻝
図 5.1
5.5
%/16
㻝㻚㻤㻞㻤
㻜㻚㻤㻥㻝
㻝㻚㻞㻜㻡
㻟㻚㻤㻥㻡
㻝㻚㻢㻠㻤
㻝㻚㻢㻢㻝
㻞㻚㻤㻣㻢
㻞㻚㻝㻢㻣
㻜㻚㻣㻞㻜
㻝㻚㻟㻟㻡
㻜㻚㻤㻝㻥
㻜㻚㻤㻡㻞
㻞㻚㻜㻜㻜
㻝㻚㻠㻥㻟
㻞㻚㻟㻢㻜
㻝㻚㻜㻢㻞
㻝㻚㻠㻡㻝
㻝㻚㻡㻡㻞
㻝㻚㻞㻜㻟
㻝㻚㻜㻠㻣
㻝㻚㻟㻟㻣
㻝㻚㻠㻢㻜
㻝㻚㻞㻡㻜
ྥୖ⋡
㻝㻚㻜㻞㻢
㻝㻚㻜㻜㻜
㻝㻚㻜㻜㻞
㻝㻚㻜㻜㻝
㻝㻚㻜㻜㻠
㻜㻚㻥㻥㻤
㻝㻚㻜㻜㻠
㻝㻚㻜㻤㻠
㻜㻚㻥㻥㻥
㻝㻚㻜㻝㻞
㻝㻚㻜㻣㻝
㻝㻚㻜㻜㻢
㻝㻚㻜㻜㻜
㻜㻚㻥㻥㻢
㻜㻚㻥㻤㻥
㻝㻚㻜㻞㻡
㻝㻚㻜㻝㻟
㻝㻚㻜㻝㻠
㻜㻚㻥㻥㻞
㻝㻚㻜㻜㻡
㻝㻚㻜㻝㻟
㻝㻚㻜㻜㻥
㻝㻚㻜㻝㻡
BLNS と LNS の IPC の比較と向上比
考察
まずは BLNS による性能向上の妥当性について検討する．最も IPC が向上したものは
CINT2006 の mcf であり，向上率は 8.4% である．その次に向上率が高いものは CFP2006
の bwaves の 7.1% であり，比較的高い数値を示している．評価に用いた 20 種のベンチ
マークの内，前述した mcf，bwaves の他に dhrystone，gcc，gobmk，h264ref，libquantum，
whetstone，cactusADM，leslie3d，milc，namd，soplex の 13 種が IPC の向上を見せた．逆
に，hmmer，omnetpp，GemsFDTD，povray のように IPC が低下しているものもある．ま
た，astar，calculix のベンチマークは，全く IPC の変化が見られなかった．
半分以上のベンチマークにおいて性能向上が見られ，また，性能が向上したベンチマー
クの数値の振れ幅と比較して，性能が低下したベンチマークの振れ幅は極めて小さい．さ
らに，ベンチマーク全体においては 1.3% の性能向上が確認できる．
5.5 考察
27
ϰ͘Ϭ
>E^
ϯ͘ϱ
>E^
ϯ͘Ϭ
Ϯ͘ϱ
/W
Ϯ͘Ϭ
ϭ͘ϱ
ϭ͘Ϭ
Ϭ͘ϱ
Ϭ͘Ϭ
ĚŚƌLJƐƚŽŶĞ
ĂƐƚĂƌ
ŐĐĐ
ŐŽďŵŬ
ŚϮϲϰƌĞĨ
ŚŵŵĞƌ
ůŝďƋƵĂŶƚƵŵ
ŵĐĨ
ŽŵŶĞƚƉƉ
>>
/Ed
ƉƉůŝĐĂƚŝŽŶ
図 5.2
整数演算ベンチマークの IPC の比較
Ϯ͘ϱ
>E^
Ϯ͘Ϭ
>E^
ϭ͘ϱ
/W
ϭ͘Ϭ
Ϭ͘ϱ
Ϭ͘Ϭ
ǁŚĞƚƐƚŽŶĞ ďǁĂǀĞƐ ĐĂĐƚƵƐD ĐĂůĐƵŝdž 'ĞŵƐ&d ŐƌŽŵĂĐƐ ůĞƐůŝĞϯĚ
ŵŝůĐ
ŶĂŵĚ
ƉŽǀƌĂLJ
ƐŽƉůĞdž
ƉƉůŝĐĂƚŝŽŶ
図 5.3 浮動小数点演算ベンチマークの IPC の比較
>>
&W
第5章
評価
28
以上から，BLNS は CoreSymphony の性能を向上したと言える．
5.5.1 命令数を考慮した考察
次に，実際に BLNS がどのような振る舞いをしているのか，を検討する．前章で述べた
とおり，BLNS 導入の目的の 1 つとして，「FB 単位で最も多く命令が割り振られたコアの
命令数を削減する」，ということが挙げられる．
実際に性能向上が得られたベンチマークについて，本当に"FB 単位で最も多く命令が割
り振られたコアの命令数を削減"したから性能が向上したのかを検討しなければならない．
その確認のため，IPC が最も上昇した mcf のベンチマークと，最も低下した gromacs
のベンチマークを用いて，FB 中で最も多くの命令を割振られたコアの命令数の変化を調
べる．
図 5.4 に mcf ベンチマークにおけるコアの命令数の最大値を示した．横軸はコアの命令
数の最大値 n，縦軸はコアの最大値が n である FB の数である．
図から分かる通り，コアの命令数の最大値が 6 となる FB の数が，LNS と比べて大幅に
増加している．その代わりにコアの命令数の最大値が 6，8 となる FB の数は減少してい
る．最大値の命令の合計は図のグラフの面積に相当し，より少ない方が IPC が高くなる．
LNS と BLNS のグラフではほぼ同程度の面積に見えるが，最大値の命令の合計は LNS の
方より BLNS の方が少ない．また，5.1 で示したように IPC も上昇している．よって，こ
れは「FB 単位で最も多く命令が割り振られたコアの命令数を削減する」というアルゴリズ
ムが成功し，性能向上につながった場合であると言える．
同様に図 5.5 に gromacs ベンチマークにおけるコアの命令数の最大値を示した．横軸は
コアの命令数の最大値ｎ，縦軸はコアの最大値がｎである FB の数である．この場合では
コアの命令数の最大値が 5 となる FB の数が減少し，その代わりにコアの命令数の最大値
が 6，7 となる FB の数が増加している．このグラフも LNS と BLNS の面積は近いよう見
えるが，計算すると LNS の方が命令数が少なかった．この場合，FB 単位で最も多く命令
が割り振られたコアの命令数を逆に増加させてしまい，性能低下に至っている．
性能が向上／低下する理由が明らかになった．次は 1FB あたりの命令数から性能向上を
論じる．
図 5.6 に各ベンチマークの 1FB あたりの平均の命令数と IPC 向上率を示す．なお，ここ
でいう平均は単に相加平均を表す．
まず，ベンチマークを整数演算と浮動小数演算にわけたとき，
全体の IPC 向上率が 1.3%，整数演算は 0.9%，浮動小数演算は 1.5% である．また，1FB
5.5 考察
29
ϵϬϬϬϬϬϬ
ϴϬϬϬϬϬϬ
>E^
ϳϬϬϬϬϬϬ
ϲϬϬϬϬϬϬ
>E^
ϱϬϬϬϬϬϬ
ਈপகऋ
‫۝‬भ ϰϬϬϬϬϬϬ
)%भਯ
ϯϬϬϬϬϬϬ
ϮϬϬϬϬϬϬ
ϭϬϬϬϬϬϬ
Ϭ
ϭ Ϯ ϯ ϰ ϱ ϲ ϳ ϴ ϵ ϭϬ ϭϭ ϭϮ ϭϯ ϭϰ ϭϱ ϭϲ
コアの命令数の最⼤値Q
図 5.4 mcf における FB 毎のコアの命令数の最大値の変化
ϲϬϬϬϬϬϬ
ϱϬϬϬϬϬϬ
>E^
ϰϬϬϬϬϬϬ
>E^
ਈপகऋ ϯϬϬϬϬϬϬ
‫۝‬भ
)%भਯ
ϮϬϬϬϬϬϬ
ϭϬϬϬϬϬϬ
Ϭ
ϭ Ϯ ϯ ϰ ϱ ϲ ϳ ϴ ϵ ϭϬ ϭϭ ϭϮ ϭϯ ϭϰ ϭϱ ϭϲ
コアの命令数の最⼤値Q
図 5.5
gromacs における FB 毎のコアの命令数の最大値の変化
第5章
30
評価
あたりの命令数の平均は，全体が 12.10 整数演算が 11.26，浮動小数演算が 12.10 である．
これは，浮動小数の方が平均の命令数が多く，従来のステアリングにより生じるロスが大
きく，そのため BLNS による改善の効果が大きかったと考えられる．また，浮動小数演算
のレイテンシが整数演算よりも大きいため，「FB 単位で最も多く命令が割り振られたコア
の命令数を削減する」アルゴリズムが効率的に働いたからであると考えられる．
結論として，浮動小数演算，FB あたりの命令数が多い (=依存関係が多く存在する．) な
どの条件をみたすとき，性能向上がより顕著に見られることがわかった．
䝧䞁䝏䝬䞊䜽
㻲㻮䛒䛯䜚䛾ᖹᆒ࿨௧ᩘ
㻵㻼㻯ྥୖ⋡
㼐㼔㼞㼥㼟㼠㼛㼚㼑
㻝㻝㻚㻜㻥
㻝㻚㻜㻞㻡㻤
㼍㼟㼠㼍㼞
㻝㻞㻚㻜㻥
㻝㻚㻜㻜㻜㻜
㼓㼏㼏
㻝㻝㻚㻜㻤
㻝㻚㻜㻜㻞㻡
㼓㼛㼎㼙㼗
㻤㻚㻟㻥
㻝㻚㻜㻜㻜㻡
㼔㻞㻢㻠㼞㼑㼒
㻝㻞㻚㻥㻣
㻝㻚㻜㻜㻠㻟
㼔㼙㼙㼑㼞
㻝㻝㻚㻠㻢
㻜㻚㻥㻥㻤㻞
䝧䞁䝏䝬䞊䜽
㼘㼕㼎㼝㼡㼍㼚㼠㼡㼙
㻲㻮䛒䛯䜚䛾ᖹᆒ࿨௧ᩘ
㻝㻝㻚㻡㻥
㻵㻼㻯ྥୖ⋡
㻝㻚㻜㻜㻟㻤
㼙㼏㼒
㻝㻝㻚㻟㻟
㻝㻚㻜㻤㻟㻡
㼛㼙㼚㼑㼠㼜㼜
㻝㻝㻚㻟㻟
㻜㻚㻥㻥㻤㻢
㼣㼔㼑㼠㼟㼠㼛㼚㼑
㻝㻞㻚㻣㻟
㻝㻚㻜㻝㻞
㼎㼣㼍㼢㼑㼟
㻝㻡㻚㻝㻥
㻝㻚㻜㻣㻜㻢
㼏㼍㼏㼠㼡㼟㻭㻰㻹
㻝㻡㻚㻤㻤
㻝㻚㻜㻜㻡㻥
㼚㼍㼙㼐
㻝㻜㻚㻤㻞
㻝㻚㻜㻝㻠㻠
䝧䞁䝏䝬䞊䜽
㻲㻮䛒䛯䜚䛾ᖹᆒ࿨௧ᩘ
㻵㻼㻯ྥୖ⋡
㼏㼍㼘㼏㼡㼕㼤
㻝㻠㻚㻜㻜
㻝㻚㻜㻜㻜㻜
㻳㼑㼙㼟㻲㻰㼀㻰
㻝㻜㻚㻠㻡
㻜㻚㻥㻥㻢㻜
㼓㼞㼛㼙㼍㼏㼟
㻥㻚㻡㻜
㻜㻚㻥㻤㻤㻣
㼘㼑㼟㼘㼕㼑㻟㼐
㻝㻠㻚㻡㻣
㻝㻚㻜㻞㻡㻝
㼙㼕㼘㼏
㻝㻟㻚㻞㻣
㻝㻚㻜㻝㻟㻟
䝧䞁䝏䝬䞊䜽
㻲㻮䛒䛯䜚䛾ᖹᆒ࿨௧ᩘ
㻵㻼㻯ྥୖ⋡
㼜㼛㼢㼞㼍㼥
㻝㻞㻚㻥㻝
㻜㻚㻥㻥㻝㻤
㼟㼛㼜㼘㼑㼤
㻝㻝㻚㻢㻟
㻝㻚㻜㻜㻠㻤
㻵㻺㼀
㻝㻝㻚㻞㻢
㻝㻚㻜㻜㻥㻜
㻲㻼
㻝㻞㻚㻥㻟
㻝㻚㻜㻝㻡㻟
㻭㻸㻸
㻝㻞㻚㻝㻜
㻝㻚㻜㻝㻞㻣
図 5.6
FB1 つに含まれる命令数の平均と IPC の向上率
31
第6章
結論
本論文では，「コア間通信を発生させない」というコンセプトのもとで CMP が要求する
並列処理性能と逐次処理性能の両方を追求する画期的な CoreSymphony アーキテクチャの
命令ステアリングに着目した．ステアリング方式による命令数の変化など様々なデータを
採取した．より効率的な命令ステアリング BLNS を提案し，実装してシミュレーションを
行った．
実験の結果，IPC の観点から性能が向上することを確認した．その性能向上は最も顕著
なもので 8.4% の向上であった．IPC が変化しない，もしくは低下するベンチマークも見
られたが，全体の平均では 1.3% の向上を確認した．さらに，その IPC の向上や低下の値
とコアに割り振られた命令数の最大値の変化から，提案手法が正しく動作することを確認
した．また，ベンチマーク全体の命令数の分布と性能向上を結びつけ，提案した命令ステ
アリングが有効に働く命令列の条件を分析した．
フロントエンドにおける改良は，リネームや命令キャッシュなどにも関わってくる箇所
である．そのため，今回の提案は命令ステアリングのみの局所的な変更に留まった．今回
の分析で性能向上が確認できたため，フロントエンド全体に改良を施せば，さらなる性能
向上を望むことができる．また，今回の提案はハードウェアの実装を視野に入れた設計を
行なっていないため，ハードウェア量を現実的な値に近づけるための構成の検討が今後の
課題として挙げられる．
32
謝辞
本研究を進めるにあたり，熱心かつ適切な御指導をいただき，直前まで校正をして頂い
た指導教員の吉瀬謙二先生に深謝します．
CoreSymphony の生みの親である若杉祐太氏無しにして本研究は有り得ず，後人へと道
を示して頂いた氏に心よりお礼申し上げます．ゼミ内外で CoreSymphony のみならず研
究全般にわたり多くのアドバイスを賜り，論文を構成する際に幾度と無く参考にさせても
らった坂口嘉一・永塚智之の両氏に感謝の意を表します。
本論文を執筆するに当たって，藤枝直輝氏に論述の方向性や全体の筋道をはっきり示し
ていただき，言い表せないほどの助力を頂いたため，こうして完成する運びとなりました．
CoreSymphony 以外でも，研究のノウハウや知識をご教授頂き，デバッグなどに協力し
ていただいた佐藤真平氏，高前田伸也氏，松村貴之氏，小林諒平氏に深く感謝します．
最後に，高いテンションで研究室を盛り上げてくれた池田貴一君と，支えて頂いた吉瀬
研究室と OB の皆様，東工大鈴村研究室の皆様，西 8 号館の皆様に心から感謝します．
33
参考文献
[1] Engin Ipek, Meyrem Kirman, Nevin Kirman and Jose F. Martinez. Core fusion: Accommodating software diversity in chip multiprocessors. In Proceedings of the 34th
International Symposium on Computer Architecture (ISCA-2007), pp. 186–197, 2007.
[2] David Tarjan, Michael Boyer, and Kevin Skadron. Federation: repurposing scalar cores
for out-of-order instruction issue. In Proceedings of the 45th annual Design Automation
Conference (DAC-2008), pp. 772–775, 2008.
[3] Carlos Madriles, Pedro López, Josep M. Codina, Enric Gibert, Fernando Latorre, Alejandro Martínez, Raúl Martínez, and Antonio González. Boosting single-thread performance in multi-core systems through fine-grain multi-threading. In Proceedings of
the 36th International Symposium on Computer Architecture (ISCA-2009), pp. 474–483,
2009.
[4] Changkyu Kim, Simha Sethumadhavan, M. S. Govindan, Nitya Ranganathan, Divya
Gulati, Doug Burger, and Stephen W. Keckler. Composable Lightweight Processors. In
Proceedings of the 40th International Symposium on Microarchitecture (MICRO-2007),
pp. 381–394, 2007.
[5] Hongtao Zhong, Steven A. Lieberman, and Scott A. Mahlke. Extending Multicore Architectures to Exploit Hybrid Parallelism in Single-thread Applications. In Proceedings of
the 13th International Conference on High-Performance Computer Architecture (HPCA2007), pp. 25–36, 2007.
[6] 若杉祐太, 坂口嘉一, 吉瀬謙二. 協調可能スーパースカラ CoreSymphony. 情報処理学
会論文誌, Vol. 3, No. 3, pp. 67–87, 2010.
[7] John Hennessy and David Patterson. Computer Architecture - A Quantitative Approach
4th edition. Morgan Kaufmann, 2006.
[8] Scott McFarling. Combining Branch Predictors. WRL Technical Note TN-36, 1993.
参考文献
34
[9] Eric Rotenberg, Steve Bennett, and James E. Smith. Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching. In MICRO 29: Proceedings of the 29th
Annual ACM/IEEE International Symposium on Microarchitecture, pp. 24–34, 1996.
[10] A. Baniasadi and A. Moshovos. Instruction distribution heuristics for quad-cluster,
dynamically-scheduled, superscalar processors. In Proceedings of 33rd International
Symposium on Microarchitecture (MICRO-2000), pp. 337–347, 2000.
[11] 服部直也, 高田正法, 岡部淳, 入江英嗣, 坂井修一, 田中英彦. 発行時間差に基づいた命
令ステアリング方式. 情報処理学会論文誌, Vol. 45, No. 11, pp. 80–93, 2004.
[12] 藤枝直輝, 渡邉伸平, 吉瀬謙二. 教育・研究に有用な MIPS システムシミュレータ
SimMips. 情報処理学会論文誌, Vol. 50, No. 11, pp. 2665–2676, 2009.