We describe an energy-based analogue of the time-based roofline model. We create this model from the perspective of algorithm designers and performance tuners, with the intent not of making exact predictions, but rather, developing highlevel analytic insights into the possible relationships among the time, energy, and power costs of an algorithm. The model expresses algorithms in terms of operations, concurrency, and memory traffic; and characterizes the machine based on a small number of simple cost parameters, namely, the time and energy costs per operation or per word of communication. We confirm the basic form of the model experimentally. From this model, we suggest under what conditions we ought to expect an algorithmic time-energy trade-off, and show how algorithm properties may help inform power management.

We present and evaluate a surrogate model, based on hardware performance counter measurements, to estimate computer system power consumption. Power and energy are especially important in the design and operation of large data centers and of clusters used for scientific computing. Tradeoffs are made between performance and power consumption, this needs to be dynamic because activity varies over time. While it is possible to instrument systems for fine-grain power monitoring, such instrumentation is costly and not commonly available. Furthermore, the latency and sampling periods of hardware power monitors can be large compared to time scales at which workloads can change and dynamic power controls can operate. Given these limitations, we argue that surrogate models of the kind we present here can provide low-cost and accurate estimates of power consumption to drive on-line dynamic control mechanisms and for use in off-line tuning.

Existing supercomputers have hundreds of thousands of processor cores, and future systems may have hundreds of millions. Developers need detailed performance measurements to tune their applications and to exploit these systems fully. However, extreme scales pose unique challenges for performance-tuning tools, which can generate significant volumes of I/O. Compute-to-I/O ratios have increased drastically as systems have grown, and the I/O systems of large machines can handle the peak load from only a small fraction of cores. Tool developers need efficient techniques to analyze and to reduce performance data from large numbers of cores.

Multi-core computers are ubiquitous and multi-socket versions dominate as nodes in compute clusters. Given the high level of parallelism inherent in processor chips, the ability of memory systems to serve a large number of concurrent memory access operations is becoming a critical performance problem. The most common model of memory performance uses just two numbers, peak bandwidth and typical access latency. We introduce concurrency as an explicit parameter of the measurement and modeling processes to characterize more accurately the complexity of memory behavior of multi-socket, multi-core systems. We present a detailed experimental multi-socket, multi-core memory study based on the PCHASE benchmark, which can vary memory loads by controlling the number of concurrent memory references per thread. The make-up and structure of the memory have a major impact on achievable bandwidth. Three discrete bottlenecks were observed at different levels of the hardware architecture: limits on the number of references outstanding per core; limits to the memory requests serviced by a single memory controller; and limits on the global memory concurrency. We use these results to build a memory performance model that ties concurrency, latency and bandwidth together to create a more accurate model of overall performance. We show that current commodity memory sub-systems cannot handle the load offered by high-end processor chips.

MAESTRO is a prototype runtime designed to provide simple, very light threads and synchronization between those threads on modern commodity (times86) hardware. The MAESTRO threading library is designed to be a target for a high-level language compiler or source-to-source translator, not for user-level programming. It provides parallel programming environments with a straight forward hardware model which can be mapped to available hardware dynamically. MAESTRO separates the size of the hardware system being used from the amount of parallelism available in an application. By separating the problem of locating parallelism from the problem of effectively using parallelism, both problems can be made easier. To the extent possible, the programming environment should be responsible for finding parallelism and the runtime should manage resource allocation and assignment. Parallel regions and parallel loops are implemented. Several simple benchmarks have been ported from OpenMP to use the MAESTRO threading interface. Two synchronization mechanisms have been implemented, one for general synchronization and one for producer-consumer relationships. We have started building a level of 'virtualization' between the programming environment and the actual hardware, which will allow better hardware utilization and support new parallel programming languages.

We report our experiences with using high-throughput techniques to run large sets of performance experiments on collections of grid accessible parallel computer systems for the purpose of deploying optimally compiled and configured scientific applications. In these environments, the set of variable parameters (compiler, link, and runtime flags; application and library options; partition size) can be very large, so running the performance ensembles is labor intensive, tedious, and prone to errors. Automating this process improves productivity, reduces barriers to deploying and maintaining multi-platform codes, and facilitates the tracking of application and system performance over time. We describe the design and implementation of our system for running performance ensembles and we use two case studies as the basis for evaluating the long term potential for this approach. The architecture of a prototype benchmarking system is presented along with results on the efficacy of the workflow approach.

