Many applications have irregular behavior - e.g., input-dependent solvers, irregular memory accesses, or unbiased branches - that cannot be captured using today's automated performance modeling techniques. We describe new hierarchical critical path analyses for the Palm model generation tool. To obtain a good tradeoff between model accuracy, generality, and generation cost, we combine static and dynamic analysis. To create a model's outer structure, we capture tasks along representative MPI critical paths. We create a histogram of critical tasks with parameterized task arguments and instance counts. To model each task, we identify hot instruction-level paths and model each path based on data flow, data locality, and microarchitectural constraints. We describe application models that generate accurate predictions for strong scaling when varying CPU speed, cache and memory speed, microarchitecture, and (with supervision) input data class. Our models' errors are usually below 8%; and always below 13%.

Representative paths analysis generalizes and improves MPI critical path analysis. To improve diagnostic insight, we sample the distribution of program path costs and retain k representative paths. We describe scalable algorithms to collect representative paths and path profiles. To collect full paths efficiently, we introduce path pruning that reduces permanent space requirements from a trace (proportional to ranks and MPI events) to path length (the minimum). To make space requirements independent of ranks and events --- even a small constant in practice --- we profile program paths. Avoiding the limitations of prior path profiling approaches, we dynamically discover tasks and attribute costs in high resolution. We evaluate our algorithms on seven applications scaled up to 7000 MPI ranks. Full program paths use as little as 0.01% the permanent space of current methods; profiles require a nearly constant 100--1000 KB. Execution overhead is under 5% when synchronization intervals are sufficiently large (a few milliseconds).

Supply voltage reduction is an effective approach to significantly reduce GPU energy consumption. As the largest on-chip storage structure, the GPU register file becomes the reliability hotspot that prevents further supply voltage reduction below the safe limit ($V_{min}$) due to process variation effects. This work addresses the reliability challenge of the GPU register file at low supply voltages, which is an essential first step for aggressive supply voltage reduction of the entire GPU chip. To better understand the reliability issues posed by undervolting and its energy-saving potential, we first rigorously model and analyze the process variation impact on the GPU register file at different voltages. By further analyzing the GPU architecture, we make a key observation that the time GPU registers contain useless data (i.e., dead time) is long, providing a unique opportunity to enhance register reliability. We then propose GR-Guard, an architectural solution that leverages long register dead time to enable reliable operations from unreliable register file at low voltages. GR-Guard is both effective and low-cost, and does not affect normal (i.e., non-faulty) register accesses. Experimental results show that for a 28nm baseline GPU under aggressive voltage reduction, GR-Guard can maintain the register file reliability with less than 2\% overall performance degradation, while achieving an average of 31% energy reduction across various applications.

Today's dynamic computing deployment for commercial and scientific applications is propelling us to an era where minor inefficiencies can snowball into significant performance and operational bottlenecks. Data center operations is increasingly relying on sensors based control systems for key decision insights. The increased sampling frequencies, cheaper storage costs and prolific deployment of sensors is producing massive volumes of operational data. However, there is a lag between rapid development of analytical techniques and its widespread practical deployment. We present empirical evidence of the potential carried by analytical techniques for operations management in computing and data centers. Using Machine Learning modeling techniques on data from a real instrumented cluster, we demonstrate that predictive modeling on operational sensor data can directly reduce systems operations monitoring costs and improve system reliability.

Emerging high-performance computing platforms, with large component counts and lower power margins, are anticipated to be more susceptible to soft errors in both logic circuits and memory subsystems. We present an online algorithm-based fault tolerance (ABFT) approach to efficiently detect and recover soft errors for general iterative methods. We design a novel checksum-based encoding scheme for matrix-vector multiplication that is resilient to both arithmetic and memory errors. Our design decouples the checksum updating process from the actual computation, and allows adaptive checksum overhead control. Building on this new encoding mechanism, we propose two online ABFT designs that can effectively recover from errors when combined with a checkpoint/rollback scheme. These designs are capable of addressing scenarios under different error rates. Our ABFT approaches apply to a wide range of iterative solvers that primarily rely on matrix-vector multiplication and vector linear operations. We evaluate our designs through comprehensive analytical and empirical analysis. Experimental evaluation on the Stampede supercomputer demonstrates the low performance overheads incurred by our two ABFT schemes for preconditioned CG (0.4% and 2.2%) and preconditioned BiCGSTAB (1.0% and 4.0%) for the largest SPD matrix from UFL Sparse Matrix Collection. The evaluation also demonstrates the flexibility and effectiveness of our proposed designs for detecting and recovering various types of soft errors in general iterative methods.

Many applications of high performance embedded computing are constrained by performance or power bottlenecks. We designed a new benchmark suite, the Suite for Embedded Applications and Kernels (SEAK), (a) to capture these bottlenecks in a way that encourages creative solutions, and (b) to facilitate rigorous tradeoff evaluation for their solutions. To avoid biases toward existing solutions, both algorithms and architecture are variables. Thus, each benchmark has a mission-centric (abstracted from a particular algorithm) and goal-oriented (functional) specification. To encourage solutions that are any combination of software or hardware, we use an end-user black-box evaluation. To inform procurement decisions, evaluations capture tradeoffs between performance, power, accuracy, size, and weight. We call our benchmarks future proof because they remain useful despite shifting algorithmic/architectural preferences. To create both concise and precise mission-centric specifications, we introduce two distinct benchmark classes. This paper describes the SEAK suite and presents an evaluation of sample solutions that highlights power and performance tradeoffs.

Faults are commonplace in large scale systems. These systems experience a variety of faults such as transient, permanent and intermittent. Multi-bit faults are typically not corrected by the hardware resulting in an error. This paper attempts to answer an important question: Given a multi-bit fault in main memory, will it result in an application error - and hence a recovery algorithm should be invoked - or can it be safely ignored? We propose an application fault modeling methodology to answer this question. Given a fault signature (a set of attributes comprising of system and application state), we use machine learning to create a model which predicts whether a multi-bit permanent/transient main memory fault will likely result in error. We present the design elements such as the fault injection methodology for covering important data structures, the application and system attributes which should be used for learning the model, the supervised learning algorithms (and potentially ensembles), and important metrics. We use three applications - NWChem, LULESH and SVM - as examples for demonstrating the effectiveness of the proposed fault modeling methodology.

Silicon photonics is an emerging technology that delivers higher ratios of bandwidth to power than today's electrical interconnects. This paper explores whether graph-based analytics, increasingly important for high performance computing, can benefit from photonics' energy-efficient bandwidth. We select two contrasting photonically-enhanced systems projected for 2020. We sketch optical and electrical interconnect variants at different points along similar performance-to-power curves. We model applications and graphs that exhibit four distinct workload characteristics: compute- bound, bandwidth-bound all-to-alls, bandwidth-bound neighbor exchange, and latency-bound. We present quantitative results that project execution time and energy on large graphs (1 trillion edges). Our results show that for these workloads, interconnects with efficient optical interconnects can be over-provisioned if their bandwidth is too high. However, interconnects with similar efficiency but lower power present an opportunity for energy savings. We also show that even though optical interconnects do not improve on electrical link latencies, they can substantially increase the performance of latency-bound applications.

PNNL's Center for Advanced Technology Evaluation (CENATE) is a new U.S. Department of Energy center whose mission is to assess and facilitate access to emerging computing technology. CENATE is assessing a range of advanced technologies, from evolutionary to disruptive. Technologies of interest include the processor socket (homogeneous and accelerated systems), memories (dynamic, static, memory cubes), motherboards, networks (network interface cards and switches), and input/output and storage devices. CENATE is developing a multi-perspective evaluation process based on integrating advanced system instrumentation, performance measurements, and modeling and simulation. We show evaluations of two emerging network technologies: silicon photonics interconnects and the Data Vortex network. CENATE's evaluation also addresses the question of which machine is best for a given workload under certain constraints. We show a performance-power tradeoff analysis of a well-known machine learning application on two systems.

This special issue is the result of an open call for papers initiated after the minisymposium ‘Analysis and Modeling: Techniques and Tools’, conducted at the Society for Industrial and Applied Mathematics (SIAM) Conference on Parallel Processing in Scientific Computing in Savannah, GA, in February 2012. The minisymposium brought together tool developers, performance and power modeling experts, and application analysts to present the state of the art on performance analysis and modeling techniques. This unique combination of expertise is highly needed in a time where complex, hierarchical architectures are the standard for all highly parallel computer systems. Without a good grip on relevant performance limitations, any ptimization attempt is just a shot in the dark. Hence, it is crucial to fully understand the performance properties and bottlenecks that come about with clustered multicore/many-core, multisocket nodes. Another aspect of modern systems is the complicated interplay between power constraints and the need for compute performance, which leads to complicated trade-offs. The challenges ahead are many-fold as systems scale in size. While parallelism is increasing, memory systems, interconnection networks, storage, and uncertainties in programming models all add to the complexities. More rapid realization of energy savings will require significant increases in measurement resolution and optimization techniques. This special issue is focused on how performance and power properties of modern highly parallel systems can be analyzed using state-of-the-art modeling and analysis techniques and real-world applications and tools. G. Hager, J. Treibig, J. Habich, and G. Wellein 1 introduce simple but insightful analytic models for execution performance and energy consumption of multicore CPUs. Automatic dynamic voltage and frequency scaling is leveraged by the “Green Queue” framework presented by J. Peraza, A. Tiwari, M. Laurenzano, L. Carrington, and A. E. Snavely 2 in their article. They show that significant energy savings at low performance loss are in reach if dynamic voltage and frequency scaling is used in an application-aware manner. A. D. Breslow, L. Porter, A. Tiwari, M. Laurenzano, L. Carrington, D. M. Tullsen, and A. E. Snavely 3 investigate the potential of job striping, a technique for co-locating HPC workloads with different characteristics on the same CPU chip, and demonstrate increased throughput and energy efficiency for a mix of typical simulation codes on a production cluster. The problem of how to deal with coarse-grained power measurements is tackled in the paper by H. Servat, G. Llort, J. Giménez, and J. Labarta 4. They present a tool that can derive fine-grained power and performance data for code with quickly alternating phases. The power usage and power variability of workloads on production supercomputers at Los Alamos National Laboratory are studied by S. Pakin, C. Storlie, M. Lang, R. E. Fields, E. E. Romero, C. Idler, S. Michalak, H. Greenberg, J. Loncaric, R. Rheinheimer, G. Grider, and J. Wendelberger in their paper 5. One of their central findings is that real power dissipation under real-world workloads is significantly lower than what the power infrastructure can handle, which opens interesting possibilities for saving cost via power capping. We think that this selection of papers is unique in providing several very different views on the problem of performance and power efficiency on present-day parallel machines from the core to the computing center level.

