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

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

来源：评论

学校读者我要写书评

暂无评论

Linear-Work Greedy parallel Approximate Set Cover and Variants 11

Linear-Work Greedy Parallel Approximate Set Cover and Varian...

引用

23rd annual symposium on parallelism in algorithms and architectures

作者： Blelloch, Guy E. Peng, Richard Tangwongsan, Kanat Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450307437

We present parallel greedy approximation algorithms for set cover and related problems. These algorithms build on an algorithm for solving a graph problem we formulate and study called Maximal Nearly Independent Set (MANIS)-a graph abstraction of a key component in existing work on parallel set cover. We derive a randomized algorithm for MANIS that has O(m) work and O(log(2)m) depth on input with m edges. Using MANIS, we obtain RNC algorithms that yield a (1 + epsilon)H-n-approximation for set cover, a (1 - 1/e - epsilon)-approximation for max cover and a (4 + epsilon)-approximation for min-sum set cover all in linear work;and an O(log*n)-approximation for asymmetric k-center for k <= log(O(1)) n and a (1.861 + epsilon)-approximation for metric facility location both in essentially the same work bounds as their sequential counterparts.

关键词： parallel algorithms approximations algorithms set cover max cover facility location

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Distributed Unconstrained Local Search for Multilevel Graph Partitioning 24

Brief Announcement: Distributed Unconstrained Local Search f...

引用

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

作者： Sanders, Peter Seemaier, Daniel Karlsruhe Inst Technol Karlsruhe Germany

ISBN: (纸本)9798400704161

Partitioning a graph into blocks of roughly equal weight while cutting only few edges is a fundamental problem in computer science with numerous practical applications. While shared-memory parallel partitioners have recently matured to achieve the same quality as widely used sequential partitioners, there is still a pronounced quality gap between distributed partitioners and their sequential counterparts. In this work, we shrink this gap considerably by describing the engineering of an unconstrained local search algorithm suitable for distributed partitioners. We integrate the proposed algorithm in a distributed multilevel partitioner. Our extensive experiments show that the resulting algorithm scales to thousands of PEs while computing cuts that are, on average, only 3.5% larger than those of a state-of-the-art high-quality shared-memory partitioner. Compared to previous distributed partitioners, we obtain on average 6.8% smaller cuts than the best-performing competitor while being more than 9 times faster.

关键词： graph partitioning distributed algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel molecular computation 95

Parallel molecular computation

引用

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

作者： Reif, John H. Duke Univ

ISBN: (纸本)9780897917179

Techniques for quickly executing lengthy computations by the use of molecular parallelism are described. It is demonstrated that molecular computations can be done using short DNA strands by more or less conventional biotechnology engineering techniques within a small number of laboratory steps. Two abstract models of molecular computation are proposed. The first, the parallel Associative Memory Model, is a very high level model which includes a parallel Associative Matching operation, that appears to improve the power of molecular parallelism beyond the operations previously considered by Lipton (1994). A Recombinant DNA Model is also proposed which is a low level model that allows operations that are abstractions of very well understood recombinant DNA operations and provides a representation, herein called complex, for the relevant structural properties of DNA.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

parallel neighbourhood modeling: Research summary

Parallel neighbourhood modeling: Research summary

引用

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

作者： Hutchinson, D. Kuttner, L. Lanthier, M. Maheshwari, A. Nussbaum, D. Roytenberg, D. Sack, J.-R. Carleton Univ Ottawa Canada

NEighborhood MOdeling (NEMO) provides transparent parallelism to develop parallel spatial data processing. It addresses the following parallel issues: architecture and machine independence;communication bottlenecks;data visualization;casualty errors;load balancing;and data coherence. NEMO is capable of processing three types of time consuming raster neighborhood models: cellular automata;propagation;and neighborhood analysis. NEMO achieves this flexibility by including five components to its design: the three application drivers such as the cellular automata driver, propagation driver, and neighborhood analysis automata driver;and the display manager and raster database manager.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

parallel and (Nearly) Work-Efficient Dynamic Programming 24

Parallel and (Nearly) Work-Efficient Dynamic Programming

引用

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

作者： Ding, Xiangyun Gu, Yan Sun, Yihan Univ Calif Riverside Riverside CA 92521 USA

ISBN: (纸本)9798400704161

The idea of dynamic programming (DP), proposed by Bellman in the 1950s, is one of the most important algorithmic techniques. However, in parallel, many fundamental and sequentially simple problems become more challenging, and open to a (nearly) work-efficient solution (i.e., the work is off by at most a polylogarithmic factor over the best sequential solution). In fact, sequential DP algorithms employ many advanced optimizations such as decision monotonicity or special data structures, and achieve better work than straightforward solutions. Many such optimizations are inherently sequential, which creates extra challenges for a parallel algorithm to achieve the same work bound. The goal of this paper is to achieve (nearly) work-efficient parallel DP algorithms by parallelizing classic, highly-optimized and practical sequential algorithms. We show a general framework called the Cordon Algorithm for parallel DP algorithms, and use it to solve several classic problems. Our selection of problems includes Longest Increasing Subsequence (LIS), sparse Longest Common Subsequence (LCS), convex/concave generalized Least Weight Subsequence (LWS), Optimal Alphabetic Tree (OAT), and more. We show how the Cordon Algorithm can be used to achieve the same level of optimization as the sequential algorithms, and achieve good parallelism. Many of our algorithms are conceptually simple, and we show some experimental results as proofs-of-concept.

