This paper presents a new method for obtaining lower bounds on the slowdown of efficient emulations between network machines based on their communication bandwidth. The proofs measure the communication complexity of a message pattern by viewing its graph as a network machine and measuring the communication bandwidth β. This approach yields an intuitive lower bound on the time to route a communication pattern represented by multigraph C on a host machine H (with uniform load) as T ≥ Ω (β(C)/β(H)), and thus a lower bound on the slowdown of emulating guest machine G on host H as the ratio of their communication bandwidths.

Describes two parallel algorithms for ranking the pixels on a curve in O (log N) time using either an EREW or CREW PRAM model. The algorithms accomplish this with N processors for a square root N* square root N image. After applying such an algorithm to an image, it is possible to move the pixels from a curve into processors having consecutive addresses. This is important because one can subsequently apply many algorithms to the curve (such as piecewise linear approximation algorithms or point in polygon tests) using segmented scan operations (i.e. parallel prefix operations). Scan operations can be executed in logarithmic time on many interconnection networks, such as hypercube, tree, butterfly, and shuffle exchange machines as well as on the EREW PRAM. The algorithms were implemented on the hypercube structured Connection Machine, and various performance tests were conducted.>

One processor network that is especially attractive for parallel processing is the Butterfly network.A very closely related interconnection network is the Bidelta (or Omega) network.It is well known how to lay out these networks with minimal area, but these layouts use long wires.We show how to lay them out with optimal area and short wires.We also introduce the Mesh-Connected Cycles network, which has optimal area (in the sense of AT 2) for a broad range of running times when executing "ascend-descend" algorithms.The length of its longest wire is nearly optimal, and its layout area has very modest constants.

Analyzes the random delay experienced by a message traversing a buffered, multistage packet-switching banyan network. The authors find the generating function for the distribution of waiting time at the first stage of the network for a very general class of traffic, assuming messages have discrete sizes. For example, traffic can be uniform or nonuniform, messages can have different sizes, and messages can arrive in batches. For light-to-moderate loads, the authors conjecture that delays experienced at the various stages of the network are nearly the same and are nearly independent. This allows us to approximate the total delay distribution. Better approximations for the distribution of waiting times at later stages of the network are attained by assuming that in the limit a sort of spatial steady state is achieved. Extensive simulations confirm the formulas and conjectures.>

A new formalism is given for read-modify-write (RMW) synchronization operations. This formalism is used to extend the memory reference combining mechanism introduced in the NYU Ultracomputer, to arbitrary RMW operations. A formal correctness proof of this combining mechanism is given. General requirements for the practicality of combining are discussed. Combining is shown to be practical for many useful memory access operations. This includes memory updates of the form mem _ val := mem _ val op val , where op need not be associative, and a variety of synchronization primitives. The computation involved is shown to be closely related to parallel prefix evaluation.

A new formalism is given for read-modify-write (RMW) synchronization operations.This formalism is used to extend the memory reference combining mechanism, introduced in the NYU Ultracomputer, to arbitrary RMW operations.A formal correctness proof of this combining mechanism is given.General requirements for the practicality of combining are discussed.Combining is shown to be practical for many useful memory access operations.This includes memory updates of the form mere val :~ mere val op val, where op need not be associative, and a variety of synchronization primitives.The computation involved is shown to be closely related to parallel prefix evaluation. INTRODUCTIONShared memory provides convenient communication between processes in a tightly coupled multiprocessing system.Shared variables can be used for data sharing, information transfer between processes, and, in particular, for coordination and synchronization.Constructs such as the semaphore introduced by Dijkstra in [Di], and the many variants that followed, provide convenient solutions to many synchronization problems involving arbitrary number of processes.These constructs are supported in hardware by machine instructions that atomically execute a Read-Modify-Write cycle.Such instructions exist on most modern CPU's.An atomic Read-Modify-Write operation only requires that it be semantically atomic, although it is often processed atomically also.The "serial bottleneck" created by this atomic processing, while acceptable for small scale parallelism, can seriously impair the performance of a system with thousands of processors.

We present an updated report on the NYU Ultracomputer design emphasizing recent results on programming, operating systems, caching, demand paging, and I/O.The user's view of the Ultracomputer is presented along with the hardware and software implementation.Freedom from serial bottlenecks in both hardware and software allows the Ultracomputer to obtain performance that scales nearly linearly in the size of the machine for a broad spectrum of problems.