Power efficiency - performance relative to power - is one of the most important concerns when designing RADAR processing systems. This paper analyzes power and performance trade-offs for a typical Space Time Adaptive Processing (STAP) application. We study STAP implementations for CUDA and OpenMP on two architectures, Intel Haswell Core I7-4770TE and NVIDIA Kayla with a GK208 GPU. We analyze the power and performance of STAP's computationally intensive kernels across the two hardware testbeds. We discuss an efficient parallel implementation for the Haswell CPU architecture. We also show the impact and trade-offs of GPU optimization techniques. The GPU architecture is able to process large size data sets without increase in power requirement. The use of shared memory has a significant impact on the power requirement for the GPU. Finally, we show that a balance between the use of shared memory and main memory access leads to an improved performance in a typical STAP application.

Support Vector Machines (SVM) is a supervised Machine Learning and Data Mining (MLDM) algorithm, which has become ubiquitous largely due to its high accuracy and obliviousness to dimensionality. The objective of SVM is to find an optimal boundary -- also known as hyperplane -- which separates the samples (examples in a dataset) of different classes by a maximum margin. Usually, very few samples contribute to the definition of the boundary. However, existing parallel algorithms use the entire dataset for finding the boundary, which is sub-optimal for performance reasons. In this paper, we propose a novel distributed memory algorithm to eliminate the samples which do not contribute to the boundary definition in SVM. We propose several heuristics, which range from early (aggressive) to late (conservative) elimination of the samples, such that the overall time for generating the boundary is reduced considerably. In a few cases, a sample may be eliminated (shrunk) pre-emptively -- potentially resulting in an incorrect boundary. We propose a scalable approach to synchronize the necessary data structures such that the proposed algorithm maintains its accuracy. We consider the necessary trade-offs of single/multiple synchronization using in-depth time-space complexity analysis. We implement the proposed algorithm using MPI and compare it with libsvm -- de facto sequential SVM software -- which we enhance with OpenMP for multi-core/many-core parallelism. Our proposed approach shows excellent efficiency using up to 4096 processes on several large datasets such as UCI HIGGS Boson dataset and Offending URL dataset.

Energy efficiency and resilience are two crucial challenges for HPC systems to reach exactable. While energy efficiency and resilience issues have been extensively studied individually, little has been done to understand the interplay between energy efficiency and resilience for HPC systems. Decreasing the supply voltage associated with a given operating frequency for processors and other CMOS-based components can significantly reduce power consumption. However, this often raises system failure rates and consequently increases application execution time. In this work, we present an energy saving undervaluing approach that leverages the mainstream resilience techniques to tolerate the increased failures caused by undervaluing. Our strategy is directed by analytic models, which capture the impact of undervaluing and the interplay between energy efficiency and resilience. Experimental results on a power-aware cluster demonstrate that our approach can save up to 12.1% energy compared to the baseline, and conserve up to 9.1% more energy than a state-of-the-art DVFS solution.

Two trends suggest network contention for one-sided messages is poised to become a performance problem that concerns application developers: an increased interest in one-sided programming models and a rising ratio of hardware threads to network injection bandwidth. Often it is difficult to reason about when one-sided tasks decrease or increase network contention. We present effective and portable techniques for diagnosing the causes and severity of one-sided message contention. To detect that a message is affected by contention, we maintain statistics representing instantaneous network resource demand. Using lightweight measurement and modeling, we identify the portion of a message's latency that is due to contention and whether contention occurs at the initiator or target. We attribute these metrics to program statements in their full static and dynamic context. We characterize contention for an important computational chemistry benchmark on InfiniBand, Cray Aries, and IBM Blue Gene/Q interconnects. We pinpoint the sources of contention, estimate their severity, and show that when message delivery time deviates from an ideal model, there are other messages contending for the same network links. With a small change to the benchmark, we reduce contention by 50% and improve total runtime by 20%.

Power has become a major impediment in designing large scale high-end systems. Message Passing Interface (MPI) is the de facto communication interface used as the back-end for designing applications, programming models and runtime for these systems. Slack --- the time spent by an MPI process in a single MPI call---provides a potential for energy and power savings, if an appropriate power reduction technique such as core-idling/Dynamic Voltage and Frequency Scaling (DVFS) can be applied without affecting the application's performance. Existing techniques that exploit slack for power savings assume that application behavior repeats across iterations/executions. However, an increasing use of adaptive and data-dependent workloads combined with system factors (OS noise, congestion) negates this assumption.

Partitioned Global Address Space (PGAS) models are emerging as a popular alternative to MPI models for designing scalable applications. At the same time, MPI remains a ubiquitous communication subsystem due to its standardization, high performance, and availability on leading platforms. In this paper, we explore the suitability of using MPI as a scalable PGAS communication subsystem. We focus on the Remote Memory Access (RMA) communication in PGAS models which typically includes get, put, and atomic memory operations. We perform an in-depth exploration of design alternatives based on MPI. These alternatives include using a semantically-matching interface such as MPI-RMA, as well as not-so-intuitive interfaces such as MPI two-sided with a combination of multi-threading and dynamic process management. With an in-depth exploration of these alternatives and their shortcomings, we propose a novel design which is facilitated by the data-centric view in PGAS models. This design leverages a combination of highly tuned MPI two-sided semantics and an automatic, user-transparent split of MPI communicators to provide asynchronous progress. We implement the asynchronous progress ranks approach and other approaches within the Communication Runtime for Exascale which is a communication subsystem for Global Arrays. Our performance evaluation spans pure communication benchmarks, graph community detection and sparse matrix-vector multiplication kernels, and a computational chemistry application. The utility of our proposed PR-based approach is demonstrated by a 2.17x speedup on 1008 processors over the other MPI-based designs.

