The Forelem framework was first introduced to optimize database queries using compiler techniques. Since its introduction, Forelem has proven to be more versatile and to be applicable beyond database applications. In this paper we show that Forelem can be used to specify parallel programs at an abstract level whilst still guaranteeing efficient parallel execution. This is achieved by a sequence of transformations that can be directly implemented as an optimizing compiler toolchain. To demonstrate this, a case study is described, k-Means clustering, for which four implementations are mechanically generated that improve standard MPI C/C++ and outperform state-of-the-art Hadoop implementations.

In the last decade, improvements on single-core performance of CPUs has stagnated. Consequently, methods for the development and optimization of software for these platforms have to be reconsidered. Software must be optimized such that the available single-core performance is exploited more effectively. This can be achieved by reducing the number of instructions that need to be executed. In this article, we show that layered database applications execute many redundant, nonessential, instructions that can be eliminated without affecting the course of execution and the output of the application. This elimination is performed using a vertical integration process which breaks down the different layers of layered database applications. By doing so, applications are being reduced to their essence, and as a consequence, transformations can be carried out that affect both the application code and the data access code which were not possible before. We show that this vertical integration process can be fully automated and, as such, be integrated in an operational workflow. Experimental evaluation of this approach shows that up to 95% of the instructions can be eliminated. The reduction of instructions leads to a more efficient use of the available hardware resources. This results in greatly improved performance of the application and a significant reduction in energy consumption.

Loop optimization and parallelization have been most successful on code using arrays exclusively. Preferably, such code does not contain indirect access and has only simple, counted loops. The use of recursive data structures makes matters even worse, and optimization of such code has been less successful. Traversal of such data structures is often done using loops with data-dependent loop conditions. In this paper, we present a compiler transformation chain that transforms pointer traversal loops into counted loops operating on arrays that are indirectly accessed. We also show that this indirect access can in some cases be eliminated if the traversed data structure is reordered in memory. This results in a representation on which many existing techniques can be applied. Our system requires monitoring of actual arguments and heap data on which loop conditions depend so that preconditions for the optimized functions can be checked. Our experiments show that this overhead is small, considering the optimization opportunities the representation of the transformed code provides, and well worth the price.

In recent years, several approaches have been proposed to use profile information in compiler optimization. This profile information can be used at the source level to guide loop transformations as well as in the backend to guide low level optimizations. At the same time, profile guided library generators have been proposed also, like Atlas, Spiral, or FFTW, that tune their routines for the underlying hardware. These approaches have led to excellent performance improvements. However, a possible drawback of these approaches is that applications are optimized using a single or a limited set of data inputs. It is well known that programs can exhibit vastly differing behaviors for different inputs. Therefore, it is not clear whether the performance numbers reported are still valid for other input than the input used to optimize the program. In this paper, we address this problem for a specific statistical compiler tuning method. We use three different platforms and several SPECint2000 benchmarks. We show that when we tune the compiler using train data, we obtain a compiler setting that still performs well for reference data. These results suggest that profile guided optimization may be more stable than is sometimes believed and that a limited number of train data sets are sufficient to obtain a well optimized program for all inputs

Finding nearly optimal optimization settings for modern compilers which can utilize a large number of optimizations is a combinatorially exponential problem. In this paper, we investigate whether in the presence of many optimization choices random generation of compiler settings can be used to obtain well performing compiler settings. We apply this random generation of compiler setting to gcc 3.3.1 which implements 54 optimizations. Our results show that this technique can be used to obtain a setting which exceeds the performance of the default optimization settings O1, O2, and O3 for each program in the SPECint95 benchmark suite. We also apply this technique to obtain a general setting which is suitable for many programs. This setting performs equally well as the default settings using significantly less options. Finally, we compare our setting with the default settings of gcc and analyze the difference.

An instruction set extension designed to accelerate multimedia applications is presented and evaluated. In the proposed complex streamed instruction (CSI) set, a single instruction can process vector data streams of arbitrary length and stride and combines complex memory accesses (with implicit prefetching), program control for vector sectioning, and complex computations on multiple data in a single operation. In this way, CSI eliminates overhead instructions (such as instructions for data sectioning, alignment, reorganization, and packing/unpacking) often needed in applications utilizing MMX-like extensions and accelerates key multimedia kernels. Simulation results demonstrate that a superscalar processor extended with CSI outperforms the same processor enhanced with Sun's VIS extension by a factor of up to 7.77 on key multimedia kernels and by up to 35% on full applications.

