Maurer Computers with Single-Thread Control

• Autorzy: Bergstra J.A. , Middelburg C.A.
• Języki publikacji: EN

Abstrakty

EN

We investigate basic issues concerning stored threads and their execution, building upon Maurer's model for computers and the thread algebra of Bergstra et al. We show among other things that a single thread can control the execution on a Maurer machine of any executable finite-state thread stored in the memory of the Maurer machine. We also relate stored threads with programs as considered in the program algebra of Bergstra et al. The work is intended as a preparation for the development of a formal approach to model micro-architectures and to verify their correctness and anticipated speed-up results.

Słowa kluczowe

EN

Maurer computer; thread algebra; stored thread; execution; control thread; program algebra

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 4
• Strony: 333--362
• Opis fizyczny: bibliogr. 22 poz., tab.

Twórcy

autor

Bergstra J.A.

autor

Middelburg C.A.

• Programming Research Group University of Amsterdam, P.O. Box 41882, 1009 DB Amsterdam, the Netherlands,

Bibliografia

• [1] Aceto, L., Fokkink,W. J., Verhoef, C.: Structural Operational Semantics, in: Handbook of Process Algebra (J. A. Bergstra, A. Ponse, S. A. Smolka, Eds.), Elsevier, Amsterdam, 2001, 197-292.
• [2] Baeten, J. C. M., Weijland, W. P.: Process Algebra, vol. 18 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, Cambridge, 1990.
• [3] Bergstra, J. A., Bethke, I.: Polarized Process Algebra and Program Equivalence, Proceedings 30th ICALP (J. C. M. Baeten, J. K. Lenstra, J. Parrow, G. J. Woeginger, Eds.), LNCS 2719, Springer-Verlag, 2003, 1-21.
• [4] Bergstra, J. A., Bethke, I., Ponse, A.: Decision Problems for Pushdown Threads, Report PRG0502, Programming Research Group, University of Amsterdam, 2005.
• [5] Bergstra, J. A., Klop, J. W.: Process Algebra: Specification and Verification in Bisimulation Semantics, Proceedings Mathematics and Computer Science II (M. Hazewinkel, J. K. Lenstra, L. G. L. T. Meertens, Eds.), CWI Monograph 4, North-Holland, 1986, 61-94.
• [6] Bergstra, J. A., Loots, M. E.: Program Algebra for Sequential Code, Journal of Logic and Algebraic Programming, 51(2), 2002, 125-156.
• [7] Bergstra, J. A., Middelburg, C. A.: A Thread Algebra with Multi-Level Strategic Interleaving, CiE 2005 (S. B. Cooper, B. L¨owe, L. Torenvliet, Eds.), LNCS 3526, Springer-Verlag, 2005, 35-48.
• [8] Bergstra, J. A., Middelburg, C. A.: Maurer Computers for Pipelined Instruction Processing, Computer Science Report 06-12, Department ofMathematics and Computer Science, EindhovenUniversity of Technology, March 2006.
• [9] Bergstra, J. A., Middelburg, C. A.: Splitting Bisimulations and Retrospective Conditions, Information and Computation, 204(7), 2006, 1083-1138.
• [10] Bergstra, J. A., Middelburg, C. A.: Synchronous Cooperation for Explicit Multi-Threading, Computer Science Report 06-29, Department ofMathematics and Computer Science, EindhovenUniversity of Technology, September 2006.
• [11] Bergstra, J. A., Middelburg, C. A.: Thread Algebra with Multi-Level Strategies, Fundamenta Informaticae, 71(2/3), 2006, 153-182.
• [12] Bergstra, J. A., Middelburg, C. A.: Simulating Turing Machines on Maurer Machines. To appear in Journal of Applied Logic, 2007. Preliminary version: Computer Science Report 05-28, Department of Mathematics and Computer Science, Eindhoven University of Technology.
• [13] Bergstra, J. A., Middelburg, C. A.: Thread algebra for strategic interleaving. To appear in Formal Aspects of Computing, 2007. Preliminary version: Computer Science Report 04-35, Department of Mathematics and Computer Science, Eindhoven University of Technology.
• [14] Bergstra, J. A., Ponse, A.: Combining Programs and State Machines, Journal of Logic and Algebraic Programming, 51(2), 2002, 175-192.
• [15] Bolychevsky, A., Jesshope, C. R., Muchnick, V.: Dynamic Scheduling in RISC Architectures, IEE Proceedings Computers and Digital Techniques, 143(5), 1996, 309-317.
• [16] Hoare, C. A. R.: Communicating Sequential Processes, Prentice-Hall, Englewood Cliffs, 1985.
• [17] Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Second edition, Addison-Wesley, Reading, MA, 2001.
• [18] Jesshope, C. R., Luo, B.: Micro-threading: A New Approach to Future RISC, Australian Computer Architecture Conference 2000, IEEE Computer Society Press, 2000, 34-41.
• [19] Maurer,W. D.: A Theory of Computer Instructions, Journal of the ACM, 13(2), 1966, 226-235.
• [20] Maurer,W. D.: A Theory of Computer Instructions, Science of Computer Programming, 60, 2006, 244-273.
• [21] Middelburg, C. A.: An Alternative Formulation of Operational Conservativity with Binding Terms, Journal of Logic and Algebraic Programming, 55(1/2), 2003, 1-19.
• [22] Milner, R.: Communication and Concurrency, Prentice-Hall, Englewood Cliffs, 1989.