|Title||Implementing an Irregular Application on a Distributed Memory Multiprocessor|
|Author(s)|| Soumen Chakrabarti, Katherine A. Yelick|
|Type||Article in Conference Proceedings|
|Abstract||Parallelism with irregular patterns of data, communication and computation is hard to manage efficiently. In this paper we present a|
case study of the Gröbner 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 applicationspecific scheduler was designed and tuned to get good performance. Our distributed memory implementation achieves impressive speedups.
|Conferencename||Symposium on Principles and Practices of Parallel Programming (SIGPLAN)|