BFS Parallel Algorithm Based on Sunway TaihuLight

In recent years,more and more attention has been paid to the research and application of graph structure.As the most typical representative of graph structure algorithm,breadth first search algorithm is widely used in many fields.However,the performance of traditional serial breadth first search(BFS)algorithm is often very low in specific areas,especially in large-scale graph structure traversal.However,it is very common to deal with large-scale graph structure in scientific research.At the same time,the computing performance of supercomputer has also made great progress.China’s self-developed supercomputer system Sunway TaihuLight(SW)has won the top 500 list for three consecutive times.The huge computing performance of supercomputer is the key to solve this problem.It can be seen that if we use the computing power of supercomputing to solve the problem of large-scale graph structure traversal,the efficiency of graph structure traversal will be greatly improved.This paper expounds how to realize the breadth first search algorithm of graph structure on the Sunway TaihuLight,and achieved some results.In this way,MPI and thread library called athread of SW platform are used,and the traversal performance is improved dozens of times through the above related technologies and some partition methods of graph structure.

Scalability and efficiency challenges for the exascale supercomputing system:practice of a parallel supporting environment on the Sunway exascale prototype system

With the continuous improvement of supercomputer performance and the integration of artificial intelligence with traditional scientific computing,the scale of applications is gradually increasing,from millions to tens of millions of computing cores,which raises great challenges to achieve high scalability and efficiency of parallel applications on super-large-scale systems.Taking the Sunway exascale prototype system as an example,in this paper we first analyze the challenges of high scalability and high efficiency for parallel applications in the exascale era.To overcome these challenges,the optimization technologies used in the parallel supporting environment software on the Sunway exascale prototype system are highlighted,including the parallel operating system,input/output(I/O)optimization technology,ultra-large-scale parallel debugging technology,10-million-core parallel algorithm,and mixed-precision method.Parallel operating systems and I/O optimization technology mainly support largescale system scaling,while the ultra-large-scale parallel debugging technology,10-million-core parallel algorithm,and mixed-precision method mainly enhance the efficiency of large-scale applications.Finally,the contributions to various applications running on the Sunway exascale prototype system are introduced,verifying the effectiveness of the parallel supporting environment design.

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.

Thread Private Variable Access Optimization Technique for Sunway High-Performance Multi-core Processors

The primary way to achieve thread-level parallelism on the Sunwayhigh-performance multicore processor is to use the OpenMP programming technique.To address the problem of low parallelism efficiency caused by slow accessto thread private variables in the compilation of Sunway OpenMP programs, thispaper proposes a thread private variable access technique based on privilegedinstructions. The privileged instruction-based thread-private variable access techniquecentralizes the implementation of thread-private variables at the compilerlevel, eliminating the model switching overhead of invoking OS core processingand improving the speed of accessing thread-private variables. On the Sunway1621 server platform, NPB3.3-OMP and SPEC OMP2012 achieved 6.2% and6.8% running efficiency gains, respectively. The results show that the techniquesproposed in this paper can provide technical support for giving full play to theadvantages of Sunway’s high-performance multi-core processors.

Heterogeneous Parallel Algorithm Design and Performance Optimization for WENO on the Sunway TaihuLight Supercomputer

A Weighted Essentially Non-Oscillatory scheme(WENO) is a solution to hyperbolic conservation laws,suitable for solving high-density fluid interface instability with strong intermittency. These problems have a large and complex flow structure. To fully utilize the computing power of High Performance Computing(HPC) systems, it is necessary to develop specific methodologies to optimize the performance of applications based on the particular system’s architecture. The Sunway TaihuLight supercomputer is currently ranked as the fastest supercomputer in the world. This article presents a heterogeneous parallel algorithm design and performance optimization of a high-order WENO on Sunway TaihuLight. We analyzed characteristics of kernel functions, and proposed an appropriate heterogeneous parallel model. We also figured out the best division strategy for computing tasks,and implemented the parallel algorithm on Sunway TaihuLight. By using access optimization, data dependency elimination, and vectorization optimization, our parallel algorithm can achieve up to 172× speedup on one single node, and additional 58× speedup on 64 nodes, with nearly linear scalability.

Enabling Highly Efficient k-Means Computations on the SW26010 Many-Core Processor of Sunway TaihuLight

