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

Proceedings of the 1998 10th annual acm symposium on parallel algorithms and architectures, SPAA

作者： Cheng, G.-I. Feng, M. Leiserson, Ch.E. Randall, K.H. Stark, A.F. MIT Lab for Computer Science Cambridge MA United States

ISBN: (纸本)9780897919890

When two parallel threads holding no locks in common access the same memory location and at least one of the threads modifies the location, a 'data race' occurs, which is usually a bug. This paper describes the algorithms and strategies used by a debugging tool, called the Nondeterminator-2, which checks for data races in programs coded in the Cilk multithreaded language. Like its predecessor, the Nondeterminator, which checks for simple 'determinacy' races, the Nondeterminator-2 is a debugging tool, not a verifier, since it checks for data races only in the computation generated by a serial execution of the program on a given input. We give an algorithm, ALL-SETS, that determines whether the computation generated by a serial execution of a Cilk program on a given input contains a race. For a program that runs serially in time T, accesses V shared memory locations, uses a total of n locks, and holds at most k n locks simultaneously, ALL-SETS runs in. O(nkT α(V, V)) time and O(nkV) space, where α is Tarjan's functional inverse of Ackermann's function. Since ALL-SETS may be too inefficient in the worst case, we propose a much more efficient algorithm which can be used to detect races in programs that obey the 'umbrella' locking discipline, a programming methodology that is more flexible than similar disciplines proposed in the literature. We present an algorithm, BRELLY, which detects violations of the umbrella discipline in O(kT α(V, V)) time using O(kV) space. We also prove that any 'abelian' Cilk program, one whose critical sections commute, produces a determinate final state if it is deadlock free and if it generates any computation which is data-race free. Thus, the Nondeterminator-2's two algorithms can verify the determinacy of a deadlock-free abelian program running on a given input.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster parallel Algorithm for Approximate Shortest Path 2020

Faster Parallel Algorithm for Approximate Shortest Path

引用

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

来源：评论

学校读者我要写书评

暂无评论

Small Value parallel Repetition for General Games 15

Small Value Parallel Repetition for General Games

引用

47th annual acm symposium on Theory of Computing (STOC) held as part of the Federated Computing Research Conference

作者： Braverman, Mark Garg, Ankit Princeton Univ Dept Comp Sci Princeton NJ 08544 USA

ISBN: (纸本)9781450335362

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) and provide alternate proofs for the parallel repetition theorems of Holenstein and Rao for general and projection games respectively. We also extend the example of Feige and Verbitsky to show that the small-value parallel repetition bound we obtain is tight. Our techniques are elementary in that we only need to employ basic information theory and discrete probability in the small-value parallel repetition proof.

关键词： parallel repetition Hardness amplification Information theory

来源：评论

学校读者我要写书评

暂无评论

Deterministic Massively parallel Connectivity*† 2022

Deterministic Massively Parallel Connectivity*†

引用

54th annual acm SIGACT symposium on Theory of Computing (STOC)

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

ISBN: (纸本)9781450392648

We consider the problem of designing fundamental graph algorithms on the model of Massive parallel Computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only Theta(n(delta)) words for an arbitrary constant delta > 0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. In a recent breakthrough, Andoni et al. (FOCS'18) and Behnezhad et al. (FOCS'19) designed parallel randomized algorithms that in O (logD + log log n) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O ( log n) derived from earlier works on PRAM algorithms. In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O (log D + log log n) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc. We complement our upper bounds by extending a recent lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires D >= log1+Omega(1) n), by showing a related conditional hardness of Omega( log D ) MPC rounds for the entire spectrum of D, covering a particularly interesting range when D <= O( log n).

关键词： derandomization connectivity MapReduce MPC massively parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer 93

A doubly logarithmic communication algorithm for the complet...

引用

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

作者： Goldberg, Leslie Ann Jerrum, Mark Leighton, Tom Rao, Satish Sandia National Labs Department 1423 PO Box 5800 AlbuquerqueNM87185 United States University of Edinburgh Department of Computer Science King's Buildings EdinburghEH9 3JZ United Kingdom MIT Mathematics Department Laboratory for Computer Science CambridgeMA02139 United States NEC Research Institute 4 Independence Way PrincetonNJ08540 United States

ISBN: (纸本)0897915992

