Parallel Processing Research
Dynamic Parallel Evaluation of Cross-product Sets
Information Processing Letters, Vol. 44, No. 5 (1992) 273-280
Author(s)
Gopal Gupta
Abstract
In this paper we consider the problem of dynamically generating
the cross-product (cartesian product) of two or more sets,
in parallel, on shared memory machines. Dynamic generation means
that the cross-product set is computed on the fly as various
elements of its constituent sets are generated asynchronously.
Dynamic evaluation of the cross-product set finds application
in a number of problems such as parallel evaluation of data-base
joins. Generation of the cross-product set using the
straight-forward algorithms is inherently sequential because
when elements of two constituents sets are generated
simultaneously computing the tuples of
cross-product set corresponding to these elements has to be
done sequentially. We present
a simple modification of the nested loop algorithm using
time-stamps which results in significant amount of parallelism being
extracted.
We present results of experiments
done on the Sequent Symmetry multiprocessor
which show that the overhead introduced for time-stamping
is minimal while speed-ups obtained are linear.
We also present an algorithm, and discuss its advantages,
which generates the tuples of the cross-product set in
an order such that two consecutive tuples differ in only
element position.
The whole paper
can be downloaded from our
server.
Parallel Proc. Page Research Page Lab Home Page