Narrow Results

In recent years, multiprocessor systems have been developed to exploit parallelism within individual programs. However, a multiprocessor system may be used more efficiently if its processors are partitioned among independent parallel programs. The partitioning of a multiprocessor system is addressed in this paper.

A simple yet powerful model is proposed for the analysis of various partitioning schemes. The model parameterizes both a multiprocessor system and its parallel workload. Attention is restricted to a multiprocessor system partitioned between two parallel programs. The model is studied to determine (1) when partitioning is worthwhile, (2) the extent of performance improvement under optimal partitioning, and (3) which of three partition scheduling schemes is best.

Prediction is a critical component in the achievement of application execution performance. The development of adequate and accurate prediction models is especially difficult in local-area clustered environments where resources are distributed and performance varies due to the presence of other users in the system. This paper discusses the use of stochastic values to parameterize cluster application performance models. Stochastic values represent a range of likely behavior and can be used effectively as model parameters. We describe two representations for stochastic model parameters and demonstrate their effectiveness in predicting the behavior of several applications under different workloads on a contended network of workstations.

The Decoupled Data-Driven (D³) architecture has shown promising results from performance evaluations based upon deterministic simulations. This paper provides performance evaluations of the D³ architecture through the formulation and analysis of a stochastic model. The D³ architecture is a hybrid control/dataflow approach that takes advantage of inherent parallelism present in a program by dynamically scheduling program threads based on data availability and it also takes advantage of locality through the use of conventional processing elements that execute the program threads. The model is validated by comparing the deterministic and stochastic model responses. After model validation, various input parameters are varied such as the number of available processing elements and average threadlength, then the performance of the architecture is evaluated. The stochastic model is based upon a closed queueing network and utilizes the concepts of available parallelism and virtual queues in order to be reduced to a Markovian system. Experiments with varying computation engine threadlengths and communication latencies indicate a high degree of tolerance with respect to exploited parallelism.

This paper investigates the influence of the interconnection network topology of a parallel system on the delivery time of an ensemble of messages, called the communication scheme. More specifically, we focus on the impact on the performance of structure in network topology and communication scheme. We introduce causal structure learning algorithms for the modeling of the communication time. The experimental data, from which the models are learned automatically, is retrieved from simulations. The qualitative models provide insight about which and how variables influence the communication performance. Next, a generic property is defined which characterizes the performance of individual communication schemes and network topologies. The property allows the accurate quantitative prediction of the runtime of random communication on random topologies. However, when either communication scheme or network topology exhibit regularities the prediction can become very inaccurate. The causal models can also differ qualitatively and quantitatively. Each combination of communication scheme regularity type, e.g. a one-to-all broadcast, and network topology regularity type, e.g. torus, possibly results in a different model which is based on different characteristics.

Direct Numerical Simulation (DNS) is an important application area that is expected to use large fractions of future large-scale simulations. In this work we develop, validate and use a performance model of the combustion code, DNS3D, to explore achieved performance on current parallel systems. The performance model is developed from a thorough analysis of the application. Its key computation characteristics are coupled with the performance characteristics of the system using an parameterized analytical model. The model is validated on three parallel systems: a muti-core AMD Opteron based system with an Infiniband fat-tree network, an IBM Power5+ system with an HPS fat-tree network, and an IBM Power7 system with a direct connect network. The performance model is shown to achieve high prediction accuracy on all three systems. We illustrate how the model can be used to explore impact of changes in either the system or the application. It is used to both analyze the achieved performance on these systems as well as to explore the possible benefits of further optimizing DNS3D's main computational kernel of one-dimensional FFTs, or in possibly overlapping communication with computation.

IBMs Blue Gene supercomputer architecture has evolved through three successive generations each providing increased levels of power-efficiency and system densities. From the original Blue Gene/L to P to Q, a higher level of integration has enabled higher single-core performance, larger concurrency per compute node, and a higher level of system integration. Although these changes have brought with them a higher overall system peak-performance, no study has examined in detail the evolution of performance across system generations. In this work we make two significant contributions that of providing a comparative performance analysis across Blue Gene generations using a consistent set of tests, and also in providing a validated performance model of the NEK-Bone proxy application from the DOE CESAR Exascale Co-Design Center. The combination of empirical analysis and the predictive capabilities of the NEK-Bone performance model enable us to not only directly compare measured performance but also allow for a comparison of system configurations that cannot currently be measured. We provide insights into how the changing architectural performance characteristics of Blue Gene have impacted on the application performance, as well as providing insight into what future systems may be able to achieve.

