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

parallel FFT algorithms for high-order approximations on three-dimensional compact stencils

parallel COMPUTING 2021年 103卷 102757-102757页

作者： Gonzales, Ronald Gryazin, Yury Lee, Yun Teck Idaho State Univ Dept Math & Stat 921 S 8th AveStop 8085 Pocatello ID 83209 USA

The recent development of multicore technologies on modern desktop computers makes parallelization of the proposed numerical approaches a priority in algorithmic research. The main performance improvement of personal computers in the upcoming years will be made based on the increasing number of cores on modern CPUs. This shifts the focus of algorithmic research from the development of sequential numerical methods to parallel methodology. This paper presents an efficient parallel direct algorithm with near-optimal complexity for the compact fourth and sixth-order approximation of the three-dimensional Helmholtz equations (Turkel et al., 2013) with the problem coefficient depending on only one of the coordinate directions. The developed method is based on a combination of the separation of variables technique and a Fast Fourier Transform (FFT) type method. Similar direct solvers for the lower-order approximations of the two and three-dimensional Helmholtz equation were considered in several previous publications by the authors and other researchers (see, e.g. Gryazin et al. (2000);Gryazin (2014);Elman and O'Leary (1998);Elman and O'Leary (1999);Toivanen and Wolfmayr (2020)). The authors also consider a generalization of the presented algorithm to the solution of a wide class of linear systems obtained from approximation on the compact 27-point three-dimensional stencils on the rectangular grids with similar requirements on the stencil coefficients. The general restrictions on the coefficients in the considered class of compact schemes are developed and presented. This class includes the second, fourth and sixth-order compact approximation schemes for the three-dimensional Helmholtz equation considered in this paper and our previous publications (Gryazin et al., 2000;Gryazin, 2014;Gryazin, 2014). As an example of the diversity of applications of the developed general method, the direct parallel implementation of a compact fourth-order approximation scheme for a convect

关键词： Compact finite-difference schemes FFT parallel algorithms OpenMP MPI Hybrid

来源：评论

学校读者我要写书评

暂无评论

Practical parallel Hypergraph algorithms 20

Practical Parallel Hypergraph Algorithms

引用

25th ACM SIGPLAN Symposium on Principles and Practice of parallel Programming (PPoPP)

作者： Shun, Julian MIT CSAIL Cambridge MA 02139 USA

ISBN: (纸本)9781450368186

While there has been significant work on parallel graph processing, there has been very surprisingly little work on high-performance hypergraph processing. This paper presents a collection of efficient parallel algorithms for hypergraph processing, including algorithms for betweenness centrality, maximal independent set, k-core decomposition, hyper-trees, hyperpaths, connected components, PageRank, and single-source shortest paths. For these problems, we either provide new parallel algorithms or more efficient implementations than prior work. Furthermore, our algorithms are theoretically-efficient in terms of work and depth. To implement our algorithms, we extend the Ligra graph processing framework to support hypergraphs, and our implementations benefit from graph optimizations including switching between sparse and dense traversals based on the frontier size, edge-aware parallelization, using buckets to prioritize processing of vertices, and compression. Our experiments on a 72-core machine and show that our algorithms obtain excellent parallel speedups, and are *** faster than algorithms in existing hypergraph processing frameworks.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms of Multi-relaxation-time Lattice Boltzmann Method

Parallel Algorithms of Multi-relaxation-time Lattice Boltzma...

引用

1st International Conference on Advanced algorithms and Control Engineering, ICAACE 2018

作者： Xu, Lei Cheng, Pan Liu, Zhixiang Zhang, Wu School of Computer Engineering and Science Shanghai University Shanghai200444 China Shanghai Aircraft Design and Research Institute Shanghai201210 China College of Information Shanghai Ocean University Shanghai201306 China

The lattice Boltzmann method has become an attractive and promising approach in computational fluid dynamics. In this paper, the D3Q19 multi-relaxation-time lattice Boltzmann method is employed to simulate complex fluid flow and its parallel algorithm is presented including Cartesian grid generation, domain decomposition method, and data exchange strategy on clusters. Considering load balancing on large scale cluster, details of domain decomposition method are presented. The numerical results show that the presented algorithm have considerable scalability on 2048 cores and the efficiency can achieve 92.01%. © Published under licence by IOP Publishing Ltd.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel and distributed algorithms for the housing allocation problem 23

