Transcript Document

Blame Passing for Analysis and
Optimisation
Charlie Brej
APT Group
University of Manchester
17/07/2015
Async Forum
1
Overview
Introduction
Synchronous methods
Blame passing
Optimisations
Results
17/07/2015
Group Talk
2
Why we need optimisation
High level entry languages
RTL
Gates
Transistors
Silicon
Large designs
More important things to worry about
Optimal designs often difficult to read
Difficult to determine inefficiencies
17/07/2015
Group Talk
3
Critical path analysis
1
2
1
17/07/2015
3
2
4
5
3
Group Talk
4
Retiming
17/07/2015
Group Talk
5
Why we don’t use the Critical Path
Assumes isochronic arrival of all inputs in each
stage
Or predictable sequencing and timing of arrival of
inputs (deterministic)
No cyclic circuits
No C-elements
Only looks at logic and not latches
No method of determining the interaction between
different computation cycles
Determines and improves the worst (not
average / “mode”) case performance
17/07/2015
Group Talk
6
Slowest Path
Designed for asynchronous circuits
Allows cyclic circuits
Allows non-deterministic behavior
Uses a real simulation
Gathers average case data (not worst case)
Sort of like critical path of a full benchmark
Start point is the release of the reset
End point is the benchmark completion signal
17/07/2015
Group Talk
7
Blame Game
2nd
Place
Output
1st
Place
Benchmark
complete
17/07/2015
Group Talk
8
Blame Game
17/07/2015
Group Talk
9
Pass the blame
Blame passing forms a path from
completion back to reset release
How to extract path
Static timing analysis (cyclic paths)
Simulation dump (lots of data)
Use a custom simulator
Small overhead (~30%)
Only remember the slowest path transitions
17/07/2015
Group Talk
10
Decrementer
while (1) {
if (Reg != 0)
else
}
17/07/2015
Reg = Reg – 1;
Reg = Const;
Group Talk
11
Graphical representation
17/07/2015
Group Talk
12
Apply Optimisations
Find known paths through elements
Paths with positive effect
Paths with negative effect
Apply optimisation
Simulate again to determine the effect
17/07/2015
Group Talk
13
Optimisation Rules
17/07/2015
Group Talk
14
Optimisation Rules
17/07/2015
Group Talk
15
Optimisation Rules
17/07/2015
Group Talk
16
Optimisation Results (Dec)
17/07/2015
Group Talk
17
Optimisation Results (GCD)
17/07/2015
Group Talk
18
Optimisation Results (MIPS)
17/07/2015
Group Talk
19
Conclusions
Novel analysis and optimisation technique
Applicable to many asynchronous systems
Not just circuits
Automatic reanalysis system
Future work:
Read SDF files
Extension to other systems (Balsa etc)
Connection to a full design system (Biscotti)
17/07/2015
Group Talk
20