Machine Learning for Predicting Path-Based Slack in Timing Analysis

undefined
 
U
s
i
n
g
 
M
a
c
h
i
n
e
 
L
e
a
r
n
i
n
g
 
t
o
 
P
r
e
d
i
c
t
P
a
t
h
-
B
a
s
e
d
 
S
l
a
c
k
 
f
r
o
m
 
G
r
a
p
h
-
B
a
s
e
d
 
T
i
m
i
n
g
 
A
n
a
l
y
s
i
s
 
A
n
d
r
e
w
 
B
.
 
K
a
h
n
g
+
$
,
 
U
d
a
y
 
M
a
l
l
a
p
p
a
$
 
a
n
d
L
a
w
r
e
n
c
e
 
S
a
u
l
+
U
C
 
S
a
n
 
D
i
e
g
o
 
$
E
C
E
 
&
 
+
C
S
E
 
D
e
p
a
r
t
m
e
n
t
 
Preliminaries
Modeling Features
Modeling Methodology
Experiments
Conclusions
 
O
u
t
l
i
n
e
S
t
a
t
i
c
 
T
i
m
i
n
g
 
A
n
a
l
y
s
i
s
 
Graph traversal problem to estimate transition and arrival time at
each node
 
Advanced nodes: Multi-corner multi-mode timing scenarios 
Long runtimes
 
Needed in every iteration of place, route and optimization
o
Avoid loops in the flow
o
Avoid overdesign that wastes power and area
 
Accuracy versus Runtime tradeoff
o
Accurate path-based analysis (PBA)
o
Fast graph-based analysis (GBA)
 
 
T
i
m
i
n
g
 
A
n
a
l
y
s
i
s
 
i
n
 
G
B
A
 
&
 
P
B
A
 
M
o
d
e
s
 
 
 
 
 
 
Path-specific transition
propagation and derived
arrival time estimation
 
 
Runtime intensive as
Launch-Capture logic
cone grows in size
 
 
 
 
 
 
Worst transition
propagation and
pessimistic arrival time
estimation
 
Faster but inaccurate,
leading to overdesign
GBA
PBA
P
B
A
-
G
B
A
 
 
(
A
c
c
u
r
a
c
y
 
v
s
.
 
R
u
n
t
i
m
e
)
 
Arrival Time of 1.803ns
 
Arrival Time of 1.693ns
PBA-GBA 
divergence
 of 110ps
(
path-consistent
)
Runtime difference as high as 15X for
the 
leon3mp
 design with 100K flops
A
c
c
u
r
a
c
y
 
v
e
r
s
u
s
 
R
u
n
t
i
m
e
 
t
r
a
d
e
o
f
f
GBA
PBA
P
B
A
-
G
B
A
 
d
i
v
e
r
g
e
n
c
e
 
(
g
l
o
b
a
l
 
p
i
c
t
u
r
e
)
 
PBA-GBA divergence values
(sorted from high to low)
 
Actual GBA versus Actual PBA
path arrival time
 
(
megaboom
: 350K flops and 990K instances, 1.2ns clock period)
C
o
s
t
 
o
f
 
P
B
A
-
G
B
A
 
S
l
a
c
k
 
D
i
v
e
r
g
e
n
c
e
 
Learning-based methods to predict STA outcomes
Han et al. DATE14: miscorrelation between STA tools
Kahng SLIP15: prediction of SI from non-SI
Onaissi DAC11: determine dominant corner set
Bian DAC17: STA in presence of on-chip variations
 
Runtime improvement for timing analysis
TAU Workshop: STA accuracy and runtime
Huang SLIP15: speedup timing analysis using MapReduce
Silva: identify single corner that has worst delay
 
Our work: Predict PBA outcomes from GBA results !
P
r
e
v
i
o
u
s
 
W
o
r
k
 
Identify 
electrical and structural features 
of the circuit that
affect PBA-GBA slack divergence
 
Develop 
bigram-based predictive model 
that can capture
PBA-GBA slack divergence
 
Generate 
artificially generated timing paths 
that can train our
predictive model
 