Breadth-First Search (BFS) is widely used in many real world applications including computational biology, social networks, and electronic design automation. The combination method, using both top-down and bottom-up techniques, is the most effective BFS approach. However, current combination methods rely on trial-and-error and exhaustive search to locate the optimal switching point, which may cause significant runtime overhead. To solve this problem, we design an adaptive method based on regression analysis to predict an optimal switching point for the combination method at runtime within less than 0.1% of the BFS execution time. Additionally, in order to fully utilize the heterogeneous resources offered by current HPC systems and further improve the performance of the combination method, we propose methodologies to allocate the most suitable computation phases of BFS to the corresponding processing components (i.e. CPUs and accelerators) in the system based on graph information and architecture details. Our adaptive method can predict the switching point with high accuracy (compared with exhaustive search) and achieve up to 695X and 8X speedup over the worst and average case. Our cross-architecture adaptive combination method also improves performance dramatically over the cases conducted on a single architecture.

The extreme level of parallelism coupled with the limited available power budget expected in the exascale era brings unprecedented challenges that demand optimization of performance, power and resiliency in unison. Scalability on such systems is of paramount importance, while power and reliability issues may change the execution environment in which a parallel application runs. To solve these challenges exascale systems will require an introspective system software that combines system and application observations across all system stack layers with online feedback and adaptation mechanisms. In this paper we propose the design of a novel self-aware, selfadaptive system software in which a kernel-level Monitor, which continuously inspects the evolution of the target system through observation of Sensors, is combined with a user-level Controller, which reacts to changes in the execution environment, explores opportunities to increase performance, save power and adapts applications to new execution scenarios. We show that the monitoring system accurately monitors the evolution of parallel applications with a runtime overhead below 1-2%. As a test case, we design and implement a runtime system that aims at optimizing application's performance and system power consumption on complex hierarchical architectures. Our results show that our adaptive system reaches 98% of performance efficiency of manually-tuned applications.

Three types of systems dominate the current High Performance Computing landscape: the Cray XE6, the IBM Blue Gene, and commodity clusters using InfiniBand. These systems have quite different characteristics making the choice for a particular deployment difficult. The XE6 uses Cray's proprietary Gemini 3-D torus interconnect with two nodes at each network endpoint. The latest IBM Blue Gene/Q uses a single socket integrating processor and communication in a 5-D torus network. InfiniBand provides the flexibility of using nodes from many vendors connected in many possible topologies. The performance characteristics of each vary vastly along with their utilization model. In this work we compare the performance of these three systems using a combination of micro-benchmarks and a set of production applications. We also discuss the causes of variability in performance across the systems and quantify where performance is lost using a combination of measurements and models. Our results show that significant performance can be lost in normal production operation of the Cray XE6 and InfiniBand Clusters in comparison to Blue Gene/Q.

In this work we provide an early performance analysis of the communication network in a small-scale POWER7-IH processing system from IBM. Using a set of communication micro-benchmarks we quantify the achievable bandwidth of the communication links available in the system that differ in their peak performance characteristics. We also identify the bottlenecks within the communication network and show that the bandwidth a single node can inject into the network is considerably less than the bandwidth available to the IBM hub chip, that acts as a NIC to the node as well as being an integral part of the P7-IH network. Using a communication pattern that is representative of activities in many scientific applications that have regular communication patterns, we show how the default task-to-core assignment on the P7-IH achieves sub-optimal performance in most cases. We also show that when using a diagonal-cyclic assignment, as developed in this work that takes into account the network topology as well as routing strategy, the communication performance can be improved by up to 75%. We expect even greater improvements in the communication performance on larger P7-IH systems.

In this work we consider a novel application centric approach for saving energy on large-scale parallel systems. By using a priori information on the expected application behavior we identify points at which processor-cores will wait for incoming data and thus may be placed in a low power state to save energy. The approach is general and complements many of the existing approaches that rely on saving energy at points of global synchronization. We capture the expected application behavior into an Energy Template whose purpose is to identify when cores are expected to be in an idle state and allow the runtime to use the template information and change the power state of the core. We prototype an Energy Template for a wave front algorithm that contains an complex processing pattern in which cores wait for incoming data before processing local data and whose wait-time varies from phase to phase. The implementation uses PMPI and requires minimal changes to the application code. Using a power instrumented cluster we demonstrate that using an Energy Template for the wave front application lowers the power requirements by 8% when using 216 cores, from the system maximum of 23%, and the energy requirements by 4%. We also show that the wave front's inherent parallel activity will lead to increased savings on larger systems.

In this work we present a performance evaluation of the POWER7-IH processor and of integrated systems built from it. We describe the architecture of P7-IH with an emphasis on those characteristics that have a direct impact on the performance for large-scale HPC systems and applications. An important area of emphasis is the memory and communication subsystems and their impact on achievable application performance. The results from a set of micro-benchmarks are presented that include memory, communication and OS-noise characteristics. In addition the results from several production level applications are analyzed and their performance linked to the results of the micro-benchmarks through the use of accurate performance models. The models will also be employed in exploring the achievable performance of these applications on much larger systems.

