Пупков К.А., Коньков В.Г. Интеллектуальные системы (1-е изд., 2001) (1245264), страница 29
Текст из файла (страница 29)
Он имеет 26 вершин, распределенных по трем ярусам. Первыйярус составляют вершины, имеющие нулевой вес и определяющие рассылкукомпонентов вектора u с предыдущего временного шага. На втором ярусерасполагаются вершины, соответствующие операциям по подсчету элементовтензора F. Данные вершины имеют веса (N3, N3, N3, 5N3, 3N3, 3N3, 5N3, 3N3, 5N3,2N3, 2N3, 2N3), где N - число узлов сетки по каждому направлению. На третьемРис. 54.
Граф явного метода решения нелинейной динамической системы.Распараллеливание метода.Видно, что функционал J(R) для данной модели от N не зависит, т.к.веса всех вершин и дуг есть величины одного порядка 0(N3). Следовательно,можно сделать вывод, что задачу поиска оптимального распараллеливаниямодели можно решать только при одном N (например, при N = 1), и это решениебудет справедливо для всех N >> 1.С помощью системы PARALLAX было проведено исследованиезависимости ускорения S от числа процессоров p и времени передачи единицыинформации t для вышеописанного явного метода.
Результаты этогоисследования отражены на рис. 55. Из представленных на нем графиков видно,что ускорение может быть достигнуто только при достаточно большой, посравнению с производительностью процессоров - производительности каналовсвязи. Так, для вычислительных систем, в которых выполняется условие,ускорение ведет себя практически линейно по числу процессоров для p 7.Дальнейшее увеличение числа процессоров на ускорение практически не98влияет, хотя степень параллелизма анализируемого графа и больше 7.Рис. 55.
Зависимость ускорения S, достигаемого при распараллеливании явногометода решения нелинейной динамической системы, от времени t передачиединицы информации по каналам ВС для разного числа процессоров p.В результате проведенных исследований были получены следующиеосновные результаты.Поставлена задача отображения алгоритмов, представленныхвзвешеннымиграфамибольшойразмерности,наархитектурымультитранспьютерных вычислительных систем, содержащих большое числотранспьютерных элементов.
Проведено теоретическое и численноеисследование поставленной задачи. Исследование показало, что функционал,подлежащий минимизации, обладает ярко выраженной овражной структурой исодержит большое число локальных минимумов, что затрудняет и даже делаетневозможным применение большинства методов решения подобных задач различных эвристических методов, методов безусловного спуска, методовнаискорейшего спуска и т.п. Единственной возможной альтернативой этимметодам является использование стохастических алгоритмов.Разработан ряд стохастических методов решения поставленнойоптимизационной задачи распараллеливания вычислений.
В первом методе стохастическом методе попарной оптимизации подграфов - поиск оптимальногорешения осуществляется за счет взаимного (стохастического) переноса вершинмежду различными парами подграфов графа алгоритма. Второй метод - методМонте-Карло случайного блуждания вершин графа алгоритма по подграфам основан на отождествлении вершин графа алгоритма с некоторыми частицами,совершающими случайные блуждания по областям-подграфам в потенциальномсиловом поле, роль потенциала которого играет минимизируемый функционал.Наиболее вероятное состояние подобной системы частиц соответствуетминимуму потенциала - и следовательно, является искомым решением. Поисктакого состояния осуществляется методом Монте-Карло с использованиемспециальной процедуры «имитации отжига».
Третий метод - стохастическийметод наискорейшего спуска - основан на использовании дискретного аналогаградиента минимизируемого функционала. Все разработанные методыреализованы программно и являются частью системы программ PARALLAX.Проведено тестирование созданных программ и сравнение их работы напростейших примерах.С помощью программной системы PARALLAX было проведеночисленное исследование распараллеливания ряда наиболее распространенныхалгоритмов линейной на различные архитектуры мультитранспьютерныхвычислительных систем. Исследована зависимость эффективности выполнениянескольких блочных алгоритмов линейной алгебры на полносвязныхтопологиях ВС от параметров ВС и параметров алгоритмов.
Показано, чтоповедение полученных численно кривых S(p) (где за S обозначено достигаемоепри распараллеливании ускорение) совпадает с поведением ускорения,полученного из расчетов на реальных многопроцессорных ВС - сначалалинейный рост, затем выход на плоский максимум, и, наконец, постепенноеуменьшение ускорения, что обусловлено возрастающими временнымизатратами на организацию обменов данными при увеличении числапроцессоров.Проведен численный анализ зависимости ускорения, достигаемого прираспараллеливании явного метода решения системы нелинейных динамическихсистем от параметров ВС - числа процессоров и скорости работы каналовобмена данными.
Т.к. веса всех вершин и дуг графа этого алгоритма естьвеличины одного порядка по N(где N есть размерность задачи), то увеличениеN, в отличие от рассмотренных выше алгоритмов линейной алгебры, наускорение никак не влияет. По причине больших объемов передаваемых данныхпри выполнении алгоритма, ускорение больше 1 достигается только на оченьвысоких (относительно производительности процессоров) скоростях каналов,что делает рассмотренный метод мало пригодным к выполнению набольшинстве реальных многопроцессорных ВС с распределенной памятью, укоторых производительности процессоров и каналов приблизительносовпадают.99Проанализирована эффективность выполнения алгоритма обратнойитерации для нахождения собственных функций на ВС с различнымитопологиями межтранспьютерных связей.
Рассмотрены следующие топологии полносвязная, гиперкуб, двумерные тор и решетка, звезда, кольцо и линейнаяцепочка. Построены зависимости ускоренияот числа процессоров ВС.Показано, что полученная при этом иерархия рассмотренных топологий (постепени эффективности выполнения на них рассматриваемого алгоритма) восновном совпадает с иерархией, принятой в современной литературе попараллельным вычислениям.Таким образом, полученные теоретические и численные результаты, атакже тестирование программной системы PARALLAX на распараллеливанииреальных вычислительных алгоритмов, графы которых содержат сотни вершин,показывают, что распараллеливание больших вычислительных алгоритмов намультитранспьютерные системы с большим числом транспьютерных элементовможет быть успешно проведено с помощью разработанных стохастическихметодов [91, 92, 93, 94, 95].1003.7.
ПРОГРАММНО - АППАРАТНЫЙ КОМПЛЕКС ДЛЯ СИНТЕЗА,ИССЛЕДОВАНИЯ И ОТРАБОТКИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВВ значительной степени существующие алгоритмы обработки относятся кпараллельным. Однако чаще всего они приводились и приводятся кпоследовательной форме, чтобы быть выполненными на вычислительныхсредствах последовательного действия.Появление вычислительных сетей, состоящих из большого числавзаимодействующих процессоров, позволило организовать принципиальнопараллельный режим обработки. Именно на распределенные вычислительныесистемы адаптируется широкий класс алгоритмов.Параллельная обработка отличается от последовательной тем, что некотороечисло отдельных компонент алгоритма может выполняться одновременно наразных процессорах. Причем, чем больше число таких компонент, тем вышестепень параллелизма.Важным свойством такой параллельной обработки является существенноеуменьшение времени расчета алгоритма, а, в ряде случаев, и повышениенадежности вычислений.
Отсюда такая важность распределенных средств длясистем управления (СУ). При этом ценными свойствами распределенных СУстановится однородность строения системы управления на всех ее уровнях ибольшие вычислительные мощности.Общие свойства параллельной (в частности, транспьютерной) технологии,опирающиеся на разнообразную номенклатуру ее элементов, позволилипрактически оформить концепцию сквозного проектирования системыуправления.Сквозное проектирование - это процесс, устраняющий границу между этапамидинамического синтеза системы, то есть синтезом математических моделейзакона управления и этапом (транспьютерной) реализации этого закона.Одно из важных мест в этом сквозном проектировании - обоснование иразработка проблемно-ориентированного на специалиста по управлениюкомплекса - Программно-Аппаратной Среды сквозного проектирования, всоставе которого становится возможным не только проверить исходныепредпосылки, но предложить и отработать конкретные варианты(транспьютерной) реализации.Предлагаемый вариант структуры среды (см.
рис.56) включает две связанныемежду собой части: исследовательскую и транспьютерной реализации.Исследовательская часть выполняется на универсальной математическойплатформе (например, MATLAB-SIMULINK или МВТУ), приспособленной длясинтеза и тщательной отработки разнообразных математических моделей не вреальном времени.Вторая часть - среда транспьютерной реализации (СТР) содержитуниверсальнуюпрограммнуюподдержкудляввода,отображения,автоматическогопереходакописаниюнапараллельномязыке,конфигурирования и загрузки параллельных программ, и элементытранспьютерной технологии, позволяющие использовать или транспьютернуюплату в PC, или линковую связь с реальной транспьютерной сетью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