Emerging petascale systems will have many hundreds of thousands of processors, but traditional task-level tracing tools already fail to scale to much smaller systems because the I/O backbones of these systems cannot handle the peak load offered by their cores. Complete event traces of all processes are thus infeasible. To retain the benefits of detailed performance measurement while reducing volume of collected data, we developed AMPL, a general-purpose toolkit that reduces data volume using stratified sampling. We adopt a scalable sampling strategy, since the sample size required to measure a system varies sub-linearly with process count. By grouping, or stratifying, processes that behave similarly, we can further reduce data overhead while also providing insight into an application's behavior. In this paper, we describe the AMPL toolkit and we report our experiences using it on large-scale scientific applications. We show that AMPL can successfully reduce the overhead of tracing scientific applications by an order of magnitude or more, and we show that our tool scales sub-linearly, so the improvement will be more dramatic on petascale machines. Finally, we illustrate the use of AMPL to monitor applications by performance-equivalent strata, and we show that this technique can allow for further reductions in trace data volume and traced execution time.

Good load balance is crucial on very large parallel systems, but the most sophisticated algorithms introduce dynamic imbalances through adaptation in domain decomposition or use of adaptive solvers. To observe and diagnose imbalance, developers need system-wide, temporally-ordered measurements from full-scale runs. This potentially requires data collection from multiple code regions on all processors over the entire execution. Doing this instrumentation naively can, in combination with the application itself, exceed available I/O bandwidth and storage capacity, and can induce severe behavioral perturbations. We present and evaluate a novel technique for scalable, low-error load balance measurement. This uses a parallel wavelet transform and other parallel encoding methods. We show that our technique collects and reconstructs system-wide measurements with low error. Compression time scales sublinearly with system size and data volume is several orders of magnitude smaller than the raw data. The overhead is low enough for online use in a production environment.

This BOF is a venue for presentations and discussions of progress in the dual problems of evaluating the performance (including reliability) of petascale computing systems and of developing application codes that scale to run effectively on such systems. We therefore invite participation by representatives of large-system vendors, funding agencies, infrastructure operators, appplication-development groups, and others that have a stake in design, operation, and successful use of these systems.Technical topics to be addressed include: scaling properties of benchmark suites; scalable machine models; application modeling to predict scaling for future machines; the problem of preparing applications for petascale environments; and the role of all of these topics in petascale acquisitions.At this session we will start planning for a series of workshops on the subject.

Call path profiling associates resource consumption with the calling context in which resources were consumed. We describe the design and implementation of a low-overhead call path profiler based on stack sampling. The profiler uses a novel sample-driven strategy for collecting frequency counts for call graph edges without instrumenting every procedure's code to count them. The data structures and algorithms used are efficient enough to construct the complete calling context tree exposed during sampling. The profiler leverages information recorded by compilers for debugging or exception handling to record call path profiles even for highly-optimized code. We describe an implementation for the Tru64/Alpha platform. Experiments profiling the SPEC CPU2000 benchmark suite demonstrate the low (2%-7%) overhead of this profiler. A comparison with instrumentation-based profilers, such as gprof, shows that for call-intensive programs, our sampling-based strategy for call path profiling has over an order of magnitude lower overhead.

The software gap - the discrepancy between the need for new software and the aggregate capacity of the workforce to produce it - is a serious problem for scientific software. Although users appreciate the convenience (and, thus, improved productivity) of using relatively high-level scripting languages, the slow execution speeds of these languages remain a problem. Lower level languages, such as C and Fortran, provide better performance for production applications, but at the cost of tedious programming and optimization by experts. If applications written in scripting languages could be routinely compiled into highly optimized machine code, a huge productivity advantage would be possible. It is not enough, however, to simply develop excellent compiler technologies for scripting languages (as a number of projects have succeeded in doing for MATLAB). In practice, scientists typically extend these languages with their own domain-centric components, such as the MATLAB signal processing toolbox. Doing so effectively defines a new domain-specific language. If we are to address efficiency problems for such extended languages, we must develop a framework for automatically generating optimizing compilers for them. To accomplish this goal, we have been pursuing an innovative strategy that we call telescoping languages. Our approach calls for using a library-preprocessing phase to extensively analyze and optimize collections of libraries that define an extended language. Results of this analysis are collected into annotated libraries and used to generate a library-aware optimizer. The generated library-aware optimizer uses the knowledge gathered during preprocessing to carry out fast and effective optimization of high-level scripts. This enables script optimization to benefit from the intense analysis performed during preprocessing without repaying its price. Since library preprocessing is performed only at infrequent "language-generation" times, its cost is amortized over many

