An Efficient CGM-Based Parallel Algorithm Solving the Matrix Chain Ordering Problem

An Efficient CGM-Based Parallel Algorithm Solving the Matrix Chain Ordering Problem

Jean Frédéric Myoupo, Vianney Kengne Tchendji
Copyright: © 2014 |Pages: 27
DOI: 10.4018/ijghpc.2014040105
OnDemand:
(Individual Articles)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

This study focuses on the parallel resolution of the matrix chain ordering problem and the optimal convex polygon triangulation problem on the Coarse grain multicomputer model (CGM for short). There has been intensive work on the parallelization of these dynamic programming problems in PRAM, including the use of systolic arrays, but a BSP/CGM solution is necessary for ease of implementation and portability. Our CGM algorithm is based on Yao's sequential solution running in O(n2) time and O(n2) space. This CGM algorithm uses p processors, each with O(n/p) local memory. It requires at most O(S/p×n2) running time with S communication rounds and with S/p<1. Our algorithm performs better than the algorithm proposed in 2012 by Dilson and Marco when S is less than n/p. We offer several ways of partitioning the problem to solve and study the impact of each partitioning algorithm performance. A CGM solution exists based on Yao's algorithm, but the subdivision of tasks is defined according to the BSP cost model. In this paper, we propose a solution based only on the CGM model specifications. Note that S is the number of super-steps of the CGM algorithm.
Article Preview
Top

The classical sequential algorithm, or Godbole’s algorithm (Godbole, 1973), for these problems is based on a dynamic programming technique. It requires O(n3) calculation operations and O(n2) memory space. By using the monotonicity property of OBST, Knuth (1973) derived an O(n2) algorithm in the same space. Yao (1982) obtained the same result with the help of the quadrangle inequalities. Eppstein, Galil and Giancarlo (1988) developed an ijghpc.2014040105.m01 algorithm using the restrictive assumption of convexity. Whereas the parallelization of the classical version has been extensively studied by the community of parallel processing researchers for the different parallel computing models (Bradford, 1994; Fotso, Kengne, & Myoupo, 2010; Guibas, Kung, & Thompson, 1979; Gupta & Tang, 1995; Karypis & Kumar, 1993; Kengne & Myoupo, 2012; Rytter, 1988), few works have been produced on the parallelization of the Knuth approach (Kechid & Myoupo, 2008a) or the Yao approach (Kechid & Myoupo, 2008b).

Complete Article List

Search this Journal:
Reset
Volume 16: 1 Issue (2024)
Volume 15: 2 Issues (2023)
Volume 14: 6 Issues (2022): 1 Released, 5 Forthcoming
Volume 13: 4 Issues (2021)
Volume 12: 4 Issues (2020)
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing