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

На правах рукописи

Лазутина Анна Александровна

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

ПЕТРОЗАВОДСК - 2006

Работа выполнена в Институте прикладных математических исследований Карельского научного центра РАН

Научный руководитель: кандидат физико-математических наук,

доцент Соколов Андрей Владимирович

Официальные оппоненты: доктор физико-математических наук,

профессор Морозов ЕвсеЙ Викторович

кандидат физико-математических наук Калегаев Владимир Владимирович

Ведущая организация: Томский государственный университет

01

час.

Защита диссертации состоится " . 2006г. в

на заседании диссертационного совета Д 212.190.03 в Петрозаводском государственном университете по адресу: 185910, Петрозаводск, пр. Ленина, д. 33.

С диссертацией можно ознакомиться в Научной библиотеке Петрозаводского государственного университета.

Автореферат разослан " УЮчК^лХ._2006г.

Ученый секретарь диссертационного совета У Поляков В. В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работц, В настоящее время вы числительная техника развивается весьма стремительными темпами. Однако, ее базовые понятия, сформированные на заре развития, актуальны до сих пор. К ним относятся, так называемые, структуры данных. Основными из них являются стеки, очереди н деки.

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

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

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

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

часть в памяти второго уровня.

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

Например, в стековых компьютерах в случае переполнения и опустошения верхушки стека были реализованы различные методы управления (Large Stack, Demand fed single element stack manager, Paging stack manager, An associative cache).

Существует ряд теоретических работ, направленных на реализацию таких алгоритмов (Мазалов В.В., Соколов A.B., 1979; Hasegava M.,Sliigei Y, 1985; Соколов A.B. 2002). В качестве математической модели описывающей управление вершипой стека в двухуровневой памяти было предложено одпомерпое случайное блуждание. Однако некоторые специалисты считают, что модель классического случайного блуждания недостаточно точно описывает поведение стеков, а более адекватной была бы модель, в которой вероятность следующей операции со стеком зависит от того, какая операция была предыдущей. Простейшая модель такого рода анализируется в работе.

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

Алгоритм Гаврика, решающий такую задачу, был описан Д.Кнутом. Одновременно им была поставлена задача разработать математическую модель процесса распределения памяти для двух стеков, растущих навстречу друг другу. В раде работ (Соколов A.B., 1980; Yao A.C., 1981; Flajolet P., 1986; Louchard G., Schott R., 1990; Maier R.S., 1991; Louchard G., 1994; Соколов A.B., 2002) была построена математическая модель процесса в виде двумерного случайного блуждания в треугольной области с двумя отражающими экранами и одним поглощающим экраном. В то же время актуальной осталась задача распределения памяти для

большего числа стеков.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикация работ. По теме диссертации опубликованы 8 статей, в том числе 2 статьи в журналах, входящих в список изданий рекомендованных ВАК, и 6 тезисов докладов.

Струргеура н рбъем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы, изложена на 146 страницах. Список литературы содержит 54 наименования.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В данной главе определяется какой из методов эффективнее в предположении, что известны некоторые вероятностные характеристики стеков. Критерий оптимальности — среднее время до переполнения памяти.

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

Первый способ — представление трех стеков, как четырех. В данном способе представления память разделена иа две части к п т — к элементов. Один из трех стеков начинает расти из точки к: при четном включении на единицу влево, при нечетном включении на единицу вправо; при включении и исключении элементов нужно помнить положение вершины этого стека. Два других стека растут навстречу этому стеку, из противоположных концов памяти. Текущие длины стеков обозначены через xiy агз, . В качестве математической модели рассмотрено четырехмерное блуждание в области: ati + x¡ + х$ + Х4 < т,х 1 + х2 < к, Хз + £4 < т — к. Область блуждания пронумеровала. Получена однородная поглощающая цепь Маркова. Доказана теорема о виде подматрицы Q, соответствующей переходам из невозвратных состояний в невозвратные, матрицы вероятностей переходов для данной цепи. Вычислена фундаментальная матрица N = (/ — <5)"1. Зная эту матрицу,

