Force directed mongrel with physical net constraints

Abstract

This paper describes a new force directed global placement algorithm that exploits and extends techniques from two leading placers, Force-directed [12] [26] and Mongrel [22]. It combines the strengths of force directed global placement with Mongrel's cell congestion removal to significantly improve the quality of placement during the difficult overlap removal stage of global placement. This is accomplished by using the spreading force in [12] to direct and control Mongrel's ripple move optimization. This new placer is called Force Directed Mongrel (FD-Mongrel). FD-Mongrel also incorporates physical net constraints [26], and improves the congestion model for sparse placements. We propose a new placement flow that uses a limited number of the spreading iterations of [12] to form a preliminary global placement. We then use the new FD-Mongrel described in this paper to remove cell overlaps, while meeting net constraints and optimizing wirelength. We present results on wirelength as well as timing driven placement flows.