With severe challenges facing computer technology scaling, parallel hardware accelerators have become increasingly attractive solutions to continued performance scaling. However, performance scaling is limited for irregular, input-dependent workloads. Often, static analysis is infeasible and overheads can outweigh benefits, resulting sometimes in weaker performance than a serial counterpart.

Deep neural networks are powerful machines for visual pattern recognition, but reasoning tasks that are easy for humans may still be difficult for neural models. Humans possess the ability to extrapolate reasoning strategies learned on simple problems to solve harder examples, often by thinking for longer. For example, a person who has learned to solve small mazes can easily extend the very same search techniques to solve much larger mazes by spending more time. In computers, this behavior is often achieved through the use of algorithms, which scale to arbitrarily hard problem instances at the cost of more computation. In contrast, the sequential computing budget of feed-forward neural networks is limited by their depth, and networks trained on simple problems have no way of extending their reasoning to accommodate harder problems. In this work, we show that recurrent networks trained to solve simple problems with few recurrent steps can indeed solve much more complex problems simply by performing additional recurrences during inference. We demonstrate this algorithmic behavior of recurrent networks on prefix sum computation, mazes, and chess. In all three domains, networks trained on simple problem instances are able to extend their reasoning abilities at test time simply by "thinking for longer."

Parallel machines have become more widely used. Unfortunately parallel programming technologies have advanced at a much slower pace except for regular programs. For irregular programs, this advancement is inhibited by high synchronization costs, non-loop parallelism, non-array data structures, recursively expressed parallelism and parallelism that is too fine-grained to be exploitable. We present ICE, a new parallel programming language that is easy-to-program, since: (i) ICE is a synchronous, lock-step language so there is no need for programmer-specified synchronization; (ii) for a PRAM algorithm its ICE program amounts to directly transcribing it; and (iii) the PRAM algorithmic theory offers unique wealth of parallel algorithms and techniques. We propose ICE to be a part of an ecosystem consisting of the XMT architecture, the PRAM algorithmic model, and ICE itself, that together deliver on the twin goal of easy programming and efficient parallelization of irregular programs. The XMT architecture, developed at UMD, can exploit fine-grained parallelism in irregular programs. We have built the ICE compiler which translates the ICE language into the multithreaded XMTC language; the significance of this is that multi-threading is a feature shared by practically all current scalable parallel programming languages thus providing a method to compile ICE code. As one indication of ease of programming, we observed a reduction in code size in 11 out of 16 benchmarks as compared to hand-optimized XMTC. For these programs, the average reduction in number of lines of code was 35.5 percent. The remaining 5 benchmarks had almost the same code size for both ICE and hand-optimized XMTC. Our main result is perhaps surprising: The run-time was comparable to XMTC with a 0.53 percent average gain for ICE across all benchmarks.

Large performance growth for processors requires exploitation of hardware parallelism, which, itself, requires parallelism in software. In spite of massive efforts, automatic parallelization of serial programs has had limited success mostly for regular programs with affine accesses, but not for many applications including irregular ones. It appears that the bare minimum that the programmer needs to spell out is which operations can be executed in parallel. However, parallel programming today requires so much more. The programmer is expected to partition a task into subtasks (often threads) so as to meet multiple constraints and objectives, involving data and computation partitioning, locality, synchronization, race conditions, limiting and hiding communication latencies. It is no wonder that this makes parallel programming hard, drastically reducing programmer's productivity and performance gains hence reducing adoption by programmers and their employers.

Lazy scheduling is a runtime scheduler for task-parallel codes that effectively coarsens parallelism on load conditions in order to significantly reduce its overheads compared to existing approaches, thus enabling the efficient execution of more fine-grained tasks. Unlike other adaptive dynamic schedulers, lazy scheduling does not maintain any additional state to infer system load and does not make irrevocable serialization decisions. These two features allow it to scale well and to provide excellent load balancing in practice but at a much lower overhead cost compared to work stealing, the golden standard of dynamic schedulers. We evaluate three variants of lazy scheduling on a set of benchmarks on three different platforms and find it to substantially outperform popular work stealing implementations on fine-grained codes. Furthermore, we show that the vast performance gap between manually coarsened and fully parallel code is greatly reduced by lazy scheduling, and that, with minimal static coarsening, lazy scheduling delivers performance very close to that of fully tuned code. The tedious manual coarsening required by the best existing work stealing schedulers and its damaging effect on performance portability have kept novice and general-purpose programmers from parallelizing their codes. Lazy scheduling offers the foundation for a declarative parallel programming methodology that should attract those programmers by minimizing the need for manual coarsening and by greatly enhancing the performance portability of parallel code.

We present novel work-optimal PRAM algorithms for Burrows-Wheeler (BW) compression and decompression of strings over a constant alphabet. For a string of length n, the depth of the compression algorithm is O(log2 n), and the depth of the corresponding decompression algorithm is O(log n). These appear to be the first polylogarithmic-time work-optimal parallel algorithms for any standard lossless compression scheme.

We present a parallel solution to the problem of determining the triconnected components of an undirected graph. We obtain significant speedups over the only published optimal (linear-time) serial implementation of a triconnected components algorithm running on a modern CPU. This is accomplished on the PRAM-inspired XMT many-core architecture. To our knowledge, no other parallel implementation of a triconnected components algorithm has been published for any platform.

Summary form only given. Today, almost all desktop and laptop computers are shared-memory multicores, but the code they run is over whelmingly serial. High level language extensions and libraries (e.g., OpenMP, Cilk++, TBB) make it much easier for programmers to write parallel code than previous approaches (e.g., MPI), in large part thanks to the efficient work-stealing scheduler that allows the programmer to expose more parallelism than the actual hardware parallelism. But when the parallel tasks are too short or too many, the scheduling overheads become significant and hurt performance. Because this happens frequently (e.g, data-parallelism, PRAM algorithms), programmers need to manually coarsen tasks for performance by combining many of them into longer tasks.

