Моделирование конвейерно-параллельного вычислителя с проблемной ориентацией

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 681. 325. 5:528. 851
МОДЕЛИРОВАНИЕ КОНВЕЙЕРНО-ПАРАЛЛЕЛЬНОГО ВЫЧИСЛИТЕЛЯ С ПРОБЛЕМНОЙ ОРИЕНТАЦИЕЙ
Н.В. ЩЕРБИНИНА
Белгородский
государственный
национальный
исследовательский
университет
e-mail:
shcherbinina@bsu. edu. ru
Аннотация: представлено обобщение метода распараллеливания изменением внутренних связей конвейерно-параллельной структуры, ориентированного на поточную обработку цифровых космических изображений вычислителя с разработкой стратегий снижения сложности выполняемых функций, алгоритмов и операций, представляющих компьютерные реализации линейных ограниченных непрерывных функционалов и операторов в векторных линейных пространствах.
Ключевые слова: изображение, конвейерный, систолический,
распараллеливание, теорема Рисса-Фреше, линейный оператор, интегральное представление.
Весомую часть в списке «бортовых» и «наземных» процедур поточной обработки данных при дистанционном космическом зондировании составляют процедуры радиационной, геометрической, радиометрической, приборной, коррекции значений пикселов цифровых изображений на угол места солнца, а также нормализации, фильтрации, спектрально-корреляционной обработки, линейных преобразований векторов (и самих изображений). Решаются эти задачи в потоковом режиме, потоки организуются на считываемых строках формируемого цифрового космического изображения и на векторах априорной или измерительной информации (как правило, при этом двумерные преобразования организуются в виде последовательности одномерных «по строкам» и на полученном результате аналогично «по столбцам»). Обширные исследования и практика разработок эффективных, ориентированных на работу с космическими изображениями, вычислительных средств резюмируют прерогативу распределенных вычислений на систолических, параллельно-конвейерных (с реконфигурацией архитектуры) процессорах [1].
Наиболее «популярными» операциями по частоте реализации являются коррекции пикселов в потоках на мультипликативные и аддитивные составляющие, свертки векторов (с участием строк и столбцов изображений), скалярные и покомпонентные перемножения (особенно для реализации преобразований Фурье по системам функций и фильтраций в пространственно-частотных координатах). Однако сокращение времени работы собственно конвейера операций или/и аппаратуры (как правило, распараллеливанием) при минимизации аппаратных затрат все еще остается исследуемой проблемой.
Обычно вычислительные процессы и средства проектируются на базе модулей или арифметико-логических устройств, ориентированных на представление алгоритмов в «традиционнных» алгебрах чисел и логики, что является достаточно надежным инструментом решения любой вычислительной задачи при наличии необходимого метода решения задачи и программного обеспечения [2]. При этом в качестве средства повышения производительности выступают:
1) использование элементной базы с повышенным быстродействием (в том числе с «внутренним» параллелизмом в исполняемых операциях) —
2) снижение значений функций сложности выполняемых в вычислительной среде алгоритмов, проебразований, операций в стратегиях, приведенных в [3]-
3) распараллелливание и/или конвейеризация (в том числе с реконфигурацией архитектуры) процессов с применением многопроцессорной или однородной вычислительной среды.
Применение таких универсализированных по функциональности подходов и средств к задачам обработки данных, скажем, приведенным выше, в принципе, оправдано, хотя и приходится решать проблемы параллельного программирования, диспетчеризации, управления в согласовании с задачами, решаемыми в потоках данных.
В соответствии с выше описанной проблемной ориентацией проектируемого вычислителя целесообразно рассмотреть параллельно-конвейерную структуру с учетом следующей особенности:
вычислитель ориентирован на поточное вычисление фнкционалов на основе теоремы Рисса-Фреше [4], вычисление элементов векторов дискретного интегрального представления линейных ограниченных операторов [5] (как следствие из теоремы Рисса-Фреше в том числе), выполнение покомпонентных перемножений массивов.
Целесообразно провести анализ конвейерной схемы (операции свертки -умножения) [6], представленной на рисунке 1 (положим сначала, что это схема умножения чисел, представленных в некоторой позиционной системе счисления с основаниеем С, где А1 и В1 — разряды входных операндов, Д1 — разряды результата операции).
Яз Ял Я1
& lt-Вз: В2 (c)J
Дуй, я& amp-± л,©,
Яз®2 Я2& amp-2 Я1& amp-2
Яз-Бз Я J (c)J Я1Л3
(c)S CDs ®-f (c)J (c)J (c)J
Рис. 1. Схема операции свертки- умножения
В ромбе частичных результатов операции произведения вида А1В1 выполняются по модулю С, а отделяемый при этом перенос (разряды более старшие, чем разрядная сетка в позиции по отношению к операндам) суммируется со старшим в строке элементом, если выполняется операция умножения операндов. Для выполнения операции свертки операндов достаточно все переносы удержать в столбце (закрыванием регистров передачи переноса и резервированием в каждой позиции столбца двойную разрядную сетку). В первом случае операнды — это числа в позиционной системе счисления, во втором случае — элементы массива (вектора), причем и в первом и во втором случае они могут иметь не только положительные знаки и даже превышать отведенную в операндах ширину разрядной сетки в позициях. Результаты в силу свойства дистрибутивности для умножения всегда будут правильными. «Непривычную» форму представления числа можно не брать в расчет. Если необходимо или желательно результат — свертку представить с индексами произведений в каждой частичной строке, изменяющимися по нарастанию «навстречу» друг другу, то достаточно один из операндов записать не слева-направо, а справа-налево. При этом эта схема является наследником при увеличении размеров решаемых задач, т.к. каждая пара вида А1В1 тоже может быть выполненной ранее сверткой, а не умножением — это демонстрирует суперпозицию сверток, причем самая первичная свертка может быть принята за базовую операцию и реализована в виде таблицы. Здесь разряд Д6 результата появляется при настройке схемы на умножение. Такой подход для умножения — выполнение сначала свертки (здесь на рисунке каждая строка представлена в системе счисления с основанием С2, иначе бы пришлось каждую строку сжать по горизонтали так, чтобы старшие компоненты произведений младших номеров столбцов пересеклись с младшими компонентами кодов старшего столбца — для выпонения умножения), а затем покомпонентное перемножение вектора — результата и нормирующего вектора, представляющего собой последовательность С в степени i, где i — отсчитываемая от нуля позиция элемента в нормирующем векторе. Выполнение покомпонентного перемножения операндов реа-
лизуется в схеме управлением регистрами так, чтобы можно было выбрать на выходе только главную диагональ ромба.
В наиболее близком по структуре конвейерно-параллельном устройстве [6] организованы три тактируемых потока данных:
— транзит множителя и множимого вдоль столбцов ромба с сответствующими коммутациями-
— передача строк частичных прозведений через строку, что реализует распараллел-ливание конвейера с минимально возможным в данном случае добавлением аппаратуры в схему — строки сумматоров, собирающих с двух ветвей конечный результат-
— тактируемый транзит переносов вдоль каждой строки, причем не только переносов арифметических, но и переносов двоичных внутри кажого частичного произведения.
Что касается перечисленных выше пунктов 1), 2) и 3), то в рамках приведенной проблемной ориентации решены задачи:
• использования полностью ресурса по быстродействию операционных элементов для любой элементной базы, т.к. на операционный элемент [6], а это для частичных произведений сумматоры со стробирумыми соответствующими разрядами множителя входами, подается порция позиции операнда, соответствующая разрядности сумматора, а на соседний старший сумматор через регистр подается следующая более старшая порция разрядов к моменту формирования переноса на первом сумматоре. Абсолютно все операнды подаются в потоке с описанными задержками и такт подачи операндов становится минимально возможным для выбранной элементной базы и равным времени задержки на операционном элементе (так как, например, сумматор, отдавший в регистр формирующийся последним внутри сумматора перенос, все остальные результаты «давно» уже отдал в регитры потока и стал свободным для загрузки его порцией разрядов следующей пары операндов подаваемых на него, без ожидания формирования правильного результата по всей разрядной сетке вычислителя). В [7] показано, что по крайней мере проблемно ориентированные вычислители целесообразно проектировать, ориентируясь именно на такой способ обмена данными во всех шинах и для всех устройств вычислителя-
• на основе приведенной схемы с использованием параллельно-конвейерного тактируемого коммутатора (в отличие от жестких коммутаций разрядов множимого и множителя с операционными элементами) реализован процессор с широкой функциональностью [1].
Не решены задачи:
• обобщения условного распараллеливания проблемно-ориентированного вычислителя —
• снижения значений функции сложноси частичных умножений в строках схемы свертки-умножения.
Цель исследований: определение оптимального проекта для потокового конвейерного вычислителя свертки, умножения, покомпонентных перемножений векторов.
В развитие метода условного распараллеливания целесообразно не ограничиваться распараллеливанием на две ветви. В общем случае, формула для числа тактов в конвейере, определяющих общее запаздывание результата относительно ввода при организации Ь ветвей имеет вид:
д (Ь) = до/Ь+1о§ 2Ь, (1)
где логарифм двоичный — дополнительные такты при организации двоичного дерева операционных единиц (сумматоров) сборки результата, а Q0 — исходная сложность алгоритма, измеренная в количестве последовательных тактов конвейера.
Для дополнения к пояснению условности распараллеливания можно заметить, что каждый операнд транзитом проходит через все регистры передачи операндов, при стандартном распараллеливании поток разбивается на два, демультиплексируется и только половина операндов проходит через ветвь транзита. Наихудший вариант распараллеливания строится на аппаратном повторе ветвей конвейера.
На рис. 2 показан систолический конвейер с описываемой ориентацией.
Серия История. Политология. Экономика. Информатика. 2013. № 15 (158). Выпуск 27/1
Рис. 2. Систолическая структура с условным распараллеливанием на две ветви
Здесь А1, В1, — регистры транзита операндов, Э1 — элементарные функциональные вычислители, С — дополнительный элемент сборки результата.
Кривая вычислительной сложности количества последовательных тактов в процессоре Q (L) в зависимости от Ь имеет минимум при Ь равном ближайшему целому к L*=Q0ln2 (при этом количество условных ветвей параллелизма не превышает ближайшее значение к Ь сверху от степени двойки). Если процессор ориентирован на конвейерный алгоритм, а его элементарные машины имеют конвейерное исполнение, то при изотропности структур машин в процессоре в них также реализуется формула (1) с М ветвями. Оптимальной такую структуру следует считать при выборе ближайшего целого к М*Ь*= Q1Q0ln22, где Q1 -количество тактов конвейера в элементарной машине Э1.
В [8] показано, что при обработке изображений алгоритмы класса Фурье-преобразований, сверток, линейных фильтраций, реализуемые в алгебре с операциями «сложить» и «умножить», более эффективно осуществляются на основе операций, таких, например, как, восьми-, четырех — или двухточечное преобразование Фурье, Адамара, Уолша, представимых довольно легко таблично и организуемых однотактной выборкой значений из таблицы, размещаемой в согласованно структурируемой памяти компьютера. Однако легко заметить, что этим таблицам однозначно соответствуют таблицы восьми-, четырех — или двухточечных сверток векторов соответствующих размерностей [7]. При этом, вычислительное устройство, реализующее вычислительные процессы на основе «классической» арифметики, работает на порядки эффективнее, если в этой арифметической системе заменить двухместную операцию умножения, скажем, на перечисленные выше билинейные, то есть удовлетворяющие условиям дистрибутивности и тому подобным условиям табличные операции. В [3] показано, что возврат вычислителя в традиционную арифметическую систему не только реализуется элементарно, но и обеспечивается при этом гораздо более эффективная реализация той же операции умножения. Примером тому теорема [3] о замене классического алгоритма умножения целых чисел (алгоритма сложности п (п — разрядность операции с учетом того, что можно считать разрядности входных операндов одинаковыми, заменяя нулями отсутствующие старшие разряды у «малоразрядного» операнда)) тремя быстрыми преобразованиями Фурье (БПФ) (с вычислительной сложностью результирующей операции 3п1о2 п. Строго говоря, здесь еще присутствует аддитивная добавка в виде 3п, где 2п — количество операций при покомпонентном перемножении спектральных образов (достаточно использовать спектры первого и второго квадрантов спектральных координат) и п — вычислительные затраты на использование нормирующего вектора при приведении результата от свертки к умножению, но в данных расчета будем иметь в виду, что размерности решаемых задач не менее п =256, и тогда добавкой в 3п можно пренебречь).
При моделировании на ПК двумерной свертки двух изображений размерностью 512×512 пикселов в индексной палитре (глубина цвета 1 байт) с реализацией модели конвейерно-параллельного вычислителя с условным распараллеливанием на 4 ветви, тактовой длиной 512 табличных операций с таблицами арифметической системы, вместо операции умножения, получено сокращение времени процедуры свертки по сравнению с использованием «традиционного» ускорения процедурой 512-точечного БПФ (конвейер в графе Баттерфляй) около 29 раз.
Серия История. Политология. Экономика. Информатика. 2013. № 15 (158). Выпуск 27/1
Расчетное сокращение времени составило примерно Зх512×512×1б/(4×25бх25б)=48 раз (в числителе — типовой расчет затрат тактов на использование БПФ, в знаменателе -расчет числа выборок из памяти для восстановления суммированием со сдвигом полноразмерной свертки).
Аналогичные результаты по сокращению времени работы процедуры фильтрации полос на космическом изображении получены для варианта программы [9].
Получено соотношение для минимизации последовательных тактов конвейера систолического процессора с использованием распараллеливания без внесения в схему существенных аппаратных затрат (условного распараллеливания), в том числе и для одного этапа рекурсии распараллеливания с использованием в частичных произведениях табличных методов реализации сложных операций.
Работа выполнена в рамках дополнительного внутривузовского конкурса грантов ««Инициатива», проект № ВКГИ 034−2013.
1. Алиева М. А., Винтаев В. Н., Гадживердиев А. З., Исмаилов К. Х., Эюбов Ф. Ф. Разработка специализированных процессоров обработки данных дистанционных измерений. // Отчет о НИР № Гос. регистрации 01. 85. 47 346, НПО Космических исследований МОМ СССР, 1984. — 113 с.
2. Григорьев В. Р. Методы параллельной цифровой обработки информации в трехмерных оптических интегральных схемах // дисс. на соискание ученой степени к.т.н. по спец. 05. 13. 17, Москва, 2005. — 231 с.
3. Ахо А. Построение и анализ вычислительных алгоритмов/ А. Ахо, Д. Хопкрофт, Д. Ульман //М. :Мир, 1979, — 536 с.
4. Морен К. Методы Гильбертова пространства/К. Морен. //М. :Мир, 1965. — 570 с.
5. Коллатц Л. Функциональный анализ и вычислительная математика// Москва. Мир, 1969. — 448 с.
6. Аллахвердов Ф. М., Винтаев В. Н., Исмаилов Т. К., Исмаилов К. Х., Гадживердиев А. Э., Мамедов Ф. А., Бадалов А. Р. Конвейерное множительное устройство. НПО космических исследований// МОМ.- АС СССР № 1 043 642 БИ № 35, 23. 09. 83.
7. Винтаев В. Н. Вычислительное устройство на основе проблемно-ориентированной компьютерной арифметики. дисс. на соискание ученой степени к.т.н. по спец. 05. 13. 05, Москва, 1989.
— 183 с.
8. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. // М.: Мир, 1978. — 848 с.
9. Константинов И. С., Щербинина Н. В., Жиленев М. Ю., Винтаев В. Н., Ушакова Н. Н. Модернизация процедуры цифровой коррекции возмущений в изображениях, формируемых панхроматической оптико-электронной съемочной аппаратурой космического аппарата «Монитор» // Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика. — 2013. -№ 8(151). — Вып. 26/1. -С. 194−199.
Выводы
Список литературы
MODELING OF THE CONVEYOR — PARALLEL CALCULATOR WITH PROBLEM ORIENTATION
Belgorod National Research University
N.V. SHCHERBININA
The generalized method of parallelization by change of internal communications of the conveyor-parallel structure, focused on line processing of digital space images. Development of strategy of decrease in complexity of carried-out functions, algorithms and the operations representing computer realization of linear limited continuous functionalities and operators in vector linear spaces.
e-mail:
shcherbinina@bsu. edu. ru
Keywords: image, conveyor, systolic, parallelization, Riesz-Frechet'-s theorem, linear operator, integrated representation.

ПоказатьСвернуть
Заполнить форму текущей работой