This paper presents Simultaneous Speculative Threading (SST), which is a technique for creating high-performance area- and power-efficient cores for chip multiprocessors. SST hardware dynamically extracts two threads of execution from a single sequential program (one consisting of a load miss and its dependents, and the other consisting of the instructions that are independent of the load miss) and executes them in parallel. SST uses an efficient checkpointing mechanism to eliminate the need for complex and power-inefficient structures such as register renaming logic, reorder buffers, memory disambiguation buffers, and large issue windows. Simulations of certain SST implementations show 18% better per-thread performance on commercial benchmarks than larger and higher-powered out-of-order cores. Sun Microsystems' ROCK processor, which is the first processor to use SST cores, has been implemented and is scheduled to be commercially available in 2009.

Silicon technology trends of 65nm technology and architectural trends of the next generation of processors, chip-sets and systems are driving new design paradigms and shifts in the approaches towards robust system design. This paper addresses the convergence of these trends in designing the next generation of highly reliable systems at Sun Microsystems.

This paper presents constructions for fault-tolerant, two-dimensional mesh architectures. The constructions are designed to tolerate k faults while maintaining a healthy n by n mesh as a subgraph. They utilize several novel techniques for obtaining trade-offs between the number of spare nodes and the degree of the fault-tolerant network. We consider both worst-case and random fault distributions. In terms of worst-case faults, we give a construction that has constant degree and O(k3) spare nodes. This is the first construction known in which the degree is constant and the number of spare nodes is independent of n. In terms of random faults, we present several new degree-6 and degree-8 constructions and show (both analytically and through simulations) that these constructions can tolerate large numbers of randomly placed faults.

In this paper we present routing algorithms that are tmiversal in the sense that they route messages along arbitrary (simple) paths in arbitrary networks.The algorithms are analyzed in terms of the number of messages being routed, the maximum number of messages that must cross any edge in the network (edge congestion), the maximum number of edges that a message must cross (dilation), the bufler size, and the bandwidth of the links.We present two main results, both of which have applications to ttnivexsal storeand-forwwd routing and universal wormhole routing.Our results yield significant performance improvements over all previously known universal routing algorithms for a wide range of parameters, and they even improve many time bounds for standard networks.In addition, we present adaptations of our main results for routing along shortest paths in arbitrary networks, and for routing in leveled networks, node-symmetric networks, edge-symmetric networks, expanders, butterflies, and meshes.

This paper considers the problem of creating message-passing protocols for parallel computers. It is assumed that the processors are connected by a network that provides guaranteed delivery of every message, provided that each message delivered by the network is removed by the receiving processor unconditionally and in finite time. Two models of message passing are considered, namely, a selective model in which the receiver specifies the source of the message and a nonselective model in which the receiver accepts messages from all sources. We consider only space-efficient protocols in which each processor has storage for a constant number of messages and message headers. We present three main results. First, we give a protocol for the selective model that performs a constant amount of communication per send or receive posted by the application. Second, we prove that no such efficient protocol exists for the nonselective model. Third, we present a protocol for the nonselective model that performs a logarithmic amount of communication per send or receive posted by the application.

This paper examines the amount of communication that is required for performing mutual exclusion.It is assumed that n processors communicate via accesses to a shared memory that is physically distributed among the processors.We consider the possibility of creating a scalable mutual exclusion protocol that requires only a constant amount of communication per access to a critical section.We present two main results, First, we show that there does not exist a scalable mutual exclusion protocol that uses only read and write operations.This result solves an open problem posed by Yang and Anderson, Second, we prove

