Recent years have seen the adoption of Machine Learning (ML) techniques to predict the performance of large-scale applications, mostly at a coarse level. In contrast, we propose to use ML techniques for performance prediction at a much finer granularity, namely at the Basic Block (BB) level, which are single entry, single exit code blocks that are used for analysis by the compilers to break down a large code into manageable pieces. Utilizing ML and BB analysis together can enable scalable hardware-software co-design beyond the current state of the art. In this work, we extrapolate the basic block execution counts of GPU applications and use it for predicting the performance for large input sizes from the counts of smaller input sizes.We trained a Poisson Neural Network (PNN) model using random input values as well as the lowest input values of the application to learn the relationship between inputs and basic block counts. Experimental results show that the model can accurately predict the basic block execution counts of 16 GPU benchmarks. We achieved an accuracy of 93.5% for extrapolating the basic block counts for large input sets when the model is trained using smaller input sets. Additionally, the model shows an accuracy of 97.7% for predicting basic block counts on random instances. In a significant case study, we applied the ML model to CUDA GPU benchmarks for performance prediction across a spectrum of applications, spanning linear algebra to machine learning benchmarks. We employed a diverse set of metrics for evaluation, including global memory requests, tensor cores’ active cycles, and the active cycles of ALU and FMA units. The results from the case study demonstrate that the model is capable of predicting the performance of large datasets with high accuracy. For example, The average error rates for global and shared memory requests are 0.85% and 0.17%, respectively. Furthermore, to address the utilization of the main functional units in Ampere architecture GPUs, we calculated the active cycles for units like tensor cores, ALU, FMA, and FP64 units. Our predictions for the active cycles show an average error of 2.3% for the ALU and 10.66% for the FMA units, while the maximum observed error across all tested applications and units reaches 18.5%.

As quantum computers become available to the general public, the need has arisen to train a cohort of quantum programmers, many of whom have been developing classical computer programs for most of their careers. While currently available quantum computers have less than 100 qubits, quantum computing hardware is widely expected to grow in terms of qubit count, quality, and connectivity. This review aims at explaining the principles of quantum programming, which are quite different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. We give an introduction to quantum computing algorithms and their implementation on real quantum hardware. We survey 20 different quantum algorithms, attempting to describe each in a succinct and self-contained fashion. We show how these algorithms can be implemented on IBM’s quantum computer, and in each case, we discuss the results of the implementation with respect to differences between the simulator and the actual hardware runs. This article introduces computer scientists, physicists, and engineers to quantum algorithms and provides a blueprint for their implementations.

Traditional Parallel Discrete Event Simulation (PDES) systems employ a monolithic approach for choosing their thread synchronization protocol. They either implement a Time Window-based conservative synchronization or an optimistic event processing capability based on the Time Warp synchronization. In this paper, we show that this binary choice is suboptimal and unnecessary, particularly in the realistic situation where the load distribution across the simulation domain changes over time. We thus propose a new PDES synchronization scheme, called Hybrid PDES, that dynamically switches between conservative and optimistic synchronization protocols based on the simulation run time characteristics.

In this paper, we present PPT-GPU, a scalable performance prediction toolkit for GPUs. PPT-GPU achieves scalability through a hybrid high-level modeling approach where some computations are extrapolated and multiple parts of the model are parallelized. The tool primary prediction models use pre-collected memory and instructions traces of the workloads to accurately capture the dynamic behavior of the kernels.

GPUs are prevalent in modern computing systems at all scales. They consume a significant fraction of the energy in these systems. However, vendors do not publish the actual cost of the power/energy overhead of their internal microarchitecture. In this paper, we accurately measure the energy consumption of various PTX instructions found in modern NVIDIA GPUs. We provide an exhaustive comparison of more than 40 instructions for four high-end NVIDIA GPUs from four different generations (Maxwell, Pascal, Volta, and Turing). Furthermore, we show the effect of the CUDA compiler optimizations on the energy consumption of each instruction. We use three different software techniques to read the GPU on-chip power sensors, which use NVIDIA's NVML API and provide an in-depth comparison between these techniques. Additionally, we verified the software measurement techniques against a custom-designed hardware power measurement. The results show that Volta GPUs have the best energy efficiency of all the other generations for the different categories of the instructions. This work should aid in understanding NVIDIA GPUs' microarchitecture. It should also make energy measurements of any GPU kernel both efficient and accurate.

