We present an approach to VLSI chip layout (placement and routing) based on a new meta-planning paradigm.' By modeling placement and routing as separate planning problems, they can then each be solved within that paradigm. In planning terminology, placement is the conjunction of subgoals, each of which is to place one component; routing is the conjunction of subgoals, each of which is to route one net. As in any planning problem, the complexity of each of these problems is caused by the subgoal interaction in which the solu-tion of one subgoal greatly impacts the ways in which subsequent subgoals may be solved. Meta-planning directly addresses this control task of managing this interaction. Our meta-planning paradigm organizes meta-level decision knowledge into two control policies - graceful retreat, which selects the most critical subgoal to solve next, and least impact, which selects the solution of that subgoal which uses the least crucial resources. This knowledge is organized in a tie-breaking, layered structure which filters the selection candidates until one most critical subgoal and its solution which uses the least crucial resources remain. The result is a dynamic, interaction-sensitive, constructive solution to the layout problem.

Date Published: 26 March 1986
PDF: 8 pages
Proc. SPIE 0635, Applications of Artificial Intelligence III, (26 March 1986); doi: 10.1117/12.964183

Published in SPIE Proceedings Vol. 0635:
Applications of Artificial Intelligence III
John F. Gilmore, Editor(s)