Many-cores, processors with 100s of cores, are becoming increasingly popular in general-purpose computing, yet power is a limiting factor in their performance. In this paper, we compare the power and performance of two design points in the many-core processor domain. The XMT general-purpose processor provides significant runtime advantage on irregular parallel programs (e.g., graph algorithms). This was previously demonstrated and tied to its architecture choices and ease-of-programming. In contrast, current commercial GPUs excel at regular parallel programs that require high processing capability. In this work, we set the power envelope as a constraint and evaluate an envisioned 1024-core XMT processor against an NVIDIA GTX280 GPU considering various scenarios for estimating the power of the XMT chip. Even under worst-case assumptions and scenarios, simulations show that the XMT processor sustains its advantage over the GPU on irregular parallel programs, while not falling significantly behind on regular programs. The total energy spent per benchmark fits a similar pattern. Given that the two architectures target different types of parallelism, a future system can potentially utilize an XMT chip and a GPU chip in complementary roles.

Summary form only given, as follows. The 25th year of IPDPS gives us the opportunity to look back and (to attempt) to assess what has gone wrong, what has gone well, and what came as a surprise, in the field of parallel and distributed processing. The panel members will give a few examples of striking events that took place in their area (covering Algorithms/ Applications/ Architectures/ Software). They will also give a short statement on how they would summarize the evolution of the field as a whole over the last 25 years.

We present a parallel solution to the Maximum-Flow (Max-Flow) problem, suitable for a modern many-core architecture. We show that by starting from a PRAM algorithm, following an established "programmer's workflow" and targeting XMT, a PRAM-inspired many-core architecture, we achieve significantly higher speed-ups than previous approaches. Comparison with the fastest known serial max-flow implementation on a modern CPU demonstrates for the first time potential for orders-of-magnitude performance improvement for Max-Flow. Using XMT, the PRAM Max-Flow algorithm is also much easier to program than for other parallel platforms, contributing a powerful example toward dual validation of both PRAM algorithmics and XMT.

A new asynchronous interconnection network is introduced for globally-asynchronous locally-synchronous (GALS) chip multiprocessors. The network eliminates the need for global clock distribution, and can interface multiple synchronous timing domains operating at unrelated clock rates. In particular, two new highly-concurrent asynchronous components are introduced which provide simple routing and arbitration/merge functions. Post-layout simulations in identical commercial 90 nm technology indicate that comparable recent synchronous router nodes have 5.6-10.7 more energy per packet and 2.8-6.4 greater area than the new asynchronous nodes. Under random traffic, the network provides significantly lower latency and identical throughput over the entire operating range of the 800 MHz network and through mid-range traffic rates for the 1.36 GHz network, but with degradation at higher traffic rates. Preliminary evaluations are also presented for a mixed-timing (GALS) network in a shared-memory parallel architecture, running both random traffic and parallel benchmark kernels, as well as directions for further improvement.

Super-scalar, out-of-order processors that can have tens of read and write requests in the execution window place significant demands on Memory Level Parallelism (MLP). Multi-and many-cores with shared parallel caches further increase MLP demand. Current cache hierarchies however have been unable to keep up with this trend, with modern designs allowing only 4-16 concurrent cache misses. This disconnect is exacerbated by recent highly parallel architectures (e.g. GPUs) where power and area per-core budget favor lighter cores with less resources. Support for hardware and software prefetch increase MLP pressure since these techniques overlap multiple memory requests with existing computation. In this paper, we propose and evaluate a novel Resource-Aware Prefetching (RAP) compiler algorithm that is aware of the number of simultaneous prefetches supported, and optimized for the same. We show that in situations where not enough resources are available to issue prefetch instructions for all references in a loop, it is more beneficial to decrease the prefetch distance and prefetch for as many references as possible, rather than use a fixed prefetched distance and skip prefetching for some references, as in current approaches. We implemented our algorithm in a GCC-derived compiler and evaluated its performance using an emerging fine-grained many-core architecture. Our results show that the RAP algorithm outperforms a well-known loop prefetching algorithm by up to 40.15% and the state-of-the art GCC implementation by up to 34.79%. Moreover, we compare the RAP algorithm with a simple hardware prefetching mechanism, and show improvements of up to 24.61%.

A new asynchronous interconnection network is introduced for globally-asynchronous locally-synchronous (GALS)chip multiprocessors. The network eliminates the need for global clock distribution, and can interface multiple synchronous timing domains operating at unrelated clock rates. In particular, two new highly-concurrent asynchronous components are introduced which provide simple routing and arbitration/merge functions. Post-layout simulations in identical commercial 90 nm technology indicate that comparable recent synchronous router nodes have 5.6-10.7x more energy per packet and 2.8-6.4x greater area than the new asynchronous nodes. Under random traffic, the network provides significantly lower latency and competitive throughput over the entire operating range of the 800 MHz network and through mid-range traffic rates for the 1.36 GHz network, but with degradation at higher traffic rates. Preliminary evaluations are also presented for a mixed-timing (GALS) network in a shared-memory parallel architecture, running both random traffic and parallel benchmark kernels, as well as directions for further improvement.

