High-level automatic pipelining for sequential circuits

ABSTRACT

This paper presents a new approach for automatically pipelining sequential circuits. The approach repeatedly extracts a computation from the critical path, moves it into a new stage, then uses speculation to generate a stream of values that keep the pipeline full. The newly generated circuit retains enough state to recover from incorrect speculations by flushing the incorrect values from the pipeline, restoring the correct state, then restarting the computation.We also implement two extensions to this basic approach: stalling, which minimizes circuit area by eliminating speculation, and forwarding, which increases the throughput of the generated circuit by forwarding correct values to preceding pipeline stages. We have implemented a prototype synthesizer based on this approach. Our experimental results show that, starting with a non-pipelined or insufficiently pipelined specification, this synthesizer can effectively reduce the clock cycle time and improve the throughput of the generated circuit.

REFERENCES

• 1: Mauricio Breternitz, Jr. , John Paul Shen, Architecture synthesis of high-performance application-specific processors, Proceedings of the 27th ACM/IEEE conference on Design automation, p.542-548, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123398]
• 2: Felix Sheng-Ho Chang, Fast Specification of Cycle-Accurate Processor Models, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.488, September 23-26, 2001
• 3: Richard J. Cloutier , Donald E. Thomas, Synthesis of pipelined instruction set processors, Proceedings of the 30th international conference on Design automation, p.583-588, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165053]
• 4: H.D.M.G.Goossens,J.Rabaey nd J.V ndew lle.An efficient microcode-compiler for custom DSP-processors.IEEE Transactions on Computer-Aided Design 9:925 -937,1990.
• 5: G. Goossens , J. Vandewlle , H. De Man, Loop optimization in register-transfer scheduling for DSP-systems, Proceedings of the 26th ACM/IEEE conference on Design automation, p.826-831, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74384]
• 6: Soha Hassoun , Carl Ebeling, Architectural retiming: pipelining latency-constrained circuits, Proceedings of the 33rd annual conference on Design automation, p.708-713, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240652]
• 7: James C. Hoe , Arvind, Hardware Synthesis from Term Rewriting Systems, Proceedings of the IFIP TC10/WG10.5 Tenth International Conference on Very Large Scale Integration: Systems on a Chip, p.595-619, December 01-04, 1999
• 8: U. Holtmann , R. Ernst, Combining MBP-speculative computation and loop pipelining in high-level synthesis, Proceedings of the 1995 European conference on Design and Test, p.550, March 06-09, 1995
• 9: I.-J. Huang , A. M. Despain, High level synthesis of pipelined instruction set processors and back-end compilers, Proceedings of the 29th ACM/IEEE conference on Design automation, p.135-140, June 08-12, 1992, Anaheim, California, United States
• 10: Cheng-Tsung Hwang , Yu-Chin Hsu , Youn-Long Lin, Scheduling for functional pipelining and loop winding, Proceedings of the 28th conference on ACM/IEEE design automation, p.764-769, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127766]
• 11: Daniel Kroening , Wolfgang J. Paul, Automated pipeline design, Proceedings of the 38th conference on Design automation, p.810-815, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379071]
• 12: C.E.Leiserson,F.Rose,nd J.Saxe.Optimizing synchronous ciruitry by retiming.In Proceedings of the 3rd Caltech Conference on VLSI
• 13: Maria-Cristina Marinescu , Martin Rinard, High-level specification and efficient implementation of pipelined circuits, Proceedings of the 2001 conference on Asia South Pacific design automation, p.655-661, January 2001, Yokohama, Japan [doi>10.1145/370155.370575]
• 14: N.P rk and A.C.Parker.Sehw :A softw re package for synthesis of pipelines from behavioral specifications.IEEE Transactions on Computer-Aided Design 7:356 -370,1988.
• 15: P.B.P ulin and J.P.Knight.Force-directed scheduling for the behavioral synthesis of ASIC 's.IEEE Transactions on Computer-Aided Design 8:661 -679,1989.
• 16: Arvind , Xiaowei Shen, Using Term Rewriting Systems to Design and Verify Processors, IEEE Micro, v.19 n.3, p.36-46, May 1999 [doi>10.1109/40.768501]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture

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

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures

General Terms:
Design, Experimentation, Performance

Keywords:
forward, modular, pipeline, speculation, stall