Deep neural networks are often over-parameterized, resulting in prohibitive storage and computational costs. A fundamental question is whether a complex network can be re-expressed in terms of a compact set of basis functions without sacrificing accuracy. Motivated by this perspective, we aim to approximate a dense model by decomposing it into a small number of lightweight components that capture the essential functional structure of the network. To this end, we propose a series expansion framework that rewrites a neural network as a linear combination of low-bit basis models. Within the post-training quantization setting, the full-precision model is expanded hierarchically at the tensor, layer, and model levels into a structured set of basis functions. We theoretically prove that this expansion converges exponentially to the original model. Furthermore, we design AbelianAdd and AbelianMul operations between isomorphic basis models, endowing the expansion with an Abelian group structure that naturally supports commutative and parallel computation. Experimental results across diverse architectures show that our series expansion method leverages a set of ultra-low-bit basis functions, not only preserving full-precision performance without the need for calibration data or fine-tuning, but also featuring a parallel-friendly design that enables efficient and scalable deployment.

AI-driven methods have demonstrated considerable success in tackling the central challenge of accurately solving the Schrödinger equation for complex many-body systems. Among neural network quantum state (NNQS) approaches, the NNQS-SCI (Selected Configuration Interaction) method stands out as a state-of-the-art technique, recognized for its high accuracy and scalability. However, its application to larger systems is severely constrained by a hybrid CPU-GPU architecture. Specifically, centralized CPU-based global de-duplication creates a severe scalability barrier due to communication bottlenecks, while host-resident coupled-configuration generation induces prohibitive computational overheads. We introduce QiankunNet-cuSCI, a fully GPU-accelerated SCI framework designed to overcome these bottlenecks. It first integrates a distributed, load-balanced global de-duplication algorithm to minimize redundancy and communication overhead at scale. To address compute limitations, it employs specialized, fine-grained CUDA kernels for exact coupled configuration generation. Finally, to break the single-GPU memory barrier exposed by this full acceleration, it incorporates a GPU memory-centric runtime featuring GPU-side pooling, streaming mini-batches, and overlapped offloading. This design enables much larger configuration spaces and shifts the bottleneck from host-side limitations back to on-device inference. Our evaluation demonstrates that our work fundamentally expands the scale of solvable problems. On an NVIDIA A100 cluster with 64 GPUs, our work achieves up to 2.32 × end-to-end speedup over the highly-optimized NNQS-SCI baseline while preserving the same chemical accuracy. Furthermore, it demonstrates excellent distributed performance, maintaining over 90% parallel efficiency in strong scaling tests.

Redundancy elimination is a key optimization direction, and loop nests are the main optimization target in modern compilers. Previous work on redundancy elimination of array computations in loop nests either targets specific computation patterns or fails to recognize redundancies with complex structures. This paper proposes RACE (Redundant Array Computation Elimination), a hash-based technique that utilizes a novel two-level scheme to identify the data reuse between array references and the computation redundancies between expressions, enabling hierarchical redundancy detection beyond pattern-specific methods. It traverses the expression trees in loop nests to detect redundancies hierarchically in linear time and generates efficient code with optimized auxiliary arrays that store redundant computation results. Furthermore, RACE supports the expression reassociation with various aggressive strategies to improve the redundancy opportunities. Experimental results demonstrate the effectiveness of RACE.

Direction optimization determines whether to use Sparse Matrix-Sparse Vector Multiplication (SpMSpV) or Sparse Matrix-Dense Vector Multiplication (SpMV) based on the input vector's sparsity at each iteration of Breadth-First Search (BFS), aiming to achieve the fastest graph traversal. Although prior work on direction optimization has achieved state-of-the-art performance on either CPUs or GPUs, it has not fully leveraged the capabilities of modern heterogeneous platforms. This is because SpMSpV/SpMV execution times on GPUs do not consistently outperform those on CPUs, particularly for SpMSpV. In response, this paper introducesCGA, a machine learning-based adaptive framework for BFS that optimally selects betweenCPU andGPU kernels, effectivelyAdapting to diverse real-world graphs, vectors, and computing platforms. Our contributions include a novel set of bucket-based SpMSpV algorithms that significantly enhance kernel performance inhigh-sparsity scenarios, along with a low-overhead decision tree model and reduced CPU-GPU data transfers. Experimental results show that our framework outperforms previous state-of-the-art methods, achieving up to a 4.91x speedup over CPU-only baseline and 3.27x speedup over GPU-only baseline.

While Tensor Core Units (TCUs) excel in AI tasks, their application to HPC algorithms like stencil computations faces significant challenges due to sparsity, which leads to underutilization and exacerbates memory-bound limitations. This paper introduces FlashFFTStencil1, a memory-efficient stencil computing system designed to bridge FFT to fully-dense stencil computations on TCUs. Aimed at bound shifting, FlashFFTStencil comprises three key techniques: Kernel Tailoring on HBM fuses distinct kernels to enhance parallelism while reducing memory transfer and footprint; Architecture Aligning on SMEM restructures FFT-based stencil computations into dense matrix multiplications tailored for shared memory architecture; Computation Streamlining on TCU optimizes TCU utilization and thread parallelism by minimizing pipeline stalls and maximizing register reuse. Notably, a distinctive extension is FlashFFTStencil's ability to enable theoretically unrestricted temporal fusion by FFT. Results show that FlashFFTStencil achieves effective sparsity-free bound shifting, with an average speedup of 2.57x over the state-of-the-art. FlashFFTStencil pioneers a new era in unifying computational patterns within the HPC landscape and bridges them with cutting-edge AI-driven hardware innovations like TCUs.

Stencil computation plays a pivotal role in numerous scientific and engineering applications. Previous studies have extensively investigated vectorization techniques to enhance in-core parallelism; however, the performance bottleneck caused by data alignment conflicts (DAC) has not been effectively resolved in all dimensions. This paper proposes Jigsaw, a conflict-free vectorization method to reduce DAC across all dimensions by tessellating swizzled finest-grained lanes. Jigsaw comprises three key components: Lane-based Butterfly Vectorization, SVD-based Dimension Flattening, and Iteration-based Temporal Merging. These components effectively address DAC across spatial and temporal dimensions. Experimental results on different machines demonstrate that Jigsaw could achieve a significant improvement compared to the state-of-the-art techniques, with an average speedup of 2.31x on various stencil kernels.

Scientific computing remains fundamentally misaligned with the execution paradigm of modern AI accelerators, which rely on structured, low-precision matrix operations for performance and scalability. Quantum chemistry exemplifies this gap through three core scalability limits: irregular computational patterns, fragmented hardware utilization, and limited scientific reach.

Neural Network Quantum States (NNQS) offer a powerful variational Monte Carlo (VMC) approach for quantum many-body problems, balancing polynomial scaling with high expressive power. However, scaling NNQS to large chemical systems faces challenges in preserving accuracy with exact energy and managing vast configurations efficiently. In this work, we introduce NNQS-SCI, a high-performance Selected Configuration Interaction (SCI) based NNQS method designed to overcome these limitations. NNQS-SCI employs highly parallelized Slater-Condon rules for fast local energy evaluations, avoiding accuracy loss, while its adaptive SCI engine dynamically manages billions of configurations without space explosion or arbitrary cutoffs that plague other NNQS-CI approaches. Optimized for extreme scalability via multi-level parallelism and memory compression, NNQS-SCI successfully simulates systems up to 152 spin orbitals, tackling Hilbert space dimensions exceeding 1014 and demonstrating significant advances in scale and efficiency. NNQS-SCI thus provides a robust and scalable path towards high-accuracy quantum chemistry on high-performance computing platforms.

Sparse Tensor Cores offer exceptional performance gains for AI workloads by exploiting structured 2:4 sparsity. However, their potential remains untapped for core scientific workloads such as stencil computations, which exhibit irregular sparsity patterns.

The efficiency of Sparse Matrix-Sparse Vector Multiplication (SpM-SpV) is critically important in fields such as machine learning and graph analytics. In certain algorithms, masked SpMSpV computes only a subset of the result entries. Despite its significance, this selective computation poses unique challenges, and existing algorithms often struggle to exploit the sparsity of the input and the mask vectors concurrently. To boost the efficiency of masked SpMSpV on shared memory architectures, we introduce a hybrid adaptive masked SpMSpV algorithm (HAM-SpMSpV) designed to select the efficient kernel automatically based on input features. This approach builds upon the foundation of a conventional algorithm, incorporating two novel masked SpMSpVs: the pre-bucketing masked SPA-based algorithm and the pre-masking bucketed hash-based algorithm. The newly proposed algorithms significantly expedite computation, especially in scenarios with high sparsity in input vectors and masks. Our evaluation involved extensive testing across a diverse range of real-world graphs, utilizing various sparsity of input vectors and masks. This rigorous testing confirmed that our approach notably outperforms existing solutions. Specifically, it achieves a speedup of up to 1.96 times compared to SuiteSparse:GraphBLAS and a remarkable 6.28 times relative to MKL Graph, demonstrating significant advancements in SpMSpV efficiency.

