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

models FOR PRACTICAL parallel computation

INTERNATIONAL JOURNAL OF parallel PROGRAMMING 1991年第2期20卷 133-158页

作者： SKILLICORN, DB 1. Department of Computing and Information Science Queen's University Kingston Canada

A major reason for the lack of practical use of parallel computers has been the absence of a suitable model of parallel computation. Many existing models are either theoretical or are tied to a particular architecture. A more general model must be architecture independent, must realistically reflect execution costs, and must reduce the cognitive overhead of managing massive parallelism. A growing number of models meeting some of these goals have been suggested. We discuss their properties and relative strengths and weaknesses. We conclude that data parallelism is a style with much to commend it, and discuss the Bird-Meertens formalism as a coherent approach to data parallel programming.

关键词： models of parallel computation ARCHITECTURE-INDEPENDENT PROGRAMMING PRAM GRAPH REDUCTION UNITY ACTION SYSTEMS LINDA ACTORS PRAM EXTENSIONS DATA parallel PROGRAMMING BIRD-MEERTENS FORMALISM

来源：评论

学校读者我要写书评

暂无评论

parallelism in multigrid methods: How much is too much?

引用

INTERNATIONAL JOURNAL OF parallel PROGRAMMING 1996年第5期24卷 397-432页

作者： Matheson, LR Tarjan, RE PRINCETON UNIV DEPT COMP SCI PRINCETON NJ 08544 USA

Multigrid methods are powerful techniques to accelerate the solution of computationally-intensive problems arising in a broad range of applications. Used in conjunction with iterative processes for solving partial differential equations, multigrid methods speed up iterative methods by moving the computation from the original mesh covering the problem domain through a series of coarser meshes. But this hierarchical structure leaves domain-parallel versions of the standard multigrid algorithms with a deficiency of parallelism on coarser grids. To compensate, several parallel multigrid strategies with more parallelism, but also more work, have been designed. We examine these parallel strategies and compare them to simpler standard algorithms to try to determine which techniques are more efficient and practical. We consider three parallel multigrid strategies: (1) domain-parallel versions of the standard V-cycle and F-cycle algorithms;(2) a multiple coarse grid algorithm, proposed by Fredrickson and McBryan, which generates several coarse grids for each fine grid;and (3) two concurrent methods, the Chan-Tuminaro algorithm and the Gannonvan Rosendale algorithm, which allow computation on all grids simultaneously. We study an elliptic model problem on simple domains, discretized with finite difference techniques on block-structured meshes in two or three dimensions with up to 10(6) or 10(9) points, respectively. We analyze performance using three models of parallel computation: the PRAM and two bridging models. The bridging models reflect the salient characteristics of two kinds of parallel computers: SIMD fine-grain computers, which contain a large number of small (bit-serial) processors, and SPMD medium-grain computers, which have a more modest number of powerful (single chip) processors. Our analysis suggests that the standard algorithms are substantially more efficient than algorithms utilizing either parallel strategy. Both parallel strategies need too much extra wor

关键词： parallel multigrid methods parallel computers models of parallel computation

来源：评论

学校读者我要写书评

暂无评论

Portable and efficient parallel computing using the BSP model

引用

IEEE TRANSACTIONS ON COMPUTERS 1999年第7期48卷 670-689页

作者： Goudreau, MW Lang, K Rao, SB Suel, T Tsantilas, T NEC US C&C Res Labs Princeton NJ 08540 USA Polytech Univ Brooklyn NY 11201 USA Bear Stearns & Co New York NY 10167 USA

The Bulk-Synchronous parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory. the BSP model has been shown to allow the asymptotically optimal execution of architecture-independent software on a variety of architectures. Our goal in this work is to experimentally examine the practical use of the BSP model on current parallel architectures. We describe the design and implementation of the Green BSP Library, a small library of functions that implement the BSP model, and of several applications that were written for this library. We then discuss the performance of the library and application programs on several parallel architectures. Our results are positive in that we demonstrate efficiency and portability over a range of parallel architectures and show that the BSP cost model is useful for predicting performance trends and estimating execution times.

关键词： BSP minimum spanning tree problem models of parallel computation N-body problem parallel computing parallel graph algorithms shortest path problem

来源：评论

学校读者我要写书评

暂无评论

The queue-read queue-write pram model: Accounting for contention in parallel algorithms

引用

SIAM JOURNAL ON COMPUTING 1998年第2期28卷 733-769页

