tailieunhanh - Handbook of algorithms for physical design automation part 92

Handbook of Algorithms for Physical Design Automation part 92 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 892 Handbook of Algorithms for Physical Design Automation FIGURE Clock hazards and timing constraints. FFi and FFj as shown in Figure . Let tt and tj be the clock delays from clock source to FF and FFj respectively. Let Dy be the set of all combinational path delays from FF to FFj. Let tck2q be the clock-to-Q delay for FF . Let t7setup and t7h01d be the setup time and hold time for FFj respectively. Let P be the clock period. The setup time and hold time constraints can be expressed as ti C2q MAX Dy t p tj P ti C2 MIN Dij tj t7Md A clock schedule is a set of delays from clock source to all registers in the synchronous system. The clock scheduling problem is to find a clock schedule t1 . tN for all registers FF1 . FFN to minimize the clock period P while satisfying the constraints in Equations and . This problem can be formulated as a linear program as follows 20 LP_SPEED Minimize P subject to tj - t tj61 1 tck2q MAX Dy - P for i j 1 . N ti - tj tholi - C2q - MIN pj for i j 1 . N ti MIN_DELAY for i 1 . N Alternatively we can find a clock schedule to maximize the minimum safety margin M for a given clock period P. This problem can be formulated as a linear program as follows LP_SAFETY Maximize M subject to tj - ti t tclk2q MAX pj - P M for i j 1 . N ti - tj tdold - tclk2q - MIN Dj M for i j 1 . N jj i j ti MIN_DELAY for i 1 . N. In both formulations MAX Dy - and MIN Dj rc if there is no combinational path from FFi to FFj . After the clock schedule S t1 . tN is computed the next step is to construct a clock network to realize the obtained schedule. The DME algorithm in Section can be easily extended to handle this problem. We only need to construct the merging segments to achieve the given skews instead of zero skews in the bottom-up phase of the DME algorithm. However the solutions of the linear programs may not be unique. Each clock delay ti could be a range rather than a fixed value. In this case the clock routing problem .