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 until 05/31/2010)
• 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 and generalized for x86 multi-cores with NUMA abstraction.
• A prefetching scheme based on dynamically collected memory traces was devised.

• 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.

• "Analyzing Memory Performance Bottlenecks in OpenMP Programs on SMP Architectures using ccSIM" by Anita Nagarajan, M.S., North Carolina State University, Aug 2003, (last known position: Intel at Bangalore, India, Desktop Platforms Group, Graphics Core Engine team)
• "METRIC: Tracking Memory Bottlenecks via Binary Rewriting" by Jaydeep Marathe, M.S., North Carolina State University, Jun 2003 (last known position: PhD candidate North Carolina State University)
• "Hybrid online/offline optimization of Application Binaries" by Anubhav Dhoot, M.S., North Carolina State University, Jul 2004 (last known position: Microsoft, WA)
• "Trace Based Performance Characterization and Optimization" by J. Marathe, Ph.D. Thesis, North Carolina State University, May 2007 (last known position: Nvidia Compiler Group, CA)
• "Trace-Based Dependence Analysis for Speculative Loop Optimizations" by Ravi Ramaseshan, M.S. Thesis, North Carolina State University, Jun 2007 (last known position: Ph.D. student, NCSU)

"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."