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

How to vectorize the algebraic multilevel iteration

acm TRANSACTIONS ON MATHEMATICAL SOFTWARE 2000年第2期26卷 293-309页

作者： Grosz, L Massey Univ Inst Informat & Math Sci N Shore Mail Ctr Auckland New Zealand

We consider the algebraic multilevel iteration (AMLI) for the solution of systems of linear equations as they arise from a finite-difference discretization on a rectangular grid. Key operation is the matrix-vector product, which can efficiently be executed on vector and parallel-vector computer architectures if the nonzero entries of the matrix are concentrated in a few diagonals. In order to maintain this structure for all matrices on all levels coarsening in alternating directions is used. In some cases it is necessary to introduce additional dummy grid hyperplanes. The data movements in the restriction and prolongation are crucial, as they produce massive memory conflicts on vector architectures. By using a simple performance model the best of the possible vectorization strategies is automatically selected at runtime. Examples show that on a Fujitsu VPP300 the presented implementation of AMLI reaches about 85% of the useful performance, and scalability with respect to computing time can be achieved.

关键词： algorithms performance large linear systems preconditioned iterative solver vector computer multigrid method numerical software parallel processing

来源：评论

学校读者我要写书评

暂无评论

Submodular Maximization with Matroid and Packing Constraints in parallel 2019

Submodular Maximization with Matroid and Packing Constraints...

引用

51st annual acm SIGACT symposium on Theory of Computing (STOC)

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

ISBN: (纸本)9781450367059

We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a 1 - 1/e - epsilon approximation for monotone functions and a 1/e - epsilon approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is O(log(2) n/epsilon(3)), which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for non-monotone submodular maximization subject to packing constraints. Our algorithm achieves a 1/e - epsilon approximation using O(log(n/epsilon) log(1/epsilon) log(n + m)/epsilon(2)) parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a 1-1/e - epsilon approximation inO(log(n/epsilon) logm/epsilon(2)) parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016). Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function.

关键词： DR-submodular maximization packing matroid parallel complexity

来源：评论

学校读者我要写书评

暂无评论

Communication-Optimal parallel and Sequential Cholesky Decomposition 09

Communication-Optimal Parallel and Sequential Cholesky Decom...

引用

21st acm symposium on parallelism in algorithms and architectures

作者： Ballard, Grey Demmel, James Holtz, Olga Schwartz, Oded Univ Calif Berkeley Dept Comp Sci Berkeley CA 94720 USA

ISBN: (纸本)9781605586069

Numerical algorithms have two kinds of costs: arithmetic and communication, by which we mean either moving data between levels of a memory hierarchy (in the sequential case) or over a network connecting processors (in the parallel case). Communication costs often dominate arithmetic costs, so it is of interest to design algorithms minimizing communication. In this paper we first extend known lower bounds on the communication cost (both for bandwidth and for latency) of conventional (O(n(3))) matrix multiplication to Cholesky factorization, which is used for solving dense symmetric positive definite linear systems. Second, we compare the cost of various Cholesky decomposition implementations to this lower bound, and draw the following conclusions: (1) "Naive" sequential algorithms for Cholesky attain neither the bandwidth nor latency lower bounds. (2) The sequential blocked algorithm in LAPACK (with the right block size), as well as various recursive algorithms [AP00, GJ01, ACW01, ST04] and one based on work of Toledo [Tol97], can attain the bandwidth lower bound. (3) The LAPACK algorithm can also attain the latency bound if used with blocked data structures rather than column-wise or row-wise matrix data structures, though the Toledo algorithm cannot. (4) The recursive sequential algorithm due to [AP00], attains the bandwidth and latency lower bounds at every level of a multi-level memory hierarchy, in a "cache-oblivious" way. (5) The parallel implementation of Cholesky in the ScaLA-PACK library (again with the right block-size) attains both the bandwidth and latency lower bounds to within a poly-logarithmic factor. Combined with prior results in [DGHL08a, DGHL08b, DGX08] this gives a complete set;of communication-optimal algorithms for O(n(3)) implementations of three basic factorizations of dense linear algebra: LU with pivoting, QR and Cholesky. But it goes beyond this prior work on sequential LU and QR by optimizing communication for any number of levels of memo

关键词： communication avoiding Cholesky decomposition lower bound bandwidth latency algorithm

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for randomized exclusive write PRAMs 95

Lower bounds for randomized exclusive write PRAMs

引用

