Handbook of Algorithms for Physical Design Automation part 78 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 752 Handbook of Algorithms for Physical Design Automation Minimize e subject to 0 p Tj slack Tj M P Tij M - i j 1 . --------1 2 2 W The above formulation is also called a ranged LP formulation where the manufacturability is guaranteed by the constraints. In addition to the LP approaches Ref. 14 introduces the Monte-Carlo method for min-variation objective. In the Monte-Carlo approach a tile is chosen randomly and its content is increment with a predetermined fill amount. Tiles are chosen based on their priority which is the probability of choosing a particular tile Tij. The priority of a tile Tij is zero if and only if either Tij belongs to a window that has already achieved the density upper bound U or the slack of Tij is equal to the already-inserted fill area. As described in Ref. 14 the priority of a tile Tij is chosen to be proportional to U - MinWin T j where MinWin T j is the minimum density over windows containing the tile Tij. The only drawback of the Monte-Carlo method is that it may insert an excessive amount of total fill. A variant of the Monte-Carlo approach is the greedy algorithm. At each step the min-variation greedy algorithm adds the maximum possible amount of fill into a tile with the highest priority which causes the priority of that particular tile to become zero. In the presence of two objectives namely min-variation and min-fill the intuitive approach would be to first find a solution that optimizes one of the objectives then modifying the solution with respect to the other objective. Min-fill objective tries to delete as much previously inserted fill as possible while maintaining the density criteria. To optimize the min-fill objective problem with the Monte-Carlo approach a filling geometry from a tile randomly chosen according to a particular priority is iteratively deleted. Priorities are chosen symmetrical to the priority in the min-variation Monte-Carlo algorithm that is proportional to MinWin Tij - L. Again symmetrically no filling .
