УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ПЕРЕПОЛНЕНИЯ ДИНАМИЧЕСКОГО ДИАПАЗОНА, ОПРЕДЕЛЕНИЯ ОШИБКИ И ЛОКАЛИЗАЦИИ НЕИСПРАВНОСТИ ВЫЧИСЛИТЕЛЬНОГО КАНАЛА В ЭВМ, ФУНКЦИОНИРУЮЩИХ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ
APPARATUS FOR DETECTING DYNAMIC RANGE OVERFLOW, DETERMINING ERROR AND LOCALISATION OF COMPUTATION CHANNEL FAULTS IN COMPUTERS OPERATING IN RESIDUE NUMBER SYSTEM

Изобретение относится к вычислительной технике и может быть использовано для тестирования вычислительных систем, функционирующих в системе остаточных классов.
Известно устройство для обнаружения, локализации и исправления ошибок в системе остаточных классов (Патент RU 2301442, G06F 011/08, G06N 003/06, 2007), содержащее нейронные сеть конечного кольца для формирования остатков по контрольным модулям системы остаточных классов, нейронные сети конечного кольца для вычисления синдрома ошибок, нейронные сети конечного кольца для исправления ошибок, блока памяти и логических элементов.
Однако данное устройство обладает следующими недостатками: низким быстродействием, вызванным высокой логической глубиной (количество последовательно соединенных нейронных сетей конечного кольца), большими аппаратными затратами и жесткими условиями, накладываемыми на абсолютную надежность каналов по избыточным модулям. Наиболее близкой по технической сущности к заявленному устройству является адаптивная параллельно-конвейерная нейронная сеть для коррекции ошибок (Патент RU 2279131, G06 №3/04, 2005 г.), которая содержит блок нейронной сети конечного кольца формирования цифр в представлении обобщенной позиционной системе счисления; блок обнаружения ошибок, блок реконфигурации и локализации ошибок и блок исправления ошибок.
Недостатками известного устройства являются сложность, которая объясняется наличием большого количества нейронных сетей конечного кольца и низкое быстродействие, которое пропорционально количеству модулей системы остаточных классов.
Целью настоящего изобретения являются упрощение устройства и повышение быстродействия.
1
2
n+r
i
i
i
i
i
i
n+1
n+r
i
Поставленная цель достигается тем, что устройство содержит: входной регистр 2, содержащий разрядные регистры 2-1, 2-2, …, 2-n+r для временного хранения контролируемого числа, представленного по модулям p, p, …, p; схему формирования проекций числа А по основаниям p (i=[1,n+r]) 3, (число A, полученное из А зачеркиванием цифры α называется проекцией числа А по основанию p); блоки памяти 4, содержащие элементы памяти 4-1, 4-2, …, 4-n+r для хранения констант по модулям p; сумматор 5 для суммирования произведения разрядных констант и соответствующих цифр разрядов числа; блок анализа на равенство, больше или меньше рабочего диапазона 6; триггер 9 для запуска и остановки счетчика проекций 10; блок логических элементов «И» 7, содержащий элементы «И» 7-1, 7-2, …, 7-n+r для локализации неисправного канала p; входные шины 1 для подачи контролируемого числа А, схему формирования проекций константы, соответствующей рабочему диапазону 11; блок хранения констант рабочего диапазона 12, состоящий из элементов 12, 12; сумматор 13; шину 8, сигнализирующую о неисправности p канала; шину сигнала «ошибка не установлена» 14 и шину 15 для подключения разрядов константы, соответствующей рабочему диапазону; шину 16 «переполнение диапазона и ошибка», сигнализирующую о переполнении рабочего диапазона и появлении ошибки.
Рассмотрим метод определения ошибки числа и номера неисправного канала системы остаточных классов, обладающий высоким быстродействием и низкими аппаратными затратами.
1
2
n
1
1
2
n
Суть метода основана на использовании Китайской теоремы об остатках числа, которая связывает позиционное число А с его представлением в остатках (α, α, …, α), где α - наименьшие неотрицательные остатки числа по модулям p, p, …,p. При этом используется нестандартный подход, который отличается от классического тем, что используются не абсолютные числа, а их относительные величины.
Кроме того, решение практически любой задачи управления требует сравнения в необходимый момент времени состояния управляемых объектов с заданными состояниями, соответствующими алгоритму функционирования систем. Целью сравнения является обнаружение факта совпадения или несовпадения значений величин, равенства или неравенства чисел, больших или меньших некоторых значений. Конкретное выполнение операции сравнения может определяться аппаратным или программным способом.
С целью упрощения определения переполнения динамического диапазона и исправления ошибок рассмотрим приближенный метод, который позволяет абсолютно правильно реализовать основные классы процедур принятия решений.
1
2
n
i
1
2
n
Суть приближенного метода сравнения модулярных чисел основана на использовании относительной величины анализируемых чисел к полному диапазону, определенному Китайской теоремой об остатках, которая связывает позиционное число А с его представлением в остатках (α, α, …, α), где α - наименьшие неотрицательные вычеты числа, относительно модулей системы остаточных классов р, р, …, p следующим выражением
i
i
i
где
p - модули СОК,
- мультипликативная инверсия P относительно p,и
Если (3) разделить на константу Р, соответствующую выбранному диапазону чисел, то получим приближенное значение
i
где
- константы выбранной системы, а α - разряды числа, представленного в СОК, при этом значение каждой суммы будет в интервале [0,1). Конечный результат суммы определяется после суммирования и отбрасывания целой части числа с сохранением дробной части суммы. Дробная часть может быть записана также как Amod1, потому что A=A+Amod1. Количество разрядов дробной части числа определяется максимально возможной разностью между соседними числами. При необходимости точного сравнения необходимо вычислить значение (4), которое является эквивалентом преобразования из СОК в позиционную систему счисления. Для решения поставленной задач достаточно знать приблизительное значение используемого числа А по отношению к динамическому диапазону Р, которое выполняется достаточно просто, но при этом верно определяется соотношение А=Р, А>Р или А<Р.
i
изб
n+1
n+2
i
i
i
Для определения ошибки, переполнения и локализации неисправного p канала используются избыточные СОК, имеющие n-рабочих r-контрольных оснований, при этом избыточный диапазон для двух избыточных модулей Р=Р·p·p, где Р=М - рабочий диапазон. Известно, что для практического применения достаточно иметь два избыточных основания, то есть r=2, при этом система гарантировано обнаруживает появления одновременно двух ошибок и одну ошибку исправляет. Если значения
, тогда число безошибочное. Аналогично определяется и переполнение диапазона представляемых чисел. Локализация неисправного канала осуществляется путем анализа относительных значений проекций числа к p. В результате анализа выявляется правильная проекция A числа А, которая определяет неисправный p канал.
i
Конечный процесс обнаружения переполнения динамического диапазона, ошибки и неисправного вычислительно p канала может быть представлен в виде обобщенного алгоритма:
1. Вычисление относительных значений
Если
, тогда ошибки нет, если
есть ошибка и переполнения динамического диапазона и тогда перейдем к шагу 2.
i
2. Вычисление относительных значений проекций
и M, если
то в разряде i нет ошибки, если
то в данном разряде есть ошибка, которая фиксируется на выходе устройства. На этом процесс заканчивается.
i
1
2
3
4
1
2
3
4
изб
Принцип обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправного канала покажем на примере. Предположим необходимо реализовать функциональный блок для реализации перечисленных функций вычислительной системы, функционирующей в СОК. Пусть набор модулей p, на которых основаны каналы вычислительной системы, равны: р=2, р=3, р=5, р=7. Выберем модули p=2, p=3 рабочими, а р=5, р=7 контрольными, тогда полный диапазон будет равен Р=2·3·5·7=210, а рабочий Р=М=2·3=6. Допустим правильный результат равен А=(1,0,3,3), а искаженный
, то есть во втором разряде возникла ошибка, вместо цифры 0 появилась цифра 1, а М=(0,0,1,6).
1
2
3
4
Для определения переполнения динамического диапазона и ошибки вычислим относительные значения
и
, представленные в СОК, и сравним их результаты. Для этого необходимо найти
Как показано в примере 1 K=0.5; K≈0.333, К=0.6, K=0.571. Тогда
i
i
i
i
i
Сравним результаты: 0.346>0.026 и мы можем заключить, что
Этим неравенством установлено наличие ошибки и переполнение динамического диапазона. Для локализации ошибочного канала найдем относительные значения проекции чисел
и М к P по каждому из оснований путем зачеркивания цифр α и m по основаниям p, где P, диапазон чисел, соответствующий i-проекции.
1
По основанию р=2
2
3
4
Для систем с основаниями р=3, р=5, р=7 получим
1
2
3
4
P=ppp=105, тогда
Вычислим:
Тогда
Сравним 0.692>0.052, тогда
2
По основанию р=3
1
3
4
Для систем с основаниями р=2, р=5, р=7 получим
2
2-1
2-3
2-4
Р=70, тогда P=35, P=14, P=10.
Вычислим:
Тогда
Сравним 0.042<0.084, тогда
3
По основанию р=5
1
2
4
Для систем с основаниями p=2, p=3, р=7 получим
3
3-1
3-2
3-4
P=42, тогда Р=21, Р=14, P=6.
Вычислим:
Тогда
Сравним 0.737>0.142, тогда
4
По основанию р=7
1
2
3
Для систем с основаниями p=2, p=3, р=5 получим
4
4-1
4-2
4-3
P=30, тогда P=15, P=10, P=6.
Вычислим:
Тогда
Сравним, тогда
0.433>0.2
2
i
2
Итак все результаты сравнении
и
показывают, что только по основанию p=3 относительное значение проекций числа
меньше, чем относительное значение константы M. Следовательно, ошибка произошла в канале по основанию р.
Рассмотрим работу устройства обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправного вычислительного канала в системах, функционирующих в системе остаточных классов, которые предназначены для оперативного определения вышеизложенных функций. Схема приведена на чертеже.
1
2
n+r
i
i
1
2
n
n+1
n+r
i
i
i
i
i
i
i
i
1
i
i
i
i
i
Контролируемое число А по шинам 1 поступает на входные регистры 2 по соответствующим модулям: p-регистр 2-1, р-регистр 2-2, …, p-регистр 2-n+r, а результаты в виде сигналов появляются на выходах устройства: шина 14 «ошибка не установлена»; шина 16 «переполнение диапазона и ошибка» и выходных шинах 8 «неисправный p» канал. По шине 15 константа М, соответствующая рабочему диапазону, по избыточным модулям поступает на вход схемы формирования проекций константы М 11. В начале работы устройства поступившие сигналы на вход схемы формирования проекций числа А по основания p и на вход схемы формирования проекции константы М по избыточным модулям напрямую проходят на блоки памяти 4 и 12 по соответствующим модулям р, р, …, p и p, …, p. Выходные сигналы схем формирования проекций являются адресами входных блоков памяти 4 и 12, элементам которых приписываются значение произведений Kα и Km, соответственно, 4-1, 4-2, … 4-n+r и 12-n+1, …, 12-n+r. Из элементов памяти выбранные значения в виде произведений Kα и Km поступают на вход сумматоров, соответственно, 5 и 13, где проходит их суммирования по mod1, т.е. отбрасываются целые части чисел. Полученные в виде дробных значений суммы поступают на входы блока анализа на равенство больше или меньше. Если результат сумматора 5 меньше, чем результат сумматора 13, то в блоке 6 формируется сигнал «ошибка не установлена» шина 14 и процесс заканчивается. Если результат сумматора 5 больше или равен результату сумматора 13, то формируется сигнал «переполнение диапазона и ошибка», который поступают на первые входы элементов «И» и вход «s» триггера 9 и переводит его в единичное состояние, выходной сигнал которого запускает счетчик проекции 10. Сигнал с первого выхода счетчика поступает на входы схем формирования проекций 3 и 11. По этому сигналу формируется первая проекция числа
и М, выходные сигналы которых являются адресными входами блоков 4 и 12, в элементах которых содержатся произведения Kα и Km, где K уже новые константы, соответствующие первой проекции. Выходные сигналы блоков памяти суммируются в сумматорах 5 и 13, результаты которых анализируются в схеме анализа 6. Если результат сумматора 5 меньше, чем результат сумматора 13, то формируется сигнал, равный единице, который поступает на все первые входы элементов «И», а на вторые входы элементов «И» поступают сигналы с выхода блока проекции 3, который соответствует первой проекции. Выходной сигнал появляется по шине 8 того элемента «И», у которого на оба входа одновременно поступают сигналы, выходной сигнал которого является индикатором неисправного канала. После анализа первой проекции счетчик проекции 10 формирует следующую проекцию и процесс контроля осуществляется аналогично. После формирования всех проекций сигнал с выхода блока проекции 3, соответствующий последней проекции, поступает на вход «R» триггера 9, выключает счетчик 10, который устанавливает в нулевое состояние. На этом процесс контроля прекращается, а устройство переходит в исходное состояние. Счетчик имеет емкость, равную n+r. После выполнения n+r проекций счетчик проекций 10 формирует сигнал окончания процесса контроля.
Предложенное устройство имеет лучшие как временные так и технические характеристики, которые определяют диапазон обрабатываемых данных. В известных устройствах диапазоны обрабатываемых данных определяются произведением модулей
, а в предложенном устройство определяется интервалом [0,1), а точность определяется разностью между соседними целыми значениями чисел (например 1 и 2), которые должны быть ниже максимально выраженной разницы ошибки. Это обстоятельство позволяется отбросить часть младших значащих разрядов дроби. Кроме того, старшие нулевые разряды можно отбросить, так как в описанных выше механизмах сравнения нас интересуют условия «больше»; «равно» или «меньше» без указания конкретной величины, на сколько больше или меньше. Разработанное устройство является лучшим на настоящее время и может быть применено в вычислительных системах, функционирующих в СОК.