Name
Abstract | ||
|---|---|---|
When performing aggressive optimizations and parallelization to exploit features of advanced architectures, optimizing and parallelizing compilers need to quantitatively assess the profitability of any transformations in order to achieve high performance. Useful optimizations and parallelization can be performed if it is known that certain points-to relationships would hold with high or low probabilities. For instance, if the probabilities are low, a compiler could transform programs to perform data speculation or partition iterations into threads in speculative multithreading, or it would avoid conducting code specialization. Consequently, it is essential for compilers to incorporate pointer analysis techniques that can estimate the possibility for every points-to relationship that it would hold during the execution. However, conventional pointer analysis techniques do not provide such quantitative descriptions and, thus, hinder compilers from more aggressive optimizations, such as thread partitioning in speculative multithreading, data speculations, code specialization, etc. We address this issue by proposing a probabilistic points-to analysis technique to compute the probability of every points-to relationship at each program point. A context-sensitive interprocedural algorithm has been implemented based on the iterative data flow analysis framework, and has been incorporated into SUIF and MachSUIF. Experimental results show this technique can estimate the probabilities of points-to relationships in benchmark programs with reasonable small errors, about 4.6 percent on average. Furthermore, the current implementation cannot disambiguate heap and array elements. The errors are further significantly reduced when the future implementation incorporates techniques to disambiguate heap and array elements. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/TPDS.2004.56 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
code specialization,iterative data flow analysis,array element,benchmark programs,multi-threading,points-to relationship,compilers,aggressive optimizations,conventional pointer analysis technique,multithreading,65,points-to analysis,interprocedural program analysis,parallelizing compiler,probabilistic points-to analysis technique,interprocedural probabilistic pointer analysis,parallelising compilers,speculative multithreading,benchmark testing,data speculation,data flow analysis,optimization.,optimising compilers,data speculations,speculation,optimizing compiler,certain points-to relationship,probability,program analysis,optimization,multi threading,pointer analysis | Multithreading,Pointer analysis,Computer science,Parallel computing,Speculative multithreading,Data-flow analysis,Heap (data structure),Compiler,Probabilistic logic,Benchmark (computing) | Journal |
Volume | Issue | ISSN |
15 | 10 | 1045-9219 |
Citations | PageRank | References |
13 | 0.69 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peng-Sheng Chen | 1 | 59 | 3.47 |
| Yuan-Shin Hwang | 2 | 403 | 40.55 |
| Roy Dz-ching Ju | 3 | 326 | 21.37 |
| Jenq Kuen Lee | 4 | 459 | 48.71 |