Free Trial

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

Share this Page URL

11.1 Introduction > 11.1 Introduction - Pg. 636

636 CHAPTER 11 Placement Interconnect delay can consume as much as 75% of clock cycle in advanced design. Therefore, a good placement solution can substantially improve the performance of a circuit. Second, placement determines the routability of a design. A well-constructed placement solution will have less routing demand (i.e., shorter total wirelength) and will distribute the routing demand more evenly to avoid routing hot spots. Third, placement decides the distribution of heat on a die surface. An uneven temperature profile can lead to reliability and timing problems. Fourth, power consumption is also affected by placement. A good placement solution can reduce the capacitive load because of the wires (by having shorter wires and larger separation between adjacent wires). Hence the switching power consumption can be reduced. In recent years, it has become essential for the logic synthesis stage to incor- porate placement techniques to perform physical design aware logic synthesis (i.e., physical synthesis). The reason is that without some placement informa- tion, it is impossible to estimate the delay of interconnect wires. Hence, given the significance of interconnect delay, logic synthesis will not have any mean- ingful timing information to guide the synthesis process. As a result, the synthe- sized netlists will have poor performance after placement. For the same reason, consideration of placement information during architecture design is also increasingly common. Placement is a computationally difficult problem. Even the simple case of placing a circuit with only unit-size modules and 2-pin nets along a straight line to minimize total wirelength is NP-complete [Garey 1974]. The VLSI placement problem is much more complicated. The circuit may contain modules of differ- ent sizes and may have multi-pin nets. The placement region is two-dimensional. Other cost functions may be used rather than total wirelength. There may also be different constraints for different design styles. (Details of problem formula- tions can be found in Section 11.2.) As designs with millions of modules are now common, it is a major challenge to design efficient placement algorithms to produce high-quality placement solutions. One way to overcome the complexity issue is to perform placement in several manageable steps. One common flow is as follows. 1. Global placement. Global placement aims at generating a rough place- ment solution that may violate some placement constraints (e.g., there may be overlaps among modules) while maintaining a global view of the whole netlist. 2. Legalization. Legalization makes the rough solution from global place- ment legal (i.e., no placement constraint violation) by moving modules around locally. 3. Detailed placement. Detailed placement further improves the legalized placement solution in an iterative manner by rearranging a small group of modules in a local region while keeping all other modules fixed. The global placement step is the most important one of the three. It has the most impact on placement solution quality and runtime, and has been the focus