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

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

Конев Илья Михайлович

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

программ

Специальность 05 13 11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Москва - 2007

003178010

Работа выполнена на механико-математическом факультете и в Институте механики Московского государственного университета им М В Ломоносова

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

профессор,

Васенин Валерий Александрович

Официальные оппоненты

Ведущая организация

доктор физико-математических наук, старший научный сотрудник, Галатенко Владимир Антонович

кандидат физико-математических наук, Аветисян Арутюн Ишханович

Вычислительного центра им А А Дородницына РАН

Защита диссертации состоится « 21 » декабря 2007 г в ь. часов на заседании диссертационного совета Д 002 087 02 в Институте системного программирования Российской академии наук по адресу 109004, Москва, ул Большая Коммунистическая, д 25

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан « »ЯОлЗи^Н 2007 г

Ученый секретарь диссертационного совета канд физ -мат наук

7?

С П Прохоров

Общая характеристика работы

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

Программные системы, в которых используется динамически выделяемая память, нуждаются в ее освобождении К таким системам можно отнести большинство реализаций современных языков программирования, некоторые распределенные базы данных и многие другие При явном, «ручном» освобождении памяти, возникают хорошо известные трудности Преждевременное удаление объектов ведет к образованию так называемых «висячих указателей» (dangling pointers), а несвоевременное освобождение памяти из-под неиспользуемых объектов вызывает «утечки памяти» (memory leaks) По этой причине еще в 1960-ые годы начали появляться системы автоматического управления памятью, получившие название сборщиков мусора (Garbage collectors или GC)

В настоящее время для большинства современных языков программирования существуют автоматические сборщики мусора В языках, в которых отсутствуют указатели и прямой доступ к памяти, таких как Java, Lisp и Python, сборщик мусора обычно встроен в систему поддержки времени исполнения В высокопроизводительных языках, таких как С и С++, он, как правило, реализуется либо в виде внешней библиотеки с использованием консервативного сборщика мусора, либо при активном участии программиста

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

• Количество и объем сообщений, посылаемых GC, не должны ока-

зывать существенного влияния на работу приложения По возможности, при использовании GC должна отсутствовать необходимость синхронизации между всеми узлами распределенной системы, что особенно актуально для систем с медленными сетевыми каналами в Во многих случаях к системам автоматического сбора мусора предъявляют требования устойчивости к частичным сбоям (fault-tolerance), таким как аварийный останов узлов, разрыв сетевых соединений, а также появление ошибок в пересылаемых сообщениях

• Производительность сборщика мусора не должна существенно ухудшаться при увеличении количества узлов в распределенной системе Масштабируемость особенно важна для крупных распределенных систем, построенных по технологии GRID, с помощью которой можно объединять большое количество ЭВМ на сетевой среде в единый комплекс — «виртуальную организацию» (термин, принятым в GRID)

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

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

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

Одним из таких средств является система автоматизированного динамического распараллеливания программ — Ке\уТБ, одной из главных целевых функций которой является возможность ее использования в составе вычислительных комплексов на гетерогенной сетевой среде Система Не\уТЭ основана на использовании идей Т-подхода1 Ключевыми особенностями такой системы являются следующие

• программы для Ые\уТ8 разрабатываются на традиционных высокопроизводительных языках (С и С++),

• распараллеливание обеспечивается небольшим количеством модификаторов (атрибутов функций и переменных), обрабатываемых на этапе трансляции исходного кода,

• ускорение достигается путем параллельного исполнения функций программы

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

1Динамическое распараллеливание программ на базе параллельной редукции графов Архитектура программного обеспечения новой версии Т-системы /СМ Абрамов, В А Васенин, Е Е Мамчиц и др // Тр Всерос науч конф «Высокопроизводительные вычисления и их приложения» (30 октября - 2 ноября 2000, г Черноголовка) - \1 Изд-во МГУ, 2000 - С 201-264

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

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

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

Для достижения этой цели поставлены следующие задачи

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

• разработка подсистемы сбора ациклического мусора, обеспечивающая «атомарное» копирование ссылок,

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

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

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

• Предложена математическая модель системы управления распределенными ссылками, описывающая работу ациклического сборщика мусора, обеспечивающего «атомарное» копирование ссылок Доказана корректность представленного в модели алгоритма

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

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

Созданная программная реализация системы сбора ациклического мусора в настоящее время используется в действующей версии системы NewTS автоматизированного распараллеливания программ как основной метод управления распределенными ссылками Она показала свою работоспособность как на модельных примерах, так и ходе решения практически значимых задач с использованием NewTS В их числе программный комплекс Vortex, моделирующий обтекание твердых тел потоком вязкой несжимаемой жидкости, приложения rt и PovRay, используемые для построения изображений методом трассировки лучей, программа анализа и индексирования текстовых документов, используемая в автоматизированной системе информационной обработки (АСИО), разработанной в МГУ им М В Ломоносова Предложенные автором механизмы прошли тестовые испытания на ряде модельных программ В их числе решение задачи N тел методом Барнса-Хата, решение задачи поиска подграфа в графе с помеченными ребрами

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

Основные положения работы докладывались на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломоносов-2006», «Ломоносов-2007», на международной конференции Finnish Data Processing Week'05 (г Петрозаводск, 17-20 мая 2005

года), на третьей международной конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на семинаре «Проблемы современных информационно-вычислительных систем» в МГУ им М В Ломоносова под руководством д ф -м н , проф В А Васе-нина (2 раза в 2005-2006 годах)

По материалам диссертации опубликовано восемь работ

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

Работа состоит из введения, четырех глав, заключения и списка литературы Общий объем диссертации — 128 страниц Список литературы содержит 84 наименования

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

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

Первая глава является вводной В ней рассматривается подход к распараллеливанию программ, основанный на использовании автомаги-зированного динамического распараллеливания В первом разделе кратко описывается архитектура ядра системы NewTS1 Представлены основные языковые конструкции, обеспечивающие распараллеливание Во втором разделе описываются предпосылки постановки задачи сбора мусора и метод ее решения в предыдущей версии Т-системы — OpenTS2, а также -в ранних версиях NewTS В третьем перечисляются основные недостатки таких решений

