采用Xilinx Zynq SoC为云计算提速新颖的可重配置硬件加速器可加速基于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。

图1：MapReduce硬件加速器的方框图

MapReduce硬件加速器单元

MapReduce加速单元负责处理Reduce任务的高效实现。其主要工作是合并来自各个处理器的中间键/值对，并为插入新键和更新（累计）键/值对提供快速途径。我们将MapReduce加速器作为协处理器来实现，可通过共享总线扩充为多核处理器。图1为多核SoC中加速器方框图。

如图所示，我们已在配备有一对ARM Cortex™-A9 IP核的Zynq SoC中整合了硬件加速器单元。每个内核都有其自己的指令级和数据级高速缓存，而每种高速缓存都可使用共享互连网络与外设进行通信。该加速器通过连接到互连网络的高性能总线实现与处理器的通信。处理器通过访问加速器的特定寄存器，给出需要更新到MapReduce加速器的键和值。Map任务结束后，加速器即累加了所有键的值。处理器仅需将该键发送给加速器并读取寄存器中的最终值，即可检索该键的最终值。通过这种方法，所提议的架构就能向包含需要更新的键/值对发送无阻塞交易，从而加速MapReduce处理。

编程框架

图2为使用硬件加速器的MapReduce应用编程框架。在原始代码中，Map级发射键/值对，而Reduce级则搜索该键并通过占用若干CPU时钟周期来更新（累加）新值。使用MapReduce加速器的情况则与此相反，Map级仅发射键/值对，而MapReduce加速器则合并所有的键/值对并更新相关条目，因而无需采用Reduce功能。

哈希函数可加速键的索引进程，但若两个键具有相同的哈希值，则可能造成冲突。我们选择了布谷鸟哈希作为解决哈希冲突的最佳途径。

运行在Linux之下的应用层与硬件加速器之间的通信通过使用存储器映射（mmap）系统调用来进行。mmap系统调用能将指定的内核存储器区域映射到用户层，因而用户能根据存储器映射过程中提供的属性对其进行读取或写入操作。

我们使用控制单元来访问这些寄存器和串行化键/值组件的更新。键/值对存储在能根据应用要求进行配置的存储器单元中。该存储器模块包含键、值和可用作标签的部分数位。这些标签用于标示存储器线路是否为空以及是否有效。为了加速键的索引进程，可用哈希模块将初始键转换为存储器模块的地址。

在当前配置中，我们设计的存储器结构可容纳2千个键/值对。每个键的长度可达到64位（8个字符），值的长度达32位。存储器结构的总体大小为2K x 104位。第一个64位存储的键用于比较使用哈希函数时我们究竟是命中还是错失；接下来的8位用于存储标签；再之后的32位则用于存储该值。在当前的配置中，最大键值为64位，哈希函数用于将键（64位）映射到存储器地址（12位）。

图2：编程框架

布谷鸟哈希

哈希函数能加速键的索引进程，但在两个不同的键有着相同哈希值的情况下，也可能造成冲突。为了解决这一问题，我们选择了布谷鸟哈希作为解决哈希冲突的最佳途径。布谷鸟哈希[2]使用两个（而非一个）哈希函数。在插入新的条目时，这个条目就会存储在第一个哈希键的位置。如果该位置被占用，就会将旧条目移到自己的第二个哈希地址。这个过程会循环往复，直到找到空闲地址为止。该算法可提供恒定的查找时间O(1)（查找只要求检查哈希表中的两个位置），而插入时间则取决于高速缓存的大小O(n)。如果该流程应进入无限循环，哈希表就进行重建。

使用T1和T2两个表能实现布谷鸟哈希算法。TI和T2分别对应一种哈希函数，每种大小为r。每个表均使用不同的哈希函数（分别为h1和h2）来创建T1和T2的地址。每个组件x分别经哈希函数h1或h2运算后，存储在T1或T2中，即有T1[h1(x)]或T2[h2(x)]。这样的查找方法简单明了。对每一个我们需要查找的组件x，我们仅需分别使用哈希函数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)]中，如此往复，直至找到一个空闲位置。

