Automatic Restructuring of Linked Data Structures

Date Added: Sep 2009
Format: PDF

The memory subsystem is one of the major performance bottlenecks in modern computer systems. While much effort is spent on the optimization of codes which access data regularly, not all codes will do so. Programs using pointer linked data structures are notorious for producing such so called irregular memory access patterns. In this paper, the authors present a compilation and run-time framework that enables fully automatic restructuring of pointer-linked data structures for type-unsafe languages, such as C.