Google:
Помощь

OpenTS. Руководство программиста

Содержание

1. Назначение программы
1.1. Назначение
1.2. Условия применения
2. Характеристика программы
2.1. Программа и параллельный алгоритм
2.2. Особенности функционального подхода к распараллеливанию
2.3. Примеры программ
2.3.1. Числа Фибоначчи
2.3.2. Краткая характеристика языка Т++
2.3.3. Рекурсивный обход дерева
2.4. Разработка программ на языке T++
2.5. Особенности реализации в различных операционных системах
2.5.1. OpenTS для Windows
2.5.1.1. Платформа Windows Compute Cluster Server
2.5.1.2. Инсталлятор
2.5.1.3. Набор для разработчика (SDK)
2.5.1.4. Интеграция с Visual Studio 2005
2.5.1.5. Сборка T-приложений
2.6. Особенности организации параллельных вычислений при помощи Т- системы
2.7. Программное обеспечение Т-системы и дополнительные возможности
2.7.1. Компилятор языка Т++
2.7.2. Архитектура ядра Т-системы
2.8. Сервисные возможности Т-системы
2.9. Алгоритм поддержки общей памяти
2.9.1. Решения, использованные при построении Суперпамяти
2.9.2. Описание архитектуры и программной реализации Суперпамяти
2.9.3. Передача значений с узла на узел
2.9.4. Алгоритм работы сборщика программного мусора
2.9.5. Операции присваивания и «замораживания» неготовых величин
2.9.6. Возможное расширение адресного пространства суперпамяти для поддержки распределенных вычислительных сетей
2.10. Планирование в OpenTS
2.10.1. Постановка задачи
2.10.2. Алгоритм планирования
2.11. Метапланировщик OpenTS
2.12. Поддержка отказоустойчивости исполнения Т-приложений
2.12.1. Неготовые значения и незавершенные по причине сбоя вычисления
2.12.2. Вектор перерождений
2.12.3. Вектор посещений
2.12.4. Классы повреждений Т-функции в случае сбоя
3. Обращение к программе
3.1. Интерфейсы C++
3.2. Пример программы, использующей суперпотоки (уровень S)
3.3. Использование Т-структур и массивов переменного размера
3.4. Описание классов реализации системы OpenTS
3.4.1. Уровень суперпамяти и суперпотоков
3.4.2. Уровень мобильных объектов, мобильных ссылок и мобильных заданий
3.4.3. Уровень поддержки Т-семантики
3.4.4. Сервисные классы
3.5. Опции конвертера t++
3.6. Определение Т-контекста во время исполнения программы
4. Сообщения
4.1. Цветовая схема
4.2. Сообщения о фатальных ошибках
4.3. Информационные сообщения
Приложение A. Пример вставки и замены листьев в дереве.
Приложение B. Использование динамического массива.
Приложение C. Класс для представления строк в Т-системе.
Приложение D. Многомерный Т-массив.

1. Назначение программы

1.1. Назначение

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

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

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

В то же время тела функций могут быть описаны в императивном стиле (на языках типа FORTRAN, C и т. п.). Важно только, чтобы:

  • всю информацию извне функция получала только через свои аргументы;

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

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

1.2. Условия применения

Для использования ПО Т-система в принципе подходит любая программно-аппаратная платформа, удовлетворяющая следующим требованиям:

SMP-компьютер, кластер или мета-кластер с процессорами одной из следующих архитектур:

  • Intel или AMD IA-32;

  • Intel или AMD x86-64;

  • PowerPC или PowerPC-64;

  • ОС Linux, ядро не ниже 2.4.20 (лучше 2.6).

  • Windows Compute Cluster Server.

Коммуникационная среда MPI одного из следующих видов:

  • LAM;

  • MPICH;

  • MP-MPICH;

  • SCALI;

  • MPICH-G2;

  • MPICH-GM;

  • PACX (MetaMPICH);

  • PVM;

  • MVAPICH;

  • MS MPI.

2. Характеристика программы

2.1. Программа и параллельный алгоритм

Все современные технологии распараллеливания призваны автоматизировать переход от программы, записанной на языке, удобном для человека, к параллельному алгоритму, который при соответствующей аппаратной поддержке позволяет получить выигрыш в производительности по сравнению с последовательным выполнением аналогичной программы на монопроцессоре. В силу сложности этой задачи, на пути распараллевания возникают те или иные проблемы, и никем пока не предложен универсальный способ для их решения. Различные подходы разнятся своими ключевыми идеями, которые в совокупности и обуславливают сильные и слабые стороны каждой конкретной технологии, и как следствие этого, имеют ту или иную область своего эффективного применения. Наиболее характерной чертой Т-системы является использование парадигмы функционального программирования для обеспечения динамического распараллеливания программ. При этом в Т-системе найдены и реализованы весьма эффективные формы как для собственно организации параллельного счета (синхронизация, распределение нагрузки), так и для сочетания функционального стиля с императивными языками программирования (в Т-системе используется гладкое расширение привычных для большинства программистов языков C, C++, Fortran). Наиболее явно преимущества Т-системы проявляются на задачах, в которых:

  • априорно (до начала счета) неизвестно, как распараллелить работу;

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

2.2. Особенности функционального подхода к распараллеливанию

Как известно из общей теории функционального программирования, базирующейся на лямбда-исчислении, окончательный результат редукции (вычисления) лямбда-выражения не зависит от порядка редукции (вычисления) входящих в него редексов (подвыражений). Это дает прямой и вполне очевидный метод для распараллеливания чисто функциональных программ, то есть программ, построенных из «чистых» функций без сторонних эффектов: нужно в каждый момент времени выделять готовые к вычислению подвыражения и распределять их по имеющимся процессорам. Проследим за тем, каким образом отправляясь от этой (довольно-таки простой) идеи можно получить полноценную среду для динамического распараллеливания программ. Прежде всего, нужно найти эффективное представление в оперативной памяти мультикомпьютера для функциональных выражений, то есть эффективное представление для набора вида «функция, ссылки на аргументы». Поскольку сейчас повсеместно используются адресные компьютеры, то за основу для такого представления естественно взять граф, узлы которого представляют вызванные функции, а ребра представляют собой отношение «подвыражение-выражение» (или, в терминологии функционально-потоковых схем, отношение «поставщик-потребитель»). Далее, необходимо реализовать эффективную схему распределения готовых к исполнению гранул параллелизма, которыми здесь и являются наборы «функция, ссылки на аргументы» по процессорам мультикомпьютера, обеспечить доставку данных по высокоскоростным коммуникациям и корректное разделение данных в пределах каждого SMP-вычислителя. Разумеется, нужно также обеспечить начальное преобразование исходного текста программы с целью получения вышеупомянутого графа в момент запуска. Дальнейшее преобразование (автотрансформация) графа будет производиться в процессе параллельного счета. Оказывается, что достаточно ввести в императивный язык программирования (например, в язык C++) понятие неготового значения, введя дополнительное ключевое слово (например, tval) в качестве необязательного атрибута переменных, и функциональная семантика легко и ненавязчиво для программиста проникает в программный код. Еще небольшое число ключевых слов потребуется для необязательных атрибутов, обозначающих:

  • tfun— Т-функции, то есть функции без побочных эффектов, вызовы которых можно вычислять параллельно;

  • tout— выход Т-функции (аргумент, для возвращения посчитанного значения);

  • и др. (подробнее см. документ “Описание языка T++”).

