Математические модели и оптимальные методы реализации динамических структур данных тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Аксёнова, Елена Алексеевна

• Аксёнова, Елена Алексеевна
• кандидат физико-математических наук
• 2007

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

Введение

1 Математические модели и алгоритмы управления стеками в двухуровневой памяти

1.1 Оптимальное управление одним стеком в двухуровневой памяти

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

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

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

1.2 Оптимальное управление двумя параллельными стеками в двухуровневой памяти

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

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

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

2 Оптимальное управление двумя FIFO-очередями в памяти одного уровня

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

2.2 Связанное представление двух очередей.

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

2.3 Страничное представление двух очередей.

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

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

2.4 Решение задачи.

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

3 Оптимальное управление очередью с двумя приоритетами в памяти одного уровня

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

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

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

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

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

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

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

3.5 Решение задачи.

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

4 Оптимальное управление тремя FIFO-очередями в памяти одного уровня

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

4.2 Последовательное представление трех очередей

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

4.3 Связанное представление трех очередей.

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

4.4 Страничное представление трех очередей.

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

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

4.5 Решение задачи.

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

5 Оптимальное управление тремя FIFO-очередями на бесконечном времени

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

5.2 Последовательное представление трех очередей

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

5.3 Связанное представление трех очередей.

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

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

Введение диссертации (часть автореферата) на тему «Математические модели и оптимальные методы реализации динамических структур данных»

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

Стеком LIFO (Last In First Out) называется линейный список, в котором все включения и исключения (и обычно всякий доступ) происходят на одном конце, который называется вершиной стека. Другой по отношению к вершине конец стека называется началом стека. Очередью FIFO (First In First Out) называется линейный список, в котором все включения происходят на одном конце (конец очереди), а все исключения (и обычно всякий доступ) происходят на другом конце (начало очереди) [25]. Под линейным списком будем понимать множество узлов, структурные свойства которого ограничиваются лишь их линейным (одномерным) относительным положением.

Понятие стека широко используется при разработке программного и аппаратного обеспечения. Стеки используются в алгоритмах синтаксического разбора [16, 34, 35], для анализа скобочной структуры текста и вычисления выражений [29], в алгоритмах машинной графики [39], в алгоритмах поиска на графах [25, 30], в алгоритмах сортировки [26, 40], в системе управления процессами [33, 38, 45], при разработке архитектуры [17, 22, 23, 27, 33, 44]. При разработке RISC процессоров для работы со скалярными аргументами и локальными переменными функций организуются перекрывающиеся окна регистров постоянного или переменного размеров [47, 51]. В этом случае получаем один стек с элементами типа "окно" в главной памяти, у которого несколько верхних элементов образуют циклический стек на регистрах. В архитектуре Intel Itanium [60] у каждой процедуры есть регистровый стек с элементами переменного размера для хранения параметров. Выходные параметры одной процедуры являются входными параметрами другой. В процессорах Intel, Motorola и др. стек наращивается в сторону уменьшающихся значений адресов памяти. Это означает, что указателю позиции вершины того или иного стека первоначально присваивается значение самого старшего адреса области памяти, предоставляемой для организации данного стека [36, 37].

При переполнении или опустошении регистровой вершины стека на практике применяют несколько программных и аппаратных методов, которые имеют преимущества по сравнению с универсальными алгоритмами замещения кэш-памяти [51, 59]:

1. Large Stack. Можно сделать стек большим и предполагать, что переполнения не будет, а если оно все же произошло, то совершить аварийное завершение работы.

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

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

4. Barometr-Pointer Algorithm. Предлагались реализации стека, когда перемещения элементов между уровнями памяти происходят не при переполнении или опустошении, а при отклонении от оптимального состояния вершины (обычно считается, что это половина быстрого буфера) в фоновом режиме, т.е. параллельно с обычным выполнением команд (аналог опережающей подкачки и откачки в страничной виртуальной памяти).

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