Matrix computation units have been equipped in current architectures to accelerate AI and high performance computing applications. The matrix multiplication and vector outer product are two basic instruction types. The latter one is lighter since the inputs are vectors. Thus it provides more opportunities to develop flexible algorithms for problems other than dense linear algebra computing and more possibilities to optimize the implementation.

We develop a high-performance simulator for variational quantum eigensolver (VQE), the major innovations include: (1) A differentiable matrix product state (MPS) based VQE simulator that seamlessly integrates MPS into the automatic differentiation framework, which overcomes the exponential memory growth of state-vector simulator and can efficiently calculate gradients with a cost independent of the number of parameters; (2) A dynamic scheme to distribute the gradient calculations to achieve good load balance; (3) A parallel adaptive VQE which integrates our differentiable MPS simulator to further enhance the simulation performance; (4) Study of real chemical systems with convergence to chemical accuracy using our simulator, achieving nearly linearly strong and weak scaling for chemical systems with up to 100 qubits. Our simulator provides an ideal test ground for VQE and paves the way of benchmarking large-scale VQE experiments on near-term quantum computers.

Sparse matrix-vector multiplication (SpMV) is a widely used computational kernel for many applications. The performance of existing vectorization-oriented and locality-optimized SpMV works is limited by increasing additional memory accesses to the output vector or using expensive gather operations. To address these issues, we present the Vectorized Non-Empty Column (VNEC), a novel SpMV storage format aiming to optimize locality and vectorization while alleviating the existing limitations. The VNEC chunks the sparse matrix by rows and removes the empty columns from each row block to improve input vector locality and reduce extra output vector memory access. It can also relieve the cost of expensive gather operations by padding zeros and employing less costly vector load instruction. Specifically, we design two variants of VNEC for different non-zero distributions and propose an effective heuristic selection model by introducing the Intra-Row Density (IRD) to evaluate which variant is suitable for optimizing a given matrix. Experimental results show that in a multicore environment, VNEC achieves up to 6.94× speedup (2.10× on average) against the standard MKL SpMV routine on the x86 CPU and up to 5.92× speedup (1.73× on average) over ArmPL on the ARM CPU. We emphasize that the VNEC format is practical for real-world iterative applications because of its low preprocessing overhead for format conversion.

Fast Fourier transform (FFT) is widely used in scientific and engineering computation. Recently developed matrix computation units for AI and high-performance computing provide new optimization opportunities for the FFT algorithm. Compared to dedicated matrix multiplication architectures like Intel AMXs, ARM’s Scalable Matrix Extension (SME) provides more flexible outer product instructions to construct matrix multiplications in software. To leverage ARM SME’s matrix multiplication capabilities, this paper proposes a novel optimized outer product pattern for the Cooley-Tukey FFT algorithm and presents OpenFFT-SME, the first FFT library for ARM SME based on this pattern. This pattern can reduce the number of outer product operations and memory accesses to the DFT matrix by exploiting the symmetric and periodic properties of twiddle factors in the DFT matrix. To further boost performance, OpenFFT-SME incorporates software pipelining to enhance execution pipelines in the assembly code kernels. Meanwhile, a butterfly network more suitable for this pattern is designed and integrated. Experiments demonstrate that OpenFFT-SME outperforms vectorization methods on ARM SME CPUs, achieving 3.60x (power of two) and 4.14x speedups (non-power of two) in double-precision compared to FFTW, 2.47x (power of two) and 3.21x (non-power of two) speedups in double-precision compared to FFTE, and speedups of 4.38x (power of two) and 7.02x (non-power of two) in single-precision compared to FFTW. Furthermore, we compare the advantages and disadvantages of our implementation against vectorization methods and analyze its performance characteristics through additional experiments.

Tensor Core Unit (TCU) is increasingly integrated into modern high-performance processors to enhance matrix multiplication performance. However, constrained to its over-specification, its potential for improving other critical scientific operations like stencil computations remains untapped.

Raman spectroscopy offers invaluable insights into the chemical composition and structural characteristics of various materials, making it a powerful tool for structural analysis. However, accurate quantum mechanical simulations of Raman spectra for large systems, such as biological materials, have been limited due to immense computational costs and technical challenges. In this study, we developed efficient algorithms and optimized implementations on heterogeneous computing architectures to enable fast and highly scalable ab initio simulations of Raman spectra for large-scale biological systems with up to 100 million atoms. Our simulations have achieved nearly linear strong and weak scaling on two cutting-edge high-performance computing systems, with peak FP64 performances reaching 400 PFLOPS on 96,000 nodes of new Sunway supercomputer and 85 PFLOPS on 6,000 node of ORISE supercomputer. These advances provide promising prospects for extending quantum mechanical simulations to biological systems.

Stencil computations play a pivotal role in numerous scientific and industrial applications, yet their efficient execution on specialized hardware accelerators like Tensor Core Units (TCUs) remains a challenge. This paper introduces LoRAStencil1, a novel stencil computing system designed to mitigate memory access redundancies on TCUs through low-rank adaptation. We first identify a nuanced form of this redundancy, dimension residue, specific to TCUs. Then LoRAStencil leverages orchestrated mathematical transformations to decompose stencil weight matrices into smaller rank-1 matrices, facilitating efficient data gathering along residual dimensions. It comprises three key components: memory-efficient Residual Dimension Gathering to facilitate more data reuse, compute-saving Pyramidal Matrix Adaptation to exploit the inherent low-rank characteristics, and performance-boosting Butterfly Vector Swapping to circumvent all data shuffles. Comprehensive evaluations demonstrate that LoRAStencil address dimension residues effectively, which outperforms state-of-the-arts with up to a 2.16x speedup, offering promising advancements for efficient tensorized stencil computation on TCUs by Low-Rank Adaptation.

The matrix multiplication algorithm is a fundamental numerical technique in linear algebra and plays a crucial role in many scientific computing applications. Despite the high performance of mainstream basic linear algebra libraries for large-scale dense matrix multiplications, they exhibit poor performance when applied to matrix multiplication with irregular input. This paper proposes an input-aware tuning framework that accounts for application scenarios and computer architectures to provide high-performance irregular matrix multiplication on ARMv8 and X86 CPUs. The framework comprises two stages: the install-time stage and the run-time stage. The install-time stage utilizes our proposed computational template to generate high-performance kernels for general data layout and SIMD-friendly data layout. The run-time stage utilizes a tiling algorithm suitable for irregular GEMM to select the optimal kernel and link as an execution plan. Additionally, load-balanced multi-threaded optimization algorithms are defined to exploit the multi-threading capability of modern processors. Experiments demonstrate that the proposed IrGEMM framework can achieve significant performance improvements for irregular GEMM on both ARMv8 and X86 CPUs compared to other mainstream BLAS libraries.

TRSM (Triangular Solve with Matrix) is an algorithm in the BLAS library for efficiently solving systems of linear equations, which is widely used in scientific computing, engineering computing, and machine learning. The traditional TRSM algorithm performs well in solving large-scale converging squareshaped matrices but is inefficient in solving small-scale irregularshaped matrices. In this paper, we propose SATRSM, a Shape-Aware auto-tuning framework that is aware of scale size and irregularity, aiming to improve performance on small-scale irregular-shaped TRSM computations. SA TRSM consists of the install-time stage and the run-time stage. In the install-time stage, we designed five components for generating high-performance kernels. In the run-time stage, we designed the Shape-Aware tiling algorithm and Plan Generator for generating an efficient execution plan. The experimental results show that the average performance of SA TRSM in this paper improves by 29.4,16.1,24.6 times, and 7.8 times on double-precision real, single-precision real, doubleprecision complex, and single-precision complex in turn, relative to the algorithms in MKL.

As the size of datasets and neural network models increases, automatic parallelization methods for models have become a research hotspot in recent years. The existing auto-parallel methods based on machine learning or graph algorithms still have issues with search efficiency and applicability. This paper proposes an automatic parallel method based on a dual-population genetic algorithm, TGA, which transforms model partitioning and placement into an integer linear programming problem and constructs a cost model to evaluate the solution. The solution space is built using the neural network’s dataflow graph and device cluster’s topology, and the dual-population genetic algorithm is used to search for the optimal model parallel strategy. Experiments with various models show that the proposed method can improve single-step execution time by up to 42% compared to the Baechi method and up to 37.7% compared to the Hierarchical method.