Диалект, полученный из языка C++ добавлением указанных ключевых слов, будем называть языком T++. Язык Т++ позволяет использовать привычную для многих императивную нотацию для записи программ в функциональном стиле. Кроме того, он позволяет получить весьма простой способ начальной трансформации программы в вычислительный граф.

2.3. Примеры программ

Для того чтобы ознакомиться с базовыми конструкциями Т-системы и языка T++, рассмотриваются два простых примера: числа Фибоначчи и рекурсивный обход древовидной структуры данных.

2.3.1. Числа Фибоначчи

На рис. 1 представлена программа вычисления n-ого числа Фибоначчи. Вычисление намеренно реализовано не самым оптимальным образом — при помощи «прямолинейного» кодирования известного рекурсивного определение для чисел Фибоначчи.

Вызовы Т-функций fib (строки 9, 15) являются новой гранулой параллелизма, готовой к вычислению. Они помещается в очередь, откуда локальные вычислительные процессы- исполнители (работающие на каждом вычислительном узле кластера, в количестве, равном числу процессоров в этом SMP узле) черпают работу сначала для себя, а затем (в случае полной локальной загрузки) и для других свободных вычислительных процессов в кластере. Обращение к неготовым переменным на чтение (за значением) блокирует процесс вычисления функции. Неготовые переменные, таким образом, являются средством синхронизации и посредниками при создании новых узлов редуцируемого вычислительного графа. Существенно различаются ситуации обращения к неготовым переменным на чтение (доступ за значением) и на запись (доступ для присваивания):

#include <stdio.h>
#include <stdlib.h>

tfun int fib (int n) {
  return n < 2 ? n : fib(n-1) + fib(n-2);
}

tfun int main (int argc, char *argv[]) {
  if (argc != 2) { printf("Usage: fib <n>\n"); return 1; }
  int n = atoi(argv[1]);
  printf("fib(%d) = %d\n", n, (int)fib(n));
  return 0;
}

     Рис. 1. Программа вычисления чисел Фибоначчи
        

При компиляции этой программы конверером t++ со специальной опцией -auto-c-call достигается скорость вычислений, практически одинаковая с со скоростью C-версии (откомпилированной обычным компилятором без Т-системы) за счет автоматического перехода на вызовы С-версий Т-функций при большой глубине вызовов. Но при этом Т- версия хорошо масштабируется на несколько десятков вычислительных узлов.

Компиляция программы осуществляется при помощи либо конвертера (t++) либо компилятора tg++. В нашем примере используется конвертер:

t++ -o fib fib.tcc

Запуск программы, в общем случае, осуществляется при помощи стандартных средств запуска параллельных приложений, например, в случае SCALI MPI:

mpirun –np 4 ./fib

Возможен также и запуск приложения в режиме монопроцессора, например, при отладке:

./fib

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

2.3.2. Краткая характеристика языка Т++

На примере программы вычисления чисел Фибоначчи мы познакомились с языком Т++ — входным языком Т-системы. Язык T++ разработан как синтаксически и семантически гладкое расширение языка C. Под «гладкостью» здесь понимается то, что дополнительные конструкции синтаксически и семантически увязаны с конструкциями основного языка C.

Явные параллельные конструкции, понимаемые в привычном смысле, в языке T++ отсутствуют, например, программист не указывает, какие части программы следует выполнять параллельно. Т-функции указывают прототипы (шаблоны) возможных гранул параллелизма— реально гранулы параллелизма возникают и обрабатываются Т-системой во время работы программы, во время вызовов Т-функций. Указаниями для организации параллельного счета являются элементы расширения синтаксиса и семантики языка, которые наиболее адекватно отражают архитектуру, функциональность и назначение Т-системы, а также зависимости по данным между отдельными счетными гранулами. Ключевые слова языка T++ и используемые специфические функции и макроопределения, свойственные языку T++, перечислены и описаны в документации языка T++. Набор таких ключевых слов невелик, и освоить его не составит труда для любого программиста, привыкшего к написанию программ на языке C++. Основные ключевые слова языка T++, описывающие основные типы данных языка, реализованы как шаблоны, написанные на языке C++, например:

  • ключевое слово tval реализовано как шаблонный класс TVar<...> языка C++;

  • ключевое слово tptr реализовано как шаблонный класс TPtr<...> языка C++. Данное ключевое слово употребляется для описания удаленного указателя, то есть указателя, который содержит в себе не только информацию об адресе в памяти, но и номер вычислительного узла кластера, для которого указывается этот адрес;

Параметризованные классы (шаблоны), определяемые Т-системой, можно непосредственно использовать в коде на языке C++, например, если требуется распараллелить программный модуль, реализованный на языке C++.

Имеется возможность последовательного исполнения программ на языке Т++.

Добавленные в язык С расширения выглядят достаточно прозрачными для синтаксиса и семантики языка C. Это позволяет программу на языке T++ разрабатывать и отлаживать без использования Т-системы. Для этого достаточно использовать специальный заголовочный файл txx, который переопределяет (с помощью макроопределений) все ключевые слова, добавленные в язык C. Таким образом Т++ программу можно компилировать обычными компиляторами С, выполнять в последовательном (однопроцессорном) режиме и отлаживать, используя штатные однопроцессорные средства отладки. Данное свойство упрощает первый этап цикла разработки программ, позволяя отлаживать последовательные части реализованного функционального алгоритма в наиболее удобной, привычной для программиста среде.

2.3.3. Рекурсивный обход дерева

Рассмотрим программу рекурсивного обхода дерева (рис. 2), написанную на языке Т++. На этом примере мы продемонстрируем работу с удаленными (tptr) указателями.

#include <stdio.h>
#include <stdlib.h>

typedef struct tree {
    tree tptr left;
    tree tptr right;
    int value;
} tree;

tfun ts::TPtr<tree> create_tree(int depth) {
    tree tptr res = new tval tree;
    res->value = 1;
    if (depth <= 1) {
        res->left = NULL;
        res->right = NULL;
    } else {
        res->left = create_tree(depth-1);
        res->right = create_tree(depth-1);
    }
    return res;
}

tfun int tsum(tree tptr _tree) {
    tval int leftSum, rightSum;

    if (_tree->left) {
        leftSum = tsum(_tree->left);
    } else {
        leftSum = _tree->value;
    }
    if (_tree->right) {
        rightSum = tsum(_tree->right);
    } else {
        rightSum = _tree->value;
    }
    return (int)leftSum + (int)rightSum;
}

tfun int main (int argc, char* argv[]) {
    tree tptr _tree = create_tree(12);
    printf("sum = %d\n", (int)tsum(_tree));
    return 0;
}

          Рис. 2. Программа рекурсивного обхода дерева. Основной код.
        

В этой программе дерево структур с типом tree сначала порождается функцией create_tree, а затем обходится в рекурсивной функции tsum. Точно так же, как и в предыдущей программе, происходит распараллеливание на каждой развилке дерева, поскольку сначала порождаются вызовы для левой и правой ветви, и лишь затем происходит обращение к результатам обхода. Ключевое слово tptr служит для описания глобальных ссылок на неготовые переменные. При операции чтения данных по Т-указателю может происходить ожидание готовности результата и (если нужно) его подгрузка из других узлов кластера, в то время как при операции записи записываемое значение (если нужно) передается по сети в нужный узел кластера, там значение записывается в переменную и, тем самым, соответствующую Т-переменную делает готовой.

