12116647
Data locality enhancement by memory reduction
In this paper, we propose memory reduction as a new approach to data locality enhancement. Under this approach, we use the compiler to reduce the size of the data repeatedly referenced in a collection of nested loops. Between their reuses, the data will more likely remain in higher-speed memory devices, such as the cache. Specifically, we present an optimal algorithm to combine loop shifting, loop fusion and array contraction to reduce the temporary array storage required to execute a collection of loops. When applied to 20 benchmark programs, our technique reduces the memory requirement, counting both the data and the code, by 51% on average. The transformed programs gain a speedup of 1.40 on average, due to the reduced footprint and, consequently, the improved data locality.
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.
37872646
The Cedar System And An Initial Performance Study
In this paper, we give an overview of the Cedar mutliprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks@ . We also present a methodology f o r judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.
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.
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%.
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
11944623
An Object-Oriented Approach Using a Top-Down and Bottom-Up Process for Manipulative Action Recognition
Different from many gesture-based human-robot interaction applications, which focused on the recognition of the interactional or the pointing gestures, this paper proposes a vision-based method for manipulative gesture recognition aiming to achieve natural, proactive, and non-intrusive interaction between humans and robots. The main contributions of the paper are an object-centered scheme for the segmentation and characterization of hand trajectory information, the use of particle filtering methods for an action primitive spotting, and the tight coupling of bottom-up and top-down processing that realizes a task-driven attention filter for low-level recognition steps. In contrast to purely trajectory based techniques, the presented approach is called object-oriented w.r.t. two different aspects: it is object-centered in terms of trajectory features that are defined relative to an object, and it uses object-specific models for action primitives. The system has a two-layer structure recognizing both the HMM-modeled manipulative primitives and the underlying task characterized by the manipulative primitive sequence. The proposed top-down and bottom-up mechanism between the two layers decreases the image processing load and improves the recognition rate.
9219226
iFlow: Middleware-assisted Rendezvous-based Information Access for Mobile Ad Hoc Applications
Due to node mobility and limitations on bandwidth availability in wireless channels, there exist unique challenges towards achieving efficient and effective information access in wireless ad hoc networks with mobile nodes. In this paper, we address two critical questions: (1) How may information be accessed with the highest degree of bandwidth efficiency? and (2) How should algorithms be designed so that node mobility contributes positively towards high performance and efficiency? We present iFlow, a middleware-based framework for bandwidth-efficient and delay-aware information access for mobile ad hoc applications. We present the case of information rendezvous, where the demands for information are satisfied by the supplies in a fully distributed fashion, across third-party nodes beyond information suppliers and consumers. Such rendezvous is achieved via controlled diffusion of information from the suppliers, matched by the gleaning process on the consumers. We validate our claims using simulation and experimental results.
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.
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.