11.4 Global placement: simulated annealing approach 649 modules, a multilevel FM algorithm is used. For instances with 35 to 200 mod- ules, the flat FM algorithm is used. Smaller instances are solved optimally with branch-and-bound. In addition, much attention has been paid in Capo to the handling of parti- tioning tolerance. First, an "uncorking" technique is proposed to prevent large modules from being the first modules in a bucket of the FM algorithm. In an ordinary FM implementation, a large module at the head of a bucket may fail to move to the other partition without violating constraints on partition sizes. Smaller modules further in the same bucket will not be considered for moves, because the bucket is temporarily invalidated. This "corking" effect may degrade solution quality of FM. Second, repartitioning, which refers to a chained FM calls on the same partitioning instance, is presented. The first call is per- formed with a much larger tolerance than requested to ensure mobility of all modules. In subsequent calls, the tolerance gradually decreases to the original value. Third, a high tolerance of e ¼ 20% is used for vertical cutlines, because the cutline locations can be adjusted after partitioning according to sizes of par- titions. However, this technique cannot be applied to horizontal cutlines, because their locations are more discrete (i.e., aligned to standard-cell rows) and cannot be easily adjusted. Fourth, a formula is derived to determine the tol-