2.4. Разработка программ на языке T++

Имеющаяся практика реализации программ для Т-системы позволяет рекомендовать организацию разработки программ на языке T++ из следующих этапов:

  1. Разработка алгоритма. Верхний уровень алгоритма разрабатывается на базе парадигмы функционального программирования.

  2. Разработка кода. При этом решается вопрос о том, какие фрагменты алгоритма, какая часть кода будет реализована на языке T++ в виде Т-функций, а какая часть—реализована в виде привычного последовательно исполняемого кода на стандартных языках последовательного программирования: С, С++, Фортран.

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

  4. Отладка на многопроцессорных установках. После отладки Т++-программы на однопроцессорном компьютере (в последовательном режиме), ее рекомендуется затем отладить на одиночном SMP- компьютере, а затем — на кластере.

  5. Тьюнинг. После отладки, при помощи трассировок и профилировок производится различного рода оптимизация кода.

2.5. Особенности реализации в различных операционных системах

2.5.1. OpenTS для Windows

2.5.1.1. Платформа Windows Compute Cluster Server

Платформа WCCS состоит из двух компонентов:

  • Операционная система Windows Compute Cluster Server 2003, которая базируется на ядре ОС Windows Server 2003 Standard x64 Edition и поддерживает только 64-разрядные аппаратные платформы (но некоторые компоненты, например, MS-MPI, способны работать и в 32-разрядных ОС Windows);

  • набор кластерных решений Compute Cluster Pack (CCP), содержащий все необходимые программные компоненты для создания, использования и управления кластерной инфраструктурой.

Стоимость ОС Windows CCS 2003 ниже, чем у любого другого издания Windows Server 2003.

Кластер под управлением WCCS состоит из одного главного и любого числа вычислительных узлов, связанных высокоскоростной сетью. Главный узел также может выполнять роль вычислительного узла. Вычислительные задачи можно передавать на кластер через приложение Compute Cluster Job Manager, а мониторинг и управление кластером осуществляются с помощью инструмента Compute Cluster Administrator. Оба инструмента поставляются вместе с CCP. Для подачи заданий можно также использовать интерфейс командной строки (Command-Line Interface, CLI). Для развертывания узлов можно использовать службу удаленной установки (Remote Installation Services, RIS), которая поставляется вместе с ОС Windows CCS 2003.

Для разработки параллельных приложений корпорация Microsoft выпустила собственную реализацию стандарта MPI — MS-MPI. Она основана на MPICH2, открытой реализации стандарта MPI 2.0. Это дает возможность независимым производителям ПО легко портировать свои продукты на WCCS.

2.5.1.2. Инсталлятор

Инсталлятор OpenTS для Windows имеет следующие отличительные особенности:

  1. Поддерживает аппаратные платформы AMD64 и x86.

  2. Включает в себя Compute Cluster Pack SDK и инсталлирует его в случае его отсутствия в системе пользователя.

  3. Проверяет работоспособность OpenTS сразу после процедуры инсталляции. Проверка проходит в несколько этапов:

    1. сборка простой T-программы;

    2. запуск программы;

    3. проверка результата;

    4. отправка разработчикам сообщения об ошибках в случае неудачного тестирования или некорректности результата.

  4. Инсталлятор также интегрирует OpenTS со средой разработки Visual Studio 2005 любого издания. Это позволяет разрабатывать и отлаживать Т-приложения в этой среде.

2.5.1.3. Набор для разработчика (SDK)

Набор для разработчика системы OpenTS предоставляет следующие возможности:

  • сборка микроядра — возможность делать правки и пересобирать микроядро из его исходных кодов;

  • сборка расширений для микроядра — это позволит совершенствовать OpenTS добавлением в нее расширений; примеры уже имеющихся расширений — DMPI (Dynamic MPI), WAD (Wide Area Debugger), VisTrace (журналирование работы Т­программы);

  • сборка Т-приложений — инструменты из стандартного дистрибутива OpenTS. Кроме того, в набор включены примеры простых Т-программ.

Для использования каждой возможности в дистрибутив OpenTS SDK включены проекты формата Visual Studio 2005 (файлы .vcproj), с которыми можно работать в среде разработки Visual Studio 2005.

2.5.1.4. Интеграция с Visual Studio 2005

Суть интеграции OpenTS с Visual Studio 2005 состоит в следующем: в диалоговом окне при добавлении нового проекта появляется новый элемент "OpenTS console application", позволяющий создать проект консольного приложения на языке Т++.

Также, в диалоговом окне добавления в проект нового файла появляется элемент "T++ file". Это даёт возможность добавления в текущий проект новых исходных файлов на языке Т++.

В процессе сборки Т-приложения в среде Visual Studio 2005 к каждому исходному файлу на языке Т++ применяется особое правило сборки ("%ProgramFiles%\Microsoft Visual Studio 8\VC\VCProjectDefaults\opents.rules"), которое использует командный файл "t++.bat". Объектные модули, полученные в результате применения этого правила, затем компонуются с некоторыми другими статическими библиотеками, в результате чего получается исполняемый файл Т-приложения.

2.5.1.5. Сборка T-приложений

В меню "Старт"-"Все программы"-"OpenTS" есть несколько ссылок для открытия терминала OpenTS. Используя этот терминал, можно создавать Т-приложения с помощью командной строки. Командный файл t++.bat используется для разработки Т-приложений в режиме командной строки. Его синтаксис: t++ [опции] файл1 ... файлN. Список его возможных опций:

  • /auto-c-call - позволяет Т-приложению вызывать Си-версии Т-функций. В некоторых случаях это может улучшить производительность приложения;

  • /c - режим компиляции исходных файлов без компоновки;

  • /dbg - отладочная сборка. Она позволит отладчику получить информацию о символах программы в случае ошибки при работе Т-приложения;

  • /do - позволяет указать расположение объектных модулей;

  • /not - способ сборки приложения, при котором все ключевые слова языка Т++ игнорируются;

  • /o - указывает имя выходного файла;

  • /p - позволяет указать дополнительные опции компилятору Cи/Cи++;

  • /v - печать команд перед их вызовом;

Т-приложения могут быть запущены тремя способами:

  1. В монопроцессорном режиме:

  2. Локально в параллельном режиме, используя mpiexec:

  3. На кластере, используя приложение Cluster Job Submission and Monitoring Console, которое поставляется вместе с Compute Cluster Pack:

2.6. Особенности организации параллельных вычислений при помощи Т- системы

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

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

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

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

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

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

2.7. Программное обеспечение Т-системы и дополнительные возможности

В состав программного обеспечения Т-системы входят

  • компилятор языка Т++;

  • ядро Т-системы;

  • программы поддержки сервисных возможностей (профилирование, трассировка, повторение трассы, отладка).

2.7.1. Компилятор языка Т++

Для построения компиляторов языка T++ в настоящее время используется две технологии. Первая основана на технологии конвертирования языковых расширений C++ с помощью технологии OpenC++, вторая использует инфраструктуру компилятора GCC, в который добавляется языковой фронтенд для языка T++.

