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

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

作者： Kejariwal, Arun Saito, Hideki Tian, Xinmin Girkar, Milind Banerjee, Utpal Nicolau, Alexandra Polychronopoulos, Constantine D. Center for Embedded Computer Systems University of California at Irvine Irvine CA United States Intel Compiler Labs Intel Corporation Santa Clara CA United States Center for Supercomputing Research and Development University of Illinois at Urbana-Champaign Urbana IL United States

ISBN: (纸本)1595934529

parallel loops account for the greatest amount of parallelism in scientific and numerical codes. For example, most of the DO loops in SPEC CFP2000 and SPEC OMPM2001 are of DOALL type and account for a large percentage of the total execution time. One of the ways to exploit parallelism is to partition the iteration space of a DOALL loop amongst different processors in a parallel processor system. Naturally, a good partitioning is of key importance to achieve high performance and for efficient use of multiprocessor systems. Although a significant amount of work has been done in partitioning and scheduling of loops with both rectangular and non-rectangular iteration spaces, the problem of partitioning loops with conditionals has not been addressed so far to the best of our knowledge. In this paper, we present a mathematical model for partitioning parallel nested loops, both perfect and non-perfect, with conditionals, where the expressions in a conditional are affine functions of the outer loop indices. We present a loop transformation based on elimination of redundant constraints bounding the iteration space of a nested loop. The transformation plays a critical role during the (static) partitioning process as it helps to capture the "exact" lower and upper bounds (can be either a constant or symbolic) of the loop indices. We generate a canonical form of the loop nest using the transformation and employ the geometric approach we proposed earlier (in [1, 2]) for partitioning the iteration space along an axis corresponding to the outermost loop. For cases in which such a transformation does not exist, we propose a general approach for loop canonicalization. We present several examples from the literature and numerical packages to illustrate the effectiveness of our approach. Copyright 2006 acm.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

On parallel k-Center Clustering 23

On Parallel k-Center Clustering

引用

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

作者： Coy, Sam Czumaj, Artur Mishra, Gopinath Univ Warwick Coventry W Midlands England

ISBN: (纸本)9781450395458

We consider the classic k-center problem in a parallel setting, on the low-local-space Massively parallel Computation (MPC) model, with local space per machine of O(n(delta)), where delta is an element of(0, 1) is an arbitrary constant. As a central clustering problem, the k-center problem has been studied extensively. Still, until very recently, all parallel MPC algorithms have been requiring Omega(k) or even Omega(kn(delta)) local space per machine. While this setting covers the case of small values of k, for a large number of clusters these algorithms require large local memory, making them poorly scalable. The case of large k, k >= Omega(n(delta)), has been considered recently for the low-local-space MPC model by Bateni et al. (2021), who gave an O(log log n)-round MPC algorithm that produces k(1 + o(1)) centers whose cost has multiplicative approximation of O(log log log n). In this paper we extend the algorithm of Bateni et al. and design a low-local-space MPC algorithm that in O(log log..) rounds returns a clustering with k(1 + o(1)) clusters that is an O(log*n)-approximation for k-center.

关键词： MPC k-center clustering parallel computing MapReduce

来源：评论

学校读者我要写书评

暂无评论

Highly efficient dictionary matching in parallel 93

Highly efficient dictionary matching in parallel

引用

5th annual acm symposium on parallel algorithms and architectures, SPAA 1993

作者： Muthukrishnan, S. Palem, K. Courant Institute of Mathematical Sciences 251 Mercer Street New YorkNY10012-1185 United States IBM Research Division T. J. Watson Research Center P. O. Box 704 Yorktown HeightsNY10598 United States

ISBN: (纸本)0897915992

We present highly efficient parallel algorithms for several well-studied dictionary matching problems. Our algorithms are faster and more efficient in terms of their parallel work, compared to previously known results. For static dictionary matching, we present an algorithm that preprocesses the dictionary and matches the text in O(logm) parallel time and 0(M + n log m) work, given any dictionary of size M whose longest pattern is m characters long, and a text of size n. We have further improved this algorithm to solve static dictionary matching with only 0((M + n)vlog m) work, if the characters are drawn from an alphabet of constant size. A distinguishing feature of these algorithms and the one stated below for matching in higher dimensions, is that in contrast with previous work, the running times, and work overheads when applicable, are dependent only on the length of the longest pattern m. We present a parallel algorithm for d-dimensional dictionary matching that runs in O(logm) time and matches the text in 0(M + nlogm) work for any fixed d. We present a new and more efficient parallel algorithm for dynamic dictionary matching. Insertions into and deletions from the dictionary, as well as matching the text can be done with optimal speedup in 0(A log M) work and 0(log M) time. Here, A denotes the length of the string to be inserted, deleted or matched into a dictionary of size M. All of the above algorithms are designed by applying the shrink-and-spawn technique that we introduce in this paper. We also show that this technique leads to parallel algorithms that only do optimal (linear) work, for multi-dimensional pattern matching and related problems [KLP89,Rab93]. Our algorithms are deterministic, as those in [KLP89], but however, are much simpler and preserve the efficiency as well as the speed of those presented there. © 1993 acm.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Batch-Dynamic algorithms for k-Core Decomposition and Related Graph Problems 22

Parallel Batch-Dynamic Algorithms for k-Core Decomposition a...

引用

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

作者： Liu, Quanquan C. Shi, Jessica Yu, Shangdi Dhulipala, Laxman Shun, Julian Northeastern Univ Boston MA 02115 USA MIT CSAIL Cambridge MA USA Univ Maryland College Pk MD USA

ISBN: (纸本)9781450391467