This paper presents a new approach to tolerating edge faults and node faults in (CCC) networks of Cube-Connected Cycles in a worst-case scenario. Our constructions of fault-tolerant CCC networks are obtained by adding extra edges to the CCC. The main objective is to reduce the cost of the fault-tolerant network by minimizing the degree of the network. Specifically, we have two main results. (i) We have created a fault tolerant CCC that can tolerate any single fault, either a node fault or an edge fault. When the dimension of the CCC is odd, the degree of the fault tolerant graph is 4. In the even case, there is a single node per cycle that is of degree 5 and the rest are of degree 4. (ii) We have created a fault-tolerant CCC, where every node has degree y + 2, which can tolerate any 2y − 1 cube-edge faults. Our constructions are extremely efficient for the case of edge faults-they result in healthy CCC networks that utilize all of the processors.

Hypercubes, meshes and tori are well known interconnection networks for parallel computers. The sets of edges in those graphs can be partitioned to dimensions. It is well known that the hypercube can be extended by adding a wildcard dimension resulting in a folded hypercube that has better fault-tolerant and communication capabilities. First we prove that the folded hypercube is optimal in the sense that only a single wildcard dimension ran be added to the hypercube. We then investigate the idea of adding wildcard dimensions to d-dimensional meshes and tori. Using techniques from error correcting codes we construct d-dimensional meshes and tori with wildcard dimensions. Finally, we show how these constructions can be used to tolerate edge and node faults in mesh and torus networks.>

A collective communication library for parallel computers includes frequently used operations such as broadcast, reduce, scatter, gather, concatenate, synchronize, and shift. Such a library provides users with a convenient programming interface, efficient communication operations, and the advantage of portability. A library of this nature, the Collective Communication Library (CCL), intended for the line of scalable parallel computer products by IBM, has been designed. CCL is part of the parallel application programming interface of the recently announced IBM 9076 Scalable POWERparallel System 1 (SP1). In this paper, we examine several issues related to the functionality, correctness, and performance of a portable collective communication library while focusing on three novel aspects in the design and implementation of CCL: 1) the introduction of process groups, 2) the definition of semantics that ensures correctness, and 3) the design of new and tunable algorithms based on a realistic point-to-point communication model.>

A fundamental issue in the use of message-passing systems is the creation of repeatable and portable programs. Repeatable program behavior is critical for debugging message-passing programs, while portability is essential for efficient software development. This paper makes two main contributions. First, it defines a set of program executions (called safe executions) that are guaranteed to be repeatable and portable. Safe program executions are defined for applications that utilize both blocking and nonblocking send and receive primitives, synchronous and asynchronous sends, and receives that select on the basis of source and/or tag values. To the best of our knowledge, this is the first time that conditions for repeatable and portable executions have been created for such rich message-passing models. Second, this paper gives precise characterizations of safe executions. The safety of an execution is shown to depend on the message-ordering properties of the underlying communication sys...

This paper studies the problem of deadlock-free packet routing in parallel and distributed architectures. Three main results are presented. First, it is shown that the standard technique of ordering the buffers so that every packet always has the possibility of moving to a higher-ordered buffer is not necessary for deadlock freedom. Second, it is shown that every deadlock-free, adaptive packet routing algorithm can be restricted, by limiting the adaptivity available, to obtain an oblivious algorithm which is also deadlock-free. Third, it is shown that any packet routing algorithm for a cycle or torus network which is free of deadlock and which uses only minimal length paths must require at least three buffers in some node. This matches the known upper bound of three buffers per node for deadlock-free, minimal packet routing on cycle and torus networks.

We consider the problem of embedding a cube-connected cycles graph (CCC) into a hypercube with edge faults. Our main result is an algorithm that, given a list of faulty edges, computes an embedding of the CCC that spans all of the nodes and avoids all of the faulty edges. The algorithm has optimal running time and tolerates the maximum number of faults (in a worst-case setting). Because ascend-descend algorithms can be implemented efficiently on a CCC, this embedding enables the implementation of ascend-descend algorithms, such as bitonic sort, on hypercubes with edge faults. We also present a number of related results, including an algorithm for embedding a CCC into a hypercube with edge and node faults and an algorithm for embedding a spanning torus into a hypercube with edge faults.>