К достоинствам первой технологии можно отнести относительную простоту, возможность контролировать ход трансляции, рассматривая листинг конвертированной T++-программы. При этом также возможно применение различных компиляторов для обработки конвертированного кода (в частности, оптимизирующего компилятора фирмы Intel). К временным недостаткам следует отнести отсутствие поддержки некоторых специфических языковых конструкций C/C++.

Достоинствами второй технологии является прямая интеграция с компилятором GCC [36]: после обработки специфических конструкций языка T++ итоговая программная структура обрабатывается стандартным для GCC образом. Кроме этого, автоматически обеспечивается поддержка всех специфических для GCC языковых конструкций. К недостаткам данного метода создания Т++ компилятора относится привязанность к компилятору GCC. Таким образом, этот подход неудобен для распространения OpenTS, поскольку в дистрибутив системы необходимо включать модифицированный дистрибутив GCC.

В обеих реализациях программа в некоторый момент времени преобразуется в семантически эквивалентную ей C++-программу, в которую добавлены соответствующие операторы и определения из заголовочного файла txx (конвенции компиляции для языка T++) и trt (T-runtime). Дальнейшее обеспечение семантики конструкций языка T++ обеспечивается средой исполнения (библиотека libtrt).

OpenC++ — это инструмент для лексического анализа и трансляции исходных кодов C/C++-программ. В нем используется протокол метаобъектов (metaobject protocol (MOP)) [37], который позволяет создавать расширения языка C++. Программа, в которой используется OpenC++, является метапрограммой, в которой описывается, каким образом следует компилировать или анализировать исходные коды программ на C++. Метапрограмма пишется на C++ и в ней описывается некоторое небольшое количество классов. Затем метапрограмма компилируется компилятором OpenC++. Результатом компиляции является динамическая библиотека, которая в дальнейшем используется как подключаемый модуль OpenC++ для компиляции расширений языка C++. Метапрограмма написана с использованием программного интерфейса MOP. В процессе синтаксического разбора части исходного кода программы представляются в виде дерева с использованием метаобъекта Ptree.

Было решено для постоянного развития OpenTS использовать Т++ компилятор на основе системы OpenC++, поскольку такой выбор обеспечивает программную независимость от операционной системы и компилятора C/C++, и не создает препятствий для распространения системы OpenTS.

2.7.2. Архитектура ядра Т-системы

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

Данная версия версия Т-системы основывается на вполне стройной математической модели и детально проработанной архитектуре программного обеспечения, что (по сравнению с предыдущей реализацией) позволило существенно уменьшить сложность кода и упростить введение полезных расширений. Как уже упоминалось выше, наиболее эффективным представление функциональных выражений в памяти адресных машин является представление в виде графа. Процесс редукции (вычисления) для случая такого представления называется параллельной редукцией графов и является одним из наиболее эффективных из используемых на практике методов реализации функциональных языков программирования. В своей классической форме алгоритмы параллельной редукции графов создавались и реализовывались для SMP-вычислителей, и поэтому их прямые реализации на мультикомпьютерах современной архитектуры (MMP, кластеры) оказывались не так эффективны на практике, как хотелось бы. Работы над данной версией Т-системы были начаты с построения расширения схемы параллельной редукции графов путем введения в нее понятия кластерного уровня. Кратко это выглядит следующим образом. Состоянием параллельной программы является совокупности всех ее данных, находящихся на узлах кластера. Процесс параллельного вычисления является процессом изменения состояния программы и, в случае параллельной реализации редукции графа, этот процесс определяется параллельными потоками преобразований графа. Разобьем все преобразования на три класса по следующим признакам:

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

  • Стратегии, которые совершают эквивалентные преобразования графа, призванные повысить эффективность вычислений;

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

Указанные три класса преобразований отвечают трем уровням в организации ядра Т- системы:

  • SMP-вычислитель;

  • демоны стратегий и их поддержка;

  • коммуникационный уровень Т-системы.

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

  • за несколько машинных команд определить, что простаивающих процессоров в кластере нет;

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

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

Вычисление функций-пересылок (преобразования класса 3) осуществляется коммуникационным уровнем Т-системы. В свою очередь коммуникационный уровень Т- системы написан с использованием библиотеки MPI.

2.8. Сервисные возможности Т-системы

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

  1. Мемоизация Т-функций. В данной версии Т-системы реализована глобальная мемоизация (табулирование) результатов вычисленных некоторых (задается программистом) Т-функций. При этом перед началом вычисления мемоизуемой Т-функции проверяется, не хранится ли в глобальной мемо-таблице ранее вычисленное значение данной функции на данных значениях аргументов. Если в поиск в таблице оказывается успешным, то вместо повторного вычисления функции извлекается из мемо-таблицы ранее посчитанный результат. Мемоизация функций широко используется в функциональном программировании.

  2. Возможность использования готовых библиотек параллельных алгоритмов. В данной версии Т-системы появилась возможность интеграции программы на языке Т++ и ранее разработанных статически распараллеленных вычислительных алгоритмов. Здесь в первую очередь имеется в виду возможность использовать в программах на языке T++ функций из таких MPI библиотек параллельных алгоритмов, таких как ScaLAPACK, ATLAS, Cactus, MODULEF и пр.

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

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

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

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

    Данные режимы позволяют изучать порядок параллельного выполнения Т-программ (что полезно на этапе тьюнинга) и обеспечивать точную повторяемость порядка параллельного вычисления Т-программ (что важно на этапе параллельной отладки).

  5. Check pointing. В данной версии Т-системы реализуется режим автоматического сохранения состояния Т-программы во вторичную память (checkpointing) и возобновления сохраненного состояния.

2.9. Алгоритм поддержки общей памяти

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

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

Общая память позволяет существенно упростить создание параллельных программ на императивных языках за счет использования для обмена между параллельными процессами общих переменных, массивов, структур, областей памяти. Как известно, существуют различные схемы организации общей памяти в распределенных системах. Некоторые из них напрямую отображают виртуальное адресное пространство на области памяти локальных узлов. Наряду с простотой, такие схемы обладают определенными недостатками. Прежде всего, единицей работы с памятью в такой схеме является аппаратная страница, что замедляет работу с совокупностями небольших по размеру объектов. На 32-разрядной архитектуре пределом совокупного объема данных оказывается 4 Гб, что по современным меркам выглядит достаточно серьезным ограничением, особенно в суперкомпьютерных применениях. Этих недостатков лишены схемы так называемой объектно-ориентированной общей памяти, где единицей адресации является не аппаратная страница а объект. Перекладывая часть работы на программное обеспечение, удается достичь снятия указанных ограничений. Дополнительно, такая схема организации памяти может быть легко интегрирована с различными аспектами объектно-ориентированных технологий, такими как автоматическая сборка мусора. Более того, объект — ячейка общей памяти — может играть разные роли в иерархии классов приложения. Например, можно предусмотреть вызовы определенных методов при записи и чтении ячейки. Т-система, являясь расширением модели вычислений традиционных языков, таких как С, С++, Фортран, предоставляет в распоряжение программиста новое понятие «неготовой величины», служащих для синхронизации между процессами-«поставщиками» и процессами-«потребителями». Использование обычной общей памяти не позволяет адекватно отразить семантику неготовых величин. Описанная в данной работе схема организации общей памяти первоначально возникла как часть новой технологии построения Т-системы — системы автоматического динамического распараллеливания вычислений на основе функционально-ориентированного расширения языка С++.

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

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

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

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

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

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

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

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

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

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

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

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

