Open Algorithmical Problems in the Analysis of Integrated Circuits

Friday, January 23, 2004 - 1:25pm - 3:00pm
Vincent 570
Edward Keyes (Semiconductor Insights)
Joint work with Vyacheslav Zavadsky.

In this talk, we will discuss several graph related problems that arise during the detailed reverse synthesis of integrated circuits (ICs). In a reverse synthesis process the electrical design schematics for an IC are reconstructed from the physical implementation of the IC (the “layout”). The process involves generation of a global circuit netlist from the physical layout followed by organization of the global netlist into recognizable circuits (amplifiers, buffer, adders etc).

Our first open problem is a general solution for the localization of mis-connections between two signals in the net list. Mis-connections occur due to errors in the reconstructed IC layout that are then incorporated into the reconstructed global netlist. In specific cases, false connections can be located as s-t cut in a network. A more general open global minimum cut like problem is presented.

The second open problem relates to the organization of the global netlist into individual circuits. We would like a method to locate a given circuit pattern within a large global netlist. This problem is essentially a generalized subgraph isomorphism problem on a netlist graph. We will present a survey of existing methods that successfully work (typically in linear time) for conventional netlists, and then consider the special problems of reconstructed netlists. Our special interest would be application of implicit breadth first relabeling techniques to limit the number of branches for brute force isomorhism approach. In particular, we will present an open problem from the error correction codes domain, which we believe is essential to obtaining efficient algorithm for the isomorphism problem.