Abstract High‐Performance Fortran (HPF) was envisioned as a vehicle for modernizing legacy Fortran codes to achieve scalable parallel performance. To a large extent, today's commercially available HPF compilers have failed to deliver scalable parallel performance for a broad spectrum of applications because of insufficiently powerful compiler analysis and optimization. Substantial restructuring and hand‐optimization can be required to achieve acceptable performance with an HPF port of an existing Fortran application, even for regular data‐parallel applications. A key goal of the Rice dHPF compiler project has been to develop optimization techniques that enable a wide range of existing scientific applications to be ported easily to efficient HPF with minimal restructuring. This paper describes the challenges to effective parallelization presented by complex (but regular) data‐parallel applications, and then describes how the novel analysis and optimization technologies in the dHPF compiler address these challenges effectively, without major rewriting of the applications. We illustrate the techniques by describing their use for parallelizing the NAS SP and BT benchmarks. The dHPF compiler generates multipartitioned parallelizations of these codes that are approaching the scalability and efficiency of sophisticated hand‐coded parallelizations. Copyright © 2002 John Wiley & Sons, Ltd.

To ameliorate the need to spend significant programmer time modifying parallel programs to achieve high-performance, while maintaining compact, comprehensible source codes, the paper advocates the use of telescoping language technology to automatically apply, during the normal compilation process, high-level performance enhancing transformations to applications using a high-level domain-specific I/O library. We believe that this approach will be more acceptable to application developers than new language extensions, but will be just as amenable to optimization by advanced compilers, effectively making it a domain-specific language extension for I/O. The paper describes a domain-specific I/O library for irregular block-structured applications based on the KeLP library, describes high-level transformations of the library primitives for improving performance, and describes how a high-level domain-specific optimizer for applying these transformations could be constructed rising the telescoping languages framework.

Application performance tuning is a complex process that requires assembling various types of information and correlating it with source code to pinpoint the causes of performance bottlenecks. Existing performance tools don't adequately support this process in one or more dimensions. We discuss some of the critical utility and usability issues for application-level performance analysis tools in the context of two performance tools, MHSim and HPCView, that we built to support our own work on data layout and optimizing compilers. MHsim is a memory hierarchy simulator that produces source-level information not otherwise available about memory hierarchy utilization and the causes of cache conflicts. HPCView is a tool that combines data from arbitrary sets of instrumentation sources and correlates it with program source code. Both tools report their results in scope-hierarchy views of the corresponding source code and produce their output as HTML databases that can be analyzed portably and collaboratively using a commodity browser. In addition to daily use within our group, the tools are being used successfully by several code development teams in DoD and DoE laboratories.

We present a strategy, called recursive prismatic time skewing, that increase temporal reuse at all memory hierarchy levels, thus improving the performance of scientific codes that use iterative methods. Prismatic time skewing partitions iteration space of multiple loops into skewed prisms with both spatial and temporal (or convergence) dimensions. Novel aspects of this work include: multi-dimensional loop skewing; handling carried data dependences in the skewed loops without additional storage; bi-directional skewing to accommodate periodic boundary conditions; and an analysis and transformation strategy that works inter-procedurally. We combine prismatic skewing with a recursive blocking strategy to boost reuse at all levels in a memory hierarchy. A preliminary evaluation of these techniques shows significant performance improvements compared both to original codes and to methods described previously in the literature. With an inter-procedural application of our techniques, we were able to reduce total primary cache misses of a large application code by 27% and secondary cache misses by 119%.

Parallel programs exhibit a small number of distinct data-sharing patterns. A common data-sharing pattern, migratory access, is characterized by exclusive read and write access by one processor at a time to a shared datum. We describe a family of adaptive cache coherency protocols that dynamically identify migratory shared data in order to reduce the cost of moving them. The protocols use a standard memory model and processor-cache interface. They do not require any compile-time or run-time software support. We describe implementations for bus-based multiprocessors and for shared-memory multiprocessors that use directory-based caches. These implementations are simple and would not significantly increase hardware cost. We use trace- and execution-driven simulation to compare the performance of the adaptive protocols to standard write-invalidate protocols. These simulations indicate that, compared to conventional protocols, the use of the adaptive protocol can almost halve the number of inter-node messages on some applications. Since cache coherency traffic represents a larger part of the total communication as cache size increases, the relative benefit of using the adaptive protocol also increases.

