新穎的可重配置硬件加速器可加速基于MapReduce編程框架的應(yīng)用處理。

流視頻、社交網(wǎng)絡(luò)和云計(jì)算等新興Web應(yīng)用亟需能容納數(shù)千臺(tái)服務(wù)器的倉(cāng)庫(kù)規(guī)模的數(shù)據(jù)中心。在數(shù)據(jù)中心和其它計(jì)算機(jī)集群中，用于處理大數(shù)據(jù)集的主要編程框架之一即為MapReduce框架[1]。MapReduce是一種運(yùn)用大量節(jié)點(diǎn)來(lái)處理大數(shù)據(jù)集的編程模型。用戶負(fù)責(zé)設(shè)定“Map”和“Reduce”功能，然后由MapReduce調(diào)度器將任務(wù)分配給處理器。

MapReduce框架的主要優(yōu)勢(shì)之一在于，其能托管在由不同類型處理器構(gòu)成的多個(gè)異構(gòu)集群中。大部分?jǐn)?shù)據(jù)中心都紛紛采用高性能的通用型器件，如英特爾至強(qiáng)(Intel Xeon)、AMD皓龍(AMD Opteron)和IBM Power處理器等。但是，即使在應(yīng)用不屬于高計(jì)算密集型而屬于高I/O密集型的時(shí)候，這些處理器也會(huì)消耗大量的電力。

為了降低數(shù)據(jù)中心的功耗，微服務(wù)器作為一種替代性平臺(tái)近期倍受關(guān)注。這類低成本服務(wù)器通常采用嵌入式系統(tǒng)中使用的低功耗處理器，如ARM?處理器等。微服務(wù)器主要針對(duì)輕量級(jí)或并行應(yīng)用，處理此類應(yīng)用最行之有效的方法是使用在節(jié)點(diǎn)間擁有充足I/O（而非擁有高性能處理器）的單個(gè)服務(wù)器。微服務(wù)器方案具有眾多優(yōu)勢(shì)，如可減少購(gòu)置成本、縮小占用面積，并能降低特定應(yīng)用類型的功耗。

在過(guò)去的幾年里，SeaMicro和Calxeda等幾家廠商已開(kāi)發(fā)出基于嵌入式處理器的微服務(wù)器。但是，MapReduce框架會(huì)占用嵌入式處理器的多種資源，從而會(huì)降低運(yùn)行在這些平臺(tái)上的云計(jì)算應(yīng)用的總體性能。

為了克服這個(gè)問(wèn)題，我們的團(tuán)隊(duì)已為MapReduce框架開(kāi)發(fā)出一種能在全面可編程平臺(tái)上與ARM IP核實(shí)現(xiàn)高效整合的硬件加速單元。為了開(kāi)發(fā)并評(píng)估所提議的方案，我們選用了開(kāi)發(fā)板上集成有雙核Cortex-A9處理器的賽靈思Zynq?-7000 All Programmable SoC。

MapReduce硬件加速器單元
MapReduce加速單元負(fù)責(zé)處理Reduce任務(wù)的高效實(shí)現(xiàn)。其主要工作是合并來(lái)自各個(gè)處理器的中間鍵/值對(duì)，并為插入新鍵和更新（累計(jì)）鍵/值對(duì)提供快速途徑。我們將MapReduce加速器作為協(xié)處理器來(lái)實(shí)現(xiàn)，可通過(guò)共享總線作為多核處理器的擴(kuò)充。圖1為多核SoC中加速器方框圖。

如圖所示，我們已在配備有一對(duì)ARM Cortex?- A9 IP核的Zynq SoC中整合了硬件加速器單元。每個(gè)內(nèi)核都有其自己的指令和數(shù)據(jù)高速緩存，而每種高速緩存都可使用共享互連網(wǎng)絡(luò)與外設(shè)進(jìn)行通信。該加速器通過(guò)連接到互連網(wǎng)絡(luò)的高性能總線實(shí)現(xiàn)與處理器的通信。處理器通過(guò)訪問(wèn)加速器的特定寄存器，給出需要更新到MapReduce加速器的鍵和值。Map任務(wù)結(jié)束后，加速器即累加了所有鍵的值。處理器僅需將該鍵發(fā)送給加速器并讀取寄存器中的最終值，即可檢索該鍵的最終值。通過(guò)這種方法，所提議的架構(gòu)就能向包含需要更新的鍵/值對(duì)發(fā)送無(wú)阻塞交易，從而加速M(fèi)apReduce處理。