Во всех этих методах вершина стека является продолжением стека, находящегося в памяти второго уровня.

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

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

Если рассмотреть несколько стеков (процессов) и общий ресурс быстрой памяти, то можно показать, что встречное расположение стеков в виде пар стеков, растущих навстречу друг другу, лучше раздельного, если в качестве критерия оптимальности выбрано среднее время работы стеков до переполнения [42, 58]. Задача построения математической модели такого способа распределения памяти была поставлена Д. Кнутом [25]. Исследовалось поведение двух стеков, расположенных в памяти объема т и растущих навстречу друг другу. В этом случае место встречи стеков можно рассматривать как случайную величину. Известно, что на каждом шаге с вероятностью р может произойти исключение элемента из одного из стеков, с вероятностью 1 — р может произойти включение информации в один из стеков. Пусть М{т,р) математическое ожидание случайной величины max(ki, £2), где ki и длины стеков при встрече. Задача состоит в том, чтобы установить вид функции М(т,р). В [41] предложен алгоритм вычисления М(т,р) для конечных значений т. Для решения задачи использовалась теория поглощающих цепей Маркова [24]. В [61] решалась задача исследования М(т,р) при т —* оо для 0.25 < р < 0.5. В [49, 52, 53] исследовалось асимптотическое поведение размеров стеков при переполнении и времени работы до переполнения памяти для 0 < р < 0.25. В [54] решалась задача для случая, когда вероятности включения и исключения информации зависят от размеров стеков. В [42, 55, 58] предложены марковские модели для решения задач управления несколькими стеками. В [14] исследовалась задача управления двумя параллельными стеками в двухуровневой памяти.

FIFO-очереди используются в компьютерных сетях, операционных системах, графических системах, устройствах промышленной автоматики. Ряд американских фирм выпускает микросхемы, реализующие работу с несколькими FIFO-очередями (IDT Inc. [32], Cypress, AverLogic Technologies). В диссертационной работе рассмотрены некоторые задачи оптимального представления нескольких FIFO-очередей в памяти одного уровня. Оптимальность понимается либо в смысле максимизации среднего времени работы до переполнения какой-либо очереди, либо в смысле минимизации доли потерянных элементов при бесконечном времени работы очередей. Первый критерий разумно применять в программных системах, когда переполнение какой-либо очереди может привести к остановке работы программы. Второй критерий уместен, например, в сетевых маршрутизаторах, когда пакеты, которые помещаются в переполненную очередь, просто теряются ("сброс хвоста") [18]. Потери пакетов приводят к нежелательному результату, поэтому число таких ситуаций необходимо свести к минимуму.

Для организации FIFO-очередей в памяти компьютера применяются два принципиально разных способа представления: последовательный и связанный [25]. Известны указатели на конец и начало очереди. В последовательном способе организации каждой очереди отводится определенная область памяти. При такой организации часто очередь зациклена, т.е. при достижении концом очереди конечной границы выделенной области памяти следующие включения элементов будут происходить с начальной границы, если есть свободная память. В связанном способе организации очередь представлена в виде связанного списка, каждый элемент которого состоит из двух единиц памяти, одна из которых используется для хранения информации, другая для хранения указателя на следующий элемент. В некоторых приложениях, например, в ряде версий операционных систем, для сетевых маршрутизаторов применяется некий промежуточный способ, когда очереди представлены в виде связанного списка буферов (страниц) одинаковой длины. В связанном представлении затраты памяти на хранение связей самые большие, в последовательном представлении таких затрат нет, но есть потери памяти за счет того, что при переполнении одной из очередей другая очередь заполнена не до конца. В страничном представлении есть затраты памяти первого и второго рода.

В работах [12, 43] рассматривались задачи оптимального управления двумя FIFO-очередями.

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

