We formulate what might be the simplest train scheduling problem considered in the literature and show it to be NP-hard. We also give a log-factor randomised algorithm for it. In our problem we have a unidirectional train track with equidistant stations, each station initially having at most one train. In addition, there can be at most one train poised to enter each station. The trains must move to their destinations subject to the constraint that at every time instant there can be at most one train at each station and on the track between stations. The goal is to minimise the maximum delay of any train. Our problem can also be interpreted as a packet routing problem, and our work strengthens the hardness results from that literature.

Introductory programming courses often leave students unimpressed. We feel this is because teaching approaches (a) overemphasize the syntactic aspects of the programming language being taught instead of using programming to do interesting things, (b) do not respect the computational maturity/intellectual leanings of the students, and (c) are simply not fun enough. We have developed an approach which we believe addresses these issues in the context of teaching introductory programming to college students majoring in science and engineering.

We consider the problem of ranking an N element list on a P processor EREW PRAM. Recent work on this problem has shown the importance of grain size. While several optimal O(N/P+log P) time list ranking algorithms are known, Reid-Miller and Blelloch (1994) recently showed that these do not lead to good implementations in practice, because of the fine-grained nature of these algorithms. In Reid-Miller and Blelloch's experiments the best performance was obtained by an O(N/P+log/sup 2/ P) time coarse grained randomized algorithm devised by them. We build upon their idea and present a coarse-grained randomized algorithm that runs in time O(N/P+log P), and is thus also optimal. Our algorithm simplifies some of the ideas from [6, 7]-these simplifications might be of interest to implementers.

We study the most general communication paradigm on a multiprocessor, wherein each processor has a distinct message (of possibly distinct lengths) for each other processor. We study this paradigm, which we call chatting, on multiprocessors that do not allow messages once dispatched ever to be delayed on their routes. By insisting on oblivious routes for messages, we convert the communication problem to a pure scheduling problem. We introduce the notion of a virtual chatting schedule, and we show how efficient chatting schedules can often be produced from efficient virtual chatting schedules. We present a number of strategies for producing efficient virtual chatting schedules on a variety of network topologies.

The finite element method is a general and powerful technique for solving partial differential equations. The computationally intensive step of this technique is the solution of a linear system of equations. Very large and very sparse system matrices result from large finite-element applications. The sparsity must be exploited for efficient use of memory and computational components in executing the solution step. In this paper we propose a scheme, called SPAR, for efficiently storing and performing computations on sparse matrices. SPAR consists of an alternate method of representing sparse matrices and an architecture that efficiently executes computations on the proposed data structure. The SPAR architecture has not been built, but we have constructed a register-transfer level simulator and executed the sparse matrix computations used with some large finite element applications. The simulation results demonstrate a 95% utilization of the floating-point units for some 3D applications. SPAR achieves high utilization of memory, memory bandwidth, and floating-point units when executing sparse matrix computations.>

We present nearly tight bounds for wormhole muting on Butterfly networks which indicate it is fundamentally different from store-and-forward packet routing. For instance, consider the problem of routing N log N (randomly generated) log N length messages from the inputs to the outputs of an N input Butterfly. We show that with high probability that this must take time at least /spl Omega/(log/sup 3/N/(log log N)/sup 2/). The best lower bound known earlier was /spl Omega/(log/sup 2/ N), which is simply the flit congestion an each link. Thus our lower bound shows that wormhole routing (unlike store-and-forward-routing) is very ineffective in utilizing communication links. We also give a routing algorithm which nearly matches our lower bound. That is, we show that with high probability the time is O(log/sup 3/ N log log N), which improves upon, the previous best bound of O(log/sup 4/ N). Our method also extends to other networks such as the two-dimensional mesh, where it is nearly optimal. Finally, we consider the problem of offline wormhole routing, where we give optimal algorithms for trees and multidimensional meshes.>

