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

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Li, Jason Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450369794

We present the firstm polylog(n) work, polylog(n) time algorithm in the PRAM model that computes (1 + epsilon)-approximate single-source shortest paths on weighted, undirected graphs. This improves upon the breakthrough result of Cohen [JACM'00] that achieves O(m(1+epsilon 0)) work and polylog(n) time. While most previous approaches, including Cohen's, leveraged the power of hopsets, our algorithm builds upon the recent developments in continuous optimization, studying the shortest path problem from the lens of the closely-related minimum transshipment problem. To obtain our algorithm, we demonstrate a series of near-linearwork, polylogarithmic-time reductions between the problems of approximate shortest path, approximate transshipment, and l(1)-embeddings, and establish a recursive algorithm that cycles through the three problems and reduces the graph size on each cycle. As a consequence, we also obtain faster parallel algorithms for approximate transshipment and l(1)-embeddings with polylogarithmic distortion. The minimum transshipment algorithm in particular improves upon the previous best m(1+o(1)) work sequential algorithm of Sherman [SODA'17]. To improve readability, the paper is almost entirely self-contained, save for several staple theorems in algorithms and combinatorics.

关键词： parallel algorithms Shortest Path Minimum Transshipment

来源：评论

学校读者我要写书评

暂无评论

MULTILEVEL SECOND-MOMENT METHODS WITH GROUP DECOMPOSITION FOR MULTIGROUP TRANSPORT PROBLEMS

MULTILEVEL SECOND-MOMENT METHODS WITH GROUP DECOMPOSITION FO...

引用

2021 International Conference on Mathematics and Computational Methods Applied to Nuclear Science and Engineering, M and C 2021

作者： Anistratov, Dmitriy Y. Coale, Joseph M. Warsa, James S. Chang, Jae H. Department of Nuclear Engineering North Carolina State University RaleighNC27695-7909 United States Los Alamos National Laboratory Los AlamosNM87545 United States

ISBN: (纸本)9781713886310

This paper presents multilevel iterative schemes for solving the multigroup Boltzmann transport equations (BTEs) with parallel calculation of group equations. They are formulated with multigroup and grey low-order equations of the Second-Moment (SM) method. The group high-order BTEs and low-order SM (LOSM) equations are solved in parallel. To further improve convergence and increase computational efficiency of algorithms Anderson acceleration is applied to inner iterations for solving the system of multigroup LOSM equations. Numerical results are presented to demonstrate performance of the multilevel iterative methods. Copyright © 2021 AMERICAN NUCLEAR SOCIETY, INCORPORATED, LA GRANGE PARK, ILLINOIS *** rights reserved.

关键词： Anderson acceleration Boltzmann equation iterative methods multigroup problems parallel algorithms particle transport

来源：评论

学校读者我要写书评

暂无评论

GPU parallel Computation of Morse-Smale Complexes

GPU Parallel Computation of Morse-Smale Complexes

引用

IEEE Visualization Conference (VIS)

作者： Subhash, Varshini Pandey, Karran Natarajan, Vijay Indian Inst Sci Dept Comp Sci & Automat Bangalore Karnataka India

ISBN: (纸本)9781728180144

The Morse-Smale complex is a well studied topological structure that represents the gradient flow behavior of a scalar function. It supports multi-scale topological analysis and visualization of large scientific data. Its computation poses significant algorithmic challenges when considering large scale data and increased feature complexity. Several parallel algorithms have been proposed towards the fast computation of the 3D Morse-Smale complex. The non-trivial structure of the saddle-saddle connections are not amenable to parallel computation. This paper describes a fine grained parallel method for computing the Morse-Smale complex that is implemented on a GPU. The saddle-saddle reachability is first determined via a transformation into a sequence of vector operations followed by the path traversal, which is achieved via a sequence of matrix operations. Computational experiments show that the method achieves up to 7 x speedup over current shared memory implementations.

关键词： Human-centered computing Visualization Visualization techniques Computing methodologies parallel computing methodologies parallel algorithms Shared memory algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Algorithm for Non-Monotone DR-Submodular Maximization 37

Parallel Algorithm for Non-Monotone DR-Submodular Maximizati...

引用

International Conference on Machine Learning (ICML)

作者： Ene, Alina Nguyen, Huy L. Boston Univ Dept Comp Sci 111 Cummington St Boston MA 02215 USA Northeastern Univ Khoury Coll Comp & Informat Sci Boston MA 02115 USA

ISBN: (纸本)9781713821120

In this work, we give a new parallel algorithm for the problem of maximizing a non-monotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy epsilon, our algorithm achieves a 1/epsilon - epsilon approximation using O(log n log(1/epsilon)epsilon(3)) parallel rounds of function evaluations. The approximation guarantee nearly matches the best approximation guarantee known for the problem in the sequential setting and the number of parallel rounds is nearly-optimal for any constant epsilon. Previous algorithms achieve worse approximation guarantees using Omega(log(2) n) parallel rounds. Our experimental evaluation suggests that our algorithm obtains solutions whose objective value nearly matches the value obtained by the state of the art sequential algorithms, and it outperforms previous parallel algorithms in number of parallel rounds, iterations, and solution quality.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A parallel Many-core CUDA-based Graph Labeling Computation 15

A Parallel Many-core CUDA-based Graph Labeling Computation

引用

15th International Conference on Software Technologies (ICSOFT)

作者： Quer, Stefano Politecn Torino Dept Control & Comp Engn DAUIN Turin Italy

ISBN: (纸本)9789897584435

When working on graphs, reachability is among the most common problems to address, since it is the base for many other algorithms. As with the advent of distributed systems, which process large amounts of data, many applications must quickly explore graphs with millions of vertices, scalable solutions have become of paramount importance. Modern GPUs provide highly parallel systems based on many-core architectures and have gained popularity in parallelizing algorithms that run on large data sets. In this paper, we extend a very efficient state-of-the-art graph-labeling method, namely the GRAIL algorithm, to architectures which exhibit a great amount of data parallelism, i.e., many-core CUDA-based GPUs. GRAIL creates a scalable index for answering reachability queries, and it heavily relies on depth-first searches. As depth-first visits are intrinsically recursive and they cannot be efficiently implemented on parallel systems, we devise an alternative approach based on a sequence of breadth-first visits. The paper explores our efforts in this direction, and it analyzes the difficulties encountered and the solutions chosen to overcome them. It also presents a comparison (in terms of times to create the index and to use it for reachability queries) between the CPU and the GPU-based versions.

关键词： Graph Theory Graph algorithms Algorithm Design and Analysis parallel algorithms Graphics Processors

来源：评论

学校读者我要写书评

暂无评论

parallel Data Partitioning algorithms for Optimization of Data-parallel Applications on Modern Extreme-Scale Multicore Platforms for Performance and Energy

引用

IEEE ACCESS 2018年 6卷 69075-69106页

作者： Manumachu, Ravi Reddy Lastovetsky, Alexey Univ Coll Dublin Sch Comp Sci Dublin D04 V1W8 4 Ireland

Data partitioning algorithms aiming to minimize the execution time and the energy of computations in self-adaptable data-parallel applications on modern extreme-scale multicore platforms must address two critical challenges. First, they must take into account the new complexities inherent in these platforms such as severe resource contention and non-uniform memory access. Second, they must have low practical runtime and memory costs. The sequential data partitioning algorithms addressing the first challenge have a theoretical time complexity of O(m*m*p*p) where m is the number of points in the discrete speed/energy function and p is the number of available processors. They, however, exhibit high practical runtime cost and excessive memory footprint, therefore, rendering them impracticable for employment in self-adaptable applications executing on extreme-scale multicore platforms. We present, in this paper, the parallel data partitioning algorithms that address both the challenges. They take as input the functional models of performance and energy consumption against problem size and output workload distributions, which are globally optimal solutions. They have a low time complexity of O(m*m*p) thereby providing a linear speedup of O(p) and low memory complexity of O(n) where n is the workload size expressed as a multiple of granularity. They employ dynamic programming approach, which also facilitates the easier integration of performance and energy models of communications. We experimentally study the practical cost of application of our algorithms in two data-parallel applications, matrix multiplication and fast Fourier transform, on a cluster in Grid'5000 platform. We demonstrate that their practical runtime and memory costs are low making them ideal for employment in self-adaptable applications. We also show that the parallel algorithms exhibit tremendous speedups over the sequential algorithms. Finally, using theoretical analysis for a forecast exascale platfor

关键词： Data parallelism data partitioning energy energy optimization homogeneous multicore CPU clusters load balancing parallel algorithms performance performance optimization

来源：评论

学校读者我要写书评

暂无评论

Research on parallel Yen algorithms on GPUs using CUDA

Research on Parallel <i>Yen</i> Algorithms on GPUs using CUD...

引用

International Forum on Computer and Information Technology (IFCIT)

作者： Li JianFu Civil Aviat Univ China Sch Comp Sci & Technol Tianjin 300300 Peoples R China

ISBN: (纸本)9783038350194

With the arrival of the intermodality era, to design fast and efficient K shortest paths(KSP) algorithms becomes gradually one of the core technologies in traveler information systems. Yen is a classical algorithm for KSP. However, Yen is time-consuming. In view of powerful general-purpose computing capabilities, GPU(Graphics Processing Units) has received increasing attention in various fields. Based on CUDA software development environment, combined with the structure of the Yen algorithm itself, this paper proposed two parallel algorithms for Yen. The first parallel algorithm computes candidate shortest paths for very possible deviation nodes in parallel. The second one computes candidate shortest paths in serial, but computes very candidate path in parallel. Finally, the efficiency of the two parallel algorithms was tested through experiments.

关键词： K Shortest Paths Yen parallel algorithms GPU(Graphics Processing Units)

来源：评论

学校读者我要写书评

暂无评论

Depth-First Search in Directed Planar Graphs, Revisited 46

Depth-First Search in Directed Planar Graphs, Revisited

引用

46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021

作者： Allender, Eric Chauhan, Archit Datta, Samir Rutgers University PiscatawayNJ United States Chennai Mathematical Institute India

ISBN: (纸本)9783959772013

We present an algorithm for constructing a depth-first search tree in planar digraphs;the algorithm can be implemented in the complexity class AC1(UL ∩ co-UL), which is contained in AC2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log10 n) (corresponding to the complexity class AC10 ⊆ NC11). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds. © Eric Allender, Archit Chauhan, and Samir Datta;licensed under Creative Commons License CC-BY 4.0 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021).

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks 35