можно вычислить среднее время. Предложен алгоритм решения задачи: построить матрицу Q> вычислить матрицу N для возможных начальных разбиений памяти к и выбрать оптимальное. Оптимальным будет такое к, которое соответствует максимальному среднему времени. Вычислено оптимальное среднее время для каждого из трех случаев: когда из точки к растет первый стек, второй и третий. Написана программа, которая реализует данный алгоритм.

Второй способ — это связанное представление. В этом способе три стека располагаются связанно в памяти размером т единиц. Текущие длины стеков обозначены через Жз, В качестве математической модели рассмотрено случайное блуждание в пирамиде % + Хъ + х$ < у, т.к. половина памяти тратится на связи. Пронумерованная область блуждания представляет собой однородную поглощающую цепь Маркова. Доказана теорема о виде подматрицы Q вероятностей переходов из невозвратных состояний в невозвратные однородной поглощающей цепи Маркова. Предложен алгоритм решения задачи: построить матрицу Q, вычислить фундаментальную матрицу ЛГ и среднее время работы со стеками. Написана программа, реализующая данный алгоритм.

Также рассмотрено страничное представление трех стеков в памяти размером тп единиц, в котором предполагается, что существует связный список свободных страниц одинаковой длины, а каждый из стеков представлен в виде связанного списка занятых страниц, где один элемент каждой страницы тратится на связь. Текущие длины стеков обозначены через 22,хь. Оптимальный размер страницы с точки зрения максимизации количества единиц памяти, которое используется под данные, х = у/т. В качестве математической модели рассмотрено случайное блуждание в пирамиде, asi + Х2 + Х3 < m*:

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

ницы, с которыми работали два других стека, тоже заполнены полностью;

• т* = т — ^ — 2 • (х — 2) для случая, когда память используется не полностью (минимально), т.е. после переполнения из одного из стеков, когда в списке свободной памяти нет свободных страниц, две другие страницы, с которыми работали два других стека, заполнены минимально, в них содержится только по одной единице данных.

Возможны две оценки для среднего времени: максимальная и минимальная. Состояния пронумерованы также, как и в задаче о связанном представлении трех стеков. Матрица переходов из невозвратных состояний в невозвратные С} для случая страничной организации памяти имеет такую же структуру, как для случая связанной организации памяти, за исключением того, что ее размерность в х раз меньше. Вычислена фундаментальная матрица N для каждого из случаев. Получены две оценки для среднего времени — максимальная и минимальная. Написана программа, которая реализует данный алгоритм.

Во второй главе предложены и исследуются математические модели, описывающие несколько методов представления четырех стеков в памяти одного уровня. Рассмотрено последовательное, связанное и страничное представление. Определяется какой из методов эффективнее в предположении, что известны некоторые вероятностные характеристики стеков. Критерий оптимальности — среднее время до переполнения памяти.

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

Первый способ — связанное представление. Рассмотрено четыре стека в памяти размером тп единиц. Текущие длины стеков обозначены через XI,х2, хз, В качестве математической модели рассмотрено четырех-

мерное блуждание в области хх + х$ + + хл, < Щ, т.к. половина памяти тратится на связи. Вводится нумерация состояний. Пронумерованные состояния представляют собой однородную поглощающую цепь Маркова. Предложен алгоритм решения задачи: построить матрицу <3, вычислить фундаментальную матрицу N и среднее время работы со стеками. Написана программа, реализующая данный алгоритм.

Второй способ — страничное представление. Рассматривается четыре стека в страничной памяти размера тп единиц. Оптимальный размер страницы х = Текущие длины стеков обозначены через х^

В качестве математической модели рассмотрено случайное блуждание в области + Хз ■+- + Х4 < ш*:

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

• тп* = ш — 3-(х — 2) для случая, когда память используется не полностью (минимально), т.е. после переполнения из одного из стеков, когда в списке свободной памяти нет свободных страниц, три другие страницы, с которыми работали три других стека, заполнены минимально, в них содержится только по одной единице данных.

Возможны две оценки для среднего времени: максимальная и минимальная. Состояния пронумерованы также, как и в задаче о связанном представлении четырех стеков. Матрица С> для случая страничной организации памяти будет иметь такую же структуру, как для случая связанной организации памяти, за исключением того, что ее размерность в х раз меньше. Вычислена фундаментальная матрица N для каждого из случаев. Получены две оценки для среднего времени — максимальная и ми-

нимальная. Написана программа, которая реализует данный алгоритм.

Третий способ — последовательное представление. Пусть в памяти объема т единиц расположены четыре стека. Двум стекам, растущим навстречу друг другу, выделено к единиц памяти, двум другим стекам, растущим на встречу друг другу, выделено т — к единиц памяти. Задача заключается в том, чтобы найти такое оптимальное разбиение памяти на две части размерами к ч т — к элементов, и определить какой из трех стеков будет объединен в пару с первым так, что бы среднее время работы со стеком было бы максимальным. Текущие длины стеков обозначены через Х\,Х2,хз,х^. В качестве математической модели рассмотрено четырехмерное блуждание в области XI + хз + + х^ < тп,х 1 + Ж2 < к, хз + х^ < ш — к. Область блуждания совпадает с областью блуждания для задачи о представлении трех стеков, как четырех. Воспользуемся уже введенной нумерацией состояний и теоремой о виде подматрицы С} вероятностей переходов из невозвратных состояний в невозвратные. Вычислена фундаментальная матрица N. Предложен алгоритм решения задачи: построить матрицу вычислить матрицу ТУ для возможных начальных разбиений памяти к и выбрать оптимальное. Оптимальным является такое к, которое соответствует максимальному среднему времени. Вычислено оптимальное среднее время для каждого из трех случаев: когда в первую пару объединены первый и второй стек, первый и третий, первый и четвертый. Написана программа, реализующая данный алгоритм.

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

В третьей главе рассматривается задача об оптимальном способе раз-

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

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

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

В памяти объема т > 0 условных единиц расположены три параллельных стека, вероятностные характеристики которых известны. Текущие длины стеков — XI, х?,

В случае последовательного представления двум стекам, растущим навстречу друг другу, отведено а единиц памяти, а третьему стеку — т— з единиц. Задача заключается в том, чтобы разбить память на две части так, чтобы среднее время работы со стеками было бы максимальным, т.е. необходимо определить оптимальное значение 5. Также необходимо выяснить, какой из трех стеков следует расположить отдельно в гп — з единиц памяти.

Для первого варианта рассмотрен более простой случай, когда возможны только включения в стеки. Пусть первый и второй стеки объединены в пару, а третий стек расположен отдельно. Введены обозначения: х = Х1 + х^, у = £3. Тогда в качестве математической модели удобно рассмотреть двумерное случайное блуждание внутри прямоугольника, х >= 0,у >= 0,х < в'+ < т — в + 1. Процесс выходит из начала координат и поглощается на прямых х = 8-Ь1иу = т — я +1- Среднее время блуждания до поглощения Т(х, у), если начальной точкой блуж-

дания была точка (ж, у) равно Т(х,у) — г • Т{х,у) + рх • Т(х + 1, у) +рз • rC«,y-H)+R-r(s + l,íí + l)+P4-T(x+2,y)+p8-T(a;+2,sf + l) + l. Попав на границы области блуждания происходит поглощение и следовательно T(s+ 1,у) = 0,T(x,m — s +1) = 0 и Т(х,т — 5 + 2) = 0. Предложен алгоритм решения задачи: выбор стека, который будет расположен отдельно, и нахождение такого значения s, чтобы Т(0,0) было максимальным. Разработана программа, реализующая данный алгоритм.

В общем случае в качестве математической модели задачи рассмотрено случайное блуждание точки, координаты которой определяются текущими длинами стеков (xi, х%, x¡), по целочисленной решетке в пространстве внутри треугольной призмы х\Л-Хч < з,£3 <m — s. Предложена нумерация состояний. Получена однородная поглощающая цепь Маркова. Доказана теорема о виде подматрицы Q вероятностей переходов данной цепи, соответствующая переходам из невозвратных состояний в невозвратные. Предложен алгоритм решения задачи: построить матрицу Q, вычислить матрицу N для возможных начальных разбиений памяти s и выбрать оптимальное. Оптимальным будет такое s, которое соответствует максимальному среднему времени. Вычислено оптимальное среднее время для каждого из трех случаев; когда отдельно расположен первый стек, второй и третий. Написана программа, реализующая данный алгоритм.

