The Parallel Research Kernels (PRK) are a tool to study parallel architectures and runtime systems from an application perspective. It provides paper and pencil specifications and reference implementations of elementary operations covering a broad range of parallel application patterns. The current PRK are trivially statically load-balanced. Future large-scale systems will require dynamic load balancing for unsteady workloads and for handling system/network fluctuations and non-uniformities. We present a new PRK that requires dynamic load balancing, and provides knobs for controlling workload behavior. It is inspired by Particle-In-Cell (PIC) applications and captures one of the computational patterns in such codes. We give a detailed specification of the new PRK, highlighting the challenges and corresponding design choices that make it compact, arbitrarily scalable and self-verifying. We also present implementations of the PIC PRK in MPI, with and without application-specific load balancing, and show an implementation with runtime-assisted load balancing provided by Adaptive MPI features. Our experimental results provide an illustrative example of how PIC can be used to assess the load-balancing capabilities of modern parallel runtimes.

NAS parallel benchmarks (NPB) are a set of applications commonly used to evaluate parallel systems. We use the NPB-OpenMP version to examine the performance of the Intel's new Xeon Phi co-processor and focus in particular on the many core aspect of the Xeon Phi architecture. A first analysis studies the scalability up to 244 threads on 61 cores and the impact of affinity settings on scaling. It also compares performance characteristics of Xeon Phi and traditional Xeon CPUs. The application of several well-established optimization techniques allows us to identify common bottlenecks that can specifically impede performance on the Xeon Phi but are not as severe on multi-core CPUs. We also find that many of the OpenMP-parallel loops are too short (in terms of the number of loop iterations) for a balanced execution by 244 threads. New or redesigned benchmarks will be needed to accommodate the greatly increased number of cores and threads. At the end, we summarize our findings in a set recommendations for performance optimization for Xeon Phi.

The NAS Parallel Benchmarks (NPB) are a well-known suite of benchmarks that proxy scientific computing applications. They specify several problem sizes that represent how such applications may run on different sizes of HPC systems. However, even the largest problem (class F) is still far too small to exercise properly a petascale supercomputer. Our work shows how one may scale the Block Tridiagonal (BT) NPB from today's published size to petascale and exascale computing systems. In this paper we discuss the pros and cons of various ways of scaling. We discuss how scaling BT would impact computation, memory access, and communications, and highlight the expected bottleneck, which turns out to be not memory or communication bandwidth, but network latency. Two complementary ways are presented to overcome latency obstacles. We also describe a practical method to gather approximate performance data for BT at exascale on actual hardware, without requiring an exascale system.

SUMMARY A message passing, distributed‐memory parallel computer on a chip is one possible design for future, many‐core architectures. We discuss initial experiences with the Intel Single‐chip Cloud Computer research processor, which is a prototype architecture that incorporates 48 cores on a single die that can communicate via a small, shared, on‐die buffer. The experiment is to port a state‐of‐the‐art, distributed‐memory, dense matrix library, Elemental, to this architecture and gain insight from the experience. We show that programmability addressed by this library, especially the proper abstraction for collective communication, greatly aids the porting effort. This enables us to support a wide range of functionality with limited changes to the library code. Copyright © 2011 John Wiley & Sons, Ltd.

Basic data flow patterns that we call \textbf{performance idioms}, such as stream, transpose, reduction, random access and stencil, are common in scientific numerical applications. We hypothesize that a small number of idioms can cover most programming constructs that dominate the execution time of scientific codes and can be used to approximate the application performance. To check these hypotheses, we proposed an automatic idioms recognition method and implemented the method, based on the open source compiler Open64. With the NAS Parallel Benchmark (NPB) as a case study, the prototype system is about $90%$ accurate compared with idiom classification by a human expert. Our results showed that the above five idioms suffice to cover $100%$ of the six NPB codes (MG, CG, FT, BT, SP and LU). We also compared the performance of our idiom benchmarks with their corresponding instances in the NPB codes on two different platforms with different methods. The approximation accuracy is up to $96.6%$. The contribution is to show that a small set of idioms can cover more complex codes, that idioms can be recognized automatically, and that suitably defined idioms may approximate application performance.

