Chakrabarti, Soumen ; Yelick, Katherine (1993) Implementing an irregular application on a distributed memory multiprocessor ACM SIGPLAN symposium on Principles and practice of parallel programming . pp. 169-178.
![]() |
PDF
1MB |
Official URL: http://doi.org/10.1145/155332.155350
Related URL: http://dx.doi.org/10.1145/155332.155350
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 Gro¨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 share 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.
Item Type: | Article |
---|---|
Source: | Copyright of this article belongs to Association for Computing Machinery |
ID Code: | 131018 |
Deposited On: | 02 Dec 2022 06:21 |
Last Modified: | 27 Jan 2023 10:03 |
Repository Staff Only: item control page