Google:
Помощь

Table of Contents

1. Язык T++ — расширение C++. Т-переменные, Т-функции,  Т-указатели.
2. Готовые и неготовые величины. Ожидание готовности. Функции tdrop и twait.
3. Гранулы параллелизма
4. Использование глобальных переменных.
5. Использование C-указателей в Т-переменных.
6. Структура программы на языке Т++.
7. Возможность предварительной отладки программы в последовательном варианте.
8. Советы по разработке программ на Т++.
9. Что происходит при вызове Т-функции.
10. Что нужно для инсталляции T-системы.
11. Компиляция и запуск Т-программ на кластере.
12. Ключевые слова Т++ как параметризованные классы (шаблоны).
13.  Пример программы рекурсивного обхода дерева.
14.  Особенности разработки Т-программ в операционной системе Windows.
14.1. Инсталлятор OpenTS под Windows
14.2. Набор для разработчика (SDK)
14.3. Интеграция с Visual Studio 2005
14.4.  Сборка T-приложений
15. Структура Т-системы.
16. Компилятор Т-системы. Опции компилятора.
17. Ядро Т-системы.
18. Сервисные возможности Т-системы
19. Общая память (суперпамять).
19.1. Решения, использованные при построении Суперпамяти
19.2. Описание архитектуры и программной реализации Суперпамяти
19.3. Передача значений с узла на узел
20. Алгоритм работы сборщика мусора
21. Операции присваивания и «замораживания» неготовых величин.
22. Планировщик T-системы. Пренатальные и непренатальные задачи.
23. Поддержка отказоустойчивости исполнения Т-приложений
23.1. Неготовые значения и незавершенные по причине сбоя вычисления
23.2. Вектор перерождений
23.3. Вектор посещений
23.4. Классы повреждений Т-функции в случае сбоя
24. Определение Т-контекста во время исполнения программы.
25. Примеры использования Т-структур и массивов переменного размера.
Приложение A. Пример вставки и замены листьев в дереве.
Приложение B. Использование динамического массива.

1. Язык T++ — расширение C++. Т-переменные, Т-функции,  Т-указатели.

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

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

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

Набор ключевых слов языка T++ невелик, и освоить его не составит труда для любого программиста, привыкшего к написанию программ на языке C.

Основные ключевые слова языка T++:

  1. tval — атрибут, указываемый в определениях Т-переменных, которые могут содержать "неготовые" значения.

  2. tptr — употребляется для описания "удаленного" указателя — указателя на Т-объект (например, неготовое значение), который может находиться на другом узле кластера. Удаленный указатель содержит в себе не только информацию об адресе в памяти, но и номер вычислительного узла кластера, в памяти которого находится Т-объект. Употреблять ключевое слово tptr в программе можно в декларациях переменных так же, как в языке C употребляется оператор '&' в значении "ссылка". tptr всегда указывает на переменную, которая может иметь неготовое значение (такие переменные объявляются с атрибутом tval). Ограничение реализации: нельзя указывать атрибут tptr у объектов, которые могут иметь конструкторы.

  3. tout — атрибут, указываемый в определениях Т-функций у выходных результатов. Употреблять ключевое слово tout в программе можно в декларациях переменных так же, как в языке C употребляется оператор '&' в значении "ссылка". Ключевое слово tout может встречаться только в описании аргументов Т-функции. Например:

    #include <stdio.h>
    
    tfun int f (tout int a) {
      a = 10;
      return 0;
    }
    tfun int main (int argc, char *argv[]) {
      tval int v;
      f(v);
      printf("v=%d\n",(int)v);
      return 0;
    }

    Программа напечатает "v=10".

  4. tfun — признак того, что определяемая функция может вычисляться параллельно (Т-функция).

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

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

       tfun int abcd(tval int a, double tptr b, tout int c, tout double d);

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

    В качестве примера рассмотрим программу на языке T++, вычисляющую N-е число Фибоначчи (как пример рекурсивного алгоритма).

    #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;
    }     

    При каждом вызове Т-функции fib (строки 5, 11) создается новый тред ( процесс) на каком-то из узлов кластера.

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

    На примере этой программы видно, что все отличие в синтаксисе от последовательного варианта заключается в использовании ключевых слов tval и tfun.

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

2. Готовые и неготовые величины. Ожидание готовности. Функции tdrop и twait.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Гранулы параллелизма

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

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

