Accelerated computing has increased the need to specialize how a program is parallelized depending on the target. Fully exploiting a highly parallel accelerator, such as a GPU, demands more parallelism and sometimes more levels of parallelism than a multicore CPU. OpenMP has a directive for each level of parallelism, but choosing directives for each target can incur a significant productivity cost. We argue that using the new OpenMP loop directive with an appropriate compiler decision process can achieve the same performance benefits of target-specific parallelization with the productivity advantage of a single directive for all targets. In this paper, we introduce a fully descriptive model and demonstrate its benefits with an implementation of the loop directive, comparing performance, productivity, and portability against other production compilers using the SPEC ACCEL benchmark suite. We provide an implementation of our proposal in NVIDIA's HPC compiler. It yields up to 56X speedup and an average of 1.91x-1.79x speedup compared to the baseline performance (depending on the host system) on GPUs, and preserves CPU performance. In addition, our proposal requires 60% fewer parallelism directives.

Between a problem statement and its solution as a computer simulation are several steps, from choosing a method, writing a program, compiling to machine code, making runtime decisions, and hardware execution. Here we will look at the middle three decision points. What decisions should be and must be left to the programmer? What decisions should be and must be relegated to a compiler? What decisions should be and must be left until runtime? Given my background, I will focus a great deal on the importance of compilers in supercomputing, and compare and contrast the advantages and impacts of compiler solutions to the "Performance + Portability + Productivity" problem with language and runtime solutions.

The Open ACC standard has been developed to simplify parallel programming of heterogeneous systems. Based on a set of high-level compiler directives it allows application developers to offload code regions from a host CPU to an accelerator without the need for low-level programming with CUDA or Open CL. Details are implicit in the programming model and managed by Open ACC API-enabled compilers and runtimes. However, it is still possible for the application developer to explicitly specify several performance-related details for the execution. To tune an Open ACC program and efficiently utilize available hardware resources, sophisticated performance analysis tools are required. In this paper we present a framework for detailed analysis of Open ACC applications. We describe new analysis capabilities introduced with an Open ACC tools interface and depict the integration of performance analysis for low-level programming models. As proof of concept we implemented the concept into the measurement infrastructure Score-P and the trace browser Vampir. This provides the program developer with a clearer understanding of the dynamic runtime behavior of the application and for systematic identification of potential bottlenecks.

Intel Pentium 4 floating-point capability made x86 systems viable for technical computing. AMD Opteron introduced 64-bit addressing and extended register sets. Intel EM64T added SSE3. These features have all gradually been adopted by both Intel and AMD. This evolutionary process creates temporal binary incompatibilities between AMD and Intel processors. In addition, microarchitecture differences dictate that distinct instruction sequences be used for optimal performance on each processor type. Applications that have many users, or persist in binary form across generations of processors, must execute correctly and perform well on all x86 processors.PGI compilers provide a unique solution by generating multiple versions of time-critical routines. Low-overhead dynamic selection of optimal code paths is enabled in a single PGI Unified Binary. The PGI tools infrastructure supports this scheme seamlessly. This unique feature enables uniformly high performance on both AMD and Intel processors and simplifies builds, validation, distribution and support of x86 applications.

Compiler technology includes language design, parsing, analysis, optimization, resource allocation, scheduling, and code generation. Associated tools include assemblers, linkers, debuggers, profilers, 'make', IDEs, optimized libraries, and more. While much of the technology developed over the past 50 years applies directly to embedded programming, there are key differences. Some are due to the limits of the embedded system, in particular memory size and power. Some are due to specialized architectures, such as DSPs. Others arise because of the different programming community and programming style, which is partially due to the economics of the marketplace. Here we explore some of these differences at three levels: the market, the programming environment, and the compiler.The compilers and tools marketplace for high performance workstation and cluster (HPC) systems is split between programmers and groups developing applications for internal use, and ISVs developing applications for resale. The marketplace for embedded systems is almost entirely for OEM applications, and many (or most) of the actual programmers work for the compiler vendor. This affects the forces that drive compiler and tool development and improvement.The goal for an HPC compiler is faster performance; in an embedded application, speed is not the only criterion. Getting the right mix of performance and other characteristics in an embedded system is important enough that programmers are more willing to tune the application by adjusting compiler options, performing limited rewrites, and even coding essential parts in assembler. In some instances, the target system itself is variable, and can be tuned.Focusing on just the compiler, we find many of the compiler techniques for the most performance critical embedded systems bear remarkable similarity to those used 20 or 30 years ago for the highest performance supercomputers. We also look in detail at the effectiveness of whole program analysis in both HPC and embedded compilers.

Summary form only given. As The Portland Group Compiler Technology and the Advanced Compilers Tools group within STMicroelectronics, we deliver compilers for both the high performance technical computing market, such as Summary form only given. AMD Opteron servers, and embedded DSP microcores, in particular, the ST100 from STMicroelectronics. This article explores the similarities and differences between compiler optimization strategies for these two markets. We demonstrate that many of the optimizations developed for high performance systems apply in the embedded market. For instance, compilers for both markets use vectorization for multimedia-type operations, loop unrolling, and interprocedural analysis. Software pipelining, first developed for the technical computing market, is now used for the ST100. There are also important differences; multiprocessing is quite mature in the technical computing industry, but is only beginning to be explored in the embedded market. On the other hand, optimizing for performance is not the only goal in the embedded industry; the total memory usage is also quite important. This article shows case-by-case performance improvements on the AMD Opteron and ST122 DSP for a selected set of common optimizations.