We present two new packet routing algorithms for parallel computers with torus interconnection networks of arbitrary size and dimension. Both algorithms use only minimal length paths, are fully adaptive in the sense that all minimal length paths may be used to avoid congestion, and are free of deadlock, livelock and starvation. Algorithm 1 requires only three central queues per routing node. It is the first known minimal length packet routing algorithm for torus networks which requires a constant number of queues per node, regardless of the size and dimension of the torus. In fact, the requirement of three queues per node is optimal, as no such algorithm is possible when all nodes have two or fewer queues. Algorithm 2 requires only that each node have two input buffers per edge. It is the first known minimal-fully-adaptive packet routing algorithm for torus networks which does not require central queues and which does not require any node to have more than two input or two output buffers per edge. Both algorithms are simple and appear to be well-suited to VLSI implementation. They can be used with either store-and-forward or virtual cut-through routing.>

This paper addresses the problem of creating a fault-tolerant interconnection network for a parallel computer. Three topologies, namely, the base-2 de Bruijn graph, the base-m de Bruijn graph, and the shuffle-exchange, are studied. For each topology an N+k node fault-tolerant graph is defined. These fault-tolerant graphs have the property that given any set of k node faults, the remaining N nodes contain the desired topology as a subgraph. All of the constructions given are the best known in terms of the degree of the fault-tolerant graph. We also investigate the use of buses to reduce the degrees of the fault-tolerant graphs still further.>

This paper studies the behavior of scientific applications running on distributed memory parallel computers. Our goal is to quantify the floating point, memory, I/O and communication requirements of highly parallel scientific applications that perform explicit communication. In addition to quantifying these requirements for fixed problem sizes and numbers of processors, we develop analytical models for the effects of changing the problem size and the degree of parallelism for several of the applications. We use the results to evaluate the trade-offs in the design of multicomputer architectures.

This paper presents constructions for fault-tolerant two-dimensional mesh architectures.The constructions are designed to tolerate k faults while maintaining a healthy n by n mesh as a subgraph.They utilize several novel techniques for obtaining trade-offs between the number of spare nodes and the degree of the fault-tolerant network.We consider both worst-case and random fault distributions.In terms of worst-cme faults, we give a construction that haa constant degree and 0(k3 ) spares.This is the first construction known in which the degree is constant and the number of spares is independent of n.In terms of random faults, we present several new degree-6 and degree-8 constructions and show (both analytically and through simulations)that they can tolerate large numbers of randomly placed faults.

Article Free Access Share on Bounds on the efficiency of message-passing protocols for parallel computers Authors: Robert Cypher IBM Almaden Research Center, San Jose, CA IBM Almaden Research Center, San Jose, CAView Profile , Smaragda Konstantinidou IBM Almaden Research Center, San Jose, CA IBM Almaden Research Center, San Jose, CAView Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 173–181https://doi.org/10.1145/165231.165253Published:01 August 1993Publication History 3citation202DownloadsMetricsTotal Citations3Total Downloads202Last 12 Months4Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Shellsort is a sorting algorithm that is based on a set of parameters called increments. Shellsort has been used both as a sequential sorting algorithm and as a sorting network. The central result of this paper is that all Shellsort sorting networks based on monotonically decreasing increments require $\Omega (N\log ^2 {N / {\log \log N}})$ comparators. Previously, only the trivial $\Omega (N\log N)$ bound was known for this class of networks. The lower bound obtained in this paper nearly matches the upper bound of $O(N\log ^2 N)$ that was proven by Pratt.

This paper presents a formal model of the pin requirements of a parallel computer. This model is then used to obtain bounds on the pin requirements of different parallel machines and on the tradeoffs between pins and time. Specifically, two new bounds are established on the relationship between pin requirements and the time needed to sort or permute data. This paper also gives new lower bounds on the pin requirements of mesh-connected, cube-connected-cycles, shuffle-exchange, and Ajtai–Komlós–Szemerédi (AKS) computers, and it gives new upper bounds on the pin requirements of shuffle-exchange and AKS computers. All of these bounds are tight to within a constant factor. Finally, the bounds on pin requirements are used to prove a tight lower bound on the time required to implement the AKS sorting algorithm on a shuffle-exchange or cube-connected-cycles computer.

