Introduction to Technology Mapping Using Linear Delay Model
Introduction to technology mapping
Technology mapping on a DAG using a
linear delay model
•
Linear delay model
•
The difficulty
•
Technology mapping starting by splitting a DAG
into trees
2
Introduction to technology mapping
Technology mapping on a DAG using a
linear delay model
•
Linear delay model
•
The difficulty
•
Technology mapping starting by splitting a DAG
into trees
3
Input :
•
A circuit
transformed into a subject graph
•
A library consisting of many gates
4
Circuit C17
Input :
•
A circuit transformed into a subject graph
•
A library consisting of many gates
5
Corresponding subject graph in which each node is a predifined
universal gate
Input :
•
A circuit transformed into a subject graph
•
A library consisting of many gates
6
A sample cell library
Output :
•
An implementation of the circuit constructed by gates in the library
•
Such implementation satisfies the user’s need
7
An implementation
Dynamic programming
8
B
D
E
C
A
Prepare library gates
for each node
Recover a
circuit implementation
B
D
E
C
A
Introduction to technology mapping
Technology mapping on a DAG using a
linear delay model
•
Linear delay model
•
The difficulty
•
Technology mapping starting by splitting a DAG
into trees
9
Linear delay model :
•
Delay = block delay + fanout delay
= block delay
+ fanout delay per load * fanout load
10
N
o
p
Delay
Load
3+2*Load
l
m
2+
3+2*Load
node N
cone rooted at N
Introduction to technology mapping
Technology mapping on a DAG using a
linear delay model
•
Linear delay model
•
The difficulty
•
Technology mapping starting by splitting a DAG
into trees
11
The diffuculty in preparing library gates
for each node
•
Prepare for all possible fanout loads
gate NAND2 is best for load L
1
gate AND2 is best for load L
2
•
There may be many possible fanout loads…
12
C
E
F
D
A
B
Prepare library gates for each node
13
X
Delay
Load
Prepare library gates for each node
14
X
Delay
Load
Prepare library gates for each node
15
X
Delay
Load
L
1
L
2
Another difficulty happens on a DAG
•
The delay of fanins is no longer clear…
16
B
D
E
C
A
B
D
E
C
A
Introduction to technology mapping
Technology mapping on a DAG using a
linear delay model
•
Linear delay model
•
The difficulty
•
Technology mapping starting by splitting a DAG
into trees
17
Perform technology mapping on every subtree
Implemented in SIS
18
After split, each node has only one fanout
19
X
X
X
Effectively reduce delay
Area increases impressively as well as
runtime
20
To prevent too much increase on area
•
There must be may equivalent nodes caused by split!
Pre-merge
Selectively merge equivalent nodes
before
technology
mapping
Reduce both area and runtime
More equivalent nodes
Sub-optimum delay may be derived
Post-merge
Selectively merge equivalent nodes
after
technology mapping
Reduce only area
Fewer equivalent nodes
Preserve optimum delay achieved
21
Split a DAG into trees provides a near
lower bound on delay
Split is better than partition in terms of
linear delay model
Split is more flexible because it explores
more solution space than partition does
Merging equivalent nodes, no matter in
Pre-merge or Post-merge, is important to
reduce area and runtime overhead
22
Thank you!
23
Explore the process of technology mapping on a Directed Acyclic Graph (DAG) using a linear delay model. Learn about transforming circuits into subject graphs, utilizing sample cell libraries, and implementing circuits to meet user requirements. The challenges of technology mapping, circuit recovery, and dynamic programming are covered, enhancing your understanding of linear delay models and circuit design optimization.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Sz-Cheng Huang ALCom lab, GIEE, NTU Jan 24, 2008
Introduction to technology mapping Technology mapping on a DAG using a linear delay model Linear delay model The difficulty Technology mapping starting by splitting a DAG into trees 2
Introduction to technology mapping Technology mapping on a DAG using a linear delay model Linear delay model The difficulty Technology mapping starting by splitting a DAG into trees 3
Circuit C17 Input : A circuit transformed into a subject graph A library consisting of many gates 4
Corresponding subject graph in which each node is a predifined universal gate Input : A circuit transformed into a subject graph A library consisting of many gates 5
A sample cell library Input : A circuit transformed into a subject graph A library consisting of many gates 6
An implementation Output : An implementation of the circuit constructed by gates in the library Such implementation satisfies the user s need 7
Dynamic programming Prepare library gates for each node Recover a circuit implementation C C A A D D B B E E 8
Introduction to technology mapping Technology mapping on a DAG using a linear delay model Linear delay model The difficulty Technology mapping starting by splitting a DAG into trees 9
Linear delay model : Delay = block delay + fanout delay = block delay + fanout delay per load * fanout load Delay 2+3+2*Load l o 3+2*Load N m p Load 10
Introduction to technology mapping Technology mapping on a DAG using a linear delay model Linear delay model The difficulty Technology mapping starting by splitting a DAG into trees 11
The diffuculty in preparing library gates for each node Prepare for all possible fanout loads gate NAND2 is best for load L1 gate AND2 is best for load L2 There may be many possible fanout loads D A E C B F 12
Prepare library gates for each node Delay X Load 13
Prepare library gates for each node Delay X Load 14
Prepare library gates for each node Delay X Load L1 L2 15
Another difficulty happens on a DAG The delay of fanins is no longer clear C C A A D D B B E E 16
Introduction to technology mapping Technology mapping on a DAG using a linear delay model Linear delay model The difficulty Technology mapping starting by splitting a DAG into trees 17
Perform technology mapping on every subtree Implemented in SIS 18
Effectively reduce delay Area increases impressively as well as runtime Delay typical split Area typical split C17 5 5 C17 14 18 C432 119.8 42.2 C432 563 583714 C499 77.4 31.8 C499 864 736352 C880 67 29.4 C880 736 15494 C1908 117.3 45.8 C1908 1002 1522094 C2670 99.5 29.8 C2670 1465 50204 C5315 145.3 57.1 C5315 3784 2505756 C7552 264 47.4 C7552 4838 1442838 20
To prevent too much increase on area There must be may equivalent nodes caused by split! Pre-merge Selectively merge equivalent nodes before technology mapping Reduce both area and runtime More equivalent nodes Sub-optimum delay may be derived Post-merge Selectively merge equivalent nodes after technology mapping Reduce only area Fewer equivalent nodes Preserve optimum delay achieved 21
Split a DAG into trees provides a near lower bound on delay Split is better than partition in terms of linear delay model Split is more flexible because it explores more solution space than partition does Merging equivalent nodes, no matter in Pre-merge or Post-merge, is important to reduce area and runtime overhead 22
Thank you! 23
