PhD Proposal: Donald Nguyen, GDC 7.808

Contact Name: 
Lydia Griffith
Dec 9, 2013 3:00pm - 5:00pm

PhD Proposal: Donald Nguyen

GDC 7.808
December 9th, 2013
Research supervisor:  Keshav Pingali

Title: Scheduling Irregular Algorithms

Traditionally, parallelism is described using program-centric constructs like
loops, and it is the job of a compiler to extract parallelism using program
analysis. While this compiler-based approach has been successful for loop nests
with affine data references, so-called \emph{regular programs}, general
techniques for the parallelization of non-regular programs, i.e.,
\emph{irregular programs} remains elusive.  One major problem is that, in many
irregular programs, dependencies are functions of runtime data, and the
required information for parallelization is simply not available at
compile-time, and runtime techniques are required in general.

One solution to this problem, studied in this thesis, is to develop a
programming model in which what a program does is separated from when and where
it should be done. When programs are in this form, parallelism is explicit and
the focus turns towards scheduling program tasks. The challenge is to design
the programming model such that users can easily specify relevant scheduling
constraints and systems can also produce efficient implementations.

We have designed and implemented one such programming model in the Galois
system. Our results show that this approach significantly outperforms some
domain-specific parallelization strategies that only allow a restricted set of
scheduling policies. The decoupling of scheduling from computation also
permits an efficient approach for deterministic scheduling and suggests
new directions for hardware, in particular, for transactional memory.