Разработка и анализ математических моделей и алгоритмов динамического распределения памяти в задачах управления стеками тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Лазутина, Анна Александровна

• Лазутина, Анна Александровна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Лазутина, Анна Александровна

Введение

1 Оптимальное управление тремя стеками в памяти одного уровня

1.1 Постановка задачи.

1.2 Последовательное представление.

1.3 Представление трех стеков, как четырех

1.3.1 Математическая модель и матрица вероятностей переходов

1.3.2 Результаты численных экспериментов.

1.4 Связанное представление.

1.4.1 Математическая модель и матрица вероятностей переходов

1.4.2 Результаты численных экспериментов.

1.4.3 Сравнение связанного и последовательного представлений

1.4.4 Случай, когда размер информационной части произвольный

1.5 Страничное представление

1.5.1 Оптимальный размер страницы.

1.5.2 Математическая модель.

1.5.3 Результаты численных экспериментов.

Введение диссертации (часть автореферата) на тему «Разработка и анализ математических моделей и алгоритмов динамического распределения памяти в задачах управления стеками»

В настоящее время вычислительная техника развивается весьма стремительными темпами. Однако, ее базовые понятия, сформированные на заре развития, актуальны до сих пор. К ним относятся, так называемые, структуры данных. Основными из них являются стеки, очереди и деки [14], [10], [31]:

• Стеком называется линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на одном конце, который называется вершиной стека. Другой по отношению к вершине конец стека будем называть началом стека.

• Очередью называется линейный список, в котором все включения делаются на одном конце, который называется концом очереди, а все исключения (и обычно всякий доступ) делаются на другом конце, который называется началом очереди.

• Деком называется линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах списка, которые называются левым и правым концами дека.

Наиболее часто используемой в вычислительной технике и программировании структурой данных является стек. Стеки широко используется при разработке программного и аппаратного обеспечения широкого класса задач.

В большинстве современных процессорах общего назначения, так или иначе, организована работа со стеком для выполнения операций, для передачи параметров процедурам и обращения к ним (Intel 8080 [9]; Intel 8085 [28]; Zilog Z80 [28]; Motorola 6800 [28]; Motorola 6809 [28]; Zilog Z8000 [25], [28]; Zilog Z8001 [25]; Zilog Z8003 [25]; Motorola 68000 [28]; Intel 432 [28]; HP 64000 [29]; VAX-11 [34]; Intel 80386 [35]; Intel 80286 [25]; Intel 8086 [16], [11], [28], [25]; Intel Pentium [16]; Intel Itanium [53], Эльбрус 1 и 2 [16], транспьютер фирмы INMOS Т 805 [16]).

Для работы со скалярными аргументами и локальными переменными процедур в первых RISC-процессорах [39], [38] организовывались перекрывающиеся окна регистров, связанные в кольцо. Для передачи параметров не требовалось перемещать данные, так как они находились в зоне пересечения окон регистров. По существу, в этом случае имеем один обычный стек с элементами типа покно"в главной памяти, несколько верхних элементов которого образуют циклический стек на регистрах. В архитектуре Intel Itanium [53] у каждой процедуры есть регистровый стек переменного размера для хранения параметров. Выходные параметры одной процедуры, являющиеся входными параметрами другой, перекрываются.

Самый распространенный способ представления стека — последовательное представление в виде одномерного массива. В этом случае для хранения стека достаточно иметь переменную, которая указывает на вершину стека.

Например, в системе VAX-11, процессорах Intel, Motorola и др., стек наращивается в сторону уменьшающихся значений адресов памяти. Это означает, что указателю позиции вершины того или иного стека первоначально присваивается значение самого старшего адреса области памяти, предоставляемой для организации данного [34], [28], [29].

В аппаратуре современных процессоров для того, чтобы стек отобразить на линейную виртуальную или физическую память, необходимо иметь, по крайней мере, два регистра. Один, указывающий на текущее состояние вершины стека — указатель стека, и второй, указывающий на основание стека в линейной памяти — база стека [16].

