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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В программе для вычисления чисел Фибоначчи вызовы Т-функции 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 происходит в рамках одного Т-процесса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

t++ -o fib fib.tcc

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

mpirun –np 4 ./fib

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

./fib

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

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

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

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

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

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

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

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

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

struct tree tptr create_tree(int deep) {
  struct tree tptr res = new tval tree;
  res->value = 1;
  if (deep <= 1) {
    res->left = NULL;
    res->right = NULL;
  } else {
    res->left = create_tree(deep-1);
    res->right = create_tree(deep-1);
  }
  return res;
}
tfun int tsum(struct tree tptr tree) {
  tval int leftSum, rightSum;

  if (tree->left != NULL) {
    leftSum = tsum(tree->left);
  } else {
    leftSum = tree->value;
  }
  if (tree->right != NULL) {
    rightSum = tsum(tree->right);
  } else {
    rightSum = tree->value;
  }
  return leftSum + rightSum;
}

tfun int main (int argc, char* argv[])
{
  struct tree tptr tree = create_tree(12);
  printf("sum = %d\n", (int)tsum(tree));
  return 0;
}
          Программа рекурсивного обхода дерева. Основной код.
        

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

Платформа Windows Compute Cluster Server (WCCS) состоит из двух компонентов:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Файл 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;
}
	

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