作者： Gibbons, PB Matias, Y Ramachandran, V AT&T Bell Labs Lucent Technol Murray Hill NJ 07974 USA Univ Texas Dept Comp Sci Austin TX 78712 USA

This paper introduces the queue-read queue-write (QRQW) parallel random access machine (pram) model, which permits concurrent reading and writing to shared-memory locations, but at a cost proportional to the number of readers/writers to any one memory location in a given step. Prior to this work there were no formal complexity models that accounted for the contention to memory locations, despite its large impact on the performance of parallel programs. The QRQW pram model reflects the contention properties of most commercially available parallel machines more accurately than either the well-studied CRCW pram or EREW pram models: the CRCW model does not adequately penalize algorithms with high contention to shared-memory locations, while the EREW model is too strict in its insistence on zero contention at each step. The QRQW PRAM is strictly more powerful than the EREW pram. This paper shows a separation of root log n between the two models, and presents faster and more efficient QRQW algorithms for several basic problems, such as linear compaction, leader election, and processor allocation. Furthermore, we present a work-preserving emulation of the QRQW pram with only logarithmic slowdown on Valiant's bsp model, and hence on hypercube-type noncombining networks, even when latency, synchronization, and memory granularity overheads are taken into account. This matches the best-known emulation result for the EREW pram, and considerably improves upon the best-known efficient emulation for the CRCW pram on such networks. Finally, the paper presents several lower bound results for this model, including lower bounds on the time required for broadcasting and for leader election.

关键词： models of parallel computation parallel algorithms PRAM memory contention work-time framework

来源：评论

学校读者我要写书评

暂无评论

Fast parallel sorting under LogP: Experience with the CM-5

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 1996年第8期7卷 791-805页

作者： Dusseau, AC Culler, DE Schauser, KE Martin, RP Computer Science Division University of California Berkeley CA USA University of California Santa Barbara USA

In this paper, we analyze four parallel sorting algorithms (bitonic, column, radix, and sample sort) with the LogP model. LogP characterizes the performance of modern parallel machines with a small set of parameters: the communication latency (L), overhead (o), bandwidth (g), and the number of processors (P). We develop implementations of these algorithms in Split-C, a parallel extension to C, and compare the performance predicted by LogP to actual performance on a CM-5 of 32 to 512 processors for a range of problem sizes. We evaluate the robustness of the algorithms by varying the distribution and ordering of the key values. We also briefly examine the sensitivity of the algorithms to the communication parameters. We show that the LogP model is a valuable guide in the development of parallel algorithms and a good predictor of implementation performance. The model encourages the use of data layouts which minimize communication and balanced communication schedules which avoid contention. With an empirical model of local processor performance, LogP predictions closely match observed execution times on uniformly distributed keys across a broad range of problem and machine sizes. We find that communication performance is oblivious to the distribution of the key values, whereas the local processor performance is not;some communication phases are sensitive to the ordering of keys due to contention. Finally, our analysis shows that overhead is the most critical communication parameter in the sorting algorithms.

关键词： massively parallel processing models of parallel computation sorting algorithm implementation communication performance communication schedules performance prediction performance analysis data layout

来源：评论

学校读者我要写书评

暂无评论

The queue-read queue-write asynchronous PRAM model

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期196卷 3-29页

作者： Gibbons, PB Matias, Y Ramachandran, V Univ Texas Dept Comp Sci Austin TX 78712 USA AT&T Bell Labs Murray Hill NJ 07974 USA

This paper presents results for the queue-read, queue-write asynchronous parallel random access machine (QRQW ASYNCHRONOUS PRAM) model, which is the asynchronous variant of the QRQW PRAM model. The QRQW PRAM family of models, which was introduced earlier by the authors, permit concurrent reading and writing to shared memory locations, but each memory location is viewed as having a queue which can service at most one request at a time. In the basic QRQW PRAM model each processor executes a series of reads to shared memory locations, a series of local computation steps, and a series of writes to shared memory locations, and then synchronizes with all other processors;thus this can be viewed as a bulk-synchronous model. In contrast, in the QRQW ASYNCHRONOUS PRAM model discussed in this paper, there is no imposed bulk-synchronization between processors, and each processor proceeds at its own pace. Thus, the QRQW ASYNCHRONOUS PRAM serves as a better model for designing and analyzing truly asynchronous parallel algorithms than the original QRQW PRAM. In this paper we elaborate on the QRQW ASYNCHRONOUS PRAM model, and we demonstrate the power of asynchrony over bulk-synchrony by presenting a work and time optimal deterministic algorithm on the QRQW ASYNCHRONOUS PRAM for the leader election problem and a simple randomized work and time optimal algorithm on the QRQW ASYNCHRONOUS PRAM for sorting. in contrast, no tight bounds are known on the QRQW PRAM for either deterministic or randomized parallel algorithms for leader election and the only work and time optimal algorithms for sorting known on the QRQW PRAM are those inherited from the EREW PRAM, which are considerably more complicated. Our sorting algorithm is an asynchronous version of an earlier sorting algorithm we developed for the QRQW PRAM, for which we use an interesting analysis to bound the running time to be O(log n). We also present a randomized algorithm to simulate one step of a CRCW PRAM on a QRQW ASYNCHRONOU

