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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных системах для обработки сигналов и изображений. Цель изобретения - повышение устойчивости к единичным сбоям. Для этого процессор содержит входной регистр 2, коммутатор 3, N - 1 операционных блоков 5, блок 6 восстановления, блок 7 расширения по дополнительным основаниям, блок 8 постоянной памяти, блок 9 управления, вычитатели 14, 15, блок 16 постоянной памяти, вычитатель 17. 2 ил.

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

Целью изобретения является повышение устойчивости процессора к единичным сбоям.

В основу работы предлагаемого процессора положено следующее.

Для предотвращения переполнения разрядной сетки вычисления производятся в остаточных классах и используется восстановление на основе китайской теории об остатках: A = , (1) где α_i= Amod ; β_i(0,0,..., 1,00) = .

Работа систолической матрицы происходит по формуле Y = ((X_n W + X_n-1)W + ...)W + X_o, (2) где Y представляется по нескольким основаниям, т.е. процессор работает по P_i каналам и, используя формулу (1), результатом переводится в позиционную систему. В случае сбоя по какому-нибудь из каналов P_i на выходе процессора формируется неправильный результат, тогда рассмотрим следующее: P₁ < P₂ < ... < P_n < P_{n + 1} < P_n+2, где P = P_i - рабочий диапазон; P_n= P P_j - полный диапазон.

Введя два контрольных P_j основания и используя основные соотношения системы остаточных классов, можно сказать, что если число Y больше A > P, то число неверно и произошел сбой. Поэтому обработку можно вести по i+2 основаниям, преобразуя результат Y в позиционную систему счисления, одновременно расширим полученный результат по контрольным основаниям, т.е.

Yʹ = , Y; Y, (3) где Y находится по алгоритму a_n-1= P _{Q =} где α⁽_i^i-1)= для i = 2, 3, ..., n-1 при α_i^(o) = α₂; α_n+1 = δ (a_n-1 - Q) (mod P_n+1) числа A по основанию P_n+1 при δ = P_i modP, так как обработка ведется по n+2 каналам, имеем Y Y. Можем сравнить полученные результаты по контрольным основаниям, если Y = Y и Y = Y - сбоя нет, в том случае, если Y ≠ Y и Y ≠ Y произошел сбой по одному из рабочих оснований. Любой другой случай говорит о возникновении сбоя в контрольных основаниях, тогда, произведя вычисление
Y - Y = Y и Y - Y = Y , и Y и Y (4) соответствуют методу нулевизации и однозначно определяют ошибку.

Таким образом, используя выражения (1), (3), (4), можно реализовать устойчивость систолического процессора по всем одиночным сбоям.

На фиг. 1 приведена схема систолического процессора для вычисления полиноминальных функций; на фиг. 2 - схема операционного блока.

Систолический процессор для вычисления полиноминальных функций содержит информационный вход 1, входной регистр 2, коммутатор 3, систолическую матрицу 4 из N-1 операционных блоков 5, блок 6 восстановления, блок 7 расширения по дополнительным основаниям, блок 8 постоянной памяти, блок 9, тактовые выходы 10 и 11, адресный выход 12 блока 9, вход 13 запуска, первый вычитатель 14, второй вычитатель 15, блок 16 постоянной памяти, третий вычитатель 17, информационный выход 18.

Операционный блок 5 (фиг. 2) содержит регистры 19 и 20, умножители 21-25, узел 26 постоянной памяти из пяти секций 27-31, сумматоры 32-36, узел 37 постоянной памяти из пяти секций 38-42, информационные входы 43-49, выходы 50-56 и тактовый вход 57.

Блок 7 может быть реализован по известному алгоритму (Торгашев В.А. Система остаточных классов и надежность ЦВМ. - Сов. радио, 1973, с.118., авт. св. СССР N 1282134, 1166116, кл. G 06 F 11/08, N 350000, кл. G 06 F 11/10).

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

Полный цикл вычислений в процессоре состоит из двух этапов: загрузки данных и вычислений. Загрузка производится по информационному входу 1 и выполняется за N тактов, этап вычислений - за N-1 тактов. Загрузка и вычисления производятся следующим образом. Производится загрузка N-1 тактов в регистры операционных блоков, а в N-й такт переключается коммутатор 3, подключая отсчет X_N-1 непосредственно к четвертому входу систолической матрицы. Затем производится вычисление полинома в следующей последовательности:
W_вх _→ W_вых
Y_1вых ←_ ((Y_1вх ^. W_вх) mod P₁ + X_N-l) mod P₁
Y_2вых ←_ ((Y_2вх ^. W_вх) mod P₂ + X_N-l) mod P₂
Y_3вых ←_ ((Y_3вх ^. W_вх) mod P₃ + X_N-l) mod P₃
Y_4вых ←_ ((Y_4вх ^. W_вх) mod P₄ + X_N-l) mod P₄
Y_5вых ←_ (Y_5вх ^. W_вх) mod P₅ + X_N-l) mod P₅, где Y_1вх, Y_2вх, Y_3вх, Y_4вх, Y_5вх - соответветственно Y_1вых, Y_2вых, Y_3вых, Y_4вых, Y_5вых предыдущего операционного блока. В первом операционном блоке 5
Y_1вх = Y_2вх = Y_3вх = Y_4вх = Y_5вх = X_N-1. Через N-1 такт на вход блока 6 восстановления поданы сформированные результаты Y_1вых, Y_2вых, Y_3вых, которые преобразуются из СОК в ПСС:
Y = Y. Одновременно блок 7 расширения выдает количественные результаты Y , Y , которые сравниваются с результатами Y = Y_4вых; Y = Y_5вых. Если Y_4вых - Y = 0, Y_5вых - Y = 0, то сбоев не было; если Y_4вых - Y ≠ 0, Y_5вых - Y ≠ 0, то происходит коррекция результата:
Y - Y_корр, где Y_корр вырабатывается блоком 16 постоянной памяти.

