Статья: Организация распределенной общей памяти в Т-системе с открытой архитектурой

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

С.М. Абрамов, В.А. Васенин, В.В. Корнеев, А.А. Московский, В.А. Роганов

ИПС РАН, ЦНТК, 2003 г.

АННОТАЦИЯ

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

СОДЕРЖАНИЕ

Достоинства объектно-ориентированной модели общей памяти как средства обмена данными в Т-системе

Решения, использованные при построении Суперпамяти

Описание архитектуры и программной реализации Суперпамяти

Организация адресного пространства

Повторное использование ячеек суперпамяти

Передача значений с узла на узел.

Общие (широковещательные) ячейки

Особенности используемого алгоритма распределенной сборки мусора

Использование Суперпамяти в составе Т-Суперструктуры

Краткое введение в архитектуру OpenTS

Операции присваивания и «замораживания» неготовых величин

Некоторые выводы и направления для дальнейшей работы

Использование возможностей стандарта MPI 2.

Возможные пути расширения адресного пространства Суперпамяти.

Благодарности

Достоинства объектно-ориентированной модели общей памяти как средства обмена данными в Т-системе

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

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

Этих недостатков лишены схемы так называемой объектно-ориентированной общей памяти, где единицей адресации является не аппаратная страница а объект. Перекладывая часть работы на программное обеспечение, удаётся достичь снятия указанных ограничений. Дополнительно, такая схема организации памяти может быть легко интегрирована с различными аспектами объектно-ориентированных технологий, такими как автоматическая сборка мусора. Более того, объект - ячейка общей памяти - может играть разные роли в иерархии классов приложения. Например, можно предусмотреть вызовы определённых методов при записи и чтении ячейки.

Т-система, являясь расширением модели вычислений традиционных языков, таких как С, С++, Фортран, предоставляет в распоряжение программиста новое понятие «неготовой величины», служащих для синхронизации между процессами-«поставщиками» и процессами-«потребителями». Использование обычной общей памяти не позволяет адекватно отразить семантику неготовых величин. Описанная в данной статье схема организации общей памяти первоначально возникла как часть новой технологии построения Т-системы - системы автоматического динамического распараллеливания вычислений на основе функционально-ориентированного расширения языка С++.

Решения, использованные при построении Суперпамяти

суперпамять алгоритм ячейка сборка

Перечислим кратко основные технические приёмы, использованные при организации общей памяти:

· «Ленивая» инициализация памяти. Ячейки общей памяти находятся в специальном сегменте виртуального адресного пространства каждого процесса, который проинициализирован нулями. Это позволяет зарезервировать большой объём виртуального адресного пространства, расходуя физическую память по мере необходимости.

· Глобальное адресное пространство. Каждая ячейка характеризуется смещением относительно начала сегмента. У объекта SCell имеет метод offset(), возвращающий это смещение. Функция cellAt(int offset) возвращает ячейку с данным смещением. При этом, в случае необходимости, вызывается конструктор ячейки. Одному и тому же смещению на разных вычислительных узлах отвечает логически одна и та же ячейка.

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

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

· Настраиваемость. Класс SCell может быть унаследован и дополнен новыми свойствами: например, в Т-системе этот класс является базовым для классов мобильных объектов и неготовых значений.

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

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

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

Следует особо подчеркнуть, что в ячейках общей памяти хранятся объекты, а не фиксированные структуры пользовательских данных. Один этот факт позволяет оперировать большими объемами физической памяти - более 4ГБ. Ограничивается лишь число ячеек, через которые происходит обмен информацией, но никак не общий объём информации, находящейся в общей памяти.

На каждом из узлов «ленивым» образом (при помощи функции calloc) резервируется область памяти под весь размер сегмента, заполненная нулями. Ячейки, «собственные» для данного узла содержат Т-величины, созданные в процессе вычислений на данном узле. «Slave» - ячейка ведёт себя как неготовая величина, заставляющая потребителя ждать, пока из сети не будет получено значение величины. Ячейки суперпамяти, расположенные на разных узлах, образуют «суперматрицу» (см рис. 1)

В «отраженных» ячейках хранятся не только данные, но и флажки о запросах на чтение, полученные для мастер-ячейки с тем же смещением.

Повторное использование ячеек суперпамяти

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

а) произошло высвобождение ячейки по каким-либо причинам.

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

в) Эта же ячейка оказалась вторично захвачена, и в неё произошла запись готового значения.

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

Рисунок 1. Организация общей памяти

Передача значений с узла на узел

Узел, запросивший значение с мастер-узла, заносит пометку в соответствующую «отраженную» ячейку и посылает запрос на мастер узел при помощи коммуникационной библиотеки (в нашем случае - MPI).

Мастер-узел поддерживает массив флагов полученных запросов на чтение (реально он хранится в отраженных ячейках «суперматрицы»). Также хранится массив признаков «отсылались ли данные» для каждого из узлов.

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

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

Листинг 1

// Exported TransportHandler

class Cell {}; // класс Ячейки

class TransportHandler : public MPITagHandler {

// класс- Обработчик связанный с низкоуровневой коммуникационной библиотекой (MPI)

public:

int cellRankSize; // размер сегмента на каждом узле

int cellStartOfs; // начальное сегмента на данном узле

int cellSize; // размер ячейки (байт)

int sharedSize; // количество «общих» или широковещательных ячеек

void (*onRead)(Cell*); // метод вызываемый при чтении содержимого ячейки

//может быть использован при реализации «ленивых» Т-функций

void (*onWrite)(Cell*); // Метод, вызываемый при записи в ячейку, может быть использован для синхронизации доступа к содержимому ячейки (также как и onRead).

};

// Supercell (Supermatrix unit)

template <TransportHandler& handler>

class SCell : public Cell, public SRef {

public:

SCell<handler> *clnk; // Сервисное поле, используется для поддержки захвата. высвобождения ячеек суперпамяти (провязывание в списки)

long long seqNo; // Последовательный номер версии ячейки

// Master-accessed, (имеют смысл в отраженных ячейках на мастер-узле)

unsigned mstRq:1; // признак запроса на чтение, выставляемый на узле-хозяине

unsigned mstDone:1;// признак , что данные из ячейки были переданы данному узлу

unsigned mstReady:1;// данные готовы для чтения данным узлом (произошла запись со времени последнего считывания)

// Slave-accessed

unsigned slvRq:1; // признак запроса на чтение на запрашивающем узле

unsigned slvReady:1; // признак , что данные считаны с мастер-узла

Общие (широковещательные) ячейки

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

Особенности используемого алгоритма распределенной сборки мусора

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

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