In this paper, we introduce an accurate and scalable memory modeling framework for General Purpose Graphics Processor units (GPGPUs), PPT-GPU-Mem. That is Performance Prediction Tool-Kit for GPUs Cache Memories. PPT-GPU-Mem predicts the performance of different GPUs' cache memory hierarchy (L1 & L2) based on reuse profiles. We extract a memory trace for each GPU kernel once in its lifetime using the recently released binary instrumentation tool, NVBIT. The memory trace extraction is architecture-independent and can be done on any available NVIDIA GPU. PPT-GPU-Mem can then model any NVIDIA GPU caches given their parameters and the extracted memory trace. We model Volta Tesla V100 and Turing TITAN RTX and validate our framework using different kernels from Polybench and Rodinia benchmark suites in addition to two deep learning applications from Tango DNN benchmark suite. We provide two models, MBRDP (Multiple Block Reuse Distance Profile) and OBRDP (One Block Reuse Distance Profile), with varying assumptions, accuracy, and speed. Our accuracy ranges from 92% to 99% for the different cache levels compared to real hardware while maintaining the scalability in producing the results. Finally, we illustrate that PPT-GPU-Mem can be used for design space exploration and for predicting the cache performance of future GPUs.

In this work, we accurately measure the energy consumption of the different instructions that can be executed in modern NVIDIA GPGPUs. We use three different software techniques to read the GPU on-chip power sensors, which use NVIDIA's NVML API and provide an in-depth comparison between these techniques. Additionally, we verified the software measurement techniques against a custom-designed hardware power measurement. The results show that Volta GPUs have the best energy efficiency of all the other generations for the different categories of the instructions. This work should give GPU architects and developers a more concrete understanding of these representative NVIDIA GPUs' microarchitecture. It should also make energy measurements of any GPU kernel both efficient and accurate.

We propose an optimization approach for determining both hardware and software parameters for the efficient implementation of a (family of) applications called dense stencil computations on programmable general purpose computing on graphics processing units. We first introduce a simple, analytical model for the silicon area usage of accelerator architectures and a workload characterization of stencil computations. We combine this characterization with a parametric execution-time model and formulate a mathematical optimization problem that seeks to maximize a common objective function of all the hardware and software parameters. The solution to this problem, therefore, “solves” the codesign problem: simultaneously choosing software-hardware parameters to optimize total performance. We validate this approach by proposing architectural variants of the NVIDIA Maxwell GTX-980 (respectively, Titan X) specifically tuned to a predetermined workload of four common 2-D stencils (Heat, Jacobi, Laplacian, and Gradient) and two 3-D ones (Heat and Laplacian). Our model predicts that performance would potentially improve by 28% (respectively, 33%) with simple tweaks to the hardware parameters, such as tuning the number of streaming multiprocessors, the number of compute cores each contains, and the size of shared memory. We also develop a number of insights about the optimal regions of the design landscape.

In this work, we propose a very low overhead and portable analysis for exposing the hidden latency of each individual instruction executing in the pipeline and different access latencies of the various memory hierarchies at the microarchitecture level. We also show the impact of the possible optimizations a CUDA compiler have over the various latencies. We run our evaluation on seven different high-end NVIDIA GPUs from five different generations/architectures namely: Kepler, Maxwell, Pascal, Volta, and Turing.

