制約条件 - 奈良先端科学技術大学院大学

ハイパースレッディングとターボブーストを考慮した
マルチコア向けタスクスケジューリングアルゴリズムの提案
指導教員：伊藤実教授†1，柴田直樹准教授†3，安本慶一教授†1，北道淳司上級准教授†2
学生：脇坂洋祐（M1）†1
研究背景

■タスクスケジューリング問題
マルチコアプロセッサの普及
•今回対象とする問題はNP困難な問題
•最新のプロセッサはほとんどマルチコア
•実行効率の良い近似アルゴリズムが求められる
•最近のマルチコアプロセッサの特徴
•ハイパースレッディング
•ターボブースト
•上記の技術を考慮したスケジューリング手法は存在しない
マルチコアプロセッサの構成例
本研究の目的：ハイパースレッディングとターボブーストによる動作周波数の変化を考慮し
タスクの処理時間を短縮するタスクスケジューリングアルゴリズムの提案
モデル化
ターボブースト
ハイパースレッディング
・コアの特定のリソースを複製することに
より同時に2つのスレッドをスケジュール
可能
Core1
・コアの一部分しか使用していない場合，動作周波数
を動的に変化させ，より高速に処理を行う
Core2
・ユーザの負荷要求に対して動的に反応
・性能とエネルギー効率を最大化
・制約条件
-動作しているコア数
‐推定消費電力や供給電流
‐プロセッサの温度
プロセッサ
リソース リソース
・同じプロセッサ要素を同時利用不可
・プロセッサリソースを効率よく使用
・コアの一部を共有
例：Intel ダイ面積 10%増加
性能
30%増加
本研究ではこれらの高速化技術を以下のようにモデル化する
・同時に利用しているコア数に応じて動的に周波数を変化するモデル
・ハイパースレッディングによる論理コアは物理コアとして扱う
例：物理2コア（論理コア数 ＝4）→物理4コア
・利用しているコア数に応じて動作周波数を変化(表1)
利用するコア数
動作周波数
1Core
2.8GHz
2Core
2.5GHz
3-4Core
1.3GHz
表1：利用するコア数に応じた動作周波数一覧
提案手法
入出力と目的関数
•入力：タスクグラフ，プロセッサグラフ
•出力：タスクノードをプロセッサに割り当てたスケジュール
•制約条件
アイディア
•高速化技術による動作周波数の変化を考慮したスケジューリング
•ハイパースレッディングとターボブーストは排他的に使用される
・同時に実行するスレッド数の考慮
•ネットワークコンテンション，ディレイを考慮（既存研究のモデルに従う）
•目的関数：
・実機上での動作を考慮
ハイパースレッディングとターボブーストによる動作周波数の変化を考慮した上で
のタスク処理時間の最小化
提案手法によるスケジューリング
既存手法によるスケジューリング
0
2
物理コアの利用効率を最大にする手法
8 10 12 14 16 18 20 22 24 26 28
4
6
Proc1
Core1
T1
30
32
0
2
論理コアの利用率を最大にする手法
8 10 12 14 16 18 20 22 24 26
4
6
Proc1
n6
n1
Core2
T1
Core1
T1
T2
n6
n3
Core2
T1
T2
n7
n2
n1
n7
n2
n4
Core3
T1
Core4
T1
Comm
Core3
T1
n5
n3
4
↓
2
6
8 10 12 14 16 18
20
n5
Comm
22 24 26 28 30
n5
n4
n8
n3
Proc2
約1.3倍
高速化
n8
3
↓
1
4
Proc1
Core1
T1
T2
Core2
T1
T2
Core3
T1
Core4
T1
n4
28
2
n8
Proc2
Proc2
0
3
↓
2
Core4
T1
HT時 1.3G
n1
n6
定格 ２G
7
n2
Comm
2
↓
3
1
↓
4
2コア使用
２．５G
1コア使用
２．８G
既存のスケジューリング手法を用いたスケジュール結果は左と中央の図である．これらは既存手法を用いた最も良い結果である．しかし，これらのスケジュール通りに実
機上で処理しても実際はその他の高速化技術が動作するため，異なった処理が行われる．そこで本研究では実機上での動きを考慮した上でスケジュール結果を出力する．
†1 奈良先端科学技術大学院大学情報科学研究科
科
†2 会津大学大学院コンピュータ理工学研究科
†3 滋賀大学経済学部情報管理学
ITO-LAB Division of foundation of Software since 1993