УДК 621.391.2
А.В.Гордиан

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

Введение

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

а)                     архитектуры MISD (Multiple Instruction - Single Data) или конвейерные архитектуры; принципы работы программного конвейера аналогичны принципам работы программного конвейера в автомобилестроении: поток данных – «деталей» - последовательно обрабатывается отдельными элементарными блоками программы - "рабочими местами"; таким образом, в установившемся режиме время, необходимое программному конвейеру для обработки единичной структуры данных (кадра изображения), определяется не суммой времени работы всех блоков конвейера, а временем, необходимым самому громоздкому блоку, выполняющему самую ресурсоемкую задачу;

б)                    архитектуры SIMD (Single Instruction - Multiple Data), характерными реализациями которых являются матричные процессоры; в общем случае для подобных архитектур поток данных разбивается на несколько субпотоков (например, кадр изображения - на несколько вертикальных полосок), каждый из которых обрабатывается своим процессором; все процессоры выполняют одну программу над небольшими порциями данных, за счет чего происходит ускорение процесса обработки;

в)                     архитектуры MIMD (Multiple Instruction - Multiple Data), к этому классу относятся транспьютерные системы (ТС); класс MIMD является универсальным, и ВС этого класса могут выполнять операции, характерные для архитектур MISD и SIMD; это свойство - универсальность - является одним из основных факторов, благодаря которому ТС получили широкое применение.

Транспьютер (TP) представляет собой высокопроизводительный микропроцессор (МП). Определяющим отличием TP от других типов МП [3] является наличие четырех выводов - «линков", каждый из которых служит для непосредственной связи с другим ТР. Хотя TP может функционировать независимо (его производительность выше» чем, например, у альянса i80386+i80387 с той же тактовой частотой), предназначен он, в первую очередь, для работы в ансамбле себе подобных. Множество TP, объединенных посредством коммутации линков, образуют ТС различной конфигурации, производительность которых много выше, чем сумма вычислительных мощностей, составляющих ее ТР. На рис.1 Представлена одна из самых простых и универсальных архитектур ТС. Каждый узел ее сети представляет собой автономно функционирующий транспьютер с локальным ОЗУ; в ходе выполнения инструкций программы TP может непосредственно обмениваться данными с четырьмя ближайшими ТР или другими ТР. В этом случае транспьютеры, с которыми oн скоммутирован, будут выступать в качестве посредников.

Рис. 1

Семейство TP включает несколько моделей (Т414, Т800, T805 и др.); в табл. 1 приведены характеристики модели Т800

Таблица 1

Тактовая частота	20, 25
Разрадность шины данных	32
Разрядность шины адреса	32
Объём непосредственно адресуемого ОЗУ	4 Гб
ОЗУ на кристалле процессора	8 Кб
Система команд, тип	RISC
Математический процессор	Встроенный
Разрядность данных для математического процессора	64
Число линков	4
Пропускная способность линков	5..20 Мбит/с

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

Вообще говоря, реализация того или иного алгоритма обработки СП для ТС является задачей не только программирования, но и конфигурирования ТС. Здесь под конфигурированием ТС подразумевается построение неориентированного графа G(N,E), содержащего N вершин (транспьютеров), каждая из которых смежна с M вершинами ;множеству E ребер графа соответствует E связей между линками транспьютеров-вершин. Характерной особенностью последнего поколения ТС является соединение системы TP не непосредственно, а через программируемый коммутатор [4]. В этом случае разработчик ценой незначительного уменьшения скорости передачи данных по линкам, получает возможность оперативного изменения структуры ТС, в том числе динамического - в ходе выполнения программы.

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