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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C022 462 Finals Page 462 24-9-2008 #17 Handbook of Algorithms for Physical Design Automation TABLE 22.1 Netweighting for RISA Routability Model Pin Count Netweight q Pin Count Netweight q 1.0000 1.0828 1.1536 1.2206 1.2823 1.3385 1.3991 1.4493 15 20 25 30 35 40 45 50 1.6899 1.8924 2.0743 2.2334 2.3895 2.5356 2.6625 2.7933 1–3 4 5 6 7 8 9 10 22.5.2 OVERFLOW WITH LOOK-AHEAD Wang et al. tried a number of cost functions that cover both congestion and wirelength objectives [38]. Let WL be the total wirelength and OF be the total overflow of the current placement. The total overflow is the sum of overflow for all the placement bins. The overflow is the difference between routing demand and routing supply of the bin, if demand is larger. The following seven cost functions are proposed (Figure 22.10): 1. WL: total HPWL (Figure 22.10a) 2. OF: total overflow (Figure 22.10b) 3. Hybrid: (1 − α)WL + αOF, 0 ≤ α ≤ 1 (Figure 22.10c) 4. TimeHybrid: (1 − αT )WL + αT OF, α is changing during the placement process (Figure 22.10d) 5. QL: quadratic function when demand is smaller than supply; linear function when demand is greater than supply (Figure 22.10e) Cost WL S OF (a) Number of nets crossing (b) Cost Cost (d) S S (1−a)WL + aOF Number of nets crossing (e) S Number of nets crossing (c) Number of nets crossing Cost QL LQ LkAhd S- d Cost Cost S Number of nets crossing (f) FIGURE 22.10 Cost function versus number of crossing nets on each global bin. S Number of nets crossing Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C022 Finals Page 463 24-9-2008 #18 463 Congestion-Driven Physical Design 6. LQ: linear function when demand is smaller than supply; quadratic function when demand is greater than supply (Figure 22.10f) 7. Look-Ahead: start considering congestion cost when demand is close enough to supply All these cost functions are experimented in both global placement and detailed placement stages. The authors found that during global placement, none of the objectives works well except total wirelength. However, in detailed placement stage, several cost functions are reasonably good and LookAhead gives the best result in terms of congestion. 22.5.3 A-TREE ROUTER Chang et al. integrate a fast A-tree router into a multilevel simulated-annealing global-placement engine called mPG [8]. mPG is inspired by the recent success of the multilevel methods in efficiently handling bipartitioning problem [18]. It consists of three stages: coarsening by clustering, initial placement on the top level, and uncoarsening with refinement. The A-tree router is based on a fast, congestion avoidance two-bend router (LZ-router). The rational behind that is the dominance of LZ-shaped routes in the actual layout. Multipin nets are decomposed to two-pin nets. An incremental A-tree algorithm is developed to efficiently update the routing topology for any pin location change. This A-tree router can be used in conjunction with HPWL at any level of refinement. In practice, the authors find that it is most effective to consider routing cost at the finest level. This is consistent with the conclusion in Ref. [38] that minimizing congestion cost early in the placement flow may have negative effect. The cost function for congestion-driven mPG is the quadratic sum of the wire usages of all the bins. The wire usage for each bin is the sum of the routed wirelength of the nets that pass through, start from, or end at this bin. Unlike the overflow method, there is no threshold for routing supply in the cost function. This cost function encourages the simulated annealing moves that can lead shorter routed length and less congestion. If the wire usage of a bin increases from W to W +d, the congestion cost change is d 2 + 2Wd. For a long wire-segment crossing multiple bins, the delta congestion cost can be quickly computed using the sum of the current wire usages of the involved bins. 22.5.4 SPARSE PARAMETER Hu and Marek-Sadowska [16] proposed a congestion cost function named sparse parameter. With this cost function, the congestion-driven placement does not follow the traditional estimate-andeliminate strategy. Instead, it tries to reduce the excessive usage of routing resources caused by local nets so that more routing resources are available for the uncertain global nets. The idea of sparse-parameter cost function originates from two facts. First, the local nets that coming in/out a region vastly determine the congestion situation of the region. This is verified with empirical data. Second, minimizing the number of local nets alone could be wrong, because the cost is often the longer wirelength and the congestion caused by global nets. The authors derive the following function as the wire cost WS(b) for a placement bin b: WS(b) = wi BB(i) d(i) i∈LC(b) where LC(b) is all the nets that enter or leave the region b wi is the weights to translate half-perimeter length to estimated routed length for net i BB(i) is the HPWL for net i d(i) is the degree of net i Once WS(b) is computed for all the bins, a mapping function is used to convert WS(b) to the sparse parameter P(b): Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C022 464 Finals Page 464 24-9-2008 #19 Handbook of Algorithms for Physical Design Automation P(b) Pmax I Pave Pmin II WS(b) WSmin WSave WSmax FIGURE 22.11 Sparse function WS(b) to P(b). P(b) = aWS(b) + b where a and b are constants obtained from three points: (WSmin , Pmin ), (WSave , Pave ), and (WSmax , Pmax ). WSmin , WSave , and WSmax are minimum, average, and maximum WS(b) over all the bins, respectively. Pmin , Pave , and Pmin are user defined values. The curve of this conversion indicates a sharper slope from WSave to WSmax , meaning higher cost when the congestion of a region is above the average (Figure 22.11). The above function works well when integrated in simulated annealing algorithm. Particularly, the wirelength increase is negligible compared to pure half-perimeter optimization. The runtime with the sparse parameter is about 2.5 or 3 times slower. Because of lack of access to real industry router, there is no detailed routing step in the experimental flow. Consequently, the internal routes within the bin are not modeled in the cost function, because they do not contribute to the global routing results (the global router used in Ref. [19] works on bin level and ignore the internal nets). The authors suggest to use some sort of pin-density metric to adjust the sparse parameter. 22.6 CONCLUSION In this chapter, we reviewed various techniques for reducing congestion and achieving routable designs. Placement-independent techniques use information from netlist connectivity to guide logic synthesis or placement. Addressing congestion in the early design has deep impact on the final design routability. In global-placement stage, congestion modeling is paramount for achieving the appropriate distribution. Pin density and fast routing estimation can be used to guide the placement engine. Detailed placement stage has more accurate routing information. Cell spreading, cell moving, or swapping should consider routing congestion and are very effective for allieviating local congestion. In summary, placement is the most important stage to achieve routable design. Many studies have shown that congestion problem can be and should be solved in placement stage by applying the right techniques at the right place. REFERENCES 1. S. N. Adya, S. Chaturvedi, J. A. Roy, D. Papa, and I. L. Markov, Unification of partitioning, floorplanning and placement, International Conference of Computer Aided Design (ICCAD), San Jose, CA, 2004, pp. 550–557. 2. S. N. Adya and I. L. Markov, On whitespace and stability in mixed-size placement and physical synthesis, International Conference on Computer Aided Design (ICCAD), San Jose, CA, 2003, pp. 311–318. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C022 Congestion-Driven Physical Design Finals Page 465 24-9-2008 #20 465 3. S. N. Adya, I. L. Markov, and P. G. Villarrubia, On whitespace and stability in physical synthesis, Integration: The VLSI Journal, 39(4): 340–362, 2006. 4. C. J. Alpert, G. -J. Nam, and P. G. Villarrubia, Free space management for cut-based placement, Proceedings of the 2002 IEEE/ACM International Conference on Computer-Aided Design, San Jose, CA, 2002, pp. 746–751. 5. K.D. Boese, A.B. Kahng, and G. Robins, High-performance routing trees with identified critical sinks, DAC, Proceedings of the 30th International Conference on Design Automation Conference (DAC), Dallas, TX, pp. 182–187, 1993. 6. U. Brenner and A. Rohe, An effective congestion driven placement framework, Proceedings of the 2002 International Symposium on Physical Design (ISPD), San Diego, CA, pp. 6–11, 2002. 7. A. E. Caldwell, A. B. Kahng, and I. L. Markov, Can recursive bisection alone produce routable placements? Proceedings of the 37th Conference on Design Automation Conference (DAC) Los Angeles, CA, pp. 477– 482, 2000. 8. C. -C. Chang, J. Cong, Z. Pan, and X. Yuan, Multi-level global placement with congestion control, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 22(4):395–409, 2003. 9. T. -C. Chen, Y. -W. Chang, and S. -C. Lin, IMF: Interconnect-driven multilevel floorplanning for large-scale building-module designs, Proceedings of the 2005 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, CA, pp. 159–164, 2005. 10. C. L. Cheng, RISA: Accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, California, pp. 690–695, 1994. 11. C. C. N. Chu. FLUTE: Fast lookup table based wirelength estimation technique, Proceedings of the 2004 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, CA, pp. 696–701, 2004. 12. E. Detjens, G. Gannot, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang, Technology mapping in MIS, ICCAD, 1987, pp. 116–119. 13. A. E. Dunlop and B. W. Kernighan, A procedure for placement of standard cell VLSI circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits, 4(1): pp. 92–98, January 1985. 14. P. Gopalkrishnan, A. Odabasioglu, L. T. Pilleggi, and S. Raje, Overcoming wireleoad model uncertainity during physical design, Proceedings of the 2001 International Symposium of Physical Design (ISPD) Sonoma, CA, pp. 182–189, 2001. 15. S. Hojat and P. Villarrubbia, An integrated placement and synthesis approach for timing closure of power PC microprocessors, ICCD, 1997, pp. 206–210. 16. B. Hu and M. Marek-Sadowska, Congestion minimization during placement without estimation, Proceedings of the 2002 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, CA, pp. 739–745, 2002. 17. D. Jariwala and J. Lillis, On interactions between routing and detailed placement, Proceedings of the 2004 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, CA, pp. 387–393, 2004. 18. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, Multilevel hypergraph partitioning: Applications in VLSI domain, Proceedings of the 34th Annual Conference on Design Automation (DAC) Anaheim, CA, pp. 526–529, 1997. Available at http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview. 19. R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh, Predictable routing, Proceedings of the 2000 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, CA, pp. 110–114, 2000. Available at http://www.ece.ucsb.edu/kastner/labyrinth/. 20. A. B. Kahng and G. Robins, A new class of iterative Steiner tree heuristics with good performance, IEEE Transactions on Computer-Aided Design, 11(7): 893–902, 1992. 21. A. B. Kahng, I. I. Mandoiu, and A. Zelikovsky. Highly scalable algorithms for rectilinear and octilinear Steiner trees, Proceedings of the 2003 Conference on Asia South Pacific Design Automation Conference (ASPDAC), Kitakyushu, Japan, pp. 827–833, 2003. 22. A. Kahng and S. Reda, Placement feedback: A concept and method for better min-cut placement, Proceedings of the 41st Annual Conference on Design Automation (DAC) San Diego, CA, pp. 357–362, 2004. 23. J. M. Kleinhans, G. Sigl, F.M. Johannes, and K.J. Antreich, VLSI placement by quadratic programming and slicing optimization, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 10(3): 356–361, 1991. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C022 466 Finals Page 466 24-9-2008 #21 Handbook of Algorithms for Physical Design Automation 24. K. Keutzer, DAGON: Technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE Conference on Design Automation Conference (DAC) Miami Beach, FL, pp. 341–347, 1987. 25. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (4598): 671–680, May 1983. 26. P. Kudva and A. Dougherty, Metrics for structural logic synthesis, Proceedings of the 2002 IEEE/ACM International Conference on Computer-Aided Design (ICCAD) San Jose, CA, pp. 551–556, 2002. 27. J. Lou, S. Krishnamoorthy, and H. S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 International Symposium on Physical Design (ISPD) Sonoma, CA, pp. 112–117, 2001. 28. C. Li, M. Xie, C. -K. Koh, J. Cong, and P. H. Madden, Routability-driven placement and white space allocation, Proceedings of the 2004 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 394–401, 2004. 29. P. N. Parakh, R. B. Brown, and K. A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th Annual Conference on Design Automation Conference (DAC) San Francisco, CA, pp. 275–278, 1998. 30. J. A. Roy, J. F. Lu, and I. L. Markov, Seeing the forest and the trees: Steiner wire-length optimization in placement, Proceedings of the 2006 International Symposium on Physical Design (ISPD), San Jose, CA, pp. 78–85, 2006. 31. D. Pandini, L. T. Pileggi, and A. J. Strojwas, Congestion-aware logic synthesis, Proceedings of the Conference on Design, Automation and Test in Europe (DATE), p. 664, 2002. 32. C. Sechen, The TimberWolf3.2 standard cell placement and global routing program, User’s Guide for Version 3.2, Release 2. 33. C. Sechen, Chip-planning, placement, and global routing macro/custom cell integrated circuits using simulated annealing, Proceedings of the 25th ACM/IEEE Conference on Design Automation Conference (DAC), Atlantic City, NJ, pp. 73–80, 1998. 34. N. Selvakkumaran, P. Parakh, and G. Karypis, Perimeter-degree: A priori metric for directly measuring and homogenizing interconnection complexity in multilevel placement, Proceedings of the 2003 International Workshop on System-Level Interconnect Prediction (SLIP), Monterey, CA, pp. 53–59, 2003. 35. N. Selvakkumaran and G. Karypis, Theto-A fast, scalable and high quality partitioning driven placement tool, Technical report, University of Minnesota, 2004. 36. K. Takahashi, K. Terai, M. Nakajima, and K. Sato, Min-cut placement with global objective functions for large scale sea-of-gates arrays, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 14(4): 434–446, 1995. 37. J. Vygen, Algorithms for large-scale flat placement, Proceedings of the 34th Annual Conference on Design Automation Conference (DAC), Anaheim, CA, pp. 746–751, 1997. 38. M. Wang, X. Yang, and M. Sarrafzadeh, Congestion minimization during placement, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19(10): 1140–1148, 2000. 39. J. Westra, C. Bartels, and P. Groeneveld, Probabilistic congestion prediction, Proceedings of the 2004 International Symposium Physical Design (ISPD), Phoenix, A2, pp. 204–209, 2004. 40. X. Yang, B. -K. Choi, and M. Sarrafzadeh, Routability driven white space allocation for fixed-die standardcell placement, Proceedings of the 2002 International Symposium on Physical Design (ISPD) San Diego, CA, pp. 42–47, 2002. 41. X. Yang, B. -K. Choi, and M. Sarrafzadeh, Routability driven white space allocation for fixed-die standardcell placement, IEEE Transactions on CAD, 22(4): 410–419, April 2003. 42. X. Yang, R. Kastner, and M. Sarrafzadeh, Congestion reduction during placement based on integer programming, Proceedings of the 2001 IEEE/ACM International Conference on Computer-Aided Design (ISPD), San Jose, CA pp. 573–576, 2001. 43. X. Yang, M. Wang, R. Kastner, S. Ghiasi, and M. Sarrafzadeh, Congestion reduction during placement with provably good approximation bound, ACM Transactions on Design Automation of Electronic Systems (TODAES), 8(3): 316–333, 2003. 44. K. Zhong and S. Dutt, Algorithms for simultaneous satisfaction of multiple constraints and objective optimization in a placement flow with application to congestion control, Proceedings of the 39th Conference on Design Automation Conference (DAC), New Orleans, Louisiana, pp. 854–859, 2002. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_S005 Finals Page 467 24-9-2008 #2 Part V Net Layout and Optimization Alpert/Handbook of Algorithms for Physical Design Automation AU7242_S005 Finals Page 468 24-9-2008 #3 Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 Finals Page 469 23-9-2008 #2 Routing Formulation 23 Global and Maze Routing Muhammet Mustafa Ozdal and Martin D. F. Wong CONTENTS 23.1 Introduction.. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.2 Grid Model . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.2.1 Channel-Based Graph Model.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.2.2 Tile-Based Graph Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.3 Capacity Computation . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.4 Routing Metrics . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.4.1 Congestion . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.4.2 Bend Count . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.4.3 Wirelength.. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.4.4 Timing .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.4.5 Coupling .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.5 Single Net Routing .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.5.1 Lee’s Maze Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.5.2 Maze-Routing Enhancements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.5.3 Line-Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.5.4 Pattern Routing.. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.5.5 Routing Nets with Multiple Terminals.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.6 Routing Multiple Nets . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.6.1 Sequential Routing .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.6.2 Concurrent Routing ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 23.7 Conclusions.. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 469 470 470 471 472 473 473 474 474 475 475 475 476 477 479 481 481 482 482 484 484 484 23.1 INTRODUCTION Global routing is an important step in the physical design process. Because of the complexity of the overall routing problem, it is typically solved in two steps: global routing and detailed routing. During global routing, nets are routed on a coarse-grain grid structure with the objective of determining the regions within which each net will be routed. After an approximate routing solution is determined for each net, the second step is to perform detailed routing to find the exact routes of all nets. Because detailed routing is performed based on the global routes, the quality of the final interconnects depends largely on the quality of the global routing solutions. Typically, detailed routing grids are much larger than the coarse-grain grids of global routing, and the solution space for individual nets is much larger because of the fine-grain modeling of routing resources. On the other hand, the resource model used in global routing is simplified, and the complexity of global routing one net is typically much smaller than the corresponding complexity of 469 Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 470 Finals Page 470 23-9-2008 #3 Handbook of Algorithms for Physical Design Automation detailed routing. Hence, global routing helps detailed routing in two ways. First, the complexity of detailed routing can be reduced by confining its search space to the regions identified by the global routes. Second, it is usually prohibitive to use expensive sophisticated algorithms during detailed routing because of the high problem complexity. Furthermore, the order in which nets are routed can significantly impact the routing quality. Hence, it is the objective of global routing to find a solution such that several metrics (such as routability, wirelength, timing) can be optimized for all nets. In this chapter, we discuss the basics of global routing formulation, and a high-level overview of global routing algorithms. The rest of the chapter is organized as follows. Section 23.2 presents a global routing grid model, and Section 23.3 describes how to set the edge capacities in such a model. The common objectives of global routing algorithms are discussed in Section 23.4. Section 23.5 describes algorithms to route a single net, with a particular focus on maze routing and its extensions. Finally, Section 23.6 provides a high-level overview of algorithms to route multiple nets. 23.2 GRID MODEL Global routing is typically represented as a graph problem to capture the adjacencies and capacities of the routing region. A channel-based global routing model has been used for many years. This model is appropriate for circuits with limited number of routing layers, where standard cells or macroblocks occupy most of the routing space. However, as the number of routing layers is increasing, aggressive over-the-cell routing has become more popular in the recent years. In this model, the global routing problem is represented as a grid graph. In the following subsections, we describe these models in more detail. 23.2.1 CHANNEL-BASED GRAPH MODEL A typical layout contains a set of cells or macroblocks of which terminals need to be routed to each other. If the number of routing layers is small, the routing space is limited to the channels between these cells or macroblocks. Figure 23.1a illustrates a set of macroblocks and the available routing resources between them. The most natural representation of this routing model is a channel intersection graph, G, where there exists a vertex vi in G corresponding to each channel intersection i, and an edge exists between vertices vi and vj if and only if there exists a channel between intersections i and j. In other words, each edge in graph G corresponds to a channel in the routing area. Figure 23.1b illustrates the graph model corresponding to the macroblocks given in Figure 23.1a. In this model, each channel c is defined to have channel capacity and channel length. The channel capacity indicates the number of nets that can use this channel without overflow, and the channel length indicates the amount of wirelength necessary to pass through this channel. The global routers using this graph model include Refs. [1–4]. A related problem here is the assignment of feedthrough space between channels of standard cell rows with the objective of wirelength and (a) (b) FIGURE 23.1 (a) Set of macroblocks and the channels between them and (b) its corresponding channel intersection graph. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 471 Global Routing Formulation and Maze Routing (a) Finals Page 471 23-9-2008 #4 (b) FIGURE 23.2 Net with terminals on three standard cell rows. The best topology of this net is illustrated (a) without feedthroughs and (b) with feedthroughs. The dark circles represent the net terminals, and the hollow circles represent the feedthrough terminals created. congestion minimization [5,6]. This concept is illustrated in Figure 23.2. After the global routing is completed, detailed routing within each channel is done using a channel routing algorithm [7–12] or a river routing algorithm [13–17]. 23.2.2 TILE-BASED GRAPH MODEL As the number of available routing layers is increasing in the current technology, over-the-cell routing model is becoming more and more popular. In this model, the lower layers that contain the cells or macroblocks are used as escape-only layers, and routing between terminals is accomplished mainly on the upper layers. Because the routing resources in the upper layers are not restricted to channels, the layout is partitioned into rectangular regions, and a grid graph G is created as illustrated in Figure 23.3. Here, there exists a vertex in G corresponding to each rectangular tie, and edges exist FIGURE 23.3 Circuit is partitioned into rectangular tiles (solid lines), and a grid graph is created. The dark circles and dashed lines represent the vertices and the edges of the grid graph, respectively.

Handbook of algorithms for physical design automation part 49

Nội dung