Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 19
Текст из файла (страница 19)
Он относится к семейству методов вариационно-итерационного типа и применим для решения знаконеопределенных СЛАУ снесимметричной в общем случае матрицей, для которой неизвестныспектральные свойства.Практически все современные алгоритмы решения задач вида Ax == b относятся к методам подпространств Крылова, основанным на минимизации следующего функционала F(x) = 〈Ax, x〉 – 2〈b, x〉.
Решениесвязано с построением системы сопряженных векторов и каждое следующее приближение ищется в направлении нового полученного вектора из условия минимума функционала в этом направлении.Bi-CGStab алгоритм с предобуславливающей матрицей:x0 – начальное приближение;r0 = b – Ax0;r0 – произвольный вектор, для которого (r0, r0 ≠ 0), например, r0 =r0;ρ0 = α = ω0 = 1; v0 = p0 = 0;for i = 1, 2, 3, …,ρi = (r0, ri−1);βi = (ρi/ρi−1)(α/ωi−1);pi = ri−1 + β(pi−1 – ωi−1 vi−1);находим y из Ky = pi; (K – предобуславливающая матрица,K ≈ A)vi = Ay;α = ρi /(r0, vi);s = ri–1 – avi;находим z из Kz = s;t = Az;ωi = (t, s)/(t, t);xi = xi–1 + αpi + ωis;если xi достаточно точное, то остановка;ri = s – ωit;end;Как указывается в [3] метод Bi-CGStab можно считать прямым методом, поскольку при точной арифметике он сойдется к точному решению за конечное число итераций.
Это следует из свойства сопряженности векторов построенной системы.91ПредобуславливательДля ускорения процесса сходимости и уменьшения числа итерацийв данной работе используется процедура предобуславливания по методу неполной факторизации Булеева, формулы которой получаются изформул явного метода Булеева исключением итерационных членов[1, 2].
Принцип конструирования явного метода Булеева можно считать формальным обобщением знаменитого безитерационного методапрогонки для решения одномерных краевых задач, основанного на разложении трехдиагональной матрицы в произведение нижней и верхнейтреугольных матриц.Существенно новым моментом для итерационных методов явилосьвведение приема, названного Н.И. Булеевым принципом компенсации.Он заключается в добавлении к сеточным уравнениям таких членов,которые приводят к взаимному исключению ошибок итерационныхприближений, в случае, если решение является гладкой функцией.Алгоритм предобуславливания (решение систем вида Ky = pi илиKz = s, K ≈ A) состоит из двух этапов: прямого и обратного хода.
Напервом шаге вычисляются прогоночные коэффициенты, формулы которых имеют рекуррентный вид (где Θ – параметр компенсации 0 ≤≤ Θ ≤ 1):Pij =aeijg ij, Qij =anijg ij, Tij = (bij + awijTi −1 j + asij Tij −1 ); i =1, 2, Nx −1;g ij = apij − awij ( Pi −1 j + ΘQi −1 j ) − asij (Qij −1 + ΘPij −1 ); j =1, 2, Ny −1;(3)А затем решение находится по формуле:yij = Pij yi +1 j + Qij yij +1 + Tij ; i = Nx − 1, ..., 0; j = Ny − 1, ..., 0;(4)Отметим, что использующееся в настоящее время предобуславливание по методу Холесского , LU-факторизации для задач вида (1) менее эффективно, чем предобуславливание по Булееву [2].Параллельная реализацияРаспараллеливание метода Bi-CGStab для случая решения одногодифференциального уравнения осуществляется следующим образом.Используется одномерная декомпозиция по столбцам, то есть каждомупроцессору выделяется определенное количество столбцов, для которых он будет производить вычисления.
При аппроксимации диффе92Рис. 2ренциальной задачи используется шаблон «крест». Поэтому для вычисления очередного приближения в приграничных узлах необходимопересылать значения с соседнего процессора. Алгоритм метода состоитиз операций умножения матрицы на вектор, перемножения векторов ивычисления скалярных произведений, которые просто распараллеливаются. Структура матрицы без труда позволяет организовать вычисления так, что обмены требуются лишь для пересылки граничных значений и сбора-рассылки частных сумм скалярного произведения.При предобуславливании системы линейных уравнений допустимоприменять асинхронный вариант метода Булеева, когда при вычислении значений прогоночных коэффициентов в (3) и решения в (4) в каждой процессорной подобласти на границе используются значениерешения с предыдущей итерации.Для случая решения системы сеточных уравнений с матрицей,представленной на рис.
1, ситуация меняется и неудачное распределение данных по процессорам может привести к значительному возрастанию пересылок, что в свою очередь свед ет на нет ускорение параллельной программы.На рис. 2 представлен оптимальный вариант распределений данных по процессорам, позволяющий избежать использования дополнительных пересылок. При другом способе декомпозиции потребуетсябольше времени на межпроцессорную пересылку данных, необходимых для проведения расчетов, вследствие размещения на одном процессоре только значений {uij} или только {vij}.Рис. 2Тестовая задачаТестовой задачей служила система двух эллиптических уравненийс граничными условиями первого рода с известным решением:93⎧ ∂ 2u ∂ 2u ∂ u+ v = 1; u G = 2;+⎪ 2 +⎪ ∂x∂ y2 ∂x⎨ 22⎪ ∂ v + ∂ v + ∂ v + u = 2; v = 1;G⎪⎩ ∂ x 2 ∂ y 2 ∂ x(5)Заметим, что в (5) после несложного преобразования можно перейти к независимым уравнениям:⎧ ∂ 2 (u + v) ∂ 2 (u + v) ∂ (u + v)+++ (u + v) = 3; (u + v) G = 3;⎪∂x⎪ ∂ x2∂ y2⎨ 22⎪ ∂ (u − v) + ∂ (u − v) + ∂ (u − v) + (u − v) = −1; (u − v) = −1;G⎪⎩ ∂ x 2∂x∂ y2(6)В качестве начального использовалось нулевое приближение.Приближенное решение соответствующих сеточных систем считалосьдостигнутым, если норма невязки становилась меньше ε = 10−5.ВыводыВ таблице приведены результаты работы (число итераций и время)соответствующих последовательных алгоритмов для решения систем(5) и (6).
В первой строке представлено число итераций необходимыхдля получения решения с заданной точностью с использованием процедуры предобуславливания во второй без е е применения.Из таблицы следует, что предлагаемый метод совместного решения сеточных уравнений обладает большей эффективностью по сравнению с последовательным решением каждой системы сеточных уравнений на одной глобальной итерации метода.СеткаBi-CGStab-P для (5)Bi-CGStab-P для (6)Bi-CGStab-P для (5)с последовательнымрешением уравнений94100*10051 (1,406 c)409 (7,812 c)52 (1,370 c)410 (7,281 c)200*200114 (16.828c)824 (73.671c)114 (16.234c)863 (71.781c)72 (3,710 с)127 (31.109с)рис. 3логорифмневязки1050-50202 Проц.4060номер итерации4 Проц.8 Проц.Рис.
3У ско р ен и ерис. 443,532,521,510,500246810Число процессоровРис. 4Приведенные на рис. 3 графики сходимости итерационного процесса при параллельном решении системы (5) демонстрируют подобиезависимости логарифма невязки от номера итерации при различномчисле процессоров.
Некоторое увеличение числа глобальных итерацийметода при большем числе процессоров обусловлено асинхроннойприродой использования предобуславливателя при параллельных вычислениях. Однако следует отметить, что это компенсируется снижением временных затрат на решение вследствие имеющего место ускорения вычислительного процесса (рис. 4).Литература1. Ильин В.П. Методы неполной факторизации для решения алгебраических систем. – М.: Наука, 1995. – 287 с.952. Старченко А.В. // Вестник Томского государственного университета. 2003. №10.
С. 70–80.3. Van der Vorst H.A. Bi-CGSTAB: a fast and smothly converging variantof Bi-CG for the solution of nonsymmetric linear systems: Preprint 633. –Univ.Utrecht. – 1990.ТЕХНОЛОГИЯ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИЦВЕТНЫХ ИЗОБРАЖЕНИЙД.И. Зимин, В.А. ФурсовСамарский государственный гэрокосмический гниверситетПостановка задачиЗадача улучшения качества цветных изображений часто должнарешаться при отсутствии априорной информации о характеристикахискажений. Типичными источниками таких искажений являютсядефокусировка объектива, скоростной сдвиг (смаз), и др. Онихарактерны, например, в случае регистрации неожиданновозникающих сюжетов и явлений, когда время на настройкурегистрирующей аппаратуры крайне ограничено.
В системахэкологического мониторинга Земли характеристики искажающейсреды также обычно изменчивы или неизвестны.Для решения указанной задачи применяют идею «слепой» обработки сигналов [6, 2], прошедших через канал с неизвестными характеристиками на фоне шумов. В данном случае должна решаться задачаслепой коррекции искажений (blind image deconvolution) при отсутствии априорной информации об импульсной реакции искажающей системы, т.е. формулируется задача восстановления двумерного, пространственно–ограниченного, неотрицательного сигнала искаженноголинейным оператором размерность и параметры которого неизвестны.В работе [2] эта задача рассматривалась применительно к обработке черно-белых полутоновых изображений.
Технология построениявосстанавливающих фильтров и обработки изображений строилась ввиде следующих этапов:1) выбор на искаженном изображении фрагментов, пригодных дляслепой идентификации модели искажений в канале;2) формирование из выбранных фрагментов тестовых образцов(компьютерное ретуширование изображений на фрагментах);3) идентификация параметров искажающей системы и/или восста96навливающего фильтра по отобранным и тестовым (ретушированным)фрагментам;4) выбор класса и уточнение параметров восстанавливающегофильтра по критериям вычислительной сложности, устойчивости икачества обработки;5) декомпозиция изображения;6) обработка изображения.При обработке цветных изображений возникают дополнительныетрудности реализации указанной технологии.
Дело в том, что цветныеизображения обычно представляются в виде RGB-компонент. К сожалению, при таком представлении не удается организовать покомпонентную обработку, так чтобы при этом обеспечивалось высокое качество цветовоспроизведения.В настоящей работе рассматривается технология обработки цветных изображений, в которой для преодоления указанной трудностиосуществляется переход в цветовое пространство Lab. Рассматриваются также связанные с этим особенности организации распределеннойобработки большеформатных цветных изображений.Описание моделей и общей схемы обработки изображенийРассматривается поэтапная технология, в которой предусматривается переход из пространства RGB в Lab и обратно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
