Timing Optimization Through Clock Skew Scheduling

__Timing Optimization Through Clock Skew Scheduling__ focuses on optimizing the timing of large scale, high performance, digital synchronous systems. A particular emphasis is placed on algorithms for non-zero clock skew scheduling to improve the performance and reliability of VLSI circuits. This research monograph answers the need for a broad introduction to state-of-the-art clock skew scheduling algorithms from a circuit, graph, and mathematical optimization background. A detailed description of clock skew scheduling application on edge-triggered and level-sensitive circuits, synchronized with single and multi-phase clocking schemes, and formulated as linear programming (LP) and quadratic programming (QP) formulations are provided along with an analysis of optimal computer solution techniques. Theoretical limits of improvement in clock frequency through clock skew scheduling are highlighted. Hints and a preliminary implementation of a parallel skew scheduling application are also included. __Timing Optimization Through Clock Skew Scheduling__ contains sufficient detail for the advanced CAD algorithm developer, researcher and graduate student. Furthermore, with the material provided on timing properties and optimization, those readers with less background can also benefit from this book.

The focus of this book is on timing analysis and optimization techniques for circuits with level-sensitive memory elements (registers). Level-sensitive registers are becoming significantly more popular in practice as integrated circuit densities are increasing and the ‘performance-per-power’ metric for integrated circuits becomes a key issue. Therefore, techniques for understanding level-sensitive based circuits and for optimizing the performance of such circuits are increasingly important.

The book includes the following major topics in the timing analysis and optimization of level-sensitive circuits:

A linear programming (LP) formulation applicable to the timing analysis of large scale circuits. The formulation uses a variation of the big M method - called the modified big M method - to transform the non-linear constraints in the problem formulation into solvable linear constraints. This LP formulation is computationally efficient and demonstrates significant circuit performance improvement. By making maximum use of cycle stealing, operation at a higher clock frequency (reduced clock period) is possible.

A delay insertion methodology that improves the efficiency of clock skew scheduling in level-sensitive circuits. It is shown that re-convergent paths limit the improvement of circuit performance that can be achieved through clock skew scheduling. The described delay insertion method mitigates the limitations cause by re-convergent data paths and improves the results of timing optimization (for increased clock frequency).

A summary of circuit partitioning, placement and synchronization methodologies that enables the implementation of high speed, low power circuits synchronized with ultra modern resonant clocking technology (such as traveling oscillators/waves). The described framework includes the particular circuit partitioning and placement methodologies that permit the hierarchical application of non-zero clock skew system timing in resonant clocking based circuits.

A framework for and results from implementing the described timing optimization algorithms in a parallel computing environment. As multi-core microprocessors become commonplace, computationally intense algorithms can benefit greatly by exploiting this available parallelism. The framework uses a heuristic approach to generate circuit partition and solve them independently on processors/computers working on parallel. This is one of the first such applications of explicit parallelism in Electronic Design Automation (EDA), and, will be of great interest to practicing EDA engineers.

History of the Book The last three decades have witnessed an explosive development in - tegrated 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 succe- ful design and implementation of thousands of high performance, large scale integrated circuits. This book (a research monograph) originated from a body of doctoral d- sertationresearchcompletedbythe?rstauthorattheUniversityofRochester 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 algorithmsfornon-zero clockskewscheduling.Duringthedevelopmentofthis 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. Front Matter....Pages i-xvi Introduction....Pages 1-6 VLSI Systems....Pages 7-18 Signal Delay in VLSI Systems....Pages 19-39 Timing Properties of Synchronous Systems....Pages 41-70 Clock Skew Scheduling and Clock Tree Synthesis....Pages 71-96 Clock Skew Scheduling of Level-Sensitive Circuits....Pages 97-120 Clock Skew Scheduling for Improved Reliability....Pages 121-143 Delay Insertion and Clock Skew Scheduling....Pages 145-165 Practical Considerations....Pages 167-181 Clock Skew Scheduling in Rotary Clocking Technology....Pages 183-204 Experimental Results....Pages 205-241 Back Matter....Pages 243-265 This book details timing analysis and optimization techniques for circuits with level-sensitive memory elements. It contains a linear programming formulation applicable to the timing analysis of large scale circuits and includes a delay insertion methodology that improves the efficiency of clock skew scheduling. Coverage also provides a framework for and results from implementing timing optimization algorithms in a parallel computing environment.