IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i21p3925-d950839.html
   My bibliography  Save this article

On Generalizing Divide and Conquer Parallel Programming Pattern

Author

Listed:
  • Virginia Niculescu

    (Department of Computer Science, Faculty of Mathematics and Computer Science, “Babeş-Bolyai” University, 400084 Cluj-Napoca, Romania)

Abstract

(1) Background: Structuring is important in parallel programming in order to master its complexity, and this structuring could be achieved through programming patterns and skeletons. Divide-and-conquer computation is essentially defined by a recurrence relation that links the solution of a problem to the solutions of subproblems of the same type, but of smaller sizes. This pattern allows the specification of different types of computations, and so it is important to provide a general specification that comprises all its cases. We intend to prove that the divide-and-conquer pattern could be generalized such that to comprise many of the other parallel programming patterns, and in order to prove this, we provide a general formulation of it. (2) Methods: Starting from the proposed generalized specification of the divide-and-conquer pattern, the computation of the pattern is analyzed based on its stages: decomposition, base-case and composition. Examples are provided, and different execution models are analyzed. (3) Results: a general functional specification is provided for a divide-and-conquer pattern and based on it, and we prove that this general formulation could be specialized through parameters’ instantiating into other classical parallel programming patterns. Based on the specific stages of the divide-and-conquer, three classes of computations are emphasized. In this context, an equivalent efficient bottom-up computation is formally proved. Associated models of executions are emphasized and analyzed based on the three classes of divide-and-conquer computations. (4) Conclusion: A more general definition of the divide-and-conquer pattern is provided, and this includes an arity list for different decomposition degrees, a level of recursion, and also an alternative solution for the cases that are not trivial but allow other approaches (sequential or parallel) that could lead to better performance. Together with the associated analysis of patterns equivalence and optimized execution models, this provides a general formulation that is useful both at the semantic level and implementation level.

Suggested Citation

  • Virginia Niculescu, 2022. "On Generalizing Divide and Conquer Parallel Programming Pattern," Mathematics, MDPI, vol. 10(21), pages 1-22, October.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:21:p:3925-:d:950839
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/21/3925/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/21/3925/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Moe Nandi Aung & Yati Phyo & Canh Minh Do & Kazuhiro Ogata, 2021. "A Divide and Conquer Approach to Eventual Model Checking," Mathematics, MDPI, vol. 9(4), pages 1-16, February.
    2. David Delgado-Gómez & Franks González-Landero & Carlos Montes-Botella & Aaron Sujar & Sofia Bayona & Luca Martino, 2020. "Improving the Teaching of Hypothesis Testing Using a Divide-and-Conquer Strategy and Content Exposure Control in a Gamified Environment," Mathematics, MDPI, vol. 8(12), pages 1-14, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.

      Corrections

      All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:21:p:3925-:d:950839. See general information about how to correct material in RePEc.

      If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

      If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

      If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

      For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

      Please note that corrections may take a couple of weeks to filter through the various RePEc services.

      IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.