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

Размещено на http://www.allbest.ru/

МНОГОУРОВНЕВЫЕ АЛГОРИТМЫ И СТРУКТУРЫ РАСПАРАЛЛЕЛИВАНИЯ РЕШЕНИЙ СИСТЕМ УРАВНЕНИЙ БОЛЬШОЙ РАЗМЕРНОСТИ

Нагорный Л.Я., Жуков И.А.

КМУГА, г.Киев, Украина

В последние годы производительность ЭВМ с параллельной архитектурой значительно возросла по сравнению с первыми однопроцессорными ЭВМ [1,2]. Однако сложность задач, связанных с расчетами в различных отраслях народного хозяйства растет еще быстрее. Этот разрыв можно сократить благодаря использованию диакоптических методов для разработки более эффективных алгоритмов и новых параллельных многопроцессорных вычислительных систем (ВС).

В докладе предлагается многоуровневая декомпозиция и организация распараллеливания решения систем линейных и нелинейных уравнений большой размерности. При этом исходная математическая модель (ММ) с разреженной матрицей коэффициентов после линеаризации и алгебраизации может быть значительных размеров, которую целесообразно представить в виде СЛАУ с блочно-диагональной матрицей с окаймлениями (БДМО) [3]

диакоптический метод алгоритм

где Hi, Xi и Qi -- квадратная подматрица коэффициентов размерности ni х ni (ni<<n, где n- порядок исходной системы уравнений; i=1,N) и ni-мерные подвекторы неизвестных переменных и правых частей уравнений i-й подсистемы соответственно; фi и ?i -- прямоугольные подматрицы размерности ni х nс и nс х ni соответственно; Wc, Xc и Qc -- квадратная подматрица связи подсистем размерности nс х nс (nс<<n) и nс-мерные подвекторы неизвестных переменных и правой части подсистемы уравнений связи.

Благодаря особенностям структуры блочной матрицы коэффициентов, обработка каждого блока или подсистемы уравнений может выполняться независимо на одном или нескольких процессорных элементах (ПЭ).

Блочное распараллеливание решения СЛАУ с БДМО в сочетании со статическим режимом распределения вычислений позволяет строить адаптивные алгоритмы, достаточно легко перестраиваемые для каждого класса ВМ и ВС с параллельной организацией вычислений, а также при изменении параметров решаемой задачи или количества используемых ПЭ.

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

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

На первом этапе при Wc=0 выполняются параллельно частичные исключения в i-ых подсистемах уравнений исходной системы

выделенных из (1), после чего они преобразуются к виду

где преобразованные подматрицы Hmi, Фmi и подвектор Qmi, а также сформированные в процессе решения подматрица Wci и подвектор правой части Qci уравнения подсистемы связи определяются выбранным методом решения СЛАУ.

На втором этапе формируются подматрица Kc и подвектор правой части Вc подсистемы уравнений связи

Kc = Wc + Wci ; Вc = Qc + Qci.(4)

На третьем этапе решается преобразованная подсистема уравнений связи

Kc Xc = Вc (5)

и определяется подвектор связи Хc.

На четвертом этапе определяются параллельно на N ПЭ подвекторы неизвестных переменных Xi из блочного уравнения

HmiXi = Qmi - ФmiXc,i=1,N. (6)

В результате получаем параллельно на N ПЭ значения всех компонент вектора неизвестных переменных для исходной

СЛАУ X=(X1, X2, .., XN, Xc)T=

= (x1,x2,…,xi,…,xn)T.

Приведенная выше вычислительная схема организации процесса решения СЛАУ большой размерности позволяет выделить в алгоритмах решения отдельные блоки вычислений. На первом и четвертом этапах -- 2N блоков, на втором -- 2 блока и на третьем -- один блок. Хотя в принципе, если количество ПЭ не ограничивать числом N, имеется возможность осуществит распараллеливание решения подсистемы уравнения связи на третьем этапе, а также преобразование подсистем уравнений на первом этапе.

В пределах каждого этапа вычислений между блоками отсутствуют функциональные связи, то есть не одна из входных переменный первого блока не является входной для j-го (i, j=1,N). Между блоками отсутствуют также связи по рабочим полям ЗУ, то есть отсутствуют обращения к одним и тем же ячейкам ЗУ при чтении и записи информации. Блоки независимы по управлению в том смысле, что условия выполнения i-го блока не зависят от признаков, вырабатываемых при выполнении j-го блока (i, j=1,N).

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

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

Последующие уровни декомпозиции распараллеливания решения СЛАУ внутри каждого i-го блока, связаны с применением прямых (Гаусса, Гаусса-Жордана, LU-разложения и др.) и итерационных методов решения подсистем уравнений.

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