We present a family of exceedingly simple sorting algorithms called Snakesort. Snakesort is a natural generalization of the simple barallel bubble sort algorithm, also known as odd-even transposition sort. Instances of Snakesort can be implemented on any interconnection network so long as it has a Hamiltonian Path.

A central problem in building large scale parallel machines is the design of the interconnection network.Interconnection network design is largely constrained by packaging technology.We start with a generic set of packaging restrictions and evaluate different network organizations under a random trafic model.We identify families of networks (product of complete graphs, high degree deBruijn graphs) that we believe will be useful for multilevel packaging.Our results indicate that customizing the network topology to the packaging constraints is useful.Some of the general pm"nciples that arise out of this study are: 1) Making the networks denser at the lower levels of the packaging hierarchy has a significant positive impact on global communication performance, 2) It is better to organize a fixed amount of communication bandwidth as a smaller number of high bandwidth channels, 3) Providing the processors with the ability to tolerate latencies (by using rnuh.ithreading) is very useful in improving performance.

The operations of scattering and gathering in a network of processors involve one processor of the network (P/sub 0/) communicating with all other processors. In scattering, P/sub 0/ sends distinct messages to P/sub 0/. The authors consider networks that are trees of processors. Algorithms for scattering messages from and gathering messages to the processor that resides at the root of the tree are presented. The algorithms are quite general, in that the messages transmitted can differ arbitrarily in length; quite strong, in that they send messages along noncolliding paths, and hence do not require any buffering or queueing mechanisms in the processors; and quite efficient in that algorithms for scattering in general trees are optimal, the algorithm for gathering in a path is optimal and the algorithms for gathering in general trees are nearly optimal. The algorithms can easily be converted using spanning trees to efficient algorithms for scattering and gathering in networks of arbitrary topologies.>

Shared memory multiprocessors are considered among the easiest parallel computers to program. However building shared memory machines with thousands of processors has proved difficult because of the inevitably long memory latencies. Much previous research has focused on cache coherency techniques, but it remains unclear if caches can obtain sufficiently high hit rates. In this paper we present improved multithreading techniques that can easily tolerate latencies of hundreds of cycles, and yet only require a small number of threads per processor. High performance is achieved by introducing an explicit context switch instruction that can be used by a simple optimizing compiler to group together several shared accesses. This grouping of shared accesses dramatically reduces the frequency of context switches compared to simpler multithreading models. The combination of our techniques achieves efficiencies of 80% or higher on a broad set of applications.

We present randomized data structures for maintaining a dynamic ordered set on sparse networks of processors.For any constant D, on a D-dimensional mesh with side length L and total number of processors N = LD, we can process any N least-upper-bound (also called find-rein, successor) queries on a set with M elements in time O(L + log MN) with high probability.We can also process any N insert queries in amortized time O(L + log MN) with high probability, per group of N queries.For Butterfly networks, we only have fast randomized algorithms for processing least-upperbound (lub) queries, and these algorithms require parallel slackness.In particular, we show how to process any group of N log N lub queries using an N processor butterfly network in time O((log N)(log MN)).All of these algorithms only use O(li4/N) storage per processor and are optimal to within constant factors.Finally, we note a simple lower bound on the performance of any deterministic algorithm that uses at most O(M/N) storage per processor, which indicates the need for randomized algorithms.and insert(%), which inserts z into the set.Our data structures allow highly concurrent access, indeed all N

