狠狠撸
Submit Search
骋笔鲍を考虑した惭补辫搁别诲耻肠别のタスクスケジューリング
?
0 likes
?
729 views
Koichi Shirahata
Presented at SWoPP 2010 (IPSJ SIG Technical Report 2010-HPC-126)
Read less
Read more
1 of 42
Download now
Download to read offline
More Related Content
骋笔鲍を考虑した惭补辫搁别诲耻肠别のタスクスケジューリング
1.
GPUを考慮したMapReduceのGPUを考慮したMapReduceの タスクスケジューリングタ ク ケジ
リ グ 白幡 晃一?1 佐藤 仁?1 松岡 聡?1?2?3 ?1?東京工業大学 ?2?科学技術振興機構科学技術振興機構 ? 3?国立情報学研究所
2.
情報爆発時代における 大規模データ処理 大規模デ タ処理? 大規模データ処理 –
気象、生物学、天文学、物理学など様々な科学技術計算 での利用での利用 ? MapReduce – 大規模データ処理のためのプログラミングモデル大規模デ タ処 グラ ング デ – スケーラブルな並列データ処理 ? GPGPU – 汎用CPU?に比べ高い性能 – CUDA?をはじめとする開発環境の整備 → CPU と GPU の混在したスパコン クラウドの出現→ CPU?と GPU?の混在したスパコン?クラウドの出現 ex)?TSUBAME?2.0 :?NVIDIA?の Fermi「Tesla?M2050」 を計算ノードに3台搭載 を活用した 処理の高速化GPU?を活用した MapReduce処理の高速化
3.
CPU と GPUの混在環境での 処理
おける問題点MapReduce処理における問題点 ? CPUとGPUへタスクを割り振る方法は自明ではない? CPUとGPUへタスクを割り振る方法は自明ではない – 計算資源への依存 数 数 容 バ ド幅? CPUコア数、GPU台数、メモリ容量、メモリバンド幅 ストレージへの I/O?バンド幅など アプリケ ションへの依存– アプリケーションへの依存 ? GPU処理の特性 長所 : ピーク性能 メモリバンド幅– 長所 :??ピーク性能、メモリバンド幅 – 短所 :? 複雑な命令は CPU?に劣る →??GPU利用による性能向上があるものの、CPU?GPU処理には 向き?不向きがある GPUとCPUのハイブリッド実行のスケジューリングを行い,リ 実行 リ グを行 , それぞれの長所を生かす → 計算資源を有効活用
4.
目的と成果目的と成果 目的? 目的 – CPUとGPUの混在環境でのMapReduce処理の高速化 ?
成果 Mapタスクのハイブリッド実行– Mapタスクのハイブリッド実行 ? MapReduce の OSS実装である Hadoop に実現 M タスク割り振りのスケジ リング手法の提案– Mapタスク割り振りのスケジューリング手法の提案 ? ジョブ全体の実行時間を最小化 プC K‐meansアプリケーションによる評価 ? ジョブ実行時間:?複数GPUと提案スケジューリング手法により、 CPUのみの場合に対し1.02‐1.93倍となる高速化
5.
発表の流れ発表の流れ 究背景? 研究背景 ? MapReduceとGPGPUMapReduceとGPGPU ?
提案手法 ? 設計と実装 ? 実験実験 ? 関連研究 ? まとめと今後の課題
6.
MapReduce と GPGPUMapReduce
と GPGPU ? MapReduce Map Shuffle Reduce の 3つのフェ ズからなる– Map,?Shuffle,?Reduce?の 3つのフェーズからなる – 様々な機械学習アルゴリズムへの適用例 主な実装– 主な実装 ? Hadoop:??MapReduce,?HDFS,?HBase などの OSS ? Mars: GPU用のフレームワークMars:? GPU用のフレ ムワ ク → 企業?研究機関での導入事例の多い Hadoop を対象 ? GPGPU? GPGPU – グラフィックプロセッサをSIMD演算機として利用 CPUに比べ安価で高いピ ク性能– CPUに比べ安価で高いピーク性能 – 主な統合開発環境 ? NVIDIA: CUDA AMD: ATI Stream? NVIDIA:?CUDA,??AMD:?ATI?Stream →??CUDAを対象
7.
発表の流れ発表の流れ 究背景? 研究背景 ? MapReduceとGPGPUMapReduceとGPGPU ?
提案手法 ? 設計と実装 ? 実験実験 ? 関連研究 ? まとめと今後の課題
8.
Hadoop の構造Hadoop の構造 ?
マスタ?ワーカモデル ? ジョブの動作 ? Client:?ジョブの投入,??JobTracker:?タスクの割り振り,?投 , 振 , TaskTracker:?タスクの実行,??Heartbeat?による送受信 Master?NodeClient?Node? Java?App JobTracker Slave?NodeSlave?NodeSlave?Node Task Task CPU CPU TaskTracker CPU CPU TaskTracker CPU CPU TaskTracker CPUCPU Task Task CPUCPU Task Task CPUCPU Task Task Task TaskTask
9.
提案 :?CPU?と GPUの
Mapタスクの ハイブリッドスケジューリング と 割り振りを自動決定? CPU?と GPU?への割り振りを自動決定 – 実行環境、計算資源 → ジョブ実行時間を最小化 – アプリケーションの特性 →??ジョブ実行時間を最小化 Master?NodeClient?Node? Java?App JobTracker Slave?NodeSlave?NodeSlave?Node Task Task ? Hadoop からの CUDA の呼び出し CPU CPU TaskTracker CPU CPU TaskTracker CPU CPU TaskTracker ? Hadoop からの CUDA?の呼び出し ? ハイブリッドスケジューリングアルゴリズム CPUCPU Task Task CPUCPU Task Task CPUCPU Task Task Task TaskTask
10.
Hadoop からの CUDA
の呼び出しHadoop からの CUDA?の呼び出し ? 実装の違いの吸収実装の違いの吸収 – Hadoop →?Java実装 (ミドルウェア,??アプリケーション) – CUDA → C++ によるライブラリ– CUDA?→?C++?によるライブラリ ? 主な手法 H d St i 標準入出力– Hadoop Streaming:??標準入出力 – Hadoop Pipes:??ソケット接続,??C++ライブラリ JNI JNIベ スの CUDAラ パ (JCUDA)– JNI,??JNIベースの CUDAラッパー (JCUDA) → Hadoop Pipes を対象→?Hadoop Pipes?を対象 ? C++?で MapReduceアプリケーション,?CUDAカーネル関数を 記述可能 ? CUDAカーネルを起動可能
11.
Hadoop からの CUDA?の呼び出し (cont’d) タ
実行 管? Mapタスク?実行スロットの管理 – Mapタスクを CPU,?GPU?のどちらのスロットでpタ クを , ちら ッ 実行するか? – 空きスロット (CPU GPU) の認識空きスロット (CPU,?GPU)?の認識 ? GPUへのMapタスクの競合 – 1ノード上に複数GPU?を搭載時に発生 – Mapタスクを実行する GPUデバイスを識別するp 必要有 ? cudaSetDevice で設定設定
12.
Mapタスクの ハイブリッドスケジューリング 設定? 設定 – CPU?nコア
と GPU m台を搭載 ? スケジューリング方法 – ジョブ実行時間を最小化ジョブ実行時間を最小化 ? CPU?と GPU?の性能比 (加速倍率)?に応じた Mapタスクの割り振り – 動的なモニタリング ? CPU,?GPU?で実行が終了した Mapタスクのプロファイル (実行時間など)?を Heartbeat?毎に繰り返し取得 ? 加速倍率を計算 ジ ブ 進捗状況 把握? ジョブの進捗状況の把握
13.
スケジュ リングアルゴリズムスケジューリングアルゴリズム ? 目標標 –
CPU,?GPU?に割り当てられた Mapタスクが共に全て終了する までにかかる時間の最小化 – CPU と GPU に割り当てる Mapタスク数を決定– CPU?と GPU?に割り当てる Mapタスク数を決定 ? 加速倍率: ? スケジューリングアルゴリズム
14.
発表の流れ発表の流れ 究背景? 研究背景 ? MapReduceとGPGPUMapReduceとGPGPU ?
提案手法 ? 設計と実装 ? 実験実験 ? 関連研究 ? まとめと今後の課題
15.
Hadoop Pipes??ユーザからの実行方法p p ?
ユーザは map関数と reduce関数を 記述 (C++ラッパーライブラリを使用) bin/hadoop pipes? ‐D??hadoop.pipes.java.recordreader=true? D hadoop pipes java recordwriter=true?記述 (C++ラッパ ライブラリを使用) ? コンパイル済のバイナリと入力?出 力ファイルを指定してジョブを実行 ‐D??hadoop.pipes.java.recordwriter=true? ‐bin??cpu‐kmeans2D? ‐input??input? ‐output output User Launch Submit?Job Client Node Master Node output??output User JobTracker ll d k CPU?App Binary JobClient Client?Node Master?Node TaskTracker Allocate?Map?or?Reduce?task C++?Wapper Wrapper Slave?Node Use?Hadoop Pipes Child?JVM Launch Wrapper? Process Send?and?Receive Key‐Value?pairsRun CPU?App Binary Child Task y p
16.
Hadoop Pipes 実行フローHadoop
Pipes 実行フロ ? TaskTracker が Childプロセスを起動 ? Child プロセスがタスクを起動? Child?プロセスがタスクを起動 ? C++?Wrapper?プロセスが C++バイナリを実行 ‐ ソケット接続による Key‐Value?ペアの送受信ソケット接続による y アの送受信 User Launch Submit?Job Client Node Master NodeUser JobTracker ll d k CPU?App Binary JobClient Client?Node Master?Node TaskTracker Allocate?Map?or?Reduce?task C++?Wapper Wrapper Slave?Node Use?Hadoop Pipes Child?JVM Launch Wrapper? Process Run Send?and?Receive Key‐Value?pairs CPU?App Binary Child Task y p
17.
ハイブリッド実行の場合 incl.?Pipes?による CUDA?の呼び出し ジ ブ実行時に
CPU GPUバイナリを指定? ジョブ実行時に CPU?GPUバイナリを指定 ? Mapタスクの識別 (CPU?GPU,??GPUデバイスID) ? 空きスロットの識別 (CPU?GPU,??空きGPUデバイスID)( , ) User Launch Submit?Job Client Node Master Node CPU?App Binary JobTracker ll d k GPU??App Binary JobClient Client?Node Master?NodeBinary TaskTracker Allocate?Map?or?Reduce?task GPU?Wapper Wrapper Slave?Node Use?Hadoop Pipes Child?JVM Launch Wrapper? Process Run Send?and?Receive Key‐Value?pairs GPU?App Binary Child Task y p
18.
Mapタスクの割り振りp 割り振り TaskTracker ? 空きスロット,?プロファイル
(実行時間) JobTracker ? プロファイルのモニタリング 空き ッ , ァイ (実行時間) の通知 ? タスクの割り当て要求 ? タスクを識別して実行 ァイ タリング ? スケジューリングアルゴリズムの計算 (Heartbeat毎) ? 各ノードへのタスクの割り振り Client?Node? タスクを識別して実行 (CPU?GPU,?GPUデバイスID?の識別) 各ノ ドへのタスクの割り振り (CPU?GPU,?GPUデバイスID?の指定) Master?Node GPU App CPU?App Binary JobTracker Slave NodeSlave NodeSlave Node GPU?App Binary TaskTask Slave?NodeSlave?NodeSlave?Node CPU CPU TaskTracker CPU CPU TaskTracker CPU CPU TaskTracker GPU CPU GPU CPU Task Task GPU CPU GPU CPU Task Task GPU CPU GPU CPU Task Task Task TaskTask
19.
発表の流れ発表の流れ 究背景? 研究背景 ? MapReduceとGPGPUMapReduceとGPGPU ?
提案手法 ? 設計と実装 ? 実験実験 ? 関連研究 ? まとめと今後の課題
20.
実験実験 ? Hadoop環境でジョブ実行時間、Mapタスク実行時間を測定 CPUのみ と
CPU GPU の場合を比較– CPUのみ と CPU?+?GPU?の場合を比較 – 提案スケジューリングの適用と非適用の場合を比較 ? 実験環境: TSUBAME実験環境 SU – CPU?16コア +?GPU?2台 / Node – Mapスロット数,??Reduceスロット数:?16?スロット /??Node 1 64ノ ドと変化– 1~64ノードと変化 – DFS?は Lustre を使用 (ストライプ数:?4,??チャンクサイズ:?32?MB) ? I/O?性能: 32?MBのファイルに対し、Write?180MB/s,??Read??610MB/s ? K‐meansアプリケーション – Mapタスクを C++バイナリ、CUDAバイナリで実行 入力 262 144 個の二次元座標デ タ(浮動小数点)と 128個のクラスタ– 入力 :?262,144?個の二次元座標データ(浮動小数点)と 128個のクラスタ を持つファイルを 1000個連結 (20GB) ? Map: 各ファイルごとに K‐means?を実行 ? Reduce:??K‐means?の結果を収集
21.
ジョブ実行時間の比較ジョブ実行時間の比較 ? Hadoop環境でジョブ実行時間 Mapタスク実行時間を測定?
Hadoop環境でジョブ実行時間、Mapタスク実行時間を測定 – CPUのみの場合とCPU+GPUの場合を比較 – CPU+GPUのとき、提案アルゴリズムの適用と非適用の場合を比較 ? 実験環境: TSUBAME? 実験環境: TSUBAME – CPU?16コア +?GPU?2台 /?node ? 16CPU、15CPU+1GPU、14CPU+2GPUを比較 – Mapスロット :?16,?Reduceスロット :?16 – 1~64ノードと変化 – DFSはLustreを使用(ストライプ数:?4、チャンクサイズ:?32MB) ? I/O性能: 32MBのファイルに対し、Write?180MB/s,??Read??610MB/s ? K meansアプリケ ション? K‐meansアプリケーション – MapタスクをC++バイナリ、CUDAバイナリで実行 – 262144個の二次元座標データ(浮動小数点)と128個の クラスタを持つファイルを1000個連結 (20GB) Org?:?Hadoopのオリジナル クラスタを持つファイルを1000個連結 (20GB) ? Map: 各ファイルごとにK‐meansを実行 ? Reduce:??K‐meansの結果を収集 スケジューリング Ours?:?提案スケジューリング
22.
ジョブ実行時間の比較ジョブ実行時間の比較 GPU?の使用による若干の性能向上有、使用 よる若干 性能向
有、 しかし加速倍率が高くないため (1.18倍)? CPU?と同等の性能 Org?:?Hadoopのオリジナル スケジューリング Ours?:?提案スケジューリング
23.
ジョブ実行時間の比較ジョブ実行時間の比較 提案アルゴリズムの使用 による更なる性能向上1.02倍 1.93倍 Org?:?Hadoopのオリジナル スケジューリング Ours?:?提案スケジューリング
24.
ジョブ実行時間の比較ジョブ実行時間の比較 ド 追 性能劣ノードの追加による性能劣化 →??Mapタスク実行時間の増加による Org?:?Hadoopのオリジナル スケジューリング Ours?:?提案スケジューリング
25.
Mapタスク実行時間の増加 ? ノード数に応じてMapタスク時間が増加 Mapタスク実行時間の増加 p – I/O性能の低下 –
ジョブ実行時間の増加の一因 – その他の原因として、スロット数の過剰が冗長
26.
ジョブ実行時間の比較 1GPU?と 2GPU 1800 2000 提案手法では、GPU台数を増やすほど、 1400 1600 より性能向上する傾向有 1000 1200 16CPU 15CPU+1GPU+Ours 600 800 14CPU+2GPU+Ours Ours?:?提案スケジューリング 200 400 0 1 2
3 4 5 6 7 4 8 16 32 6421
27.
プロセス起動によるオーバーヘッド 1台の計算機での実験 ? バイナリのみとMapタスクの実行時間を比較バイナリのみとMapタスクの実行時間を比較 – バイナリ実行時間
:?C++?または CUDA?の Map関数 – Mapタスク実行時間 :?Mapタスクの割り当てから終了までpタ ク実行時間 pタ ク 割り当 ら終了ま →?実装依存のオーバー ヘッドは無視できない12.1秒 (16%) [sec] 12 4秒 (44%) CPU‐Binary,?GPU‐Binary?:? バイナリ実行時間 CPU‐MapTask,?GPU‐MapTask : タスク実行時間 12.4秒 (44%) Mapタスク実行時間
28.
発表の流れ発表の流れ 究背景? 研究背景 ? MapReduceとGPGPUMapReduceとGPGPU ?
提案手法 ? 設計と実装 ? 実験実験 ? 関連研究 ? まとめと今後の課題
29.
関連研究関連研究 ? 学習メカニズムによるCPU?GPUタスクスケジューリング [Chi‐Keung?Lu?et?al.?`09] ? チャンクサイズの変化によるCPU?GPUハイブリッド実行 の高速化の高速化 [T.?Ravi?Vifnesh
et?al.?`10] ? 不均質な環境でのMapReduceのタスクスケジューリング不均質な環境でのMapReduceのタスクスケジュ リング [Matei et?al.?`08] ? 既存の不均質環境下のタスクスケジューリング手法 [ d ` ][?Suda `06?] →??計算資源?アプリの特性に応じた CPU?GPU同時実行による 大規模データ処理に特化 ‐ 資源競合 (メモリ、ストレージ)?を考慮 オンラインで自動スケジ リング‐ オンラインで自動スケジューリング
30.
まとめと今後の課題今後 課題 ? まとめ タ
クを から呼び出– Mapタスクを GPU?から呼び出し ? MapReduce実装の Hadoop環境で実現 CPU と GPU の混在環境を考慮したタスクスケジ リング– CPU?と GPU?の混在環境を考慮したタスクスケジューリング 手法の提案 K meansアプリケーションでの実験– K‐meansアプリケーションでの実験 ? ジョブ実行時間:? 2GPUと提案手法により 1.02‐1.93倍の高速化 ? Hadoopの実装に依存するオーバーヘッドは無視できないHadoopの実装に依存するオ バ ッドは無視できない ? 今後の課題 – スケジューリングモデルの改良– スケジュ リングモデルの改良 ? メモリ?ディスクアクセス等を考慮 ? GPU上でのタスク実行時における CPUとの資源の競合によるタ ク実行時 おける 資源 競合 よる オーバーヘッドを考慮
31.
ご清聴ありがとうございました清聴ありがとう ざ ました
33.
実験結果実験結果 ?Mapタスク実行時間 倍 高速‐ GPUではCPUに対し1.0‐1.25倍となる高速化 (プロセス起動時間等を含む) ?ジョブ実行時間?ジョブ実行時間 ‐2GPUの使用と提案スケジューリングアルゴリ ズムの適用により1.02‐1.93倍の高速化 ‐14CPU+2GPUでは15CPU+1GPUに対し 1.02‐1.29倍の高速化
(複数GPUによる効果) Ours?:?提案スケジューリング Org?:?Hadoopのオリジナルスケジューリング ‐ 提案アルゴリズムの使用により 14CPU+2GPUの場合に平均1.28倍、 15CPU+1GPUの場合に平均1.08倍の高速化 ? GPUの使用 提案タスクスケジューリングの適用に g pのオリジナル ケジ リング ? GPUの使用、提案タスクスケジュ リングの適用に よる性能向上を確認
35.
Mapタスク実行時間の増加 ? ノードを増やすにつれてMapタスク時間が増加 Mapタスク実行時間の増加 ノ ドを増やすにつれてMapタスク時間が増加 –
滨/翱の増加が原因か
36.
プロセス起動等のオーバーヘッドプロセス起動等のオーバーヘッド ? ローカル1ノードでの実験 (7CPU+1GPU) –
バイナリ実行時間とMapタスク実行時間を比較 ? バイナリ実行時間 :? C++またはCUDAのMap関数の実行時間 ? Mapタスク実行時間 :??Mapタスクが割り当てされてからp p 終了するまでの時間 – オーバーヘッド ? CPU上では約16% ? GPU上では約44% バイナリ実行時間とMapTask実行時間の比較 →?実装依存のオーバーヘッドは無視できない CPU GPU [sec] バイナリ 実行時間 64.93~65.68?秒 11.66~16.86 秒 Mapタスク 72.13~78.14?秒 24.04~37.06?秒pタ ク 実行時間 秒 秒
37.
GPUを呼び出す手法の比較を す 法
較 ? Hadoop Streaming Hadoopとユーザプログラムの間にUnix標準ストリームを使用– Hadoopとユーザプログラムの間にUnix標準ストリームを使用 – 標準入出力の解析が必要 × ? Hadoop Pipesp p – ソケット接続を確立し、スレーブノードとの通信のチャネルを 生成するC++インターフェース – C++とCUDAの親和性 ○C++とCUDAの親和性 ○ ? JNI(Java?Native?Interface) – 関数呼び出しのオーバーヘッド大、実行環境依存のライブラリ が必要 ×が必要 × ? jCUDA(Java?for?CUDA) – 現状では明示的なメモリアラインメント不可 非同期の命令が現状では明示的なメモリアラインメント不可、非同期の命令が メモリ破損を引き起こす可能性有 × → C++との親和性を考慮しHadoop Pipesを使用→?C++との親和性を考慮しHadoop Pipesを使用
38.
GPUを呼び出す手法の比較を す 法
較 ? Hadoop Streaming – HadoopとユーザプログラムのインターフェースにUnix標準ストリームを使用p ザ グラ インタ 標準 リ を使用 – 任意の言語でユーザプログラムを記述可能 – 標準入出力の解析が必要 ? Hadoop Pipesp p – C++?インターフェース – ソケット接続を確立し、スレーブノードとの通信のチャネルを生成 ? JNI(Java?Native?Interface) – JVMで実行されるJavaコードが他のプログラミング言語で記述されたネイティ ブコードを利用するためのAPI – JVMで動作させるには不利なプログラムをネイティブコードに置き換えて高速 化することが可能化することが可能 – 関数呼び出しのオーバーヘッド大、実行環境依存のライブラリが必要 ? jCUDA(Java?for?CUDA) GPU上のメモリの割り当て 転送のためのメソッドを提供– GPU上のメモリの割り当て?転送のためのメソッドを提供 – Jcublas,?Jcufft,?Jcudppなどのライブラリと相互運用が可能 – 現状では明示的なメモリアラインメント不可、非同期の命令がメモリ破損を引 き起こす可能性有き起こす可能性有 → 今回はHadoop Pipesを使用
39.
Streaming Pipes TaskTracker TaskTracker Child TaskTracker Child Child Task Task Child?JVM Child?JVM C++ Wapper
Library Streaming Process C++?Map?or? Reduce C ?Wapper Library
40.
K‐meansにおける Mapタスクの加速倍率
41.
笔颁础でのジョブ时间笔颁础でのジョブ时间
42.
Launch Submit?Job User JobTrackerGPU?App Binary JobClient Client?Node Master?Node TaskTracker Allocate?Map?or?Reduce?task C++?Wapper Slave?Node Use?Hadoop
Pipes TaskTracker Child JVM Launch Run Wrapper? Process Send?and?Receive Key‐value pairs GPU?App Binary Child Task Child?JVMKey‐value?pairs
Download