Parallel and distributed systems that provide compute resources on demand are convenient, cost-effective, and becoming increasingly common. Boosting workload performance in such environments through scheduling has been of great interest, as users and providers aim to increase parallelism and reduce execution times. For modern data centers, leaving a smaller carbon footprint while maintaining high performance and low cost is becoming the next big challenge. With this in mind, we analyze the relative impacts on resource utilization of three well-motivated platform-oblivious scheduling heuristics. We simulate over 50,000 DAG workflow executions and measure performance, cost, and resource utilization under the three scheduling heuristics. Our results provide insights to better enable high-performance execution of workflows and advanced capacity planning while increasing resource utilization and reducing costs.

Summary The Area of a schedule Σ for a directed acyclic graph (DAG) is a quality metric that measures the rate at which Σ renders 's nodes eligible for execution. Specifically, AREA(Σ) is the average number of nodes of that are eligible for execution as Σ executes node by node. Extensive simulations suggest that, for many distributions of processor availability and power, DAG‐schedules having larger Areas execute DAGs faster on platforms that are dynamically heterogeneous: the platform's processors change power and availability status in unpredictable ways and at unpredictable times. (Clouds and desktop grids exemplify such platforms.) While Area‐maximal schedules can provably be found for everyDAG, efficient generators of such schedules are known only for families of well‐structured DAGs. Our first result shows that the problem of crafting Area‐maximal schedules for general DAGs is NP‐complete, hence likely computationally intractable. We also provide an efficient algorithm that approximates optimal Area to within a factor of , where n is the number of tasks in the DAG—a factor that is likely interesting only for small DAGs. The lack of efficient Area‐maximizing schedulers for general DAGs has instigated the development of several heuristics for producing DAG‐schedules that have large Areas. We propose a novel polynomial‐time heuristic that produces schedules having quite large Areas; the heuristic is based on the Sidney decomposition of a DAG. (1) Simulations on DAGs having random structure yield the following results. The SIDNEY heuristic produces schedules whose Areas: (a) are at least 85% of maximal; and (b) are at least 1.25 times greater than previously known heuristics. (2) Simulations on DAGs having the structure of random LEGO®;DAGs (as formulated in earlier studies) indicate that the schedules produced by the SIDNEY heuristic have Areas that are at least 1.5 times greater than previously known heuristics. The ‘85%’ result is obtained from formulating the Area‐maximization problem as a linear program (LP); the Areas of DAG‐schedules produced by the SIDNEY heuristic are at least 85% of the Area value produced by the (unrounded) LP. (3) The reported results on random DAGs are essentially matched by a second heuristic, which produces DAG‐schedules by rounding the results of the LP formulation. Copyright © 2015 John Wiley & Sons, Ltd.

Many modern computing platforms-notably clouds and desktop grids-exhibit dynamic heterogeneity: the availability and computing power of their constituent resources can change unexpectedly and dynamically, even in the midst of a computation. We introduce a new quality metric, AREA, for schedules that execute computations having interdependent constituent chores (jobs, tasks, etc.) on such platforms. AREA measures the average number of chores that a schedule renders eligible for execution at each step of a computation. Even though the definition of AREA does not mention any properties of host platforms (such as volatility), intuition suggests that rendering chores eligible at a faster rate will have a benign impact on the performance of volatile platforms. We report on simulation experiments that support this intuition. Earlier work has derived the basic properties of the AREA metric and has shown how to efficiently craft AREA-maximizing (A-M) schedules for several classes of significant computations. Even though A-M schedules always exist for every computation, it is not always known how to derive such schedules efficiently. In response, the current study develops an efficient algorithm that produces AREA-Oriented (A-O) schedules, which aim to efficiently approximate the AREAs of A-M schedules on arbitrary computations. The simulation experiments reported on here suggest that, in common with A-M schedules, A-O schedules complete computations on volatile heterogeneous platforms faster than a variety of heuristics that range from lightweight ones to computationally intensive ones-albeit not to the same degree as A-M schedules do. Our experiments suggest that schedules having larger AREAs have smaller completion times-but no proof of that yet exists.

Parallelism pervades all aspects of modern computing, from in-home devices such as cell phones to large-scale supercomputers. Recognizing this - and motivated by the premise that every undergraduate student in a computer-related field should be prepared to cope with parallel computing - a working group sponsored by NSF and IEEE/TCPP, and interacting with the ACM CS2013 initiative, has developed guidelines for assimilating parallel and distributed computing (PDC) into the core undergraduate curriculum. Over 100 Early-Adopter institutions worldwide are currently modifying their computer-related curricula in response to the guidelines. Additionally, the CDER Center for Curriculum Development and Educational Resources, which grew out of the working group, is currently assembling a book of contributed essays on how to teach PDC topics in lower-level CS/CE courses, to fill the serious lack of textual material for students and instructors.

Advancing technologies have enabled simple mobile robots that collaborate to perform complex tasks. Understanding how to achieve such collaboration with simpler robots leverages these advances, potentially allowing more robots for a given cost and/or decreasing the cost of deploying a fixed number of robots. This paper is a step toward understanding the algorithmic strengths and weaknesses of robots that are identical mobile finite-state machines (FSMs)—FSMs being the avatars of simple, yet non-trivial, discrete control structures. We study the ability of (teams of) FSMs to identify and search varied-size quadrants of square (i.e. n×n) meshes of tiles—such meshes being the avatars of simple tesselated geographically constrained environments. Each team must be able to accomplish its assigned tasks in arbitrarily large meshes—i.e. for arbitrarily large values of n. Partitions of a mesh into quadrants are specified via pairs of rational numbers 〈 φ, ψ 〉, where 0 < φ, ψ < 1, chosen from a fixed, finite repertoire of such pairs. The quadrants specified by a pair 〈 φ, ψ 〉 are delimited by a horizontal line and a vertical line that that cross at the anchor mesh-tile v = 〈 ⌊ φ (n−1) ⌋, ⌊ ψ (n−1) ⌋ 〉. The following results are established. A single FSM cannot identify anchor tiles in meshes of arbitrary sizes, even for a single pair 〈 φ, ψ 〉—except when the anchor tile resides on an edge of the mesh. A pair of identical FSMs can identify anchor tiles in meshes of arbitrary sizes, for arbitrary fixed finite sets of k pairs {〈 φi, ψi 〉}i=1k. After identifying an anchor tile, the pair can sweep each of the resulting quadrants in turn. Single FSMs can verify—for arbitrary fixed finite sets of pairs and for meshes of arbitrary sizes—that all of the tiles of each quadrant are labeled in a way that is unique to that quadrant. Deploying multiple FSMs for this task achieves linear parallel speedup.

We have teams of r identical mobile finite-state machines (FSMs, for short) act as robots that rearrange objects within a "warehouse" whose floor is the side-n square mesh M_n. We study a variety of rearrangement problems that (teams of) FSMs can solve via algorithms that are scalable-i.e., that work in arbitrarily large meshes-and fully pipeline able-i.e., that achieve (asymptotic) linear speedup when larger teams of FSMs are deployed. Regarding pipelining, in detail: If r FSMs can solve a problem on M_n in time T_r(n), then as r grows, even as large as n, T_r(n) = O((1/r) T_1(n)), uniformly in n and r. The rearrangement problems we have chosen are reminiscent of tasks that one might have robots perform in a warehouse. Sample problems have FSMs move objects from the top edge of M_n to the bottom edge: (1) in the reverse of the objects' original top-edge order, (2) in piles organized by object type (from a fixed set of types).

No abstract available.

Heterogeneity in resources pervades all modern computing platforms. How do the effects of heterogeneity depend on which resources differ among computers in a platform? Some answers are derived within a formal framework, by comparing heterogeneity in computing power (node-heterogeneity) with heterogeneity in communication speed (link-heterogeneity). The former genre of heterogeneity seems much easier to understand than the latter.

Heterogeneity complicates the efficient use of multicomputer platforms, but does it enhance their performance? their cost effectiveness? How can one measure the power of a heterogeneous assemblage of computers (¿cluster,¿ for short), both in absolute terms (how powerful is this cluster) and relative terms (which cluster is more powerful)? What makes one cluster more powerful than another? Is one better off with a cluster that has one super-fast computer and the rest of ¿average¿ speed or with a cluster all of whose computers are ¿moderately¿ fast? If you could replace just one computer in your cluster with a faster one, which computer would you choose: the fastest? the slowest? How does one even ask questions such as these in a rigorous, yet tractable manner? A framework is proposed, and some answers are derived, a few rather surprising. Three highlights: (1) If one can replace only one computer in a cluster by a faster one, it is provably (almost) always most advantageous to replace the fastest one. (2) If the computers in two clusters have the same mean speed, then, empirically, the cluster with the larger variance in speed is (almost) always the faster one. (3) Heterogeneity can actually lend power to a cluster!

One has a large workload that is ldquodivisiblerdquo-its constituent work's granularity can be adjusted arbitrarily;-and one has access to p remote computers that can assist in computing the workload. The problem is that the remote computers are subject to interruptions of known likelihood that kill all work in progress. One wishes to orchestrate sharing the workload with the remote computers in a way that maximizes the expected amount of work completed. Strategies for achieving this goal, by balancing the desire to checkpoint often, in order to decrease the amount of vulnerable work at any point, vs. the desire to avoid the context-switching required to checkpoint, are studied. Strategies are devised that provably maximize the expected amount of work when there is only one remote computer (the case p = 1). Results suggest the intractability of such maximization for higher values of p, which motivates the development of heuristic approaches. Heuristics are developed that replicate works on several remote computers, in the hope of thereby decreasing the impact of work-killing interruptions. The quality of these heuristics is assessed through exhaustive simulations.

