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

MODELING AND EVALUATION OF A NEW message-passing system FOR PARALLEL MULTIPROCESSOR systemS

PARALLEL COMPUTING 1993年第6期19卷 633-649页

作者： AZARIA, H ELOVICI, Y Department of Electrical and Computer Engineering Ben-Gurion University of the Negev Beer-Sheva Israel

As parallel implementation of complex applications is becoming popular, the need for a high performance interprocessor communication system becomes imminent, especially in loosely coupled distributed-memory multiprocessor networks. An important factor in the efficiency of these networks is the effectiveness of the message-passing system which manages the data exchanges among the processors of the network. This paper presents the modeling and performance evaluation of a new message-passing system (MPS) for distributed multiprocessor networks without shared-memory and where the processors or Processing Elements (PEs) are connected to each other by point-to-point communication links. For maximum performance, the MPS manages the communication and the synchronization between the different tasks of an application by means of three approaches. One is an asynchronous send/receive approach which handles efficiently server like tasks. the second is a synchronous send/receive approach which handles efficiently streaming communication mode and the third is a virtual channel approach which minimizes the overhead of the synchronization mechanism, efficiently handling the burst mode of heavy communication between tasks. The developed models of the MPS approaches enable the determination of analytical expressions for different performances and a comparison between analytical and experimental performances reveals that the models predict the MPS performance with high accuracy. The MPS written in Parallel ANSI C, is studied on a mesh topology network of 16 transputers T800. The MPS performances for each approach are studied and presented in terms of communication latency, throughput, computation efficiency and memory consumption.

关键词： message-passing system DISTRIBUTED-MEMORY MULTIPROCESSOR PARALLEL IMPLEMENTATION TRANSPUTER NETWORK MODELING PERFORMANCE EVALUATION

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for all-to-all communications in multiport message-passing systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED systemS 1997年第11期8卷 1143-1156页

作者： Bruck, J Ho, CT Kipnis, S Upfal, E Weathersby, D IBM CORP ALMADEN RES CTRSAN JOSECA 95120 NEWS DATACOM RES LTD IL-34635 HAIFAISRAEL UNIV WASHINGTON DEPT COMP SCI & ENGNSEATTLEWA 98195

We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-to-all personalized communication) and concatenation (or all-to-all broadcast). We assume a model of a fully connected message-passing system, in which the performance of any point-to-point communication is independent of the sender-receiver pair. We also assume that each processor has k greater than or equal to 1 ports, through which it can send and receive k messages in every communication round. The complexity measures we use are independent of the particular system topology and are based on the communication start-up time, and on the communication bandwidth. In the index operation among n processors, initially, each processor has n blocks of data, and the goal is to exchange the ith block of processor j with the jth block of processor i. We present a class of index algorithms that is designed for all values of n and that features a trade-off between the communication start-up time and the data transfer time. This class of algorithms includes two special cases: an algorithm that is optimal with respect to the measure of the start-up time, and an algorithm that is optimal with respect to the measure of the data transfer time. We also present experimental results featuring the performance tuneability of our index algorithms on the IBM SP-1 parallel system. In the concatenation operation, among n processors, initially, each processor has one block of data, and the goal is to concatenate the n blocks of data from the n processors, and to make the concatenation result known to all the processors. We present a concatenation algorithm that is optimal, for most values of n, in the number of communication rounds and in the amount of data transferred.

关键词： all-to-all broadcast all-to-all personalized communication complete exchange concatenation operation distributed-memory system index operation message-passing system multiscatter/gather parallel system

来源：评论

学校读者我要写书评

暂无评论

Read/write shared memory abstraction on top of asynchronous Byzantine message-passing systems

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2016年 93-94卷 1-9页

作者： Imbs, Damien Rajsbaum, Sergio Raynal, Michel Stainer, Julien Univ Bremen Dept Math D-28359 Bremen Germany Inst Univ France Paris France Univ Rennes IRISA F-35042 Rennes France Ecole Polytech Fed Lausanne Distributed Programming Lab CH-1015 Lausanne Switzerland Univ Nacl Autonoma Mexico Inst Matemat Mexico City DF Mexico

This paper is on the construction and use of a shared memory abstraction on top of an asynchronous message-passing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n single-writer/multi-reader atomic registers, where n is the number of processes. These registers enable Byzantine tolerance by recording the whole history of values written to each one of them. A distributed algorithm building such a shared memory abstraction is first presented. This algorithm assumes t < n/3, which is shown to be a necessary and sufficient condition for such a construction. Hence, the algorithm is resilient-optimal. Then the paper presents distributed objects built on top of this read/write shared memory abstraction, which cope with Byzantine processes. As illustrated by these objects, the proposed shared memory abstraction is motivated by the fact that, for a lot of problems, algorithms are simpler to design and prove correct in a shared memory system than in a message-passing system. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Approximate agreement Asynchronous message-passing system Atomic read/write register Broadcast abstraction Byzantine process Distributed computing message-passing system Quorum Reliable broadcast Reliable shared memory Single-writer/multi-reader register t-Resilience

来源：评论

学校读者我要写书评

暂无评论

Reliable Shared Memory Abstraction on Top of Asynchronous Byzantine message-passing systems

引用

21st International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Imbs, Damien Rajsbaum, Sergio Raynal, Michel Stainer, Julien Univ Nacl Autonoma Mexico Inst Math Mexico City 04510 DF Mexico Inst Univ France F-75005 Paris France IRISA F-35042 Rennes France

ISBN: (纸本)9783319096209;9783319096193

This paper is on the construction and the use of a shared memory abstraction on top of an asynchronous message-passing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n single-writer/multi-reader atomic registers, where n is the number of processes. Differently from usual atomic registers which record a single value, each of these atomic registers records the whole history of values written to it. A distributed algorithm building such a shared memory abstraction it first presented. This algorithm assumes t < n/3, which is shown to be a necessary and sufficient condition for such a construction. Hence, the algorithm is resilient-optimal. Then the paper presents distributed algorithms built on top of this shared memory abstraction, which cope with up to t Byzantine processes. The simplicity of these algorithms constitutes a strong motivation for such a shared memory abstraction in the presence of Byzantine processes. For a lot of problems, algorithms are more difficult to design and prove correct in a message-passing system than in a shared memory system. Using a protocol stacking methodology, the aim of the proposed abstraction is to allow an easier design (and proof) of distributed algorithms, when the underlying system is an asynchronous message-passing system prone to Byzantine failures.

关键词： APppproximate agreement Asynchronous message-passing system Atomic read/write register Broadcast abstraction Byzantine process Distributed computing message-passing system Quorum Reliable broadcast Reliable shared memory Single-writer/multi-reader register t-Resilience

来源：评论

学校读者我要写书评

暂无评论

Quorum-based group mutual exclusion algorithm for a distributed system with dynamic group set

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED systemS 2007年第10期18卷 1345-1360页

作者： Atreya, Ranganath Mittal, Neeraj Peri, Sathya Univ Texas Dept Comp Sci Richardson TX 75083 USA

The group mutual exclusion problem extends the traditional mutual exclusion problem by associating a type ( or a group) with each critical section. In this problem, processes requesting critical sections of the same type can execute their critical sections concurrently. However, processes requesting critical sections of different types must execute their critical sections in a mutually exclusive manner. We present a distributed algorithm for solving the group mutual exclusion problem based on the notion of surrogate-quorum. Intuitively, our algorithm uses the quorum that has been successfully locked by a request as a surrogate to service other compatible requests for the same type of critical section. Unlike the existing quorum-based algorithms for group mutual exclusion, our algorithm achieves a low message complexity of O(q) and a low ( amortized) bit-message complexity of O(bqr), where q is the maximum size of a quorum, b is the maximum number of processes from which a node can receive critical section requests, and r is the maximum size of a request while maintaining both synchronization delay and waiting time at two message hops. As opposed to some existing quorum-based algorithms, our algorithm can adapt without performance penalties to dynamic changes in the set of groups. Our simulation results indicate that our algorithm outperforms the existing quorum-based algorithms for group mutual exclusion by as much as 45 percent in some cases. We also discuss how our algorithm can be extended to satisfy certain desirable properties such as concurrent entry and unnecessary blocking freedom.

关键词： message-passing system resource management mutual exclusion group mutual exclusion quorum-based algorithm

来源：评论

学校读者我要写书评

暂无评论

MICROS, A DISTRIBUTED OPERATING system FOR MICRONET, A RECONFIGURABLE NETWORK COMPUTER

引用

IEEE TRANSACTIONS ON COMPUTERS 1980年第12期29卷 1133-1144页

作者： WITTIE, LD VANTILBORG, AM Department of Computer Science State University of New York

MICROS is the distributed operating system for the MICRONET network computer. MICRONET is a reconfigurable and extensible network of 16 loosely coupled LSI-11 microcomputer nodes, connected by packet-switching interfaces to pairs of high-speed shared communication buses. MICROS simultaneously supports many users, each running multicomputer parallel programs. MICROS is intended for control of network computers of thousands of nodes.

关键词： Concurrent Pascal MICRONET/ MICROS distributed operating system management hierarchy message-passing system multimicrocomputer network computer packet-switching network reconfigurable parallel computer

来源：评论

学校读者我要写书评

暂无评论

What Can be Computed in a Distributed system?

引用

Workshop on From Programs to systems - The systems Perspective in Computing (FPS) held in Honor of Joseph Sifakis