The sophisticated hierarchy and shared characteristics of cache in multicore CPU architectures bring challenges to the performance improvement of fundamental algorithms, especially in implementing and optimizing 3D FFT. 3D FFT is a memory-bounded algorithm that contains many highly discretized memory accesses. With the working set scaling, the data locality becomes poor, which is prone to cause serious memory access overhead, especially for high-dimensional data transposition. This paper proposes a 3D FFT optimization framework named OpenFFT. This framework optimizes the memory access of 3D FFT by the following methods, including 1) A novel tiling algorithm, Z-OpenFFT, based on the column-order algorithm for high-dimensional vectorization to improve data locality and eliminate transposition; 2) An efficient search algorithm Section-cache-aware algorithm to optimize the memory access of butterfly network of 1D FFT; 3) A multi-thread allocation model by analyzing the characteristics of cache hierarchy and task size to allocate threads adaptively. Experiments demonstrate that OpenFFT could obtain a more competitive performance than the best configuration of FFTW and ARMPL on ARM CPUs.

Gradient Boosting Decision Tree (GBDT) is a costly machine learning model. Current parallel GBDT algorithms generally follow a synchronous parallel design: Fork-join parallel manner, like MapReduce. Fork-join parallel manner needs considerable time. Thus, we propose whether synchronization is necessary for GBDT training and is asynchronous training manner efficient. In this paper, we solve the above problem by offering an asynchronous algorithm. We try to build a stochastic optimization problem by sampling, which shares the same output with original GBDT training problem and use asynchronous parallel SGD manner to train Gradient step GBDT. We name our algorithm as asynch-SGBDT. Our theoretical and experimental results indicate that compared with the serial GBDT training process, when the datasets’ high sample diversity is high and using Gradient step training GBDT, asynch-SGBDT does not slow down convergence speed on the epoch, and the sample diversity of current high-dimensional sparse datasets is usually high. We conduct experiments on a 32-node cluster using four different datasets. The results show that with LightGBM using a single worker as the baseline, LightGBM (the state-of-the-art synchronous parallel algorithm implement) on 32 workers achieves 5x-7x speedup, while our asynch-SGBDT on 32 workers increases the speedup to 11x-15x.

This paper proposes an algorithm-specific instruction (ASI)-based fast Fourier transform (FFT) code generation framework, named FFTASI, to generate unified architecture independent butterfly kernels that can be transformed into architecture-dependent kernels by establishing the mapping between ASIs and architecture-specific instructions for various hardware platforms. FFTASI strikes a good balance between performance and productivity on CPUs.

Abstract With the widespread use of Internet of things(IoT) devices, it generates an enormous volume of data, and it is a challenge to mine the IoT data value while ensuring security and privacy. Federated learning is a decentralized approach for training data located on edge devices, such as mobile phones and IoT devices, while keeping privacy, efficiency, and security. However, the Non-IID (non-independent and identically distributed) data, always greatly impacts the performance of the global model. In this paper, we propose a FedDynamic algorithm to solve the statistical challenge of federated learning caused by Non-IID. As Non-IID data can lead to significant differences in model parameters between edge devices, we set different weights for different devices during model aggregation to get a high-performance global model. We analyze and exact key indices (local model accuracy, local data quality, and model difference between local models and the global model), which can reflect the quality of the model, and calculate the aggregation weight for edge devices based on the key indices. Furthermore, we dynamically adjust aggregation weight based on accuracy’s variety to solve weight staleness during the training process. Experiments on the MNIST, FMNIST, EMNIST, CINIC-10 and CIFAR-10 datasets show that the FedDynamic algorithm has better accuracy and convergence performance, compared to the FedAvg, FedProx and Scaffold algorithms.

The atmospheric general circulation model (AGCM) has been an important research tool in the study of climate change for decades. As the demand for high-resolution simulation is becoming urgent, the scalability and simulation efficiency is faced with great challenges, especially for the latitude-longitude mesh-based models. In this paper, we propose a highly scalable 3-D atmospheric general circulation model based on leap-format, namely AGCM-3DLF. First, it utilizes a 3-D decomposition method allowing for parallelism release in all three physical dimensions. Then the leap-format difference computation scheme is adopted to maintain computational stability in grid updating and avoid additional filtering at the high latitudes. A novel shifting window communication algorithm is designed for parallelization of the unified model. Furthermore, a series of optimizations are conducted to improve the effectiveness of large-scale simulations. Experiment results in different platforms demonstrate good efficiency and scalability of the model. AGCM-3DLF scales up to the entire CAS-Xiandao1 supercomputer (196,608 CPU cores), attaining the speed of 11.1 simulation-year-per-day (SYPD) at a high resolution of 25KM. In addition, simulations conducted on the Sunway TaihuLight supercomputer exhibit a 1.06 million cores scalability with 36.1% parallel efficiency.

The atomic kinetic Monte Carlo method plays an important role in material simulations by connecting the microscale mechanism with macroscale evolution. However, the long-time simulation of multi-component materials is highly challenging because it demands significant computing resources. With the advent of exascale computing, ultra-high computing power can enable kinetic Monte Carlo (KMC) simulations. In this paper, we deeply optimize OpenKMC for the new-generation Sunway supercomputer. This includes optimizing the memory access for the SW39000 architecture, eliminating various redundant computations at growing scales, and proposing a communication strategy for heterogeneous platforms. In addition, we expanded OpenKMC's simulation for multi-component alloys. Finally, the acceleration framework can produces a$37\times$performance enhancement on the Sunway platform. Furthermore, when powered by 10 million cores, our program can perform trillion-atom simulations of complex multi-component alloys with 85% parallel efficiency.

Recently the mainstream basic linear algebra libraries have delivered high performance on large scale General Matrix Multiplication(GEMM) and Triangular System Solve(TRSM). However, these libraries are still insufficient to provide sustained performance for batch operations on large groups of fixed-size small matrices on specific architectures, which are extensively used in various scientific computing applications. In this paper, we propose IATF, an input-aware tuning framework for optimizing large group of fixed-size small GEMM and TRSM to boost near-optimal performance on ARMv8 architecture. The IATF contains two stages: install-time stage and run-time stage. In the install-time stage, based on SIMD-friendly data layout, we propose computing kernel templates for high-performance GEMM and TRSM, analyze optimal kernel sizes to increase computational instruction ratio, and design kernel optimization strategies to improve kernel execution efficiency. Furthermore, an optimized data packing strategy is also presented for computing kernels to minimize the cost of memory accessing overhead. In the run-time stage, we present an input-aware tuning method to generate an efficient execution plan for large group of fixed-size small GEMM and TRSM, according to the input matrix properties. The experimental results show that IATF could achieve significant performance improvements in GEMM and TRSM compared with other mainstream BLAS libraries.

Stencil computation is one of the most important kernels in various scientific and engineering applications. A variety of work has focused on vectorization and tiling techniques, aiming at exploiting the in-core data parallelism and data locality respectively. In this paper, the downsides of existing vectorization schemes are analyzed. Briefly, they either incur data alignment conflicts or hurt the data locality when integrated with tiling. Then we propose a novel transpose layout to preserve the data locality for tiling and reduce the data reorganization overhead for vectorization simultaneously. To further improve the data reuse at the register level, a time loop unroll-and-jam strategy is designed to perform multistep stencil computation along the time dimension. Experimental results on the AVX2 and AVX-S12 CPUs show that our approach obtains a competitive performance with the classic vectorization methods (Auto Vectorization and Data Reorganization), state-of-the-art compilers (Pluto and SDSL), and highly-optimized work (DLT and Tessellation).

Quantum computational chemistry (QCC) is the use of quantum computers to solve problems in computational quantum chemistry. We develop a high performance variational quantum eigensolver (VQE) simulator for simulating quantum computational chemistry problems on a new Sunway supercomputer. The major innovations include: (1) a Matrix Product State (MPS) based VQE simulator to reduce the amount of memory needed and increase the simulation efficiency; (2) a combination of the Density Matrix Embedding Theory with the MPS-based VQE simulator to further extend the simulation range; (3) A three-level parallelization scheme to scale up to 20 million cores; (4) Usage of the Julia script language as the main programming language, which both makes the programming easier and enables cutting edge performance as native C or Fortran; (5) Study of real chemistry systems based on the VQE simulator, achieving nearly linearly strong and weak scaling. Our simulation demonstrates the power of VQE for large quantum chemistry systems, thus paves the way for large-scale VQE experiments on near-term quantum computers.

As the data size in Machine Learning fields grows exponentially, it is inevitable to accelerate the computation by utilizing the ever-growing large number of available cores provided by high-performance computing hardware. However, existing parallel methods for clustering or regression often suffer from problems of low accuracy, slow convergence, and complex hyperparameter-tuning. Furthermore, the parallel efficiency is usually difficult to improve while striking a balance between preserving model properties and partitioning computing workloads on distributed systems. In this paper, we propose a novel and simple data structure capturing the most important information among data samples. It has several advantageous properties supporting a hierarchical clustering strategy that contains well-defined metrics for determining optimal hierarchy, balanced partition for maintaining the clustering property, and efficient parallelization for accelerating computation phases. Then we combine the clustering with regression techniques as a parallel library and utilize a hybrid structure of data and model parallelism to make predictions. Experiments illustrate that our library obtains remarkable performance on convergence, accuracy, and scalability.