Demonstrate 
accuracy and robustness
 of our models on a
variety of testcases and use cases
O
u
r
 
C
o
n
t
r
i
b
u
t
i
o
n
s
F
r
a
m
e
w
o
r
k
:
 
 
B
i
g
r
a
m
-
B
a
s
e
d
 
M
o
d
e
l
i
n
g
 
Stage-wise or path-wise
(lumped)
 
 
 
Shield stage-specific details
Very large space of features
Difficult to debug outlier stages
In a given path, transition divergence will be translated
into arrival time divergence only for the next stage.
            
 Bigrams are a Natural Choice !
 
Bigram-based
 (n = 2) representation
Lumped Model
 
Preliminaries
Modeling Features
Modeling Methodology
Experiments
Conclusions
 
O
u
t
l
i
n
e
 
L
i
s
t
 
o
f
 
M
o
d
e
l
i
n
g
 
F
e
a
t
u
r
e
s
 
f
o
r
 
e
a
c
h
 
b
i
g
r
a
m
 
u
n
i
t
transition time of the first cell
transition time of the second cell
arrival time of first cell
transition time ratio (TR ratio) of first cell
arrival time of second cell
drive strength of first cell
drive strength of second cell
functionality of first cell
functionality of second cell
fanout of first cell
load capacitance of first cell
accumulated transition time ratio of first cell
propagation delay of second cell
M
o
d
e
l
i
n
g
 
F
e
a
t
u
r
e
s
F
e
a
t
u
r
e
 
I
m
p
o
r
t
a
n
c
e
 
Dropping “TR ratio”
reduces the model
accuracy by 27%
 
Dropping any feature
pair that includes
“TR ratio” corresponds
to peaks
 
Preliminaries
Modeling Features
Modeling Methodology
Experiments
Conclusions
 
O
u
t
l
i
n
e
M
o
d
e
l
i
n
g
 
F
l
o
w
Need Non-linear techniques can capture complex interactions between features
 Classification and  Regression Trees !!!
 
Bigram-based Two Stage Model
M
o
d
e
l
 
D
e
f
i
n
i
t
i
o
n
 
Transition Time
Prediction
 
Arrival Time
Prediction
 
Model1
 
Model2
 
R
e
p
o
r
t
i
n
g
 
M
e
t
r
i
c
s
^
 
We use lumped metrics such as 99th percentile value of divergence, mean
absolute value of divergence, and worst-case divergence
 
Arrival Time (ps)
 
Actual PBA
 
Actual GBA
 
Model PBA
 
model_*
 metric
 
actual_*
 metric
 
Preliminaries
Modeling Features
Modeling Methodology
Experiments
Conclusions
 
O
u
t
l
i
n
e
D
e
s
i
g
n
 
o
f
 
E
x
p
e
r
i
m
e
n
t
s
 
Knobs
number of stages in a timing
path;
standard cell types in the path;
launch and capture flop-types;
aggressor cell types;
load cap range;
transition (slew) time values;
clock period values.
 
Artificial Circuits
Real Designs
 
28nm FDSOI foundry technology libraries
Five public benchmark designs along
with artificial circuits
Three experiments
Accuracy versus Robustness
 
 
M
o
d
e
l
 
S
e
t
u
p
 
Actual 
GBA
 
Actual 
PBA
 
Actual
 PBA
 
Model
 PBA
 
Reference
 
Evaluation
 
70% for training and 30% for testing
E
x
p
e
r
i
m
e
n
t
 
1
:
 
A
c
c
u
r
a
c
y
 
netcard 
design
 
Actual 
GBA
 Arrival (ps)
 
Predicted
 PBA Arrival (ps)
 
Actual 
PBA
 Arrival (ps)
 
Actual
 PBA Arrival (ps)
 
39.59ps
 
19.90ps
 
E
x
p
e
r
i
m
e
n
t
 
1
:
 
A
c
c
u
r
a
c
y
 
megaboom
 
leon3mp
 
netcard
 
dec_viterbi
 
