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


Т-система: среда программирования с поддержкой автоматического динамического распараллеливания программ на платформе "IP-сеть UNIX-компьютеров"
T-system: programming environment providing automatic dynamic parallelizing on IP-network of Unix-computers

Sergei Abramov
abram@botik.ru
Alexey Adamovich
lexa@adam.botik.ru
Maxim Kovalenko
mk@adam.botik.ru


Институт программных систем Российской Академии наук, Исследовательский центр мультипроцессорных систем 152140, Переславль-Залесский═
Program Systems Institute of Russian Academy of Sciences
Research Center for Multiprocessor Systems Pereslavl-Zalessky, Russia, 152140

Введение

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

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

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

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

[x,y,z] = G(a,b)

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

T-call

Autotransformation

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

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

Т-система

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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-система поддерживает высокий уровень утилизации вычислительной мощьности мультипроцессора и низкий уровень накладных расходов.

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

сцена B2
3 прожектора, 91 сфера, 1 многоугольник)
сцена G
5 прожекторов, 147 многоугольников)
сцена B3
(3 прожектора, 820 сфер, 1 многоугольник)

Время счета в %

Коэффициент ускорения

кол-во процессоров

сцена B2

сцена B3

сцена G

кол-во процессоров

сцена B2

сцена B3

сцена G

1

100.00%

100.00%

100.00%

1

1.00

1.00

1.00

2

53.24%

51.81%

51.88%

2

1.88

1.93

1.93

3

35.99%

35.06%

34.78%

3

2.78

2.85

2.88

4

28.02%

26.84%

26.69%

4

3.57

3.73

3.75

Время счета (сек)

Утилизация вычислительной мощности

кол-во процессоров

сцена B2

сцена B3

сцена G

кол-во процессоров

сцена B2

сцена B3

сцена G

1

278.11

2,785.99

1,295.25

1

100.00%

100.00%

100.00%

2

148.06

1,443.52

671.96

2

93.92%

96.50%

96.38%

3

100.08

976.85

450.43

3

92.63%

95.07%

95.85%

4

77.94

747.64

345.68

4

89.21%

93.16%

93.67%

сцена G2
5 прожекторов, 1169 многоугольников)
сцена B4
3 прожектора, 7381 сферa, 1 многоугольник)

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

[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.

Большинство публикаций FTP-доступны с WWW-страницы: http://www.botik.ru/~abram/ts-pubs.html
Most of the publications are FTP-available from Web-page: