Co-synthesis of pipelined structures and instruction reordering constraints for instruction set processors

ABSTRACT

This paper presents a hardware/software co-synthesis approach to pipelined ISP (instruction set processor) design. The approach synthesizes the pipeline structure from a given instruction set architecture (behavioral) specification. In addition, it generates a set of reordering constraints that guides the compiler back-end (reorderer) to properly schedule instructions so that possible pipeline hazards are avoided and throughput is improved.Co-synthesis takes place while resolving pipeline hazards, which can be attributed to interin-struction dependencies (IIDs). An extended taxonomy of IIDs have been proposed for the systematic analysis of pipeline hazards. Hardware/software methods are developed to resolve IIDs. Algorithms based on taxonomy and resolutions are constructed and integrated into the pipeline synthesis process to explore hardware and software design space. Application benchmarks are used to evaluate possible designs and guide the design decision. The power of the co-synthesis tool PIPER is demonstrated through pipeline synthesis of one illustrative example and two ISPs, including an industrial one (TDY-43). In comparison with other related approaches, our approach achieves higher throughput and provides a systematic way to explore the hardware/software trade-off.

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: CARLTON, M. 1991. Source codes of the Aquarius prolog compiler (Back-end). Computer Science Department, University of California at Berkeley, Berkeley, CA.
• 3: R. G. Cattell, Automatic Derivation of Code Generators from Machine Descriptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.173-190, April 1980 [doi>10.1145/357094.357097]
• 4: Wei Kai Cheng , Youn Long Lin, Code generation for a DSP processor, Proceedings of the 7th international symposium on High-level synthesis, p.82-87, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 5: CLOUTIER, R. 1993. Synthesis of pipelined instruction set processors. Ph.D. Dissertation. Dept. of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA.
• 6: FISHER, J. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7 (July), 478-490.
• 7: Robert Giegerich, A Formal Framework for the Derivation of Machine-Specific Optimizers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.478-498, July 1983 [doi>10.1145/2166.357219]
• 8: GOOSSENS, G., RABAEY, J., VANDEWALLE, J., AND DE MAN, H. 1990. An efficient microcode compiler for application specific DSP processors. IEEE Trans. Comput.-Aided Des. 9,9 (Sept.), 925-937.
• 9: GRAHAM, S. L. 1980. Table-driven code generation. IEEE Computer 13, 8 (Aug.).
• 10: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• 11: 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
• 12: HUANG, I.-J. 1997. Synthesis and analysis of an industrial embedded microcontrol. In Proceedings of the Conference on Asia and South Pacific Design Automation (Jan.). ACM Press, New York, NY.
• 13: 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]
• 14: Gerry Kane, MIPS RISC architecture, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 15: KOGGE, P. M. 1981. The Architecture of Pipelined Computers. McGraw-Hill, Inc., New York, NY.
• 16: Monica Sin-Ling Lam, A systolic array optimizing compiler, 1987
• 17: Tsing-Fa Lee , Allen C.-H. Wu , Daniel D. Gajski , Youn-Long Lin, An effective methodology for functional pipelining, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.230-233, November 1992, Santa Clara, California, United States
• 18: LIEM,C.M.T.AND PAULIN, P. 1994. Instruction-set matching and selection for DSP and ASIP code generation. In Proceedings of the 1994 Conference on European Design and Test (Paris, France, Feb.). 31-37.
• 19: Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
• 20: PARK,N.AND PARKER, A. C. 1988. Sehwa: A software package for synthesis of pipelines from behavioral specifications. IEEE Trans. Comput.-Aided Des. Integr. Circuits 7, 3 (Mar.), 356-368.
• 21: Janak H. Patel , Edward S. Davidson, Improving the throughput of a pipeline by insertion of delays, Proceedings of the 3rd annual symposium on Computer architecture, p.159-164, January 19-21, 1976
• 22: PAULIN,P.G.AND KNIGHT, J. P. 1989. Force-directed scheduling for the behavioral synthesis of ASICs. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 8, 6 (June), 661-679.
• 23: Apoorv Srivastava , Alvin M. Despain, Prophetic branches: a branch architecture for code compaction and efficient execution, Proceedings of the 26th annual international symposium on Microarchitecture, p.94-99, December 01-03, 1993, Austin, Texas, United States
• 24: SU, C.-L. AND DESPAIN, A. 1992. An instruction scheduler and register allocator for prolog parallel microprocessors. In Proceedings of the Conference on International Computer Symposium.
• 25: TELEDYNE SYSTEMS CO. 1988. Programming Manual for the Teledyne TDY-43 Computer.
• 26: TOMASULO, R. M. 1967. An efficient algorithm for exploiting multiple arithmetic units. IBM J. Res. Dev. 11, 1 (Jan.), 25-33.
• 27: Johan Van Praet , Gert Goossens , Dirk Lanneer , Hugo De Man, Instruction set definition and instruction selection for ASIPs, Proceedings of the 7th international symposium on High-level synthesis, p.11-16, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.2 Control Structure Performance Analysis and Design Aids
          Subjects: Automatic synthesis**

General Terms:
Design, Theory

Keywords:
compiler instruction optimization\, instruction set processor, pipeline hazards, pipeline taxonomy, synthesis