熊本大学学術リポジトリ
プログラムフェーズを考慮した SMTプロセッサ上で のスレッドスケジューリング手法
著者 市川, 雄二郎, 有次, 正義
雑誌名 データ工学ワークショップ論文集 : DEWS2007
巻 18
ページ E2‑8
発行年 2007‑06‑01
その他の言語のタイ トル
A Thread Scheduling Method for SMT Processor considering Program Phase
URL http://hdl.handle.net/2298/10956
DEWS2007 E2-8
プログラムフェーズを考慮した
SMT プロセッサ上でのスレッドスケジューリング手法
市川 雄二郎†
有次 正義‡
†群馬大学大学院工学研究科情報工学専攻 〒
376-8515
群馬県桐生市天神町1-5-1
‡群馬大学工学部情報工学科 〒
376-8515
群馬県桐生市天神町1-5-1 E-mail:
†[email protected],
‡[email protected]
あらましあらまし あらまし
あらまし 複数のスレッドコンテキストから同時にインストラクションを発行し，実行できる，SMTプロセッサ では，同時実行されるスレッドの組合せがシステム利用効率に影響する．従来研究では，より適切なスケジュー ルを探索するためにスケジューリングを２つのフェーズに分けた．1 つ目は，いくつかのスケジュールを評価す るための情報を集める，2 つ目は，得られたサンプリング結果からその時点において最適と予期されるスケジュ ールを決定するフェーズである．本稿では，各ジョブの振る舞いを表すプログラムフェーズを用いることで
1
つ 目のフェーズにおけるサンプリング処理を効率化し，スレッドの実行パフォーマンスが向上することを示す．キーワード キーワード キーワード
キーワード SMT，スレッドスケジューリング
A Thread Scheduling Method for SMT Processor considering Program Phase
Yujiro ICHIKAWA
†and Masayoshi ARITSUGI
‡†
Department of Computer Science, Graduate School of Engineering, Gunma University 1-5-1 Tenjin-cho, Kiryu, Gunma, 376-8515 Japan
‡
Department of Computer Science, Faculty of Engineering Gunma University 1-5-1 Tenjin-cho, Kiryu, Gunma, 376-8515 Japan
E-mail:
†[email protected],
‡[email protected]
Abstract How to combine threads to be executed simultaneously must effect the performance of SMT processor systems in which multiple instructions can be issued from multiple thread contexts and executed. A conventional research divides a scheduling method into two phases for generate a good schedule: one is to collect information in order to evaluate candidate schedules, and the other is to decide the best schedule among them at that moment. In this paper, we extend the former phase to make it efficiency by exploiting program phase, which represents the behavior of each job. We also report some simulation results showing that our proposal can improve the performance of an SMT processor system.
Keyword SMT, Thread Scheduling
1. はじめに
はじめにはじめにはじめにSimultaneous Multithreading
（SMT
）[1,2]
は ， 各 サ イ ク ル で 複 数 の 独 立 す る ジ ョ ブ の 実 行 単 位 ， す な わ ち ， ス レ ッ ド か ら 同 時 に イ ン ス ト ラ ク シ ョ ン を 発 行 し ， ス ー パ ー ス カ ラ プ ロ セ ッ サ に 実 行 さ せ る こ と を 可 能 に し た 技 術 で あ る ．SMT
プ ロ セ ッ サ を 用 い た シ ス テ ム で は ， ス レ ッ ド レ ベ ル 並 列 性 （TLP
） が 命 令 レ ベ ル 並 列 性（
ILP
）に 転 換 さ れ ，命 令 実 行 ス ル ー プ ッ ト が 増 大 し 各 ス レ ッ ド の 実 行 速 度 が 向 上 す る ．図
1
に ， 複 数 の ス レ ッ ド が 存 在 す る 状 況 で のSMT
お よ び 既 存 ア ー キ テ ク チ ャ の 振 る 舞 い を 示 す ． こ の 図 で は ， シ ス テ ム 上 に 実 行 可 能 ス レ ッ ド が5
つ 存 在 し ，SMT
プ ロ セ ッ サ が 同 時 実 行 を サ ポ ー ト す る 数 ，す な わ ち ，ハ ー ド ウ ェ ア コ ン テ キ ス ト 数 が4
つ あ る 場 合 で の ， サ イ ク ル が 進 む に つ れ て 各 ス レ ッ ド か ら イ ン ス ト ラ ク シ ョ ン が 発 行 さ れ る こ と で ス レ ッ ド の 同 時 実 行 が 行 な わ れ る 様 子 を 示 し て い る ． こ の よ う な ， 実 行 可 能 ス レ ッ ド が ハ ー ド ウ ェ ア コ ン テ キ ス ト 数 を 超 え る 状 況 で は ， ス レ ッ ド ス ケ ジ ュ ー ラ は ， ハ ー ド ウ ェ ア コ ン テ キ ス ト の 数 だ け を 実 行 可 能 ス レ ッ ド か ら 選 択 し ， 選 択 さ れ た ス レ ッ ド に イ ン ス ト ラ ク シ ョ ン を 発 行 さ せ る こ と で 同 時 実 行 を 行 な っ て い る ．SMT
プ ロ セ ッ サ 上 で 同 時 実 行 を 行 な う 場 合 ， ハ ー ド ウ ェ ア リ ソ ー ス が 選 択 さ れ た ス レ ッ ド 集 合 間 で 共 有 さ れ る た め ， 実 行 ス レ ッ ド の 組 合92
せ に よ っ て シ ス テ ム の 利 用 効 率 に 違 い が 生 じ る こ と に な る ．そ の た め ，
SMT
シ ス テ ム で は ス ケ ジ ュ ー ラ が 適 切 な 実 行 ス レ ッ ド の 集 合 を 決 定 で き る か が 重 要 と な る ．図
1
複 数 の 実 行 ス レ ッ ド が 存 在 す る 環 境 で の 各 ア ー キ テ ク チ ャ の 振 る 舞 い[1]
Fig1. Behavior of each architecture in an environment where two or more execution threads exist [1]
こ の よ う な 課 題 に 対 し ， 従 来 研 究 で は あ ら か じ め い く つ か の 候 補 ス ケ ジ ュ ー ル を 比 較 す る た め の 情 報 を サ ン プ リ ン グ す る こ と で ， よ り 適 切 な ス ケ ジ ュ ー ル の 探 索 を 行 い ， 結 果 と し て 応 答 速 度 の 向 上 に 繋 が っ た こ と を 示 し て い る
[3]
．し か し ，こ の 研 究 で は サ ン プ リ ン グ に 必 要 と な る サ イ ク ル 数 が 過 多 に な ら な い よ う サ ン プ ル 数 を 少 な い 数 に 抑 え て い る ． そ の た め ， 実 行 ス レ ッ ド の 組 合 せ が 多 く な る 環 境 で は ， サ ン プ ル 数 が 候 補 ス ケ ジ ュ ー ル 数 に 比 べ て わ ず か な も の と な る ． も し ， 比 較 す る 候 補 ス ケ ジ ュ ー ル 数 を 全 候 補 数 に 近 づ け た な ら ば ， よ り 適 切 な ス ケ ジ ュ ー ル を 探 索 す る こ と が で き る と い え る ． 本 研 究 で は ， サ ン プ リ ン グ に 必 要 と す る サ イ ク ル 数 を 増 加 せ ず に ， こ れ を 行 う 方 法 に つ い て 考 え る ．本 研 究 で は ， 従 来 手 法 の ス ケ ジ ュ ー リ ン グ に プ ロ グ ラ ム フ ェ ー ズ を 用 い て ， 比 較 す る 候 補 ス ケ ジ ュ ー ル の 数 を 増 加 し ， よ り 性 能 の 高 い ス ケ ジ ュ ー ル の 実 行 を ね ら う こ と で ， ス レ ッ ド の 実 行 パ フ ォ ー マ ン ス を 向 上 す る こ と を 目 的 と す る ． プ ロ グ ラ ム フ ェ ー ズ と は ， 等 し い 命 令 間 隔 で 各 ジ ョ ブ の 振 る 舞 い を 分 類 し た も の で あ る ． プ ロ グ ラ ム フ ェ ー ズ が 同 一 の 場 合 は ， 該 当 す る 範 囲 間 で そ の 性 能 が 類 似 す る と 考 え ら れ て い る
[5]
．こ の 性 質 を 利 用 し ， 提 案 手 法 で は ， サ ン プ リ ン グ 結 果 を シ ス テ ム 上 に 保 持 し 以 降 の ス ケ ジ ュ ー リ ン グ で 使 用 す る ．本 手 法 の 特 徴 と し て ， 比 較 す る 候 補 ス ケ ジ ュ ー ル の 数 の 増 加 が 挙 げ ら れ る ． 従 来 手 法 で は ， あ る 時 点 に お け る 適 切 な ス ケ ジ ュ ー ル の 探 索 は ， そ の 直 前 に 得 ら れ た 比 較 対 象 の 候 補 ス ケ ジ ュ ー ル の サ ン プ リ ン グ 結 果 に 基 づ い て 行 わ れ る ． そ れ に 対 し ， 本 手 法 で は プ ロ グ ラ ム フ ェ ー ズ の 性 質 に よ り 過 去 に 取 得 し た 結 果 も 利 用 す る こ と が で き る ． ス ケ ジ ュ ー ラ は ， サ ン プ リ ン グ 処 理 の 開 始 時 に ， シ ス テ ム が 保 持 す る 過 去 の サ ン プ リ ン グ
結 果 を 参 照 す る ． も し ， 開 始 さ れ る サ ン プ リ ン グ 処 理 に 関 す る プ ロ グ ラ ム フ ェ ー ズ が ， あ る 過 去 の 結 果 に 関 す る も の と 同 一 で あ る な ら ば ， こ れ か ら 行 わ れ る サ ン プ リ ン グ 処 理 の 結 果 も そ れ と 類 似 す る と 考 え る こ と が で き そ の 処 理 を 省 略 す る こ と が で き る ． 同 一 の も の が 存 在 し な い 場 合 は ， サ ン プ リ ン グ 処 理 を 行 い そ の 結 果 を シ ス テ ム に 格 納 す る ． 省 略 さ れ た 処 理 の 数 が 増 加 す れ ば ，サ ン プ リ ン グ に 用 い る サ イ ク ル 数 を 増 や さ ず に ， 従 来 と 比 べ て 多 く の 候 補 ス ケ ジ ュ ー ル を 比 較 す る こ と が で き る ． こ れ に よ り ， ス ケ ジ ュ ー ラ が よ り 完 全 に 適 切 な ス ケ ジ ュ ー ル を 探 索 す る こ と が で き ， 各 ス レ ッ ド の シ ス テ ム 利 用 効 率 が 向 上 す る こ と が 期 待 で き る ． 実 験 で は ， 従 来 手 法 と 同 一 の サ ン プ リ ン グ に 使 用 す る サ イ ク ル 数 で ， 平 均 の 候 補 ス ケ ジ ュ ー ル 比 較 数 が 増 大 し た こ と が 確 認 で き た ．
以 下 ，
2
章 で 関 連 研 究 に つ い て 述 べ ，3
章 で 提 案 手 法 に つ い て 説 明 す る ．4
章 で 提 案 手 法 の 性 能 評 価 を 行 な い ， 最 後 に5
章 で 本 研 究 の ま と め を 行 な う ．2.
関連研究関連研究関連研究関連研究Symbiotic Jobscheduling [3]
は ，SMT
プ ロ セ ッ サ で 発 生 す る 実 行 ス レ ッ ド 間 で の ハ ー ド ウ ェ ア リ ソ ー ス に 対 す る 相 互 作 用 に 着 目 し た ス ケ ジ ュ ー リ ン グ 手 法 で あ る ． こ の 研 究 で は ， シ ス テ ム 上 に ハ ー ド ウ ェ ア コ ン テ キ ス ト の 数 を 超 え る ス レ ッ ド が 存 在 し ， そ れ ぞ れ が 公 平 に サ イ ク ル を 割 り 当 て ら れ 実 行 さ れ る 環 境 を 想 定 し て い る ． ま た ， ス ケ ジ ュ ー リ ン グ を2
つ の フ ェ ー ズ に 分 け る こ と で よ り 適 切 な 候 補 ス ケ ジ ュ ー ル を 探 索 し ジ ョ ブ 実 行 効 率 を 向 上 さ せ て い る ．候 補 ス ケ ジ ュ ー ル は ， タ イ ム ス ラ イ ス が 複 数 集 ま る こ と で 構 成 さ れ る ． タ イ ム ス ラ イ ス は ， ハ ー ド ウ ェ ア コ ン テ キ ス ト の 数 だ け ス レ ッ ド 識 別 子 を 持 ち ， あ る 時 点 に お い て ど の ス レ ッ ド を 同 時 実 行 す る か を 示 す ． タ イ ム ス ラ イ ス が 開 始 さ れ る と き ， そ れ が 持 つ 識 別 子 に 該 当 す る ス レ ッ ド に イ ン ス ト ラ ク シ ョ ン を 発 行 さ せ る こ と で ス レ ッ ド の 同 時 実 行 が 行 な わ れ る ． 同 時 実 行 の 対 象 で あ る ス レ ッ ド を ア ク テ ィ ブ ス レ ッ ド ， そ れ 以 外 の も の を ノ ン ア ク テ ィ ブ ス レ ッ ド と 呼 ぶ ． 候 補 ス ケ ジ ュ ー ル の 生 成 は ， ス レ ッ ド 数 ， ハ ー ド ウ ェ ア コ ン テ キ ス ト 数 ， ま た ， タ イ ム ス ラ イ ス 終 了 時 に ア ク テ ィ ブ ・ ノ ン ア ク テ ィ ブ を 切 り 替 え る ス レ ッ ド 数 ， と い う パ ラ メ ー タ で 候 補 ス ケ ジ ュ ー ル の 生 成 が 行 な わ れ る ．
図
2
に ， ス レ ッ ド 数 を8
， ハ ー ド ウ ェ ア コ ン テ キ ス ト 数 を4
， 切 り 替 え ス レ ッ ド 数 を1
と し た と き の 候 補 ス ケ ジ ュ ー ル の 例 とSMT
上 で の 実 行 の 様 子 を 示 す ．ま ず ， 候 補 ス ケ ジ ュ ー ル の 生 成 は ， そ れ が い く つ の タ イ ム ス ラ イ ス を 持 つ か 決 定 す る こ と か ら 始 ま る ． 図2
で は ，最 も 左 の 初 期 タ イ ム ス ラ イ ス が ス レ ッ ド 識 別 子 ，0
，93
2
，3
，5
，を 持 つ ．こ れ ら は ，8
個 の ス レ ッ ド の 識 別 子0
～7
よ り ラ ン ダ ム に4
つ 選 択 し た も の で あ る ．次 の タ イ ム ス ラ イ ス で は ，選 択 さ れ て い る ス レ ッ ド 識 別 子 を ， 切 り 替 え ス レ ッ ド 数 の 数 ， こ こ で は1
つ だ け を 選 択 さ れ て い な い ス レ ッ ド 識 別 子 と 入 れ 替 え る ．図2
で は ，2
番 目 の タ イ ム ス ラ イ ス で ， ス レ ッ ド識 別 子3
の 代 わ り に4
が 含 ま れ て い る ． こ の よ う に し て ， 各 ス レ ッ ド が ア ク テ ィ ブ に な る 回 数 が 同 一 に な る ま で タ イ ム ス ラ イ ス を 増 加 す る ．あ る 候 補 ス ケ ジ ュ ー ル 内 で 各 ス レ ッ ド が ア ク テ ィ ブ に な る 回 数 を 同 じ に す る の は ， シ ス テ ム が 各 ス レ ッ ド に 対 し て 公 平 に 同 時 実 行 の た め の サ イ ク ル を 割 り 当 て る こ と を 考 え な け れ ば な ら な い か ら で あ る ． 候 補 ス ケ ジ ュ ー ル に 与 え ら れ る サ イ ク ル は ， そ れ を 構 成 す る タ イ ム ス ラ イ ス 間 で 等 し く 分 割 さ れ る ． 図
2
で は ， 候 補 ス ケ ジ ュ ー ル にn
サ イ ク ル 与 え ら れ た と き ， 各 タ イ ム ス ラ イ ス は1n/8
サ イ ク ル の 間 だ け 開 始 さ れ る こ と が 示 さ れ て い る ． ま た ， こ こ で は 各 ス レ ッ ド が4
回 ず つ ア ク テ ィ ブ に な る ．よ っ て ，そ れ ぞ れ が4*1n/8
サ イ ク ル だ け 同 時 実 行 の た め の サ イ ク ル が 与 え ら れ る こ と に な る ． ま た ， 候 補 ス ケ ジ ュ ー ル は 複 数 存 在 す る ． 候 補 ス ケ ジ ュ ー ル は ， 各 ス レ ッ ド が ア ク テ ィ ブ に な る タ イ ミ ン グ に よ っ て 異 な る ． 例 え ば ， 図2
で 示 し た 候 補 ス ケ ジ ュ ー ル は ， 初 期 タ イ ム ス ラ イ ス の ア ク テ ィ ブ ス レ ッ ド が ，0
，2
，3
，5
， で あ る が ， 別 の 候 補 ス ケ ジ ュ ー ル で は ， こ れ が ，1
，2
，4
，7
， に な る 場 合 も あ る ．図
2
候 補 ス ケ ジ ュ ー ル の 例 とSMT
上 で の 実 行Fig2. Example of a possible schedule
and execution on SMT
タ イ ム ス ラ イ ス で は ， ア ク テ ィ ブ ス レ ッ ド が ハ ー ド ウ ェ ア リ ソ ー ス を 競 合 す る 可 能 性 が あ る ． 競 合 の 度 合 い は ， 同 時 実 行 さ れ る 各 ス レ ッ ド の動 作 よ っ て 変 化 す る ． 例 え ば ， あ る 実 行 ス レ ッ ド が メ モ リ ア ク セ ス 待 ち 状 態 で
SMT
プ ロ セ ッ サ に 対 し イ ン ス ト ラ ク シ ョ ン を発 行 し な い と き ， そ の 分 別 の 実 行 ス レ ッ ド が ハ ー ド ウ ェ ア リ ソ ー ス を 利 用 す る こ と が で き る ． 従 っ て ， 候 補 ス ケ ジ ュ ー ル 間 で シ ス テ ム の 利 用 効 率 に 違 い が 生 じ る こ と に な る ．
ス ケ ジ ュ ー リ ン グ は
Sample Phase
，Symbiosis Phase
と い う2
つ の フ ェ ー ズ で 行 な わ れ る[3]
．こ れ ら は ，各 自 設 定 さ れ た サ イ ク ル 数 に 基 づ い て順 番 に 切 り 替 え て い く ．初 期 状 態 はSample Phase
で あ り ，こ こ で は ス ケ ジ ュ ー ラ が よ り 適 切 な ス ケ ジ ュ ー ル を 探 索 す る た め の 情 報 を 集 め る ． ま ず ， 候 補 ス ケ ジ ュ ー ル を い く つ か ラ ン ダ ム で 選 択 す る ． 選 び 出 さ れ た 候 補 ス ケ ジ ュ ー ル は サ ン プ ル ス ケ ジ ュ ー ル と し て 扱 い ， そ れ ぞ れ 順 番 に 同 じ サ イ ク ル 数 を 割 り 当 て タ イ ム ス ラ イ ス 内 の ス レ ッ ド を 実 行 す る ．そ の 際 ，ス ケ ジ ュ ー ラ はCPU
の ハ ー ド ウ ェ ア パ フ ォ ー マ ン ス カ ウ ン タ よ り 候 補 ス ケ ジ ュ ー ル を 比 較 す る た め の 情 報 を 集 め る ． こ れ は ，IPC
や キ ャ ッ シ ュ ミ ス 率 を 計 算 す る こ と で 行 な わ れ る ．Sample Phase
終 了 後 ， ス ケ ジ ュ ー ラ はSymbiosis Phase
に 切 り 替 わ る ．Symbiosis Phase
で は ，直 前 に 得 ら れ た サ ン プ ル ス ケ ジ ュ ー ル の 内 ， 最 も 良 い 結 果 を 出 し た も の を そ の 時 点 に お け る 最 適 な ス ケ ジ ュ ー ル と し て 考 え ， タ イ ム ス ラ イ ス 内 の ス レ ッ ド を 実 行 す る ．Symbiotic Jobscheduling[3]
に よ っ て 応 答 速 度 の 向 上 が 示 さ れ て い る ， し か し ， サ ン プ リ ン グ に 使 用 す る サ イ ク ル 数 が 過 多 に な ら な い よ う ， サ ン プ ル 数 を 少 な い 数 に 抑 え て い る ．[3]
で は ，候 補 ス ケ ジ ュ ー ル 数 が2520
に 対 し て サ ン プ ル 数 が10
で あ る 実 験 が 行 な わ れ て い た ． こ の 場 合 ， サ ン プ リ ン グ に よ っ て 判 断 し た ス ケ ジ ュ ー ル が 全 ス ケ ジ ュ ー ル の 中 で ど の く ら い 適 切 で あ る か が 疑 問 と な る ． 本 研 究 で は ， こ の 問 題 に 着 目 し ，Symbiotic Jobscheduling[3]
を 従 来 手 法 と す る こ と で ，新 し いSMT
上 で の ス レ ッ ド ス ケ ジ ュ ー リ ン グ 手 法 を 提 案 す る ．[4]
で は ，[5]
で 示 さ れ て い る プ ロ グ ラ ム フ ェ ー ズ を 利 用 し て ，SMT
上 で2
つ の プ ロ グ ラ ム を 動 か し た 場 合 で の 性 能 評 価 を 行 う 研 究 を 行 っ て い る ． こ の 研 究 で は ， プ ロ グ ラ ム フ ェ ー ズ の 性 質 を 利 用 す る こ と で ， プ ロ グ ラ ム 同 時 実 行 を 終 始 行 う こ と な く ， 同 時 実 行 全 体 の 性 能 を 計 測 す る ．[4]
と 本 研 究 の 違 い は ，ま ず ，本 研 究 で は ハ ー ド ウ ェ ア コ ン テ キ ス ト の 数 を 超 え る ス レ ッ ド が 存 在 す る 環 境 を 想 定 し て い る ． そ し て ， 同 時 実 行 全 体 の 性 能 を 計 測 す る こ と で は な く ， 多 数 の 実 行 ス レ ッ ド の 組 合 せ が 存 在 す る 状 況 で 適 切 な ス ケ ジ ュ ー リ ン グ を 行 う た め に プ ロ グ ラ ム フ ェ ー ズ を 用 い る こ と を 考 え る 点 で あ る ．94
3. プ ロ グ ラ ム フ ェ ー ズ
プ ロ グ ラ ム フ ェ ー ズプ ロ グ ラ ム フ ェ ー ズプ ロ グ ラ ム フ ェ ー ズ をををを 考 慮考 慮考 慮 し た考 慮し たし たし た ス レ ッ ド スス レ ッ ド スス レ ッ ド スス レ ッ ド ス ケジューリングケジューリングケジューリング ケジューリング
本 研 究 で は ，従 来 手 法
[3]
の ス ケ ジ ュ ー リ ン グ に プ ロ グ ラ ム フ ェ ー ズ を 用 い て ， 比 較 す る 候 補 ス ケ ジ ュ ー ル の 数 を 増 加 し,
よ り 性 能 の 高 い ス ケ ジ ュ ー ル の 実 行 を ね ら う こ と で ， ス レ ッ ド の 実 行 パ フ ォ ー マ ン ス を 向 上 さ せ る こ と を 目 的 と す る ． こ こ で は ， ま ず ， プ ロ グ ラ ム フ ェ ー ズ を 用 い た 場 合 の 特 徴 を 述 べ る ． 続 い て ，2
で 説 明 し た 従 来 手 法 を 拡 張 し ， プ ロ グ ラ ム フ ェ ー ズ を 考 慮 し た ス レ ッ ド ス ケ ジ ュ ー ラ の 実装 に 関 し て 具 体 的 に 説 明 す る ．3.1.
プログラムフェーズプログラムフェーズプログラムフェーズプログラムフェーズプ ロ グ ラ ム フ ェ ー ズ と は ， あ る ジ ョ ブ を 等 し い 命 令 間 隔 で 分 割 し ， そ れ ぞ れ を そ の 振 る 舞 い に 関 し て 分 類 し た も の で あ る ．プ ロ グ ラ ム フ ェ ー ズ が 同 一 の 場 合 は ， 該 当 す る 範 囲 間 で そ の 性 能 が 類 似 す る と 考 え ら れ て い る
[5]
．各 ジ ョ ブ の プ ロ グ ラ ム フ ェ ー ズ は ，SimPoint[6]
に よ っ て 得 る こ と が で き る ．
プ ロ グ ラ ム フ ェ ー ズ の 性 質 を 利 用 す る こ と で ， ス ケ ジ ュ ー ラ は 過 去 に 得 ら れ た サ ン プ リ ン グ 結 果 を 利 用 す る こ と が で き る ． つ ま り ， あ る タ イ ム ス ラ イ ス の サ ン プ リ ン グ 開 始 時 に ， シ ス テ ム が 保 持 す る 過 去 の サ ン プ リ ン グ 結 果 を 参 照 し 可 能 な ら ば サ ン プ リ ン グ 処 理 を 省 略 す る こ と が で き る ．そ の 結 果 ，従 来 手 法
[3]
に 比 べ 多 く の 候 補 ス ケ ジ ュ ー ル に 対 し て 比 較 を 行 う こ と が で き る ．サ ン プ リ ン グ 処 理 を 省 略 で き る か ど う か は ， ス ケ ジ ュ ー ラ が 実 行 中 の タ イ ム ス ラ イ ス に 関 す る プ ロ グ ラ ム フ ェ ー ズ ， す な わ ち ， そ の タ イ ム ス ラ イ ス を 構 成 す る ス レ ッ ド の
ID
と プ ロ グ ラ ム フ ェ ー ズ の 集 合 と 同 一 の も の が シ ス テ ム 上 に 保 持 さ れ て い る か で 判 断 す る ． こ の た め に ， 本 研 究 で は ， シ ス テ ム 上 に サ ン プ リ ン グ 結 果 を 保 持 す る 仕 組 み を 用 意 し ， ス ケ ジ ュ ー ラ は 必 要 に 応 じ て こ れ に ア ク セ ス す る 処 理 を 追 加 す る こ と を 考 え る ．具 体 的 に は ，TaskPhaseTable
，CoPhaseTable
と い う2
つ の テ ー ブ ル を 追 加 し ， ス ケ ジ ュ ー ラ が こ れ ら を 利 用 し て 目 的 を 達 成 す る よ う 処 理 を 拡 張 す る ．3.2.
スレッドスケジューラスレッドスケジューラのスレッドスケジューラスレッドスケジューラのの実装の実装実装実装本 手 法 で は ， ス ケ ジ ュ ー ラ が 過 去 に 取 得 し た サ ン プ リ ン グ 結 果 を 利 用 す る た め の 仕 組 み と し て ， ま ず ，
TaskPhaseTable
，CoPhaseTable
と い う2
つ の テ ー ブ ル を 追 加 す る ． 図3
， 図4
に 各 テ ー ブ ル の 例 を 示 す ．TaskPhaseTable
は ，SimPoint[6]
に よ っ て 得 ら れ た あ る ジ ョ ブ に 関 す る プ ロ グ ラ ム フ ェ ー ズ 識 別 子 を 保 持 す る も の で あ る ． 本 研 究 で は そ の 識 別 子 と し て 整 数 を 使 用 し た ．TaskPhaseTable
の 各 レ コ ー ド 間 に は 等 し い 命 令 間 隔 が あ り ， ス ケ ジ ュ ー ラ は ， あ る ス レ ッ ド が 現 在 の プ ロ グ ラ ム フ ェ ー ズ 識 別 子 を 取 得 す る ． 図3
で は ，あ る ジ ョ ブ が
10M
の イ ン ス ト ラ ク シ ョ ン 間 隔 で 分 割 さ れ ， 各 間 隔 が 整 数 値 ， 例 え ば ，0
～10M
の 範 囲 で は プ ロ グ ラ ム フ ェ ー ズ 識 別 子 が10
，を 持 つ こ と が 示 さ れ て い る ． そ し て ，TaskPhaseTable
を 作 成 す る 際 は ， ジ ョ ブ 開 始 方 向 か ら 終 了 方 向 に 向 け て ， 各 イ ン ス ト ラ ク シ ョ ン 間 隔 の プ ロ グ ラ ム フ ェ ー ズ 識 別 子 を 格 納 し て い く ． ス ケ ジ ュ ー ラ が ，TaskPhaseTable
よ り ス レ ッ ド の 現 在 の フ ェ ー ズ を 取 得 す る と き は ， そ の ス レ ッ ド が 実 行 し た イ ン ス ト ラ ク シ ョ ン 数 を 引 数 に す る ． 図3
を 例 に 取 る と ，ス レ ッ ド が11M
イ ン ス ト ラ ク シ ョ ン 実 行 し た な ら ば ，11/10=1.1
≦2
よ りTaskPhaseTable
の2
番 目 の レ コ ー ド に 格 納 さ れ て い る プ ロ グ ラ ム フ ェ ー ズ 識 別 子8
が 得 ら れ る ．CoPhaseTable
は ， サ ン プ リ ン グ 処 理 が 行 わ れ た と き の ， タ イ ム ス ラ イ ス が 持 つ ス レ ッ ド 識 別 子 と ， 処 理 が 開 始 さ れ た 時 点 でTaskPhaseTable
よ り 取 得 し た 各 ス レ ッ ド の プ ロ グ ラ ム フ ェ ー ズ 識 別 子 か ら な るCoPhase
エ ン ト リ と ， サ ン プ リ ン グ 終 了 時 に 計 算 す る 性 能 結 果SCORE
で 構 成 さ れ る ．図4
を 例 に 取 る と ，あ る 候 補 ス ケ ジ ュ ー ル の ， 左 よ り3
番 目 の タ イ ム ス ラ イ ス に 関 し て サ ン プ リ ン グ 処 理 が 行 わ れ る と き ， ま ず ， ス レ ッ ド 識 別 子 ，2
，4
，5
，7
， の ス レ ッ ド そ れ ぞ れ に 関 し てTaskPhaseTable
よ り プ ロ グ ラ ム フ ェ ー ズ 識 別 子 を 取 得 す る ． こ こ で は ， 得 ら れ た プ ロ グ ラ ム フ ェ ー ズ 識 別 子 を そ れ ぞ れ ，16
，6
，14
，3
， と す る ． こ れ ら2
種 類 の 識 別 子 に よ り ， こ の タ イ ム ス ラ イ ス に 関 す るCoPhase
エ ン ト リ は ，{{ThreadID}{ProgramPhaseID}}
= {{2,4,5,7}{16,6,14,3}}
と な る ． そ し て ， サ ン プ リ ン グ 終 了 時 に 計 算 し た 性 能 結 果 ，例 え ば ，
IPC=2.13
，を 開 始 時 に 作 成 し たCoPhase
エ ン ト リ と 共 にCoPhaseTable
に 格 納 す る ．図
3 TaskPhaseTable
の 例Fig3. Example of a TaskPhaseTable
95
図
4 CoPhaseTable
へ の サ ン プ リ ン グ 結 果 の 格 納Fig4. Example of inserting a sampling result
into CoPhaseTable
本 研 究 で は ，従 来 手 法
[3]
の ス ケ ジ ュ ー リ ン グ 処 理 に 対 し ， 上 の2
つ の テ ー ブ ル に ア ク セ ス す る 処 理 を 追 加 し ， 拡 張 す る ． 図5
， 図6
に ， 本 手 法 に お け る ス ケ ジ ュ ー リ ン グ 処 理 の 実 行 の 流 れ を 示 す ．Sample Phase
で は ， あ る タ イ ム ス ラ イ ス の サ ン プ リ ン グ 開 始 時 に ， ま ず そ れ を 構 成 す る ス レ ッ ドID
お よ び プ ロ グ ラ ム フ ェ ー ズ の 集 合 か らCoPhase
エ ン ト リ を 生 成 し ，そ れ と 同 一 の も の がCoPhaseTable
内 に 存 在 す る か 調 べ る ． 同 一 の エ ン ト リ が 存 在 し た 場 合 ， ス ケ ジ ュ ー ラ は ， そ の レ コ ー ド に 含 ま れ る サ ン プ リ ン グ 結 果 値 を ， 開 始 し た タ イ ム ス ラ イ ス の 結 果 値 と し て 扱 い 以 降 の サ ン プ リ ン グ 処 理 を 省 略 す る ．エ ン ト リ が 存 在 し な い 場 合 は ， 従 来 通 り そ の タ イ ム ス ラ イ ス の サ ン プ リ ン グ 処 理 を 行 う ． そ し て ， 得 ら れ た 結 果 を 開 始 時 に 作 成 し たCoPhase
エ ン ト リ と 共 にCoPhaseTable
に 格 納 す る ． こ の と き ，CoPhaseTable
に 設 定 さ れ て い る 最 大 レ コ ー ド 数 を 上 回 る 場 合 は ， 既 存 の レ コ ー ド を 上 書 き す る ． 本 実 験 で は ， 最 後 に 参 照 さ れ た レ コ ー ド を 上 書 き す る 方 式 で 更 新 す る こ と と し た ．図
5 Sample Phase
の 実 行 の 流 れFig5. Flow of execution in Sample Phase
図
6 Symbiosis Phase
の 実 行 の 流 れFig6. Flow of execution in Symbiosis Phase
従 来 手 法 に 対 し ，本 手 法 で は ，Symbiosis Phase
で も ス ケ ジ ュ ー ル の 性 能 に 関 す る 情 報 の収 集 を 行 な う ． こ れ は ，Sample Phase
で 得 ら れ た サ ン プ リ ン グ 結 果 値 とSymbiosis Phase
に お け る 実 測 値 の 違 い を 考 慮 す る た め で あ る ． 従 来 手 法 で は ， 両 方 の 値 に 違 い が 見 ら れ て も 以 降 の ス ケ ジ ュ ー リ ン グ に そ れ が 活 か さ れ る こ と は な か っ た ．そ れ に 対 し ，本 手 法 で はSymbiosis Phase
で 取 得 し た サ ン プ リ ン グ 結 果 値 をCoPhaseTable
に 反 映 す る こ と が で き る ．Symbiosis Phase
に お い て 取 得 し た サ ン プ リ ン グ 結 果 は ，CoPhaseTable
内 に 同 一 のCoPhase
エ ン ト リ が 存 在 す る 場 合 で も 結 果 値 を 上 書 き さ せ る ． こ れ に よ り ， よ り 精 度 の 高 い 適 切 な 候 補 ス ケ ジ ュ ー ル の 探 索 を 行 う こ と が で き る と 考 え ら れ る ．4.
実験実験実験実験4.1. 実験環境
実験環境実験環境実験環境本 実 験 で は ， シ ス テ ム 上 に ハ ー ド ウ ェ ア コ ン テ キ ス ト 数 を 超 え る ジ ョ ブ が 存 在 す る 状 況 に お け る 複 数 の ス ケ ジ ュ ー リ ン グ 手 法 の 比 較 実 験 を 行 っ た ． 実 験 対 象 と な る ス ケ ジ ュ ー リ ン グ 手 法 に は ，本 手 法 ，従 来 手 法
[3]
， お よ び ラ ウ ン ド ロ ビ ン ス ケ ジ ュ ー リ ン グ を 選 択 し た ． ラ ウ ン ド ロ ビ ン で は ， ス ケ ジ ュ ー ラ は サ ン プ リ ン グ 処 理 を 行 わ ず ， 一 定 の サ イ ク ル 間 隔 で ラ ン ダ ム に 候 補 ス ケ ジ ュ ー ル を1
つ 選 択 し 各 ジ ョ ブ を 実 行 す る ． こ の サ イ ク ル 間 隔 は ，他 の 手 法 に お け るSymbiosis Phase
で 使 用 す る サ イ ク ル 数 と 同 一 と す る ．本 実 験 を 行 っ た 環 境 に つ い て 説 明 す る ．
SMT
プ ロ セ ッ サ の シ ミ ュ レ ー タ と し てSMTSIM[7,8]
を 選 択 し ， 実 行 ジ ョ ブ に はSPEC
ベ ン チ マ ー ク[9]
よ り ，crafty
，equake
，gcc-166
，gcc-200
，gcc-expr
，gzip-log
，gzip-graphic
，gzip-source
， を 使 用 し た ． ま た ， 実 験 を 行 う 上 で 設 定96
す る 必 要 が あ る パ ラ メ ー タ が い く つ か 存 在 す る ．ま ず ， ス ケ ジ ュ ー ル を 生 成 す る た め の ， ジ ョ ブ 数 ， ハ ー ド ウ ェ ア コ ン テ キ ス ト 数 ， お よ び ， タ イ ム ス ラ イ ス 終 了 時 に ア ク テ ィ ブ ・ ノ ン ア ク テ ィ ブ を 切 り 替 え る ス レ ッ ド 数 で あ る ． ま た ，
Sample Phase
，Sample Phase
で 取 得 す る サ ン プ ル の 最 小 数 ，Symbiosis Phase
で 使 用 す る サ イ ク ル 数 ，TaskPhaseTable
の 各 レ コ ー ド 間 に あ る 命 令 間 隔 ，そ し てCoPhaseTable
の 最 大 レ コ ー ド 数 が 挙 げ ら れ る ．表1
に 今 回 設 定 し た パ ラ メ ー タ と そ の 値 を 示 す ．実 験 で は ， 各 ス ケ ジ ュ ー リ ン グ 手 法 を 比 較 す る た め の 指 標 と し て
IPC
を 選 択 し た ．そ し て ，各 ス ケ ジ ュ ー リ ン グ 手 法 の ス レ ッ ド 実 行 パ フ ォ ー マ ン ス を 求 め た ． ス レ ッ ド 実 行 パ フ ォ ー マ ン ス は ， 以 下 の 式 に よ っ て 計 算 す る ．こ の 式 に お け る ス ケ ジ ュ ー ル は ， 本 手 法 お よ び 従 来 手 法
[3]
で はSymbiosis Phase
で 選 択 さ れ た 候 補 ス ケ ジ ュ ー ル ， ラ ウ ン ド ロ ビ ン ス ケ ジ ュ ー リ ン グ で は ラ ン ダ ム に 選 択 さ れ た 候 補 ス ケ ジ ュ ー ル と な る ．ま た ，本 手 法 の 性 能 を 確 認 す る た め に ，
Sample Phase
で 比 較 し た 候 補 ス ケ ジ ュ ー ル の 数 と ， 他 の 手 法 に 対 す る 性 能 の 増 加 率 を 次 の 式 を 用 い て 求 め た ．表
1
本 実 験 で 設 定 し た パ ラ メ ー タTable1. Parameters set by our experiment
Number of Jobs 8
Multithreading 4
Number of Swapped Threads
1 (Possible Schedules) (2520) Number of Samples 10 CYCLE of
Sample Phase
100000 CYCLE of
Symbiosis Phase
1000000 Instruction Interval
of TaskPhaseTable
10000000 Max Records
of CoPhaseTable
5000000
4.2. 実験環境
実験環境実験環境実験環境本 研 究 の 目 的 は ， 従 来 手 法 の ス ケ ジ ュ ー リ ン グ に プ ロ グ ラ ム フ ェ ー ズ を 用 い る こ と で ， 比 較 す る 候 補 ス ケ ジ ュ ー ル の 数 を 増 加 し ， よ り 性 能 の 高 い ス ケ ジ ュ ー ル の 実 行 を ね ら う こ と で ス レ ッ ド の 実 行 パ フ ォ ー マ ン ス を 向 上 さ せ る こ と で あ る ． そ れ を 確 認 す る た め に
4.1
で 説 明 し た 実 験 の 結 果 を 示 す ．ま ず ，図
7
に 本 手 法 に お け る 各Sample Phase
で 比 較 し た 候 補 ス ケ ジ ュ ー ル の 数 を 示 す ． 図7
で は 確 認 で き な い が ， 実 験 開 始 直 後 で は シ ス テ ム が 保 持 す る サ ン プ リ ン グ 結 果 が 少 な い た め ， 比 較 し た 候 補 ス ケ ジ ュ ー ル が15
前 後 と い っ た 数 で あ っ た ．こ の 数 は ，ス ケ ジ ュ ー ラ が ，サ ン プ リ ン グ 結 果 をCoPhaseTable
に 格 納 す る に つ れ て 増 加 し ， 実 験 終 了 時 ま で 従 来 手 法 よ り 多 く の 候 補 ス ケ ジ ュ ー ル を 比 較 し た こ と が 分 か る ．図
7 Sample Phase
で 比 較 し た 候 補 ス ケ ジ ュ ー ル の 数Fig7. Number of possible schedules that
compared in Sample Phase
続 い て ， 各 ス ケ ジ ュ ー リ ン グ 手 法 の ス レ ッ ド 実 行 の パ フ ォ ー マ ン ス を 図
8
， 図9
， 図10
に 示 す ． ラ ウ ン ド ロ ビ ン 形 式 で は ， ス ケ ジ ュ ー ル の 実 行 パ フ ォ ー マ ン ス に ば ら つ き が 見 ら れ た ． こ れ は ， ラ ン ダ ム に 選 択 さ れ た 候 補 ス ケ ジ ュ ー ル の 中 に 適 切 で な い も の が 含 ま れ る こ と で ， 実 行 ス レ ッ ド 間 で の ハ ー ド ウ ェ ア リ ソ ー ス 競 合 の 度 合 い が 高 く な る 状 況 が 発 生 し た か ら だ と 考 え ら れ る ．そ れ に 対 し て ，本 手 法 お よ び 従 来 手 法[3]
は ，ス ケ ジ ュ ー ル の 実 行 パ フ ォ ー マ ン ス が安 定 す る 結 果 と な っ た ． こ れ に よ り ， ス ケ ジ ュ ー ラ は サ ン プ リ ン グ を 行 う こ と で ス レ ッ ド に 安 定 し た シ ス テ ム 利 用 効 率 を 提 供 す る こ と が で き る と い え る ．最 後 に ， 図
11
， 図12
で ， ラ ウ ン ド ロ ビ ン ス ケ ジ ュ ー リ ン グ ， お よ び 従 来 手 法 に 対 す る に 本 手 法 の 性 能 増 加 率 を 示 す ． 本 手 法 で は ， ラ ウ ン ド ロ ビ ン ス ケ ジ ュ ー リ ン グ に 対 し て は 大 幅 に ス ケ ジ ュ ー ル 実 行 パ フ ォ ー マ ン ス を 伸 ば す こ と が で き た ． 従 来 手 法 に 対 し て も ， 実 行 し た ス ケ ジ ュ ー ル の50.7%
が1
を 超 え る 性 能 増 加 率97
を 示 し ， そ の 内
12.5%
が1.3
を 超 え る 結 果 と な っ た ， ま た ，0.7
を 下 回 る 性 能 増 加 率 を 示 し た も の は 全 体 の6.32%
で あ っ た ． 以 上 よ り ， 本 手 法 は ， 従 来 手 法 に 対 し て ， ス レ ッ ド 実 行 パ フ ォ ー マ ン ス を 向 上 さ せ る こ と が で き る と い え る ．図
8
ラ ウ ン ド ロ ビ ン ス ケ ジ ュ ー リ ン グ の ス レ ッ ド 実 行 パ フ ォ ー マ ン スFig8. Execution performance of threads
for Round-Robin Scheduling
図
9
従 来 手 法 の ス レ ッ ド 実 行 パ フ ォ ー マ ン スFig9. Execution performance of threads
for the conventional method
図
10
本 手 法 の ス レ ッ ド 実 行 パ フ ォ ー マ ン スFig10. Execution performance of threads for our method
図
11
ラ ウ ン ド ロ ビ ン ス ケ ジ ュ ー リ ン グ に 対 す る 本 手 法 の 性 能 増 加 率Fig11. Performance improvement rate of our method against Round-Robin Scheduling
図
12
従 来 手 法 に 対 す る 本 手 法 の 性 能 増 加 率Fig12. Performance improvement rate of our method
against the conventional method
5.
まとめまとめまとめまとめ本 稿 で は ，比 較 す る 候 補 ス ケ ジ ュ ー ル の 数 を 増 加 し
,
よ り 性 能 の 高 い ス ケ ジ ュ ー ル の 実 行 を ね ら う こ と で ， ス レ ッ ド の 実 行 パ フ ォ ー マ ン ス を 向 上 さ せ る こ と を 目 的 と し ， 従 来 手 法 に プ ロ グ ラ ム フ ェ ー ズ を 用 い た ス レ ッ ド ス ケ ジ ュ ー リ ン グ 手 法 を 提 案 し た ． 本 手 法 で は ，TaskPhaseTable
，CoPhaseTable
と い う2
つ の テ ー ブ ル を 追 加 し ， ス ケ ジ ュ ー ラ が こ れ ら に ア ク セ ス す る よ う 処 理 を 拡 張 す る ． ス ケ ジ ュ ー ラ は ， サ ン プ リ ン グ 処 理 の 開 始 時 に ， シ ス テ ム が 保 持 す る 過 去 の サ ン プ リ ン グ 結 果 を 参 照 す る ． も し ， 開 始 さ れ る サ ン プ リ ン グ 処 理 に 関 す る プ ロ グ ラ ム フ ェ ー ズ が ， あ る 過 去 の 結 果 に 関 す る も の と 同 一 で あ る な ら ば ， こ れ か ら 行 わ れ る サ ン プ リ ン グ 処 理 の 結 果 も そ れ と 類 似 す る と 考 え る こ と が で き そ の 処 理 を 省 略 す る こ と が で き る ． 実 験 に よ っ て ， 本 手 法 は ， 比 較 す る 候 補 ス ケ ジ ュ ー ル の 数 が 増 え ， 他 の 手 法 に 対 し て ス ケ ジ ュ ー ル 実 行 性 能 の 増 加 し た こ と が 確 認 で き た ．今 後 の 課 題 と し て ， 使 用 し た ジ ョ ブ の 性 質 と 候 補 ス
98
ケ ジ ュ ー ル を 比 較 す る た め の 指 標 と の 関 係 に 着 目 し ， 本 手 法 の 性 能 評 価 を 行 な う こ と が 挙 げ ら れ る ．今 回 は ， 指 標 と し て
IPC
を 選 択 し た が ，も し 使 用 す る ジ ョ ブ が デ ー タ 集 中 的 な も の で あ る な ら ば ，IPC
で は な く キ ャ ッ シ ュ ミ ス 率 で 候 補 ス ケ ジ ュ ー ル の 比 較 を 行 な っ た 方 が ， ス ケ ジ ュ ー ラ が 判 断 し た 適 切 な ス ケ ジ ュ ー ル に よ る ス レ ッ ド 実 行 パ フ ォ ー マ ン ス が 高 く な る の で は な い か と 考 え ら れ る ．謝 謝謝 謝
辞辞辞辞
本 研 究 の 一 部 は ， 科 学 研 究 費 補 助 金 基 盤 研 究
(C)(18500073)
に よ り 行 な わ れ た ．文文文 文
献献献献
[1] D. Tullsen, S. Eggers, J. Emer, H. Levy, J. Lo, and R.
Stamm. Exploiting choice: Instruction fetch and issue on an implementable simultaneous multithreading processor. In ISCA96, pages 191-202, May 1996.
[2] J. L. Lo, S. J. Eggers, J. S. Emer, H. M. Levy, R. L.
Stamm, and D. Tullsen. Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading. ACM Transactions on Computer Systems, Volume 15, Issue 3, Pages 322 - 354, Aug. 1997.
[3] A. Snavely and D. Tullsen. Symbiotic jobscheduling for a simultaneously multithreading processor. In Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, Pages 234 - 244, Nov. 2000.
[4] M. V. Biesbrouck, T. Sherwood, B. Calder. A Co-Phase Matrix to Guide Simulation Multithreading Simulation. In IEEE International Symposium on Performance Analysis of Systems and Software, Pages 45 - 56, March 2004.
[5] T. Sherwood, E. Perelman, G. Hamerly, and B.
Calder. Automatically characterizing large scale program behavior. In 10th International Conference on Architectural Support for Programming, Pages 45 - 57, October 2002.
[6] G. Harmerly, E. Perelman, J. Lau, B. Calder.
SimPoint 3.0: Faster and More Flexible Program Analysis.
[7] SMTSIM,
<http://www-cse.ucsd.edu/~tullsen/smtsim.html>
[8] D. M. Tullsen, S. Eggers, and H. Levy. Simulation and modeling of a simultaneous multithreading processor. In 22nd Annual Computer Measurement Group Conference, Dec. 1996.
[9] SPEC Benchmarks, <http://www.spec.org/>
99
![図 1 複 数 の 実 行 ス レ ッ ド が 存 在 す る 環 境 で の 各 ア ー キ テ ク チ ャ の 振 る 舞 い [1]](https://thumb-ap.123doks.com/thumbv2/123deta/5677144.2011190/3.892.92.420.194.408/数実行スレッド存在する環境各ア.webp)
