Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 25)

Рис. 53. Зависимость ускорения S от числа процессоров p при распараллеливании метода обратной итерации поиска собственных функций на различные топологии многопроцессорных ВС.

1. Распараллеливание явного метода решения нелинейной динамической системы

1. Общая схема метода.

Рассмотрим систему трехмерных уравнений магнитной гидродинамики, описывающих течение жидкости, способной проводить электрический ток [90]. Система имеет следующий вид

(160)

Здесь - вектор решения, тензор системы F, определяющий плотности потоков, имеет вид

Из 21 элемента этого тензора только 12 являются различными.

Явная разностная схема для выписанной системы имеет вид

(161)

где P, Q, R - столбцы тензора F.

На рис.54 изображен граф такой вычислительной модели на одном временном шаге. Он имеет 26 вершин, распределенных по трем ярусам. Первый ярус составляют вершины, имеющие нулевой вес и определяющие рассылку компонентов вектора u с предыдущего временного шага. На втором ярусе располагаются вершины, соответствующие операциям по подсчету элементов тензора F. Данные вершины имеют веса (N³, N³, N³, 5N³, 3N³, 3N³, 5N³, 3N³, 5N³, 2N³, 2N³, 2N³), где N - число узлов сетки по каждому направлению. На третьем уровне находятся вершины, соответствующие операциям по пересчету вектора u по формулам (161). Их веса равны (3N³, 3N³, 3N³, 3N³, 2N³, 2N³, 2N³). Каждая из дуг графа обозначает пересылку одного трехмерного массива, поэтому вес всех дуг равен N слов, и если положить, что 1 слово = 4 байта, то вес дуг равен 64N Бт.

Рис. 54. Граф явного метода решения нелинейной динамической системы.

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

Видно, что функционал J(R) для данной модели от N не зависит, т.к. веса всех вершин и дуг есть величины одного порядка 0(N³). Следовательно, можно сделать вывод, что задачу поиска оптимального распараллеливания модели можно решать только при одном N (например, при N = 1), и это решение будет справедливо для всех N >> 1.

С помощью системы PARALLAX было проведено исследование зависимости ускорения S от числа процессоров p и времени передачи единицы информации t для вышеописанного явного метода. Результаты этого исследования отражены на рис. 55. Из представленных на нем графиков видно, что ускорение может быть достигнуто только при достаточно большой, по сравнению с производительностью процессоров - производительности каналов связи. Так, для вычислительных систем, в которых выполняется условие, ускорение ведет себя практически линейно по числу процессоров для p 7. Дальнейшее увеличение числа процессоров на ускорение практически не влияет, хотя степень параллелизма анализируемого графа и больше 7.

Рис. 55. Зависимость ускорения S, достигаемого при распараллеливании явного метода решения нелинейной динамической системы, от времени t передачи единицы информации по каналам ВС для разного числа процессоров p.

В результате проведенных исследований были получены следующие основные результаты.

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

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

С помощью программной системы PARALLAX было проведено численное исследование распараллеливания ряда наиболее распространенных алгоритмов линейной на различные архитектуры мультитранспьютерных вычислительных систем. Исследована зависимость эффективности выполнения нескольких блочных алгоритмов линейной алгебры на полносвязных топологиях ВС от параметров ВС и параметров алгоритмов. Показано, что поведение полученных численно кривых S(p) (где за S обозначено достигаемое при распараллеливании ускорение) совпадает с поведением ускорения, полученного из расчетов на реальных многопроцессорных ВС - сначала линейный рост, затем выход на плоский максимум, и, наконец, постепенное уменьшение ускорения, что обусловлено возрастающими временными затратами на организацию обменов данными при увеличении числа процессоров.

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

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

Таким образом, полученные теоретические и численные результаты, а также тестирование программной системы PARALLAX на распараллеливании реальных вычислительных алгоритмов, графы которых содержат сотни вершин, показывают, что распараллеливание больших вычислительных алгоритмов на мультитранспьютерные системы с большим числом транспьютерных элементов может быть успешно проведено с помощью разработанных стохастических методов [91, 92, 93, 94, 95].

3.7. ПРОГРАММНО - АППАРАТНЫЙ КОМПЛЕКС ДЛЯ СИНТЕЗА, ИССЛЕДОВАНИЯ И ОТРАБОТКИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

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

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

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

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

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

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

Одно из важных мест в этом сквозном проектировании - обоснование и разработка проблемно-ориентированного на специалиста по управлению комплекса - Программно-Аппаратной Среды сквозного проектирования, в составе которого становится возможным не только проверить исходные предпосылки, но предложить и отработать конкретные варианты (транспьютерной) реализации.

Предлагаемый вариант структуры среды (см. рис.56) включает две связанные между собой части: исследовательскую и транспьютерной реализации.

Исследовательская часть выполняется на универсальной математической платформе (например, MATLAB-SIMULINK или МВТУ), приспособленной для синтеза и тщательной отработки разнообразных математических моделей не в реальном времени.

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

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

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

Характеристики

Список файлов книги