Gemini GPU 分割資源調度器（Token-based Scheduler）

回覆提問

上回跟大家介紹了 Gemini GPU分割解決方案。有些讀者來詢問，Gemini GPU Partitioning 和別家的解決方案，有何不同之處？

Gemini GPU Partitioning 分割共享簡介

其實有關在 Kubernetes 上實現 GPU Sharing 這個議題，產學界己經有很多不同的解決方案。例如 Reference #6 Volta MPS 就是一個NVIDIA提供的GPU分割方案，Reference #7 是阿里雲的GPU 分享功能。此外，像 Georgia Tech（Reference #8） 跟 N. Carolina（Reference #9） 也有他們的研究計劃。這些解決方案有些利用硬體，也有些是利用Kubernetes Scheduler來做時間分割(time slicing)的。

Gemini 除了是一個沒有任何 GPU hardware dependency 的軟體解決方案外，比較特別的地方就是我們的 scheduler 有跟前台結合，去減低overhead，並及最佳化 GPU 的使用率。

Gemini在Kubernetes上定義了一個POD Kind，叫 SharePod。SharePOD的前台跑在每個Kubernetes worker node 上，去收集所有虛擬GPU使用狀況，那Gemini後台的SharePod Scheduler又是怎樣利用這些資訊，去公平地派送使用虛擬GPU的POD呢？

接著，我們來解釋一下，我們SharePod Scheduler的設計理念。

SharePod Scheduler Requirement

一個理想的虛擬GPU分享調度器，應該要滿足下列四點需求：

1. 具有彈性使用 GPU 資源的功能。Gemini GPU Partitioning 用 Request 和 Limit 的概念來控制單個容器在使用 GPU 計算資源時的QoS (Quality of Service)。Request 確保容器能夠獲得最低限度需要的GPU，Limit 確保容器不能使用超過特定值的GPU 資源。
2. 因為虛擬GPU可以彈性要求GPU資源，調度器就必需公平分配實體GPU給不同的用戶。
3. 充份利用未被使用的GPU資源
4. 減低收集GPU使用量所需要用到的CPU 資源（overhead），因為這部份的code是和使用者的POD同時跑在K8S worker 上的，這也代表了管理GPU的額外開銷 Overhead。

Fair Share Scheduler （公平調度器 ）簡介

Gemini GPU Partitioning 實踐了以下功能來滿足上面四點需求 （參考圖一)：

圖一. Gemini Fair Share Scheduler

1. Event Driven Monitoring

Gemini GPU Partitioning 在前台設計了一個GPU Kernel 同步事件的監控器， 來收集虛擬GPU資源使用數據，傳到後台，提供給scheduler 計算下一個應該被派送的sharePod。這個「監控器」其實是 CPU API library 的一個插件（hook），當GPU application 使用如cudaEventSychronize 指令時，就會被 trigger.

2. Token-based time-slicing scheduler

Gemini SharePod scheduler 是用令牌（token）的方式，去彈性管理（Dynamic and Elastic scheduling) 所有SharePod 上虛擬GPU可公平分配使用實體GPU。這個 token 是根據上述Event Monitor送回來的數據，去彈性計算出來的。

Token 裡主要埋有兩項指令：其一是最適合派送到空出來實體GPU的sharePod。其二是預算這個sharePod要執行kernel burst的理想時間額度（Quota）。只要SharePod 被重覆派送，每次配備一個動態調整過的令牌，就會滿足Gemini GPU partitioning 的 QoS，使用資源會落在 Request 和 Limit的範圍內。

3. Dynamic Quota

一個 sharePod scheduler 令牌內的配額（quota）是表示該sharePod 要執行的 GPU kernel burst 可以使用 GPU timeslice 的上限。這個quota 是根據歷史紀錄動態計算出來的。對一個sharePod來說，它所有 kernel burst 的quota總和一定不能小過它的Request，但在 實體GPU 還有空餘資源情況下，Scheduler就可以增加quota timeslice 的長度（以不超過Limit為限），去充份利用實體GPU的資源。

4. Token Revokation

因為 scheduler 令牌quota的預算時間值，是用統計學算出來的，事實上每次kernel burst實際執行時間仍可能有差異，所以Gemini的前台也設計了一個撒銷token 的機置。簡單來說，就是當一個kernel burst 察覺到quota 剩下來的時間已經不足夠下一個GPU kernel 估計所需時間值時，Gemini 前台可以主動把token註銷，這樣kernel burst就會提早停止執行，避免一個sharePod overuse 它的時限。

