A divide-and-conquer parallel pattern implementation for multicores

Marco Danelutto; Tiziano De Matteis; Gabriele Mencagli; Massimo Torquati

doi:10.1145/3002125.3002128

A divide-and-conquer parallel pattern implementation for multicores

Marco Danelutto
, Tiziano De Matteis
, Gabriele Mencagli
, Massimo Torquati

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Divide-and-Conquer (DaC) is a sequential programming paradigm which models a large class of algorithms used in real-life applications. Although suitable to extract parallelism in a straightforward way, the parallel implementation of DaC algorithms still requires some expertise in parallel programming tools by the programmer. In this paper we aim at providing to non-expert programmers a high-level solution for fast prototyping parallel DaC programs on multicores with minimal programming effort. Following the rationale of parallel design pattern methodology, we design a C++11-compliant template interface for developing parallel DaC programs. The interface is implemented using different back-end frameworks (i.e. OpenMP, Intel TBB and FastFlow) supporting source code reuse and a certain amount of performance portability. Experiments on a 24-core Intel server show the effectiveness of our approach: with a reduced programming effort the programmer easily prototypes parallel versions with performance comparable with hand-made parallelizations.

Original language	English
Title of host publication	SEPS 2016 - Proceedings of the 3rd International Workshop on Software Engineering for Parallel Systems, co-located with SPLASH 2016
Editors	A. Jannesari, Y. Sato, S. Winter
Publisher	Association for Computing Machinery, Inc
Pages	10-19
ISBN (Electronic)	9781450346412
DOIs	https://doi.org/10.1145/3002125.3002128
Publication status	Published - 21 Oct 2016
Externally published	Yes
Event	3rd International Workshop on Software Engineering for Parallel Systems, SEPS 2016 - Amsterdam, Netherlands Duration: 1 Nov 2016 → …

Conference

Conference	3rd International Workshop on Software Engineering for Parallel Systems, SEPS 2016
Country/Territory	Netherlands
City	Amsterdam
Period	1/11/16 → …

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Access to Document

10.1145/3002125.3002128

Persistent URL (handle)

Persistent link

Cite this

Danelutto, M., De Matteis, T., Mencagli, G., & Torquati, M. (2016). A divide-and-conquer parallel pattern implementation for multicores. In A. Jannesari, Y. Sato, & S. Winter (Eds.), SEPS 2016 - Proceedings of the 3rd International Workshop on Software Engineering for Parallel Systems, co-located with SPLASH 2016 (pp. 10-19). Association for Computing Machinery, Inc. https://doi.org/10.1145/3002125.3002128

Danelutto, Marco ; De Matteis, Tiziano ; Mencagli, Gabriele et al. / A divide-and-conquer parallel pattern implementation for multicores. SEPS 2016 - Proceedings of the 3rd International Workshop on Software Engineering for Parallel Systems, co-located with SPLASH 2016. editor / A. Jannesari ; Y. Sato ; S. Winter. Association for Computing Machinery, Inc, 2016. pp. 10-19

@inproceedings{92e54e85e4e64f9b8fc8939c8567245f,

title = "A divide-and-conquer parallel pattern implementation for multicores",

abstract = "Divide-and-Conquer (DaC) is a sequential programming paradigm which models a large class of algorithms used in real-life applications. Although suitable to extract parallelism in a straightforward way, the parallel implementation of DaC algorithms still requires some expertise in parallel programming tools by the programmer. In this paper we aim at providing to non-expert programmers a high-level solution for fast prototyping parallel DaC programs on multicores with minimal programming effort. Following the rationale of parallel design pattern methodology, we design a C++11-compliant template interface for developing parallel DaC programs. The interface is implemented using different back-end frameworks (i.e. OpenMP, Intel TBB and FastFlow) supporting source code reuse and a certain amount of performance portability. Experiments on a 24-core Intel server show the effectiveness of our approach: with a reduced programming effort the programmer easily prototypes parallel versions with performance comparable with hand-made parallelizations.",

author = "Marco Danelutto and \{De Matteis\}, Tiziano and Gabriele Mencagli and Massimo Torquati",

year = "2016",

month = oct,

day = "21",

doi = "10.1145/3002125.3002128",

language = "English",

pages = "10--19",

editor = "A. Jannesari and Y. Sato and S. Winter",

booktitle = "SEPS 2016 - Proceedings of the 3rd International Workshop on Software Engineering for Parallel Systems, co-located with SPLASH 2016",

publisher = "Association for Computing Machinery, Inc",

note = "3rd International Workshop on Software Engineering for Parallel Systems, SEPS 2016 ; Conference date: 01-11-2016",

}