1 Водомеров А Н Методы и средства автоматизированного распараллеливания приложений в распределенной среде Дис каид физ -мат наук 05 13 11 / МГУ им М В Ломоносова — Москва, 2007 - 144 с

2 OpenTS An Outline of Dynamic Parallelization Approach / S Abramo/ and A Adamovich and A Inyukhm et al // Parallel Computing Technologies 8th International Conference, Krasnoyarsk, Russia, September 5-9, 2005 / Ed by V Malyshkin - Springer-Verlag, 2005 - Vol 2606 of Lecture Notes m Computer Sctence - Pp 303-312

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

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

К числу таких систем относится и программный комплекс NewTS Программы для NewTS пишутся на языке ТС — модификации языка С++ В язык С++ добавлено несколько ключевых слов, наиболее важными из которых являются tfun и tval Модификатор tfun указывается перед функцией и означает, что объявляемая функция является Т-функцией Т-функция обладают тем свойством, что вызывающая ее функция продолжает свою работу, а сама Т-функция может быть запущена позже на другом узле вычислительной системы параллельно с вызывающей Синхронизация Т-функций в случаях, когда вызывающая и вызываемая функции получают доступ к одним и тем же данным, например, к возвращаемому значению вызываемой, обеспечивается с помощью Т-переменных Такими называются переменные, помеченные модификатором tval

Данные, общие для нескольких Т-функций, (такие как возвращаемое значение для вызывающей и вызываемой функций) хранятся в специальной структуре — Т-объекте При этом Т-переменные представляют собой ссылки на соответствующий объект, который может быть расположен на другом узле вычислительной системы Время жизни Т-объекта определяется количеством ссылок из Т-функций, указывающих на него Если ссылки на какой-либо из Т-объектов закончились, то не существует способов получения доступа к его данным Как следствие, такой объект можно удалить Данные Т-объекта могут содержать ссылки на другие Т-объекты, ссылки во входных аргументах Т-функций могут перемещаться между узлами вычислительной системы В результате все Т-объекты и ссылки на них образуют вычислительный граф, распределенный между узлами кластера

На рис 1 показан пример вычислительного графа в некоторый момент времени Серым цветом помечены пользовательские ссылки, черными — ссылки из данных одного Т-объекта на другой Объекты, помеченные числами от 1 до 5 должны быть автоматически удалены Они являются мусором, поскольку доступ к ним нельзя получить ни из одной Т-функции Таким образом, возникает необходимость решения задачи автоматического сбора мусора

В OpenTS, также как и в первых версиях NewTS, эта задача решалась использованием весового счетчика ссылок1 Такое решение обладает двумя недостатками

Во-первых, копирование ссылок на Т-объект на удаленном узле (отличном от того, па котором расположен Т-объект) может вызывать посылку сообщения и синхронное ожидание ответа Копирование ссылки, таким образом, не является «атомарным» Исполнение программы при этом приостанавливается, вызывая простои вычислительных узлов

Во-вторых, использование весового счетчика ссылок не позволяет ав-

1Bevaп D I Distributed garbage collection usmg reference counting // Proceedmgs of the Parallel Architectures and Laguages Europe, Volume I — London, UK Spnngcr-Verlag, 1987 — Pp 176-187

Рис 1 Пример вычислительного графа

томатически удалять циклический мусор (объекты 3 и 4 на рис 1), что снижает применимость системы, в частности для графовых задач, которые создают циклические структуры данных

По перечисленным причинам перед автором была поставлена задача разработки для МешТБ системы сбора мусора, устраняющей отмеченные недостатки

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

Основное назначение этой главы состоит в определении алгоритмов, позволяющих решить поставленные задачи, а также в оценке сложности их реализации в Не\уТБ

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

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

Методики для последовательных вычислительных систем нельзя напрямую применять в распределенных системах в силу следующих причин Во-первых, схема, работающая в однопроцессорной системе, перестает быть корректной при переходе к распределенной в силу параллельной модификации вычислительного графа несколькими узлами вычислительной системы одновременно Во-вторых, наличие сетевых задержек и ограниченность пропускной способности сетевых каналов существенно влияют на эффективность алгоритма Например, в параллельном варианте алгоритма подсчета ссылок необходимо при каждом копировании ссылки на удаленном для объекта узле посылать сообщение и приостанавливать работу программы По этим причинам для распределенных систем был разработан ряд алгоритмов, позволяющих избавиться от основных недостатков алгоритмы WRC, GRC, IRC, RRC, reference listing для схем, основанных на подсчете ссылок, алгоритмы Худака и Келлера,

Хагса, схемы с использованием «back tracing» для трассирующих алгоритмов и другие

В базовом варианте реализация многих из этих алгоритмов в NewTS вызвала бы существенные технические трудности или была бы неэффективной и не решала проблем, возникших в OpenTS В частности, при использовании IRC возникают сложности с удалением ссылок, расположенных на стеке, поскольку время жизни ссылки больше времени жизни ее копий Алгоритмы WRC и GRC не обеспечивают возможности кэширования удаляемых ссылок Трассирующие алгоритмы требуют наличия механизма обхода полей произвольной С++-структуры и рефлексии стека для определения корневого множества, что является технически сложной задачей

Анализ перечисленных факторов позволяет сделать вывод о том, что для распределенных систем автоматизированного распараллеливания программ, аналогичных NewTS, необходимо модифицировать один из существующих алгоритмов, а также решить ряд технических задач, вызванных использованием языка С++ Для этого автором предлагается структура системы сбора мусора, состоящая из двух компонентов сборщика ациклического мусора, основанного на подсчете ссылок и сборщика циклического мусора, базирующегося на одном из трассирующих алгоритмов Механизм подсчета ссылок может быть использован для определения корневого множества без необходимости анализа содержимого стека

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