Для случая связанного представления трех стеков, расположенных связанно в памяти размером ш единиц, в качестве математической модели рассмотрено случайное блуждание в пирамиде Х1 + Х2 + Х3 < у,Т.К. половина памяти тратится на связи. Введена нумерация состояний. Доказана теорема о виде подматрицы Q вероятностей переходов из невозвратных состояний в невозвратные однородной поглощающей цепи Маркова. Предложен алгоритм решения задачи: построить матрицу Q, вычислить фундаментальную матрицу N и среднее время работы со стеками. Написана программа, реализующая данный алгоритм.

Также рассматривается страиичное представление трех стеков в памяти размера ш единиц, в кагором предполагается, что существует связный список свободных страниц одинаковой длины, а каждый из стеков представлен в виде связанного списка занятых страниц, где один элемент каждой страницы тратится на связь. Через Х],>х2,хз обозначены текущие длины стеков. Оптимальный размер страницы х — у/т. В качестве математической модели рассмотрено случайное блуждание в пирамиде + х2 + Яз < "г*:

• т' = т — ^ для случая, когда память используется полностью (максимально), т.е. после переполнения одного из стеков, когда в списке свободной памяти нет свободных страниц, две другие страницы, с которыми работали два других стека, тоже заполнены полностью;

• тп* = т — ^ — 2 • (я - 2) для случая, когда память используется не полностью (минимально), т.е. после переполнения из одного из стеков, когда в списке свободной памяти нет свободных страниц, две другие страницы, с которыми работали два других стека, заполнены минимально, в них содержится только по одной единице данных.

Возможны две оценки для среднего времени: максимальная и минимальная. Состояния пронумерованы также, как и в задаче о связанном представлении трех стеков. Матрица <3 для случая страничной организации памяти будет иметь такую же структуру, как для случая связанной организации памяти, за исключением того, что ее размерность в х раз меньше. Вычислена фундаментальная матрица N для каждого из случаев. Получены две оценки для среднего времени — максимальная и минимальная. Написана программа, которая реализует данный алгоритм.

Второй случай, когда существуют два процессора и возможно не более двух одновременных включений или исключений в три стека в па-

шгги одного уровня рассмотрен аналогичным способом.

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

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

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

Поставлена задача определить, как производить перераспределение стека между уровнями памяти, чтобы минимизировать средние временные затраты. Под перераспределением понимается перепись хо +1 верхних элементов стека с памяти второго уровня в быструю память, если быстрая память стала пустой (теперь, после исключения элемента, в быстрой памяти будет хо элементов), или выталкивание т — хо + 1 элементов на второй уровень и, возможно, перепись хо — 1-верхних элементов стека в начало быстрой памяти, если произошло ее переполнение (теперь, после включения нового элемента в стек, в быстрой памяти станет Хо элементов).

Задача заключается в определении такого состояния хо (1 < хо < ш), в которое происходит переход после перераспределения памяти.

Вероятности переходов изменяются следующим образом. Если стек перешел в состояние a~o ~ 1> то вероятность возврата в состояние ха равна pi, а вероятность перехода в состояние xq — 2 равна 1 — p¡. Если стек перешел в состояние хо + 1, то вероятность возврата в состояние хо равна Р2, а вероятность перехода в состояние хо + 2 равна 1 — рг- То есть параметры pi и ра определяют вероятность возвращения в состояние, из которого стек перешел в заданное, в зависимости от того включение или исключение элемента произошло. Заметим, что в случае Рх = р2 — Р вероятность вернуться ие зависит от операции, которая произошла со стеком, а в случае pi ~ рг = 1/2 — имеем классическое симметричное случайное блуждание.

Рассмотрены следующие возможные способы управления вершиной стека с различными начальными вероятностями переходов:

• Пусть факт переполнения или опустошения вершины стека пе отслеживается. ТЪгда можно считать, что вероятность включения и исключения элемента из начального состояния равна 1/2. Для всех остальных состояний вероятность возвращения в предыдущее состояние при исключении равна pi, при включении — p-¿, а вероятность удаления от него соответственно равна qi = 1—Pi и <й = 1—Рг-

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

