Параллельная реализация процесса фильтрации СП

В решении задачи параллельной обработки СП возможны следующие подходы:

а)  параллельная обработка последовательным алгоритмом различных частей СП (например, слабозависимых вертикальных полосок кадра для алгоритма Вудса [7]);

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

Рассмотрим вопрос параллельной обработки различных частей СП. Примером может служить последовательность двумерных СП (кадров) размером 1024x1024 элементов. В работе [2] обсуждаются различные подходы к решению проблемы распараллеливания данных; все подходы в данном случае сводятся к двум основным: геометрическое решение (базируется на принципе SIMD), конвейерное решение (базируется на принципе M1SD).

Геометрическое решение заключается в разбиении СП на отдельные полоски, имеющие небольшой размер. Полоски обрабатываются параллельно на различных ТР. Время, необходимое для оценивания всего СП, сводится таким образом ко времени оценивания одной полоски. Подобное решение было предложено Вудсом [7] для своего весьма громоздкого алгоритма. На рис.2 представлена схема разбиения СП на отдельные вертикальные полоски. Такой подход построен на предположении о независимости вертикальных полосок друг от Друга. Поскольку для реальных изображений это не так. то геометрическое решение всегда будет иметь потери в качестве по отношению к оптимальной процедуре. Строка полоски В (рис.2), строго говоря, не может обрабатываться одновременно с той же строкой полоски А, поскольку зависит от результатов ее оценивания. Могут быть предложены различные выходы из создавшегося положения; все они основаны на применении алгоритмов «склеивания» вертикальных полосок. Из рис.2, например, видно, что полоски могут быть перекрывающимися; в этом случае прогноз граничных элементов делается по двум независимым опенкам, сделанным для разных полосок. Применение подобных алгоритмов "склеивания" повышает время, необходимое для обработки поля, качество же решения не всегда будет достаточным.

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

Рассматривая подобный подход, можно предложить следующую модель обработки трехмерных (в общем случае n-мерных) СП. Каждое двумерное СП последовательности разбивается на несколько горизонтальных полосой (рис.3), каждую из которых обозначим номером от (1) до (n). Максимально возможное количество полосок равно числу строк СП; в этом случае каждой полоске соответствует одна полная строка СП. Каждая из этих полосок, будучи зависимой, не может обрабатываться параллельно с другими и оценивается, таким образом, после оценки предыдущей полоски на основе результатов оценки последней строки и наблюдений. Обработка каждой полоски ведется с помощью алгоритма (5) с заранее рассчитанной матрицей .

Рис. 2                                                 Рис. 3

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

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

Рис. 4

Рассмотрим вариант разбиения каждого текущего кадра размером 1024x1024 на 16 горизонтальных полосок. В этом случае каждая полоска представляет собой СП размерностью 64x1024 элементов. Обработка каждой из полосок ведется алгоритмом (5), реализованным в виде программного процесса на отдельном TP, располагающим локальной памятью необходимого объема. Предположим, что кадр разбивается автоматически программируемым устройством ввода на 16 горизонтальных полосок, каждая из которых одновременно поступает на вход одного из 16-ти транспьютерных блоков (ТРБ). Каждый ТРБ предназначен для оценивания соответствующей полоски кадра на основе результатов наблюдения и результатов оценивания смежным ТРБ последней строки предыдущей полоски. Для этого результаты фильтрации последней строки каждый ТРБ передает своему "соседу".

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

ТРБ состоит из собственно TP и системы накопительных буферов (НБ). В конкретной системе обработки СП НБ могут быть реализованы как программно, в виде массивов в локальной памяти TP, так и аппаратно. НБ необходим для хранения полоски кадра до того момента, когда будут оценены все предыдущие полоски, ТРБ получит результаты их фильтрации .и сможет приступить к процессу оценивания. В установившемся режиме на вход ТС подобной конфигурации кадры поступают с периодом, необходимым для обработки одной полоски. Нетрудно подсчитать число НБ, необходимых каждому ТРБ для хранения поступающей информации: для первого - 0, для второго - 1, для третьего 2, для 16-го - 15, для n-го - (n-1); минимальная емкость ЗУ для организации НБ составляет 0 ячеек (для 1 -го ТРБ), а максимальная -  -  ячеек (для n-го ТРБ). Подобная система действует по принципу очереди:  «первый пришел - первый вышел».

Было оценено время, необходимое ТС на базе TP типа Т800 с тактовой частотой 20МГц, для обработки кадра размерностью 1024x1024 в установившемся режиме (с учетом ориентировочного времени пересылки данных между TP я ТР,УВ,УВВ). Результаты сведены в табл.2. Как следует из приведенных данных, с уменьшением размерности полоски (с увеличением числа ТРБ в ТС)- время обработки кадра уменьшается в зависимости, близкой к линейной. Отклонение обусловлено возрастанием времени пересылки данных между ТРБ по отношению ко времени обработки полоски. При этом, относительное время пересылки данных не превышает 2,2% от общего времени обработки» и, чаще всего, зависимость приближенно можно считать линейной. Также линейно, с уменьшением размера полоски, уменьшается и объем дополнительного ОЗУ для каждого ТРБ, необходимого для хранения матрицы .

Таблица 2

Алгоритм	Размер кадра, N	Число ТРБ	Время оценки, с	Доп. ЗУ, яч./ТРБ
Тензорный фильтр Калмана с готовой матрицей	1024	1	9139,4
‘’	1024	16	580,7
‘’	1024	64	145,4
‘’	1024	1024	9,15