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

Efficient deterministic sorting on the BSP model

Parallel Processing Letters 1999年第1期9卷 69-79页

作者： Gerbessiotis, Alexandros V. Programming Research Group Computing Laboratory Oxford University Oxford OX1 3QD United Kingdom

We present a new algorithm for deterministic sorting on the Bulk-Synchronous Parallel (BSP) model of computation. We sort n keys using a partitioning scheme that achieves the requirements of efficiency (one-optimality) and insensitivity against initial key distribution. Although we employ sampling to realize efficiency, we give a precise worst-case estimation of the maximum imbalance which might occur. The algorithm is one-optimal for a wide range of the BSP parameters in the sense that its speedup on p processors is asymptotically (1 - o(1)) p.

关键词： Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Re-synthesis in technology mapping for heterogeneous FPGAs

Re-synthesis in technology mapping for heterogeneous FPGAs

引用

IEEE International Conference on Computer Design: VLSI in Computers and Processors, (ICCD)

作者： M. Inuani J. Saul Programming Research Group Oxford University Computing Laboratory Oxford UK

Field programmable gate arrays containing more than one size of lookup-table occupy a large and growing portion of the market, but technology mapping for these architectures has hardly been considered. New algorithms have been developed for decomposition, covering and restructuring targeted at these architectures. Benchmark results show that the new method produces circuits which are on average 15% smaller than the best previous approach we know of.

关键词： Field programmable gate arrays Table lookup Cost function Logic circuits Laboratories Programmable logic arrays Consumer electronics Reconfigurable logic Prototypes Integrated circuit interconnections

来源：评论

学校读者我要写书评

暂无评论

PRAM programming: theory vs. practice

PRAM programming: theory vs. practice

引用

Euromicro Workshop on Parallel and Distributed Processing

作者： A.V. Gerbessiotis D.S. Lecomber C.J. Siniolakis K.R. Sujithan Programming Research Group Computing Laboratory Oxford University Oxford UK

We investigate the practical viability of PRAM programming within the BSP framework. We argue that there is a necessity for PRAM computations in situations where the problem exhibits poor data locality. We introduce a C++ PRAM simulator that is built on top of the Oxford BSP Toolset, BSPlib, and provide a succinct PRAM language. Our approach achieves simplicity of programming over direct-mode BSP programming for reasonable overhead cost. We objectively compare optimized BSP algorithms with PRAM algorithms implemented with our library and provide encouraging experimental results for the latter style of programming.

关键词： Phase change random access memory Concurrent computing Computational modeling Costs Memory management Hardware Automatic programming Laboratories DSL Libraries

来源：评论

学校读者我要写书评

暂无评论

Billiards and related systems on the bulk-synchronous parallel model

Billiards and related systems on the bulk-synchronous parall...

引用

11th Workshop on Parallel and Distributed Simulation

作者： Marin, M Programming Research Group Computing Laboratory University of Oxford Oxford UK

ISBN: (纸本)0818679654

With two examples we show the suitability of the bulk-synchronous parallel (BSP) model for discrete-event simulation of homogeneous large-scale systems. This model provides a unifying approach for general purpose parallel computing which in addition to efficient and scalable computation, ensures portability across different parallel architectures. A valuable feature of this approach is a simple cost model that enables precise performance prediction of BSP algorithms. We show both theoretically and empirically that systems with uniform event occurrence among their components, such as colliding hard-spheres and ising-spin models, can be efficiently simulated in practice on current parallel computers supporting the BSP model.

关键词： Discrete event simulation Concurrent computing Large-scale systems Parallel processing Parallel architectures Costs Predictive models Prediction algorithms Computational modeling Computer simulation

来源：评论

学校读者我要写书评

暂无评论

Probabilistic models for the guarded command language

引用

SCIENCE OF COMPUTER programming 1997年第2-3期28卷 171-192页

作者： He, JF Seidel, K McIver, A Oxford University Computing Laboratory Programming Research Group 11 Keble. Road Oxford OX1 3QD UK

The two models presented in this paper provide two different semantics for an extension of Dijkstra's language of guarded commands. The extended language has an additional operator, namely probabilistic choice, which makes it possible to express randomized algorithms. An earlier model by Claire Jones included probabilistic choice but not non-determinism, which meant that it could not be used for the development of algorithms from specifications. Our second model is built on top of Claire Jones' model, using a general method of extending a probabilistic cpo to one which also contains non-determinism. The first model was constructed from scratch, as it were, guided only by the desire for certain algebraic properties of the language constructs, which we found lacking in the second model. We compare and contrast the properties of the two models both by giving examples and by constructing mappings between them and the non-probabilistic model. On the basis of this comparison we argue that, in general, the first model is preferable to the second. (C) 1997 Elsevier Science B.V.

关键词： probabilistic programming language semantics algebraic laws

来源：评论

学校读者我要写书评

暂无评论

Event-driven hard-particle molecular dynamics using bulk-synchronous parallelism

引用

COMPUTER PHYSICS COMMUNICATIONS 1997年第1-3期102卷 81-96页

作者： Marin, M Programming Research Group Wolson Building Parks Road Computing Laboratory University of Oxford Oxford OX1 3QD England UK

We describe and analyse a new parallel algorithm for event-driven simulation of hard-particle systems that is based on the ideas of the bulk-synchronous parallel (BSP) model. This model provides a unifying approach for general purpose parallel computing which in addition to efficient computation ensures portability across different parallel architectures. The hard-particle system is divided into regions that are owned by a unique processor. Events involving particles located in the region boundaries are called border zone events and are used to synchronize the parallel operation of the processors. On a P-processor BSP computer the algorithm works doing iterations composed of two phases: the parallel phase where each processor is simultaneously allowed to simulate serially and asynchronously its own region, and the synchronization phase where the occurrence of at most P border zone events is scheduled for the next iteration considering the state of neighboring regions. We show that this algorithm is efficient in practice provided that a sufficiently large hard-particle system is to be simulated.

关键词： molecular dynamics hard particles parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

The Rely-Guarantee Method for Verifying Shared Variable Concurrent Programs

引用

Formal Aspects of computing 1997年第2期9卷 149-174页

作者： Xu, Qiwen De Roever, Willem-Paul He, Jifeng Inst. Informatik Praktische M. Chrstn.-Albrechts-Univ. zu Kiel Kiel Germany Programming Research Group Oxford Univ. Computing Laboratory Oxford United Kingdom Intl. Inst. for Software Technology United Nations University PO Box 3058 Macao

Compositional proof systems for shared variable concurrent programs can be devised by including the interference information in the specifications. The formalism falls into a category called rely-guarantee (or assumption-commitment), in which a specification is explicitly (syntactically) split into two corresponding parts. This paper summarises existing work on the rely-guarantee method and gives a systematic presentation. A proof system for partial correctness is given first, thereafter it is demonstrated how the relevant rules can be adapted to verify deadlock freedom and convergence. Soundness and completeness, of which the completeness proof is new, are studied with respect to an operational model. We observe that the rely-guarantee method is in a sense a reformulation of the classical non-compositional Owicki & Gries method, and we discuss throughout the paper the connection between these two methods.

关键词： Compositionality Concurrency Deadlock freedom Partial and total correctness Rely-Guarantee formalism Soundness and completeness Specification and verification

来源：评论

学校读者我要写书评

暂无评论

Billiards and related systems on the bulk-synchronous parallel model 97

Billiards and related systems on the bulk-synchronous parall...

引用

Proceedings of the eleventh workshop on Parallel and distributed simulation

作者： Mauricio Marín Programming Research Group Computing Laboratory University of Oxford Wolson Building Parks Road Oxford OX1 3QD England UK

ISBN: (纸本)9780818679650

关键词： ising-spin models bulk-synchronous parallel model discrete event simulation general purpose parallel computing billiards homogeneous large-scale systems colliding hard-spheres scalable computation discrete-event simulation

来源：评论

学校读者我要写书评

暂无评论

BULK-SYNCHRONOUS PARALLEL ALGORITHMS FOR QR AND QZ MATRIX FACTORISATION

引用

Parallel Algorithms and Applications. 1997年第1-2期11卷 97-112页

作者： RADU CALINESCU DAVID J. EVANS [a] Programming Research Group Oxford University Computing Laboratory Oxford 0X1 3QD UK [b] Parallel Algorithms Research Centre Loughborough University of Technology Loughborough Leicestershire LE11 3TU UK

This paper presents bulk-synchronous parallel (BSP) algorithms for linear system solving through QR and QZ factorisation. The two new algorithms are analysed in terms of the BSP cost model, and portable implementations of the QR and QZ decomposition methods are devised using the Oxford BSP Library. The experimental results obtained on a shared-memory multiprocessor accurately match the theoretical predictions, permitting a thorough comparison of the two algorithms.

关键词： linear system solving QR factorisation QZ factorisation bulk-synchronous parallel model

来源：评论

学校读者我要写书评

暂无评论

A fundamental group for greyscale digital images

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 1996年第2-3期6卷 161-167页

作者： Newman, M Programming Research Group Oxford University Computing Laboratory Oxford United Kingdom

One of the concepts from topology that has found use in image processing is the so called Fundamental group of an image. A definition for the digital fundamental group of a binary picture was introduced by Kong in A digital fundamental group [4]. This paper introduces a fundamental group for greyscale images. We also describe Poincare's classical method for computing a representation of the fundamental group and extend this to work with our greyscale version.

关键词： Image processing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：