We present Lazy Binary Splitting (LBS), a user-level scheduler of nested parallelism for shared-memory multiprocessors that builds on existing Eager Binary Splitting work-stealing (EBS) implemented in Intel's Threading Building Blocks (TBB), but improves performance and ease-of-programming. In its simplest form (SP), EBS requires manual tuning by repeatedly running the application under carefully controlled conditions to determine a stop-splitting-threshold (sst)for every do-all loop in the code. This threshold limits the parallelism and prevents excessive overheads for fine-grain parallelism. Besides being tedious, this tuning also over-fits the code to some particular dataset, platform and calling context of the do-all loop, resulting in poor performance portability for the code. LBS overcomes both the performance portability and ease-of-programming pitfalls of a manually fixed threshold by adapting dynamically to run-time conditions without requiring tuning.

All students at our high school are required to take at least one course in Computer Science prior to their junior year. They are also required to complete a year-long senior project associated with a specific in-house laboratory, one of which is the Computer Systems Lab. To prepare students for this experience the lab offers elective courses at the post-AP Computer Science level. Since the early 1990s one of these electives has focused on parallel computing. The course enrolls approximately 40 students each year for two semesters of instruction. The lead programming language is C and topics include a wide array of industry-standard and experimental tools. Since the 2007-2008 school year we have included a unit on parallel algorithmic thinking (PAT) using the Explicit Multi-Threading (XMT) system. We describe our experiences using this system after self-studying the approach from a publicly available tutorial. Overall, this article provides significant evidence regarding the unique teachability of the XMT PAT approach, and advocates using it broadly in Computer Science education.

Abstract—Our earlier parallel algorithmics work on the parallel random-access-machine/model (PRAM) computation model led us to a PRAM-On-Chip vision: a comprehensive many-core system that can look to the programmer like the abstract PRAM model. We introduced the eXplicit Multi-Threaded (XMT) design and prototyped it in hardware and software. XMT comprises a programmer’s workflow that advances from work-depth, a standard PRAM theory abstraction, to an XMT program, and, if desired, to its performance tuning. XMT provides strong performance for programs developed this way due to its hardware support of very fine-grained threads and the overhead of handling them. XMT has also shown unique promise when it comes to ease-ofprogramming, the biggest problem that has limited the impact of all parallel systems to date. For example, teachability of XMT programming has been demonstrated at various levels from rising 6 th graders to graduate students, and students in a freshman class were able to program 3 parallel sorting algorithms. The main purpose of the current paper is to stimulate discussion on the following somewhat open-ended question. Now that we made significant progress on a system devoted to supporting PRAM-like programming, is it possible to incorporate our hardware support as an add-on into other current and future many-core systems? The paper considers a concrete proposal for doing that: recasting our work as a hardware-enhanced programmer’s workflow “module ” that can then be essentially imported into the other systems. I.

We compare the Paraleap FPGA computer, a 64-processor hardware prototype of the PRAM-driven XMT architecture, with an Intel Core 2 Duo processor and show that Paraleap outperforms the Intel processor by up to 13.89x in terms of cycle counts. The comparison favors the Intel design, since the silicon area of an ASIC implementation of the 64-processor XMT design is the same as that of a single core.

In single-chip parallel processors, it is crucial to implement a high-throughput low-latency interconnection network to connect the on-chip components, especially the processing units and the memory units. In this paper, we propose a new mesh of trees (MoT) implementation of the interconnection network and evaluate it relative to metrics such as wire complexity, total register count, single switch delay, maximum throughput, tradeoffs between throughput and latency, and post-layout performance. We show that on-chip interconnection networks can provide higher bandwidth between processors and shared first-level cache than previously considered possible, facilitating greater scalability of memory architectures that require that. MoT is also compared, both analytically and experimentally, to some other traditional network topologies, such as hypercube, butterfly, fat trees and butterfly fat trees. When we evaluate a 64-terminal MoT network at 90-nm technology, concrete results show that MoT provides higher throughput and lower latency especially when the input traffic (or the on-chip parallelism) is high, at comparable area. A recurring problem in networking and communication is that of achieving good sustained throughput in contrast to just high theoretical peak performance that does not materialize for typical work loads. Our quantitative results demonstrate a clear advantage of the proposed MoT network in the context of single-chip parallel processing.

Single-chip parallel processing requires high bandwidth between processors and on-chip memory modules. A recently proposed Mesh-of-Trees (MoT) network provides high throughput and low latency at relatively high area cost. In this paper, we introduce a hybrid MoT-BF network that combines MoT network with the area efficient butterfly network. We prove that the hybrid network reduces MoT network's area cost. Cycle-accurate simulation and post-layout results all show that significant area reduction can be achieved with negligible performance degradation, when operating at same clock rate.

The shading processors in graphics hardware are becoming increasingly general-purpose. We test, through simulation and benchmarking, the potential performance impact of replacing these processors with a fully general-purpose parallel processor, without the fixed-function graphics hardware legacy of current graphics processing units (GPUs). The representative general-purpose processor we test against is XMT (for eXplicit Multi-Threading), a PRAM-like single-chip parallel architecture. Performance is compared for two characteristic shaders running in a fragment-limited GPU benchmark harness and on a cycle-accurate XMT simulator. The general-purpose processor is found to be significantly faster at a compute-only shader, but slower on a memory bound texture shader. Finally we analyze the design tradeoffs that would allow combining the best of both worlds: (i) a competitive XMT texture shader, with (ii) a general-purpose easy-to-program XMT many-core approach that scales up or down to the amount of parallelism provided by the application and is even compatible with serial code.

No abstract available.

