A network is proposed that preserves all of the properties of the hypercube, but has a diameter which is only about half of that of the hypercube. this network is self-routing, in the sense that there is a simple dist...
详细信息
ISBN:
(纸本)0818619538
A network is proposed that preserves all of the properties of the hypercube, but has a diameter which is only about half of that of the hypercube. this network is self-routing, in the sense that there is a simple distributed routing algorithm which guarantees optimal paths between any pair of vertices. this fact, together with other properties such as regularity, symmetry, high connectivity, and a simple recursive structure, implies that the multiply twisted cube is an alternative to the ordinary hypercube for massively parallel architectures. Single-input multiple-data stream algorithms were developed which utilize the new architecture. the multiply-twisted hypercube architecture can be used to profitably emulate the ordinary hypercube. Some of the basic properties of this network are discussed, the programming issues are emphasized, and it is shown that any hypercube algorithm can be mapped to run on the new architecture. In many cases this mapping results in a substantial reduction in the running time due to more efficient routing of data between processors.
the Camelot library extends the C programming language to provide a high-level programming interface to Camelot, a general-purpose distributed transaction system. the Camelot library is implemented as a collection of ...
详细信息
the Camelot library extends the C programming language to provide a high-level programming interface to Camelot, a general-purpose distributed transaction system. the Camelot library is implemented as a collection of C functions and macros. the interface presented by the library also provides a concise high-level model of the services offered by a general-purpose transaction system. A broad overview of the interface is given, and implementation experience is briefly summarized.
A language paradigm called shared dataspace is defined that causes computations to be performed using an anonymous, content-addressable communication medium acted upon by atomic transactions. To probe the essence of t...
详细信息
A language paradigm called shared dataspace is defined that causes computations to be performed using an anonymous, content-addressable communication medium acted upon by atomic transactions. To probe the essence of this paradigm, a relatively simple shared dataspace language called Swarm is defined. An overview is presented of the Swarm language. A formal operational model for the language is given and some of the programming implications and distinctive features of the model and language are discussed. Swarm programming strategies are examined using a series of related example programs.
Many algorithms for replicated data concurrency control are based on voting methods. Techniques are developed for optimizing the assignment of votes in an environment where intersite communications costs are nonunifor...
详细信息
ISBN:
(纸本)0818619538
Many algorithms for replicated data concurrency control are based on voting methods. Techniques are developed for optimizing the assignment of votes in an environment where intersite communications costs are nonuniform and individual site reliabilities vary. these techniques apply to all algorithms that are based on voting. Availability is considered as a realistic measure of reliability, and so is incorporated in an optimization model. the optimization model is based on minimizing communications costs subject to a given availability constraint. A semiexhaustive algorithm is described for solving this model. the algorithm utilizes a signature-based method for identifying equivalent vote combinations and an efficient technique for computing availability. It is compared to an equal vote assignment to estimate the extent of possible savings in communications costs.
A new parallel programming environment, Id World, is under development by MIT’s Laboratory of Computer Science. this approach to parallel processing is distinct in that it employs a dataflow architecture and a functi...
详细信息
Concert, a high-level-language approach to programming heterogeneous distributed systems, is described. the Concert model introduces a small set of language extensions into conventional procedural languages. these lan...
详细信息
Concert, a high-level-language approach to programming heterogeneous distributed systems, is described. the Concert model introduces a small set of language extensions into conventional procedural languages. these language extensions support a cooperative peer process model which addresses in the distributed environment the same issues addressed by language semantics in the conventional environment. the Concert implementation provides layered support for these language extensions, bridging a different source of heterogeneity at each layer. A prototype Concert system currently includes C programs running on OS/2 on multiple PS/2s communicating via calls with one another as well as with PL/I programs running on VM/370.
the design and implementation of a reliable version of the distributed bitonic sorting algorithm using the application-oriented fault tolerance paradigm on a commercial multicomputer is described. Sorting assertions i...
详细信息
the design and implementation of a reliable version of the distributed bitonic sorting algorithm using the application-oriented fault tolerance paradigm on a commercial multicomputer is described. Sorting assertions in general are discussed and the bitonic sort algorithm is introduced. Faulty behavior is discussed and a fault-tolerant parallel bitonic sort developed using this paradigm is presented. the error coverage and the response of the fault-tolerant algorithm to faulty behavior are presented. Both asymptotic complexity and the results of run-time experimental measurements on an Ncube multicomputer are given. the authors demonstrate that the application-oriented fault tolerance paradigm is applicable to problems of a noniterative nature.
A family of distributed algorithms for decentralized evaluation of associative and commutative functions is presented. It is shown that if N is the number of processes which cooperate to evaluate such a function, then...
详细信息
A family of distributed algorithms for decentralized evaluation of associative and commutative functions is presented. It is shown that if N is the number of processes which cooperate to evaluate such a function, then for each positive integer c ≥ 1 there is an algorithm in the family that carries out the computation in c rounds of message exchange and requires a total of cN(N1/c - 1) messages to be sent. Using c as a design parameter, this family of algorithms permits a tradeoff between the number of rounds of message exchange and the total number of messages passed among the processes. the class of functions considered underlies many decentralized protocols, such as decentralized extrema finding and distributed transaction commit.
An algorithm is presented that detects for termination of distributed computations by an auxiliary controlling agent. the algorithm assigns a weight W, 0 < W &le 1, to each active process and to each message in...
详细信息
An algorithm is presented that detects for termination of distributed computations by an auxiliary controlling agent. the algorithm assigns a weight W, 0 < W &le 1, to each active process and to each message in transit. the algorithm maintains that the sum of all the weights related to the computation is equal to one. the controlling agent terminates the algorithm if its weight equals one. A space-efficient scheme is proposed to encode the weights such that an active process can send a very large number of messages before reaching a weight equal to one. thus, in the proposed encoding scheme, each process and message needs only a small number of bits to encode the weight;the processes can be almost free from the delays of waiting for a supply of weights from the controlling agent.
the authors take efficient kernel-level support as a given, and study the performance implications of design alternatives one level up--in the stubs, which insulate the client and server from details about network com...
详细信息
the authors take efficient kernel-level support as a given, and study the performance implications of design alternatives one level up--in the stubs, which insulate the client and server from details about network communication. these alternatives represent a collection of approaches to achieving standard remote procedure call of semantics. Consideration is given to the performance implications of compiled vs. interpreted stubs, procedural vs. inline code for moving data to/from packet buffers, block copy vs. individual data item copy moving data to/from packet buffers, and the presence or absence of byte swapping.
暂无评论