This paper presents a compiler optimization algorithm to reduce the run time overhead of array subscript range checks in programs without compromising safety. The algorithm is based on partial redundancy elimination and it incorporates previously developed algorithms for range check optimization. We implemented the algorithm in our research compiler, Nascent, and conducted experiments on a suite of 10 benchmark programs to obtain four results: (1) the execution overhead of naive range checking is high enough to merit optimization, (2) there are substantial differences between various optimizations, (3) loop-based optimizations that hoist checks out of loops are effective in eliminating about 98% of the range checks, and (4) more sophisticated analysis and optimization algorithms produce very marginal benefits.

Linear induction variable detection is usually associated with the strength reduction optimization. For restructuring compilers, effective data dependence analysis requires that the compiler detect and accurately describe linear and nonlinear induction variables as well as more general sequences. In this article we present a practical technique for detecting a broader class of linear induction variables than is usually recognized, as well as several other sequence forms, including periodic, polynomial, geometric, monotonic, and wrap-around variables. Our method is based on Factored Use-Def (FUD) chains, a demand-driven representation of the popular Static Single Assignment (SSA) form. In this form, strongly connected components of the associated SSA graph correspond to sequences in the source program: we describe a simple yet efficient algorithm for detecting and classifying these sequences. We have implemented this algorithm in Nascent, our restructuring Fortran 90+ compiler, and we present some results showing the effectiveness of our approach.

Several definitions of dependence distance can be found in the literature. A single coherent definition is the vector distance between the iteration vectors of two iterations involved in a dependence relation. Different ways to associate iteration vectors with iterations can give different dependence distances to the same program, and have different advantages.

We describe and prove algorithms to convert programs which use the Parallel Computing Forum Parallel Sections construct into Static Single Assignment (SSA) form. This proces allows compilers to apply classical scalar optimization algorithms to explicitly parallel programs. To do so, we must define what the concept of dominator and dominance frontier mean in parallel programs. We also describe how we extend SSA form to handle parallel updates and still preserve the SSA properties.

Abstract Many papers have been written dealing with the science of data dependence tests, particularly for dependence of arrays in loops; the techniques typically reduce the dependence problem to an algebraic problem, then solve the algebraic problem by an algorithm which has some desired blend of efficiency, generality or precision. While a sound theoretical basis is necessary for dependence‐based tools, these papers often leave out many implementation details. This paper addresses the engineering aspects of data dependence testing, particularly focusing on details that are necessary in any competent implementation of a data dependence test.

Abstract We report our experiences with the implementation of InterProcedural Alias Analysis (IPA) for Fortran. Implicit aliasing caused by reference parameter passing can be uncovered in a program with multiple compilation units by interprocedural analysis. For scalar objects and for full arrays, the IPA processor described here finds all alias relations. For indexed array elements and partial arrays, conservative assumptions must still be made in the absence of precise knowledge about the subscripts. IPA has been integrated into nascent, the front‐end of a Fortran translator under development at the Oregon Graduate Institute (OGI). This report explains the goals and limitations of alias analysis for conventional procedural languages with reference parameters, shows in detail the actual design and implementation of IPA, and provides algorithmic and speed improvements over the best previously known aliasing algorithms. Empirical results gathered during the analysis of large Fortran programs are also listed and discussed.

Induction variable detection is usually closely tied to the strength reduction optimization. This paper studies induction variable analysis from a different perspective, that of finding induction variables for data dependence analysis. While classical induction variable analysis techniques have been used successfully up to now, we have found a simple algorithm based on the Static Single Assignment form of a program that finds all linear induction variables in a loop. Moreover, this algorithm is easily extended to find induction variables in multiple nested loops, to find nonlinear induction variables, and to classify other integer scalar assignments in loops, such as monotonic, periodic and wrap-around variables. Some of these other variables are now classified using ad hoc pattern recognition, while others are not analyzed by current compilers. Giving a unified approach improves the speed of compilers and allows a more general classification scheme. We also show how to use these variables in data dependence testing.

A data dependence decision algorithm called the power test is introduced. The power test is a combination of the extended GCD algorithm and the Fourier-Motzkin method to eliminate variables in a system of inequalities. This is the first test that can generate the information needed for some advanced transformations, and that can handle complex simultaneous loop limits. Previous work in data dependence decision algorithms is reviewed. Some examples which motivated the development of this test are examined, including those which demonstrate the additional power of the power test. Although it may be too expensive for use as a general-purpose dependence test in a compiler, the power test has proved useful in an interactive program restructuring environment.>

Data dependence information,in some form, is used in compilers and environments for parallel computers to decide what transformations and optimizations can be applied to a program.Here we focus on loop optimiza-

Subdividing the iteration space of a loop into blocks or tiles with a fixed maximum size has several advantages. Tiles become a natural candidate as the unit of work for parallel task scheduling. Synchronization between processors can be done between tiles, reducing synchronization frequency (at some loss of potential parallelism). The shape and size of a tile can be optimized to take advantage of memory locality for memory hierarchy utilization. Vectorization and register locality naturally fits into the optimization within a tile, while parallelization and cache locality fits into optimization between tiles.

Dependence graphs can be used as a vehicle for formulating and implementing compiler optimizations. This paper defines such graphs and discusses two kinds of transformations. The first are simple rewriting transformations that remove dependence arcs. The second are abstraction transformations that deal more globally with a dependence graph. These transformations have been implemented and applied to several different types of high-speed architectures.