Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

241

реализации [3] предлагается параллельная версия алгоритма двойного

описания. Предварительные результаты по улучшению версии [2] уже

докладывались ранее в [4]. Автору известна и другая параллельная

реализация [1] модификации алгоритма [6].

Оригинальный алгоритм [2] имеет итеративный характер: на

каждой из итераций рассматривается очередное неравенство из

матрицы

и проводятся все необходимые вычисления, после чего

алгоритм переходит к следующему неравенству.

Анализ потока данных в [2] показал, что можно построить такой

параллельный алгоритм, который не имеет обязательных барьеров (т.е.

ситуаций, когда все потоки синхронизируются в одной точке

исполнения) в вычислениях как между различными стадиями одной

итерации, так и между

соседними итерациями. Предлагаемый

алгоритм работает на многопроцессорной машине с общей памятью и

использует только дешёвый способ синхронизации через атомарно

модифицируемые целочисленные переменные (interlocked-операции).

Это позволило получить удовлетворительные результаты по

масштабируемости алгоритма даже на тех входных данных, обработка

которых занимает малое время и содержит достаточно много итераций

(«малые» данные). На графике

показано ускорение в вычислениях

полученное на 4-процессорной машине Intel Xeon 2.4ГГц при

использовании различного числа процессоров. Подобраны такие

исходные данные, на которых либо 1) последовательный алгоритм

имеет малое среднее время исполнения одной итерации, т.е. данные,

на которых параллельный алгоритм имеет высокую гранулярность

параллелизма (данные A, C, D), либо 2) порождает большую (по

сравнению со входом) матрицу

(данные B). В скобках указаны

параметры решаемых задач и время, требуемое на решение

последовательным алгоритмом. Реализация использует потоки Win32

API операционной системы Microsoft Windows.

242

Ма сштабируе мость алгоритма для разных наборов входных данных

0.5

1.5

2.5

3.5

4.5

1234

Число процессоров

Ускорение, раз

Данные A (d = 10, m =

100, n = 6522, 5.08

сек.)

Данные B (d = 17, m =

32, n = 65536, 6.51

сек.)

Данные C (d = 9, m =

729, n = 4862, 46.7

сек.)

Данные D (d = 24, m =

3461, n = 168, 67.3

сек.)

идеальная

масштабируемость

Рис. 1.

В дополнение к высокоуровневой параллельности, по сравнению с

оригинальной реализацией [3], схема вычислений была изменена так,

чтобы использовать низкоуровневый параллелизм по данным через

векторные инструкции целевой машины (использовались Intel SSE,

Intel SSE 2). Особое внимание уделяется локальности вычислений, т.е.

эффективному использованию кэш-памяти на многопроцессорной

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

данных на блоки и

систематическим использованием предвыборки из

основной памяти (prefetch-инструкции).

Кроме нахождения двойного описания для «малых» задач, которые

встречаются в приложениях, где алгоритм двойного описания

многократно вызывается как часть другого алгоритма, представляет

интерес решения поставленной задачи для «больших» данных,

которые также появляются на практике и, порою, настолько велики,

что либо время работы алгоритма на

одной (хотя бы и

многопроцессорной) машине с общей памятью не является

практически удовлетворительным, либо данные просто не

помещаются в память одной машины. С целью решения таких задач

идёт работа над реализацией данного алгоритма для машин с

распределённой памятью.

Литература

1. Агафонов Е.А., Земскова Е.Л., Золотых Н.Ю. Параллельный

алгоритм построения

остова многогранного конуса и его программная реализация.

243

Информационный бюллетень Ассоциации математического

программирования №

10. Конференция "Математическое программирование и

приложения" (тезисы

докладов). - Екатеринбург: УрО РАН, 2003. - С.15–16.

Золотых Н.Ю. Новая модификация метода двойного описания

для построения остова многогранного конуса. III

Всероссийская конференция «Проблемы оптимизации и

экономические приложения». Тезисы докладов. – Омск, 2006.

– С. 108.

Золотых Н.Ю. Skeleton – программа построения остова

многогранного конуса. Информационный бюллетень

Ассоциации математического программирования. № 11.

Конференция «Математическое программирование и

приложения». – Екатеринбург, 2007. – C. 120–121.

Золотых Н.Ю., Лялин С.С. Оптимизация одной модификации

алгоритма двойного описания для многогранного конуса.

Технологии Microsoft в теории и практике программирования.

Материалы конференции. Под ред. проф. Р.Г. Стронгина. –

Нижний Новгород: изд-во Нижегородского госуниверситета,

2007. – С. 333–336.

K. Fukuda and A. Prodon. Double description method revisited. In

