ABSTRACT

Traditional logic optimization techniques, simulated-annealing-based placement algorithms, and maze routing methods were common in the field-programmable gate arrays (FPGAs) world. A major breakthrough in the FPGA technology mapping came about in 1994 with the introduction of the FlowMap tool. Floorplanning is used on FPGAs to speed up the placement process or to place hard macros with prespecified shapes. Another partitioning-based timing-driven placement method for hierarchical FPGAs was presented by M. Hutton et al. The chapter focuses on the placement methods used in physical synthesis approaches. It reviews miscellaneous routing methods such as pipeline routing, congestion-driven routing, and statistical timing routing. To estimate congestion, waves are started from a source node, and all possible paths are implicitly enumerated at every step of the wave propagation. A pipeline-aware routing problem requires the connection from a source node to a sink node to pass through certain number of pipeline registers and each segment of the route must satisfy delay constraints.