The Poisson solver for the calculation of the electrostatic potential is an essential primitive in quantum mechanics calculations. In this article, we adopt the Ewald method and propose a highly-optimized and scalable framework for Poisson solver, MMEwald, on the new generation Sunway supercomputer, capable of utilizing the collection of 390-core accelerators it uses. The MMEwald is based on a grid adapted cut-plane approach to partition the points into batches and distribute the batch to the processors. Furthermore, we propose a set of architecture-specific optimizations to efficiently utilize the memory bandwidth and computation capacity of the supercomputer. Experimental results demonstrate the efficiency of the MMEwald in providing strong and weak scaling performance.

GEMM with the small size of input matrices is becoming widely used in many fields like HPC and machine learning. Although many famous BLAS libraries already supported small GEMM, they cannot achieve near-optimal performance. This is because the costs of pack operations are high and frequent boundary processing cannot be neglected. This paper proposes an input-aware adaptive tuning framework(IAAT) for small GEMM to overcome the performance bottlenecks in state-of-the-art implementations. IAAT consists of two stages, the install-time stage and the run-time stage. In the run-time stage, IAAT tiles matrices into blocks to alleviate boundary processing. This stage utilizes an input-aware adaptive tile algorithm and plays the role of runtime tuning. In the install-time stage, IAAT auto-generates hundreds of kernels of different sizes to remove pack operations. Finally, IAAT finishes the computation of small GEMM by invoking different kernels, which corresponds to the size of blocks. The experimental results show that IAAT gains better performance than other BLAS libraries on ARMv8 platform.

Stencil computation is one of the most important kernels in various scientific and engineering applications. A variety of work has focused on vectorization techniques, aiming at exploiting the in-core data parallelism. However, they either incur spatial data conflicts or hurt the data locality when integrated with tiling. In this paper, a novel spatial computation folding is devised to reduce the data reorganization overhead for vectorization and preserve the data locality for tiling in the data space simultaneously. We then propose an approach of temporal computation folding enhanced with shifts reusing, tessellate tiling, and semi-automatic code generation. It aims to further reduce the redundancy of arithmetic calculations and exploit the register reuse along the time dimension. Experimental results on the AVX2 and AVX-512 CPUs show that our approach obtains significant performance improvements compared with state-of-the-art techniques.

The atomic kinetic Monte Carlo method plays an important role in multi-scale physical simulations because it bridges the micro and macro worlds. However, its accuracy is limited by empirical potentials. We therefore propose herein a triple-encoding algorithm and vacancy-cache mechanism to efficiently integrate ab initio neural network potentials (NNPs) with AKMC and implement them in our TensorKMC codes. We port our program to SW26010-pro and innovate a fast feature operator and a big fusion operator for the NNPs for fully utilizing the powerful heterogeneous computing units of the new-generation Sunway supercomputer. We further optimize memory usage. With these improvements, TensorKMC can simulate up to 54 trillions of atoms and achieve excellent strong and weak scaling performance up to 27,456,000 cores.

Raman spectroscopy provides chemical and compositional information that can serve as a structural fingerprint for various materials. Therefore, simulations of Raman spectra, including both quantum perturbation analyses and ground-state calculations are of significant interest. However, highly accurate full quantum mechanical (QM) simulations of Raman spectra have previously been confined to small systems. For large systems such as biological materials, the computational cost of full QM simulations is extremely high, and their extension to such systems remains challenging. In the work described here, by employing robust new algorithms and advances in implementation for the many-core architectures, we are able to perform fast, accurate, and massively parallel full ab initio simulations of the Raman spectra of biological systems with excellent strong and weak scaling, thereby providing a starting point for applying QM approaches to structural studies of such systems.

Raman spectroscopy provides chemical and compositional information that can serve as a structural fingerprint for various materials. Therefore, simulations of Raman spectra, including both quantum perturbation analyses and ground-state calculations, are of significant interest. However, highly accurate full quantum mechanical (QM) simulations of Raman spectra have previously been confined to small systems. For large systems such as biological materials, full QM simulations have an extremely high computational cost and remain challenging. In this work, robust new algorithms and advanced implementations on many-core architectures are employed to enable fast, accurate, and massively parallel full ab initio simulations of the Raman spectra of realistic biological systems containing up to 3006 atoms, with excellent strong and weak scaling. Up to a performance of 468.5 PFLOP/s in double-precision and 813.7 PLOPS/s in mixed-half precision is achieved on the new-generation Sunway high-performance computing system, suggesting the potential for new applications of the QM approach to biological systems.

Stencil computations represent a very common class of nested loops in scientific and engineering applications. Exploiting vector units in modern CPUs is crucial to achieving peak performance. Previous vectorization approaches often consider the data space, in particular the innermost unit-strided loop. It leads to the well-known data alignment conflict problem that vector loads are overlapped due to the data sharing between continuous stencil computations. This paper proposes a novel temporal vectorization scheme for stencils. It vectorizes the stencil computation in the iteration space and assembles points with different time coordinates in one vector. The temporal vectorization leads to a small fixed number of vector reorganizations that is irrelevant to the vector length, stencil order, and dimension. Furthermore, it is also applicable to Gauss-Seidel stencils, whose vectorization is not well-studied. The effectiveness of the temporal vectorization is demonstrated by various Jacobi and Gauss-Seidel stencils.

As the training dataset size and the model size of machine learning increase rapidly, more computing resources are consumed to speedup the training process. However, the scalability and performance reproducibility of parallel machine learning training, which mainly uses stochastic optimization algorithms, are limited. In this paper, we demonstrate that the sample difference in the dataset plays a prominent role in the scalability of parallel machine learning algorithms. We propose to use statistical properties of dataset to measure sample differences. These properties include the variance of sample features, sample sparsity, sample diversity, and similarity in sampling sequences. We choose four types of parallel training algorithms as our research objects: (1) the asynchronous parallel SGD algorithm (Hogwild! algorithm), (2) the parallel model average SGD algorithm (minibatch SGD algorithm), (3) the decentralization optimization algorithm, and (4) the dual coordinate optimization (DADM algorithm). Our results show that the statistical properties of training datasets determine the scalability upper bound of these parallel training algorithms.

The finite-difference dynamical core based on the equal-interval latitude-longitude mesh has been widely used for numerical simulations of the Atmospheric General Circulation Model (AGCM). Previous work utilizes different filtering schemes to alleviate the instability problem incurred by the unequal physical spacing at different latitudes, but they all incur high communication and computation overhead and become a scaling bottleneck. This paper proposes a new leap-format finite-difference computing scheme. It generalizes the usual finite-difference format with adaptive wider intervals and is able to maintain the computational stability in the grid updating. Therefore, the costly filtering scheme is eliminated. The new scheme is parallelized with a shifting communication method and implemented with fine communication optimizations based on a 3D decomposition. With the proposed leap-format computation scheme, the communication overhead of the AGCM is significantly reduced and good load balance is exhibited. The simulation results verify the correctness of the new leap-format scheme. The new scheme achieves the speed of 16.6 simulation-year-per-day (SYPD) and up to 3.3x speedup over the latest implementation.

This article presents AutoFFT, a template-based code generation framework that can automatically generate high-performance FFT kernels for all natural-number radices. AutoFFT is based on the Cooley-Tukey FFT algorithm, which exploits the symmetric and periodic properties of the DFT matrix, as the outer parallelization framework. Because butterflies are the core operations of the Cooley-Tukey algorithm, we explore additional symmetric and periodic properties of the DFT matrix and formulate multiple optimized calculation templates to further reduce the number of floating-point operations for butterflies of arbitrary natural numbers. To fully exploit hardware resources, we encapsulate a series of optimizations in an assembly template optimizer. Given any DFT problem, AutoFFT automatically generates C FFT kernels using these calculation templates and converts them into efficient assembly kernels using the template optimizer. Through a series of experiments on Arm, Intel, and AMD processors, we show that AutoFFT-generated kernels can outperform those in Fastest Fourier Transform in the West (FFTW), the Arm Performance Libraries (ARMPL), and the Intel Math Kernel Library (MKL).

Stencil computations represent a very common class of nested loops in scientific and engineering applications. The exhaustively studied tiling is one of the most powerful transformation techniques to explore the data locality and parallelism. Existing work often uniformly handles different stencil shapes. This paper first presents a concept called natural block to identify the difference between the star and box stencils. Then we propose anew two-level tessellation scheme for star stencils, where the natural block, as well as its successors can tessellate the spatial space and their extensions along the time dimension are able to form a tessellation of the iteration space. Furthermore, a novel implementation technique called double updating is developed for star stencils specifically to improve the in-core data reuse pattern. Evaluation results are provided that demonstrate the effectiveness of the approach.

