Memory, control and communications synthesis for scheduled algorithms

ABSTRACT

This paper explores a method of grouping individual memory requirements from a hardware-constrained schedule of an algorithm, such that control and communications may be optimised. A new representation of memory requirements is introduced to explain the method. The technique may also be used to allocate operations to hardware resources. This, and control and communication optimisation are illustrated with an example.

REFERENCES

• 1: Verbauwhede, i. et al., "Background Memory Synthesis for Algebraic Algorithms on Multi-Processor DSP Chips," Proc. VLSI 89, pp. 209-218.
• 2: Balakrishnan, M. et al., "Allocation of Multiport Memories in Data Path Synthesis'" IEEE Trans. CAD. Vol. 7, No. 4, April 1988, pp. 536-540.
• 3: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 4: Stok, L. and Van Den Born, R., "EASY ~ Multiprocessor Architecture Optimization", in Proc. Int. Workshop on Logic and Architecture Synthesis for Silicon Compilers, ed. Saucier, G. and McLellan, P.M., Grenoble, May 1988, pp. 313-328.
• 5: Tseng, C. and Sewiorek, D.P., "Automated Synthesis of Data Paths in Digital Systems," 1EEE Trans. Computer-Aided Design, Vol. CAD-5, july 1985, pp. 379-395.
• 6: Barry M. Pangre, Splicer: a heuristic approach to connectivity binding, Proceedings of the 25th ACM/IEEE conference on Design automation, p.536-541, June 12-15, 1988, Atlantic City, New Jersey, United States
• 7: Haroun, B.S. and Elmasry, M.I., "Architectural Synthesis for DSP Silicon Compilers", IEEE Trans. CAD., Vol. 8, No. 4, April 1989, pp. 43}-447.
• 8: Bergamaschi, R.A. and Allerton, D.J., "A Graph- Based Silicon Compiler for Concurrent VLSI Systems," IEEE CompEuro., 1988, pp. 36-4 7.
• 9: P. G. Paulin , J. P. Knight, Force-directed scheduling in automatic data path synthesis, Proceedings of the 24th ACM/IEEE conference on Design automation, p.195-202, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37918]
• 10: Alan Tucker, Applied combinatorics (3rd ed.), John Wiley & Sons, Inc., New York, NY, 1994

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design