作者： Raynal, Michel Univ Rennes Inst Univ France Rennes France

ISBN: (纸本)9783642548482;9783642548475

Not only the world is distributed, but more and more applications are distributed. Hence, a fundamental question is the following one: What can be computed in a distributed system? The answer to this question depends on the environment in which evolves the considered distributed system, i.e., on the assumptions the system relies on. This environment is very often left implicit and nearly always not formulated in terms of precise underlying requirements. In the extreme case where the environment is such that there is no synchrony assumption and the computing entities may commit failures, many problems become impossible to solve (in these cases, a network of Turing machines where some machines may crash, is less powerful than a single reliable Turing machine). Given a distributed computing problem, it is consequently important to know the weakest assumptions (lower bounds) that give the limits beyond which the considered distributed problem cannot be solved. This paper is a short introduction to this kind of issues. It first presents a few of elements related to distributed computability, and then briefly addresses distributed complexity issues. The style of the paper is voluntarily informal.

关键词： Agreement Asynchronous system Atomicity Concurrency Consensus Crash failure Distributed complexity Distributed computability Distributed computing Environment Fault-tolerance Impossibility Indulgence message adversary message-passing system Progress condition Read/ write system Synchronous system Universal construction Wait-freedom

来源：评论

学校读者我要写书评

暂无评论

AN OPTIMAL ALGORITHM FOR COMPUTING CENSUS FUNCTIONS IN message-passing systemS

引用

Parallel Processing Letters 1993年第1期3卷 19-23页

作者： AMOTZ BAR-NOY SHLOMO KIPNIS BARUCH SCHIEBER IBM Research Division T.J. Watson Research Center Yorktown Heights NY 10598 USA

We consider a message-passing system of n processors, each of which initially holds one piece of data. The goal is to compute an associative and commutative census function f on the n distributed pieces of data and to make the result known to all processors. To perform the computation, processors communicate with each other by sending and receiving messages in specified communication rounds. We describe an optimal algorithm for this problem that requires the least number of communication rounds and that minimizes the time spent by any processor in sending and receiving messages.

关键词： Census computation census function combining algorithm message-passing system parallel computer

来源：评论

学校读者我要写书评

暂无评论

Set-constrained delivery broadcast: A communication abstraction for read/write implementable distributed objects

引用

THEORETICAL COMPUTER SCIENCE 2021年 886卷 49-68页

作者： Imbs, Damien Mostefaoui, Achour Perrin, Matthieu Raynal, Michel Aix Marseille Univ LIS F-13288 Marseille France CNRS F-13288 Marseille France Univ Toulon & Var F-13288 Marseille France Univ Nantes LS2N F-44322 Nantes France Univ Rennes IRISA INRIA CNRS F-35042 Rennes France Polytech Univ Dept Comp Hong Kong Peoples R China

This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message in', no process delivers first a set of messages including in' and later a set of message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data types), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Abstraction Asynchronous system Communication abstraction Communication pattern Conflict-free replicated data type Design simplicity Distributed task Linearizability message-passing system Process crash Read/write atomic register Sequential consistency Snapshot object

来源：评论

学校读者我要写书评

暂无评论

A priority-based distributed group mutual exclusion algorithm when group access is non-uniform

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2007年第7期67卷 797-815页

作者： Mittal, Neeraj Mohan, Prajwal K. Univ Texas Dept Comp Sci Richardson TX 75083 USA Intel Corp Digital Home Grp Hillsboro OR 97124 USA

In the group mutual exclusion problem, each critical section has a type or a group associated with it. Processes requesting critical sections belonging to the same group (that is, of the same type) may execute their critical sections concurrently. However, processes requesting critical sections belonging to different groups (that is, of different types) must execute their critical sections in a mutually exclusive manner. Most algorithms for solving the group mutual exclusion problem that have been proposed so far in the literature treat all groups equally. This is quite acceptable if a process, at the time of making a request for critical section, selects a group for the critical section uniformly. However, if some groups are more likely to be selected than others, then better performance can be achieved by treating different groups in a different manner. In this paper, we propose an efficient algorithm for solving the group mutual exclusion problem when group selection probabilities are nonuniformly distributed. Our algorithm has a message complexity of 2n - 1 per request for critical section, where n is the number of processes in the system. It has low synchronization delay of one message hop and low waiting time of two message hops. The maximum concurrency of our algorithm is n, which implies that if all processes have requested critical sections of the same type then all of them may execute their critical sections concurrently. Finally, the amortized message-size complexity of our algorithm is O(1). Our experimental results indicate that our algorithm outperforms the existing algorithms, whose complexity measures are comparable to that of ours, by as much as 50% in some cases. (C) 2007 Elsevier Inc. All rights reserved.

关键词： message-passing system resource management group mutual exclusion token-based algorithm non-uniform group selection priority-based scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：