The prefix computation problem is to compute allninitial productsa1* . . . *a1,i=1, . . .,nof a set ofnelements, where * is an associative operation. An O(((logn) log(2n/p))XI(n/p)) time deterministic parallel algorithm usingp≤nprocessors is presented to solve the prefix computation problem, when the order of the elements is specified by a linked list. Forp≤O(n1-ε)(ε〉0 any constant), this algorithm achieves linear speedup. Such optimal speedup was previously achieved only by probabilistic algorithms. This study assumes the weakest PRAM model, where shared memory locations can only be exclusively read or written (the EREW model).

The feasibility of automatic restructuring of nonnumerical programs for parallel processing is studied through experiments using Parafrase, an automatic restructurer at the University of Illinois, Urbana-Champaign. Parallel processing speedup results due to automatic restructuring for several basic nonnumerical problems are presented. The loops encountered are classified at a low level. On the basis of the speedup results and the analyses of the loop types, the difficulty and the effectiveness of automatic restructuring are discussed. The experiments suggest that automatic restructuring can be a useful tool for exploiting parallelism in the sequential form of nonnumerical programs.

When using MIMD (multiple instruction, multiple data) parallel computers, one is often confronted with solving a task composed of many independent subtasks where it is necessary to synchronize the processors after all the subtasks have been completed. This paper studies how the subtasks should be allocated to the processors in order to minimize the expected time it takes to finish all the subtasks (sometimes called the makespan). We assume that the running times of the subtasks are independent, identically distributed, increasing failure rate random variables, and that assigning one or more subtasks to a processor entails some overhead, or communication time, that is independent of the number of subtasks allocated. Our analyses, which use ideas from renewal theory, reliability theory, order statistics, and the theory of large deviations, are valid for a wide class of distributions. We show that allocating an equal number of subtasks to each processor all at once has good efficiency. This appears as a consequence of a rather general theorem which shows how some consequences of the central limit theorem hold even when we cannot prove that the central limit theorem applies.

We present a theory that defines performance of packet-switching interconnection networks (delay and capacity) and their cost in terms of their geometry. This is used to prove that square banyan networks have optimal performance/cost ratio. These results, together with some known results on the complexity of routing in multistage networks, show that multistage shuffle-exchange networks are the unique networks with both optimal performance and simple routing. Finally, square delta networks are shown to have optimal area complexity.

For a wide class of problems, we obtain lower bounds for algorithms executed on certain parallel processors.These bounds show that for sufficiently large problems many known algorithms are optimal.The central result of the paper is the following sharper lower bound for permutation algorithms.Any permutation algorithm for N data items on a P processor parallel machine without shared memory requires time on the order of NlogxP/P, where K is the maximum number of processors directly connected to a single processor.In particular, a speedup on the order of P is impossible if K is bounded.

We present the design for the NYU Ultracomputer, a shared-memory MIMD parallel machine composed of thousands of autonomous processing elements. This machine uses an enhanced message switching network with the geometry of an Omega-network to approximate the ideal behavior of Schwartz's paracomputer model of computation and to implement efficiently the important fetch-and-add synchronization primitive. We outine the hardware that would be required to build a 4096 processor system using 1990's technology. We also discuss system software issues, and present analytic studies of the network performance. Finally, we include a sample of our effort to implement and simulate parallel variants of important scientific p̀rograms.

We study the number of comparison steps required for searching, merging, and sorting with P processors. We present a merging algorithm that is optimal up to a constant factor when merging two lists of equal size (independent of the number of processors); as a special case, with N processors it merges two lists, each of size N, in 1.893 lg lg N + 4 comparison steps. We use the merging algorithm to obtain a sorting algorithm that, in particular, sorts N values with N processors in 1.893 lg N lg lg N/lg lg lg N(plus lower order terms) comparison steps. The algorithms can be implemented on a shared memory machine that allows concurrent reads from the same location with constant overhead at each comparison step.

This paper studies the performance of unbuffered and buffered, packet-switching, multistage interconnection networks. We begin by reviewing the definition of banyan networks and introducing some generalizations of them. We then present an asymptotic analysis of the performance of unbuffered banyan networks, thereby solving a problem left open by Patel. We analyze the performance of the unbuffered generalized banyan networks, and compare networks with approximately equivalent hardware complexity. Finally, we analyze the performance of buffered banyan networks and again compare networks with approximately equivalent hardware complexity.

We present the design for the NYU Ultracomputer, a shared-memory MIMD parallel machine composed of thousands of autonomous processing elements. This machine uses an enhanced message switching network with the geometry of an Omega-network to approximate the ideal behavior of Schwartz's paracomputer model of computation and to implement efficiently the important fetch-and-add synchronization primitive. We outline the hardware that would be required to build a 4096 processor system using 1990's technology. We also discuss system software issues, and present analytic studies of the network performance. Finally, we include a sample of our effort to implement and simulate parallel variants of important scientific programs.