With the advent of the big data era,the amounts of sampling data and the dimensions of data features are rapidly growing.It is highly desired to enable fast and efficient clustering of unlabeled samples based on feature similarities. As a fundamental primitive for data clustering,the k-means operation is receiving increasingly more attentions today.To achieve high performance k-means computations on modern multi-core/many-core systems,we propose a matrix-based fused framework that can achieve high performance by conducting computations on a distance matrix and at the same time can improve the memory reuse through the fusion of the distance-matrix computation and the nearest centroids reduction.We implement and optimize the parallel k-means algorithm on the SW26010 many-core processor,which is the major horsepower of Sunway TaihuLight.In particular,we design a task mapping strategy for load-balanced task distribution,a data sharing scheme to reduce the memory footprint and a register blocking strategy to increase the data locality.Optimization techniques such as instruction reordering and double buffering are further applied to improve the sustained performance.Discussions on block-size tuning and performance modeling are also presented.We show by experiments on both randomly generated and real-world datasets that our parallel implementation of k-means on SW26010 can sustain a double-precision performance of over 348.1 Gflops,which is 46.9% of the peak performance and 84%of the theoretical performance upper bound on a single core group,and can achieve a nearly ideal scalability to the whole SW26010 processor of four core groups.Performance comparisons with the previous state-of-the-art on both CPU and GPU are also provided to show the superiority of our optimized k-means kernel.

Towards Efficient Short-Range Pair Interaction on Sunway Many-Core Architecture

The short-range pair interaction consumes most of the CPU time in molecular dynamics(MD)simulations.The inherent computation sparsity makes it challenging to achieve high-performance kernel on the emerging many-core architecture.In this paper,we present a highly efficient short-range force kernel on the Sunway,a novel many-core architecture with many unique features.The parallel efficiency of this algorithm on the Sunway many-core processor is strongly limited by the poor data locality and write conflicts.To enhance the data locality,we adopt a super cluster based neighbor list with an appropriate granularity that fits in the local memory of computing cores.In the absence of a low overhead locking mechanism,using data-privatization force array is a more feasible method to avoid write conflicts,but results in the large overhead of data reduction.We adopt a dual-slice partitioning scheme for both hardware resources and computing tasks,which utilizes the on-chip data communication to reduce data reduction overhead and provide load balancing.Moreover,we exploit the single instruction multiple data(SIMD)parallelism and perform instruction reordering of the force kernel on this many-core processor.The experimental results show that the optimized force kernel obtains a performance speedup of 226x compared with the reference implementation and achieves 20%of peak flop rate on the Sunway many-core processor.

Memory Access Optimization of Molecular Dynamics Simulation Software Crystal-MD on Sunway Taihu Light

The radiation damage effect of key structural materials is one of the main research subjects of the numerical reactor.From the perspective of experimental safety and feasibility,Molecular Dynamics(MD)in the materials field is an ideal method for simulating the radiation damage of structural materials.The Crystal-MD represents a massive parallel MD simulation software based on the key material characteristics of reactors.Compared with the Large-scale Atomic/Molecurlar Massively Parallel Simulator(LAMMPS)and ITAP Molecular Dynamics(IMD)software,the Crystal-MD reduces the memory required for software operation to a certain extent,but it is very time-consuming.Moreover,the calculation results of the Crystal-MD have large deviations,and there are also some problems,such as memory limitation and frequent communication during its migration and optimization.In this paper,in order to solve the above problems,the memory access mode of the Crystal-MD software is studied.Based on the memory access mode,a memory access optimization strategy is proposed for a unique architecture of China’s supercomputer Sunway Taihu Light.The proposed optimization strategy is verified by the experiments,and experimental results show that the running speed of the Crystal-MD is increased significantly by using the proposed optimization strategy.

Parallel Region Reconstruction Technique for Sunway High-Performance Multi-core Processors

The leading way to achieve thread-level parallelism on the Sunwayhigh-performance multicore processors is to use OpenMP programming techniques.In order to address the problem of low parallel efficiency caused by highthread group control overhead in the compilation of Sunway OpenMP programs,this paper proposes the parallel region reconstruction technique. The parallelregion reconstruction technique expands the parallel scope of parallel regionsin OpenMP programs by parallel region merging and parallel region extending.Moreover, it reduces the number of parallel regions in OpenMP programs,decreases the overhead of frequent creation and convergence of thread groups,and converts standard fork-join model OpenMP programs to higher performanceSPMD modelOpenMP programs. On the Sunway 1621 server computer, NPB3.3-OMP and SPEC OMP2012 achieved 8.9% and 7.9% running efficiency improvementrespectively through parallel region reconstruction technique. As a result,the parallel region reconstruction technique is feasible and effective. It providestechnical support to fully exploit the multi-core parallelism advantage of Sunway’shigh-performance processors.