Proceedings of the 7th annual acm symposium on parallel algorithms and architectures, SPAA'95

作者： MacKenzie, Philip D. Sandia Natl Lab Albuquerque NM United States

ISBN: (纸本)9780897917179

In this paper we study the question: How useful is randomization in speeding up Exclusive Write PRAM computations? Our results give further evidence that randomization is of limited use in these types of computations. First we examine a compaction problem on both the CREW and EREW PRAM models, and we present randomized lower bounds which match the best deterministic lower bounds known. (For the CREW PRAM model, the lower bound is asymptotically optimal). These are the first non-trivial randomized lower bounds known for the compaction problem on these models. We show that our lower bounds also apply to the problem of approximate compaction. Next we examine the problem of computing boolean functions on the CREW PRAM model, and we present a randomized lower bound which improves on the previous best randomized lower bound for many boolean functions, including the OR function. (The previous lower bounds for these functions were asymptotically optimal, but we improve the constant multiplicative factor). We also give an alternate proof for the randomized lower bound on PARITY, which was already optimal to within a constant additive factor. Lastly, we give a randomized lower bound for integer merging on an EREW PRAM which matches the best deterministic lower bound known. In all our proofs, we use the Random Adversary method, which has previously only been used for proving lower bounds on models with Concurrent Write capabilities. Thus this paper also serves to illustrate the power and generality of this method for proving parallel randomized lower bounds.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Meeting the Challenges of parallelizing Sequential Programs 17

Brief Announcement: Meeting the Challenges of Parallelizing ...

引用

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

作者： Atre, Rohit Jannesari, Ali Wolf, Felix Tech Univ Darmstadt Darmstadt Germany Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9781450345934

Discovering which code sections in a sequential program can be made to run in parallel is the first step in parallelizing it, and programmers routinely struggle in this step. Most of the current parallelism discovery techniques focus on specific language constructs while trying to identify such code sections. In contrast, we propose to concentrate on the computations performed by a program. In our approach, a program is treated as a collection of computations communicating with one another using a number of variables. Each computation is represented as a Computational Unit (CU). A CU contains the inputs and outputs of a computation, and the three phases of a computation: read, compute, and write. Based on the notion of CU, We present a unified framework to identify both loop and task parallelism in sequential programs.

关键词： parallelism discovery multicore architectures static analysis task parallelism profiling

来源：评论

学校读者我要写书评

暂无评论

Many Sequential Iterative algorithms Can Be parallel and (Nearly) Work-efficient 22

