Abstract Group communication primitives have broad utility as building blocks for distributed applications. The challenge is to create and maintain the distributed structures that support these primitives while accounting for volatile end‐nodes and variable network characteristics. Most solutions proposed to date rely on complex algorithms or on global information, thus limiting the scale of deployments and acceptance outside the academic realm. This article introduces a low‐complexity, self‐organizing solution for building and maintaining data dissemination trees, which we refer to as Unstructured Multi‐source Overlay (UMO). UMO uses traditional distributed systems techniques: layering, soft‐state, and passive data collection to adapt to the dynamics of the physical network and maintain data dissemination trees. The result is a simple, adaptive system with lower overheads than more complex alternatives. We implemented UMO and evaluated it on a 100‐node PlanetLab testbed and on up to 1024‐node emulated ModelNet networks. Extensive experimental evaluations demonstrate UMOs low overhead, efficient network usage compared with alternative solutions, and the ability to quickly adapt to network changes and to recover from failures. Copyright © 2009 John Wiley & Sons, Ltd.

We present linear-time algorithms for the classic problem of finding dominators in a flowgraph, and for several other problems whose solutions require evaluating a function defined on paths in a tree. Although all these problems had linear-time solutions previously, our algorithms are simpler, in some cases substantially. Our improvements come from three new ideas: a refined analysis of path compression that gives a linear bound if the compressions favor certain nodes; replacement of random-access table look-up by a radix sort; and a more careful partitioning of a tree into easily managed parts. In addition to finding dominators, our algorithms find nearest common ancestors off-line, verify and construct minimum spanning trees, do interval analysis of a flowgraph, and build the component tree of a weighted tree. Our algorithms do not require the power of a random-access machine; they run in linear time on a pointer machine. The genesis of our work was the discovery of a subtle error in the analysis of a previous allegedly linear-time algorithm for finding dominators. That algorithm was an attempt to simplify a more complicated algorithm, which itself was intended to correct errors in a yet earlier algorithm. Our work provides a systematic study of the subtleties in the dominators problem, the techniques needed to solve it in linear time, and the range of application of the resulting methods. We have tried to make our techniques as simple and as general as possible and to understand exactly how earlier approaches to the dominators problem were either incorrect or overly complicated.

Corrigendum to ACM Transactions on Programming Languages and Systems , 20(6):1265--1296, 1998.

Massive transaction streams present a number of opportunities for data mining techniques. The transactions in such streams might represent calls on a telephone network, commercial credit card purchases, stock market trades, or HTTP requests to a web server. While historically such data have been collected for billing or security purposes, they are now being used to discover how the transactors, for example, credit-card numbers or IP addresses, use the associated services.Over the past 5 years, we have computed evolving profiles (called signatures ) of transactors in several very large data streams. The signature for each transactor captures the salient features of his or her behavior through time. Programs for processing signatures must be highly optimized because of the size of the data stream (several gigabytes per day) and the number of signatures to maintain (hundreds of millions). Originally, we wrote such programs directly in C, but because these programs often sacrificed readability for performance, they were difficult to verify and maintain.Hancock is a domain-specific language we created to express computationally efficient signature programs cleanly. In this paper, we describe the obstacles to computing signatures from massive streams and explain how Hancock addresses these problems. For expository purposes, we present Hancock using a running example from the telecommunications industry; however, the language itself is general and applies equally well to other data sources.

Article Hancock: a language for extracting signatures from data streams Share on Authors: Corinna Cortes AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJView Profile , Kathleen Fisher AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJView Profile , Daryl Pregibon AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJView Profile , Anne Rogers AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJView Profile Authors Info & Claims KDD '00: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data miningAugust 2000 Pages 9–17https://doi.org/10.1145/347090.347094Online:01 August 2000Publication History 102citation888DownloadsMetricsTotal Citations102Total Downloads888Last 12 Months4Last 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

