NDP-Ledger：面向区块链应用的通用高通量加速架构①

安述倩 李文明 范志华 吴海彬 吴 萌 王 达 张 浩 唐志敏

(*计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190)

(**中国科学院大学 北京 100049)

0 引 言

作为去中心化交易协议，区块链已广泛应用于众多领域，如数字货币、金融服务和物联网(Internet of things，IoT)[1-4]等，成为研究热点之一。最初基于区块链技术的数字货币应用，如比特币采用的典型的安全哈希算法(secure Hash algorithm，SHA-256)对计算资源需求较大，对存储容量和带宽的需求较小，这使SHA-256算法在图形处理器(graphics processing unit， GPU)上取得了优异的效率。但是由于GPU的通用性设计，SHA-256并不能充分利用GPU上的各类计算资源，导致计算能效比并不理想[5]。另一方面，由于SHA-256算法固定，计算模式简单，定制化的ASIC芯片较GPU可以实现更高的性能和能效比[6]，成为了当前数字货币领域的主要算力之一。但是ASIC芯片却违背了比特币设计的去中心化思想[7]，为缓解这种冲突，研究人员提出了众多新的数字货币应用，如莱特币(litecoin, LTC)[8]、以太坊(Ethereum)[9]、Dash币[10]、Zcash[11]、Equihash算法[12]、Bytom[13]等，算法变得更加复杂，并且需要更大的存储容量和更高的访存带宽。这些数字货币的发展方向是寻找反中心化算法以实现区块链处理器的公平性，导致越来越多的区块链算法增加了对存储、内存带宽的需求，并降低了对计算资源的需求，这使中央处理器(central processing unit, CPU)、GPU甚至ASIC的效率越来越低。同时，区块链算法迅速演变，而ASIC只能针对一类区块链算法进行加速，无法实现通用性的加速。基于以上分析，需要找到相对通用的处理架构，满足高能效的区块链算法处理。

近年来，近数据处理(near-data-processing，NDP)为需要大存储容量和高存储访问带宽的应用提供了一种有效的解决方案。3D堆叠存储技术提供了一种通过降低数据搬运成本来提高计算系统的性能和降低功耗的方法。此外，为了进一步提高大规模并行执行应用程序的效率，数据流执行模式已在许多处理器中得到广泛应用。数据流执行模式具有天然的并行特征，并通过降低访存来缓解“存储墙”问题。

通过分析不同类型的区块链应用程序的特点以及3D堆叠存储技术特征，本文提出了一种基于3D堆叠存储器和数据流执行模式的面向区块链应用处理的通用数据处理架构，NDP-Ledger。本文的主要贡献包括：

(1)分析并对比了不同区块链应用程序的算法特征，并基于算法特征，提出了通用NDP加速器架构设计NDP-Ledger。

(2)提出了基于3D堆叠存储器的面向区块链应用的通用NDP加速架构。

(3)设计并实现了粗粒度的数据流执行模型，提高数据处理的并行度，高效地控制内存以及阵列之间的数据流动。

(4)实验结果表明，本文提出的通用加速处理架构与通用多核CPU相比，性能提升了39.98倍；与通用GPU相比，性能提升了1.8倍。

1 相关工作

近几年，区块链技术在学术界和工业界都获得了极大的关注，基于区块链协议的应用越来越多地服务于国民经济的发展，包括金融服务、公证、智能合约、IoT以及数字货币。此类应用对处理器的性能和功耗提出了更高的要求，低效的CPU无法满足此类应用的需求。因为具有更多的计算资源和更高的并行度，GPU一度成为继CPU之后的首选区块链处理架构。为了追求更高的收益，针对一种或几种区块链应用的专用ASIC加速器逐渐替代了GPU，例如针对比特币设计的AvalonMiner[14]等。然而，由于新算法和新应用的不断涌现，这些ASIC无法满足不断演化的算法需求，仅能支持一种或几种算法的高效执行。另外，越来越多的算法不适合在ASIC上进行计算，这给ASIC设计带来了更大的挑战。