This paper presents several techniques for tolerating faults in d-dimensional mesh and hypercube architectures. The approach consists of adding spare processors and communication links so that the resulting architecture will contain a fault-free mesh or hypercube in the presence of faults. The authors optimize the cost of the fault-tolerant architecture by adding exactly k spare processors (while tolerating up to k processor and/or link faults) and minimizing the maximum number of links per processor. For example, when the desired architecture is a d-dimensional mesh and k=1, they present a fault-tolerant architecture that has the same maximum degree as the desired architecture (namely, 2d) and has only one spare processor. They also present efficient layouts for fault-tolerant two- and three-dimensional meshes, and show how multiplexers and buses can be used to reduce the degree of fault-tolerant architectures. Finally, they give constructions for fault-tolerant tori, eight-connected meshes, and hexagonal meshes.>

In the state-parallel implementation of the Viterbi algorithm, one add-compare-select (ACS) unit is devoted to each state in the treillis. A systematic approach to partitioning, scheduling, and mapping N trellis states to P ACSs, where N>P, is presented here. The area saving of this architecture comes from the reduced number of ACSs and interconnection wires. The design of the ACS, path metric storage, and routing network is discussed in detail. The proposed architecture creates internal parallelism due to the ACS sharing, which can be exploited to increase the throughput rate by pipelining. Consequently, the architecture offers a favorable (smaller) area-time product, compared to the state-parallel implementation.>

In part I the theoretical foundations of a new class of area-efficient architectures for the Viterbi algorithm were established. Area-efficient architectures for practical codes are presented here to illustrate the design procedures and demonstrate the favourable area-time tradeoff results. Three examples from convolutional codes, matched-spectral-null (MSN) trellis codes, and Ungerboeck codes are presented. The application of the area-efficient techniques to codes with a very large number of states, codes with time-varying trellises, and a programmable Viterbi decoder is discussed.>

Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still emulate G without any performance degradation. They show that for a wide range of values of n, k and d, for any graph on n nodes with maximum degree d there is a k-fault tolerant graph with maximum degree O(kd). They provide lower bounds as well: there are graphs G with maximum degree d such that any k-fault tolerant version of them has maximum degree at least Ω(d√k)

This paper studies the problem of deadlock-free packet routing in parallel and distributed architectures. We present three main results. First, we show that the standard technique of ordering the queues so that every packet always has the possibility of moving to a higher ordered queue is not necessary for deadlock-freedom. Second, we show that every deadlock-free, adaptive packet routing algorithm can be restricted, by limiting the adaptivity available, to obtain an oblivious algorithm which is also deadlock-free. Third, we show that any packet routing algorithm for a cycle or torus network which is free of deadlock and which uses only minimal length paths must require at least three queues in some node. This matches the known upper bound of three queues per node for deadlock-free, minimal packet routing on cycle and torus networks.

The authors examine the issue of running algorithms on a hypercube which has both node and edge faults, and they assume a worst-case distribution of the faults. It is proven that for any constant c, an n-dimensional hypercube (n-cube) with n/sup c/ faulty components contains a fault-tree subgraph that can implement a large class of hypercube algorithms with only a constant factor slowdown. In addition, the approach yields practical implementations for small numbers of faults. For example, it is shown that any regular algorithm can be implemented on an n-cube that has at most n-1 faults with slowdowns of at most two for computation and at most four for communication. This is the first result showing that an n-cube can tolerate more than O(n) arbitrarily placed faults with a constant factor slowdown.>

Article Free Access Share on Running algorithms efficiently on faulty hypercubes Authors: J. Bruck IBM Almaden Research Center, Dept. K54/802, 650 Harry Road, San Jose, CA IBM Almaden Research Center, Dept. K54/802, 650 Harry Road, San Jose, CAView Profile , R. Cypher IBM Almaden Research Center, Dept. K54/802, 650 Harry Road, San Jose, CA IBM Almaden Research Center, Dept. K54/802, 650 Harry Road, San Jose, CAView Profile , D. Soroker IBM Almaden Research Center, Dept. K54/802, 650 Harry Road, San Jose, CA IBM Almaden Research Center, Dept. K54/802, 650 Harry Road, San Jose, CAView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 37–44https://doi.org/10.1145/97444.97455Published:01 May 1990Publication History 22citation208DownloadsMetricsTotal Citations22Total Downloads208Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper presents a deterministic sorting algorithm, called Sharesort, that sorts n records on an n processor hypercube, shuffle-exchange or cube-connected cycles in O(log n(loglog n) 2) time in the worst case.The algorithm requires only a constant amount of storage at each processor.The fastest previous deterministic algorithm for this problem was bitonic sort [3], which runs in O(log 2 n) time.

This paper presents algorithms for implementing an important image processing operation, the Hough transform, on a mesh connected computer (MCC). The MCC consists of an $N \times N$ array of processors, each of which holds a single pixel of the image. The MCC operates in a Single Instruction Stream, Multiple Data Stream (SIMD) mode, which is in agreement with the hardware constraints found in existing meshes. Five algorithms for computing the Hough transform are presented. These algorithms use a number of different techniques, and they have varying time complexities and architectural requirements. The most notable algorithm presented computes any P angles of the Hough transform in $O(N + P)$ time and uses only a constant amount of memory per processor. Because the Hough transform is a particular case of the discrete Radon transform, all of the algorithms will be presented for computing the Radon transform of gray-level images.

Two parallel algorithms are presented for the problem of labeling the connected components of a binary image. The machine model is an SIMD two-dimensional mesh-connected computer consisting of an N*N array of processing elements, each containing a single pixel of an N*N image. Both new algorithms use a local shrinking operation defined by S. Levialdi (1972) and have time complexities of O(N log N) bit operations, making them the fastest local algorithms for the problem. Compared to other approaches with similar or better asymptotic time complexities, this local approach greatly simplifies the algorithms and reduces the constants of proportionality by nearly two orders of magnitude, making them the first practical algorithms for the problem. The two algorithms differ in the amount of memory required per processing element; the first uses O(N) bits, while the second uses a novel compression scheme to reduce the requirement to O(log N) bits.>

The central result of this paper is that all Shellsort sorting networks based on monotonically decreasing increments require ~t(N log 2 N/log log N) comparators.This result is significant because previously only the trivial fl(N log N) bound was known for this class of networks.Thus this paper provides the first proof that such networks cannot be of optimal size.The lower bound obtained in this paper nearly matches the upper bound of O(N log 2 N) that was proven by Pratt.

An important midlevel task for computer vision is addressed. The problem consists of labeling connected components in N/sup 1/2/*N/sup 2/2/ binary images. This task can be solved with parallel computers by using a simple and novel algorithm. The parallel computing model used is a synchronous fine-grained shared-memory model where only one processor can read from or write to the same memory location at a given time. This model is known as the exclusive-read exclusive-write parallel RAM (EREW PRAM). Using this model, the algorithm presented has O(log N) complexity. The algorithm can run on parallel machines other than the EREW PRAM. In particular, it offers an optimal image component labeling algorithm for mesh-connected computers.>

The complexity of efficiently programming massively parallel machines is illustrated by presenting a number of algorithms. These algorithms deal with computational geometry, data histogramming, list manipulation, and other problems or operations that arise in computer vision tasks. All of the algorithms presented use a divide-and-conquer strategy, and they all use routines that solve a problem of size M using a machine size N, where M>