Manchester data-flow: a progress report

ABSTRACT

The Manchester Data-Flow Machine, MDFM, has evolved continuously during the past decade. By the time the prototype uniprocessor hardware system was decommissioned, in 1989, the putative multi-processor architecture comprised separate Processing Elements and Structure Store Units, together with a “global” Allocator and Throttle Unit, all linked by a packet-based Interconnection Switch. The decisions leading to this design are well documented in the literature, but some of the reasoning behind these decisions is now out-of-date. This paper looks afresh at the MDFM architecture, in the light of new hardware and software technology and the new state-of-the-art in data-flow computing, and derives an updated architecture, NMDFM, for a Manchester-style multi-processor system. The variable parameters of the NMDFM are investigated in an attempt to find an “optimum” set for future simulation studies.

REFERENCES

• 1: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• 2: Arvind, Brobst, S.A. and Maa, G.K., "Evaluation of the MIT Tagged-Token Dataflow Project", CSG Memo 281, Lab. for Comp. Sci., M1T, Dec. 1985.
• 3: Arvind , D. E. Culler, Managing resources in a parallel machine, Proc. of the IFIP TC 10 working conference on Fifth generation computer architectures, p.103-121, October 1986, Manchester, United Kingdom
• 4: Arvind and Gostelow, K.P., "Some Relationships between Asynchronous Interpreters of a Dataflow Language", in: Neuhold, E.J. (ed.), Formal Description of Programming Concepts, North Holland, 1978, pp. 95-119.
• 5: P M C C Barahona , J R Gurd, Processor allocation in a multi-ring dataflow machine, Journal of Parallel and Distributed Computing, v.3 n.3, p.308-327, Sept. 1986
• 6: B6hm, A.P.W. and Gurd, J.R., "Tools for Performance Evaluation of Parallel Machines", LNCS 297, 1988, pp. 212-229.
• 7: A. P. W. Böhm , J. R. Gurd, Iterative Instructions in the Manchester Dataflow Computer, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.129-139, April 1990 [doi>10.1109/71.80141]
• 8: A. P. Wim Böhm , J. Sargeant, Code Optimization for Tagged-Token Dataflow Machines, IEEE Transactions on Computers, v.38 n.1, p.4-14, January 1989 [doi>10.1109/12.8726]
• 9: BOhm, A.P.W. and Teo, Y.M., "The Heterogeneous Multi- Ring Dataflow Machine Simulator", Tech. Rep. UMCS-88- 6-3, Dept. Comp. Sci., Univ. Manchester, Jun. 1988.
• 10: A. P. W. Böhm , Y. M. Teo, Resource management in a multi-ring dataflow machine, Proceedings of the conference on CONPAR 88, p.566-577, October 1989, UMIST, Manchester, United Kingdom
• 11: B6hm, A.P.W. and Teo, Y.M., "Resource Management and Iterative Instructions", In: Gaudiot, J.L. and Bic, L., Advanced Topics in Data.Flow Computing, Prentice Hall, 1991, pp. 481-500.
• 12: Bowen, D.L., "Implementation of Data Structures in a Dataflow Computer", Ph.D. Thesis, Dept. Comp. Sci., Univ. Manchester, May 1981.
• 13: Cann, D.C. and Oldehoeft, R.R., "Reference Count and Copy Elimination for Parallel Applicative Computing", Tech. Rep. CS-888-129, Dept. Comp. Sci. Colorado State Univ., Nov. 1988.
• 14: Cann, D.C. and Oldehoeft, R.R., "High Performance }?arallel Applicative Computing", Tech. Rep. CS-89-104, Dept. Comp. Sci., Colorado State University, Feb. 1989.
• 15: Cann, D.C. (ed.), "SISAL" Draft Lang. ReL Manual, version 2.0, CRG, Lawrence Livermore Nat. Lab., 1991.
• 16: Crowley, W.P., Hendrickson, C.P. and Rudy, T.E,, "The SIM- PLE Code", Tech. Rep. UCID-17715, Lawrence Livermore Nat. Lab., 1978.
• 17: da Silva, J.G.D. and Woods, J.V., "Design of a Processing Subsystem for the Manchester Dataflow Computer", Proc. lEE 128E/5, 1981, pp. 218-224.
• 18: da Silva, J.G.D. and Watson, i., "A Pseudo-Associative Matching Store with Hardware Hashing", Proc. lEE }{30EI1, 1983, pp. 19-24.
• 19: Dent, D., "The ECMWF Model: Past, Present and Future", In: Hoffman, G.-R. and Snelling, D.F. (eds.), Multlprocesslng In Meteorological Models, Spdnger-Verlag, 1988, pp. 369-382.
• 20: Egan, G.K., "The CSIRC II Dataflow Computer: Token and Node Definitions", Tech. Rep. 31-001, Lab. for Concurrent Comp. Sys., School of Elec. Eng., Swinbome Institute of Technology, 1990.
• 21: Egan, G.K,, "The Delta Throttle", Tech. Rep. 31-0(}19, Lab. for Concurrent Comp. Sys., School of Elec. Eng., Swinborne Institute of Technology, 1990.
• 22: Fisher, J.A., "The VLIW Machine: A Multiproce,;sor for Compiling Scientific Code", IEEE Comp. 17/7, 1984, pp. 45- 53.
• 23: Foley, J.F., "Manchester Dataflow Machine: Benchmark Test Evaluation Report", Tech. Rep. UMCS-89-11-1, Dept. Comp. Sci., Univ. Manchester, Nov. 1989.
• 24: Glauert, J.R.W., "A Single-Assignment Language for Datafiow Computing", M.Sc. Thesis, Dept. Comp. Sci., Univ. Manchester, Jan. 1978.
• 25: Gottlieb, A., "An Outsider's View of Data-Flow", In: Gaudiot, J.L. and Bic, L., Advanced Topics in Data.Flow Computing, Prentice Hall, 1991, pp. 575-581.
• 26: Grafe, V., Hoch, J., Davidson, G., Holmes, V., Davenport, D. and Steele, K., "The Epsilon Project", in: Gaudiot, .I.L. and Bic, L., Advanced Topics In Data.Flow Computing, Prentice Hall, 1991, pp. 175-205.
• 27: Gurd, J.R. and BShm, A.P.W., "Implicit Parallel Processing: SISAL on the Manchester Dataflow Computer", In: ,Paul, G. and Almasi, G.S. (eds.), Parallel Systems and Computation, North Holland, 1988, pp. 179-204.
• 28: Gurd, J.R., BShm, A.P.W. and Kirkham, C.C., "The Manchester Dataflow Computing System", In: Dongarra, J.J. (ed.), Experimental Parallel Computing Architectures, North Holland, 1987, pp. 177-219.
• 29: J. Gurd , W. Bohm , Y. M. Teo, Performance issues in dataflow machines, Future Generation Computer Systems, v.3 n.4, p.285-297, Dec. 1987 [doi>10.1016/0167-739X(87)90033-1]
• 30: 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]
• 31: Gurd, J.R. and Treleaven, P.C., "A Highly Parallel Computer Architecture", Int. Rep., Dept. Comp. Sci., Univ. Manchester, Apr. 1976.
• 32: Gurd, J'.R. and Watson, I., "Data Driven System for High Speed Parallel Computing - Part 2", Comp. Design 9/7, 1980, pp. 97-106.
• 33: Gurd, J.R., Watson, I. and Glauert, J.R.W., "A MultJlayered Data-Flow Computer Architecture", Int. Rep., Dept. Comp. Sci., Univ. Manchester, Jan. 1978 (updated Jul. 1978 and Mar. 1980).
• 34: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 35: Iannueei, R.A., "A Dataflow/von Neumann Architecture", Tech. Rep. TR-418, LCS, MIT, May 1988.
• 36: Yasuhiro Inagami , John F. Foley, The specification of a new Manchester Dataflow machine, Proceedings of the 3rd international conference on Supercomputing, p.371-380, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318830]
• 37: K. Hawakami , J. R. Gurd, A scalable dataflow structure store, ACM SIGARCH Computer Architecture News, v.14 n.2, p.243-250, June 1986
• 38: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 39: McGraw, J.R., et al., "SISAL: Streams and Iteration in a Single-Assignment Language", Lang. Ref. Manual, version 1.2, Lawrence Livermore Nat. Lab. Jan. 1985.
• 40: O'Boyle, M,F.P., "Program and Data Transformations for Efficient Execution of Distributed Memory Architectures" Ph.D. Thesis, Dept. Comp. Sei., Univ. Manchester, May 1992,
• 41: Gregory M. Papadopoulos, Implementation of a general-purpose dataflow multiprocessor, MIT Press, Cambridge, MA, 1991
• 42: Carlos A. Ruggiero , John Sargeant, Control of parallelism in the Manchester Dataflow Machine, Proc. of a conference on Functional programming languages and computer architecture, p.1-15, October 1987, Portland, Oregon, United States
• 43: Sargeant, J., "Efficient Stored Data Structures for Dataflow Computing", Ph.D. Thesis UMCS-85-8-2, Dept. Comp. Sci., Univ. Manchester, Aug. 1985.
• 44: T. Shimada , K. Hiraki , K. Nishida , S. Sekiguchi, Evaluation of a prototype data flow processor of the SIGMA-1 for scientific computations, ACM SIGARCH Computer Architecture News, v.14 n.2, p.226-234, June 1986
• 45: Skedzielewski, S.K. and Glauert, J.R.W., "IFI: An Intermediate Form for Applicative Languages", Ref. Manual M-170, Lawrence Livermore Nat. Lab., Jul. 1985.
• 46: S. K. Skedzielewski , M. L. Welcome, Data flow graph optimization in ifi, Proc. of a conference on Functional programming languages and computer architecture, p.17-34, January 1985, Nancy, France
• 47: Snelling, D.F., "The Stateless Data-Flow Architecture", Ph.D. Thesis, Dept. Comp. Sci., Univ. Manchester, (in preparation).
• 48: Welcome. M.L.. Skedzielewski. S.K.. Yates. R.K. and Ranelletti, J.E., "IF2: An Applicative Language Intermediate Form with Explicit Memory Management", Ref. Manual M-195, Lawrence Livermore Nat. Lab., Dec. 1986.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  K. Computing Milieux
  K.2 HISTORY OF COMPUTING
      Subjects: Hardware

General Terms:
Design, Experimentation, Measurement, Performance