Danelutto, M, De Matteis, T, Mencagli, G & Torquati, M 2016, A divide-and-conquer parallel pattern implementation for multicores. in A Jannesari, Y Sato & S Winter (eds), SEPS 2016 - Proceedings of the 3rd International Workshop on Software Engineering for Parallel Systems, co-located with SPLASH 2016. Association for Computing Machinery, Inc, pp. 10-19, 3rd International Workshop on Software Engineering for Parallel Systems, SEPS 2016, Amsterdam, Netherlands, 1/11/16. https://doi.org/10.1145/3002125.3002128

A divide-and-conquer parallel pattern implementation for multicores. / Danelutto, Marco; De Matteis, Tiziano; Mencagli, Gabriele et al.
SEPS 2016 - Proceedings of the 3rd International Workshop on Software Engineering for Parallel Systems, co-located with SPLASH 2016. ed. / A. Jannesari; Y. Sato; S. Winter. Association for Computing Machinery, Inc, 2016. p. 10-19.

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A divide-and-conquer parallel pattern implementation for multicores

AU - Danelutto, Marco

AU - De Matteis, Tiziano

AU - Mencagli, Gabriele

AU - Torquati, Massimo

PY - 2016/10/21

Y1 - 2016/10/21

N2 - Divide-and-Conquer (DaC) is a sequential programming paradigm which models a large class of algorithms used in real-life applications. Although suitable to extract parallelism in a straightforward way, the parallel implementation of DaC algorithms still requires some expertise in parallel programming tools by the programmer. In this paper we aim at providing to non-expert programmers a high-level solution for fast prototyping parallel DaC programs on multicores with minimal programming effort. Following the rationale of parallel design pattern methodology, we design a C++11-compliant template interface for developing parallel DaC programs. The interface is implemented using different back-end frameworks (i.e. OpenMP, Intel TBB and FastFlow) supporting source code reuse and a certain amount of performance portability. Experiments on a 24-core Intel server show the effectiveness of our approach: with a reduced programming effort the programmer easily prototypes parallel versions with performance comparable with hand-made parallelizations.

AB - Divide-and-Conquer (DaC) is a sequential programming paradigm which models a large class of algorithms used in real-life applications. Although suitable to extract parallelism in a straightforward way, the parallel implementation of DaC algorithms still requires some expertise in parallel programming tools by the programmer. In this paper we aim at providing to non-expert programmers a high-level solution for fast prototyping parallel DaC programs on multicores with minimal programming effort. Following the rationale of parallel design pattern methodology, we design a C++11-compliant template interface for developing parallel DaC programs. The interface is implemented using different back-end frameworks (i.e. OpenMP, Intel TBB and FastFlow) supporting source code reuse and a certain amount of performance portability. Experiments on a 24-core Intel server show the effectiveness of our approach: with a reduced programming effort the programmer easily prototypes parallel versions with performance comparable with hand-made parallelizations.

UR - https://www.scopus.com/pages/publications/84997787441

UR - https://www.scopus.com/pages/publications/84997787441#tab=citedBy

U2 - 10.1145/3002125.3002128

DO - 10.1145/3002125.3002128

M3 - Conference contribution

SP - 10

EP - 19

BT - SEPS 2016 - Proceedings of the 3rd International Workshop on Software Engineering for Parallel Systems, co-located with SPLASH 2016

A2 - Jannesari, A.

A2 - Sato, Y.

A2 - Winter, S.

PB - Association for Computing Machinery, Inc

T2 - 3rd International Workshop on Software Engineering for Parallel Systems, SEPS 2016

Y2 - 1 November 2016

ER -

Danelutto M, De Matteis T, Mencagli G, Torquati M. A divide-and-conquer parallel pattern implementation for multicores. In Jannesari A, Sato Y, Winter S, editors, SEPS 2016 - Proceedings of the 3rd International Workshop on Software Engineering for Parallel Systems, co-located with SPLASH 2016. Association for Computing Machinery, Inc. 2016. p. 10-19 doi: 10.1145/3002125.3002128

A divide-and-conquer parallel pattern implementation for multicores

Abstract

Conference

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this