Geodesic
Optimal management of two parallel stacks in two-level memory
Diskretnaya Matematika, Tome 19 (2007) no. 1, pp. 67-75.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the problem to manage two stacks in two-level memory. It is assumed that the tops of the stacks grow towards one another in the fast memory to which several processors are allowed to have simultaneous access, and the size of the stacks exceeds that of the fast memory. The fast memory stores the tops of the stacks only, while the remaining parts are stored in the second level memory. If the top of one of the stacks becomes empty or the stacks fill all the fast memory, that is, the stack overflow occurs, then a swapping to the second level memory is performed in such a way that each time a certain state of the memory is set and the next step starts. We study how to choose such a state of the memory in order to maximise the average time before the next swapping to the second level memory. 
@article{DM_2007_19_1_a8,
     author = {E. A. Aksenova and A. V. Sokolov},
     title = {Optimal management of two parallel stacks in two-level memory},
     journal = {Diskretnaya Matematika},
     pages = {67--75},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_1_a8/}
}
TY  - JOUR
AU  - E. A. Aksenova
AU  - A. V. Sokolov
TI  - Optimal management of two parallel stacks in two-level memory
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 67
EP  - 75
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_1_a8/
LA  - ru
ID  - DM_2007_19_1_a8
ER  - 
%0 Journal Article
%A E. A. Aksenova
%A A. V. Sokolov
%T Optimal management of two parallel stacks in two-level memory
%J Diskretnaya Matematika
%D 2007
%P 67-75
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_1_a8/
%G ru
%F DM_2007_19_1_a8
E. A. Aksenova; A. V. Sokolov. Optimal management of two parallel stacks in two-level memory. Diskretnaya Matematika, Tome 19 (2007) no. 1, pp. 67-75. http://geodesic.mathdoc.fr/item/DM_2007_19_1_a8/

[1] Knut D., Iskusstvo programmirovaniya, t. 1: Osnovnye algoritmy, Vilyams, Moskva, 2000

[2] Koopman P., Stack computers, Ellis Horwood, Chichester, 1989

[3] Katevanis M. G. Kh., Sekuin K. Kh., Patterson D. A., Sherburn R. U., Effektivnye arkhitektury dlya SBIS-kompyuterov. Elektronika SBIS. Proektirovanie mikrostruktur, Mir, Moskva, 1989

[4] Stanley T., Wedig R., “A performance analysis of automatically managed top of stack buffers”, Proc. 14th Annual International Symposium on Computer Architecture, IEEE Computer Society Press, Pittsburgh, 1987, 272–281

[5] Sokolov A. V., Matematicheskie modeli i algoritmy optimalnogo upravleniya dinamicheskimi strukturami dannykh, Izd-vo Petrozavodskogo gosuniversiteta, Petrozavodsk, 2002

[6] Sokolov A. V., O raspredelenii pamyati dlya dvukh stekov. Avtomatizatsiya eksperimenta i obrabotki dannykh, KF AN SSSR, Petrozavodsk, 1980

[7] Yao A. C., “An analysis of a memory allocation scheme for implementing stacks”, SIAM J. Comput., 10 (1981), 398–403 | DOI | MR | Zbl

[8] Flajolet P., “The evolution of two stacks in bounded space and random wolks in a triangle”, Lecture Notes Computer Sci., 223 (1986), 325–340 | DOI | MR

[9] Louchard G., Schott R., “Probabilistic analysis of some distributed algorithms”, Lecture Notes Computer Sci., 431 (1990), 239–253 | MR | Zbl

[10] Louchard G., Schott R., Tolly M., Zimmermann P., “Random walks, heat equation and distributed algorithms”, J. Comput. Appl. Math., 53 (1994), 243–274 | DOI | MR | Zbl

[11] Maier R. S., “Colliding stacks: a large deviation analysis”, Random Structures and Algorithms, 2 (1991), 379–421 | MR

[12] Sokolov A. V., “Mathematical models and optimal algorithms of dynamic data structure control”, Lecture Notes Computer Sci., 2138 (2001), 416–419 | DOI | Zbl

[13] Aksenova E. A., Volkova O. V., Lazutina A. A., Sokolov A. V., “Metody optimalnogo upravleniya stekami v dvukhurovnevoi pamyati”, Trudy IPMI KarNTs RAN, 3 (2002), 127–152 | Zbl

[14] Sokolov A. V., “Optimization strategies of stack control”, Recent Advances in Java Technology. Theory, Application, Implementation, Computer Sci. Press, Trinity College, Dublin, 193–203

[15] Kemeni Dzh., Snell Dzh., Konechnye tsepi Markova, Nauka, Moskva, 1970