A new quality metric, called area, is introduced for schedules that execute dags, i.e., computations having intertask dependencies. Motivated by the temporal unpredictability encountered when computing over the Internet, the goal under the new metric is to maximize the average number of tasks that are eligible for execution at each step of a computation. Area-maximization is a weakening of IC-optimality, which strives to maximize the number of eligible tasks at every step of the computation. In contrast to IC-optimal schedules, area-maximizing schedules exist for every dag. For dags that admit IC-optimal schedules, all area-maximizing schedules are IC-optimal, and vice versa. The basic properties of this metric are derived in this paper, and tools for efficiently crafting area-maximizing schedules for large classes of computationally significant dags are developed. Several of these results emerge from a close connection between area-maximizing scheduling and the MAX Linear-Arrangement Problem for Dags.

A mathematical-plus-conceptual framework is presented for studying problems such as the following. One wants to deploy an n-node multi-channel wireless network N in an environment that is inaccessible for repair and/or that contains malicious adversaries. (Example: One wants to ldquohardenrdquo a facility-say, a control base or organizational headquarters or hospital or computation center-against ldquodestructive incidentsrdquo such as attacks by malicious adversaries or accidents of nature.) Given a (finite) set Omega of topologies that one wants to be able to ldquooverlayrdquo on (the surviving portion of) network N, one wants to design N to be Omega-robust, in the following very strong sense. Even if any set of m < n nodes is disabled, one still wants all of the surviving n - m nodes to be able to organize themselves (logically, in the manner of an overlay network) into any topology T isin Omega that has les n-m nodes. A mathematical model for multi-channel wireless networks is presented and is used to develop a scalable, deterministic strategy for designing networks that are Omega-robust, for a very broad class of sets Omega. The strategy is illustrated for the simple case when Omega is the set of all paths of lengths les n. The resulting path-robust networks: (a) are within a factor of 2 of optimal in complexity, as measured by the number of node-channel access points; (b) enable power-efficient communication, in that a node's logical neighbors in the overlay path are its physically nearest nodes in the surviving portion of N. It is suggested how the model and approach can extend to a much richer variety of topologies.

A model for realizing ant-inspired algorithms that coordinate robots within a fixed, geographically constrained environment is proposed and illustrated. The model, dubbed cellular ANTomata, inverts the relationship between ant-robots and the environment that they navigate: intelligence now resides in the environment rather than in the ants. The cellular ANTomaton model is illustrated via three proof-of-concept problems: having ants "park" in the nearest corner; having ants seek "food items" (both with and without impenetrable obstacles); having a single ant thread a maze. In all cases, "unintelligent" cellular-ANTomata-based ant-robots accomplish goals provably more efficiently than traditional "intelligent" ant-robots can; indeed, "intelligent" ant-robots cannot park at all! All of the presented algorithms are scalable: they provably work within any finite-size environment.

Strategies are developed for "fattening" the tasks ofcomputation-dags so as to accommodate the heterogeneity of remote clients in Internet-based computing (IC). Earlier work has developed the underpinnings of IC-Scheduling theory, an algorithmic framework for scheduling computations having intertask dependencies for IC. The theory's schedules strive to render tasks eligible for execution at the maximum possible rate, so as to: (a) utilize remoteclients' computational resources well, by enhancing the likelihood of having work to allocate to an available client; (b) lessen the likelihood of a computation's stalling for lack of tasks that are eligible for allocation. The current study begins to enhance IC-Scheduling theory so that it can accommodate the varying computational resources of remote clients. The techniques developed here render a dag multi-granular by clustering its tasks. Several clustering strategies are developed: one works for any dag but produces only a limited variety of "fattened" tasks; others exploit the detailed structure of the dag being scheduled but allow a broad range of "fattened" tasks.

Earlier work has developed the rudiments of a scheduling theory for computations having intertask dependencies - modeled via dags - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution as fast as possible, with the aim of: (a) utilizing clients' computational resources well, by always having work to allocate to an available client; (b) lessening the likelihood of a computation's stalling for lack of eligible tasks. Simulation studies suggest that this goal does accelerate computation over the Internet. The theory crafts a schedule for a dag Q by "parsing" Q (if possible) into connected building-block dags that one can "compose " to form Q and then analyzing the scheduling dependencies among these building blocks. The current paper extends the theory by developing the Sweep Algorithm, a tool that allows one to: (1) schedule using building blocks that are not necessarily connected, and (2) craft schedules that interleave the execution of subdags that have no interdependencies. The augmented scheduling algorithms allow one to craft optimal schedules for previously unschedulable dags. Examples presented include artificial dags that are "close" to ones arising in real computations, as well as a component of a dag that arises in a functional MRI application.

Earlier work has developed the underpinnings of IC-scheduling theory, an algorithmic framework for scheduling computations having intertask dependencies for Internet-based computing (IC). The theory aims to produce schedules that render tasks eligible for execution at the maximum possible rate, so as to: (a) utilize remote clients' computational resources well, by always having work available for allocation; (b) lessen the likelihood that a computation can stall for lack of tasks that are eligible for execution. The current paper reconnects the theory, which models computations abstractly, with a variety of significant real computations and computational paradigms, by illustrating how to schedule these computations optimally.

A fundamental challenge in Internet computing (IC) is to efficiently schedule computations having complex inter job dependencies, given the unpredictability of remote machines, in availability and time of access. The recent IC scheduling theory focuses on these sources of unpredictability by crafting schedules that maximize the number of executable jobs at every point in time. In this paper, we experimentally investigate the key question: does IC scheduling yield significant positive benefits for real IC? To this end, we develop a realistic computation model to match jobs to client machines and conduct extensive simulations to compare IC-optimal schedules against popular, intuitively compelling heuristics. Our results suggest that for a large range of computation-dags, client availability patterns, and two quite different performance metrics, IC-optimal schedules significantly outperform schedules produced by popular heuristics, by as much as 10-20%.

No abstract available.

Earlier work has developed the underpinnings of the IC-scheduling theory, a framework for scheduling computations having intertask dependencies - modeled via directed acyclic graphs (DAGs) - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate, with the dual aim of 1) utilizing remote clients' computational resources well by always having work to allocate to an available client and 2) lessening the likelihood of a computation's stalling for lack of eligible tasks. The DAGs handled by the theory thus far are those that can be decomposed into a given collection of bipartite building block DAGs via the operation of DAG decomposition. A basic tool in constructing schedules is a relation >, which allows one to "prioritize" the scheduling of a complex DAG's building blocks. The current paper extends the IC-scheduling theory in two ways: by expanding significantly the repertoire of DAGs that the theory can schedule optimally and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the theory to schedule optimally, among other DAGs, a large range of DAGs that are either "expansive", in the sense that they grow outward from their sources, or "reductive", in the sense that they grow inward toward their sinks. The algorithmic shortcuts allow one to "read off" an optimal schedule for a DAG from a given optimal schedule for the DAG's dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks).

Techniques are developed for mapping structured data to an ensemble of parallel memory modules in a way that limits the number of conflicts, i.e., simultaneous accesses by distinct processors to the same memory module. The techniques determine, for any given conflict tolerance c, the smallest ensemble that allows one to store any n-node data structure "of type X" in such a way that no more than c nodes of a structure are stored on the same module. This goal is achieved by determining the smallest c-perfect universal graphs for data structures "of type X." Such a graph is the smallest graph that contains a homomorphic image of each n-node structure "of type X" with each node of the image holding < c nodes of the structure. In the current paper, "type X" refers to rooted binary trees and three array-like structures: chaotic arrays, ragged arrays, and rectangular arrays. For each of these families of data structures, the number of memory modules needed to achieve conflict tolerance c is determined to within constant factors.

It is often difficult to perform efficiently a collection of jobs with complex job dependencies due to temporal unpredictability of the grid. One way to mitigate the unpredictability is to schedule job execution in a manner that constantly maximizes the number of jobs that can be sent to workers. A recently developed scheduling theory provides a basis to meet that optimization goal. Intuitively, when the number of such jobs is always large, high parallelism can be maintained, even if the number of workers changes over time in an unpredictable manner. In this paper we present the design, implementation, and evaluation of a practical scheduling tool inspired by the theory. Given a DAGMan input file with interdependent jobs, the tool prioritizes the jobs. The resulting schedule significantly outperforms currently used schedules under a wide range of system parameters, as shown by simulation studies. For example, a scientific data analysis application, AIRSN, was executed at least 13% faster with 95% confidence. An implementation of the tool was integrated with the Condor high-throughput computing system

Earlier work has developed the underpinnings of a theory of scheduling computations having intertask dependencies - modeled via dags - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate. This goal aims: (a) to utilize remote clients’ computational resources well, by always having work to allocate to an available client; (b) to lessen the likelihood of the "gridlock" that ensues when a computation stalls for lack of eligible tasks. The dags handled by the theory thus far are those that can be constructed from a given collection of bipartite building-block dags via the operation of dagcomposition. The current paper extends the range of applicability of the theory by significantly expanding the repertoire of building-block dags that the scheduling algorithms can handle. Thereby, the theory can now schedule large classes of "expansive" and "reductive" dags optimally.

