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

11th annual acm symposium on parallel algorithms and architectures

作者： Gibbons, PB Bruno, JL Phillips, S Intel Res Pittsburgh Pittsburgh PA 15213 USA Univ Calif Davis Off Vice Provost Informat & Educ Technol Davis CA 95616 USA AT&T Labs Res Shannon Lab Florham Pk NJ 07932 USA

Operations on basic. data structures such as, queues, priority queues, stacks, and counters c an dominate the execution time of a parallel program due to both their frequency and their coordination and contention overheads. There are considerable performance payoffs in developing highly optimized, asynchronous, distributed, cache-conscious, parallel implementations of such data structures. Such implementations may employ a variety of tricks to reduce latencies and avoid serial bottlenecks, as long as the semantics of the data structure are preserved The complexity of the implementation and the difficulty in reasoning about asynchronous systems increases concerns regarding possible bugs in the implementation. In this paper we consider postmortem, black-box procedures for testing whether a, parallel data structure:behaved correctly. We present the first systematic study of algorithms and hardness results for such testing procedures, focusing on queues, priority queues, stacks, and counters, under various important scenarios. Our results demonstrate the importance of selecting test data such that distinct values are inserted into them data structure (as appropriate). In such cases we present an O (n) time algorithm for testing linearizable queues, an O (n log n) time algorithm for testing linearizable priority queues, and an O (np(2)) time algorithm for testing sequentially consistent queues, where n is the number of data structure operations and p is the number of processors. In contrast, we show that testing such data structures for executions with arbitrary input values is NP-complete. Our results also help clarify the thresholds between scenarios that admit polynomial time solutions and those that are NP-complete. Our algorithms are the first nontrivial algorithms for these problems.

关键词： Data structures

来源：评论

学校读者我要写书评

暂无评论

Black-box correctness tests for basic parallel data structures

引用

THEORY OF COMPUTING SYSTEMS 2002年第4期35卷 391-432页

关键词：

来源：评论

学校读者我要写书评

暂无评论

A simple and efficient parallel disk mergesort

引用

THEORY OF COMPUTING SYSTEMS 2002年第2期35卷 189-215页

作者： Barve, RD Vitter, JS Winphoria Networks Andheri 400093 Mumbai India Duke Univ Dept Comp Sci Ctr Geometr & Biol Comp Durham NC 27708 USA

External sorting-the process of sorting a file that is too large to fit into the computer's internal memory and must be stored externally on disks-is a fundamental subroutine in database systems [G], [IBM]. Of prime importance are techniques that use multiple disks in parallel in order to speed up the performance of external sorting. The simple randomized merging (SRM) mergesort algorithm proposed by Barve et al. [BGV] is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth [K, Section 5.4.9] recently identified SRM (which he calls "randomized striping") as the method of choice for sorting with parallel disks. In this paper we present an efficient implementation of SRM, based upon novel and elegant data structures. We give a new implementation for SRM's lookahead forecasting technique for parallel prefetching and its forecast and flush technique for buffer management. Our techniques amount to a significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to read blocks of input runs efficiently during external merging. Our implementation is based on synchronous parallel I/O primitives provided by the TPIE programming environment [TPI], whenever our program issues an I/O read (write) operation, one block of data is synchronously read from (written to) each disk in parallel. We compare the performance of SRM over a wide range of input sizes with that of disk-striped mergesort (DSM), which is widely used in practice. DSM consists of a standard mergesort in conjunction with striped I/O for parallel disk access. SRM merges together significantly more runs at a time compared with DSM, and thus it requires fewer merge passes. We demonstrate in practical scenarios that even though the streaming speeds for merging with DSM are a little higher than those for SRM (since DSM merges fewer runs at a time), sorting using SRM is often significantly faster than with DSM

关键词：

来源：评论

学校读者我要写书评

暂无评论

Two techniques for reconciling algorithm parallelism with memory constraints 02

Two techniques for reconciling algorithm parallelism with me...

引用

Proceedings of the fourteenth annual acm symposium on parallel algorithms and architectures

作者： Uzi Vishkin University of Maryland

ISBN: (纸本)9781581135299

