"Базовые" микрооперации

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

Но какой же вид неисправной работы является наиболее характерным для электронных элементов? Сейчас уже остановлено, что "сбои" в электронных элементах, в частности, в триггерах, возникают значительно более часто, чем "отказы". Существует два режима работы электронных элементов: (1) режим, когда элемент находится в стабильном (устойчивом) состоянии и (2) режим переключения, когда элемент переключается из одного устойчивого состояния в другое. Экспериментально доказано, что интенсивность "сбоев" триггеров в режиме переключения больше на 2-3 порядка, чем интенсивность "сбоев" элементов, находящихся в стабильном состоянии. Отсюда вытекает, что "сбои" триггеров в режиме переключения являются наиболее вероятной причиной ненадежного функционирования процессоров. Вот почему проектирование самоконтролирующихся цифровых автоматов, гарантирующих эффективный контроль "сбоев" триггеров, является одной из важнейших проблем проектирования высоконадежных процессоров.

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

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

    Покажем возможность реализации этой идеи на основе "фибоначиевой" и "золотой" систем счисления. С этой целью рассмотрим четыре "базовые микрооперации":
  1. "свертка";
  2. "развертка";
  3. "перемещение";
  4. "поглощение".

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

"Свертка":
0 1 1 ® 1 0 0
"Развертка":
1 0 0 ® 0 1 1.

Микрооперация "перемещения"

является двуместной микрооперацией и реализуется над одним и тем же разрядом двух регистров, верхнего регистра A и нижнего регистра B. Если регистр A имеет двоичную цифру 1 в k-м разряде, а регистр B имеет двоичную цифру 0 в том же самом разряде, мы можем реализовать микрооперацию "перемещения". Это означает, что мы передвигаем цифру 1 из верхнего регистра A в нижний регистр B.

Микрооперация "поглощение"

также является двуместной операцией и состоит в том, что две "двоичные" цифры 1 одного и того же разряда регистров A и B взаимно уничтожаются, то есть заменяются двоичными цифрами 0.

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

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

Рассмотрим две двоичные комбинации, которые находятся в регистрах A и B. Сначала выполним все возможные микрооперации "перемещения" из верхнего регистра A в нижний регистр B:

В результате "перемещения" мы получаем две новые кодовые комбинации A' и B'. Мы видим, что первая кодовая комбинация есть "конъюнкция" кодовых комбинаций A and B (A' = A Щ B), а другая комбинация есть "дизъюнкция" кодовых комбинаций A и B (B' = A Ъ B) . Следовательно, мы можем использовать микрооперацию "перемещение" для выполнения "конъюнкции" (Щ) и "дизъюнкции" (Ъ).

Логическая операция "сложение по модулю 2" выполняется путем применения микроопераций "перемещения" и "поглощения". Например:

В рассмотренном выше примере мы выполнили одновременно все возможные микрооперации "перемещения" и "поглощения" над кодовыми комбинациями A и B. В результате такого преобразования мы получили две новые кодовые комбинации A' = "const 0" и B' = A Е B.

Логическая операция "инвертирование кода A" сводится к выполнению микрооперации "поглощения" над исходной кодовой комбинацией A и кодовой комбинацией B = "const 1":

В результате мы получаем кодовую комбинацию B' = `A в нижнем регистре B и кодовую комбинацию A' = "const 0" в верхнем регистре A.

"Фибоначчиевое" сложение. Раньше мы показали, как реализовать "счет" и "вычитание" двоичных единиц, используя микрооперации "свертка" и "развертка". И сейчас мы покажем, как реализовать "фибоначчиевое" сложение, используя "базовые микрооперации". Общая идея сложения двух "фибоначчиевых" или "золотых" представлений состоит в следующем. Мы должны переместить все "двоичные цифры 1 из верхнего регистра A в нижний регистр B. С этой целью мы используем микрооперации "перемещения", "развертки" и "свертки". Сумма формируется в нижнем регистре B.