jpeg_encoder
 
Actual GBA  (ps)
 
Predicted PBA (ps)
 
Actual PBA (ps)
 
Timing paths from a post-CTS database for training,
and test the model on a post-routed database of the
same design.
 
E
x
p
e
r
i
m
e
n
t
 
2
:
 
R
o
b
u
s
t
n
e
s
s
 
netcard 
design
 
Actual 
GBA
 Arrival (ps)
 
Predicted
 PBA Arrival (ps)
 
Actual 
PBA
 Arrival (ps)
 
Actual
 PBA Arrival (ps)
 
33.56
 
29.63ps
 
E
x
p
e
r
i
m
e
n
t
 
2
:
 
R
o
b
u
s
t
n
e
s
s
 
megaboom
 
leon3mp
 
netcard
 
dec_viterbi
 
jpeg_encoder
 
Actual GBA  (ps)
 
Predicted PBA (ps)
 
Actual PBA (ps)
 
Artificial designs and a sample from a real design
(30%) for training, and test on (70%) datapoints of
the same real design.
R
e
s
u
l
t
 
3
:
 
R
o
b
u
s
t
n
e
s
s
 
netcard 
design
 
Actual 
GBA
 Arrival (ps)
 
Predicted
 PBA Arrival (ps)
 
Actual 
PBA
 Arrival (ps)
 
Actual
 PBA Arrival (ps)
 
R
e
s
u
l
t
 
3
:
 
R
o
b
u
s
t
n
e
s
s
 
megaboom
 
leon3mp
 
netcard
 
dec_viterbi
 
jpeg_encoder
 
Actual PBA (ps)
 
Actual GBA  (ps)
 
Predicted PBA (ps)
 
Preliminaries
Modeling Features
Modeling Methodology
Experiments
Conclusions
 
O
u
t
l
i
n
e
 
First to apply machine learning techniques to model PBA-GBA
divergence
Artificial circuit generation methodology  for potential
availability during an initial, “bootstrap” training phase of
modeling
Model based on decision trees along with electrical and
physical features of stage bigrams in timing paths
We assess potential benefits of our model using 28nm FDSOI
foundry technology
Model-predicted PBA arrival times reduce mean, 99th
percentile and max divergence metrics by at least 26.6%,
13.4% and 11.7%, respectively as compared to reference
PBA-GBA divergence metrics
C
o
n
c
l
u
s
i
o
n
s
 
Integrate our models with an academic sizer and
optimizer
Obtain practical benefits from improved accuracy-runtime
tradeoff
Richer artificial testcases that can span the space of
timing paths in real designs
We see outlier stages (bigrams) that are very different from
any artificial training data)
R
e
d
u
c
t
i
o
n
 
o
f
 
o
p
t
i
m
i
s
m
 
i
n
 
P
B
A
 
s
l
a
c
k
 
p
r
e
d
i
c
t
i
o
n
But: Optimism not viewed as harmful in current use context!
Better use of multiple GBA paths to a given endpoint
Multiple GBA paths give more information, but our
approach does not derive benefit from them!
 
F
u
t
u
r
e
 
W
o
r
k
 
Dr. Tuck-Boon Chan
Dr. Siddhartha Nath
Support: NSF, DARPA, Qualcomm, Samsung, NXP,
Mentor Graphics, and the C-DEN center.
 
A
c
k
n
o
w
l
e
d
g
m
e
n
t
s
 
T
h
a
n
k
 
Y
o
u
Slide Note

Thank you for the introduction. My talk is on “Using Machine Learning to Predict Path-Based Slack from Graph-Based Timing Analysis”.

Embed
Share

Utilizing machine learning to forecast path-based slack in graph-based timing analysis offers a solution for optimizing power and area efficiency in the design process. The Static Timing Analysis incorporates accurate path-based analysis (PBA) and fast graph-based analysis (GBA) to estimate transition and arrival times, with a focus on accuracy versus runtime tradeoff. Different modes of GBA and PBA are compared for their impact on timing divergence, illustrating the critical balance between accuracy and efficiency.

  • Machine Learning
  • Timing Analysis
  • Graph-Based
  • Path-Based Slack
  • Power Optimization

