Download now Free registration required
The Matrix Chain Ordering Problem (MCOP) is widely used in computer and specially in combinatorial optimization. Even though there has been intensive work for the parallelization of dynamic programming on PRAM, systolic arrays among others, its parallel version on BSP/CGM is still to be done. In the former work, the authors proposed a BSP/CGM for this problem running in O (n3/p)). The approach was based on the classical sequential algorithm (running in O (n3)), hence the algorithm they obtained is not optimal. In this paper the strategy is based on the Yao's sequential algorithm for dynamic programming running in O (n2). The resulting algorithm runs in S super-steps with O (n2/P) as time of execution per processor.
- Format: PDF
- Size: 204.8 KB