Conceptual and algorithmic tools are developed as a foundation for a theory of scheduling complex computation-dags for Internet-based computing. The goal of the schedules produced is to render tasks eligible for allocation to remote clients (hence, for execution) at the maximum possible rate. This allows one to utilize remote clients well, as well as to lessen the likelihood of the "gridlock" that ensues when a computation stalls for lack of eligible tasks. Earlier work has introduced a formalism for studying this optimization problem and has identified optimal schedules for several significant families of structurally uniform dags. The current paper extends this work via a methodology for devising optimal schedules for a much broader class of complex dags, which are obtained via composition from a prespecified collection of simple building-block dags. The paper provides a suite of algorithms that decompose a given dag /spl Gscr/ to expose its building blocks and an execution-priority relation /spl utri/ on building blocks. When the building blocks are appropriately interrelated under /spl utri/ the algorithms specify an optimal schedule for /spl Gscr/.

We present a game-theoretic model of the interactions between server and clients in a constrained family of commercial P2P computations (where clients are financially compensated for work). We study the cost of implementing redundant task allocation (redundancy, for short) as a means of preventing cheating. Under the assumption that clients are motivated solely by the desire to maximize expected profit, we prove that, within this framework, redundancy is cost effective only when collusion among clients, including the Sybil attack, can be prevented. We show that in situations where this condition cannot be met, non-redundant task allocation is much less costly than redundancy.

A "pebble game" is developed to model the process of scheduling computation-dags for Internet-based computing (IC, for short). Strategies are derived for scheduling three common, significant families of such dags for IC: reduction-meshes, which represent (the intertask dependencies of) computations that can be performed by "up-sweeps" of meshes; reduction-trees, which represent "accumulative" computations that can be performed by "up-sweeps" of trees; and FFT (fast fourier transform) dags, which represent a large variety of convolutional computations. Two criteria are used to assess the quality of a schedule: its memory requirements and its rate of producing tasks that are eligible for allocation to remote clients. These criteria are important because of, respectively, the typically enormous sizes of IC computations and the typical temporal unpredictability of remote clients in IC. In particular, a high production rate of eligible tasks decreases a computation's vulnerability to the gridlock that can occur when a computation stalls pending the return of intermediate results by remote clients. Under idealized assumptions, the schedules derived are optimal in the rate of producing eligible tasks and are either exactly or approximately optimal in memory requirements.

In this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS graph with that of graphs produced by topology generators that match the power-law degree distribution of the AS graph. We are guided by the existing notion that nodes in the AS graph can be placed in tiers with the resulting graph having an hierarchical structure. Our techniques are based on identifying graph nodes at each tier, decomposing the graph by removing such nodes and their incident edges, and thus explicitly revealing the interconnection structure of the graph. We define quantitative metrics to analyze and compare the decomposition of synthetic power-law graphs with the Internet-AS graph. Through experiments, we observe qualitative similarities in the decomposition structure of the different families of power-law graphs and explain any quantitative differences based on their generative models. We believe our approach provides insight into the interconnection structure of the AS graph and finds continuing applications in evaluating the representativeness of synthetic topology generators.

Summary form only given. By adding a computational component to the communication-oriented HiHCoHP model of Cappello et al., while specializing that model to a single heterogeneous cluster (HNOW, for short) built upon a single network, we obtain a model suitable for designing algorithms for an HNOW and analyzing these algorithms, either mathematically or via simulations. We describe this model and discuss the rationale for its detailed depiction of an HNOW's features and for the way it represents those features. We review two algorithmic studies that attest to the model's mathematical tractability and briefly discuss ongoing experimental work aimed at validating the model's predictive value.

Advances in technology have rendered the Internet a viable medium for employing multiple independent computers collaboratively in the solution of a single computational problem. A variety of mechanisms - e.g., Web-based computing, peer-to-peer computing, and grid computing - have been developed for such Internet-based computing (IC). Scheduling a computation for IC presents challenges that were not encountered with earlier modalities of parallel or distributed computing, especially when the computation's constituent tasks have interdependencies that constrain their order of execution. The process of scheduling such computations for IC is studied via a "pebble game" that abstracts the process of orchestrating the allocation of a computation's interdependent tasks to participating computers. A quality measure for plays of this game is developed that addresses the danger of "gridlock" in IC when a computation stalls because (due to dependencies) no tasks are eligible for execution. This measure rewards schedules that maximize the number of tasks that are eligible for execution at every step of the computation, one avenue for minimizing the likelihood of "gridlock." The resulting formal setting is illustrated via the problem of scheduling computations whose intertask dependencies have the structure of "evolving" meshes of finite dimensionalities. Within an idealized setting, a simple scheduling strategy is shown to be optimal when the dependencies have the structure of a two-dimensional mesh and within a constant factor of optimal for meshes of higher dimensionalities. The strategy remains optimal for a generalization of two-dimensional meshes whose structures are determined by abelian monoids (a monoid-based version of Cayley graphs). The optimality results for the idealized setting provide scheduling guidelines for real settings.

In recent years there has been considerable research on new distributed hash tables (DHTs), improvements on existing DHTs, and DHT-enabled systems. However, little of it focuses on their differences [M. Castro et al., 2002]. To this purpose we introduce a simple modeling framework that allows us to mathematically model the search costs of most classes of DHTs. To illustrate the usefulness of this framework, we examine a class of DHTs, which includes tapestry and pastry, that we call dynamic PRR meshes (DPMs). In particular we examine how planned object duplication (POD) strategies affect the search costs of DPMs that employ them. We introduce 3 new DPMs that employ different POD strategies and compare them with the POD strategies that tapestry and pastry use. Through our model we discover cyclic behaviors in search costs over the number of nodes present in the DPM, the effects of variability in the underlying network and provide comparisons of the performance of all 5 DPMs.

We prove that "FIFO" worksharing protocols provide asymptotically optimal solutions to a problem related to sharing a bag of identically complex tasks in a heterogeneous network of workstations (HNOW) n. In the HNOW-Exploitation Problem, one seeks to accomplish as much work as possible on n during a prespecified fixed period of L time units. The worksharing protocols we study are crafted within an architectural model that characterizes n via parameters that measure workstations' computational and communicational powers. The protocols are self-scheduling, in that they determine completely both an amount of work to allocate to each of n's workstations and a schedule for all related interworkstation communications. A protocol observes a FIFO regimen if it has n's workstations finish their assigned work, and return their results, in the same order in which they are supplied with their workloads. The optimality of FIFO protocols resides in the fact that they accomplish at least as much work as any other protocol during all sufficiently long worksharing episodes. Simulation experiments indicate that the superiority of FIFO protocols is often observed during worksharing episodes of only a few minutes' duration.

Web-based computing (WBC) is a modality of collaborative computing wherein "volunteers" register at a Web site, receiving one (usually compute-intensive) task to compute at each visit and returning the results from that task at the subsequent visit. The security of a WBC project is enhanced if the owner of the Web site can easily keep track of which "volunteer" computed which tasks, thereby endowing the project with accountability. We develop a framework for constructing computationally lightweight schemes for endowing WBC projects with accountability. The framework is built around the notion of a directly computed task allocation function (TAF) that reserves a dedicated subset of the Web site's tasks for each "volunteer." We show how TAFs simplify the data structures needed to link "volunteers" with their tasks, even when "volunteers" are allowed to join and leave the WBC project dynamically. We then design a methodology for constructing easily computed TAFs that enhance the efficiency of the accountability scheme.

We refine the model underlying our prior work on scheduling bag-of-tasks ("embarrassingly parallel") workloads via cycle-stealing in networks of workstations (S.N. Bhatt et al., 1997; A.L. Rosenberg, 1999), obtaining a model wherein the scheduling guidelines of Rosenberg produce optimal schedules for every such cycle-stealing opportunity. We thereby render prescriptive the descriptive model of those sources. Although computing optimal schedules usually requires the use of general function-optimizing methods, we show how to compute optimal schedules efficiently for the broad class of opportunities whose durations come from a concave probability distribution. Even when no such efficient computation of an optimal schedule is available, our refined model often suggests a natural notion of approximately optimal schedule, which may be efficiently computable. We illustrate such efficient approximability via the important class of cycle-stealing opportunities whose durations come from a heavy-tailed distribution. Such opportunities do not admit any optimal schedule, nor even a natural notion of approximately optimal schedule, within the model of Bhatt and Rosenberg. Within our refined model, though, we derive computationally simple schedules for heavy-tailed opportunities, which can be "tuned" to accomplish an expected amount of work that is arbitrarily close to optimal.

We craft protocols for solving two problems related to sharing a large partitionable bag-of-tasks workload in a heterogeneous network of workstations (NOW) N. In the NOW-Rental Problem, one must complete W units of work and wishes to rent N for as short a time as necessary. In the NOW-Exploitation Problem, one has access to N for L time units and wishes to accomplish as much work as possible. Our protocols are crafted within an architectural model that characterizes N via parameters that measure its workstations' computational and communicational efficiencies; hence, our solutions are robust across a broad range of actual NOWs. The protocols determine both an allocation of work for each of N's workstations and a schedule for transmitting that work; hence, they are self-scheduling. The schedules provide a value for either L or W, given the other, thereby solving both motivating problems. By studying two specific protocols, we prove that the intuitive strategy of supplying as much work as possible to faster workstations is not optimal; this nonoptimality is often discernible for values of L less than one minute.

