This thesis describes a near-optimal standard cell placement strategy which consists of three consecutive steps; initial placement, iterative placement improvement, and string placement.
In the initial placement step, cell placement was done by solving the linear ordering problem for a one-dimensional layout of standard cells and then zigzaging the resultant linear order within the chip plane. The iterative placement improvement step is based on the iterative pairwise interchange using the estimated total routing length as a figure-of merit.
The string placement is used to reorder cells and terminals in each standard cell row such that channel routing in the adjacent channels is not blocked by cyclic constraints and needs fewer routing tracks.
The placement program is coded in PASCAL and implemented on a VAX-11/750 computer. Experimental results for several examples were quite encouraging.