下面再進一步介紹一下這四個概念的技術細節。

Event driven Monitoring

• 這個功能我們上星期有介紹過。它的主要目的就是收集虛擬GPU 資源使用的歷史紀錄. 對硬體加速器（如GPU）來說，收集這些數據的挑戰性是加速器是跟CPU非同步進行的，假如在CPU開一個thread 一直去 Monitor加速器的狀態，那overhead 會非常大。另一個挑戰是 GPU的kernel 不可以被interrupt，所以就算監控到GPU kernel執行狀態，也沒有辦法用scheduler 去下一個固定的時間上限，來分配給各個虛擬GPU.
• 依我們的了解，application使用加速器的情境，通常都是把data送到加速器運算。等加速器運算結束，才把運算結果從加速器的memory，copy回CPU的memory內。所以 application都需要在某點要跟GPU同步（CUDA sync），確定GPU運算結束，才可以copy data。
• Gemini GPU Partitioning 設計了一套API hook library，埋在 CUDA sync event 的API call 內，這時候我就可以順便計算出一個kernel burst裡面所有GPU kernel 的使用時間，並把資訊送回backend 的 Device Manager。
• 在這邊順便一提的是Application issue sync event 其實也是實體GPU空出來可以讓我們啟動下一個GPU kernel burst 的窗口。所以這個窗口，也是sharePod scheduler 動態決定每次啟動一個GPU kernel burst time slice 的最好時機。
• 綜合來說，Gemini GPU Paritioning event monitoring是用搭便車方式（piggyback）在使用者 call cudaEventSynchronize 的API call 裡，去收集虛擬GPU資源使用紀錄。這樣使用者不用改他們的CUDA code，Gemini 也可以大量降低 SharePod scheduler 的 overhead.

Token-based dynamic and elastic scheduling

• Gemini sharePod scheduler 有兩個主要的目的。一個就是根據使用者對虛擬GPU 下的QOS 要求 （Request, Limit) , 動態調整虛擬GPU kernel被配置的時間，以確保每個虛擬GPU可以公平分配到它Request 的GPU資源。第二個目的，就是確保實體GPU 的資源被充份利用到。就是說在所有同一個GPU上的所有虛擬GPU，都已達到Request 的數量後，它們還是可以繼續被配置到GPU 時間，直至使用量達到 Limit為止。
• Gemini sharePod scheduler 使用的方法，是一個令牌式（token）的指令那一個sharePod，可以使用下一個空出來的實體GPU, 並配置一個時間上限來管理各個虛擬GPU使用實體GPU的時間, 這樣在SharePod 被 scheduler重覆派送，漸進方式使用的狀況下，Gemini sharePod scheduler 就會滿足使用者 的 QOS (Quality of Service)要求，使用資源會落在 REQUEST 跟 LIMIT的數值內。
• Scheduler 選取下一個sharePod 的方法，跟K8S scheduler 的方式相近，也是用過濾（filtering）跟優先順序的方法，去選取最個適的sharePod。

1. 首先，scheduler會根據各虛擬GPU的使用紀錄，算出下一個sharePod可佔用GPU的時間值。
2. 第二步，scheduler會把已經達標的虛擬GPU過濾掉。
3. 在剩下虛擬GPU內，scheduler會比較它們目前的使用量，跟QOS 的Request 時間的差距。Scheduler 會派送距離最遠的sharePod。原因很明顯，就是要讓這些虛擬GPU，漸進式追上它們 QOS 的Request數量。

Dynamic Token Quota

• 下一步要解釋的，就是 scheduler 如何去達到GPU使用率最佳化的目標。
• 每次前台的 API hook 要啟動一個 GPU kernel前，除了把剛結束的kernel burst 便用數據送到後台外，還必需要跟後台的Scheduler 獲取一個有效令牌（token）。這個token不單止指定那一個sharePod可以使用剛空出來的實體GPU, 它也要訂定下一個Kernal burst （由多個GPU kernel 組成）可以佔住實體GPU的timeslice 時間值。Token 的 timeslice是後台 scheduler 根據該虛擬GPU的使用紀錄用統計學推算出來的。所以sharePod scheduler才能同時滿足每個虛擬GPU 的 Request （保証值）跟Limit （上限值）。
• Token 時間值很重要，因為假如時間訂得太長，就可能有實體GPU 被空置，那GPU 的平均使用率就會下降。相反來說，假若時間值訂得太短，那前台就要跟頻密地跟後台scheduler申通獲取新的令牌，這樣就會令scheduler的overhead 增高。
• 順便提一下，另一個令牌達成的目標，就是多專案（multi-tenant）完全分隔，因為Gemini GPU partitioning 限定只能讓持有有效令牌的thread，才可以經CUDA driver去啟動新的kernel，就是說在任何時間點，都不可能有兩個不同的專案在同一張實體GPU card 上。