In this paper we consider the problem of interprocessor communication on a Completely Connected Optical Communication parallel Computer (OCPC). The particular problem we study is that of realizing an h-relation. In this problem, each processor has at most h messages to send and at most h messages to receive. It is clear that any 1-relation can be realized in one communication step on an OCPC. However, the best known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires Q(h + logp) expected communication steps. (This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for h-fì(logp) and it is an open question of Geréb-Graus and Tsantilas whether there is a faster algorithm for h-o(logp). In this paper we answer this question in the affirmative by presenting a 0(/ì 4-log log p) communication step randomized algorithm that realizes an arbitrary h-relation on a p-processor OCPC. We show that if h © 1993 acm.

关键词： Optical communication

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for the circuit value update problem

引用

THEORY OF COMPUTING SYSTEMS 1997年第6期30卷 583-597页

作者： Leiserson, CE Randall, KH Laboratory for Computer Science MIT 545 Technology Square Cambridge MA 02139 USA cel@mit.edu randall@theory.lcs.mit.edu US

The circuit value update problem is the problem of updating values in a representation of a combinational circuit when some of the inputs are changed. We assume for simplicity that each combinational element has bounded fan-in and fan-out and can be evaluated in constant time. This problem is easily solved on an ordinary serial computer in O(W + D) time, where W is the number of elements in the altered subcircuit and D is the subcircuit's embedded depth (its depth measured in the original circuit). In this paper we show how to solve the circuit value update problem efficiently on a P-processor parallel computer. We give a straightforward synchronous, parallel algorithm that runs in O(W/P + D1g P) expected time. Our main contribution, however, is an optimistic, asynchronous, parallel algorithm that runs in O(W/P + D + 1g W + 1g P) expected time, where W and D are the size and embedded depth, respectively, of the ''volatile'' subcircuit, the subcircuit of elements that have inputs which either change or glitch as a result of the update. To our knowledge, our analysis provides the first analytical bounds on the running time of an optimistic, asynchronous, parallel algorithm.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel construction of optimal alphabetic trees 93

Parallel construction of optimal alphabetic trees

引用

Proceedings of the 5th annual acm symposium on parallel algorithms and architectures

作者： Larmore, Lawrence Przytycka, M. Department of Computer Science University of California Riverside 92521 CA United States Department of Mathematics and Computer Science Odense University Odense M DK-5239 Denmark Institute of Informatics Warsaw University ul. Banacha 2 Warsaw 02-097 Poland

ISBN: (纸本)0897915992

A parallel algorithm is given which constructs an optimal alphabetic tree in 0(log3 n) time with n2 log n processors. The construction is basically a parallelization of the Garsia-Wachs version [5] of the Hu-tucker algorithm [8]. The best previous MC algorithm for the problem uses ra6/logn processors. [15] Our method is an extension of techniques used first in [3] and later used in [13] for the Huffman coding problem, which can be viewed as the alphabetic tree problem for the special case of a monotone weight sequence. In this paper, we extend to the case of certain "almost monotone" sequences, which we call "sorted regular valleys." The processing of such subsequences depends on a quadrangle inequality, while the total number of global iterations depends on a kind of tree contraction. Altogether we can view our algorithmic approach as (quadrangle inequality + tree contraction). An optimal alphabetic tree is a special case of an optimal binary search tree where all the weights are in the leaves. Thus, the result gives a partial answer to the open problem posed in [3]: is there an AfC algorithm which can find an optimal binary search tree and which user processors for some ep > 0?

关键词： Forestry

来源：评论

学校读者我要写书评

暂无评论

Studying overheads in massively parallel Min/Max-tree evaluation (extended abstract) 94

Studying overheads in massively parallel Min/Max-tree evalua...

引用

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

作者： Feldmann, Rainer Mysliwietz, Peter Monien, Burkhard Department of Mathematics and Computer Science University of Paderborn Germany

ISBN: (纸本)0897916719

In this paper we study the overheads arising in our algorithm for distributed evaluation of Min/Max trees. The overheads are classified into search overhead, performance loss, and decrease of work load. Several mechanisms are investigated to cope with these overheads in order to achieve a high performance. We study a combination of local, medium range, and global load distribution strategies that does not only show a good behavior in terms of work load, but also has a positive influence on the search overhead. The efficient use of a virtual shared memory, that is distributed among the processors, shows also a big contribution to the overall performance of the system. A carefully restricted application of parallelism using an improved version of the Young Brothers Wait Concept (YBWC) leads to a perfect behavior for minimal Min/Max trees and to a quite low search overhead, if well ordered trees are searched. Well ordered trees constitute the most important case in practice, since a couple of move ordering mechanisms are known that achieve a nearly optimal move ordering in many applications. The resulting combination of the methods shows an efficiency better than any previous approach. Experiments carried out using 256 DeBruijn-connected Transputers result in a speedup of 142 even applying restricted timing constraints. With a system consisting of 1024 grid connected Transputers we obtain a speedup of 344. Moreover the algorithm shows a very good scalability, especially using interconnection networks with logarithmic diameter. The experiments have been carried out using a Min/Max search program that incorporates all important state-of-the- art search techniques (Zugzwang, current vice world champion in computer chess) and therefore makes sure, that no artificial or simplifying assumptions on the structure of the problem are made. © 1994 acm.

关键词： Transputers

来源：评论

学校读者我要写书评

暂无评论

parallel CONSTRUCTION OF NEAR OPTIMAL BINARY-TREES 90

PARALLEL CONSTRUCTION OF NEAR OPTIMAL BINARY-TREES

引用

2ND annual SYMP OF THE ASSOC FOR COMPUTING MACHINERY : parallel algorithms AND architectures ( SPAA 90 ) / AEGEAN WORKSHOP ON COMPUTING

作者： KIRKPATRICK, DG PRZYTYCKA, T The University of British Columbia Computer Science Vancouver B.C. Canada V6T 1W5

ISBN: (纸本)0897913701

We present parallel algorithms to construct, for given sets of leaf weights, binary trees with almost optimal weighted path length (i.e. approximate Huffman trees). Specifically, assuming that weights are normalized (to sum up to one) and error refers to the (absolute) difference between the weighted path length of a given tree and the optimal tree with the same weights, we present: (i) O(logn) time and n loglogn/logn EREW processor algorithm which constructs a tree with error less than 0.172;(ii) O(klogn log^*n) time and n CREW processor algorithm which produces a tree with error at most 1/n^k, and (iii) an O(k²logn) time and n² CREW processor algorithm which produces a tree with error at most 1/n^k. Our approach also leads to two sequential algorithms: an O(kn) time algorithm which produces a tree with error at most 1/n^2(k) and O(kn) time algorithm which produces a tree with error at most 1/2^n2(k). The last two algorithms use different computation models. (A detailed description of sequential algorithms is left to an expanded version of the paper [KP89].)

关键词： Computer programming

来源：评论

学校读者我要写书评

暂无评论

Design and performance of multipath MIN architectures 92

Design and performance of multipath MIN architectures

引用

4th annual acm symposium on parallel algorithms and architectures - SPAA '92

作者： Chong, Frederic T. Knight Jr., Thomas F. Massachusetts Inst of Technology Cambridge MA United States

ISBN: (纸本)089791483X

In this paper, we discuss the use of multipath multistage interconnection networks (MINs) in the design of a fault-tolerant parallel computer. Multipath networks have multiple paths between any input and any output. In particular, we examine networks with either the property of expansion or maximal-fanout. We present an Ω(n 1/2 ) lower time bound for a worst-case permutation on deterministic maximal-fanout networks. We further show how a randomized approach to maximal-fanout avoids the regularity from which this worst case arises. Unlike most previous work, we examine systems which can tolerate node failure and isolation. We describe mechanisms for fault identification and system reconfiguration. In reconfiguring a faulty system, a naive approach is to preserve processing power by maximizing the number of processing nodes left in operation. However, our results show that the synchronization requirements of applications make it critical to eliminate nodes with poor network connections. We find that a conservative fault-propagation algorithm for reconfiguration, adapted from work by Leighton and Maggs [LM92], performs well for all of our multipath networks. We also address some practical issues of network construction and present performance simulations based upon the MIT Transit architecture [DcH90]. Simulation results for 1024 node systems demonstrate that multipath networks, reconfigured with our fault-propagation algorithm, perform well not only in theory, but also in practice. In fact, our systems suffer only a small decrease in performance from network faults;the degradation is linear in the percentage of network failure.

关键词： Fault tolerant computer systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：