表1：可编程逻辑资源分配

根据原始布谷鸟哈希文章[2]的说明，如果在一定次数的尝试之后未能找到空闲位置，则建议对表中的所有组件进行重新处理。在我们当前实现的软件中，每当运算进入这种环路时，软件就会停止运行并将0返回给函数调用。然后该函数调用可能会发起重新哈希处理，或者可能选择像原始代码中的做法一样，向软件存储器结构中添加特定的键。

我们将布谷鸟哈希用于图1所示的MapReduce加速器。我们使用了两个Block RAM来存储T1和T2两个表的条目。这些BRAM可存储键、值和标签。在标签字段中使用1位用于标示特定的列是否有效。使用两个基于简单XOR函数的哈希函数将键映射到BRAM的地址。每次需要访问BRAM地址时，就需要使用哈希表来创建地址，然后根据两个比较器的指示来判断能否命中BRAM（即创建的键与RAM中存储的键一样，且有效位为1）。控制单元可协调对存储器的访问。我们将控制单元实现为可执行布谷鸟哈希的有限状态机（FSM）。

性能评估

我们已在Zynq SoC中实现了所提议的架构。具体而言，我们将Phoenix MapReduce框架映射到Linux 3下的嵌入式ARM IP核中。每当处理器需要更新键/值对的时候，它们就会通过特定的函数调用功能发送信息。为了评估本系统的性能，我们使用了Phoenix框架提供的三种应用，经修改后利用硬件加速器运行。这三种应用分别是字数统计、线性回归和直方图。

所提议的方案具有可配置性，能根据应用需求进行微调。为了评估Phoenix MapReduce框架应用的性能，我们已为加速器配置了4K容量的存储器单元（可存储4,096个键/值对，每个BRAM存储容量为2K）。每个键的大小最大可为8字节。

表1显示了MapReduce加速器的可编程逻辑资源。正如您能看到的，加速器基本上由存储器组成，而控制单元则用于有限状态机，哈希功能只占据器件的一小部分。

图3将原始应用和采用MapReduce加速器应用的执行时间进行了比较。这两次测量均以赛灵思Zynq SoC设计为基础。

在字数统计应用中，原始应用里Map的任务是对字进行识别，然后提交给Reduce任务。Reduce任务随即收集所有的键/值对，并累积每个键的值。在加速器应用中，Map的任务是识别字，然后通过高性能AXI总线将数据提交给MapReduce加速器单元。将键/值对存储在寄存器（每个处理器均不相同）中，然后加速器通过访问存储器结构来累积每个键的值。

为处理器减负

执行时间缩短的原因在于，在原始代码中，Reduce任务必须首先加载键/值表，再在全表范围内搜索需要的键。然后，在完成值的累积后，Reduce任务必须将键存回存储器。在使用MapReduce加速器后，我们可将该处理器从这项任务中释放出来，从而缩短MapReduce应用的总体执行时间。布谷鸟哈希（O(1)）让键的搜索工作在加速器中完成，同时处理器在键/值对的更新过程中通畅无阻。

如图3所示，系统的总体速度提升了1.23倍到1.8倍不等。具体加速情况取决于每项应用的特征。在映射函数较为复杂的情况下，MapReduce加速器的加速性能就不那么明显了。在映射函数较为简单且占用的总体执行时间较少的应用中，加速性能比较显著，因为有大量总体执行时间可用于Map和Reduce功能之间的通信。因此在这种情况下，MapReduce加速器能提供非常明显的加速效果。此外，MapReduce加速器还能在处理器中创建较少的新线程，从而减少环境切换次数和执行时间。例如，在字数统计应用中，平均环境切换次数就从88次降到60次。

MapReduce框架能广泛应用于多核SoC和云计算应用的编程框架。对于赛灵思Zynq SoC等多核SoC平台以及基于MapReduce框架的云计算应用来说，我们提议的硬件加速器能通过为这些应用的Reduce任务加速来降低总体执行时间。