Generation of synthetic sequential benchmark circuits

ABSTRACT

Programmable logic architectures increase in capacity before commercial circuits are designed for them, yielding a distinct problem for FPGA vendors: how to test and evaluate the effectiveness of new architectures and software. Benchmark circuits arc a precious commodity, and often cannot be found at the correct granularity, or in the desired quantity. In previous work, we have defined important physical characteristics of combinational circuits. We presented a tool (CIRC) to extract them, and gaue an algorithm and tool (GEN) which generates random circuits, parameterized by those characteristics or by a realistic set of defaults. Though a promising step, only a small portion of real circuits are fully combinational. In this paper we extend the effort to model sequential circuits. We propose new characteristics and generate circuits which are sequential. This allows for the generation of truly useful benchmark circuits, both at and beyond the sizes of next-generation FPGAs. By comparing the post-lay out properties of the generated circuits with already existing circuits, we demonstrate that the synthetic circuits are much more realistic than random graphs with the same number of nodes, edges and I/Os.

REFERENCES

• 1: C. Alpert, Private communication. UCLA and IBM Austin.
• 2: Altera Corporation, I996 Data Book.
• 3: Vaughn Betz , Jonathan Rose, Directional bias and non-uniformity in FPGA global routing architectures, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.652-659, November 10-14, 1996, San Jose, California, United States
• 4: Joel Darnauer , Wayne Wei-Ming Dai, A method for generating random circuits and its application to routability measurement, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.66-72, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228380]
• 5: E. R. Gansner , E. Koutsofios , S. C. North , K.-P. Vo, A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering, v.19 n.3, p.214-230, March 1993 [doi>10.1109/32.221135]
• 6: M.D. Hutton, Characterization and Generation of Digital Benchmark Circuits. Ph.D. Thesis in preparation, University of Toronto, 1996.
• 7: Michael Hutton , J. P. Grossman , Jonathan Rose , Derek Corneil, Characterization and parameterized random generation of digital circuits, Proceedings of the 33rd annual conference on Design automation, p.94-99, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240537]
• 8: Programmable Electronics Performance Corporation, PLD Benchmark Suite~I, VI.2. 504 Nino Ave. Los Gatos, CA 95032, 1993.
• 9: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Sequential circuits; Combinational logic

General Terms:
Algorithms, Design, Performance, Verification