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