Performing Technology Mapping and

Optimization by DAG Covering: A Review of Traditional Approaches

Evriklis Kounalakis

Introduction

Technology Mapping:

Requires technology description

Requires technology independent netlist

Produce technology dependent netlist

Netlist:

Can be a DAG

Requires heuristics

Maybe convert DAG into forest of trees

Problem Formulation

MAP:

INTO:

Methodology

Decompose DAG into forest of trees

Map each tree independently

Glue results together

Overview of Approaches

DAGON [1]

Novel technology mapper

Maps trees only

NOA [2]

Minimize area under delay constraints

Maps trees only

DOT [3]

Delay-optimal mapping by DAG covering

Maps trees and DAGs in general

[1] K. Keutzer: DAGON: Technology Binding and Local Optimization by DAG Matching, 1989

[2] K. Chaudhary and M. Pedram: A Near Optimal Algorithm for Technology mapping under Delay Constraints, DAC 1992

[3] Y. Kukimoto, R. K. Brayton and P. Sawkar: Delay-Optimal Technology Mapping by DAG Covering, DAC 1998

DAGON Overview

3 phases

Decompose DAG into forest of trees

Match using twig[1] and Aho-Corasick[2]

Glue results together

In case of multiple matches, choose best

Best match = minimum cost match

[1] S. Tjiang: Twig Reference Manual, 1986

[2] A. V. Aho and M. J. Corasick: Efficient String Matching:An Aid to Bibliographic Search, Communications of the ACM, vol.18, 1975

DAGON Implementation

Traverse tree starting from leafs

For every node:

Search all library gates

Find all matches

Store match cost for each match

Traverse tree starting from root

DFS to find minimum cost based on stored values

Match with minimum cost and mark nodes

Continue until all nodes are matched

DAGON Match Example

NOA Overview

Technology mapping under delay constraints

Provides area-speed tradeoff

Flow:

Map nodes and create area-speed tradeoff

Choose implementation

Perform mapping

Based on area-speed curves

NOA Area-Speed Curves

NODE A: a and b implementations

NODE B: c, d and e implementations

Area-Speed for every implementation

NOA Curve Combination

NOA Implementation

Decompose DAG to forest of trees

For every tree:

Post-order traversal to determine curves

Choose implementation for the root

Pre-order traversal

Choose implementations for all nodes

Glue results together

May be interactive

DOT Overview

Works directly on DAGs

Based on FPGA mapping by [1]

Identifies k-cuts of a node

Uses FlowMap by [1]

Requires two traversals

Chooses minimum-delay matches

[1] J. Cong and Y. Ding: An Optimal Technology Mapping Algorithm for Delay-Optimization in Lookup-Table Based FPGA Designs, IEEE Transactions on Computer-Aided Design, vol.13, 1994

DOT Matching

Supports exact and extended match

DOT Implementation

Traverses DAG from leafs and finds k-cuts

Determine how many fanin nodes can be included in a k-cut

Find all possible matches

Store nodes that belong to k-cut

Traverse DAG from root

For each node check k-cuts

Assign best implementation

Mark all nodes that belong to mapped k-cuts

Proceed until all nodes are marked

Results

DAGON implementations better than NAND/NOT implementations

NOA compared with MIS2.2 [1]

6% faster, 3% larger

Similar speed, 17% smaller

DOT compared with standard tree matching

Much faster but much larger

[1] H. J. Touati, C. W. Moon, R. K. Brayton and A. Wang: Performance-Oriented Technology Mapping, In Proceedings of 6th MIT Conference in Advanced Research in VLSI, 1990

Comparison

DAGON tries all library gates for each node

Complexity : O(DAG_SIZE * LIBRARY_SIZE)

NOA complexity depends on curve determination speed

Curves are sorted with O(k* logk)

Curve for one point is generated at: O(k* logk)

Total complexity: O(N* k*k * logk * logk)

DOT finds matches at O(LIBRARY_SIZE)

For all nodes: O (NODES * LIBRARY_SIZE)

Enhancements

DAGON:

Better if complete DAG information is used

Fanout of nodes

Existence of inverted pins

Search for redundant gates (for adjacent trees)

DOT:

Sequential circuits optimization by retiming

Transform subject graph using knowledge about technology library

Conclusions

Technology Mappers

Use library gates, work on subject graphs

May require decomposition of DAG

Can complete in O(DAGSIZE*LIBRARYSIZE)

Can optimize speed

Can find optimal area implementations

Evriklis Kounalakis

2005-12-09T15:12:12