A parameterized model of hyperclusters of processors-clusters of clusters of... of clusters of processors-is formulated under which a hypercluster enjoys generality along three orthogonal axes: (1) Its processors are heterogeneous: they may have different computational powers (speed of computation and memory access). (2) Its constituent clusters are interconnected via a hierarchy of networks of possibly differing bandwidths and speeds. (3) Its clusters at each level of the hierarchy are heterogeneous: they may differ in size. The model accounts for architectural details such as the bandwidths and transit costs of both networks and their ports. The algorithmic tractability of the model is demonstrated via broadcast and reduction algorithms, which are predictably efficient in general and actually optimal in special circumstances.

Hierarchies have long been used for organization, summarization, and access to information. In this paper we define summarization in terms of a probabilistic language model and use the definition to explore a new technique for automatically generating topic hierarchies by applying a graph-theoretic algorithm, which is an approximation of the Dominating Set Problem. The algorithm efficiently chooses terms according to a language model. We compare the new technique to previous methods proposed for constructing topic hierarchies including subsumption and lexical hierarchies, as well as the top TF.IDF terms. Our results show that the new technique consistently performs as well as or better than these other techniques. They also show the usefulness of hierarchies compared with a list of terms.

We study four augmentations of ring networks which are intended to enhance a ring's efficiency as a communication medium significantly, while increasing its structural complexity only modestly. Chordal rings add "shortcut" edges, which can be viewed as chords, to the ring. Express rings are chordal rings whose chords are routed outside the ring. Multirings append subsidiary rings to edges of a ring and, recursively, to edges of appended subrings. Hierarchical ring networks (HRN's) append subsidiary rings to nodes of a ring and, recursively, to nodes of appended subrings. We show that these four modes of augmentation are very closely related: 1) Planar chordal rings, planar express rings, and multirings are topologically equivalent families of networks with the "cutwidth" of an express ring translating into the "tree depth" of its isomorphic multiring and vice versa. 2) Every depth-d HRN is a spanning subgraph of a depth-(2d-1) multiring. 3) Every depth-d multiring /spl Mscr/ can be embedded into a d-dimensional mesh with dilation 3 in such a way that some node of /spl Mscr/ resides at a corner of the mesh. 4) Every depth-d HRN /spl Hscr/ can be embedded into a d-dimensional mesh with dilation 2 in such a way that some node of /spl Hscr/ resides at a corner of the mesh. In addition to demonstrating that these four augmented ring networks are grid graphs, our embedding results afford us close bounds on how much decrease in diameter is achievable for a given increase in structural complexity for the networks. Specifically, we derive upper and lower bounds on the optimal diameters of N-node depth-d multirings and HRN's that are asymptotically tight for large N and d.

We refine the model underlying our prior work on scheduling cycle-stealing opportunities in NOWs [5, 16], obtaining a model wherein the scheduling guidelines of [16] produce optimal schedules for every such opportunity. Although computing optimal schedules usually requires the use of general (often inefficient) function-optimizing methods, we show how to compute optimal schedules efficiently for the broad class of opportunities whose durations come from a concave probability distribution. Even when no such efficient computation of an optimal schedule is available, our refined model always suggests a natural notion of approximately optimal schedule, which may be efficiently computable. We illustrate such efficient approximability via the important class of cycle-stealing opportunities whose durations come from a heavy-tailed distribution. Such opportunities do not admit any optimal schedule—nor even a natural notion of approximately optimal schedule—within the model of [5, 16]. Within our refined model, though, we derive computationally simple schedules for heavy-tailed opportunities, which can be “tuned” to have expected work-output that is arbitrarily close to optimal.

Modern hardware and software systems promote a view of parallel systems in which interprocessor communications are uniform and rather expensive in cost. Such systems demand efficient clustering algorithms that aggregate atomic tasks in a way that diminishes the impact of the high communication costs. We develop here a linear-time algorithm that optimally clusters computations that comprise a sequence of disjoint complete up- and/or down-sweeps on a complete binary tree for such parallel environments. Such computations include, for instance, those that implement broadcast, accumulation, and the parallel-prefix operator; such environments include, for instance, networks of workstations or BSP-based programming systems. The schedules produced by our clustering are optimal in the sense of having the exact minimum makespan-not just an approximation thereof-accounting for both computation and communication time. We show by simulation that the makespans of the schedules produced by our algorithm are close to half of those produced by the algorithm that yielded the best schedules previously known.

We illustrate the potential of techniques and results from the theory of network emulations to enhance the performance of a parallel architecture. The vehicle for this demonstration is a suite of algorithms that endow an N-processor bit-serial processor array A with a "meta-instruction" GAUGE k, which (logically) reconfigures A into an N/k-processor virtual machine B/sub k/ that has: 1) a datapath and memory bus whose emulated width is k bits, as opposed to A's 1-bit width and 2) an instruction set that operates on k-bit words, in contrast to A's instruction set, which operates on 1-bit words. In order to stress the strength of the approach, we show (via pseudocode) how our emulation techniques can be implemented efficiently even if A operates in strict SIMD mode, with only single-bit masking capabilities and with no indexed memory accesses. We describe at an algorithmic level how to implement our technique-including datapath conversion ("corner-turning") and the creation of the word-parallel instruction sets-on arrays of any regular network topology. We instantiate our technique in detail for arrays based on topologies with quite disparate characteristics: the hypercube, the de Bruijn network, and a genre of mesh with reconfigurable buses. Importantly, the emulations that underlie our technique do not alter the native machine's instruction set, hence allowing an invariant programming model across gauges.

We study the problem of centrally scheduling multiple messages in a linear network, when each message has both a release time and a deadline.We show that the problem of transmitting optimally many messages is NP-hard, both when messages may be buffered in transit and when they may not be; for either case, we present efficient algorithms that produce approximately optimal schedules.In particular, our bufferless scheduling algorithm achieves throughput that is within a factor of two of optimal.We show that buffering can improve throughput in general by a logarithmic factor (but no more), but that in several significant special cases, such as when all messages can be released immediately, buffering can help by only a small constant factor.Finally, we show how to convert our centralized, offline bufferless schedules to equally productive fully

This paper considers two properties of graphs, one geometrical and one topological, and shows that they are strongly related. Let G be a graph with four distinguished and distinct vertices, w 1 , w 2 , b 1 , b 2 . Consider the two properties, TRI + (G) and MONO(G), defined as follows. TRI + (G): There is a planar drawing of G such that all 3-cycles of G are faces; all faces of G are triangles except for the single face which is the 4-cycle (w 1 -b 1 -w 2 -b 2 -w 1 ). MONO(G): G contains the 4-cycle (w 1 -b 1 -w 2 -b 2 -w 1 ) and, for any labeling of the vertices of G by the colors {white, black} such that w 1 and w 2 are white, while b 1 and b 2 are black, precisely one of the following holds. There is a path of white vertices connecting w 1 and w 2 . There is a path of black vertices connecting b 1 and b 2 . Our main result is that a graph G enjoys property TRI + (G) if and only if it is minimal with respect to property MONO. Building on this, we show that one can decide in polynomial time whether or not a given graph G has property MONO(G).

In this paper, we study the problem of emulating T G steps of an N G -node guest network, G, on an N H -node host network, H.We call an emulation work-preserving if the time required by the host, T H , is O(T G N G /N H ), because then both the guest and host networks perform the same total work (i.e., processor-time product), ⌰(T G N G ), to within a constant factor.We say that an emulation occurs in real-time if T H ϭ O(T G ), because then the host emulates the guest with constant slowdown.In addition to describing several work-preserving and real-time emulations, we also provide a general model in which lower bounds can be proved.Some of the more interesting and diverse consequences of this work include:(1) a proof that a linear array can emulate a (much larger) butterfly in a work-preserving fashion, but that a butterfly cannot emulate an expander (of any size) in a work-preserving fashion,(2) a proof that a butterfly can emulate a shuffle-exchange network in a real-time work-preserving fashion, and vice versa,(3) a proof that a butterfly can emulate a mesh (or an array of higher, but fixed, dimension) in a real-time work-preserving fashion, even though any O(1)-to-1 embedding of an N-node mesh in an N-node butterfly has dilation ⍀(log N), and (4) simple O(N 2 /log 2 N)-area and O(N 3/ 2 /log 3/2 N)-volume layouts for the N-node shuffle-exchange network.

We study the parallel scheduling problem for a new modality of parallel computing: having one workstation "steal cycles" from another. We focus on a draconian mode of cycle-stealing, in which the owner of workstation B allows workstation A to take control of B's processor whenever it is idle, with the promise of relinquishing control immediately upon demand. The typically high communication overhead for supplying workstation B with work and receiving its results militates in favor of supplying B with large amounts of work at a time; the risk of losing work in progress when the owner of B reclaims the workstation militates in favor of supplying B with a sequence of small packets of work. The challenge is to balance these two pressures in a way that maximizes the amount of work accomplished. We formulate two models of cycle-stealing. The first attempts to maximize the expected work accomplished during a single episode, when one knows the probability distribution of the return of B's owner. The second attempts to match the productivity of an omniscient cycle-stealer, when one knows how much work that stealer can accomplish. We derive optimal scheduling strategies for sample scenarios within each of these models.

We study fine-grain computation on the Reconfigurable Ring of Processors (RRP), a parallel architecture whose processing elements (PEs) are interconnected via a multiline reconfigurable bus, each of whose lines has one-packet width and can be configured, independently of other lines, to establish an arbitrary PE-to-PE connection. We present a "cooperative" message passing protocol that will, in the presence of suitable implementation technology, endow an RRP with message latency that is logarithmic in the number of PEs a message passes over in transit. Our study focuses on the computational consequences of such latency in such an architecture. Our main results prove that: (1) an N-PE RRP can execute a sweep up or down an N-leaf complete binary tree in time proportional to log N log log N;(2) a broad range of N-PE architectures, including N-PE RRPs, require time proportional to log N log log N to perform such a sweep.

