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

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

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 17.01.2018
Размер файла 21,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на 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. Т-система

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

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

Текущая реализация Т-системы в качестве программно-аппаратной платформы использует Linux-кластер -- сеть процессорных элементов, объединенных в единую вычислительную систему с помощью локальной сети с протоколом TCP/IP; каждый из процессорных элементов представляет собой компьютер семейства IBM PC, работающий под управлением операционной системы Linux--клона ОС UNIX. Кроме того, реализована и версия Т-системы, поддерживающая симметричные мультипроцессоры, удовлетворяющие спецификациям Intel SMP 1.1/1.4.

3. Основные функции Т-системы

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

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

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

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

4. Основные компоненты Т-системы

Текущая реализация Т-системы с точки зрения её структуры состоит из трех относительно независимых компонент:

Tthreads -- компонента, поддерживающая множественные потоки управления в рамках единого процесса ОС Linux;

LMCE -- компонента, обеспечивающая распределённый запуск исполнителей, обмен сообщениями между ними и их согласованное завершение;

Т-ядро, реализующее вычислительную модель с использованием средств, предоставляемых TThreads и LMCE.

Tthreads. С каждым Т-процессом в Т-системе связан свой поток управления, иногда называемый легковесным процессом (в англоязычной терминологии -- thread). Реализуемый компонентой TТhreads аппарат множественных потоков управления асимметричен: помимо обычных потоков управления, в исполнителе всегда присутствует единственный выделенный поток управления, которому отводится роль "ядра". TТhreads предоставляет средства для создания, завершения и планирования выполнения "ядром" обычных потоков управления в рамках одного исполнителя, т.е. средства внутреннего планирования. Кроме того, TТhreads поддерживает механизм взаимодействия между "ядром" и обычными потоками управления, аналогичный механизму системного вызова.

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

Т-ядро. Реализуя основные функции Т-системы, Т-ядро для размещения элементов вычисляемой сети использует структуры специального вида (Т-структуры). Т-структуры состоят из звеньев -- тегированных фрагментов памяти. Звенья Т-структур расположены последовательно в выделенной для них области памяти исполнителя -- звеньевой памяти. Для управления звеньевой памятью используется дисциплина сборки мусора. Взаимодействие между Т-процессами и Т-ядром, которое функционирует как выделенный поток управления, осуществляется с использованием механизма "системных вызовов" компоненты TThre-ads. Каждому типу производимых Т-процессом атомарных действий по преобразованию вычисляемой сети, существенно изменяющих её состояние, соответствует отдельный системный вызов Т-ядра: сетевому вызову Т-функции -- системный вызов spark; ожиданию одного или нескольких неготовых значений -- системный вызов alt; рассылке потребителям вычисленного Т-процессом значения одного из результатов Т-функции -- системный вызов send, и т.д.

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

5. Программирование в Т-системе

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

Язык t2cp реализуется несложным препроцессором, преобразующим входную Т-программу в программу на языке С: Т-конструкции заменяются на соответствующие вызовы Т-системы; остальная часть программы оставляется без изменения. Результат препроцессирования обрабатывается стандартным в ОС Linux компилятором языка С и собирается с библиотеками Т-системы в исполняемый файл, пригодный для запуска на любой вычислительной установке вида "TCP/IP-сеть Linux-машин".

С точки зрения программиста, язык t2cp мало чем отличается от языка С: большая часть текста Т-программы является обычным текстом на языке С, и только небольшая часть -- Т-конструкциями. Разработку Т-программ удобно вести "сверху вниз". Сначала планируется верхний уровень Т-задачи небольшой набор Т-функций, в совокупности реализующий задачу. Затем разрабатываются -- на языке С с использованием Т-конструкций -- тела Т-функций. При этом, в рамках реализации тела одной Т-функции, программисту доступны все средства языка С, в том числе и те, которые принято считать не соответствующими функциональному стилю: операторы goto, вспомогательные С-функции с побочным эффектом, ограниченным рамками тела реализуемой Т-функции и т.п.

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

реализация аналогичных препроцессорных расширений для других императивных языков программирования ОС Linux (например, для языка Фортран);

разработка и реализация Т-языка как диалекта (а не препроцессируемого расширения) императивных языков программирования;

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

6. Использование Т-системы для реализации различных приложений

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

построение качественных изображений трехмерных сцен методом трассировки лучей [Адамович и др., 1999];