The utility of algorithm parallelism for coping with increased processor to memory latencies using "latency hiding" is part of the folklore of parallel computing. Latency hiding techniques increase the traffic to memory and therefore may "hit another wall": limited bandwidth to memory. The current paper attempts to stimulate research in the following general direction: show that algorithm parallelism need not conflict with limited bandwidth.A general technique for using parallel algorithms to enhance serial implementation in the face of processor-memory latency problems is revisited. Two techniques for alleviating memory bandwidth constraints are presented. Both techniques can be incorporated in a *** is often considerable parallelism in many of the algorithms which are known as useful serial algorithms. Interestingly enough, all the examples provided for the use of the two techniques come from such serial algorithms.

关键词： prefetching memory systems constraints parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A simple and efficient parallel disk mergesort

A simple and efficient parallel disk mergesort

引用

11th annual acm symposium on parallel algorithms and architectures

作者： Barve, RD Vitter, JS Winphoria Networks Andheri 400093 Mumbai India Duke Univ Dept Comp Sci Ctr Geometr & Biol Comp Durham NC 27708 USA

关键词： Computation theory

来源：评论

学校读者我要写书评

暂无评论

parallel dynamic programming for solving the string editing problem on a CGM/BSP 02

Parallel dynamic programming for solving the string editing ...

引用

Proceedings of the fourteenth annual acm symposium on parallel algorithms and architectures

作者： C. E. R. Alves E. N. Cáceres F. Dehne FTCE - Universidade São São Paulo Brazil Universidade Federal de Mato Campo Grande Brazil Carleton University Ottawa Canada

ISBN: (纸本)9781581135299

In this paper we present a coarse-grained parallel algorithm for solving the string edit distance problem for a string A and all substrings of a string C. Our method is based on a novel CGM/BSP parallel dynamic programming technique for computing all highest scoring paths in a weighted grid graph. The algorithm requires \log p rounds/supersteps and O(\fracn^2p\log m) local computation, where $p$ is the number of processors, p^2 \leq m \leq n. To our knowledge, this is the first efficient CGM/BSP algorithm for the alignment of all substrings of C with A. Furthermore, the CGM/BSP parallel dynamic programming technique presented is of interest in its own right and we expect it to lead to other parallel dynamic programming methods for the CGM/BSP.

关键词： BSP string editing parallel algorithms dynamic programming CGM

来源：评论

学校读者我要写书评

暂无评论

annual acm symposium on parallel algorithms and architectures: Foreword

Annual ACM Symposium on Parallel Algorithms and Architecture...

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

作者： Anon

来源：评论

学校读者我要写书评

暂无评论

Thirteen annual acm symposium on parallel algorithms and architectures

Thirteen annual ACM symposium on parallel algorithms and arc...

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

The proceedings contains 48 papers from Thirteen annual acm symposium on parallel algorithms and architectures. Topics discussed include: compact routing schemes;simple on-line algorithms for the maximum disjoint paths problem;competitive buffer management for shared-memory switches;attack propagation in networks;computational power of pipelined memory hierarchies;and a data tracking scheme for general networks.

关键词： Routers

来源：评论

学校读者我要写书评

暂无评论

Towards practical deterministic Write-All algorithms

Towards practical deterministic Write-All algorithms

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

作者： Chlebus, B.S. Malewicz, G. Dobrev, S. Shvartsman, A. Kowalski, D.R. Vrto, I. Instytut Informatyki Uniwersytet Warszawski Banacha 2 Warszawa 02-097 Poland

A family of deterministic asynchronous Write-All algorithms were studied to analyze the properties of the set of permutations proposed by Kanellakis and Shvartsman. The efficiency of the algorithms was measured in terms of work acounted for all machine instructions executed by processors. It was found that the analytical results covered only a subset of the possible adversarial patterns of asynchrony. The analysis suggested that the proposed method yielded a faster construction of the Write-All algorithms compared to other methods.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

A parallel block algorithm for exact triangularization of rectangular matrices

A parallel block algorithm for exact triangularization of re...

引用

13th annual symposium on parallel algorithms and architectures (SPAA 2001)

作者： Dumas, J.-G. Roch, J.-L. Lab. Informatique et Distribution ENSIMAG - antenne de'Montbonnot ZIRST - 51 av. Jean Kuntzmann 38330 Montbonnot Saint-Martin France

A new block algorithm for triangularization of regular or singular matrices with dimension m × n, is proposed. Taking benefit of fast block multiplication algorithms, it achieves the best known sequential complexity O(mω-1n) for any sizes and any rank. Moreover, the block strategy enables to improve locality with respect to previous algorithms as exhibited by practical performances.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：