随着3D封装技术的发展，NDP为具有简单计算模式和大存储容量需求的应用程序提供了新的高效解决方案。Kang等人[15]将计算单元、有限状态机和其他控制逻辑集成到普通动态随机存储器(dynamic random access memory, DRAM)中构成了3D堆叠内存，用来加速用于DNA比对的Blast算法。Pugsley等人[16]使用了低能耗的指令内核，例如Cortex A5，与混合内存立方体(hybrid memory cube，HMC)一起实现了高能效的新一代数据中心(new data center, NDC)架构。Nair等人[17]在HMC的逻辑层上实现了复杂的运算部件，用于加速科学计算应用处理。Ahn等人[18]提出了一种称为PEI(PIM-enabled instructions)的通用NDP体系结构，该体系结构实现了一种可基于数据的位置实现内存处理的机制。与之前的工作类似，Santos等人[19]在HMC的逻辑层中放置了可重构处理单元，可以灵活处理不同类型的数据。文献[20]利用现场可编程门阵列(field programmable gate array, FPGA)和粗粒度可重构阵列(coarse-grained reconfigurable array，CGRA)的优势来实现高能效和高灵活性的NDP系统。同时，由于图计算的大量离散存储访问的特征，研究人员提出了基于HMC的高效架构用于图计算处理[21-23]。在其他相关工作中，HMC用于字符串处理[24]和矩阵中的乘加运算[25]，这些算法具有简单的计算模式和海量的数据集。综上所述，随着3D堆叠技术的发展，NDP已成为解决内存密集型应用程序的最有前景的方法之一。

另一方面，随着应用程序(如人工智能(artificial intelligence， AI)、IoT和网络服务)所需要处理的数据量的不断增长，数据流体系结构展现出比传统冯诺依曼体系结构具有更好的执行并行度和执行性能。数据流体系结构的优点主要来自2个方面：首先是数据流执行模式的天然并行性，一旦数据准备好就触发指令，无需考虑指令和数据的依赖性；第二是内存访问量的减少，相当一部分数据在片上流动，缓解了传统冯诺依曼结构中的“存储墙”的问题。已有的诸多研究工作已经证明了数据流体系结构在许多应用程序中的优势。例如，Wave Computing提出的数据流处理器(DPU)[26]实现了高性能处理AI应用程序，NeuFlow处理器[27]是为视觉处理设计的数据流架构。其他典型的数据流体系结构包括TeraFlux[28]、Runnemede[29]、TRIPS[30]和WaveScalar[31]，在特定应用中，均体现出数据流结构对于冯诺依曼体系结构的巨大优势。

基于以上分析，本文探索了基于3D堆叠内存和数据流控制机制的区块链应用通用加速结构设计思路，以实现更为高效的区块链通用处理架构。

2 区块链应用分析

去中心化及不可篡改是区块链的核心思想，分布式账本是由不断产生的区块组成，这些区块在整个区块链网络上共享给不同的组织，以确保分类账的公平性、开放性和安全性。区块链网络中的每个节点都接收区块头，并在处理后返回计算结果。该过程由多种算法组成，用以证明工作已经完成。随着越来越多不同需求的逐渐演变，基于区块链应用的算法变得越来越复杂，算法的核心对于计算资源要求不高，但是越来越依赖于存储器来减少ASIC对于去中心化思想的影响。在本节中，首先根据算法采用的核心思想总结不同算法的特征和具体的资源需求，然后根据不同的算法特征以及各种计算、存储需求，分析适用于不同区块链应用程序的硬件架构设计，并结合新兴的存储技术，分析未来的结构设计的可能性。

2.1 哈希相关的算法

比特币作为区块链技术的第1个著名应用，利用了加密算法SHA-256，该算法执行定点模式的哈希运算，包括6个逻辑运算功能，如表1所示。在大多数的哈希算法中，移位、与、或、异或、非运算是最常见而且是主要的运算。这些操作很简单，对计算资源的复杂性要求不高，但是需要重复执行多次，这对于结构复杂而功能强大的CPU及GPU来说是一种资源浪费。

表1 SHA-256算法的逻辑运算符和功能描述

