Efficient Support for Irregular Applications on Distributed--Memory Machines

Abstract:

Irregular computation problems underlie many important scientific
applications. Although these problems are computationally expensive, and
so would seem appropriate for parallel machines, their irregular
and unpredictable run-time behavior makes this type of parallel program
difficult to write and adversely affects run-time performance.
This paper explores three issues---partitioning, mutual exclusion, and
data transfer---crucial to the efficient execution of irregular
problems on distributed-memory machines. Unlike previous work, we
studied the same programs running in three alternative systems on the
same hardware base (a Thinking Machines CM-5): the CHAOS irregular
application library, Transparent Shared Memory (TSM), and eXtensible
Shared Memory (XSM). CHAOS and XSM performed equivalently for all
three applications. Both systems were somewhat (13\%) to
significantly faster (991\%) than TSM.