Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL
Help

11.3 Global placement: partitioning-base... > 11.3 Global placement: partitioning-... - Pg. 648

648 CHAPTER 11 Placement A p p A p q d q B (b) A (c) B A p d q B1 q B (a) B2 (d) FIGURE 11.7 Terminal propagation. this external net, assume module q is placed at the center of subregion B. The terminal in q is "propagated" to the closest point on the boundary of subregion A and is replaced by a dummy terminal d (as shown in Figure 11.7b). During the partitioning of A, the net between p and d is treated as an internal net and d is treated as a fixed terminal of subcircuit A. For this example, if subregion A is divided by a horizontal cutline, module p will be biased toward the lower parti- tion because of the net between p and d. However, if subregion A is divided by a vertical cutline, d will be very near to the cutline. In this case, it is not clear whether the external net should bias p to the left or to the right partition. It is suggested in [Dunlop 1985] that dummy terminals that are within the middle third of the side should be ignored. Another example is shown in Figure 11.7c. Assume both subregions A and B are divided by horizontal cutlines. Suppose subcircuit B is partitioned first. Dur- ing the partitioning of B, the dummy terminal caused by p is too close to the cutline and hence is ignored. Suppose module q is assigned to the top subregion B1. Then during the partitioning of A, a dummy terminal d is introduced near to the top of subregion A (as shown in Figure 11.7d). Thus, it will bias p to the top. 11.3.3 Practical implementations In the past, partitioning-based placement was generally perceived to be simple and efficient but not as good as simulated annealing or analytical approaches in terms of solution quality. In late-1990s, partitioning algorithms dramatically improved because of the multilevel scheme. Partitioning-based placement should also improve as a result. Capo [Caldwell 2000] and Fengshui [Yildiz 2001a, 2001b; Agnihotri 2003] are two placement algorithms that leverage this break- through in partitioning. They demonstrated that a careful implementation of the partitioning-based approach could produce very competitive wirelength with a relatively short runtime. 11.3.3.1 The Capo algorithm In Capo, different bipartitioning techniques are applied to subcircuits of differ- ent sizes during recursive bipartitioning. For instances with more than 200