Data locality optimization of interference graphs based on polyhedral computations

Motallebi, Hassan; Parsa, Saeed
September 2012
Journal of Supercomputing;Sep2012, Vol. 61 Issue 3, p935
Academic Journal
In achieving high performance on modern architectures it is critical to make effective use of the memory hierarchy. There are compiler-directed locality enhancement techniques that allow the transformation of program to achieve a higher locality: loop transformations, which are constrained by data dependences and data layout transformations, which have a global impact on the program locality. Due to these drawbacks, there must be a unification of the two techniques to achieve the benefits of both. In this paper, a novel unification of these techniques is presented. Using a model based on parameterized polyhedra and introducing new concepts, we propose a data locality optimization algorithm. In comparison with the other approaches, the technique proposed is capable of solving more conflicts and optimizing more references, a subtle way is proposed to optimize incompatible references to the same array, in the same loop, and also references in a cycle in the interference graph. Using parameterized cost functions, our technique estimates the importance of each sub-graph and optimizes data locality. Our experimental results show a significant improvement over the prior approaches.


Related Articles

  • HSM debate rages: Cost versus user ease. Yager, Tom; Borck, James R. // InfoWorld;02/26/2001, Vol. 23 Issue 9, p56 

    Presents information on the hierarchical storage management (HSM). Strategy of HSM; Factors that will affect the success of HSM; Cause of the hesitation of companies to HSM; Benefits offered by HSM; Cost-effectiveness of HSM strategy.

  • Region-based parallelization of irregular reductions on explicitly managed memory hierarchies. Seonggun Kim; Hwansoo Han; Kwang-Moo Choe // Journal of Supercomputing;Apr2011, Vol. 56 Issue 1, p25 

    Multicore architectures are evolving with the promise of extreme performance for the classes of applications that require high performance and large bandwidth of memory. Irregular reduction is one of important computation patterns for many complex scientific applications, and it typically...

  • The Cache Assignment Problem and Its Application to Database Buffer Management. Levy, Hanoch; Messinger, Ted G.; Morris, Robert J. T. // IEEE Transactions on Software Engineering;Nov96, Vol. 22 Issue 11, p827 

    Given N request streams and L ≤ N LRU caches, the cache assignment problem asks to which cache each stream should be assigned in order to minimize the overall miss rate. An efficient solution to this problem is provided, based on characterizing each stream using the stack reference model...

  • Hierarchical Binary Set Partitioning in Cache Memories. Zarandi, Hamid Reza; Sarbazi-Azad, Hamid // Journal of Supercomputing;Feb2005, Vol. 31 Issue 2, p185 

    In this paper, a new cache placement scheme is proposed to achieve higher hit ratios with respect to the two conventional schemes namely set-associative and direct mapping. Similar to set-associative, in this scheme, cache space is divided into sets of different sizes. Hence, the length of tag...

  • Optimizing the Management of Reference Prediction Table for Prefetching and Prepromotion. Junjie Wu; Xuejun Yang // Journal of Computers;Feb2010, Vol. 5 Issue 2, p242 

    Prefetching and prepromotion are two important techniques for hiding the memory access latency. Reference prediction tables (RPT) plays a significant role in the process of prefetching or prepromoting data with linear memory access patterns. The traditional RPT management, LRU replacement...

  • Microsoft's Quiet Little Database. Taschek, John // PC Week;02/15/99, Vol. 16 Issue 7, p73 

    Comments on Microsoft Corp.'s in-memory database (IMDB), which is being developed along with Component Object Model (COM)+. Performance gains that IMDBs offer over relational databases; How IMDBs will impact the enterprise resource planning market; The impact Microsoft's IMDB will have on...

  • Combating I-O bottleneck using prefetching: model, algorithms, and ramifications. Verma, Akshat; Sen, Sandeep // Journal of Supercomputing;Aug2008, Vol. 45 Issue 2, p205 

    Multiple memory models have been proposed to capture the effects of memory hierarchy culminating in the I-O model of Aggarwal and Vitter (Commun. ACM 31(9):1116–1127, []). More than a decade of architectural advancements have led to new features that are not captured in the I-O...

  • Enhancing GPU parallelism in nature-inspired algorithms. Cecilia, José; Nisbet, Andy; Amos, Martyn; García, José; Ujaldón, Manuel // Journal of Supercomputing;Mar2013, Vol. 63 Issue 3, p773 

    We present GPU implementations of two different nature-inspired optimization methods for well-known optimization problems. Ant Colony Optimization (ACO) is a two-stage population-based method modelled on the foraging behaviour of ants, while P systems provide a high-level computational modelling...

  • Effective Monitoring Memory Operations for Dynamic Race Detection through Hierarchical Filtering Method. Ok-Kyoon Ha; Yong-Kee Jun // International Journal of Multimedia & Ubiquitous Engineering;2014, Vol. 9 Issue 4, p199 

    Data races are the hardest defect to handle in multithreaded programs due to the non-deterministic interleaving of concurrent threads. It incurs the expensive costs of dynamic data race detection to monitor all of memory operations to shared memory locations. This paper presents a hierarchical...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics