|
Descripción
|
|
|---|---|
| The ability to accurately model the evolution of the program heap during the execution of a program is critical for many types of program optimization and verification techniques. Past work on the topic of heap analysis has identified a number of important heap properties (connectivity, shape, heap based dependence information, and region identification) that are used in many client applications (parallelization, scheduling, memory management) and has explored a range of approaches for computing this information. However, past work has been unable to compute this information with the required level of accuracy and/or has not been computationally efficient enough to make the analysis practical. The inability to compute the required heap information has limited the scope or effectiveness of many branches of research (the inability to compute the required heap information made the optimization technique impractical or severely limited its effectiveness). A general--purpose heap analysis technique is proposed. The major objective in the construction of this is to provide the range of heap information needed by the optimization applications stated above, on real world programs, in a computationally tractable manner. Keeping tractability in mind, a set of properties/information required by client optimization applications, e.g., automatic parallelization, classical scheduling, redundancy elimination transformation, stack allocation, pool allocation, object co--location or static garbage collection, is proposed. A set of design heuristics are selected to ensure that the analysis is fast and precise in the common case, and that ensure good computational performance by reducing precision in less common situations. This general approach allows the construction of an analysis that satisfies a number of key requirements for producing a practical heap analysis: The ability to handle most of the Java 1.4 language including major language features; arrays, virtual calls, interfaces, exceptions, etc., as well as the standard Java libraries. No restrictions are placed on the heap structures that are constructed; no restrictions on the recursive data structures built or how these structures are connected/shared. The analysis is able to provide precise information needed for a wide range of optimization applications; aliasing, connectivity, shape, identification of logical data structures and heap carried data dependence information. Finally, that in practice this information can be computed efficiently. The technique has been implemented and used on a range of small to medium size benchmarks from the JOlden and SPECjvm suites as well as a number of benchmarks that were developed during this work. The analysis technique is evaluated using a number of detailed case studies which focus on the heap structures that the analysis is able to identify in the program and how this information can be used in a variety of optimization techniques (focusing on vectorization/loop scheduling, thread-level parallelization and memory management). Most of these benchmarks are naturally amenable to thread--level parallelization, thus as a more empirical evaluation of the heap analysis results a detailed evaluation of the analysis is done using the results to drive the parallelization of the benchmark programs, resulting in a substantial speedup over the benchmark suites. The runtime costs of the analysis are evaluated both in terms of the total analysis time and the general scalability of the analysis. The results of this evaluation indicate that the technique presented in this thesis is indeed a general purpose solution to the heap analysis problem (at least for small/medium size programs) that can be used to efficiently compute precise and useful information for program optimization over a wide range of real world Java programs. | |
|
Internacional
|
Si |
|
ISBN
|
|
|
Tipo de Tesis
|
Doctoral |
|
Calificación
|
Sobresaliente cum laude |
|
Fecha
|
|