This paper presents simple randomized algorithms for dynamically embedding M-node binary trees in either a butterfly or a hypercube network of N processors. These algorithms are dynamic in the sense that the tree to be embedded may start as one node and grow by dynamically spawning children. The nodes are incrementally embedded as they are spawned. Thus, the algorithm is especially suited for maintaining dynamic tree structures like those in divide-and-conquer and branch-and-bound algorithms. In the embeddings, the paper seeks to optimize the load on the processors of the network, the dilation of the tree edges, and the congestion on the network edges, in order to satisfy the demands of load balancing, process locality, and communication efficiency. The paper begins by presenting a simple level-by-level scheme for dynamically embedding trees in a butterfly network, and by successive modifications. The following results are obtained: 1. An embedding algorithm for the hypercube that achieves dilation 1 and, with high probability, load $O((M /N) + \log N)$. 2. An embedding algorithm for the butterfly that achieves dilation 2 and, with high probability, load $O((M/ N) + \log N)$. 3. An embedding algorithm for the hypercube that achieves dilation $O(1)$ and, with high probability, load $O((M/N) + 1)$ and congestion $O((M/ N) + 1)$. The third embedding simultaneously optimizes load and dilation to within constant factors, optimizing congestion as well when $M = O(N)$. The first two embeddings are also optimal to within constant factors when the tree to be embedded is large (i.e., $M = \Omega (N\log N)$. In addition, this paper proves a lower bound of $\Omega (\sqrt {\log N} )$ dilation for deterministic embedding algorithms that achieve load $O((M/ N) + 1)$, which implies that any embedding algorithm that simultaneously optimizes load and dilation must be randomized.

Article Three-dimensional finite-element analyses: implications for computer architectures Share on Authors: Valerie E. Taylor Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CAView Profile , Abhiram Ranade Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CAView Profile , David G. Messerschmitt Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CAView Profile Authors Info & Claims Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on SupercomputingAugust 1991 Pages 786–795https://doi.org/10.1145/125826.126188Online:01 August 1991Publication History 0citation278DownloadsMetricsTotal Citations0Total Downloads278Last 12 Months0Last 6 weeks0 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 SiteGet Access

Article Free Access Share on Optimal speedup for backtrack search on a butterfly network Author: Abhiram Ranade Computer Science Division, University of California, Berkeley, CA Computer Science Division, University of California, Berkeley, CAView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 40–48https://doi.org/10.1145/113379.113383Published:01 June 1991Publication History 43citation229DownloadsMetricsTotal Citations43Total Downloads229Last 12 Months23Last 6 weeks5 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

We present a simple algorithm for emulating an N-processor CROW PRAM on an N-ode butterfly. Each step of the PRAM is emulated in time O(log N) with high probability, using FIFO queues of size O(1) at each node. The only use of randomization is in selecting a hash function to distribute the shared address space of the PRAM onto the nodes of the butterfly. The routing itself is both deterministic and oblivious, and messages are combined without the use of associative memories or explicit sorting. As a corollary we improve the result of Pippenger by routing permutations with bounded queues in logarithmic time, without the possibility of deadlock. Besides being optimal, our algorithm has the advantage of extreme simplicity and is readily suited for use in practice.

Article Dynamic tree embeddings in butterflies and hypercubes Share on Authors: T. Leighton M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MAView Profile , M. Newman M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MAView Profile , A. G. Ranade Department of EECS, University of California, Berkeley, CA Department of EECS, University of California, Berkeley, CAView Profile , E. Schwabe M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MAView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 224–234https://doi.org/10.1145/72935.72959Online:01 March 1989Publication History 23citation365DownloadsMetricsTotal Citations23Total Downloads365Last 12 Months1Last 6 weeks0 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 SiteGet Access

We present a simple algorithm for emulating an N processor CRCW PRAM on an N node butterfly. Each step of the PRAM is emulated in time O(log N) with high probability, using FIFO queues of size O(1) at each node. The only use of randomization is in selecting a hash function to distribute the shared address space of the PRAM onto the nodes of the butterfly. The routing itself is both deterministic and oblivious, and messages are combined without the use of associative memories or explicit sorting. As a corollary we improve the result of Pippenger [8] by routing permutations with bounded queues in logarithmic time, without the possibility of deadlock. Besides being optimal, our algorithm has the advantage of extreme simplicity and is readily suited for use in practice.