面向流計算的GPU存儲資源動態(tài)分配技術

朱琳

摘要摘要：針對流處理計算模式中的任務分配不平衡問題，提出一種資源動態(tài)分配的硬件調度機制。該機制通過實時監(jiān)測各個任務的計算量，動態(tài)地調節(jié)分配各個任務的計算資源，提髙不規(guī)則任務的計算資源利用率，并且利用任務間數(shù)據流動的特性優(yōu)化了緩存設計。與現(xiàn)有GPU的成熟調度算法相比，該調度算法能使系統(tǒng)性能獲得明顯提升。

關鍵詞關鍵詞：圖形處理器；不規(guī)則任務；訪存；調度

DOIDOI：10.11907/rjdk.1431081

中圖分類號：TP302

文獻標識碼：A文章編號

文章編號：16727800（2015）004005702

0引言

流計算作為一種典型的基于任務流水線（Task Pipeline）的計算模式，由數(shù)據流（Data）和任務（Task）兩部分組成。在流計算執(zhí)行過程中，數(shù)據流需要按照流水線的方式依次順序接受各個任務的處理[1]。同時，各個任務之間存在著產生數(shù)據和消費數(shù)據（Producerconsumer）的關系，即前一個任務運算的輸出數(shù)據是下一個任務的輸入數(shù)據[2]。這種計算模式廣泛存在于多媒體處理、信號處理、數(shù)據挖掘、金融計算等領域[3]。

GPU順序執(zhí)行流計算程序會造成兩種問題：一是片上計算資源利用率不同，二是對片外內存的頻繁訪問[4]。為了降低不同任務計算量不均勻對于GPU計算資源和存儲資源的影響，本文提出了支持雙任務并發(fā)執(zhí)行的動態(tài)調度方法，能夠支持GPU同時運行兩個任務，并且動態(tài)監(jiān)測每個任務的計算規(guī)模和性能擴展性，從而達到計算資源分配方式最優(yōu)。

1計算資源分配

計算資源分配的核心問題是尋找并發(fā)執(zhí)行的兩個任務最優(yōu)的計算資源的數(shù)量分配。為此，最直接的方式是對所有的配置方式進行遍歷，記錄下每一種配置方式的性能，從中找出最優(yōu)方案。這種基于遍歷的方法過多地引入了性能很差的配置方式，所以遍歷的過程會造成性能損失。因此，這里提出利用性能曲線線性插值的方法快速準確地找到最優(yōu)的配置方式。在接下來的討論中，需要調度的兩個任務分別表示為K1和K2，它們共同占有計算資源的數(shù)量記為N。兩個任務的執(zhí)行時間分別為T1（n）和T2（n），其中n為分配給該任務的計算資源數(shù)量。由于兩個任務并發(fā)執(zhí)行且兩個任務在計算每個數(shù)據流時的計算量固定，因此運行兩個任務的時間由最慢的任務時間決定，即：

T（n）=MAX（T1（n），T2（N-n））（1）

調度的目的是選擇合適的n，使得Tn（n）的值最小。由于T1（n）和T2（n）都是非解析函數(shù)，因此很難通過解析的方式找到公式（1）的最小值。但是，由于時間函數(shù)T1（n）和T2（n）都是單調遞減函數(shù)，因此，Tn（n）獲得最小值的充分條件為：

T1（n）=T2（N-n）（2）

通過迭代計算的方法，可以得出近似的最優(yōu)資源分配值，對程序性能不會帶來明顯損失。

2緩存資源分配

多任務并發(fā)執(zhí)行時任務間的臨時數(shù)據可以存儲在末級緩存中，從而減少對內存訪問的次數(shù)。由于不同任務對于緩存資源的需求數(shù)量并不相同，因此設計了面向任務級流水線的緩存結構，從而給每個任務分配最優(yōu)的緩存資源。在任務流水線中，前一個任務生成的數(shù)據會被下一個任務利用，一旦下一個任務使用完這些數(shù)據之后，這些數(shù)據則很少被其它任務利用。基于這種觀察，對于任務生成的數(shù)據應該盡可能地存儲在緩存中，而一旦這些數(shù)據被讀取之后，應該立即將這些數(shù)據從緩存中替換出來，從而釋放出這些緩存空間。圖1給出了支持多任務并發(fā)執(zhí)行的緩存結構和管理策略。