Abstract Clustered systems have become a dominant architecture of scalable high‐performance super computers. In these large‐scale computers, the network performance and scalability is as critical as the compute‐nodes speed. InfiniBandTMhas become a commodity networking solution supporting the stringent latency, bandwidth and scalability requirements of these clusters. The network performance is also affected by its topology, packet routing and the communication patterns the distributed application exercises. Fat‐trees are the topology structures used for constructing most large clusters as they are scalable, maintain cross‐bisectional‐bandwidth (CBB), and are practical to build using fixed‐arity switches. In this paper, we propose a fat‐tree routing algorithm that provides a congestion‐free, all‐to‐all shift pattern leveraging on the InfiniBandTMstatic routing capability. The algorithm supports partially populated fat‐trees built with switches of arbitrary number of ports and CBB ratios. To evaluate the proposed algorithm, detailed switch and host simulation models were developed and multiple fabric topologies were run. The results of these simulations as well as measurements on real clusters show an improvement in all‐to‐all delay by avoiding congestion on the fabric. Copyright © 2009 John Wiley & Sons, Ltd.

We present predictive performance models of two of the petascale applications, S3D and GTC, from the DOE Office of Science workload. We outline the development of these models and demonstrate their validation on an Opteron/Infiniband cluster and the pre-upgrade ORNL Jaguar system (Cray XT3/XT4). Given the high accuracy of the full application models, we predict the performance of the Jaguar system after the upgrade of its nodes, and subsequently compare this to the actual performance of the upgraded system. We then analyze the performance of the system based on the models to quantify bottlenecks and potential optimizations. Finally, the models are used to quantify the benefits of alternative node allocation strategies.

In this paper, we present a methodology for profiling parallel applications executing on the IBM PowerXCell 8i (commonly referred to as the ldquoCellrdquo processor). Specifically, we examine Cell-centric MPI programs on hybrid clusters containing multiple Opteron and Cell processors per node such as those used in the petascale Roadrunner system. Our implementation incurs less than 3.2 mus of overhead per profile call while efficiently utilizing the limited local store of the Cell's SPE cores. We demonstrate the use of our profiler on a cluster of hybrid nodes running a suite of scientific applications. Our analyses of inter-SPE communication (across the entire cluster) and function call patterns provide valuable information that can be used to optimize application performance.

Abstract Conjugate gradient (CG) solvers are the most time consuming part of many scientific applications. These solvers exhibit communication operations that can prevent high performance from being achieved on large‐scale systems. In this paper we present a novel technique to boost the performance of these solvers. In this, multiple independent solvers, which occur in some applications, are combined allowing for the overlapping of communication with other communication and computation, resulting with increased performance. This is the first work where a combination of CG solvers has been exploited and offers performance improvements, which may be particularly important in very large‐scale systems. Results are presented for the MIMD lattice computation (MILC) application that show the cost of collective communications can be reduced by a factor of up to 2.5×. Moreover the performance of MILC is significantly improved, by over 10% for typical lattice sizes on a 1024‐processor system, and by 15% on a 4096‐processor system. Larger improvements are expected on larger systems. Copyright © 2009 John Wiley & Sons, Ltd.

In this work we present an initial performance evaluation of AMD and Intel's first quad-core processor offerings: the AMD Barcelona and the Intel Xeon X7350. We examine the suitability of these processors in quad-socket compute nodes as building blocks for large-scale scientific computing clusters. Our analysis of intra-processor and intra-node scalability of microbenchmarks and a range of large- scale scientific applications indicates that quad-core processors can deliver an improvement in performance of up to 4x per processor but is heavily dependent on the workload being processed. While the Intel processor has a higher clock rate and peak performance, the AMD processor has higher memory bandwidth and intra-node scalability. The scientific applications we analyzed exhibit a range of performance improvements from only 3x up to the full 16x speed-up over a single core. Also, we note that the maximum node performance is not necessarily achieved by using all 16 cores.

The achievable performance on Infiniband networks is governed by the latencies and bandwidths of communication channels as well as by contention within the network. Currently Infiniband statically routes messages and thus do not take into account dynamic loading of the channels. By interrogating the network routing tables we quantify the contention that occurs for a number of communication patterns using a large-scale (1024 processor) system. Empirical data confirms our contention calculation almost exactly. Custom routing tables are defined that provide both optimum and worst-case performance for a large- range of communication patterns. Performance differences can be as large as 12x (from optimum to worst-case). Two large-scale applications show a runtime improvement of between 10-20% and up to 40% improvement in just their communication time when using optimized routing tables. The approach taken is applicable to many Infiniband systems, and we expect the performance improvements to be even greater on larger-scale systems.

In order to take full advantage of multi-core processors careful attention must be given to the way in which each core interacts with main memory. In data-rich parallel applications multiple transfers between the main memory and local memory (cache or other) of each core will be required. It will be increasingly important to overlap these data transfers with useful computation in order to achieve highperformance. One approach to exploit this compute-transfer overlap is to use double-buffering techniques that require minimal resources in the local memory available to the cores. In this paper, we present optimized buffering techniques and evaluate them for two state-of-the-art multi-core architectures: quad-core Opteron and the Cell-BE. Experimental results show that using double buffering can substantially deliver higher performance for codes with data-parallel loop structures. Performance improvements of 1.4times and 2.2times can be achieved for the quad-core Opteron and Cell- BE respectively. Moreover, this study also provides insight into the application characteristics required for achieving improved performance when using double-buffering, and also the tuning that is required in order to achieve optimal performance.