Модифицируем программу с вычислением функции Фибоначчи так, чтобы можно было регулировать размер гранулы параллелизма:

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

unsigned cfib (unsigned n)
{
  return n < 2 ? n : cfib(n - 1) + cfib(n - 2);
}
tfun unsigned fib (unsigned n)
{
  return n < 20 ? cfib(n) : fib(n - 1) + fib(n - 2);
}
tfun int main (int argc, char** argv)
{
  unsigned n;
  tval unsigned res;
  if (argc < 2) {
    fprintf(stderr, "Usage: fib <number>\n");
    return -1;
  }
  n = (unsigned)atoi(argv[1]);
  res = fib(n);
  printf("fib(%u) = %u\n", n, (unsigned)res);
  return 0;
}

Функция cfib используется для регулировки размера гранулы параллелизма (см. раздел "Размер гранулы параллелизма"). Рекурсия для n < 20 происходит в рамках одного Т-процесса.

4. Использование глобальных переменных.

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

5. Использование C-указателей в Т-переменных.

Переменная, которая может содержать неготовое значение, объявляется в языке T++ как

tval <type> var;

где tval - ключевое слово языка T++ — признак того, что переменная var может содержать неготовое значение, <type> — C-тип этой переменной.

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

tval char * var;

или

struct example{
  int *fun();
  double num;
};

tval struct example var1;

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

6. Структура программы на языке Т++.

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

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

7. Возможность предварительной отладки программы в последовательном варианте.

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

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

8. Советы по разработке программ на Т++.

Для наиболее эффективного процесса разработки программ для исполнения под Т-системой следует придерживаться следующей последовательности действий:

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

  2. Решается вопрос о том, какая часть алгоритма будет реализована на языке T++, а какая — оставлена в виде последовательно исполняемого кода.

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

  4. Программа отлаживается вначале на SMP-компьютере, а затем на реальном кластере.

  5. Снимается профиль программы, производятся различного рода оптимизации.

9. Что происходит при вызове Т-функции.

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

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

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

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

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

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

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

10. Что нужно для инсталляции T-системы.

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

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

  • Intel или AMD IA-32;

  • Intel или AMD x86-64;

  • PowerPC или PowerPC-64;

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

  • ОС Windows 2000/XP/2003/CCS/2008.

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

  • LAM MPI;

  • OPEN MPI;

  • MPICH;

  • MP-MPICH;

  • SCALI MPI;

  • MPICH-G2;

  • MPICH-GM;

  • PACX (MetaMPICH);

  • PVM;

  • MVAPICH;

  • MS MPI.

11. Компиляция и запуск Т-программ на кластере.

Пусть fib.tcc – программа вычисления чисел Фибоначчи, текст которой был приведен ранее. Компиляция программы осуществляется при помощи либо конвертера (t++) либо компилятора tg++. В нашем примере используется конвертер:

t++ -o fib fib.tcc

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

mpirun –np 4 ./fib

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

./fib

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

12. Ключевые слова Т++ как параметризованные классы (шаблоны).

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

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

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

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

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

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

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

13.  Пример программы рекурсивного обхода дерева.

Рассмотрим программу рекурсивного обхода дерева, написанную на языке Т++. На этом примере мы продемонстрируем работу с удаленными (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;
}

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

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

14.  Особенности разработки Т-программ в операционной системе Windows.

Платформа 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), содержащий все необходимые программные компоненты для создания, использования и управления кластерной инфраструктурой.

Кластер под управлением 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.

14.1. Инсталлятор OpenTS под Windows

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

14.3. Интеграция с 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". Объектные модули, полученные в результате применения этого правила, затем компонуются с некоторыми другими статическими библиотеками, в результате чего получается исполняемый файл Т-приложения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15. Структура Т-системы.

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

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

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

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

16. Компилятор Т-системы. Опции компилятора.

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

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

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

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

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

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

Для вывода списка допустимых опций компилятора 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 в системе должен быть корректно установлен оптимизирующий компилятор фирмы Интел.

17. Ядро Т-системы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. Общая память (суперпамять).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22. Планировщик T-системы. Пренатальные и непренатальные задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Во время исполнения программы можно изменять Т-контекст, или совокупность параметров Т-надстройки над стандартной средой исполнения 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)). Установка наименования Т-функции (используется при использовании режима отладки).

25. Примеры использования Т-структур и массивов переменного размера.

Приведенная в приложении 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.

Приложение 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;
}