KNMC:基于近內(nèi)存計算的k-NN和k-means加速器設(shè)計

連 鐸,劉博生,吳亞蘭,武繼剛

(廣東工業(yè)大學(xué) 計算機學(xué)院,廣州 510006)

1 引 言

k近鄰(k-Nearest Neighbor,k-NN)算法和k-均值(k-means)算法為機器學(xué)習(xí)中的經(jīng)典算法.在大數(shù)據(jù)時代,k-NN和k-means在數(shù)據(jù)挖掘[1,2],醫(yī)學(xué)成像[3,4],3D點云[5],文本分類[6],人臉識別[7]等領(lǐng)域廣泛應(yīng)用.k-NN是一種簡單常用的分類算法,通過比較出待測樣本與訓(xùn)練集樣本距離最近的k個樣本,得出待測樣本的分類.k-means是一種無監(jiān)督學(xué)習(xí)聚類算法,實現(xiàn)將距離相近的樣本聚集進(jìn)行分類.

盡管k-NN和k-means應(yīng)用廣泛,但是,在大數(shù)據(jù)處理過程中,k-NN和k-means在計算和數(shù)據(jù)傳輸過程需要消耗巨量的能耗開銷.這源于k-NN和k-means需要對不同數(shù)據(jù)進(jìn)行反復(fù)距離計算.例如,文獻(xiàn)[8]在Intel Xeon E5-4620 CPU上使用UCI Gas數(shù)據(jù)集測試k-NN和k-means.結(jié)果顯示k-NN的距離計算過程占其總運行時間的84.44%,而k-means的距離計算過程占總運行時間的89.83%.在反復(fù)的距離計算中,處理單元(Process Element,PE)需要不斷的對片外動態(tài)隨機存取存儲器(Dynamic Random-Access Memory,DRAM)設(shè)備進(jìn)行讀寫,產(chǎn)生巨大的能耗開銷.

前人已針對k-NN和k-means展開硬件加速方面的研究.PuDianNao[8]提出一個基于專用集成電路(Application Specific Integrated Circuit,ASIC)的k-NN和 k-means加速器硬件架構(gòu).然而,由于該加速器的存儲系統(tǒng)與計算部件是分離的,輸入必須從片外DRAM設(shè)備通過內(nèi)存層次結(jié)構(gòu)傳輸?shù)接糜谟嬎愕腜E部件中,存在嚴(yán)重的 “內(nèi)存墻(memory wall)”[9]問題,導(dǎo)致加速器的計算性能和能效不佳.

近內(nèi)存計算(near-memory computing)[10]是緩解“內(nèi)存墻” 的一項重要技術(shù).近內(nèi)存計算通過將數(shù)據(jù)處理單元設(shè)計于數(shù)據(jù)中心附近,使數(shù)據(jù)傳輸擁有更高的帶寬,最大限度地減少數(shù)據(jù)移動所帶來的能耗開銷[11-13].近內(nèi)存架構(gòu)雖然減少了加速器對片外DRAM的讀寫能耗,但是由于k-NN和k-means算法在計算和傳輸過程會頻繁地讀寫片外DRAM,依舊會導(dǎo)致加速器巨量的能耗開銷.簡單地將加速器直接設(shè)于近內(nèi)存部件中仍會導(dǎo)致加速器效率低下,需要靈活的調(diào)度流來減少加速器對片外DRAM的讀寫頻率.另一方面,近內(nèi)存計算技術(shù)減少了加速器片外DRAM讀寫能耗,片上緩存和PE元件的能耗占比變高,這使得對加速器的設(shè)計空間探索變得更有意義.

本項工作提出一種基于近內(nèi)存計算的k-NN和k-means加速器(簡稱KNMC)設(shè)計.與傳統(tǒng)基于ASIC的加速器相比,KNMC通過近內(nèi)存處理數(shù)據(jù)減少數(shù)據(jù)傳輸能耗.為靈活支持k-NN 和 k-means 加速計算,本項工作設(shè)計可配置的靈活近內(nèi)存加速器架構(gòu),有效減少硬件資源開銷.同時,本文發(fā)現(xiàn)加速器在PE規(guī)模大小和片上緩存(on-chip buffer)容量大小對其整體性能和能耗都有很大影響.本項工作通過設(shè)計不同的加速器配置方案,探索在這些權(quán)衡因素下,加速器達(dá)到最優(yōu)能效的方案.

