33433140
Optimal skewed tiling for cache locality enhancement
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. Hence, exploitation of temporal data locality can lead to significantly improved cache performance. This paper shows that, to optimally tile iterative stencil loops, the imperfectly nested inner loops must be realigned such that they can be minimally skewed across different time steps. A memory-reference cost analysis proves that the number of cache misses is minimized when the skewing is minimum. A graph-theoretical algorithm, which takes polynomial time, is presented to determine the minimum skew factors for a given nesting of iterative stencil loops.
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%.
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.
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.
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.
378727
Position Variance, Recurrence and Perceptual Learning
Stimulus arrays are inevitably presented at different positions on the retina in visual tasks, even those that nominally require fixation. In particular, this applies to many perceptual learning tasks. We show that perceptual inference or discrimination in the face of positional variance has a structurally different quality from inference about fixed position stimuli, involving a particular, quadratic, non-linearity rather than a purely linear discrimination. We show the advantage taking this non-linearity into account has for discrimination, and suggest it as a role for recurrent connections in area VI, by demonstrating the superior discrimination performance of a recurrent network. We propose that learning the feedforward and recurrent neural connections for these tasks corresponds to the fast and slow components of learning observed in perceptual learning tasks.
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.
13022636
A Neural Model of Contour Integration in the Primary Visual Cortex
Experimental observations suggest that contour integration may take place in V1. However, there has yet to be a model of contour integration that uses only known V1 elements, operations, and connection patterns.This article introduces such a model, using orient ation selective cells, local cortical circuits, and horizontal intracortical connections. The model is composed of recurrently connected excitatory neurons and inhibitory interneurons, receiving visual input via oriented receptive fields resembling those found in primary visual cortex. Intracortical interactions modify initial activity patterns from input, selectively amplifying the activities of edges that form smooth contours in the image. The neural activities produced by such interactions are oscillatory and edge segments within a contour oscillate in synchrony. It is shown analytically and empirically that the extent of contour enhancement and neural synchrony increases with the smoothness, length, and closure of contours, as observed in experiments on some of these phenomena. In addition, the model incorporates a feedback mechanism that allows higher visual centers selectively to enhance or suppress sensitivities to given contours, effectively segmenting one from another. The model makes the testable prediction that the horizontal cortical connections are more likely to target excitatory (or inhibitory) cells when the two linked cells have their preferred orientation aligned with (or orthogonal to) their relative receptive field center displacements.
566308
Reducing Energy Consumption of Disk Storage Using Power-Aware Cache Management
Reducing energy consumption is an important issue for data centers. Among the various components of a data center, storage is one of the biggest consumers of energy. Previous studies have shown that the average idle period for a server disk in a data center is very small compared to the time taken to spin down and spin up. This significantly limits the effectiveness of disk power management schemes. This paper proposes several power-aware storage cache management algorithms that provide more opportunities for the underlying disk power management schemes to save energy. More specifically, we present an off-line power-aware greedy algorithm that is more energy-efficient than Belady’s off-line algorithm (which minimizes cache misses only). We also propose an online power-aware cache replacement algorithm. Our trace-driven simulations show that, compared to LRU, our algorithm saves 16% more disk energy and provides 50% better average response time for OLTP I/O workloads. We have also investigated the effects of four storage cache write policies on disk energy consumption.
31862696
Basic Topological Models for Spatial Entities in 3-Dimensional Space
In recent years, models of spatial relations, especially topological relations, have attracted much attention from the GIS community. In this paper, some basic topologic models for spatial entities in both vector and raster spaces are discussed.It has been suggested that, in vector space, an open set in 1-D space may not be an open set any more in 2-D and 3-D spaces. Similarly, an open set in 2-D vector space may also not be an open set any more in 3-D vector spaces. As a result, fundamental topological concepts such as boundary and interior are not valid any more when a lower dimensional spatial entity is embedded in higher dimensional space. For example, in 2-D, a line has no interior and the line itself (not its two end-points) forms a boundary. Failure to recognize this fundamental topological property will lead to topological paradox. It has also been stated that the topological models for raster entities are different in Z2 and R2. There are different types of possible boundaries depending on the definition of adjacency or connectedness. If connectedness is not carefully defined, topological paradox may also occur. In raster space, the basic topological concept in vector space—connectedness—is implicitly inherited. This is why the topological properties of spatial entities can also be studied in raster space. Study of entities in raster (discrete) space could be a more efficient method than in vector space, as the expression of spatial entities in discrete space is more explicit than that in connected space.