A multi-processor reduction machine for user-defined reduction languages.

ABSTRACT

The design of a multi-processor reduction machine, supporting a class of user-defined reduction languages, is presented. A reduction machine is based on a “by need” or demand driven model of computation in which an instruction is executed only when a result it generates is requested. In such a machine, an instruction is a (variable length and possibly nested) expression and the machine language is referred to as a reduction language. In the multi-processor reduction machine presented, the asynchronous operation of a processor is controlled by a swappable, user-defined, state transition table. Each table supports a particular reduction language. To ensure the harmonious operation of the processors a state transition table is generated automatically for a user, in a similar way that a parser generator is used to generate table driven parsers.

REFERENCES

• 1: E.I. Organick, "New Directions in Computer Systems Architecture". Euromicro Journal, Vol. 5, No. 4 (July 1979), pp. 190-202.
• 2: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 3: W. Wilner, "Recursive Machines". Xerox PARC, SSL Internal Memorandum (January 1978).
• 4: P.C. Treleaven, "Exploiting Program Concurrency in Computing Systems". IEEE Computer, Vol. 12, No. 1 (January 1979) pp.42-50.
• 5: Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, ACM SIGARCH Computer Architecture News, v.3 n.4, p.126-132, December 1974
• 6: J.C. Syre, et al, "Pipelining, Parallelism and Asynchronism in the LAU System". Proc. 1977 Int. Conf. on Parallel Processing (1977) pp.87-92.
• 7: Arvind and K.P. Gostelow, "A Computer Capable of Exchanging Processors for Time". Proc. IFIP Congress (1977) pp.849-853.
• 8: P.C. Treleaven, "Principal Components of a Data Flow Computer". Proc. 1978 Euromicro Symp. (1978) pp.366-374.
• 9: A. L. Davis, The architecture and system method of DDM1: A recursively structured Data Driven Machine, Proceedings of the 5th annual symposium on Computer architecture, p.210-215, April 03-05, 1978 [doi>10.1145/800094.803050]
• 10: Edward P. Farrell , Noordin Ghani , Philip C. Treleaven, A concurrent computer architecture and a ring based implementation, Proceedings of the 6th annual symposium on Computer architecture, p.1-11, April 23-25, 1979 [doi>10.1145/800090.802887]
• 11: R.P. Hopkins, P.W. Rautenbach and P.C. Treleaven, "A Computer Supporting Data Flow, Control Flow and Updateable Memory". Tech. Report 144, Computing Laboratory, University of Newcastle upon Tyne (September 1979).
• 12: K. J. Berkling, Reduction languages for reduction machines, Proceedings of the 2nd annual symposium on Computer architecture, p.133-140, January 20-22, 1975
• 13: W.E. Kluge, "The Architecture of a Reduction Language Machine Hardware Model". Tech. Report ISF-Report 79.03, Gesellschaft fur Mathematik und Datenverarbeitung MBH Bonn (August 1979).
• 14: G.A. Mago, "A Network of Microprocessors to Execute Reduction Languages". Int. Journ. of Computer and Information Sciences, Vol. 8, No. 5 and Vol. 8, No. 6 (1979).
• 15: R.M. Keller, et al, "A Loosely-coupled Applicative Multi-processing System". AFIPS Conf. Proc. Vol. 48 (1979) pp. 861-870.
• 16: S.S. Patil and T.A. Welch, "A Programmable Logic Approach for VLSI". IEEE Trans. on Computers, Vol. C-28, No. 9 (September 1979) pp.594-601.
• 17: J. Backus, "Reduction Languages and Variable Free Programming". IBM Research, RJ 1010 (April 1972).
• 18: J. Backus, "Programming Languages and Closed Applicative Languages". IBM Research RJ 1245 (July 1973).
• 19: Elliott Irving Organick, Interpreting machines: Architecture and programming of the B1700/B1800 series (Operating and programming systems series), North-Holland, 1978
• 20: G.F. Mole, "A Multi-processor Reduction Machine for executing User-defined Reduction Languages". M.Sc. Dissertation, University of Newcastle upon Tyne (submitted).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Macro and assembly languages

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: User-centered design

General Terms:
Design, Languages