Систолический процессор для вычисления полиномиальных функций Советский патент 1990 года по МПК G06F17/14 G06F19/00 

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

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

На фиг.1 представлена структурная схема процессораi на фиг. 2 - структурная схема операционного блока ; на фиг. 3 - структурная схема блока восстановленияj на фиг. 4 - структурная схема блока синхронизации.

Проц ессор содержит (фиг.1) информационный вход 1, входной регистр 2, коммутатор 3, систолическую матрицу 4 из N-1 чоперацирнного блока 5,. блок 6 восстановления, информационный выход 7, блок 8 постоянной памяти (ПЗУ) коэффициентов, блок 9 синхронизации, тактовые выходы 10 и 11, информационный выход 12 блока 9, вход 13 запуска.

Операционный блок 5 (фиг2) содержит регистры 14 и 15, ,умножители 16- 18, узел 19 постоянной памяти из трех секций 20-22, сумматоры 23-25, узел 26 постоянной памяти из трех Секций 27-29, информ а1щонные входы 30-34, выходы 35-39 и тактовый вход 40.

Блоь 6 восстановления содержит (фиг.3)1 узел 41 постоянной памяти из трех сек1щй 42-44, узел 45 постоянной памяти, трехвходовый сумматор 46, информационные входы 47-49, выход 50 и тактовый вход 51.

Блок 9 синхронизации (фиг.4) содержит генератор 52 тактовых пульсов, счетчик 53 и дешифратор 54.

Процессор работает следующим образом.

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

Т Т,- modP; ,

(О

где Р- - попарно взаимно-простые числа, а i 1,...,п, имеет единственное решение по mod. Это решение можно записать в виде

Т 1,; A;modP, (2) .

где находится по алгоритму Евклида или из условия N; Л; ImodP.

Для практических вычислений удобно использовать модули вида 2,2 +1,. Тогда для п 4, Р 16, PJ, 17, РЙ 15, Р 4080.

Определим коэффигщенты из соотношений

А, ;L,+ 2.Л2.+ -А-з 1iaod4080, (3) тогда имеем сравнение 91 |А, 1modP .Aj, ImodP (4) ImodPj

где-A., p/p,, 255, Л,, p/p,, 240, , P/P 272.

Далее найдем вьяеты ;Л-, по raodP , i 1, 2, 3

255 15mod16

240 2mod17 (5)

272 2mod15 Отсюда

15.., -1mod16 , 15

2 2; 1mod17 9 (6)

2,, lTnod15- Лэ 8

B результате ИЗ (1) получим формулу преобразования вычетов в числе позиционной системы счисления

Т ( 3825 + Tj- 2160 +

+ Т,- 2176) mod4080 (7) Подставим значения-Т , Tj, Т в (7)

Т 3825 + Tg. 2160 +

+ T,j 2176) mod4080, (8)

где Т, Т, Tj -: вычеты по модулям

16, 17 и 15 соответственно.

I

Рассмотрим реиение численного примера. Пусть необходимо произвести вычисления по некоторой формуле

у ((x,W:+ x,J + y,)W + Хо, (9) где XQ О, X, 31 , Xg 27, Хд 35,

10

15

0h889

6

лическон матрицы 4, При загрузке на каждом такте отсчет х;У1е(П -2 передается от операционного бло- 5 ка 5 с номером 1 к соседнему блоку с номером (1+1).Это достигается передачей соответствующего отсчета с второго выхода 36 операционного блока 5 на третий : вход 31 следующего операционного блока 5.В результате через N-1 тактов с начала загрузки отсчеты исходных дан- ных X оказываются загруженными во все операционные блоки 5 систолической матрицы 4 и хранятся в регистрах 15 соответствующих блоков 5 При этом в регистре 15 последнего л-1 блока 5 хранится отсчет х а в регистре 15 первого операционного 20 . При поступлении последнего отсчета х,., загрузка исходных данных закончена. Таким образом этап загрузки исходных данньк тре- бует N тактов. На следующем такте с информационного выхода ПЗУ 8 на пятый вход систолической матрицы поступает значение коэффиодента W. Дан- ньи коэффициент поступает на вход 30 операционного блока 5 и заносится в регистр 14. С данного такта начинается второй этап - этап-вычислений. На этом этапе,на 1-м такте V 1 начала этапа 1-й операционный блок S выполняет операщто вида:

Изобретение относится к вычислительной технике и может быть использовано в специализированных системах для обработки сигналов и изображений. Цель изобретения - повышение точности вычислений за счет реализации арифметических операций в остаточных классах. Поставленная цель достигается за счет того, что в состав процессора входят информационный вход 1, входной регистр 2, коммутатор 3, систолическая матрица 4 из /N-1/-го операционного блока 5 /N - размер преобразования/, блок восстановления 6, блок постоянной памяти 8, блок синхронизации. 4 ил.

35

,,

40

45

У( nodl +x)inodP У2вык ()°1оар2 )raodP (Ю) Seb(x y ev WBx)niodPj +Xj)modPj ,

6Х У ie УзбХ есть соответ° (бык УЗВЫХ пР ДЬщущего операционного блока 5. В первом операционном блоке 5

ibx Уг вх У-5ВХ При выполнении базовых операций- (10) операцию у,w реализуется в VMHOMTiTorro 1/;

1 nj t}f i cclJlM

