Т-система: система автоматического динамического распараллеливания программ на кластерных платформах

Размещено на http://www.allbest.ru/

Т-система: система автоматического динамического распараллеливания программ на кластерных платформах

С.М. Абрамов

А.И. Адамович

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

Введение

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

Самый распространенный подход к разработке параллельных программ, основанный на использовании программных пакетов типа PVM или MPI и ручном статическом распараллеливании, требует от разработчика повышенного объема специальных знаний и навыков и значительных затрат времени как на этапе разработки программ, так и при их отладке. Автоматизация этого подхода с использованием распараллеливающих компиляторов, снижая затраты на этапах разработки и отладки, всё же не позволяет избавиться от основного недостатка статических методов: чрезвычайно высокая алгоритмическая сложность задач, связанных с оптимальным статическим распараллеливанием программ, может в общем случае привести к недостаточной глубине распараллеливания.

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

В данной работе рассматривается разработанная в Исследовательском центре мультипроцессорных систем (ИЦМС) ИПС РАН система автоматического динамического распараллеливания программ -- Т-система.

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

1. Вычислительная модель

аппаратный параллельный платформа вычислительный

Для реализации концепции автоматического динамического распараллеливания программ нами была предложена новая модель организации вычислительного процесса [Abramov et al, 1993], [Абрамов и др., 1999]. Коротко отметим основные черты данной вычислительной модели:

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

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

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

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

Наиболее близкие аналоги данной вычислительной модели использовались в работах Э.Х. Тыугу, А.С. Нариньяни, в параллельных реализациях reduction machine (см., например, [Goldberg et al., 1988]), системе МДА (мультипроцессор с динамической архитектурой) [Плюснин и др., 1984] и системе программирования Cilk [Blumofe et al., 1995].

2. Т-система

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

Программно-аппаратная платформа для Т-системы.