Существуют различные способы реализации очередей с приоритетами. Одним из часто используемых способов является представление N - приоритетной очереди в виде N FIFO-очередей. Приложениями очередей по приоритетам являются системы моделирования, в рамках которых ключи могут соответствовать моментам возникновения событий, что обеспечивает возможность их обработки в хронологическом порядке, системы планирования заданий в компьютерных системах, где ключи могут соответствовать приоритетам, указывающим, какой из пользователей должен быть обслужен первым. Метод приоритетной очереди достаточно широко используется, например, как один из аппаратно-независимых методов управления перегрузками в технологии QoS. В операционной системе Cisco IOS реализация приоритетной очереди содержит четыре различные подочереди: high, medium, normal и low priority [18].

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

Основными результатами диссертации являются:

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

Заключение

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

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

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

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

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

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

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

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

5. Аксенова Е.А., Соколов А.В. Об оптимальном управлении двумя FIFO-очередями.// Материалы VIII Международного семинара «Дискретная математика и ее приложения». М.: Изд-во механико-математического факультета МГУ, 2004, с. 167-169.

6. Аксенова Е.А., Соколов А.В. Некоторые задачи оптимального управления FIFO-очередями.// Труды Второй Всероссийской научной конференции «Методы и средства обработки информации». Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2005, с.318-322.

7. Аксенова Е.А., Соколов А.В., Тарасюк А.В. Об оптимальном управлении двумя FIFO-очередями в конечной области памяти.// Системы управления и информационные технологии, №3, 2006, с.62-68.

8. Аксенова Е.А. Оптимальное управление FIFO-очередями на бесконечном времени.// Межвуз. сб. «Стохастическая оптимизация в информатике». Изд-во С.-Петербургского университета, вып.2, 2006, с.71-76.

9. Аксенова Е.А., Соколов А.В. Оптимальное управление двумя параллельными стеками в двухуровневой памяти.// Дискретная математика, М, 2007, с.67-75.

10. Аксенова Е.А. Некоторые задачи управления динамическими структурами данных.// Материалы IX Международного семинара «Дискретная математика и ее приложения». М.: Изд-во механико-математического факультета МГУ, 2007, с.201-203.

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

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

13. Боллапаргада В., Мэрфи К., Расс У. Структура операционной системы Cisco IOS. М.: Вильяме. 2002. с. 163-189.

14. Вавилов В.В., Устинов А.В. Многоугольники на решетках. М.:МЦНМО, 2006.-72с.

15. Гантмахер Ф.Р. Теория матриц. М.:Наука, 1967.-576с.

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

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

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

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

20. Кнут Д. Искусство программирования для ЭВМ. Т.1, М.:Изд-во "Вильяме", 2001.-720с.

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

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

23. Кормен Т., Лейзерсои Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.-960С.

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

25. Липский В. Комбинаторика для программистов. М.:Мир, 1988.-213с.

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

27. Мамаева Т.Ю. Новые семейства памяти FIFO-TeraSync DDR и Multi-queue. URL:http: / / www.efo.ru / doc/IDT/IDT.pl?179

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

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

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

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

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

33. Робачевский А. Операционная система Unix.-Cn6.:BHV Санкт - Петербург, 1998.-528с.

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

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

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

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

38. Соколов А.В., Тарасюк А.В. Об оптимальном управлении циклическими FIFO-очередями.// Системы управления и информационные технологии, 2005. №3(20), с.29-33.

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

40. Таненбаум Э. Современные операционные системы. Спб.: Питер, 2002,-1040с.

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

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

43. Ertl Anton М. Stack caching for interpreters. SIGPLAN '95 Conf. Programm. Lang. Des. and Implem.(PLDI), 15 La Jolla,Calif,June 18-21,1995.

44. 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.

45. 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.

46. Koopman P. Stack Computers. Ellis Horwood, 1989.

47. URL: http://www.cs.cmu.edu/~koopman/stackcomputers/

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

49. 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.

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

51. 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.

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

53. 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.

54. 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.

55. Stanley Т., Wedig R. A performance analysis of automatically managed top of stack buffers // Proceeding of 14th Symposuim on Computer Architecture. June. 1987. P. 272-281.

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