Управление памятью в системах автоматизированного распараллеливания программ

• Автор: Конев, Илья Михайлович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 128 с. : ил.

Оглавление
Введение

Актуальность темы

Цель и задачи работы. б

Основные результаты работы

Научная новизна работы.

Практическая значимость

Доклады и публикации.

Структура и объем диссертации

Краткое содержание работы

1 Автоматическое управление памятью в Тсистеме

1.1 Тсистема как подход к распараллеливанию программ.
1.2 Распределенные ссылки и работа с ним в Тсистеме
1.3 Недостатки подсистемы работы с распределенными ссылками в первых
версиях .
1.4 Выводы
2 Основные методики автоматического управления памятью
2.1 Основные понятия
2.2 Основные алгоритмы для последовательных систем
2.2.1 Подсчет ссылок i.
2.2.2 Алгоритмы пометки и очистки i
2.2.3 Копирующие коллекторы i i
2.2.4 Выводы
2.3 Автоматическое управление памятью в распределенных системах .
2.3.1 Распределенный подсчет ссылок
2.3.2 Распределенные трассирующие алгоритмы.
2.3.3 Устойчивость к частичным сбоям в распределенной системе .
2.3.4 Выводы
2.4 Управление памятью в средствах параллельного программирования . .
2.5 Особенности управления памятью в МеигТ8
3 Сборщик ациклического мусора
3.1 Базовый алгоритм для сбора ациклического мусора
3.2 Математическая модель системы распределенных объектов
3.2.1 Основные понятия
3.2.2 Модель подсчета ссылок
3.2.3 Корректность модели с подсчетом ссылок
3.2.4 Удаление недостижимых объектов 1 системе с подсчетом ссылок
3.3 Оптимизации системы подсчета ссылок
3.3.1 Преобразование ссылок при передаче данных.
3.4 Реализация сборщика ациклического мусора.
3.5 Практические испытания.
3.5.1 Тестирование в однопроцессорной системе.
3.5.2 Тестирование в многопроцессорной системе
3.6 Выводы.
4 Сборщик циклического мусора
4.1 Алгоритм сбора циклического мусора.
4.1.1 Сбор циклического мусора в остановленной системе
4.1.2 Имитация останова системы без синхронизаций.
4.1.3 Построение корневого множества и обход графа .
4.2 Особенности программной реализации алгоритма сбора циклического
мусора
4.2.1 Создание копии вычислительного графа
4.2.2 Определение корневого множества.
4.2.3 Распределенный обход вычислительного графа тагкфаза. . .
4.2.4 Удаление недостижимых клеток янесрфаза.
4.3 Практические испытания
4.4 Выводы
Заключение
Литература


Целью диссертационной работы является исследование и разработка механизмов автоматического управления памятью в распределенных системах. В качестве системы, на которой апробируются разработанные алгоритмы, была выбрана система автоматизированного динамического распараллеливания КсуТ8 [4, б, 8]. НетсТБ. Научной новизной обладают следующие результаты диссертационной работы. Предложена математическая модель системы управления распределенными ссылками, описывающая работу ациклического сборщика мусора, обеспечивающего «атомарное» копирование ссылок. Доказана корректность представленного в модели алгоритма. Предложен комбинированный метод сбора циклического мусора, не требующий останова пользовательского приложения и механизмов синхронизаций при доступе к ссылкам. Созданная программная реализация системы сбора ациклического мусора в настоящее время используется в системе NewTS как основной метод управления распределенными ссылками. Она показана свою работоспособность как на модельных примерах, так и в практических задачах, реализованных для NcwTS. В их числе: программный комплекс Vortex, обсчитывающий обтекание твердых тел потоком жидкости |9|; приложения rt [1] и PovRay [], используемые для построения изображений методом трассировки лучей; программа анализа и индексирования текстовых документов, для текущей версии автоматизированной системы информационной обработки (АСИО [2|), разработанной в МГУ им. М. В. Ломоносова. Разработанные механизмы опробованы на ряде модельных программ, в числе которых решение задачи N тел методом Барнса-Хата, решение задачи поиска подграфа в графе с помеченными ребрами. Основные положения работы докладывались па IX международной конференции «Проблемы функционирования информационных сетей» ПФИС- (Новосибирск, июля - 3 августа года) на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-», «Ломоносов-», «Ломоносов-», на международной конференции Finnish Data Processing Week’ (г. Петрозаводск, - мая года), на третьей международной конференции по проблемам управления МКПУ- (Москва, ИПУ РАН, - июня года), на семинаре «Проблемы современных информационно-вычислительных систем» в МГУ им. М.В. Ломоносова под руководством д. В.А. Васенина. По материалам диссертации опубликовано восемь работ [, , 8,, 7,,,]. Работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации — 8 страниц. Список литературы содержит наименований. Первая глава является вводной. В ней кратко описывается Т-подход и его реализация в программном комплексе Мс? Т8. Обосновывается актуальность решаемых в диссертации задач для эффективной и корректной работы комплекса. Глава состоит из трех разделов. Вторая глава является обзорной и содержит изложение основных методик сбора мусора, лежащих в основе разработок, описанных в последующих двух главах. В этой главе описаны основные алгоритмы сбора мусора, как для однопроцессорных, так и для многопроцессорных систем. Основной акцент делается на алгоритмы сбора мусора в распределенных системах, не требующие синхронизаций. Глава состоит из четырех разделов. Третья глава посвящена описанию разработанной автором системы сбора ациклического мусора. Сначала строится математическая модель системы распределенных объектов, в рамках модели описывается алгоритм сбора мусора. Затем реализация этого алгоритма с различными оптимизациями для болсс быстрой работы описывается на псевдокоде. Показывается, что он является более эффективным, чем метод, реализованный в первых версиях КеигТ8. Приводятся испытания работы подсистемы на практических задачах, разработанных для ЫсхуТБ. Глава состоит из пяти разделов. Четвертая глава посвягцсиа разработке сборщика циклического мусора и его реализации в №уТ8. Сначала по шагам строится алгоритм и показывается его корректность. После этого рассматриваются особенности реализации, технические задачи, возникшие в ходе написания программного кода, и методы их решения. Приводятся испытания работы тестовых программ, содержащих циклический мусор. Глава состоит из трех разделов. В заключении перечисляются основные результаты работы.