примерах с алгоритмом из OpenTS

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

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

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

Автором предложено строить древовидную структуру не на ссылках, а на копиях объекта (на каждом узле, на котором есть ссылки, есть и копия) При этом новая вершина в дерево добавляется при операциях копировании ссылок с весом 1 Ссылки с большим весом копируются, как в схеме WRC Такая комбинация позволяет избежать недостатков как WRC, так и IRC за счет использования копий объектов

В разделе 2 представлена математическая модель сбора мусора Ее изложение проводится по следующей схеме

• описывается работа пользовательской программы, как набора по-

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

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

• доказывается, что достижимая из пользовательской программы часть вычислительного графа остается неизменной при наличии подсчета ссылок и удалении объектов,

• описывается класс объектов, удаляемых с помощью системы сбора мусора

В подразделе 2 1 вводятся понятия ссылки (как пары (пст, гЛ), где па — номер узла, гс1 — идентификатор объекта, на который она указывает), объекта (как пятерки (псг,м1,птЛ,К)), сообщения со ссылкой (как четверки (nSTC,ndst,'r,гd)) Далее вводится понятие состояния распределенной системы (как четверки (0,5Л, и,пг<1)), включающей в себя состояние сети 5Е и вычислительного графа О Описываются в виде инвариантов условия его корректности Далее вводятся операции над состоянием распределенной системы (соответствующие естественным операциям копирования, создания, удаления ссылок), описывается класс применимых операций После этого доказывается теорема о том, что применимые операции не нарушают инварианты корректности

Теорема 1 Пусть операция ор применима в корректном состоянии Я (Б 5гу) Тогда состояние £г тоже корректно

Эта теорема позволяет доказать, что введенные понятия корректного состояния и применимой операции непротиворечивы

В подразделе 2 2 модель расширяется подсчетом ссылок При этом вводятся понятия расширенной ссылки, и расширенного объекта Затем вводятся понятия расширенной операции После этого доказывается теорема о корректности системы с расширенными ссылками, обьектами и операциями

Теорема 2. Пусть операция ор применима в корректном состоянии S (S Sr) Тогда состояние Sr тоже корректно

В подразделе 2 3 доказывается корректность системы с подсчетом ссылок (тот факт, что подсчет ссылок не удаляет Т-объекты достижимые для пользователя) Для этого вводятся понятия проекции расширенной операции на обычную, а также расширенного состояния на обычное Далее даются понятия обычного и расширенного процесса, как последовательности операций Вводится понятие соответствия обычного и расширенного процесса, после чего доказывается, что состояние обычного процесса на каждом шаге есть проекция состояния расширенного

Теорема 3. Верны следующие утверждения

• Пусть расширенный пользовательский процесс (ор1} ,орп) находится в состоянии S и соответствует пользовательскому процессу (op 1,. ,орт), находящемуся в состоянии S Тогда состояние S есть проекция расширенного состояния S

• Пусть пользовательский процесс (opi, ,орт) находится в состоянии S Тогда существует соответствующий ему расширенный процесс S

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

Теорема 4. Пусть есть корректное состояние S вида (О, Net, U, nid) Пусть Oa(S) — множество распределенных объектов, являющихся ациклическим мусором в состоянии S Тогда существует последовательность операций оръ ,дрп вида recv_del_ref таких, что S Si, Si ¿>2, ,Sn-i Sn, а множество Oa(Sn) пусто

Раздел 3 посвящен описанию реализации предложенного в модели алгоритма в NewTS Несмотря на то, что алгоритм, описанный в рамках

формальной модели, и является корректным, он недостаточно эффективен Копирование ссылки является тяжеловесной операцией в силу того, что при ее выполнении необходимо делить вес в некоторой пропорции Для устранения этого недостатка объект был разделен на две части локальную и глобальную Локальная часть реализована как обычный счетчик ссылок Значение этого счетчика равняется общему количеству ссылок, указывающих на объект и расположенных на данном узле Глобальная часть действует так, как описано в предложенном в рамках модели алгоритме Такая схема позволяет не хранить вес в расположенных на узле ссылках и, тем самым, значительно ускорить локальные операции с ними В таблице 1 представлены результаты замеров работы тестового приложения fib до и после описанной оптимизации

Измеряемый параметр Значение параметра га

29 30 31 32

количество созданных объектов, в млн время работы подсчета ссылок после оптимизации, сек время работы подсчета ссылок до оптимизации, сек 1 7 0 47 38 27 0 77 59 44 1 16 89 70 2 05 14 5

Таблица 1 Измерение работы счетчика ссылок в программе fib

Разделение объекта на две части позволило также снизить нагрузку на сетевые коммуникации В алгоритме, описанном в рамках формальной модели, при удалении ссылки на узле, отличном от того, на котором расположен объект, необходимо послать сообщение с возвращаемым весом В реализованном алгоритме удаление ссылки, которая не является последней, вызывает лишь уменьшение соответствующего счетчика ссылок Такая схема позволяет в несколько раз (как правило, в 1,5 — 2) уменьшить количество сообщений, относящихся к сбору мусора

Разделение объекта на две части требует автоматического преобразования локальных ссылок в глобальные при посылке сообщений с данными Поскольку по сети могут посылаться данные произвольных объявленных пользователем типов, необходим механизм «просмотра» и ана-

лиза содержимого объектов произвольных типов, что является сложной технической задачей для языка С++ Для решения этой задачи автором был предложен и реализован механизм, позволяющий добавлять методы в классы языка С++ на этапе трансляции исходного кода

В разделе 4 описываются практические испытания разработанной системы подсчета ссылок Измерения проводились на двух типах приложений модельных, в которых основную часть времени работы занимают функции ядра NewTS, и практических (трассировщик лучей rt и программный комплекс Vortex, моделирующие нестационарное двумерное обтекание тел потоком несжимаемой жидкости) Приложения первого типа позволяют измерить, какую часть работы ядра составляют операции со ссылками, приложения второго типа — какую нагрузку на сеть вызывает система сбора мусора в практических приложениях

Кол-во узлов 2 4 8 16 32 64 128 200

Кол-во сообщений, в тыс 1 3 53 19 5 717 271 6 1054 4201 6677

Объем сообщений, в Мб 30 0 152 2 392 6 860 0 936 7 1915 3906 6199

Кол-во БЕС-сообщений, в тыс 1 03 08 20 42 86 17 6 35 4 55 5

Объем БЯС-сообщений, в Мб 0 009 0 027 0 06 013 0 28 0 56 113 1 78

Таблица 2 Замеры работы комплекса Vortex

Измерения на комплексе Vortex, показали, что сетевая нагрузка, создаваемая системой подсчета ссылок, составляет менее 1% от общей сетевой нагрузки приложения (см табл 2)

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

Большинство существующих алгоритмов сбора циклического мусора основаны на распределенном обходе вычислительного графа Основную

1 Количество сообщений с возвращаемым весом

сложность в таких алгоритмах составляет реализация параллельной работы сборщика мусора и пользовательского приложения Причина в том, что процедура обхода графа может занимать продолжительное время Существует несколько методик, обеспечивающих параллельную работу пользовательского приложения и системы сбора мусора В числе основных распределенная версия алгоритма Дейкстры, схемы на основе временных меток и алгоритмы, использующие back tracing Однако многие из этих алгоритмов неэффективны либо сложны в реализации В частности, схемы на основе временных меток требуют, чтобы время посылки и последующего приема сообщения было 01рапичен0 сверху Алгоритм Дейкстры может потребовать синхронизации с удаленным узлом при копировании ссылок По этой причине автором был предложен и реализован альтернативный алгоритм

Идея предлагаемого алгоритма состоит в создании «копии» вычислительного графа, по которой и выполняется обход Копия после ее создания остается неизменной, а именно — операции работы со ссылками и объектами никак не меняют ее содержимое Такой подход позволяет сборщику мусора и пользовательскому приложению работать параллельно

Создание копии без необходимости синхронизации узлов не является простой задачей Алгоритм, заключающийся в том, что какой-то выделенный узел инициирует создание копии, посылая всем остальным сообщение о необходимости построения копии, некорректен В этом случае узлы построят копии частей вычислительного графа в различные моменты времени По этой причине для создания распределенной копии применяются традиционные двухфазные методы При этом описанные выше действия выполняются последовательно два раза, после чего берется пересечение этих двух копий (множество объектов, которые находятся в одном и том же состоянии в' обоих копиях) После таких действий пересечение будет содержаться некоторое подмножество вычислительного графа, который был в момент времени между созданием первой и второй копии

На рис 2 показан процесс создания копии вычислительного графа на

одном из узлов Серыми стрелками обозначены пользовательские ссылки, черными — ссылки из данных одного Т-объекта на другой Легко видеть, что результирующий граф, полученный из двух копий содержит в себе информацию только о тех объектах, которые не менялись между созданием первой и второй копии

Рис 2 Пример создания копии вычислительного графа на одном из узлов

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

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

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

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

1 Некоторый узел становится выделенным и инициирует цикл сбора мусора

2 Выполняется первая фаза создания распределенной копии вычислительного графа

3 Выполняется вторая фаза создания распределенной копии

4 Каждый узел собирает информацию о весах объектов, согласно содержимому копии

5 Вычисляется распределенное корневое множество (с помощью сравнения общего веса в ссылках и в самом объекте)

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

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

При реализации алгоритма возникает два технических вопроса Первый состоит в том, что при построений копии объекта необходимо обойти

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

Первый вопрос разрешается с использованием разработанной на основе парсера ОрепСХХ системы для добавления методов в классы языка С++ на этапе трансляции кода В каждый класс, содержащий ссылки, добавляется метод, обходящий поля с данными и записывающий в копию информацию о полях-ссылках

Разрешение второго вопроса сводится к необходимости определения наличия в сети сообщений, выполняющих распределенный обход Эта задача решается путем подсчета общего количества отправленных и принятых сообщений Для этого выделенный узел подсчитывает суммарное количество отправленных и полученных сообщений на всех узлах После этого он сравнивает результат с аналогичным числом, полученным в предыдущий раз Если все четыре числа (количество отправленных и полученных сообщений в текущий и прошлый раз) совпадают, и все узлы закончили обход локального корневол о множества (обработали все локальные ссылки и послали необходимые сообщения), то обход графа завершен Совпадение четырех чисел означает, что в сети нет больше сообщений, относящихся к обходу графа, следовательно он уже полностью обойден

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

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

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

1 Построена математическая модель управления распределенными объектами В рамках модели предложен алгоритм сбора ациклического мусора, обеспечивающий «атомарное» копирование ссылок Доказана корректность работы этого алгоритма

2 Алгоритм сбора ациклического мусора реализован в программном комплексе NewTS Результаты тестирования и практические испытания показали соответствие реализации предъявляемым к ней требованиям, эффективность с позиции временных затрат на поддержку операций в ядре системы и создаваемой ею сетевой нагрузки

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

4 Алгоритм сбора циклического мусора реализован в программном комплексе NewTS Корректность функционирования и работоспособность алгоритма подтверждены результатами его тестирования на модельных приложениях

Публикации по теме диссертации

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

1 Водомеров А Н , Конев И М , О некоторых способах создания эффективных распределенных приложений // Тезисы III междунар коиф по проблемам управления МКПУ-2006 (20-22 июня 2006, ИПУ РАН, Москва) — Т 2 — М Институт проблем управления 2006 -С 137

2 Водомеров А Н , Конев И М , Степанов Е А , Некоторые методы организации высокопроизводительных вычислений в распределенной среде // Материалы IX Междунар конф «Проблемы функционирования информационных сетей» ПФИС-2006 (31 июля — 3 августа 2006, ИВМиМГ СО РАН, Новосибирск) / Под ред В К Попкова, А С Родионова — Новосиб РИЦ «Прайс-курьер», 2006 -С 78-82

3 Конев И М Механизмы организации ссылок в открытой Т-системе // Тез докл науч корф «Ломоносовские чтения» (18-28 апреля,

МГУ им Ломоносова, Москва) — М Изд-во Московского университета, 2005 - С 122-123

4 Конев И М К созданию системы автоматического сбора мусора в новой версии Т-системы // Тез докл науч конф « Ломоносовские чтения » (17-27 апреля, МГУ им Ломоносова, Москва) — М Изд-во Московского университета, 2006 — С 89-90

5 Конев И М Управление динамической памятью в ядре системы автоматического распараллеливания 1ЧетеТ8 реализация подсистемы сбора мусора // Тезисы III Междунар конф по проблемам управления МКПУ-2006 (20-22 июня 2006, ИПУ РАН, Москва) - Т 2 — М Ин-т проблем управления, 2006 — С 138

6 Конев И М О некоторых способах организации рефлексии объектов при разработке параллельных программ // Тез докл науч конф «Ломоносовские чтения» (16-25 апреля, МГУ им Ломоносова, Москва) — М Изд-во Московского университета 2007

7 Конев И М , Степанов Е А Автоматизация динамического распараллеливания программ планирование, управление памятью, работа в гетерогенной среде // Информационные технологии — №10 М Изд-во «Новые технологии», 2007 — С 71-73

8 Конев И М , Степанов Е А Автоматизация динамического распараллеливания программ планирование, управление памятью, работа в гетерогенной среде // Приложение к журналу «Информационные технологии» — №10 М Изд-во «Новые технологии», 2007 — 32 с

Подписано в печать 15 11 2007 г Исполнено 16 11 2007 г Печать трафаретная

Заказ № 1004 Тираж 50 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш, 36 (495) 975-78-56 ште айогеГега! ги

Введение

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

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

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

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

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

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

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

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

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

1.1 Т-система как подход к распараллеливанию программ.

1.2 Распределенные ссылки и работа с ним в Т-системе

1.3 Недостатки подсистемы работы с распределенными ссылками в первых версиях NewTS.

1.4 Выводы.

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

2.1 Основные понятия.

2.2 Основные алгоритмы для последовательных систем

2.2.1 Подсчет ссылок (reference counting).

2.2.2 Алгоритмы пометки и очистки (mark-and-sweep collection)

2.2.3 Копирующие коллекторы (copying collection)

2.2.4 Выводы.

2.3 Автоматическое управление памятью в распределенных системах . 34 2.3.1 Распределенный подсчет ссылок.

2.3.2 Распределенные трассирующие алгоритмы.

2.3.3 Устойчивость к частичным сбоям в распределенной системе

2.3.4 Выводы.

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

2.5 Особенности управления памятью в NewTS.

3 Сборщик ациклического мусора

3.1 Базовый алгоритм для сбора ациклического мусора

3.2 Математическая модель системы распределенных объектов.

3.2.1 Основные понятия.

3.2.2 Модель подсчета ссылок.

3.2.3 Корректность модели с подсчетом ссылок.

3.2.4 Удаление недостижимых объектов в системе с подсчетом ссылок

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 Удаление недостижимых клеток (sweep-фаза).

4.3 Практические испытания.

4.4 Выводы.

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

Программные системы, в которых используется динамически выделяемая память, нуждаются в ее освобождении. К таким системам можно отнести большинство реализаций современных языков программирования, некоторые распределенные базы данных и многое другое. При явном, «ручном» освобождении памяти возникают хорошо известные трудности. Преждевременное удаление объектов ведет к образованию так называемых «висячих указателей» (dangling pointers), а неосвобождение памяти из-под неиспользуемых объектов вызывает «утечки памяти» (memory leaks). По этой причине еще в 60-ые годы прошлого века начали появляться системы автоматического управления памятью, получившие название систем сбора мусора (garbage collectors или GC).

В настоящее время для большинства современных языков программирования существуют автоматические сборщики мусора. В языках, в которых отсутствуют указатели и прямой доступ к памяти, таких как Java, Lisp и Python, сборщик мусора обычно встроен в систему поддержки времени исполнения. В высокопроизводительных языках, таких как С и С++, он, как правило, реализуется в виде внешней библиотеки и, как следствие, не требует специальной поддержки со стороны компилятора или средств поддержки времени исполнения (runtime).

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

• Количество и объем сообщений, посылаемых GC, не должен оказывать существенного влияния на работу приложения. По возможности, при использовании GC должны отсутствовать синхронизации между всеми узлами распределенной системы, что особенно актуально для систем с медленными сетевыми каналами.

• Во многих случаях от системы автоматического сбора мусора требуют высокой степени устойчивости к частичным сбоям (fault-tolerance), таким как аварийный останов узлов, разрыв сетевых соединений, а также появление ошибок в пересылаемых сообщениях.

• Производительность сборщика мусора не должна существенно ухудшаться при увеличении количества узлов в распределенной системе. Масштабируемость особенно важна для крупных распределенных систем, построенных по технологиям GRID [38], поскольку с помощью такой технологии можно объединять большое количество машин в единую систему — «виртуальную организацию» (в терминологии, принятой в GRID).

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

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

Одним из таких средств является система автоматизированного динамического распараллеливания NewTS [4, б, 8], которая призвана в большей степени, чем аналоги, быть приспособленной к работе в гетерогенной среде. Система NewTS основана на использовании идей Т-подхода. Ключевыми моментами системы являются следующие:

• программы для NewTS разрабатываются на традиционных высокопроизоводи-тельных языках (С и С++);

• распараллеливание обеспечивается небольшим количеством модификаторов (атрибутов функций и переменных), обрабатываемых на этапе трансляции исходного кода;

• ускорение достигается путем параллельного исполнения функций программы.

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

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

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

Для достижения этой цели поставлены следующие задачи:

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

2. разработка подсистемы сбора ациклического мусора, обеспечивающая «атомарное» копирование ссылок;

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

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

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

1. построена математическая модель управления распределенными объектами;

2. разработан алгоритм сбора ациклического мусора, обеспечивающий «атомарное» копирование ссылок;

3. доказана корректность разработанного алгоритма в рамках построенной модели распределенных объектов;

4. разработанный алгоритм реализован в системе автоматизированного распараллеливания NewTS;

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

6. на его основе реализована система освобождения неиспользуемых ресурсов (циклического мусора) для ядра NewTS.

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

Научной новизной обладают следующие результаты диссертационной работы.

• Предложена математическая модель системы управления распределенными ссылками, описывающая работу ациклического сборщика мусора, обеспечивающего «атомарное» копирование ссылок. Доказана корректность представленного в модели алгоритма.

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

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

Созданная программная реализация системы сбора ациклического мусора в настоящее время используется в системе NewTS как основной метод управления распределенными ссылками. Она показала свою работоспособность как на модельных примерах, так и в практических задачах, реализованных для NewTS. В их числе: программный комплекс Vortex, обсчитывающий обтекание твердых тел потоком жидкости [9]; приложения rt [1] и PovRay [72], используемые для построения изображений методом трассировки лучей; программа анализа и индексирования текстовых документов, для текущей версии автоматизированной системы информационной обработки (АСИО [2]), разработанной в МГУ им. М. В. Ломоносова. Разработанные механизмы опробованы на ряде модельных программ, в числе которых решение задачи N тел методом Барнса-Хата, решение задачи поиска подграфа в графе с помеченными ребрами.

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

Основные положения работы докладывались на IX международной конференции «Проблемы функционирования информационных сетей» ПФИС-2006 (Новосибирск, 31 июля - 3 августа 2006 года) на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломоносов-2006», «Ломоносов-2007», на международной конференции Finnish Data Processing Week'05 (г. Петрозаводск, 17-20 мая 2005 года), на третьей международной конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на семинаре «Проблемы современных информационно-вычислительных систем» в МГУ им. М.В. Ломоносова под руководством д.ф.-м.н., проф. В.А. Васенина.

По материалам диссертации опубликовано восемь работ [15, 16, 8, 13, 7, 12, 11, 14].

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

Работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации — 128 страниц. Список литературы содержит 85 наименований.

4.4 Выводы

В данной главе представлен алгоритм сбора циклического мусора, основанный на использовании комбинации подсчета ссылок и mark-sweep алгоритма. Разработанный алгоритм позволяет обеспечить сбор циклического мусора без синхронизации узлов и необходимости остановки мутаторов. Сбор мусора может производиться в любом заранее заданном множестве объектов. Такая функциональность является принципиально новой для NewTS и позволяет расширить класс распараллеливаемых программ.

Заключение

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

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

• Алгоритм сбора ациклического мусора реализован в программном комплексе NewTS. Результаты тестирования и практические испытания показали соответствие реализации предъявляемым к ней требованиям, эффективность с позиции временных затрат на поддержку операций в ядре системы и создаваемой ею сетевой нагрузки.

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

• Алгоритм сбора циклического мусора реализован в программном комплексе NewTS. Корректность функционирования и работоспособность алгоритма подтверждены результатами его тестирования на модельных приложениях.

1. Афонин С. А., Козицын А. С., Титов А. В. Автоматизированная система обработки информации в интересах обеспечения безопасности критически важных объектов // Проблемы безопасности и противодействия терроризму. — МЦНМО, 2006. — С. 383-400.

2. Васепин В. А., Водомеров А. Н. Формальная модель системы автоматизированного распараллеливания программ // Программирование. — 2007. — № 4.

3. Васенин В. А., Водомеров А. Н., Инюхин А. В. Средства автоматизированного динамического распараллеливания программ на основе сочетания императивных и функциональных механизмов // Информационные Технологии. — 2007. — № 5. — 32 с.

4. Васенин В. А., Роганов В. A. GRACE: распределенные приложения в интернет // Открытые системы. — 2001. — № 5. — С. 29-33.

5. Водомеров А. Н. Методы и средства автоматизированного распараллеливания приложений в распределенной среде: Дис. .канд. физ.-мат. наук: 05.13.11 / МГУ им. М. В. Ломоносова. — Москва, 2007. — 144 с.

6. Конев И. М. Механизмы организации ссылок в открытой Т-системе // Тез. докл. науч. конф. «Ломоносовские чтения» (18-28 апреля, МГУ им. Ломоносова, Москва). — М.: 2005. С. 122-123.

7. Конев И. М. К созданию системы автоматического сбора мусора в новой версии Т-системы // Тез. докл. науч. конф. «Ломоносовские чтения» (17-27 апреля, МГУ им. Ломоносова, Москва). — М.: Изд-во Московского университета, 2006,— С. 89-90.

8. Конев И. М. О некоторых способах организации рефлексии объектов при разработке параллельных программ // Тез. докл. науч. конф. «Ломоносовские чтения» (16-25 апреля, МГУ им. Ломоносова, Москва). — М.: 2007.

9. Конев И. М., Степанов Е. А. Автоматизация динамического распараллеливания программ: планирование, управление памятью, работа в гетерогенной среде // Информационные технологии. — 2007. — № 10. — С. 71-79.

10. Конев И. М., Степанов Е. А. Автоматизация динамического распараллеливания программ: планирование, управление памятью, работа в гетерогенной среде // Приложение к журналу «Информационные технологии». — № 10. М.: Изд-во «Новые технологии», 2007. 32 с.

11. Моделирование нестационарных нагрузок при движении тел в вязкой жидкости: Отчет №4775 / С. В. Гувернюк, Г. Я. Дынникова, П. Р. Андронов и др.; Ин-т механики МГУ. — М., 2005.- 93 с.

12. Т-система с открытой архитектурой / С. М. Абрамов, А. И. Адамович, А. В. Инюхин и др. // Тр. Междунар. науч. конф. «Суперкомпьютерные системы и их применение SSA'2004» (26-28 октября 2004, г. Минск).- Минск: ОИПИ НАН Беларуси, 2004. — С. 18-22.

13. Таненбаум Э., ван Стеен М. Распределенные системы. Принципы и парадигмы, — П.: Питер, 2003. 880 с.

14. Abdullahi S. E.-Y. Empirical Studies of Distributed Garbage Collection: Ph.D. thesis / Department of Computer Science, Queen Mary and Westfield College, University of London. — UK, London, 1996. 318 pp.

15. Baden S. B. Low-Overhead Storage Reclamation in the Smalltalk-80 Virtual Machine // Smalltalk-80: Bits of History, Words of Advice. — Addison-Wesley Publishing Company, 1983.-Pp. 331-342.

16. Baker H. G. The treadmill: real-time garbage collection without motion sickness // SIGPLAN Not. 1992. - Vol. 27, no. 3. - Pp. 66-70.

17. Bennett J. K. The design and implementation of distributed Smalltalk // OOPSLA '87: Conference proceedings on Object-oriented programming systems, languages and applications. New York, NY, USA: ACM Press, 1987. - Pp. 318-330.

18. Bevan D. I. Distributed garbage collection using reference counting // Proceedings of the Parallel Architectures and Languages Europe, Volume I,— London, UK: Springer-Verlag, 1987.-Pp. 176-187.

19. Boehm H.-J. Space efficient conservative garbage collection // PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation. — New York, NY, USA: ACM, 1993. Pp. 197-206.

20. Boehm H.-J., Demers A. J., Shenker S. Mostly parallel garbage collection // Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation (PLDI). —Vol. 26.- 1991.-Pp. 157-164. citeseer.ist.psu.edu/boehm91mostIy.html.

21. Brownbridge D. R. Cyclic reference counting for combinator machines // Proc. of a conference on Functional programming languages and computer architecture. — New York, NY, USA: Springer-Verlag New York, Inc., 1985. Pp. 273-288.

22. The Charm Parallel Programming Language and System: Part I Description of Language Features / L. Kal'e, B. Ramkumar, A. Sinha, A. Gursoy; University of Illinois, University of Iowa. - Urbana, Iowa City, USA, 1995. - 27 pp.

23. Cilk: An efficient multithreaded runtime system: Tech. rep. / R. D. Blumofe, C. F. Joerg, В. C. Kuszmaul et al. — Cambridge, MA, USA: Massachusetts Institute of Technology, 1996.

24. Cohen J., Trilling L. Remarks on garbage collection using a two level store // Tidskrift for Informations Behandeling, Denmark. — 1967. — Vol. 7. — Pp. 22-30.

25. Collins G. E. A method for overlapping and erasure of lists // Commun. ACM. — 1960.— Vol. 3, no. 12. Pp. 655-657.

26. Define F. К. H. A., bins R. D. Distributed cyclic reference counting // Canada-France Conference on Parallel and Distributed Computing. — 1994. — Pp. 95-100. citeseer.ist.psu.edu/dehne94distributed.html.

27. Dickman P. Optimizing Weighted Reference Counts for Scalable Fault-Tolerant Distributed Object-Support Systems. — Submitted for HICSS 26.

28. El-Habbash A., Horn C., Harris N. Garbage collection in an object oriented distributed environment // Proceedings of the ECOOP/OOPSLA Workshop on Garbage Collection.— Ottawa, Canada: 1990. citeseer.ist.psu.edu/338568.html.

29. Fenichel R. R., Yochelson J. C. A lisp garbage-collector for virtual-memory computer systems // Commun. ACM. 1969. - Vol. 12, no. 11.- Pp. 611-612.

30. Frigo M., Leiserson С. E., Randall К. H. The implementation of the Cilk-5 multithreaded language // Proc. of the ACM SIGPLAN 1998 conference on Programming language design and implementation. New York, NY, USA: ACM Press, 1998. - Pp. 212-223.

31. Fuchs M. Garbage collection on an open network // IWMM '95: Proceedings of the International Workshop on Memory Management. — London, UK: Springer-Verlag, 1995. — Pp. 251-265.

32. GNU prof Электронный ресурс. — Электрон, текст, дан. — Б. изд., 2007. — Режим доступа: http://www.gnu.Org/software/binutils/manual/gprof-2.9.l/htmlmono/gprof.html, свободный. — Электрон, текст, док.

33. Grimshaw A. S. An introduction to parallel object-oriented programming with mentat: Tech. rep. Charlottesville, VA, USA: 1991.

34. GUM: a portable parallel implementation of Haskell / P. W. Trinder, K. Hammond, J. J. S. Mattson et al. // Proc. of the ACM SIGPLAN 1996 conference on Programming language design and implementation. — N.Y.: ACM Press, 1996. — Pp. 79-88.

35. Halstead R. H. Implementation of Multilisp: Lisp on Multiprocessor // Proc. of the 1984 ACM Symposium on LISP and functional programming, Austin, Texas, United States. — N.Y.: ACM Press, 1984,- Pp. 9-17.

36. Henry G. Baker J. List processing in real time on a serial computer // Commun. ACM.— 1978. Vol. 21, no. 4. - Pp. 280-294.

37. Hudak P., Keller R. M. Garbage collection and task deletion in distributed applicative processing systems // LFP '82: Proceedings of the 1982 ACM symposium on LISP and functional programming. New York, NY, USA: ACM Press, 1982. - Pp. 168-178.

38. Hughes J. A distributed garbage collection algorithm // Proc. of a conference on Functional programming languages and computer architecture. — New York, NY, USA: Springer-Verlag New York, Inc., 1985,- Pp. 256-272.

39. Jones R. E., Lins R. D. Cyclic weighted reference counting without delay // Parallel Architectures and Languages Europe. — 1993. — Pp. 712-715. citeseer.ist.psu.edu/jones92cyclic.html.

40. Keller R., Nguyen V. PACX-MPI Project Homepage Электронный ресурс. — Электрон, текст, дан. — 2003. — Режим доступа: http://www3.niu.edu/mpi/, свободный. — Электрон, текст, док.

41. Knizhnik К. Reflection Package for С++ Электронный ресурс.— Электрон. текстовые дан. — Б. изд., 2004. — Режим доступа: http://www.garret.ru/~knizhnik/cppreflection/docs/reflect.html, свободный. — Электрон, версия печ. публикации.

42. Kranz D. A., R. Н. Halstead J., Mohr Е. Mul-t: a high-performance parallel lisp // PLDI '89: Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation. New York, NY, USA: ACM Press, 1989. - Pp. 81-90.

43. Lang В., Dupont F. Incremental incrementally compacting garbage collection // SIGPLAN '87: Papers of the Symposium on Interpreters and interpretive techniques. — New York, NY, USA: ACM, 1987. Pp. 253-263.

44. Lermen C.-W., Maurer D. A protocol for distributed reference counting // LFP '86: Proceedings of the 1986 ACM conference on LISP and functional programming. — New York, NY, USA: ACM Press, 1986. Pp. 343-350.

45. Lieberman H., Hewitt C. A real-time garbage collector based on the lifetimes of objects // Commun. ACM. 1983. - Vol. 26, no. 6. - Pp. 419-429.

46. Lins R. D. Cyclic reference counting with lazy mark-scan // Information Processing Letters. — 1990.-Vol. 44, no. 4.-Pp. 215-220. citeseer.ist.psu.edu/lins90cyclic.html.

47. Maheshwari U. Distributed garbage collection in a client-server, transaction, persistent object system: Tech. rep. — Cambridge, MA, USA: 1993.

48. Maheshwari U., Liskov B. Collecting distributed garbage cycles by back tracing // PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing. New York, NY, USA: ACM, 1997. - Pp. 239-248.

49. Marti J. Rlisp '88: An Evolutionary Approach to Program Design and Reuse.— World Scientific Pub Co Inc, 1988. 257 pp.

50. McCarthy J. Recursive functions of symbolic expressions and their computation by machine, part i // Commun. ACM.- I960. Vol. 3, no. 4.- Pp. 184-195.

51. Miranda E. Brouhaha — a portable Smalltalk interpreter // OOPSLA '87: Conference proceedings on Object-oriented programming systems, languages and applications. — New York, NY, USA: ACM Press, 1987. Pp. 354-365.

52. Mohamed-Ali K. A. Object-Oriented Storage Management and Garbage Collection in Distributed Processing Systems: Academic dissertation / Royal Institute of Technology, Dept of Computer Systems. — Stockholm, Sweden, 1984.

53. MPI: A Message-Passing Interface Standard Электронный ресурс.— Электрон, текст, дан.— Knoxville, Tennessee: University of Tennessee, 1995.— Режим доступа: http://www.mpi-forum.org/docs/mpi-ll.ps, свободный. — Электрон, версия печ. публикации.

54. MPICH-G2 Электронный ресурс. — Электрон, текст, дан, — 2005,— Режим доступа: http://www3.niu.edu/mpi/, свободный. — Электрон, текст, док.

55. Nori А. К. A Storage Reclamation Scheme for Applicative Multiprocessor Systems: Ph.D. thesis / University of Utah. — Salt Lake City, Utah, 1979.

56. On-the-fly garbage collection: An exercise in cooperation / E. W. Dijkstra, L. Lamport, A. J. Martin et al. // Commun. ACM. 1978. - Vol. 21, no. 11. - Pp. 966-975.

57. OProffie Электронный ресурс.— Электрон, текст, дан.— Режим доступа: http://oprofile.sourceforge.net, свободный. — Электрон, текст, док.

58. The Persistence of Vision Raytracer Электронный ресурс.— Электрон, текст, дан.— 2007. — Режим доступа: http://www.povray.org/, свободный, — Электрон, текст, док.

59. Randall К. H. Cilk: Efficient Multithreaded Computing: Ph.D. thesis / Massachusetts Institute of Technology. — Cambridge, MA, USA: Massachusetts Institute of Technology, 1998.

60. Richter J. Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework Электронный ресурс.— Электрон, текст, дан, — Б. изд.— Режим доступа: http://msdn.microsoft.com/msdnmag/issues/1100/gci/, свободный. — Электрон, текст, док.

61. Robert Н. Halstead J. Multilisp: a language for concurrent symbolic computation // A CM Trans. Program. Lang. Syst. — 1985. — Vol. 7, no. 4. — Pp. 501-538.

62. Rodriguez-Riviera G., Russo V. Cyclic distributed garbage collection without global synchronization in corba. — 1997. citeseer.ist.psu.edu/95492.html.

63. Rudalics M. Correctness of distributed garbage collection algorithms: Tech. rep. — Johannes Kepler Universitat, Linz, Austria: 1990.

64. Shapiro M., Gruber O., Plainfosse D. A garbage detection protocol for a realistic distributed object-support system: Tech. Rep. 1320: 1990. citeseer.ist.psu.edu/shapiro90garbage.html.

65. Thomas R. E. A data flow architecture with improved asymptotic: Tech. rep. — Cambridge, MA, USA: 1981.

66. Tuning Garbage Collection with the 1.4.2 Javatin. Virtual Machine [Электронный ресурс].— Электрон, текст, дан.— Б. изд., 2007.— Режим доступа: http://java.sun.eom/docs/hotspot/gcl.4.2/, свободный, — Электрон, текст, док.

67. Weizenbaum J. Symmetric list processor // Communications of ACM.— 1963.— Vol. 6, no. 9. Pp. 524-536.

68. Wise D. S., Friedman D. P. The one-bit reference count // BIT Numerical Mathematics. — 1977. Vol. 17, no. 3. - Pp. 351-359.