Dataflow machine architecture

ABSTRACT

Dataflow machines are programmable computers of which the hardware is optimized for fine-grain data-driven parallel computation. The principles and complications of data-driven execution are explained, as well as the advantages and costs of fine-grain parallelism. A general model for a dataflow machine is presented and the major design options are discussed. Most dataflow machines described in the literature are surveyed on the basis of this model and its associated technology. For general-purpose computing the most promising dataflow machines are those that employ packet-switching communication and support general recursion. Such a recursion mechanism requires an extremely fast mechanism to map a sparsely occupied virtual space to a physical space of realistic size. No solution has yet proved fully satisfactory. A working prototype of one processing element is described in detail. On the basis of experience with this prototype, some of the objections raised against the dataflow approach are discussed. It appears that the overhead due to fine-grain parallelism can be made acceptable by sophisticated compiling and employing special hardware for the storage of data structures. Many computing-intensive programs show sufficient parallelism. In fact, a major problem is to restrain parallelism when machine resources tend to get overloaded. Another issue that requires further investigation is the distribution of computation and data structures over the processing elements.

REFERENCES

• 1: ALLAN, S. J., ANO OLDEHOEFT, A. E. 1980. A flow analysis procedure for the translation of highlevel languages to a data flow language. IEEE Trans. Comput. C-29, 9 (Sept.) 826-831.
• 2: AMAMIVA, M., HASEGAWA, R., NAKAMURA, O., ANO MIKAMI, H. 1982. A list-processing-oriented data flow machine architecture. In Proceedings of the AFIPS National Computer Conference 82. AFIPS Press, Reston, Va., pp. 143-151.
• 3: M. Amamiya , M. Takesue , R. Hasegawa , H. Mikami, Implementation and evaluation of a list-processing-oriented data flow machine, Proceedings of the 13th annual international symposium on Computer architecture, p.10-19, June 02-05, 1986, Tokyo, Japan
• 4: ARVIND AND GOSTELOW, K. P. 1977. A computer capable of exchanging processors for time. In In{ormation Processing 77, B. Gilchrist, Ed. North-Holland, New York, pp. 849-853.
• 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: ARVINO AND THOMAS, R. E. 1980. I-Structures: An efficient data type for functional languages. Tech. Memo. 210, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass.
• 7: ARVIND, KATHAIL, V., AND PINGALI, K. 1980. A datafiow architecture with tagged tokens. Tech. Memo. 174, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass.
• 8: BARAHONA, P., AND GURD, J. R. 1985. Simulated performance of the Manchester multi-ring dataflow machine. In Parallel Computing 85. North- Holland, Amsterdam, pp. 419-424.
• 9: BOHM, A. P. W., AND SARGEANT, J. 1985. Efficient dataflow code generation. In Parallel Computing 85. North-Holland, Amsterdam, pp. 339-344.
• 10: BOWEN, D. L. i981. Implementation of data structures on a data flow computer. Ph.D. dissertation, Dept. of Computer Science, Victoria Univ. of Manchester, Manchester, England.
• 11: BROCK, J. D., AND MONTZ, L. B. 1979. Translation and optimization of data flow programs. CSG Memo. 181, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass.
• 12: F. J. Burkowski, A multi-user data flow architecture, Proceedings of the 8th annual symposium on Computer Architecture, p.327-340, May 12-14, 1981, Minneapolis, Minnesota, United States
• 13: CALUWAERTS, L. J., DEBACKER, J., AND PEPER- STRAETE, J.A. 1982. Implementing code reentrancy in functional programs on a datafiow computer system with a paged memory. In The International Workshop on High-Level Language Computer Architecture (Fort Lauderdale, Fla., Dec. 1-3).
• 14: COMTE, D., HIFDI, N., AND SYRE, J. C. 1980. The data driven LAU multiprocessor system: Results and perspectives. In Proceedings of the IFIP Congress 80 (Tokyo and Melbourne, Australia, Oct. 6-17), S. Lavington, Ed. North-Holland, Amsterdam, pp. 175-180.
• 15: CORNISH, M., ET AL. 1979. The TI data flow architectures: The power of concurrency for avionics. In Proceedings of the 3rd Conference on Digital Avionics Systems (Fort Worth, Tex., Nov.). IEEE, New York, pp. 19-25.
• 16: J. Darlington , D. Turner , P. Henderson, Functional Programming and Its Applications: An Advanced Course, Cambridge University Press, New York, NY, 1982
• 17: DA SILVA, J. G. D., AND WATSON, I. 1983. Pseudoassociative store with hardware hashing. IEEE Proceedings, Pt. E 130, 1, 19-24.
• 18: DAVIS, A. L. 1977. Architecture of DDMi: A recursively structured data driven machine. Tech. Rep., Dept. of Computer Science, Univ. of Utah, Salt Lake City, Utah.
• 19: DAVIS, A. L. 1979. A data flow evaluation system based on the concept of recursive locality. In Proceedings o{ the National Computing Conference. AFIPS Press, Reston, Va., pp. 1079-1086.
• 20: DENNIS, J. B. 1969. Programming generality, parallelism and computer architecture. Information Processing 68 (Amsterdam). North-Holland, Amsterdam, pp. 484-492.
• 21: 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
• 22: DENNIS, J. B. 1980. Data flow supercomputers. Computer 13, 4 (Nov.), 48-56.
• 23: Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, Proceedings of the 2nd annual symposium on Computer architecture, p.126-132, January 20-22, 1975
• 24: Jack B. Dennis , G. Andrew Boughton , Clement K.C. Leung, Building blocks for data flow prototypes, Proceedings of the 7th annual symposium on Computer Architecture, p.1-8, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801902]
• 25: DENNIS, J. B., LIM, W. Y. P., AND ACKERMAN, W. B. 1983. The MIT data flow engineering model. In Proceedings of the IFIP 9th World Computer Congress (Paris, Sept. 19-23), R. E. A. Mason, Ed. North-Holland, New York, pp. 553-560.
• 26: DENNIS, J. B., GAD, G. R., AND TODD, K. W. 1984. Modeling the weather with a data flow supercomputer. IEEE Trans. Comput. C-33, 7 (July), 592-603.
• 27: FLYNN, M. J., 1972. Some computer organizations and their effectiveness, iEEE Trans. Comput. C-21, 9 (Sept.), 948-960.
• 28: John Francis Foley, A hardware simulator for a multi-ring dataflow machine, 1986
• 29: GAJSKI, D. D., PADUA, D. A., KUCK, D. J., AND KUHN, R. H. 1982. A second opinion on data flow machines and languages. Computer 15, 2 (Feb.), 58-69.
• 30: Jean-Luc Gaudiot, Structure handling in data-flow systems, IEEE Transactions on Computers, v.35 n.6, p.489-502, June 1986 [doi>10.1109/TC.1986.5009426]
• 31: GAUDIOT, J. L., AND WEI, Y. H. 1986. Token relabeling in a tagged data-flow architecture. In Proceedings o{ the 1986 International Con{erence on Parallel Processing (St. Charles, Aug. 19-22). IEEE, New York, pp. 592-599.
• 32: GLAUERT, J. R. W. 1984. High level datafiow programming. In Distributed Computing, F. B. Chambers, D. A. Duce and G. P. Jones, Eds. Academic Press, Orlando, Fla., pp. 43-53.
• 33: GOSTELOW, K. P., AND THOMAS, R. E. 1980. Performance of a simulated datafiow computer. IEEE Trans. Comput. C-29, 10 (Oct.), 905-919.
• 34: GURD, J., AND BOHM, A. P.W. 1987. Implicit parallel processing: SISAL on the manchester datafiow computer. In Proceedings o{ the IBM-Europe Institute on Parallel Processing (Oberlech, Aug.), G. Amalsi, R. W. Hockney, and G. Paul, Eds. North-Holland, Amsterdam.
• 35: GURD, J., AND WATSON, I. 1980. A data driven system for high speed parallel computing. Comput. Design 9, 6 and 7 (June), 91-100 and 97-106.
• 36: GURD, J., AND WATSON, I. 1983. Preliminary evaluation of a prototype datafiow computer. In Proceedings of the 9th IFIP World Computer Congress (Paris, Sept. 19-23), R. Mason, Ed. North-Holland, Amsterdam, pp. 545-551.
• 37: J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
• 38: GURD, J., KIRKHAM, C. C., AND BOHM, A. P. W. 1987. The Manchester datafiow computing systern. In Experimental Parallel Computing Architecture, J. Dongarra, Ed. North-Holland, Amsterdam, pp. 177-219.
• 39: Iiro Hartimo , Klaus Kronlof , Olli Simula , Jorma Skytta, DFSP: A data flow signal processor, IEEE Transactions on Computers, v.35 n.1, p.23-33, Jan. 1986 [doi>10.1109/TC.1986.1676654]
• 40: HAZRA, A. 1982. A description method and a classification scheme for data flow architectures. In Proceedings of the 3rd International Conference on Distributed Computing Systems (Oct.). IEEE, New York, pp. 645-651.
• 41: HIRAKI, K., NISHIDA, K., SEKIGUCHI, S., AND SmMAOA, T. 1986. Maintenance architecture and its LSI implementation of a datafiow computer with a large number of processors. In Proceedings of the international Conference on Parallel Processing. IEEE, New York, pp. 584-591.
• 42: HOGENAUER, E. B., NEWBOLO, R. F., AND INN, Y. J. 1982. DDSP--A data flow computer for signal processing. In Proceedings of the International Conference on Parallel Processing. IEEE, New York, pp. 126-133.
• 43: Paul Hudak , Benjamin Goldberg, Distributed execution of functional programs using serial combinators, IEEE Transactions on Computers, v.34 n.10, p.881-891, Oct. 1985
• 44: N Ito , M Kishi , E Kuno , K Rokusawa, The dataflow-based parallel inference machine to support two basic languages in KL1, Proc. of the IFIP TC 10 working conference on Fifth generation computer architectures, p.123-145, October 1986, Manchester, United Kingdom
• 45: N. Ito , M. Sato , E. Kuno , K. Rokusawa, The architecture and preliminary evaluation results of the experimental parallel inference machine PIM-D, Proceedings of the 13th annual international symposium on Computer architecture, p.149-156, June 02-05, 1986, Tokyo, Japan
• 46: IWASHITA, M., TEMMA, T., MATSUMOTO, K., ANO KUROKAWA, H. 1983. Modular datafiow image processor. In Spring 83 COMPCON. IEEE, New York, pp. 464-467.
• 47: JEFFERY, T. 1985. The ~PD7281 Processor. Byte (Nov.) 237-246.
• 48: JOHNSON, D., ET AL. 1980. Automatic partitioning of programs in multiprocessor systems. In Proceedings of the Spring 80 COMPCON. IEEE, New York.
• 49: KARP, R. M., AND MILLER, R. E. 1966. Properties of a model for parallel computations: Determinacy, termination, queueing. SIAM J. Appl. Math. 14, 6 (Nov.), 1390-1411.
• 50: K. Hawakami , J. R. Gurd, A scalable dataflow structure store, Proceedings of the 13th annual international symposium on Computer architecture, p.243-250, June 02-05, 1986, Tokyo, Japan
• 51: KELLER, R. M., LINDSTROM, G., AND PATIL, S. 1979. A loosely-coupled applicative multiprocessing system. In Proceedings of the National Computer Conference (New York, June 4-7). AFIPS Press, Reston, Va., pp. 613-622.
• 52: KIRKHAM, C. C. 1981. Basic programming manual of the Manchester prototype datafiow system, 2nd ed. Datafiow Research Group, Manchester Univ., Manchester, England.
• 53: Masasuke Kishi , Hiroshi Yasuhara , Yasusuke Kawamura, DDDP-a Distributed Data Driven Processor, Proceedings of the 10th annual international symposium on Computer architecture, p.236-242, June 13-17, 1983, Stockholm, Sweden
• 54: LECOUFFE, M. P. 1979. MAUD: A dynamic singleassignment system. Comput. Digital Tech. 2, 2 (Apr.), 75-79.
• 55: R. W. Marczyński , J. Milewski, A data driven system based on a microprogrammed processor module, Proceedings of the 10th annual international symposium on Computer architecture, p.98-106, June 13-17, 1983, Stockholm, Sweden
• 56: James R. McGraw, The VAL Language: Description and Analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.44-82, Jan. 1982 [doi>10.1145/357153.357157]
• 57: MIRANKER, G. S. 1977. Implementation of procedures on a class of data flow processors, in Proceedings of the 1977 International Conference on Parallel Processing (Detroit, Mich., Aug. 23-26), J. L. Baer, Ed. IEEE, New York, pp. 77-86.
• 58: MISUNAS, D. P. 1978. A computer architecture for data flow computation. Tech. Memo. 100, Laboratory for Computer Science, Massachusetts institute of Technology, Cambridge, Mass.
• 59: L. B. Montz, SAFETY AND OPTIMIZATION TRANSFORMATIONS FOR DATA FLOW PROGRAMS, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 60: PEYTON-JoNEs, S. L. 1984. Directions in functional programming research. In Distributed Computing Systems Programme, D. A. Duce, Ed. Peter Peregrinus, London, pp. 220-249.
• 61: Bruno R. Preiss , V. C. Hamacher, Data flow on a queue machine, Proceedings of the 12th annual international symposium on Computer architecture, p.342-351, June 17-19, 1985, Boston, Massachusetts, United States
• 62: J. E. Rodrigues , Jorge E Rodriguez Bezos, A GRAPH MODEL FOR PARALLEL COMPUTATIONS, Massachusetts Institute of Technology, Cambridge, MA, 1969
• 63: RUMBAUGH, J. 1975. A data flow multiprocessor. In Proceedings of the 1975 Sagamore Computer Conference on Parallel Processing (Sagamore, N.Y.), pp. 220-223.
• 64: J. Sargeant , C. C. Kirkham, Stored data structures on the Manchester dataflow machine, Proceedings of the 13th annual international symposium on Computer architecture, p.235-242, June 02-05, 1986, Tokyo, Japan
• 65: T. Shimada , K. Hiraki , K. Nishida , S. Sekiguchi, Evaluation of a prototype data flow processor of the SIGMA-1 for scientific computations, Proceedings of the 13th annual international symposium on Computer architecture, p.226-234, June 02-05, 1986, Tokyo, Japan
• 66: SMITH, B. J. 1978. A pipelined shared resource MIMD computer. In Proceedings of the 1978 International Conference on Parallel Processing. IEEE, New York.
• 67: Vason P Srini, An architectural comparison of dataflow systems, Computer, v.19 n.3, p.68-88, March 1986 [doi>10.1109/MC.1986.1663181]
• 68: SWAN, R. J., FULLER, S. H., AND SIEWIOREK, D. P. 1977. Cm*--A modular, multi-microprocessor. In Proceedings of the National Computer Conference (Dallas, Tex., June 13-16). AFIPS Press, Arlington, Va., pp. 637-644.
• 69: SYRE, J. C. 1980. l~tude et realisation d'un systeme multiprocesseur MIMD en assignation unique. Thbse, Univ. Paul Sabartier de Toulouse, Toulouse, France.
• 70: SYRE, J. C., COMTE, D., AND NlrDI, N. 1977. Pipelining, parallelism and asynchronism in the LAU system. In Proceedings of the 1977 International Conference on Parallel Processing (Detroit, Mich., Aug. 23-26), J. L. Baer, Ed. IEEE, New York, pp. 87-92.
• 71: Naohisa Takahashi , Makoto Amamiya, A data flow processor array system: Design and analysis, Proceedings of the 10th annual international symposium on Computer architecture, p.243-250, June 13-17, 1983, Stockholm, Sweden
• 72: K Toda , Y Yamaguchi , Y Uchibori , T Yuba, Preliminary measurements of the ETL LISP-based data-driven machine, Proc. of the IFIP TC 10 working conference on Fifth generation computer architectures, p.235-253, October 1986, Manchester, United Kingdom
• 73: TRELEAVEN, P. C., HOPKINS, R. P., AND RAUTEN- SACH, P. W. 1982a. Combining data flow and control flow computing. Comput. J. 25, 2 (Feb.), 207-217.
• 74: Philip C. Treleaven , David R. Brownbridge , Richard P. Hopkins, Data-Driven and Demand-Driven Computer Architecture, ACM Computing Surveys (CSUR), v.14 n.1, p.93-143, March 1982 [doi>10.1145/356869.356873]
• 75: Rex Vedder , Dennis Finn, The Hughes Data Flow Multiprocessor: architecture for efficient signal and data processing, Proceedings of the 12th annual international symposium on Computer architecture, p.324-332, June 17-19, 1985, Boston, Massachusetts, United States
• 76: VEEN, A. H. 1980. Data flow computers. In Colloquium Hogere Programmeertalen en Computerarchitectuur-Syllabus 45, P. Klint, Ed. Centre for Mathematics and Computer Science, Amsterdam, pp. 99-132 (in Dutch).
• 77: VEEN, A. H. 1981. A formal model for data flow programs with token coloring. Tech. Rep. IW 179, Centre for Mathematics and Computer Science, Amsterdam.
• 78: A. H. Veen, The misconstrued semicolon: reconciling imperative languages and dataflow machines, Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands, 1986
• 79: VEEN, A. H. 1985b. Locality in the matching store. Internal report. Dept. of Computer Science, Victoria Univ. of Manchester, Manchester, England.
• 80: VEGDAHL, S. R. 1984. A survey of proposed architectures for the execution of functional languages. IEEE Trans. Comput. C-33, 12 (Dec.), 1050-1071.
• 81: WATSON, I., AND GURD, J. 1982. A practical data flow computer. Computer 15, 2 (Feb.) 51-57.
• 82: K. S. Weng, AN ABSTRACT IMPLEMENTATION FOR A GENERALIZED DATA FLOW LANGUAGE, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 83: Yoshinori Yamaguchi , Kenji Toda , Toshitsugu Yuba, A performance evaluation of a Lisp-based data-driven machine (EM-3), Proceedings of the 10th annual international symposium on Computer architecture, p.363-369, June 13-17, 1983, Stockholm, Sweden

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Performance