編程框架
圖2為使用硬件加速器的MapReduce應(yīng)用編程框架。在原始代碼中，Map級(jí)發(fā)射鍵/值對(duì)，而Reduce級(jí)則搜索該鍵并消耗若干CPU時(shí)鐘周期的時(shí)間來(lái)更新（累加）新值。使用MapReduce加速器的情況則與此相反，Map級(jí)僅發(fā)射鍵/值對(duì)，而MapReduce加速器則合并所有的鍵/值對(duì)并更新相關(guān)條目，因而無(wú)需采用Reduce功能。

Hash函數(shù)可加速鍵的索引進(jìn)程，但若兩個(gè)鍵具有相同的Hash值，則可能造成沖突。我們選擇了Cuckoo Hashing作為解決Hash沖突的最佳途徑。

運(yùn)行在Linux之下的應(yīng)用層與硬件加速器之間的通信通過(guò)使用存儲(chǔ)器映射(mmap)系統(tǒng)調(diào)用來(lái)進(jìn)行。mmap系統(tǒng)調(diào)用能將指定的內(nèi)核存儲(chǔ)器區(qū)域映射到用戶層，因而用戶能根據(jù)存儲(chǔ)器映射過(guò)程中提供的屬性對(duì)其進(jìn)行讀取或?qū)懭氩僮鳌?/p>

我們使用控制單元來(lái)訪問(wèn)這些寄存器和串行化鍵/值組件的更新。鍵/值對(duì)存儲(chǔ)在能根據(jù)應(yīng)用要求進(jìn)行配置的存儲(chǔ)器單元中。該存儲(chǔ)器模塊包含鍵、值和可用作標(biāo)簽的部分?jǐn)?shù)位。這些標(biāo)簽用于標(biāo)示存儲(chǔ)器線路是否為空以及是否有效。為了加速鍵的索引進(jìn)程，可用Hash模塊將初始鍵轉(zhuǎn)換為存儲(chǔ)器模塊的地址。

在當(dāng)前配置中，我們?cè)O(shè)計(jì)的存儲(chǔ)器結(jié)構(gòu)可容納2千個(gè)鍵/值對(duì)。每個(gè)鍵的長(zhǎng)度可達(dá)到64位（8個(gè)字符），值的長(zhǎng)度達(dá)32位。存儲(chǔ)器結(jié)構(gòu)的總體大小為2K x 104位。第一個(gè)64位存儲(chǔ)的鍵用于比較使用Hash函數(shù)時(shí)我們究竟是命中還是錯(cuò)失；接下來(lái)的8位用于存儲(chǔ)標(biāo)簽；再之后的32位則用于存儲(chǔ)該值。在當(dāng)前的配置中，最大鍵值為64位，Hash函數(shù)用于將鍵（64位）映射到存儲(chǔ)器地址（12位）。

Cuckoo Hashing
Hash函數(shù)能加速鍵的索引進(jìn)程，但在兩個(gè)不同的鍵有著相同Hash值的情況下，也可能造成沖突。為了解決這一問(wèn)題，我們選擇了Cuckoo Hashing作為解決Hash沖突的最佳途徑。Cuckoo Hashing[2]使用兩個(gè)（而非一個(gè)）Hash函數(shù)。在插入新的條目時(shí)，這個(gè)條目就會(huì)存儲(chǔ)在第一個(gè)Hash鍵的位置。如果該位置被占用，就會(huì)將舊條目移到自己的第二個(gè)Hash地址。這個(gè)過(guò)程會(huì)循環(huán)往復(fù)，直到找到空閑地址為止。該算法可提供恒定的查找時(shí)間O(1)（查找只要求檢查Hash表中的兩個(gè)位置），而插入時(shí)間則取決于高速緩存的大小O(n)。如果該流程應(yīng)進(jìn)入無(wú)限循環(huán)，Hash表就進(jìn)行重建。

使用T1和T2兩個(gè)表能實(shí)現(xiàn)Cuckoo Hashing算法。TI和T2分別對(duì)應(yīng)一種Hash函數(shù)，每種大小為r。每個(gè)表均使用不同的Hash函數(shù)（分別為h1和h2）來(lái)創(chuàng)建T1和T2的地址。每個(gè)組件x分別經(jīng)Hash函數(shù)h1或h2運(yùn)算后，存儲(chǔ)在T1或T2中，即有T1[h1(x)]或T2[h2(x)]。這樣的查找方法簡(jiǎn)單明了。對(duì)每一個(gè)我們需要查找的組件x，我們僅需分別使用Hash函數(shù)h1和h2檢查T1和T2表中的兩個(gè)可能位置。

要插入組件x，我們需要檢查T1[h1(x)]是否為空。如果為空，就可以把組件x存儲(chǔ)在這個(gè)位置。如果不為空，我們就用x替換T1[h1(x)]中已經(jīng)存在的組件y。然后再檢查T2[h2(y)]是否為空。如果為空，我們將組件y存儲(chǔ)在這個(gè)位置。如果不為空，就用y替換T2[h2(y)]中的組件z。然后我們?cè)賴L試把z存儲(chǔ)到T1[h1(z)]中，如此往復(fù)，直至找到一個(gè)空閑位置。

根據(jù)原始Cuckoo Hashing文章[2]的說(shuō)明，如果在一定次數(shù)的嘗試之后未能找到空閑位置，則建議對(duì)表中的所有組件進(jìn)行重新處理。在我們當(dāng)前實(shí)現(xiàn)的軟件中，每當(dāng)運(yùn)算進(jìn)入這種環(huán)路時(shí)，軟件就會(huì)停止運(yùn)行并將0返回給函數(shù)調(diào)用。然后該函數(shù)調(diào)用可能會(huì)發(fā)起重新Hash處理，或者可能選擇像原始代碼中的做法一樣，向軟件存儲(chǔ)器結(jié)構(gòu)中添加特定的鍵。

我們將Cuckoo Hashing用于圖1所示的MapReduce加速器。我們使用了兩個(gè)Block RAM來(lái)存儲(chǔ)T1和T2兩個(gè)表的條目。這些BRAM可存儲(chǔ)鍵、值和標(biāo)簽。在標(biāo)簽字段中使用1位用于標(biāo)示特定的列是否有效。使用兩個(gè)基于簡(jiǎn)單XOR函數(shù)的Hash函數(shù)將鍵映射到BRAM的地址。每次需要訪問(wèn)BRAM地址時(shí)，就需要使用Hash表來(lái)創(chuàng)建地址，然后根據(jù)兩個(gè)比較器的指示來(lái)判斷能否命中BRAM（即創(chuàng)建的鍵與RAM中存儲(chǔ)的鍵一樣，且有效位為1）。控制單元可協(xié)調(diào)對(duì)存儲(chǔ)器的訪問(wèn)。我們將控制單元實(shí)現(xiàn)為可執(zhí)行Cuckoo Hashing的有限狀態(tài)機(jī)(FSM)。

性能評(píng)估
我們已在Zynq SoC中實(shí)現(xiàn)了所提議的架構(gòu)。具體而言，我們將Phoenix MapReduce框架映射到Linux 3下的嵌入式ARM IP核中。每當(dāng)處理器需要更新鍵/值對(duì)的時(shí)候，它們就會(huì)通過(guò)特定的函數(shù)調(diào)用功能發(fā)送信息。

為了評(píng)估本系統(tǒng)的性能，我們使用了Phoenix框架提供的三種應(yīng)用，經(jīng)修改后利用硬件加速器運(yùn)行。這三種應(yīng)用分別是字?jǐn)?shù)統(tǒng)計(jì)、線性回歸和直方圖。

