检索结果-内蒙古大学图书馆

On the parallelization and performance analysis of barnes-hut algorithm using Java parallel platforms

SN APPLIED SCIENCES 2020年第4期2卷 601页

作者： Munier, Badri Aleem, Muhammad Khan, Majid Islam, Muhammad Arshad Iqbal, Muhammad Azhar Khattak, Muhammad Kamran Capital Univ Sci & Technol Islamabad Pakistan Natl Univ Comp & Emerging Sci Dept Comp Sci Islamabad 44000 Pakistan Quaid I Azam Univ Dept Phys Islamabad 44000 Pakistan Southwest Jiaotong Univ SWJTU Leeds Joint Sch Chengdu Peoples R China COMSATS Univ Islamabad Dept Phys Pk Rd Islamabad 44000 Pakistan

Multi-core processors provide time-efficient and cost-effective solutions to execute the algorithms for complex physical systems. However, to efficiently exploit the processing capabilities of the underlying architectures, the applications executing on multi-core processors must be parallelized. Conventionally, the applications for high-performance computing (HPC) are written in native (programming) languages. However, several researchers have argued that Java can be an excellent alternative for writing HPC applications. To gauge the comparative performance of Java parallel platforms, a benchmark study is required considering some real HPC applications. In this study, as a pioneer application, Java-based parallel platforms, namely Java thread API, JavaSymphony, and MPJ Express, are used to parallelize and benchmark the barnes-hut algorithm to simulate the N-body physical system of celestial objects. The parallel implementations of the barnes-hut algorithm are tested for performance on shared memory multi-core architectures. The hardware-level performance analysis involving the parameters like the number of instructions executed by the CPU, level-1 and level-3 cache misses, and the number of main memory accesses is conducted to investigate the insights of the attained performances. The celestial objects up to one million are simulated, and the results revealed that the JavaSymphony-based implementation of the barnes-hut algorithm produces better results as compared to the other employed parallel frameworks.

关键词： barnes-hut algorithm High-performance computing Java parallel frameworks Locality optimization

来源：评论

学校读者我要写书评

暂无评论

Improving data field hierarchical clustering using barnes-hut algorithm

引用

PATTERN RECOGNITION LETTERS 2016年第0期80卷 113-120页

作者： Zhuo, Zhongliu Zhang, Xiaosong Niu, Weina Yang, Guowu Zhang, Jingzhong Univ Elect Sci & Technol China Sch Engn & Comp Sci 2006 Xiyuan Ave Chengdu 6111731 Peoples R China

Traditional Data Field Hierarchical Clustering algorithm (DFHCA) uses brute force method to compute the forces exert on each object. The computation complexity increases as O(n(2)). In this study, we improve the force computation efficiency of DFHCA to O (n log n). We use the barnes-hut tree to reduce the number of force computation by approximating far away particles with their center of mass. And compared with traditional method, our method does not need to tune the parameters. In our implementation, we discuss two different merging strategies. Experimental results show that the proposed method could improve the computation efficiency under the same settings. We also find that DFHCA-M merging strategy converges faster than DFHCA-S merging strategy. Finally, we compare and analyze the time complexity and space complexity of our algorithm. (C) 2016 Elsevier B.V. All rights reserved.

关键词： barnes-hut algorithm Data field Hierarchical clustering Computation efficiency

来源：评论

学校读者我要写书评

暂无评论

Probabilistic guards: A mechanism for increasing the granularity of work-stealing programs

引用

PARALLEL COMPUTING 2019年 82卷 19-36页

作者： Yoritaka, Hiroshi Matsui, Ken Yasugi, Masahiro Hiraishi, Tasuku Umatani, Seiji Kyushu Inst Technol Iizuka Fukuoka 8208502 Japan Kyoto Univ Kyoto 6068501 Japan Ad Sol Nissin Corp Tokyo Japan Nintendo Co Ltd Kyoto Japan

We propose probabilistic guards and analyze their performance. To reduce the total task division cost, probabilistic guards can prevent thief workers from stealing small tasks from victim workers probabilistically. In this study, we have implemented probabilistic guards on a work-stealing framework called Tascell. Without an upper limit to the number of repeated probabilistically prevented steal attempts, a thief may repeat an unbounded number of probabilistically prevented steal attempts until success if a victim uses a probabilistic guard that rejects steal attempts with a non-zero probability. We measured the actual numbers of repeated attempts until success, and evaluated the performance of probabilistic guards with various upper limits. In this paper, we also propose virtual probabilistic guards that act as probabilistic guards without repeating probabilistically prevented steal attempts. Virtual probabilistic guards exhibit superior performance compared to probabilistic guards. Our evaluation is based on parallelized "highly serial" force calculation in a shared memory environment and five Tascell programs in a distributed memory environment. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Parallel programming language Work stealing Probability Concurrency Many-core barnes-hut algorithm

来源：评论

学校读者我要写书评

暂无评论

Understanding and Analyzing the Performance Scalability of N-body Problem

Understanding and Analyzing the Performance Scalability of N...

引用

作者： Jiayu Chen The University of Melbourne

The rapid data growing recently years has provided us much more information about the universe and has contributed to the rising needs of strong computer powers in the meantime as it means that it is not feasible to handle such large amount of data without strong computer powers. Therefore, it is important to understand how the computer and programs work to help model and solve the complex problems, so that we can discover and explore more principles other than just numbers. This paper mainly focuses on the N-Body problem which is a common problem that can be extends to many fields, aiming to find the subsequent motion of multiple objects with known initial position, velocity, and mass in classical *** paper discusses about the understanding of both brute force and barnes-hut algorithm and analyses the performance and scalability of two approaches on the N-Body problem under a personal computer environment. In addition to this, the serial simulation and the parallel simulation of the brute force implementation are also get compared in the perspective of running time and the scalability in the paper.

关键词： N-body brute force method barnes-hut algorithm scalability time complexity galaxy simulation computational

来源：评论

学校读者我要写书评

暂无评论

Extending a Work-Stealing Framework with Priorities and Weights 9

Extending a Work-Stealing Framework with Priorities and Weig...

引用

9th IEEE/ACM Workshop on Irregular Applications - Architectures and algorithms (IA3)

作者： Nakashima, Ryusuke Yoritaka, Hiroshi Yasugi, Masahiro Hiraishi, Tasuku Umatani, Seiji Kyushu Inst Technol Fukuoka Japan Kyoto Univ Kyoto Japan Kanagawa Univ Yokohama Kanagawa Japan Ad Sol Nissin Corp Tokyo Japan

ISBN: (纸本)9781728159874

This paper proposes priority- and weight-based steal strategies for an idle worker (thief) to select a victim worker in work-stealing frameworks. Typical work-stealing frameworks employ uniformly random victim selection. We implemented the proposed strategies on a work-stealing framework called Tascell;Tascell programmers can let each worker estimate and declare, as a real number, the amount of remaining work required to complete its current task so that declared values are used as priorities or weights in the enhanced Tascell framework. To reduce the total task-division cost, the proposed strategies avoid stealing small tasks. With a priority-based strategy, a thief selects the victim that has the highest known priority at that point in time. With a weight-based non-uniformly random strategy, a thief uses the relative weights of victim candidates as their selection probabilities. The proposed selection strategies outperformed uniformly random victim selection. Our evaluation uses a parallel implementation of the "highly serial" version of the barnes-hut force-calculation algorithm in a shared memory environment and five benchmark programs in a distributed memory environment.

关键词： parallel programming languages work stealing priority weight concurrency many-core barnes-hut algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallel OpenMP and CUDA Implementations of the N-Body Problem 19th

Parallel OpenMP and CUDA Implementations of the N-Body Probl...

引用

19th International Conference on Computational Science and Its Applications (ICCSA)

作者： Gangavarapu, Tushaar Pal, Himadri Prakash, Pratyush Hegde, Suraj Geetha, V Natl Inst Technol Karnataka Dept Informat Technol Surathkal Mangaluru India

ISBN: (纸本)9783030242893

The N-body problem, in the field of astrophysics, predicts the movements of the planets and their gravitational interactions. This paper aims at developing efficient and high-performance implementations of two versions of the N-body problem. Adaptive tree structures are widely used in N-body simulations. Building and storing the tree and the need for work-load balancing pose significant challenges in high-performance implementations. Our implementations use various cores in CPU and GPU via efficient work-load balancing with data and task parallelization. The contributions include OpenMP and Nvidia CUDA implementations to parallelize force computation and mass distribution, and achieve competitive performance in terms of speedup and running time which is empirically justified and graphed. This research not only aids as an alternative to complex simulations but also to other big data applications requiring work-load distribution and computationally expensive procedures.

关键词： All-Pairs algorithm barnes-hut algorithm CUDA N-body simulations OpenMP Parallel processing Performance

来源：评论

学校读者我要写书评

暂无评论

Multipoint Neighbor Embedding 20th

Multipoint Neighbor Embedding

引用

20th International Conference on Text, Speech, and Dialogue (TSD)

作者： Lancucki, Adrian Chorowski, Jan Univ Wroclaw Inst Comp Sci Wroclaw Poland

ISBN: (纸本)9783319642062;9783319642055

Dimensionality reduction methods for visualization attempt to preserve in the embedding as much of the original information as possible. However, projection to 2-D or 3-D heavily distorts the data. Instead, we propose a multipoint extension to neighbor embedding methods, which allows to express datapoints from a high-dimensional space as sets of datapoints in a low-dimensional space. Cardinality of those sets is not assumed a priori. Using gradient of the cost function, we derive an expression, which for every datapoint indicates its remote area of attraction. We use it as a heuristic that guides selection and placement of additional datapoints. We demonstrate the approach with multipoint t-SNE, and adapt the O(N logN) approximation for computing the gradient of t-SNE to our setting. Experiments show that the approach brings qualitative and quantitative gains, i. e., it expresses more pairwise similarities and multi-group memberships of individual datapoints, better preserving the local structure of the data.

关键词： Manifold learning Data visualization t-SNE barnes-hut algorithm

来源：评论

学校读者我要写书评

暂无评论

A Computationally Efficient Gravitational Search algorithm 17

A Computationally Efficient Gravitational Search Algorithm

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Rothwell, Alex Aleti, Aldeida Monash Univ Caulfield Vic Australia

ISBN: (纸本)9781450349390

Gravitational search algorithm (GSA) is a population-based optimisation technique that was originally developed to deal with high-dimensional search spaces. In recent years, GSA has been successfully applied to a wide range of problems. At every iteration, the algorithm calculates the gravitational force of each solution with respect to all other solutions, which has combinatorial complexity. In this paper, we propose an efficient way for calculating the force component of each solution, reducing the complexity of GSA from O(N-2) to O(N log (N)), where N is the population size. The experimental evaluation shows that the new algorithm is computationally efficient and cost effective.

关键词： Gravitational search algorithm barnes-hut algorithm

来源：评论

学校读者我要写书评

暂无评论

Extending aWork-Stealing Framework with Probabilistic Guards 45

Extending aWork-Stealing Framework with Probabilistic Guards

引用

45th International Conference on Parallel Processing (ICPP)

作者： Yoritaka, Hiroshi Matsui, Ken Yasugi, Masahiro Hiraishi, Tasuku Umatani, Seiji Kyushu Inst Technol Fukuoka Japan Kyoto Univ Kyoto Japan Nintendo Co Ltd Kyoto Kyoto Japan

ISBN: (纸本)9781509028252

We propose probabilistic guards and analyze their performance. To reduce the total task division cost, probabilistic guards can prevent thief workers from stealing small tasks from victim workers probabilistically. In this study, we have implemented probabilistic guards on a work-stealing framework called Tascell and have confirmed that they perform well. In theory, a thief may repeat an unbounded number of probabilistically prevented steal attempts until success if a victim uses a probabilistic guard that rejects steal attempts with a non-zero probability. Therefore, in this paper, we also propose a mechanism that invalidates probabilistic guards on demand by setting an upper limit to the number of repeated probabilistically prevented steal attempts. We evaluate its potential effects on probabilistic guards by measuring the actual numbers of repeated attempts until success. We also evaluate the performance of probabilistic guards with various upper limits. Finally, we propose and evaluate virtual probabilistic guards that act as probabilistic guards without repeating probabilistically prevented steal attempts and they exhibit superior performance.

关键词： parallel programming languages work stealing probability concurrency many-core barnes-hut algorithm

来源：评论

学校读者我要写书评

暂无评论

FAST AND ACCURATE DATA EXTRACTION FOR NEAR REAL-TIME REGISTRATION OF 3-D ULTRASOUND AND COMPUTED TOMOGRAPHY IN ORTHOPEDIC SURGERY

引用

ULTRASOUND IN MEDICINE AND BIOLOGY 2015年第12期41卷 3194-3204页

作者： Brounstein, Anna Hacihaliloglu, Ilker Guy, Pierre Hodgson, Antony Abugharbieh, Rafeef Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada Rutgers State Univ Dept Biomed Engn Piscataway NJ 08855 USA Univ British Columbia Dept Orthopaed Vancouver BC V5Z 1M9 Canada Univ British Columbia Dept Mech Vancouver BC V5Z 1M9 Canada

Automatic, accurate and real-time registration is an important step in providing effective guidance and successful anatomic restoration in ultrasound (US)-based computer assisted orthopedic surgery. We propose a method in which local phase-based bone surfaces, extracted from intra-operative US data, are registered to pre-operatively segmented computed tomography data. Extracted bone surfaces are downsampled and reinforced with high curvature features. A novel hierarchical simplification algorithm is used to further optimize the point clouds. The final point clouds are represented as Gaussian mixture models and iteratively matched by minimizing the dissimilarity between them using an L2 metric. For 44 clinical data sets from 25 pelvic fracture patients and 49 phantom data sets, we report mean surface registration accuracies of 0.31 and 0.77 mm, respectively, with an average registration time of 1.41 s. Our results suggest the viability and potential of the chosen method for real-time intra-operative registration in orthopedic surgery. (C) 2015 World Federation for Ultrasound in Medicine & Biology.

关键词： Ultrasound-computed tomography registration Point cloud matching Local phase features Curvature Gaussian mixture model registration Particle simulation barnes-hut algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：