本文的主要貢獻(xiàn)包括3個方面:

1)提出一種基于近內(nèi)存計算的k-NN和k-means硬件加速器硬件架構(gòu)(KNMC).所設(shè)計的加速器能通過硬件重配置,靈活支持k-NN和k-means硬件加速.

2)在近內(nèi)存架構(gòu)前提下,本文通過評估不同設(shè)計方案,權(quán)衡不同片上緩存大小和PE大小下的能效分析,探索最佳能效下的片上緩存容量和PE規(guī)模配置.

3)綜合實驗結(jié)果表明,所提出的設(shè)計與前人最先進(jìn)的基準(zhǔn)加速器PuDianNao相比,對k-NN實現(xiàn)1.5倍的性能提高和2.1倍的能效提升; 對k-means實現(xiàn)1.2倍的性能提高和1.5倍的能效提升.

2 相關(guān)工作

本節(jié)主要介紹k-NN 和k-means相關(guān)研究,以及本項工作與前人工作的不同之處.

部分研究人員針對k-NN或k-means展開了加速研究.針對k-NN加速計算器的研究中,Mokhles Aamel.Mohsin等人提出一個由微處理器和定制k-NN加速器組成的異構(gòu)系統(tǒng)[14].該系統(tǒng)能實現(xiàn)數(shù)據(jù)預(yù)處理階段,進(jìn)行計算優(yōu)化以提高分類精度.Reid Pinkham等人設(shè)計一個基于k-d樹的k-NN加速器QuickNN[15],通過利用k-d樹對輸入的數(shù)據(jù)集進(jìn)行分層,從而減少k-NN距離計算的計算量,相比于CPU基準(zhǔn),能提升19倍性能.

針對k-means加速器的研究中,Winterstein等人提出基于樹結(jié)構(gòu)的k-means加速器[16].該加速器使用二叉k-d樹結(jié)構(gòu)存儲數(shù)據(jù),實現(xiàn)減少計算量以提升性能.最近Li Du等人提出一種適用于高維度數(shù)據(jù)計算的k-means加速器設(shè)計[17],通過設(shè)計二級移位位數(shù)比較器實現(xiàn)減少數(shù)據(jù)比較的能耗.

部分研究人員還設(shè)計同時支持加速k-NN和k-means的加速器.Daofu Liu等人提出PuDianNao,一個基于ASIC的能夠同時支持k-NN和k-means加速的加速器.該加速器通過對算法的共同點進(jìn)行分析,能夠充分利用硬件資源進(jìn)行加速計算,相比于NVIDIA K20M GPU,能提升1.2倍性能,并減少128.41倍能耗.

上述的加速器,都需要與片外DRAM設(shè)備頻繁進(jìn)行數(shù)據(jù)交互,而在與片外DRAM設(shè)備進(jìn)行數(shù)據(jù)傳輸時,會產(chǎn)生巨大的能耗開銷.本項研究針對上述問題設(shè)計一種適用于k-NN和k-means的近內(nèi)存可配置加速器.同時,本項工作通過設(shè)計空間探索,探索最優(yōu)片上緩存容量和PE規(guī)模配置,實現(xiàn)最優(yōu)能效.

3 研究動機

本節(jié)主要介紹研究動機,包括研究來源和研究出發(fā)點.

本項工作提出基于近內(nèi)存計算的k-NN和k-means加速器.近內(nèi)存計算將加速器的架構(gòu)耦合于片外DRAM附近,這樣大大減少了數(shù)據(jù)傳輸時數(shù)據(jù)移動的硬件資源消耗,極大程度地減少讀寫片外DRAM設(shè)備所需要的能耗.盡管如此,簡單將加速器搬運到近內(nèi)存部件仍會導(dǎo)致加速器部件效率低下.本項工作提出通過靈活的k-NN和k-means調(diào)度使得加速器能夠充分利用計算資源.

