A recursive computer architecture for VLSI

ABSTRACT

We present a general-purpose computer architecture based on the concept of recursion, suitable for VLSI computer systems built from replicated (LEGO-like) computing elements. The recursive computer architecture is defined by presenting a program organisation, a machine organisation and an experimental machine implementation oriented to VLSI. The program organisation, called recursive control flow, attempts a synthesis of the concepts underlying traditional control flow, data flow and reduction, to exploit the individual strengths of each organisation. The machine organisation is based on replicated general-purpose computing elements, as well as special-purpose computing elements that allow the function of individual computer systems to be specialised. These elements are interconnected to form a larger computer system and cooperate in the concurrent execution of a program. The experimental implementation is being restricted to simple, identical microcomputers each containing a memory, a processor and a communications capability. This future generation of LEGO-like computer systems are termed fifth generation computers [1] by the Japanese.

REFERENCES

• 1: Anon: "Proc. Int. Conf. on Fifth-Generation Computers", Japan Information Processing Development Center, (October 1981).
• 2: Arvind et al: "A Processing Element for a Large Multiple Processor Dataflow Machine", Proc. Int. Conf. on Circuits and Computers, (October 1980).
• 3: 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]
• 4: Barton R.M.: UK Patent Specification 1 503 321-325.
• 5: K. J. Berkling, Reduction languages for reduction machines, Proceedings of the 2nd annual symposium on Computer architecture, p.133-140, January 20-22, 1975
• 6: Browning S.A. and Seitz C.L.: "Communication in a Tree Machine", Proc. Caltech Conf. on VLSI, (January 1981).
• 7: 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]
• 8: Dennis J. B.: "The Varieties of Data Flow Computers", Proc. First Int. Conf. on Distributed Computing Systems, (October 1979) pp. 430-439.
• 9: Alvin M. Despain , David A. Patterson, X-Tree: A tree structured multi-processor computer architecture, Proceedings of the 5th annual symposium on Computer architecture, p.144-151, April 03-05, 1978 [doi>10.1145/800094.803041]
• 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: Foster M.J. and Kung H.T.: "The Design of Special-Purpose VLSI Chips", IEEE Computer Magazine, (January 1980) pp. 26-40.
• 12: Glushkov V.M. et al: "Recursive Machines and Computing Technology", Proc. of the IFIP Congress, (1974), pp. 65-70.
• 13: Hopkins R.P. et al: "A Computer Supporting Data Flow, Control Flow and Updateable Memory", Computing Laboratory, The University of Newcastle upon Tyne, Technical Report 144, (1979).
• 14: Daniel H. H. Ingalls, The Smalltalk-76 programming system design and implementation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.9-16, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512762]
• 15: Johnson R.C.: "32-bit Microprocessors inherit mainframe features", Electronics, (February 1981) pp. 138-141.
• 16: Keller R. M., et al: "A Loosely-coupled Applicative Multi-processing System", Proc. Nat.Comp. Conf., (1978) pp. 861-870.
• 17: Mago G. A.: "A Network of R Microprocessors to Execute Reduction Languages", Int. Journ. of Computer and Information Sciences, vol. 8, no. 5 and vol. 8, no. 6, (1979).
• 18: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 19: Rivest R.L.: "A Description of a Single-Chip Implementation of the RSA Cipher", LAMBDA Magazine, vol. 4, (1980) pp. 14-18.
• 20: Seitz C.L.: "Proc. of the Caltech Conference on Very Large Scale Integration", (January 1979).
• 21: Simon H.: "The Architecture of Complexity", Proc. of the American Philosophical Society, vol. 1.
• 22: Sussman G.J. et al: "Scheme-79 - Lisp on a Chip", IEEE Computer Magazine, (July 1981) pp. 10-21.
• 23: Syre J. C. et al: "Pipelining, Parallelism and Asynchronism in the LAU System", Proc. 1977 Int. Conf. on Parallel Processing, (August 1977) pp. 87-92.
• 24: Treleaven P.C.: "Principal Components of a Data Flow Computer", Proc. 1978 Euromicro Symp., (October 1978) pp. 366-374.
• 25: Philip C. Treleaven , Geoffrey F. Mole, A multi-processor reduction machine for user-defined reduction languages., Proceedings of the 7th annual symposium on Computer Architecture, p.121-130, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801917]
• 26: Philip C. Treleaven, VLSI: machine architecture and very high level languages, ACM SIGARCH Computer Architecture News, v.8 n.7, p.27-38, October 1980 [doi>10.1145/641926.641931]
• 27: Philip C. Treleaven , Richard P. Hopkins, Decentralized computation, Proceedings of the 8th annual symposium on Computer Architecture, p.279-290, May 12-14, 1981, Minneapolis, Minnesota, United States
• 28: 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]
• 29: Treleaven P.C. "VLSI Processor Architectures", IEEE Computer Magazine (to be published).
• 30: Wilner W.T.: "Recursive Machine", Xerox Corporation's Palo Alto Research Centre, Internal Report, (1980).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Design