Customizing the protocols that manage accesses to different data structures within an application can improve the performance of software shared-memory programs substantially. Existing systems for using customizable protocols are hard to use directly because the mechanisms they provide for manipulating protocols are low-level ones. This article is an in-depth study of the issues involved in providing language support for application-specific protocols. We describe the design and implementation of a new language for parallel programming, Ace, that integrates support for customizable protocols with minimal extensions to C. Ace applications are developed using a shared-memory model with a default sequentially consistent protocol. Performance can then be optimized, with minor modifications to the application, by experimenting with different protocol libraries. The design of Ace was driven by a detailed study of the use of customizable protocols. We delineate the issues that arise when programming with customizable protocols and present novel abstractions that allow for their easy use. We describe the design and implementation of a runtime system and compiler for Ace nd discuss compiler optimizations that improve the performance of such software shared-memory systems. We study the communication patterns of a set of benchmark applications and consider the use of customizable protocols to optimize their performance. We evaluate the performance of our system through experiments on a Thinking Machine CM-5 and a Cray T3E. We also present measurements that demonstrate that Ace has good performance compared to that of a modern distributed shared-memory system.

We present two new data structure tools—disjoint set union with bottom-up linking, and pointer-based radix sort—and combine them with bottom-level microtrees to devise the first linear-time pointer-machine algorithms for off-line least common ancestors, minimum spanning tree (MST) verification, randomized MST construction, and computing dominators in a flowgraph.

We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data structures, we combine the use of microtrees and memoization with new observations on a restricted class of path compressions. We have implemented our algorithm, and we report experimental results that show that the constant factors are low. Compared to the standard, slightly superlinear algorithm of Lengauer and Tarjan, which has much less overhead, our algorithm runs 10-20% slower on real flowgraphs of reasonable size and only a few percent slower on very large flowgraphs.

Computer speech recognition has been very successful in limited domains and for isolated word recognition. However, widespread use of large-vocabulary continuous-speech recognizers is limited by the speed of current recognizers, which cannot reach acceptable error rates while running in real time. This paper shows how to harness shared memory multiprocessors, which are becoming increasingly common, to increase the speed significantly, and therefore the accuracy or vocabulary size, of a speech recognizer. To cover the necessary background, we begin with a tutorial on speech recognition. We then describe the parallelization of an existing high-quality speech recognizer, achieving a speedup of a factor of 3, 5, and 6 on 4-, 8-, and 12-processors respectively for the benchmark North American business news (NAB) recognition task.

Customizing the protocols used to manage accesses to different data structures within an application can improve the performance of shared-memory programs substantially [10, 21]. Existing systems for using customizable protocols are, however, hard to use because they force programmers to rely on low-level mechanisms for manipulating these protocols. Since several shared-memory systems implement protocols in software and can support customizable protocols, the development of intuitive abstractions for the use of application-specific protocols ia important.We have designed a language, Ace, that integrates support for customizable protocols with minimal extensions to C. Ace applications are developed using the standard shared-memory model with a default sequentially consistent protocol. Performance can then be optimized, with minor modifications to the application, by experimenting with different protocol libraries. In this paper, we isolate the issues involved in providing language support for using customizable protocols and present novel language abstractions for their easy use. We describe the implementation of a compiler and runtime system for Ace, and discuss the issues involved in their design. We also present measurements that demonstrate that Ace has good performance compared to an efficient software distributed shared-memory system.

Pipelined processors employ hardware bypassing to eliminate certain pipeline hazards. By passing is logically simple but can be costly, especially in wide issue and deeply pipelined machines. In this paper bypassing is studied in detail, with an emphasis on designs in which the bypassing network is not complete. Cycle-level simulations of a model of integer and floating-point pipelines running some of the SPEC92 benchmarks show that at least half of the instructions executed used a bypassed register result from a previous instruction. Missing bypasses induce interlock stalls. The paper reports measurements of the performance impact of a number of pipeline configurations with incomplete bypassing networks. This impact ranges from a slowdown of just a few percent for a configuration with one late bypass missing to a slowdown of almost a factor of two for the integer pipe with no bypassing at all. Two types of code alterations reduce the new interlock stalls. A simple code transformation, the interchange of operands in instructions that perform commutative operations, cuts the performance loss from interlock stalls in certain configurations between about 20 and 50 percent. The second transformation is to reschedule code within basic blocks to avoid any missing bypasses. In five individual experiments with a small number of configurations and two benchmarks, this rescheduling saved 25 to 50 percent of the interlock stalls. In certain configurations both transformations can be applied.

