新型cache共享CPU-FPGA异构平台的开发与分析文献综述

1. 文献综述（或调研报告）：

随着各类应用实例如人工智能，宽带宽通信，大数据中心等等的开发，计算系统的运算能力需求越来越大，计算加速也成为了值得研究的话题。对于某一种或者某一类应用，如果实现了计算加速，便能够减少执行时间，增大吞吐量，或者降低功耗，都节省了时间，金钱，能源。我们知道，不同的计算平台有不同的优势特性，CPU平台是发展时间最久的平台之一，流水线处理高速，各类资源库利于开发；GPU适合高效处理大量同类运算；FPGA能够编程实现并行运算。对于不同的平台，如果能够实现优势互补，将是硬件计算领域的一大进步。近几年来，各家厂商开始尝试整合不同的计算平台来探索新的可能：Xilinx推出的ZYNQ系列将ARM嵌入FPGA中，Intel推出的HARP平台使CPU和FPGA共享同一个Cache。对于这样的异构平台，开发者进行开发研究，希望探索出一种能够合理发挥两种平台优势的方法。

HARP平台使CPU和FPGA共享一部分Cache实现了高速数据交换，因此对于一项本来运行在CPU上的程序，可以将其笨重繁复的计算模块并行化，交予FPGA进行计算加速，从而提高计算效率。Chi Zhang[1]等设计出了运行在HARP上的Merge Sort应用，Sorting是最基本的数据库原始操作之一，需要在延迟，吞吐量和内存带宽利用方面实现高效率和高性能的设计[2]。 最近在FPGA平台上提出了几项关于加速Sorting的工作[3]，[4]，[5]。 这些结果表明，与多核CPU和GPU相比，用于加速分类的FPGA展现出了其竞争力。 但是，由于可用的片上存储器资源有限，FPGA加速器支持的最大数据集大小通常很小。随着加速器不断提高性能和能源效率的标准，将CPU与FPGA相结合的异构架构正在成为实现大型性能改进的新可能。 新兴的异构架构，如Microsoft Catapult，Xilinx Zynq和Intel QuickAssist QPI FPGA平台[6]，[7]，[8]，[9]通过FPGA技术提供硬件加速实现了大规模的并行性。他们对与在HARP上如何加速计算做出了大胆的尝试：基于CPU-FPGA异构平台的高吞吐量合并排序混合设计、基于分而治之的策略，通过使用共享内存在CPU和FPGA上进行并发处理来利用线程级并行性、详细的系统设计，将大规模Merge Sort Accelerator映射到异构CPU-FPGA平台、与仅使用FPGA和仅使用CPU的基线相比，分析混合设计的性能改进和资源利用率、与仅使用CPU，仅基于FPGA的基线和最先进的FPGA设计相比，吞吐量提高了2.9倍，1.9倍和2.3倍。从Chi Zhang等人的研究中可以成功总结出一种HARP的加速计算的理念和方法。

加强学习(Reinforcement Learning)是一种人工智能，它允许代理从与其插入的环境的交互中学习[10]。这种方法适用于没有足够的信息来了解代理为实现其目标必须采取的行为的情况，即没有先前知识的代理人通过与环境的交互来学习，获得他的行动的奖励和发现和最优政策[11]。Q-learning是加强学习的一种，是一种独立于环境的学习方法，。Q(S,A)=Q(S,A) alpha;[R gamma;*max{Q(S,:)}-Q(S,A)][12]是其基本公式原理。通过多次“探索-利用”的学习方法，Q-learning模型收集从环境反馈的每一个动作带来的收益，利用上诉算法，计算出在当前状态下进行某一动作的未来期望收益，最终构建出Q-table：记录了每一种状态下每一种动作的未来期望收益的二维矩阵，Q-table内的每一个值都是一个未来期望收益，记为Q-value，达到足够的次数之后，Q-value会收敛。这样，将训练完成后的Q-table运用于该训练环境，机器便可以成功选择在当前环境下的最佳动作。在硬件中开发Q-learning强化学习技术使得能够设计比其软件等同物更快的系统，从而开启其在满足紧迫时间约束或处理大数据量的问题中使用的可能性。通过在处理速度不相关或低于低功耗需求的限制的应用中减少时钟周期，还可以降低功耗。移动机器人应用中的导航算法通常在几百毫秒内响应，并且该属性使得具有低时钟频率的专用硬件工作与嵌入在微控制器和微处理器上的其他软件限制相吻合。实时应用程序可能有不同的时间限制。最受限制的应用的一些示例是：用于监视卫生设施中的信号的系统，工业系统控制，数字通信系统，机器人甚至汽车和飞机。传统的机制和方法并不总能克服更具挑战性的时间限制所带来的障碍。近年来，由于采样时间性能的潜在影响，实时应用的人工智能硬件算法的研究和开发显着增长[13][14][15][16][17]。在硬件中实现Q学习技术的目的之一便是加速算法处理并获得更快的最优策略，以便它可以用于高要求的应用中。

