Optimization strategies of stack control

ABSTRACT

This paper concerns issues related to building mathematical models and optimal algorithms of stacks [1] control in single-and two-level memory. These models were constructed as 1, 2 and 3 dimensional random walks. In our opinion the algorithms, constructed for concrete data structure, will work better, than universal replacement algorithms in paging virtual and cache-memory. It was confirmed by the practice of construction of stack computers [1].Some scientists think, that non-Merkov model is more exact model of stacks behavior[12]. In [13] we have studied models, which include the possibility that, probabilities of the operations depend on the operations performed at the previous step. We can't include this models to the paper because of its small volume. On the other hand Ertl's finding concerns only particular application of stacks - stack caching for interpreters. It is very important, but there are many other applications of stacks. For example recursive algorithms, computer graphics, system tables and many other, when dynamic allocation of stacks after compilation(in the time of program running) it requires.This research work was supported by the Russian Foundation for Fundamental Research. grant 01-01-00113.

REFERENCES

• 1: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 2: S. Aviezri, Fraenkel. Paired sequential lists in a memory interval. Inform. Process Lett. (1979)8.9--10.
• 3: A. V. Sokolov, A. A. Lemetti. On the problem of optimal stack control. In: Probabilistic methods in discrete mathematics. Proceedings of the Fifth International Petrozavodsk Conference VSP. Utrecht. The Netherlands.(2002). p.351--366.
• 4: Philip J.Koopman.Jr. Stack Computers. Ellis Horwood. 1989. URL: http://www.cs.cmu.edu/~koopman/strack_computers/
• 5: T. J. Stanley , R. G. Wedig, A performance analysis of automatically managed top of stack buffers, Proceedings of the 14th annual international symposium on Computer architecture, p.272-281, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30381]
• 6: Y. Tamir, C. Sequin. Strategies of controll register's file. IEEE Trans. Comput. c-32(11), 1983.p.977.
• 7: David A. Patterson , Carlo H. Sequin, RISC I: A Reduced Instruction Set VLSI Computer, Proceedings of the 8th annual symposium on Computer Architecture, p.443-457, May 12-14, 1981, Minneapolis, Minnesota, United States
• 8: M.G.H. Katevanis, C. H. Sequin,D. A. Patterson,R.W.Sherburne.Jr.RISC:Effective Archiectures for VLSI Computer. In:VLSI Electronics. Microstructure Science. V. 14 Edited by Norman G. Einspruch.1986.
• 9: V. Mazalov, A.Sokolov About optimal dynamic storage allocation. In: Controll in dynamic systems. Leningrad.1979. (in Russion).
• 10: T. Kohonen, Contentaddressable Memories, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 11: Makoto Hasegawa , Yoshiharu Shigei, High-speed top-of-stack scheme for VLSI processor: a management algorithm and its analysis, Proceedings of the 12th annual international symposium on Computer architecture, p.48-54, June 17-19, 1985, Boston, Massachusetts, United States
• 12: M. Anton Ertl, Stack caching for interpreters, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.315-327, June 18-21, 1995, La Jolla, California, United States
• 13: A.V. Sokolov. Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control. Petrozavodsk University Press. 2002. (in Russion).
• 14: A. Sokolov. About storage allocation for implementing two stacks. In: Automation of experiment and data processing. Petrozavodsk. 1980. P.65--71. (in Russian).
• 15: Andrew V. Sokolov, Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control, Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, p.416-419, August 22-24, 2001
• 16: A. C. Yao. An analysis of a memory allocation scheme for implementating stacks. SIAM J. Computing. (1981)10.398--403.
• 17: P Flajolet, The evolution of two stacks in bounded space and random walks in a triangle, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, p.325-340, June 1986, Bratislava, Czechoslovakia
• 18: G. Louchard , R. Schott , M. Tolley , P. Zimmermann, Random walks, heat equation and distributed algorithms, Journal of Computational and Applied Mathematics, v.53 n.2, p.243-274, Aug. 19, 1994 [doi>10.1016/0377-0427(94)90048-5]
• 19: David R. Ditzel , H. R. McLellan, Register allocation for free: The C machine stack cache, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.48-56, March 01-03, 1982, Palo Alto, California, United States

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms, Documentation, Theory