Roadrunner is a 1.38 Pflop/s-peak (double precision) hybrid-architecture supercomputer developed by LANL and IBM. It contains 12,240 IBM PowerXCell 8i processors and 12,240 AMD Opteron cores in 3,060 compute nodes. Roadrunner is the first supercomputer to run Linpack at a sustained speed in excess of 1 Pflop/s. In this paper we present a detailed architectural description of Roadrunner and a detailed performance analysis of the system. A case study of optimizing the MPI-based application Sweep3D to exploit Roadrunner's hybrid architecture is also included. The performance of Sweep3D is compared to that of the code on a previous implementation of the Cell Broadband Engine architecture-the Cell BE-and on multi-core processors. Using validated performance models combined with Roadrunner-specific microbenchmarks we identify performance issues in the early pre-delivery system and infer how well the final Roadrunner configuration will perform once the system software stack has matured.

We demonstrate the outstanding performance and scalability of the VPIC kinetic plasma modeling code on the heterogeneous IBM Roadrunner supercomputer at Los Alamos National Laboratory. VPIC is a three-dimensional, relativistic, electromagnetic, particle-in-cell (PIC) code that self-consistently evolves a kinetic plasma. VPIC simulations of laser plasma interaction were conducted at unprecedented fidelity and scale-up to 1.0 times 1012particles on as many as 136 times 106voxels-to model accurately the particle trapping physics occurring within a laser-driven hohlraum in an inertial confinement fusion experiment. During a parameter study of laser reflectivity as a function of laser intensity under experimentally realizable hohlraum conditions, we measured sustained performance exceeding 0.374 Pflop/s (s.p.) with the inner loop itself achieving 0.488 Pflop/s (s.p.). Given the increasing importance of data motion limitations, it is notable that this was measured in a PIC calculation-a technique that typically requires more data motion per computation than other techniques (such as dense matrix calculations, molecular dynamics N-body calculations and Monte-Carlo calculations) often used to demonstrate supercomputer performance. This capability opens up the exciting possibility of using VPIC to model, from first-principles, an issue critical to the success of the multi-billion dollar DOE/NNSA National Ignition Facility.

In parallel applications communication overheads generally increase as the processor count increases and in particular, collective communication operations can become a critical limiting factor in achieving high performance. In this paper we explore a novel technique to boost application performance by dedicating some processors in the system to collective operations. We demonstrate the viability and efficiency of this approach for the allreduce collective operation on a state-of-the-art cluster. Experimental results show that the collective latency can be reduced by 30% and that the communication overhead per processor is also very low, at 1.6 mus, which represents one order of magnitude higher performance than with conventional implementations. Moreover, results on a large-scale scientific application (POP) show that this approach achieves 15% higher performance on 640 processors than when using the default collective implementation.

We present an analytic performance model of a large-scale hydrodynamics code developed at Los Alamos National Laboratory. This modeling work is part of an ongoing effort to develop models and modeling techniques for large-scale codes and systems of interest to Los Alamos and the national laboratory community (Kerbyson et al., 2001). Krak (Burton, 1994) comprises over 270,000 lines of source code and is capable of executing on a large number of parallel processors. Developing an accurate model is complicated by the irregular partitioning of input spatial grid cells to processors and the various material properties assigned to each cell. Model development proceeds by separating inter-processor communication from computation and modeling each individually. In addition, several approximations concerning subgrid size, shape, and material composition are made which reduce modeling complexity without adversely impacting prediction accuracy. We validate our model on several spatial grid sizes and processor configurations and demonstrate an accuracy at the largest scale on 512 processors to within a 3% error

This work explores the expected performance of three applications on a high performance computing cluster interconnected using InfiniBand. In particular, the expected performance across a range of configurations is analyzed notably InfiniBand 4times, 8times and 12times representing link-speeds of 10 Gb/s, 20 Gb/s, and 30 Gb/s respectively as well as near-neighbor MPI message latencies of 4mus and 1.5mus. In addition we also consider the impact of node size, from one to eight processors that share a single network connection. The performance analysis is based on the use of detailed performance models of the three applications developed at Los Alamos. The results of the analysis show that the application performance can range by as much as 60% from best to worst. The relative importance of bandwidth, latency and node size differs between the applications