The Complex Streamed Instruction (CSI) set is an ISA extension targeted at multimedia applications. CSI instructions process two-dimensional data streams stored in memory, performing sectioning, data alignment and conversion between different packed data types all in hardware. It has been shown previously that CSI provides significant speedups compared to current media ISA extensions such as MMX and VIS. This paper presents a detailed design of a unit that can execute CSI instructions under the assumption that the unit is interfaced with the L1 data cache. In particular it is shown that the complex, two-dimensional, address-generation calculations can be performed in a pipelined fashion and implemented using a three-stage pipeline with acceptable delay and hardware cost.

The efficiency of sparse codes heavily depends on the size and structure of the input data. Peculiarities of the nonzero structure of each sparse matrix must be accounted for to avoid unsatisfying performance. Therefore, it is important to have an efficient analyzer that automatically determines characteristics of nonzero structures. In this paper, some efficient algorithms are presented that automatically detect particular nonzero structures.

This paper presents an overview of the activities carried out within the ESPRIT project OCEANS whose objective is to investigate and develop advanced compiler infrastructure for embedded VLIW processors. This combines high and low-level optimisation approaches within an iterative framework for compilation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

In recent years, a large number of parallel computation models have been proposed to replace the PRAM as the parallel computation model presented to the algorithm designer. Although mostly the theoretical justifications for these models are sound, and many algorithmic results where obtained through these models, little experimentation has been conducted to validate the effectiveness of these models for developing cost-effective algorithms and applications on existing hardware platforms. In this article a first attempt is made to perform a detailed experimental account on the preciseness of these models. The achieve this, three models (BSP, E-BSP, and BPRAM) were selected and validated on five parallel platforms (Cray T3E, Thinking Machines CM-5, Intel Paragon, MasPar MP-1, and Parsytec GCel). The work described in this article consists of three parts. First, the predictive capabilities of the models are investigated. Unlike previous experimental work, which mostly demonstrated a close match between the measuredd and predicted execution times, this article shows that there are several situations in which the models do not precisely predict the actual runtime behavior of an algorithm implementation. Second, a comparison between the models is provided in order to determine the model that induces that most efficient algorithms. Lastly, the performance achieved by the model-derived algorithms is compared with the performace attained by machine-specific algorithms in order to examine the effectiveness of deriving fast algorithms through the formalisms of the models.

Primitives in mathematical software are usually written and optimized by hand. With the implementation of a “sparse compiler” that is capable of automatically converting a dense program into sparse code, however, a completely different approach to the generation of sparse primitives can be taken. A dense implementation of a particular primitive is supplied to the sparse compiler, after which it can be converted into many different sparse versions of this primitive. Each version is specifically tailored to a class of sparse matrices having a specific nonzero structure. In this article, we discuss some of our experiences with this new approach.

This paper experimentally validates performance related issues for parallel computation models on several parallel platforms (a MasPar NIP-1 with 1024 processors, a 64-node GCel and a CM-5 of 64 processors).

The problem of compiler optimization of sparse codes is well known and no satisfactory solutions have been found yet. One of the major obstacles is formed by the fact that sparse programs explicitly deal with particular data structures selected for storing sparse matrices. This explicit data structure handling obscures the functionality of a code to such a degree that optimization of the code is prohibited, for instance, by the introduction of indirect addressing. The method presented in this paper delays data structure selection until the compile phase, thereby allowing the compiler to combine code optimization with explicit data structure selection. This method enables the compiler to generate efficient code for sparse computations. Moreover, the task of the programmer is greatly reduced in complexity.

Because the efficiency of sparse codes is very much dependent on the size and structure of input data, peculiarities of the nonzero structures of sparse matrices must be accounted for in order to avoid unsatisfying performance. Usually, this implies retargeting a sparse application to specific instances of the same problem. However, if characteristics of the input data are collected at compile-time and used in the data structure selection and code generation by a compiler that converts dense programs into sparse programs automatically, the complexity of sparse code development can be greatly reduced, and an efficient way for this retargeting results. Such a “sparse compiler” requires an analysis engine, which is the topic of this paper.

