演化算法在RISC-V体系结构上的高效实现

EFFICIENT IMPLEMENTATIONS OF EVOLUTIONARY ALGORITHMS ON RISC-V ARCHITECTURE

高向能

11849244

硕士

计算机科学与技术

姚新

2020-05-30

2020-07-08

哈尔滨工业大学

深圳

在学术研究和工业生产的许多领域中，常用演化算法对实值问题进行优化和求解。演化算法作为一种群体为基础的随机优化方法，与传统梯度方法相比，缺少梯度信息和优化方向，需要通过大量的迭代来优化和求解问题，存在运行效率上的不足，这是制约演化算法应用的一个重要因素。为了应对这一挑战，本课题从计算机体系结构的角度出发，围绕演化算法运行效率和硬件加速进行研究。基于最新的第五代精简指令集计算（Reduced Instruction Set Computing V, RISC-V）体系结构，本课题对粒子群优化（Particle Swarm Optimization, PSO）、差分演化（Differential Evolution, DE）、协方差矩阵自适应演化策略（Covariance Matrix Adaptation Evolution Strategy, CMAES）三种单目标演化算法和第二代非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm II, NSGA-II）、基于多指标的随机排序算法（Stochastic Ranking-based Multi-indicator Algorithm, SRA）两种多目标演化算法的运行效率进行研究，使用不同参数的CEC’05（2005年“IEEE Congress on Evolutionary Computation”会议发布）和DTLZ（四位作者的名字首字母缩写）基准函数作为演化算法优化的问题，使用硬件仿真作为研究成果的验证方式，以演化算法运行消耗的周期作为运行效率的评价指标。本课题的目的是研究和设计出演化算法在RISC-V体系结构上的高效实现。本课题的第一部分，围绕RISC-V体系结构的存储器系统，对演化算法的运行效率进行初步研究。研究发现在演化算法运行时，高速缓存存在性能下降的风险，进而影响了演化算法的运行效率。为了应对该风险，设计并得到一个在存储器系统的层面，相对高效地运行演化算法的RISC-V体系结构，作为进一步研究的基础。研究还发现多目标演化算法中可能存在耗时的操作，严重影响算法的运行效率，与单目标演化算法相比，多目标演化算法的运行效率具有更大的提升空间，将是进一步研究的重点。本课题的第二部分，围绕NSGA-II和SRA两种多目标演化算法的运行效率进行进一步研究。研究针对NSGA-II算法的非支配排序和SRA算法的计算指标这两种耗时的操作，分别设计了协处理器加速其运行，并在不同规模的DTLZ基准函数上进行验证。验证结果表明，本课题设计的两个协处理器对非支配排序实现了7~11倍的加速，对NSGA-II算法整体实现了1.4~2倍的加速；对计算指标实现了18~34倍的加速，对SRA算法整体实现了11~26倍的加速。本课题设计的协处理器提升了NSGA-II和SRA算法整体的运行效率，得到了相应演化算法在RISC-V体系结构上的高效实现。

In many areas of academic research and industrial production, evolutionary algorithms are used to optimize and solve real-value problems. As population-based stochastic optimization methods, compared to traditional gradient methods, evolutionary algorithms lack gradient information and optimization direction, requiring a large number of iterations to optimize and solve the problem, and there is a deficiency in operational efficiency, which is an important factor constraining the application of evolutionary algorithms. In order to address this challenge, this topic revolves around evolutionary algorithm operational efficiency and hardware acceleration from the perspective of computer architecture.Based on the state-of-the-art reduced instruction set computing V (RISC-V) architecture, this topic investigates the operational efficiency of three single-objective evolutionary algorithms, particle swarm optimization (PSO), differential evolution (DE) and covariance matrix adaptation evolution strategy (CMAES), and two multi-objective evolutionary algorithms, non-dominated sorting genetic algorithm II (NSGA-II) and stochastic ranking-based multi-indicator algorithm (SRA). The CEC'05 (presented at the 2005 IEEE Congress on Evolutionary Computation) and DTLZ (initials of the four authors) benchmark functions with different parameters are used as the problems, hardware emulation is used as the validation method, and the number of cycles consumed by evolutionary algorithms is used as evaluation indicator of the operational efficiency. The aim is to study and design efficient implementations of evolutionary algorithms on RISC-V architecture.In the first part of this topic, a preliminary study of the operational efficiency of evolutionary algorithms is investigated around the memory system of the RISC-V architecture. It was found that there is a risk of performance degradation of the cache when evolutionary algorithms are running, which affects the operational efficiency of evolutionary algorithms. To address this risk, we design a RISC-V architecture that runs evolutionary algorithms relatively efficiently at the level of the memory system, as a basis for further research. It was also found that there may be time-consuming operations in multi-objective evolutionary algorithms that severely affect the operational efficiency, which has more room for improvement compared to single-objective evolutionary algorithms and will be the focus of further research.The second part of this topic revolves around the operational efficiency of two multi-objective evolutionary algorithms, NSGA-II and SRA. We design two co-processors to accelerate non-dominated sorting, the time-consuming operation of NSGA-II, and calculation of indicators, the time-consuming operation of SRA respectively, and the two co-processors are validated on DTLZ benchmark functions with different scales. The validation results show that that these co-processors achieve 7~11X acceleration for non-dominated sorting and 1.4-2X acceleration for NSGA-II algorithm, and 18~34X acceleration for calculation of indicators and 11-26X acceleration for SRA algorithm. The two co-processors improve the overall operational efficiency of the NSGA-II and SRA algorithms and achieves the efficient implementations of the corresponding evolutionary algorithms on RISC-V architecture.

演化算法的运行效率 演化算法的硬件加速 RISC-V体系结构 多目标演化算法 协处理器

operational efficiency of evolutionary algorithms hardware acceleration of evolutionary algorithms RISC-V architecture multi-objective evolutionary algorithms co-processor

中文

联合培养

南方科技大学

高向能. 演化算法在RISC-V体系结构上的高效实现[D]. 深圳. 哈尔滨工业大学,2020.