在其距離計算中,由于片上緩存資源有限,需要和片外DRAM設(shè)備進(jìn)行交互,減少片外訪存效率是提高能效的關(guān)鍵.盡管前人加速器早有通過設(shè)計空間探索片上緩存在加速器中的效率影響[18],但是很少有工作關(guān)注片上緩存和PE規(guī)模同時對近內(nèi)存加速器的效率影響.其中,片上緩存的容量大小影響加速器讀寫操作的延遲和能耗.PE規(guī)模決定同時進(jìn)行處理的數(shù)據(jù)量.近內(nèi)存計算減少加速器讀寫片外DRAM的能耗開銷,使得片上緩存容量和PE規(guī)模對加速器讀寫操作的能耗影響變得更大.加速器不僅需要選擇合適的PE數(shù)量,更是需要選擇適當(dāng)容量的片上緩存部件避免不必要的能耗開銷.為探索得出加速器的最優(yōu)能效,本項工作先量化加速器能效和片上緩存、 PE規(guī)模的最優(yōu)化問題,然后通過求解最優(yōu)化問題,得出在能效達(dá)到最優(yōu)時的加速器片上緩存容量和PE規(guī)模配置.

4 預(yù)備知識

本節(jié)主要介紹本加速器所涉及到的近內(nèi)存計算技術(shù),k-NN算法和k-means算法.

4.1 近內(nèi)存計算

近內(nèi)存計算的主要目標(biāo),是讓數(shù)據(jù)處理在數(shù)據(jù)所在的位置附近進(jìn)行,即將計算處理單元耦合在數(shù)據(jù)附近,從而最大限度地減少數(shù)據(jù)移動的資源消耗.而3D集成和堆疊技術(shù)的發(fā)展,有效支撐近內(nèi)存技術(shù)的實現(xiàn)[19].

圖1展示了近內(nèi)存加速器與傳統(tǒng)加速器的區(qū)別.圖1(a)是傳統(tǒng)加速器概念架構(gòu).該類型加速器與片外DRAM設(shè)備進(jìn)行讀寫數(shù)據(jù)時,需要經(jīng)過內(nèi)存層次結(jié)構(gòu)的長數(shù)據(jù)通道,才能將數(shù)據(jù)傳輸至處理單元模塊以進(jìn)行計算.片外DRAM的讀寫能耗限制加速器的能效瓶頸.圖1(b)為基于雙列直插式內(nèi)存模塊(Dual In-line Memory Module,DIMM)的近內(nèi)存計算加速器概念架構(gòu).加速器直接設(shè)計在片外DRAM附近,將數(shù)據(jù)處理傳輸過程縮減,減少數(shù)據(jù)的移動開銷,降低讀寫DRAM能耗,從而提高加速器能效.

圖1 傳統(tǒng)加速器與近內(nèi)存加速器架構(gòu)比較Fig.1 Comparison between conventional accelerators and near-memory accelerator

4.2 k-NN算法

k-NN[20]是一種基本的分類和回歸算法,主要用于已知分類情況下,對未知類型的數(shù)據(jù)進(jìn)行分類.

k-NN包括兩個關(guān)鍵步驟.首先,每個待測樣本都需要與整個訓(xùn)練集樣本進(jìn)行距離計算.如公式(1)所示:

dis(x-yi)

(1)

x表示待測樣本,yi表示訓(xùn)練集樣本,公式(1)求出待測樣本x與訓(xùn)練集樣本yi的歐式距離.其次,k-NN從距離的計算結(jié)果中比較找出與待測樣本距離最近的k個訓(xùn)練集樣本.

在整個k-NN計算過程中,數(shù)據(jù)之間的距離計算是最主要且最耗時的部分.距離計算的過程需要不斷將數(shù)據(jù)輸入到PE中進(jìn)行處理.片上緩存的容量大小和PE規(guī)模在距離計算中至關(guān)重要.

4.3 k-means算法

k-means[21]是一種無監(jiān)督的機器學(xué)習(xí)算法.k-means主要將數(shù)據(jù)樣本劃分為k個無相交的集合,每一個集合稱之為一個 “群”(cluster).