Parallel and distributed algorithms for the housing allocati...

引用

23rd International Conference on Principles of Distributed Systems, OPODIS 2019

作者： Zheng, Xiong Garg, Vijay K. Electrical and Computer Engineering Department University of Texas Austin United States

ISBN: (纸本)9783959771337

We propose parallel and distributed algorithms for the housing allocation problem. In this problem, there is a set of agents and a set of houses. Each agent has a strict preference list for a subset of houses. We need to find a matching for agents to houses such that some criterion is optimized. One such criterion which has attracted much attention is Pareto optimality. A matching is Pareto optimal if no coalition of agents can be strictly better off by exchanging houses among themselves. We also study the housing market problem, a variant of the housing allocation problem, where each agent initially owns a house. In addition to Pareto optimality, we are also interested in finding the a matching in the core of a housing market. A matching is in the core if there is no coalition of agents that can be better off by breaking away from other agents and switching houses only among themselves in the initial allocation. In the first part of this work, we show that computing a Pareto optimal matching of a house allocation is in CC and computing a matching in the core of a housing market is CC-hard, where CC is the class of problems logspace reducible to the comparator circuit value problem. Given a matching of agents to houses, we show that verifying whether it is Pareto optimal is in NC. We also show that verifying whether it is in the core can be done in NC. We then give an algorithm to show that computing a maximum cardinality Pareto optimal matching for the housing allocation problem is in RNC2 and quasi-NC2. In the second part of this work, we present a distributed version of the top trading cycle algorithm for finding a matching in the core of a housing market. To that end, we first present two algorithms for finding all the disjoint cycles in a functional graph. The first algorithm is a Las Vegas algorithm which terminates in O(log l) rounds with high probability, where l is the length of the longest cycle. The second algorithm is a deterministic algorithm which term

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel graph algorithms by blocks: from I/O to algorithms 21

Parallel graph algorithms by blocks: from I/O to algorithms

引用

Proceedings of the 18th ACM International Conference on Computing Frontiers

作者： Abdurrahman Yaşar Kasimir Gabert Ümit V. Çatalyürek Georgia Institute of Technology

ISBN: (纸本)9781450384049

In today's data-driven world and heterogeneous computing environments, processing large-scale graphs in an architecture agnostic manner has become more crucial than ever before. In terms of graph analytics frameworks, on the one side, there has been a significant interest in developing hand-optimized high-performance computing solutions. On the systems side, following the big data movement and to bring parallel computing to the masses, researchers have proposed several graph processing and management systems to handle large-scale graphs. Hand optimized HPC approaches require high expertise and are expensive to maintain and develop, and graph processing frameworks suffer from limited expressibility and performance. We propose parallel Graph algorithms by Blocks (PGAbB), a block-based graph algorithms framework for shared-memory, multi-core, multi-GPU machines. PGAbB offers a sweet spot between efficient parallelism and architecture agnostic algorithm design for a wide class of graph problems while performing close to hand-optimized HPC *** our PGAbB framework, as well as many other recent HPC graph-analytics frameworks, are highly tuned and able to run complex graph analytics in fractions of seconds on billion-edge graphs, there remains a gap in their end-to-end use. Despite the significant improvements that modern hardware and operating systems have made towards input and output, reading the graph from file systems easily takes thousands of times longer than running the computational kernel itself. This slowdown causes both a disconnect for end users and a loss of productivity for researchers and developers. We close this gap by providing a simple to use, small, header-only, and dependency-free C++11 library, PIGO, that brings I/O improvements to graph and sparse matrix systems. Using PIGO, we improve the end-to-end performance for state-of-the-art systems significantly---in many cases by over 40X.

关键词： parallel I/O parallel algorithms graphs algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel in-place algorithms: Theory and practice

arXiv

引用

arXiv 2021年

