.png){kind=icon}
返回
Parallel algorithms for computing the smallest binary tree size in unit simplex refinement
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2017.05.016.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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. (C) 2017 Elsevier Inc. All rights reserved.
Keyword:
Regular simplex
Longest edge bisection
Binary tree
TBB
Pthreads
Dynamic number of threads
Shared memory
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
引用论文
分享收藏The semi-continuous quadratic mixture design problem:: Description and branch-and-bound approach
PREAI
分享收藏On the Minimum Number of Simplex Shapes in Longest Edge Bisection Refinement of a Regular n-Simplex.png)
Informatica
OAAI
InformaticaIF2.8
OAAI分享收藏
查看更多内容