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

 

Ьп ИСАНИЕ

ИЗЬБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистимеских

Республик (11) 478306 (61) Дополнительное к авт. свид-ву(22) Заявлено 25.07.73 (21) 1948110/18-24 с присоединением заявки №(23) ПриоритетОпубликовано 25.07.75,Бюллетень № 27

Дата опубликования описания 05.08.75 (51) М. Кл.

0 06 2 9/00

6 06 Х 15/20

Геоударотоеенмв комитет

Вовата Маеотров ССР ео делам нзооретеноа в открытие (53) УДК 681.326 (088.8) А. И. Гренишников (72) Автор изобретения (71) Заявитель (54) МАТРИЧНЫЙ ПАРАЛЛЕЛЬНЫЙ ПРОБЕССОР ДЛЯ

ВЫЧИСЛЕНИЯ ПРЕОБРАЗОВАНИЯ АДАМАРА

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

Известен матричный параллельный про- 5 цессор для вычисления преобразования

Адамара, содержащий в узлах матрипы вычислительные блоки, выполненные в виде сумматоров, входы каждого нз которых соединены с входами вычислительного блока, 10 а первый выход каждого вычислительного блока соединен с выходом соответствующего сумматора. Невысокое быстродействие известного процесса обусловлено затратами времени на хранение промежуточ- 15 ных результатов вычислений до окончания операции.

Бель изобретения - повышение быстродействия матричного параллельного процессора. 20

Достигается это тем, что каждый вычислительный блок содержит инвертор и дополнительный сумматор, выход которого соединен со вторым выходом вычислительного блока, один вход которого соединен с пер- 25 вым входом дополнительного сумматора непосредственно, а другой вход через инвертор соединен со вторым входом дополнительного сумматора, причем входы первого вычислительного блока второго и третьего столбцов матрицы соединены с первыми: выходами первого и второго вы числительных блоков первого и второго .столбцов матрицы соответственно, входы второго вычислительного блока второго и третьего столбцов матрицы соединены с первыми выходами третьего и четвертого вычислительных блоков первого и второго столбцов матрицы соответственно, входы третьего вычислительного блока второго и третьего столбцов матрицы соединены с вторыми выходами первого и второго блоков первого и второго столбцов матрицы соответственно, входы четвертого вычислительного блока второго и третьего столбцов матрицы соединены со вторыми выходами третьего и четиелToro емчислителм .ных блоков первого и второго столбцов матрицы соответственно, а входы вычисли;тельных блоков первого столбца и выходы

478306

В 2В 2В+ 0,5 СП

00,1010011 01,010011 01,110011 01 0,0

O0,110011 0l,10011 10,00011

10 0,01

00 0,001

01 0,0010

10 0,00101

01 0,001010

00 0,0010011

00,0011 00, 1011

00,00011

OO,1011

01,111

10,01

01,0

00,1

01,011

00,111 01,11

00, 01

00,1

00,0

00,0

3

Таблица2.!

СП СП СП А + А

01 01 10 0,1

10 10 00 001 вычислительных блоков третьего столбца матрицы соединены с входами и выходами,) процессора непосредственно.

На фиг. 1 представлена блок-схема

:процессора, на фиг. 2 схема вычисли;тельного блока.

Матричный параллельный процессор со,держит вычислительные блоки 1, объеди1 пенные в три столбца. Бифрами 2 и 3 обоз" начены соответственно входы и выходы

-процессора.

Вычислительный блок 1 содержит сумма;торы "4. -5 и инвертор 6. Пифрами 7,8 и 9, 10 рбозначены входы и выходы вычис-. лительного блока соответственно.

Информация поступает в процессор, бу,!дучи закодированной в виде степенных приf!

Декодирование представляет собой ал; гебраическое сложение количественных

, эквивалентов (весов) степенных приращений (см. последний,;столбец табл. 1).

Как видим выполнение операции сложе :, ния возможно только при отсутствии переносов на один разряд вперед, т. е. при отсутствии комбинаций степенных прираше;ний вида 10.10 и 00.00. Это условие вы;полняется всегда в силу существования ряда теорем.

Пример сложения закодированного ранее числа А = 0,0010011 (СП = 01.10.00.

1 1

01.10.01.00) и чйсла А = 0,0010101 ,(СП = 01; 10.00,10.00.10.11) приведен в таол. 2.

:ращений (СП). Кодирование производят по

:следующему алгоритму:

Масштабирование информации в пределах от О до 1.

Сложение с числом 0,5.

Умножение на 2.

Сложение с числом 0,5.

Первые два двоичных разряда, стоящие

1слева от запятой являются очередным сте- ! .,пенным приращением. ! 1

В табл. 1 приведен пример кодирования., числа A=0,0010011 в виде степенных +P ращений, тогда B = (A+0,5) !

i= (0,1010011) где В - кодируемое

Ф число, а - номер шага кодирования. !

Таблица 1.

00 00 0 О 010

01 10 10 0,0101

10 00 01 0,01010

01 10 01 0,010100

00 00 01 0,0101ООО

Сложение производится по мере поступ-l. ления прйрашений,. в приведенном примере5 478

Ф сверху вниз, т. е. от старших приращений к младшим.

Каждый вычислительный блок 1 матричного параллельного процессора реализует выражения: где а - номер столбца матричного параллельного процессора, А В - операнды, поступающие на входы

si

7 и 8 вычислительного блока 1 соответственно, А + 1, В. + 1 - результаты вычислений, поS ступающие на выходы 9 и

10 вычислительного блока

1 матричного параллельно -. го процессора соответственно.

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

Количество входов матричного параллельного процессора всегда кратно степени двойки. Тогда количество столбцов процессора будет равно величине показателя степени, а число строк - числу входов деленному пополам. Каждый вычислительный блок 1 обрабатывает информацию последовательно, начиная со старших разрядов. Вычислительный блок 1 реализует формулы (1) и (2), причем сумматор 4формулу (1), а сумматор 5 - формулу (2).

Инвертор 6 необходим для умножения числа,,В на -1.

306 6

Ю

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

Оценим быстродействие матричного параллельного процессора. Оно определяется задержкой всех вычислительных блоков 1, T. е. задержкой в наиболее короткцй последовательной цепи, составленной из вычи слительных блоков 1. В данном случае длина цепи равна количеству столбцов мат-, ричного параллельного процессора, которое можно вычислить по формуле )=tg

Тогда время, необходимое для обработки всего исходного массиве чисел .(в тактах)

Т= о яфИ„ где Н - количество входов матричного па раллельного процессора, равное количеству чисел в исходном об- . рабатываемом массиве, а М - j число старших разрядов результата, обеспечивающее необходимую точность вы- числений.

Если Н = 1024, длительность одного такта равна 1 мксек, а М =10, то Т=20 мксек, что в 800 раз быстрее, чем у известного процессора.

Работа матричного параллельного процессора происходит следующим образом. На входы 2 поступает последовательно информация, закодированная в виде степенных приращений. Обработанные в первом столбце матричного параллельного процессора старшие разряды результата поступают для дальнейшей обработки во второй столбец, оттуда — в третий и т. д. В то время, как с выходов 3 происходит выдача старших разрядов окончательного результата преобразования Адамара, на входы 2 еще продолжают поступать младшие разряды исходного массива чисел. Приняв с выходов 3 достаточное для обеспечения необходимой точности количество старших разрядов результата, процесс вычислений можно остановить. Легко видеть, что работа вычислительного блока 1 матричного параллельно"- : го процессора заключается в приеме очередных степенных приращений операндов и сложении (вычитанни) их в соответствии

Предмет изобретения

Матричный параллельный процессор для вычисления преобразования Адамара, со1 держащий в узлах матрицы вычислительные блоки, выполненные в виде сумматоров, входы каждого из которых соединены с входами вычислительного блока, а первый выход каждого вычислительного блока соединен с выходом соответствующего сумматора, отл и ч а ю щ н и с я тем, что, с целью повышения быстродействия, каждый вычислительный блок содержит инвертор и дополнительный сумматор, выход которого соединен со вторым выходом вычислительного блока, один вход которого соединен с первым входом дополнительного сумматора. непосредственно, а другой вход через ин-вертор соединен со вторым входом дополнительного сумматора, причем входы перво478306

Фиг. f го вычислительного блока второго и треть,его столбцов матрицы соединеныс первыми выходами первого и второго вычислительных блоков первого и второго столбцов матрицы соответственно, входы второго вычислительного блока второго и третьего столбцов матрицы соединены с первыми выходами третьего и четвертого вычислительных блоков первого и второго столбцов матрицы соответственно, входы третьего 10 вычислительного блока второго и третьего столбцов матрицы соединены со вторыми выходами первого и второго блоков первого и второго столбцов матрицы соответственно, входы четвертого вычислитель ного блока второго и третьего столбцов ,матрицы соединены со вторыми выходами третьего и четвертого вычислительных

:блоков первого и второго столбцов матри:цы соответственно, а входы вычислитель1 ных блоков первого столбца и выходы вычислительных блоков третьего столбца матрицы соединены с входами и выходами процессора соответственно.

478306

Составитель Ф.Шагиахметов

Ред ктор Е.Гончар Техред Л.Казачкова Корректор 1.БРахззина

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, 113035, Раушская наб., 4

Предприятие «Патент», Москва, Г-59, Бережковская наб., 24

Заказ Я

Изд. М 8Ж Тираж 679 Подписное