Token Revokation

• 因為令牌內的GPU quota，是sharePod scheduler 根據統計學算出來的預測，所以GPU kernel burst 的實際執行時間，可能會有所差異。前面已經交代過若token 的time slice設得太長，就會導致GPU 空轉，使用率降低。但假如一個token訂定的time slice已用完，但kernel burst 所有的GPU kernel 仍未執行完畢，則有可能導致虛擬GPU 過度使用（overuse）資源的狀況。Gemini GPU Partitioning 還是要處理這個狀況。
• 圖二解釋了Gemini GPU Partioning 設計的 令牌撒消機制 （token revokation）。當 Gemini kernel burst啟動時，前台的client 會同時在GPU上（不是CPU）起動一個thread去監控GPUkernel 的結束。當GPU kernel 結束時，這個thread就會去算token timeslice 剩下的時間，是否足夠讓下一個GPU kernel 的預算運算時間。假若不足，Gemini 前台可以invalidate 目前的 token，強迫kernel burst提早結束，並把實體GPU讓出來給下一個sharePod 使用。

圖二. Token Revokation

Gemini GPU Partitioning 功能總結

這幾週分別介紹了下列幾個題目：

1. K8S scheduler 的功能與可客製化特質。
2. 為何在一些AI 開發過程（尤其是 model definition 與 inference）上，多專案能共享實體GPU，可以增強效率，同時減低成本。
3. 利用以上兩點概念，簡介為何我們開發了Gemini GPU Partitioning 分割解決方案
4. 特別介紹了 Gemini SharePod scheduler 利用令牌設計，為多專案提供了彈性，且可定義QoS的GPU資源分享功能。

因為產業界其實已經有不少 GPU 虛擬化的解決方案，最後我再比較其他方，列舉幾項 Gemini GPU 分割的優勢：

1. Gemini GPU Partitioning 是一個純軟體解決方案，利用 K8S controller 的特性，只在 K8S worker node 上前台功能，達成虛擬 GPU分享資源目標。這方案沒有任何硬體的dependency，只要是CUDA支援的GPU，Gemini都可以使用。
2. Gemini GPU Partitioning 利用令牌 scheduler的概念，達成多專案資源完全隔離獨立。在任何時間點都不會讓兩個專案同時使用硬體GPU資源。
3. 利用前台收集 GPU 使用數據，Gemini GPU Partitioning 能根據使用者定義的QoS分配資源。而且Gemini GPU Partitioning可彈性增加專案使用額度，增加整體 GPU 使用率。
4. 最重要的一點，是Gemini GPU Partitioning完全不影響到GPU應用程式。使用者無需改寫任何軟體，就可以多專案分享GPU資源，且保持了各專案間完全隔離的安全性。

Gemini AI Console 團隊正在招募資料科學家、IT/MIS人員來試用 Gemini GPU Partitioning，意者請於此報名：https://www.surveycake.com/s/Do7bX

References

1. https://github.com/kubernetes/kubernetes/blob/release-1.3/plugin/pkg/scheduler/algorithm/predicates/predicates.go
2. https://github.com/kubernetes/kubernetes/tree/release-1.3/plugin/pkg/scheduler/algorithm/priorities/
3. https://github.com/fabric8io/jenkinshift/blob/master/vendor/k8s.io/kubernetes/docs/devel/scheduler_algorithm.md
4. https://kubernetes.io/docs/tasks/extend-kubernetes/custom-resources/custom-resource-definitions/
5. https://alibaba-cloud.medium.com/getting-started-with-kubernetes-scheduling-process-and-scheduler-algorithms-847e660533f1
6. https://docs.nvidia.com/deploy/pdf/CUDA_Multi_Process_Service_Overview.pdf
7. https://www.alibabacloud.com/blog/gpu-sharing-scheduler-extender-now-supports-fine-grained-kubernetes-clusters_594926
8. https://ieeexplore.ieee.org/document/7530081 （GPUshare from Georgia Tech）
9. https://people.engr.ncsu.edu/xshen5/Publications/ppopp17.pdf （N. Carolina U）