Maintaining a k-core decomposition quickly in a dynamic graph has important applications in network analysis. The main challenge for designing efficient exact algorithms is that a single update to the graph can cause significant global changes. Our paper focuses on approximation algorithms with small approximation factors that are much more efficient than what exact algorithms can obtain. We present the first parallel, batch-dynamic algorithm for approximate k-core decomposition that is efficient in both theory and practice. Our algorithm is based on our novel parallel level data structure, inspired by the sequential level data structures of Bhattacharya et al. [STOC '15] and Henzinger et al. [2020]. Given a graph with n vertices and a batch of updates B, our algorithm provably maintains a (2 + epsilon)-approximation of the coreness values of all vertices (for any constant epsilon > 0) in O(|B| log(2) n) amortized work and /o(log(2) n log log n) depth (parallel time) with high probability. As a by-product, our k-core decomposition algorithm also gives a batch-dynamic algorithm for maintaining an O(alpha) out-degree orientation, where alpha is the current arboricity of the graph. We demonstrate the usefulness of our low out-degree orientation algorithm by presenting a new framework to formally study batch-dynamic algorithms in bounded-arboricity graphs. Our framework obtains new provably-efficient parallel batch-dynamic algorithms for maximal matching, clique counting, and vertex coloring. We implemented and experimentally evaluated our k-core decomposition algorithm on a 30-core machine with two-way hyperthreading on 11 graphs of varying densities and sizes. Compared to the state-of-the-art algorithms, our algorithm achieves up to a 114.52x speedup against the best parallel implementation, up to a 544.22x speedup against the best approximate sequential algorithm, and up to a 723.72x speedup against the best exact sequential algorithm. We also obtain results for our

关键词： parallel batch-dynamic algorithms k-core decomposition low out-degree orientation maximal matching k-clique counting vertex coloring

来源：评论

学校读者我要写书评

暂无评论

A constant time optimal parallel algorithm for two-dimensional pattern matching

引用

SIAM JOURNAL ON COMPUTING 1998年第3期27卷 668-681页

作者： Crochemore, M Gasieniec, L Hariharan, R Muthukrishnan, S Rytter, W Univ Marne La Vallee Inst Gaspard Monge F-93160 Noisy Le Grand France Univ Warsaw Inst Informat PL-02097 Warszawa Poland Max Planck Inst Informat Saarbrucken Germany NYU Courant Inst New York NY USA AT&T Bell Labs Murray Hill NJ 07974 USA

We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size m(h) x m(w) in a text array of size n(h) x n(w) in the concurrent-read-concurrent-write-parallel-random-access-machine (CRCW-PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(n(h) x n(w)) work, following preprocessing of the pattern. This improves the previous best bound of O(loglogm) time with optimal work [A. Amir, G. Benson, and M. Farach, Proceedings 5th annual acm symposium on parallel algorithms and architectures, acm, New York, 1993, pp. 79-85], following preprocessing of the pattern, where m = max {m(h),m(w)}. The preprocessing required by our algorithm (and that due to Amir, Benson, and Farach) can be accomplished in O(loglogm) time and O(m(h) x m(w)) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].

关键词： pattern matching PRAM two-dimensional witnesses duelling periodicity

来源：评论

学校读者我要写书评

暂无评论

Julienne: A Framework for parallel Graph algorithms usingWork-efficient Bucketing 17

Julienne: A Framework for Parallel Graph Algorithms usingWor...

引用

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

作者： Dhulipala, Laxman Blelloch, Guy Shun, Julian Carnegie Mellon Univ Pittsburgh PA 15213 USA Univ Calif Berkeley Berkeley CA USA

ISBN: (纸本)9781450345934

Existing graph-processing frameworks let users develop efficient implementations for many graph problems, but none of them support efficiently bucketing vertices, which is needed for bucketing-based graph algorithms such as.-stepping and approximate set-cover. Motivated by the lack of simple, scalable, and efficient implementations of bucketing-based algorithms, we develop the Julienne framework, which extends a recent shared-memory graph processing framework called Ligra with an interface for maintaining a collection of buckets under vertex insertions and bucket deletions. We provide a theoretically efficient parallel implementation of our bucketing interface and study several bucketing-based algorithms that make use of it (either bucketing by remaining degree or by distance) to improve performance: the peeling algorithm for k-core (coreness), Delta-stepping, weighted breadth-first search, and approximate set cover. The implementations are all simple and concise (under 100 lines of code). Using our interface, we develop the first work-efficient parallel algorithm for k-core in the literature with nontrivial parallelism. We experimentally show that our bucketing implementation scales well and achieves high throughput on both synthetic and real-world workloads. Furthermore, the bucketing-based algorithms written in Julienne achieve up to 43x speedup on 72 cores with hyper-threading over well-tuned sequential baselines, significantly outperform existing work-inefficient implementations in Ligra, and either outperform or are competitive with existing special-purpose parallel codes for the same problem. We experimentally study our implementations on the largest publicly available graphs and show that they scale well in practice, processing real-world graphs with billions of edges in seconds, and hundreds of billions of edges in a few minutes. As far as we know, this is the first time that graphs at this scale have been analyzed in the main memory of a single multicore m

关键词： parallel programming graph algorithms experiments shared memory

来源：评论

学校读者我要写书评

暂无评论

The parallel Repetition of Non-signaling Games Counterexamples and Dichotomy 2019

The Parallel Repetition of Non-signaling Games Counterexampl...

引用

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

作者： Holmgren, Justin Yang, Lisa Princeton Univ Princeton NJ 08544 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450367059

Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition. We show that, unlike the situation both for classical games and for two-player non-signaling games, there are k-player non-signaling games (for k = 3) whose values do not tend to 0 with sufficient parallel repetition. In fact, parallel repetition sometimes does not decrease their value whatsoever. We show that in general, every game's non-signaling value under parallel repetition is either lower bounded by a positive constant or decreases exponentially with the number of repetitions. Furthermore, exponential decrease occurs if and only if the game's sub-non-signaling value (Lancien and Winter, CJTCS '16) is less than 1.

关键词： parallel repetition non-signaling multi-player games

来源：评论

学校读者我要写书评

暂无评论

Provably good and practically efficient parallel race detection for fork-join programs 16

Provably good and practically efficient parallel race detect...

引用

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

作者： Utterback, Robert Agrawal, Kunal Fineman, Jeremy T. Lee, I-Ting Angelina Washington University St. Louis United States Georgetown University United States

ISBN: (纸本)9781450342100

If a parallel program has determinacy race(s), different schedules can result in memory accesses that observe different values - various race-detection tools have been designed to find such bugs. A key component of race detectors is an algorithm for series-parallel (SP) maintenance, which identifies whether two accesses are logically parallel. This paper describes an asymptotically optimal algorithm, called WSP-Order, for performing SP maintenance in programs with fork-join (or nested) parallelism. Given a fork-join program with T1 work and T∞ span, WSP-Order executes it while also maintaining SP relationships in O(T1/P + T∞) time on P processors, which is asymptotically optimal. At the heart of WSP-Order is a work-stealing scheduler designed specifically for SP maintenance. We also implemented C-RACER, a race-detector based on WSP-Order within the Cilk Plus runtime system, and evaluated its performance on five benchmarks. Empirical results demonstrate that when run sequentially, it performs almost as well as previous best sequential race detectors. More importantly, when run in parallel, it achieves almost as much speedup as the original program without race-detection. © 2016 acm.

关键词： Maintenance

来源：评论

学校读者我要写书评

暂无评论

Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract) 94

Dynamic load balancing in parallel and distributed networks ...

引用

6th annual acm symposium on parallel algorithms and architectures, SPAA 1994

作者： Ghosh, Bhaskar Muthukrishnan, S. Department of Computer Science Yale University P.O. Box 208285 New HavenCT06520 United States Courant Institute of Mathematical Sciences New York University 251 Mercer Street New YorkNY10012-1185 United States

ISBN: (纸本)0897916719

The fundamental problems in dynamic load balancing and job scheduling in parallel and distributed computers involve moving load between processors. In this paper, we consider a new model for load movement in synchronous parallel and distributed machines. In each step of our model, each processor can transfer load to at most one neighbor;also, any amount of load can be moved along a communication link between two processors in one step. This is a reasonable model for load movement in significant classes of dynamic load balancing problems. We derive efficient algorithms for a number of task reallocation problems under our model of load movement. These include dynamic load balancing on processor networks, adaptive mesh re-partitioning such as those in finite element methods, and progressive job migration under dynamic generation and consumption of load. To obtain the above-mentioned results, we introduce and solve the abstract problem of Incremental Weight Migration (IWM) on arbitrary graphs. Our main result is a simple, randomized, algorithm for this problem which provably results in asymptotically optimal convergence towards the state where weights on the nodes of the graph are all equal. This algorithm utilizes an appropriate random set of edges forming a matching. Our algorithm for the IWM problem is used in deriving efficient algorithms for all the problems mentioned above. Our results are very general. The algorithms we derive are local, and hence, scalable. They work for arbitrary load distributions and for networks of arbitrary topology which can possibly undergo link failures. Of independent interest is our proof technique which we use to lower bound the convergence of our algorithms in terms of the eigenstructure of the underlying graph. Finally, we present preliminary experimental results analyzing issues in load balancing related to our algorithms. © 1994 acm.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

architectures and algorithms for millisecond-scale molecular dynamics simulations of proteins 41

Architectures and algorithms for millisecond-scale molecular...

引用

2008 - 41st annual IEEE/acm International symposium on Microarchitecture, MICRO-41

作者： Shaw, David E. Columbia's Medical School United States

ISBN: (纸本)9781424428366

The ability to perform long, accurate molecular dynamics (MD) simulations involving proteins and other biological macromolecules could in principle lead to important scientific advances and provide a powerful new tool for drug discovery. A wide range of biologically interesting phenomena, however, occur over time scales on the order of a millisecond - several orders of magnitude beyond the duration of the longest current MD simulations. Our research group is currently building a specialized, massively parallel machine, called Anton, which should soon be capable of executing millisecond-scale MD simulations of proteins at an atomic level of detail. Anton's highly accelerated execution of such simulations is attributable in large part to specialized logic for the high-speed calculation of pairwise interactions between particles and/or gridpoints separated by no more than some specified cutoff radius. In particular, each of Anton's 512 ASICs, which are implemented using 90-nm technology, includes a "high-throughput interaction subsystem" incorporating 32 highly specialized pipelines running at 800 MHz. During every cycle, each of these pipelines produces a pairwise-interaction result that would require approximately 50 arithmetic operations to calculate on a general-purpose processor. Novel algorithms and architectural features are used to greatly reduce the requirements for inter- and intra-chip communication, allowing Anton to feed these pipelines and collect their results at a speed sufficient to take advantage of the machine's computational power. The ASIC also includes a "flexible subsystem" based on eight programmable "geometry cores," each containing eight arithmetic pipelines. This talk will provide an overview of our work on parallel algorithms and machine architectures for high-speed MD simulation, with special attention to the respective roles of specialized vs. general-purpose hardware, and to the techniques used to minimize communication at various levels

关键词： Molecular dynamics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：