507298
Automatic tiling of iterative stencil loops
Iterative stencil loops are used in scientific programs to implement relaxation methods for numerical simulation and signal processing. Such loops iteratively modify the same array elements over different time steps, which presents opportunities for the compiler to improve the temporal data locality through loop tiling. This article presents a compiler framework for automatic tiling of iterative stencil loops, with the objective of improving the cache performance. The article first presents a technique which allows loop tiling to satisfy data dependences in spite of the difficulty created by imperfectly nested inner loops. It does so by skewing the inner loops over the time steps and by applying a uniform skew factor to all loops at the same nesting level. Based on a memory cost analysis, the article shows that the skew factor must be minimized at every loop level in order to minimize cache misses. A graph-theoretical algorithm, which takes polynomial time, is presented to determine the minimum skew factor. Furthermore, the memory-cost analysis derives the tile size which minimizes capacity misses. Given the tile size, an efficient and general <i>array-padding</i> scheme is applied to remove conflict misses. Experiments were conducted on 16 test programs and preliminary results showed an average speedup of 1.58 and a maximum speedup of 5.06 across those test programs.
833146
Experience in the Automatic Parallelization of Four Perfect-Benchmark Programs
This paper discusses the techniques used to hand-parallelize, for the Alliant FX/80, four Fortran programs from the Perfect-Benchmark suite. The paper also includes the execution times of the programs before and after the transformations. The four programs considered here were not effectively parallelized by the automatic translators available to the authors. However, most of the techniques used for hand parallelization, and perhaps all of them, have wide applicability and can be incorporated into existing translators.
5807481
Compiler algorithms for event variable synchronization
Event variable synchronization is a well known mecha nism for enforcing data dependences in a program that runs in parallel on a shared memory multiprocessor This paper presents compiler algorithms to automati cally generate event variable synchronization code Pre viously published algorithms dealt with single parallel loops in which dependence distances are constant and known by the compiler However loops in real appli cation programs are often arbitrarily nested Moreover compilers are often unable to determine dependence dis tances In contrast our algorithms generate synchro nization code based directly on array subscripts and do not require constant distances in data dependences The algorithms are designed for arbitrarily nested loops in cluding triangular or trapezoidal loops
15170626
New tiling techniques to improve cache temporal locality
Tiling is a well-known loop transformation to improve temporal locality of nested loops. Current compiler algorithms for tiling are limited to loops which are perfectly nested or can be transformed, in trivial ways, into a perfect nest. This paper presents a number of program transformations to enable tiling for a class of nontrivial imperfectly-nested loops such that cache locality is improved. We define a program model for such loops and develop compiler algorithms for their tiling. We propose to adopt odd-even variable duplication to break anti- and output dependences without unduly increasing the working-set size, and to adopt speculative execution to enable tiling of loops which may terminate prematurely due to, e.g. convergence tests in iterative algorithms. We have implemented these techniques in a research compiler, Panorama. Initial experiments with several benchmark programs are performed on SGI workstations based on MIPS R5K and R10K processors. Overall, the transformed programs run faster by 9% to 164%.
20563509
A theoretical foundation for program transformations to reduce cache thrashing due to true data sharing
Cache thrashing due to true data sharing can degrade the performance of parallel programs significantly. Our previous work showed that parallel task alignment via program transformations can be quite effective for the reduction of such cache thrashing. In this paper, we present a theoretical foundation for such program transformations. Based on linear algebra and the theory of numbers, our work analyzes the data dependences among the tasks created by a fork-join parallel program and determines at compile time how these tasks should be assigned to processors in order to reduce cache thrashing due to true data sharing. Our analysis and program transformations can be easily performed by compilers for parallel computers.
31492830
On Reducing Data Synchronization in Multiprocessed Loops
In this correspondence we present and prove the correctness of an algorithm for reducing the number of synchronized memory references to shared data elements in multiprocessed loops. Optimizing compilers for shared memory multiprocessors can use this algorithm to reduce synchronization overhead. The algorithm has been implemented as a new module in the multiprocessors version of Parafrase, the restructuring system of the University of Illinois. We present a brief discussion of experiments we performed to asses the effectiveness of this algorithm in reducing the synchronization overhead for the 61 subroutines of EISPACK, a package for computing matrix eigenvectors and eigenvalues.
5391500
A High-Throughput Overlay Multicast Infrastructure with Network Coding
Network coding has been recently proposed in information theory as a new dimension of the information multicast problem that helps achieve optimal transmission rate or cost. End hosts in overlay networks are natural candidates to perform network coding, due to its available computational capabilities. In this paper, we seek to bring theoretical advances in network coding to the practice of high-throughput multicast in overlay networks. We have completed the first real implementation of network coding in end hosts, as well as decentralized algorithms to construct the routing strategies and to perform random code assignment. Our experiences suggest that approaching maximum throughput with network coding is not only theoretically sound, but also practically promising. We also present a number of unique challenges in designing and realizing coded data dissemination, and corresponding solution techniques to address them.
5937656
Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost
As gate delays decrease faster than wire delays for each technology generation, buffer insertion becomes a popular method to reduce the interconnect delay. Several modern buffer insertion algorithms (e.g., [7, 6, 15]) are based on van Ginneken's dynamic programming paradigm [14]. However, van Ginneken's original algorithm does not control buffering resources and tends to over-buffering, thereby wasting area and power. It has been a major open problem whether it is possible to optimize slack and at the same time minimize the buffer usage.This paper settles this open problem by showing that for arbitrary integer cost functions, the problem is NP-complete. We also extend the pre-buffer slack technique [12] to minimize the buffer cost. This technique can significantly reduce the running time and memory in buffer cost minimization problem. The experimental results show that our algorithm can speed up the running time up to 17 times and reduces the memory to 1/30 of traditional best know algorithm. Finally, we show how to efficiently deal with multiway merge in buffer insertion.
16074749
A Parallel Implementation of Non-rigid Registration Using a Volumetric Biomechanical Model
Because of the accuracy required in a neurosurgical procedure, tracking intra-operative deformations is a challenging task. Furthermore, the clinical demand for fast non rigid registration will have to be met in a very near future. In this paper, we propose a patient-specific biomechanical model based on block-matching in order to register two MR images of the same patient with a parallel implementation. Compared to other intra-operative registration techniques, this method combines a viscoelastic mechanical regularization with a correlation-based iconic energy term. We first shortly present the theoretical aspects of our method (more detailed in [9]). Then we describe in more details the parallel implementation of the algorithm. Finally we present a retrospective registration study made of four pre/post operative MRI pairs.
5916479
Enumeration of 2 -connected Loopless 4 -regular Maps on the Plane
In this paper rooted (near-) 4-regular maps on the plane are counted with respect to the root-valency, the number of edges, the number of inner faces, the number of non-root vertex loops, the number of non-root vertex blocks, and the number of multi-edges. As special cases, formulae of several types of rooted 4-regular maps such as 2-connected 4-regular planar maps, rooted 2-connected (connected) 4-regular planar maps without loops are also presented. Several known results on 4-regular maps and trees of Tutte are also concluded. Finally, asymptotic formulae for the numbers of those types of maps are given.
7618781
Mining block correlations to improve storage performance
Block correlations are common semantic patterns in storage systems. They can be exploited for improving the effectiveness of storage caching, prefetching, data layout, and disk scheduling. Unfortunately, information about block correlations is unavailable at the storage system level. Previous approaches for discovering file correlations in file systems do not scale well enough for discovering block correlations in storage systems.In this article, we propose two algorithms, C-Miner and C-Miner*, that use a data mining technique called frequent sequence mining to discover block correlations in storage systems. Both algorithms run reasonably fast with feasible space requirement, indicating that they are practical for dynamically inferring correlations in a storage system. C-Miner is a direct application of a frequent-sequence mining algorithm with a few modifications; compared with C-Miner, C-Miner* is redesigned for mining block correlations by making concessions for the specific problem of long sequences in storage system traces. Therefore, C-Miner* can discover 7--109% more correlation rules within 2--15 times shorter time than C-Miner. Moreover, we have also evaluated the benefits of block correlation-directed prefetching and data layout through experiments. Our results using real system workloads show that correlation-directed prefetching and data layout can reduce average I/O response time by 12--30% compared to the base case, and 7--25% compared to the commonly used sequential prefetching scheme for most workloads.