Automatic machine learning (automl) is a crucial technology in machine learning. Sequential model-based optimisation algorithms (SMBO) (e.g., SMAC, TPE) are state-of-the-art hyperparameter optimisation methods in automl. However, SMBO does not consider known information, like the best hyperparameters high possibility range and gradients. In this paper, we accelerate the traditional SMBO method and name our method as accSMBO. In accSMBO, we build a gradient-based multikernel Gaussian process with a good generalisation ability and we design meta-acquisition function which encourages that SMBO puts more attention on the best hyperparameters high possibility range. In L2 norm regularised logistic loss function experiments, our method exhibited state-of-the-art performance.

The discrete Fourier transform (DFT) is widely used in scientific and engineering computation. This paper proposes a template-based code generation framework named AutoFFT that can automatically generate high-performance fast Fourier transform (FFT) codes. AutoFFT employs the Cooley-Tukey FFT algorithm, which exploits the symmetric and periodic properties of the DFT matrix as the outer parallelization framework. To further reduce the number of floating-point operations of butterflies, we explore more symmetric and periodic properties of the DFT matrix and formulate two optimized calculation templates for prime and power-of-two radices. To fully exploit hardware resources, we encapsulate a series of optimizations in an assembly template optimizer. Given any DFT problem, AutoFFT automatically generates C FFT kernels using these two templates and transfers them to efficient assembly codes using the template optimizer. Experiments show that AutoFFT outperforms FFTW, ARMPL, and Intel MKL on average across all FFT types on ARMv8 and Intel x86-64 processors.

With more attention attached to nuclear energy, the formation mechanism of the solute clusters precipitation within complex alloys becomes intriguing research in the embrittlement of nuclear reactor pressure vessel (RPV) steels. Such phenomenon can be simulated with atomic kinetic Monte Carlo (AKMC) software, which evaluates the interactions of solute atoms with point defects in metal alloys. In this paper, we propose OpenKMC to accelerate large-scale KMC simulations on Sunway many-core architecture. To overcome the constraints caused by complex many-core architecture, we employ six levels of optimization in OpenKMC: (1) a new efficient potential computation model; (2) a group reaction strategy for fast event selection; (3) a software cache strategy; (4) combined communication optimizations; (5) a Transcription-Translation-Transmission algorithm for many-core optimization; (6) vectorization acceleration. Experiments illustrate that our OpenKMC has high accuracy and good scalability of applying hundred-billion-atom simulation over 5.2 million cores with a performance of over 80.1% parallel efficiency.

In many areas of program and system analysis and optimization, locality is a common concept and has been defined and measured in many ways. This article aims to formally establish relations between these previously disparate types of locality. It categorizes locality definitions in three groups and shows whether and how they can be interconverted. For the footprint, a recent metric, it gives a new measurement algorithm that is asymptotically more time/space efficient than previous approaches. Using the conversion relations, the new algorithm derives with the same efficiency different locality metrics developed and used in program analysis, memory management, and cache design.

It is commonly recognized that the dynamical core of the atmospheric model based on latitude-longitude mesh has poor parallel scalability, since it has to perform the costly polar or high-latitude filtering to dump out the unwanted modes. To parallelize the algorithm, only two dimensions can be partitioned even for a 3-dimensional mesh because of the costly filtering, which hinders the scalability of the algorithm. In this paper, we develop a highly scalable finite-difference dynamical core based on the latitude-longitude mesh using a 3D decomposition method, named as AGCM3D. Different from the traditional methods, our method releases the parallelism in all three dimensions, namely latitude, longitude, and level. To replace the costly Fast Fourier Transform (FFT) filtering, we propose a novel adaptive Gaussian filtering scheme, whose filtering strength increases as the latitude increases. Compared with the parallel FFT filtering, the parallel adaptive Gaussian filtering is far more efficient. In addition, we use the techniques of communication avoiding and message aggregation to further reduce the communication overhead. Experiments are conducted on Tianhe-2 supercomputer, and the resolution of the model is set as 0.5°x0.5°(50 km). Results show that our implementation scales up to 32,768 CPU cores in strong scaling and achieves the maximal simulation speed of 15.6 simulation-year-per-day (SYPD).

The limitation of simulation scales leads to a gap between simulation results and physical phenomena. This paper reports our efforts on increasing the scalability of metal material microscopic damage simulation on the Sunway TaihuLight supercomputer. We use a multiscale modeling approach that couples Molecular Dynamics (MD) with Kinetic Monte Carlo (KMC). According to the characteristics of metal materials, we design a dedicated data structure to record the neighbor atoms for MD, which significantly reduces the memory consumption. Data compaction and double buffer are used to reduce the data transfer overhead between the main memory and the local store. We propose an on-demand communication strategy for KMC to remarkably reduce the communication overhead. We simulate 4 * 1012 atoms on 6,656,000 master+slave cores using MD with 85% parallel efficiency. Using the coupled MD-KMC approach, we simulate 3.2 * 1010 atoms in 19.2 days temporal scale on 6,240,000 master+slave cores with runtime of 8.6 hours.

Dynamical core is one of the most time-consuming parts in the global atmospheric general circulation model, which is widely used for the numerical simulation of the dynamic evolution process of global atmosphere. Due to its complicated calculation procedures and the non-uniformity of latitude-longitude mesh, the parallelization suffers from high communication overhead. In this paper, we deduce the operator form of the calculating flow in the dynamical core. Furthermore, it is abstracted out that the stencil and collection alternate action is the basic operation in the dynamic core. Based on the operator form of the calculation flow, we propose the corresponding optimization strategy for each operator. In the end, we develop a communication-avoiding algorithm to reduce communication overhead in the dynamic core. Our experiments show that the communication-avoiding algorithm reduces the total runtime by 54% at most for a 50 km resolution model running 10 years. Especially for communication reduction, the new algorithm achieves 1.4x speedup on average for the collective communication and 3.9x speedup on average for the communication involved in the stencil computation.

Many-core systems with a rapidly increasing number of cores pose a significant challenge to parallel applications to use their complex memory hierarchies efficiently. Many such applications rely on collective communications in performance-critical phases, which become a bottleneck if they are not optimized. We address this issue by proposing cache-oblivious algorithms for MPI_Alltoall, MPI_Allgather, and the MPI neighborhood collectives to exploit the data locality. To implement the cache-oblivious algorithms, we allocate the send and receive buffers on a shared heap and use Morton order to guide the memory copies. Our analysis shows that our algorithm for MPI_Alltoall is asymptotically optimal. We show an extension to our algorithms to minimize the communication distance on NUMA systems while maintaining optimality within each socket. We further demonstrate how the cache-oblivious algorithms can be applied to multi-node machines. Experiments are conducted on different many-core architectures. For MPI_Alltoall, our implementation achieves on average 1.40X speedup over the naive implementation based on shared heap for small and medium block sizes (less than 16 KB) on a Xeon Phi KNC, achieves on average 3.03X speedup over MVAPICH2 on a Xeon E7-8890, and achieves on average 2.23X speedup over MVAPICH2 on a 256-node Xeon E5-2680 cluster for block sizes less than 1 KB.

Scale Invariant Feature Transform (SIFT) is one of the most popular and robust feature extraction algorithms for its invariance to scale, rotation and illumination. It has been widely adopted in many fields, such as video tracking, image stitching, simultaneous localization and mapping (SLAM), structure from motion (SFM) and so on. However, high computational complexity constrains its further application in real-time systems. These systems have to make a tradeoff between accuracy and performance to achieve real-time feature extraction. They adopt other faster algorithms but with less accuracy, like SURF and PCA-SIFT. In order to address this problem, this paper proposes a GPU-accelerated SIFT using CUDA, named HartSift, which realizes high-accuracy and real-time feature extraction by making full use of computing resources of CPU and GPU within a single machine. Experiments show that, on the NIVDIA GTX TITAN Black GPU, HartSift can process an image within 3.14?10.57ms (94.61?318.47fps) according to the size of images. In addition, HartSift is 59.34?75.96 times and 4.01?6.49 times faster than OpenCV-SIFT (a CPU version) and SiftGPU (a GPU version), respectively. In the mean time, HartSift's performance and CudaSIFT's (the fastest GPU version so far) are almost the same, while HartSift's accuracy is much higher than CudaSIFT's.

In the many-core era, the performance of MPI collectives is more dependent on the intra-node communication component. However, the communication algorithms generally inherit from the inter-node version and ignore the cache complexity. We propose cache-oblivious algorithms for MPI all-to-all operations, in which data blocks are copied into the receive buffers in Morton order to exploit data locality. Experimental results on different many-core architectures show that our cache-oblivious implementations significantly outperform the naive implementations based on shared heap and the highly optimized MPI libraries.