Не существует общепринятого подхода к реализации стека при разработке аппаратного обеспечения. Эта проблема наряду с задачей управления стеками исследуется довольно давно. Так в [12] рассматривались два варианта реализации стека: либо как часть основной оперативной памяти со своим особым механизмом формирования адресов, либо как отдельная сверхоперативная память с такой же организацией формирования адресов. Показаны недостатки каждой из реализации: в первом случае глубина стека может быть практически не ограничена, но такой способ приводит к недопустимо большому числу обращений к главной памяти; во втором случае возможности машины в части сложности арифметических выражений, которые могут быть вычислены с ее помощью, тем больше, чем больше глубина стека, однако тем большее время будет занимать при прерываниях программ переписывание данных стека. Компромиссное решение: можно несколько верхних ячеек стека располагать в сверхоперативной памяти. Однако, если количество регистров велико, то возникает сложность передачи данных при прерываниях. Если же таких регистров мало, то количество обращений к оперативной памяти при работе со стеком по-прежнему велико.

То есть в то время не предполагалось как-то управлять процессом переполнения или опустошения верхушки стека.

В стековых компьютерах в случае переполнения и опустошения верхушки стека возможны разные методы управления [43]:

1. Large Stack. Можно сделать стек большим и предполагать, что переполнения не будет, а если переполнение произойдет, то совершить аварийное завершение работы. Так сделано, например, в процессорах WISC CPU/16 с размером стека 256 элементов. Ясно, что, так как одно из основных приложений стековых компьютеров — это управление в реальном времени, такое решение чаще всего неприемлемо.

2. Demand fed single element stack manager. В этой стратегии верхушка стека реализована аппаратно, как циклический буфер, а продолжение стека находится в памяти. На каждый стек требуется три указателя — на верх и низ аппаратного стека и на верх продолжения стека в памяти. При переполнении и опустошении аппаратного стека всегда перемещается один элемент в память из буфера или наоборот. Метод реализован в FRISK 3.

3. Paging stack manager. В этом методе верхушка реализована программно как часть специальной памяти. При опустошении верхушки стека из памяти копируется половина буфера, а при переполнении нижняя половина буфера перемещается в память, а верхняя половина перемещается в начало буфера. Метод реализован в RTX200 и RTX32P.

4. An associative cache. Кэш-память для стековых машин не дает преимуществ по сравнению с рассмотренными методами, так как сложнее для аппаратной реализации и в то же время не учитывает специфики стека как структуры "LIFO". Хотя, если в стек нужно помещать структуры данных переменного размера, такие, как строки и структуры, использование кэшпамяти, как утверждается в работе, может быть целесообразно.

В [52] предполагается реализация стека, когда при переполнении и при опустошении быстрой вершины переносится к элементов стека. Вершина стека является продолжением стека, находящегося в памяти второго уровня.

В работах [23], [52] в качестве теоретической модели описывающей управление вершиной стека в двухуровневой памяти было предложено одномерное случайное блуждание [36]. В [33] в качестве модели рассматривалось блуждание, в котором вероятность включения элемента в стек р(х) это функция от длины стека х.

Однако некоторые специалисты [41] считают, что модель классического случайного блуждания недостаточно точно описывает поведение стеков, а более адекватной была бы модель, в которой вероятность следующей операции со стеком зависит от того, какая операция была предыдущей. Простейшая модель такого рода анализируется в [1], [7].

Помимо задачи управления вершиной стека, актуальной является задача управления несколькими стеками, а именно их оптимальное распределение в памяти и максимизация времени работы до переполнения или опустошения отведенной им памяти. Пусть в памяти одного уровня распределено несколько стеков. Переполнение — это ситуация, когда один из стеков переполнил отведенное, для него место и это значит, что произошла ошибка и один из вариантов возможного далее события — завершение работы программы. Также возможна обратная ситуация — исключение из пустого стека. Это, как правило, не является ошибкой. Такая ситуация может, например, интерпретироваться как переход на другую ветвь алгоритма программы.

Алгоритм Гаврика перераспределения памяти между стеками в случае переполнения одной из них предложен в [14]. В этом алгоритме при переполнеиии одного из стеков производится перераспределение памяти так, что приблизительно 10 % распределяются ровно между стеками, а 90 % распределяются пропорционально росту размеров стеков с момента предыдущего перераспределения.

Д. Кнут поставил задачу разработать математическую модель процесса распределения памяти для двух стеков, растущих навстречу друг другу и установить вид функции математического ожидания М(т,р), где т -это размер памяти для двух стеков, р — вероятность исключения из одного из стеков. М(т,р) — математическое ожидание случайной величины тах(к 1, к2), где к\ и ^ — длины стеков при встрече. Для безотказной работы в случае раздельного хранения двух стеков потребовалось бы 2тах(к\, к2) единиц памяти, в то время как для стеков, направленных навстречу друг другу, нужно т = ki + к2 единиц памяти.

