Trace-driven simulation is an important technique used in the evaluation of computer architecture innovations. However using it for studying parallel computers and applications is at best very challenging. Acquiring, representing and storing the traces are among the major issues. In this paper, we introduce path grammar guided trace compression (PGGTC) and effective address trace approximation (TA) to speedup compression and reduce trace sizes. PGGTC relies on static analysis to build rules and determine actions to guide online trace compression. Combined with gzip, PGGTC can compresses control flow traces over 330 times smaller than using gzip alone. Compared to the widely popular Sequitur algorithm alone, PGGTC with gzip is on average 40 times faster, while the traces are only 3 times bigger. PGGTC can be also used with Sequitur to double the compression ratios of Sequitur by itself and do it 14 times faster than Sequitur by itself. Address traces of parallel applications with significant randomness are often impossibly large even after being compressed with any lossless scheme including PGGTC. For effective address trace reduction, we introduce trace approximation (TA). Performance-wise similar effective addresses are generated based on very compact summaries of how the memory is accessed during each structure instance instead of compressing them. We demonstrate two approaches: selective dumping and memory signatures, to summarize the properties of effective address sequences. Both approaches are validated by feeding the generated approximate trace to cache simulators of 25 different configurations. The simulated results are very close to the simulation results based on full effective traces while the selective dumped address or memory signatures require several order of magnitude less disk space to store. In summary, we move trace-driven simulation into the realm of the feasible for larger parallel machines and applications

Many applications written in garbage collected languages have large dynamic working sets and poor data locality. We present a new system for continuously improving program data locality at run time with low overhead. Our system proactively reorganizes the heap by leveraging the garbage collector and uses profile information collected through a low-overhead mechanism to guide the reorganization at run time. The key contributions include making a case that garbage collection should be viewed as a proactive technique for improving data locality by triggering garbage collection for locality optimization independently of normal garbage collection for space, combining page and cache locality optimization in the same system, and demonstrating that sampling provides sufficiently detailed data access information to guide both page and cache locality optimization with low runtime overhead. We present experimental results obtained by modifying a commercial, state-of-the-art garbage collector to support our claims. Independently triggering garbage collection for locality optimization significantly improved optimizations benefits. Combining page and cache locality optimizations in the same system provided larger average execution time improvements (17%) than either alone (page 8%, cache 7%). Finally, using sampling limited profiling overhead to less than 3%, on average.