We establish upper and lower bounds on the layout area of the butterfly network, which differ only in low-order terms. Specifically, the N-input, N-output butterfly network can be laid out in area (1 + o(1)) N^2, while no layout of the network can have area smaller than (1 - o(1)) N^2. These results improve both the known upper bound and the known lower bound on the area of butterfly network layouts.

Article Free Access Share on On trading task reallocation for thread management in partitionable multiprocessors Authors: Lixin Gao Department of Computer Science, University of Massachusetts, Amherst, Mass. Department of Computer Science, University of Massachusetts, Amherst, Mass.View Profile , Arnold L. Rosenberg Department of Computer Science, University of Massachusetts, Amherst, Mass. Department of Computer Science, University of Massachusetts, Amherst, Mass.View Profile , Ramesh K. Sitaraman Department of Computer Science, University of Massachusetts, Amherst, Mass. Department of Computer Science, University of Massachusetts, Amherst, Mass.View Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 309–317https://doi.org/10.1145/237502.237575Published:24 June 1996Publication History 0citation155DownloadsMetricsTotal Citations0Total Downloads155Last 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 SiteeReaderPDF

Have1 and Liebl [1973], and Leighton 119841.' The networks of interest are defined in section 1.3.' For any graph 53, we denote by (%I the number of nodes in %.

We study a combinatorial problem that is motivated by “client–server” schedulers for parallel computations. Such schedulers are often used, for instance, when computations are being done by a cooperating network of workstations. Our results expose and quantify a control–memory trade-off for such schedulers, when the computation being scheduled has the structure of a binary tree, with all arcs oriented either root-toward-leaves or leaves-toward-root. The combinatorial problem for the root-toward-leaves case takes the following form. (The leaves-toward-root case gives rise to a dual formulation, which yields the same trade-offs.) Consider, for integersk,N> 0, an algorithm that employskFIFO queues in order to schedule anN-leaf binary tree in such a way that each nonleaf node of the tree is executed before its children. We establish a trade-off between the number of queues used by the algorithm—which we view as measuring thecontrol complexityof the algorithm—and thememory requirementsof the algorithm, as embodied in the required capacity of the largest-capacity queue. Specifically, for each integerk∈ {1, 2, ..., log2N}, letQk(N) denote the minimax per-queue capacity for ak-queue algorithm that schedules allN-leaf binary trees; letQ*k(N) denote the analogous quantity forcompletebinary trees. We establish the following bounds: For generalN-leaf binary trees, for allk, [formula]≤Qk(N) ≤ 2N1/k+ 1. For complete binary trees, we derive tighter bounds. We prove that for all constantk, Q*k(N) = Θ[formula]. For generalk, we obtain the following bounds: [formula]≤Q*k(N) ≤ (4k)1−1/k[formula]. Similar trade-offs are readily established for trees of any fixed branching factor.

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.

A salvage-embedding (S-embedding) maps an M-leaf complete binary tree into $\mathcal{G}$ an ($N > M$)-leaf complete binary tree $\mathcal{H}$, the fraction G of whose leaves have been labeled GOOD. The S-embedding maps leaves of $\mathcal{G}$ one-to-one to GOOD leaves of $\mathcal{H}$; it may be many-to-one on internal nodes. The quality of an S-embedding depends on its harvest, the ratio $H\mathop = \limits^{def} M/GN$, and its congestion, the largest number of edges $\mathcal{G}$ that get “routed” across the same edge of $\mathcal{H}$. We study three scenarios. In the worst-case scenario, given any target harvest $H \leq \frac{1}{2}$, one can S-embed a $2^{\lfloor {\log ( HGN )} \rfloor }$-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $\log \log N + $ a constant depending only on G and H, no matter how the GOOD leaves are distributed; this congestion cannot be lowered by more than a small constant factor. In the expected-case scenario—where leaves of $\mathcal{H}$ are labeled GOOD or not, independently, with fixed probability—with probability exceeding $1 - N^{ - \Omega ( 1 )} $, for any target harvest $H \leq 1/8$, one can S-embed a $2^{\lfloor {HN} \rfloor } $-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $O( \log \log \log N )$. In the salvaging scenario, we present an algorithm that, in time $O( CN ( \log N )^{3C + 2} )$, S-embeds in a given a leaf-labeled $\mathcal{H}$ the largest possible $\mathcal{G}$, subject to the prespecified bound C on congestion. This work is inspired by the problem of salvaging a fault-free subnetwork of a leaf-tree machine—a tree architecture whose leaves hold “full-power” processors and whose nonleaf nodes hold “rudimentary” processors that route messages and perform simple combining tasks.

We study a combinatorial problem that is motivated by '(client-server" schedulers for networks of

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.>

The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications overhead. In this paper it is shown that every bounded-degree tree can be simulated on the hypercube with constant communications overhead. In fact, the proof shows that every bounded-degree graph with an $O(1)$-separator can be embedded in a hypercube of the same size with dilation and congestion both $O(1)$. It is also proved that not all bounded-degree graphs can be efficiently embedded within the hypercube.

The problem of laying out the edges of a graph using queues is studied. In a k-queue layout, vertices of the graph are placed in some linear order and each edge is assigned to exactly one of the k queues so that the edges assigned to each queue obey a first-in/first-out discipline. This layout problem abstracts a design problem of fault-tolerant processor arrays, a problem of sorting with parallel queues, and a problem of scheduling parallel processors. A number of basic results about queue layouts of graphs are established, and these results are contrasted with their analogues for stack layouts of graphs (the book-embedding problem). The 1-queue graphs (they are almost leveled-planar graphs) are characterized. It is proved that the problem of recognizing 1-queue graphs is NP-complete. Queue layouts for some specific classes of graphs are given. Relationships between the queuenumber of a graph and its bandwidth and separator size are presented. An apparent tradeoff between the queuewidth and the number of queues allowed in layouts of complete binary trees is indicated.

The relative powers of queues and stacks are compared as mechanisms for laying out the edges of a graph. In a k-queue layout, vertices of the graph are placed in some linear order (also called a linear arrangement), and each edge is assigned to exactly one of the k queues, so that the edges assigned to each queue obey a first-in/first-out (FIFO) discipline. As the vertices are scanned left to right, an edge is enqueued on its assigned queue when its left endpoint is encountered and is dequeued from its queue when its right endpoint is encountered. In a k-stack layout, vertices of the graph are placed in some linear order, and each edge is assigned to exactly one of the k stacks so that the edges assigned to each stack obey a last-in/first-out discipline. As the vertices are scanned left to right, an edge is pushed on its assigned stack when its left endpoint is encountered and is popped from its stack when its right endpoint is encountered. The paper has three main results. First, a tradeoff between queuenumber and stacknumber is shown for a fixed linear order of the vertices of G. In particular, for a fixed-order layout of a graph G, \[ {\text{queuenumber }} \times {\text{ stacknumber }} \geq {\text{ cutwidth/valence }}( G ).\] Second, it is shown that every 1-queue graph has a 2-stack layout and that every 1-stack graph has a 2-queue layout. Third, in a surprising display of the power of queues, it is shown that the ternary hypercube requires exponentially more stacks than queues. More precisely, an N-vertex ternary hypercube has a $( 2\log _3 N )$-queue layout but requires $\Omega ( N^{1/9 - \epsilon } )$ stacks, $\epsilon > 0$, in any stack layout. Also, some asymptotic bounds for the queuenumber of bounded-valence graphs are derived.

The authors develop an algebraic framework that exposes the structural kinship among the deBruijn, shuffle-exchange, butterfly, and cube-connected cycles networks and illustrate algorithmic benefits that ensue from the exposed relationships. The framework builds on two alge-braically specified genres of graphs: A group action graph (GAG, for short) is given by a set V of vertices and a set $\Pi$ of permutations of V : For each $v \in V$ and each $\pi \in \Pi$, there is an arc labeled $\pi$ from vertex v to vertex $v \pi$. A Cayley graph is a $\operatorname{GAG}(V, \Pi)$, where V is the group ${\bf {\operatorname{Gr}}}(\Pi)$ generated by $\Pi$ and where each $\pi \in \Pi$ acts on each $g \in {\bf {\operatorname{Gr}}} (\Pi)$ by right multiplication. The graphs $({\bf {\operatorname{Gr}}}(\Pi), \Pi)$ and $(V, \Pi)$ are called associated graphs. It is shown that every ${\operatorname{GAG}}$ is a quotient graph of its associated Cayley graph. By applying such general results, the authors determine the following: • The butterfly network (a Cayley graph) and the deBruijn network (a ${\operatorname{GAG}}$) are associated graphs. • The cube-connected cycles network (a Cayley graph) and the shuffle-exchange network (a ${\operatorname{GAG}}$) are associated graphs. • The order-n instance of both the butterfly and the cube-connected cycles share the same underlying group, but have slightly different generator sets $\Pi$. By analyzing these algebraic results, it is delimited, for any Cayley graph $\mathcal{G}$ and associated $\operatorname{GAG} \mathcal{H}$, a family of “leveled” algorithms which run as efficiently on $\mathcal{H}$ as they do on (the much larger) $\mathcal{G}$. Further analysis of the results yields new, surprisingly efficient simulations by the shuffle-oriented networks (the shuffle-exchange and deBruijn networks) of like-sized butterfly-oriented networks (the butterfly and cube-connected cycles networks): • An N-vertex butterfly-oriented network can be simulated by the smallest shuffle-oriented network that is big enough to hold it with slowdown $O(\log \log N)$. This simulation is exponentially faster than the anticipated logarithmic slowdown. The mappings that underlie the simulation can be computed in linear time; and they afford one an algorithmic tech-nique for translating any program developed for a butterfly-oriented architecture into an equivalent program for a shuffle-oriented architecture, the latter program incurring only the indicated slowdown factor.

In this paper, we study the problem of emulating TG steps of an NG-node guest network on an NH-node host network. We call an emulation work-preserving if the time required by the host, TH, is Ο(TGNG/NH) because then both the guest and host networks perform the same total work, Θ(TGNG), to within a constant factor. We say that an emulation is real-time if TH = Ο(TG), because then the host emulates the guest with constant delay. Although many isolated emulation results have been proved for specific networks in the past, and measures such as dilation and congestion were known to be important, the field has lacked a model within which general results and meaningful lower bounds can be proved. We attempt to provide such a model, along with corresponding general techniques and specific results in this paper. Some of the more interesting and diverse consequences of this work include:

How small can a graph be that contains as subgraphs all trees on n vertices with maximum degree d? In this paper, this question is answered by constructing such universal graphs that have n vertices and bounded degree (depending only on d). Universal graphs with n vertices and $O(n\log n)$ edges are also constructed that contain all bounded-degree planar graphs on n vertices as subgraphs. In general, it is shown that the minimum universal graph containing all bounded-degree graphs on n vertices with separators of size $n^\alpha $ has $O(n)$ edges if $\alpha < \frac{1}{2}$; $O(n\log n)$ edges if $\alpha = \frac{1}{2}$; $O(n^{2\alpha } )$ edges if $\alpha > \frac{1}{2}$.

A new measure of the complexity of a book-embedding of a simple undirected graph, the number of vertex types in the embedding, is studied. The type of a vertex $v $ in a p-page book-embedding is the $p \times 2$ matrix of nonnegative integers \[ \tau (v ) = \begin{pmatrix} L_1 & & R_1 \\ L_2 & & R_2 \\ & \vdots & \\ L_P & & {R_P } \end{pmatrix}, \] where $L_i $; (respectively, $R_i $) is the number of edges incident to $v $ that connect on page i to vertices lying to the left (respectively, to the right) of $v $. The number of types in a book-embedding relates to the amount of logic necessary to realize fault-tolerant arrays of processors using one specific design methodology. Three sorts of issues regarding vertex types in book-embeddings are studied. A number of techniques for bounding the type-numbers of a variety of graphs are developed; the relationships between typenumber and other graph properties, such as book thickness, are investigated; and the problem of minimizing the typenumber of a graph is considered. Finding that problem to be NP-complete, the problem of finding a (cyclic) rotation of a given book-embedding that minimizes the number of vertex types is studied.

Article Free Access Share on Optimal simulations by Butterfly Networks Authors: Sandeep Bhatt Department of Computer Science, Yale University, New Haven, CT Department of Computer Science, Yale University, New Haven, CTView Profile , Fan Chung Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJ Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJView Profile , Jia-Wei Hong Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NY Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NYView Profile , Arnold Rosenberg Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 192–204https://doi.org/10.1145/62212.62229Published:01 January 1988Publication History 24citation283DownloadsMetricsTotal Citations24Total Downloads283Last 12 Months20Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of realizing an idealized parallel architecture on a (possibly fault-laden) physical architecture is studied. Our formulation performs the mapping in the light of the algorithm that one wants to implement on the idealized architecture. A version of the mapping algorithm suggested by the DIOGENES methodology for designing fault-tolerant VLSI processor arrays is settled definitely. Two quality metrics for mappings are considered, the first embodying an idealized notion of average delay , which relates to power consumption, and the second being the length of the longest run of wire . For the average-delay measure, four algorithms that optimally assign the m vertices of the embedded graph to the n fault-free processors that have been fabricated are presented. The most general algorithm makes no assumptions about the structure of the array or the physical format of the processors; it runs in time O ( m · ( n - m ) 2 ). The other algorithms assume that the processors are laid out in such a way that interprocessor distances obey the triangle equality; they run in times ranging from time O (max{ m , n - m } · log min { m, n - m }) for certain array structures, including linear arrays, to time O (max{ m, n - m }) for a narrow class of array structures, including pyramid arrays. For the max-wire-run cost measure, it is shown that the problem of finding cost-optimal vertex-to-processor assignments is NP-complete. However, an algorithm is presented that yields, in time O ( m · ( n - m ) 2 ), vertex-to-processor assignments that are within a factor of 3 of optimal (they are optimal when the input graph-embedding is outplanar). This algorithm can easily be converted to one that yields, in time O ( m · ( n - m ) 3 ), vertex-to-processor assignments that are within a factor of 2 of optimal. Finally, an algorithm that yields optimal assignments when the interprocessor distances obey the triangle equality is presented; this algorithm operates in time O ( m · ( n - m ) · log( m · ( n - m )) · log M ), where M is the largest interprocessor distance.

Universal networks offer the advantage that they can execute programs written for simpler architectures without significant run-time overhead. In this paper we investigate simulations of tree machines; the fact that divide-and-conquer algorithms are programmed naturally on trees motivates our investigation. Among various proposals for parallel computing the boolean hypercube has emerged as a particularly versatile network. It is well known that programs for multidimensional grid machines, for example, can be executed on a hypercube with no communications overhead by embedding the grid as a subgraph of the hypercube. Our first result is that a program for any tree machine can be executed on the hypercube with constant overhead. More precisely, every cycle of a synchronous binary tree can be simulated in O(1) cycles on a hypercube, independent of the shape of the tree. The algorithm to embed the tree within the hypercube runs in polynomial time. We also give efficient simulations of arbitrary binary trees on the complete binary tree, the FFT and shuffle-exchange networks. It is natural to ask if any sparse network can simulate every binary tree efficiently. Somewhat surprisingly, we construct a universal bounded-degree network on N nodes for which every N node binary tree is a spanning tree. In other words, every binary tree can be simulated on our universal network with no overhead. This improves previous bounds on the sizes of universal graphs for trees.

Recent advances in fabrication technology have rendered imminent the fabrication of multilayer (i.e., three-dimensional) chips, wafers, and packages. In this paper, we examine the savings in material (as measured by Area in a two-dimensional medium and Volume in a three-dimensional one) and in communication time (as measured by the length of the longest uninterrupted run of wire) afforded by this developing technology. We derive close upper and lower bounds on the efficiency with which circuits can be realized in a multilayer medium, based on the sizes of the smallest bifurcators of the circuit. We find that the smallest Volume of any three-dimensional layout of an N-device circuit is no more than (roughly) $(NA)^{{1 / 2}} $, where A is the smallest Area of any two-dimensional layout of the circuit. We then refine our layout techniques so that we can deal with multilayer layouts having a fixed numberr of layers. We find that we can efficiently transform a two-dimensional layout of Area A and Maximum Wire Run R into a three-dimensional layout of Volume (roughly) $V = {A / H}$ and Maximum Wire Run $R^ * = {R / H}$ for moderate numbers of layers H. Two noteworthy features of the study are: (1) that, within logarithmic factors, the indicated savings can be realized with layouts that use the third dimension only for interconnect; and (2) that the indicated savings can be realized algorithmically: we present polynomial-time algorithms that transform a given two-dimensional layout into a more efficient three-dimensional one.

We study here a formal version of a strategy for constructing fault-tolerant VLSI processor arrays in an environment of wafer-scale integration. The strategy achieves tolerance to faults by running buses past the implemented PE's and interconnecting the fault-free ones into an array of the desired structure by having PE's tap into the bank of buses. Earlier studies [12] have shown this strategy to be competitive with more familiar strategies, particularly given the availability of laser-welding technology. We study here fault-tolerant implementation of linear arrays and tree-structured arrays, deriving both upper and lower bounds on the area required to lay out the fault-tolerant arrays. We also consider briefly the issue of wire lengths.

We investigate three cost measures for the recently introduced brother search trees. In particular we characterize node visit optimal, comparison-cost optimal and space-cost optimal 1-2 brother trees and present linear-time algorithms to construct optimal 1-2 brother trees for each cost measure. Furthermore we also consider, briefly, these cost measures for brother leaf search trees.

An embedding of the graph G in the graph H is a one-to-one association of the vertices of G with the vertices of H.There are two natural measures of the cost of a graph embedding, namely, the dilationcost of the embedding: the maximum distance in H between the images of vertices that are adjacent in G; and the expansion-cost of the embedding: the ratio of the size of H to the size of G.The main results of this paper illustrate three situaUons wherein one of these costs can be minimized only at the expense of a dramatic increase in the other cost.The first result establishes the following: There is an embedding of n-node complete ternary trees in complete binary trees with dilation-cost 2 and expansion cost O(n~), where ~ = 1og3(4/3); but any embedding of these ternary trees in binary trees that has expansion-cost c < 2 must have dilation-cost G(logloglogn).The second result provides a stronger but less easily stated example of the same type of trade-off.The third result concerns generic binary trees, that is, complete binary trees into which all n-node binary trees are "efficiently" embeddable.There is a generic binary tree into which all n-node binary trees are embeddable with dilauon-cost O(1) and expansion-cost O(n ~) for some fixed constant c; if one insists on embeddings whose dilation-cost is exactly 1, then these embeddings must have expansion-cost f~(n¢~°*~)/~); tf one insists on embeddmgs whose expansion-cost is less than 2, then these embeddings must have dilation cost ~(log log log n) An interesting application of the polynomial size genenc binary tree m the first part of this three-part result is to yield simplified proofs of several results concerning computational systems with an intrinsic nouon of "computation tree," such as alternating and nondeterministic Turing machines and context-free grammars.

