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

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

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

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

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

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

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

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

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

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

運行在Linux之下的應用層與硬件加速器之間的通信通過使用存儲器映射(mmap)系統調用來進行。mmap系統調用能將指定的內核存儲器區域映射到用戶層，因而用戶能根據存儲器映射過程中提供的屬性對其進行讀取或寫入操作。

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

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

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

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

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

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

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

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

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

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

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

圖3將原始應用和采用MapReduce加速器應用的執行時間進行了比較。這兩次測量均以賽靈思Zynq SoC設計為基礎。

?

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

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

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

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