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

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

1 引 言

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 研究動(dòng)機(jī)

本節(jié)主要介紹研究動(dòng)機(jī),包括研究來源和研究出發(fā)點(diǎn).

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

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

4 預(yù)備知識(shí)

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

4.1 近內(nèi)存計(jì)算

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

圖1展示了近內(nèi)存加速器與傳統(tǒng)加速器的區(qū)別.圖1(a)是傳統(tǒng)加速器概念架構(gòu).該類型加速器與片外DRAM設(shè)備進(jìn)行讀寫數(shù)據(jù)時(shí),需要經(jīng)過內(nèi)存層次結(jié)構(gòu)的長(zhǎng)數(shù)據(jù)通道,才能將數(shù)據(jù)傳輸至處理單元模塊以進(jìn)行計(jì)算.片外DRAM的讀寫能耗限制加速器的能效瓶頸.圖1(b)為基于雙列直插式內(nèi)存模塊(Dual In-line Memory Module,DIMM)的近內(nèi)存計(jì)算加速器概念架構(gòu).加速器直接設(shè)計(jì)在片外DRAM附近,將數(shù)據(jù)處理傳輸過程縮減,減少數(shù)據(jù)的移動(dòng)開銷,降低讀寫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]是一種基本的分類和回歸算法,主要用于已知分類情況下,對(duì)未知類型的數(shù)據(jù)進(jìn)行分類.

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

dis(x-yi)

(1)

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

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

4.3 k-means算法

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

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

(2)

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

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

(3)

(4)

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

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ù)移動(dòng)所需要的能耗開銷.

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

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

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

5.2 總調(diào)度流程

圖3(a)、圖3(b)、圖3(c)介紹KNMC的總調(diào)度流程,包括輸入流程,計(jì)算流程和輸出流程.首先,KNMC進(jìn)行輸入流程.圖3(a)介紹KNMC的輸入流程.KNMC從片外DRAM讀取相應(yīng)的數(shù)據(jù)作為輸入,寫入片上緩存IB中,同時(shí),若有需要,則讀取另外的數(shù)據(jù)寫入另一個(gè)片上緩存CB中.然后,KNMC進(jìn)入計(jì)算流程.圖3(b)介紹KNMC的計(jì)算流程.KNMC將輸入數(shù)據(jù)從片上緩存輸入到PE模塊中進(jìn)行距離計(jì)算等一系列操作.輸出相應(yīng)數(shù)據(jù)存儲(chǔ)于片上緩存OB中.同時(shí),若有需要,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)度流程及對(duì)不同算法的調(diào)度流程舉例Fig.3 KNMC overall scheduling process and illustration of KNMC for different algorithms

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

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

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

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

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

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

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

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

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

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

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

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

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

6 設(shè)計(jì)空間探索

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

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

本次工作所要優(yōu)化的參數(shù)是片上緩存容量大小和PE數(shù).片上緩存參數(shù)為5個(gè)片上緩存IB,OB,CB,PSB和PSB-C的容量大小:wIB,wOB,wCB,wPSB和wPSB-C.處理單元PE的參數(shù)為PE數(shù)量NPE.為求得加速器的最優(yōu)能效,本項(xiàng)工作需要對(duì)wIB,wOB,wCB,wPSB,wPSB-C和NPE盡可能進(jìn)行組合,通過不同組合求出最優(yōu)能效.因?yàn)榧铀倨魇轻槍?duì)k-NN和k-means兩種算法進(jìn)行加速,為求得對(duì)k-NN和k-means兩種算法的最優(yōu)能效值,這里本項(xiàng)工作將加速器最優(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)都表示對(duì)算法加速的總能效,該能效等效于:

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

7 實(shí)驗(yàn)方法

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

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

8 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

8.2 性能對(duì)比結(jié)果

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

8.3 能效對(duì)比結(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,計(jì)算延遲時(shí)間占比是總時(shí)間的1.39%.基準(zhǔn)加速器的頻率是1GHz,片上緩存總大小為32kB.基準(zhǔn)加速器的PE規(guī)模是KNMC的2倍.圖6(c)和圖6(d)分別為KNMC與基準(zhǔn)加速器對(duì)k-NN和k-means加速的歸一化能效比較.結(jié)果表明,KNMC對(duì)k-NN加速的平均能效是基準(zhǔn)加速器的2.1倍,對(duì)k-means加速的平均能效是基準(zhǔn)加速器的1.5倍.KNMC獲得更高的能效主要?dú)w于近內(nèi)存計(jì)算減少對(duì)片外DRAM讀寫所需的能耗,以及合理的片上緩存容量和PE規(guī)模配置.

9 總 結(jié)

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