В качестве примера просуммируем два "фибоначчиевых" представления:

A0 = 0 1 0 1 0 0 1 0 0 и B0 = 0 0 1 0 1 0 1 0 0.

Первый шаг "фибоначчиевого" сложения состоит в "перемещении" всех возможных 1 из регистра A в регистр B:

Второй шаг состоит в выполнении всех возможных "разверток" в кодовой комбинации A1, которая находится в регистре A, и всех возможных "сверток" в кодовой комбинации B1, которая находится в регистре B:

Сложение закончено, потому что все двоичные 1 перемещены из регистра A в регистр B. После приведения "фибоначчиевого" представления B3 к "минимальной" форме мы получаем результат сложения B3 = A + B:

B3 = 1 0 0 1 1 0 1 1 1 ® 1 0 1 0 0 1 0 0 1 ® 1 0 1 0 0 1 0 1 0 = A + B.

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

"Фибоначчиевое" вычитание. Общая идея вычитания, выполняемого над двумя "фибоначчиевыми" представлениями А и В, находящимися в регистрах А и В, состоит в следующем. "Фибоначчиевое" вычитание выполняется в "прямом" коде. При этом необходимо выполнить все возможные взаимные "поглощения" двоичных 1 в "фибоначчиевых" представлениях А и В до тех пор, пока одно из "фибоначчиевых" представлений A или B станет равным 0. Чтобы реализовать эту идею, мы последовательно выполняем упомянутые выше микрооперации "поглощения" и "развертки" над "фибоначчиевыми" представлениями в регистрах A и B. Результат вычитания всегда формируется в регистре числа, большего по абсолютной величине. Если результат вычитания формируется в верхнем регистре A, это означает, что знак результата положительный ("+"), в противном случае - отрицательный ("-").

Продемонстрируем "фибоначчиевое" вычитание с помощью следующего примера. Пусть необходимо вычесть "фибоначчиевое" представление B0 = 1 0 1 0 1 0 0 1 0 (регистр B) из "фибоначчиевого" представления A0 = 1 0 1 0 0 1 0 0 0 (регистр A).

Первый шаг состоит в "поглощении" всех возможных двоичных 1 в "фибоначчиевых" представлениях A0 и B0:

Второй шаг состоит в "развертке" "фибоначчиевых" представлений A1 и B1:

A1 = 0 0 0 0 0 1 0 0 0 ® 0 0 0 0 0 0 1 1 0 = A2,
B1 = 0 0 0 0 1 0 0 1 0 ® 0 0 0 0 0 1 1 0 1 = B2.

Третий шаг есть "поглощение" двоичных 1 в кодовых комбинациях A2 и B2:

Четвертый шаг сводится к "разверткам" A3 и B3:

A3 = 0 0 0 0 0 0 0 1 0 ® 0 0 0 0 0 0 0 0 1 = A4,
B3 = 0 0 0 0 0 1 0 0 1 ® 0 0 0 0 0 0 1 1 1 = B4.

Пятый шаг есть "поглощение":

Вычитание закончено. После приведения "фибоначчиевого" представления B4 к "минимальной" форме получаем:

B5 = 0 0 0 0 0 1 0 0 0.

Результат вычитания находится в нижнем регистре B. Это означает, что знак результата отрицательный, то есть разность

R = (A - B) = - 0 0 0 0 0 1 0 0 0.

Заметим, что арифметические операции "умножение" и "деление" сводятся к арифметическим операциям "сложения" и "вычитания". Это означает, что "фибоначчиевое" умножения и деление также сводятся к "базовым микрооперациям".

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

Но какое преимущество будет иметь такой Фибоначчи-процессор в сравнении с классическими компьютерами, основанными на классической "двоичной" системе счисления? Чтобы ответить на этот вопрос, мы должны продемонстрировать возможность контроля ошибок в процессорах, которые могут возникнуть в процессоре под влиянием различных внешних и внутренних факторов. Следуйте за нами!