Multipol: Data Structures for Irregular Parallel Applications 
Soumen Chakrabarti, Etienne Deprit, and Jeff Jones
(Professor K. A. Yelick)
(ARPA) DABT63-92-C-0026 and NSF Research Initiation Award

The most challenging applications for large-scale multiprocessors are
those with a high degree of irregularity. We have identified three
sources of irregularity in real problems: irregular control flow, such
as frequent branches or exceptions; irregular data structures, such as
unbalanced trees and graphs; and irregular communication in space or
in time. All of these factors make the applications difficult to
analyze statically for automatic parallelization, and it makes them
inefficient in a strict data parallel programming model.

We are developing parallel applications for distributed memory
multiprocessors. Our list of applications includes a symbolic algebra
problem (the Grobner Basis computation) [2], a timing-level circuit
simulation (PARSWEC [3]), a symbolic CAD application (logic
verification using BDDs), and a computational biology application
(phylogeny tree construction). For each of the applications, the goal
is to develop a clean and efficient parallel implementation, analyze
the design tradeoffs, and develop runtime support in the form of
general purpose distributed data structures.

Distributed data structures hide the details of the underlying
message-passing nature of the machine, allowing for a shared object
style of programming and making it easier to reason about program
correctness [4]. We are developing a library of such data structures
called Multipol, which includes a task queue, a time warp abstraction
for speculative simulation, a multiset, a hash table, and a bipartite
graph. They use a kind of "relaxed" interface, that generalizes weak
consistency models of memory to data types other than memory. The
structures provide efficient, tunable access to the underlying
hardware, which has proven essential in achieving high performance on
the applications.

[1] K. Yelick, "Programming Models for Irregular Applications,"
Proc. Workshop on Languages, Compilers, and Runtime Environments for
Distributed Memory Multiprocessors, SIGPLAN Notices, Vol. 28, No. 1,
Boulder, CO, January 1993, pp. 28-31.

[2] S. Chakrabarti and K. Yelick, "Implementing an Irregular
Application on a Distributed Memory Multiprocessor," 4th ACM SIGPLAN
Proc. Principles and Practice of Parallel Programming, Vol. 28, No. 7,
San Diego, CA, May 1993, pp. 169-178.

[3] C.-P. Wen and K. Yelick, "Parallel Timing Simulation on a
Distributed Memory Multiprocessor," Proc. IEEE ICCAD, Santa Clara, CA,
November 1993.

[4] S. Chakrabarti and K. Yelick, "On the Correctness of a Distributed
Grobner Basis Algorithm," Proc. Rewriting Techniques and Applications,
June 1993.