Preface
History of the Book
The last three decades have witnessed an explosive development in integrated circuit fabrication technologies. The complexities of current CMOS circuits are reaching beyond the 65 nanometer feature size and multi-hundred million transistors per integrated circuit. To fully exploit this technological potential, circuit designers use sophisticated Computer-Aided Design (CAD) tools. While supporting the talents of innumerable microelectronics engineers, these CAD tools have become the enabling factor responsible for the successful design and implementation of thousands of high performance, large scale integrated circuits.
This book (a research monograph) originated from a body of doctoral dissertation research completed by the first author at the University of Rochester from 1994 to 1999 while under the supervision of Prof. Eby G. Friedman. This research focuses on issues in the design of the clock distribution network in large scale, high performance digital synchronous circuits and particularly, on algorithms for non-zero clock skew scheduling. During the development of this research, it became clear that incorporating timing issues into the successful integrated circuit design process is of fundamental importance, particularly in that advanced theoretical developments in this area have been slow to reach the designers' desktops. The second edition of the book is enhanced by the body of doctoral dissertation research completed by the second author at the University of Pittsburgh from 2000 to 2005 under the supervision of Prof. Ivan S. Kourtev. This dissertation focuses on advanced timing, synchronization and design methodologies based on non-zero clock skew scheduling. Included in this book are methods on the applicability of clock skew scheduling on circuits with level-sensitive latches, a timing-driven circuit design methodology to attain the maximum performance out of clock skew scheduling and a solution to non-zero clock skew scheduling problem in a parallel computing environment, specifically derived for integration into the physical design process of an emerging non-zero clock skew clocking technology.
It is the authors' belief that the successful application of non-zero clock skew scheduling techniques to the integrated circuit design process can only follow a detailed understanding of the operation of integrated circuits at many different levels-from device physics through system architecture to packaging. While a detailed coverage of all of these topics in a single text is impractical, an honest effort has been made to provide an in-depth treatment of all of those areas closely related to the clock skew scheduling techniques presented in this book. Tutorial chapters on the structure and design of modern integrated circuits, as well as on the fundamental principles of signal delay are included in this text since these topics are crucial to understanding clock skew scheduling in general. The information presented in these tutorial chapters can also quickly familiarize the reader with the problems, definitions, and terminology used throughout the book.
Automated methodologies for synchronous circuit performance optimization through clock skew scheduling is the primary topic presented in this book. The objectives of these methodologies are to improve the performance (specifically, the operating frequency or speed) while increasing the reliability of fully synchronous digital integrated circuits. Traditionally, design wisdom has dictated the use of global zero clock skew. In the research presented here, however, non-zero clock skew scheduling is exploited. A set of algorithms to accomplish this objective are considered in more detail. Specifically, this book deals in depth with the following issues:
A methodology for simultaneous non-zero clock skew scheduling and design of the topology of the clock distribution network. This methodology is based on the pioneering works of Friedman [1] and Fishburn [2], and builds on Linear Programming (LP) solution techniques. The non-zero clock skew scheduling of circuits with level-sensitive latches and for multi-phase clock signals is formulated as a LP problem. The simultaneous clock scheduling and clock tree topology synthesis problem is formulated as a mixed-integer linear programming problem that can be solved efficiently. The proposed algorithms have been evaluated on a variety of benchmark and industrial circuits and synchronous performance improvements of well above 60% have been demonstrated.
For those cases where reliable circuit operation and production yield are the highest level priorities, an alternative problem formulation is developed. This formulation is based on a quadratic (hence the QP-quadratic programming) measure, or cost function, of the tolerance of a clock schedule to parameter variations. A mathematical framework is presented for solving the constrained and bounded QP problem. A constrained version of the problem is iteratively solved using the Lagrange multipliers method. As these research issues are topics of great practical importance for input/output (I/O) interfacing and Intellectual Property (IP) blocks, explicit clock delay and skew requirements are fully integrated into the mathematical model described here.
The theoretical derivation of the limits on the improvements on the clock period available through clock skew scheduling. The theoretical derivation is performed by identifying the limits for three local data path topologies. A methodology to mitigate the limitation of clock skew scheduling for a reconvergent path system is presented. The methodology involves delay insertion on some data paths of the reconvergent system and is formulated as an LP problem for an automated application.
A practical (and necessary) implementation of clock skew scheduling for an emerging clock generation and distribution technology in resonant rotary clocking technology. Preliminary efforts in modeling and implementation are demonstrated. Details are included on the integration of clock skew scheduling into a complete physical design flow for the automated design of rotary clock synchronized synchronous circuits.
As with any project of this magnitude, mistakes are likely. To the best knowledge of the authors, proper credit has been given to everyone whose work has been mentioned here, but the authors take full responsibility for any errors or omissions.
Acknowledgments
The authors would like to thank all of those who have helped writing and correcting early manuscript versions of this monograph-fellow colleagues and students, as well as the anonymous reviewers who provided important comments on improving the overall quality of this book. The authors would also like to thank Dr. Bob Grafton from the National Science Foundation for supporting the early research projects that have culminated in the writing and production of this book. We would also like to warmly acknowledge the assistance and support of Alex Greene and Katelyn Stanne from Springer-Alex and Katie's patience and encouragement have been crucial to the success of this project.
The research work described in this research monograph was made possible in part by support from the National Science Foundation under Grant No. MIP-9423886 and Grant No. MIP-9610108, by a grant from the New York State Science and Technology Foundation to the Center for Advanced Technology-Electronic Imaging Systems, and by grants from the Xerox Corporation, IBM Corporation, Intel Corporation and Multigig Inc.
Pittsburgh, PA, Ivan S. Kourtev
Philadelphia, PA, Baris Taskin
Rochester, NY, Eby G. Friedman July, 2008