Optimization strategies of stack control

摘要

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, systemtables 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.