所提議的方案具有可配置性，能根據(jù)應(yīng)用需求進(jìn)行微調(diào)。為了評(píng)估Phoenix MapReduce框架應(yīng)用的性能，我們已為加速器配置了4K容量的存儲(chǔ)器單元（可存儲(chǔ)4,096個(gè)鍵/值對(duì)，每個(gè)BRAM存儲(chǔ)容量為2K）。每個(gè)鍵的大小最大可為8字節(jié)。

表1顯示了MapReduce加速器的可編程邏輯資源。正如您能看到的，加速器基本上由存儲(chǔ)器組成，而控制單元?jiǎng)t用于有限狀態(tài)機(jī)，Hash功能只占據(jù)器件的一小部分。

圖3將原始應(yīng)用和采用MapReduce加速器應(yīng)用的執(zhí)行時(shí)間進(jìn)行了比較。這兩次測(cè)量均以賽靈思Zynq SoC設(shè)計(jì)為基礎(chǔ)。

?

在字?jǐn)?shù)統(tǒng)計(jì)應(yīng)用中，原始應(yīng)用里Map的任務(wù)是對(duì)字進(jìn)行識(shí)別，然后提交給Reduce任務(wù)。Reduce任務(wù)隨即收集所有的鍵/值對(duì)，并累積每個(gè)鍵的值。在加速器應(yīng)用中，Map的任務(wù)是識(shí)別字，然后通過(guò)高性能AXI總線將數(shù)據(jù)提交給MapReduce加速器單元。將鍵/值對(duì)存儲(chǔ)在寄存器（每個(gè)處理器均不相同）中，然后加速器通過(guò)訪問(wèn)存儲(chǔ)器結(jié)構(gòu)來(lái)累積每個(gè)鍵的值。

為處理器減負(fù)
執(zhí)行時(shí)間縮短的原因在于，在原始代碼中，Reduce任務(wù)必須首先加載鍵/值表，再在全表范圍內(nèi)搜索需要的鍵。然后，在完成值的累積后，Reduce任務(wù)必須將鍵存回存儲(chǔ)器。在使用MapReduce加速器后，我們可將該處理器從這項(xiàng)任務(wù)中釋放出來(lái)，從而縮短MapReduce應(yīng)用的總體執(zhí)行時(shí)間。Cuckoo Hashing(O(1))讓鍵的搜索工作在加速器中完成，同時(shí)處理器在鍵/值對(duì)的更新過(guò)程中通暢無(wú)阻。

如圖3所示，系統(tǒng)的總體速度提升了1.23倍到1.8倍不等。具體加速情況取決于每項(xiàng)應(yīng)用的特征。在映射函數(shù)較為復(fù)雜的情況下，MapReduce加速器的加速性能就不那么明顯了。在映射函數(shù)較為簡(jiǎn)單且占用的總體執(zhí)行時(shí)間較少的應(yīng)用中，加速性能比較顯著，因?yàn)橛写罅靠傮w執(zhí)行時(shí)間可用于Map和Reduce功能之間的通信。因此在這種情況下，MapReduce加速器能提供非常明顯的加速效果。此外，MapReduce加速器還能在處理器中創(chuàng)建較少的新線程，從而減少環(huán)境切換次數(shù)和執(zhí)行時(shí)間。例如，在字?jǐn)?shù)統(tǒng)計(jì)應(yīng)用中，平均環(huán)境切換次數(shù)就從88次降到60次。

MapReduce框架能廣泛應(yīng)用于多核SoC和云計(jì)算應(yīng)用的編程框架。對(duì)于賽靈思Zynq SoC等多核SoC平臺(tái)以及基于MapReduce框架的云計(jì)算應(yīng)用來(lái)說(shuō)，我們提議的硬件加速器能通過(guò)為這些應(yīng)用的Reduce任務(wù)加速來(lái)降低總體執(zhí)行時(shí)間。如欲了解有關(guān)如何運(yùn)用Zynq SoC平臺(tái)為云計(jì)算加速的更多詳細(xì)，敬請(qǐng)聯(lián)系首席作者Christoforos Kachris博士，也可訪問(wèn) 。