The advantages of three-dimensional c~rcmts are studied by comparing sample three-dimensional reahzauons of certain common families of c~rcmts, namely, permutation networks, FFT circmts, and complete binary trees, with the famd~es' optunal two-dtmens~onal reahzatlons.These circuits are then used as building blocks to obtain efficient three-dimensional realizations of arbitrary circuits.The results obtained indicate (roughly) that bounds on area (both upper and lower) in the neighborhood of order n 2 m the two-dtmens~onal case translate to bounds on volume m the neighborhood of order n a/2 m the three-dimensional case.Moreover, several of the upper bounds are attainable using (idealized) realizations that have actwe devices on only one level and that use the third dimension only for wirerouting, such reahzauons place fewer demands on the fabrication technology.However, it is also shown that unrestricted use of the third dimension can y~eld reallzauons that are more conservative of volume (by the factor log~/2n) than any "one-actwe-level" reallzauon can be.Finally, examples are presented whereto two-dunenslonal reahzaUons reqmre dewce-to-dewce wire lengths as large as n/logn, whde eqmvalent three-dLmens~onal reahzatlons can get by w~th wire lengths not exceeding n ~/2.Thus, at least in the worst case, there are substantive savings from three-dLmens~onal circuit realizations, in both material (area versus volume) and tune (wire length) Categories and SubJect Descnptors B.2.m [Arithmetic and Logic Structures]: Miscellaneous; B.7 1 [Integrated Circuits]: Types and Design Styles--VLS1; F 2.2 [Analysis of Algorithms and Problem Complexity].Nonnumencal Algorithms and Problems--routing and layout