The caches within a multiprocessor typically use either a write-invalidate protocol or a write-update protocol to maintain consistency. The recently introduced MIPS R4000 processor allows operating system software to select, on a per-page basis, which multiprocessor cache coherence protocol (write-invalidate versus write-update) the hardware will use. The availability of the R4000 and the prospect of even more flexible hardware motivated us to examine the potential performance advantages of allowing user-level control over the choice of coherence protocol on a per-page basis and to ask whether more powerful hybrid protocols provide substantially more benefit. We examine the potential benefits of three classes of hybrid protocols: (1) hybrid protocols that choose statically, at the beginning of the program, between write-invalidate (WI) or write-update (WU) on a per-page basis, (2) hybrid protocols that choose statically between WI or WU for each cache block, and (3) dynamic hybrid protocols that can choose between WI or WU at each write. In order to determine how much potential benefit could be obtained by each of these protocol classes, we used trace-driven simulations to evaluate the optimal off-line protocol for each class. We found that the use of a hybrid protocol can substantially reduce the cost of memory references for most of the programs studied. A few programs can also realize large additional benefits from a per-block static hybrid protocol compared to a per-page static hybrid protocol. None of the programs, however, receive a significant additional benefit from using a dynamic hybrid protocol compared to the per-block static hybrid protocol, unless cache block sizes are larger than 16 words (64 bytes).

Multiprocessor memory reference traces provide a wealth of information on the behavior of parallel programs.We have used this information to explore the relationship between kernel-based NUMA management policies and multiprocessor memory architecture.Our trace analysis techniques employ an off-line, optimal cost policy as a baseline against which to compare on-line policies, and as a policyinsensitive tool for evaluating architectural design alternatives.We compare the performance of our optimal policy with that of three implementable policies (two of which appear in previous work), on a variety of applications, with varying relative speeds for page moves and local, global, and remote memory references.Our results indicate that a good NUMA policy must be chosen to match its machine, and confirm that such policies can be both simple and effective.They also indicate that programs for NUMA machines must be written with care to obtain the best performance.

To understand a parallel program's execution we must be able to analyze lots of information describing complex relationships among many processes. Various techniques have been used, from program replay to program animation, but each has limited applicability and the lack of a common foundation precludes an integrated solution. Our approach to parallel program analysis is based on a multiplicity of views of an execution. We use a synchronization trace captured during execution to construct a graph representation of the program's behavior. A user manipulates this representation to create and fine-tune visualizations using an integrated, programmable toolkit. Additional execution details can be recovered as needed using program replay to reconstruct an execution from an existing synchronization trace. We present a framework for describing views of a parallel program's execution, and an analysis methodology that relates a sequence of views to the program development cycle. We then describe our toolkit implementation and explain how users construct visualizations using the toolkit. Finally, we present an extended example to illustrate both our methodology and the power of our programmable toolkit.

PLATINUM is an operating system kernel with a novel memory management system for Non-Uniform Memory Access (NUMA) multiprocessor architectures. This memory management system implements a coherent memory abstraction. Coherent memory is uniformly accessible from all processors in the system. When used by applications coded with appropriate programming styles it appears to be nearly as fast as local physical memory and it reduces memory contention. Coherent memory makes programming NUMA multiprocessors easier for the user while attaining a level of performance comparable with hand-tuned programs.

The University of Washington's Eden project is a five-year research effort to design, build and use an “integrated distributed” computing environment. The underlying philosophy of Eden involves a fresh approach to the tension between these two adjectives. In briefest form, Eden attempts to support both good personal computing and good multi-user integration by combining a node machine / local network hardware base with a software environment that encourages a high degree of sharing and cooperation among its users.

For representation of terrain, an efficient alternative to dense grids is the Triangulated Irregular Network (TIN), which represents a surface as a set of non-overlapping contiguous triangular facets, of irregular size and shape. The source of digital terrain data is increasingly dense raster models produced by automated orthophoto machines or by direct sensors such as synthetic aperture radar. A method is described for automatically extracting a TIN model from dense raster data. An initial approximation is constructed by automatically triangulating a set of feature points derived from the raster model. The method works by local incremental refinement of this model by the addition of new points until a uniform approximation of specified tolerance is obtained. Empirical results show that substantial savings in storage can be obtained.