Handbook of algorithms for physical design automation part 81.pdf (Sổ tay thuật toán)

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 782 Finals Page 782 19-9-2008 #13 Handbook of Algorithms for Physical Design Automation 37.3.2.1.3.2 Critical Area Integration Let us assume that the appropriate Voronoi subdivision of a layer for a fault type is available. Each Voronoi region can be partitioned into simple subregions such as rectangles and triangles (assuming the L∞ , L1 , or octagon metric), where the critical area integral can be computed analytically given the defect size distribution D(r). Once analytic formulas are established for each type of simple region, the total critical area integral can be derived as a simple summation of those formulas. As formulas are analytic, there is no integration error. In Refs. [45,48] analytic formulas were derived for the widely used defect size distribution D(r) = 1/r 3 assuming the L∞ metric and were shown to simplify into terms derived directly from Voronoi edges. As a result, critical area extraction becomes trivial once the appropriate Voronoi diagram is computed. In case A(r), the critical area for a given specific defect size r, is also needed, it can be easily derived in linear time from the same Voronoi subdivision of the layout. 37.3.2.1.3.3 Scanline Construction of the Voronoi Diagram The Voronoi diagram of a layout can be constructed by a scanline approach as described in Refs. [45,48] for the L∞ metric. The main advantage of the scanline construction is the low memory requirement for critical area computation. For critical area extraction, there is never any need to keep the Voronoi diagram of the entire layout in memory. Instead, only a portion of the Voronoi diagram near the scanline is maintained. As soon as the Voronoi cell of a polygon or a net is computed, second-order computation and critical area computation within that cell can be performed and the Voronoi cell can be immediately discarded. As a result, the layout can remain in a compact hierarchical form while the scanline incrementally flattens keeping only a small neighborhood of the design flat at a time near the scanline. The time complexity of the scanline algorithm to compute the L∞ Voronoi diagram is O(n log n), where n is the number of input layout edges, that is, the size of the layout. The second-order Voronoi diagram within the Voronoi cell of a polygon is computed in the same way maintaining the same time complexity. Critical area integration is then easily done in linear time. Thus, the entire critical area integral can be computed accurately in one scanline pass of the layout in O(n log n) time. Results on the wide use of the Voronoi method to compute critical area and predict yield by IBM Microelectronics are given in Ref. [49]. 37.3.2.1.3.4 Other Noniterative Approaches The grid method of Ref. [26] assumes a fine grid over the layout and uses it to perform critical area integration. The grid resolution can provide a trade-off between accuracy and speed. The method computes the critical radius for every grid point and uses this information to compute the critical area integral. The approach is appropriate for an interactive tool and can be sped up as shown in Ref. [45]. FedEx [50] is a fault extractor for shorts. That is, instead of computing critical area, it extracts a list of all two node intralayer bridges (shorts). It also computes approximate weighted critical area for each bridge, and provides approximate fault locations. As pointed out in Ref. [50] FedEx trades accuracy for speed and memory. It assumes Manhattan layouts. FedEx starts with a hierarchical design description, incrementally flattens the layout, and writes bridging faults out in a flat manner. For circuit and fault extraction uses a scanline algorithm that first converts polygons into rectangles. Memory consumption √ is relatively small as only a moving window of geometry is kept, that is, approximately O( n), where n is the size of the layout (number of rectangles). Bridge fault sites are written flat to the output file. There are several performance similarities between FedEx and the Voronoi method. Both methods start with a hierarchical design using a scanline that only locally sees the layout geometry flat. Memory consumption is relative small as only a neighborhood of the design near the scanline is kept in memory. The first-order Voronoi diagram of the layout geometry also provides information on same layer two node bridges as obtained by FedEx. FedEx outputs fast an approximate critical area for each bridge and the Voronoi method uses the second-order Voronoi Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 Finals Page 783 19-9-2008 #14 Yield Analysis and Optimization 783 diagram to obtain an accurate same layer critical area number maintaining an O(n log n) worst-case performance. 37.4 METHODS FOR YIELD OPTIMIZATION Aggressive technology scaling has made process variation control from purely manufacturing perspective very tough. Design-related yield losses have been projected to increase [51], which implies greater cooperation between physical design and process communities is necessary. Yield optimization methods work with the measure, model, and mitigate flow. Measurements are usually done by targeted test structures, which are measured on silicon for physical parameters like linewidth and thickness as well as electrical parameters like sheet resistance and transistor saturation current. A good publication to keep track of for those interested in test-structure design and measurement is ICMTS [52]. Models of process extracted from such test-structure measurements are usually abstracted to simpler models or a set of rules for physical design and verification tools to use. In this section, we briefly discuss the evolution of yield optimization physical design techniques. 37.4.1 CRITICAL AREA AND CATASTROPHIC YIELD OPTIMIZATION METHODS Back-end-of-the-line yield and manufacturability optimization is a complicated task. Methods for yield improvement vary ranging from critical-area-based wire spreading, metal fill, and the development of new rules and optimization for routers. We start with a review of available methods for wire spreading and critical area reduction. Methods for critical area reduction fall into two broad categories: methods that alter the topology of the layout by attempting critical area optimization at the routing phase and methods used as a postprocessing step that keep the layout topology fixed while attempting to alleviate congestion and increase wire spacing. The two categories can be regarded complementary and both can be incorporated into the design cycle. In the first category, the most representative method is Ref. [53], where a general routing cost function is described that takes into account critical area in conjunction with traditional routing objectives. The cost function combines most types of major defects, that is, shorts, opens, number of vias, and pinhole defects. Results verify that taking critical area into account at the routing phase can result in effective critical area reduction and therefore effective optimization for yield. In Ref. [54], channel routing is modified to reduce critical area between wire segments. Reference [54] also minimizes the number of vias as their presence increases manufacturability complexity and degrades the yield. The methods in the second category attempt to redistribute spacing between adjacent wires without changing the layout topology. They are usually based on compaction techniques using the following observation: In a VLSI layout, distances between shapes can vary as long as the minimum value imposed by the design rules is met. Slack between two shapes is defined by the difference of the current distance between the two shapes and the minimum distance required by the design rules. Carefully redistributing the slacks can result in a layout with a better yield. Several slack redistribution techniques have been proposed, see Refs. [55–58]. In their majority, they are based on principles of layout compaction and are formulated as a one-dimensional layout optimization problem. They start with a constraint graph representation of the layout and perform layout modification for yield in one direction at the time, using in majority a one-dimensional yield objective function. The main drawback of a one-dimensional yield objective function is that, although it optimizes for critical area in one direction, it fails to take into consideration a potential critical area increases in the orthogonal direction. Figure 37.7 illustrates one such situation where movement of a layout element in one direction decreases critical area in one direction but increases critical area in the orthogonal direction. To address this problem, Ref. [57] combines the one-dimensional movement for slack redistribution with a two-dimensional yield objective. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 784 Finals Page 784 19-9-2008 #15 Handbook of Algorithms for Physical Design Automation d c B: critical area in Y direction X-direction modification a b b2 b1 X A: critical area in X direction Yield cost = A+B FIGURE 37.7 Movement of wire b in x-direction decreases critical area in x-direction but increases critical area in y-direction. (Reproduced from Heng, F.L. and Chen, Z., VLSI yield enhancement through layout modification, IBM T.J. Watson Research Report, 1999.) The first compaction based algorithm to improve yield was given in Ref. [55]. A heuristic algorithm increases the spacing of layout objects through a series of spacing iterations in one direction. Only objects off the critical path are allowed to move maintaining the original layout area. The defect sensitivity of open-circuit type faults is reduced by increasing the width of certain noncritical elements in the layout. In Ref. [56] the slack redistribution problem in one direction was transformed into a network flow problem, which can be solved via the fast wirelength minimization algorithm of Ref. [59]. The layout is represented by a constraint graph where a node corresponds to a layout object and an edge links the nodes of two adjacent layout objects. The cost of each graph edge is an estimate of the fault probability between the two corresponding objects, expressed as a function of the length of the graph edge, that can be approximated by a convex piecewise linear cost function. Another one-dimensional compaction based formulation is given in Ref. [58] where first the critical area rectangles for one chosen defect size are computed. The standard compaction area optimization objective is enhanced with the additional terms of minimizing the critical area rectangles, which are reduced into functions of original layout variables. In this manner, the original compaction algorithm is upgraded with yield enhancement without introducing extra variables or constraints. A noncompaction-based approach in this category is based on postroute optimization using a rubber-band wiring model [60]. The layout is given in a rubber-band sketch (RBS) form, which represents every layer of interconnect as a set of flexible rubber-bands with elastic properties. Wire spreading is achieved by estimating the critical area of the RBS and exploiting the flexibility of the rubber band behavior while maintaining wire connectivity. For more information see Ref. [60]. Heuristic layout changes to improve yield are described in Ref. [61] through the use of a set of local rules for contacts, metal and polysilicon layers. A system that allows the user to first evaluate layout modifications by applying them to samples only of the chip layout, rather than the entire layout, is described in Ref. [62]. The results from these samples can be used to define the modifications to be applied to the whole chip. An effective way to reduce open faults is the introduction of redundant interconnects. Using redundant interconnects, the potential for open faults reduces at the cost of increasing the potential for shorts. By trading off, the two overall design reliability can increase. The problem was formulated in Ref. [63] as a variant of the classic 2-edge connectivity augmentation problem taking into account a wirelength increase budget, Steiner points, and routing obstacles. The formulation is as follows: Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 Yield Analysis and Optimization Finals Page 785 19-9-2008 #16 785 Manhattan routing tree augmentation (MRTA) problem: Given a rectilinear feasible routing region (FRR), a rectilinear Steiner routing tree T within FRR, and a wirelength budget W , find a set of augmenting paths. A within the FRR such that the total length of augmenting paths is at most W , and the total length of edges of T that ate nonbridges in G = T ∪ A is maximum. An exact algorithm based on an integer programming formulation, and a greedy heuristic algorithm that iteratively adds an augmenting path between vertices were given in Ref. [63]. Experimental results show that the greedy augmentation method achieves significant increase in reliability, as measured by the percentage of biconnected tree edges, with only small increase in wirelength. In addition to reducing the potential for opens, redundant interconnects have also been proposed in clock networks to overcome the clock skew variation problem. In Ref. [64] cross links are inserted to a regular clock tree converting it to a nontree with lower skew variability and only a small increase in wirelength. Redundant via insertion provides another effective way of increasing design reliability and yield. Vias have an inherently low reliability (e.g., due to stress related via voids) and thus redundant via insertion is a good solution to reduce the yield loss by via failure. Typically redundant via insertion is done postrouting on a “wherever space is available” basis but considering redundant vias in detailed routing also has been proposed [65]. Note that an increased number of vias could have a negative impact in terms of routing area and may reduce critical area for via blocks at the cost of increasing the critical area for shorts. Overall, however, making appropriate trade-offs design reliability can increase considerably. Antenna fixes is another topic for improving design reliability. Because VLSI layers are formed one at a time during fabrication, dangling metal1 routes (e.g., nets not yet fully fabricated) connected to the polygate can cause stray charge deposition on gate damaging it. Methods to correct such situations include inserting jumpers in routes such that the maximum dangling route length is limited (see e.g., Ref. [66]). Diffusions diodes can also be inserted to provide a discharge path if space is available. 37.4.2 DESIGN RULES The abstraction of manufacturing constraints into a set geometric of constraints or design rules, for the layout designers to follow, has traditionally been the foundry’s main method to ensure a high probability of correct fabrication of integrated circuits. Typical design rules are constraints on width, spacing, or pattern density. The origins of design rules lie in the constraints imposed by various manufacturing steps such as lithography, etch, implant, and CMP. Other factors influencing design rule values include preserving scaling, area overhead, layout migratability,∗ and the ability of design tools and flows to handle them. Manufacturability implications of technology scaling have led to three major trends in design rules: • More complicated rule sets. The sheer number of design rules has been growing at a rapid pace with every technology generation. More process constraints have required new kinds of rules [67,68]. This has made physical verification, routing as well as custom layout very difficult and time-consuming tasks. • Restrictive design rules. To cope with sub-100 nm manufacturability concerns where manufacturing equipment is not keeping pace with feature scaling, radically restraining layout options has been proposed as a viable option [69,70]. One common restriction is to enforce regularity in layout that aids printability. An example of such a rule is allowing only one or two pitches on the polysilicon layer. ∗ The automatic migration of layouts from one technology generation to next is an important concern, especially for custom layouts. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 786 Finals Page 786 19-9-2008 #17 Handbook of Algorithms for Physical Design Automation • DFM rules. Most 90 and 65 nm design rule manuals include a separate set of nonminimum design rules. These design rules if obeyed by the layout, enhance its manufacturability. For example, the minimum metal-via enclosure can be 20 nm while the corresponding DFM rule can be 30 nm. The increased enclosure can reduce chances of loss of contact between metal route and via at the cost of increased routing area. Though design rules have served the industry well in the past as the abstraction layer, the inadequacy and suboptimality of such yes/no rules has led to a slow but steady adoption of model-based checking methods [68]. 37.4.3 CORNER-BASED DESIGN ANALYSIS Traditionally, static timing and power analysis tools have relied on two or more corners of process, voltage, and temperature or PVT. We are not going to discuss operating variations such as voltage fluctuations and temperature gradients here. Timing corners are typically specified as slow (S), typical (T), or fast (F). Thus, SS represents a process corner with slow PFET and slow NFET behavior. The common performance analysis process corners are (TT, SS, FF, SF, FS). Similarly, interconnect parasitics are extracted at multiple (usually two) corners. A more systematic approach to determine interconnect R/C corners is given in Ref. [71]. Usually, hold time violations are checked at the FF corner and setup time violations are checked at the SS corner. Similarly, interconnect parasitics can also have typical, minimum, and maximum values. The rationale for corner-based analyses lies in the fact that ensuring correct operation of the design at the PVT extrema ensures correct operation throughout the process and operation range. This assumption, though not strictly correct, usually holds well in practice. Corner-based analysis enables pessimistic but deterministic analysis and optimization of designs. Most modern physical design algorithms rely on corner-based design being acceptable. Sub-100 nm process issues (especially variability) have led to the following trends in corner-based design analysis and optimization. • More corners. As more complicated process effects emerge and as a result of nonmonotone dependence of delay on many of the process parameters, the number of PVT corners at which a design needs to be signed off is increasing. • On chip variation (OCV) analysis. To model within-die variation in static timing tools implicitly analyze clock paths and data paths at separate corners [72]. For example, for setup time analysis, the launching clock path may be analyzed at a slow corner while the capturing clock is analyzed at a fast corner and the data path is analyzed at the slow corner. This in essence tries to model the worst-case impact of on chip variation. Additional techniques such as common path pessimism removal (CPPR), which figures out the shared logic between launching and capturing paths to avoid pushing them to different corners, are used to reduce the inherent pessimism in OCV analysis. Though the runtime overhead of ever-increasing number of corners, the excess pessimism in corner-based analysis and fear of missing some corners in a high process-variability regime has led to an increasing interest in statistical analysis tools, corner-based design deterministic design optimization still remains mainstay of commercial parametric yield optimization. 37.4.4 FUTURE OF PARAMETRIC YIELD OPTIMIZATION As mentioned earlier, explicit parametric yield analysis and optimization is a relatively new field of research. Several interesting published works in the past few years have attempted to deal with the problem of manufacturing variability. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 Yield Analysis and Optimization 37.4.4.1 Finals Page 787 19-9-2008 #18 787 Methods for Systematic Variability There are several pattern-dependent process effects, which are systematic in nature. These can be compensated for during physical design to aid manufacturability and hence improve yield. The largest contributors in this bucket are CMP and photolithography. Metal filling and slotting techniques for CMP are discussed elsewhere in the book. Traditionally, design rules have been the method to optimize for systematic variation. Recently, more explicit mitigation of impact of systematic variation on circuit power and performance has been studied. For instance, some methods have tried to reduce CD variability by avoiding lithography-induced forbidden pitches during detailed placement [73] or detailed routing [74,75]. Making circuit more robust to focus variations has been studied in Refs. [76,77]. 37.4.4.2 Statistical Optimization Just as statistical analyses, statistical physical design is an active area of research with very little in terms of well-accepted methods of optimization. Deterministic physical design tends to generate a wall of slack. As the number of uncorrelated critical paths increase in a design, any of them can pop up to being critical and hence be the determinant of circuit delay. As a result, a higher wall of slack can mean a slower circuit delay distribution. Intentional under-optimization by assigning a penalty to paths that are close to critical has been suggested as a simple technique to overcome this issue [78]. Another approach in same vein assigns a delay penalty to every gate proportional to its delay variability [79] and uses standard static timing analysis in optimization. Other approaches explicitly rely on a statistical timing engine in a statistical sensitivity [80,81] or nonlinear programming based optimization [82]. The largest challenge in statistical physical design besides computational complexity is accurate modeling of physical reality. For example, ignoring parametric or spatial correlations (i.e., assuming independence or perfect correlation between performance or process random variables) can undo any benefit from statistical optimization. 37.5 CONCLUSION In this chapter, we have touched upon various sources of manufacturing yield loss in modern submicron processes. We have briefly described methods of yield calculation and optimization with emphasis on well-known methods related to random-defect driven yield loss. We have also discussed the emerging area of parametric yield analysis and optimization in physical design. REFERENCES 1. International Technology Roadmap for Semiconductors: Yield Enhancement. http://public.itrs. net, 2005. 2. Z.G. Song, S.P. Neo, S.K. Loh, and C.K. Oh. Root cause analyses of metal bridging for copper damascene process. In International Symposium for Testing and Failure Analysis, 2005. 3. Richard Goering. 90-, 65-nm yields prey to leakage. EE Times. http://www.eetimes.com/news/latest/ showArticle.jhtml?articleID=172303036, October 24, 2005. 4. W.-B Jone and K.S. Tsai. Confidence analysis for defect-level estimation of VLSI random testing. ACM Transactions on Design Automation of Electronic Systems, 3(3):389–407, July 1998. 5. S. Pateras, J. Hussain, and T. Martis. Reducing leakage-induced field returns. Whitepaper Logicvision Inc., 2005. 6. C. Constantinescu. Trends and challenges in VLSI circuit reliability. IEEE Micro, 23(4):14–19, July–August 2003. 7. M. Abramovici, M.A. Breuer, and A.D. Friedman. Digital Systems Testing and Testable Design. John Wiley & Sons, New York, 1994. 8. M. Orshansky and K. Keutzer. A general probabilistic framework for worst-case timing analysis. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 556–561, 2002. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 788 Finals Page 788 19-9-2008 #19 Handbook of Algorithms for Physical Design Automation 9. H. Chang and S.S. Sapatnekar. Statistical timing analysis considering spatial correlations using single PERT-like traversal. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 621–625, 2003. 10. A. Agarwal, D. Blaauw, and V. Zolotov. Statistical timing analysis for intra-die process variations with spatial correlations. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 900–907, 2003. 11. C. Visweswariah, K. Ravindran, K. Kalafala, S.G. Walker, and S. Narayan. First-order incremental block-based statistical timing analysis. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 331–336, 2004. 12. International Technology Roadmap for Semiconductors: Front End Processes. http://public.itrs.net, 2005. 13. S.-D. Kim, H. Wada, and J.C.S. Woo. TCAD-based statistical analysis and modeling of gate line-edge roughness effect on nanoscale mos transistor performance and scaling. IEEE Transactions on Semiconductor Manufacturing, 17(2):192–200, May 2004. 14. P. Gupta, A.B. Kahng, C.-H. Park, K. Samadi, and X. Xu. Wafer topography-aware optical proximity correction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(12):2747– 2756, December 2006. 15. S. Borkar, T. Karnik, S. Narendra, J. Tschanz, A. Keshavarzi, and V. De. Parameter variations and impact on circuits and microarchitecture. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 338–342, 2003. 16. D. Boning and S. Nassif. Models of process variations in device and interconnect. In A. Chandrakasan, W.J. Bowhill, and F. Fox, Eds., Design of High-Performance Microprocessor Circuits, pp. 98–116. WileyIEEE Press, New York, 2000. 17. C. Visweswariah. Death, taxes and failing chips. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 343–347, 2003. 18. R.R. Rao, A. Devgan, D. Blaauw, and D. Sylvester. Modeling and analysis of parametric yield under power and performance constraints. IEEE Design & Test, 22(4), 376–385, July–August 2005. 19. H. Chang and S.S. Sapatnekar. Full-chip analysis of leakage power under process variations, including spatial correlations. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 523–528, 2005. 20. A. Srivastava, D. Sylvester, and D. Blaauw. Statistical Analysis and Optimization for VLSI. Springer, Boston, MA, 2005. 21. L. Chen, L. Milor, C. Ouyang, W. Maly, and Y. Peng. Analysis of the impact of proximity correction algorithms on circuit performance. IEEE Transactions on Semiconductor Manufacturing, 12(3):313–322, August 1999. 22. M. Orshansky, L. Milor, and C. Hu. Characterization of spatial intrafield gate CD variability, its impact on circuit performance, and spatial mask-level correction. IEEE Transactions on Semiconductor Manufacturing, 17(1):2–11, February 2004. 23. P. Gupta and F.-L. Heng. Toward a systematic-variation aware timing methodology. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 321–326, 2004. 24. J. Yang, L. Capodieci, and D. Sylvester. Advanced timing analysis based on post-OPC extraction of critical dimensions. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 359–364, 2005. 25. C.H. Stapper. Modeling of integrated circuit defect sensitivities. IBM Journal of Research and Development, 27(6):549–557, November 1983. 26. I.A. Wagner and I. Koren. An interactive VLSI CAD tool for yield estimation. IEEE Transactions on Semiconductor Manufacturing,8(2):130–138, May 1995. 27. W. Maly. Computer-aided design for VLSI circuit manufacturability. In Proceedings of the IEEE, pp. 356–392, February 1990. 28. A.V. Ferris-Prahhu. Introduction to Semiconductor Device Yield Modeling. Artech House, Norwood, MA, 1992. 29. A.V. Ferris-Prabhu. Role of defect size distribution in yield modeling. IEEE Transactions on Electron Devices, 32(9):1727–1736, September 1985. 30. A.V. Ferris-Prabhu. Defect size variations and their effect on the critical area of VLSI devices. IEEE Journal of Solid State Circuits, 20(4):878–880, August 1985. 31. E. Papadopoulou. Critical area computation for missing material defects in VLSI circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20(5):583–597, May 2001. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 Yield Analysis and Optimization Finals Page 789 19-9-2008 #20 789 32. H. Walker and S.W. Director. VLASIC: A yield simulator for integrated circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 5(4):541–556, April 1986. 33. C.H. Stapper. Modeling of defects in integrated circuit photolithographic patterns. IBM Journal of Research and Development, 28(4):461–475, July 1984. 34. G.A. Allan. Yield prediction by sampling IC layout. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19(3):359–371, March 2000. 35. D.M.H. Walker and D.S. Nydick. DVLASIC; Catastrophic yield simulator in a distributed processing environment. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 9(6): 655–664, June 1990. 36. G.A. Allan and A.J. Walton. Efficient extra material critical area algorithms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(10):1480–1486, October 1999. 37. I. Bubel, W. Maly, T. Wass, P. Nag, H. Hartmann, D. Schmitt-Landsiedel, and S. Griep. AFFCA: A tool for critical area analysis with circular defects and lithography deformed layout. In Proceedings of the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, pp. 10–18, 1995. 38. A.L. Jee and F.J. Ferguson. CARAFE: An inductive fault analysis tool for CMOS VLSI circuit. In Proceedings of the IEEE VLSI Test Symposium, pp. 92–98, 1992. 39. P.K. Nag and W. Maly. Hierarchical extarction of critical area for shorts in very large ICs. In Proceedings of the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, pp. 19–27, 1995. 40. S. T. Zachariah and S. Chakravarty. Algorithm to extract two-node bridges. IEEE Transactions on VLSI Systems, 11(4):741–744, April 2003. 41. J. Pineda de Gyvez and C. Di. IC defect sensitivity for footprint-type spot defects. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 11(5):638–658, May 1992. 42. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry, Algorithms and Applications. Springer-Verlag, Berlin, Germany, 1997. 43. W.A. Pleskacz, C.H. Ouyang, and W. Maly. Extraction of critical areas for opens in large VLSI circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(2):151–162, 1999. 44. D.K. de Vries and P. L. C. Simon. Calibration of open interconnect yieldmodels. In Proceedings of the IEEE Intermational Symposium on Defect and Fault Tolerance in VLSI Systems, pp. 26–33, 2003. 45. E. Papadopoulou and D.T. Lee. Critical area computation via Voronoi diagrams. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(4):463–474, April 1999. 46. E. Papadopoulou. The Hausdorff Voronoi diagram of point clusters in the plane. Algorithmica, 40:63–82, December 2004. 47. Z. Chen, E. Papadopoulou, and Jinhui Xu. Robustness of k-gon Voronoi diagram construction. Information Processing Letters, 97(4):138–145, February 2006. 48. E. Papadopoulou and D.T. Lee. The l∞ Voronoi diagram of segments and VLSI applications. International Journal of Computational Geometry and Applications, 11(5):503–528, October 2001. 49. D.N. Maynard and J.D. Hibbeler. Measurement and reduction of critical area using Voronoi diagrams. In Advanced Semiconductor Manufacturing IEEE Conference and Workshop, 2005, pp. 243–249. 50. Z. Stanojevic and D.M.H. Walker. FedEx–A fast bridging fault extractor. In Proceedings of the IEEE International Test Conference, pp. 696–703, 2001. 51. K. Wu, D. Thon, and P. Mayor. Collaborative DFM critical for enabling nanometer design. FSA Fabless Forum. http://www.fsa.org/publications/forum/article.asp?article=0503/wu, March 2005. 52. IEEE International Conference on Microelectronic Test Structures. 53. E.P. Huijbregts, H. Xue, and J.A.G. Jess. Routing for reliable manufacturing. IEEE Transactions on Semiconductor Manufacturing, 8(2), 188–194, May 1995. 54. S.Y. Kuo. YOR: A yield optimizing routing algorithm by minimizing critical areas and vias. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 12(9):1303–1311, September 1993. 55. V.K.R. Chiluvuri and I. Koren. Layout synthesis techniques for yield enhancement. IEEE Transactions on Semiconductor Manufacturing, 8(2):178–187, May 1995. 56. C. Bamji and E. Malavasi. Enhanced network flow algorithm for yield optimization. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 746–751, 1996. 57. F.L. Heng and Z. Chen. VLSI yield enhancement through layout modification. IBM T.J. Watson Research Report, 1999. 58. Y. Bourai and C.J.R. Shi. Layout compaction for yield optimization via critical area minimization. In Design and Test in Europe, pp. 122–125, 2000. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C037 790 Finals Page 790 19-9-2008 #21 Handbook of Algorithms for Physical Design Automation 59. R. Varadarajan and G. Lakhani. A wire length minimization algorithm for circuit layout compaction. In Proceedings of the IEEE International Symposium on Circuits and Systems, 1987, pp. 276–279. 60. J.Z. Su and W. Dai. Post route optimization for improved yield using a rubber-band wiring model. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 700–706, 1997. 61. G.A. Allan and A.J. Walton. A yield improvement technique for IC layout using local design rules. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 11(11):1355–1360, November 1992. 62. G.A. Allan. Targeted layout modifications for semiconductor yield/reliability enhancement. IEEE Transactions on Semiconductor Manufacturing, 17(4):573–581, November 2004. 63. A.B. Kahng, B. Liu, and I.I. Mandoiu. Non-tree routing for reliability and yield improvement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 23(1):148–156, January 2004. 64. A. Rajaram, J. Hu, and R. Mahapatra. Reducing clock skew variability via cross links. In Proceedings of the ACM/IEEE Design Automation Conference, pp. 18–23, 2004. 65. G. Xu, L. Huang, D.Z. Pan, and M.D.-F. Wong. Redundant-via enhanced maze routing for yield improvement. In Proceedings of the Asia-South Pacific Design Automation Conference, 2005, pp. 1148–1151. 66. B.-Y. Su, Y.-W. Chang, and J. Hu. An optimal jumper insertion algorithm for antenna avoidance/fixing on general routing trees with obstacles. In Proceedings of the ACM International Symposium on Physical Design, 2006, pp. 56–63. 67. A.B. Kahng. Research directions for coevolution of rules and routers. In Proceedings of the ACM/IEEE International Symposium on Physical Design, pp. 122–125, 2003. 68. P. Rabkin. DFM for advanced technology nodes: Fabless view. Future Fab International. Issue 20. http://www.future-fab.com, 2006. 69. L. Liebmann, G. Northrop, J. Culp, L. Sigal, A. Barish, and C. Fonseca. Layout optimization at the pinnacle of optical lithography. In Proceedings of SPIE, vol. 5042, pp. 1–14, 2003. 70. M. Lavin, F.-L. Heng, and G. Northrup. Backend cad flows for restrictive design rules. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, p. 739746, 2004. 71. N. Chang, V. Kanevsky, O.S. Nakagawa, K. Rahmat, and S.-Y. Oh. Fast generation of statistically-based worst-case modeling of on-chip interconnect. In Proceedings of the IEEE International Conference on Computer Design, 1997, 720–725. 72. M. Weber. My head hurts, my timing stinks, and I don’t love on-chip variation. In SNUG, Boston. http://www.siliconlogic.com/pdf/OCVstinks_MattWeber_SLE.pdf, 2002. 73. P. Gupta, A.B. Kahng, and C.-H. Park. Enhanced resist and etch CD control by design perturbation. In Proceedings of the 25th SPIE BACUS Symposium on Photomask Technology and Management, 2005, pp. 3P1–3P11. 74. S.C. Shi, A.K. Wong, and T.-S. Ng. Forbidden-area avoidance with spacing technique for layout optimization. In Proceedings of SPIE Design and Process Integration for Microelectronic Manufacturing II, Vol. 5379, pp. 67–75, 2004. 75. J. Mitra, P. Yu, and D.Z. Pan. RADAR: RET-aware detailed routing using fast lithography simulations. In Proceedings of the ACM/IEEE Design Automation Conference, 2005, pp. 369–372. 76. P. Gupta, A.B. Kahng, Y. Kim, and D. Sylvester. Self-compensating design for focus variation. In Proceedings of the IEEE/ACM Design Automation Conference, pp. 365–368, 2005. 77. A.B. Kahng, S. Muddu, and P. Sharma. Defocus-aware leakage estimation and control. In Proceedings of the International Symposium on Low Power Electronics and Design, pp. 263–268, 2005. 78. X. Bai, C. Visweswariah, P.N. Strenski, and D.J. Hathaway. Uncertainty-aware circuit optimization. In Proceedings of the IEEE/ACM Design Automation Conference, pp. 58–63, 2002. 79. S. Boyd, S.-J. Kim, D. Patil, and M. Horowitz. A heuristic method for statistical digital circuit sizing. In Proceedings of the SPIE International Symposium on Microlithography, 2006, pp. 08-1–08-9. 80. M.R. Guthaus, N. Venkateswaran, C. Visweswariah, and V. Zolotov. Gate sizing using incremental parameterized statistical timing. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 1029–1036, 2005. 81. M. Hashimoto and H. Onodera. A performance optimization method by gate sizing using statistical static timing analysis. In Proceedings of the ACM International Sympoium on Physical Design, pp. 111–116, 2000. 82. E.T.A.F. Jacobs and M.R.C.M. Berkelaar. Gate sizing using a statistical delay model. In Proceedings of Design and Test in Europe, pp. 283–290, 2000. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C038 Finals Page 791 23-9-2008 #2 38 Manufacturability-Aware Routing Minsik Cho, Joydeep Mitra, and David Z. Pan CONTENTS 38.1 38.2 38.3 38.4 Introduction.. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Major Manufacturability Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Rule-Based Approach versus Model-Based Approach .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Manufacturability-Aware Routing Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 38.4.1 CMP-Aware Routing for Topography Variation Minimization . . . . .. . . . . . . . . . . . . . 38.4.2 Critical-Area-Aware Routing for Random Defect Minimization .. . .. . . . . . . . . . . . . . 38.4.3 Lithography-Aware Routing for Printability . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 38.4.4 Redundant-Via- and Antenna-Effect-Aware Routings . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 38.5 Dealing with Manufacturing Rules during Detailed Routing . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 38.5.1 Representative Rule 1—Minimum Edge Rule . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 38.5.2 Representative Rule 2—Width-Dependent Parallel-Length Spacing Rule. . . . . . . . 38.5.3 Representative Rule 3—Width-Dependent Influence Spacing Rule . . . . . . . . . . . . . . 38.6 Conclusion .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Acknowledgments .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 791 792 793 794 794 796 798 801 802 802 804 805 805 806 806 38.1 INTRODUCTION Nanometer very large scale integration (VLSI) design is facing increasing challenges from manufacturing limitations, arising from factors such as printability issues because of deep subwavelength lithography, topography variations because of chemical–mechanical polishing (CMP), and random defects because of missing/extra material, the via void. Thus, for nanometer designs, conventional design closure may not lead to closure in manufacturing because of yield factors. It has been shown, however, that the majority of the yield loss is strongly layout-dependent (as demonstrated in Chapters 35 through 37), and therefore, manufacturability-aware layout optimization can play a key role in the overall yield improvement of a design. In this chapter, we focus on manufacturability-aware routing. Although manufacturability considerations may be brought to bear on earlier design stages such as logic synthesis and placement [1–3], routing is often believed to be one of the most effective stages to address the manufacturability issues because of the following reasons [4–7]: (1) the key manufacturing issues (e.g., topography variation because of CMP, random defects, lithography, and redundant vias) are tightly coupled with the distribution of interconnects, which is mainly determined by routing; (2) routing is the last major VLSI physical design step before manufacturing, and thus it has more a comprehensive and accurate picture on the expected manufacturability; (3) routing still has considerable design flexibility to find a reasonable trade-off between manufacturability and conventional design objectives 791

Handbook of algorithms for physical design automation part 81

Nội dung