Табл. 1 Структура матрицы суперпамяти

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

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

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

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

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

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

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

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

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

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

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

2.9.4. Алгоритм работы сборщика программного мусора

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

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

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

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

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

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

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

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

  • Горячими неготовыми

  • Горячими готовыми

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

  • Холодными готовыми

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

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

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

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

2.9.6. Возможное расширение адресного пространства суперпамяти для поддержки распределенных вычислительных сетей

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

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

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

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

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

  • сравнение номера сегмента с номером локального сегмента — возвращается адрес в локальном сегменте в случае совпадения;

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

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

2.10. Планирование в OpenTS

Задача планировщика заключается в том, чтобы свести к минимуму время исполнения программы. Это означает, что в каждый момент времени каждый узел кластера занят какой-то работой. Узел простаивает, если его очередь пренатальных задач (ptq) пуста, а все исполняемые задачи находятся в ожидании ресурсов. Таким образом, главная задача планировщика — обеспечить наличие задач в очереди на каждом узле [43].

2.10.1. Постановка задачи

Имеется вычислительная система, состоящая из N узлов. На каждом узле есть множество задач. Задачи делятся на пренатальные и исполняемые (непренатальные). Пренатальные задачи могут перемещаться между узлами кластера, исполняемые — нет. Исполняемые задачи, в свою очередь, делятся на следующие:

  • ожидающие неготового значения;

  • готовые к исполнению (ожидающие процессорного времени).

Планировщик может предпринимать следующие действия:

  • переслать одну или несколько пренатальных задач на другие узлы;

  • продолжить одну из исполняемых задач;

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

Исполняемые задачи могут порождать новые пренатальные задачи. Их количество заранее неизвестно и не зависит от действий планировщика. Задача планировщика — минимизировать общее время исполнения программы.

2.10.2. Алгоритм планирования

Каждый раз, когда планировщик получает управление, он производит следующие действия:

  • пересылку части пренатальных задач на другие узлы кластера;

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

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

С каждой задачей связывается набор из N+1 числа, характеризующий

  • вычислительную сложность задачи (1 значение);

  • создаваемую нагрузку на коммуникационные каналы (N значений, по одному для каждого узла).

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

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

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

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

Таким образом, каждый узел имеет информацию T1,T2,...,TN о состоянии ptq (очереди пренатальных задач) на всех узлах кластера. В качестве характеристики распределения задач возьмем дисперсию (среднеквадратичное отклонение) этих значений:

Допустим, мы имеем данные T1, T2 и D(T). Рассмотрим эффект от пересылки некоторой задачи с узла 1 на узел 2. Предположим,

где δi зависят от сложности задачи и ее сетевой активности. При этом:

