A Compile/Run-time Environment for the Automatic Transformation of Linked List Data Structures |
| |
Authors: | H L A van der Spek S Groot E M Bakker H A G Wijshoff |
| |
Affiliation: | (1) LIACS, Leiden University, Leiden, The Netherlands |
| |
Abstract: | Irregular access patterns are a major problem for today’s optimizing compilers. In this paper, a novel approach will be presented
that enables transformations that were designed for regular loop structures to be applied to linked list data structures.
This is achieved by linearizing access to a linked list, after which further data restructuring can be performed. Two subsequent
optimization paths will be considered: annihilation and sublimation, which are driven by the occurring regular and irregular access patterns in the applications. These intermediate codes are
amenable to traditional compiler optimizations targeting regular loops. In the case of sublimation, a run-time step is involved
which takes the access pattern into account and thus generates a data instance specific optimized code. Both approaches are
applied to a sparse matrix multiplication algorithm and an iterative solver: preconditioned conjugate gradient. The resulting
transformed code is evaluated using the major compilers for the x86 platform, GCC and the Intel C compiler. |
| |
Keywords: | Optimizing compilers Parallel processing Linked list data structures |
本文献已被 SpringerLink 等数据库收录! |
|