There is a recent surge of interest in single-chip parallel processors. In such machines, it is crucial to implement a high-throughput low-latency interconnection network to connect the on-chip components, especially the processing units and the memory units. In this paper, we propose a new mesh of trees (MoT) implementation of the interconnection network and evaluate it relative to metrics such as wire area, total switch delay and maximum throughput taking into account latencythroughput trade-offs. We show that on-chip interconnection networks can provide higher bandwidth between processors and shared first-level cache than previously considered possible, facilitating greater scalability of memory architectures that require that. MoT is also compared, both analytically and experimentally, to some other traditional network topologies, such as hypercube, butterfly, fat trees and butterfly fat trees. When we evaluate a 64-terminal MoT network at 65nm technology, concrete results show that MoT provides higher throughput and lower latency especially when the input traffic (or the on-chip parallelism) is high, at the cost of larger area. A recurring problem in networking and communication is that of achieving good sustained throughput in contrast to just high theoretical peak performance that does not materialize for typical work loads. Our quantitative results demonstrate a clear advantage of the proposed MoT network in the context of single-chip parallel processing.

We introduce a challenging problem in establishing and initially configuring or bootstrapping a Free Space Optical (FSO) network. In such networks, it is assumed that each communication node is a base station, including a router and wireless optical communications hardware, and its number of transceivers is limited. In addition, the FSO networks are characterized by narrow beam, directional links (e.g., operating at 1550 nm) and support up to Gbps data rates. The problem of initially configuring the transceivers to form a connected topology is NP-complete because of the transceiver limitation. What makes this problem even more challenging is the need to configure the transceiver in a "distributed" fashion, because a node can have only direct knowledge of its neighbors. We have developed a fully distributed approximation algorithm, which constructs a spanning tree with maximal node degree at most one larger than that in the optimal solution. Due to its distributed nature, this algorithm outperforms known serial algorithms. For a graph with 200 nodes generated in some randomized model, speed-ups greater than 6 have been demonstrated.

The utility of algorithm parallelism for coping with increased processor to memory latencies using "latency hiding" is part of the folklore of parallel computing. Latency hiding techniques increase the traffic to memory and therefore may "hit another wall": limited bandwidth to memory. The current paper attempts to stimulate research in the following general direction: show that algorithm parallelism need not conflict with limited bandwidth.A general technique for using parallel algorithms to enhance serial implementation in the face of processor-memory latency problems is revisited. Two techniques for alleviating memory bandwidth constraints are presented. Both techniques can be incorporated in a compiler.There is often considerable parallelism in many of the algorithms which are known as useful serial algorithms. Interestingly enough, all the examples provided for the use of the two techniques come from such serial algorithms.

Explicit-multithreading (XMT) is a parallel programming model designed for exploiting on-chip parallelism. Its features include a simple thread execution model and an efficient prefix-sum instruction for synchronizing shared data accesses. By taking advantage of low-overhead parallel threads and high on-chip memory bandwidth, the XMT model tries to reduce the burden on programmers by obviating the need for explicit task assignment and thread coarsening. This paper presents features of the XMT programming model, and evaluates their utility through experiments on a prototype XMT compiler and architecture simulator. We find the lack of explicit task assignment has slight effects on performance for the XMT architecture. Despite low thread overhead, thread coarsening is still necessary to some extent, but can usually be automatically applied by the XMT compiler. The prefix-sum instruction provides more scalable synchronization than traditional locks, and the simple run-untilcompletion thread execution model (no busy-waits) does not impair performance. Finally, the combination of features in XMT can encourage simpler parallel algorithms that may be more efficient than more traditional complex approaches.

The resource discovery problem was introduced by Harchol-Balter, Leigh ton and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph, that represents the vertices' “knowledge” about the topology of the underlying communication network.

Explicit-multithreading (XMT) is a parallel programming approach for exploiting on-chip parallelism. XMT introduces a computational framework with 1) a simple programming style that relies on fine-grained PRAM-style algorithms; 2) hardware support for low-overhead parallel threads, scalable load balancing, and efficient synchronization. The missing link between the algorithmic-programming level and the architecture level is provided by the first prototype XMT compiler. This paper also takes this new opportunity to evaluate the overall effectiveness of the interaction between the programming model and the hardware, and enhance its performance where needed, incorporating new optimizations into the XMT compiler. We present a wide range of applications, which written in XMT obtain significant speedups relative to the best serial programs. We show that XMT is especially useful for more advanced applications with dynamic, irregular access pattern, where for regular computations we demonstrate performance gains that scale up to much higher levels than have been demonstrated before for on-chip systems.

Suppose that a parallel algorithm can include any number of parallel threads. Each thread can proceed without ever having to busy wait to another thread. A thread can proceed till its termination, but no new threads can be formed. What kind of problems can such restrictive algorithms solve and still be competitive in the total number of operations they perform with the fastest serial algorithm for the same problem?

This paper envisions an extension to a standard instruction set which efficiently implements PRAM-style algorithms using explicit multi-threaded instruction-level parallelism (ILP); that is, Explicit Multi-Threading (XMT), a fine-grained computational paradigm covering the spectrum from algorithms through architecture to implementation is introduced; new elements are added where needed.

A key approach in string processing algorithmics has been the labeling paradigm which is based on assigning labels to some of the substrings of a given string. If these labels are chosen consistently, they can enable fast comparisons of substrings. Until the first optimal parallel algorithm for suffix tree construction was given by the authors in 1994 the labeling paradigm was considered not to be competitive with other approaches. They show that this general method is also useful for several central problems in the area of string processing: approximate string matching, dynamic dictionary matching, and dynamic text indexing. The approximate string matching problem deals with finding all substrings of a text which match a pattern "approximately", i.e., with at most m differences. The differences can be in the form of inserted, deleted, or replaced characters. The text indexing problem deals with finding all occurrences of a pattern in a text, after the text is preprocessed. In the dynamic text indexing problem, updates to the text in the form of insertions and deletions of substrings are permitted. The dictionary matching problem deals with finding all occurrences of each pattern set of a set of patterns in a text, after the pattern set is preprocessed. In the dynamic dictionary matching problem, insertions and deletions of patterns to the pattern set are permitted.