Далее находится D(T') по соответствующей формуле. Таким образом, можно констатировать, что сложность вычисления D(T) не зависит от N.

Планировщик рассматривает всевозможные пересылки задач из своего ptq на другие узлы и выбирает вариант с наименьшим итоговым значением D(T). Разумеется, если нет вариантов, приводящих к уменьшению дисперсии, то пересылок не производится.

От формул для δi существенно зависит поведение планировщика. В простейшем случае они выглядят следующим образом:

где  — сложность задачи, vi — мощность i-го вычислительного узла. Вычислительная сложность задачи вычитается на одном узле и прибавляется на другом. Это дает стратегию планирования, при которой не учитывается состояние коммуникационных каналов. Данная стратегия при определенных условиях может привести к тому, что задачи, пересылаемые с узла на узел, составят существенную часть сетевой нагрузки Т-приложения. Однако, при малой сетевой активности собственно вычислительного алгоритма, излишне большое число пересылок не сказывается на производительности. Добавление в эти формулы зависимости от сетевой активности переносимой задачи также ее размера (с ним связаны затраты на собственно пересылку задачи), например:

где S — размер задачи, r12 — скорость связи между узлами, позволит учесть влияние этих факторов.

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

2.11. Метапланировщик OpenTS

Математическая модель. Пусть имеются два узла с вычислительной мощностью C1 и C2 соответственно. Они связаны коммуникационным каналом с задержкой l и пропускной способностью b. Время пересылки данных объема S по такому каналу составляет .

На узле 1 есть нераспределенная работа общей вычислительной сложности A. Допустим, характер задачи таков, что объем входных и выходных данных, используемых при выполнении части работы, пропорционален ее объему. Другими словами, есть некоторый общий объем данных B, и вычисление части работы сложности A1 требует данных объемом . Практика использования разных версий Т-системы при решении задач механики позволяет утверждать, что многие подобные задачи удовлетворяют этому условию.

Допустим, на узел 2 будет передана работа сложностью A2, соответственно на узле 1 останется работа сложностью . Работа на узле 1 будет выполнена за время

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

Общее время исполнения задачи  как функция от A2 монотонно убывает на [0, A], T2 монотонно возрастает на этом отрезке, T1(0) > T2(0), T1(A) < T2(A). Заметим, что T достигает минимума на [0, A] в точке : , если такое  существует.

 

Действительно, при  имеем:

а при :

Если  не существует то минимум T достигается в точке A2 = 0 из-за разрывности функции T2 в этой точке. Это означает, что связь между узлами настолько медленная, что пересылка любой части работы не имеет смысла, и ее выгоднее выполнить на узле 1. Необходимым и достаточным условием для этого является

или

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

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

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

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

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

2.12. Поддержка отказоустойчивости исполнения Т-приложений

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

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

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

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

Мы будем предполагать, что прикладная программа написана в функциональном стиле, и в случае его расширения прикладной программист так же точно отвечает за отказоустойчивость своей программы при использовании отказоустойчивой OpenTS, как и за простые корректность и детерминированность результатов счета в случае обычной Т-системы.

2.12.1. Неготовые значения и незавершенные по причине сбоя вычисления

С точки зрения прикладного программиста наиболее существенное новшество Т-системы (языка T++) по сравнению с базовым языком (C++) состоит в поддержке Т-функций и неготовых значений. Неготовые значения генерируется Т-функциями, и служат удобными абстракциями, инкапсулирующими синхронизацию и обмен данных между параллельно вычисляющимися функциями-потоками.

Для того чтобы у прикладного программиста появилась возможность самостоятельно принимать решение об обработке сбоев, мы пополним диаграмму состояний неготового значения еще одним состоянием — «незавершенное». Это состояние является альтернативой готовому состоянию и отличается от него следующими ключевыми свойствами:

  • Неготовое значение становится незавершенным, если его вычисление было остановлено вследствие сбоя.

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

  • В случае, когда прикладная программа использует примитив языка T++ twait(), то она получает событие, означающее что величина готова, но вычисление не было завершено. В этом случае она может продолжать счет, предприняв то или иное действие в соответствии с выбранной «заказной» моделью обработки сбоя.

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

2.12.2. Вектор перерождений

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

Если ограничить значение счетчика перерождений некой разумной величиной (например, типом данных int), то можно хранить вектор перерождений в массиве байт (каждый элемент содержит 31 бит на порядковый номер и 1 бит на текущий статус работоспособности).

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

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

2.12.3. Вектор посещений

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

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

2.12.4. Классы повреждений Т-функции в случае сбоя

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

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

  • Полуповрежденные вычисления. Неповрежденные Т-функции, которые были отосланы на другие узлы, и при этом после миграции стали поврежденными, будем назы-вать полуповрежденными. Такие Т-функции нужно запустить на счет заново.

3. Обращение к программе

3.1. Интерфейсы C++

Т-система с открытой архитектурой – средство двойного назначения. Это и высокоуровневое средство для автоматического динамического распараллеливания программ, и библиотека C++-классов и шаблонов, с открытой вертикалью:

  • суперпамять;

  • суперпотоки;

  • динамический выбор супертранспорта;

  • активные сообщения;

  • мобильные задачи/объекты/ссылки;

  • Т-надстройка.

Параметризованные классы (шаблоны), определяемые Т-системой, можно непосредственно использовать в коде на языке C++, (например, если требуется распараллелить программный модуль, реализованный на языке C++).

3.2. Пример программы, использующей суперпотоки (уровень S)

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

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <SDL/SDL.h>
#include <trt>
ts::ThrQ waitq;
void draw(void *pixel) {
  int color = 1;
  while(true) {
    color = color*5 + (int)pixel;
    *(Uint16*)pixel = color;
    //printf("%p : %d\n",&color,color);
    waitq.stopHereAndRunOthers();
  }
}
SDL_Surface *screen;
Uint16 * pixelAddress(int x, int y) {
  if (screen->format->BytesPerPixel != 2) printf("Display depth !=
  16 :-(\n");
  return (Uint16 *)screen->pixels + y*screen->pitch/2 + x;
}
#define XSZ 512
#define YSZ 512
tfun int main(int argc, char *argv[]) {
  printf("Setting video mode\n");
  screen = SDL_SetVideoMode(XSZ, YSZ, 16, SDL_SWSURFACE);
  if (screen == NULL) {
    fprintf(stderr, "Problem setting %dx%d resolution: %s\n", XSZ,
    YSZ, SDL_GetError());
    exit(1);
  }
  printf("Running threads\n");
  int x,y;
  for (x=0; x<XSZ; x++) {
    printf("One cswitch takes %.0f nanoseconds\
    n",ts::tick2Sec(t.finish())*1000000000./(ITER*XSZ*YSZ));
    return 0;
  }
}
      

3.3. Использование Т-структур и массивов переменного размера

Приведенная в приложении A программа показывает пример использования T-структур, а именно, вставка и замена листьев в дереве. Деревья задаются в формате: expr ::= 0 | len (expr_1) ... (expr_{len}). Функция insert вставляет в каждый лист дерева e данное дерево s. А функция subst заменяет каждую ветку, ведущую в лист, на дерево s.

Если сказать: echo "1(0) 2(0)(0)" | ./subst, то программа выдает:
expr: 1 (0)
subst: 2 (0) (0)
after insert: 1 (2 (0) (0))
after subst.insert: 1 (4 (0) (0) (0) (0))

В том случае, если в качестве T-переменной вы хотите использовать массив, не следует использовать обычный массив. Для этого можно использовать класс TArray, экземпляры которого можно использовать как массивы. Он имеет метод resize, с помощью которого можно задать и динамически менять его размерность. Пример использования динамического массива приведен в приложении B.

3.4. Описание классов реализации системы OpenTS

3.4.1. Уровень суперпамяти и суперпотоков

SystemMemoryAllocator – класс, ответственный за выделение памяти

DataAllocator – класс-шаблон для выделения памяти объектам определенного типа FIXME: при оптимизации должен кэшировать!

StackAllocator – класс для выделения памяти для стеков суперпотоков

ThreadAllocator – кэширующий аллокатор суперпотоков

ThrH – заголовочная структура суперпотока

SThread – суперпоток

THInit – инициализация суперпотокового уровня

DestructionQueue – реентерабильная процедура для удаления совокупностей объектов

Header – класс-заголовок для суперданных

SData – класс представления суперданных

SRef – локальная ссылка на суперданные

WTimer – оптимизированная процедура для получения системного времени

MPITagHandler – системный сервис для взаимодействия с подсистемами MPI/DMPI

TransportHandler – системный сервис - транспортная поддержка суперпамяти

VZeroes – виртуальное пространство для суперматрицы, проинициализированное нулями

CachedChunks – класс для кэширующего захвата диапазона ячеек суперпамяти

MasterSCell – базовый класс для представления состояния диагональных (собственных) элементов суперматрицы

SlaveSCell – базовый класс для представления состояния несобственных (отраженных) элементов суперматрицы

SCell – базовый класс для представления ячеек суперпамяти

SPtr – глобальный указатель на ячейку суперпамяти

Data – базовый класс для представления суперданных в виде активных сообщений

DataCell – ячейка суперпамяти, содержащая обычные суперданные

StaticCell – специальная (статическая) ячейка суперпамяти (используется для управляющей информации)

SharedCell – общая (широковещательная) ячейка суперпамяти

DynamicSegment – сегмент суперпамяти

StaticSegment – специальный (статический) сегмент суперпамяти

3.4.2. Уровень мобильных объектов, мобильных ссылок и мобильных заданий

InitControlHandler – класс инициализации статического служебного сегмента (управляющей) суперпамяти

MData – мобильные суперданные с Copy-On-Write-семантикой

MControlData – мобильные суперданные со служебной (управляющей) информацией

DRCObj – база объекта для поддержки распределенной сборки мусора

DRCRef – база указателя для поддержки распределенной сборки мусора

MRef – мобильная ссылка на суперданные

Resource – базовая структура для представления свободных и необходимых ресурсов

FreeResource – класс для представления свободных ресурсов

TaskResource – класс для представления необходимых ресурсов

TaskCtxt – класс представления контектста задачи

Task – класс представления задачи

TaskPrioQueue – приоритетная очередь заданий

MThread – мобильный поток-задача

MObj – класс для представления мобильных объектов с суперданными

MRef – класс для представления мобильных ссылок на мобильные объекты с суперданными

TaskBoard – доска объявлений о наличии/потребности в задачах/свободных ресурсах

MacroScheduler – кооперативный макропланировщик для мобильных заданий

3.4.3. Уровень поддержки Т-семантики

TData – базовый класс для представления суперданных неготовых величин

TDataReady – класс для представления готовых суперданных

TDsc – базовый класс для представления мобильной ссылки на неготовое значение

TObj – класс для представления Т-величин (мобильных Т-обектов, содержащих суперданные)

TDataNotReady – класс для представления неготовых суперданных

TFrz – класс для "замораживания" Т-величин

TPtr – указатель на Т-величину

TVar – Т-переменная

TOut – Т-переменная - выход (или возвращаемый результат) Т-функции

TFun – класс для представления Т-функций

3.4.4. Сервисные классы

Atomic – атомарно изменяемое значение

ACnt – счетчик для атомарно изменяемых значений

ARef – ссылка на счетчик для атомарно изменяемых значений

Spinlock – класс для организации синхронизации системных тредов

String – класс для упрощенной работы со (временными) строками

UserInterface – класс, отвечающий за взаимодействие с Оператором

Viz – базовый класс для визуализации

Ring – класс для представления двухсвязных колец

Service – класс для представления системных сервисных функций FIXME: добавить маскирование

Delay – базовый класс для представления задерженных операций

SContext – часть Т-контектста, соответствующая статической системной конфигурации

TContext – динамическая часть Т-контекста

Prof – базовая поддержка для профилирования заданий

StatisticValues – базовая структура, содержащая статистические величины для заданий

TaskStatistic – статистика для задний

Statistic – структура для представления статистики в контрольной суперпамяти

CmdLine – класс, ответственный за обработку командной строки

Feature – базовый класс для определения расширений Т-ядра

DefaultExceptionHandler – базовый обработчик исключительных ситуаций

TRT – Т-рантайм

MainTRT – Т-рантайм для стартового узла

3.5. Опции конвертера t++

Для вывода списка допустимых опций конвертера t++ можно набрать команду

t++ --help:

На экран будет выведен список поддерживаемых в текущей версии опций:

T++->(C++,TSS) Converter v3.0, 2003-2004, PSI RAS, Russia.
Available options:
-v - print commands before invocation
-icc - compile using Intel icc compiler 
-not - compile for sequential execution
-dbg - compile and link with debug info 
-ltdb - link with "lightweight debugger"
-mdbg - link with "memory debugger"
-opt -do maximal possible optimization 
-auto-c-call - try to call C-versions of tfuns
-static-mpicxx=<mpicxx> - statically link with <mpicxx>
-- xxx - pass "xxx" to used C++ compiler
+xxx -pass "-DWITH_xxx" to used C++ compiler 
      

Поддержка тех или иных опций зависит от установленных расширений Т-системы с открытой архитектурой, а также сторонних продуктов. Так, например, для нормальной работы опции -icc в системе должен быть корректно установлен оптимизирующий компилятор фирмы Интел.

3.6. Определение Т-контекста во время исполнения программы

Во время исполнения программы можно изменять Т-контекст, или совокупность параметров Т-надстройки над стандартной средой исполнения C++.

Вид оператора, изменяющего контекст, определяется в спецификации языка T++. Он имеет вид tct(parameter[(value)]) и действует в пределах блока. Перечень поддерживаемых в данной версии параметров Т-контекста приведен ниже.

tct(magnetic). Создаваемые в пределах блока Т-дескрипторы (Т-переменные и Т-указатели) будут “намагниченными”. Намагниченный дескриптор, будучи переданным на другой узел кластера, влечет за собой автоматическое “притяжение” неготовых данных, на которые он ссылается, в момент их готовности (то есть в будущем). Данная возможность является существенной для спекулятивной подкачки данных, которая может существенно влиять на производительность определенной группы приложений, и является критической для сравнения с другими технологиями распараллеливания.

tct(glue). Создаваемые в пределах блока Т-дескрипторы (Т-переменные и Т-указатели) будут “клейкими”. Клейкий дескриптор, будучи переданным на другой узел кластера, влечет за собой автоматическое “притяжение” неготовых данных, на которые он ссылается, в момент пересылки. Данная возможность является существенной для спекулятивной подкачки данных, которая может существенно влиять на производительность определенной группы приложений, и является критической для сравнения с другими технологиями распараллеливания.

tct(cpuUsage(usage)). Указание Т-системе на тяжесть гранул (Т-функций), которые порождаются в пределах данного блока. Данная информация может использоваться стандартным и внешним планировщиками.

tct(atRank(rank)). Указание на то, что все Т-функции, которые порождены в пределах блока, следует направлять для вычисления на узле с рангом rank.

tct(extraSize(n)). Указание на то, что данные, аллокируемые для ячеек суперпамяти, выделяемых в пределах данного блока, должны содержать n байт неразмеченной памяти дополнительно. Неразмеченная память располагается непосредственно после стандарной структуры данных и трактуется системой как массив байт. Она не должна содержать Т-дескрипторов (Т- переменных и Т-указателей). Техника использования конструкции extraSize морально устарела. Вместо неё мы рекомендуем использовать другие конструкции на основе класса ts::TExtData.

tct(priority(prio)). Определение динамического приоритета порождаемых в пределах данного блока Т- функций.

tct(stackSizeLg(lg)). Определение двоичного логарифма размера стека для порождаемых в пределах данного блока Т-функций.

tct(memoize). Указание на то, что для порождаемых в пределах данного блока Т-функций следует использовать стратегию мемоизации (табулирования)

tct(setLabel(label)). Установка наименования Т-функции (используется при использовании режима отладки).

4. Сообщения

4.1. Цветовая схема

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

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

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

4.2. Сообщения о фатальных ошибках

"Regexp `%s' compilation failed!"

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

”Unknown TCT option %s !"

  • неизвестная опция командной строки (следует за ключом -tct), определяющей начальный Т-контекст времени исполнения

"Internal feature failed"

  • одно из встроенных расширений Т-микроядра не удалось проинициализировать

"Stack overflow"

  • недостаточно памяти для требуемого программой количества суперпотоков

“Threads initialization failed"

  • Ошибка на стадиии инициализации подсистемы поддержки суперпотоков

"Out of memory"

  • недостаточно памяти для программы

“MPI_Error[%d != %d]: %.*s"

  • сбой подсистемы обмены сообщений MPI

"No free MPI_Request (%d tries)"

  • недопустимая задержка в подсистеме коммуникаций

”Out of supermemory"

  • исчерпан лимит ячеек суперпамяти. Необходимо увеличить размер суперматрицы.

“Deadlock detected" - внутреняя ошибка синхронизации.

"Drop or freeze on unitialized T-value!" - Т-функция не проинициализировала один из своих выходных аргументов

4.3. Информационные сообщения

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

“MemoryLeak: ...”

  • в программе осталась неосвобожденная память в момент завершения

“main result is ready and %d TFuns are still working. Memory leaks are possible”

  • в момент завершения головной функции tfun main остались работающие Т-функции.

“Leaked cell %x,%lld with data %s (%d bytes)”

  • в программе осталась неосвобожденная суперпамять в момент завершения

“local memo works”

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

“global memo works”

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

Приложение A. Пример вставки и замены листьев в дереве.

Файл trefal.tcc

#include <iostream>

#define DBG fprintf(stderr,"%d: %d\n",ts::myRank,__LINE__)

using namespace std;

struct Expr;

typedef ts::TVar<Expr> TExpr;

struct Expr : private ts::TExtData
{
private:

  TExpr* terms;

  void copyFrom (const Expr& e, size_t start, size_t length) {
    TExpr* p = *this;
    const TExpr* q = e;
    q += start;
    for (unsigned i = 0; i < length; i++)
      new (p++) TExpr(*q++);
  }

  void clear () {
    if (terms) {
      delete[] terms;
      terms = 0;
    } else {
      TExpr* p = *this;
      for (unsigned i = 0; i < getLength(); i++)
        p++->~TExpr();
    }
  }

public:

  Expr () : terms(0) {};

  void init (size_t s) {
    assert(!terms);
    terms = new TExpr[s];
    extDataSize() = s * sizeof(TExpr);
  };

  operator const TExpr* () const { return terms ? terms : (TExpr*)extData(); }
  operator       TExpr* ()       { return terms ? terms : (TExpr*)extData(); }

  Expr (const Expr& e) : terms(0) {
    copyFrom(e, 0, e.getLength());
  }

  Expr& operator= (const Expr& e) {
    if (this != &e) {
      clear();
      init(e.getLength());
      copyFrom(e, 0, e.getLength());
    }
    return *this;
  }

  Expr subexpr (size_t start, size_t length) const {
    Expr e;
    e.init(length);
    e.copyFrom(*this, start, length);
    return e;
  }

  size_t getLength () const {
    return extDataSize() / sizeof(TExpr);
  }

  TExpr& operator[] (int i) {
    return ((TExpr *)*this)[i];
  }

  ~Expr () {
    clear();
  }
};

// e is intentionally not const!
ostream& operator< (ostream& os, Expr& e) {
  os < e.getLength();
  TExpr* p = e;
  for (unsigned i = 0; i < e.getLength(); i++)
    os < " (" < (Expr &)*p++ < ")";
  return os;
}

istream& operator> (istream& is, Expr& e) {
  size_t len;
  char c1, c2;
  is > len;
  e.init(len);
  TExpr* p = e;
  for (unsigned i = 0; i < len; i++) {
    is > c1 > (Expr &)*p++ > c2;
    assert (c1 == '(' & c2 == ')');
  }
  return is;
}

Expr operator+ (const Expr& e1, const Expr& e2) {
  Expr e;
  e.init(e1.getLength() + e2.getLength());
  TExpr* p = e;
  const TExpr* q = e1;
  for (unsigned i = 0; i < e1.getLength(); i++)
    new (p++) TExpr(*q++);
  q = e2;
  for (unsigned i = 0; i < e2.getLength(); i++)
    new (p++) TExpr(*q++);
  return e;
}

tfun int insert (TExpr e, TExpr s, Expr tout out) {
  Expr& x = (Expr&) e;
  if (x.getLength() == 0) {
    out = (Expr&) s;
  } else {
    TExpr z;
    Expr& o = (Expr&) z;
    o.init(x.getLength());
    TExpr* p = o;
    TExpr* q = x;
    for (unsigned i = 0; i < x.getLength(); i++)
      insert(*q++, s, *p++);
    out = o;
  }
  return 0;
}

Expr empty;

 tfun int subst (TExpr e, TExpr s, Expr tout out) {
   Expr& x = (Expr&) e;
   if (x.getLength() == 0) {
     out = empty;
   } else {
     TExpr out1;
     TExpr* q = x;
     if (((Expr&)*q).getLength() == 0)
       out1 = s;
     else {
       TExpr o;
       subst(*q, s, o);
       ((Expr&) out1).init(1);
       ((TExpr*)(Expr&) out1)[0] = o;
     }
     TExpr out2;
     TExpr e2;
     ((Expr&) e2) = x.subexpr(1, x.getLength() - 1);
     subst(e2, s, out2);
     out = (Expr&)out1 + (Expr&)out2;
   }
   return 0;
 }
 

tfun int main (int argc, char *argv[]) {
  TExpr s;
  TExpr e;
  TExpr out;
  cin > e > s;
  cerr < "expr: " < e < endl < "subst: " < s < endl;
  insert(e, s, out);
  cerr < "after insert: " < out < endl;
  TExpr out2;
  insert(e, s, out2);
  subst(out2, s, out2);
  cerr < "after subst.insert: " < out2 < endl;
  return 0;
}

Приложение B. Использование динамического массива.

#include <iostream>
using namespace std;

template <typename type>
class TArray : public ts::TExtData {
  type *arr;
public:
  TArray() : arr(NULL) {}

  void resize(int sz) {
    int curSz = size();
    if (curSz < sz) {
      type* curArr = arr;
      type* curData = (type*)*this;
      arr = new type[sz];
      if (curData) memcpy(arr,curData,curSz*sizeof(type));
      if (curArr) delete [] curArr;
    }
    extDataSize() = sz*sizeof(type);
  }

  operator const type* () const { return arr ? arr : (type*)extData(); } 
  operator type* ()             { return arr ? arr : (type*)extData(); }

  type& operator [] (int i)     { return *(((type*)*this)+i); }

  int size() {return extDataSize() / sizeof(type);}
   
  ~TArray() { 
    if (arr) delete[] arr;
  }

  TArray (const TArray<type>& t) : arr(NULL) {
    memcpy(extData(),(const type*)t,extDataSize());
  }     
};

tfun int tGranula(tval TArray<int> tArr){
  TArray<int> &arr = (TArray<int>&)tArr;  
  int res = 0;

  for( int i = 0; i < arr.size(); i++ ){
    res += arr[ i ];
    cout << ts::myRank << ": " << arr[i] << endl;
  }
  cout << endl;
  return res;
}

tfun int main (int argc, char *argv[]) {
  tval TArray<int> tArr;
  TArray<int> &arr = (TArray<int>&)tArr;
  int res;

  arr.resize(10);

  for (int i = 0; i < arr.size(); i++) {
    arr[i] = i;
  }
  
  res = tGranula(tArr);
  arr.resize(15);
  res = tGranula(tArr);
  arr.resize(5);
  res = tGranula(tArr);
  arr.resize(15);
  res = tGranula(tArr);

  cout << endl << "Result = " << res << endl << endl;

  return 0;
}

Приложение C. Класс для представления строк в Т-системе.

class tString 
{
  tval ts::tArray<char> tstr;
public:
  ts::tArray<char>& operator=  (const char* str) 
  {
    ts::tArray<char>& s = (ts::tArray<char>&) tstr;
    s.resize(strlen(str));
    for (int i = 0; i < s.size(); i++) {
      s[i] = str[i];
    }
    return s;
  }

  char* ToString() {
    ts::tArray<char>& s = (ts::tArray<char>&) tstr;
    char *s1 = new char[s.size()+1];
    for (int i = 0; i < s.size(); i++) 
      s1[i]=s[i];
    s1[s.size()] = '\0';
    return s1;
  }

};

tfun int f(tString str){
  …
  printf("%s\n", str.ToString());
  return 0;
}
tfun int main(int argc, char* argv[]) {
  tString s = "abcde";
  …
  (int)f(str);
  return 0;
}

Приложение D. Многомерный Т-массив.

#include <iostream>
#include <stdexcept>

using namespace std;

template <typename T, int Dim>
class Array
{
private:
    // recursively create object
    Array<T, Dim - 1> vecRow;
    int d;

public:
    int index;
    int size;
    Array() 
    {
        index = 0;
        size = 1;
    }

    template<typename ... Types>
    void Resize(int iSize, Types ... rest)
    {
        d = iSize;
        size *= iSize;
        vecRow.size = size;
        size = 1;
        vecRow.Resize(rest...);
    }

    int Size()
    {
        return vecRow.Size();
    }

    Array<T, Dim - 1>& operator [] (int x)
    {
        if (x >= 0 && x < vecRow.Size())
        {
            vecRow.index = index*d + x;
            index = 0;
            return vecRow;
        }

        throw std::out_of_range("Index is out of range");
    }
};

// specialized class to stop recursion
template <typename T>
class Array<T, 1>
{
private:
    tval ts::tArray<T> vecRow;
    int d;
public:
    int index;
    int size;
    Array() 
    {
    }

    void Resize(int iSize)
    {
        ts::tArray<T>& vR = (ts::tArray<T>&)vecRow;
        vR.resize(iSize*size);
    }

    int Size()
    {
        ts::tArray<T>& vR = (ts::tArray<T>&)vecRow;
        return vR.size();
    }

    T& operator [] (int x)
    {
        ts::tArray<T>& vR = (ts::tArray<T>&)vecRow;
        if (x >= 0 && x < vR.size())
        {
            int i = index*d + x;
            index = 0;
            return vR[i];
        }

        throw std::out_of_range("Index is out of range");
    }
};