在比特币之后，研究人员提出了使用更复杂的哈希运算或不同哈希运算组合的数字货币。因此，更加复杂和需要更多软硬件资源的工作量证明(proof of work， PoW)算法被提出，如Quark应用了9种哈希函数，包括BLAKE，BMW，GROESTL，JH，KECCAK和SKEIN等等。DASH结合了11种哈希加密算法，命名为X11。相应地，X13和X15算法也随之被提出。几乎所有方法都基于现有的加密算法进行了升级，这些算法强调简单的逻辑运算而不是复杂的科学计算，这使得针对此类算法的ASIC的研发相对容易。

2.2 内存依赖型算法

因为纯哈希算法易于ASIC加速，这违背了区块链去中心化的原则，因此，一些更平等的共识算法被逐渐提出。例如，Ethash是对Dagger-Hashimoto进行优化，该算法的执行很大程度依赖存储容量和访存带宽，其数据量的大小超过1 GB，并且每年增加7 GB，与内存需求相比，对CPU的计算能力的需求并不是那么强烈。另一个典型的应用是Zcash，它使用被称为生日悖论的Equihash作为其共识算法。 Equihash是一种依赖于内存的算法，每个线程至少需要1 GB的内存容量。还有许多其他共识算法，所有这些算法都强调带宽和内存容量，而不是计算性能。 因此，针对这类应用，NDP架构具有很大的优势。

2.3 其他典型算法

有些研究人员认为ASIC仅支持哈希类运算，造成了资源浪费，因此并不认可这种做法。使用现有的计算资源来处理区块链应用程序，同时进行一些其他有效计算，这方面是有意义的。例如，tensority是基于张量计算模型的ASIC友好共识算法，其中矩阵和张量运算被引入到哈希过程中。因此，这些处理机还可以用于AI硬件加速服务、并行计算，并产生额外的社会效益。 另一个例子是Primecoin，它是世界上第1个以科学计算为设计目标的共识算法。在Primecoin中，PoW不仅为网络提供了安全性和生成区块的功能，而且还生成了数学研究人员感兴趣的特殊形式的质数链。

以上为代表性的区块链应用程序。当然，还有许多其他的区块链应用程序使用了复杂且有意义的共识算法，这些算法面向不同的应用领域，都可以归为上述类别。

2.4 设计面向区块链应用的高效结构

大多数区块链应用程序的特点是逻辑操作简单，内存容量需求大和带宽需求高。因此，要为区块链应用开发更加通用和高效的处理架构，应该充分考虑并利用这些特征。随着3D封装技术的发展，3D堆叠存储器技术已经成熟。已有研究证明了3D堆叠存储器[25-30]的优势，它通过减少数据搬运距离并提供高带宽来提高计算机的性能。3D堆叠存储器，如HMC已经成为比传统存储器体系结构更具吸引力的设计方案。本文以HMC为例，研究3D堆叠存储器在区块链应用场景中的效果。

如图1所示，在HMC中，逻辑层(logic die)和多层DRAM堆叠在芯片上，使用硅通孔(through silicon via，TSV)技术以进行层间通信。典型的HMC由32个库(vault)组成，每个库在垂直方向上由几个可以独立访问的堆叠随机存取存储(random access memory，RAM)块组成，以此实现更短的存储访问距离和更高的内存带宽。与传统的内存系统相比，HMC具有更高的访存性能和更低的能耗损失。逻辑层可以通过集成运算部件来就近处理存储器中的数据，添加了运算部件的HMC可以像ASIC一样作为高能效的加速架构。

图1 HMC存储结构示意图

3 NDP-Ledger架构设计

本文提出了一种基于3D堆叠存储器和数据流执行模式的近数据处理架构NDP- Ledger，以加速各种区块链应用程序的执行。 本节将讨论NDP- Ledger的结构设计、编程模型和数据流控制机制。

3.1 NDP-Ledger 体系结构概述

