книги из ГПНТБ / Торгашев В.А. Система остаточных классов и надежность ЦВМ

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

Аналогично вычисляются таблицы констант, соответствующие любому числу отказавших модулей.

Вместо того, чтобы каждый раз корректировать результаты опе­ раций умножения п деления, можно при отказе какого-либо из ин­ формационных модулей и переходе к другому знаменателю изменить числители всех дробей, хранящихся в ОЗУ. Тогда в процессе даль­ нейшей работы ЦВМ отпадает необходимость корректировать ре­ зультаты каких-либо операций.

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

Пример 2. 8. В исходной системе остаточных классов с основа­ ниями 3, 5, 7, 11, 13, 17, 19 первые четыре модуля являются инфор­

исключить из СОК, так как в них возникли ошибки постоянного типа. Тогда:

{А (3)}лі-= {0,2,9,10.16}*,;

Оценим разность между величинами дробей A jN и A J N 1:

70

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

Если отказал информационный модуль р,-, то при его исключе­ нии знаменатель уменьшается в р,- раз. Для того чтобы величина дроби не изменилась, числитель необходимо разделить на р,-. При этом данную операцию следует проделать со всеми дробями, запи­ санными в оперативном запоминающем устройстве и принимающими участие в решении дайной задачи. Если отказал один из контроль­ ных модулей, то он заменяется информационным модулем р„ (при условии, что р„ больше всех остальных информационных модулей).

в ЦВМ, а — диапазон представления входной информа­ ции, то исходные данные можно записывать в ЦВМ в следующей форме:

71

Величину l/li-W,,]^ найдем с помощью метода, предложенного в предыдущем параграфе. Так как < N u то минимальное рас­ стояние кода при вычислении величины {А/р/}^', определяется

модулями, входящими в произведение R N 2.

Следует отметить, что при уменьшении точности вычислении увеличивается скорость обработки информации, так как быстродей­ ствие ЦВМ изменяется прямо пропорционально числу информа­ ционных модулей.

В тех случаях, когда одновременно предъявляются высокие требования и к точности и к надежности решения задачи, а с по­ мощью модулей, используемых в ЦВМ, эти требования не обеспе­

арифметических операций. Однако, если учесть, что число информа­ ционных модулей, а следовательно, и время выполнения операции перевода чисел из СОК в ССО уменьшатся в два раза, то число модульных операций, необходимых для выполнения вычислений, увеличится примерно в полтора раза для умножения и деления, в п/2 раз для сложения и вычитания, а для остальных операций менее чем в полтора раза. Количество модульных операций, необ­

чтобы код позволял исправлять ошибки постоянного типа в любых

разно использовать в тех случаях, когда высокие требования к точ­ ности и надежности характерны лишь для части задач, решаемых на ЦВМ. С помощью небольшой подпрограммы можно легко пере­ ходить от одного способа представления чисел к другому, тем самым полностью используя резерпы точности, быстродействия пли надежности ЦВМ, которые образуются при выполнении различных задач.

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

72

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

Предположим, что запоминающее устройство содержит N ячеек

ошибку. Обычно при появлении ошибки в коде адреса приходится останавливать ЦВМ (если код не позволяет исправить эту ошиб­ ку). Если же адреса представлены в системе остаточных классов, то сигнал ошибки можно использовать для перехода к той части программы, которая размещается в первых Njpn или меньшем количестве ячеек запоминающего устройства. В этих ячейках мо­ жет храниться программа какого-либо контрольного теста, после выполнения которого происходит возвращение к рабочей програм­

какого-либо элемента адресного тракта, то переход к выполнению

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

Таким образом, R-код с минимальным расстоянием d = 2 позво­ ляет исправлять одиночные ошибки постоянного типа.

Обычно в управляющих ЦВМ используются запоминающие уст­ ройства двух типов. Для хранения программы и различных кон­ стант служит постоянное запоминающее устройство (ПЗУ), а дан­ ные (исходные, промежуточные и результаты) хранятся в оператив­ ном запоминающем устройстве (ОЗУ). Поэтому если ошибка про­ изошла в адресном тракте ОЗУ, то для локализации отказавшего модуля следует перейти к такому участку программы, в процессе выполнения которого используются лишь первые N/p„ ячейки ОЗУ. Естественно, что данный участок программы не обязательно должен носить тестовый характер.