Stencil computations represent a very common class of nested loops in scientific and engineering applications. The exhaustively studied tiling is one of the most powerful transformation techniques to explore the data locality and parallelism. Unlike previous work, which mostly blocks the iteration space of a stencil directly, this paper proposes a novel two-level tessellation scheme. A set of blocks are designed to tessellate the spatial space in various ways. The blocks can be processed in parallel without redundant computation. This corresponds to extending them along the time dimension and can form a tessellation of the iteration space. Experimental results show that our code performs up to 12% better than the existing highly concurrent schemes for the 3d27p stencil.

The Workshop on High Performance Data Intensive Computing was held in conjunction with IEEE IPDPS 2012 in Shanghai, China, May 25, 2012. It was chaired by Prof. Song WU, Huazhong University of Science and Technology, China, and Prof. Yong-Jian REN, Hangzhou Dianzi University, China. Prof. Shyamasundar (IEEE Fellow and ACM Fellow) and Prof. Weisong Shi (IEEE Fellow) present two significant and wonderful keynotes in the workshop. Nearly 29 papers were presented in oral sessions. The proceedings have been available through the IEEE digital repository. There is no doubt in the industry and research community that the importance of data intensive computing has been raising and will continue to be the foremost fields of research. This raise brings up many research issues, in forms of capturing and accessing data effectively and quickly, processing it while still achieving high performance and high throughput, and storing it efficiently for future use. Programming for high performance yielding data-intensive computing is an important challenging issue. Expressing data access requirements of applications and designing programming language abstractions to exploit parallelism are at immediate need. Application and domain-specific optimizations are also part of a viable solution in data-intensive computing. While these are a few examples of issues, research in data intensive computing has become quite intense during the last few years yielding strong results. This workshop focuses on the challenges imposed by high performance data intensive applications on distributed systems, and on the different state-of-the-art solutions. It brought together the collaborative and distributed computing community and the data management community in an effort to generate productive conversations on the planning, management, and scheduling of data handling tasks and data storage resources. The four papers of this workshop with the most significant scientific findings and important technical developments have been improved and expanded to the quality of peer-reviewed journal articles and published in this issue. We divided four papers into two groups: (1) innovations in system schedule and security and (2) high performance data intensive computing applications. In recent years, more and more companies outsource their data to the cloud service provider to greatly reduce the cost. However, it also raises underlying security and privacy issues for the significant corporate data. Therefore, a natural way to keep sensitive data confidential against an untrusted cloud service provider is only to store the encrypted data in the cloud. Shan-shan Tu, Shao-zhang Niu, and Hui Li 1 propose a concrete access control scheme constructed over the composite-order bilinear groups and prove its security under the standard model. They also propose a fully fine-grained revocation scheme under the direct revocation model so as to efficiently revoke access rights from users on cloud servers. To optimize the design of job scheduler, Javid Taheri, Albert Y. Zomaya, and Samee U. Khan 2 describe a genetic algorithm (GA)-based optimization technique, called GA-ParFnt, to find the Pareto frontier for optimizing data transfer versus job execution time in grids. New challenges for large-scale data management and sharing have arisen because of the information evolution from massive data to ‘big data’. Zhenyu Liu, Jingyuan Hu, Yang Li, and Yi Huang 3 propose the concept of virtual data spaces and domain scientific data in scientific domain. To build the virtual data spaces, a logical resources model based on ontology is discussed. And the new mapping and evolutionary model of vitriol data spaces is described in a ‘pay-as-you-go’ fashion. Results show that this approach is efficient in scientific data management and suitable for data-intensive application. Parallel semi-implicit method for pressure-linked equations (SIMPLE) algorithm is used to solve the three-dimensional incompressible pipe flow problem. Ji-Lin Zhang, Jun-Feng Yuan, Jian Wan, Jie Mao, Li-Ting Zhu, Li Zhou, Cong-Feng Jiang, Peng Di, and Jue Wang 4 proposed a novel parallel SIMPLE algorithm that uses the alternate tiling technique. The results showed that the parallel SIMPLE algorithm that uses the two-way finite difference stencil algorithm based on alternate tiling has good data locality, performance, and scalability in the Deepcomp7000 cluster computing environment.

The volume, variety, and velocity properties of big data and the valuable information it contains have motivated the investigation of many new parallel data processing systems in addition to the approaches using traditional database management systems (DBMSs). MapReduce pioneered this paradigm change and rapidly became the primary big data processing system for its simplicity, scalability, and fine-grain fault tolerance. However, compared with DBMSs, MapReduce also arouses controversy in processing efficiency, low-level abstraction, and rigid dataflow. Inspired by MapReduce, nowadays the big data systems are blooming. Some of them follow MapReduce's idea, but with more flexible models for general-purpose usage. Some absorb the advantages of DBMSs with higher abstraction. There are also specific systems for certain applications, such as machine learning and stream data processing. To explore new research opportunities and assist users in selecting suitable processing systems for specific applications, this survey paper will give a high-level overview of the existing parallel data processing systems categorized by the data input as batch processing, stream processing, graph processing, and machine learning processing and introduce representative projects in each category. As the pioneer, the original MapReduce system, as well as its active variants and extensions on dataflow, data access, parameter tuning, communication, and energy optimizations will be discussed at first. System benchmarks and open issues for big data processing will also be studied in this survey.

Sparse Matrix-Vector multiplication (SpMV) is a key operation in engineering and scientific computing. Although the previous work has shown impressive progress in optimizing SpMV on many-core architectures, load imbalance and high memory bandwidth remain the critical performance bottlenecks. We present our novel solutions to these problems, for both GPUs and Intel MIC many-core architectures. First, we devise a new SpMV format, called Blocked Compressed Common Coordinate (BCCOO). BCCOO extends the blocked Common Coordinate (COO) by using bit flags to store the row indices to alleviate the bandwidth problem. We further improve this format by partitioning the matrix into vertical slices for better data locality. Then, to address the load imbalance problem, we propose a highly efficient matrix-based segmented sum/scan algorithm for SpMV, which eliminates global synchronization. At last, we introduce an autotuning framework to choose optimization parameters. Experimental results show that our proposed framework has a significant advantage over the existing SpMV libraries. In single precision, our proposed scheme outperforms clSpMV COCKTAIL format by 255% on average on AMD FirePro W8000, and outperforms CUSPARSE V7.0 by 73.7% on average and outperforms CSR5 by 53.6% on average on GeForce Titan X; in double precision, our proposed scheme outperforms CUSPARSE V7.0 by 34.0% on average and outperforms CSR5 by 16.2% on average on Tesla K20, and has equivalent performance compared with CSR5 on Intel MIC.

The successive over-relaxation (SOR) algorithm is an important method to solve the linear equations in the numerical marine forecasting model, but it is not appropriate for parallelism. In this paper, the red-black ordering and the method to avoid cost of communication are used to implement the parallelism of the SOR algorithm and improve the performance of it. The experiments show that the performance of the parallel SOR algorithm with the red-black ordering and communication optimization is high, but the errors between the serial SOR algorithm and the parallel SOR algorithm are bigger and bigger with the increase of computing time steps. Based on the characteristics of the numerical marine forecasting model, a four-step parallel SOR algorithm is designed to solve the error problem.

The recently released MPI-3.0 standard introduced a process-level shared-memory interface which enables processes within the same node to have direct load/store access to each others' memory. Such an interface allows applications to declare data structures that are shared by multiple MPI processes on the node. In this paper, we study the capabilities and performance implications of using MPI-3.0 shared memory, in the context of a five-point stencil computation. Our analysis reveals that the use of MPI-3.0 shared memory has several unforeseen performance implications including disrupting certain compiler optimizations and incorrectly using suboptimal page sizes inside the OS. Based on this analysis, we propose several methodologies for working around these issues and improving communication performance by 40-85% compared to the current MPI-1.0 based approach.

Sharpness is an algorithm used to sharpen images. As the increase of image size, resolution, and the requirements for real-time processing, the performance of sharpness needs to get improved greatly. The independent pixel calculation of sharpness makes a good opportunity to use GPU to largely accelerate the performance. However, to transplant it to GPU, one challenge is that sharpness involves several stages to execute. Each stage has its own characteristics, either with or without data dependency to other stages. Based on those characteristics, this paper proposes a complete solution to implement and optimize sharpness on GPU. Our solution includes five major and effective techniques: Data Transfer Optimization, Kernel Fusion, Vectorization for Data Locality, Border and Reduction Optimization. Experiments show that, compared to a well-optimized CPU version, our GPU solution can reach 10.7~ 69.3 times speedup for different image sizes on an AMD Fire Pro W8000 GPU.

