Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The execution of a program on a processor is viewed as a representation of that program going through a sequence of states. Each state change is manifested by the execution of a single instruction. Models that depend on this perspective are presented. The first is a static model of a description of a procedural computation. This model formalizes the description of the information in an executable module. Following this dynamic model of a procedural computation is given. This second model describes how a computation transitions from state to state and how the states of a computation are represented. Next, the state of a procedural computation is defined at certain well-defined points in its progression. These points represent potential points of correspondence to another instance of the computation. Then, the equivalence of these well-defined computation states is described. This refinement eliminates the nonmatching potential correspondences. The remaining points describe where the two computations are in the same state. These are precisely the points of equivalence of procedural computations. This final model of pointwise equivalence can be applied to the problem of migrating a computation from one processor to another (possibly architecturally dissimilar) processor.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: ATTARDZ, G., BALDY, A., BONI, U., CARIGNANI, F., COZ~I, G., PhiL, A., DUROCH~R, E., FILOTTI, I., QUNG, W., HUNTBR, M., MARKS, J., RICHARDSON, C., AND WATSON, A. 1988. Techniques for dynamic software migration. In Proceedings oj the 5th Annual Esprit Conference. North-Holland, Amsterdam, 475-491.
• 3: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 4: CHERITON, D. R. 1984. The v kernel: A software base for distributed systems. IEEE Soflw. 1, 2 (Apr.), 19-42.
• 5: David Cheriton, The V distributed system, Communications of the ACM, v.31 n.3, p.314-333, March 1988 [doi>10.1145/42392.42400]
• 6: DUBACH, F. B. 1990. Code-point and data mapping in dynamic native-code cross-architectural process ndgration. M.S. thesis, Univ. of Colorado at Colorado Springs, Colorado Springs, Colorado.
• 7: F. B. Dubach , C. M. Shub, Process-originated migration in a heterogeneous environment, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.98-102, February 21-23, 1989, Louisville, Kentucky [doi>10.1145/75427.75437]
• 8: Joseph R. Falcone, A programmable interface language for heterogeneous distributed systems, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.330-351, Nov. 1987 [doi>10.1145/29868.29870]
• 9: HOLLANDER, Y. AND SILBERMAN, G. 1987. A mechanism for the migration of tasks in heterogeneous d~strlbuted processing systems. In Internai~onal Conference on Parallel Processing and Applications. North-Holland, Amsterdam, 93-98.
• 10: Gerald Q. Maguire, Jr. , Jonathan M. Smith, Process migration: effects on scientific computation, ACM SIGPLAN Notices, v.23 n.3, p.102-106, March 1988 [doi>10.1145/43895.43906]
• 11: SHARP, S. E. 1989. Register mismatch in heterogeneous process originated migration. UCCS CS-650 Proj. Rep, Univ. of Colorado at Colorado Springs, Colorado Springs, Colorado.
• 12: Charles M. Shub, Native code process-originated migration in a heterogeneous environment, Proceedings of the 1990 ACM annual conference on Cooperation, p.266-270, February 20-22, 1990, Washington, D.C., United States [doi>10.1145/100348.100389]
• 13: Jonathan M. Smith, A survey of process migration mechanisms, ACM SIGOPS Operating Systems Review, v.22 n.3, p.28-40, July 1988 [doi>10.1145/47671.47673]
• 14: Marvin M. Theimer, Preemptable remote execution facilities for loosely-coupled distributed systems (migration, transparency, scheduling), 1986
• 15: THBIMBR, M. M. AND HAYES, B. 1992. Heterogeneous migration by recompilation. Tech. Rep. CSL-92-3 (Mar.), Xerox Corporation, Palo Alto, CIMf.
• 16: Marvin M. Theimer , Keith A. Lantz , David R. Cheriton, Preemptable remote execution facilities for the V-system, Proceedings of the tenth ACM symposium on Operating systems principles, p.2-12, December 1985, Orcas Island, Washington, United States [doi>10.1145/323647.323629]
• 17: VON BANK, D. G. 1990. Gnu c language system support for dynamic native code heterogeneous process-originated migration in the v system. M.S. thesis, Univ. of Colorado at Colorado Springs, Colorado Springs, Colorado.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Logics of programs

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Specification techniques

General Terms:
Design, Languages, Theory

Keywords:
dynamic migration, heterogeneous migration