Предлагаемый процессор может обнаружить и скорректировать одиночный, а в некоторых случаях и двойной сбой. При этом время быстродействия практически не увеличивается, так как операцию расширения, вычитания и выбора кода коррекции можно осуществлять при переводе из СОК в ПСС.

Формула изобретения

СИСТОЛИЧЕСКИЙ ПРОЦЕССОР ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ, содержащий N - 1 (N - размер преобразования) операционных блоков, блок управления, коммутатор, блок восстановления, первый блок постоянной памяти и входной регистр, выход которого подключен к информационному входу коммутатора, первый выход которого подключен к первому информационному входу первого операционного блока, второй, третий и четвертый информационные входы которого подключены к второму выходу коммутатора, управляющий вход которого подключен к первому тактовому выходу блока управления, вход запуска которого является входом запуска процессора, информационным входом которого является информационный вход входного регистра, тактовый вход которого соединен с тактовыми входами всех операционных блоков и подключен к второму тактовому выходу блока управления, при этом первый - третий выходы i-го ( i= ) операционного блока подключены соответственно к второму - четвертому информационным входам (i + 1)-го операционного блока, адресный выход блока управления подключен к адресному входу первого блока постоянной памяти, выход которого подключен к пятому информационному входу первого операционного блока, четвертый и пятый выходы i-го операционного блока подключены соответственно к первому и пятому информационным входам (i + 1)-го операционного блока, а первый - третий выходы (N - 1)-го операционного блока подключены соответственно к одноименным информационным входам блока восстановления, тактовый вход которого подключен к второму тактовому выходу блока управления, при этом блок восстановления содержит первый и второй узлы постоянной памяти и сумматор, первый - третий информационные входы которого подключены соответственно к одноименным выходам первого узла постоянной памяти, первый - третий адресные входы которого являются одноименными информационными входами блока восстановления, выходом которого является выход второго узла постоянной памяти, адресный вход которого подключен к выходу сумматора, вход синхронизации которого соединен с входами разрешения считываний первого и второго узлов постоянной памяти и является тактовым входом блока восстановления, причем операционный блок содержит первый и второй регистры, первый и второй узлы постоянной памяти, первый - третий сумматоры и первый - третий умножители, выходы которых подключены соответственно к одноименным адресным входам первого узла постоянной памяти, первый - третий выходы которого подключены к первым информационным входам соответственно первого - третьего сумматоров, выходы которых подключены соответственно к первому - третьему адресным входам второго узла постоянной памяти, первый - третий выходы которого являются одноименными выходами операционного блока, первым информационным входом которого является информационный вход первого регистра, выход которого подключен к вторым информационным входам первого регистра, выход которого подключен к вторым информационным входам первого - третьего сумматоров, входы синхронизации которых соединены с входами синхронизации первого - третьего умножителей, тактовыми входами первого и второго регистров, входами разрешения считывания первого и второго узлов постоянной памяти и подключены к тактовому входу операционного блока, вторым - четвертым информационными входами которого являются первые информационные входы соответственно первого, второго и третьего умножителей, вторые информационные входы которых подключены к выходу второго регистра, информационный вход которого является пятым информационным входом операционного блока, четвертым и пятым выходами которого являются выходы соответственно первого и второго регистров, отличающийся тем, что, с целью повышения устойчивости устройства к единичным сбоям, в него введены блок расширения по дополнительным основаниям, первый - третий вычитатели, второй блок постоянной памяти, а операционный блок содержит дополнительно четвертый и пятый сумматоры, четвертый и пятый умножители, первые информационные входы которых являются соответственно шестым и седьмым информационными входами операционного блока, вторые информационные входы четвертого и пятого умножителей соединены с выходом второго регистра, выходы четвертого и пятого умножителей подключены соответственно к четвертому и пятому адресным входам первого узла постоянной памяти, четвертый и пятый выходы которого подключены к первым информационным выходам соответственно четвертого и пятого сумматоров, выходы которых подключены соответственно к четвертому и пятому адресным входам второго узла постоянной памяти, четвертый и пятый выходы которого являются соответственно шестым и седьмым выходами операционного блока, выход первого регистра подключен к вторым информационным входам четвертого и пятого сумматоров, входы синхронизации которых соединены с входами синхронизации четвертого и пятого умножителей и тактовым входом операционного блока, шестой и седьмой выходы (N - 1)-го операционного блока соединены с первыми входами соответственно первого и второго вычитателей, выход первого вычитателя соединен с первым адресным входом второго блока постоянной памяти, первый - третий выходы (N - 1)-го операционного блока соединены соответственно с одноименными информационными входами блока расширения по дополнительным основаниям, выход которого соединен с вторыми входами первого и второго вычитателей, выход второго вычитателя соединен с вторым адресным входом второго блока постоянной памяти, выход которого соединен с первым входом третьего вычитателя, второй вход которого соединен с выходом блока восстановления, выход третьего вычитателя является выходом процессора шестой и седьмой информационные входы первого операционного блока соединены с вторым выходом коммутатора, шестой и седьмой выходы i-го операционного блока - соответственно с шестым и седьмым информационными входами (i + 1)-го операционного блока.

РИСУНКИ

Рисунок 1, Рисунок 2