Implementing an Irregular Application on a
Distributed Memory Multiprocessor

Soumen Chakrabarti and Katherine Yelick

Parallelism with irregular patterns of data, communication and
computation is hard to manage efficiently.  In this paper we
present a case study of the Grobner basis problem, a symbolic
algebra application.  We developed an efficient parallel
implementation using the following techniques. First, a
sequential algorithm was rewritten in a transition axiom style,
in which computation proceeds by non-deterministic invocations
of guarded statements at multiple processors.

Next, the algebraic properties of the problem were studied to
modify the algorithm to ensure correctness in spite of locally
inconsistent views of the shared data structures.  This was used
to design data structures with very little overhead for
maintaining consistency.  Finally, an application-specific
scheduler was designed and tuned to get good performance.  Our
distributed memory implementation achieves impressive speedups.