DECOMPOSABLE SEARCHING PROBLEMS AND CIRCUIT OPTIMIZATION BY RETIMING: TWO STUDIES IN GENERAL TRANSFORMATIONS OF COMPUTATIONAL STRUCTURES.

摘要

An important activity in the advancement of knowledge is the search for general methods: techniques applicable to large classes of problems. This dissertation studies general transformations of computational structures in two domains: (1) design of data struc- tures for decomposable searching problems and (2) optimization of synchronous digital circuits.;A digital circuit is a network of combinational functional elements and clocked registers (memory elements). The second portion of the dissertation (Chapters IV-VII) deals with transformations for improving the performance of such circuits. The transformations add and delete registers at various points in the circuit so that the functional behavior is left unchanged while the shortest safe clock period is decreased.;In each domain, transformations are introduced that allow solu- tions for any of a large class of design problems to be transformed systematically into solutions for related, but (intuitively) more difficult, problems. After presenting precisely-stated technical results in each of the two problem domains, the dissertation concludes with a more.;philosophical discourse on the similarities and differences of the approaches taken in studying the two domains.;A searching problem is characterized by a query function Q, which takes as arguments a query object x and a set A of data objects and returns a response Q(x,A). The problem is decompos- able if there exists an operator (SQUARE) such that Q(x,A (UNION) B) = Q(x,A) (SQUARE) Q(x,B) whenever (x,A) and (x,B) are in the domain of Q. The first part of this dissertation (Chapters II and III) studies general methods for transforming any data structure for any decomposable searching problem into a new data structure with enhanced capability. For example, a static data structure, which must be built all at once, might be transformed into a dynamic data structure, which allows new insertions to be intermingled with queries.;*This research was sponsored in part by the Office of Naval Research under Contract N00014-76-C-0370 and by the Defense Advanced Research Projects Agency under Contract N00014-80-C-0622. During the academic year 1981-82 the author was supported in part by an IBM Graduate Fellowship. The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of the International Business Machines Corporation, the Office of Naval Research, the Defense Advanced Research Projects Agency, or the U.S. Government.