1. Пусть произошло переполнение и стек перешел в некоторое состояние i (последняя операция перед перераспределением — включение). Тогда pz — вероятность перехода из г-го состояния в i — 1, и, соответственно, 1 — рг — вероятность перехода из состояния г в состояние i +1.

2. Пусть произошло опустошение и стек перешел в некоторое состояние г (последняя операция перед перераспределением — исключение). Тогда рх — вероятность перехода из состояния г в г + 1, и, соответственно, 1 — — вероятность перехода из состояния г в состояние г — 1.

Рассмотрена задача нахождения оптимального состояния вершины стека для трех рассмотренных методов управления и для следующего критерия оптимизации — максимизация среднего времени между двумя последовательными перераспределениями.

Для решения задачи осуществлен переход от немарковской модели к цепи Маркова путем удвоения числа состояний.

В качестве состояний рассматриваются переходы из одного состояния стека в другое: каждому состоянию i поставим в соответствие пару состояний (г, { 4- 1) и (г + 1, г). Тогда состояния будут нумероваться так: сначала из 1 в г +1, т. е. (г,г +1), затем обратно в 1 из г 4-1, т. е. (г + 1,г).

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

В заключепии приведены основные результаты, полученные в диссертации:

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

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

2. Лазутина A.A. Об оптимальном управлении динамическими структурами данных/ Лазутина A.A., Аксенова Б.А., Соколов A.B. и др. Труды V международной конференции "Дискретные модели в теории управляющих систем". Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2003. с. 5-6. (вклад диссертанта 25 %)

3. Лазутина A.A. Оптимальные методы динамического распределения нестраничпой памяти/ Лазутина A.A., Аксенова Е.А., Соколов A.B. и др. Труды Первой Всероссийской научной конференции "Методы и средства обработки информации". Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2003. с.74-79. (вклад диссертанта 25 %)

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

■ 33 96)

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

6. Лазутина A.A. Оптимальное управление тремя стеками в памяти одного уровня в случае параллельного выполнения операций/ Лазутина A.A. Труды VII международной конференции "Дискретные модели в теории управляющих систем". ВМК МГУ им. М.В. Ломоносова. -М.: МАКС Пресс, 2006, с. 205-210.

7. Лазутина A.A. Оптимальное управление тремя стеками в памяти одного уровня/ Лазутина A.A., Соколов A.B. Системы управления и информационные технологии. №1.1 (23) 2006. с. 152-158. (вклад диссертанта 50 %)

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

Тезисы докладов:

1. Lazutina А.А. Mathematical models of dynamic data structure/ Lazutina A.A., Sokolov A.V., Aksenova E.A. et ai. V international congress on mathematical modeling. Book of abstract, vol. II, JINR, Dubna 2002, p. 127, (вклад диссертанта 25 %)

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

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

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

5. Лазутина А.А, Оптимальное управление тремя стеками в памяти одного уровня/ Лазутина А.А., Соколов А.В. Тезисы докладов XIV Международной конференции "Проблемы теоретической кибернетики". Изд. центра прикладных исследований при механико-математическом факультете МГУ, Москва 2005, с. 84. (вклад диссертанта 50 %)

6. Lazutina А.А. Probability models and optimal algorithms of dynamic data structure control/ Lazutina A.A., Sokolov A.V., Aksenova E.A. et al. Extended abstracts, PTAP, Petrozavodsk, 2006, p.57-58. (вклад диссертанта 25%)

Изд. лиц. № 00041 от 30.08.99. Подписано в печать 13.31.06. Формат 60x84 '/]£. Бумага офсетная. Гарнитура «Птег». Печяп офсетная. Уч.-изд. л. 1,0. Печ. л. 1,0. Тираж 100 экз. Изд. № 84. Заказ 623.

Карельский научный центр РАН 185003, Петрозаводск, пр. А. Невского, 50 Редакщгонно-иадательсклй отдел

Введение

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. Пакет программ, реализующий рассмотренные в работе математические модели. Для заданного размера памяти и заданных наборов вероятностей вычисляется среднее время работы до переполнения или перераспределения, находится оптимальное разбиение памяти для последовательных способов.

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.