A novel parallel algorithm for enumerating combinations
168. B. B. Zhou,
R. P. Brent, X. Qu and W. Liang,
A novel parallel algorithm for enumerating combinations,
Proceedings of the 25th International Conference on
Parallel Processing,
Bloomingdale, Illinois, August 1996.
IEEE Press, Vol. 2, 70-73.
Paper:
dvi (11K),
pdf (65K),
ps (47K).
Abstract
In this paper we propose a new algorithm
for parallel enumeration of combinations of M out of N items.
This algorithm uses N processing elements (or PEs).
We prove that, if N and M are relatively prime,
each PE will do the same operations and generate the same
number of distinct combinations
so that the computational load is well balanced.
The algorithm has an important application in solving
the problem of fault tolerance in replicated file systems.
Comments
Essentially the same algorithm was published earlier by
Ivan Stojmenovic [Internat. J. of Computer Mathematics
42 (1992), 125-135].
We are grateful to Professor Stojmenovic for this information
[personal communication, January 1997].
Go to next publication
Return to Richard Brent's index page