关键词： models of parallel computation asynchronous PRAM QRQW parallel algorithms sorting

来源：评论

学校读者我要写书评

暂无评论

A MODEL FOR ASYNCHRONOUS SHARED-MEMORY parallel computation

引用

SIAM JOURNAL ON COMPUTING 1994年第6期23卷 1231-1252页

作者： NISHIMURA, N Univ of Waterloo Waterloo Ont Canada

Traditional theoretical shared memory parallel models have been based on a number of assumptions which simultaneously simplify solutions to problems and distance the models from actual parallel machines. One such assumption is that processors work together in a synchronous fashion. Recent work has focused on finding a model that captures the essence of computation by processors communicating asynchronously through shared memory. In this paper, a general framework and set of criteria used to analyze these models, including the complexity analysis of several fundamental algorithmic paradigms, are considered. A general asynchronous model is introduced and how it satisfies these criteria is demonstrated. In this model, O(log p) algorithms are demonstrated for solving p-input versions of the problems of AND, OR, parity, maximum, minimum, and list ranking. To handle list ranking, a technique of analyzing algorithms is developed in which the set of tasks that are to be executed depends on the processor schedules.

关键词： ASYNCHRONY parallel computation models of parallel computation computationAL COMPLEXITY parallel ALGORITHMS

来源：评论

学校读者我要写书评

暂无评论

COMMUNICATION ISSUES IN THE DESIGN AND ANALYSIS OF parallel ALGORITHMS

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1981年第2期7卷 174-188页

作者： LINT, B AGERWALA, T IBM CORP THOMAS J WATSON RES CTRYORKTOWN HTSNY 10598

The importance of parallel programming increases as multiple processor systems become accepted more widely. Recent research investigates some approaches to the design and analysis of parallel algorithms, and several examples serve to illustrate the importance of interprocessor communication in parallel processing. Various techniques that are applicable in the design and analysis of parallel algorithms are reviewed, the emphasis being on those techniques that incorporate communication aspects. Included in the research are several models of synchronous and asynchronous parallel computation and their use in the analysis of algorithms. Relatively primitive methodologies for designing parallel algorithms are examined, with the conclusion that a need exists for more general and practical methodologies. models reviewed include: 1. a shared memory parallel method, 2. a communication-oriented model, and 3. automata models.

关键词： parallel Programming Analysis Of Algorithms models of parallel computation Module Assignment Problem Multiprocessing

来源：评论

学校读者我要写书评

暂无评论

A SURVEY OF PRAM SIMULATION TECHNIQUES

引用

ACM COMPUTING SURVEYS 1994年第2期26卷 187-206页

作者： HARRIS, TJ Univ. of Edinburgh Scotland

The parallel Random Access Machine (PRAM) is an abstract model of parallel computation which allows researchers to focus on the essential characteristics of a parallel architecture and ignore other details. The PRAM has long been acknowledged to be a useful tool for the study of parallel computing, but unfortunately it is not physically implementable in hardware. In order to take advantage of the broad base of algorithms and results regarding this high-level abstraction one needs general methods for allowing the execution of PRAM algorithms on more realistic machines. In the following we survey these methods, which we refer to as PRAM simulation techniques. The general issues of memory management and routing are discussed, and both randomized and deterministic solutions are considered. We show that good theoretical solutions to many of the subproblems in PRAM simulation have been developed, though questions still exist as to their practical utility. This article should allow those performing research in this field to become well acquainted with the current state of the art, while allowing the novice to get an intuitive feeling for the fundamental questions being considered. The introduction should provide a concise tutorial for those unfamiliar with the problem of PRAM simulation.

关键词： ALGORITHMS BOUNDED-DEGREE NETWORKS models of parallel computation parallel COMPLEXITY THEORY

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：