Name
Abstract | ||
|---|---|---|
Locality analysis is important since accessing memory is much slower than computing. Compile-time locality analysis can provide detailed program-level feedback for compilers or runtime systems faster than trace-based locality analysis.
In this paper, we describe a new approach to locality analysis based on static parallel sampling. A compiler analyzes loop-based code and generates sampler code which is run to measure locality. Our approach can predict precise cache line granularity miss ratio curves for complex loops with non-linear array references and even branches. The precision and overhead of static sampling are evaluated using PolyBench and a bit-reversal loop. Our result shows that by randomly sampling 2% of loop iterations, a compiler can construct almost exact miss ratio curves as trace based analysis. Sampling 0.5% and 1% iterations can achieve good precision and efficiency with an average 0.6% to 1% the time of tracing respectively. Our analysis can also be parallelized. The analysis may assist program optimization techniques such as tiling, program co-location, cache hint selection and help to analyze write locality and parallel locality.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3192366.3192402 | PLDI |
Keywords | Field | DocType |
Static analysis, locality, program specialization | Program optimization,Locality,Cache,Computer science,CPU cache,Static analysis,Parallel computing,Compiler,Theoretical computer science,Sampling (statistics),Tracing | Conference |
Volume | Issue | ISSN |
53 | 4 | 0362-1340 |
ISBN | Citations | PageRank |
978-1-4503-5698-5 | 1 | 0.35 |
References | Authors | |
33 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| dong | 1 | 6 | 1.77 |
| Fangzhou Liu | 2 | 125 | 10.67 |
| Chen Ding | 3 | 422 | 28.21 |
| Sreepathi Pai | 4 | 177 | 9.58 |