GPU architects have introduced on-chip memories in GPUs to provide local storage nearby processing to reduce the traffic to the device global memory. From then on-wards, modeling to predict the cache performance has been an active area of research. However, due to the complexities found in this highly parallel hardware, this has not been a straightforward task. In this paper, we propose a memory model to predict the entire cache performance (L1 & L2 caches) in GPUs. Our model is based on reuse distance. We use an analytical probabilistic measure of the reuse distance distributions from the memory traces of an application to predict the hit rates. The application’s memory trace is extracted using NVIDIA’s SASSI instrumentation tool. We use 20 different kernels from Polybench and Rodinia benchmark suites and compare our model to the real hardware. The results show that the average prediction accuracy of the model over all the kernels is 86.7% compared to the real device with higher accuracy for the L2 (95.26%) cache than the L1. Furthermore, extracting the application’s memory trace is on average 4. 9x slower compared to the kernels running without instrumentation. This overhead is much smaller than other published results. Furthermore, our model is very flexible where it takes into account the different cache parameters thus it can be used for design space exploration and sensitivity analysis.

We present the Analytical Memory Model with Pipelines (AMMP) of the Performance Prediction Toolkit (PPT). PPT-AMMP takes high-level source code and hardware architecture parameters as input, predicts runtime of that code on the target hardware platform, which is defined in the input parameters. PPT-AMMP transforms the code to an (architecture-independent) intermediate representation, then (i) analyzes the basic block structure of the code, (ii) processes architecture-independent virtual memory access patterns that it uses to build memory reuse distance distribution models for each basic block, (iii) runs detailed basic-block level simulations to determine hardware pipeline usage. Further, PPT-AMMP uses machine learning and regression techniques to build the prediction models based on small instances of the input code, then integrates into a higher-order discrete-event simulation model of PPT running on Simian PDES engine. We validate PPT-AMMP on four standard computational physics benchmarks, finally present a use case of hardware parameter sensitivity analysis to identify bottleneck hardware resources on different code inputs.

Parallel application performance models provide valuable insight about the performance in real systems. Capable tools providing fast, accurate, and comprehensive prediction and evaluation of high-performance computing (HPC) applications and system architectures have important value. This paper presents PyPassT, an analysis based modeling framework built on static program analysis and integrated simulation of the target HPC architectures. More specifically, the framework analyzes application source code written in C with OpenACC directives and transforms it into an application model describing its computation and communication behavior (including CPU and GPU workloads, memory accesses, and message-passing transactions). The application model is then executed on a simulated HPC architecture for performance analysis. Preliminary experiments demonstrate that the proposed framework can represent the runtime behavior of benchmark applications with good accuracy.

As the US Department of Energy (DOE) invests in exascale computing, scalable performance modeling of physics codes on CPUs remains a hard challenge in computational codesign due to advanced design features of processors such as the memory hierarchy, instruction pipelining, and speculative execution. Reuse distance is a powerful (but unscalable) characteristic that helps to predict cache hit-rates. We propose, Analytical Memory Model (AMM), a novel hardware model based on cache memory hierarchies. AMM efficiently computes close approximations of reuse distance distributions through a combination of static analysis of basic code blocks and sampling from very small code instances. The results show that AMM accurately predicts reuse profiles of scientific mini-applications (for example, matrix multiplication). Coupling AMM with the Performance Prediction Toolkit (PPT), we further show a scalable runtime prediction of scientific codes on Intel Xeon.

Branch prediction is crucial in improving the throughput of microprocessors. It reduces branching stalls in the pipeline, which helps to maintain the instruction execution flow. Of these instructions, conditional branches are non-trivial in determining the microprocessor performance and throughput. Modern microprocessors accurately predict the branches using advanced branch prediction techniques. Appropriately estimating the branch mis-predictions benefits to improve the overall performance of an application through effectively saving the CPU cycles. In general, collecting branch prediction statistics using state-of-the-art simulators is time consuming and not scalable. We present a novel Monte Carlo simulation framework that predicts branch mis-prediction rate. Our framework produces results that suggest that the mis-prediction rates on three scientific applications are similar (with an average difference of 0.3%) to that of a Markov model of a 2-bit saturating branch predictor.