NDP-Ledger的总体架构如图2所示。在主机端，设置了1个加速使能单元(acceleration enable unit，AEU)。AEU用于监视主机处理器的行为并决定是否激活NDP-Ledger。用户使用专门的编程接口来控制AEU。在收到启动NDP-Ledger加速区块链算法的CALL之后，CALL将绕过缓存直接发送到HMC控制器的NDP处理内核，NDP处理器核解析指令并运行，指令执行结束后，收集结果并处理，并将最终结果发送回主机端。在AEU未使能状态下，传统的内存访问系统仍可按其普通方式工作。当选择NDP-Ledger模式时，数据将直接在HMC中被处理。在数据一致性方面，为了保持高速缓存和HMC之间的数据一致性，2种方式可以选择。第1个方法是当命令从AEU发送到HMC控制器时，控制器需要广播到所有缓存，无效掉HMC端需要由内核处理的所有数据。第2个方法是高速缓存绕过策略，即需要由处理器核处理的数据应标记为非高速缓存存储数据。在NDP-Ledger中，选择第2种方法，即绕过缓存策略，以避免维护缓存一致性带来开销。图2(b)显示了NDP-Ledger的执行模型。

图2 NDP-Ledger 体系结构图

图3显示了NDP-Ledger的详细加速架构设计。如图3(a)所示，在HMC的逻辑层中的每个vault控制器上实现加速处理单元阵列，由16个处理单元(process element，PE)组成。所有运算单元都由高速总线连接。如图3(b)所示，PE之间由1个mesh结构的片上网络连接。4个PE由同一个路由器连接，并且可以在数据流执行模型中作为1个工作组。共享路由器可提高PE组内部的通信效率。图3(c)展示了PE的结构，它由指令缓冲区、上下文操作数、流水线和路由器组成。本文采用粗粒度的数据流执行模型，指令块(而不是指令)作为最小的调度单元。粗粒度的数据流执行模型可以简化控制逻辑，并且流水线设计仍使用控制流执行模型。图3(d)展示了流水线的结构。区块链应用程序中大部分的运算为简单的逻辑运算，因此，PE中配置了2个逻辑单元(logic unit，LU)来增强逻辑运算能力，此外还包含1个算术单元，1个浮点单元和1个LD/ST单元。与传统处理器流水线不同，在数据流执行模式中，增加了FLOW单元来支持PE之间的数据流动。FLOW单元由特殊指令控制，用来将数据从操作数缓冲区复制到其他PE中。该指令在源代码的编译阶段生成。数据流映射决定了指令块和PE之间的映射关系。为了提高执行的并行性，PE采用SIMD执行模式。

图3 NDP-Ledger加速架构示意图

3.2 编程和指令映射

在编程模型的设计上，实现了类似于CUDA的编程模型作为用户调用运行内核算法的NDP-Ledger加速器的接口。加速单元仅用于处理算法的内核部分，而其他功能，如通过Internet与其他节点进行通信等功能，在主处理器上执行。

本文实现了粗粒度的数据流执行模型，其中指令块是最小的调度单元。指令块通常包含多条指令，用于实现特定功能。比如for()、while() 或者公式等(例如比特币应用中的Maj()、Ch()、Σ0()、σ1())，其中一个或者多个的功能实现可以编写在1个指令块中，称之为执行块(execution block，Exeblock)。

下面以比特币为例来详细说明Exeblock和映射机制的实现。如图4所示，根据上面介绍的规则，将该算法编程为几个Exeblock(白色上层框)， 灰色底框显示运行Exeblock的PE。右侧部分显示数据的流向。在当前映射方式中，选择边缘PE加载数据并将数据搬运到它们的右侧的PE中以进行下一步计算。空闲PE可以处理另一个比特币任务，为了充分利用计算资源，多个任务可以同时映射到PE阵列上运行。

图4 比特币算法到PE阵列的映射方式以及数据流图

在进行Exeblock划分时，按照图5所示的方法，针对算法进行解析。根据SHA-256的算法特点，首先将算法的执行过程划分为“报文预处理”、“加载Hash初值”、“Hash运算”等3大部分，针对每一部分，根据其所需要执行的具体功能，按照指令数均衡的原则，划分指令块，并利用PE的任务级并行以及SIMD特性，挖掘算法的并行性；根据指令块之间的数据依赖关系，实现算法的依赖关系图，最终形成数据流图。图4是针对SHA-256算法的宏观解析，具体到实际的指令块，编译器通过检索实际的数据流依赖关系，会形成更加复杂的数据流图。

