A data flow architecture with a paged memory system

ABSTRACT

During the last ten years, data flow has become an exciting research area and several architectures have been proposed and built. They differ mostly in the way they handle data structures and how they provide mechanisms for token labeling or colouring in order to make data flow graphs reentrant. The paper presents a data flow architecture with a paged memory system to hold both data flow programs and data structures. The token labeling mechanism is coupled with the memory management system in order to provide for each token a unique memory location. The instruction format allows instructions with multiple operands and multiple destinations for each result. Data structures are held in memory while pointers to the structures are circulating as tokens. The proposed architecture is able to execute data flow programs at the level of single instructions or at a higher level.

REFERENCES

• 1: Ackerman, William B., "A structure processing facility for data flow computers", Proc. of the Int. Conf. on Parallel Processing for Computer Aug. 1978, pp. 166-172.
• 2: Ackerman, W.B., "Data flow languages", Proc. 1979 National Computer Conf., pp. 1087-1095.
• 3: Arvind, and Gostelow, Kim P., "The ID report: an asynchronous language and computing machine," TR-114, Dept. of Computer and Information Science, Univ. of California, Irvine, CA, Sept. 1978.
• 4: Arvind, and Thomas, "I-structures: an efficient datatype for functional languages", TM-178, Laboratory for Comp. Sc., MIT, Cambridge, Mass., Sept. 1980.
• 5: Arvind , Vinod Kathail, A multiple processor data flow machine that supports generalized procedures, Proceedings of the 8th annual symposium on Computer Architecture, p.291-302, May 12-14, 1981, Minneapolis, Minnesota, United States
• 6: Chamberlin, D. D., "The 'single-assignment' approach to parallel processing", Proc. AFIPS 1971, FJCC, Nov. 1971, pp. 263-269.
• 7: Comte, D., Durrieu G., Gelly O., Plas A., and Syre J. C., "Systeme LAU, Summary in English, Teau 9/7", CERT-ONERA Toulouse, 10 Oct. 1976.
• 8: Davis, A. L., "A data flow evaluation system based on the concept of recursive locality", National Computer Conf. 1979, pp. 1079-1086.
• 9: J. B. Dennis, First version of a data flow procedure language, Programming Symposium, Proceedings Colloque sur la Programmation, p.362-376, April 09-11, 1974
• 10: Gostelow, K.P., and Thomas, R.E., "Performance of a simulated data flow computer", IEEE Trans. on Comp., Vol. C-29, no. 10, Oct. 1980, pp. 905-919.
• 11: Gurd, J. and Watson, I., Glauert, "A multilayered data flow computer architecture", Dept. of Comp. Sc., Univ. of Manchester, Manchester, March 1980.
• 12: Gurd, J., "The Manchester data flow machine: Basic programming manual", Dept. of Comp. Sc., Univ. of Manchester, Manchester, Dec. 1980.
• 13: Hopkins, Richard P., Rautenbach, Paul W., and Treleaven, Philip C., "A data flow computer with addressable memory", Proc. Workshop on Data Driven Languages and Machines, Toulouse, France, February 1979, pp. IX1-IX12.
• 14: Johnson, D., "Data flow machines threaten the program counter", Electronic design, 22 Nov. 1980, pp. 255-258.
• 15: J. Lewi , M. Huybrechts , Vlaminck K. De , J. Huens, A Programming Methodology in Compiler Construction, Elsevier Science Inc., New York, NY, 1979
• 16: Miranker, Glen Seth, "Implementation of procedures on a class of data flow processors", Proc. of the 1977 Int. Conf. on Parallel Processing, Aug. 1977, pp. 77-86.
• 17: Misunas, D.P., "A Computer architecture for data flow computation", TM-100, Laboratory for Comp. Sc., MIT, Cambridge, Mass., March 1978.
• 18: Misunas, D.P., "Report on the second workshop on data flow computer and program organization", TM-136, Laboratory for Comp. Sc., MIT, Cambridge, Mass., June 1979.
• 19: Rumbaugh, J.E., "A parallel asynchronous computer architecture for data flow programs", TR-150, Laboratory for Comp. Sc., MIT, Cambridge, Mass., May 1975.
• 20: Watson, I. and Gurd, J., "A prototype data flow computer with token labelling", AFIPS National Computer Conf. 1979, Vol. 48, June 1979, pp. 623-628.
• 21: K. S. Weng, AN ABSTRACT IMPLEMENTATION FOR A GENERALIZED DATA FLOW LANGUAGE, Massachusetts Institute of Technology, Cambridge, MA, 1980

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Design, Management

Keywords:
Data flow, Paged memory, Parallel processing