BIBLIOS

  Ciências References Management System

Visitor Mode (Login)
Need help?


Back

Publication details

Document type
Journal articles

Document subtype
Full paper

Title
Overcoming the No Free Lunch Theorem in Cut-off Algorithms for Fork-Join programs

Participants in the publication
Alcides Fonseca (Author)
Dep. Informatica
Bruno Cabral (Author)

Scope
International

Refereeing
Yes

Summary
The No Free Lunch Theorem establishes that for any algorithm, any elevated performance over one class of problems is offset by performance over another class. Empirically, this is true for Granularity Control algorithms, particularly in Fork-Join style concurrent programs. Cut-off Algorithms make the decision to either continue forking work (parallelising) or instead computing the remaining execution branches sequentially. These algorithms affect how well a program dynamically adjusts to the parallelism available in the machine. To put things into context, choosing the wrong algorithm can make a program go from 30 s of execution to over a day. Cut-off Algorithms such as Max-Tasks, Max-Level, SurplusTasks and variants do not provide the same performance improvements over the same classes of Fork-Join programs. Thus, programmers have to decide which Cut-off Algorithms to use on different classes of problems. Finding the right Cut-off Algorithm is a time-consuming task, as, most of times, it requires trial-and-error execution of several configurations before determining the right solution. To the best of our knowledge, there is no definitive solution for making this decision automatically. Being able to do so would largely enhance the performance of parallel programs generated by optimising compilers and/or executed by parallelising frameworks. In this work, we address the problem of automatically selecting the right Cut-off Algorithm for highly parallel programs. We evaluate the performance of nowadays most relevant Cut-off Algorithms over different programs. We identify possible correlations between program characteristics and performance improvements observed with different cut-off strategies. Finally, we derive a set classification rules for selection of Cut-off Algorithms that can be integrated into compilers and frameworks that perform automatic parallelisation of programs.

Date of Publication
2018-08

Where published
Parallel Computing

Publication Identifiers
ISSN - 0167-8191

Publisher
Elsevier BV

Volume
76

Number of pages
14
Starting page
42
Last page
56

Document Identifiers
URL - http://dx.doi.org/10.1016/j.parco.2018.04.005
DOI - https://doi.org/10.1016/j.parco.2018.04.005

Rankings
CORE A (2010) -
SCIMAGO Q2 (2017) - 0.351 - Software
SCOPUS Q1 (2013) - 0.694 - Software

Tags
lasige lasige-rss


Export

APA
Alcides Fonseca, Bruno Cabral, (2018). Overcoming the No Free Lunch Theorem in Cut-off Algorithms for Fork-Join programs. Parallel Computing, 76, 42-56. ISSN 0167-8191. eISSN . http://dx.doi.org/10.1016/j.parco.2018.04.005

IEEE
Alcides Fonseca, Bruno Cabral, "Overcoming the No Free Lunch Theorem in Cut-off Algorithms for Fork-Join programs" in Parallel Computing, vol. 76, pp. 42-56, 2018. 10.1016/j.parco.2018.04.005

BIBTEX
@article{35828, author = {Alcides Fonseca and Bruno Cabral}, title = {Overcoming the No Free Lunch Theorem in Cut-off Algorithms for Fork-Join programs}, journal = {Parallel Computing}, year = 2018, pages = {42-56}, volume = 76 }