The design of an emulator for a parallel machine language

ABSTRACT

A paradigm is developed for structuring a complex emulator operating in a parallel hardware environment. This paradigm is based on the view that a complex emulator is best structured as of a set of microprocesses, each performing a small independent task, that interact in a closely-coupled manner. This is in contrast to the conventional method of structuring an emulator as a set of subroutines with a sequential flow of control among them. The design of an emulator for a parallel machine language (i.e. Adam's Graph Machine Language) using the new paradigm is discussed in detail, including the dynamic execution characteristics of the emulator in a parallel hardware environment. The analysis indicates that, given an appropriate microcomputer architecture, this structuring allows an emulator for a parallel machine language to be naturally and compactly coded and to fully map parallelism at the emulated machine language level into parallelism at the hardware level. In particular, it has been shown that an emulator can be structured so as to utilize well more than sixteen identical microprocessors. In addition, the emulator uses the idea of tailoring an emulator's control structure both to the emulated machine language and dynamically to the specific program being emulated.

REFERENCES

• 1: Duane Albert Adams, A computation model with data flow sequencing, 1969
• 2: D.W. Anderson et al, "The IBM System/360 Model 91: Machine Philosophy and Instruction-Handling", IBM Systems Journal, Vol. 11, No. 3, January 1967, pp. 8-23.
• 3: C.G. Bell and A. Newell, "The PMS and ISP Descriptive System for Computer Structure", in 1970 Spring Joint Comput. Conf., AFIPS Conf. Proc., Vol. 22, Montvale, N.J.: AFIPS Press, 1970, pp. 657-676.
• 4: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 5: Andrei P. Ershov, Parallel programming, Stanford University, Stanford, CA, 1971
• 6: R.M. Karp and R.E. Miller, "Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing", SIAM J. Appl. Meth. 14, November 1966.
• 7: Butler W. Lampson, A scheduling philosophy for multiprocessing systems, Communications of the ACM, v.11 n.5, p.347-360, May 1968 [doi>10.1145/363095.363144]
• 8: Victor Richard Lesser, Dynamic control structures and their use in emulation, 1973
• 9: V.R. Lesser, "An Introduction to the Direct Emulation of Control Structures by a Parallel Microcomputer", IEEE Tran. Comput., Vol. C-20, July 1971, pp. 751-763.
• 10: John William Mccredie, Jr., Analytic models of time-shared computing systems: new results, validations, and uses, 1972
• 11: W. McKeeman, "Language Directed Computer Design", in 1967 Fall Joint Comput. Conf., AFIPS Conf. Proc., Vol. 31, Washington, D.C.: Thompson, 1967, pp. 413-418.
• 12: Edward C. Nelson, Graph program simulation, Stanford University, Stanford, CA, 1970
• 13: E. Nelson, "Free Running and Resource Limited Graph Programs", (Ph.D. Thesis), Computer Science Department, Stanford University, September 1972.
• 14: R. Rice and W.R. Smith, "SYMBOL: A Major Departure from Classic Software Dominated von Neumann Computing Systems", in 1971 Spring Joint Comput. Conf., AFIPS Conf. Proc., Vol. 38, Montvale, N.J.: AFIPS Press, 1971, pp. 601-616.
• 15: J.E. Rodriquez, "A Graph Model for Parallel Computations", (Ph.D. Thesis), Mass. Institute of Technology, September 1967.
• 16: Robert F. Rosin, Contemporary Concepts of Microprogramming and Emulation, ACM Computing Surveys (CSUR), v.1 n.4, p.197-212, Dec. 1969 [doi>10.1145/356556.356559]
• 17: J.E. Thornton, "Parallel Operation in the Control Data 6600", in 1964 Fall Joint Comput. Conf., AFIPS Conf. Proc., Pt. II, Vol. 26, Washington, D.C.: Spartan Books, 1964, pp. 33-40.
• 18: S. G. Tucker, Emulation of large systems, Communications of the ACM, v.8 n.12, p.753-761, Dec. 1965 [doi>10.1145/365691.365931]
• 19: W.T. Wilner, "Design of the B1700", Burroughs Corporations, Santa Barbara Plant, Goleta, Calif., May 1972.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Design, Languages