SOM算法在申威众核上的实现和优化

自组织神经网络(SOM)是一种被广泛使用的经典机器学习算法,但在处理复杂数据时其执行时间将急剧延长。并行化是解决这个问题的有效途径。基于目前TOP500上排名第一的“神威·太湖之光”超算平台,从模型并行和数据并行的角度出发,设计了SOM在申威众核处理器上的单核组和多核组的并行。一方面,通过程序重构将主要计算步骤转换为矩阵运算并利用高性能扩展数学库实现向量计算的并行化;另一方面,针对超算硬件的特性使用多种优化手段进行进一步的性能优化,使算法的性能得到了极大的提升。实验中,当使用64个核组时,所提算法的总加速比超过10000倍,同时最高可达900多倍的从核加速比也证明了所提算法有效发挥了申威核组中众核的能力。     

基于K-均值的“教”与“学”优化算法

在解决复杂多峰优化问题时,传统的"教"与"学"优化算法易于陷入局部搜索且优化效率较低.针对此问题,提出了一种基于K-均值的"教"与"学"优化改进算法,算法采用K-均值来降低种群规模,又针对"教"和"学"两个阶段进行相应改进,提高全局收敛速度;还加入了"变异"操作来避免算法陷入局部最优.实验对7个单峰值优化问题和2个有代表性的多峰值优化问题进行优化,并与手榴弹爆破算法和传统"教"与"学"优化算法进行比较,实验结果表明,该改进算法在单峰和多峰测试函数中,均能快速高效地寻得全局最优解,优于原始"教"与"学"优化算法.     

基于BSP模型的并行神经网络训练算法

提出了一种适合集群计算机上实现的基于BSP模型的并行神经网络训练算法，分析了其他价函数和加速比，在作者研制的集群计算机上进行了实现和测试，结果表明：当问题规模比较大时，此并行算法能区委了的加速比。     

面向申威众核处理器的并行SaNSDE算法

演化算法作为解决大规模优化问题的重要方法,被广泛应用于机器学习、过程控制、工程优化、管理科学和社会科学等领域.然而在求解高维度、高计算密度问题时,程序性能很难得到保证.在高性能计算机上实现并行化是问题的一个热门解决方案.针对申威众核处理器的硬件特征,提出了采用二级并行策略的自适应邻域搜索的差分进化算法(SaNSDE).第一级为进程并行,实现了合作协同进化模型和池模型,将大规模问题划分为多个低维子问题并分布在不同进程上;第二级为线程并行,使用从核加速了适应度的计算过程.实验结果表明,采用合作协同进化模型和池模型的算法与传统的并行算法相比,经过多核扩展之后收敛效果提升更加明显.相较于串行版本算法,二级并行的SaNSDE算法在四个测试函数上分别获得了134.29、186.05、239.01和189.80的最大加速比.     

多核集群系统下的混合并行遗传算法研究

为应对传统遗传算法在处理大规模组合优化问题面临的进化速度缓慢,难以达到实时要求的严峻挑战,提出了一种在多核PC集群系统上实现“粗粒度一主从式”混合并行遗传算法的模型:通过把“粗粒度一主从式”并行遗传算法映射到多核PC集群上,结合消息传递和共享存储两种并行编程模型,在节点间使用消息传递模型(MPI),对应的遗传算法为粗粒度并行遗传算法,在节点内使用共享存储模型(OpcnMP),对应的遗传算法为主从式并行遗传算法,用MPI和OpenMP混合编程的方式以进程和线程两级并行在多核集群上实现具体的混合并行遗传算法。理论分析和实验结果表明,提出的实现模型有较好的性能,可大大改进传统遗传算法的缺陷。为利用并行遗传算法在普通多核PC集群上处理大规模组合优化问题提出了一种有效、可行的解决方案。     

基于申威众核处理器的NSGA-Ⅱ并行和优化方法

