arkady@cs.tamu.edu (Arkady Kanevsky) (03/26/91)
The 3rd Workshop on Algorithmic Research in the Midsouthwest March 29, 1991 Room 601 Rudder Tower Texas A&M University WARM Spring 1991 1 AGENDA 10:30 - 11:00 Registration (Room 601 Rudder Tower) 11:00 - 11:45 David Matula Department of Computer Science and Engineering Southern Methodist University Dallas, Texas "Highly Parallel IEEE Standard Floating Point Units: Current Designs and Future Trends" Abstract We describe several methods by which parallelism is incorporated in the design of fast multipliers suitable for convenient VLSI layout. We describe new algorithms for divide and square root employing a fast multiplier and yielding results satisfying the IEEE 754 floating point standard. Performance statistics for the Cyrix Fasmath* coprocessor employing such methods are given in comparison to traditional floating point coprocessor designs. We discuss trends in the incorporation of new arithmetic functi onalities (i.e. vector arithmetic, quad precision) in the design of chips and boards for the next generation P.C. and workstation platforms. 11:45 - 12:30 Jesse Chen Department of Computer Science University of Texas at Dallas "Area Optimization for Floorplan Design" Abstract Floorplan is the first stage of VLSI layout design and perhaps the most important one. It is the problem of allocating space to a set of modules in the plane in order to minimize the area of the floor rectangle. One of the most important classes of non-slicing floorplans, which has received much attention recently, is the class of spiral floorplans. Previous algorithms minimize the area of such floorplans in O(n3 logn) time and O(n3) space. We present an improved algorithm that minimizes the area of a s piral floorplan in O(n2 logn) time and O(n2) space. This is a joint work with Dr. Tollis. 12:30 - 2:00 Lunch 2:00 - 2:45 Sridhar Radhakrishnan School of Electrical Engineering and Computer Science University of Oklahoma "Efficient Parallel Algorithms for Domination Problems in Special Graphs" Abstract Location models on networks (graphs) typically have a set of clients who have demand for services or commodities, and facilities to serve the clients. Various problems arise while imposing constraints on the clients and/or the facilities. One such classical problem is the DOMINATION PROBLEM. The notion of DOMINATION is that a set of vertices (or edges) dominating or covering another set. Conditions can be imposed both on the dominating set (e.g. it be a connected set, an independent set, induce a path , a clique, or a graph without isolated vertices, etc.), and the dominated set (e.g. set of vertices, edges, etc.). In this presentation we review the state-of-the-art results in the area of parallel aglorithms for domination problems in special graphs such as interval graph, permutation graph, partial-k-trees, etc. Certain new results, relating to domination problems in strongly chordal graphs will also be presented. 2:45 - 3:45 Chee K. Yap Courant Institute New York University Invited Distinguished Speaker "On Computational Modes: Choice and Stochastic Machines" Abstract We distinguish between computational models (Turing, RAM, Storage Modification Machines, etc) and their modes of computation (nondeterministic, parallel, randomized, etc). Models and modes are essentially orthogonal concepts. Complexity theory is model-independent but not mode-independent. We classify computational modes along two dimensions: the degree of choice and the degree of parallelism. Focusing only on the choice dimension, we have many recent examples: interactive proof systems (Goldwasser-Michali-Rackoff), Arthur-Merlin games (Babai), nondeterministic-probabilistic machines (Goldwasser-Sipser), games against nature (Papadimitriou), logical Turing machine types (Hong), probabilistic game automata (Condon-Ladner), generalized nondeterministic machines that define the Boolean (Hausdorff) Hierarchy (Wechsung). We introduce choice machines that provides a common and natural foundation for all the above choice modes. Our theory is based on two technical tools: interval algebra (or any complete partial order) and the least fixed point mechanism. A class of choice machines is specified by a set of basis functions that are continuous and monotonic. We describe complexity results for choice machines with the following basis functions: and, or, negation, coin-toss, probabilistic-and, probabilistic-or. The latter three functions characterize the stochastic machines. Using the latter, one obtains a stochastic polynomial-time hierarchy in analogy with the polynomial-time hierarchy of Meyer-Stockmeyer: the role of P is replaced by BPP or PP (depending on whether we assume bounded-error). 3:45 - 4:15 Break 4:15 - 5:00 Greg Plaxton Department of Computer Sciences University of Texas at Austin "Highly Fault-Tolerant Probabilistic Sorting Circuits" Abstract This talk considers the problem of designing highly fault-tolerant probabilistic sorting circuits. A "probabilistic sorting circuit" is an n-input, n-output comparator circuit (i.e., an acyclic circuit made up of 2-input, 2-output comparator gates) that sorts the vast majority (e.g., all but a polynomially small fraction) of the n! possible input permutations. A probabilistic sorting circuit is "highly fault-tolerant" if it can sustain a constant fraction of random faults and still sort the vast majorit y of input permutations with high probability. In order to establish a tradeoff between the fault-tolerance level and the size and/or depth of sorting circuits, one must first provide a formal framework for modelling the kind of faults that may occur in a sorting circuit. We consider two different fault models. In each case, we assume that no faults occur in the RwiresS of the sorting circuits, but instead that a randomly chosen subset of the comparator gates are designated as "faulty". Under the first fault model, which will be referred to as the "non-destructive" fault model, a faulty comparator gate simply passes the inputs to the outputs (according to some predetermined mapping) without performing a comparison. Under the second, or "destructive", fault model, a faulty comparator gate always produces an unsorted pair of outputs. Note that the destructive fault model does not permit the existence of a high probability sorting circuit of any size and/or depth. Thus, in the case of th e destructive fault model, it is necessary to either consider variants of the sorting problem (e.g., nearsorting), or to incorporate other types of gates into the basic comparator circuit model. This talk will describe a sorting circuit construction for the non-destructive fault model that matches the trivial W(log n)-depth lower bound to within log log n factors. A non-trivial lower bound for the destructive model will also be given. Joint work with Tom Leighton of MIT. 6:30 Dinner