Robert K. Brayton

Patrick C. McGeer

This book is an extension of one author's doctoral thesis on the false path problem. The work was begun with the idea of systematizing the various solutions to the false path problem that had been proposed in the literature, with a view to determining the computational expense of each versus the gain in accuracy. However, it became clear that some of the proposed approaches in the literature were wrong in that they under estimated the critical delay of some circuits under reasonable conditions. Further, some other approaches were vague and so of questionable accu racy. The focus of the research therefore shifted to establishing a theory (the viability theory) and algorithms which could be guaranteed correct, and then using this theory to justify (or not) existing approaches. Our quest was successful enough to justify presenting the full details in a book. After it was discovered that some existing approaches were wrong, it became apparent that the root of the difficulties lay in the attempts to balance computational efficiency and accuracy by separating the tempo ral and logical (or functional) behaviour of combinational circuits. This separation is the fruit of several unstated assumptions; first, that one can ignore the logical relationships of wires in a network when considering timing behaviour, and, second, that one can ignore timing considerations when attempting to discover the values of wires in a circuit.

The False Path Problem and Its Implications

Integrating Functional and Temporal Domains in Logic Design

Alberto Sangiovanni-Vincentelli

Tiziano Villa

Nina Yevtushenko

Alan Mishchenko

Alexandre Petrenko

The Problem of the Unknown Component: Theory and Applications addresses the issue of designing a component that, combined with a known part of a system, conforms to an overall specification. The authors tackle this problem by solving abstract equations over a language. The most general solutions are studied when both synchronous and parallel composition operators are used. The abstract equations are specialized to languages associated with important classes of automata used for modeling systems. The book is a blend of theory and practice, which includes a description of a software package with applications to sequential synthesis of finite state machines. Specific topologies interconnecting the components, exact and heuristic techniques, and optimization scenarios are studied. Finally the scope is enlarged to domains like testing, supervisory control, game theory and synthesis for special omega languages. The authors present original results of the authors along with an overview of existing ones.

Theory and Applications

The Unknown Component Problem

Fan Mo

Regular Fabrics in Deep Sub-Micron Integrated-Circuit Design discusses new approaches to better timing-closure and manufacturability of DSM Integrated Circuits. The key idea presented is the use of regular circuit and interconnect structures such that area/delay can be predicted with high accuracy. The co-design of structures and algorithms allows great opportunities for achieving better final results, thus closing the gap between IC and CAD designers. The regularities also provide simpler and possibly better manufacturability. In this book we present not only algorithms for solving particular sub-problems but also systematic ways of organizing different algorithms in a flow to solve the design problem as a whole. A timing-driven chip design flow is developed based on the new structures and their design algorithms, which produces faster chips in a shorter time.

Regular Fabrics in Deep Sub-Micron Integrated-Circuit Design

Alberto L. Sangiovanni-Vincentelli

Rajeev Murgai

Short turnaround has become critical in the design of electronic systems. Software- programmable components such as microprocessors and digital signal processors have been used extensively in such systems since they allow rapid design revisions. However, the inherent performance limitations of software-programmable systems mean that they are inadequate for high-performance designs. Designers thus turned to gate arrays as a solution. User-programmable gate arrays (field-programmable gate arrays, FPGAs) have recently emerged and are changing the way electronic systems are designed and implemented. The growing complexity of the logic circuits that can be packed onto an FPGA chip means that it has become important to have automatic synthesis tools that implement logic functions on these architectures. Logic Synthesis for Field-Programmable Gate Arrays describes logic synthesis for both look-up table (LUT) and multiplexor-based architectures, with a balanced presentation of existing techniques together with algorithms and the system developed by the authors. Audience: A useful reference for VLSI designers, developers of computer-aided design tools, and anyone involved in or with FPGAs.

Logic Synthesis for Field-Programmable Gate Arrays

Robert K. Brayton

About

Books

Join the club