While it is possible to accurately predict the execution time of a given iteration of an adaptive application, it is not generally possible to predict the data-dependent adaptive behavior the application will take and therefore to predict the total execution time for a given execution. To remedy this situation we have developed an executable performance model that can be utilized dynamically at runtime directly from the application of interest. In this manner, the application itself can rapidly predict the expected execution time for its next iteration based on current information on the data layout and level of adaptivity. This enables the application itself to determine: if an optimum level of performance is being achieved (i.e. by comparing measured and predicted times); when to perform a checkpoint (if the next iteration will exceed a predefined time limit between checkpoints); or when to terminate (if the next iteration will exceed the application's system time allocation for instance). The dynamic model is shown to have high accuracy over a number of test cases, even in the presence of interference (system activities that are not a part of application activities)

This work provides a performance analysis of three leading supercomputers that have recently been deployed: Purple, Red Storm and Blue Gene/L. Each of these machines are architecturally diverse, with very different performance characteristics. Each contains over 10,000 processors and has a system peak of over 40 Teraflops. We analyze each system using a range of micro-benchmarks which include communication performance as well as quantifying the impact of the operating system. The achievable application performance is compared across the systems. The application performance is confirmed via the use of detailed application models which use the underlying performance characteristics as measured by the micro-benchmarks. We also compare the machines in a realistic production scenario in which each machine is used so as to maximize its memory usage with the applications executed in a weak-scaling mode. The results also help illustrate that achievable performance is not directly related to the peak performance.

This tutorial presents a practical approach to the performance modeling of large-scale, scientific applications on high performance systems. The defining characteristic involves the description of a proven modeling approach, developed at Los Alamos, of full-blown scientific codes, ranging from a few thousand to over 100,000 lines, that has been validated on systems containing 1,000's of processors. We show how models are constructed and demonstrate how they are used to predict, explain, diagnose, and engineer application performance in existing or future codes and/or systems. Our approach does not require specific tools but rather is applicable across commonly used environments. Moreover, since our performance models are parametric, they imbue the user with the ability to "experiment ahead" with different system configurations or algorithms/coding strategies. Both will be demonstrated in studies emphasizing the application of these modeling techniques including: verifying system performance, comparison of large-scale systems, and examination of possible future systems.

The design and implementation of a high performance communication network are critical factors in determining the performance and cost-effectiveness of a largescale computing system. The major issues center on the trade-off between the network cost and the impact of latency and bandwidth on application performance. One promising technique for extracting maximum application performance given limited network resources is based on overlapping computation with communication, which partially or entirely hides communication delays. While this approach is not new, there are few studies that quantify the potential benefit of such overlapping for large-scale production scientific codes. We address this with an empirical method combined with a network model to quantify the potential overlap in several codes and examine the possible performance benefit. Our results demonstrate, for the codes examined, that a high potential tolerance to network latency and bandwidth exists because of a high degree of potential overlap. Moreover, our results indicate that there is often no need to use finegrained communication mechanisms to achieve this benefit, since the major source of potential overlap is found in independent work--computation on which pending messages does not depend. This allows for a potentially significant relaxation of network requirements without a consequent degradation of application performance.

The interconnect plays a key role in both the cost and performance of large-scale HPC systems. The cost of future high-bandwidth electronic interconnects mushrooms due to expensive optical transceivers needed between electronic switches. We describe a potentially cheaper and more power-efficient approach to building high-performance interconnects. Through empirical analysis of HPC applications, we find that the bulk of inter-processor communication (barring collectives) is bounded in degree and changes very slowly or never. Thus we propose a two-network interconnect: An Optical Circuit Switching (OCS) network handling long-lived bulk data transfers, using optical switches; and a secondary lower-bandwidth Electronic Packet Switching (EPS) network. An OCS could be significantly cheaper, as it uses fewer optical transceivers than an electronic network. Collectives and transient communication packets traverse the electronic network. We present compiler techniques and dynamic run-time policies, using this two-network interconnect. Simulation results show that our approach provides high performance at low cost.

Abstract This work gives a detailed analysis of the relative performance of the recently installed Earth Simulator and the next top four systems in the Top500 list using predictive performance models. The Earth Simulator uses vector processing nodes interconnected using a single‐stage, cross‐bar network, whereas the next top four systems are built using commodity based superscalar microprocessors and interconnection networks. The performance that can be achieved results from an interplay of system characteristics, application requirements and scalability behavior. Detailed performance models are used here to predict the performance of two codes representative of the ASCI workload, namely SAGE and Sweep3D. The performance models encapsulate fully the behavior of these codes and have been previously validated on many large‐scale systems. One result of this analysis is to size systems, built from the same nodes and networks as those in the top five, that will have the same performance as the Earth Simulator. In particular, the largest ASCI machine, ASCI Q, is expected to achieve a similar performance to the Earth Simulator on the representative workload. Published in 2005 by John Wiley & Sons, Ltd.

Summary form only given. The performance of unstructured mesh applications presents a number of complexities and subtleties that do not arise for dense structured meshes. From a programming point of view, handling an unstructured mesh has an increased complexity to manage the necessary data structures and interactions between mesh-cells. From a performance point of view, there are added difficulties in understanding both the processing time on a single processor and the scaling characteristics. Here we present a performance model for the calculation of deterministic S/sub N/ transport on unstructured meshes. It builds upon earlier work that successfully modeled the same calculation on structured meshes. The model captures the key processing characteristics and is parametric using both the system performance data (latency, bandwidth, processing rate etc.) and application data (mesh size etc.) as input. The model is validated on two clusters (an HP AlphaServer and an Itanium-2 system) showing high accuracy. Importantly it is also shown that a single formulation of the model can be used to predict the performance of two quite different implementations of the same calculation.

Based on a set of measurements done on the 512-node 500MHz prototype and early results on a 2048 node 700MHz BlueGene/L machine at IBM Watson, we present a performance and scalability analysis of the architecture from low-level characteristics to large-scale applications. In addition, we present predictions using our models for the performance of two representative applications from the ASC² workload on the full BlueGene/L configuration of 64K nodes. We have compared the measured values for several of the benchmarks in our suite against the predicted numbers from our performance models. In general, the error bars were relatively low. A comparison between the performance of BlueGene/L and the ASCI Q, the largest supercomputer in the US, is presented, also based on our predictive performance models.

In this paper we describe how we improved the effective performance of ASCI Q, the world's second-fastest supercomputer, to meet our expectations. Using an arsenal of performance-analysis techniques including analytical models, custom microbenchmarks, full applications, and simulators, we succeeded in observing a serious-but previously undetectable-performance problem. We identified the source of the problem, eliminated the problem, and 'closed the loop' by demonstrating improved application performance. We present our methodology and provide insight into performance analysis that is immediately applicable to other large-scale cluster-based supercomputers.

It is envisaged that the grid infrastructure will be a large-scale distributed software system that will provide high-end computational and storage capabilities to differentiated users. A number of distributed computing technologies are being applied to grid development work, including CORBA and Jini. In this work, we introduce an A4 (Agile Architecture and Autonomous Agents) methodology, which can be used for resource management for grid computing. An initial system implementation utilises the performance prediction techniques of the PACE toolkit to provide quantitative data regarding the performance of complex applications running on local grid resources. At the meta-level, a hierarchy of identical agents is used to provide an abstraction of the system architecture. Each agent is able to cooperate with other agents to provide service advertisement and discovery to schedule applications that need to utilise grid resources. A performance monitor and advisor (PMA) is in development to optimize the performance of agent behaviours.

Resource management is an important infrastructure in the grid computing environment. Scalability and adaptability are two key challenges in the implementation of such complex software systems. We introduce a new model for resource management in a metacomputing environment using a hierarchy of homogeneous agents that has the capability of service discovery. The performance of the agent system can be improved using different combinations of optimisation strategies. A modelling and simulation environment has been developed in this work that enables the performance of the system to be investigated. A simplified model of the resource management infrastructure is given as a case study and simulation results are included that show the impact of the choice of performance optimisation strategies on the overall system performance.

In this work we present a predictive analytical model that encompasses the performance and scaling characteristics of an important ASCI application. SAGE (SAIC's Adaptive Grid Eulerian hydrocode) is a multidimensional hydrodynamics code with adaptive mesh refinement. The model is validated against measurements on several systems including ASCI Blue Mountain, ASCI White, and a Compaq Alphaserver ES45 system showing high accuracy. It is parametric --- basic machine performance numbers (latency, MFLOPS rate, bandwidth) and application characteristics (problem size, decomposition method, etc.) serve as input. The model is applied to add insight into the performance of current systems, to reveal bottlenecks, and to illustrate where tuning efforts can be effective. We also use the model to predict performance on future systems.

With increasing requirements of distributed software systems, software agents are becoming a mainstream technology for software engineering and data management. Scalability and adaptability are two key challenges that must be addressed. In this work a new model is introduced for building large-scale distributed software systems with high dynamics, using a hierarchy of homogeneous agents that has the capability of service discovery. The performance of the agent system can be improved using different combinations of optimisation strategies. A modelling and simulation environment has been developed to aid the performance evaluation process. Two case studies are given and simulation results are included that show the impact of the agent mobility and the choice of performance optimisation strategies on the overall system performance.

Cache behavior is complex and inherently unstable, yet it is a critical factor affecting program performance. A method of evaluating cache performance is required, both to give quantitative predictions of miss-ratio and information to guide optimization of cache use. Traditional cache simulation gives accurate predictions of miss-ratio, but little to direct optimization, Also, the simulation time is usually far greater than the program execution time. Several analytical models have been developed, but concentrate mainly on direct-mapped caches, often for specific types of algorithm, or to give qualitative predictions. Novel analytical models of cache phenomena are presented, applicable to numerical codes consisting mostly of array operations in looping constructs. Set-associative caches are considered, through an extensive hierarchy of cache reuse and interference effects, including numerous forms of temporal and spatial locality. Models of each effect are given which, when combined, predict the overall miss-ratio. An advantage is that the models also indicate sources of cache interference. The accuracy of the models is validated through example program fragments. The predicted miss-ratios are compared with simulations and shown typically to be within 15 percent. The evaluation time of the models is shown to be independent of the problem size, generally several orders of magnitude faster than simulation.

We introduce a novel formulation of the Circle Hough Transform that we call the Coherent Circle Hough Transform. The technique uses phase to code for radii of circles. The usual simplifications of the Circle Hough Transform (CHT) are used in which lines pointing away from edge points are plotted rather than circles. Intersections of these "spokes " accumulate edge magnitude, or edge "energy", near the centres of circles. We introduce the use of a complex accumulator space and allow each spoke to vary in phase along its length. The spokes are in phase near the centre of circles and out of phase elsewhere. The spokes generated by noise are in random phase and destructively interfere. We present results for an isolated circle with additive white Gaussian noise for both the conventional Energy CHT and the new Coherent CHT. The results demonstrate that the technique reduces the mean and variance of the background level in the accumulator array, that the peak to background level improves, and that the peak width is reduced improving localisation of circle centres.

The use of a heterogeneous multiple-SIMD (M-SIMD) architecture with image-based measurements and optimal (Kalman) estimators for the analysis of image sequences is illustrated. The architecture integrates SIMD and MIMD processing paradigms, combining heterogeneity of processor types matched to the computation at each level and operational autonomy within an SIMD array. It is suited to real-time simultaneous data parallel (iconic) and control parallel (numeric) processing.>

The application of multiple-single instruction multiple-data (M-SIMD) processing techniques to the problem of finding straight lines in an image is described, and the advantages of using these techniques instead of direct SIMD computation are illustrated by reference to a hierarchical architecture: the Warwick pyramid machine. The advantages over conventional implementations of the Hough transform are discussed, and performance timings for a hierarchical implementation are provided.>

The Warwick Pyramid Machine, an architecture consisting of both SIMD and MIMD parts in a multiple SIMD organization which can operate effectively at all levels of an image analysis problem, is described. The hardware design is discussed, along with programming issues. Several image analysis algorithms that have been mapped onto the architecture are presented.>