k-means主要包括兩個步驟.首先,k-means需要進(jìn)行分群操作.k-means先隨機選取k個樣本點作為質(zhì)心(centroid),再將樣本數(shù)據(jù)與這k個質(zhì)心進(jìn)行距離計算,比較得出每一個樣本數(shù)據(jù)所屬最近質(zhì)心,如公式(2)所示:

(2)

Ci表示第i個質(zhì)心對應(yīng)的群.x表示群集Ci中的樣本,yi表示的是群集Ci的質(zhì)心,dis(x-yi)求出樣本x與質(zhì)心yi間的歐式距離.公式最后將所屬相同質(zhì)心的樣本數(shù)據(jù)歸于一個群,得到k個群.

其次,k-means需要進(jìn)行質(zhì)心更新操作.k-means將所屬同一個質(zhì)心的數(shù)據(jù)進(jìn)行累加平均,得出每一個群的新質(zhì)心,如公式(3)所示:

(3)

(4)

整個k-means過程中,最耗時的部分為數(shù)據(jù)與質(zhì)心之間的距離計算.而且,k-means算法需要多次迭代計算,這意味著需要重復(fù)進(jìn)行數(shù)據(jù)與質(zhì)心的距離計算.

5 硬件架構(gòu)

本節(jié)主要介紹所提出的加速器硬件架構(gòu),包括加速器的基本架構(gòu)和調(diào)度流.

5.1 基本架構(gòu)

圖2(a)為所提出KNMC加速器的整體架構(gòu).KNMC位于DIMM中,DIMM橋接處理單元和標(biāo)準(zhǔn)的內(nèi)存通道接口.內(nèi)存控制器通過內(nèi)存通道接口與內(nèi)存中的加速器進(jìn)行通信.由于該加速器靠近DRAM,該架構(gòu)可以減少片外DRAM設(shè)備與加速器交互的數(shù)據(jù)移動所需要的能耗開銷.

圖2 KNMC加速器Fig.2 Proposed KNMC accelerator

圖2(b)展示KNMC組件,主要包括PE計算部件,片上緩存和Centroid模塊.PE模塊主要用于對數(shù)據(jù)之間的距離計算和所產(chǎn)生的結(jié)果進(jìn)行累加.KNMC包括5個片上緩存,分別是:用于存放質(zhì)心的片上緩存CB; 用于存放輸入數(shù)據(jù)的片上緩存IB和輸出數(shù)據(jù)的片上緩存OB; 用于存放部分和的片上緩存PSB和存放部分和累加計數(shù)的片上緩存PSB-C.Centroid模塊用于實現(xiàn)對質(zhì)心的更新和新舊質(zhì)心比較.

PE模塊用于計算不同數(shù)據(jù)間的距離,以及對所產(chǎn)生的結(jié)果進(jìn)行累加.在k-NN的距離計算上,由公式(1)得知,PE模塊以待測數(shù)據(jù)x和訓(xùn)練數(shù)據(jù){y1,y2…yn}作為輸入,得出x1與{y1,y2…yn}距離最近的k個訓(xùn)練數(shù)據(jù),最后輸出k個訓(xùn)練數(shù)據(jù)的索引.在k-means中,由公式(2)得知,PE模塊以待測數(shù)據(jù)x和質(zhì)心{y1,y2…yn}作為輸入,計算數(shù)據(jù)x與每一個質(zhì)心yi的距離,然后比較x與{y1,y2…yn}距離的大小,得出距離最小的一個,輸出其對應(yīng)的質(zhì)心索引.PE模塊同時進(jìn)行對應(yīng)質(zhì)心群上的數(shù)據(jù)累加,輸出對應(yīng)的累加結(jié)果.

5.2 總調(diào)度流程

