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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?

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

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

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

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