Доклад на 4-ой Международной Российско-Индийской выставке-семинаре "Математическое моделирование и визуализация", Москва 15-25 сентября 1997 г.══

---

Т-система: среда программирования с поддержкой автоматического динамического распараллеливания программ на платформе "IP-сеть UNIX-компьютеров"

---

T-system: programming environment providing automatic dynamic parallelizing on IP-network of Unix-computers═

---

Введение

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

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

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

Для реализации концепции автоматического динамического распараллеливания программ нами была предложена новая модель организации вычислительного процесса [NATUG'93, RCMS'94]. А именно:

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

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

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

Наиболее близкие аналоги к данной вычислительной модели--Daisy/DSI project (Indiana Univ.), reduction machine, и система МДА (мультипроцессор с динамической архитектурой, Россия, 1978-1985 годы).

Т-система

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

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

Текущая реализация Т-системы в качестве аппаратной платформы (мультикомпьютера) может использовать произвольную сеть (с протоколом TCP/IP) компьютеров семейства IBM PC с операционной системой Linux.

В ближайших планах развития:

• поддержка многопроцессорных (SMP) IBM PC в составе мультикомпьютера;
• перенос Т-системы под другие архитектуры и клоны Unix (возможно-под MS Windows NT).

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

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

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

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

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

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

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

В ближайших планах развития:

• завершение разработки языка cT [PACT'95]-расширения языка С, включающего в себя типы данных и конструкции вычислительной модели;
• разработка компилятора языка cT.

Построение изображений трехмерных сцен с использованием Т системы

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

Структура программы

На базовом уровне в программе используется следующий алгоритм:

[image] main(scene, full_screen_description) {
══ [tree] = render_scene(scene, full_screen_description);
══ [image] = flaten(tree);
}

[image_tree] render_scene(scene, part_of_screen_description) {
══ var part1, part2, tree, part_of_img;
══ if (size_too_big(part_of_screen_description)) {
═════ [part1,part2] = split(part_of_screen_description);
═════ br_node = new(2);
═════ [br_node[0]] = render_scene(scene,part1);
═════ [br_node[1]] = render_scene(scene,part2);
═════ [image_tree] = br_node; -- развилка в дереве фрагментов изображения
══ } else {
═════ ... размещение массива part_of_image и заполнение его--
═════════ обычным алгоритмом трассировки лучей
═════ image_tree = part_of_image; --═ лист дерева фрагментов изображения
══ }
}

[image] flaten(tree) {
══ ... рекурсивный обход дерева и сбор целого изображения из фрагментов.
}

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

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

Результаты вычислительных экспериментов

Т-программа трассировки лучей выполнялась на мультикомпьютерах из одного, двух, трех и четырех ПЭВМ класса IBM PC Pentium 166/32Mb/4Gb. Строились изображения сцен различной сложности. В процессе экспериментов показано, что T-система поддерживает высокий уровень утилизации вычислительной мощьности мультипроцессора и низкий уровень накладных расходов.

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

═

═

Литература по Т-системе

[NATUG'93] 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.

[RCMS'94] Abramov S.M., Nesterov I.A., Shevchuk Yu.V. T-language. Preliminary description, RCMS Tech. Report #09/18/1994

[PACT'95] Adamovich A.I. cT: an Imperative Language with Parallelizing Features Supporting the Computation Model "Autotransformation of the Evaluation Network"//LNCS #964 1995, Parallel computing technologies: third international conference; proceedings / PaCT-95, St. Petersburg, Russia, September 12 - 25, 1995. Victor Malyshkin (ed), pp. 127-141

[SIAM'95] I.A.Nesterov, I.V.Suslov., Towards programming of numerical problems within the system providing automatic parallelizing//Proceedings of 7th SIAM conference on parallel processing for scientific computing, p.716, San-Francisco, CA, 1995.

═