圖3(a)、圖3(b)、圖3(c)介紹KNMC的總調(diào)度流程,包括輸入流程,計算流程和輸出流程.首先,KNMC進(jìn)行輸入流程.圖3(a)介紹KNMC的輸入流程.KNMC從片外DRAM讀取相應(yīng)的數(shù)據(jù)作為輸入,寫入片上緩存IB中,同時,若有需要,則讀取另外的數(shù)據(jù)寫入另一個片上緩存CB中.然后,KNMC進(jìn)入計算流程.圖3(b)介紹KNMC的計算流程.KNMC將輸入數(shù)據(jù)從片上緩存輸入到PE模塊中進(jìn)行距離計算等一系列操作.輸出相應(yīng)數(shù)據(jù)存儲于片上緩存OB中.同時,若有需要,KNMC將另外的數(shù)據(jù)輸出于片上緩存PSB和PSB-C中,再經(jīng)由Centroid模塊調(diào)度.最后,KNMC進(jìn)行輸出流程.圖3(c)介紹KNMC的輸出流程.KNMC將數(shù)據(jù)從片上緩存 OB寫入片外DRAM中,待OB數(shù)據(jù)全部寫出,結(jié)束調(diào)度.

圖3 KNMC總調(diào)度流程及對不同算法的調(diào)度流程舉例Fig.3 KNMC overall scheduling process and illustration of KNMC for different algorithms

5.3 k-NN調(diào)度流程

圖3(d)為KNMC加速計算k-NN算法的整個過程.圖中灰色部分是未參與調(diào)度的模塊.以下仔細(xì)介紹整個k-NN的調(diào)度過程:

1)KNMC從DRAM讀取待測數(shù)據(jù)和訓(xùn)練數(shù)據(jù)寫入片上緩存IB.然后KNMC從IB讀取一個待測數(shù)據(jù),廣播到PE上,同時從IB讀取多個訓(xùn)練數(shù)據(jù),輸入到PE;

2)待測數(shù)據(jù)與多個訓(xùn)練數(shù)據(jù)在PE中同時進(jìn)行距離計算.KNMC將距離計算結(jié)果進(jìn)行比較,最后得出k個待測試數(shù)據(jù)最近的距離數(shù)據(jù);

3)KNMC將這k個待測數(shù)據(jù)寫入片上緩存OB.待整個流程結(jié)束后,KNMC將OB中的結(jié)果寫入DRAM中,完成加速器對k-NN算法的計算.

5.4 k-means調(diào)度流程

圖3(e)為KNMC加速計算k-means算法的整個過程.以下仔細(xì)介紹整個k-means的調(diào)度過程:

1)KNMC從DRAM讀取待分群數(shù)據(jù),寫入片上緩存IB.同時,KNMC從IB讀取一個待分群數(shù)據(jù)廣播到PE;

2)KNMC從DRAM讀取初始化好的質(zhì)心寫入片上緩存CB.同時,KNMC從CB讀取多個質(zhì)心,輸入到PE;

3)KNMC將待分群數(shù)據(jù)與多個質(zhì)心同時進(jìn)行距離計算并比較,得出待分群數(shù)據(jù)距離最近的質(zhì)心索引,即該數(shù)據(jù)所屬的群索引;

4)KNMC將所得出的群索引輸出并寫入OB.若OB已被寫滿,則KNMC對OB進(jìn)行刷新,將OB中的數(shù)據(jù)寫入DRAM中,再將索引寫入OB;

5)KNMC將片上緩存PSB對應(yīng)索引的部分和與當(dāng)前數(shù)據(jù)進(jìn)行累加,并根據(jù)該索引從片上緩存PSB-C讀出對應(yīng)的計數(shù)進(jìn)行累加,累加后的部分和與計數(shù)分別寫入PSB和PSB-C中;

6)KNMC將存儲于PSB中的部分和與PSB-C中的計數(shù)輸入到Centroid模塊中進(jìn)行相除,得出新的質(zhì)心,并將新的質(zhì)心與舊的質(zhì)心進(jìn)行比較.若新質(zhì)心與舊質(zhì)心相同,則循環(huán)停止,算法結(jié)束; 若新質(zhì)心與舊質(zhì)心不相等,則KNMC重新跳轉(zhuǎn)到①繼續(xù)執(zhí)行上述步驟.

6 設(shè)計空間探索

本節(jié)針對加速器PE規(guī)模和片上緩存容量進(jìn)行設(shè)計空間探索.本節(jié)首先通過PE規(guī)模和片上緩存容量作為變量建立最優(yōu)化問題.其次,求解最優(yōu)化問題,得出最優(yōu)加速器片上緩存容量和PE規(guī)模配置.

