Как известно из общей теории функционального программирования, базирующейся на лямбда-исчислении, окончательный результат редукции (вычисления) лямбда — выражения не зависит от порядка редукции (вычисления) входящих в него редексов (подвыражений). Это дает прямой и вполне очевидный метод для распараллеливания чисто функциональных программ, то есть программ, построенных из «чистых» функций без сторонних эффектов: нужно в каждый момент времени выделять готовые к вычислению подвыражения и распределять их по имеющимся процессорам. Проследим за тем, каким образом отправляясь от этой (довольно-таки простой) идеи можно получить полноценную среду для динамического распараллеливания программ. Прежде всего, нужно найти эффективное представление в оперативной памяти мультикомпьютера для функциональных выражений, то есть эффективное представление для набора вида «функция, ссылки на аргументы». Поскольку сейчас повсеместно используются адресные компьютеры, то за основу для такого представления естественно взять граф, узлы которого представляют вызванные функции, а ребра представляют собой отношение «подвыражение-выражение» (или, в терминологии функционально-потоковых схем, отношение «поставщик-потребитель»). Далее, необходимо реализовать эффективную схему распределения готовых к исполнению гранул параллелизма, которыми здесь и являются наборы «функция, ссылки на аргументы» по процессорам мультикомпьютера, обеспечить доставку данных по высокоскоростным коммуникациям и корректное разделение данных в пределах каждого SMP-вычислителя. Разумеется, нужно также обеспечить начальное преобразование исходного текста программы с целью получения вышеупомянутого графа в момент запуска. Дальнейшее преобразование (автотрансформация) графа будет производиться в процессе параллельного счета. Оказывается, что достаточно ввести в императивный язык программирования (например, в язык C++) понятие неготового значения, введя дополнительное ключевое слово (например, tval) в качестве необязательного атрибута переменных, и функциональная семантика легко и ненавязчиво для программиста проникает в программный код. Еще небольшое число ключевых слов потребуется для необязательных атрибутов, обозначающих:
- tfun— Т-функции, то есть функции без побочных эффектов, вызовы которых можно вычислять параллельно;
- tout— выход Т-функции (аргумент, для возвращения посчитанного значения);
- и др. (подробнее см. документ “Описание языка T++”).
Диалект, полученный из языка C++ добавлением указанных ключевых слов, будем называть языком T++. Язык Т++ позволяет использовать привычную для многих императивную нотацию для записи программ в функциональном стиле. Кроме того, он позволяет получить весьма простой способ начальной трансформации программы в вычислительный граф.
Примеры программ
Для того чтобы ознакомиться с базовыми конструкциями Т-системы и языка T++, рассматриваются два простых примера: числа Фибоначчи и рекурсивный обход древовидной структуры данных.
Числа Фибоначчи
На рис. 1 представлена программа вычисления n-ого числа Фибоначчи. Вычисление намеренно реализовано не самым оптимальным образом — при помощи «прямолинейного» кодирования известного рекурсивного определение для чисел Фибоначчи.
Вызовы Т-функций fib (строки 9, 15) являются новой гранулой параллелизма, готовой к вычислению. Они помещается в очередь, откуда локальные вычислительные процессы- исполнители (работающие на каждом вычислительном узле кластера, в количестве, равном числу процессоров в этом SMP узле) черпают работу сначала для себя, а затем (в случае полной локальной загрузки) и для других свободных вычислительных процессов в кластере. Обращение к неготовым переменным на чтение (за значением) блокирует процесс вычисления функции. Неготовые переменные, таким образом, являются средством синхронизации и посредниками при создании новых узлов редуцируемого вычислительного графа. Существенно различаются ситуации обращения к неготовым переменным на чтение (доступ за значением) и на запись (доступ для присваивания):
#include
#include
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); return 1; }
int n = atoi(argv[1]);
printf(fib(%d) = %d\n, n, (int)fib(n));
return 0;
}
Рис. 1. Программа вычисления чисел Фибоначчи
При компиляции этой программы конвертером t++ со специальной опцией -auto-c-call достигается скорость вычислений, практически одинаковая с со скоростью C-версии (откомпилированной обычным компилятором без Т-системы) за счет автоматического перехода на вызовы С-версий Т-функций при большой глубине вызовов. Но при этом Т- версия хорошо масштабируется на несколько десятков вычислительных узлов.
Компиляция программы осуществляется при помощи либо конвертера (t++) либо компилятора tg++. В нашем примере используется конвертер:
t++ -o fib fib.tcc
Запуск программы, в общем случае, осуществляется при помощи стандартных средств запуска параллельных приложений, например, в случае SCALI MPI:
mpirun –np 4 ./fib
Возможен также и запуск приложения в режиме монопроцессора, например, при отладке:
./fib
При запуске, консольный вывод приложения содержит статистическую информацию о выполнении программы: общее время исполнения, число запущенных Т-функций и другую. Конвертером Т++ поддерживается компиляция приложения с отладочным выводом, запуск отладочной версии порождает, во время выполнения, вывод информации о создающихся Т-переменных, запуске Т-функций и ожидании неготовых величин.
2.3.2. Краткая характеристика языка Т++
На примере программы вычисления чисел Фибоначчи мы познакомились с языком Т++ — входным языком Т-системы. Язык T++ разработан как синтаксически и семантически гладкое расширение языка C. Под «гладкостью» здесь понимается то, что дополнительные конструкции синтаксически и семантически увязаны с конструкциями основного языка C.
Явные параллельные конструкции, понимаемые в привычном смысле, в языке T++ отсутствуют, например, программист не указывает, какие части программы следует выполнять параллельно. Т-функции указывают прототипы (шаблоны) возможных гранул параллелизма— реально гранулы параллелизма возникают и обрабатываются Т-системой во время работы программы, во время вызовов Т-функций. Указаниями для организации параллельного счета являются элементы расширения синтаксиса и семантики языка, которые наиболее адекватно отражают архитектуру, функциональность и назначение Т-системы, а также зависимости по данным между отдельными счетными гранулами. Ключевые слова языка T++ и используемые специфические функции и макроопределения, свойственные языку T++, перечислены и описаны в документации языка T++. Набор таких ключевых слов невелик, и освоить его не составит труда для любого программиста, привыкшего к написанию программ на языке C++. Основные ключевые слова языка T++, описывающие основные типы данных языка, реализованы как шаблоны, написанные на языке C++, например:
- ключевое слово tval реализовано как шаблонный класс TVar языка C++;
- ключевое слово tptr реализовано как шаблонный класс TPtr языка C++. Данное ключевое слово употребляется для описания удаленного указателя, то есть указателя, который содержит в себе не только информацию об адресе в памяти, но и номер вычислительного узла кластера, для которого указывается этот адрес;
Параметризованные классы (шаблоны), определяемые Т-системой, можно непосредственно использовать в коде на языке C++, например, если требуется распараллелить программный модуль, реализованный на языке C++.
Имеется возможность последовательного исполнения программ на языке Т++.
Добавленные в язык С расширения выглядят достаточно прозрачными для синтаксиса и семантики языка C. Это позволяет программу на языке T++ разрабатывать и отлаживать без использования Т-системы. Для этого достаточно использовать специальный заголовочный файл txx, который переопределяет (с помощью макроопределений) все ключевые слова, добавленные в язык C. Таким образом Т++ программу можно компилировать обычными компиляторами С, выполнять в последовательном (однопроцессорном) режиме и отлаживать, используя штатные однопроцессорные средства отладки. Данное свойство упрощает первый этап цикла разработки программ, позволяя отлаживать последовательные части реализованного функционального алгоритма в наиболее удобной, привычной для программиста среде.