Сформулируем концепцию [9,10] создания многоуровневых параллельных ВС для решения задач большой размерности, основным архитектурным принципом организации которых является принцип распараллеливания исходной ММ вида ?(X,Y)=0, где оператор ? определяет зависимость между вектором Y заданных и вектором X неизвестных величин. В зависимости от класса решаемых задач или сложности воспроизводимых ММ параллелльные ВС представляются мноуровневыми системами.

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

1) Распараллеливание ММ на логическом уровне заключается в аппаратной реализации элементарных функций ?(x) с помощью операционных узлов (регистров, сумматоров, дешифраторов, каналов передачи данных и др.).

2) Распараллеливание ММ ?(X,Y)=0 на микрооперационном уровне представляет собой аппаратно-программную реализацию функций yij=?ij(xij) (i-х управляющих функций и обработки прерываний; j-х командных функций, обеспечивающих алгоритмы преобразования информации).

3) Распараллеливание ММ ?(X,Y)=0 на уровне разрядов представления информации заключается в преобразовании ее в виде n-разрядных уравнений

), Y(0)=Y, ?(0)= ?,

на базе каждого из которых определяется значение соответствующего разряда неизвестного вектора X, которые в совокупности и представляют решение X.

4) Распараллеливание ММ ?(X,Y)=0 на уровне процессорного исполнения обеспечивается блоком управления процессором, который может быть реализован аппаратным и программным способами.

5) Распараллеливание ММ ?(X,Y)=0 на уровне системной обработки состоит в преобразовании множества потоков данных на множестве ПЭ или процессоров ВС под управлением одного или нескольких потоков команд.

Как следует из пунктов 1-5, в параллельных ВС диапазон реализуемого распараллеливания ММ достаточно широк, т.е. используются разные уровни распараллеливания, что обеспечивает универсальность создаваемой системы, однако по эффективности реализации отдельных уровней распараллеливания параллельных ВС могут уступать другим типам систем. Возможности ВС по реализации распараллеливания ММ ?(X,Y)=0 можно приблизительно оценить, используя показатели универсальности взаимодействий (функци-ональные возможности) и быстродействия взаимодействий (интенсивность). По этим показателям параллельные ВС разделяют на слабосвязанные мультисистемы (многомашинные ВС и сети вычислительных машин), многопроцессорные ВС (МПВС) и проблемно-ориентированные ВС. В слабосвязанных ВС быстродействие взаимодействий значительно ниже, чем в МПВС. Поэтому в таких ВС реализуется уровень распараллеливания очень крупных фрагментов работы. В проблемно-ориентированных параллельных ВС быстродействие взаимодействий может быть выше, чем в МПВС, а универсальность взаимодействий - значительно ниже. Поэтому проблемно-ориентированные параллельные ВС реализуют частные и вырожденные уровни распараллеливания и являются специализированными. Реальные ВС часто представляют собой комбинацию разных классов параллельных систем.

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

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

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

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

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

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

Литература

1.Хокни Р., Джессхоут К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы: Пер. с англ. - М.: Радио и связь, 1986. - 392 с.

2.Введение в кибернетическую технику. Параллельные структуры и методы /Малиновский Б.Н., Боюн В.П., Козлов Л.Г.; отв. ред. А.В. Палагин; АН УССР. Ин-т кибернетики им. В.М. Глушкова. -К.: Наукова думка, 1989. - 248 с.

3.Нагорный Л.Я. Декомпозиция и распараллеливание алгоритмов решения систем линейных уравнений большой размерности. -К.: Общество “Знание”, УССР, 1980. - 28 с.

4.Нагорный Л.Я. Моделирование электронных цепей на ЦВМ. - К.: Технiка, 1974. - 360 с.

5.Нагорный Л.Я., Кофто А.Г. Распараллеливание алгоритмов моделирования нелинейных систем большой размерности. Электронное моделирование, 1983, № 4, с. 45-51.

6.Нагорный Л.Я., Жуков И.А. Решение на ЭВМ больших систем нелинейных уравнений с разреженной структурой //Автоматизация проектирования в электронике.- К.: Технiка.- 1978. - Вып. 17.- С. 61-65.

7.Писсанецки С. Технология разреженных матриц: Пер. с англ. - М.: Мир, 1988. - 410 с.

8.Нагорный Л.Я. Об одном методе решения на ЦВМ больших систем уравнений с разреженной матрицей. Электронное моделирование, 1975, 18, № 6, с. 60 - 67.

9.Жуков И.А. Концепция создания параллельных вычислительных систем для решения задач большой размерности //Проблемы информатизации и управления. -К.: КМУГА, 1997. - Вып. 2. с. 3-7.

10. Жуков И.А. Методология синтеза параллельных вычислительных систем //Проблемы информатизации и управления. -К.: КМУГА, 1997. - Вып. 2. с. 7-10.

Размещено на Allbest.ru