Search

This paper discusses the design and implementation of the first compiler that optimizes programs for power and energy using dynamic voltage scaling. The compiler identifies program regions where the CPU can be slowed down without resulting in a significant overall performance loss. For such regions the lowest CPU voltage is selected that operates correctly under the reduced clock frequency. Our trace-based compiler prototype uses the SUIF2 compiler infrastructure. For the SPECfp95 benchmark, simulation results show energy savings of up to 24% with performance penalties of less than 2.7%.

Loop tiling is an effective optimizing transformation to boost the memory performance of a program, especially for dense matrix scientific computations. The magnitude and stability of the achieved performance improvements is heavily dependent on the appropriate selection of tile sizes. Many existing tile selection algorithms try to find tile sizes which eliminate self-interference cache conflict misses, maximize cache utilization, and minimize cross-interference cache conflict misses. These techniques depend heavily on the actual layout of the arrays in memory. Array padding, an effective data layout optimization technique, is therefore incorporated by many algorithms to help loop tiling stabilize its effectiveness by avoiding “pathological” array sizes. In this paper we examine several such combined algorithms in terms of cost-benefit trade-offs, and introduce a new algorithm. The preliminary experimental results show that more precise and costly tile selection and array padding algorithms may not be justified by the resulting performance improvements since such improvements may also be achieved by much simpler and therefore less expensive strategies. The key issues in finding a good tiling algorithms are (1) to identify critical performance factors and (2) to develop corresponding performance models that allow predictions at a sufficient level of accuracy. Following this insight, we have developed a new tiling algorithms that performs better than previous algorithms in terms of execution time and stability, and generates code with a performance comparable to the best measured algorithm. Experimental results on two standard benchmark kernels for matrix multiply and LU factorization show that the new algorithm is orders of magnitude faster than the best previous algorithm without sacrificing stability and execution speed of the generated code.

Loop tiling is an effective optimizing transformation to reduce the memory access cost of a program, especially for dense matrix computations. However, the success of loop tiling is heavily dependent on the appropriate selection of tile shapes and sizes. In this paper we examine several existing tile selection algorithms in a unified framework, and quantify their performance improvements for three dense matrix computation kernels and three target architectures. In addition, a new tiling algorithm is discussed that was inspired by the observed behavior of previous algorithms. Four different quality metrics are introduced to measure the performance improvements of the algorithms over untitled versions of the three program kernels. The experiments showed that tile selection algorithms can be either very similar in performance, or significantly different depending on the chosen performance metric. For the measured test cases, our new selection algorithm had a better overall performance across the different performance metrics.

Linear-C is a data-parallel extension to C. It extends C by treating arrays (or more precisely, aggregate value) as first-class citizens. It provides activity association and segment association to control aggregate values in a computation. It also supplies new operators for aggregate values. Linear-C is designed to be intuitively simple to learn, to use, yet powerful enough to express many kinds of data parallelism. In this report we show that (1) the rationale behind our decision to choose a particular manipulation rule, and (2) the whole picture of the language in a systematic way. In the first part, we identify the trade-offs between the simplicity, the expressiveness, and the implementability of Linear-C. After that, the entire language is introduced systematically, to show the simplicity of the language model and the consistency of the manipulation rules. Finally, we conclude the report in terms of possible future research directions.

Linear-C is a data-parallel extension to C. In this report we show, by implementing Dijkstra's algorithm in Linear-C to solve the shortest-paths problem, that (1) data-parallelism in Dijkstra's algorithm can be easily expressed in Linear-C, (2) even a small amount of data parallelism can speed up the whole algorithm substantially, and (3) the algorithm, the data representation, and the efficiency are closely inter-related. Three implementations are provided, each with a different level of data parallelism exploited. The programs are explained, their time complexities are analyzed, and their strength and weakness in efficiency are compared.