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

35th acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Sachdeva, Sushant Zhao, Yibin Univ Toronto Toronto ON Canada

ISBN: (纸本)9781450395458

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear systems in nearly linear time, several algorithms have been designed for the task. Yet, the work of Kyng and Sachdeva (2016) remains the simplest and most practical sequential solver. They presented a solver purely based on random sampling and without graph-theoretic constructions such as low-stretch trees and sparsifiers. In this work, we extend the result of Kyng and Sachdeva to a simple parallel Laplacian solver with O(m log(3) n log log n) or O((m + n log(5) n) log n log log n) work and O(log(2) n log log n) depth using the ideas of block Cholesky factorization from Kyng et al. (2016). Compared to the best known parallel Laplacian solvers that achieve polylogarithmic depth due to Lee et al. (2015), our solver achieves both better depth and, for dense graphs, better work.

关键词： Laplacian Linear Systems parallel algorithms Linear System Solvers

来源：评论

学校读者我要写书评

暂无评论

Just join for parallel ordered sets 16

Just join for parallel ordered sets

引用

28th acm symposium on parallelism in algorithms and architectures, SPAA 2016

作者： Blelloch, Guy E. Ferizovic, Daniel Sun, Yihan Carnegie Mellon University United States Karlsruhe Institute of Technology Germany

ISBN: (纸本)9781450342100

Ordered sets (and maps when data is associated with each key) are one of the most important and useful data types. The set-set functions union, intersection and difference are particularly useful in certain applications. Brown and Tarjan first described an algorithm for these functions, based on 2-3 trees, that meet the optimal θ m log(n/m + 1)) time bounds in the comparison model (n and m ≤ n are the input sizes). Later Adams showed very elegant algorithms for the functions, and others, based on weight-balanced trees. They only require a single function that is specific to the balancing scheme - a function that joins two balanced trees-and hence can be applied to other balancing schemes. Furthermore the algorithms are naturally parallel. However, in the twenty-four years since, no one has shown that the algorithms, sequential or parallel are asymptotically work optimal. In this paper we show that Adams' algorithms are both work efficient and highly parallel (polylog span) across four different balancing schemes-AVL trees, red-black trees, weight balanced trees and treaps. To do this we use careful, but simple, algorithms for JOIN that maintain certain invariants, and our proof is (mostly) generic across the schemes. To understand how the algorithms perform in practice we have also implemented them (all code except JOIN is generic across the balancing schemes). Interestingly the implementations on all four balancing schemes and three set functions perform similarly in time and speedup (more than 45x on 64 cores). We also compare the performance of our implementation to other existing libraries and algorithms. © 2016 acm.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Space-efficient scheduling of parallelism with synchronization variables 97

Space-efficient scheduling of parallelism with synchronizati...

引用

Proceedings of the 1997 9th annual acm symposium on parallel algorithms and architectures, SPAA

作者： Blelloch, Guy E. Gibbons, Phillip B. Matias, Yossi Narlikar, Girija J. Carnegie Mellon Pittsburgh PA United States

ISBN: (纸本)9780897918909

Recent work on scheduling algorithms has resulted in provable bounds on the space taken by parallel computations in relation to the space taken by sequential computations. The results for online versions of these algorithms, however, have been limited to computations in which threads can only synchronize with ancestor or sibling threads. Such computations do not include languages with futures or user-specified synchronization constraints. Here we extend the results to languages with synchronization variables. Such languages include languages with futures, such as Multilisp and Cool, as well as other languages such as ID. The main result is an online scheduling algorithm which, given a computation with w work (total operations), σ synchronizations, d depth (critical path) and s1 sequential space, will run in O(w/p+σlog(pd)/p+d log(pd)) time and s1+O(pd log (pd)) space, on a p-processor CRCW PRAM with a fetch-and-add primitive. This includes all time and space costs for both the computation and the scheduler. The scheduler is non-preemptive in the sense that it will only move a thread if the thread suspends on a synchronization, forks a new thread, or exceeds a threshold when allocating space. For the special case where the computation is a planar graph with left-to-right synchronization edges, the scheduling algorithm can be implemented in O(w/p+d log p) time and s1+O(pd log p) space. These are the first non-trivial space bounds described for such languages.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Bandwidth Optimized parallel algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking 20

Bandwidth Optimized Parallel Algorithms for Sparse Matrix-Ma...

引用

32nd acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Gu, Zhixiang Moreira, Jose Edelsohn, David Azad, Ariful Indiana Univ Bloomington IN 47405 USA IBM Corp Armonk NY 10504 USA Facebook Inc Menlo Pk CA 94025 USA

ISBN: (纸本)9781450369350