Basic data flow patterns which we call idioms, such as stream, transpose, reduction, random access and stencil, are common in scientific numerical applications. We hypothesize that a small number of idioms can cover most programming constructs that dominate the execution time of scientific codes and can be used to approximate the application performance. In this paper, we start with a manual analysis of code coverage on the NAS Parallel Benchmark (NPB) and find that five idioms suffice to cover 100% of the NPB codes. We then compare the performance of our idiom benchmarks and their corresponding instances in different NPB codes on two different platforms and find that they differ by about 30%. To check the hypotheses with real applications further, we propose an automatic idioms recognition method, implement the method basing on the open source compiler Open64, and verify the prototype system with the previous manual analysis results.

Intel's 80-core terascale processor was the first generally programmable microprocessor to break the Teraflops barrier. The primary goal for the chip was to study power management and on-die communication technologies. When announced in 2007, it received a great deal of attention for running a stencil kernel at 1.0 single precision TFLOPS while using only 97 Watts. The literature about the chip, however, focused on the hardware, saying little about the software environment or the kernels used to evaluate the chip. This paper completes the literature on the 80-core terascale processor by fully defining the chip's software environment. We describe the instruction set, the programming environment, the kernels written for the chip, and our experiences programming this microprocessor. We close by discussing the lessons learned from this project and what it implies for future message passing, network-on-a-chip processors.

The growing gap between sustained and peak performance for scientific applications is a well-known problem in high-performance computing. The recent development of parallel vector systems offers the potential to reduce this gap for many computational science codes and deliver a substantial increase in computing capabilities. This paper examines the intranode performance of the NEC SX-6 vector processor, and compares it against the cache-based IBM Power3 and Power4 superscalar architectures, across a number of key scientific computing areas. First, we present the performance of a microbenchmark suite that examines many low-level machine characteristics. Next, we study the behavior of the NAS Parallel Benchmarks. Finally, we evaluate the performance of several scientific computing codes. Overall results demonstrate that the SX-6 achieves high performance on a large fraction of our application suite and often significantly outperforms the cache-based architectures. However, certain classes of applications are not easily amenable to vectorization and would require extensive algorithm and implementation reengineering to utilize the SX-6 effectively. Copyright © 2005 John Wiley & Sons, Ltd.

Summary form only given. We describe a new suite of computational benchmarks that models applications featuring multiple levels of parallelism. Such parallelism is often available in realistic flow computations on systems of meshes, but had not previously been captured in benchmarks. The new suite, named NPB (NAS parallel benchmarks) multizone, is extended from the NPB suite, and involves solving the application benchmarks LU, BT and SP on collections of loosely coupled discretization meshes. The solutions on the meshes are updated independently, but after each time step they exchange boundary value information. This strategy provides relatively easily exploitable coarse-grain parallelism between meshes. Three reference implementations are available: one serial, one hybrid using the message passing interface (MPI) and OpenMP, and another hybrid using a shared memory multilevel programming model (SMP+OpenMP). We examine the effectiveness of hybrid parallelization paradigms in these implementations on three different parallel computers. We also use an empirical formula to investigate the performance characteristics of the hybrid parallel codes.

Summary form only given. The NAS Grid Benchmarks (NGB) are a collection of synthetic distributed applications designed to rate the performance and functionality of computational grids. We compare several implementations of the NGB to determine programmability and efficiency of NASA's Information Power Grid (IPG), whose services are mostly based on the Globus toolkit. We report on the overheads involved in porting existing NGB reference implementations to the IPG. No changes were made to the component tasks of the NGB.

The growing gap between sustained and peak performance for scientific applications is a well-known problem in high end computing. The recent development of parallel vector systems offers the potential to bridge this gap for many computational science codes and deliver a substantial increase in comput-ing capabilities. This paper examines the intranode performance of the NEC SX-6 vector processor and the cache-based IBM Power3/4 superscalar architectures across a number of scientific computing areas. First, we present the performance of a microbenchmark suite that examines low-level machine characteristics. Next, we study the behavior of the NAS Parallel Benchmarks. Finally, we evaluate the performance of several scientific computing codes. Results demonstrate that the SX-6 achieves high performance on a large fraction of our applications and often significantly outperforms the cache-based architectures. However, certain applications are not easily amenable to vectorization and would require extensive algorithm and implementation reengineering to utilize the SX-6 effectively.

We derive tight bounds on cache misses for evaluation of explicit stencil operators on rectangular grids. Our lower bound is based on the isoperimetric property of the discrete crosspolytope. Our upper bound is based on a good surface-to-volume ratio of a parallelepiped spanned by a reduced basis of the interference lattice of a grid. Measurements show that our algorithm typically reduces the number of cache misses by a factor of three, relative to a compiler optimized code. We show that stencil calculations on grids whose interference lattices have a short vector feature abnormally high numbers of cache misses. We call such grids unfavorable and suggest to avoid these in computations by appropriate padding. By direct measurements on a MIPS R10000 processor we show a good correlation between abnormally high numbers of cache misses and unfavorable three-dimensional grids.

We present a benchmark suite for computational grids in this paper. It is based on the NAS Parallel Benchmarks (NPB) and is called the NAS Grid Benchmark (NGB). We present NGB as a data flow graph encapsulating an instance of an NPB code in each graph node, which communicates with other nodes by sending/receiving initialization data. These nodes may be mapped to the same or different Grid machines. Like NPB, NGB specifies several different classes (problem sizes). NGB also specifies the generic Grid services that are sufficient for running the suite. The implementor has the freedom to choose any Grid environment. We describe a reference implementation in Java and present some scenarios for using NGB.

Observationsshow that fine-grain software pipelines on

A comparison is made between several domain decomposition strategies for the solution of threedimensional partial differential equations on a MIMD distributed memory parallel computer.The grids used are structured, and the numerical algorithm iv ADI.Important implementation issues regarding load balancing, storage requirements, network latency, and overlap of computations and communications are discussed.Results of the solution of the threedimensional heat equation on the Intel iPSC/860 ape presented for the th?'ee most viable methods.It is found that the Bruno-Cappeilo decomposition delivers optimal computational speed through an almost complete elimination of processor idle time, while providing good memory eficiency.plicit methods.Numerical solution of PDE's typically involves more or less the same operations for all the points in a computational grid used to discretize the problem space.Consequently, domain decomposition is the natural way of creating separate tasks for a parallel computer: a roughly equal number of grid points is assigned to each processor.Depending on the type of implicit algorithm chosen, some domain decompositions perform better than others.Efficiency is also affected by hardware parameters (e.g.network latency and bandwidth, and processor memory) and operating model (e.g.MIMD, SIMD).In this paper we compare three viable domain decompositions for the solution of @ 1993 ACM 0-8186-4340-4/93/0011 $1.50 c specific heat, and k the conduction tensor.Assuming k to be a constant scalar, i.e. k = kI, we get Equation (2) is subsequently discretized using central differencing in space and the 0-method in time: (1 -*[(U)2 +(6;)2 + (6:)2])AT = (3) 'k [(6:)2+ (6;)2 + (6:)2]T.p Here &< signifies the central difference operator in the xi-direction, T is the temperature, AT its te"mporal increment, and h is the size of the time step.The Permission to copy wilhout fee all or pan of this material is granted, provided that the copies m not made or ditibuwd for dimcl -ma advantage, the ACM copyright mxice and the title of tk publication and 102 h date appear, and notice is given Ihat copying is by permissmn cl the Association for Compning Machinery.To copy ciherwise, or to mp"blish, requires a fee andfor Spedc fermis$ion.