Предположим, что ЦВМ решает ряд различных самостоятельных задач л программы, соответствующие некоторым из этих задач, можно разместить в первых N/p„ ячейках ПЗУ. Тогда при исклю­ чении какого-либо модуля прежнюю корректирующую способность кода можно сохранить, если ограничиться лишь выполнением про­ грамм, расположенных в первых N/pn ячейках ПЗУ. При появле­ нии второй ошибки номер неисправного модуля можно определить, переходя к программам, расположенным в первых N/(pn_\, р„) ячейках и т. д.

Таким образом, использование приведенного выше корректиру­ ющего кода позволяет обеспечить безошибочное выполнение всей программы, записанной в ЗУ при отказе любого модуля системы остаточных классов, в которой представлен код адреса, или безоши­ бочное выполнение части программы, записанной в первых N/p„ ячейках ПЗУ при отказе двух любых модулей, или части програм­ мы, записанной в первых NI(pn-iPn) ячейках ПЗУ при отказе трех любых модулей и т. д.

73

То же самое справедливо и для оперативного запоминающего устройства. Разница состоит лишь в том, что при отказе каких-либо модулей адресного тракта ОЗУ приходится переходить к таким частям программы, при выполнении которых используются только

N/pп, Nj(pn_\pn) ячеек ОЗУ и т. д.

Итак, применение системы остаточных классов позволяет суще­ ственно повысить надежность ЦВМ. Даже в тех случаях, когда количество отказавших элементов превышает корректирующие воз­ можности К-кода, машина все еще может решать ряд наиболее важных задач, хотя, скорее всего, с меньшей точностью.

2.7.ФУНКЦИОНАЛЬНОЕ КОДИРОВАНИЕ

Одним из наиболее замечательных свойств системы остаточных классов является независимость и равноправность всех оснований. Даже в том случае, когда исходная СОК не. избыточна, отказ элементов, относящихся к любому из модулей, не приводит к пол­ ному выходу ЦВМ из строя. Если каким-либо способом установить факт появления ошибки и локализовать ее, то, исключая неисправ­ ный модуль из СОК, можно продолжать вычисления при некотором уменьшении точности. Поэтому, применяя для обнаружения ошибок, возникающих в ходе решения задачи, программные методы конт­ роля, можно обеспечить высокую надежность ЦВМ, работающих в системе остаточных классов, не привлекая практически никакой добавочной аппаратуры.

К числу наиболее эффективных алгоритмических способов обна­ ружения и коррекции ошибок относится метод избыточных пере­ менных (функциональное кодирование) [6—8].

Для того чтобы избежать введения большого числа новых по­ нятий, ограничимся изложением лишь основной идеи этого метода. Любой алгоритм можно рассматривать как некоторое отображение

выходных переменных, добавляя функции у„ +1 ...........У п + г такие, что:

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

В работах [6, 7] подробно исследуются вопросы построения функциональных кодов для таких исходных функций у\, . .., у п, которые являются линейными относительно некоторой базисной си­

74

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

Если функции у\, . . у,, обладают указанным выше свойством, то добавочные переменные определяются как линейные комбина­ ции исходных функций.

Для обнаружения практически любых ошибок достаточно вве­ сти лишь одну добавочную переменную:

Добавочная переменная вычисляется либо непосредственно п разложению относительно базисных функции, либо путем «сверты­ вания» его в более удобную формулу. Очевидно, что при отсут­ ствии ошибок должно выполняться следующее условие:

п + 1

2 У '1(•*!’ ' ' ' 1Хт) = t= 1

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

л+ 1