The analysis and understanding of large-scale application behavior is critical for effectively utilizing existing HPC resources and making design decisions for upcoming systems. In this work we utilize the information about the behavior of an MPI application at a series of smaller core counts to characterize its behavior at a much larger core count. Our methodology first captures the application's behavior via a set of features that are important for both performance and energy (cache hit rates, floating point intensity, ILP, etc.). We then find the best statistical fit from among a set of canonical functions in terms of how these features change across a series of small core counts. The models for a given feature can then be utilized to generate an extrapolated trace of the application at scale. The accuracy of the extrapolated traces is evaluated by calculating the error of the extrapolated trace relative to an actual trace for two large-scale applications, UH3D and SPECFEM3D. The accuracy of the fully extrapolated traces is further evaluated by comparing the results of building performance models using both the extrapolated trace along with an actual trace in order to predict application performance. For these two full-scale HPC applications, performance models built using the extrapolated traces predicted the runtime with absolute relative errors of less than 5%.

Functional Algorithm Simulation is a methodology for predicting the computation and communication characteristics of parallel algorithms for a class of scientific problems, without actually performing the expensive numerical computations involved. In this paper, we use Functional Algorithm Simulation to study the parallel Fast Multipole Method (FMM), which solves the N-body problem. Functional Algorithm Simulation provides us with useful information regarding communication patterns in the algorithm, the variation of available parallelism during different algorithmic phases, and upper bounds on available speedups for different problem sizes. Furthermore, it allows us to predict the performance of the FMM on message-passing multiprocessors with topologies such as cliques, hypercubes, rings, and multirings, over a wider range of problem sizes and numbers of processors than would be feasible by direct simulation. Our simulations show that an implementation of the FMM on low-cost, scalable ring or multiring architectures can attain satisfactory performance.

Modern GPUs can execute multiple kernels concurrently to keep the hardware resources busy and to boost the overall performance. This approach is called simultaneous multiple kernel execution (MKE). MKE is a promising approach for improving GPU hardware utilization. Although modern GPUs allow MKE, the effects of different MKE scenarios have not adequately studied by the researchers. Since cache memories have significant effects on the overall GPU performance, the effects of MKE on cache performance should be investigated properly. The present study proposes a framework, called RDMKE (short for Reuse Distance-based profiling in MKEs), to provide a method for analyzing GPU cache memory performance in MKE scenarios. The raw memory access information of a kernel is first extracted and then RDMKE enforces a proper ordering to the memory accesses so that it represents a given MKE scenario. Afterward, RDMKE employs reuse distance analysis (RDA) to generate cache-related performance metrics, including hit ratios, transaction counts, cache sets and Miss Status Holding Register reservation fails. In addition, RDMKE provides the user with the RD profiles as a useful locality metric. The simulation results of single kernel executions show a fair correlation between the generated results by RDMKE and GPU performance counters. Further, the simulation results of 28 two-kernel executions indicate that RDMKE can properly capture the nonlinear cache behaviors in MKE scenarios.

Extensive large-scale data and applications have increasing requests for high-performance computations which is fulfilled by Chip Multiprocessors (CMP) and System-on-Chips (SoCs). Network-on-Chips (NoCs) emerged as the reliable on-chip communication framework for CMPs and SoCs. NoC architectures are evaluated based on design parameters such as latency, area, and power. Cycle-accurate simulators are used to perform the design space exploration of NoC architectures. Cycle-accurate simulators become slow for interactive usage as the NoC topology size increases. To overcome these limitations, we employ a Machine Learning (ML) approach to predict the NoC simulation results within a short span of time. LBF-NoC: Learning-based framework is proposed to predict performance, power and area for Direct and Indirect NoC architectures. This provides chip designers with an efficient way to analyze various NoC features. LBF-NoC is modeled using distinct ML regression algorithms to predict overall performance of NoCs considering different synthetic traffic patterns. The performance metrics of five different (Mesh, Torus, Cmesh, Fat-Tree and Flattened Butterfly) NoC architectures can be analyzed using the proposed LBF-NoC framework. BookSim simulator is employed to validate the results. Various architecture sizes from $2\times 2$ to $45\times 45$ are used in the experiments considering various virtual channels, traffic patterns, and injection rates. The prediction error of LBF-NoC is 6% to 8%, and the overall speedup is $5000\times$ to $5500\times$ with respect to BookSim simulator.