ISSN:1063-7192    

DOI:10.1080/10637199608915540

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

We introduce a new paradigm For Ihc design of parallel algorithms called eventual determinism. In an eventualfy-determinizing algorithm, all processes execute identical programs from identical starting states. A program has two parts (also called modes) —probabilistic and deterministic. A process begins execution in the probabilistic mode and eventually (with probability one) switches to a deterministic mode. The decision to switch is taken independently by each process. This means that it is possible for different processes to be executing in different modes at the same time. It is possible that a process may change back to the probabilistic mode but it is required that eventually, each process should switch and stay in the deterministic mode. Thus determinacy pervades the system.

ISSN:1063-7192    

DOI:10.1080/10637199608915541

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

Interval orders are partial orders defined by having interval representations. It is well known that a transitively oriented digraphGis an interval order iff its (undirected) complement G¯ is chordal. We investigate parallel algorithms Tot the following scheduling problem: Given a system consisting of a setTofntasks (each requiring unit execution time) and an interval order ≺ overT, and given m identical parallel processors, construct an optimal (i.e., minimal length) schedule for (T, ≺).

ISSN:1063-7192    

DOI:10.1080/10637199608915542

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

This paper presents a framework of usingresource metricsto characterize the various models of parallel computation. Our framework reflects the approach of recent models to abstract architectural details into several generic parameters, which we call resource metrics. We examine the different resource metrics chosen by different parallel models, categorizing the models into four classes: the basic synchronous models, and extensions of the basic models which more accurately reflect practical machines by incorporating notions of asynchrony, communication cost, and memory hierarchy. We then present a new parallel computation model, the LogP-HMM model, as an illustration of design principles based on the framework of resource metrics. The LogP-HMM model extends an existing parameterized network model (LogP) with a sequential hierarchical memory model (HMM) characterizing each processor. The result captures both network communication costs and the effects of multileveled memory such as local cache and I/O. More generally, the LogP-HMM is representative of a class of models formed by combining a network model with any of several existing hierarchical memory models. Along these lines we introduce a variant of the LogP-HMM model, the LogP-UMH, which combines the LogP with the Universal Memory Hierarchy (UMH) model. We examine the potential utility of both our models in the design of several near optimal FFT and sorting algorithms. We also examine the potential of the LogP-UMH to more accurately reflect parallel machines by matching the model to the CM-5 and IBM SP2.

ISSN:1063-7192    

DOI:10.1080/10637199608915543

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

In this paper we present a new algorithm for thek-partitioning problem which achieves an improved solution uality compared to known heuristics. We apply the principle of so called “helpful sets”, which has shown to be very efficient for graph bisection, to the directk-partitioning problem. The principle is extended in several ways. We introduce a new abstraction technique which shrinks the graph during runtime in a dynamic way leading to shorter computation times and improved solutions qualities. The use of stochastic methods provides further improvements in terms of solution quality. Additionally we present a parallel implementation of the new heuristic. The parallel algorithm delivers the same solution quality as the sequential one while providing reasonable parallel efficiency on MIMD-systems of moderate size.

ISSN:1063-7192    

DOI:10.1080/10637199608915544

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor

摘要:

We show thatrpseudo-random bits can be obtained by concatenatingtblocks ofr/tpseudo-random bits, where the blocks are generated in parallel. This can be considered as a parallel version of [8]—recycling random bits by doing a random walk on an expander. The proof is based on the fact thattsimultaneous independent random walks on an expander graph is equivalent to a random walk on a much larger expander. In [8] generating the random walk requires arithmetic operation with long integers. In the parallel version the integers involved are much shorter, and different segments of the pseudo-random bits are generated independently in parallel. Optimal speedup is also achieved.

ISSN:1063-7192    

DOI:10.1080/10637199608915545

出版商:Taylor & Francis Group    

年代:1996

数据来源: Taylor