We study the effect of limited communication throughput on parallel computation in a setting where the number of processors is much smaller than the length of the input.Our model haa p processors that communicate through a shared memory of size m.The input haa size n, and can be read directly by all the processuggest that such new methodologies are likely to be found.

There are several serial algorithms for suffix tree construction which run in linear time, but the number of operations in the only parallel algorithm available, due to Apostolic, Iliopoulos, Landau, Schieber and VLshkin, is proportional to n log n.The algorithm is based on labeling substringsj similar to a classical serial algorithm, with the same operations bound, by Karp, Miller and Rosenberg.We show how to break symmetries that occur in the process of assigning labels using the Deterministic Coin Tossing (DCT) technique, and thereby reduce the number of labeled substrings to linear.We give several algorithms for suffix tree construction.One of them runs in 0(log2 n) parallel time and O(n) work for input strings whose characters are drawn from a constant size alphabet.

Given m points in the plane and a threshold t, a curve is defined to be robust if at least t points lie on it. Efficient algorithms for detecting robust curves are given; the key contribution is to use randomized sampling. In addition, an approximate version of the problem is introduced. A geometric solution to this problem is given; it too can be enhanced by randomization. These algorithms are readily generalized to solve the problem of robust curve detection in a scene of curve fragments: given a set of curve segments, a curve σ is defined to be robust if curve segments of total length at least l lie on σ. Again, both an exact and an approximate version of the problem are considered. The problems and solutions are closely related to the well-investigated Hough transform technique.

A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? Unfortunately, the problem is known to be NP-hard. We consider the problem of finding a better approximation to the smallest 2-connected subgraph, by an efficient algorithm. For 2-edge connectivity, our algorithm guarantees a solution that is no more than 3/2 times the optimal. For 2-vertex connectivity, our algorithm guarantees a solution that is no more than 5/3 times the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure called a carving of a graph, which is of independent interest. We show that approximating the optimal solution to within an additive constant is NP-hard as well. We also consider the case where the graph has edge weights. For this case, we show that an approximation factor of 2 is possible in polynomial time for finding a k -edge connected spanning subgraph. This improves an approximation factor of 3 for k = 2, due to Frederickson and Ja´Ja´ [1981], and extends it for any k (with an increased running time though).

A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers $[1..s]$. For an input of size n, it runs in $O(\log \log \log s)$ time and $O(n)$ work (which is optimal). A faster algorithm is presented for the special case $s = n$; it runs in $O(\log ^ * n)$ time with optimal work. Both algorithms are for the Priority concurrent-read concurrent-write parallel random access machine (CROW PRAM). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can be solved significantly faster than the $\Omega (\log \log n)$ time lower bound in a decision model of parallel computation, as described by Valiant [SIAM J. Comput., 4 (1975), pp. 348–355]. The top-bottom routing problem, which is an important subproblem of routing wires around a rectangle in two layers, is also considered. It is established that, for parallel (and hence for serial) computation, the problem of top-bottom routing is no harder than the prefix minima problem with $s = n$, thus giving an $O(\log ^ * n)$ time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be given an optimal parallel algorithm that runs in sublogarithmic time.

This paper introduces a novel parallel data structure called the recursive star-tree (denoted “${}^ * $-tree”). For its definition a generalization of the $ * $ functional is used (where for a function $f * f(n) = \min \{ {i|f^{(i)} (n) \leqslant 1} \}$ and $f^{(i)} $ is the ith iterate of f). Recursive ${}^ * $-trees are derived by using recursion in the spirit of the inverse Ackermann function. The recursive ${}^ * $-tree data structure leads to a new design paradigm for parallel algorithms. This paradigm allows for extremely fast parallel computations, specifically, $O(\alpha (n))$ time (where $\alpha (n)$ is the inverse of the Ackermann function), using an optimal number of processors on the (weakest) concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM). These computations need only constant time, and use an optimal number of processors if the following nonstandard assumption about the model of parallel computation is added to the CRCW PRAM: an extremely small number of processors each can write simultaneously into different bits of the same word. Applications include finding lowest common ancestors in trees by a new algorithm that is considerably simpler than the known algorithms for the problem, restricted domain merging, parentheses matching, and a new parallel reducibility.

A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? Unfortunately, the problem is known to be NP-hard.

It is demonstrated that randomization is an extremely powerful tool for designing very fast and efficient parallel algorithms. Specifically, a running time of O(lg* n) (nearly-constant), with high probability, is achieved using n/lg* n (optimal speedup) processors for a wide range of fundamental problems. Also given is a constant time algorithm which, using n processors, approximates the sum of n positive numbers to within an error which is smaller than the sum by an order of magnitude. A variety of known and new techniques are used. New techniques, which are of independent interest, include estimation of the size of a set in constant time for several settings, and ways for deriving superfast optimal algorithms from superfast nonoptimal ones.>

Article Converting high probability into nearly-constant time—with applications to parallel hashing Share on Authors: Yossi Matias Univ. of Maryland, College Park Univ. of Maryland, College ParkView Profile , Uzi Vishkin Univ. of Maryland, College Park Univ. of Maryland, College ParkView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 307–316https://doi.org/10.1145/103418.103453Published:03 January 1991 68citation339DownloadsMetricsTotal Citations68Total Downloads339Last 12 Months7Last 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 SiteGet Access