The goal of the Olden project is to build a system that provides parallelism for general purpose C programs with minimal programmer annotations. We focus on programs using dynamic structures such as trees, lists, and DAGs. We demonstrate that providing both software caching and computation migration can improve the performance of these programs, and provide a compile-time heuristic that selects between them for each pointer dereference. We have implemented a prototype system on the Thinking Machines CM-5. We describe our implementation and report on experiments with ten benchmarks.

Irregular computation problems underlie many important scientific applications. Although these problems are computationally expensive, and so would seem appropriate for parallel machines, their irregular and unpredictable run-time behavior makes this type of parallel program difficult to write and adversely affects run-time performance.

Compiling for distributed-memory machines has been a very active research area in recent years. Much of this work has concentrated on programs that use arrays as their primary data structures. To date, little work has been done to address the problem of supporting programs that use pointer-based dynamic data structures. The techniques developed for supporting SPMD execution of array-based programs rely on the fact that arrays are statically defined and directly addressable. Recursive data structures do not have these properties, so new techniques must be developed. In this article, we describe an execution model for supporting programs that use pointer-based dynamic data structures. This model uses a simple mechanism for migrating a thread of control based on the layout of heap-allocated data and introduces parallelism using a technique based on futures and lazy task creation. We intend to exploit this execution model using compiler analyses and automatic parallelization techniques. We have implemented a prototype system, which we callOlden, that runs on the Intel iPSC/860 and the Thinking Machines CM-5. We discuss our implementation and report on experiments with five benchmarks.

Message passing and shared memory are two techniques parallel programs use for coordination and communication. This paper studies the strengths and weaknesses of these two mechanisms by comparing equivalent, well-written message-passing and shared-memory programs running on similar hardware. To ensure that our measurements are comparable, we produced two carefully tuned versions of each program and measured them on closely-related simulators of a message-passing and a shared-memory machine, both of which are based on same underlying hardware assumptions.

Recent distributed shared memory (DSM) systems and proposed shared-memory machines have implemented some or all of their cache coherence protocols in software. One way to exploit the flexibility of this software is to tailor a coherence protocol to match an application's communication patterns and memory semantics. This paper presents evidence that this approach can lead to large performance improvements. It shows that application-specific protocols substantially improved the performance of three application programs-appbt, em3d, and barnes-over carefully tuned transparent shared memory implementations. The speed-ups were obtained on Blizzard, a fine-grained DSM system running on a 32-node Thinking Machines CM-5.>

The lack of high-level languages and good compilers for parallel machines hinders their widespread acceptance and use. Programmers must address issues such as process decomposition, synchronization, and load balancing. We have developed a parallelizing compiler that, given a sequential program and a memory layout of its data, performs process decomposition while balancing parallelism against locality of reference. A process decomposition is obtained by specializing the program for each processor to the data that resides on that processor. If this analysis fails, the compiler falls back to a simple but inefficient scheme called run-time resolution. Each process's role in the computation is determined by examining the data required for execution at run-time. Thus, our approach to process decomposition is data-driven rather than program-driven. We discuss several message optimizations that address the issues of overhead and synchronization in message transmission. Accumulation reorganizes the computation of a commutative and associative operator to reduce message traffic. Pipelining sends a value as close to its computation as possible to increase parallelism. Vectorization of messages combines messages with the same source and the same destination to reduce overhead. Our results from experiments in parallelizing SIMPLE, a large hydrodynamics benchmark, for the Intel iPSC/2, show a speedup within 60% to 70% of handwritten code.>

This paper describes a simple hardware mechanism and related compiler support for soft ware-controlled specu-

In the context of sequential computers, it is common practice to exploit temporal locality of reference through devices such as caches and virtual memory. In the context of multiprocessors, we believe that it is equally important to exploit spatial locality of reference. We are developing a system which, given a sequential program and its domain decomposition, performs process decomposition so as to enhance spatial locality of reference. We describe an application of this method - generating code from shared-memory programs for the (distributed memory) Intel iPSC/2.