Upgrade to Pro — share decks privately, control downloads, hide ads and more …

System Reading: "Disengaged Scheduling for Fair...

Yusuke SUZUKI
September 19, 2014

System Reading: "Disengaged Scheduling for Fair, Protected Access to Fast Computational Accelerators"

System Reading meetup 2 http://system-reading.connpass.com/event/8493/
Reading ASPLOS '14, "Disengaged Scheduling for Fair, Protected Access to Fast Computational Accelerators".
http://www.cs.rochester.edu/~kmenycht/

Yusuke SUZUKI

September 19, 2014
Tweet

More Decks by Yusuke SUZUKI

Other Decks in Research

Transcript

  1. Reference • Konstantinos Menychtas, Kai Shen and Michael L. Scott

    – University of Rochester • Proceedings of the 19th International conference on Architectural support for programming languages and operating systems (ASPLOS ’14)
  2. 問題点 • アクセラレータの制御は性能向上のために direct-mapped interface to user space によってなされる –

    kernel/user mode 切り替えによる latency を避けるため – OS によるリソース管理のレイヤをバイパスしている • GPU のインターフェースは black-box である
  3. Direct-mapped interface • user space に公開された interface (mmap) を経由して GPU

    へアクセス App GPU GPU Driver Runtime Kernel Space User Space
  4. Direct-mapped interface • user space に公開された interface (mmap) を経由して GPU

    へアクセス App GPU GPU Driver Runtime Kernel Space User Space 1. Syscall
  5. Direct-mapped interface • user space に公開された interface (mmap) を経由して GPU

    へアクセス App GPU GPU Driver Runtime Kernel Space User Space 1. Syscall Direct-mapped Interface 2. Expose Direct-mapped interface
  6. Direct-mapped interface • user space に公開された interface (mmap) を経由して GPU

    へアクセス App GPU GPU Driver Runtime Kernel Space User Space 1. Syscall Direct-mapped Interface 2. Expose Direct-mapped interface 3. Access to GPU
  7. 事前実験: system call のコストの考察 • 半分以上の request が 10μs 以内に終了している

    • 小さな request が大量に発行されるため trap は non-trivial なコストとなる – efficiency のために,direct-mapped interface を利用する必要がある
  8. 関連研究 • PTask [C.J.Rossbach et al. SOSP ‘11], Pegasus [V.Gupta

    et al. ATC ’11] – system / hypervisor call による request の管理 (efficiency の欠如) – direct-mapped interface を勝手に使われると制御ができなくなる (protection の欠如) • TimeGraph [S.Kato et al. ATC ‘11], Gdev [S.Kato et al. ATC ‘12], LoGV [M. Gottschlag et al. FHC ‘13] – black-box software stack を open-source のものに置き換えている – OpenCL など user level GPU library との integration が必要になる • TimeGraph,Gdev,GERM [A.Demers et al. SIGCOMM ‘89] – スケジューリングを行っている – request 単位での制御のため,オーバーヘッドが大きい (efficiency の欠如)
  9. 提案: Disengaged Fair Queueing • スケジューリング方式 Disengaged Fair Queueing を提案する

    – efficiency / protection を犠牲にすることなく fairness を実現する • direct-mapped interface を解放し,効率を犠牲にすることなく, かつサンプリングを行い利用率を管理することで 確率的な fair share を実現する – trap によるオーバーヘッドなしに fair share を実現する • work-conserving なスケジューリングを実現する – task が block されているのに, GPU を利用していないという状況を 作らない • NVIDIA の driver を含め unmodified な stack に対して 提案手法を実現する
  10. Timeslice • interface へのアクセスを token holder にのみ許可 – Interface は

    no page に設定され,アクセスすると fault handler が動作 – token holder のアクセスのみ許可し,ほかの task は suspend する • work conserving ではない • fault handler のオーバーヘッドが大きい App GPU Runtime Kernel Space User Space Direct-mapped Interface App Runtime Direct-mapped Interface
  11. Timeslice • interface へのアクセスを token holder にのみ許可 – Interface は

    no page に設定され,アクセスすると fault handler が動作 – token holder のアクセスのみ許可し,ほかの task は suspend する • work conserving ではない • fault handler のオーバーヘッドが大きい App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface
  12. Timeslice • interface へのアクセスを token holder にのみ許可 – Interface は

    no page に設定され,アクセスすると fault handler が動作 – token holder のアクセスのみ許可し,ほかの task は suspend する • work conserving ではない • fault handler のオーバーヘッドが大きい App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface 2. Access
  13. Timeslice • interface へのアクセスを token holder にのみ許可 – Interface は

    no page に設定され,アクセスすると fault handler が動作 – token holder のアクセスのみ許可し,ほかの task は suspend する • work conserving ではない • fault handler のオーバーヘッドが大きい App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface 2. Access 3. Invoke fault handler
  14. Timeslice • interface へのアクセスを token holder にのみ許可 – Interface は

    no page に設定され,アクセスすると fault handler が動作 – token holder のアクセスのみ許可し,ほかの task は suspend する • work conserving ではない • fault handler のオーバーヘッドが大きい App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface 2. Access 3. Invoke fault handler 4. Access
  15. Timeslice • interface へのアクセスを token holder にのみ許可 – Interface は

    no page に設定され,アクセスすると fault handler が動作 – token holder のアクセスのみ許可し,ほかの task は suspend する • work conserving ではない • fault handler のオーバーヘッドが大きい App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface 2. Access 3. Invoke fault handler 4. Access 5. Blocked
  16. Disengaged Timeslice • Direct-mapped interface を disengage する – Interface

    へのアクセスに対して毎回 fault handler を呼ばず, token を保持している間は直接アクセスできる • request を trap していないためオーバーヘッドは低い • work-conserving ではない App GPU Runtime Kernel Space User Space Direct-mapped Interface App Runtime Direct-mapped Interface
  17. Disengaged Timeslice • Direct-mapped interface を disengage する – Interface

    へのアクセスに対して毎回 fault handler を呼ばず, token を保持している間は直接アクセスできる • request を trap していないためオーバーヘッドは低い • work-conserving ではない App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface
  18. Disengaged Timeslice • Direct-mapped interface を disengage する – Interface

    へのアクセスに対して毎回 fault handler を呼ばず, token を保持している間は直接アクセスできる • request を trap していないためオーバーヘッドは低い • work-conserving ではない App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface Disengaged
  19. Disengaged Timeslice • Direct-mapped interface を disengage する – Interface

    へのアクセスに対して毎回 fault handler を呼ばず, token を保持している間は直接アクセスできる • request を trap していないためオーバーヘッドは低い • work-conserving ではない App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface 2. Access Disengaged
  20. Disengaged Timeslice • Direct-mapped interface を disengage する – Interface

    へのアクセスに対して毎回 fault handler を呼ばず, token を保持している間は直接アクセスできる • request を trap していないためオーバーヘッドは低い • work-conserving ではない App GPU Runtime Kernel Space User Space Direct-mapped Interface 1. Get token App Runtime Direct-mapped Interface 2. Access 3. Blocked Disengaged
  21. Disengaged Fair Queueing (1) • work-conserving にするために,TCP のパケットの スケジューリング方式である Fair

    Queueing を元にした, Disengaged Fair Queueing を提案する • Task ごとの以前の区間での GPU の resource usage, これまでの usage がわかるとしたとき – Active task のそれぞれの usage に前の区間での usage を足す • このとき,system virtual time を,active task 中もっとも低い usage にそろえる – Inactive task の usage が system virtual time よりも低ければ, system virtual time にそろえる – Task のうち,system virtual time + 区間の長さ より高い usage のもの に対して,次の区間での実行を block する – Disengaged free run: active task に向かって interface を 一定時間開放する • 以前の区間での usage はわかるのか?
  22. Disengaged Fair Queueing (2) • In general, 各 task に所属する

    queue に積まれた GPU の command は round robin で GPU 内で実行される • よって,ある一定時間すべての task に実行を許可した場合, その usage はそれぞれの request の長さに比例する • Disengaged Fair Queueing は,sampling 区間で request の 平均長を得ることで,disengaged free run 区間での usage を 求める
  23. 実装 • prototype, NEON を Linux 3.4.7 kernel 上に実装 •

    GPU のデバイスドライバは NVIDIA のものを用い,mmap, ioctl,initialization に hook するための wrapper を用いる • NEON は3つの components に大別される – initialization phase: GPU の task (GPU channel) ごとの device registers と buffer の map されているアドレスを特定する • この構造は先行研究によるリバースエンジニアリングで明らかになっている [K.Menychtas et al. ATC ’13 short paper] – page-fault-handling: device register への書き込みを trap し request submission を検出 – polling-thread service: 特定の値を polling する thread を用いて, request の終了を検知する
  24. 評価 • NVIDIA GPUs GTX 670 (Kepler),GTX 275 (Tesla),NVS295 (Tesla),GTX

    460 (Fermi) に対して deploy した – 評価においては GTX 670 (Kepler) の結果のみ利用する • 環境 – 2.27GHz Intel Xeon E5520 CPU – triple-channel 1.066GHz DDR3 RAM • ベンチマーク – compute request を中心に – small request なものを選んだ • on-chip GPUs platform という small,interactive な requests 発行される 環境を想定している Benchmarks
  25. 評価 – standalone execution (1) • standalone application のオーバーヘッドを direct

    device access の場合と比較する • Timeslice – large request の場合コストは低い – small request の場合コストが高い (BitonicSort 38% slow etc.) – 全ての request をインターセプト するため • Disengaged Timeslice – status update,切り替えの時の trap コストは低い (~2%) • Disengaged Fair Queueing – draining の時の idleness が中心 コストは低い (~5%)
  26. 評価 – standalone execution (2) • throttle benchmark (決められた大きさの request

    を繰り返す) を request の大きさを変えて比較 • Timeslice が小さい request でコストが高いことが確認できる
  27. 評価 – concurrent extensions (1) • benchmark と throttle を同時に動作させ,それぞれの

    slowdown を調べる – Direct で単体で実行したときの実行時間で正規化されている • 提案手法により,fair share が達成されている • Timeslice で小さい request のとき throttle が x2 にならないの は,request size が小さいと回数が多くなり,fault による trap のコストが大きくなるため
  28. 評価 – concurrent extensions (2) • glxgears (OpenGL) で Disengaged

    Fair Queueing 19μs のとき, 大きな差が付いている – OpenCL のみと異なり,graphic request と混在すると, 「GPU による request のスケジューリングは round-robin である」 という仮定が崩れているため – internal な scheduling について vendor の documentation が 公開される OR resource usage が公開されれば解決可能
  29. 評価 – Concurrency Efficiency • concurrent な の applications があった時,単体で動かした実行時間を1

    , 2 … 同時に動作させた際の十応時間を1 , 2 … としたとき, =1 ( ) を concurrency efficiency として定義 – 1 を超える = mutual synergy (DMA / computation の overlap) / 1 を下回る = resource lost • Direct device access が 1 を下回る – context switch cost • Timeslice は高いコストがかかる (avg. 19%, high 42% to direct) • Disengaged Timeslice も多少オーバーヘッドがかかる (10%/35%) • Disengaged Fair Queueing は background concurrency を許容し オーバーヘッドが低い (4%/18%)
  30. 評価 – Nonsaturating Workloads (1) • nonsaturating workloads のときの性能を比較する –

    throttle に sleep を入れ,nonsaturating な状態を模倣する • fairness が保たれているのが確認できる – Disengaged Fair Queueing において 2x より悪化していない
  31. 評価 – Nonsaturating Workloads (2) • Timeslice,Disengaged Timeslice は concurrency

    efficiency が低くなる – 80% の sleep ratio のとき,efficiency は direct と比較して 36%,34% 下がる • Disengaged Fair Queueing は direct と比較して 0% の 性能低下である
  32. System Consideration (1) • OS level accelerator management に必要な情報は少ない –

    event-based scheduling interface – utilization information – request の十分な semantics の情報 (scheduling において deadlock を防ぐため) • 性能のため memory-mapped interface が主流になると考え られる – このとき,request queue についての layout,interfaction, また performance counter (利用率のため)が必要である • “partial opening” な仕様が望まれる • accelerator は data transfer と computing と言った処理を overlap することができるため,それぞれについての完了を 別々に通知してもらえる必要がある (e.g. tag)
  33. System Consideration (2) • GPU へのアクセスは DMA に限られている – CPU

    以外の device が GPU をうまく利用するためには,デバイス間 通信の仕様の公開が必要 • preemption support – GPU は non-preemptive に実行を行う – GPU の interactivity の向上のためには preemption が必要 – 現在は閾値以上に長く実行する task は kill する以外にないが, preemption があれば,任意長の request の実行を許すことができる • resource protection – channel の数は限られているため,大量の channel を確保すると denial-of-service 攻撃を仕掛けることができる – OS level management があれば,channel,memory といった resource の確保を保護することができる (一定値以上は禁止など)
  34. まとめ • fairness,protection,efficiency を満たす OS level management を達成した • Disengagement

    と request の trap を用いた性能を犠牲に しない scheduling を達成した – Disengaged Fair Queueing は idleness を抑制し, 平均 4% の オーバーヘッド増加に抑えた • graphic/computation の混ざった benchmark での unfairness は vendor からの情報があれば解決可能である • Disengaged resource management において必要な ハードウェアの機能を特定した – currently running GPU request – per-context resource usage – cleanly terminate an aberrant context – preemption