A fine-grained parallel completion procedure

1 January 1994

conference paper
Published by Association for Computing Machinery (ACM)

p. 269-277
https://doi.org/10.1145/190347.190427

Abstract

We present a parallel Knuth-Bendix completion algorithm where the inner loop, deriving the consequences of adding a new rule to the system, is multi-threaded. The selection of the best new rule in the outer loop, and hence the completion strategy, is exactly the same as for the sequential algorithm. Our implementation, which is within the PARSAC-2 parallel symbolic computation system, exhibits good parallel speedups on a standard multi-processor workstation.

Keywords

NEW RULE
INNER LOOP
STANDARD MULTI-PROCESSOR WORKSTATION
COMPLETION STRATEGY
FINE-GRAINED PARALLEL COMPLETION PROCEDURE
SEQUENTIAL ALGORITHM
OUTER LOOP
PARALLEL KNUTH-BENDIX COMPLETION ALGORITHM
GOOD PARALLEL SPEEDUP
PARSAC-2 PARALLEL SYMBOLIC COMPUTATION
SYMBOLIC COMPUTATION

This publication has 0 references indexed in Scilit: