СИСТОЛИЧЕСКИЙ ПРОЦЕССОР ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ Российский патент 1994 года по МПК G06F15/31 

Описание патента на изобретение RU2015549C1

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

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

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

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

Работа систолической матрицы происходит по формуле
Y = ((Xn W + Xn-1)W + ...)W + Xo, (2) где Y представляется по нескольким основаниям, т.е. процессор работает по Pi каналам и, используя формулу (1), результатом переводится в позиционную систему. В случае сбоя по какому-нибудь из каналов Pi на выходе процессора формируется неправильный результат, тогда рассмотрим следующее:
P1 < P2 < ... < Pn < Pn+1 < Pn+2, где P = Pi - рабочий диапазон;
Pn= P Pj - полный диапазон.

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

Y′ = , Y; Y, (3) где Y находится по алгоритму
an-1= P
Q= где α(i

i-1)= для i = 2, 3, ..., n-1 при αi(o) = α2;
αn+1 = δ (an-1 - Q) (mod Pn+1) числа A по основанию Pn+1 при δ = PimodP, так как обработка ведется по n+2 каналам, имеем YY. Можем сравнить полученные результаты по контрольным основаниям, если
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, подключая отсчет XN-1 непосредственно к четвертому входу систолической матрицы. Затем производится вычисление полинома в следующей последовательности:
Wвх _→ Wвых
Y1вых ←_ ((Y1вх. Wвх) mod P1 + XN-l) mod P1
Y2вых ←_ ((Y2вх. Wвх) mod P2 + XN-l) mod P2
Y3вых ←_ ((Y3вх. Wвх) mod P3 + XN-l) mod P3
Y4вых ←_ ((Y4вх. Wвх) mod P4 + XN-l) mod P4
Y5вых ←_ (Y5вх. Wвх) mod P5 + XN-l) mod P5, где Y1вх, Y2вх, Y3вх, Y4вх, Y5вх - соответветственно Y1вых, Y2вых, Y3вых, Y4вых, Y5вых предыдущего операционного блока. В первом операционном блоке 5
Y1вх = Y2вх = Y3вх = Y4вх = Y5вх = XN-1. Через N-1 такт на вход блока 6 восстановления поданы сформированные результаты Y1вых, Y2вых, Y3вых, которые преобразуются из СОК в ПСС:
Y = Y. Одновременно блок 7 расширения выдает количественные результаты Y , Y , которые сравниваются с результатами Y = Y4вых; Y = Y5вых. Если Y4вых - Y = 0, Y5вых - Y = 0, то сбоев не было; если Y4вых - Y ≠ 0, Y5вых - Y ≠ 0, то происходит коррекция результата:
Y - Yкорр, где Yкорр вырабатывается блоком 16 постоянной памяти.

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

Похожие патенты RU2015549C1

название год авторы номер документа
СИСТОЛИЧЕСКИЙ ПРОЦЕССОР ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С КОРРЕКЦИЕЙ ОШИБКИ 1992
  • Калмыков Игорь Анатольевич
  • Оленев Александр Анатольевич
  • Бережной Виктор Васильевич
RU2018950C1
СИСТОЛИЧЕСКИЙ ОТКАЗОУСТОЙЧИВЫЙ ПРОЦЕССОР ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 1992
  • Калмыков Игорь Анатольевич
  • Оленев Александр Анатольевич
RU2029437C1
Систолический процессор для вычисления полиномиальных функций 1988
  • Кухарев Георгий Александрович
  • Тропченко Александр Ювенальевич
  • Павловский Владимир Федорович
SU1608689A1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ 2+1 1991
  • Оленев Александр Анатольевич
RU2012136C1
УСТРОЙСТВО ДЛЯ КОНТРОЛЯ И ИСПРАВЛЕНИЯ ОШИБОК В ИЗБЫТОЧНОМ МОДУЛЯТОРНОМ КОДЕ 1991
  • Бережной Виктор Васильевич
  • Червяков Николай Иванович
  • Оленев Александр Анатольевич
  • Николаев Юрий Иванович
RU2022472C1
УСТРОЙСТВО ДЛЯ КОНТРОЛЯ И ИСПРАВЛЕНИЯ ОШИБОК В ИЗБЫТОЧНОМ МОДУЛЯРНОМ КОДЕ 1991
  • Бережной Виктор Васильевич
  • Оленев Александр Анатольевич
  • Микула Николай Павлович
  • Николаев Юрий Иванович
RU2015620C1
Многоканальный систолический процессор для вычисления полиномиальных функций 2020
  • Калмыков Игорь Анатольевич
  • Юрданов Дмитрий Владимирович
  • Волошин Евгений Александрович
  • Проворнов Игорь Александрович
  • Калмыкова Наталья Игоревна
RU2737236C1
Арифметическое устройство для процессора быстрого преобразования Фурье 1981
  • Коляда Андрей Алексеевич
  • Василевич Леонид Николаевич
  • Ревинский Виктор Викентьевич
  • Чернявский Александр Федорович
SU1042028A1
УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ ЧИСЛА В КВАДРАТИЧЕСКИЕ ОСТАТКИ 1992
  • Оленев Александр Анатольевич
  • Червяков Николай Иванович
  • Горлачев Игорь Викторович
  • Федорцов Сергей Владимирович
RU2029436C1
ПРОЦЕССОР С МАКСИМАЛЬНО ВОЗМОЖНОЙ ПРОИЗВОДИТЕЛЬНОСТЬЮ ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 2005
  • Стальной Александр Яковлевич
  • Литвинов Дмитрий Михайлович
  • Шуцко Валерий Александрович
RU2290687C1

Иллюстрации к изобретению RU 2 015 549 C1

Реферат патента 1994 года СИСТОЛИЧЕСКИЙ ПРОЦЕССОР ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ

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

Формула изобретения RU 2 015 549 C1

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

Документы, цитированные в отчете о поиске Патент 1994 года RU2015549C1

Систолический процессор для вычисления полиномиальных функций 1988
  • Кухарев Георгий Александрович
  • Тропченко Александр Ювенальевич
  • Павловский Владимир Федорович
SU1608689A1
Приспособление для точного наложения листов бумаги при снятии оттисков 1922
  • Асафов Н.И.
SU6A1

RU 2 015 549 C1

Авторы

Оленев Александр Анатольевич

Даты

1994-06-30Публикация

1991-02-21Подача