Retiming synchronous circuitry

This paper describes a circuit transformation calledretiming in which registers are added at some points in a circuit and removed from others in such a way that the functional behavior of the circuit as a whole is preserved. We show that retiming can be used to transform a given synchronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph in which the vertex setV is a collection of combinational logic elements and the edge setE is the set of interconnections, each of which may pass through zero or more registers. We give anO(¦V∥E¦lg¦V¦) algorithm for determining an equivalent retimed circuit with the smallest possible clock period. We show that the problem of determining an equivalent retimed circuit with minimum state (total number of registers) is polynomial-time solvable. This result yields a polynomial-time optimal solution to the problem of pipelining combinational circuitry with minimum register cost. We also give a chacterization of optimal retiming based on an efficiently solvable mixed-integer linear-programming problem.     

Understanding retiming through maximum average-delay cycles

A synchronous circuit built of functional elements and registers is a simple implementation of the semisystolic model of computation that can be used to design parallel algorithms. Retiming is a well-known technique that transforms a given circuit into a faster circuit by relocating its registers. We give tight bounds on the minimum clock period that can be achieved by retiming a synchronous circuit. These bounds are expressed in terms of the maximum delay-to-register ratio of the cycles in the circuit graph and the maximum propagation delayd _max of the circuit components. Our bounds do not depend on the size of the circuit, and they are of theoretical as well as practical interest. They characterize exactly the minimum clock period that can be achieved by retiming a unit-delay circuit, and they lead to more efficient algorithms for several important problems related to retiming. Specifically, we give anO(V ^1/2 E IgV) algorithm for minimum clock-period retiming of unit-delay circuitry. For non-unit-delay circuitry, we describe anO(VE Igd _max ) algorithm for minimum clock-period retiming. We also describe anO(V ^1/2 E lg²(Vd _max ) algorithm for retiming with clock period that does not exceed the minimum by more thand _max — 1. Finally, we give anO(E Igd _max ) algorithm for minimum clock-period pipelining of combinational circuitry.This research was supported in part by the Defense Advanced Research Projects Agency under Contract N00014-87-K-0825.     

Dynamic maintenance of planar digraphs, with applications

We show that a planarst-graphG admits two total orders on the setVE F, whereV, E, andF are respectively the set of vertices, edges, and faces ofG, with ¦V¦ =n. Assuming thatG is to be dynamically modified by means of insertions of edges and expansions of vertices (and their inverses), we exhibit anO(n)-space dynamic data structure for the maintenance of these orders such that an update can be performed in timeO(logn). The discovered structural properties of planarst-graphs provide a unifying theoretical underpinning for several applications, such as dynamic point location in planar monotone subdivisions, dynamic transitive-closure query in planarst-graphs, and dynamic contact-chain query in convex subdivisions. The presented techniques significantly outperform previously known solutions of the same problems.This work was carried out at the University of Illinois and was supported in part by National Science Foundation Grant ECS-84-10902 and by the Joint Services Electronics Program under Contract N00014-84-C-0149.     

How to clear a block: A theory of plans

Problems in commonsense and robot planning are approached by methods adapted from program synthesis research; planning is regarded as an application of automated deduction. To support this approach, we introduce a variant of situational logic, called plan theory, in which plans are explicit objects.A machine-oriented deductive-tableau inference system is adapted to plan theory. Equations and equivalences of the theory are built into a unification algorithm for the system. Frame axioms are built into the resolution rule.Special attention is paid to the derivation of conditional and recursive plans. Inductive proofs of theorems for even the simplest planning problems, such as clearing a block, have been found to require challenging generalizations.This research was supported by the National Science Foundation under Grants DCR-82-14523 and DCR-85-12356, by the Defense Advanced Research Projects Agency under Contract N00039-84-C-0211, by the United States Air Force Office of Scientific Research under Contract AFOSR-85-0383, by the Office of Naval Research under Contract N00014-84-C-0706, by United States Army Research under Contract DAJA-45-84-C-0040, and by a contract from the International Business Machines Corporation.Preliminary versions of parts of this paper were presented at the Eighth International Conference on Automated Deduction, Oxford, England, July 1986, and the Workshop on Planning and Reasoning about Actions, Timberline, Oregon, July 1986.     

Communication-efficient parallel algorithms for distributed random-access machines

This paper introduces a model for parallel computation, called thedistributed randomaccess machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. A DRAM explicitly models the congestion of messages across cuts of the network.We introduce the notion of aconservative algorithm as one whose communication requirements at each step can be bounded by the congestion of pointers of the input data structure across cuts of a DRAM. We give a simple lemma that shows how to shortcut pointers in a data structure so that remote processors can communicate without causing undue congestion. We giveO(lgn)-step, linear-processor, linear-space, conservative algorithms for a variety of problems onn-node trees, such as computing treewalk numberings, finding the separator of a tree, and evaluating all subexpressions in an expression tree. We giveO(lg² n)-step, linear-processor, linear-space, conservative algorithms for problems on graphs of sizen, including finding a minimum-cost spanning forest, computing biconnected components, and constructing an Eulerian cycle. Most of these algorithms use as a subroutine a generalization of the prefix computation to trees. We show that any suchtreefix computation can be performed inO(lgn) steps using a conservative variant of Miller and Reif's tree-contraction technique.This research was supported in part by the Defense Advanced Research Projects Agency under Contract N00014-80-C-0622 and by the Office of Naval Research under Contract N00014-86-K-0593. Charles Leiserson is supported in part by an NSF Presidential Young Investigator Award with matching funds provided by AT&T Bell Laboratories and Xerox Corporation. Bruce Maggs is supported in part by an NSF Fellowship.     

Shortest paths in euclidean graphs

We analyze a simple method for finding shortest paths inEuclidean graphs (where vertices are points in a Euclidean space and edge weights are Euclidean distances between points). For many graph models, the average running time of the algorithm to find the shortest path between a specified pair of vertices in a graph withV vertices andE edges is shown to beO(V) as compared withO(E +V logV) required by the classical algorithm due to Dijkstra.Support for the first author was provided in part by NSF Grant MCS-83-08806. Support for the second author was provided in part by NSF Grants MCS-81-05324 and DCR-84-03613, an NSF Presidential Young Investigator Award, an IBM research contract, and an IBM Faculty Development Award. Support for this research was also provided in part by an ONR and DARPA under Contract N00014-83-K-0146 and ARPA Order No. 4786. Equipment support was provided by NSF Grant MCS-81-218106.     

A generic algorithm for one-dimensional homotopic compaction

One-dimensional homotopic compaction problems model the task of VLSI layout compaction with automatic jog insertion. They have the following form: given a routable layout, find a layout of minimum width reachable by a continuous motion of layout components that displaces each rigid component horizontally and preserves routability. We define a configuration space for this problem, and prove that if routability is characterized bycut conditions, then the set of reachable configurations is a closed, convex polyhedron. We also present a polynomial-time algorithm that finds the constraints defining this polyhedron and solves them to produce an optimal configuration. A homotopic router can recover the compacted layout from this configuration. We illustrate our strategy in thesketch model of VLSI layout, where it yields a compaction algorithm with worst-case running timeO(N ⁴) on input of sizeN.This paper is based on a thesis submitted in May of 1986 in partial fulfillment of the requirements for the degree of Master of Science in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. The work described herein was supported in part by a Graduate Fellowship from the Office of Naval Research, in part by the Defense Advanced Research Projects Agency under Contract N00014-80-C-0622, and in part by a Mathematical Sciences Postdoctoral Research Fellowship from the National Science Foundation, Grant DMS-8705835.     

Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons

Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems.Work on this paper by this author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, the IBM Corporation, and from the U.S.-Israel Binational Science Foundation.Work on this paper by this author has been supported by National Science Foundation Grant DCR-86-05962.     

A faster approximation algorithm for the Steiner problem in graphs

Summary We present an algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V. The set V-S is traditionally denoted as Steiner vertices. The total distance on all edges of this Steiner tree is at most 2(1–1/l) times that of a Steiner minimal tree, where l is the minimum number of leaves in any Steiner minimal tree for the given graph. The algorithm runs in O(¦E¦log¦V¦) time in the worst case, where E is the set of all edges and V the set of all vertices in the graph. It improves dramatically on the best previously known bound of O(¦S¦¦V¦²), unless the graph is very dense and most vertices are Steiner vertices. The essence of our algorithm is to find a generalized minimum spanning tree of a graph in one coherent phase as opposed to the previous multiple steps approach.The work of this author was partially supported by the National Science Foundation under Grants MCS 8342682 and ECS 8340031. This work was performed while this author was a summer visitor at the IBM T.J. Watson Research Center.On leave from: Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6380, D-7500 Karlsruhe, Federal Republic of Germany     

A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

We show that anyk-connected graphG = (V, E) has a sparsek-connected spanning subgraphG = (V, E) with ¦E¦ =O(k¦V¦) by presenting anO(¦E¦)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time boundO(max{k ²¦V¦^1/2,k¦V¦}¦E¦) to determine whether node-connectivityK(G) of a graphG = (V, E) is larger than a given integerk or not can be reduced toO(max{k ³¦V¦^3/2,k ²¦V¦²}).The first author was partially supported by the Grant-in-Aid for Encouragement of Young Scientists of the Ministry of Education, Science and Culture of Japan and by the subvention to young scientists by the Research Foundation of Electrotechnology of Chubu.