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
      1. It's continuous
      2. It's monotonically decreasing
      3. It's convex
    • The Three Realities of the Banana Curve
      1. It's not a curve, but a set of disconnected points, each corresponding to a different netlist
      2. Theoretically, it's monotonically decreasing, but tools may behave strangely
      3. 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