Part I of this paper presented a novel technique for approximate parallel scheduling and a new logarithmic time optimal parallel algorithm for the list ranking problem. In this part, we give a new logarithmic time parallel (PRAM) algorithm for computing the connected components of undirected graphs which uses this scheduling technique. The connectivity algorithm is optimal unless m = o(n log∗ n) in graphs of n vertices and m edges. (log(k) denotes the kth iterate of the log function and log∗ n denotes the least i such that log(i) n ≤ 2). Using known results, this new algorithm implies logarithmic time optimal parallel algorithms for a number of other graph problems, including biconnectivity, Euler tours, strong orientation and st-numbering. Another contribution of the present paper is a parallel union/find algorithm.

Consider the following three-stage strategy for recognizing patterns in larger scenes: Mimic randomization deterministically. Sample several positions of the pattern.Search for sample. Find all occurrences of the sample in the scene. Verify. For each occurrence of the sample, verify occurrence of the full pattern. This strategy has led to the core of the new idea given in this paper. Consider the string matching problem. Given the pattern, a sample of its positions is carefully selected whose size is at most logarithmic (the deterministic sample). Then, the sample is searched for. For nonperiodic patterns, the sample has the following perhaps surprising property. It is possible to disqualify all occurrences of the sample positions but one, within each “neighborhood” of locations in the text, without any further comparisons of characters. This provides sparse verification. This approach enables the text analysis (stages “search for sample” and “verify”) to be performed in $O(\log ^ * n)$ time and optimal speedup on a PRAM. This improves on the previous fastest optimal speedup result. It also leads to a new serial algorithm for string matching that runs in linear time including preprocessing. The approach is expected to be applicable for pragmatic pattern recognition problems. In some sense the algorithms are based on degenerate forms of computation, such as AND and OR of a large number of bits. However, traditional machine designs do not take advantage of such degeneracies, and usual complexity measures do not even enable them to be reflected. This leads to the conclusion of the paper with some speculative thoughts on desirable capabilities that would enhance computing machinery for some pattern recognition applications.

It is established that several natural problems have triply logarithmic, or even faster, optimal parallel algorithms. These problems include: merging two sorted lists, where the values are drawn from a large, but restricted, domain on a CREW PRAM; finding all prefix minima, where the values are drawn from a restricted domain; and top-bottom global routing around a rectangle, a well-investigated problem in VLSI routing for which only highly involved serial algorithms were known.>

Consider the following threestage strategy for recognizing patterns in larger scenes: Mimic randomization deterministically: Sample several positions of the pattern. Search for sample:Find all occurrences of the sample in the scene. Verify:For each occurrence of the sample, verify occurrence of the full pattern.This strategy led to the core of our new idea.Consider the string matching problem.Given the pattern, we select carefully a sample of its positions, whose size is at most logarithmic (the deterministic sample).Then, we search for the sample.For nonperiodic patterns, the sample has the following perhaps surprising property.It is possible to disqualify all occurrences of the sample positions but one, within each "neighborhood" of locations in the text, without any further comparisons of characters.This provides sparse verification.This approach enables to perform the text analysis (stages "search for sample" and "verify") in O (log*n) time and optimal speed-up on a PRAM.This improves on the previous fastest optimal speed-up result.It also leads to a new linear time serial algorithm for string matching.We expect the approach to be applicable for pragmatic pattern recognition problems.

The authors introduce a fundamentally novel parallel data structure, called recursive *-tree (star tree). For its definition, they use a generalization of this * functional and apply it to functions other than log. Using recursion in the spirit of the inverse-Akermann function, they derive recursive *-trees. The recursive *-tree data structure leads to a new design paradigm for parallel algorithms. The paradigm allows for unusually fast parallel computations that need only constant time, using an optimal number of processors under the assumption that a very small number of processors can write simultaneously, each into different bits of the same word.>

of Results.We establish that several problems are highly parallelizable.For each of these problems, we design an optimal 0 (loglogn ) time parallel algorithm on the Common CRCW PRAM model which is the weakest among the CRCW PRAM models.These problems include: 0 all nearest smaller values, l preprocessing for answering range maxima queries, l several problems in Computational Geometry, l string matching.

We present a parallel algorithm for the prefix sums problem which runs in timeO( logn/log logn) usingnlog logn/lognprocessors (optimal speedup). This algorithm leads to a parallel list ranking algorithm which runs inO(logn) time usingn/lognprocessors (optimal speedup).

Given two sequences, a pattern of length m, a text of length n and a positive integer k, we give two algorithms. The first finds all occurrences of the pattern in the text as long as these do not differ from each other by more than k differences. It runs in O(nk) time. The second algorithm finds all subsequence alignments between the pattern and the test with at most k differences. This algorithm runs in O(nmk) time, is very simple and easy to program.

We define a novel scheduling problem; it is solved in parallel by repeated, rapid, approximate reschedulings. This leads to the first optimal logarithmic time PRAM algorithm for list ranking. Companion papers show how to apply these results to obtain improved PRAM upper bounds for a variety of problems on graphs, including the following: connectivity, biconnectivity, Euler tour and $st$-numbering, and a number of problems on trees.

We consider the following problem. Suppose a rooted tree T is available for preprocessing. Answer on-line queries requesting the lowest common ancestor for any pair of vertices in T. We present a linear time and space preprocessing algorithm that enables us to answer each query in $O(1)$ time, as in Harel and Tarjan [SIAM J. Comput., 13 (1984), pp. 338–355]. Our algorithm has the advantage of being simple and easily parallelizable. The resulting parallel preprocessing algorithm runs in logarithmic time using an optimal number of processors on an EREW PRAM. Each query is then answered in $O(1)$ time using a single processor.