One has a shift register of length n and a collection of designated subsets of {0, 1,···, n-1}. The problem is to devise a method for feeding a string of bits into the shift register in such an order that, for each designated subset S = {k1,···, kr}, if one keeps track of the bit patterns appearing at the corresponding positions k1, ···, krof the shift register, all 2r possible bit patterns will ultimately appear at those positions. A simple and efficient solution to this problem, derived from the connections between polynomials over finite fields and linear feedback shift registers, is presented. Applications of this solution to the problem of VLSI self-testing are discussed and illustrated.

This paper describes by a series of examples a strategy for designing testable fault-tolerant arrays of processors. The strategy achieves fault tolerance by introducing redundancy in an array's communication links rather than in its processing elements (PE's). The major characteristics of the designs produced are as follows.

This paper studies embeddings of graphs in binary trees. The cost of such an embedding is the maximum distance in the binary tree between images of adjacent graph vertices. Several techniques for bounding the costs of such embeddings from above are derived; notable among these is an algorithm for embedding any outerplanar graph in a binary tree with a cost that is within a factor of 3 of optimal. A number of techniques for bounding the costs of such embeddings from below are developed; notable here are two techniques for inferring the presence of large separators in graphs. Finally, a number of characterizations are established of those families of graphs that are almost binary trees, in the sense that every graph in the family is embeddable in a binary tree within bounded cost.

The main results in this paper demonstrate that there exist pairs of integers 〈E, D〉 (for "area Expansion" and "edge Dilation," respectively) such that any n-vertex rectangular grid can be embedded into a square grid having at most En vertices, in such a way that images in the square grid of vertices that are adjacent in the rectangular grid are at most distance D apart. Several techniques for "squaring"-up rectangular grids are presented; sample values for the parameter-pair 〈E, D〉 are: 〈E = 1.2, D = 15〉, 〈E = 1.45, D = 9〉, 〈E = 1.8, D = 3〉. Note that these values of E and D hold for all rectangular grids, independent of number of vertices. The quest for these results was motivated by the question of whether or not one could automatically "square up" circuit layouts having aspect ratios very far from unity, without compromising the efficiency of the layout (in terms of area and length of the longest run of wire). The results reported here yield an affirmative answer to this question, at least in an idealized setting. One corollary of the embeddings presented here is that the side-2n½ square "king's-move" grid contains as a subgraph every n-vertex rectangular grid. Another way to think of this result is that this embellished grid can be "programmed" or "personalized," by setting switches, to represent any n-vertex rectangular grid.

We present the design of a dictionary machine that is suitable for VLSI implementation, and we discuss how to realize this implementation efficiently. The machine supports the operations of SEARCH, INSERT, DELETE, and EXTRACTMIN on an arbitrary ordered set. Each of these operations takes time O(log n), where n is the number of entries present when the operation is performed. Moreover, arbitrary sequences of these instructions can be pipelined through the machine at a constant rate (i.e., independent of n and the capacity of the machine). The time O(log n) is an improvement over previous VLSI designs of dictionary machines which require time O(log N) per operation, where N is the maximum number of keys that can be stored.

This paper studies embeddings of graphs in binary trees. The cost of such an embedding is the maximum distance in the binary tree between images of adjacent graph vertices. Several techniques for bounding the costs of such embeddings from above are derived; notable among these is an algorithm for embedding any outerplanar graph in a binary tree with a cost that is within a factor of 3 of optimal. A number of techniques for bounding the costs of such embeddings from below are developed; notable here are two techniques for inferring the presence of large separators in graphs. Finally, a number of characterizations are established of those families of graphs that are almost binary trees, in the sense that every graph in the family is embeddable in a binary tree within bounded cost.

A B-tree is compact if it is minimal in number of nodes, hence has optimal space utilization, among equally capacious B-trees of the same order. The space utilization of compact B-trees is analyzed and compared with that of noncompact B-trees and with (node)-visit-optimal B-trees, which minimize the expected number of nodes visited per key access. Compact B-trees can be as much as a factor of 2.5 more space efficient than visit-optimal B-trees; and the node-visit cost of a compact tree is never more than 1 + the node-visit cost of an optimal tree. The utility of initializing a B-tree to be compact (which initialization can be done in time linear in the number of keys if the keys are presorted) is demonstrated by comparing the space utilization of a compact tree that has been augmented by random insertions with that of a tree that has been grown entirely by random insertions. Even after increasing the number of keys by a modest amount, the effects of compact initialization are still felt. Once the tree has grown so large that these effects are no longer discernible, the tree can be expeditiously compacted in place using an algorithm presented here; and the benefits of compactness resume.

The use of external hashing schemes for storing broad classes of data structures is studied The general framework of the paper considers a class of data structures parutioned into smaller classes by the number of positions m the structure For instance, one could start with the class of all binary trees and partiuon that class into the subclasses ~, % ..... each q¢~ comprising all n-node binary trees.The mare results establish nonconstructively the existence of an external hashing scheme h,, with O(n) storage demand and O(1) expected access time that will store any structure in % O q¢2 U ... U %, provtded ten contains a number of structures growing at most exponenttally m n Classes of data structures subsumed by these results include ragged arrays, binary trees, stringindexed arrays, and refmable arrays

A B-tree is compact if it is minimal in number of nodes, hence has optimal space utilization, among equally capacious B-trees of the same order. The space utilization of compact B-trees is analyzed and is compared with that of noncompact B-trees and of (node)-visit-optimal B-trees, which minimize the expected number of nodes visited per key access. Compact B-trees can be as much as a factor of 2.5 more space-efficient than visit-optimal B-trees; and the node-visit cost of a compact tree is never more than 1 + the node-visit cost of an optimal tree. Finally, an in-place compactification algorithm is presented which operates in linear time in the size of the file.

We review the motivation underlying the study of data encodings and the formal framework of the study. We then present a series of results whose main message is that (complete) trees are materially less congenial storage representations for tree-like data structures than they have been shown to be for array-like data structures. In response to these results, we propose a new data structure, called a dree, which we show to share the advantages of trees, but not to suffer their disadvantages, when used as a storage structure.

The notion of a data encoding is meant to be a formal counterpart of the informal notion of the translauon of a logical data structure into a physical storage structure Both kinds of structures are represented here by graphs, and an encoding is a type of embedding of the guest (logical structure) graph in the host (physical structure) graph The cost of an encoding is the average amount that the edges of the guest graph are stretched as they are replaced by paths m the host graph via the encoding, the average is weighted by a probability distribution (called a "usage pattern") on the edges of the guest graph, that is intended to represent the anticipated pattern of traversing that graph This paper studms encodmgs of data structures in trees, with an eye toward developing techniques for analyzing such encodlngs.Two guest structures are studied here, namely, lines and arrays Upper and lower bounds on the costs of encodmgs of these structures in trees are derived, in several cases these bounds are asymptotically coincident, or at least very close The main results concerning line-guests exhibit certain (best possible) sufficient conditions for the costs of encodmgs of lines in trees to be independent of the lengths of the lines The mare results concerning array-guests are exemplified by the foUowmg The costs of encodlngs of d-dimensional arrays m 2a-ary trees are shown to have colnodent upper and lower bounds of 4 + o(1), and the costs of encodlngs of such arrays in binary trees are shown to have upper and lower bounds of 3d + 1 + o(I) and 2 885d + I + 0 116/d + o(1), respectively, for the case d = 2, the derived bounds are even closer than this general result would suggest the upper and lower bounds for encodmgs of 2-dimensional arrays in binary trees are 7 + o(i) and 6 98 + o(I), respectwely KEY WORDS AND PHRASES data encoding, data representation, complexity of data representaUon, data structure, graph embedding, storage structure, storage representations for (extendJble) arrays, storage representations for data structures CR CATEGORIES 4.34, 5 25, 5 32

