Placement with incomplete data

Traditional placement problems are studied under a fully specified cell lib rary and a complete netlist. However, in the first, e.g., 2 years of a 2 - 3 year microprocessor design cycle, the detailed netlist is unavailable. Fo r area and performance estimation, layout must nevertheless be done with in complete information. Another source of incompleteness comes from logic syn thesis changes; some instances and their parameters will change as the proj ect evolves. In the re-configurable computing area, sometimes we need to pe rform quick placement before all information is available. The problem of p lacement with incomplete data (PID) can be abstracted as having to place a circuit when p(c)% of the cells and p(n)% of the nets are missing. The key challenge in PID is how to add missing cells and nets. In this paper, two "patching-methods" for adding missing nets and cells are proposed. The methods are called abstraction and fusion. Experimental results are very interesting. First, they show that PID is a d ifficult problem and an arbitrary (and perhaps intuitively sound) method ma y not produce high-quality results. Experiments verify that the abstraction method is a very good predictor and that fusion is not. Specifically, when a circuit has 10% incompleteness, abstraction can predict the final total wirelength with an error of 5.8% while fusion has a 67.8% error in predicti ng the wirelength in the same circuit.