作者： Gu, Yan Obeya, Omar Shun, Julian UC Riverside United States MIT CSAIL United States

Many parallel algorithms use at least linear auxiliary space in the size of the input to enable computations to be done independently without conflicts. Unfortunately, this extra space can be prohibitive for memory-limited machines, preventing large inputs from being processed. Therefore, it is desirable to design parallel in-place algorithms that use sublinear (or even polylogarithmic) auxiliary space. In this paper, we bridge the gap between theory and practice for parallel in-place (PIP) algorithms. We first define two computational models based on fork-join parallelism, which reflect modern parallel programming environments. We then introduce a variety of new parallel in-place algorithms that are simple and efficient, both in theory and in practice. Our algorithmic highlight is the Decomposable Property introduced in this paper, which enables existing non-in-place but highly-optimized parallel algorithms to be converted into parallel in-place algorithms. Using this property, we obtain algorithms for random permutation, list contraction, tree contraction, and merging that take linear work, (formula presented) auxiliary space, and(formula presented) · polylog(formula presented) span for (formula presented). We also present new parallel in-place algorithms for scan, filter, merge, connectivity, biconnectivity, and minimum spanning forest using other techniques. In addition to theoretical results, we present experimental results for implementations of many of our parallel in-place algorithms. We show that on a 72-core machine with two-way hyper-threading, the parallel in-place algorithms usually outperform existing parallel algorithms for the same problems that use linear auxiliary space, indicating that the theory developed in this paper indeed leads to practical benefits in terms of both space usage and running time. © 2021, CC BY.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Sequential and parallel algorithms for Incremental Record Linkage Using Complete Linkage Clustering

Efficient Sequential and Parallel Algorithms for Incremental...

引用

IEEE International Conference on Bioinformatics and Biomedicine

作者： Abdullah Baihan Sanguthevar Rajasekaran Computer Science and Engineering University of Connecticut

ISBN: (纸本)9781728118680

In the biomedical domain, the record linkage is considered as a crucial problem. When the number of records is very large, existing algorithms for record linkage take too much time. Often, we have to link a small set of new records with a large set of old records. This can be done by putting together the old and new records and performing a linkage on all the records. Clearly, this will call for an enormous amount of time. An alternative is to develop algorithms that perform linkage in an incremental manner. We refer to any such algorithm as an Incremental Record Linkage (IRL) algorithm. In this paper we present an efficient IRL algorithm. In addition to taking large amounts of time, existing algorithms might also suffer from a chaining problem and hence introduce some errors in linking. As has been observed in the literature, this chaining problem can be solved by performing clustering under complete linkage. The IRL algorithm we present in this paper employs complete linkage and is called as Incremental Record Linking Algorithm using Complete Linkage "IRLA-CL". We propose sequential and parallel versions of this algorithm. IRLA-CL can handle any number of datasets. In contrast, many of the existing algorithms can only link two datasets at a time. Our algorithm outperforms previous algorithms and offer state-of-the-art solutions to the IRL problem as well. Our algorithms have been tested on millions of records on synthetic and real datasets and outperform the best-known RLA-CL algorithm when the number of new records is up to around 20% of the total number of old records and achieve a very nearly linear speedup in parallel.

关键词： Incremental Record Linkage Edit Distance Blocking parallel Computing Hierarchical Clustering algorithms parallel PROCESSING (COMPUTERS) New records parallel algorithms IRL BLOCKING DVD Audio Incremental Dataset

来源：评论

学校读者我要写书评

暂无评论

Investigating the Efficiency of parallel algorithms for Stochastic Optimization

Investigating the Efficiency of Parallel Algorithms for Stoc...

引用

International Conference on Complex Systems: Control and Modeling Problems

作者： Marat Voronukhin Valery Zasov Samara State Transport University

ISBN: (纸本)9781728167015

The paper presents the results of investigating the efficiency indicators of two parallel algorithms for stochastic optimization - the genetic algorithm and the particle-swarm algorithm. The paper discusses experimental relationships for the efficiency indicators of the parallel algorithms: runtime, acceleration, error, and solution stability, depending on the type and dimension of the target function, the number of agents used, and processor cores. The comparative estimates for the algorithms are given.