Sparse matrix-matrix multiplication (SpGEMM) is a widely used kernel in various graph, scientific computing and machine learning algorithms. It is well known that SpGEMM is a memory-bound operation, and its peak performance is expected to be bound by the memory bandwidth. Yet, existing algorithms fail to saturate the memory bandwidth, resulting in suboptimal performance under the Roofline model. In this paper, we characterize existing SpGEMM algorithms based on their memory access patterns and develop practical lower and upper bounds for SpGEMM performance. We then develop an SpGEMM algorithm based on the outer product. The newly developed algorithm called PB-SpGEMM saturates memory bandwidth by using the propagation blocking technique and by performing in-cache sorting and merging. For many practical matrices, PB-SpGEMM runs 20%-50% faster than the state-of-the-art heap and hash SpGEMM algorithms on modern multicore processors. Most importantly, PB-SpGEMM attains performance predicted by the Roofline model, and its performance remains stable with respect to matrix size and sparsity.

关键词： parallel algorithm SpGEMM

来源：评论

学校读者我要写书评

暂无评论

Provably-Efficient and Internally-Deterministic parallel Union-Find 23

Provably-Efficient and Internally-Deterministic Parallel Uni...

引用

35th acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Fedorov, Alexander Hashemi, Diba Nadiradze, Giorgi Alistarh, Dan IST Austria Klosterneuburg Austria

ISBN: (纸本)9781450395458

Determining the degree of inherent parallelism in classical sequential algorithms and leveraging it for fast parallel execution is a key topic in parallel computing, and detailed analyses are known for a wide range of classical algorithms. In this paper, we perform the first such analysis for the fundamental Union-Find problem, in which we are given a graph as a sequence of edges, and must maintain its connectivity structure under edge additions. We prove that classic sequential algorithms for this problem are well-parallelizable under reasonable assumptions, addressing a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential argument that, under uniform random edge ordering, parallel union-find operations are unlikely to interfere: T concurrent threads processing the graph in parallel will encounter memory contention O(T-2 center dot log vertical bar V vertical bar center dot log vertical bar E vertical bar) times in expectation, where vertical bar E vertical bar and vertical bar V vertical bar are the number of edges and nodes in the graph, respectively. We leverage this result to design a new parallel Union-Find algorithm that is both internally deterministic, i.e., its results are guaranteed to match those of a sequential execution, but also work-efficient and scalable, as long as the number of threads T is O(vertical bar E vertical bar(1/3-epsilon)), for an arbitrarily small constant epsilon > 0, which holds for most large real-world graphs. We present lower bounds which show that our analysis is close to optimal, and experimental results suggesting that the performance cost of internal determinism is limited.

关键词： union-find parallel algorithms graph algorithms deterministic parallelism

来源：评论

学校读者我要写书评

暂无评论

Buffer-space Efficient and Deadlock-free Scheduling of Stream Applications on Multi-core architectures 10

Buffer-space Efficient and Deadlock-free Scheduling of Strea...

引用

22nd acm symposium on parallelism in algorithms and architectures

作者： Park, Jongsoo Dally, William J. Stanford Univ Comp Syst Lab Stanford CA 94305 USA

ISBN: (纸本)9781450300797

We present a scheduling algorithm of stream programs for multi-core architectures called team scheduling Compared to previous multi-core stream scheduling algorithms, team scheduling achieves 1) similar synchronization overhead, 2) coverage of a larger class of applications, 3) better control over buffer space, 4) deadlock-free feedback loops, and 5) lower latency We compare team scheduling to the latest stream scheduling algorithm, SGMS, by evaluating 14 applications on a multi-core architecture with 16 cores. Team scheduling successfully targets applications that cannot be validly scheduled by SGMS clue to excessive buffer requirement or deadlocks in feedback loops (e.g., GSM and W-cDmA) For applications that can be validly scheduled by SGMS, team scheduling shows on average 37% higher throughput within the same buffer space constraints

关键词： Compiler and Tools for Concurrent Programming Stream Programming Green Computing and Power-Efficient architectures Multi-core architectures

来源：评论

学校读者我要写书评

暂无评论

A 3D parallel Algorithm for QR Decomposition 18

A 3D Parallel Algorithm for QR Decomposition

引用

30th acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Ballard, Grey Demmel, James Grigori, Laura Jacquelin, Mathias Knight, Nicholas Wake Forest Univ Winston Salem NC 27101 USA Univ Calif Berkeley Berkeley CA 94720 USA INRIA Paris Rocquencourt Paris France Lawrence Berkeley Natl Lab Berkeley CA USA NYU New York NY USA

ISBN: (纸本)9781450357999

Interprocessor communication often dominates the runtime of large matrix computations. We present a parallel algorithm for computing QR decompositions whose bandwidth cost (communication volume) can be decreased at the cost of increasing its latency cost (number of messages). By varying a parameter to navigate the bandwidth/latency tradeoff, we can tune this algorithm for machines with different communication costs.

关键词： communication-avoiding algorithms bandwidth-latency tradeoffs communication-memory tradeoffs

来源：评论

学校读者我要写书评

暂无评论

Massively parallel algorithms for b-Matching* 22

Massively Parallel Algorithms for b-Matching*

引用

