View source for "Data Locality Enhancement of Dynamic Simulations for Exascale Computing," Xipeng Shen, College of William and Mary


== Motivation ==

Memory performance is key to maximizing computing efficiency in the
era of Chip Multiprocessors (CMP) due to the growing disparity between
the slowly expanded memory bandwidth and the rapidly increased demands
for data by processors. The importance is underlined by the trend
towards exascale computing, in which, the processors are expected to
each contain hundreds or thousands of (heterogeneous) cores.

Computer simulation is important for scientific research in many
disciplines. Many such programs are complex, and transfer a large
amount of data in a dynamically changing pattern. Unfortunately,
today's computer systems lack support for high degree of memory
transfer.  Although hardware cache can reduce the amount of memory
access, scientific programs---especially those with dynamic reference
patterns---are among the most difficult to cache. The issue has become
more critical than before in CMP systems, where certain on-chip
storage and off-chip pin bandwidth are shared among cores on a single
chip. The sharing causes co-running threads to compete for the limited
cache and bandwidth, further worsening the issue of memory
performance. Many traditional optimization techniques, being oblivious
to the new features, lose their effectiveness. It indicates that it is
important for existing locality optimizations to evolve to match with
the new features of multicore and manycore memory hierarchy,
especially for dynamic scientific applications.


== Summary of Proposed Techniques ==

In this research, the PI proposes to improve memory performance of
dynamic applications by developing two new techniques that are
tailored especially for the emerging features of CMP. 

The first is asynchronous streamlining. It analyzes the memory
reference patterns of an application during runtime and regulates both
control flows and memory references on the fly. Its underlying
observation is that both irregular memory references and control flows
essentially stem from an inferior mapping between threads and data
(data locations for the former; data values for the latter). It
enhances the mapping through three components. The first includes a set of transformations
for realizing new thread-data mappings. Its core consists of two
primary mechanisms, data relocation and reference redirection, which
work hand in hand to provide a spectrum of solutions suitable for
various scenarios. There are two key factors for the transformations
to work effectively: the computation of desirable data layouts or
mappings, and the minimization and concealment of transformation
overhead. The first is supported by optimality analysis and
approximation algorithm design. The second is achieved by asynchronous
transformation over a pipelining scheme and a two-level
efficiency-driven adaptation. We have implemented a prototype of the
technique, achieving 20--58% speedup for many scientific simulations,
including molecular dynamics simulations, partial differential
equation solving, 3-D image reconstruction. (details [http://dl.acm.org/citation.cfm?id=1950365.1950408‎ here])

The second technique, neighborhood-aware locality optimizations,
concentrates on another key feature of CMP, the non-uniform relations
among computing elements. It consists of two components. The first
aims to reveal the implications of the non-uniformity on the
interactions among co-running threads and on the use of on-chip
storage and memory bandwidth. Based on traditional locality analysis,
we propose concurrent reuse distance and cross-thread reference affinity analysis to capture inter-thread interferences
and cross-thread data reference patterns. The second component
translates the analysis results into performance improvement by
adjusting the distribution of tasks, the organization of data in
memory, and the scheduling of threads accordingly.
We have developed a prototype of shared-cache--aware transformations,
which yields 36% speedup on a set of multithreading applications. (details [http://dl.acm.org/citation.cfm?id=2442523‎ here])

This research will produce a robust tool for scientific users to
enhance program locality on multi- and many-core systems that is not
possible to achieve with existing tools.  It is the next step from the
PI's previous work in memory optimizations for scientific programs. It
will contribute to the advance of computational sciences and promote
academic research and education in the challenging field of scientific
computing.

Quad chart:[[File:Quad_shen_icon.jpg]] (Larger: [[File:QUAD.pdf]])

Publications: [http://www.cs.wm.edu/caps/publications.html here.]