Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleImplementing an Irregular Application on a Distributed Memory Multiprocessor
Author(s) Soumen Chakrabarti, Katherine A. Yelick
TypeArticle in Conference Proceedings
AbstractParallelism 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.
Translation No
Refereed No
ConferencenameSymposium on Principles and Practices of Parallel Programming (SIGPLAN)