Procedure exlining: a transformation for improved system and behavioral synthesis

ABSTRACT

Abstract: We present techniques for solving the inverse problem of procedure inlining, namely the problem of replacing sequences of statements with procedure calls. Two techniques are provided, one for finding redundant sequences of statements that can be replaced by calls to one procedure, and another for dividing a large set of statements into several procedures, where each procedure performs a distinct computation. Such procedure exlining can transform a behavioral specification, originally written for readability, into a specification that can be implemented efficiently, because procedures can greatly improve the results of synthesis tools. We demonstrate the usefulness of the techniques on several examples. We have implemented the procedure exlining technique as part of a VHDL transformation tool.

REFERENCES

• 1: Donald E. Thomas , Jay K. Adams , Herman Schmit, A Model and Methodology for Hardware-Software Codesign, IEEE Design & Test, v.10 n.3, p.6-15, July 1993 [doi>10.1109/54.232468]
• 2: Pravil Gupta , Chih-Tung Chen , J. C. DeSouza-Batista , Alice C. Parker, Experience with image compression chip design using unified system construction tools, Proceedings of the 31st annual conference on Design automation, p.250-256, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196367]
• 3: F. Vahid , D. D. Gajski, Specification partitioning for system design, Proceedings of the 29th ACM/IEEE conference on Design automation, p.219-224, June 08-12, 1992, Anaheim, California, United States
• 4: D. Gajski, F. Vahid, and S. Narayan, 'CA system-design methodology: Executable-specification refinement," in Proceedings of the European Conference on Design A utornation (EDAC), pp. 458-463, 1994.
• 5: N. Kumar, R. Vemuri, and R. Vemuri, "Partitioning for multicomponent synthesis from VHDL specifications," in VHDL International Users' Forum, pp. 19-28, 1993.
• 6: R. Camposano , L. F. Saunders , R. M. Tabet, VHDL as Input for High-Level Synthesis, IEEE Design & Test, v.8 n.1, p.43-49, January 1991 [doi>10.1109/54.75662]
• 7: R. Camposano and R. Brayton, "Partitioning before logic synthesis," in Proceedings of the International Conference on Computer-Aided Design, 1987.
• 8: R. Walker and D. Thomas, "Behavioral transformation for algorithmic level IC design," IEEE Transactions on Computer-Aided Design, pp. 1115-1128, October 1989.
• 9: L. Ramachandran, S. Narayan, F. Vahid, and D. Gajski, "Synthesis of functions and procedures in behavioral VHDL," in Proceedings of the European Design Autornation Conference (EuroVHDL), 1993.
• 10: P. Gutberlet , W. Rosenstiel, Specification of interface components for synchronous data paths, Proceedings of the 7th international symposium on High-level synthesis, p.134-139, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 11: A. Jerraya, I. Park, and K. O'Brien, "Amical: An interactive high-level synthesis environment," in Proceedings of the European Conference on Design Automation (EDAC), pp. 58-62, 1993.
• 12: D. S. Rao , F. J. Kurdahi, Partitioning by regularity extraction, Proceedings of the 29th ACM/IEEE conference on Design automation, p.235-238, June 08-12, 1992, Anaheim, California, United States
• 13: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 14: S. Devadas and A. Newton, "Decomposition and factorization of sequential FSM's," in Proceedings of the International Conference on Computer-Aided Design, 1988.
• 15: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
• 16: E. Lagnese and D. Thomas, "Architectural partitioning for system level synthesis of integrated circuits," IEEE Transactions on Computer-Aided Design, July 1991.
• 17: Frank Vahid , Daniel D. Gajski, Clustering for improved system-level functional partitioning, Proceedings of the 8th international symposium on System synthesis, p.28-35, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224492]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

          Nouns: VHDL

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Experimentation, Languages

Keywords:
VHDL transformation tool, behavioral specification, behavioral synthesis, distinct computation, distributed processing, formal specification, hardware description languages, procedure calls, procedure exlining, procedure inlining, redundant sequences, remote procedure calls, statements, synthesis tools, system synthesis