Conditional branch instructions have a significant effect on the microprocessor performance and throughput. Accurate branch prediction is crucial in reducing control hazards and improving microprocessor performance. Modern microprocessors accurately predict the branch outcomes using advanced prediction techniques. Estimating branch mis-prediction rates accurately helps to improve the overall performance by saving CPU cycles and power. In general, we run the application programs on cycle accurate hardware simulators such as GEM5 [4], to collect the branch prediction statistics. This method comes out to be time consuming and is also not scalable. We present a novel Monte Carlo simulation framework that produces the branch prediction rate statically, without actually running the application on the hardware. Our framework mimics the execution behavior of the real hardware. It uses one of the three different branch prediction schemes to calculate the branch prediction statistics. It also comments on the branch prediction rates of individual branches. Results suggest that the conditional prediction rates for four scientific applications are similar to that of results from the GEM5 [4] simulator.

Interconnection network is a critical component of high-performance computing architecture and application co-design. For many scientific applications, the increasing communication complexity poses a serious concern as it may hinder the scaling properties of these applications on novel architectures. It is apparent that a scalable, efficient, and accurate interconnect model would be essential for performance evaluation studies. In this paper, we present an interconnect model for predicting the performance of large-scale applications on high-performance architectures. In particular, we present a sufficiently detailed interconnect model for Cray's Gemini 3-D torus network. The model has been integrated with an implementation of the Message-Passing Interface (MPI) that can mimic most of its functions with packet-level accuracy on the target platform. Extensive experiments show that our integrated model provides good accuracy for predicting the network behavior, while at the same time allowing for good parallel scaling performance.

The maximum likelihood decoding problem is known to be NP-hard for binary linear codes, while belief propagation decoding is known to work well in practice for several LDPC codes. In this paper we give a polynomial time reduction from the maximum likelihood decoding (MLD) problem for binary linear codes to the weighted MLD problem for (3,3)- LDPC codes. The reduction proves the NP-hardness of weighted MLD for (3,3)-LDPC codes. It also provides a method which can be used to transform the decoding problem for dense codes to the decoding of sparse codes. The later problem is often more amenable to the use of belief propagation algorithm. For ease of presentation, we have organized the total reduction in several intermediate reductions, most of which are elementary and easy to follow.

We consider a list decoding algorithm recently proposed by Pellikaan-Wu [8] for q-ary Reed-Muller codes R M q(l, m, n) of length n les qmwhen I les q. A simple and easily accessible correctness proof is given which shows that this algorithm achieves a relative error-correction radius of taules (1 - radiclqm-1/n). This is an improvement over the proof using one-point Algebraic-Geometric codes given in [8]. The described algorithm can be adapted to decode Product-Reed- Solomon codes. We then propose a new low complexity recursive algebraic decoding algorithm for Reed-Muller and product-Reed-Solomon codes. Our algorithm achieves a relative error correction radius of taui=1m(1 - radicki/q). This technique is then proved to outperform the Pellikaan-Wu method in both complexity and error correction radius over a wide range of code rates.

The branching program is a fundamental model of (nonuniform) computation, which conveniently captures both time and space restrictions. Recently, an interesting connection between the minimum distance of a code and the branching program complexity of its encoder was established by Bazzi and Mitter. Here, we establish a relationship between the minimum distance of a linear code C and the branching program complexity of computing the syndrome function for C and/or its dual code Cperp. Specifically, let C be an (n, k, d) linear code over Fq, and suppose that there is a branching program B that computes the syndrome vector with respect to the dual code Cperpin time T and space S. We prove that the minimum distance of C is then bounded by d les 2T(S+log2T)/klog2q + 1. We also consider the average-case complexity in the branching program model: we show that if B computes the syndrome with respect to Cperpin expected time T and expected space S, then d les 12T(S+log2T + 6)/klog2q + 1. Since there are trivial branching programs that compute the syndrome vector with time-space complexity ST = O(n2log q), the bound in (2) is asymptotically tight. Furthermore, with the help of the bounds in (1) and (2), we prove the conjecture of Bazzi and Mitter that a sequence of codes whose encoder function is computable by a branching program with time-space complexity ST = o(n2) cannot be asymptotically good, for the special case of self-dual codes. Our proof of these results is based on the probabilistic method developed by Borodin-Cook and Abrahamson

It is well-established "folk knowledge" that in order to be iteratively decodable, a code should have a sparse parity-check matrix, as it has some qualitative and quantitative properties for finite-length codes.