Name
Abstract | ||
|---|---|---|
Precise modeling of the program heap is fundamental for understanding the behavior of a program, and is thus of significant interest for many optimization applications. One of the fundamental properties of the heap that can be used in a range of optimization techniques is the sharing relationships between the elements in an array or collection. If an analysis can determine that the memory locations pointed to by different entries of an array (or collection) are disjoint, then in many cases loops that traverse the array can be vectorized or transformed into a thread-parallel version. This paper introduces several novel sharing properties over the concrete heap and corresponding abstractions to represent them. In conjunction with an existing shape analysis technique, these abstractions allow us to precisely resolve the sharing relations in a wide range of heap structures (arrays, collections, recursive data structures, composite heap structures) in a computationally efficient manner. The effectiveness of the approach is evaluated on a set of challenge problems from the JOlden and SPECjvm98 suites. Sharing information obtained from the analysis is used to achieve substantial thread-level parallel speedups. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1512475.1512485 | PASTE |
Keywords | Field | DocType |
fundamental property,program heap,optimization technique,concrete heap,composite heap structure,sharing relationship,recursive structure,heap structure,optimization application,existing shape analysis technique,sharing relation,thread level parallelism,shape analysis,recursive data structure | Data structure,Disjoint sets,Computer science,Theoretical computer science,Heap (data structure),Binary heap,Recursion,Traverse,Shape analysis (digital geometry) | Conference |
Citations | PageRank | References |
18 | 0.71 | 17 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Marron | 1 | 124 | 9.74 |
| Mario Méndez-Lojo | 2 | 272 | 10.20 |
| Manuel V. Hermenegildo | 3 | 2692 | 182.60 |
| Darko Stefanovic | 4 | 18 | 0.71 |
| Deepak Kapur | 5 | 2282 | 235.00 |