由申威众核处理器组成的“神威·太湖之光”是当前我国性能最高的超级计算机,可为大规模NSGA-Ⅱ求解提供硬件平台。基于硬件架构特点,设计了分岛/主从增强混合并行NSGA-Ⅱ。在主从模式基础上,利用从核间寄存器通信,实现核组内从核局部数据存储的共享。优化流程,实现更多算法模块在从核上的并行。运用DMA传输、向量化、双缓冲、存储优化等方法显著提高加速比。实验表明,优化的并行NSGA-Ⅱ在申威众核处理器上具有良好的加速比和扩展性。     

基于并行遗传算法的智能公交排班研究

智能公交排班问题是公交车辆智能调度的一个典型问题之一。它可以描述为：利用某种智能化算法,在有限的步骤内,找出所有满足约束条件的最优或者接近最优的排班方案。由于排班问题搜索规模巨大,传统算法在短时间内难以获得高质量可行解。文章引入并行遗传算法,对三种主流并行模型进行评价分析,并设计了求解车辆排班问题的粗粒度并行遗传算法,编制了算法实现程序。     

并行遗传算法在弧岛模型上的设计和分析

本文探讨了遗传算法的并行化原理；给出了并行遗传算法弧岛模型上的具体实现方法；分析和比较了用串行遗传算法和并行遗传算法求解ＴＳＰ的实验结果，获得了接近线性的加速比，最后讨论了相关参数对实验结果的影响。     

一种面向多核处理器并行系统的启发式任务分配算法

多核处理器使得并行系统的结构更加复杂并且其中任务个数大大增加,为了在这类系统中高效地进行任务分配,建立了任务分配模型,并提出了一种包含两轮操作的启发式任务分配算法,分别完成进程到处理节点和进程内线程到处理器核的分配.每轮操作经过带回溯的多次迭代处理,最终得到任务到处理器核的分配方案.与穷举查找法和遗传算法的对比测试表明该算法能在较短时间内求得近优解,并且当线程个数增大时,算法的求解时间远小于遗传算法.     

申威众核处理器的并行NSGA-II算法

非支配排序遗传算法（NSGA-II）在多目标优化领域有着广泛的应用,但在处理复杂问题时运行时间相当长。并行化是提高算法执行速度的有效途径。众核处理器的出现,为实现高度并行奠定了物质基础。基于国产超算“神威·太湖之光”的申威众核处理器平台设计了并行NSGA-II算法（PNSGA-II）,实现了算法基于主核的一级并行和基于主/从核的二级并行。在典型测试函数集上的实验表明,在不影响解的质量前提下,PNSGA-II算法不仅大大加快了执行速度,同时算法的收敛速度也更快。     

基于申威众核处理器的HOG特征提取算法并行加速

HOG特征是一种简单高效的常用来进行物体检测的特征描述子,广泛应用于行人检测等领域,然而在处理海量图片时却面临着严峻的性能挑战。解决方法之一就是通过使用"神威太湖之光"超级计算机的处理器节点对海量图像背景下的行人检测算法进行加速。主要采用了两种并行方案:一种是一个处理器同时处理4张图片,另一种是同时处理256张图片。大量的串行和并行处理的实验测试结果表明,对高分辨率多幅图像的并行处理可采用第一种方案,加速比可达83倍;对低分辨率图像可采用第二种方案,加速比最高可达到95。两种并行设计方案在"神威太湖之光"的多处理器节点上具有很好的可扩展性能。     

A parallel ETD algorithm for large-scale rate theory simulation

Rate theory (RT) is a commonly used method to simulate the evolution of material defects. A promising numerical method, exponential time difference (ETD), can reduce the stiff RT equations to explicit ordinary differential equations (ODEs). Previous implementations of ETD on the “Sunway TaihuLight” supercomputer suffer from high computation cost and poor parallel efficiency while solving a large amount of ODEs. This paper improves the algorithm with hybrid MPI+SIMD and additional instruction-level optimizations by taking advantage of the architecture of “Sunway TaihuLight”. The execution time of a single iteration is reduced by about 40%. Scaling from 64 to 4096 processes, the parallel efficiency of the new algorithm achieves 33.5% and 50.6% in strong and weak scalability, which corresponds to 21.4 and 32.4 in speedup, respectively.

     

