CAREER: Exploiting Binary Rewriting to Analyze and Alleviate Memory Bottlenecks for Scientific Applications

• funded by: NSF (award abstract)
• funding level: $400,000 (+$35,000 cost sharing by NC State COE+CSC)
• duration: 06/01/2003 - 05/31/2008 (no-cost extension till 05/31/2009)
• PI: Frank Mueller
• prior funding: FRPD and SPAN

Today, high-performance clusters of shared-memory multiprocessors (SMPs) are employed to cope with large data sets for scientific applications. On these SMPs, hybrid programming models combing message passing and shared memory are often less efficient than pure message passing although the former fits SMP architectures more closely.

The objective of this work is to determine the sources of inefficiencies in utilizing memory hierarchies of SMPs and to optimize memory behavior. The novelty lies in the reliance on dynamic binary rewriting, i.e., performance analysis and tuning are performed on the application while it executes.

The technical challenges are to

1. develop a framework for dynamic binary rewriting,
2. determine coherence traffic resulting in misses for non-deterministic orders of executions in the presence of parallelism,
3. identify memory bottlenecks,
4. determine data dependencies between data references for hot-spots for binaries,
5. study the potential for memory-improving program transformations on the executing binary and
6. evaluate the merits of optimizations for large-scale benchmarks among others.

The key intellectual merit is in providing additional, dynamic optimizations for long-running applications. The broader impact of this work lies in its contribution to counter the increasing gap between processor and main memory speeds by fully exploiting software optimizations.

• Preliminary results are reported on the binary rewiting framework to extract Partial Data Traces from running programs.
• Preliminary results on optimizations are reported in Detecting Memory Performance Bottlenecks via Binary Rewriting.
• A more comprehensive write-up for uniprocessors is given in METRIC: Tracking Down Inefficiencies in the Memory Hierarchy via Binary Rewriting. An extended journal version refines the approach and shows the superiority of our online compression scheme for regular references over the most advanced compression techniques to date.
• Memory access metrics and optimizations are described in Identifying and Exploiting Spatial Regularity in Data Memory References.
• The handling of shared-memory multi-processors and coherence traffic is dicussed in Detailed Cache Coherence Characterization for OpenMP Benchmarks. An extended journal version provides additional experiments.
• A subsequent paper details the efficient generation of partial (lossy) address traces through hardware support, which allows cache coherence analysis to be performed without the high overhead of software instrumentation. An extended journal version provides additional experiments to assess a variety of tracing techniques and discusses additiona traceoffs of hardware and software tracing.
• A novel technique to improve first-touch page placement based on low-cost hardware profiling was developed for the SGI Altix.

• The base protocol is specified in A Log(n) Multi-Mode Locking Protocol for Distributed Systems.
• Algorithmic details and extended result are presented in A Log(n) Multi-Mode Locking Protocol for Distributed Systems.
• The work is summarized in a journal article in Scalable Hierarchical Locking for Distributed Systems.

"Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation."