LISP and Symbolic Computation, 7(2/3)147-172
Distributed Data Structures and Algorithmsfor Gröbner Basis ComputationSoumen Chakrabarti, Computer Science Division, University of California, Berkeley, CA 94720, USA
Katherine Yelick, Computer Science Division, University of California, Berkeley, CA 94720, USA
|
Abstract: We present the design and implementation of a
parallel algorithm for computing Gröbner bases on distributed
memory multiprocessors. The parallel algorithm is irregular both in
space and time: the data structures are dynamic pointer-based
structures and the computations on the structures have unpredictable
duration. The algorithm is presented as a series of refinements on a
transition rule program, in which computation proceeds by
nondeterministic invocations of guarded commands. Two key data
structures, a set and a priority queue, are distributed across
processors in the parallel algorithm. The data structures are designed
for high throughput and latency tolerance, as appropriate for
distributed memory machines. The programming style represents a
compromise between shared-memory and message-passing models. The
distributed nature of the data structures shows through their
interface in that the semantics are weaker than with shared atomic
objects, but they still provide a shared abstraction that can be used
for reasoning about program correctness. In the data structure design
there is a classic trade-off between locality and load balance. We
argue that this is best solved by designing scheduling structures in
tandem with the state data structures, since the decision to replicate
or partition state affects the overhead of dynamically moving
tasks. Keywords: parallel computing, distributed data structures, Gröbner basis, software caching, relaxed consistency, load balancing |
This article is not available online.
![[picture of journal cover]](../LISP.JPG)