Enhancing locality in Java based irregular applications

• Author(s): Faria, Nuno Filipe Monteiro ; Silva, Rui C. ; Sobral, João Luís Ferreira
• Date: 2011
• Persistent ID: http://hdl.handle.net/1822/15113
• Origin: RepositóriUM - Universidade do Minho
• Subject(s): Locality; Irregular data structures
• Document Type: Conference Object
• Language: English

Description

Improving locality of memory accesses in current and future multi-core platforms is a key to efficiently exploit those platforms. Irregular applications, which operate on pointer-based data structures, are hard to optimize in modern computer architectures due to their intrinsic unpredictable patterns of memory accesses. In this paper we explore a memory locality-driven set of data-structures in order to attenuate the memory bandwidth limitations from typical irregular algorithms. We identify the inefficiencies in the standard Java implementation of a priority-queue as one of the main memory limitations in Prim’s Minimal Spanning Tree algorithm. We also present a priority-queue using the data layout inspired in Van Emde Boas for ordering heaps. We also implement optimizations in the graph data-structure and explore ways to efficiently combine it with the memory-efficient priority-queue. In order to improve efficiency in both case studies we had to transform the data-structures in the form of array of pointer into arrays of structures or structure of arrays.