В умножителе 16, операция уR V jrUt- -arTTmnr А

Wo -.

, ,-t..i j, BV ttv

телГГТ - « Умножи- 0 теле Id. Нахождение вычетов по модуJTKl Р Р 15 f- tJ

« 2 Ч производится в COOT мГ..Г„Т5р1ЙГ cS- циями 20-22 трехсекционного ПЗУ 19. 5 В каждой k(Vke ТТз) секции данного ПЗУ хранятся остатки от деления (вычеты) всех возможных произведений ; ykftx sif по модулю Р.. Аналогичные функции выполняет трехсекционное ПЗУ

;

26, только п каждой k-й секции которого записаны остатки от деления (вычеты) всех возможных сумм вида

I ВХ

Wp,v)modPo +

БХ

)modPj.

у

Через (N-1) такт с начала второго этапа будут сформированы резуль- ,,, ,, У, 8ь,х выходах 37-39 соответственно последнего операционного блока 5. С указанных выходов результаты поступают на выход систолической матрицы 4 и далее на входы 47-49 блока 6 восстановления. В последнем реализуется операция, соответствующая выражению (7). В основу работы блока восстановления также положен принцип табличной арифметики. В трехсекционном ПЗУ 41 хранятся все возможные произведения вычетов на-нормируюпще множители.,. При этом в каждой k-й секции;

(Vk G 1,3) хранятся произведения у.,„у

Лл

1, где 7(. и jV (. определяются

в соответствии с формулами (3) - (6). Указанные произведения взяты по модулю Р с целью зкономии памяти каждой из секций ПЗУ. С выходов секций 42-44 указанные результаты поступают на входы трехвходового сумматора 46 и с его выхода сформированная сумма поступает на адресный вход ПЗУ, в котором хранятся остатки от деления (вычеты) полученной суммы по,модулю Р . Таким образом, с выхода ПЗУ 41 получен результат, сформированный в позиционной системе счисления.

Работа процессора синхронизируется тактовыми импульсами, поступающими с тактового выхода 10 блока управления на тактовые входы всех операционных устройств. Управляющий сигнал на переключение коммутатора 3 поступает с выхода 1,1 блока 9. Данный сигнал оказывается сформированным через (N-1) такт с начала работы процессора, когда все работы счетчи- ка 53 примут единичное значение, в результате чего на выходе схемы совпадения блока 9 происходит переключение значения указывающего сигнала с нулевого значения на единичное.. Выборка козффициентов производится из ПЗУ 8 по адресу, соответствующему текуще- му значению счетчика 53, поступаюй1ему от блока 9 через адресный выход 12 на адресный вход ПЗУ 8. ормула изобретения

Систолический процессор для вычисления полиномиальных функций.

0

5

0

5

0

5

0

5

0

5

содержащей (N-1) (N -размер преобразования) операционных блоков, блок синхронизации, коммутатор и входной регистр; выход которого подключен к информационному входу коммутатора, первый выход которого подключен к первому информационному входу первого операционного блока, второй, третий и четвертый информационные входы которого подключены к второму выходу коммутатора, управляющий вход которого подключен к первому тактовому выходу блока синхронизации, вход запуска которого является входом запуска процессора, информационным входом которого является информационный вход входного регистра, тактовый вход которого соединен с тактовыми входами всех операционных блоков и подключен к второму тактовому выходу блока синхронизации, при этом первый, второй и третий выходы i-ro (i i,N-2) операционного блока подключены соответственно к второму,третьему и че т- вертому информационным входам (i+1)- го операционного блока, о т л ч а ю- щ и и с я тем, что, с целью повышения точности, в него введены блок постоянной памяти и блок восстановления, выход которого является информационным выходом процессора, информационный выход блока синхронизации подключен к адресному входу блока постоянной памяти, выход которого подключен к пятому информационному входу первого операционного блока, четвертый и пятый выходы i-ro операционного блока подключены соответственно к первому и пятому информационным входам (i+1)-ro операционного блока, а первый, второй и третий вькоды (N-l)-ro операционного блока .подключены соответственно к первому,, второму и третьему информационным входам блока восстановления, тактовый вход которого подключен к второму тактовому выходу блока управления, при этом блок восстановления содержит первый и второй узлы постоянной памяти и сумматор, первый, второй и третий информационные входы ко-- торого подключены соответственно к первому, второму и третьему выходам первого узла постоянной памяти, первый, второй и третий адресные входы которого являются соответственно niep- вым, вторым и третьим информационными

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

0

5

0

5

операционного блока, первым инфор- ..-, мационнм входом которого является информационный вход первого регистра, выход которого подключен к вторым информационным входам первого, второго и третьего сумматоров, входы синхронизации которых соединены с входами синхрониза:ции первого, второго и третьего умножителей, тактовыми входами первого и второго регистров, входами разрешения считывания первого и второго узлов постоянной памяти и подключены к тактовому входу операционного блока, вторым, третьим и четвертым информанронными входами которого являются первые информационные входы соответственно первого, второго и третьего умножителей, вторые информационные входы которых подключены к выходу второго регистра, информащюнный вход которого является пятым информационным входом операционного блока, четвертым и пятым выходами которого являются вtIxo J;ы соответственно первого и второго регистров.

.г