34th acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Ghaffari, Mohsen Grunau, Christoph Mitrovic, Slobodan Swiss Fed Inst Technol Zurich Switzerland Univ Calif Davis Davis CA USA

ISBN: (纸本)9781450391467

This paper presents an O (log log (d) over bar) round massively parallel algorithm for 1 +epsilon approximation of maximum weighted b-matchings, using near-linear memory per machine. Here (d) over bar denotes the average degree in the graph and epsilon is an arbitrarily small positive constant. Recall that b -matching is the natural and well-studied generalization of the matching problem where different vertices are allowed to have different numbers of incident edges in the matching. Concretely, each vertex v is given a positive integer budget b(v) and it can have up to b(v) incident edges in the matching. Previously, there were known algorithms with round complexity O (log log n), or O(log logn) where Delta denotes maximum degree, for 1 + epsilon approximation of weighted matching and for maximal matching [Czumaj et al., STOC'18, Ghaffari et al. PODC'18;Assadi et al. SODA'19;Behnezhad et al. FOCS'19;Gamlath et al. PODC'19]. But these algorithms do not extend to the more general b-matching problem.

关键词： matchings approximate b-matchings massively parallel computation MPC

来源：评论

学校读者我要写书评

暂无评论

A Fast Algorithm for Aperiodic Linear Stencil Computation using Fast Fourier Transforms

引用

acm TRANSACTIONS ON parallel COMPUTING 2023年第4期10卷 1-34页

作者： Ahmad, Zafar Chowdhury, Rezaul Das, Rathish Ganapathi, Pramod Gregory, Aaron Zhu, Yimin SUNY Stony Brook Stony Brook NY 11794 USA Univ Houston Houston TX USA

Stencil computations are widely used to simulate the change of state of physical systems across a multidimensional grid over multiple timesteps. The state-of-the-art techniques in this area fall into three groups: cache-aware tiled looping algorithms, cache-oblivious divide-and-conquer trapezoidal algorithms, and Krylov subspace methods. In this article, we present two efficient parallel algorithms for performing linear stencil computations. Current direct solvers in this domain are computationally inefficient, and Krylov methods require manual labor and mathematical training. We solve these problems for linear stencils by using discrete Fourier transforms preconditioning on a Krylov method to achieve a direct solver that is both fast and general. Indeed, while all currently available algorithms for solving general linear stencils perform T(NT) work, where N is the size of the spatial grid and T is the number of timesteps, our algorithms perform o ( NT) work. To the best of our knowledge, we give the first algorithms that use fast Fourier transforms to compute final grid data by evolving the initial data for many timesteps at once. Our algorithms handle both periodic and aperiodic boundary conditions and achieve polynomially better performance bounds (i.e., computational complexity and parallel runtime) than all other existing solutions. Initial experimental results show that implementations of our algorithms that evolve grids of roughly 107 cells for around 105 timesteps run orders of magnitude faster than state-of-the-art implementations for periodic stencil problems, and 1.3x to 8.5x faster for aperiodic stencil problems.

关键词： Stencil computation fast fourier transform divide-and-conquer parallel stencil solver

来源：评论

学校读者我要写书评

暂无评论

Position paper and brief announcement: An empirical study to compare two parallel programming models

Position paper and brief announcement: An empirical study to...

引用

SPAA 2006: 18th annual acm symposium on parallelism in algorithms and architectures

作者： Hochstein, Lorin Basili, Victor R. University of Maryland Computer Science Department College Park MD 20742

ISBN: (纸本)1595934529

While there are strong beliefs within the community about whether one particular parallel programming model is easier to use than another, there has been little research to analyze these claims empirically. Currently, the most popular paradigm is message-passing, as implemented by the MPI library [1]. However, MPI is considered to be difficult for developing programs, because it forces the programmer to work at a very low level of abstraction. One alternative parallel programming model is the PRAM model, which supports fine-grained parallelism and has a substantial history of algorithmic theory [2]. It is not possible to program current parallel machines using the PRAM model because modern architectures are not designed to support such a model efficiently. However, current trends towards multicore chips suggest that large-scale, fine-grained uniform-memory-access parallel machines may soon be feasible. XMT-C is an extension of the C language that supports parallel directives to provide a PRAM-like model to the programmer. A prototype compiler exists that generates code which runs on a simulator for an XMT architecture [3]. To better understand how much benefit a PRAM-like model could provide over a message-passing model, we conducted a feasibility study in an academic setting to compare the effort required to solve a particular problem. The questions under study were: can we measure the effort in developing a program using these two programming models and can we differentiate the amount of effort for each model? The subjects participating in the study were divided up into two groups. One group solved a problem using the MPI library in either C,C++, or Fortran, and the other group solved the problem using XMT-C. The task was to write a function to multiply a sparse matrix with a dense *** obtain subjects, we leveraged existing graduate-level parallel programming courses at two different universities: University of California, Santa Barbara (UCSB), and Universit

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：