特征点检测DoG并行算法

特征点检测被广泛应用于目标识别、跟踪及三维重建等领域。针对三维重建算法中特征点检测算法运算量大、耗时多的特点,对高斯差分（Difference-of-Gaussian,DoG）算法进行改进,提出特征点检测DoG并行算法。基于OpenMP的多核CPU、CUDA及OpenCL架构的GPU并行环境,设计实现DoG特征点检测并行算法。对hallFeng图像集在不同实验平台进行对比实验,实验结果表明,基于OpenMP的多核CPU的并行算法表现出良好的多核可扩展性,基于CUDA及OpenCL架构的GPU并行算法可获得较高加速比,最高加速比可达96.79,具有显著的加速效果,且具有良好的数据和平台可扩展性。     

swSpAMM: optimizing large-scale sparse approximate matrix multiplication on Sunway Taihulight

Although matrix multiplication plays an essential role in a wide range of applications, previous works only focus on optimizing dense or sparse matrix multiplications. The Sparse Approximate Matrix Multiply (SpAMM) is an algorithm to accelerate the multiplication of decay matrices, the sparsity of which is between dense and sparse matrices. In addition, large-scale decay matrix multiplication is performed in scientific applications to solve cutting-edge problems. To optimize large-scale decay matrix multiplication using SpAMM on supercomputers such as Sunway Taihulight, we present swSpAMM, an optimized SpAMM algorithm by adapting the computation characteristics to the architecture features of Sunway Taihulight.Specifically, we propose both intra-node and inter-node optimizations to accelerate swSpAMM for large-scale execution. For intra-node optimizations, we explore algorithm parallelization and block-major data layout that are tailored to better utilize the architecture advantage of Sunway processor. For inter-node optimizations, we propose a matrix organization strategy for better distributing sub-matrices across nodes and a dynamic scheduling strategy for improving load balance across nodes. We compare swSpAMM with the existing GEMM library on a single node as well as large-scale matrix multiplication methods on multiple nodes. The experiment results show that swSpAMM achieves a speedup up to 14.5× and 2.2× when compared to xMath library on a single node and 2D GEMM method on multiple nodes, respectively.     

Parallel genetic algorithm for N-Queens problem based on message passing interface-compute unified device architecture

N-Queens problem derives three variants: obtaining a specific solution, obtaining a set of solutions and obtaining all solutions. The purpose of the variant I is to find a constructive solution, which has been solved. Variant III is aiming to find all solutions and the largest number of queens currently being resolved is 26. Variant II whose purpose is to obtain a set of solutions for larger-scale problems relies on various intelligent algorithms. In this paper, we use a master-slave model genetic algorithm that combines the idea of the evolutionary algorithm and simulated annealing algorithm to solve Variant III, and use a parallel fitness function based on compute unified device architecture. Experimental results show that our scheme achieved a maximum 60-fold speedup over the single-CPU counterpart. On this basis, a two-level parallel genetic algorithm based on the island model and master-slave model is implemented on the GPU cluster by using message passing interface technology. Using two-node and three-node GPU cluster, speedup of 1.46 and 2.01 are obtained on average over single-node, respectively. Compared with the sequential genetic algorithm, the two-level parallel genetic algorithm makes full use of the parallel computing power of GPU cluster in solving N-Queen variant II and improves the performance by 99.19 times in the best case.     

基于CUDA的SKINNY加密算法并行实现与分析

针对SKINNY加密算法在中央处理器（CPU）下实现效率偏低的问题,提出一种基于图形处理器（GPU）的快速实现方法。首先,结合SKINNY算法的结构特征提出优化方案,将5个分步操作优化整合为1个整体运算;然后,分析该算法的电子密码本（ECB）模式和计数器（CTR）模式的特性,并给出并行粒度、内存分配等并行设计方案。实验结果表明,与传统的CPU实现方法下的SKINNY算法相比,基于计算统一设备架构（CUDA）实现的SKINNY算法的效率和吞吐量得到很大提升。具体来说,当处理的数据达到16 MB及以上时,在所提实现方法下,SKINNY算法的ECB模式的加速效率提升峰值为99.85%,加速比峰值为671,CTR模式的加速效率提升峰值为99.87%,加速比峰值为765;而与已有AES-256（ECB）和SKINNY_ECB并行算法比较,新提出的SKINNY-256（ECB）并行算法的吞吐量分别是它们的吞吐量的1.29倍和2.55倍。     

