Interconnect-centric macrocell placement approaches for ASICs

As the interconnect characteristics dominate in Deep Sub-Micron regime, CAD tools need to focus on interconnect optimization. Several interconnect-centric Register Transfer-Level design methodologies based on net clustering are presented. Each net cluster identifies a set of nets that should be routed in the same region, so that all nets in question are optimized. Nets are clustered by clique partitioning the net dependency graph.; First, two approaches—constructive and iterative improvement based—are proposed. Just by introducing the net clustering idea into macrocell placement, the wire length is reduced significantly compared to a classic macrocell placer. Next, a hierarchical RTL macrocell placement approach is presented. It starts At the net level, a coarse net placement is obtained using a force-directed procedure. At the lowest level, terminals of a net can move freely in the quest for an optimal wire length solution for the net. A net model based on the star net topology is used. Forces on the net terminals drive the net length optimization, while forces between the pins of each macrocell and between a pin and the parent cell ensure a feasible position. Cell overlap is reduced by using an electrostatic repulsive force. The proposed design methodology reduces the wire length compared with the O-tree algorithm and a classic force-directed placement procedure. Finally, an iterative approach that tries to optimize the net length by placing the cells in the minimum energy positions is proposed. The cell energy is the sum of the net energy (analogous to the spring elastic energy) and the overlap potential energy (analogous to the gravitational potential energy). This approach further improves the wire length savings of the force-directed approach.; Since the force-directed and energy-based methods used in this work generate placements with cell overlaps, a novel macrocell overlap removal algorithm based on the ant colony optimization metaheuristic is introduced. It uses the concept of ant colonies, a set of agents that work together to improve an existing solution. Each ant in the colony will generate a placement based on the relative positions of the cells and feedback information generated by previous colonies.