关键词： Stochastic optimization Genetic algorithm Swarm algorithm parallel computing Efficiency indicators Acceleration Stability Error Computational experiments Software package parallel algorithms Software packages parallel PROCESSING (COMPUTERS) Genetic Algorithm (GA) acceleration Stochastic acceleration error

来源：评论

学校读者我要写书评

暂无评论

New parallel algorithms for All Pairwise Computation on Large HPC Clusters

New Parallel Algorithms for All Pairwise Computation on Larg...

引用

IEEE International Conference on parallel and Distributed Computing, Applications and Technologies (PDCAT)

作者： Tao Tang Hao Wu Wei Bao Pengyi Yang Dong Yuan Bing Bing Zhou Faculty of Engineering and IT University of Technology Sydney Sydney Australia School of Computer Science University of Sydney Sydney Australia School of Mathematics & Statistics University of Sydney Sydney Australia School of Elec. & Inf. Engineering University of Sydney Sydney Australia

ISBN: (数字)9781728126166

ISBN: (纸本)9781728126173

All pairwise computation is defined as performing computation between every pair of the elements in a given dataset. It is often a necessary first step in a number of bioinformatics applications. Many of such applications require multiple terabytes of main memory and take multiple peta floating point operations to complete the computation. Therefore, large HPC clusters are needed to tackle these large-scale computational problems. Conventionally designed parallel algorithms using data partitioning may have a scalability issue, i.e., for a given problem of fixed size the efficiency may decrease if the number of compute nodes is increased (Amdahl's law). In this paper we introduce a new method for parallel algorithm design. Using this method we first design an efficient one-dimensional (1D) ring algorithm and then a two-dimensional (2D) algorithm based on the 1D ring for all pairwise computation. When increasing the compute nodes, instead of reducing the block size, we make multiple copies of the original data blocks in the 1D ring and distribute them across the added compute nodes in the other dimension. By properly organizing the compute nodes the communication overhead can be reduced to a minimum in this two-dimensional setting. Experiments on a Cray XC40 HPC supercomputer show that our new algorithms are very efficient and scalable for large-scale all pairwise computation on large HPC clusters.

关键词： parallel algorithms Clustering algorithms Australia Two dimensional displays Partitioning algorithms Task analysis Correlation

来源：评论

学校读者我要写书评

暂无评论

Novel Data Segmentation Techniques for Efficient Discovery of Correlated Patterns Using parallel algorithms 1

引用

20th International Conference on Big Data Analytics and Knowledge Discovery (DaWaK)

作者： Kotni, Amulya Kiran, R. Uday Toyoda, Masashi Reddy, P. Krishna Kitsuregawa, Masaru Int Inst Informat Technol Hyderabad Telangana India Univ Tokyo Inst Ind Sci Tokyo Japan Natl Inst Informat & Commun Technol Tokyo Japan Natl Inst Informat Tokyo Japan

ISBN: (数字)9783319985398

ISBN: (纸本)9783319985398;9783319985381

Efficient discovery of interesting patterns using parallel algorithms is an actively studied topic in data mining. A key research issue related to this topic is data segmentation, which influences the overall computational requirements of an algorithm. This paper makes an effort to address this issue in correlated pattern mining. Two novel data segmentation techniques, 'database segmentation' and 'transaction segmentation,' have been introduced to discover the patterns efficiently. The former technique involves segmenting the database into multiple sub-databases such that each sub-database can be mined independently. The latter technique involves segmenting a transaction into multiple sub-transactions such that each sub-transaction can be processed as an individual transaction. The proposed techniques are algorithm independent, and therefore, can be incorporated into any parallel algorithm to find correlated patterns effectively. In this paper, we introduce map-reduce based pattern-growth algorithm by incorporating the above mentioned techniques. Experimental results demonstrate that the proposed algorithm is memory and runtime efficient and highly scalable as well.

关键词： Data mining Knowledge discovery in databases parallel algorithms Correlated patterns and map-reduce

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：