Explore / Methods & Algorithms / Synthesis / Tree Covering by Dynamic Programming

Tree Covering by Dynamic Programming

Synthesis foundational 1987 Keutzer (DAGON) optimal on each tree tree boundaries cost area

The idea

Express the design and every library cell as graphs of the same simple gates; Keutzer's DAGON (1987) used two-input NAND gates and inverters. Mapping then means covering the design graph with cell patterns, so that every node is covered and every cell's inputs connect to other cells' outputs.

On a tree this has an exact solution by dynamic programming. Visit the nodes from the inputs toward the output. At each node, try every library pattern that matches with this node as its root. The cost of a match is the cell's area plus the best costs already computed at the nodes that feed the match's inputs:

cost(v) = min over matches m at v of [ area(m) + Σ cost(u) ]
  • cost(v) least total area that implements the subtree rooted at node v
  • m a library cell pattern that matches with v as its root
  • area(m) the area of that cell
  • u the nodes feeding the inputs of the match, whose best costs are already known

The best cost at the root is the optimal cover of the tree, and the chosen matches are recovered by walking back from the root. For a fixed library the time is linear in the size of the tree.

Watch it work: a tree, a library, and the cheapest cover

f = abc decomposed into NAND gates and inverters, and a library of five cells with areas. The walkthrough computes the best cost at every node from the inputs up, then walks back from the root to recover the cheapest cover.

The fine print

Real networks are directed acyclic graphs, not trees. A node with several fanouts is cut into tree boundaries, and the cover is optimal only within each tree. Covering across the boundaries could share or duplicate logic better, but covering a general directed acyclic graph optimally is NP-hard (Non-deterministic Polynomial-time hard). The result also depends on how the design was decomposed into simple gates. Delay-oriented versions use arrival time instead of area as the cost.

Where you meet it today

Tree covering is the textbook method and the basis of the first generation of library mappers; ABC's standard-cell mapper extends the same dynamic programming from trees to cuts of the full graph (the next page).

References and further reading