基于FPGA的遗传算法实现

针对基于软件实现的遗传算法在求解问题的规模与复杂性不断扩大时,往往会速度慢、效率低下的缺点,提出了一种基于现场可编程门阵列的实现方法,并利用测试函数对算法的实现进行效果验证。实际效果显示,这种硬件实现方法,不仅结构简单,而且有效地减少了运算时间、提高了运行效率,为遗传算法能在一些实时、高速的场合得到应用提供了依据。     

面向国产异构众核系统的Parallel C语言设计与实现

异构众核架构具有超高的性能功耗比,已成为超级计算机体系结构的重要发展方向.但众核系统更为复杂的并行层次和存储层次,给编程和优化带来了极大的挑战,因此研究面向众核系统的并行编程技术,对于降低国产众核系统并行应用的编程难度、提升并行程序的性能都具有重要的意义.提出统一架构的多模式并行编程模型,包括异构融合的加速运算模型和按同构方式编程的自主运算模型,根据编程模型设计了Parallel C语言,能有效描述国产众核系统的异构并行性,与其它众核系统上MPI+X的使用模式相比,编程和系统优化都具有全局视角,在多级局部性描述、单边消息、兼容已有多核应用等方面具有特色;基于Open64构建了Parallel C编译系统,全面支持加速运算模型和自主运算模型,提出并实现了数据布局与自动DMA、编译指导的线程代理和拓扑位置感知的集合通信等优化.Micro Benchmark和实际应用在神威太湖之光计算机系统上的测试数据表明,Parallel C语言和编译系统具有良好的性能和可扩展性,能够有效支撑大型应用.     

申威26010众核处理器上一维FFT实现与优化

根据申威26010众核处理器的特点提出了基于两层分解的一维FFT众核并行算法.该算法基于迭代的Stockham FFT计算框架和Cooley-Tukey FFT算法,将大规模FFT分解成一系列的小规模FFT来计算,并通过设计合理的任务划分方式、寄存器通信、双缓冲以及SIMD向量化等与计算平台相关的优化方法来提高FFT的计算性能.最后对所提出算法的性能进行了测试,相比于单主核上运行的FFTW3.3.4库,获得了平均44.53x的加速比,最高加速比可达56.33x,且其带宽利用率最高可达83.45%.     

FastNBL: fast neighbor lists establishment for molecular dynamics simulation based on bitwise operations

In the molecular dynamics simulation, an important step is the establishment of neighbor list for each particle, which involves the distance calculation for each particle pair in the simulation space. However, the distance calculation will cause costly floating-point operations. In this paper, we propose a novel algorithm, called Fast Neighbor List, which establishes the neighbor lists mainly using the bitwise operations. Firstly, we design a data layout, which uses an integer value to represent the three-dimensional coordinates of a particle. Then, a bunch of bitwise operations and two subtraction operations are used to judge whether the distance between a pair of particles is within the cutoff radius. We demonstrate that our algorithm can deal with the periodic boundary seamlessly. We also use single instruction multiple data (SIMD) instructions to further improve the performance. We implement our algorithm on Intel Xeon E5-2670, ARM v8, and Sunway many-core processors, respectively. Compared with the traditional method, our algorithm achieves on average 1.79x speedup on Intel Xeon E5-2670 processor, 3.43x speedup on ARM v8 processor, and 4.03x speedup on Sunway many-core processor. After using SIMD instructions, our algorithm achieves on average 2.64x speedup and 14.43x speedup on Intel Xeon E5-2670 and ARM v8 processors, respectively.