The following problem is considered: given a linked list of length n, compute the distance of each element of the linked list from the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O((n log n)/p + log n) time parallel algorithm using p processors. We present a randomized parallel algorithm for the problem. The algorithm is designed for an exclusive-read exclusive-write parallel random access machine (EREW PRAM). It runs almost surely in time O(n/p + log n log∗ n) using p processors. Using a recently published parallel prefix sums algorithm the list-ranking algorithm can be adapted to run on a concurrent-read concurrent-write parallel random access machine (CRCW PRAM) almost surely in time O(n/p + log n) using p processors.

The problem of sorting n elements using p processors in a parallel comparison model is considered. Lower and upper bounds which imply that for $p \geqq n$, the time complexity of this problem is $\Theta ({ {\log n} / { \log ({ {1+p} / n }) } })$ are presented. This complements [AKS-83] in settling the problem since the AKS sorting network established that for $p \leqq n$ the time complexity is $\Theta ({{n\log n} / p})$. To prove the lower bounds we show that to achieve $k \leqq \log n$ parallel time, we need $\Omega (n^{{{1 + 1} / k}} )$ processors.

The time complexity of sorting n elements using p ≥ n processors on Valiant's parallel comparison tree model is considered. The following results are obtained. 1. We show that this time complexity is Θ(logn/log(1+p/n)). This complements the AKS sorting network in settling the wider problem of comparison sort of n elements by p processors, where the problem for p ≤ n was resolved. To prove the lower bound, we show that to achieve time k ≤ logn, we need Ω(kn1+1/k) comparisons. Häggkvist and Hell proved a similar result only for fixed k. 2. For every fixed time k, we show that: (a) Ω(n1+1/k lognl/k) comparisons are required, (O(n1+1/k logn) are known to be sufficient in this case), and (b) there exists a randomized algorithm for comparison sort in time k with an expected number of O(n1+1/k) comparisons. This implies that for every fixed k, any deterministic comparison sort algorithm must be asymptotically worse than this randomized algorithm. The lower bound improves on Häggkvist-Hell's lower bound. 3. We show that "approximate sorting" in time 1 requires asymptotically more than nlogn processors. This settles a problem raised by M. Rabin.

We study two parallel scheduling problems and their use in designing parallel algorithms. First, we define a novel scheduling problem; it is solved by repeated, rapid, approximate reschedulings. This leads to a first optimal PRAM algorithm for list ranking, which runs in logarithmic time. Our second scheduling result is for computing prefix sums of logn bit numbers. We give an optimal parallel algorithm for the problem which runs in sublogarithmic time. These two scheduling results together lead to logarithmic time PRAM algorithms for the connectivity, biconnectivity and minimum spanning tree problems. The connectivity and biconnectivity algorithms are optimal unless m = o(nlog*n), in graphs of n vertices and m edges.

Article Free Access Share on Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms Authors: R Cole New York University and Tel Aviv University New York University and Tel Aviv UniversityView Profile , U Vishkin New York University and Tel Aviv University New York University and Tel Aviv UniversityView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 206–219https://doi.org/10.1145/12130.12151Online:01 November 1986Publication History 118citation925DownloadsMetricsTotal Citations118Total Downloads925Last 12 Months39Last 6 weeks11 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Consider the string matching problem where differences between characters of the pattern and characters of the text are allowed. Each difference is due to either a mismatch between a character of the text and a character of the pattern or a superfluous character in the text or a superfluous character in the pattern. Given a text of length n, a pattern of length m and an integer k, we present an algorithm for finding all occurrences of the pattern in the text, each with at most k differences. The algorithm runs in O(m2 + k2n) time. Given the same input we also present an algorithm for finding all occurrences of the pattern in the text, each with at most k mismatches (superfluous characters in either the text or the pattern are not allowed). This algorithm runs in O(k(m logm + n)) time.

In this paper we propose a new algorithm for finding the blocks (biconnected components) of an undirected graph. A serial implementation runs in $O(n + m)$ time and space on a graph of n vertices and m edges. A parallel implementation runs in $O(\log n)$ time and $O(n + m)$ space using $O(n + m)$ processors on a concurrent-read, concurrent-write parallel RAM. An alternative implementation runs in $O(n^2 /p)$ time and $O(n^2 )$ space using any number $p \leqq n^2 /\log ^2 n$ of processors, on a concurrent-read, exclusive-write parallel RAM. The last algorithm has optimal speedup, assuming an adjacency matrix representation of the input. A general algorithmic technique that simplifies and improves computation of various functions on trees is introduced. This technique typically requires $O(\log n)$ time using processors and $O(n)$ space on an exclusive-read exclusive-write parallel RAM.

A new technique for proving lower bounds for parallel computation is introduced. This technique enables us to obtain, for the first time, nontrivial tight lower bounds for shared-memory models of parallel computation that allow several processors to have simultaneous access to the same memory location. Specifically, we use a concurrent-read concurrent-write model of parallel computation. It has p processors, each has access to a common memory of size m (also called communication width or width in short). The input to the problem is located in an additional read-only portion of the common memory. For a wide variety of problems (including parity, majority and summation) we show that the time complexity T (depth) and the communication width m are related by the trade-off curve $mT^2 = \Omega (n)$, (where n is the size of the input), regardless of the number of processors. Moreover, for every point on this curve with $m = O(n/\log ^2 n)$ we give a matching upper bound with the optimal number of processors. We extend our technique to prove $mT^3 = \Omega (n)$ trade-off for a class of “simpler” functions (including Boolean OR) on a weaker model that forbids simultaneous write access. We also state and give a proof of a new result by Beame [B-83] that achieves a tight lower bound for the OR in this model, namely $mT^2 = \Omega (n)$. These results improve the lower bound of Cook and Dwork [CD-82] when communication is limited.