В работах [32], [54], [42], [44], [46], [45], [33] была построена математическая модель процесса в виде двумерного случайного блуждания в треугольной области с двумя отражающими экранами и одним поглощающим экраном.

Был предложен алгоритм вычисления М(т,р) для конечных значений т [32]. Для решения задачи использовалась теория поглощающих цепей Маркова.

Решалась задача исследования М(т,р) при т —» со для 0.25 < р < 0.5 [54].

В ряде работ [42], [44], [45] исследовалось асимптотическое поведение стеков при переполнении и времени работы до переполнения памяти для 0 < р > 0.25. Так же задача решалась для случая, когда вероятности включения и исключения информации зависят от размеров стеков[46].

Помимо аппаратного обеспечения понятие стека широко используется в программировании. В операционной системе Unix стек используется в подсистеме управления процессами [24]. Стеки имеют важное значение для исполняющей среды Лауа-программ: текущая Лауа-программа имеет свой собственный Java-стек, который используется для наблюдения за локальными переменными и прочей информацией [40]. Стеки используются в алгоритмах синтаксического разбора [26], для анализа скобочной структуры некоторого текста и вычисления выражений [17], в алгоритмах машинной графики [30], в алгоритмах поиска на графах [14], [15], в алгоритмах сортировки [31]. В современных языках программирования работа со стеком реализуется в виде специальных классов стандартных библиотек, например java.util.Stack в Java2 SDK [40] и stacks в STL (Standard Template Library) в С++ [37]. В языке PostScript реализован внутренний стек [31].

Последовательное представление стеков в программировании используется наряду со связанным представлением, когда стек рассматривается в виде одно-связанного списка: каждый узел содержит поле информации и поле связи, известен указатель на первый элемент [10], [14], [31].

Последовательное и связанное представление сравниваются с точки зрения программирования в [10], [14], [31].

В данной работе построены математические модели этих двух способов представления стеков и сравнение этих способов с точки зрения среднего времени работы до переполнения.

Существует большое количество устройств с ограниченными ресурсами памяти. Это мобильные устройства, встраевыемые системы, бортовые и промышленные компьютеры, системы реального времени, сетевые устройства • и т.д. В своей работе они активно используют стековую архитектуру. Поэтому для подобных устройств актуально не только грамотное управление памятью как таковой, но и управление конкретными структурами данных, в частности, стеками. Это позволит повысить эффективность их работы и снизит затраты на производство.

В последнее время вычислительная техника достигла небывалых высот. Наряду с многопроцессорными системами широкое распространение получили системы, основанные на многоядерных процессорах. Это могут быть мощные вычислительные серверы со множеством процессоров и однопроцессорные персональные компьютеры [16]. В связи с этим особую актуальность приобрела задача исследования поведения стеков при параллельном выполнении операций. В работе построена модель поведения трех стеков в памяти одного уровня при наличии двух или трех процессоров.

В связи с вышеизложенным, построение математических моделей поведения одного или нескольких стеков в памяти одного или двух уровней, а также с учетом возможного параллельного выполнения операций, является важной и актуальной задачей.

Цель работы — построение математических моделей и алгоритмов оптимального управления стеками, с точки зрения максимизации среднего времени до переполнения одного из стеков в памяти одного уровня и максимизации среднего времени работы до перераспределения одного стека в памяти двух уровней.

На защиту выносятся следующие основные результаты:

1. Математические модели, описывающие поведение трех стеков в памяти одного уровня для следующих вариантов представления стеков: последовательное представление трех стеков как четырех, связанное, страничное представление.

2. Математические модели, описывающие поведение четырех стеков в памяти одного уровня для следующих способов представления стеков: последовательное, связанное, страничное представление.

3. Математические модели, описывающие поведение трех стеков в памяти одного уровня в случае параллельного выполнения операций для следующих способов представления стеков: последовательное, связанное, страничное представление.

4. Немарковская модель поведения одного стека в двухуровневой памяти в случае, когда вероятность операции, которая будет произведена со стеком на следующем шаге, зависит от того, какая операция была произведена на текущем шаге, для трех алгоритмов управления верхушкой стека.

5. Пакет программ, реализующий рассмотренные в работе математические модели. Для заданного размера памяти и заданных наборов вероятностей вычисляется среднее время работы до переполнения или перераспределения, находится оптимальное разбиение памяти для последовательных способов. Пакет разработай на С++ для суперкомпьютера IBM pSeries690(Regatta), установленного на ВМК МГУ им. М.В. Ломоносова.

Научная новизна и практическая ценность. В работе предложены новые математические модели поведения трех и четырех стеков в памяти одного уровня, а также трех стеков в случае параллельного выполнения операций в памяти одного уровня. Получены выводы об эффективности основных способов представления стеков с точки зрения максимизации среднего времени работы, в предположении, что известны вероятностные характеристики стеков. Предложена новая математическая модель, описывающая поведение одного стека в двух уровневой памяти, когда вероятность операции, которая будет произведена со стеком на следующем шаге, зависит от того, какая операция была произведена на текущем шаге.

Разработан пакет программ, реализующий рассмотренные в работе математические модели.

Предложенные в работе алгоритмы могут быть использованы при разработке аппаратного и программного обеспечения ЭВМ со стековой организацией памяти и при реализации алгоритмов работы со стеками на обычных ЭВМ.

Апробация работы. Основные материалы диссертации представлялись на Пятом Международном Конгрессе по математическому моделированию (Дубна, 2002 г.); на V международной конференции "Дискретные модели в теории управляющих систем"(Ратмино, 2003 г.); на IV Всероссийском симпозиуме по прикладной и промышленной математике (Летняя сессия. Петрозаводск, июнь 2003 г.), (Осенняя сессия. Сочи, октябрь 2003 г.); на Первой Всероссийской научной конференции "Методы и средства обработки информации" (Москва, 2003 г.); на Шестой Международной Петрозаводской конференции "Вероятностные методы в дискретной математике"(Петрозаводск, 2004); на VII Международной конференции "Дискретные модели в теории управляющих систем "(Москва, 2006г.); на Российско-Скандинавском симпозиуме "Теория вероятностей и ее приложения "(Петрозаводск, 2006г.).

Работа поддержана грантами РФФИ №01-01-0113, №06-01-00303.

Публикация работ. Основные результаты диссертиции опубликованы в 8 статьях [1], [2], [3], [7], [22], [18], [19], [20] и 6 тезисах докладов [49], [4], [5], [6], [21], [50].

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Лазутина, Анна Александровна

Результаты работы программы показывают, что для заданного набора вероятностей среднее время работы в случае связанного представления меньше, чем в случае последовательного представления [33] и чем в случае представления трех стеков, как четырех (См. Таблицы 1.1,1.2).

1.4.3 Сравнение связанного и последовательного представлений

Сравним связанное представление со следующими вариантами последовательного представления (См. Таблицы 1.3, 1.4):

• последовательное в случае оптимального представления стеков (См. раздел 1.1);

• последовательное интуитивное представление, в котором память разделена поровну между стеками, т.е. двум стекам, растущим навстречу

9т друг другу отведено ^ единиц памяти, а третьему стеку, расположенному отдельно, отведено у ;

• представление трех стеков, как четырех в оптимальном случае (См. радел 2.2);

• интуитивное представление трех стеков, как четырех, в котором двум парам стеков, растущих навстречу друг другу отведено по j единиц памяти.

Заключение

В данной работе получены следующие основные результаты:

1. Математические модели, описывающие поведение трех стеков в памяти одного уровня для следующих вариантов представления стеков: последовательное представление трех стеков как четырех, связанное, страничное представление.

2. Математические модели, описывающие поведение четырех стеков в памяти одного уровня для следующих способов представления стеков: последовательное, связанное, страничное представление.

3. Математические модели, описывающие поведение трех стеков в памяти одного уровня в случае параллельного выполнения операций для следующих способов представления стеков: последовательное, связанное, страничное представление.

4. Немарковская модель поведения одного стека в двухуровневой памяти в случае, когда вероятность операции, которая будет произведена со стеком на следующем шаге, зависит от того, какая операция была произведена на текущем шаге, для трех алгоритмов управления верхушкой стека.

5. Пакет программ, реализующий рассмотренные в работе математические модели. Для заданного размера памяти и заданных наборов вероятностей вычисляется среднее время работы до переполнения или перераспределения, находится оптимальное разбиение памяти для последовательных способов.

Список литературы диссертационного исследования кандидат физико-математических наук Лазутина, Анна Александровна, 2006 год

1. Аксенова Е.А., Волкова О.В., Лазутина А.А., Соколов А.В. Методы оптимального управления стеками в двухуровневой памяти. Труды Института прикладных математических исследований КарНЦ РАН.2002. Вып.З. с.127-152.

2. Аксенова Е.А., Лазутина А.А., Соколов А.В. Об оптимальном распределении памяти для стеков. Обозрение прикладной и промышленной математики 2003 т. 10, в.1, с.86-87.

3. Аксенова Е.А., Лазутина А.А., Соколов А.В. Об оптимальных методах представления динамических структур данных. Обозрение прикладной и промышленной математики 2003 т. 10, в.2, с.375-376.

4. Аксенова Е.А., Лазутина А.А., Соколов А.В. Анализ методов представления динамических структур данных. Обозрение прикладной и промышленной математики 2004 т. И, в.2, с.233-234.

5. Аксенова Е.А., Лазутина А.А., Соколов А.В. Исследование немарковской модели управления стеком в двухуровневой памяти. Программирование, 2004, №1, с.37-46.

6. Алгол 68. Методы реализации. Под. ред. Г.С. Цейтина. Издательство Ленинградского университета. Ленинград 1976.

7. Брусенцов Н.П. Микрокомпьютеры.-М.: Наука. Гл.ред.физ.-мат.лит.,1985.-208 с.

8. Гудрич М.Т., Тамассия Р. Структуры данных и алгоритмы в Java. Пер. с англ. Чернухо А.М.-Мн.:Новое знание,2003.-671с.

9. Исада X. Программирование для микрокомпьютеров: Пер с яп. М.: Мир, 1988.- 224 с.

10. Карцев М.А. Архитектура цифровых вычислительных машин. Главная редакция физико-математической литературы, М., Наука, 1978, 296 с.

11. Кемени Дою., Сиелл Дж. Конечные цепи Маркова. М:Наука, 1970.

12. Кнут Д. Искусство программирования для ЭВМ. Т.1. М.:Мир, 1976.

13. Кнут Д. Искусство программирования для ЭВМ. Т.З. М.:Мир, 1976.

14. Королев JI.H. Архитектура электронных вычислительных машин.-М.,Научный мир, 2005, 272 с.

15. Кубенский А.А. Создание и обработка структур данных в примерах на Лауа.-СПб.:БХВ-Петербург,2001.-336с.

16. Лазутина А.А. Оптимальное управление четырьмя стеками в памяти одного уровня. Труды Института прикладных математических исследований КарНЦ РАН. 2005. Вып.6. с.193-217.

17. Лазутина А.А. Оптимальное управление тремя стеками в памяти одного уровня в случае параллельного выполнения операций. Труды Института прикладных математических исследований КарНЦ РАН. 2006. Вып.7. с. 154-175.

18. Лазутина А.А., Соколов А.В. Оптимальное управление тремя стеками в памяти одного уровня. Информационные системы и технологии. МЛ (23) 2006. с. 152-158

19. Мазалов В. ВСоколов ■ А.В. Об оптимальном динамическом распределении нестраничной памяти. Управление в динамических системах. Л., 1979. Рукопись деп. в ВИНИТИ 24.07.1979.

20. Морис Дою. Бах. Архитектура операционной системы Unix. Нью-Джерси 1986. URL: http://rsusul.rnd.runet.ru/inix/bach/index.html

21. Морисита И. Аппаратные средства микроЭВМ: Пер. с яп.-М.:Мир, 1988.-280с.

22. Опалева Э.А., Самойленко В.П. Языки программирования и методы трансляции.- СПб.:БХВ-Петербург,2005.-480с.

23. Пратт Т., Языки программирования. Мир, 1979 г.

24. Рафикузамаи М. Микропроцессоры и машинное проектирование микропроцессорных систем: В 2-х кн. Кн. 1. Пер. с англ.-М.:Мир, 1988.-312с.

25. Рафикузаман М. Микропроцессоры и машинное проектирование микропроцессорных систем: В 2-х кн. Кн. 2. Пер. с англ.-М.:Мир, 1988.-288с.

