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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) щ) 5 С 06 Р 15/332

ГОСУД

IlO ИЗО

ПРИ ГН

КАВ

OPCHOMY СВИДЕТЕЛЬСТВУ пользовано в специализированных системах для обработки сигналов и изображений. Цель изобретения — повышение точности вычислений за счет реализации арифметических операций в остаточных классах. Поставленная цель достигается за счет того, что в состав процессора входят информационный вход 1, входной регистр 2, коммутатор 3, систолическая матрица 4 из (N-1)-го операционного блока 5 (N — размер преобразования), блок восстановления 6, блок постоянной памяти 8, блок синхронизации. 4.ил. (54). С

U (21) 4 (22) 1 (46) 2 . (71) Л механи (72) Г и В.Ф. (53) 6 (56) S

Shivap

52, Р

Алл т ельнь работк с.416.

ТВЕННЫЙ КОМИТЕТ

РЕТЕНИЯМ И ОТНРЫТИЯМ

Т СССР

04860/24-24 .11.88 . 11.90. Вюл. ),"- 43 нинградский институт точной и и оптики

А.Кухарев, А.10.тропченко авловский

1.32(088.8)

umyunath К., Svivaram Н.S.

asad А.Р. Jorn Electron, 1982, рр.429-436. н Дж. Архитектура вычислиустройств для цифровой обсигналов, ТИИЭР, 1985, У 5, ТОЛИЧЕСКИР ПРОЦЕССОР ДЛЯ

ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ (57) Изобретение относится к вычис- лительной технике и может быть ис1606889 где % находится по алгоритму Евклида или из условия l\) Л; = 1modP.

Для практических вычислений удобно испольэовать модули вида

2",2"+1,2"-1. Тогда для и = 4, Р

16, Р = 17, Рь = 15, Р = 4080 °

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

Ъ,A.,= т . Л,= э -з= где -Л-т = Р/Р, % = Р/Р = 272

Далее найдем

i 1, 2, 3 вычеты,Л-, по modP

255 = 15тпос116 (5)

240 = 2тпос117

272 = 2mod15

Отсюда (6) (8) Т = Т; шосР

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

-5

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

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

Процессор содержит (фиг.1) информационный вход 1, входной регистр

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

13 запуска.

Операционный блок 5 (фиг2) содержит регистры 14 и 15, умножители 1618, узел 19 постоянной памяти из трех секций 20-22, сумматоры 23-25, узел

26 постоянной памяти из трех екций

27-29, информационные входы 30-34, выходы 35-39 и тактовый вход 40.

Блок 6 восстановления содержит (фиг.3);.узел 41 постоянной памяти из трех секЦий 42-44, узел 45 постояннои

35 памяти, трехвходовый сумматор 46, информационные входы 47-49, выход 50 и тактовый вход 51.

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

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

Дпя предотвращения переполнения разрядной сетки вычисления производят- . ся в достаточных классах, т.е. вычетами чисел по некоторому модулю.

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

55 система уравнений где Р— попарно взаимно.-простые чис4 ла, а i = 1,...,п, имеет единственное решение по modP. Это решение можно записать в виде п

Т = Т; ; 3. modP, (2) .

1 1

Ъ,.тт + Ъ Л + Ъ Л = 1ной4080> (3) тогда имеем сравнение

1modP

1modP (4)

1modP

255 э = P/P = 240 э

15 Ф. = 1modiб %,= 15

2 % = 1mod17 h = 9

2 h = 1mod15. h>= 8

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

Т = (Т 3825 + Т ° 2160 +

+ Т 2176)mod4080 (7)

Подставим значения .T, Т, Т в (7)

Т = /Т 3825 + Т ° 2160 +

+ Т 2176)mod4080, где Тт, Т, Ту — вычеты по модулям

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

Рассмотрим решение численного примера ° Пусть необходимо произвести вычисления по некоторой формуле у ((x>W + xPY + х1) + хо» где х0= О, хт = 31, х = 27, хз =35, 6С Я89

Опреде тим вычеты по каждому дулей

W 4 из мо

Х»

27 = 11modiб

27 = 10mod17

27 = 12mod15

1 = 15mod16

1 = 14mod1 7 t mod 15 — Зтпот11 6 — 1modf7

4 = 4mod16

4 = 4mod17

5mod15 4 = 4mod15 ь произведем арифметические ции с вычетами согласно форму) попарно, причем эти операции выполнять по модулям 16, 17, ответственно каждой паре

3 xäW + xà

4 = 12mod lá 12+ l i = 7тпос116

Теп р опе а ле 9 буд

15 со

4 = 4mod17

4+10 = 14mod17

4 = 5mod15 5+12 = 2modi5 (х,W+ х

7 4 = 12 mod16

14 ° 4 = 5mod17

2 4 = 8mod15

47 + х )У+х ((ХР+хг) +хв) W

15 = 11mod16 11 -4 = f 2modi á (х

14 = 2mod17 2 ° 4 = 8mod17

11 = 9modi5 9.4 = ámod15 ьзуясь формулой восстановления олучим результат в позиционной е счисления

Воспо (8), систе котор толуч числе

По соре(. загру посту

1, ко

:и эта ется отсче входи комму лич ес.ленин хода р поступ

12:3825 + 8;2160 + 6„ 2176

2796 mod (4080),. тй соответствует результату,. енному известным способом выий. ный цикл вычислений в процесиг. 1) состоит из двух этапов:. ки исходных данных х = ."х

» аюцих с информационного входа орый выполняется за N тактов, а вычислений, который реализуа (N-1) тактов. При загрузке ов данных х,, i G ON-2 выход го регистра 2 подключен через атор 3 к первому)входу систок и матрицы 4 и лишь при поступтсчета х„,данный отсчет с вы-; гистра 2 через коммутатор 3 ет уже на четвертый вход систолической матрицы 4. При загрузке на каждом такте отсчет х, 7 i 6 О,N-2 передается от операционного бло5 ка 5 с номером 1 к соседнему блоку с номером (1+1) . Зто достигается передачей соответствуюцего отсчета с второго выхода 36 операционного блока 5 на третий, вход 31 следуюцего операционного бло1p ка 5. В результате через N-1 тактов с наL чала загрузки отсчеты исходных данных х оказываются загруженными во все операционные блоки 5 систолической матрицы 4 и хранятся в ре15 гистрах l5 соответствуюцих блоков 5.

При этом в регистре 15 последнего

N-1 блока 5 хранится отсчет хо, а в регистре 15 первого операционного

20 блока — отсчет хт» . При поступлении последнего отсчета х, загрузка исходных данных закончена. Таким образом, этап загрузки исходных данных требует N тактов. На следующем такте с информационного выхода ПЗУ 8 на пя25 тый вход систолической матрицы поступает значение коэффициента W. Данный коэффициент поступает на вход

30 операционного блока 5 и заносится в регистр 14. С данного такта начи3 нается второй этап — этап. вычислений.

На этом этапе,на 1-м такте g 1 < 1,N с начала этапа 1-й операционный блок 5 выполняет оператптю вида: живых вх

У вы ((у»вi нв„) modp» +х»» )modP . Угвых ((угвх 7вх)птодР +хт» P)modPZ (10)

У„,„((У„„Wax)modp +х )modP

40 где У» вх, Уг»»x, Увqy есть соответственно у<вцх угвьп узвых предыдущего операционного блока 5. В первом oneр аци о ином блок е 5

>» ы уг вх уз вх т»-»

При выполнении базовых операций. (10) операцию у, х И er реализуется в умножителе 16 операция у

Э .г вх вх в умножителе 17, у хИ „— в умножи 0 теле 18. Нахождение вычетов по модулю Р», Р, Р> производится в соответствии с принципами табличной арифметики посредством обрацения к секциями 20-22 трехсекционного ПЗУ 19.

В каждой k(V k С 1,3) секции данного

ПЗУ хранятся остатки от деления (вычеты) всех возможных произведений у„вxW 8у по модулю Р». Аналогичные функции выполняет трехсекционное ПЗУ !

1608689

26, только в каждо" k-й секции которого записаны остатки от деления (вычеты) всех возможных сумм вида ((У» IIx WIEx)modPB + хH-0)modP<.

Через (N-1) такт с начала второго этапа будут сформированы резульTaTbI УЛ Ь.ь|х У Þbi>, У Х на выхоД

37-39 соответственно последнего операционного блока 5. С указанных выходов результаты поступают на выход систолической матрицы 4 и далее на входы 47-49 блока 6 восстановления.

В последнем реализуется операция, соответствующая выражению (7). В основу работы блока восстановления также положен принцип табличной арифметики. В трехсекционном ПЗУ 41 хранятся все возможные произведения вычетов на -нормирующие множители., При этом в каждой k-й секции: (It k 6 1,3) хранятся произведения у на „ Л, где ф „ и Л. определяются в соответствии с формулами (3) — (6).

Указанные произведения взяты по мо- 25 дулю P с целью экономии памяти каждой из секций ПЗУ. С выходов секций

42-44 указанные результаты поступают на входы трехвходового сумматора 46 и с его выхода сформированная сумма поступает на адресный вход ПЗУ, в котором хранятся остатки от деления (вычеты) полученной суммы по,модулю

P . Таким образом, с выхода ПЗУ 41 получен результат, сформированный в позиционной системе счисления.

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

4 процессора, когда все работы счетчи ка 53 примут единичное значение, в результате чего на выходе схемы совпадения блока 9 происходит переключение значения указывающего сигнала с нулевого значения на единичное. Выборка коэффициентов производится из ПЗУ

8 по адресу, соответствующему текуще-: му значению счетчика 53, поступаюгггему от блока 9 через адресный выход 12 на адресный вход ПЗУ 8, Формула из обр етения

Систолический процессор для вычисления полиномиальных функций, содержащий (N — 1) (N -размер преобразования) операционных блоков, блок синхронизации, коммутатор и входной регистр, выход которого подключен к информационному входу коммутатора, первый выход которого подключен к первому информационному входу первого операционного блока, второй, третий и четвертый информационные входы которого подключены к второму выходу коммутатора, управляющий вход которого подключен к первому тактовому выходу блока синхронизации, вход запуска которого является входом запуска процессора, информационным входом которого является информационный вход входного регистра, тактовый вход которбго сое-! динен с тактовыми входами всех операционных блоков и подключен к второму тактовому выходу блока синхронизации, при этом первый, второй и третий выходы i-го (i = 1, N-2) операционного блока подключены сооТ ветственно к второму третьему ичет-вертому информационным входам (i+1)го операционного блока, о т л ч а юшийся тем, что, с целью noBbI шения точности, в него введены блок постоянной памяти и блок восстановления, выход которого является информационным выходом процессора, информационный выход блока синхронизации подключен к адресному входу блока постоянной памяти, выход которого подключен к пятому информационному входу первого операционного блока, четвертый и пятый выходы i-го операционного блока подключены соответственно к первому и пятому информационным входам (i+1)-ro операционного блока, а первый, второй и третий выходы (N-1)-го операционного блока подключены соответственно к первому„ второму и третьему информационным входам блока восстановления, тактовый вход которого подключен к второму тактовому выходу блока управления, при этом блок восстановления содержит первый и второй узлы постоянной памяти и сумматор, первый, второй и третий информапионные входы ко-. торого подключены соответственно к первому, второму и третьему выходам первого узла постоянной памяти, первый, второй и третий адресные входы которого являются соответственно первым, вторым и третьим HHAopMBUEfoHHblMEI

1608689 в о к т п с т р в о с в в r м т к ньй

r c я н т и т е в г д и т р r в дами блока восстановления, выходом

oporo является выход второго узла тоянной памяти, адресный вход коого подключен к выходу сумматора, д синхронизации которого соединен ходами разрешения считывания перо и второго узлов постоянной паи и является тактовым входом бловосстановления, причем операционблок содержит первый и второй ретры, первый и второй узлы постоой памяти, первый, второй и тр6сумматоры и первый, второй и тий умножители, выходы которых

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

1608689

Тираж 568

Подписное

ВНИИПИ Государственного комитета по изобретениям и открьггиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина, 101

Редактор Н. Тупица

Заказ 3619

Составитель А.Баранов

ТекРед А.Кравчук Корректор А.Осауленко