图5 SHA-256算法数据流图解析过程

除了Exeblock的划分，数据流执行模式中最重要的映射机制，是将Exeblock放到指定PE上的策略，以往研究人员针对映射机制研究已经有很多工作，如面向科学计算的映射算法[32]、考虑负载均衡的映射算法TBIM[33](topology-based instruction mapping) 等。TBIM算法如图6所示，将Exeblock根据数据依赖关系形成数据流图(dataflow graph)，作为映射算法输入之一，并且将PE阵列以及拓扑关系作为映射算法第2个输入，通过衡量各个PE上定点浮点负载以及网络传输代价的大小，逐个检索各个指令块的最佳映射位置，获得最优的映射结果。

图6 TBIM算法[33]

3.3 粗粒度的数据流控制机制

在本文实现的粗粒度数据流模型中，最小调度单位是Exeblock，其中包含一行或几行程序代码，这些代码可以实现用户确定的一个或多个功能。一旦所有数据到达，就可以触发Exeblock执行。如图7所示，一个应用程序可以分为几个任务，每个任务由几个Exeblock组成。可以根据数据量的大小和同时运行的任务数将Exeblock执行流图映射到内部PE级别、PE阵列级别或跨PE阵列级别。在图中，有2个要处理的应用程序，每个应用程序包含几个任务。图中显示了只有1个PE阵列的可能映射结果。数据流图映射可能跨PE阵列，多个PE阵列共同在一个应用程序或任务上工作。数据流映射是在编程时确定的，并将配置信息发送到每个PE阵列的控制逻辑，如图4所示。为了使数据流图的Exeblock更有效地工作，本文开发了一种双向ack机制来控制Exeblock之间的交互。每个Exeblock都有1个三位的状态字，该状态字指示与执行块相关的运行状态。三位的状态字用来控制上游和下游Exeblock的执行，如图8所示。Ack、active 和 done是3个控制信号，用于维持数据流图的执行。Ack用于将自身节点的完成消息通知上游节点。Active负责启动下游节点。Done信号标记节点所有循环的结束。所有Exeblock均受HMC内存中NDP内核的控制。这样的设计方案使得PE支持任务级并行，同时可以并行执行一个任务的不同迭代。图8展示了5个Exeblock的执行示例。图中标记了控制步骤的详细说明。每个Exeblock都有upstream、downstream、 enable三位状态字，分别用于表示当前节点需要回应的上游个数、需要激活的下游个数以及是否已经被控制部件激活。Exeblock可以执行的条件是当前被激活的节点需要发送ack和active的上下游节点数都为0，即在上次迭代执行已经结束的情况下，才可以进入下一次执行。图中B0、B1为根节点，无父节点，B2、B3分别为其子节点，B3和B4为叶子节点。Enable主要用来控制根节点是否可以正常执行，根节点收到控制核的激活信号后，处于可执行状态，执行结束后需要将enable归0，避免在子节点当前迭代未结束之前再次执行；中间各子节点包括叶子节点，主要通过判断upstream来确定是否可以正常执行。运行过程中，中间节点的enable信号一直处于激活状态，后续的各次迭代收到上游节点的激活信息后进行开始执行。控制核需要收到所有节点发出的done信号之后，才会激活任务的下一次迭代，如图8第9步所示，B0和B4同时在执行任务的不同迭代，实现任务级并行。

图7 PE阵列和PE单元上的映射示例图

图8 粗粒度数据流的控制机制示意图

4 实验与评估

为了验证NDP-Ledger的性能，对本文所提出的架构进行了模拟仿真，并将其与Intel CPU和NVIDIA GPU进行了比较。

4.1 实验设置

