Содержание к диссертации
Введение
1 Метод сопряженных градиентов (МСГ) 10
1.1 Прямые и итерационные методы решения линейных систем . 10
1.2 Описание предобусловленного метода сопряженных градиентов 12
1.3 Оценка сходимости МСГ через спектральное число обусловленности 14
1.4 Оценка сходимости МСГ через К-число обусловленности . 15
1.5 Устойчивость предобусловливаний МСГ 16
2 Методы приближенных треугольных разложений 18
2.1 Предобусловливания, основанные на треугольном разложении 18
2.2 Неполные и приближенные треугольные разложения . 19
2.3 Предварительное масштабирование как этап предобусловливания 22
2.4 Теория приближенного треугольного разложения 2-го порядка 23
2.4.1 Приближенное треугольное разложение 2-го порядка 23
2.4.2 Улучшение обусловленности, достигаемое применением приближенных треугольных разложений 24
2.4.3 Устойчивость приближенных треугольных разложений 26
2.5 Алгоритмы безотказного приближенного треугольного разложения 27
2.6 Трудности распараллеливания 1С2 разложения 28
3 Параллелизуемое аддитивное предобусловливание 31
3.1 Методы построения параллельных предобусловливаний . 31
3.1.1 Использование окаймленной блочно-диагональной структуры 31
3.1.2 Использование приближенных обратных матриц . 34
3.2 Блочное неполное обратное треугольное разложение 35
3.2.1 Построение ВНС-предобусловливания 36
3.2.2 Оценка качества предобусловливания по методу ВНС-1С2 39
3.3 Диагональное и блочно-диагональное предобусловливание . 46
4 Параллельная реализация и балансировка вычислений 48
4.1 Параллельные ЭВМ и параллельные вычисления 48
4.2 Параллельная реализация итерационных методов 52
4.3 Описание параллельной реализации 62
4.4 Способы балансировки вычислений 65
4.5 Теоретический анализ стратегий постфильтрации построенного предобусловливателя 66
4.6 Описание реализации балансировки и применения параллельного ВНС-1С2-предобусловливания 73
5 Численные эксперименты 77
5.1 Тестовые задачи и методика проведения численных экспериментов 77
5.2 Численные эксперименты для задач упругости тонкостенных оболочек 82
5.3 Численные эксперименты для задач теории линейной упругости в механике упругого тела 89
5.4 Численные эксперименты по балансировке вычислений для задач из коллекции университета Флориды 108
5.5 Сравнение метода ВНС-1С2-МСГ с другими методами . 122
Заключение 124
Литература 126
Введение
- Оценка сходимости МСГ через спектральное число обусловленности
- Улучшение обусловленности, достигаемое применением приближенных треугольных разложений
- Использование окаймленной блочно-диагональной структуры
- Теоретический анализ стратегий постфильтрации построенного предобусловливателя
Введение к работе
Объект исследования и актуальность темы. Актуальность темы диссертационной работы обусловлена необходимостью эффективного численного решения систем линейных алгебраических уравнений с разреженными симметричными положительно-определенными матрицами большой размерности. Численное решение систем линейных уравнений является одной из наиболее часто встречающихся задач в научно-технических исследованиях и практических приложениях. Подобные задачи возникают, например, в математической физике при численном решении дифференциальных и интегральных уравнений. При этом прикладные задачи часто требуют решения систем линейных уравнений с большим числом неизвестных. К таким системам, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов. Для возникающих систем линейных уравнений применение прямых методов решения оказывается неприемлемым как по причине большого времени решения, так и недостаточности объема оперативной памяти для хранения данных задачи. Итерационные методы решения систем линейных уравнений намного экономичнее с точки зрения использования оперативной памяти, но для ускорения их сходимости требуется строить эффективные предобусловливания, особенно при решении систем с плохо обусловленными матрицами.
Существенные затруднения связаны с тем, что наиболее актуальной задачей является решение систем линейных уравнений настолько большой размерности, что их решение возможно только на современных параллельных ЭВМ с распределенной памятью, что подразумевает разбиение данных на блоки, каждый из которых обрабатывается отдельным процессором. Поэтому для таких многопроцессорных вычислительных машин необходимо построение специальных параллельных предобусловливаний, использующих разбиение на блоки матрицы решаемой системы. Причем для универсальности метода требуется построение разбиения на блоки без привлечения информации о пространственном расположении узлов расчетной сетки.
Эффективность использования каждого процессора многопроцессорной ЭВМ в конечном итоге определяет эффективность решения задачи в целом, поэтому регулирование загруженности процессоров также является актуальной задачей. Использование специальных методов балансировки вычислений на различных процессорах призвано решить задачу повышения эффективности параллельных вычислений.
Целью диссертационной работы является разработка, исследование и реализация на параллельных ЭВМ высокопроизводительного итерационного метода решения жестких систем линейных алгебраических уравнений с разреженными симметричными положительно-определенными матрицами, а также численные исследования работоспособности предложенного метода для различных типов плохо обусловленных систем линейных уравнений.
В соответствии с целью исследования были поставлены следующие задачи:
1. Разработка и исследование параллельного итерационного предобус- ловленного метода решения жестких систем линейных алгебраических уравнений с разреженными симметричными положительно- определенными матрицами.
2. Разработка эффективного способа балансировки вычислений для подзадач на различных процессорах.
3. Исследование эффективности метода в зависимости от параметров предобусловливания и количества процессоров.
4. Подтверждение эффективности метода для различных типов решаемых задач и на различных вычислительных системах.
Методы исследования. В диссертационной работе используется математический аппарат численных методов, теории итерационных алгоритмов, линейной алгебры, теории графов, методов параллельного программирования.
Научная новизна:
1. Установлено, что при однопроцессорной реализации методов решения систем линейных уравнений с симметричными положительно- определенными матрицами, метод приближенного треугольного разложения второго порядка существенно превосходит по качеству пре- добусловливания аналогичные методы первого порядка.
2. Показано, что предложенная схема построения параллельного предо- бусловливания имеет более высокую скорость сходимости по сравнению с некоторыми известными схемами типа декомпозиции области.
3. Предложена комбинация приближенного треугольного разложения второго порядка и неполного обратного треугольного разложения, позволяющая получить высокое качество параллельного предобуслов- ливания.
4. Разработана новая методика балансировки вычислений на основе восполнения треугольных сомножителей элементами матрицы ошибок и показана надежность и эффективность ее применения.
5. Проведены численные эксперименты, показавшие, что как общие арифметические затраты, так и количество итераций для предложенного метода слабо зависят от количества используемых процессоров по сравнению с известными параллельными предобусловливаниями.
6. Численными экспериментами подтверждена теоретически обоснованная высокая параллельная эффективность и вычислительная надежность разработанного метода.
Научная и практическая ценность. Разработан параллельный метод решения жестких систем линейных алгебраических уравнений с симметричными положительно-определенными матрицами, который может быть использован во многих приложениях. Предложенный метод показал высокую надежность и эффективность при решении задач из самых различных научных и практических областей применения. Выполненная работа вносит теоретический и практический вклад в развитие высокопроизводительных параллельных вычислений, так как она призвана не только решить проблему экономии памяти и сокращения времени вычислений при решении систем линейных уравнений, но и сделать возможным решение задач, которые ранее в принципе не могли быть решены на однопроцессорных компьютерах.
Положения, выносимые на защиту:
1. Теоретические основы построения эффективного параллельного пре- добусловливания для решения систем линейных алгебраических уравнений с симметричными положительно-определенными матрицами.
2. Методика балансировки вычислений на основе восполнения треугольных сомножителей элементами матрицы ошибок.
3. Результаты практического исследования эффективности предложенного алгоритма на тестовых и прикладных задачах, его вычислительных и коммуникационных затрат, а также времени счета при изменении параметров предобусловливания и количества процессоров.
Обоснованность и достоверность результатов основывается на строгих математических доказательствах и проверке теории в численных экспериментах. Эффективность построения параллельного предобусловливания обосновывается использованием широкого ряда тестовых задач для верификации полученных численных результатов, а также прямым сравнением результатов расчетов с результатами, полученными при использовании других предобусловливаний семейства блочных методов Якоби. Достоверность того, что предложенный метод является эффективным, подтверждена результатами расчетов и сравнением с результатами других авторов на примере задач из коллекции университета Флориды.
Апробация работы. Результаты работы докладывались и обсуждались на международной конференции "РаСТ99" (Санкт-Петербург, Россия, 1999 г.), Всемирном 16-ом Конгрессе "IMACS 2000" по научным вычислениям, прикладной математике и моделированию (Лозанна, Швейцария, 2000), Голландско-российском симпозиуме NWO (МГУ, Москва, июнь 2000), Симпозиуме NWO (Амстердам-Ниймеген, Голландия, ноябрь 2000), Втором Международном научно-практическом Семинаре и Всероссийской молодежной школе "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород, Россия, 2002), Международной конференции "Parallel CFD 2003" (Москва, 2003), Международной конференции "VIII Забабахинские научные чтения" (РФЯЦ-ВНИИТФ, Сне- жинск, Россия, 2005), Международной конференции по численной геометрии, построении расчетных сеток и научным вычислениям "NUM- GRID2008" (ВЦ РАН, Москва, 2008), на научно-исследовательских семинарах Вычислительного центра РАН, Московского физико-технического института, Института автоматизации проектирования РАН, а также на семинарах Департамента информационных технологий Республики Индия (С- DAC, Пуна, Индия), Institut Franais du Ptrol (Париж, Франция), ExxonMobil Upstream Research Co. (Хьюстон, США).
Личный вклад соискателя. В работах соискателя соавтором является научный руководитель Капорин И. Е., ему принадлежит постановка задач и выбор математических методов исследований. Соискателем проведены теоретические исследования, разработаны параллельные предобус- ловливания, выполнены параллельные реализации предложенных алгоритмов и исследованы границы применения предложенных методов.
Публикации. Основные публикации по теме диссертации включают 11 работ, из них 3 работы [27, 28, 37] в ведущих отечественных и международных рецензированных научных изданиях, рекомендованных ВАК, 3 в других международных рецензируемых изданиях, 1 в российском рецензируемом издании, 1 в трудах международной конференции, 3 публикации в других научных изданиях.
Кроме того, по теме диссертации имеются публикации в трудах и тезисах 7 всероссийских и 16 международных конференций.
Структура и объем работы. Диссертационная работа состоит из введения, 5 глав, заключения, списка литературы, содержит 18 таблиц и 23 рисунка. Объем работы 138 страниц. Список литературы включает в себя 112 наименований.
Оценка сходимости МСГ через спектральное число обусловленности
Научная и практическая ценность. Разработан параллельный метод решения жестких систем линейных алгебраических уравнений с симметричными положительно-определенными матрицами, который может быть использован во многих приложениях. Предложенный метод показал высокую надежность и эффективность при решении задач из самых различных научных и практических областей применения. Выполненная работа вносит теоретический и практический вклад в развитие высокопроизводительных параллельных вычислений, так как она призвана не только решить проблему экономии памяти и сокращения времени вычислений при решении систем линейных уравнений, но и сделать возможным решение задач, которые ранее в принципе не могли быть решены на однопроцессорных компьютерах.
Положения, выносимые на защиту: 1. Теоретические основы построения эффективного параллельного пре- добусловливания для решения систем линейных алгебраических уравнений с симметричными положительно-определенными матрицами. 2. Методика балансировки вычислений на основе восполнения треугольных сомножителей элементами матрицы ошибок. 3. Результаты практического исследования эффективности предложенного алгоритма на тестовых и прикладных задачах, его вычислительных и коммуникационных затрат, а также времени счета при изменении параметров предобусловливания и количества процессоров.
Обоснованность и достоверность результатов основывается на строгих математических доказательствах и проверке теории в численных экспериментах. Эффективность построения параллельного предобусловливания обосновывается использованием широкого ряда тестовых задач для верификации полученных численных результатов, а также прямым сравнением результатов расчетов с результатами, полученными при использовании других предобусловливаний семейства блочных методов Якоби. Достоверность того, что предложенный метод является эффективным, подтверждена результатами расчетов и сравнением с результатами других авторов на примере задач из коллекции университета Флориды.
Апробация работы. Результаты работы докладывались и обсуждались на международной конференции "РаСТ99" (Санкт-Петербург, Россия, 1999 г.), Всемирном 16-ом Конгрессе "IMACS 2000" по научным вычислениям, прикладной математике и моделированию (Лозанна, Швейцария, 2000), Голландско-российском симпозиуме NWO (МГУ, Москва, июнь 2000), Симпозиуме NWO (Амстердам-Ниймеген, Голландия, ноябрь 2000), Втором Международном научно-практическом Семинаре и Всероссийской молодежной школе "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород, Россия, 2002), Международной конференции "Parallel CFD 2003" (Москва, 2003), Международной конференции "VIII Забабахинские научные чтения" (РФЯЦ-ВНИИТФ, Сне- жинск, Россия, 2005), Международной конференции по численной геометрии, построении расчетных сеток и научным вычислениям "NUM- GRID2008" (ВЦ РАН, Москва, 2008), на научно-исследовательских семинарах Вычислительного центра РАН, Московского физико-технического института, Института автоматизации проектирования РАН, а также на семинарах Департамента информационных технологий Республики Индия (С- DAC, Пуна, Индия), Institut Franais du Ptrol (Париж, Франция), ExxonMobil Upstream Research Co. (Хьюстон, США).
Личный вклад соискателя. В работах соискателя соавтором является научный руководитель Капорин И. Е., ему принадлежит постановка задач и выбор математических методов исследований. Соискателем проведены теоретические исследования, разработаны параллельные предобус- ловливания, выполнены параллельные реализации предложенных алгоритмов и исследованы границы применения предложенных методов.
Публикации. Основные публикации по теме диссертации включают 11 работ, из них 3 работы [27, 28, 37] в ведущих отечественных и международных рецензированных научных изданиях, рекомендованных ВАК, 3 в других международных рецензируемых изданиях, 1 в российском рецензируемом издании, 1 в трудах международной конференции, 3 публикации в других научных изданиях. Кроме того, по теме диссертации имеются публикации в трудах и тезисах 7 всероссийских и 16 международных конференций.
Структура и объем работы. Диссертационная работа состоит из введения, 5 глав, заключения, списка литературы, содержит 18 таблиц и 23 рисунка. Объем работы 138 страниц. Список литературы включает в себя 112 наименований. В этой главе рассматривается метод сопряженных градиентов (МСГ), применяющийся для решения линейных систем в случае, если матрица системы является симметричной положительно-определенной (с.п.о.). Обсуждаются также вопросы, связанные с построением и оптимизацией предо- бусловливаний для этого метода.
Рассмотрены итерационные методы решения систем линейных алгебраических уравнений, приводятся особенности их применения, в частности, указано, когда их применение может быть более эффективно по сравнению с прямыми методами решения. Показана необходимость построения предо- бусловливания для ускорения сходимости итерационных методов, особенно для достаточно жестких задач. 1
Улучшение обусловленности, достигаемое применением приближенных треугольных разложений
Как уже упоминалось в предыдущей главе, методы "точной" треугольной факторизации примененные к численному решению системы линейных уравнений с невырожденной разреженной с.п.о. п х тг-матрицей А общего вида, могут потребовать чрезмерно больших вычислительных ресурсов. Это происходит, если свойства структуры разреженности матрицы таковы, что имеет место сильное заполнение треугольного сомножителя U (даже если перестановка Р близка к наилучшей). Так, известно [90], что nz(U) оценивается снизу через квадрат числа узлов, образующих минимальный сепаратор неориентированного графа, отвечающего структуре разреженности А. Этим объясняется трудность применения точной треугольной факторизации к матрицам, отвечающим дискретным моделям на трехмерных пространственных сетках, особенно в случаях, когда одновременно моделируются несколько связанных физических полей и/или используются шаблоны аппроксимации с увеличенным числом узлов.
С другой стороны, итерационные методы, используемые со "слабым" предобусловливанием, например, типа точечного метода Якоби: где И а = diag(A), обычно требуют выполнения непредсказуемо большого числа итераций, если матрица системы плохо обусловлена. Таким образом, значительно опережая методы точной факторизации по экономии памяти, они могут тратить гораздо больше времени на решение. Наиболее перспективным в настоящее время считается сочетание вышеупомянутых двух подходов, приводящее к МСГ, предобусловленному при помощи приближенного треугольного разложения где Е представляет собой матрицу погрешности. Предобусловливатель при этом строится в виде Следует отметить, что введение такого сложного предобусловливания в итерационный метод влечет неизбежные затраты (а) перед итерациями, когда необходимо вычислить треугольный множитель и и (б) на каждой итерации, где необходимо решать две системы с треугольными матрицами. В случае, когда выбор матрицы и не обеспечивает достаточного сокращения числа итераций МСГ, эти затраты могут даже превысить предполагаемый выигрыш (иначе говоря, простейший алгоритм Якоби-МСГ решит задачу быстрее). Поэтому ключевым является вопрос о построении приближенного разложения, способного существенно улучшать подходящую меру обусловленности матрицы НА, используя сравнительно небольшое количестве ненулевых элементов матрицы 17. 2.2. Неполные и приближенные треугольные разложения Среди методов построения таких разложений можно выделить два основных подхода: неполные и приближенные треугольные разложения. Неполные треугольные разложения Разложения первого типа можно назвать неполными разложениями, или "разложениями по позициям". Здесь структура разреженности матрицы и фиксируется заранее, и алгоритмы неполного разложения получаются из алгоритмов полного разложения путем вставки операций замены на нули тех ненулевых элементов матрицы и, которые не вписываются в эту структуру разреженности. Простейшим вариантом являются "алгоритмы без заполнения" типа 1С(0) (см., например, [88]), а более сложные их версии, обозначаемые 1С(к): допускают заполнение на фиксированную глубину уровней. Теоретическим критерием качества таких предобуслов- ливаний служит оценка спектрального числа обусловленности где 71 и 72 представляют собой (положительные) границы обобщенного отношения Рэлея у АУ 71 утитиу 72 Для разреженных матриц специального вида (с диагональным преобладанием и неположительными внедиагональными элементами), например, отвечающих простым аппроксимациям уравнений эллиптического типа на регулярных сетках, известны многочисленные результаты, детализирующие оценки указанного вида. Однако следует отметить, что для с.п.о. матриц общего вида предобусловливания такого типа не только не поддаются содержательному теоретическому анализу, но и не известны их конкурентоспособные алгоритмические реализации.
При этом основным препятствием является тот факт, что, в отличие от точного треугольного разложения, неполное треугольное разложение в общем случае может привести к появлению неположительных ведущих элементов. Всякие попытки "адаптивной коррекции" такой ситуации в рамках жестко фиксированной структуры заполнения, как правило, ведут к резкому ухудшению качества соответствующего предобусловливания. Априорная коррекция, заключающаяся в применении того же алгоритма 1С (к) к сдвинутой матрице А + a;diag(y4.) (см., например, [92]), может приводить к более качественным предобусловливаниям, однако для этого требуется достаточно точный подбор параметра ш 0, что является весьма дорогостоящей процедурой. Если же принять возникающую ситуацию как "естественную", то возникают экзотические методики [51], основанные на использовании разложения типа А = LDLT + Е и предобусловливателя Н = L-:rZ)-1L 1, где L - верхнетреугольная матрица с единичной диагональю, а D — невырожденная диагональная матрица, возможно, с отрицательными элементами. Такие методы также исключены из рассмотрения, так как для них не известны теоретические оценки качества предобуслов- ливания, а при практической реализации они требуют использования итерационных схем, отличных от МСГ, и не обладают достаточной эффективностью.
Более подходящим инструментом предобусловливания показали себя разложения другого типа, которые можно назвать приближенными разло- оюениями, или "разложениями по значению". Здесь структура разреженности матрицы заранее не известна и определяется естественным образом в процессе факторизации. Алгоритмы приближенных разложений получаются из алгоритмов полного разложения путем вставки операций замены на нули тех ненулевых элементов матрицы U, которыми можно пренебречь в соответствии с некоторым подходящим числовым критерием, зависящим от малого параметра т - порога отсечения малых элементов. Понятно, что в этом случае для нормы матрицы ошибок Е типичным поведением является убывание, наблюдающееся при уменьшении параметра т.
В случае приближенных треугольных разложений, ключевым моментом остается обеспечение устойчивости разложения, то есть гарантированное отсутствие неположительных ведущих элементов без нарушения условия малости модулей элементов матрицы ошибок Е. В нашем случае оказывается возможным удовлетворить даже этому весьма ограничительному требованию. Такие алгоритмы приближенного разложения с.п.о. матриц будем называть безотказными.
Теоретическое исследование качества предобусловливания посредством приближенного треугольного разложения оказывается возможным как с использованием спектрального числа обусловленности, так и с привлечением К-обусловленности.
Использование окаймленной блочно-диагональной структуры
Нетривиальным вопросом является алгоритмическая реализация предлагаемого метода, в частности проблема хранения матрицы Я. Для фактического вычисления треугольного разложения 2-го порядка, помимо параметра отсечения малых элементов г вводятся: вторичный порог отсечения Г2 = 0(т2), параметр предварительного диагонального сдвига а = 0{т2) и параметр релаксации в 6 [0,1] в процедуре усечения (типа Дженнингса-Малика), которой отвечает матрица В. Если наложить на матрицу II условие т, а на матрицу Я - условие г \г1,з\ т2 причем принять, что структуры разреженности и и Я не имеют общих позиций, то они могут быть определены рекурсивно из покомпонентной записи формулы Вычисления могут быть организованы по так называемой компактной схеме, где последовательно вычисляются строки II и Я. При этом, особенно если матрица А предварительно переупорядочена с целью уменьшения максимальной ширины ленты, например, с использованием переупорядочивания по алгоритму типа Катхилл-Макки [65], периодическое сжатие матрицы Я за счет удаления уже отработанных столбцов, позволяет свести к минимуму затраты памяти, связанные с ее вовлечением в рекуррентные формулы. Матрицы U и R молено хранить вместе в виде суммы U+R, используя для последней матрицы сжатую схему хранения по строкам. Напомним также, что здесь подразумевается, что матрица А предварительно отмасштабирована к единичной диагонали. Отметим особо, что при 9 — 1 и неотрицательных значениях остальных параметров, построенный алгоритм приближенной факторизации является безотказным (см. 2.2).
Таким образом, если на вход факторизации подана положительно определенная матрица, то (при достаточной рабочей памяти) алгоритм обязательно выдаст в результате треугольный сомножитель U. Никаких делений на нуль или извлечений корня из отрицательного числа здесь не будет. И напротив, если появился неположительный ведущий элемент, то можно с уверенностью заключить, что на вход была подана матрица А, не являющаяся положительно определенной.
Ввиду рекуррентности формул исключения Гаусса, применяемых в неполных треугольных разложениях, их непосредственное распараллеливание сталкивается со значительными трудностями. Этот алгоритм не может быть эффективно реализован на многих важных типах параллельных ЭВМ.
Однако существуют подходы, использующие специальные перестановки строк и столбцов матрицы А для приведения ее к блочно- диагональному окаймленному виду (Block Diagonal Bordered, BDB). После такой перестановки на главной диагонали образуются несколько независимых блоков (по количеству используемых процессоров), а сепараторы, разделяющие блоки, образуют так называемое "окаймление". Внутри независимых блоков треугольное разложение можно выполнять независимо, т. е. полностью параллельно. Однако, при обработке окаймления, которое может оказаться достаточно большого размера (особенно в трехмерном случае и случае нескольких неизвестных функций на узел), возникнут значительные трудности как при выполнении дальнейших операций исключения, так и при синхронизации вычислений. Возможно также рекурсивное применение описанной методики к замыкающему блоку (количество уровней рекурсии при этом иногда достигает 10 и более). Это, в конечном итоге, отрицательно сказывается на параллельной эффективности ввиду большого количества синхронизаций, а также из-за трудностей с балансировкой вычислений.
Замечание 2.6.1 Приведение к блочно-диагональному окаймленному виду для 1С2-разложения оказывается нецелесообразным также ввиду необходимости поддерживать достаточно малую глобальную ширину ленты (см. 2.5), что невозможно из-за наличия окаймления.
Замечание 2.6.2 Применение специальных априорных перестановок хорошо согласуется с неполным разложением (т. е. разложением в фиксированную структуру), но противоречит проведению приближенного разложения (т.е. разложения по порогу), где структура заполнения определяется по ходу самого процесса исключения.
Исходя из сделанных замечаний, в дальнейшем рассматриваются пре- добусловливатели, имеющие заранее фиксированную глобальную структуру разреженности, определяющую межпроцессорный обмен данными, которая удобна для построения именно параллельных предобусловливаний, использующих приближенное разложение, примененное не ко всей матрице, а к ее некоторым подматрицам достаточно большого размера, каждая из которых может обрабатываться на отдельном процессоре.
Таким образом, как вычисление, так и применение неполного разложения Холецкого для всей матрицы А не может быть эффективно реализовано на параллельных архитектурах с распределенной памятью, которые имеют значительные накладные расходы па организацию пересылок данных. При этом параллельная реализация алгоритмов для неполных треугольных разложений потребует достаточно большого количества инициализаций обменов, что также приведет к потере параллельной эффективности за счет несбалансированности вычислений на различных процессорах.
Тем не менее в дальнейшем будет рассмотрен специальный способ построения параллельных предобусловливаний на основе неполного разложения Холецкого 2-го порядка для некоторых наборов подматриц исходной матрицы А. Глава 3. Параллелизуемое аддитивное предобусловливание
В этой главе содержится описание аддитивного приближенного разложения разреженной с.п.о. матрицы, которое пригодно для построения надежных, эффективных и легко параллелизуемых предобусловливаний для МСГ. Для решения подзадач, возникающих при использовании этого разложения, существенно используется алгоритм 1С2-разложения, описанный в предыдущей главе.
В начале главы приводится обзор различных схем построения параллельных предобусловливаний. Перечислены их основные свойства и особенности их реализации. Рассматриваются некоторые варианты аддитивных предобусловливаний типа декомпозиции области.
Теоретический анализ стратегий постфильтрации построенного предобусловливателя
Увеличение мощности вычислительной техники происходит одновременно в двух принципиально различных направлениях: увеличение мощности процессора и увеличение количества процессоров.
С первым наиболее тесно связаны "сериальные" вычисления и развития однопроцессорных ЭВМ, а второе направление включает в себя, в частности, развитие самой передовой и самой мощной современной параллельной вычислительной техники [105].
Известно, что последние 10-15 лет каждый год производительность процессоров увеличивалась в среднем в 1,4 раза, т. е. за 2 года происходило удвоение вычислительной мощности. Однако к настоящему времени этот процесс замедлился, потому что создатели чипов уже вплотную подошли к размерам, когда начинает играть роль межатомные взаимодействия. Таким образом, дальнейшее увеличение мощности процессоров будет сопряжено со значительными трудностями.
С другой стороны, увеличение количества процессоров, ранее рассматриваемое как наиболее "дешевый" вариант получения большей производительности, становится все более популярным решением не только в оборонных отраслях промышленности, но и в среде научных исследований. Известны трудности, связанные с распараллеливанием старых последовательных программ, которое, конечно, не сводится просто к переписыванию старых программ на новом параллельном языке, а требует использования принципиально нового подхода к программированию, основанного на межпроцессорном распределении данных задачи, а также разделении команд обработки данных. В настоящее время все больше появляется информации об успехах параллельных вычислений, развиваются специальные методы решения задач на параллельных ЭВМ, развивается и методика параллельного программирования (см. [99]).
Многопроцессорные вычислительные системы часто подразделяют на два класса в зависимости от доступа процессоров к оперативной памяти: системы с общей памятью - когда процессоры могут считывать и записывать данные из одной и той же общей оперативной памяти; системы с распределенной памятью - когда каждый процессор обладает своей оперативной памятью и не может напрямую обратиться к области памяти другого процессора. Системы с общей памятью обычно более дороги с точки зрения аппаратной реализации и наиболее дешевы с точки зрения разработки программного обеспечения. И наоборот, распределенные процессоры требуют очень малых аппаратных затрат, однако требуют значительных затрат как на разработку специальных параллельных методов решения, так и на само параллельное программирование, реализующее эти идеи и новые параллельные методы. Автору довелось работать на самых различных типах однопроцессорных и многопроцессорных компьютеров. Это и отечественные БЭСМ-6 (см. [1, 2]), и компьютеры серии ЕС (см. [3, 5]), и персональные компьютеры (см. [33, 35]), и зарубежные суперкомпьтеры Convex С1 (см. [6]), Cray ХМР, Cray YMP, Cray С90 (см. [11, 13]), Cray T3D (см. [12, 14]), многопроцессорные компьютеры фирмы IBM (см. [18]), многопроцессорный компьютер SUN Enterprise 3000 (см. [16,17,19-29,31,32]), сеть рабочих станций (см. [15, 16, 27, 30, 34]), а также современный высокопроизводительный вычислительный комплекс MVS6000IM ([36, 37, 38]). Интересно заметить, что 8-процессорный SUN Enterprise 3000 является системой с общей памятью, однако с помощью MPI использовался как система процессоров с распределенной памятью. Это хотя и являлось более сложным с точки зрения программирования, позволило избежать конфликтов по обращению к памяти, и в итоге получить большую эффективность, чем обычно бывает у программных реализаций, использующих общую память. Развитие вычислительной техники приводило к появлению некоторых архитектур ЭВМ, которые в настоящее время уже не используется. Перечислим их, следуя 2.5.3 работы [39]: 1) векторные процессоры, способные выполнять операции над векторами как базовые операции (см. [11, 13], для эффективного использования которых автором использовался специальный язык инструкций компилятора внутри языка высокого уровня Fortran для эффективного использования возможностей векторной обработки данных); 2) матричные процессоры, способные выполнять операции над матрицами как базовые операции, представляющие собой группу процессоров, разделяющих общую память и выполняющих один поток инструкций (см. [4], при использовании языка самого нижнего уровня APAL (Array Processor Assembler Language) автором был выписан асимптотически неулучшаемый алгоритм умножения структурированной матрицы на вектор); 3) транспьютеры, представляющие собой многопроцессорные архитектуры, состоящие из процессоров с независимой памятью, и связанных с 4-я ближайшими соседями высокоскоростными соединениями (см. [7, 8, 9,10], из языка высокого уровня Fortran использовалась специальная библиотека, реализующая межпроцессорные обмены; следует заметить, что созданный комплекс программ CRAG использовался для реальных промышленных задач расчета течения воздуха в новом поколении отечественных чистых производственных помещениях). На всех упомянутых 3-х типах архитектур ЭВМ, при организации обменов данными между процессорами, для каждой архитектуры приходилось использовать свой язык программирования, однако в 1990-х годах появился интерфейс MPI (Message Passing Interface) [95], ставший фактически стандартом для программирования систем с распределенной пямятью. Сейчас наиболее популярна свободно распространяемая реализация MPI (называемая MPICH, [96]), разработанная Argonne National Lab. и Missis- sipi State University. Сразу после появления интерфейса обменов MPI, он стал использоваться автором, что сразу решило проблему переносимости программного обеспечения на новые архитектуры параллельных ЭВМ.