6.1 最優(yōu)化問題的確立

本次工作所要優(yōu)化的參數(shù)是片上緩存容量大小和PE數(shù).片上緩存參數(shù)為5個片上緩存IB,OB,CB,PSB和PSB-C的容量大小:wIB,wOB,wCB,wPSB和wPSB-C.處理單元PE的參數(shù)為PE數(shù)量NPE.為求得加速器的最優(yōu)能效,本項工作需要對wIB,wOB,wCB,wPSB,wPSB-C和NPE盡可能進(jìn)行組合,通過不同組合求出最優(yōu)能效.因為加速器是針對k-NN和k-means兩種算法進(jìn)行加速,為求得對k-NN和k-means兩種算法的最優(yōu)能效值,這里本項工作將加速器最優(yōu)能效表示為:

max(fk-NN(BS,NPE)×fk-means(BS,NPE))

(5)

該公式由以下條件約束:

BS=C(wIB,wOB,wCB,wPSB,wPSB-C)

(6)

NPE∈{1,2,4,8,16,32,64}

(7)

wIB,wOB,wCB,wPSB,wPSB-C∈{1,2,4,8,16,32,64}kB

(8)

在式(5)中,fk-NN(BS,NPE)表示加速器調(diào)度k-NN的能效,fk-means(BS,NPE)表示加速器調(diào)度k-means的能效.約束(6)中,BS表示加速器中wIB,wOB,wCB,wPSB和wPSB-C的組合.約束(7)確定NPE的數(shù)量選擇范圍.約束(8)確定wIB,wOB,wCB,wPSB和wPSB-C的容量選擇范圍.fk-means(BS,NPE)和fk-NN(BS,NPE)都表示對算法加速的總能效,該能效等效于:

(9)

其中fenergy efficiency代表加速器的總能效,fenergy代表加速器的總能耗,該能耗由片上緩存,KNMC和片外DRAM設(shè)備所消耗的能耗組成.fperformance表示加速器的總性能.通過式(5)～式(9),求得該加速器wIB,wOB,wCB,wPSB,wPSB-C和NPE的最優(yōu)配置,以得到最優(yōu)能效.

6.2 求解最優(yōu)問題

由約束式(7)、式(8)可知,變量wIB,wOB,wCB,wPSB,wPSB-C和NPE值個數(shù)非常有限.本項工作通過窮舉法對這些變量進(jìn)行組合,結(jié)合式(5)～式(9)求解該最優(yōu)問題.本項工作將每一種組合的情況一一列出,從這些組合中找出最高能效的片上緩存容量和PE規(guī)模配置.為使加速器獲得最佳能效,提高加速器對不同數(shù)據(jù)集的適應(yīng)能力,本項工作采用多個數(shù)據(jù)集進(jìn)行計算空間探索.通過計算出加速器調(diào)度每一個數(shù)據(jù)集的能效,再對所有數(shù)據(jù)集的能效求幾何平均,本方法將得出用于空間探索的評估計算的能效參考值.

7 實驗方法

本節(jié)介紹實驗的具體方法,包括部分參數(shù)選取,實驗所選用的工具和實驗步驟.

本項工作主要通過兩個步驟對加速器進(jìn)行評估.第1步是通過設(shè)計空間探索,求得加速器的最優(yōu)能效配置.由于本項工作的參數(shù)較多,本項工作先通過不同PE規(guī)模的能效影響確定PE數(shù)量,再在該PE規(guī)模下進(jìn)一步確定最優(yōu)片上緩存容量組合.在本項工作中,每一個PE包含16個乘法器,32個加法器,14個比較器和1個累加器.第2步是將本項工作提出的加速器與前人最先進(jìn)的加速器基準(zhǔn),PuDianNao[8],進(jìn)行比較.PuDianNao能夠?qū)-NN和k-means進(jìn)行加速.

8 實驗結(jié)果

本節(jié)主要介紹實驗結(jié)果并對實驗結(jié)果進(jìn)行分析.

8.1 設(shè)計空間探索結(jié)果