Many Sequential Iterative Algorithms Can Be Parallel and (Ne...

引用

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

作者： Shen, Zheqi Wan, Zijin Gu, Yan Sun, Yihan UC Riverside Riverside CA 92521 USA

ISBN: (纸本)9781450391467

Some recent papers showed that many sequential iterative algorithms can be directly parallelized, by identifying the dependences between the input objects. This approach yields many simple and practical parallel algorithms, but there are still challenges to achieve work-efficiency and high-parallelism. Work-efficiency means that the number of operations is asymptotically the same as the best sequential solution. This can be hard for certain problems where the number of dependences between objects is asymptotically more than optimal sequential work, and we cannot even afford the cost to generate them. To achieve high-parallelism, we always want it to process as many objects as possible in parallel. The goal is to achieve (O) over tilde (D) span for a problem with the deepest dependence length D. We refer to this property as round-efficiency. This paper presents work-efficient and round-efficient algorithms for a variety of classic problems and propose general approaches to do so. To efficiently parallelize many sequential iterative algorithms, we propose the phase-parallel framework. The framework assigns a rank to each object and processes the objects based on the order of their ranks. All objects with the same rank can be processed in parallel. To enable work-efficiency and high parallelism, we use two types of general techniques. Type 1 algorithms aim to use range queries to extract all objects with the same rank to avoid evaluating all the dependences. We discuss activity selection, and Dijkstra's algorithm using Type 1 framework. Type 2 algorithms aim to wake up an object when the last object it depends on is finished. We discuss activity selection, longest increasing subsequence (LIS), greedy maximal independent set (MIS), and many other algorithms using Type 2 framework. All of our algorithms are (nearly) work-efficient and round-efficient, and some of them (e.g., LIS) are the first to achieve the both. Many of them improve the previous best bounds. Moreover,

关键词： parallel algorithms phase-parallel framework parallel programming sequential iterative algorithms activity selection longest increasing subsequence maximal independent set independence system

来源：评论

学校读者我要写书评

暂无评论

Collaborate with strangers to find own preferences 05

Collaborate with strangers to find own preferences

引用

Seventeenth annual acm symposium on parallelism in algorithms and architectures

作者： Awerbuch, Baruch Azar, Yossi Lotker, Zvi Patt-Shamir, Boaz Tuttle, Mark R. Dept. of Computer Science Johns Hopkins University School of Computer Science Tel Aviv University Tel Aviv 69978 Israel Kruislaan 413 CWI 1090 GB Amsterdam Netherlands Dept. of Electrical Engineering Tel Aviv University Tel Aviv 69978 Israel HP Cambridge Research Lab. One Cambridge Center Cambridge MA 02142 United States

ISBN: (纸本)9781581139860

We consider a model with n players and m objects. Each player has a "preference vector" of length m that models his grade for each object. The grades are unknown to the players. A player can learn his grade for an object by probing that object, but performing a probe incurs cost. The goal of a player is to learn his preference vector with minimal cost, by adopting the results of probes performed by other players. To facilitate communication, we assume that players collaborate by posting their grades for objects on a shared billboard: reading from the billboard is free. We consider players whose preference vectors are popular, i.e., players whose preferences are common to many other players. We present distributed and sequential algorithms to solve the problem with logarithmic cost overhead. Copyright 2005 acm.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

HARP: A fast spectral partitioner

HARP: A fast spectral partitioner

引用

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

作者： Simon, Horst D. Sohn, Andrew Biswas, Rupak Lawrence Berkeley Natl Lab Berkeley United States

Partitioning unstructured graphs is central to the parallel solution of computational science and engineering problems. Spectral partitioners, such recursive spectral bisection (RSB), have proven effective in generating high-quality partitions of realistically-sized meshes. The major problem which hindered their widespread use was their long execution times. This paper presents a new inertial spectral partitioner, called HARP. The main objective of the proposed approach is to quickly partition the meshes at runtime in a manner that works efficiently for real applications in the context of distributed-memory machines. The underlying principle of HARP is to find the eigenvectors of the unpartitioned vertices and then project them onto the eigenvectors of the original mesh. Results for various meshes ranging in size from 1000 to 100,000 vertices indicate that HARP can indeed partition meshes rapidly at runtime. Experimental results show that our largest mesh can be partitioned sequentially in only a few seconds on an SP2 which is several times faster than other spectral partitioners while maintaining the solution quality of the proven RSB method. A parallel MPI version of HARP has also been implemented on IBM SP2 and Cray T3E. parallel HARP, running on 64 processors SP2 and T3E, can partition a mesh containing more than 100,000 vertices into 64 subgrids in about half a second. These results indicate that graph partitioning can now be truly embedded in dynamically-changing real-world applications.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

Faster construction of planar two-centers

Faster construction of planar two-centers

引用

8th annual acm/SIAM symposium on Discrete algorithms

作者： Eppstein, D Univ of California Irvine United States

Improving on a recent breakthrough of Sharir, we find two minimum-radius circular disks covering a planar point set, in randomized expected time O (n log(2) n).

ISBN: (纸本)0898713900

Improving on a recent breakthrough of Sharir, we find two minimum-radius circular disks covering a planar point set, in randomized expected time O (n log(2) n).

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

ParlayLib - A Toolkit for parallel algorithms on Shared-Memory Multicore Machines 20

ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memo...

引用

32nd acm symposium on parallelism in algorithms and architectures, SPAA 2020

作者： Blelloch, Guy E. Anderson, Daniel Dhulipala, Laxman Carnegie Mellon University PittsburghPA United States

ISBN: (纸本)9781450369350

ParlayLib is a C++ library for developing efficient parallel algorithms and software on shared-memory multicore machines. It provides additional tools and primitives that go beyond what is available in the C++ standard library, and simplifies the task of programming provably efficient and scalable parallel algorithms. It consists of a sequence data type (analogous to std::vector), many parallel routines and algorithms, a work-stealing scheduler to support nested parallelism, and a scalable memory allocator. It has been developed over a period of seven years and used in a variety of software including the PBBS benchmark suite, the Ligra, Julienne, and Aspen graph processing frameworks, the Graph Based Benchmark Suite, and the PAM library for parallel balanced binary search trees, and an implementation of the TPC-H benchmark suite. © 2020 Owner/Author.

关键词： parallel programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：