An efficient coarse-grain multicomputer algorithm for the minimum cost parenthesizing problem

Kengne Tchendji, Vianney; Myoupo, Jean
September 2012
Journal of Supercomputing;
Several problems modeled by dynamic programming have been solved using a coarse-grain multicomputer parallel model (CGM for short). These problems use either polyadic dynamic programming or monadic non-serial dynamic programming. In this paper, we address the general case: we propose a parallel algorithm in the CGM model with p processors for the Optimal String Parenthesizing Problem or Minimum Cost Parenthesizing Problem, which is a typical polyadic non-serial dynamic programming problem. The algorithm we obtain requires ⌈(2 p)⌉ communication rounds and, at most, O( n/ p) time-steps on p processors. This new CGM algorithm performs better than the previously most efficient solution, which uses p communication rounds.


Related Articles

  • A Shortest Path Algorithm in Robotics and Its Implementation on the FPS T-20 Hypercube. Thornton, John R.; Warner, Daniel D. // Annals of Operations Research;1988, Vol. 14 Issue 1-4, p305 

    A broad class of problems involving the optimal control of robot arms can be formulated as dynamic programming problems whose structure is particularly attractive for parallel processing. For certain simple cost functions the dynamic programming formulation reduces to determining the shortest...

  • Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function. Verkhovsky, Boris S. // International Journal of Communications, Network & System Scienc;Sep2011, Vol. 4 Issue 9, p549 

    In this paper we consider a parallel algorithm that detects the maximizer of unimodal function ƒ(x) computable at every point on unbounded interval (0,∞) . The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching...

  • Solving the facility location and design (1∣1)-centroid problem via parallel algorithms. Redondo, J.; Fernández, J.; García, I.; Ortigosa, P. // Journal of Supercomputing;Dec2011, Vol. 58 Issue 3, p420 

    Several parallel strategies for solving a centroid problem are presented. In the competitive location problem considered in this paper, the aim is to maximize the profit obtained by a chain (the leader) knowing that a competitor (the follower) will react by locating another single facility after...

  • FPGA high-level synthesis compile optimization algorithm based on matrix partitioning. ZHANG Mo-li; YANG Hai-gang; CUI Xiu-hai; LI Yuan-qiang // Application Research of Computers / Jisuanji Yingyong Yanjiu;Nov2013, Vol. 30 Issue 11, p3349 

    In order to achieve the optimal throughput by extracting parallelism in matrix during high-level synthesis, this paper proposed a matrix partitioning compile optimization algorithm to handle matrix applications, especially in multiplications. This algorithm divided data-intensive arrays into...

  • A Modified Parallel Heuristic Graph Matching Approach for Solving Task Assignment Problem in Distributed Processor System. Mohan, R.; Gopalan, N. P. // International Journal of Information Technology & Computer Scien;Sep2013, Vol. 5 Issue 10, p78 

    Task assignment is one of the most fundamental combinatorial optimization problems. Solving the Task Assignment Problem is very important for many real time and computational scenarios where a lot of small tasks need to be solved by multiple processors simultaneously. In this paper a Heuristic...

  • Parallel Search Algorithms for Discrete Optimization Problems . Grama, Ananth; Kumar, Vipin // ORSA Journal on Computing;Fall95, Vol. 7 Issue 4, p365 

    Discrete optimization problems (DOPs) arise in various applications such as planning, scheduling, computer aided design, robotics, game playing and constraint directed reasoning. Often, a DOP is formulated in terms of finding a (minimum cost) solution path in a graph from an initial node to a...

  • Optimization Model of Bus Station Based on the Largest System Benefit. Jun Qian; Fuqiang Jia; Yuan Liu; Bin Wei // Advanced Materials Research;2014, Vol. 1065-1069, p3329 

    By applying time-value theory, this article establish a optimization model of bus station based on the largest system benefit. As the model works out, design algorithm of it by using dynamic programming theory. Meanwhile combine a instance to verify the model, the model has been proved to be...

  • Parallel evolutionary algorithms based on shared memory programming approaches. Redondo, J.; García, I.; Ortigosa, P. // Journal of Supercomputing;Nov2011, Vol. 58 Issue 2, p270 

    In this work, two parallel techniques based on shared memory programming are presented. These models are specially suitable to be applied over evolutionary algorithms. To study their performance, the algorithm UEGO ( Universal Evolutionary Global Optimizer) has been chosen.

  • LOCAL AND GLOBAL OPTIMIZATION BY PARALLEL ALGORITHMS FOR MIMD SYSTEMS. Sutti, C. // Annals of Operations Research;1984, Vol. 1 Issue 1-4, p151 

    This paper describes an implementation on the Neptune system at Loughborough University of Sutti's parallel (MIMD) algorithm [1–3] and an analysis of its performance. Parallel asynchronous versions of Powell's method [6] and Price's algorithm [7] are proposed, designed for efficient...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics