Доклад на 4-ой Международной Российско-Индийской выставке-семинаре "Математическое моделирование и визуализация", Москва 15-25 сентября 1997 г.══
Sergei Abramov═ abram@botik.ru |
Alexey Adamovich═ lexa@adam.botik.ru |
Maxim Kovalenko═ mk@adam.botik.ru |
До сегодняшнего дня проблема реализации параллельных вычислений в большей мере все еще является проблемой программного обеспечения, а не аппаратных средств.
В данной работе рассматривается разработанная в ИЦМС ИПС РАН система автоматического динамического распараллеливания программ--Т-система--и пример ее применения в задаче построения качественных изображений трехмерных сцен с использованием метода трассировки лучей.
Для реализации концепции автоматического динамического распараллеливания программ нами была предложена новая модель организации вычислительного процесса [NATUG'93, RCMS'94]. А именно:
[x,y,z] = G(a,b)
Автотрансформация вычисляемой сети, как модель организации вычислений, поддерживает возможность автоматического динамического распараллеливания программ--при такой организации вычислений для большинства приложений в вычислительной сети в каждый момент времени находится достаточное количество процессов готовых к выполнению-их можно выполнять параллельно. Модель предусматривает единственный механизм синхронизации процессов--описанный выше механизм засыпания и побудки процессов.
Наиболее близкие аналоги к данной вычислительной модели--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: |
═