Jerry Lacmou Zeutouo ; Vianney Kengne Tchendji ; Jean-Frédéric Myoupo - Coarse-grained multicomputer parallel algorithm using the four-splitting technique for the minimum cost parenthesizing problem

arima:11217 - Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, 6 novembre 2023, Volume 38 - Numéro spécial CARI 2022 - 2023 - https://doi.org/10.46298/arima.11217
Coarse-grained multicomputer parallel algorithm using the four-splitting technique for the minimum cost parenthesizing problemArticle

Auteurs : Jerry Zeutouo 1; Vianney Tchendji 1; Jean-Frédéric Myoupo ORCID2

Dynamic programming is a technique widely used to solve several combinatory optimization problems. A well-known example is the minimum cost parenthesizing problem (MPP), which is usually used to represent a class of non-serial polyadic dynamic-programming problems. These problems are characterized by a strong dependency between subproblems. This paper outlines a coarse-grained multicomputer parallel solution using the four-splitting technique to solve the MPP. It is a partitioning technique consisting of subdividing the dependency graph into subgraphs (or blocks) of variable size and splitting large-size blocks into four subblocks to avoid communication overhead caused by a similar partitioning technique in the literature. Our solution consists in evaluating a block by computing and communicating each subblock of this block to reduce the latency time of processors which accounts for most of the global communication time. It requires O(n^3/p) execution time with O(k * \sqrt{p}) communication rounds. n is the input data size, p is the number of processors, and k is the number of times the size of blocks is subdivided.


Volume : Volume 38 - Numéro spécial CARI 2022 - 2023
Publié le : 6 novembre 2023
Accepté le : 27 octobre 2023
Soumis le : 19 avril 2023
Mots-clés : coarse-grained multicomputer,dynamic programming,dynamic graph,irregular partitioning,four-splitting,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Financement :
    Source : OpenAIRE Graph
  • Deep Drug Discovery and Deployment; Code: PTDC/CCI-BIO/29266/2017

Statistiques de consultation

Cette page a été consultée 207 fois.
Le PDF de cet article a été téléchargé 122 fois.