Uploaded on Jul 16, 2024 | 1 Views


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


  1. Using Machine Learning to Predict Path-Based Slack from Graph- Based Timing Analysis Andrew B. Kahng+$, Uday Mallappa$and Lawrence Saul+ UC San Diego $ECE & +CSE Department

  2. Outline Preliminaries Modeling Features Modeling Methodology Experiments Conclusions 2

  3. Static Timing Analysis Graph traversal problem to estimate transition and arrival time at each node Advanced nodes: Multi-corner multi-mode timing scenarios Long runtimes Needed in every iteration of place, route and optimization o Avoid loops in the flow o Avoid overdesign that wastes power and area Accuracy versus Runtime tradeoff o Accurate path-based analysis (PBA) o Fast graph-based analysis (GBA) 3

  4. Timing Analysis in GBA & PBA Modes GBA PBA Path-specific transition propagation and derived arrival time estimation Worst transition propagation and pessimistic arrival time estimation Faster but inaccurate, leading to overdesign Runtime intensive as Launch-Capture logic cone grows in size 4

  5. PBA-GBA (Accuracy vs. Runtime) GBA PBA Arrival Time of 1.803ns Arrival Time of 1.693ns PBA-GBA divergence of 110ps (path-consistent) Accuracy versus Runtime tradeoff Runtime difference as high as 15X for the leon3mp design with 100K flops 5

  6. PBA-GBA divergence (global picture) PBA-GBA divergence values (sorted from high to low) Actual GBA versus Actual PBA path arrival time (megaboom: 350K flops and 990K instances, 1.2ns clock period) 6

  7. Cost of PBA-GBA Slack Divergence GBA SLACK PBA SLACK IMPACT Reduces the ability to exploit available timing slack during power optimization POSITIVE (+) POSITIVE (+) Fixing of false violations schedule, area and power NEGATIVE (-) POSITIVE (+) Over-fixing of timing violations schedule, power and area. NEGATIVE (-) NEGATIVE (-) 7

  8. Previous Work Learning-based methods to predict STA outcomes Han et al. DATE14: miscorrelation between STA tools Kahng SLIP15: prediction of SI from non-SI Onaissi DAC11: determine dominant corner set Bian DAC17: STA in presence of on-chip variations Runtime improvement for timing analysis TAU Workshop: STA accuracy and runtime Huang SLIP15: speedup timing analysis using MapReduce Silva: identify single corner that has worst delay Our work: Predict PBA outcomes from GBA results ! 8

  9. Our Contributions Identify electrical and structural features of the circuit that affect PBA-GBA slack divergence Develop bigram-based predictive model that can capture PBA-GBA slack divergence Generate artificially generated timing paths that can train our predictive model Demonstrate accuracy and robustness of our models on a variety of testcases and use cases 9

  10. Framework: Bigram-Based Modeling Stage-wise or path-wise (lumped) Lumped Model Shield stage-specific details Very large space of features Difficult to debug outlier stages Bigram-based (n = 2) representation In a given path, transition divergence will be translated into arrival time divergence only for the next stage. Bigrams are a Natural Choice ! 10

  11. Outline Preliminaries Modeling Features Modeling Methodology Experiments Conclusions 11

  12. Modeling Features List of Modeling Features for each bigram unit transition time of the first cell transition time of the second cell arrival time of first cell transition time ratio (TR ratio) of first cell arrival time of second cell drive strength of first cell drive strength of second cell functionality of first cell functionality of second cell fanout of first cell load capacitance of first cell accumulated transition time ratio of first cell propagation delay of second cell 12

  13. Feature Importance Dropping TR ratio reduces the model accuracy by 27% Dropping any feature pair that includes TR ratio corresponds to peaks 13

  14. Outline Preliminaries Modeling Features Modeling Methodology Experiments Conclusions 14

  15. Modeling Flow Need Non-linear techniques can capture complex interactions between features Classification and Regression Trees !!! 15

  16. Model Definition Bigram-based Two Stage Model ????= ? ?????,?????,??_??????,??,???_??_??????,?? , ??,??,? Model2 Transition Time Prediction Arrival Time Prediction Model1 ???? = ? ????,?????,?????,??_??????,??,???_??_??????,?? , ??,??,? 16

  17. Reporting Metrics^ Actual GBA Arrival Time (ps) actual_* metric Model PBA model_* metric Actual PBA We use lumped metrics such as 99th percentile value of divergence, mean absolute value of divergence, and worst-case divergence 17

  18. Outline Preliminaries Modeling Features Modeling Methodology Experiments Conclusions 18

  19. Design of Experiments Knobs number of stages in a timing path; standard cell types in the path; launch and capture flop-types; aggressor cell types; load cap range; transition (slew) time values; clock period values. Artificial Circuits Design Name megaboom leon3mp netcard dec_viterbi jpeg_encoder # Instances 990K 450K 303K 61K 40K Real Designs # Flip-flops 350K 100K 66K 26K 4K 19

  20. Model Setup 28nm FDSOI foundry technology libraries Five public benchmark designs along with artificial circuits Three experiments Accuracy versus Robustness Reference Evaluation Actual GBA Model PBA Actual PBA Actual PBA 20

  21. Experiment 1: Accuracy 70% for training and 30% for testing netcard design Predicted PBA Arrival (ps) 19.90ps 39.59ps Actual GBA Arrival (ps) Actual PBA Arrival (ps) Actual PBA Arrival (ps) 21

  22. Experiment 1: Accuracy megaboom leon3mp netcard dec_viterbi jpeg_encoder Actual GBA (ps) Predicted PBA (ps) Actual PBA (ps) 22

  23. Experiment 2: Robustness Timing paths from a post-CTS database for training, and test the model on a post-routed database of the same design. netcard design Predicted PBA Arrival (ps) 33.56 29.63ps Actual GBA Arrival (ps) Actual PBA Arrival (ps) Actual PBA Arrival (ps) 23

  24. Experiment 2: Robustness megaboom leon3mp netcard dec_viterbi jpeg_encoder Actual GBA (ps) Predicted PBA (ps) Actual PBA (ps) 24

  25. Result 3: Robustness Artificial designs and a sample from a real design (30%) for training, and test on (70%) datapoints of the same real design. netcard design Predicted PBA Arrival (ps) Actual GBA Arrival (ps) Actual PBA Arrival (ps) Actual PBA Arrival (ps) 25

  26. Result 3: Robustness megaboom leon3mp netcard dec_viterbi jpeg_encoder Actual GBA (ps) Predicted PBA (ps) Actual PBA (ps) 26

  27. Outline Preliminaries Modeling Features Modeling Methodology Experiments Conclusions 27

  28. Conclusions First to apply machine learning techniques to model PBA-GBA divergence Artificial circuit generation methodology for potential availability during an initial, bootstrap training phase of modeling Model based on decision trees along with electrical and physical features of stage bigrams in timing paths We assess potential benefits of our model using 28nm FDSOI foundry technology Model-predicted PBA arrival times reduce mean, 99th percentile and max divergence metrics by at least 26.6%, 13.4% and 11.7%, respectively as compared to reference PBA-GBA divergence metrics 28

  29. Future Work Integrate our models with an academic sizer and optimizer Obtain practical benefits from improved accuracy-runtime tradeoff Richer artificial testcases that can span the space of timing paths in real designs We see outlier stages (bigrams) that are very different from any artificial training data) Reduction of optimism in PBA slack prediction But: Optimism not viewed as harmful in current use context! Better use of multiple GBA paths to a given endpoint Multiple GBA paths give more information, but our approach does not derive benefit from them! 29

  30. Acknowledgments Dr. Tuck-Boon Chan Dr. Siddhartha Nath Support: NSF, DARPA, Qualcomm, Samsung, NXP, Mentor Graphics, and the C-DEN center. 30

  31. Thank You 31

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#