关键词： parallel algorithms Dynamic Programming Longest Increasing Subsequence Longest Common Subsequence Least Weighted Sum Optimal Alphabetic Tree Decision Monotonicity

来源：评论

学校读者我要写书评

暂无评论

The power of parallel pointer manipulation 89

The power of parallel pointer manipulation

引用

1st annual acm symposium on parallel algorithms and architectures, SPAA 1989

作者： Lam, Tak Wah Ruzzo, Walter L. Department of Computer Science University of Hong Kong Pokfulam Road Hong Kong Computer Science Department University of Washington SeattleWA98195 United States

ISBN: (纸本)089791323X

An HMM is a very simple parallel machine consisting of finite state devices that can manipulate pointers to each other. The more commonly studied PRAM is a much richer parallel machine with a shared global memory and arithmetic capabilities. We define a natural restriction of the PRAM that is shown to be equivalent to the HMM to within a constant factor in both time and hardware simultaneously. Basically, the restricted PRAM is a Concurrent Read, Owner Write (CROW) PRAM, stripped of arithmetic capabilities, except for successor (+1) a doubling ( x 2) operations. © 1989 acm.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Quantitative comparison of parallel computation models

Quantitative comparison of parallel computation models

引用

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

作者： Juurlink, Ben H.H. Wijshoff, Harry A.G. Leiden Univ Leiden Netherlands

This paper experimentally validates performance related issues for parallel computation models on several parallel platforms (a MasPar MP-1 with 1024 processors, a 64-node GCel and a CM-5 of 64 processors). Our work consists of three parts. First, there is an evaluation part in which we investigate whether the models correctly predict the execution time of an algorithm implementation. Unlike previous work, which mostly demonstrated a close match between the measured and predicted running times, this paper shows that there are situations in which the models do not precisely predict the actual execution time of an algorithm implementation. Second, there is a comparison part in which the models are contrasted with each other in order to determine which model induces the fastest algorithms. Finally, there is an efficiency validation part in which the performance of the model derived algorithms are compared with the performance of highly optimized library routines to show the effectiveness of deriving fast algorithms through the formalisms of the models.

关键词： parallel processing systems

来源：评论

学校读者我要写书评

暂无评论

On a scheme for parallel sorting on heterogeneous clusters

引用

FUTURE GENERATION COMPUTER SYSTEMS 2002年第3期18卷 353-372页

作者： Cérin, C Gaudiot, JL Univ So Calif Los Angeles CA 90089 USA Univ Picardie Jules Verne Laria F-80000 Amiens France

We discuss parallel sorting algorithms and their implementations suitable for cluster architectures in order to optimize cluster resources. We focus on the time spent in computation and the load balancing properties when processors are running at different speeds, i.e. correlated by a multiplicative constant factor (our weak definition of heterogeneous platform). One scheme is under study: parallel sorting by sampling (either regular sampling technique introduced by Shi and Schaeffer [J. parallel Distrib. Comput. 14 (4) (1992) 361] or the over-partitioning scheme introduced by Li and Seveik [parallel sorting by over-partitioning, in: proceedings of the Sixth annual symposium on parallel algorithms and architectures, acm Press, New York, June 1994]). What is important in the paper is mainly the load balance factor and not necessary the execution time. It is clear that improved load balance leads to improved execution titre. The results presented in the paper demonstrate that load balancing for the case of computers with heterogeneous processing capacity is more challenging than for the homogeneous case. The survey, through the sorting case study, allow us to identify some algorithmic issues and software challenges to master heterogeneous cluster platforms in order to better utilize theta: data decomposition techniques, scheduling and load balancing methods. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： performance evaluation and modeling of parallel integer sorting algorithms sorting by regular sampling and by over-partitioning data distribution load balancing strategies BSP programming

来源：评论

学校读者我要写书评

暂无评论

Directed Transmission Method, a Fully Asynchronous Approach to Solve Sparse Linear Systems in parallel 08

Directed Transmission Method, a Fully Asynchronous Approach ...

引用

20th acm symposium on parallelism in algorithms and architectures

作者： Wei, Fei Yang, Huazhong Tsinghua Univ Dept Elect Engn Beijing Peoples R China

ISBN: (纸本)9781595939739

There are many algorithms to solve large sparse linear systems in parallel;however, most of them acquire synchronization and thus are lack of scalability. In this paper, we propose a new distributed numerical algorithm, called Directed Transmission Method (DTM). DTM is a fully asynchronous, scalable and continuous-time iterative algorithm to solve the arbitrarily-large sparse linear system whose coefficient matrix is symmetric-positive-definite (SPD). DTM is able to be freely running on the heterogeneous parallel computer with arbitrary number of processors, which might be manycore microprocessors, clusters, grids, clouds, and the Internet. We proved that DTM is convergent by making use of the final value theorem of Laplacian Transformation. Numerical experiments show that DTM is efficient.

关键词： Asynchronous Algorithm Convergence Theory Directed Transmission Method (DTM) Distributed Algorithm Sparse Linear System Virtual Transmission Method (VTM)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：