Wake up and join me! An energy-efficient algorithm for maxim...

引用

35th International Symposium on Distributed Computing, DISC 2021

作者： Dani, Varsha Gupta, Aayush Hayes, Thomas P. Pettie, Seth Department of Computer Science Rochester Institute of Technology NY United States Department of Computer Science University of New Mexico AlbuquerqueNM United States Computer Science and Engineering University of Michigan Ann ArborMI United States

ISBN: (纸本)9783959772105

We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is O(log2 n), and the time complexity is O(∆ log n). Here n is any upper bound on the number of nodes, and ∆ is any upper bound on the maximum degree;n and ∆ are parameters of our algorithm that we assume are known a priori to all the processors. We note that there exist families of graphs for which our bounds on energy cost and time complexity are simultaneously optimal up to polylog factors, so any significant improvement would need additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of eventual node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present an efficient decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog(n) factor bigger that the optimum. © Varsha Dani, Aayush Gupta, Thomas P. Hayes, and Seth Pettie;licensed under Creative Commons License CC-BY 4.0

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel two-stage algorithms for solving the PageRank problem

引用

ADVANCES IN ENGINEERING SOFTWARE 2018年 125卷 188-199页

作者： Migallon, Hector Migallon, Violeta Penades, Jose Univ Miguel Hernandez Dept Phys & Comp Architectures E-03202 Elche Alicante Spain Univ Alicante Dept Comp Sci & Artificial Intelligence E-03071 Alicante Spain

In this work we present parallel algorithms based on the use of two-stage methods for solving the PageRank problem as a linear system. Different parallel versions of these methods are explored and their convergence properties are analyzed. The parallel implementation has been developed using a mixed MPI/OpenMP model to exploit parallelism beyond a single level. In order to investigate and analyze the proposed parallel algorithms, we have used several realistic large datasets. The numerical results show that the proposed algorithms can speed up the time to converge with respect to the parallel Power algorithm and behave better than other well-known techniques.

关键词： PageRank parallel algorithms Two-stage methods Shared memory Distributed memory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：