вычисление sl- и so-полиномов для 3-графов [Bar-Natan, 1995] -- реальная задача компьютерной алгебры с высокой вычислительной сложностью: вычисление Т-программой so-полинома для 3-графа с 24 вершинами на установке с 12 процессорами Pentium Pro/200 заняло 55 часов;

фильтрация линейного потока данных динамически порождаемыми фильтрами -- на примере построения потока простых чисел методом "решето Эратосфена";

построение множества данных, заданного рекурсивным определением -- на примере алгоритма построения бесконфликтных расстановок ферзей на шахматной доске;

игровая программа -- переборный алгоритм -- с отсечениями, эвристикой и учетом ограничений на время счета -- выбора очередного хода в игре Pousse (усложненный вариант "крестиков-ноликов").

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

Заключение

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

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

Литература

Адамович и др., 1999 Адамович А.И., Коваленко М.Р., Конышев А.П. Реализация в Т-системе программы построения качественных изображений трехмерных сцен методом трассировки лучей -- Программные системы: теоретические основы и приложения/Под ред. А.К.Айламазяна -- М.: Наука. Физматлит, 1999, стр. 224-233.

Абрамов и др., 1999 Абрамов С.М., Адамович А.И. Т-система -- среда программирования с поддержкой автоматического динамического распараллеливания программ -- Программные системы: теоретические основы и приложения/Под ред. А.К.Айламазяна -- М.: Наука. Физматлит, 1999, стр. 201-213.

Abramov et al., 1993 Abramov S.M., Adamowitch A.I., Nesterov I.A., Pimenov S.P., Shevchuck Yu.V. Autotransformation of evaluation network as a basis for automatic dynamic parallelizing -- Proceedings of NATUG 1993 Meeting Transputer: Research and Application -- May 10-11, 1993.

Bar-Natan, 1995 D. Bar-Natan, On the Vassiliev knot invariants -- Topology, 34 (1995) 423-472.

Blumofe et al., 1995 Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. Cilk: An Efficient Multithreaded Runtime System -- In 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP '95) -- July 19-21, 1995, Santa Barbara, California, pp. 207-216.

Goldberg et al., 1988 B.F. Goldberg. Multiprocessor execution of functional programs -- Ph.D. thesis, Yale University, Dept. of Computer Science, 1988. Доступна как технический отчет YALEU/DCS/RR-618.

Размещено на Allbest.ur

...

Подобные документы

  • Основные направления развития параллелизма, модели параллельного программирования. Автоматические средства разработки параллельного ПО, анализ последовательной программы. Разработка системы автоматического распараллеливания программ на языке Fortran77.

    дипломная работа [57,7 K], добавлен 14.10.2010

  • Развитие концепций и возможностей ОС. Параллельные компьютерные системы и особенности их ОС. Симметричные и асимметричные мультипроцессорные системы. Виды серверов в клиент-серверных системах. ОС для облачных вычислений. Кластерные вычислительные системы.

    лекция [1,8 M], добавлен 24.01.2014

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

    дипломная работа [1,3 M], добавлен 09.09.2010

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

    курсовая работа [73,7 K], добавлен 15.10.2010

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

    отчет по практике [64,6 K], добавлен 18.09.2013

  • Описание кластерных систем и характеристика библиотек параллелизма. Аналоги PVM. Организация параллельных вычислений. Описание оборудования и программного обеспечения кластера. Гипотеза Гольдбаха. Процесс компиляции собственной программы для работы с PVM.

    курсовая работа [847,2 K], добавлен 05.12.2014

  • Вычислительные системы, сети и телекоммуникации: цели и задачи обработки информации, аппаратные средства её реализации. Функции управления ЭВМ, их программные составляющие (память, интерфейс, средства обработки). Многопроцессорные вычислительные системы.

    курсовая работа [2,1 M], добавлен 17.12.2009

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

    курс лекций [2,5 M], добавлен 10.11.2010

  • Интерфейс OpenMP - системы программирования на масштабирующих SMP-системах. Разработка алгоритмов блока "Эксперт для мультипроцессора" в проекте "Экспериментальная система автоматизации распараллеливания" для генерации вариантов локализации данных.

    дипломная работа [129,8 K], добавлен 15.10.2010

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

    курсовая работа [1023,2 K], добавлен 23.05.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.