Developing an efficient and highly scalable ray tracer for the Metropolis light transport algorithm is becoming increasingly important as the request for photorealistic images becomes a common trend. Although the Metropolis light transport algorithm has produced some of the most realistic images to date, it usually takes a great amount of time to render an image. The development of an efficient and highly scalable ray tracer for the Metropolis light transport algorithm is hard due in large part to the irregular memory access patterns, the imbalanced workload of light-carrying paths and the complicated mathematical model and complex physical processes. In this paper, we present a highly scalable physically based parallel ray tracer for the Metropolis light transport algorithm. Firstly, we present the idea of snapshot and sub-snapshot, then propose a novel assignment partitioning algorithm for compute nodes and CPU cores since the demand-driven assignment partitioning algorithms don't work. Secondly, we propose a physically based parallel ray racing framework for the Metropolis light transport algorithm, which is based on a master-worker architecture. Finally, we discuss the issue of granularity of the assignment partitioning and some optimization strategies for improving overall performance, then a hybrid scheduling strategy combining a static and dynamic scheduling strategy is described. Experiments show that our physically based ray tracer almost reaches linear speedup by using 26,400 CPU cores on the Tianhe-2 supercomputer. Our ray tracer is more efficient and highly scalable.

SpMV is a key linear algebra algorithm and has been widely used in many important application domains. As a result, numerous attempts have been made to optimize SpMV on GPUs to leverage their massive computational throughput. Although the previous work has shown impressive progress, load imbalance and high memory bandwidth remain the critical performance bottlenecks for SpMV. In this paper, we present our novel solutions to these problems. First, we devise a new SpMV format, called blocked compressed common coordinate (BCCOO), which uses bit flags to store the row indices in a blocked common coordinate (COO) format so as to alleviate the bandwidth problem. We further improve this format by partitioning the matrix into vertical slices to enhance the cache hit rates when accessing the vector to be multiplied. Second, we revisit the segmented scan approach for SpMV to address the load imbalance problem. We propose a highly efficient matrix-based segmented sum/scan for SpMV and further improve it by eliminating global synchronization. Then, we introduce an auto-tuning framework to choose optimization parameters based on the characteristics of input sparse matrices and target hardware platforms. Our experimental results on GTX680 GPUs and GTX480 GPUs show that our proposed framework achieves significant performance improvement over the vendor tuned CUSPARSE V5.0 (up to 229% and 65% on average on GTX680 GPUs, up to 150% and 42% on average on GTX480 GPUs) and some most recently proposed schemes (e.g., up to 195% and 70% on average over clSpMV on GTX680 GPUs, up to 162% and 40% on average over clSpMV on GTX480 GPUs).

In response to the high demand of big data analytics, several programming models on large and distributed cluster systems have been proposed and implemented, such as MapRe-duce, Dryad and Pregel. However, compared with high performance computing areas, the basis and principles of computation and communication behavior of big data analytics is not well studied. In this paper, we review the current big data computational model DOT and DOTA, and propose a more general and practical model p-DOT (p-phases DOT). p-DOT is not a simple extension, but with profound significance: for general aspects, any big data analytics job execution expressed in DOT model or BSP model can be represented by it; for practical aspects, it considers I/O behavior to evaluate performance overhead. Moreover, we provide a cost function implying that the optimal number of machines is near-linear to the square root of input size for a fixed algorithm and workload, and demonstrate the effectiveness of the function through several experiments.

Power-hungry Graphics processing unit (GPU) accelerators are ubiquitous in high performance computing data centers today. GPU virtualization frameworks introduce new opportunities for effective management of GPU resources by decoupling them from application execution. However, power management of GPU-enabled server clusters faces significant challenges. The underlying system infrastructure shows complex power consumption characteristics depending on the placement of GPU workloads across various compute nodes, power-phases and cabinets in a datacenter. GPU resources need to be scheduled dynamically in the face of time-varying resource demand and peak power constraints. We propose and develop a power-aware virtual OpenCL (pVOCL) framework that controls the peak power consumption and improves the energy efficiency of the underlying server system through dynamic consolidation and power-phase topology aware placement of GPU workloads. Experimental results show that pVOCL achieves significant energy savings compared to existing power management techniques for GPU-enabled server clusters, while incurring negligible impact on performance. It drives the system towards energy-efficient configurations by taking an optimal sequence of adaptation actions in a virtualized GPU environment and meanwhile keeps the power consumption below the peak power budget.

Scan (also known as prefix sum) is a very useful primitive for various important parallel algorithms, such as sort, BFS, SpMV, compaction and so on. Current state of the art of GPU based scan implementation consists of three consecutive Reduce-Scan-Scan phases. This approach requires at least two global barriers and 3N (N is the problem size) global memory accesses. In this paper we propose StreamScan, a novel approach to implement scan on GPUs with only one computation phase. The main idea is to restrict synchronization to only adjacent workgroups, and thereby eliminating global barrier synchronization completely. The new approach requires only 2N global memory accesses and just one kernel invocation. On top of this we propose two important op-timizations to further boost performance speedups, namely thread grouping to eliminate unnecessary local barriers, and register optimization to expand the on chip problem size. We designed an auto-tuning framework to search the parameter space automatically to generate highly optimized codes for both AMD and Nvidia GPUs. We implemented our technique with OpenCL. Compared with previous fast scan implementations, experimental results not only show promising performance speedups, but also reveal dramatic different optimization tradeoffs between Nvidia and AMD GPU platforms.

Basic Liner algebra subprograms (BLAS) is a fundamental library in scientific computing. In this paper, we present a template-based optimization framework, AUGEM, which can automatically generate fully optimized assembly code for several dense linear algebra (DLA) kernels, such as GEMM, GEMV, AXPY and DOT, on varying multi-core CPUs without requiring any manual interference from developers. In particular, based on domain-specific knowledge about algorithms of the DLA kernels, we use a collection of parameterized code templates to formulate a number of commonly occurring instruction sequences within the optimized low-level C code of these DLA kernels. Then, our framework uses a specialized low-level C optimizer to identify instruction sequences that match the pre-defined code templates and thereby translates them into extremely efficient SSE/AVX instructions. The DLA kernels generated by our template-based approach surpass the implementations of Intel MKL and AMD ACML BLAS libraries, on both Intel Sandy Bridge and AMD Piledriver processors.

The increasing speed gap between the processor and memory is usually the critical bottleneck in achieving high performance. Hardware caches, programming models, algorithms and data structures have been introduced and proposed to exploit localities on reducing the memory overhead. Some of these new designs share a common load and compute style in which the algorithm first moves all needed data to cache and then performs operations only on the ready data. In this paper, we introduce a locality function to model the reuse ability of an algorithm and propose a corresponding performance model. Then we theoretically analyze how to utilize and design on cache under our model: (1) We present theorems to give the optimal cache partition scheme for the software buffering technique targeting at hiding the memory overhead. (2) We provide methods to decide the optimal multicore design to maximally leverage benefits of both the shared and private caches. (3) We incorporate the memory overhead into the Amdahl's Law to study the speedup limitation on memory bandwidth.

Every mainstream processor vendor provides an optimized BLAS implementation for its CPU, as BLAS is a fundamental math library in scientific computing. The Loongson 3A CPU is a general-purpose 64-bit MIPS64 quad-core processor, developed by the Institute of Computing Technology, Chinese Academy of Sciences. To date, there has not been a sufficiently optimized BLAS on the Loongson 3A CPU. The purpose of this research is to optimize level 3 BLAS performance on the Loongson 3A CPU. We analyzed the Loongson 3A architecture and built a performance model to highlight the key point, L1 data cache misses, which is different from level 3 BLAS optimization on the mainstream x86 CPU. Therefore, we employed a variety of methods to avoid L1 cache misses in single thread optimization, including cache and register blocking, the Loongson 3A 128-bit memory accessing extension instructions, software prefetching, and single precision floating-point SIMD instructions. Furthermore, we improved parallel performance by reducing bank conflicts among multiple threads in the shared L2 cache. We created an open source BLAS project, OpenBLAS, to demonstrate the performance improvement on the Loongson 3A quad-core processor.

An increasing number of applications in physical and social sciences require the analysis of large graphs. The efficiency of these programs strongly depends on their memory usage especially the locality of graph data access. Intuitively, the locality in computation should reflect the locality in graph topology. Existing locality models, however, operate either at program level for regular loops and arrays or at trace level for arbitrary access streams. They are not sufficient to characterize the relation between locality and connectivity. This paper presents a new metrics called the vertex distance and uses it to model the locality in breadth-first graph traversal (BFS). It shows three models that use the average node degree and the edge distribution to predict the number of BFS levels and the reuse distance distribution of BFS. Finally, it evaluates the new models using random and non-random graphs.

