朱琳

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

關(guān)鍵詞關(guān)鍵詞：圖形處理器；不規(guī)則任務(wù)；訪存；調(diào)度

DOIDOI：10.11907/rjdk.1431081

中圖分類號(hào)：TP302

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)

文章編號(hào)：16727800（2015）004005702

0引言

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

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

1計(jì)算資源分配

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

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

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

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

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

2緩存資源分配

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

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

3硬件開銷評(píng)估

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

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)參考文獻(xiàn)：

[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.

責(zé)任編輯（責(zé)任編輯：黃健）