GM Plan: a gate matrix layout algorithm based on artificial intelligence planning techniques

Gate matrix layout is formulated as a planning problem where a plane (the solution steps) is generated to achieve a goal (the gate matrix layout) that consists of interacting subgoals. Each subgoal corresponds to the placement of a gate to a slot, or to the routing of a net connecting gates. The interaction among subgoals is managed with two artificial-intelligence planning techniques: hierarchical planning and metaplanning. A distance measure is defined and used to arrange the subgoals into prioritized classes in the hierarchical planning phase. Two metaplanning policies-graceful retreat and least impact-are used to decide which subgoal is to be achieved within the same priority class and how it can be achieved. In doing so, GM Plan successfully combines gate placement and net routing of the gate matrix layout into one process and has the potential to deliver better results