本实验将CasHMC[34]集成到Gem5[35]中来模拟NDP-Ledger的架构设计。Gem5是一个完整的系统模拟器。CasHMC是一个实现了HMC存储的周期精确的模拟器。实验中，采用了1个Cube，存储空间大小为8 GB。每个Cube包含32个vaults，每个vault分为16个banks，其中32个vaults分别对应32个PE 阵列结构。本文在HMC内存中添加了4个ARM1176作为多NDP处理器核来控制PE阵列，ARM1176用作加速器的MCU，它负责调度任务到加速器并与主机处理器进行通信。为了提高并行计算能力，在实验中，每个PE单元包含4组算术部件，并以SIMD方式执行。本文使用CACTI对寄存器的功耗和面积、配置缓冲区以及其他部件进行建模。使用通用服务器级Intel E5-2697 v3和高性能服务器加速卡NVIDIA TITAN XP作为对比平台，详细配置如表2所示。NDP-Ledger的功耗和面积参数为32 nm工艺下参数。

表2 CPU、GPU 和 NDP-Ledger 参数对比

HMC逻辑芯片的功耗和面积数据来源于Micron公司公布的数据[36]。四个NDP核心的总功率为0.5 W，HMC为90 W[16]，每个PE阵列的总功率为0.8 W，32个PE阵列的总功率为25.6 W。NDP-Ledger的整体功率为116 W。NDP-Ledger的面积等于HMC控制逻辑部分的面积。从表中可以看出，NDP-Ledger的面积和功率都小于CPU和GPU。

本文选择了具有代表性的区块链应用的算法作为基准测试程序，如表3所示。算法中的主要操作步骤已在表中列出。这些运算主要与移位运算、逻辑运算和矩阵运算有关。费马小定理是搜索素数Cunningham链的关键操作。

表3 基准测试程序说明

4.2 性能评估与分析

在实验中，通过编程来充分利用CPU和GPU的硬件资源。为了排除主机系统对CPU、GPU和NDP-Ledger的影响，仅使用这3个平台执行区块链应用程序的核心算法部分。

图9显示了CPU、GPU和NDP-Ledger的性能比较。结果表明，NDP-Ledger的平均运算速度是E5-2697 v3的39.98倍，是NVIDIA TITAN XP平均速度的1.8倍。最好的加速结果为Scrypt算法，因为该算法具有简单的逻辑运算和访存密集型的特点。

图9 CPU、GPU和 NDP-Ledger性能对比图

图10显示了3种结构的能效对比。由于NDP-Ledger所拥有的热设计功耗(thermal design power，TDP)比GPU少，因此在能效上取得了更好的结果。结果表明，NDP-Ledger和GPU相比，能效比是其3.9倍；和CPU相比，能效比是其49.97倍。

图10 CPU、GPU和 NDP-Ledger 功效对比图

在性能密度方面，NDP-Ledger由于其3D堆叠存储技术减小了总面积，从而提高了单位面积的性能，如图 11所示。集成PE阵列的逻辑层，其面积等于HMC本身面积。实验结果表明，NDP-Ledger的单位面积计算密度是E5-2697 v3的60.11倍，是NVIDIA TITAN XP的2.81倍。

图11 CPU、GPU和NDP-Ledger 性能密度对比图

5 结 论

随着区块链技术的飞速发展，区块链应用越来越丰富，其核心算法对处理器的计算性能和存储访问性能要求不断变化，目前缺乏可以高效处理区块链应用的通用结构。针对这一现状，本文提出了基于3D堆叠存储的具有数据流执行模式的通用NDP区块链加速结构设计，将PE阵列单元与3D堆叠存储集成在一起，以提高性能密度并减少数据传输距离。实验表明，本文提出的NDP-Ledger提高了区块链应用的处理性能和能效比。同时，提出了一种面向粗粒度数据流执行模型的高效编程和控制行机制，提高了程序执行的并发度，减少了存储器访问的需求。评估结果表明，NDP-Ledger处理性能是主流CPU的39.98倍，是主流GPU的1.8倍，验证了本文提出的结构的有效性。

本文提出的通用性加速结构NDP-Ledger结合了3D堆栈存储以及数据流执行模型，下一步的研究工作需要针对这两方面结合来进行。针对数据流执行模型的编译技术研究，进一步减少对存储访问的依赖；针对存储层次结构的优化研究，进一步提升存储的效率。这两方面对NDP-Ledger的结构及性能提升有着重要影响，也是基于本文提出的结构未来要开展的工作。