James B. Saxe Decomposable Searching Problems and Circuit Optimization by Retiming: Two Studies in General Transformation on Computational Structures Degree Type: Ph.D. in Computer Science Advisor(s): Jon Bentley Graduated: December 1985 Abstract: 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 structures for decomposable searching problems and 2 optimization of synchronous digital circuits . A searching problem is characterized by a query function ath Q , which takes as arguments a query object ath x and a set ath A of data objects and returns a response ath Q x,#A . The problem is decomposable if there exists an operator ath qv such that 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. A digital circuit is a network of combinatorial 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 solutions 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.