本項工作通過PE數(shù)量和片上緩存的容量進(jìn)行設(shè)計空間探索,PE的數(shù)量取值從1個～64個(每個PE有16個乘法器,32個加法器,14個比較器和1個累加器),而每一個片上緩存的容量取值從1kB～64kB.片外DRAM的容量取值為1GB.

圖4為取不同PE規(guī)模時,該加速器的最高歸一化能效值.加速器由公式(9)求出能效值,加速器的歸一化能效值由最低能效值點作為基準(zhǔn)點求出.可以看出,當(dāng)PE數(shù)量為8時(NPE= 8),加速器能夠得到最高的能效值.在圖4中,隨著PE數(shù)量的增加,加速器的最高能效值先增長,然后再減少.這是由于隨著PE數(shù)量的增加,每一次并行計算的數(shù)據(jù)增加,計算所需要的周期數(shù)就會隨之減少,即性能得到提升,能效隨之提升.但同時,PE規(guī)模的增大造成加速器的功耗增加,而且需要將片外DRAM設(shè)備和片上緩存的I/O位寬增加保證計算過程的連續(xù)性.這導(dǎo)致加速器的能耗增加.當(dāng)能耗的增加程度高于性能的提升程度時,加速器的能效也會隨之下降.經(jīng)過本項工作的實驗得知,該加速器在PE數(shù)量等于8時能夠得到最佳能效.

圖4 不同PE規(guī)模的歸一化能效比較Fig.4 Normalized energy efficiency comparison of different PE scales

圖5(a)為PE數(shù)量等于8時,加速器采用不同容量的片上緩存時的歸一化能效變化圖.本項工作通過對比加速器不同片上緩存大小配置下的能效值,選取能效最高值作為加速器的能效最優(yōu)點.當(dāng)wIB=16kB,wOB= 16kB,wCB= 4kB,wPSB= 4kB和wPSB-C= 1kB(總片上緩存大小為41kB)時加速器能達(dá)到能效最優(yōu)點.可以發(fā)現(xiàn),加速器在片上緩存容量較小時,所取得的能效很低.因為對于CB,PSB這些片上緩存,CB所存儲的是質(zhì)心值,PSB所存儲的是各個數(shù)據(jù)中間累加的部分和.它們所需存儲的值相對較少,但卻需要頻繁地讀取所存儲的全部數(shù)據(jù).當(dāng)容量取值太小導(dǎo)致無法將數(shù)據(jù)全部存儲時,加速器需要頻繁地對片外DRAM進(jìn)行讀寫以暫存無法存儲的數(shù)據(jù),這造成大量的能耗開銷.當(dāng)片上緩存容量取值較小時,加速器需要反復(fù)刷新片上緩存,讀寫片外DRAM導(dǎo)致延時增加,導(dǎo)致性能降低.當(dāng)片上緩存容量取值較大時,加速器能效也會降低.因為隨著片上緩存容量的增加,其訪問延時和訪問能耗也增加.經(jīng)過實驗得知,wIB= 16kB,wOB= 16kB,wCB= 4kB,wPSB= 4kB和wPSB-C= 1kB時能夠得到加速器的最優(yōu)能效.

圖5 NPE=8時不同片上緩存大小下的歸一化能效,能耗,性能趨勢Fig.5 Normalized energy efficiency,energy and performance trend under different on-chip buffer sizes when NPE=8

圖5(b)為該加速器在PE數(shù)量等于8時,采用不同容量的片上緩存時的歸一化能耗圖.圖5(b)中接近最優(yōu)的能耗點,是指在能效最優(yōu)的加速器配置下,加速器的相對能耗值.另外,由圖可見在片上緩存較小時有兩個能耗值相對較大(72.9和5.0).這是由于當(dāng)CB,PSB兩個片上緩存容量都較小時,無法將數(shù)據(jù)全部存儲,加速器需要頻繁對片外DRAM設(shè)備讀寫.當(dāng)CB片上緩存的容量能夠容納整個質(zhì)心數(shù)據(jù)時(wCB= 4kB),加速器對片外DRAM設(shè)備的讀寫會極大程度的減少,加速器的相對能耗值會從72.9下降至5.0.當(dāng)PSB片上緩存容量能夠容納整個中間部分和的數(shù)據(jù)時(wPSB= 4kB),加速器與片外DRAM設(shè)備的數(shù)據(jù)傳輸也會減少,從而減少能耗,加速器的相對能耗值從5.0降至1.0.之后加速器的相對能耗值隨著片上緩存容量的增大而增加.