26. Роджерс Д. Алгоритмические основы машинной графики. М.:Мир, 1989.

27. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ /Структуры данных /Сортировка/ Поиск: Пер. с англ./Роберт Седвик-К.Издательство "ДиаСофт 2001.-688с.

28. Соколов А.В. О распределении памяти для двух стеков// Автоматизация эксперимента и обработки данных. Петрозаводск, 1980. с. 65-71.

29. Соколов А.В. Математические модели и алгоритмы оптимального управления динамическими структурами данных./ПетрГУ. Петрозаводск, 2002. 216с.

30. Сибеста Р. Структурное программирование на языке ассемблера ЭВМ Vax-11: Пер. с англ.-М.:Мир,1988.-536с.

31. Смит Б.Э., Джонсон М.Т. Архитектура и программирование микропроцессора INTEL 80386. Пер. с англ. Григорьева В.JI.-M.:Конкорд, 1992.-334с.

32. Феллер В. Введение в теорию вероятностей и ее приложения. Мир,Москва,1964

33. Шилдт Г. Самоучитель С++, 3-е издание: пер. с англ.-СПб. :BHV-Санкт-Петербург, 1998.-688с.

34. Электроника СБИС. Проектирование микроструктур: Пер. с англ./ Под. ред. Айнспрука Н.-М.:Мир, 1989.-256с.

35. RISC: Эффективные архитектуры для СБИС-компьютеров. Электроника СБИС. Проектирование микроструктур./ Катеванис М.Г.Х., Се-куин К.Х., Паттерсон Д.А., Шербурн Р.У. М.:Мир, 1989.

36. Core Java 2. Volume II Advanced Features. Sun Microsystems, Inc.-USA, 2002.

37. Ertl Anton M. Stack caching for interpreters. SIGPLAN '95 Conf. Programm. Lang. Des. and Implem.(PLDI), 15 La Jolla,Calif,June 1821,1995.

38. Flajolet P. The evolution of two stacks in bounded space and random walks in a triangle// Lec. Notes Computer Sci. 1986. Vol.223, p.325-340.

39. Koopman P. Stack Computers. Ellis Horwood, 1989. URL: http://www.cs.cmu.edu/~koopman / stackcomputers /

40. Louchard G., Schott R. Probabilistic analysis of some distributed algorithms // Lect. Notes Computer Sci. 1990. № 431. p. 239-253.

41. Louchard G. Random walks, heat equation and distributed algorithms / G. Louchard, R. Schott, M. Tolley, P. Zimmermann //J. Comput. Appl. Math. 1994. № 53. p. 243-274.

42. Maier R. S. Colliding Stacks: A Large Deviations Analysis // Random Structures and Algorithms. 1991. № 2. p. 379-421.

43. Sokolov A.V. On the problem of optimal stack control in two level memory. In: Probabilistic methods in discrete mathematics. Proceedings of the Fourth International Petrozavodsk Conference VSP, Utrecht, The Netnerlands,( 1997 )349-351.

44. Sokolov A. V. Optimization strategies of stack control. Chapter 22. Recent Advances in Java Technology. Theory, Application, Implementation. Intermediate Reprezentation Engineering. Computer Science Press Trinity College Dublin 2002. P. 193-203.

45. Sokolov A.V., Aksenova E.A., Lazutina A.A., Tarasijuk A.V. Mathematical models of dynamic data structure. V international congress on mathematical modeling. Book of abstract, vol. II, JINR, Dubna 2002, p. 127.

46. Sokolov A. V., Aksenova E.A., Lazutina A.A., Tarasyuk A. V. Probability models and optimal algorithms of dynamic data structure control. Extended abstracts, PTAP, Petrozavodsk, 2006, p.57-58.

47. Sokolov A. V., Lemetti A.A. On the problem of optimal stack control. Probabilistic methods of discrete mathemetics: Proceedings of the Fifth International Conference. Utrecht, Netherlands: VSP, 2001. P.351-366.

48. Hasegava M., Shigei Y. High-speed top-of-stack scheme for VLSI processor: a management algorithm and its analysis // Proceedings of 12th Symposium on Computer Architecture. June. 1985. p. 48-54.

49. Yao A.C. An analysis of a memory allocation scheme for implementating stacks // SIAM J. Computing. 1981. №10. p. 398-403.