圖1（a）顯示了新的緩存結構在傳統(tǒng)的緩存行結構上增加了兩個標識符，Kernel_ID和Stream_ID。其中Kernel_ID記錄訪問該行數(shù)據的任務編號，Stream_ID記錄該行數(shù)據所屬的數(shù)椐流編號。對于一個沒有存儲有效數(shù)據的緩存行，兩個標識位的值都初始化為-1。添加了兩個標識符的緩存工作方式如下：當有訪存請求從計算單元發(fā)射時，對應的Kernel_ID和Stream_ID的信息將添加到該訪存請求中。新的緩存機制對于訪存請求的數(shù)據處理方式與傳統(tǒng)的緩存相同（缺失和命中的判斷以及對于數(shù)據塊的相應處理），區(qū)別在于增加了對于標識符的操作：①如果訪存請求是讀操作，且緩存缺失，則對應緩存行的標識符初始化為訪存請求中的標識符信息；②如果訪存請求是讀操作，且緩存命中，則對應的標識符保持不變；③如果訪存請求是寫操作，不論緩存缺失還是命中，對應緩存行的標識符信息都將進行更新，從而替換為訪存請求中的標識符信息。因此，在新的緩存結構下，能夠明確緩存中數(shù)據的來源。當有任務結束時，能夠快速找到屬于該任務的但不再需要的數(shù)據，從而把這些數(shù)據替換出緩存。

3硬件開銷評估

以下介紹資源動態(tài)分配的硬件開銷。支持計算資源分配的硬件單元被稱為動態(tài)任務分配器（Dynamic Kernel Allocator，DKA），負責計算兩個任務并發(fā)執(zhí)行時最優(yōu)的計算資源分配方式（即分配給兩個任務的計算資源數(shù)量）。該硬件單元可以集成在當前的GPU全局任務調度單元中。

DKA主要的硬件開銷來自于查找表的存儲空間和插值計算單元。假設GPU中集成了24個SM，對于一對任務，需要25條存儲單元來記錄這對任務在各種計算資源分配時的性能。每1條存儲單元需要記錄3條信息，即存儲NK1需要5bits，存儲K1_perf和K2_perf各需要16bits。因此，每1條存儲單元需要37bits的存儲空間。假設DKA可以支持任務流水線的長度為8，那么需要9組（buffer pool也需要一組查找表）查找表的存儲空間，接近1KB（9x25x37bits），這個面積開銷十分微小。此外，DKA還需要一個插值計算單元和若干個組合邏輯?？紤]到插值計算單元的硬件開銷小于一個標準的浮點運算單元，而當前的GPU包含成百上千規(guī)模的浮點運算單元，因此，可以認為額外引入的插值計算單元的硬件開銷對于系統(tǒng)來說是微小的。

對于支持任務并發(fā)執(zhí)行的緩存結構，硬件結構只發(fā)生了很小的改動，因此額外引入的硬件開銷微乎其微。由于每個緩存行增添了兩個標識符，它們分別需要3bits （存儲Kernel_ID，可以支持8個任務）和5bits（存儲Stream_ID，可以支持32個數(shù)據流并且數(shù)據流的ID編號可以循環(huán)使用）的存儲空間。當前典型的GPU緩存包含有12K個緩存行（緩存容量為768KB），新的存儲結構增加了12KB的存儲空間，占現(xiàn)在緩存空間不到1.5%的面積開銷。

4結語

本文討論了任務級的不規(guī)則計算模式，即以流計算為代表的程序中包含任務級流水線，但是不同任務的計算規(guī)模有著很大差異。針對這種不規(guī)則的計算模式，順序執(zhí)行各個任務會造成片上計算資源的空閑。當前典型的多任務并發(fā)機制采用基于搶占式的靜態(tài)調度方式，該調度機制能夠把更多任務發(fā)射到計算資源上，從而消除計算資源空閑的問題。但是，當多個任務并發(fā)執(zhí)行時，該機制無法給出每個任務最優(yōu)的資源分配方式。因此，本文提出了雙任務的動態(tài)調度機制，該機制能夠動態(tài)地分析每個任務的計算規(guī)模，從而賦予每個任務合適的計算資源和緩存資源。該機制能夠改善計算性能，減少內存訪問次數(shù)，并且隨著未來GPU上計算資源規(guī)模的不斷擴大，動態(tài)調度機制的優(yōu)勢將更加顯著。

參考文獻參考文獻：

[1]JANG B，SCHAA D，MISTRY F，et al.Exploiting memory access patterns to improve memory performance in data-parallel architectures[J].Parallel and Distributed Systems，IEEE Transactions on，2011，22（1）：105118.

[2]TZCNG S，PATNCY A，OWENS J D.Task management for irregularparallel workloads on the GPU[C].Proceedings of the Conference on High Performance Graphics，2010：2937.

[3]YANG Y，XIANG P，KONG J，et al.A GPGPU compiler for memory optimization and parallelism management[J].ACM Sigplan Notices，2010，45（6）：8697.

[4]YANG Y，XIANG P，KONG J，et al.A unified optimizing compiler framework for different GPGPU architectures[J].ACM Transactions on Architectures and Code Optimization，2012，9（2）：133.

責任編輯（責任編輯：黃?。?