LUCILEIDE[18]等人的研究提出了一种在FPGA平台上加速运行Q-learning的方法，其在FPGA上同时构建了学习环境和Q-learning算法，把Q-learning的“探索-利用”策略并行化，实现了更高效率的计算。具体而言，他们的工作在Q-learning强化学习技术的FPGA上为硬件并行架构做出了很大贡献。 其主要思想是基于模块化和并行架构的开发，通过降低时钟频率来提高算法执行速度或降低功耗，FPGA的固有属性如灵活性和并行处理是实现这一目标的基础。 FPGA上数据流的并行化允许Q学习技术用于存在大量数据流和严格处理时间限制的应用中。 应用这种架构的另一种可能性是低功耗系统，其中可以减少系统时钟以降低功耗。系统共有“Action Draw”、“Update Module”、“Reward Function Module”、“Value Function Calculation Module”、“Future State Selection Module”五大模块，对这五大模块都进行了复数配置，从而可以同时对不同的状态进行“探索-利用”。

综上，在CPU或FPGA环境下，Q-learning已经有成功的实例，但缺少在异构平台上的实现，也缺少对异构平台进行Q-learning的潜力的探索,同时对于HARP平台也有实现加速的理念和方法，这些都为本设计提供了思路。

参考文献：

[1] C. Zhang, R. Chen and V. Prasanna, High Throughput Large Scale Sorting on a CPU-FPGA Heterogeneous Platform, 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Chicago, IL, 2016, 148-155.

[2] Goetz Graefe. 2006. Implementing sorting in database systems. ACM Comput. Surv. 38, 3, Article 10 (September 2006).

[3] R. Chen and V. Prasanna, Energy and memory efficient mapping of bionic sorting on FPGA, in Proc. of ACM/SIGDA FPGA, 2015.

[4] J. Casper and K. Olukotun, Hardware acceleration of database operations, in Proc. of ACM/SIGDA FPGA, 2014.

[5] D. Koch and J. Torresen, FPGASort: A high performance sorting architecture exploiting run-time reconfiguration on FPGAs for large problem sorting, in Proc. of ACM/SIGDA FPGA, 2011, pp. 45–54.

[6] Microsoft Corporation, An FPGA-based reconfigurable fabric for large-scale datacenters, http://research.microsoft.com/en-us/projects/

[7] Xilinx Inc, Zynq-7000 all programmable soc. [Online]. Available: http://www.xilinx.com/products/silicon-devices/soc/zynq-7000.html

[8] Intel Inc., Xeon FPGA platform for the data center. [Online] Available: http://www.ece.cmu.edu/sim;calcm/carl/lib/

[9] Micron Technology, Inc., “The Convey HC-2 computer.” [Online]. Available: http://www.conveycomputer.com/files/ 4113/5394/7097/Convey HC-2 Architectural Overview.pdf.

[10] R. S. Sutton, Ed., Reinforcement Learning: A Special Issue of Machine

Learning on Reinforcement Learning, 8th ed. Norwell, MA, USA: Kluwer,

1992.

[11] N. C. de Almeida, M. A. C. Fernandes, and A. D. D. Neto, Beamforming

and power control in sensor arrays using reinforcement learning, Sensors, vol. 15, no. 3, pp. 66686687, 2015.

[12] Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, 1998. 107-109.

[13] L. M. Reyneri, Implementation issues of neuro-fuzzy hardware: Going

toward HW/SW codesign, IEEE Trans. Neural Network., vol. 14, no. 1, pp. 176194, Jan. 2003.

[14] A. C. D. de Souza and M. A. C. Fernandes, Parallel fixed-point implementation of a radial basis function network in an FPGA, Sensors, vol. 14, no. 10, pp. 1822318243, 2014.

[15] B. J. Leiner, V. Q. Lorena, T. M. Cesar, and M. V. Lorenzo, Hardware architecture for FPGA implementation of a neural network and its application in images processing, in Proc. Electron., Robot. Automot. Mech. Conf. (CERMA), Morelos, Mexico, 2008, pp. 405410.

[16] F. Mengxu and T. Bin, FPGA implementation of an adaptive genetic algorithm, in in Proc. 12th Int. Conf. Service Syst. Service Manage. (ICSSSM), Guangzhou, China, Jun. 2015, pp. 15.

[17] M. F. Torquato and M. A. C. Fernandes. (2018). High-performance parallel implementation of genetic algorithm on FPGA. [Online]. Available:

https://arxiv.org/abs/1806.11555

[18] L. M. D. Da Silva, M. F. Torquato and M. A. C. Fernandes, Parallel Implementation of Reinforcement Learning Q-Learning Technique for FPGA, in IEEE Access, vol. 7, pp. 2782-2798, 2019.