Technology Binding (DAGON)

Technology independent mapping of circuit to cell library components. They called this technique DAG rewriting. The complexity of finding a minimal match, or cover, is NP-complete.

It assumes non-local optimizations are done at global optimization or decomposition stages.

Two essential steps
- partitioning into forest of trees (special case of DAG)
- partitioning split any fanout > 1 and is O(G).
- optimally match trees to patterns based on cost (e.g. time, area, or both)
- matching is done with twig (based on Aho-Corasick) is O(T).

It borrows from code generator in compilers
- the use of grammar to specify families of patterns
- peehole optimizer to handle cross-tree boundary opt.

Quality enhancements:
- use annotations to export local information globally
- e.g. inverse, signal, and fanout

--------------------------------------------

(circuit) base function ==> subject graph

(library) base function ==> pattern graphs

Partitioning

- single fanout - split multiple fanout

- single cone - traverse from sink nodes

- may have overlap clustering because of the input-output constraint from patterns

Dynamic programming

- store intermediate best result for each stage

- at each new stage, compute best matches using previous best results