The 2,3-trees that are optimal in the sense of having minimal expected number of nodes visited per access are characterized in terms of their “profiles”. The characterization leads directly to a linear-time algorithm for constructing a K-key optimal 2,3-tree for a sorted list of K keys. A number of results are derived that demonstrate how different in structure these optimal 2,3-trees are from their “average” cousins.

Those 2,3-trees that are minimal in expected number of comparisons per access for a given number of keys are characterized. The characterization yields directly a linear-time algorithm for constructing a minimal-comparison 2,3-tree for a given sorted set of keys. Regrettably, the property of comparison minimality is incompatible with the earlier-studied property of node-visit optimality. Specifically, the two types of optimality can coexist in a K-key 2,3-tree only for sixteen values of K, none exceeding 32. In contrast, comparison-minimal node-visit-pessimalK-key 2,3-trees exist for just over half the possible values of K.

The use of hashing schemes for storing extendible arrays is investigated. It is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely hashing schemes that utilize storage too conservatively are inevitably poor in expected access time. If requirements for the utilization of storage are relaxed slightly, then one can find rather efficient extendible hashing schemes. Specifically, for any dimensionality of arrays, one can find extendible hashing schemes which at once utilize storage well (fewer than 2 p storage locations need be set aside for storing arrays having p or fewer positions) and enjoy good access characteristics (expected access time is O (1), and worst-case access time is O (log log p ) for p - or fewer-position arrays). Moreover, at the cost of only a modest additive increase in access time, storage demands can be decreased to (1 + δ) p locations for arbitrary δ > 0.

The use of hashing schemes for storing extendible arrays is investigated. It is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely, hashing schemes that utilize storage too conservatively are inevitably poor in expected access time. If requirements on the utilization of storage are relaxed slightly, then one can find rather efficient extendible hashing schemes. Specifically, for any dimensionality of arrays, one can find extendible hashing schemes which at once utilize storage well [fewer than 2p storage locations need be set aside for storing arrays having p or fewer positions] and enjoy good access characteristics [expected access time is 0(1), and worst-case access time is 0(log log p) for p- or fewer-position arrays]. Moreover, at the cost of only an additive increase in access time, storage demands can be decreased to (l+ε)p locations for arbitrary ε>0. In fact, if one will abide a more drastic degradation of access efficiency, one can lower storage demands to p+o(p) locations.

No abstract available.

Schemes which allocate storage for extendible arrays cannot utilize storage as efficiently as can their nonextendible counterparts. Relative to formal notions of array scheme and (extendible) array realization, a formal way of gauging efficiency of storage utilization by extendible array realizations is proposed; a lower bound of $O(p \cdot (\log p)^{d - 1} )$, where p is the array size and d the dimensionality, is derived for this measure; and an extendible allocation scheme which achieves this lower bound is exhibited. Certain seminorms on Euclidean spaces can be used to construct extendible array realizations. It is shown that for realizations so constructed, the lower bound on storage utilization efficiency is $O(p^d )$. In the opposite direction, certain restrictions on the patterns of expansions of arrays can be used to circumvent the lower bound: When arrays are constrained to expand according to some fixed finite set of patterns, then one can devise extendible realizations which (a) utilize storage very efficiently $(O(p))$ on arrays which conform to the patterns and (b) approach the general lower bound $(O(p \cdot (\log p)^{d - 1} ))$ on arrays which do not conform. It is not known if this improvement is available for infinite sets of patterns.

Efficiency of storage management in algorithms which use arrays is often enhanced if the arrays are stored in a proximity-preserving manner; that is, array positions which are close to one another in the array are stored close to one another. This paper is devoted to studying certain qualitative and quantitative questions concerning preservation of proximity by array storage schemes (or,realizations). It is shown that fully extendible array realizations cannot preserve proximity in any global sense, not even proximity along a single direction (say, along rows). They can, however, preserve proximity in certain local senses; and realizations which are optimal in various senses of local preservation are exhibited. Partially extendible array storage schemes can preserve proximity in a global way; bounds on their “diameters of preservation” are derived, and optimal schemes are exhibited.

Efficient storage utilization by schemes which allocate storage for extendible arrays is studied. A minimax lower bound on efficiency of storage use by such schemes is derived; and a scheme which achieves this bound is exhibited. When arrays are constrained to expand according to a preassigned finite set of shapes, the general lower bound can be lowered dramatically; in fact, if a single shape for expansion is chosen, one can devise a scheme which utilizes storage perfectly for arrays of that shape.

Arrays are among the best understood and most widely used data structures. Yet even now, there are no satisfactory techniques for handling algorithms involving extendible arrays (where, e.g., rows and/or columns can be appended dynamically). In this paper, the problem of allocating storage for extendible arrays is examined in the light of the author's earlier work on data graphs and addressing schemes. A formal analog of the assertion that simplicity of array extension precludes simplicity of traversal (marching along rows/columns) is proved. Two strategies for constructing extendible realizations of arrays are formulated, and certain inherent limitations of such realizations are established.

Arrays are among the best understood and most widely used data structures. Yet even now, there are no satisfactory techniques for handling algorithms involving extendible arrays (where, e.g., rows and/or columns can be added dynamically). In this paper, the problem of allocating storage for extendible arrays is examined in the light of our earlier work on data graphs and addressing schemes. A formal analog of the assertion that simplicity of array extension precludes simplicity of transition (marching along rows/columns) is proved.

In this paper we look at a number of matching problems and devise general techniques for attacking such problems. In particular, we describe a strategy for constructing efficient algorithms for solving two types of matching problems. We use this strategy to develop explicit algorithms for these two problems applied to strings (where the patterns are substrings) and arrays (where the patterns are subarrays or blocks). We also develop algorithms for these and related problems for trees, where the patterns are subtrees. Certain special cases of these algorithms are also discussed.

The main result of this paper is that, given a Turing machine with several readwrite heads per tape, one can effectively construct an equivalent multitape Turing machine with a single read-write head per tape, which runs at precisely the same speed.This result implies that serial storage may be used to handle files requiring several points of immediate two-way read-write access without interruptions for rewinds, etc.It also yields simplified proofs of several results in the literature of computational complexity.

The classes of data graphs which are implementable in a random access memory using "relative addressing" and "relocatable realization" were characterized algebraically in a previous paper by the author.In the present paper the investigation of these classes is continued.A new characterization of the class of rooted (= relative addressable) data graphs yields simple and natural proofs of the preservation of rootedness under broad families of operations for composing data graphs.These combinatory operations somewhat diminish the impact of the general unsolvability of detecting rootedness and free-rootedness (= relocatability) in data graphs.

Data graphs were introduced as a vehicle for studying uniformities in the structure of graphs underlying data structures. This paper is devoted to investigating symmetries in data graphs. Such symmetries are of no little significance in every phase of the computational process. They can often be exploited to formulate more efficient algorithms, to simplify the specification of these algorithms, and to facilitate analysis of the resulting programs. The main thrust of this paper is to investigate the influence of various structural features of data graphs on the types of symmetries the data graphs enjoy what features ensure the presence of symmetries of various types, and what features limit the possible types of symmetries. These questions are studied first on the class of all data graphs, and then on the class of addressable (= realizable by relative addressing) data graphs.

This paper continues the study of the classes of data graphs which are implementable in a random access memory using “relative addressing” and “relocatable realization”, which was initiated in [1]. A new characterization of the class of rooted (=relative addressable) data graphs yields simple and natural proofs of the preservation of rootedness under broad families of operations for composing data graphs. These positive results somewhat diminish the impact of the general unsolvability of detecting rootedness and free-rootedness (=relocatability) in data graphs.

A data graph is obtained from a data structure by masking out the specific data items at the nodes of the structure and concentrating only on the linkages in the structure. Structural uniformities in data graphs can often be exploited to facilitate and systematize the accessing of nodes in the graph and the implementation of the graph in a computer. This paper presents a model for data graphs which can be used to study such uniformities. The main results reported characterize, in terms of structural uniformities, those classes of data graphs which can be implemented by “relative addressing” and by “relocatable relative addressing”.

An investigation is made of certain quantitative and qualitative aspects of inherent ambiguity of context-free languages.Two main results are proved.The first asserts that for every integer k there are inherently k-ambiguous context-free subsets of a*b*c*.This result is obtained as a corollary of a more general result concerning ambiguous presentations of semilinear sets.The second result asserts that inherent ambiguity can arise from the "nesting" property of context-free languages, as well as from the "pairwise matching" property. KEY WORDS AND PHRASES: inherent ambiguity,

An operator precedence language which is not real-time definable by any multitple Turing machine is constructed. This strengthens previous results about the existence of unambiguous context-free languages (CFL's) which are not real-time definable. In contrast, a family of CFL's of increasing degree of inherent ambiguity, each real-time definable by a one-tape Turing machine, is exhibited. In fact, an unboundedly ambiguous CFL, also real-time definable by a one-tape Turing machine, is presented. These results are the basis for the assertion that real-time definability of a CFL is independent from each of the structural properties considered.

The closure properties of the class of languages defined by real-time, online, multi-tape Turing machines are proved. The results obtained are, for the most part, negative and, as one would expect, asymmetric. It is shown that the results remain valid for a broad class of real-time devices. Finally, the position of the class of real-time definable languages in the “classical” linguistic hierarchy is established.