Размещено на http://www.allbest.ru/

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

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

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

АННОТАЦИЯ

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

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Узел-1	Узел-2	Узел-3	Узел-4	Узел-5	Узел-7
Мастер область	Отраженная область	Отраженная область	Отраженная область	Отраженная область	Отраженная область	Адресное пространство
Отраженная область	Мастер область	Отраженная область	Отраженная область	Отраженная область	Отраженная область
Отраженная область	Отраженная область	Мастер область	Отраженная область	Отраженная область	Отраженная область
Отраженная область	Отраженная область	Отраженная область	Мастер область	Отраженная область	Отраженная область
Отраженная область	Отраженная область	Отраженная область	Отраженная область	Мастер область	Отраженная область
Отраженная область	Отраженная область	Отраженная область	Отраженная область	Отраженная область	Мастер область
«Общие» ячейки

Рисунок 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; // признак , что данные считаны с мастер-узла

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

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

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

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

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

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

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

Нами разработана следующая модификация алгоритма со взвешенными ссылками:

· Во время конструирования дескриптора для объекта данных, исходный вес является максимальным 64-битным числом, а выдаваемый при присваивании вес является максимальным 32-битным. Таким образом, при присваивании на верхнем уровне не удастся исчерпать весь вес при сколько-нибудь реалистичном числе одновременно активных дескрипторов, поскольку при уничтожении вес уничтожаемых дескрипторов прибавляется к весу породившего их дескриптора.

· При копировании дескриптора, копии дескриптора передаётся не половина, как в классической схеме, а корень квадратный от веса копируемого дескриптора. Эта схема обладает качественно теми же характеристиками при копировании всё более далёких потомков дескрипторов, но выгодно отличается в случае порождении итеративного копирования дескрипторов в цикле. Такая стратегия должна иметь преимущества при преобладании циклов над рекурсивными вызовами, что, как мы полагаем, верно, для вычислительных задач, особенно первоначально реализованных на императивных языках (С, С++, Фортран).

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

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

В новой версии Т-системы - openTS - выделены три уровня параметризованных классов:

T-уровень, инкапсулирующий семантику переменных с многократным присваиванием.

M-уровень. На М-уровне реализованы абстракции мобильных объектов (со счётчиком ссылок), потоков . Кроме этого на этом уровне реализованы операции захвата (блокирования), и ожидания заблокированной ячейки суперпамяти.

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

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

Листинг 2

template <typename type>

class MRef : protected DRCRef {

public:

int cellOffset;// При пересылке данных по сети будет передано содержимое объекта класса MRef , значение cellOffset номер ячейки суперпамяти, в которое должен быть записан объект, полученный по сети.

long long seqNo;// номер версии объекта , идентифицирует значение в ячейке совместно с cellOffset

// Mobile object

template <typename type>

class MObj : public SCell<dataHandler>, public ThrH, public DRCObj {

public:

long long owner; // 0 или идентификатор задачи, заблокировавшего данную ячейку

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

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

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

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

Таким образом, величины могут быть

§ Горячими Неготовыми

§ Горячими Готовыми

§ Холодными Неготовыми

§ Холодными Готовыми

Одна неготовая величина может быть присвоена другой до того момента, как величина-источник получит реальное значение (станет готовой). Операция присваивание неготовых величин реализуется при помощи дополнительного списка: к каждой неопределенной величине может быть привязан список присвоенных ей неготовых величин. Неопределенна величина - не провязана в список ожидания никакой другой неготовой величины. Определённой называется величина, либо имеющая реальное значение, либо провязанная в списке ожидания у неопределённой величины.

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

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

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

Листинг 3

/* TObj - наследует класс MObj, добавляя специфические для Т-системы свойства */

template <typename type>

class TObj : public MObj<type>, public Ring /* Список ожидающих определённости Т-величин от данной Т-величины*/!

{

public:

TObj<type>* dropTo; // Только для горячих величин, ссылка на Т-величину ожидающую «охлаждения» данной величины

int dropSeqNo; // Только для горячих величин, последовательный номер dropTo, по увеличению dropSeqNo можно понять, что охлаждённые данные больше не нужны

TDsc<type> asnFrom; // Ссылка на неопределённую величину, которую мы ожидаем.

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

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

В настоящее время, Суперпамять реализована при помощи подмножества функций стандарта MPI 1.2: MPI_Isend, MPI_Iprobe, MPI_Recv, MPI_Test, MPI_Wait.

Возможности MPI-2 в части односторонних пересылок (One-Sided-Communications) дают новые возможности для повышения производительности Суперпамяти. Поддержка MPI-2 сейчас имеется во всех перспективных реализациях MPI (в частности, LAM, MP-MPICH, MPICH-2).

По ссылке http://t-system2.polnet.botik.ru/misc можно найти рабочие материалы по Т-Суперструктуре и Т-системе с открытой архитектурой (OpenTS)

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

Предполагается, что в мета-кластерных решениях потребуется расширение адресного пространства «суперпамяти».

В этом случае предполагается использовать тип long long вместо long для номера ячейки суперпамяти.

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

Старшие 2 байта будут использоваться как номер в массиве сегментов (рис. 2).



Рисунок 2. Расширение адресного пространства суперпамяти

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

1) сравнение номера сегмента с номером локального сегмента - возвращается адрес в локальном сегменте в случае совпадения.

2) вычисление адреса в массиве указателей сегментов. Неинициализированные элементы массива (сегменты, к которым ни разу не обращались), содержат NULL.

Очевидно, что все ячейки, находящиеся в не-локальных сегментах суперпамяти являются отраженными (или slave) ячейками.

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

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

Данная работа выполнена в рамках следующих проектов:

§ проекта «Функционально-Ориентированные T-Суперструктуры как Эффективное средство для построение высокопроизводительных распределённых приложений и сервисов» по теме:«Разработка фундаментальных основ создания научной распределенной информационно-вычислительной среды на основе технологий GRID» Программы фундаментальных научных исследований ОИТВС РАН «Оптимизация вычислительных архитектур под конкретные классы задач, информационная безопасность сетевых технологий», номер регистрации: № 10002-251/П-21/101-111/270603-934

§ проекта «Разработка и реализация языков Т# и Т++ и соответствующих им средств для эффективной поддержки высокопроизводительного параллельного счёта» по теме: «Высокопроизводительные вычислительные системы, основанные на принципиально новых методах организации вычислительных процессов» номер регистрации: № 10002-251/ОИТВС-04/103-111/260503-200 а также по программе «СКИФ» Союзного государства.

Размещено на Allbest.ru