On the Behaviours Produced by Instruction Sequences under Execution

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

Abstrakty

EN

We study several aspects of the behaviours produced by instruction sequences under execution in the setting of the algebraic theory of processes known as ACP. We use ACP to describe the behaviours produced by instruction sequences under execution and to describe two protocols implementing these behaviours in the case where the processing of instructions takes place remotely. We also show that all finite-state behaviours considered in ACP can be produced by instruction sequences under execution.

Słowa kluczowe

EN

instruction sequence; remote instruction processing; instruction sequence producible process

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 2
• Strony: 111--144
• Opis fizyczny: Bibliogr. 41 poz., tab.

Twórcy

autor

Bergstra J.A.

autor

Middelburg C.A.

• Informatics Institute, University of Amsterdam Science Park 904, 1098 XH Amsterdam, the Netherlands,

Bibliografia

• [1] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, Cambridge, 2009.
• [2] Baeten, J. C. M., Bergstra, J. A.: Process Algebra with Signals and Conditions, Programming and Mathematical Methods (M. Broy, Ed.), vol. F88 of NATO ASI Series, Springer-Verlag, 1992, 273-323.
• [3] Baeten, J. C. M., Weijland, W. P.: Process Algebra, vol. 18 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, Cambridge, 1990.
• [4] Baker, H. G.: Precise Instruction Scheduling without a Precise Machine Model, SIGARCH Computer Architecture News, 19(6), 1991, 4-8.
• [5] 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.), vol. 2719 of Lecture Notes in Computer Science, Springer-Verlag, 2003, 1-21.
• [6] Bergstra, J. A., Klop, J. W.: Process Algebra for Synchronous Communication, Information and Control, 60(1-3), 1984, 109-137.
• [7] Bergstra, J. A., Loots, M. E.: Program Algebra for Component Code, Formal Aspects of Computing, 12(1), 2000, 1-17.
• [8] Bergstra, J. A., Loots, M. E.: Program Algebra for Sequential Code, Journal of Logic and Algebraic Programming, 51(2), 2002, 125-156.
• [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.: Maurer Computers with Single-Thread Control, Fundamenta Informaticae, 80(4), 2007, 333-362.
• [11] Bergstra, J. A., Middelburg, C. A.: Instruction Sequences for the Production Of Processes, arXiv: 0811.0436v2 [cs.PL], November 2008.
• [12] Bergstra, J. A., Middelburg, C. A.: Program Algebra with a Jump-Shift Instruction, Journal of Applied Logic, 6(4), 2008, 553-563.
• [13] Bergstra, J. A., Middelburg, C. A.: A Protocol for Instruction Stream Processing, arXiv:0905.2257v1 [cs.PL], May 2009.
• [14] Bergstra, J. A., Middelburg, C. A.: Transmission Protocols for Instruction Streams, ICTAC 2009 (M. Leucker, C. Morgan, Eds.), vol. 5684 of Lecture Notes in Computer Science, Springer-Verlag, 2009, 127-139.
• [15] Bergstra, J. A., Middelburg, C. A.: Instruction Sequences and Non-uniform Complexity Theory, arXiv: 0809.0352v3 [cs.CC], July 2010.
• [16] Bergstra, J. A., Middelburg, C. A.: On the Operating Unit Size of Load/Store Architectures, Mathematical Structures in Computer Science, 20(3), 2010, 395-417.
• [17] Bergstra, J. A., Middelburg, C. A.: Indirect Jumps Improve Instruction Sequence Performance, arXiv: 0909.2089v2 [cs.PL], December 2011. To appear in Scientific Annals of Computer Science, 2012.
• [18] Bergstra, J. A., Middelburg, C. A.: Thread Extraction for Polyadic Instruction Sequences, Scientific Annals of Computer Science, 21(2), 2011, 283-310.
• [19] Bergstra, J. A., Middelburg, C. A.: Instruction Sequence Processing Operators, Acta Informatica, 49(3), 2012, 139-172.
• [20] Bergstra, J. A., Middelburg, C. A.: On the Expressiveness of Single-Pass Instruction Sequences, Theory of Computing Systems, 50(2), 2012, 313-328.
• [21] Bergstra, J. A., Ponse, A.: An Instruction Sequence Semigroup with Involutive Anti-Automorphisms, Scientific Annals of Computer Science, 19, 2009, 57-92.
• [22] Brock, C., Hunt, W. A.: Formally Specifying and Mechanically Verifying Programs for the Motorola Complex Arithmetic Processor DSP, ICCD '97, 1997, 31-36.
• [23] Brookes, S. D., Hoare, C. A. R., Roscoe, A. W.: A Theory of Communicating Sequential Processes, Journal of the ACM, 31(3), 1984, 560-599.
• [24] Fokkink, W. J.: Introduction to Process Algebra, Texts in Theoretical Computer Science, An EATCS Series, Springer-Verlag, Berlin, 2000.
• [25] Hennessy, J., Jouppi, N., Przybylski, S., Rowen, C., Gross, T., Baskett, F., Gill, J.: MIPS: A Microprocessor Architecture, MICRO '82, 1982, 17-22.
• [26] Hennessy, J. L., Patterson, D. A.: Computer Architecture: A Quantitative Approach, Third edition, Morgan Kaufmann, San Francisco, 2003.
• [27] Hennessy, M., Milner, R.: Algebraic Laws for Non-determinism and Concurrency, Journal of the ACM, 32(1), 1985, 137-161.
• [28] Hermes, H.: Enumerability, Decidability, Computability, Springer-Verlag, Berlin, 1965.
• [29] Hoare, C. A. R.: Communicating Sequential Processes, Prentice-Hall, Englewood Cliffs, 1985.
• [30] Lunde, A.: Empirical Evaluation of Some Features of Instruction Set Processor Architectures, Communications of the ACM, 20(3), 1977, 143-153.
• [31] Milner, R.: Communication and Concurrency, Prentice-Hall, Englewood Cliffs, 1989.
• [32] Mosses, P. D.: Formal Semantics of Programming Languages-An Overview, Electronic Notes in Theoretical Computer Science, 148, 2006, 41-73.
• [33] Nair, R., Hopkins, M. E.: Exploiting Instruction Level Parallelism in Processors by Caching Scheduled Groups, SIGARCH Computer Architecture News, 25(2), 1997, 13-25.
• [34] Ofelt, D., Hennessy, J. L.: Efficient Performance Prediction for Modern Microprocessors, SIGMETRICS '00, 2000, 229-239.
• [35] Patterson, D. A., Ditzel, D. R.: The Case for the Reduced Instruction Set Computer, SIGARCH Computer Architecture News, 8(6), 1980, 25-33.
• [36] Ponse, A., van der Zwaag, M. B.: An Introduction to Program and Thread Algebra, CiE 2006 (A. Beckmann, et al., Eds.), vol. 3988 of Lecture Notes in Computer Science, Springer-Verlag, 2006, 445-458.
• [37] Sannella, D., Tarlecki, A.: Algebraic Preliminaries, in: Algebraic Foundations of Systems Specification (E. Astesiano, H.-J. Kreowski, B. Krieg-Brückner, Eds.), Springer-Verlag, Berlin, 1999, 13-30.
• [38] Sipser, M.: Introduction to the Theory of Computation, Second edition, Thomson, Boston, MA, 2006.
• [39] Tennenhouse, D. L., Wetherall, D. J.: Towards an Active Network Architecture, SIGCOMM Computer Communication Review, 37(5), 2007, 81-94.
• [40] Wirsing, M.: Algebraic Specification, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Elsevier, Amsterdam, 1990, 675-788.
• [41] Xia, C., Torrellas, J.: Instruction Prefetching of Systems Codes with Layout Optimized for Reduced Cache Misses, ISCA '96, 1996, 271-282.