圖5(c)為該加速器在PE數(shù)量等于8時采用不同容量片上緩存時的歸一化性能圖.圖5(c)中接近最優(yōu)的性能點是指能效最優(yōu)時加速器的相對性能值.片上緩存的讀寫延時隨片上緩存容量的增大而增大.片上緩存總?cè)萘吭谛∮?6kB時,相對性能取值很小,這是由于片上緩存所能存儲的數(shù)據(jù)量少,導(dǎo)致片上緩存刷新頻率高,對片外DRAM的讀寫頻率高,導(dǎo)致加速器性能下降.此時相對性能隨著片上緩存容量的增加而增加,因為片上緩存容量的增加能夠極大程度減少片外DRAM的讀寫頻率.當(dāng)片上緩存容量大于26kB,片上緩存容量的增大對片外DRAM讀寫頻率影響減少,訪問片上緩存的時延成為影響性能的主要因素,導(dǎo)致相對性能開始隨片上緩存容量的增大而減小.

8.2 性能對比結(jié)果

本項工作加速器的PE規(guī)模和片上緩存與基準(zhǔn)加速器PuDianNao規(guī)模不同.為進(jìn)行公平的性能比較,本項工作將KNMC的PE規(guī)模重置為與基準(zhǔn)加速器相同(NPE=16).圖6(a)顯示本項工作與基準(zhǔn)加速器對k-NN加速的歸一化性能比較.圖6(b)顯示本項工作與基準(zhǔn)加速器對k-means加速的歸一化性能比較.結(jié)果表明,KNMC對k-NN加速的平均性能是基準(zhǔn)加速器的1.5倍,對k-means加速的平均性能是基準(zhǔn)加速器的1.2倍.性能的提升歸于加速器靈活的調(diào)度流使加速器充分利用硬件資源,提升了加速器的PE利用率.加速器對k-NN加速的PE利用率提升1.5倍,對k-means加速的PE利用率提升1.3倍.

8.3 能效對比結(jié)果

該能效比較基于加速器的原始配置.KNMC的配置是通過空間探索得出的最佳配置(PE數(shù)量NPE= 8,片上緩存wIB= 16kB,wOB= 16kB,wCB= 4kB,wPSB= 4kB,wPSB-C= 1kB,總片上緩存容量為41kB).KNMC的頻率是800MHz.KNMC硬件架構(gòu)中,PE的功耗為50.6mW,總面積為0.6mm2,Centroid模塊的功耗為1.1mW,總面積為0.05mm2,計算延遲時間占比是總時間的1.39%.基準(zhǔn)加速器的頻率是1GHz,片上緩存總大小為32kB.基準(zhǔn)加速器的PE規(guī)模是KNMC的2倍.圖6(c)和圖6(d)分別為KNMC與基準(zhǔn)加速器對k-NN和k-means加速的歸一化能效比較.結(jié)果表明,KNMC對k-NN加速的平均能效是基準(zhǔn)加速器的2.1倍,對k-means加速的平均能效是基準(zhǔn)加速器的1.5倍.KNMC獲得更高的能效主要歸于近內(nèi)存計算減少對片外DRAM讀寫所需的能耗,以及合理的片上緩存容量和PE規(guī)模配置.

9 總 結(jié)

本項工作提出一個基于近內(nèi)存計算的k-NN和k-means加速器.該加速器通過靈活的調(diào)度流,讓加速器充分利用硬件資源對k-NN和k-means進(jìn)行加速計算.同時,本項工作通過設(shè)計空間探索,尋求最優(yōu)的片上緩存容量大小和PE規(guī)模,實現(xiàn)加速器的最優(yōu)能效.實驗結(jié)果表明,與前人最先進(jìn)的基準(zhǔn)加速器相比,本項工作對k-NN實現(xiàn)1.5倍的性能提高和2.1倍的能效提升,對k-means實現(xiàn)1.2倍的性能提高和1.5倍的能效提升.