An Efficient CGM-Based Parallel Algorithm Solving the Matrix Chain Ordering Problem
International Journal of Grid and High Performance Computing · 2014
DOI: 10.4018/ijghpc.2014040105 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Grid and High Performance Computing, 2014. Verfasst von Jean Frédéric Myoupo und 1 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 22 Literaturangaben.
Abstract (Originalsprache)
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
Zitieren
APA
Myoupo, J. F., & Tchendji, V. K. (2014). An Efficient CGM-Based Parallel Algorithm Solving the Matrix Chain Ordering Problem. International Journal of Grid and High Performance Computing. https://doi.org/10.4018/ijghpc.2014040105
Vancouver
Myoupo JF, Tchendji VK. An Efficient CGM-Based Parallel Algorithm Solving the Matrix Chain Ordering Problem. International Journal of Grid and High Performance Computing. 2014. doi:10.4018/ijghpc.2014040105
BibTeX
@article{Myoupo2014,
author = {Myoupo, Jean Frédéric and Tchendji, Vianney Kengne},
title = {An Efficient CGM-Based Parallel Algorithm Solving the Matrix Chain Ordering Problem},
journal = {International Journal of Grid and High Performance Computing},
year = {2014},
doi = {10.4018/ijghpc.2014040105}
}
EUVIMED