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

1606889 где % находится по алгоритму Евкли"да или из условия Ъ Л; = 1 шойР.10 Для практических вычисленийудобно испольэовать модули вида2",2"+1,2"-1. Тогда для и = 4, Р16, Р = 17, Р = 15, Р = 4080.Определим коэффициенты из соот 15 ношений Ъ,Л,= 7,Л,= "э -з= где Л., = Р/Р %= Р/Р = 272Далее найдем 1=1,2,3 вычеты,Л-,по шос 1 Р 255 = 15 шос 116(8) Т=Т;шосР;,Изобретение относится к вычислительной технике и может быть использовано в специализированных системахдля обработки сигналов и изображений..5Бель изобретения - повьппение точности вычислений за счет реализацииарифметических операций в остаточныхклассах.На Фиг.1 представлена структурнаясхема процессора на фиг. 2 - структурная схема операционного блока,на фиг, 3 - структурная схема блокавосстановлениями на фиг. 4 - структурная схема блока синхронизации.Процессор содержит (фиг.1) информационный вход 1, входной регистр2, коммутатор 3, систолическую матрицу 4 иэ И.операционного блока 5блок 6 восстановления, информационный выход 7, блок 8 постоянной памяти (ПЗУ) коэффициентов, блок 9 синхронизации, тактовые выходы 10 и 11, информационный выход 12 блока 9, вход2513 запуска.Операционный блок 5 (Фиг 2) содержит регистры 14 и 15, умножители 1618, узел 19 постоянной памяти из трехсекций 20-22, сумматоры 23-25, узел26 постоянной памяти из трех 1 екций27-29, инФормаЦионные входы 30-34,выходы 35-39 и тактовый вход 40.1Блок 6 восстановления содержит(Фиг.3); узел 41 постоянной памяти изтрех секЦий 42-44, узел 45 постояннои35памяти, трехвходовый сумматор 46, информационные входы 47-49, выход 50и тактовый вход 51,Блок 9 синхронизации (Фиг.4)содержит генератор 52 тактовых импульсов, счетчик 53 и дешифратор 54.Процессор работает следующим образом.Дпя предотвращения переполненияразрядной сетки вычисления производят- .ся в достаточных классах, т.е. вычетами чисел по некоторому модулю.В связи с этим конечный результаттакже представлен вычетом, которыйнеобходимо восстановить до полногозначения в позиционную систему счисления. Такое восстановление производится на основе китайской теории обостатках, в которой утверждается,что для любых значений числе ТтТ55система уравнений где Р - попарно взаимно.-простые чис 4ла, а 1 = 1п, имеет единственное решение по шос 1 Р, Это решение можно записать в видепТ = т Т,3, Л,тпос 1 Р, (2),11 Ът 3-,+ ЪаЛ+ Ъ Л ф 1 шой 4080 (3)тогда имеем сравнение 1 шойР1 шос 1 Р (4)1 шодР255, Л = Р/Р = 240,15 Ф, =. 1 шой 16 %,= 15 2= 1 шой 17 % = 92= 1 тпой 15 - Ъп= 8 В результате иэ (1) получим формулу преобразования вычетов в числе позиционной системы счисления Т = (Тт 3825 + Т 2160 ++ Т 2176)тпой 4080 где Тт, Тп, Ту - вычеты по модулям16, 17 и 15 соответственно. Рассмотрим решение численного примераПусть необходимо произвести вычисления по некоторой формуле у = х У:+ хтИ + х,)И + х, (9) гдех 0=0, ххт =31, х=27, хз=35,Определим вычеты по каждомудулей из мо х,27 = 11 щой 16 27 = 10 щод 17 27 = 12 щод 15 1 = 15 щод 16 1 = 14 щос 117 1 пюс 15- Зтпос 11 6 - 1 тпод 17 4 = 4 щос 116 4 = 4 пюс 117 5 пюс 115 4 = 4 щос 115ьпроизведем арифметическиеции с вычетами согласно форму) попарно, причем эти операциивыполнять по модулям 16, 17,ответственно каждой парех И хднф + х4 = 12 тпос 116 12+11 = 7 тпос 116 5Теп ропе але 9буд15 со Зф 4+10 = 14 щос 117 4 = 4 щод 17 4 = 5 щод 15 5+12 = 2 тпой 15 (х,1 + х 7 4 = 12 тпод 16 144 = 5 щос 117 2 4 = 8 щос 115 1 т + х )тт+х х У+х )+х ) Ъ 7 15 = 11 щос 116 11 4 = 12 щос 116(х 14 = 2 щос 117 24 = 8 щой 17 11 = 9 щос 115 9.4 = бпюс 115 ьзуясь Формулой восстановленияолучим результат в позиционнойе счисления Воспо (8),систе котортолуччислеПосоре(.загрупосту1, кои этается отсче входи комму личес.ленин хода р поступ 12:3825 + 8;2160 + 621762796 щод (4080),.Й соответствует результату,. енному известным способом выий.ный цикл вычислений в процесиг. 1) состоит из двух этапов:ки исходных данных х = Гхаюцих с информационного входаорый выполняется за гх тактов,а вычислений, который реализуа (И) тактов. При загрузкеов данных х д 6 О,Ивыходго регистра 2 подключен черезатор 3 к первомувходу систок й матрицы 4 и лишь при поступтсчета х,данный отсчет с вы-,гистра 2 через коммутатор 3ет уже на четвертый вход систолической матрицы 4. При загрузке накаждом такте отсчет х,7 х 6 О,И передается от операционного блока 5 с номером 1 к соседнему блоку с номером (1+1) . Зто достигается передачейсоответствуюцего отсчета с второго выхода 36 операционного блока 5 на третий, вход 31 следуюцего операционного блогса 5. В результате через Мтактов с начала загрузки отсчеты исходных данных х оказываются загруженными вовсе операционные блоки 5 систолической матрицы 4 и хранятся в ре гистрах 15 соответствуюцих блоков 5.При этом в регистре 15 последнегоИблока 5 хранится отсчет хо, ав регистре 15 первого операционного 20блока - отсчет х м. При поступлениипоследнего отсчета хн, загрузка исходных данных закончена. Таким образом,этап загрузки исходных данных требует И тактов. На следующем такте синформационного выхода ПЗУ 8 на пятый вход систолической матрицы поступает значение коэффиггиента тх. Данный коэффициент поступает на вход30 операционного блока 5 и заноситсяв регистр 14. С данного такта начи нается второй этап - этап вычислений. ЗОНа этом этапе,на 1-м такте T 1 б 1,Б сначала этапа 1-й операционный блок 5выполняет операгггтю вида: 1 вых г вх,х Увхдвх) щоЖ +х )щоа,Уавых Упвх 1 вх)щодР 2 +хп )тпосР (10)Уьвьх УЗвх 1 хвх)щось +хм)щос 1 РЭ 40где У вх, У пх, У вх есть соответственно увцхф угвых, узвых предыдущегооперационного блока 5. В первом опер аци о ином блок е 545У ы ус вх уз вх хт-При выполнении базовых операций(10) операцию у, х И пх реализуетсяв умножителе 16 операция у и.я бх вхв умножителе 17, у хИ- в умножи теле 18. Нахождение вычетов по модулю Р ф Рйф Ръ производится В соответствии с принципами табличной арифметики посредством обрацения к секциями 20-22 трехсекционного ПЗУ 19.В каждой с(с С 1 3) секпии данногоПЗУ хранятся остатки от деления (вычеты) всех возможных произведенийувход пх по модузгю Р. Аналогичныефункции выполняет трехсекционное ПЗУ1608689 26, только в каждой 1 с-й секции которого записаны остатки от деления(вычеты) всех возможных сумм видас( (У 1 ох Ы ьх ) тос 1 Р я + х ) шос 1 Р.Через (И) такт с начала второго этапа будут сформированы результаты у Ььх у Юьи уЗ в Х на вь37-39 соответственно последнего операционного блока 5. С указанных выходов результаты поступают на выходсистолической матрицы 4 и далее навходы 47-49 блока 6 восстановления.В последнем реализуется операция,соответствующая выражению (7). В основу работы блока восстановления также положен принцип табличной арифметики. В трехсекционном ПЗУ 41 хранятся все возможные произведениявычетов на нормирующие множители.,При этом в каждой 1 с-й секции( 1 с 6 1,3) хранятся произведения у,снаЛ , где фи Л.с определяютсяв соответствии с формулами (3) - (6).Указанные произведения взяты по модулю Р с целью экономии памяти каждой из секций ПЗУ. С выходов секций42-44 указанные результаты поступаютна входы трехвходового сумматора 46 ис его выхода сформированная сумма 30поступает на адресный вход ПЗУ, в котором хранятся остатки от деления(вычеты) полученной суммы по,модулюР . Таким образом, с выхода ПЗУ 41получен результат, сформированныйв позиционной системе счисления.Работа процессора синхронизируется тактовыми импульсами, поступающими с тактового выхода 10 блока управления на тактовые входы всех опера Оционных устройств, Управляющий сигнал на переключение коммутатора 3поступает с выхода 1,1 блока 9. Данный сигнал оказывается сформированным через (Б) такт с начала работы4процессора, когда все работы счетчи ка 53 примут единичное значение, врезультате чего на выходе схемы совпадения блока 9 происходит переключение значения указывающего сигнала снулевого значения на единичное. Выборка коэффициентов производится из ПЗУ8 по адресу, соответствующему текуще-му значению счетчика 53, поступающемуот блока 9 через адресный выход 12 наадресный вход ПЗУ 8,Формула изобретенияСистолический процессор для вычисления полиномиальных функций,содержащий (М - 1) (Б -размер преобразования) операционных блоков, блок синхронизации, коммутатор и входной регистр; выход которого подключен к информационному входу коммутатора, первый выход которого подключен к первому информационному входу первого операционного блока, второй, третий и четвертый информационные входы которого подключены к второму выходу коммутатора, управляющий вход которого подключен к первому тактовому выходу блока синхронизации, вход запуска которого является входом запуска процессора, информационным входом которого является информационный вход входного регистра, тактовый вход которого соединен с тактовыми входами всех операционных блоков и подключен к второму тактовому выходу блока синхронизации, при этом первый, второй и третий выходы 1-го ( : 1, И) операционного блока подключены соответственно к второму, третьему ичет-вертому информационным входам (+1)- го операционного блока, о т л ч а ющ и й с я тем, что, с целью повышения точности, в него введены блок постоянной памяти и блок восстановления, выход которого является информационным выходом процессора, информационный выход блока синхронизации подключен к адресному входу блока постоянной памяти, выход которого подключен к пятому информационному входу первого операционного блока, четвертый и пятый выходы х-го операционного блока подключены соответственно к первому и пятому информационным входам (+1)-го операционного блока, а первый, второй и третий выходы (И)-го операционного блока подключены соответственно к первому второму и третьему информационным входам блока восстановления, тактовый вход которого подключен к второму тактовому выходу блока управления, при этом блок восстановления содержит первый и второй узлы постоянной памяти и сумматор, первый, второй и третий информапионные входы которого подключены соответственно к первому, второму и третьему выходам первого узла постоянной памяти, первый, второй и третий адресные входы которого являются соответственно первым, вторым и третьим информационнымив о к т п с т р в о с в в г м т кньй г с я н т й т е в г ди т р гв дами блока восстановления, выходом орого является выход второго узла тоянной памяти, адресный вход коого подключен к выходу сумматора, д синхронизации которого соединен ходами разрешения считывания перо и второго узлов постоянной пан и является тактовым входом бловосстановления, причем операционблок содержит первый и второй ретры, первый и второй узлы постоой памяти, первый, второй и тресумматоры и первый, второй итий умножители, выходы которых15 п ключены соответственно к первому, в орому и третьему адресным входам перо узла постоянной памяти, первый, в орой и третий выходы которого подчены к первым информационным вхосоответственно первого, второгоретьего сумматоров, выходы котоо подключены соответственно к перу, второму и третьему адресным в одам второго узла постоянной па мяти, первый, второй и третий выходы к торого являются соответственно и вым, вторым и третьим выходами операционного блока, первым информационнм входом которого являетсяинформационныи вход первого регистра,выход которого подключен к вторым информационным входам первого, второгои третьего сумматоров, входы синхронизации которых соединены с входамисинхронизации первого, второго итретьего умножителей, тактовыми входами первого и второго регистров,входами разрешения считывания первого и второго узлов постоянной памяти и подключены к тактовомувходу операционного блока, вторым,третьим и четвертым информационнымивходами которого являются первые информационные входы соответственнопервого, второго и третьего умножителей, вторые информационные входыкоторых подключены к выходу второгорегистра, информационный вход которого является пятым информационнымвходом операционного блока, четвертым и пятым выходами которого являются восходы соответственно первого ивторого регистров.1608689 иг 4 да ица ираж 56 одписное митета по и сква, Ж,изводственно-издательский комбинат "Патент", г. Ужгород,арина,Заказ 3619 ВНИИПИ Государственного 113035, оставитель А,БарановТехред А,Кравчук. . Корректор А.Осауленк обретениям и открьггиям при ГКНТ СССРаушская наб., д. 4/5