This paper presents efficient algorithms, designed to leverage SIMD for performing additions and Montgomery reductions on integers larger than 512 bits. The existing algorithms encounter inefficiencies when parallelized using SIMD due to extensive dependencies in both operations, particularly noticeable in ARM’s SVE where SIMD operations are costly. To mitigate this problem, a novel addition algorithm is introduced that simulates the addition of large integers using a smaller addition, quickly producing the same set of carries. These carries are then utilized to perform parallel additions on large integers. For Montgomery reductions, serial multiplications are replaced with precomputations that can be effectively calculated using SIMD extensions. Experimental evidence demonstrates that these proposed algorithms substantially enhance the performance of state-of-the-art implementations of several post-quantum cryptography algorithms. Notably, they deliver a 30% speed-up from the latest CTIDH implementation, an 11% speed-up from the latest CSIDH implementation in AVX-512 processors, and a 7% speed-up from Microsoft’s standard PQCrypto-SIDH for SIKEp503 on A64FX.

Matrix powers kernel calculates the vectors Akv, for k = 1, 2,..., m and they are the heart of various scientific computations, including communication avoiding iterative solvers. In this paper we propose diamond matrix powers kernel - DMPK, which has the purpose to apply the "diamond tiling" stencil algorithm to general matrices. It can also be considered as an extension of the PA1 and PA2 algorithms, introduced by Demmel et al. Our approach enables us to control the balance between the amount of communication avoidance and redundant computation inherently present in communication avoiding algorithms. We present a proof of concept implementation of the algorithm using MPI routines. The experiments we performed show that the control of the amount of computation and communication is achievable, and with more thorough optimisations, DMPK is a promising alternative to existing MPK approaches.

What makes untrained deep neural networks (DNNs) different from the trained performant ones? By zooming into the weights in well-trained DNNs, we found that it is the location of weights that holds most of the information encoded by the training. Motivated by this observation, we hypothesized that weights in DNNs trained using stochastic gradient-based methods can be separated into two dimensions: the location of weights, and their exact values. To assess our hypothesis, we propose a novel method called lookahead permutation (LaPerm) to train DNNs by reconnecting the weights. We empirically demonstrate LaPerm's versatility while producing extensive evidence to support our hypothesis: when the initial weights are random and dense, our method demonstrates speed and performance similar to or better than that of regular optimizers, e.g., Adam. When the initial weights are random and sparse (many zeros), our method changes the way neurons connect, achieving accuracy comparable to that of a well-trained dense network. When the initial weights share a single value, our method finds a weight agnostic neural network with far-better-than-chance accuracy.

Summary This paper introduces the Xevolver code transformation framework to separate system‐aware code optimizations from HPC application codes. System‐aware code optimizations often make it difficult for programmers to maintain HPC application codes. On the other side, system‐aware code optimizations are mandatory to exploit the performance of target HPC systems. To achieve both high maintainability and high performance, the Xevolver framework provides an easy way to express system‐aware code optimizations as user‐defined code transformation rules. Those rules can be defined separately from HPC application codes. As a result, an HPC application code is converted into its optimized version for a particular target system just before the compilation, and standard HPC programmers do not usually need to maintain the optimized version that could be complicated and difficult‐to‐maintain. In this paper, three important components of the Xevolver framework are described, and then their practicality and benefits are demonstrated through six case studies. Accordingly, the user‐defined code transformation approach behind the Xevolver framework is promising to express system‐awareness for extracting the performance of an HPC system, and also for sharing expert knowledge and experiences about code optimizations. As the complexity and diversity of HPC system architectures are increasing in an extreme‐scale computing era, system‐aware code optimization without overcomplicating the code as discussed in this paper will become more and more important in the future.

Most machine learning models use hyperparameters empirically defined in advance of their training processes in a time-consuming and try-and-error fashion. Hence, there is a strong demand for systematically finding an appropriate hyperparameter configuration in a practical time. Recent works have been interested in Bayesian Optimization to tune the hyperparameters with a less number of trials, using a Gaussian Process to determine the next hyperparameter configuration being sampled for evaluation. Most of the works use some criteria including the probability of improving (GP-PI), the expected improvement (GP-EI), and the upper confidence bounds (GP-UCB), without consideration of the execution time of each trial. In this paper, we focus on minimizing the total execution time to find an appropriate configuration. Specifically, we propose to take the execution time of each trial into account. We demonstrate the feasibility of the proposed approach and show that our proposal can find an optimal or suboptimal hyperparameter configuration faster than other Bayesian optimization-based approaches in terms of execution time.

In a perfect world, code would only be written once and would run on different devices with high efficiency. A programmer's time would primarily be spent on thinking about the algorithms and data structures, not on implementing them. To a degree, that used to be the case in the era of frequency scaling on a single core. However, due to power limitations, parallel programming has become necessary to obtain performance gains. But parallel architectures differ substantially from each other, often require specialized knowledge, and typically necessitate reimplementation and fine tuning of application code. These slow tasks frequently result in situations where most of the time is spent reimplementing old rather than writing new code. The goal of our research is to find new programming techniques that increase productivity, maintain high performance, and provide abstraction to free the programmer from these unnecessary and time-consuming tasks. However, such techniques usually come at the cost of substantial performance degradation. This paper investigates current approaches to portable accelerator programming, seeking to answer whether they make it possible to combine high efficiency with sufficient algorithm abstraction. It discusses OpenCL as a potential solution and presents three approaches of writing portable code: GPU-centric, CPU-centric and combined. By applying the three approaches to a real-world program, we show that it is at least sometimes possible to run exactly the same code on many different devices with minimal performance degradation using parameterization. The main contributions of this paper are an extensive review of the current state-of-the-art regarding the stated problem and our original approach of addressing this problem with a generalized excessive-parallelism approach.

We are presenting a high-performance GPU implementation of a 2-opt and 3-opt algorithms used to solve the Traveling Salesman Problem. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. It is a very important local search technique and using GPU to parallelize the search greatly decreases the time needed to find the best edges to be swapped in a route. Our results show, that at least 90% of the time during an Iterative Local Search is spent on the 2-opt itself. Our result show that by using our algorithm for GPU, the time need to find optimal swaps can be decreased approximately 100 times in case of 2-opt compared to a sequential CPU code and more than 220-fold speedup can be observed in case of 3-opt search achieving more than 430 GFLOPS on a single Tesla C2075 GPU.

This paper presents a multiple stream scheduling mechanism to enable parallel execution of kernels, data sending from host to device and data receiving from device to host with multiple streams in CUDA. Our mechanism can divide the kernels and bi-directional data transmission into small subtasks, and allow to easily and efficiently overlap them on the CUDA compatible graphic processing unit(GPU). To set the optimal subtask size, we have built one compute bound model for computing intensive application and one data bound model for bi-directional data transmission intensive application. Basing on the two models, we also provided three scheduling algorithms for data dependent and data independent applications to maximize the efficiency of the overlap. We have applied the mechanism to a set of benchmarks to understand the performance. The results show that our work can successfully hide the latency to achieve high performance which is very close to the optimal.

In this paper we are presenting high performance GPU implementations of the 2-opt and 3-opt local search algorithms used to solve the Traveling Salesman Problem. This type of local search optimization is a very effective and fast method in case of small problem instances. However, the time spent on comparing the graph edges grows significantly with the problem size growing. They are usually a part of global search algorithms such as Iterated Local Search (ILS). Our results showed, that at least 90% of the time during a single ILS run is spent on the local search itself. Therefore we utilized GPU to parallelize the local search and that greatly improved the overall speed of the algorithm. Our results show that the GPU accelerated algorithm finds the optimal swaps approximately 3 to 26 times compared to parallel CPU code using 32 cores, operating at the speed of over 1.5 TFLOPS on a single GeForce GTX 680 GPU. The preliminary experimental studies show that the optimization algorithm using the GPU local search converges 10 to 50 times faster on average compared to the sequential CPU version, depending on the problem size.

Even with a powerful hardware in parallel execution, it is still difficult to improve the application performance and reduce energy consumption without realizing the performance bottlenecks of parallel programs on GPU architectures. To help programmers have a better insight into the performance and energy-saving bottleneck of parallel applications on GPU architectures, we propose two models: an execution time prediction model and an energy consumption prediction model. The execution time prediction model(ETPM) can estimate the execution time of massively parallel programs which take the instruction-level and thread-level parallelism into consideration. ETPM contains two components: memory sub-model and computation sub-model. The memory sub-model is estimating the cost of memory instructions by considering the number of active threads and GPU memory bandwidth. Correspondingly, the computation sub-model is estimating the cost of computation instructions by considering the number of active threads and the application's arithmetic intensity. We use ocelot to analysis PTX codes to obtain several input parameters for the two sub-models such as the memory transaction number and data size. Basing on the two sub-models, the analytical model can estimates the cost of each instruction while considering instruction-level and thread-level parallelism, thereby estimating the overall execution time of an application. The energy consumption prediction model(ECPM) can estimate the total energy consumption basing on the data from ETPM. We compare the outcome from the models and the actual execution on GTX260 and Tesla C2050. The results show that the models can reach almost 90 percentage accuracy in average for the benchmarks we used.

