Katherine Yelick, Soumen Chakrabarti, Etienne Deprit, Jeff Jones, 
		Arvind Krishnamurthy, and Chih-Po Wen

		U.C. Berkeley, Computer Science Division 


Symbolic applications often require dynamic irregular data structures,
such as linked lists, unbalanced trees, and graphs, and they exhibit
unpredictable computational patterns that lead to asynchronous
communication and load imbalance when parallelized.  In this paper we
describe several symbolic applications and their parallelizations.
The main problem in parallelization of each application was to replace
the primary data structures with parallel versions that allow for high
throughput, low latency access.  In each case there are two problems
to be solved: load balancing the parallel computation and sharing
information about the solution as it is being constructed.  The first
problem is typically solved using a scheduling data structure, a
stack, queue, or priority queue in sequential programs.  The
difficulty in parallelizing these structure is the trade-off between
locality and load balancing: aggressive load balancing can lead to
poor locality.  The second problem of storing the solution depends
much more on the type of solution, but range from simple scalar values
to sets or tables.  These structures use partitioning, full
replication, or dynamic caching in their parallelizations.

In sequential programming environments, common data structures are
often provided through reusable libraries.  We have built a parallel
analog to these libraries, called Multipol.  Multipol support
irregular and asynchronous applications, including symbolic
applications, discrete event simulation, and adaptive algorithms.  The
performance issues in Multipol include masking remote latency,
elimination of communication, load balance, performance portability
across machines, and local node performance.