Стронгин Р.Г. Высокопроизводительные паралленльные вычисления на кластерных системах. 2003

ПРОСТРАНСТВЕННОЕ И ПОТОКОВОЕ РАСПАРАЛЛЕЛИВАНИЕ В ТЕХНОЛОГИЯХ ОБРАБОТКИ ИЗОБРАЖЕНИЙ СКОЛЬЗЯЩИМ ОКНОМ

С.Б. Попов, С.А. Скуратов

Институт систем обработки изображений РАН, г.Самара Самарский государственный аэрокосмический университет

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

Несмотря на это, большинство алгоритмов и методов обработки изображений носят последовательный характер [1]. Это проявляется, с одной стороны, в структуре вычислений «внутри» алгоритма – очень популярно использование построчной, последовательной развертки отсчетов изображений и преобразований, имеющих локальный характер (поэлементных или на основе скользящего окна). С другой стороны, значительное число методов сложной обработки изображений могут быть реализованы как последовательное применение некоторых законченных типовых операций над изображениями [2]. Причем очень часто в качестве таких типовых операций выступают методы, использующие последовательную обработку отсчетов изображений «скользящим окном»:

g(m, n) = Φ[{f (m + k, n + l)}, (k,l) D],

где Ф – оператор преобразования отсчетов исходного изображения {f}; D – «окно» обработки, определенное относительно начала координат. Наиболее популярным видом окна обработки является квадратная окрестность, симметрично расположенная относительно текущего отсчета.

Рассмотрим некоторую типовую технологию обработки изображения, которая описывается следующим образом:

fi (m, n)= ∑K ∑L ai (k, l) fi−1 (m + k, n +l),

k =−K l=−L

m = 0, M −1, n = 0, N −1, i =1, I

141

т.е. к исходному изображению f0 последовательно применяется I операций обработки. При K = L = 1 это соответствует локальной обработке скользящим окном 3×3, при K = L = 2 – окном 5×5 и т.д.

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

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

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

Время рассылки фрагментов изображения определяется следующим образом:

где P – число параллельно исполняемых задач, tc(N) – время пересылки строки изображения длиной N точек. Время выполнения одного шага

обработки составляет Tpi = MP t p (N ), где tp (N) – время обработки

одной строки изображения. Время обмена перекрывающимися строками после выполнения одного шага обработки – Tci = 2Ktc(N). Время формирования результирующего изображения из обработанных

обмен строками после последнего шага не производится, или окончательно

142

сложностью алгоритма обработки, чем проще алгоритм, тем больше это отношение, чем сложнее алгоритм, тем меньше это отношение.

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

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

Время работы одной задачи складывается из времени обработки M

строк изображения и пересылки их другой задаче Tp = M t p (N )+ M tc (N ). Начало обработки i-ой задачи задерживается на Tidlei = (i −1)(K +1)(t p (N )+ tc (N )) в случае I ≤ P, т.е. число шагов

обработки не превышает число процессоров. Если число шагов

143

обработки превышает число процессоров, то задержка i-ой задачи составит

где [x] – обозначает целую часть числа х.

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

+I −1 +1 M (t p (N )+tc (N ))P

Относительная эффективность потокового (конвейерного)

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

144

Рис. 1. Зависимость относительной эффективности от числа шагов обработки при P = 32, M = 16384, tc (N) / tp (N) =1.

Рис. 2. Зависимость относительной эффективности от вычислительной сложности алгоритма обработки – tc (N) / tp (N) при P = 16, I = 16,

M = 16384.

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

145

традиционному распараллеливанию с использованием декомпозиции по данным.

Работа выполнена при поддержке Министерства образования РФ, Администрации Самарской области и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02) в рамках российско-американской программы «Фундаментальные исследования и высшее образование» (BRHE), а также при частичной поддержке РФФИ (грант № 01-01-00097).

Литература

1.Методы компьютерной обработки изображений / по ред. Сойфера В.А., М.: Физматлит, 2001, 780 с.

2.Попов С.Б., Сойфер В.А., Тараканов А.А., Фурсов В.А. Кластерная технология формирования и параллельной фильтрации больших изображений. // Компьютерная оптика, вып.23, Самара: ИСОИ РАН, 2002, с.75-78.

ПАРАЛЛЕЛЬНЫЕ СТРУКТУРЫ ПОТОКОВЫХ И ИТЕРАЦИОННЫХ АЛГОРИТМОВ РАСПРЕДЕЛЕНИЯ РЕСУРСА

В ИЕРАРХИЧЕСКИХ СИСТЕМАХ

М.Х. Прилуцкий, Л.Г. Афраймович

Нижегородский государственный университет им. Н.И.Лобачевского

Общая математическая модель

Распределение ресурса осуществляется в многоуровневой иерархической системе, которая моделируется взвешенным ориентированным графом G=(V,A), A V2, множество V вершин которого соответствует узлам системы, а множество A дуг – определяет связи между узлами. Пусть (Vs, Vc, Vu) – разбиение множества V (соответственно, источники, коммуникационные узлы и потребители ресурса). Предполагается, что на элементах системы (на узлах и дугах) заданы сегментные ограничения, определяющие объемы ресурса, которые могут циркулировать в системе. Требуется определить такие допустимые объемы ресурса, которые соответствуют эффективной схеме функционирования системы.

146

Обозначим через Qν={i|(ν,i) A} – множество узлов системы, непосредственно следующих после узла ν, Rν={i|(i,ν) A} – множество узлов системы, непосредственно предшествующих узлу ν, ν V. Тогда

Qj≠, Rj= для j Vs; Qj≠, Rj≠ для j Vc, Qj= , Rj≠ для j Vu.

количество ресурса, которое будет передано по дуге (i,j), (i,j) A. Ограничения математической модели включают в себя:

(коммуникационные узлы полностью передают весь поступивший к ним ресурс);

(источники ресурса способны производить, а коммуникационные узлы передавать, ограниченные объемы ресурса);

Bi ≤ ∑x ji ≤ Ci , i Vu, (3)

j Ri

(связи между узлами способны пропускать лишь ограниченные количества ресурса). Здесь [Bi,Ci] – сегмент, соответствующий

ресурсным ограничениям элемента i, 0≤Bi≤Ci<∞, i V; [dij,eij] – сегмент, соответствующий ресурсным ограничениям связи (i,j), 0≤dij≤eij<∞,

(i,j) A.

Вдальнейшем, для удобства изложения материала, ограничения

(1)будем рассматривать в эквивалентном виде

Исследование общей математической модели

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

147

многоуровневых иерархических систем в виде сетевых транспортных потоковых моделей с ограниченными пропускными способностями дуг. Использование для решения потоковых задач известных методов (например, модифицированный метод расстановки пометок для задачи о максимальном потоке [1], который требует O(n3) вычислительных операций) дало возможность построить эффективную процедуру проверки на совместность системы неравенств (2)–(6).

Постановки оптимизационных задач распределения ресурса

Среди множества узлов V выделим подмножество контролируемых K, которые определяют эффективность функционирования системы. Каждый из контролируемых узлов ν задает на соответствующем ему сегменте [Bv, Cv] бинарное отношение, отражающее его предпочтение относительно соответствующего ему объёма ресурса, ν K. Зададим бинарные отношения в виде функций

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

χν (xν )→ extr, ν K.

Поставленная задача является задачей многокритериальной оптимизации, поэтому для ее решения необходимо выбрать схему компромисса. В работе [2] рассмотрена лексикографическая схема компромисса, в данной работе, предполагая, что распределение ресурсов в системе удовлетворяет условиям аддитивности и пропорциональности, будем рассматривать (как и в [3], но для общей структуры иерархической системы) линейные схемы компромисса.

Обозначим через dν, dν ≥ 0, – экономический показатель, соответствующий контролируемому узлу ν, ν K. Тогда в качестве функций предпочтения выберем χν (xν) = dν xν, ν K.

148

Поставленные задачи являются задачами линейного программирования и для их решения могут быть использованы известные методы (например, симплекс-метод), однако специфика задач дала возможность применить для их решения более эффективные алгоритмы. Дугам канонической транспортной сети, моделирующей систему ограничений (2)–(6), кроме пропускных способностей, поставим в соответствие стоимости, определяемые экономическими показателями. Тогда решение каждой из поставленных задач заключается в поиске потока минимальной стоимости равного по величине максимальному потоку канонической транспортной сети. Для решения этих задач предлагается использовать прямой или двойственный алгоритмы поиска потока минимальной стоимости заданной величины [1], которые требуют O(n4) вычислительных операций. В случае большеразмерных систем решение поставленных задач требует значительных временных затрат. Для их решения здесь предлагается использовать модификацию метода ортогональных проекций Агмона-Моцкина [4], применительно к системе линейных алгебраических неравенств транспортного типа [5], позволяющий за счет «огрубления» результатов уменьшать время решения задачи. Для этого процедуру решения оптимизационной

149

задачи сведем к последовательной проверке на совместность системы линейных алгебраических неравенств, включающей неравенства транспортного типа, соответствующие ограничениям (2)–(6) и дополнительные линейные неравенства общего вида:

здесь [Ds, Gs] – сегмент возможных допустимых значений критерия решаемой задачи, s – номер шага алгоритма. Задав количество шагов алгоритма и изменяя границы сегмента возможных значений критерия, можно с заданной точностью найти решение поставленной задачи.

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

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

Пусть h – количество параллельно работающих процессоров. При поиске максимального потока в сети, которая моделирует систему неравенств (2)–(6), предлагается в качестве начального потока использовать некоторый тупиковый поток. Для нахождения этого потока возможен одновременный поиск h различных прямых путей, увеличивающих поток. Тогда предлагается пропускать поток по одному из найденных путей, а затем, если какой-либо из найденных путей все еще увеличивает поток, то пропускать поток и через него, так просматривая все найденные пути. При поиске максимального потока методом расстановки пометок возможен одновременный поиск h различных путей, увеличивающих поток (обрабатывая их также как и прямые пути увеличивающие поток). При поиске максимального потока модифицированным методом расстановки пометок возможна параллельная обработка h точек одного слоя вспомогательной слоистой сети с целью ускорения операций «проталкивания» и «протягивания» потока (вспомогательных операций метода), а также ускорения процесса построения очередного слоя слоистой сети.

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

150