Given a general arithmetic expression, we find a computation binary tree representation in O (log n ) time using n /log n processors on a concurrent-read, exclusive-write, parallel random-access machine. A new algorithm is introduced for this purpose. Unlike previous serial and parallel solutions, it is not based on using a stack.

We propose a new algorithm for finding the blocks (biconnected components) of an undirected graph. A serial implementation runs in 0[n+m] time and space on a graph of n vertices and m edges. A parallel implmentation runs in 0[log n] time and 0[n+m] space using 0[n+m] processors on a concurrent-read, concurrent-write parallel RAM. An alternative implementation runs in 0[n/sup 2/p] time and 0[n/sup 2/] space using any number p ⩽ n/sup 2/log/sup 2/-n of processors, on a concurrent-read, exclusive-write parallel RAM. The latter algorithm has optimal speedup, assuming an adjacency matrix representation of the input. A general algorithmic technique which simplifies and improve computation of various functions on tress is introduced. This technique typically requires 0(log n) time using 0(n) space on an exclusive-read exclusive-write parallel RAM.

The following problem is considered: given a linked list of length n, compute the distance of each element of the linked list from the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O((nlog n)/p + log n) time parallel algorithm using p processors. A known conjecture states that it is impossible to design an O(log n) time deterministic parallel algorithm that uses only n/log n processors.

A general technique is described for solving certain NP-hard graph problems in time that is exponential in a parameter k defined as the maximum, over all nonseparable components C of the graph, of the number of edges that must be added to a tree to produce C; for a connected graph, k is no more than the number of edges of the graph minus the number of vertices plus one.The technique is illustrated in detail for the following facility location problem: Given a connected graph G(V, E) such that each edge has an associated positive integer length and given a positive integer r, place the minimum number of centers on points of the graph such that every point of the graph is within distance r from some center (a "point" is either a vertex or a point on some edge).An algorithm of time complexity O(I El. (6r) rkm) is given.A parallel implementation of the algorithm, with optimal speedup over the sequential version for a fairly wide range for the number of processors, is presented.

The purpose of this paper is to study reducibilities that can be computed by combinational logic networks of polynomial size and constant depth containing AND’s, OR’s and NOT’s, with no bound placed on the fan-in of AND-gates and OR-gates. Two such reducibilities are defined, and reductions and equivalences among several common problems such as parity, sorting, integer multiplication, graph connectivity, bipartite matching and network flow are given. Certain problems are shown to be complete, with respect to these reducibilities, in the complexity classes deterministic logarithmic space, nondeterministic logarithmic space, and deterministic polynomial time. New upper bounds on the size-depth (unbounded fan-in) circuit complexity of symmetric Boolean functions are established.

A relationship is established between (i) parallel random-access machines that allow many processors to concurrently read from or write into a common memory including simultaneous reading or writing into the same memory location (CROW PRAM), and (ii) combinational logic circuits that contain AND’s, OR’s and NOT’s, with no bound placed on the fan-in of AND-gates and OR-gates. Parallel time and number of processors for CROW PRAM’s are shown to correspond respectively (and simultaneously) to depth and size for circuits, where the time-depth correspondence is to within a constant factor and the processors-size correspondence is to within a polynomial. By applying a recent result of Furst, Saxe and Sipser, we obtain the corollary that parity, integer multiplication, graph transitive closure and integer sorting cannot be computed in constant time by a CROW PRAM with a polynomial number of processors. This is the first nonconstant lower bound on the parallel time required to solve these problems by a CROW PRAM with a polynomial number of processors. We also state and outline the proof of a similar result, due to W. L. Ruzzo and M. Tompa, that relates time and processor bounds for CRCW PRAM’S to alternation and space bounds for alternating Turing machines.

A new technique for proving lower bounds for parallel computation is introduced. This technique enables us to obtain, for the first time. non-trivial tight lower bounds for shared-memory models of parallel computation that allow simultaneous read/write access to the same memory location. The size m of the common memory is called communication width or width in short. For a wide variety of problems (including parity and majority) we show that the time complexity T (depth) and the communication width m are related by the trade-off curve mT2 = Ω(n) (where n is the size of the input). This bound is tight lot every m ≤n/log2n We extend our technique to prove mT3 = Ω(n) trade-off for a class of "simpler" functions (includind Boolean Or) on a weaker model that forbids simultaneous write access. This result improves the lower bound of Cook and Dwork [CD-82] when communication is limited.

An algorithm for constructing and maintaining full information on the structure of a communication network is presented. The algorithm uses distributed computation. It can be used as an information-gathering step, to be followed by special-purpose algorithms which are to be executed within the nodes, without any additional communication. The load of the lines of the network is measured and shown to be better than any known algorithm for determining connectivity, suggesting shortest path, routing, etc., when the number of topological changes is big enough. It is shown that the network will recover in finite time from a finite number of topological changes in the network. Other, more powerful, recovery criteria are also given.

A complexity theory for unbounded fan-in parallelism is developed where the complexity measure is the simultaneous measure (number of processors, parallel time). Two models of unbounded fan-in parallelism are (1) parallel random access machines that allow simultaneous reading from or writing to the same common memory location, and (2) circuits containing AND's, OR's and NOT's with no bound placed on the fan-in of gates. It is shown that these models can simulate one another with the number of processors preserved to within a polynomial and parallel time preserved to within a constant factor. Reducibilities that preserve the measure in this sense are defined and several reducibilities and equivalences among problems are given. New upper bounds on the (unbounded fan-in) circuit complexity of symmetric Boolean functions are proved.