Staff Publications

Staff Publications

  • external user (warningwarning)
  • Log in as
  • language uk
  • About

    'Staff publications' is the digital repository of Wageningen University & Research

    'Staff publications' contains references to publications authored by Wageningen University staff from 1976 onward.

    Publications authored by the staff of the Research Institutes are available from 1995 onwards.

    Full text documents are added when available. The database is updated daily and currently holds about 240,000 items, of which 72,000 in open access.

    We have a manual that explains all the features 

Record number 546763
Title Parallel algorithms for computing the smallest binary tree size in unit simplex refinement
Author(s) Aparicio, G.; Salmerón, J.M.G.; Casado, L.G.; Asenjo, R.; Hendrix, E.M.T.
Source Journal of Parallel and Distributed Computing 112 (2018). - ISSN 0743-7315 - p. 166 - 178.
Department(s) Operations Research and Logistics
Publication type Refereed Article in a scientific journal
Publication year 2018
Keyword(s) Regular simplex - Longest edge bisection - Binary tree - TBB - Pthreads - Dynamic number of threads - Shared memory
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.
There are no comments yet. You can post the first one!
Post a comment
Please log in to use this service. Login as Wageningen University & Research user or guest user in upper right hand corner of this page.