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

Чем же отличаются машины в остаточных классах от обычных позиционных ЦВМ?

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

Рис. 3.1

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

80

ствляющме сдвиги, без которых немыслима работа позиционных ЦВМ.

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

В рассматриваемой ЦВМ можно выделить четыре группы таких трактов:

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

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

3. Третья группа содержит счетчик команд (СК), адресную часть постоянного запоминающего устройства, а также те элементы устройства управления, которые обеспечивают обращение к ПЗУ. Для контроля и коррекции ошибок служит дешифратор адреса ПЗУ.

4. Наконец, последняя группа оборудования состоит из элемен­ тов ПЗУ и УУ, обеспечивающих хранение и расшифровку кодов операций. Коррекция ошибок в этом случае осуществляется при по­

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

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

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

ема решаемых задач, которые обеспечивает система остаточных классов.

3.2. СХЕМЫ СЛОЖЕНИЯ, ВЫЧИТАНИЯ И УМНОЖЕНИЯ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ

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

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

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

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

Если 2‘~] < р ^ 2 1, то сумму [ct+ßlji можно вычислять при по­

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

вычитания модуля, если окажется, что a + ß ^ p .

Количество оборудования, реализующего указанные дополни­ тельные операции, существенно зависит от типа используемъіх эле­ ментов, способа построения двоичного сумматора (накапливающе­

82

Обратный код числа ß соответствует величине ß ==2'—I—ß. Поэтому

I “ — ßlp = I“ + P - (2' - 1 - - P)\„ - H’a + J + p + 1|2,| p.

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

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

прибавить основание /;. Для этого можно использовать те же цепи, которые применяются и для коррекции результата операции сложе­ ния, так как

I a - ß — (2' — р) |2, = I a — р + р 12, .

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

Для вычисления произведения |a ß |P также можно воспользо­ ваться схемой сложения по модулю р, если остатки а и ß пере­ множать как обычные двоичные числа при помощи итеративной процедуры:

влево числу у(/—1). Если символ, соответствующий старшему раз­ ряду этого числа, равен единице, то 2у(/— 1 )^ 2 ' и, следовательно, после сдвига необходимо выполнить такую же коррекцию резуль­ тата, как и при сложении. В противном случае сдвиг суммы у (/—1) выполняется без коррекции.

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

Пусть числа а и а взаимно просты с модулем р. Тогда вели­ чина / называется индексом числа а по модулю р и основанию а, если а и а1 сравнимы по модулю р, т. е. / = inda а, если a l= а mod р. В этом случае величину а можно назвать антииндексом числа /,

Обычно основание индекса является фиксированным для каж­ дого модуля и потому при записи индексов опускается.

84

Предположим, что р является простым числом. Тогда справед­ ливы следующие соотношения:

если а н р mod р, то ind а = ind ß mod (р — 1), и наоборот:

пп

ind (a/ß) = (ind a — ind ß) mod (p — 1); ind 1 = 0 ;

ind 0 не существует.

Кроме простых модулей, индексы существуют для любых целых

V (aß) = [Ü (a) -f V (ß)] mod 2г_2-

Если обозначить (и, ѵ) = ind а, то

пп

85

по модулю р. Если сумма индексов меньше, чем 2', то результат операции умножения определяется непосредственно из таблицы ан-

ной сумме прибавить величину 2'—р+1.

Применение индексов для выполнения операции умножения на­ кладывает определенные ограничения на выбор оснований, входя­ щих в СОК, поскольку в качестве модулей могут использоваться только простые числа. Что касается модулей вида /У, 2р1 или 2', то из-за отсутствия индексов для чисел, имеющих общие дели­

зующей операцию * по модулю р, условимся понимать комбина­ ционную схему, которая каждой паве операндов а и ß ставит в со­ ответствие величину |а* Р |р .

Возможны различные способы построения подобных таблиц, но чаще всего для этих целей используется схема, приведенная на рис. 3.2. Схема состоит из двухступенчатых дешифратора и шифра­ тора. Дешифраторы первой ступени ДШ 1-1 н ДШ 1-2 преобразуют операнды а и ß из двоичной формы в унитарную. Дешифратор ДШ2 и шифратор Ш1 обеспечивают вычисление результата |oH}tß|p в унитарном коде, а шифратор Ш2 переводит полученный резуль­ тат в двоичную форму.

Будем считать, что дешифраторы состоят из логических эле­ ментов И, а шифраторы —• из элементов ИЛИ, причем слож­ ность этих элементов оценивается числом их входов. Тогда слож­ ность комбинационной схемы, которая предназначена для реализа­ ции таблицы, приведенной на рис. 3.2, можно оценить следующим образом:

Lp (Т) = 2L (ДШ1) + L (ДШ2) + L (Ш1) + L (Ш2) =

= 2рі + 2р* + р* + Ip ß ,

где L — сложность комбинационных схем; I— число двоичных раз­ рядов, необходимых для представления модуля.

86

Унитарным кодом числа называется код, содержащий только одну единицу, положение которой и определяет величину числа. Например, для р = 23 LP( T ) = 1937.

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

Lp {T) = 2/-2г + 2-2гІ -I- /-2г_1.

Для того же модуля р — 23; L P(T) =3472. Такую же сложность имеют таблицы для модуля, величина которых лежит в интервале (16,32).

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

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

взятое со знаком плюс либо минус в соответствии со следующим правилом:

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

S 7 = S o ® S ß 0 S 7 и у' = у ' .

Очевидно, что переход к прямым кодам позволяет при выполнении

рацию умножения, уменьшается до 518 при использовании непол­ ных дешифраторов и до 988 при использовании полных шифраторов и дешифраторов.

87

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

Пусть

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

где уі—управляющий сигнал, соответствующий операции вычитания. В этой таблице одновременно вычисляется как сумма мантисс (бло­

сложения и вычитания остатков в прямых кодах. Здесь при различ­ ных знаках операндов одна из мантисс предварительно преобразует­ ся в обратный код:

р = 2Z_1 — 1 — ß'.

Затем вычисляется сумма | a' + ß/ |p, из которой в процессе перехо­ да от унитарного кода к двоичному вычитается константа (2І_1—1).

Пусть V = 5а ® 5р, ß' = nß' + tiß',

(ST, 7 ' ) = | “' + ß '— w(2, - , - l ) | p .

висимости от способа построения таблицы, но добавляется значи­ тельно более простая коммутационная схема КС1, содержащая I—1

88

рис. 3.3,6, равна 714 (1132) *. Следовательно, применение прямых кодов для представления остатков позволяет уменьшить объем таб­ лиц, реализующих операции сложения и вычитания примерно в три раза.

Таблицы сложения, вычитания и умножения можно реализовать при помощи одной универсальной схемы. При этом за счет исполь-

Рис. 3.3

зования общих дешифраторов удается получить определенный вы­ игрыш в оборудовании по сравнению с вариантом, когда каждая из элементарных операций реализуется с помощью отдельной таб­ лицы. Структурная схема таблицы, реализующей операции сложе­ ния, вычитания и умножения для остатков, представленных в пря­ мых кодах, приведена на рис. 3.4, где iji — управляющий сигнал, со­ ответствующий операции умножения. Для модуля р — 23 сложность такой схемы равна 920 (1480).

Более подробные сведения о способах построения схем сложе­ ния, вычитания и умножения для различных модулей читатель мо­ жет найти в монографии И. Я. Акушского и Д. И. Юдицкого «Ма­ шинная арифметика в остаточных классах» (М., «Сов. радио», 1968).

* В скобках указывается сложность схемы при использовании полных дешифраторов и шифраторов.

89