`Zone-refining´ techniques for IC layout compaction

Zone-refining refers to a technique that forms a basis for layout compaction algorithms intermediate between one-dimensional (1-D) compactors and two-dimensional (2-D) placement techniques. An expanded zone in which 2-D refinement techniques are employed is repeatedly swept across the layout in different directions. The basic principle is reviewed and the computational complexity of zone refining is analyzed. The difficulties that had to be overcome in making the basic concept useful for compaction of integrated circuit layouts is discussed. One implementation is described, and some of the tradeoffs made and data structures used to obtain an efficient compactor are examined. The scope of possibilities for other implementations are discussed