Visualizing The Behavior Of Logic Synthesis Algorithms
Howard A. Landman
Toshiba America Electronic Components
Unpredictability vs Benchmarking
- Input parameters for synthesis
- Discrete parameters
- RTL architecture, logic function
- Synthesis library
- "Effort" (in dc_shell & ac_shell)
- Flattening, structuring, other switches
- Choice of algorithm
- Choice of synthesis tool
- Continuous parameters
- Input & output delays
- Loading
- Time constraints
- Synthesis tools do not always give predictable results.
- Asking for a faster design may produce a slower one
- Small change to RTL may cause large change in gates
- There's some amount of luck involved!
- Benchmarking issues
- One synthesis is never enough.
- To get reliable comparison of two tools requires many runs
- How do you decide which runs to perform?
- How do you analyze the resulting data to make sense of it?
CDA Space
- Only vary one input parameter, delay constraint (C)
- Only examine resulting delay (D) and area (A)
- Gives a 3-D data set
- Can view in 3 different 2-D projections
- Constraint vs Delay (CD)
- Theoretical curve is:
- Monotonically increasing
- Piecewise constant (each piece = a specific netlist)
- Discontinuous at certain constraint values ("breakpoints") which are equal to delays of optimal netlists
- Constraint vs Area (CA)
- Theoretical curve is:
- Monotonically decreasing
- Piecewise constant (each piece = a specific netlist)
- Discontinuous at same "breakpoints" as for C vs D)
- Delay vs Area (DA, "Banana Curve")
- The Three Myths of the Banana Curve
- It's continuous
- It's monotonically decreasing
- It's convex
- The Three Realities of the Banana Curve
- It's not a curve, but a set of disconnected points, each corresponding to a different netlist
- Theoretically, it's monotonically decreasing, but tools may behave strangely
- Convexity happens when a linear blend of any two solutions is also a solution - but you can't average two netlists!
Gathering the Data
- The Computational Dilemma
- We would like to see the entire curves, but that appears to require #runs = o(1/resolution)
- Not enough computer cycles
- Even worse, not enough licenses!
- A Bold Assumption
- Observe that many synthesis runs (with not-too-different constraints) should produce precisely identical netlists
- ASSUME: That if two adjacent constraints produce exactly the same netlist (character for character), then all intermediate constraints will too
- Then, we don't have to try any more constraints within that interval
- Instead, focus on intervals where the endpoints differ
- The Algorithm
- Binary splitting search on delay constraint, except don't split any interval whose endpoints are identical
- # of runs to resolve a single breakpoint is now o(log(1/resolution))
- In practice, have been able to get resolution of 0.000001 nS in a few thousand runs instead of a few million.
- Implementation details
- For Synopsys, wrote a Perl front-end that talks to dc_shell through a pipe
- Be careful about buffering or it will deadlock!
- For Ambit, recoded same functionality in Tcl
- For both tools, saved all netlists & area & timing reports (disk space is cheap)
- Compare size, followed by cmp, to check whether netlists are identical
Visualization
- The Visual Display of Quantitative Information by Tufte
- Perl scripts to extract timing and area data from reports
- Gnuplot
- does simple things pretty well
- is free & comes with source code
- preview on screen, redirect to color PostScript printer
Examples
Conclusions
- Visualization helps show whether, and how, tools differ
- Cost of getting entire spectrum of data is not prohibitive for small designs
- Pictures suggest statistical measures which can be used to reliably evaluate effect of code changes