Раздел: Документация

0 ... 48 49 50 51 52 53 54 ... 78

17.4. АРХИТЕКТУРА ПАРАЛЛЕЛЬНЫХ СБИС

Важными факторами при разработке любой СБИС являются простота и эффективность проектирования [11]. По мере увеличения плотности логических элементов на кристалле до сотен тысяч время проектирования и сложность топологии кристалла становятся доминирующими условиями, определяющими возможности создания СБИС. Ввиду этого модульное проектирование высокорегулярных структур является основным аргументом в пользу внедрения СБИС. Потенциально наиболее регулярным классом структур, спроектированных на сегодня, оказались запоминающие устройства с высокой степенью плотности размещения элементов. По этой причине возник интерес к реализации высокоскоростных комплексных операций, основанных на поиске в таблицах, размещаемых в памяти с произвольным доступом. Этот метод имеет значительные преимущества при решении задач выделения признаков и контуров, однако при прямой реализации он требует чрезвычайно большого объема памяти. Например, при 12-разрядном квантовании яркости изображения может потребоваться поиск в таблицах общим объемом около 224, или 20 Мбит. Очевидно, что это нереально для современных или перспективных кристаллов СБИС, и можно ожидать, что такой поиск потребует чрезвычайно большого времени доступа в любой из комбинированных структур.

Существует несколько подходов к снижению общего объема памяти, включая подходы, основанные на методе Офмана - Карацубы [12] и нестандартных численных представлениях. Метод Офмана - Карацубы основан на разбиении машинного слова длиной W нам секций размером W/n, в результате чего для некоторых операций общая потребность в памяти может быть сокращена в 2п раз. Интересным примером применения этого подхода, предложенным в [13], является расчет плотности контура изображения по методу Собела [14], в котором девять значений 3 X 3-матрицы яркостей точек используются для вычисления величины

где

с(17.26)

ал- яркость двумерного контура в точке Xt у. При прямом вычислении с учетом того, что яркость / каждой точки представлена W разрядами, потре-буется 2<2+2> бит для таблиц при условии обеспечения полной точности представления S. Если каждую из составляющих контура выразить в виде комбинации из двух слов длиной но Й 2, представляющих старшую и младшую части данных, т. е.

X=XL2WP+XR9(173)

то можно записать следующее выражение:

X2 =Х[ 2W + (X* + Х2)-(XL -XR)2 2W2 +X2R .(17.4)

Поскольку Xj (XL - XR) и XR имеют самое большее Щ2 ненулевых разрядов, то размер таблиц в результате уменьшается с 22W до примерно 2W. Этот метод может быть и далее применен для разбиения слова на п секций размером W/n и получения в результате общего объема памяти в 2/п X и. В настоящее время фирма Hughes Research Laboratories разрабатывает основанный на данном методе процессор выделения контура, в котором размер требуемой памяти будет сокращен с 10 X 106 до величины примерно 104 бит.

Другой подход, который мы в настоящее время исследуем с целью использования технологии новых СБИС ЗУПВ для анализа изображений, основан на арифметике в остаточных классах [15]. Этот метод требует кодирования входных данных с помощью деления их на простые числа, как показано на рис. 17.4, с последующей обработкой только остатков. В нашем случае, например, были использованы четыре простых числа 31, 29, 23 и 19, каждое длиной менее 5 разрядов, а следовательно, и остатки имели длину менее 5 разрядов. Арифметические операции в каждом из каналов выполнялись как обычно, но с той оговоркой, что любой промежуточный результат, превышающий основание, преобразовывался в остаток посредством по сл е до вате л ьно -го вычитания основания. Выходные данные параллельных каналов могут быть затем преобразованы в двоичную форму и обеспечивают точность, эквивалентную произведению оснований, т. е. 392 863, или приблизительно 18 разрядов. Значительным достоинством данного подхода является то, что все арифметические операции, включая входное кодирование в остаточных классах, внутренние вычисления и декодирование на выходе, могут осуществляться с небольшими таблицами (5 X 32) . Кроме того, такая машина может быть

Кодер по осноданию

в,

Процессор RADIUS с основанием Bj

Входные данные

Кодер по основанию

Кодер по осноданию

вн-1

Процессор RADIUS с основанием Вг

Процессор RADIUS с основанием BN-f

Декодер по остаткам

кодер ло осноданию В

Процессор RADIUS с основанием BN

Рис. 17.4. Структура процессора для анализа изображения в остаточных классах

---

Рис. 17.5. Заказная «МОП-микросхема * Рис. 17.6. Обобщенная структура дву-для процессора в остаточных классах мерной конвейерной матрицы

сделана программируемой для выполнения различных операций выделения признаков. Машина RADIUS [16], которая была построена с использованием данных методов, сейчас работает в нашей лаборатории, как правило, в реальном масштабе времени. Она состоит из некоторого числа специализированных заказных и МОП-кристаллов, которые содержат просмотровые таблицы и несколько модульных арифметических блоков, как показано на рис. 17.5. Машина в целом выполняет операции вида

У = 2/((1и),(17.5)

где 1ц - значение яркости ядра из 5 X 5 элементов, a f- - многочлены одной переменной. Эффективная производительность машины в режиме выделения признаков эквивалентна 200 X 106 он. умножения в секунду.

Еще одним подходом к проблеме параллелизма в СБИС, привлекающим все больший интерес, является использование двумерной конвейерной матрицы, изображенной на рис. 17.6. Она имеет прямоугольную структуру и состоит из некоторого числа одинаковых процессоров, связанных только с ближайшими соседями. Эта обобщенная форма архитектуры включает в себя как систолические структуры, так и волновые [17. 18]. Такая матрица с возможностями выполнения простых арифметических операций, таких как умножение и сложение в каждом из элементов, может оказаться очень эффективной для анализа изображений. Приведенная на рис. 17.6 прямоугольная структура во многих отношениях идеально подходит для анализа изображений ввиду топологического соответствия между расположением процессоров и элементов изображения в кадре. Наша цель состояла в разработке алгоритмов для таких архитектур и оптимальных элементарных процессоров на СБИС для систем АИРО.

Хорошо соответствует двумерным структурам алгоритм Фаддеевой [ 19]. Он полезен при решении систем линейных уравнений вида 312

АХ = В,(17-6>

где А - п X «-матрица; ХиВ - векторы длиной п. Эта операция является ядром многих алгоритмов АИРО, включая алгоритмы большинства предварительных операций обработки и коррекции изображений. Если, например, данные загружены в матрицу в форме

(17.7)

	«12	«1п
«21	«2 2	«2и	b2
«,,1	«„2 *		К
-1	0 •	• 0	0

А	В
Л	0

(17.8)

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

С А1 В + D, ВС + I),

которые при загрузке преобразуются к виду

А	В
-С	1)
А	1
-1	0
А	в
-1	0
I	в
-С	D

(17.9)

(17.10)

(17.11) (17.12)

(17.13)

(17.14)

(17.15)

(17.16)

соответственно

---

Если эти операции реализуются прямо, процессоры требуют некоторого числа сдвигов глобальных данных ввиду того, что для умножения на каждой позиции требуются элементы крайних столбцов и строк массива. Это можно расценивать как нарушение одного из основных принципов использования СБИС: желательность только локальных связей и устранения таким образом необходимости в длинных шинах данных и драйверах. Поэтому нами был разработан конвейерный процессор, показанный на рис. 17.7, который требует только локальных связей. Первоначально элементы одномерных массивов

п+1 процессоров ,- -л,-

X. Ь

д

д

с

±

УС

"Г

с

Г. р		УС

р		УС
г
\ \
р		УС

Строки I

вычисляет а-1

вычисляет х=а-Ьс

вычисляет ab

а регистр для запоминания а

У			У
\			I *
УС			УС
			\
УС			УС

со

С;

Рис. 17.7. Функциональная схема, реализации конвейеризованного алгоритма Фадеева-Д - делитель; У - умножитель, Ус - "

умножитель-сумматор; р - регистр

С и В запоминаются в процессорах ниже двойной линии и справа от одинарной сплошной линии соответственно, а п 2 элементов матрицы Л запоминаются в левом верхнем углу, и определяется функция каждого элементарного процессора. Связи между соседними процессорами осуществляются по горизонталям, вертикалям и диагоналям. На каждом шаге активные процессоры осуществляют указанные вычисления и передают данные соседним процессорам для их дальнейшего использования. Этот вариант организации процессора имеет характер "волнового фронта" [18], когда одна волна активности распространяется по всему процессору. Однако можно распространить этот подход и на последовательные конвейерные волны. Для вычислений большего объема, когда В, С и D - матрицы, потребуется увеличить размеры процессора.

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

Для решения уравнений вида

«ы

«12

а

13

«12

«и

а

12

а

а

13

11

и

(17.17)

а

In

а

пп

X

л

с теплицевой матрицей можно использовать другой метод, требующий только одного массива процессоров [16]. При использовании этого метода в сущности необходимо выполнить следующие четыре шага: декомпозицию матрицы А:

А = UU+,(17.18)

обратную подстановку:

<р= [ir] 1B,(17.19)

умножение:

ф=[0]"1,(17.20)

где D - диагональная матрица щ1, щ\ , • • • > и~1т,

и обратную подстановку для получения конечного результата: Х= [U]"1 ф. Этот метод основан на алгоритме Винера - Левинсона [20], в котором используется симметрия матрицы А и все вычисления реализуются за 0(п) операций. Схема процессорной матрицы для этих вычислений показана на рис. 17.8. Она состоит из п каскадов одинаковых секций, каждая из которых содержит два процессора, выполняющих умножение и сложение, четыре регистра и стек. В общей структуре могут быть выделены две базовые секции: массив процессоров для получения U* на основе алгоритма Винера - Левинсона (ВЛ-структура) и секция обратной подстановки, которая служит для получения как промежуточного результата Ф, так и конечного результата X. Меж-

315

0 ... 48 49 50 51 52 53 54 ... 78