2 УI ("И >• ' ■' х т) < д . /=1

где А — максимально допустимая ошибка, которая может появиться в результате суммирования указанных погрешностей.

Нетрудно убедиться в том, что рассмотренный код позволяет

Кроме того, обнаруживается любая комбинация таких грубых оши­ бок, сумма которых по абсолютной величине больше, чем Д. Оче­

75

составляет 1—NIL. Поскольку A/LÄ;0, можно считать, что практи­ чески любые ошибки, возникающие в процессе решения задачи, могут быть обнаружены с помощью подобного простейшего функ­ ционального кода.

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

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

у, = х, sin а -+- A'jjlcos’a; у2 = х хCOS а + Sin а.

Положим у3 = — (Уі + Уг)- Тогда, выполняя элементарные триго­ нометрические преобразования, получим:

Уз = — 1,41 [л', cos (я/4 — а) -f- jr* Sin (it/4 — а)]. При этом выполняется контрольное условие

задачи. Если грубые ошибки, искажающие отдельные выходные пе­ ременные, являются независимыми, то для коррекции любых /-крат­ ных ошибок достаточно использовать 2t добавочных переменных. Причем подавляющую часть этих ошибок можно исправить при использовании лишь t+ 1 добавочных переменных. Здесь также мож­ но провести определенную аналогию с корректирующими /^-кодами. Следует отметить, однако, что отказ какого-либо из элементов ЦВМ чаще всего приводит к искажению всех функций, вычисляемых в ходе решения задачи. Поэтому корректирующие функциональные коды принципиально не могут применяться для борьбы с подоб­ ными ошибками и область их применения обычно ограничивается коррекцией ошибок, обусловленных случайными сбоями. В то же время даже простейший функциональный код в сочетании с систе­ мой остаточных классов позволяет в известной степени бороться

с ошибками, вызванными отказами элементов ЦВМ.

Пусть в вычислительной машине используется нензбыточная

лении ошибки нарушается контрольное условие: м+ 1

Для того чтобы проверить, не вызвана ли ошибка случайным сбоем, задачу следует прорешать еще раз. Если и в этом случае

76

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

л+1

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

Если же исключен исправный модуль р>, то вероятность выпол­

искажениях символов по основанию р,- минимальная величина ошиб­

машина продолжает работать в сокращенной СОК, т. е. с умень­ шенной точностью. Тем временем неисправный блок можно ремон­

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

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

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

Итак, если ЦВМ работает в неизбыточной системе остаточ­ ных классов, то, решая задачи в функциональных кодах, можно по­ высить надежность машины с помощью простых программныя методов.

77

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

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

циальной декодирующей аппаратуры, кроме той, которая исполь­ зуется для реализации арифметических операций.

С помощью корректирующих ^-кодов можно обнаруживать, а порой и исправлять значительную долю''ошибок более высокой кратности, чем та, которая допускается заданным минимальным расстоянием кода. В частности, для коррекции одиночных ошибок можно использовать /?-код с минимальным расстоянием cf= 2, по­ степенно локализуя место ошибки в процессе выполнения операций модульного типа.

Методы локализации н коррекции ошибок, предложенные в этой главе, основаны на использовании свойств позиционных характери­ стик чисел. Эти методы позволяют восстанавливать правильные значения результатов как модульных, так п немодульиых опера­ ций без повторных обращений к исходным операндам. Более того, при помощи этих методов можно восстановить истинное значение остатка по некоторому основанию СОК даже в том случае, когда аппаратура арифметического устройства (АУ), соответствующая этому основанию, вышла из строя.

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

нии на одной и той же машине относительно разнородных задач. Например, если при решении какой-либо задачи часть ячеек ЗУ остается свободной и допустимо некоторое уменьшение скорости вычислений, то эти резервы также можно использовать для повы­ шения надежности ЦВМ, переходя к парному представлению чисел.

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

78

і-іия задачи, позволяет даже при использовании неизбыточной си­

стемы остаточных классов обеспечить работоспособность вычисли­ тельной машины.

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

Г Л А В А Т Р Е Т Ь Я

ПРИНЦИПЫ ПОСТРОЕНИЯ ЦВМ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

3.1. О СТРУКТУРЕ ВЫЧИСЛИТЕЛЬНЫХ МАШИН, РАБОТАЮЩИХ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

Данная работа в основном посвящена вопросам повышения надежности цифровых вычислительных машин. Эти вопросы с осо­ бой остротой встают при проектировании управляющих ЦВМ, по­ скольку отказ такой машины в процессе работы может» привести к катастрофическим последствиям.

Поэтому излагаемый ниже материал ориентирован именно на управляющие ЦВМ. Основной особенностью таких машин, по-види­ мому, следует считать наличие двух внутренних запоминающих устройств: оперативного, предназначенного для хранения чисел, и постоянного, в котором хранится программа и некоторые числовые константы. Специфика управляющих машин, безусловно, заключается также в особой организации устройств ввода-вывода (однако в дай­ ной работе эти устройства ме рассматриваются).

На рис. 3.1 приведена блок-схема простейшей управляющей ЦВМ (без устройства ввода-вывода). Более сложные ЦВМ могут содержать схемы модификации адресов, индексные регистры, одно или несколько сверхоперативных запоминающих устройств, схемы, обеспечивающие реализацию различных систем адресации (прямой, косвенной), и т. д. Однако все эти добавления относительно слабо влияют на структуру основных блоков ЦВМ. В то же время пере­

В дальнейшем основное внимание будет акцентироваться на тех отличиях в структуре основных устройств ЦВМ, которые обуслов­ лены применением системы остаточных классов. И хотя полученные результаты относятся непосредственно только к относительно про­ стому варианту ЦВМ, приведенному на рис. 3.1, но их легко рас­ пространить и на более сложные варианты.

79