ABSTRACT

This chapter describes an approach called min-cut that can be used to organize the building blocks for constructive placement. Physical design process is a collective term indicating the operations involved in the production of layout information for the fabrication of Very Large Scale Integration systems. Traditionally, an iterative improvement approach accepts only solutions that have lowered the cost. Solutions with increased costs are rejected. A probabilistic hill climbing technique called simulated annealing has been introduced into the iterative improvement placement. The basic idea behind the force-directed placement is that building blocks connected by a signal net exert forces proportional to their distance on one another. Detailed routing deals with the determination of wiring paths in a given routing region. The routing space is modeled as lists of lines. A channel is a rectangular routing region bounded by two parallel rows of terminals. The left-edge channel routing algorithm was the first algorithm developed for channel routing.