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

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

作者： Kelson, Pierre Univ. of British Columbia Vancouver B.C. Canada

Let iT be a bipartite graph with bipartition (A, B) where \A\-n and every subset X of A with at most a n elements has at least b\X\ neighbors (o 1). We consider the problem of computing a matching from a given subset... 详细信息

ISBN: (纸本)0897915992

Let iT be a bipartite graph with bipartition (A, B) where \A\-n and every subset X of A with at most a n elements has at least b\X\ neighbors (o < 1,6 > 1). We consider the problem of computing a matching from a given subset X A of size at most a n into B. By Hall's theorem such a matching does indeed exist. We propose two algorithms for this problem. the first algorithm is in NC for b > d' for a constant e > 0;here d denotes the maximum degree of a vertex in A. the second algorithm uses randomization and computes a matching for X provided b = Q(diogd). It terminates in 0(log n) steps for constant d and in polylog(n) time for d = O(polylog(n)) (with high probability). this algorithm is a local algorithm in the sense that the vertices in the graph establish the matching themselves in an online fashion. Both algorithms have applications to local and global routing in communication networks. In particular our results improve a construction of a self-routing nonblocking network by Arora, Leighton, and Maggs. © 1993 acm.

关键词： Computation theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

SPAA 2006: 18th Annual ACM Symposium on Parallelism in Algor...

引用

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

ISBN: (纸本)1595934529

the proceedings contain 43 papers. the topics discussed include: publish and perish: definition and analysis of an n-person publication impact game;exponential separation of quantum and classical online space complexity;minimizing the stretch when scheduling flows of biological requests;position paper and brief announcement: the FG programming environment - good and good for you;efficient parallel algorithms for dead sensor diagnosis and multiple access channels;on the communication complexity of randomized broadcasting in random-like graphs;strip packing with precedence constraints and strip packing with release times;on space-stretch trade-offs: lower bounds;a performance analysis of local synchronization;the cache complexity of multithreaded cache oblivious algorithms;and deterministic load balancing and dictionaries in the parallel disk model.

关键词： Computer architecture

来源：评论

学校读者我要写书评

暂无评论

Matching nuts and bolts in O(n log n) time

引用

SIAM JOURNAL ON DISCRETE MAthEMATICS 1998年第3期11卷 347-372页

作者： Komlos, J Ma, Y Szemeredi, E Rutgers State Univ Dept Math Piscataway NJ 08855 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA MIT Cambridge MA 02139 USA Rutgers State Univ Dept Comp Sci Piscataway NJ 08855 USA Univ Gesamthsch Paderborn D-4790 Paderborn Germany

Given a set of n nuts of distinct widths and a set of n bolts such that each nut corresponds to a unique bolt of the same width, how should we match every nut with its corresponding bolt by comparing nuts with bolts? (No comparison is allowed between two nuts or two bolts.) the problem can be naturally viewed as a variant of the classic sorting problem as follows. Given two lists of n numbers each such that one list is a permutation of the other, how should we sort the lists by comparisons only between numbers in different lists? We give an O(n log n)-time deterministic algorithm for the problem. this is optimal up to a constant factor and answers an open question posed by Alon et al. [proceedings of the 5th annual acm-SIAM symposium on Discrete algorithms, 1994, pp. 690-696]. Moreover, when copies of nuts and bolts are allowed, our algorithm runs in optimal O(log n) time on n processors in Valiant's parallel comparison tree model. Our algorithm is based on the AKS sorting algorithm with substantial modifications.

关键词： sorting matching selection parallel computation AKS sorting algorithm random graphs

来源：评论

学校读者我要写书评

暂无评论

Construction with parallel derivatives of the closure of a parallel program schema 74

Construction with parallel derivatives of the closure of a p...

引用

6th annual acm symposium on theory of Computing, STOC 1974

作者： Millen, Jonathan K. MITRE Corporation BedfordMA01730 United States

ISBN: (纸本)9781450374231

the parallel derivative of a set of strings is introduced. Given a serial, repetition-free parallel program schema, its closure is constructed by taking parallel derivatives of its set of computations. the construction resembles the construction of a state diagram from a regular expression by means of derivatives. © Association for Computing Machinery. All rights reserved.

关键词： parallel programming

来源：评论

学校读者我要写书评

暂无评论

BSP vs LogP 96

BSP vs LogP

引用

proceedings of the 1996 8th annual acm symposium on parallel algorithms and architectures

作者： Bilardi, Gianfranco Herley, Kieran T. Pietracaprina, Andrea Pucci, Geppino Spirakis, Paul Universita di Padova Padova Italy

ISBN: (纸本)9780897918091