We discuss hardware and software aspects of GPGPU, specifically focusing on NVIDIA cards and CUDA, from the viewpoints of parallel computing. The major weak points of GPU against newest supercomputers are identified to be and summarized as only four points: large SIMD vector length, small memory, absence of fast L2 cache, and high register spill penalty. As software concerns, we derive optimal scheduling algorithm for latency hiding of host-device data transfer, and discuss SPMD parallelism on GPUs.

Power dissipation is one of the most imminent limitation factors influencing the development of High Performance Computing (HPC). Toward power-efficient HPC on CPU-GPU hybrid platform, we are investigating software methodologies to achieve optimized power utilization by algorithm design and programming technique. In this paper we discuss power measurements of GPU, propose a method of automatic extraction of power data of CUDA kernels from long measurement sequence, and execute an exactitude and effective power analysis on CUDA kernels. By using the proposed method above, we measured a sample kernel that performs single precision floating point additions on GeForce 8800 GTS. Our results suggest that the power consumption by a non-working thread in underoccupied half-warp is 71% of the power consumed by a working thread.

A new Dynamic Load Balancing (DLB) method for automatic performance tuning in parallel, adaptive, 3-D mesh refinement is developed based on study of characteristics of Finite Element Method (FEM) on electromagnetics with tetrahedra. On the top of existing DLB algorithms, the new design optimized the task pool location of each Processing Element (PE) and the initial data assignments in multiprocessor parallel architecture. To accomplish our method, we investigate it by applying the algorithm in implementations of parallel 3-D Hierarchical Tetrahedra and Octahedra (HTO) mesh refinement. By comparing the benchmark results derived from the performance measures of the new method with the performance results from other two existing DLB algorithms running the same HTO example geometric mesh refinement model and on the same parallel architecture, the benefits of the new method for achieving high performance parallel mesh refinement are demonstrated.

Divisible load model allows scheduling algorithms that give nearly optimal makespan with practical computational complexity. Beaumont et al. have shown that their algorithm produces a schedule whose makespan is within 1+O(1/radicT) times larger than the optimal solution when the total amount of tasks T scales up and the other conditions are fixed. We have proposed an extension of their algorithm for multiple masters with heterogeneous performance of processors but limited to uniform network performance. This paper analyzes the asymptotic performance of our algorithm, and shows that the asymptotic performance of our algorithm is either 1+O(1/radicT), 1+O(log T/T) or 1+O(1/T ), depending on the problem. For the latter two cases, our algorithm asymptotically outperforms the algorithm by Beaumont et al.

We propose the Ensparsed LU decomposition (ELU) method as a linear solver for large-scale circuit transient analysis. Ensparsing is an algorithmic technique of ignoring small values in computation. While some researchers have used ensparsing by value in linear solvers for circuit simulation, the ELU method incorporates ensparsing by time as well. A high performance implementation of the ELU method for transient analysis is also investigated. The ELU method is faster than the conventional linear solvers, and the advantages of the ELU method will still increase for larger circuits.

This paper investigates an efficient implementation of circuit simulator sparta based on the preconditioned Jacobi method on a loosely coupled distributed memory machine Fujitsu AP1000. The preconditioned relaxation methods are linear solvers effective in large scale circuit simulations. Because the preconditioned Jacobi method has a high parallelism, the only problem of parallelization of sparta is the application of the preconditioner to the residual vector. This paper investigates the matrix mapping schemes and the communication methods for efficient preconditioner application. The peculiarity of the preconditioner in sparta is a few full rows and columns, in spite of its rather high sparsity. The column-row mapping is the best scheme by far, where the decisive point is the low communication requirements. The best communication method is the far-first cascade method, despite the out-of-order reception of messages of the one-to-one method. The parallel efficiency of sparta is reporte...

A novel Josephson device with many desirable properties/spl minus/fast switching speed, high operation frequency, and low power dissipation/spl minus/has been researched these several years: the Quantum Flux Parametron (QFP). This paper discusses the interconnection problem of QFP circuits, where wire inductance matching and high clock rate restrict the lengths of interconnection wires. A layout model of QFP interconnection wires is clarified, and the effects of wire inductance matching on interconnection area and wire length are analyzed. The limitation comes from the bound of the number of squares of wires, therefore similar effects will exist where wire resistance is bounded. This paper discusses a simple wiring and buffering algorithm for QFP circuits, in which wire inductance is adjusted and the maximum wire length is controlled, to prove that any logic is realizable as a QFP circuit.>