In this paper, a nonsymmetric sparse linear system solver based on the exploitation of multilevel parallelism is proposed. One of the main issues addressed is the application of tearing techniques to enhance large grain parallelism in a manner that maintains reasonable stability. This is accomplished by a combination of a novel reordering technique (H*) and pivoting strategy. The large grain parallelism exposed by the reordering is combined with medium (various parallel row updates strategies) and fine grain (vectorization) parallelism to allow adaptation to a wide range of multiprocessor architectures. Experimental results are presented which show the effectiveness of the reordering, as well as the stability and efficiency of the solver. 1 Introduction Several techniques have been proposed to solve large sparse systems of linear equations on parallel processors. A key task which determines the effectiveness of these techniques is the identification and exploitation of the computatio...

Most of the sophisticated optimization tools dealing with data dependence analysis, parallelization and data locality exploitation cannot provide satisfactory solutions to a number of problems because they are, in general, unable to precisely handle some complex systems of linear equations coming from dependence equations between array subscripts. For such cases, these algorithms either provide rough estimates or resort to unefficient and therefore costly enumeration strategies. In this paper, we present an efficient technique, named Fast Determination, for dealing with the enumeration problem which degrades the behavior of sophisticated algorithms. Incorporating Fast Determination would enhance the performance and accuracy of existing algorithms, and widen their scope of application.

The problem of compiler optimization of sparse codes is well known and no satisfactory solutions have been found yet. One of the major obstacles is formed by the fact that sparse programs deal explicitly with the particular data structures selected for storing sparse matrices. This explicit data structure handling obscures the functionality of a code to such a degree that the optimization of the code is prohibited, e.g. by the introduction of indirect addressing. The method presented in this paper postpones data structure selection until the compile phase, thereby allowing the compiler to combine code optimization with explicit data structure selection. Not only enables this method the compiler to generate efficient code for sparse computations, also the task of the programmer is greatly reduced in complexity.

In large-scale multiprocessors, whether loosely or tightly coupled, some memory is cheaper to access than other memory. Because direct management of memory on these machines is quite burdensome to the programmer, much research effort has been directed toward providing a shared virtual memory (SVM) interface. Clearly, the success of this endeavor depends heavily on the efficiency of page management strategies. To date, this has been primarily the responsibility of the operating system, and secondarily that of the hardware. Unfortunately, delaying page management decisions entirely until run time can lead to an unacceptable loss of efficiency, due to poor data layout and memory reference patterns that are fixed by the end of compile time. For this reason, programmer assistance has been occasionally solicited. However, this disrupts the SVM abstraction. Moreover, many of these problems may be addressable at the compiler level instead. This is especially promising for array-based languages where compiler-based, analytical technology is most mature. Surprisingly, this possibility is largely unexplored. In this paper, we discuss the issue of compiler involvement in areas ranging from loop transformations and scheduling issues, to data layout strategies, page placement decisions, access pattern analysis, and use of run time system directives.

In this paper, we give an overview of the Cedar multiprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks. We also present a methodology for judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.

In this paper we study the practical viability of the BSP model of parallel computation as proposed by Valiant.This model is intended for simulating the often considered PRAM model on more realistic parallel computers with a fixed interconnection hetwork.One of the main attributes of the BSP model is randomized routing.From experimentation on an existing parallel architecture, analytic models are derived which characterize the eiliciency of this routing scheme.This characterization leads to the identification of the bottlenecks involved in building a parallel architecture in which the BSP model can efficiently be embedded.

Regular data dependence checking onsparsecodesusually resultsin very conservative estimates of actual dependences that will occur at run-time.Clearly, this is caused by the usage of compact data structures that are necessary to exploit sparsity in order to reduce storage requirements and computational time.However, if the compiler is presented with dense code and automatically converts it into code that operates on sparse data structures, then the dependence information obtained by analysis on the original code can be used to exploit potential concurrency inthe generated code.In this paper we present synch~onization generating and manipulating techniques that are based on this concept. PreliminariesIn this section we summarize data dependence theory, and discuss the elimination of dependence by automatic conversion into sparse code.

The authors study the instrumentation perturbations of software event tracing on the Alliant FX/80 vector multiprocessor in sequential, vector, concurrent, and vector-concurrent modes. Based on experimental data, they derive a perturbation model that can approximate true performance from instrumented execution. They analyze the effects of instrumentation coverage, (i.e., the ratio of instrumented to executed statements), source level instrumentation, and hardware interactions. The results show that perturbations in execution times for complete trace instrumentations can exceed three orders of magnitude. With appropriate models of performance perturbation, these perturbations in execution time can be reduced to less than 20% while retaining the additional information from detailed traces. In general, it is concluded that it is possible to characterize perturbations through simple models. This permits more detailed, accurate instrumentation than traditionally believed possible.>

