Enhancing locality in Java based irregular applications
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 pattern...
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | conferencePaper |
| Language: | eng |
| Published: |
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1822/15113 |
| Country: | Portugal |
| Oai: | oai:repositorium.sdum.uminho.pt:1822/15113 |
| Summary: | 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. |
|---|