M. Deza, R. Euler, and I. Manoussakis, editors, Combinatorics and

Computer Science, volume 1120 of Lecture Notes in Computer

Science, pages 91–111. Springer-Verlag, 1996.

T.S. Motzkin, H. Raiffa, G.L. Thompson, and R.M. Thrall. The

double description method. In H. W. Kuhn and A. W. Tucker,

editors, Contributions to the Theory of Games – Volume II,

number 28 in Annals of Mathematics Studies, pages 51–73.

Princeton University Press, Princeton, New Jersey, 1953.

244

ПОДХОД К ПОСТРОЕНИЮ КАРКАСА ПАРАЛЛЕЛЬНЫХ

ПРИЛОЖЕНИЙ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

В ОБЛАСТИ МЕХАНИКИ СПЛОШНЫХ СРЕД,

ОСНОВАННЫЙ НА DSL

А.В. Медведев

GDT Software Group

Многие из существующих пакетов прикладных программ,

предназначенные для численного моделирования в области механики

сплошных сред, обладают тем недостатком, что расширение их

возможностей за счёт модификации используемых методов и

алгоритмов практически невыполнимо. Кроме того, так как многие из

них являются коммерческими продуктами, то они ориентированы на

привлечение как можно большего круга

покупателей и поэтому

обладают лишь наиболее общими базовыми алгоритмами, что не

позволяет проводить с их помощью специализированные

исследования. Создание системы, в которой замена или расширение

вычислительного модуля представляла бы относительно простую, а

главное – независимую от значительных изменений в код самого

пакета процедуру, является значительным шагом на пути всё более

широкого внедрения

в промышленную практику современных

вычислительных комплексов.

Идея создания разного рода каркасов приложений

математического моделирования в области механики сплошных сред

не нова и нетрудно обнаружить ряд успешных её реализаций на том

или ином уровне. Главное в самой этой идее – снизить трудоёмкость

кодирования сложных численных схем за счёт введения некоторой

степени автоматизации

многократно повторяющихся операций. Чаще

всего предлагаются готовые блоки, такие как библиотеки функций или

библиотеки классов или шаблонов для того или иного языка

программирования. Программист может воспользоваться некоторыми

базовыми численными методами, некоторыми примитивами для

работы с сетками, так же как и некоторыми примитивами для

распараллеливания кода. Однако, всё это лишь способы дать

в руки

разработчика готовые вспомогательные инструменты, в то время как

главная трудность, связаная непосредственно с программированием

численной схемы на одном из языков высокого уровня – Си, С++ или

FORTRAN остаётся нерешённой. Трудность состоит в том, что

245

полноценное освоение этих языков не всегда доступно специалистам

по численным схемам, и наоборот, эксперты в области одного из трёх

этих языков редко являются одновременно и специалистами по

численному моделированию. Кроме того, сами выразительные

средства каждого из этих трёх языков многие считают не вполне

развитыми для довольно сложных задач, которые встают

перед

современными программистами в сфере механики сплошных сред.

Разработчики компании GDT Software Group на данный момент

рассматривают возможность более радикального подхода к проблеме

снижения сложности программирования численных схем. В основе его

лежит, во-первых, идея модификации уже имеющейся связки

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

GasDynamicsTool и ScientificVR (S-VR), чтобы воспользоваться уже

заложенной в их

архитектуру модульностью для построения

универсального каркаса приложений, а во-вторых, в активном

использовании идей метапрограммирования и, в частности, языков

программирования предметной области (Domain Specific Languages).

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

Программные пакеты GasDynamicsTool и ScientificVR обладают

следующими важными особенностями. GasDynamicsTool является сам

по себе в высокой степени модульным приложением. Имеется модуль,

предоставляющий развитый графический

интерфейс пользователя,

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

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

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

специфической объектной иерархии элементов счётной области. За

восстановление и сохранение результатов расчёта в виде “снимков”

счётной области в различных форматах отвечают также отдельные

модули. Наконец, в виде

изолированных модулей выполнены

собственно коды численных схем, реализованных в пакете.

Параллельность в пакете реализована таким образом, что

однопроцессорный вариант отличается от параллельного опять же

использованием набора модулей. Например, параллельная версия

пакета имеет особую разновидность, называемую гибридной версией

(GDT Hybrid, [1]) , которая позволяет запускать счётные задачи на

параллельных системах и интерактивно управлять ими с

рабочих

станций, не включённых в состав кластера. При этом важно, что

пользователь не видит разницы в работе с кластерной системой и

однопроцессорной версией для персонального компьютера –

246

интерфейс пакета в обоих вариантах в точности совпадает, а “солверы”

пакета просто вынесены в отдельный модуль, работающий удалённо,

на кластере.

Важно также отметить, что не в последнюю очередь благодаря

такой архитектуре пакета достаточно широк диапазон

поддерживаемых архитектур и операционных систем:

поддерживаются все процессоры, которые наиболее популярны в

сфере высокопроизводительных вычислений,

все современные версии

Linux, а также Solaris и MacOS X, работающие на различных

аппаратных средствах для параллельных вычислений: c кластерной

архитектурой Beowulf-типа, NUMA и SMP архитектурами, пакет готов

к работе также и в системах GRID.

Ещё одним важным следствием модульной архитектуры можно

назвать тесную интеграцию пакета моделирования с визуализатором

S-VR [2], который позволяет анализировать полученные в результате

расчёта данные с

использованием новейших подходов к трёхмерному

Volume Rendering'у, в том числе с технологией Ray Tracing [3],

реализованной на базе современных графических процессоров nVidia и

ATI. Получаемые изображения отличаются особой реалистичностью и

могут быть выведены в стереоскопическом формате на специальном

оборудовании.

Интеграция такова, что S-VR фактически можно рассматривать

как отдельный модуль визуализации, входящий в пакет моделирования

GasDynamicsTool. Это дало

возможность реализовать уникальную для

параллельных CFD-пакетов технологию – визуализацию на лету

("on-the-fly"), когда все операции по отображению данных могут быть

выполнены непосредственно в ходе расчёта без его остановки – вы

можете наблюдать развитие процессов в модели, даже если

моделируется задача в несколько миллиардов ячеек без остановки

процесса моделирования и сохранения промежуточных файлов.

Таким

образом, пакет GasDynamicsTool представляется неплохим

плацдармом для построения универсального каркаса параллельных

приложений численного моделирования. Единственная серьёзная

функция, которая отсутствует в его составе – это сеточный генератор

(все солверы на данный момент работают на равномерных кубических

сетках).

Далее, несколько слов о том, почему именно концепция языков

программирования предметной области представляется разработчикам

ключевой идеей

. К сожалению, лишь три языка общего назначения

247

нашли широкое распространение в современном мире параллельного

программирования численных моделей – Си, С++ и FORTRAN.

Каждый из них достаточно универсален, но при этом не слишком

развит для уверенно контролируемой и предсказуемой по качеству

реализации действительно сложных задач. Это выражается в том, что

даже несмотря на такие мощные концепции, как объектно-

ориентированное программирование

и простейшие элементы

метапрограммирования с помощью шаблонов, внесённые в язык

программирования С++, практика показывает, что он не способен

действительно эффективно снижать сложность реализации численных

схем. Это же касается и стандарта MPI, который также не слишком

преуспел в сокращении сложности параллельного программирования.

Использование давно проверенной концепции специализированных

языков предметной области взамен универсальных языков

кажется

разумным выходом. Говоря о специализированных языках, имеется в

виду не просто какой-то один синтетический язык для описания

численной схемы какого-то определённого вида, речь идёт о целой

группе описательных и не только описательных языков, которые

могли бы помочь программисту в формулировании на машинном

языке всего, что относится к

реализации численной схемы в составе

полноценного пакета, начиная от перечня используемых параметров и

формального описания всех схемных вычислений, заканчивая

текстовой справкой для пользователя по вводу констант и описанием

вида диалоговых окон.

Особенность этой идеи описываемого подхода именно в том,

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

человека, который в гораздо большей

степени владеет предметной

областью, то есть построением численных схем, чем приёмами работы

с языками программирования общего назначения, такими как C++. Вся

концепция языков программирования предметной области (DSL)

направлена как раз на это, вот почему использование семейств или

даже иерархий DSL-языков представляется тут многообещающим

решением [4].

В докладе рассматривается примерная структура предлагаемого

подхода на

основе параллельного пакета GasDynamicsTool с учётом

всех описанных идей, даётся краткое представление уже

разработанных в рамках этого подхода описательных DSL и

предварительных проектов DSL описания. схемных вычислений.

248

Литература

1. Babayev D.B., Medvedev A.V. Architecture of Parallel CFD Code

for Hybrid Computer Systems // Parallel CFD 2003, May 13-15,

2003, Moscow, Russia. p. 285 - 287

Zibarov A.V., Babayev D.B., Mironov A.A., Komarov I.Yu.,

Konstantinov P.V. Modern Visualization Techniques in

ScientificVR(R) Package. // Proceedings of 10th International

Symposium on Flow Visualization. August 26-29, 2002, Kyoto,

Japan.

Engel K., Hadwiger M., Kniss J., Rezk-Salama C. High-Quality

Volume Graphics on Consumer PC Hardware. Course notes for

course No 42 at SIGGRAPH 2002.

. Lugovsky V.S Using a hierarchy of Domain Specific Languages

in complex Software systems design.

ИДЕЯ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА СИНТЕЗА

СТРАТЕГИЙ ОБСЛУЖИВАНИЯ ГРУППИРОВКИ

СТАЦИОНАРНЫХ ОБЪЕКТОВ

Д.В. Минаев, Ю.С. Федосенко, А.Ю. Шлюгаев

Волжская государственная академия водного транспорта

Введение

Исследуется задача синтеза стратегий одностадийного

обслуживания автономно перемещающимся процессором − mobile-

процессором [1] группировки стационарных объектов,

дислоцированных в границах существенно протяженной двумерной

рабочей зоны.

На содержательном уровне рассматриваемая математическая

модель обслуживания адекватно описывает технологию снабжения

топливом группировки плавучих дизель-электрических добывающих

комплексов (ПДК), осуществляющих русловую добычу нерудных

строительных материалов (НСМ). За навигацию объемы

добычи НСМ,

широко используемых в дорожном, гражданском и промышленном

строительстве, достигают нескольких десятков миллионов тонн.

Рабочая зона группировки ПДК представляет собой

крупномасштабный судоходный полигон со сложной русловой

249

топологией. Для иллюстрации на рис.1 представлен пример

дислокации группировки ПДК.

Рис. 1. Пример дислокации группировки ПДК в крупномасштабном

судоходном полигоне

В условиях высоких расходов по содержанию ПДК и цен на

дизельное топливо, сокращения возможностей предприятий по

созданию его технически значимых оперативных запасов основная

задача лица, принимающего решения, − диспетчера группировки

заключается в минимизации экономических потерь, связанных с

непроизводительными простоями добывающих комплексов. При этом

существенным обстоятельством, оказывающим влияние на работу

диспетчера, являются

жесткие ограничения на допускаемую штатным

регламентом длительность Δ формирования стратегий обслуживания.

Очевидно, что при должной формализации технологических

аспектов вышеописанная проблема может быть конструктивно решена

путем создания компьютерных систем поддержки организационного

управления процессами снабжения группировки ПДК дизельным

топливом. Основным препятствием, сдерживающим создание таких

систем, является отсутствие достаточно быстро работающих

алгоритмов синтеза

оптимальных и субоптимальных стратегий

обслуживания. И хотя определенное продвижение в разработке таких

алгоритмов было получено на основе идеологии динамического

программирования [2–3], все же их вычислительная сложность в

зависимости от n − количества стационарных объектов − остается

высокой и оценивается величиной

)2(

12 −n

. Как показали

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

случайных выборках начальных условий, уже для группировки из

двенадцати – тринадцати объектов продолжительность синтеза

оптимальной стратегии может существенно превышать значение

что неприемлемо для управления снабжением топливом в оперативном

режиме.

250

В силу указанного обстоятельства проблема разработки методик

синтеза оптимальных и субоптимальных стратегий обслуживания,

требующих при своей компьютерной реализации приемлемых для

практического применения временных затрат, остается актуальной и,

как представляется авторам, возможным направлением ее решения

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

Математическая модель обслуживания и постановка

экстремальной задачи

Имеется совокупность

)}(),...,2(),1({ noooO

стационарных

объектов, расположенных в вершинах

ni ,1=

связного

неориентированного графа

с базисной вершиной

. Все объекты

совокупности

подлежат однократному одностадийному

обслуживанию mobile-процессором

, в начальный момент времени

находящимся в вершине

. Для каждого объекта

)(io

(

ni ,1=

)

известен момент времени

)(it

, начиная с которого осуществимо его

обслуживание; заданы функции:

),( ti

− продолжительности

обслуживания, если оно начинается в момент

, и

),( ti

− индивидуального штрафа за обслуживание, завершающееся в

момент

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

по второму аргументу в нестрогом смысле. Укажем, что типичным для

практических приложений является задание функций

продолжительностей обслуживания в виде констант (

)(),( idtti

) и

функций индивидуального штрафа в виде кусочно-линейных

зависимостей вида:

⎩

⎨

⎧

++>−⋅

++≤

)()()()),(()(

)()()(,0

),(

itfidtittприitftia

itfidtittпри

Задана матрица

)},({ jivV

размерности

)1()1(

⋅

, где

),( jiv

− продолжительность перемещения процессора из вершины

вершину

графа

непосредственно (

∞

),( jiv

, если такое

перемещение недопустимо); время перемещения из вершины

вершину

может оказаться меньшим

),( jiv

, если переход

осуществляется через некоторые промежуточные вершины. Также

известны элементы матрицы

)},({ jilL

− продолжительности