Many fields of science and engineering, such as astronomy, medical imaging, seismology and spectroscopy, have been revolutionized by Fourier methods. The fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. The emerging class of high performance computing architectures, such as GPU, seeks to achieve much higher performance and efficiency by exposing a hierarchy of distinct memories to programmers. However, the complexity of GPU programming poses a significant challenge for programmers. In this paper, based on the Kronecker product form multi-dimensional FFTs, we propose an automatic performance tuning framework for various OpenCL GPUs. Several key techniques of GPU programming on AMD and NVIDIA GPUs are also identified. Our OpenCL FFT library achieves up to 1.5 to 4 times, 1.5 to 40 times and 1.4 times the performance of clAmdFft 1.0 for 1D, 2D and 3D FFT respectively on an AMD GPU, and the overall performance is within 90% of CUFFT 4.0 on two NVIDIA GPUs.

Sparse Matrix-Vector multiplication (SpMV) is an important computational kernel in scientific applications. Its performance highly depends on the nonzero distribution of sparse matrices. In this paper, we propose a new storage format for diagonal sparse matrices, defined as Compressed Row Segment with Diagonal-pattern (CRSD). In CRSD, we design diagonal patterns to represent the diagonal distribution. As the Graphics Processing Units (GPUs) have tremendous computation power and OpenCL makes them more suitable for the scientific computing, we implement the SpMV for CRSD format on the GPUs using OpenCL. Since the OpenCL kernels are complied at runtime, we design the code generator to produce the codelets for all diagonal patterns after storing matrices into CRSD format. Specifically, the generated codelets already contain the index information of nonzeros, which reduces the memory pressure during the SpMV operation. Furthermore, the code generator also utilizes property of memory architecture and thread schedule on the GPUs to improve the performance. In the evaluation, we select four storage formats from prior state-of-the-art implementations (Bell and Garland, 2009) on GPU. Experimental results demonstrate that the speedups reach up to 1.52 and 1.94 in comparison with the optimal implementation of the four formats for the double and single precision respectively. We also evaluate on a two-socket quad-core Intel Xeon system. The speedups reach up to 11.93 and 12.79 in comparison with CSR format under 8 threads for the double and single precision respectively.

Large-scale simulation of the thermal convection in the Earth's outer core is studied. Starting from a legacy parallel code using Aztec and MPI, two optimized codes have been developed based on the PETSc software package. The first version gains several times acceleration with the help of the block-Jacobi preconditioners and the well-optimized libraries provided in PETSc. The second version, aiming at better parallel scalability, is developed based on the ideas of domain decomposition method for multi-physical problems. Test results employing thousands of processor cores on three supercomputers, i.e., an IBM Blue Gene/L, a Dawning 5000A and a Lenovo DeepComp 7000, are provided.

Sparse matrix vector multiplication (SpMV) is used in many scientific computations. The main bottleneck of this algorithm is memory bandwidth and many methods reduce memory bandwidth usage by compressing the index array. The matrices from finite difference modeling applications often have several dense diagonals and sparse diagonals. For these matrices, the index array can be deleted by using diagonal storage format (DIA) to store dense diagonals and DIA & CSR mixed algorithm. In this paper we propose two improved sparse matrix storage format based on DIA format and the corresponding SpMV algorithms. We present the performance results on two platforms, which show that our method can reduce the memory usage for a wide range of sparse matrices and achieve speedup up to 1.87.

Matrix multiplication is one of the most common numerical operations in the field of scientific computing, which is the kernel routine of Level 3 BLAS. The STI CELL processor is a heterogeneous multiprocessor with a unique design to achieve high peak floating point performance. As matrix multiplication operation is essential for a wide range of numerical algorithms, so performance improvements to the GEMM routine immediately can benefit the entire algorithm. In this paper, we provide a new way to utilize the hardware features of Cell to achieve better performance on the Single Precision General Matrix Multiplication (SGEMM), through both heterogeneous PPEs and SPEs parallelization, our method gains speedup over the Cell SDK (2.5%). An extra speedup about 30% of performance is achieved via interleaved memory allocation, which improves memory access.

Sparse matrix-vector multiplication is an important computational kernel in scientific applications. However, it performs poorly on modern processors because of a low compute-to-memory ratio and its irregular memory access patterns. This paper discusses the implementations of sparse matrix-vector algorithm using OpenMP to execute iterative methods on the Dawning S4800A1. Two storage formats (CSR and BCSR) for sparse matrices and three scheduling schemes (static, dynamic and guided) provided by the standard OpenMP are evaluated. We also compared these three schemes with non-zero scheduling, where each thread is assigned approximately the same number of non-zero elements. Experimental data shows that, the non-zero scheduling can provide the best performance in most cases. The current implementation provides satisfactory scalability for most of matrices. However, we only get a limited speedup for some large matrices that contain millions of non-zero elements.

Nowadays proteomics becomes more and more popular in life science. Protein quantification, especially based on mass spectrometry (short for MS) method, is perceived as an essential part of research on proteomics. There have been some algorithms and software for protein quantification based on MS. But they have difficulties on portability, applicability and longtime running. To solve these problems, we developed a new domestic parallel software package called QuantWiz for high performance liquid chromatography (short for LC)-MS-based label-free protein quantification. In this paper, we described the framework design and prototype development of this high performance software package firstly. Also, user interface developed for the visualization of QuantWiz is introduced. Finally, we showed implementation of the parallelization version and performance of some experiments on this software package.

In this paper, we present our early performance evaluation results with the NPB benchmark and two scientific computing applications program, i.e., a HFFT package developed by our lab and a CFDO application software, on two 100 Teraflops-scale Dawning 5000A and DeepComp 7000. We compared the NPB performance evaluation results of Dawning 5000A and DeepComp 7000, with their corresponding predecessor, Dawning 4000A and DeepComp 6800, which demonstrating their performance improvements across a variety of NPB benchmark problems. From our evaluation results, we can find that the NPB benchmark can keep its scalability up to 16384 cores on Dawning 5000A while on DeepComp 7000 this number becomes 4096. We also find that the HFFT scales well over 2048 cores while the CFDO scales well over 512 cores on Dawning 5000A.

With the increasing number of processors in modern HPC (high performance computing) systems, there are two emergent problems to solve. One is scalability, the other is fault tolerance. In our previous work, we proposed an MPI operation level checkpoint/rollback system. The main benefits of the system is that it offers the opportunity to employ in-memory (disk-less) checkpoint/rollback techniques which has demonstrated a much better performance over its on-disk counterpart, and the opportunity to have a concurrent two level recover-and-continue MPI system which has been proven to have a high efficiency. To the scope of my knowledge, this is the first concurrent two-level checkpoint/recovery system in use. With the coming of multi-core era, it's time to utilize the multi-threading techniques to improve the performance of in-memory checkpointing algorithm. In this paper, we present two versions of MPI operation level checkpoint/rollback system, one is of single-threaded, the other is of multi-threaded. Also, we provide an in-depth performance analysis between these two approaches to illustrate the benefits of multi-threading techniques on multi-core platform. With the progress of our work, a picture of the hierarchy of future generation fault tolerant HPC system is gradually unrolled.

In this paper, we focus on satisfying the actual demands of quickly finding the shortest paths over real-road networks in an intelligent transportation system. A parallel shortest path algorithm based on graph partitioning and iterative correcting is proposed. After evaluating the algorithm using three real road networks, we conclude that our graph-partitioning and iterative correcting based parallel algorithm has good performance. In addition, it achieves more than a 15-fold speedup on 16 processors in an IBM cluster over these real road networks.

Sparse matrix-vector multiplication is an important computational kernel in scientific applications, and CSR storage algorithm often performs poorly on modern computer systems. But the register-level blocking algorithm can optimize memory hierarchy access, reduce memory access time, and then improve the performance. RAM (h) is a computation model that has h-level memory hierarchies. It indicates that different implementation forms of the same algorithm can have different memory access complexity. In this paper, we try to analyze Memory access complexity of two implementation forms of SpMV(which are CSR storage algorithm and register- level blocking algorithm) and to predict the performance of SpMV through combining the memory access complexity analysis and the data movement/floating point operation ratio analysis. The performance data of two forms and Statistical results of miss number of II, 12 and TIB on Pentium IV platform are listed. Model analytical results matched well with experimental results.

A parallel design and implementation of FM-index is presented in this paper. In applications, the performance of the FM-index is crucial, which is a self-contained, highly compressed indexing algorithm. With the popularity of multi-core processors, parallel computing allows the FM-index to run faster by performing multiple computations simultaneously when possible. Our approach works by splitting input data into overlapping blocks with equal size, and running them through the FM-index algorithm simultaneously on multiple processors. After analyzing and refactoring the sequential version, we organize the data flows of all operations according to a unified parallel framework. The experimental results show that, in general our approach has achieved a significant and sub-linear speedup on widespread symmetrical multi-processing architectures. This will greatly reduce the running time of executing operations on large data sets.