Parallel algorithms for computing the smallest binary tree size in unit simplex refinement

G. Aparicio, J.M.G. Salmerón, L.G. Casado, R. Asenjo, E.M.T. Hendrix

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

Refinement of the unit simplex by iterative longest edge bisection (LEB) up to sub-simplices have a size smaller or equal to a given accuracy, generates a binary tree. For a dimension higher than three, the size of the generated tree depends on the bisected LE. There may exist more than one selection sequence of LE that solves the Smallest Binary Tree Size Problem (SBTSP). Solving SBTSP by full enumeration requires considering every possible LE bisection in each sub-simplex. This is an irregular Combinatorial Optimization problem with an increasing computational burden in the dimension and the stopping criterion. Therefore, parallel computing is appealing to find the minimum size for hard instances in a reasonable time.

The aim of this study is to develop and compare threaded algorithms running on multicore systems to solve the SBTS problem. Versions running on multicore systems with a static number of threads using TBB, and a dynamic number of threads using Pthread are compared. Interestingly, TBB scales better than the Pthread implementations for lower dimensional problems. However, when the problem dimension is higher than six, the Pthread approach with a dynamic number of threads finds a solution, where the TBB version fails. This is caused by the smaller memory footprint of the Pthread version, as it traverses deeper branches of the tree than the TBB work-stealing approach.
LanguageEnglish
Pages166-178
JournalJournal of Parallel and Distributed Computing
Volume112
DOIs
Publication statusPublished - 1 Feb 2018

Fingerprint

Binary trees
Binary Tree
Parallel algorithms
Parallel Algorithms
Refinement
Unit
Computing
Thread
Bisection
Combinatorial optimization
Parallel processing systems
Stopping Criterion
Data storage equipment
Parallel Computing
Combinatorial Optimization Problem
Enumeration
Higher Dimensions
Irregular
Branch

Keywords

  • Regular simplex
  • Longest edge bisection
  • Binary tree
  • TBB
  • Pthreads
  • Dynamic number of threads
  • Shared memory

Cite this

@article{f117ace8cad047a0a5e2dbe6b38dc635,
title = "Parallel algorithms for computing the smallest binary tree size in unit simplex refinement",
abstract = "Refinement of the unit simplex by iterative longest edge bisection (LEB) up to sub-simplices have a size smaller or equal to a given accuracy, generates a binary tree. For a dimension higher than three, the size of the generated tree depends on the bisected LE. There may exist more than one selection sequence of LE that solves the Smallest Binary Tree Size Problem (SBTSP). Solving SBTSP by full enumeration requires considering every possible LE bisection in each sub-simplex. This is an irregular Combinatorial Optimization problem with an increasing computational burden in the dimension and the stopping criterion. Therefore, parallel computing is appealing to find the minimum size for hard instances in a reasonable time.The aim of this study is to develop and compare threaded algorithms running on multicore systems to solve the SBTS problem. Versions running on multicore systems with a static number of threads using TBB, and a dynamic number of threads using Pthread are compared. Interestingly, TBB scales better than the Pthread implementations for lower dimensional problems. However, when the problem dimension is higher than six, the Pthread approach with a dynamic number of threads finds a solution, where the TBB version fails. This is caused by the smaller memory footprint of the Pthread version, as it traverses deeper branches of the tree than the TBB work-stealing approach.",
keywords = "Regular simplex, Longest edge bisection, Binary tree, TBB, Pthreads, Dynamic number of threads, Shared memory",
author = "G. Aparicio and J.M.G. Salmer{\'o}n and L.G. Casado and R. Asenjo and E.M.T. Hendrix",
year = "2018",
month = "2",
day = "1",
doi = "10.1016/j.jpdc.2017.05.016",
language = "English",
volume = "112",
pages = "166--178",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Elsevier",

}

Parallel algorithms for computing the smallest binary tree size in unit simplex refinement. / Aparicio, G.; Salmerón, J.M.G.; Casado, L.G.; Asenjo, R.; Hendrix, E.M.T.

In: Journal of Parallel and Distributed Computing, Vol. 112, 01.02.2018, p. 166-178.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Parallel algorithms for computing the smallest binary tree size in unit simplex refinement

AU - Aparicio, G.

AU - Salmerón, J.M.G.

AU - Casado, L.G.

AU - Asenjo, R.

AU - Hendrix, E.M.T.

PY - 2018/2/1

Y1 - 2018/2/1

N2 - Refinement of the unit simplex by iterative longest edge bisection (LEB) up to sub-simplices have a size smaller or equal to a given accuracy, generates a binary tree. For a dimension higher than three, the size of the generated tree depends on the bisected LE. There may exist more than one selection sequence of LE that solves the Smallest Binary Tree Size Problem (SBTSP). Solving SBTSP by full enumeration requires considering every possible LE bisection in each sub-simplex. This is an irregular Combinatorial Optimization problem with an increasing computational burden in the dimension and the stopping criterion. Therefore, parallel computing is appealing to find the minimum size for hard instances in a reasonable time.The aim of this study is to develop and compare threaded algorithms running on multicore systems to solve the SBTS problem. Versions running on multicore systems with a static number of threads using TBB, and a dynamic number of threads using Pthread are compared. Interestingly, TBB scales better than the Pthread implementations for lower dimensional problems. However, when the problem dimension is higher than six, the Pthread approach with a dynamic number of threads finds a solution, where the TBB version fails. This is caused by the smaller memory footprint of the Pthread version, as it traverses deeper branches of the tree than the TBB work-stealing approach.

AB - Refinement of the unit simplex by iterative longest edge bisection (LEB) up to sub-simplices have a size smaller or equal to a given accuracy, generates a binary tree. For a dimension higher than three, the size of the generated tree depends on the bisected LE. There may exist more than one selection sequence of LE that solves the Smallest Binary Tree Size Problem (SBTSP). Solving SBTSP by full enumeration requires considering every possible LE bisection in each sub-simplex. This is an irregular Combinatorial Optimization problem with an increasing computational burden in the dimension and the stopping criterion. Therefore, parallel computing is appealing to find the minimum size for hard instances in a reasonable time.The aim of this study is to develop and compare threaded algorithms running on multicore systems to solve the SBTS problem. Versions running on multicore systems with a static number of threads using TBB, and a dynamic number of threads using Pthread are compared. Interestingly, TBB scales better than the Pthread implementations for lower dimensional problems. However, when the problem dimension is higher than six, the Pthread approach with a dynamic number of threads finds a solution, where the TBB version fails. This is caused by the smaller memory footprint of the Pthread version, as it traverses deeper branches of the tree than the TBB work-stealing approach.

KW - Regular simplex

KW - Longest edge bisection

KW - Binary tree

KW - TBB

KW - Pthreads

KW - Dynamic number of threads

KW - Shared memory

U2 - 10.1016/j.jpdc.2017.05.016

DO - 10.1016/j.jpdc.2017.05.016

M3 - Article

VL - 112

SP - 166

EP - 178

JO - Journal of Parallel and Distributed Computing

T2 - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

ER -