An implementation of the ε-relaxation algorithm on the CM-5
B. Narendran, Renato De Leone, Prasoon Tiwari · 1993
This paper discusses a parallel implementation of the e-relaxation algorithm for the rein-cost flow problem on the CM-5.There is considerable loss in et%ciency in going from one processor sequential implementation to one processor parallel implementation.While a naive parallelization is shown to have very low parallelism, we investigate the effectiveness of a set of algorithmic augmentations.These augmentations work by either eliminating non-parallel iterations or increasing the parallelism of the remaining iterations.Although the size of memory on the machine limits the size of problems used in our experiments, experimental scalability data shows that the parallel implementation may be able to beat the best sequential implementation on large enough problems.1 *Some of the performance data presented in this paper was derived using CMMD2.0-betaand CMOST7.2-betawhich are prerelease versions of system softwere for the CM-S from Thinking Machines Corp.