As the diversity of novel architectures expands rapidly there is a growing interest in studying the behavior of these architectures for computations arising in different applications. There has been significant efforts in evaluating the performance of supercomputers on typical dense computations, and several packages for this purpose have been developed, such as the Linpack benchmark, the Lawrence Livermore Loops, and the Los Alamos Kernels. On the other hand there has been little effort put into evaluating the performance of these architectures on the more complicated and perhaps more important sparse computations. In this paper a package is proposed to fill this gap. Its goal is not only to evaluate the performance of supercomputers on sparse computations, but also to analyze the machine-algorithm interaction.

It is demonstrated how the behavior of a cache-based multi-vector-processor memory system can be systematically characterized and its performance experimentally correlated with key features of the address stream. The approach is based on the definition of a family of parameterized kernels used to explore specific aspects of the memory system's performance. The empirical results from this kernel suite provide the data from which architectural or algorithmic characteristics can be studied. The results of applying the approach to an Alliant FX/8 are presented and evaluated.>

In this paper we discuss the performance prediction of Fortran constructs commonly found in numerical scientific computing. Although the approach is applicable to multi-processors in general, within the scope of the paper we will concentrate on the Alliant FX/8 multiprocessor. The techniques proposed involve a combination of empirical observations, architectural models and analytical techniques, and exploits earlier work on data locality analysis and empirical characterization of the behavior of memory systems. The Lawrence Livermore Loops are used as a test-case to verify the approach.

The speed and efficiency of the memory system is a key limiting factor in the performance of supercomputers. Consequently, one of the major concerns when developing a high-performance code, either manually or automatically, is determining and characterizing the influence of the memory system on performance in terms of algorithmic parameters. Unfortunately, the performance data available to an algorithm designer such as various benchmarks and, occasionally, manufacturer-supplied information, e.g. instruction timings and architecture component characteristics, are rarely sufficient for this task. In this paper, we discuss a systematic methodology for probing the performance characteristics of a memory system via a hierarchy of data-movement kernels. We present and analyze the results obtained by such a methodology on a cache-based multi-vector processor (Alliant FX/8). Finally, we indicate how these experimental results can be used for predicting the performance of simple Fortran codes by a combination of empirical observations, architectural models and analytical techniques.

We examine the problem of evaluating performance of supercomputer architectures on sparse (matrix) computations and lay out the details of a benchmark package for this problem. Whereas there already exists a number of benchmark packages for scientific computations, such as the Livermore Loops, the Linpack benchmark and the Los Alamos benchmark, none of these deals with the specific nature of sparse computations. Sparse matrix techniques are characterized by the relatively small number of operations per data element and the irregularity of the computation. Both facts may significantly increase the overhead time due to memory traffic. For this reason, the performance evaluation of sparse computations should not only take into account the CPU performance but also the degradation of performance caused by high memory traffic. Furthermore, sparse matrix techniques comprise a variety of different types of basic computations. Taking these considerations into account we propose a benchmark package that consists of several independent modules, each of which has a distinct role.

Linear skewing schemes were introduced by Kuck et al. in the nineteen sixties, to provide a simple class of storage mappings for N × N matrices for use in vector processors with a large number of memory banks. Conditions on linear skewing schemes that guarantee conflict-free access to rows, columns, and/or (anti-) diagonals are usually presented in terms of conditions on so-called d-ordered vectors. We shall argue that these formulations are mathematically imprecise, and revise and extend the existing theory. Several claims are proved to bound the minimum number of memory banks needed for successful linear skewing by, e.g., the smallest prime number ≥ N.

The use of parallel memories in SIMD machines requires special data mappings, known as ``skewing schemes,'' for storing matrices for the purposes of efficient vector computations. Some schemes have explicitly been implemented in current super-computers. Periodic skewing schemes are of particular interest because they have a regular structure and can be represented by simple formulas. In this paper we show that periodic skewing schemes have an elegant foundation in the mathematical theory of integral lattices and Z-modules, which leads to insightful proofs of a number of general properties of periodic skewing schemes in all dimensions.