A quantitative comparison of the BSP and LogP models for parallel computation is developed. Very efficient cross simulations between the two models are derived, showing their substantial equivalence for algorithmic design guided by asymptotic analysis. It is also shown that the two models can be implemented with similar performance on most point-to-point networks. In conclusion, within the limits of our analysis that is mainly of asymptotic nature, BSP and LogP can be viewed as closely related variants within the bandwidth-latency framework for modeling parallel computation. BSP seems somewhat preferable due to greater simplicity and portability, and slightly greater power.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

A Framework for parallelizing Approximate Gaussian Elimination 24

A Framework for Parallelizing Approximate Gaussian Eliminati...

引用

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

作者： Baumann, Yves Kyng, Rasmus Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9798400704161

In a breakthrough result, Spielman and Teng (2004) developed a nearly-linear time solver for Laplacian linear equations, i.e. equations where the coefficient matrix is symmetric with non-negative diagonals and zero rowsums. Since the development of the Spielman-Teng solver, there has been substantial progress, simplifying and improving their result, but obtaining a fast practical, parallel Laplacian solver remains an open problem. We present a framework for obtaining extremely simple, parallel Laplacian linear equation solvers with nearly-linear work and sub-linear depth. Our framework allows us to parallelize any Laplacian solver based on repeated single-vertex approximate Gaussian elimination. We demonstrate this by parallelizing both the algorithm of Kyng and Sachdeva (2016) and the practical variant by Gao, Kyng, and Spielman (2023). Our framework is work-efficient in the sense of matching the sequential work of these algorithms. Our parallelization framework is very simple: We sample a subset of the current low-degree vertices (sparse columns), and in parallel we eliminate all vertices that are isolated in the resulting induced subgraph. this approach can be combined with any parallelizable approximate single-vertex elimination subroutine with sparse output. Given the simplicity of the approach, we believe that using it to parallelize the solver of Gao, Kyng, and Spielman (2023) is the most promising direction for obtaining practical parallel Laplacian solvers. If we additionally use a parallel spectral sparsification routine, our approach can be modified to work in polylogarithmic depth and nearly-linear work.

关键词： Approximate Gaussian Elimination Laplacian Linear System Solver parallel algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Computational bounds for fundamental problems on general-purpose parallel models 98

Computational bounds for fundamental problems on general-pur...

引用

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

作者： MacKenzie, Ph.D. Ramachandran, V. Boise State Univ Boise ID United States

ISBN: (纸本)9780897919890

We present lower bounds for time needed to solve basic problems on three general-purpose models of parallel computation: the shared-memory models QSM and s-QSW, and the distributed-memory model, the BSP. For each of these models, we also obtain lower bounds for the number of rounds needed to solve these problems using a randomized algorithm on a p-processor machine. Our results on 'rounds' is of special interest in the context of designing work-efficient algorithms on a machine where latency and synchronization costs are high. Many of our lower bound results are complemented by upper bounds that match the lower bound or are close to it.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

SPAA 2014 - proceedings of the 26th acm symposium on parallelism in algorithms and architectures

SPAA 2014 - Proceedings of the 26th ACM Symposium on Paralle...

引用

26th acm symposium on parallelism in algorithms and architectures, SPAA 2014

ISBN: (纸本)9781450328210

the proceedings contain 42 papers. the topics discussed include: on dynamic bin packing for resource allocation in the cloud;on the online fault-tolerant server consolidation problem;on computing maximal independent sets of hypergraphs in parallel;simple parallel and distributed algorithms for spectral graph sparsification;concurrent data structures for efficient streaming aggregation;provably good scheduling for parallel programs that use data structures through implicit batching;scheduling selfish jobs on multidimensional parallel machines;LP rounding and combinatorial algorithms for minimizing active and busy time;a note on multiprocessor speed scaling with precedence constraints;executing dynamic data-graph computations deterministically using chromatic scheduling;the PCL theorem. transactions cannot be parallel, consistent and live;adaptive integration of hardware and software lock elision techniques;and transaction-friendly condition variables.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Explicit multi-threading (XMT) bridging models for instruction parallelism *(extended abstract) 98

Explicit multi-threading (XMT) bridging models for instructi...

引用

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

作者： Vishkin, U. Dascal, Sh. Berkovich, E. Nuzman, J. Univ of Maryland and Tel-Aviv Univ

ISBN: (纸本)9780897919890

this paper envisions an extension to a standard instruction set which efficiently implements PRAM-style algorithms using explicit multi-threaded instruction-level parallelism (ILP);that is, Explicit Multi-threading (XMT), a fine-grained computational paradigm covering the spectrum from algorithms through architecture to implementation is introduced;new elements are added where needed.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：