Устройство реализации кубической операции ИЛИ
APPARATUS FOR IMPLEMENTING A CUBIC OPERATION OR

Изобретение относится к вычислительной технике и может быть использовано при создании специализированной ЭВМ (специализированного сопроцессора для универсальной ЭВМ), реализующих операции кубического исчисления, используемые в алгоритмах Рота синтеза дискретных устройств (алгоритм извлечения) и синтеза тестов поиска неисправностей (D-алгоритм) схем автоматики и вычислительной техники [см. Миллер Р. Теория переключательных схем. - М.: Наука, 1970. Т. 1; Чжен Г., Мэннинг Е., Метц Г. Диагностика отказов цифровых вычислительных машин. - М.: Мир, 1972; Проектирование цифровых вычислительных машин. Под ред. С.А. Майорова. Учебн. пособ. для вузов. М.: Высшая школа, 1972; Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - Л.: Энергия, Ленингр. отд., 1979. - 232 с.; Луцик Ю.А., Лукьянова И.В. Арифметические и логические основы вычислительной техники: Учеб. пособие - Минск: БГУИР, 2004. - 121 с.].
Известно устройство («Ячейка одномерной однородной вычислительной среды») реализации операции d-пересечения [А.с. SU 1173406 А, авторы: Альбеков А.Ш., Герасимов Е.Р., Чикалов А.Н., 1985]. Устройство содержит логические элементы И, ИЛИ, ИЛИ-НЕ, ЗАПРЕТ, восемь входов и семь выходов и реализует таблицу истинности кубической операции d-пересечения [Чжен Г., Мэннинг Е., Метц Г. Диагностика отказов цифровых вычислительных машин. - М.: Мир, 1972]. Недостатком данного устройства является реализация всего одной кубической операции d-пересечения n-мерных кубов.
Известно устройство реализации кубической операции х-произведение [А.с. SU 1656522 А1, авторы: Альбеков А.Ш., Герасимов Е.Р., 1991]. Устройство содержит n вычислительных ячеек, каждая из которых содержит элементы И, ИЛИ-НЕ, ИЛИ, по четыре входа и по три выхода и один решающий узел, содержащий 3n входов, 3n выходов и элементы ИЛИ, ЗАПРЕТ, мажоритарный элемент и реализует таблицу истинности кубической операции х-произведение [Миллер Р. Теория переключательных схем. - М.: Наука, 1970. Т. 1; Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - Л.: Энергия, Ленингр. отд., 1979. - 232 с.]. Недостатком данного устройства также является реализация всего одной кубической операции х-произведение n-мерных кубов.
Наиболее близким {прототипом) к патентуемому изобретению является устройство для обработки логической информации, реализующее кубическую операцию склеивания n-мерных кубов [Патент RU 2027218 С1, авторы: Альбеков А.Ш., Герасимов Е.Р., Хализев В.Н., 1995]. Устройство является комбинационным, с жесткой логикой, содержит n вычислительных ячеек, каждая из которых содержит элементы И, ИЛИ-НЕ, ИЛИ, по четыре входа и по три выхода и один решающий блок, содержащий 3n входов, 3n выходов и элементы И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ и реализует таблицу истинности кубической операции склеивания n-мерных кубов [Миллер Р. Теория переключательных схем. - М.: Наука, 1970. Т. 1; Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - Л.: Энергия, Ленингр. отд., 1979. - 232 с.]. Причина, которая не позволяет достичь с помощью аналога того технического результата, который обеспечивается заявляемым изобретением, заключается в невозможности реализации прототипом кубической операции ИЛИ (OR, ∨) из-за жесткости закона его функционирования.
Целью изобретения является расширение функциональных возможностей и производительности специализированной вычислительной техники при реализации ею алгоритмов синтеза дискретных устройств и тестов поиска неисправностей схем автоматики и вычислительной техники. Цель достигается за счет аппаратной реализации кубической операции ИЛИ (OR, ∨).
Техническим результатом изобретения является возможность схемного выполнения заявляемым устройством кубической операции логического сложения ИЛИ (OR, ∨) над двумя n-мерными кубами, n-мерный куб К[1:n] представляет собой вектор, содержащий n координат (компонент), каждая из которых принимает значение на троичном множестве {0, 1, X}.
1
2
Операция «кубическое ИЛИ» осуществляется над двумя n-разрядными кубами К[1:n] и К[1:n] в соответствии с таблицей истинности табл. 1 [см. studfile.net/preview/7014248/page:5; studall.org/all3-26567.html; dl.nure.ua/plug-infile.php/534/mod_resource/content/2/content/example1.html].
3
Результатом выполнения операции является n-разрядный куб К[1:n], координаты которого также определены на троичном множестве {0, 1, X}.
Для практической реализации заявляемого устройства на серийной двоичной элементной базе необходимо осуществить переход от троичной системы счисления к двоичной системе.
i
С целью схемного представления троичных значений координат кубов предлагается двухпозиционное представление b[i] и x[i] (табл. 2) координат кубов К[1:n], i=1, 2, 3, где b[i] - позиция, кодирующая бинарные значения 0 и 1 из табл. 1; x[i] - позиция, кодирующая значение X из табл. 1.
3
Поскольку значения координат куба-результата К[1:n] независимы друг от друга и полностью определяются таблицей истинности (табл. 1), устройство содержит n независимых вычислительных ячеек, каждая из которых реализует табл. 1 с учетом принятой двоичной кодировки (табл. 2) значений координат, и не содержит решающего узла (блока), имеющегося в аналогах. Извлечение из таблиц 1 и 2 аналитических формул логических функций, реализуемых ячейками устройства, дает следующую систему уравнений:
1,2,3
1,2,3
где  - кодовые значения бинарных (0, 1) координат кубов К[1:n],  - кодовые значения Х-координат кубов К[1:n], i (i=1, 2, …n) - номер кубической координаты.
На фиг. 1 представлена структурная схема устройства реализации кубической операции ИЛИ, на фиг. 2 - функциональная схема вычислительной ячейки 1 устройства. Каждая вычислительная ячейка устройства 2, …, 3, как и ячейка 1, реализует систему логических функций (1) и идентична ячейке 1.
1
2
3
Устройство (фиг. 1) содержит n вычислительных ячеек 1, 2, …, 3; 2×n входов, соответствующих координатам куба К[1:n]; 2×n входов, соответствующих координатам куба К[1:n]; и 2×n выходов, соответствующих координатам куба-результата К[1:n].
Вычислительная ячейка 1 устройства (фиг. 2), имеет четыре входа, два выхода и содержит инверторы НЕ 4, 5, 6, 7, четырехвходовые элементы И 8, 9, 10, 11, 12, 14, 15, 16, пятивходовый элемент ИЛИ 13 и трехвходовый элемент ИЛИ 17. Причем, первый вход ячейки соединен с входом элемента НЕ 4, первым входом элемента И 9, первым входом элемента И 10, первым входом элемента И 11. Второй вход ячейки соединен с входом элемента НЕ 5, третьим входом элемента И 12, третьим входом элемента И 15, и третьим входом элемента И 16. Третий вход ячейки соединен с входом элемента НЕ 6, вторым входом элемента И 8, вторым входом элемента И 10, вторым входом элемента И 12. Четвертый вход ячейки соединен с входом элемента НЕ 7, четвертым входом элемента И 11, четвертым входом элемента И 14, четвертым входом элемента И 16. Выход элемента НЕ 4 соединен с первым входом элемента И 8, первым входом элемента И 12, первым входом элемента И 14, первым входом элемента И 15, первым входом элемента И 16. Выход элемента НЕ 5 соединен с третьим входом элемента И 8, третьим входом элемента И 9, третьим входом элемента И 10, третьим входом элемента И 11, третьим входом элемента И 14. Выход элемента НЕ 6 соединен с вторым входом элемента И 9, вторым входом элемента И 11, вторым входом элемента И 14, вторым входом элемента И 15, вторым входом элемента И 16. Выход элемента НЕ 7 соединен с четвертым входом элемента И 8, четвертым входом элемента И 9, четвертым входом элемента И 10, четвертым входом элемента И 12, четвертым входом элемента И 15. Выход элемента И 8 соединен с первым входом элемента ИЛИ 13, выход элемента И 9 соединен с вторым входом элемента ИЛИ 13, выход элемента И 10 соединен с третьим входом элемента ИЛИ 13, выход элемента И 11 соединен с четвертым входом элемента ИЛИ 13, выход элемента И 12 соединен с пятым входом элемента ИЛИ 13, выход которого является первым выходом вычислительной ячейки. Выход элемента И 14 соединен с первым входом элемента ИЛИ 17, выход элемента И 15 соединен с вторым входом элемента ИЛИ 17, выход элемента И 16 соединен с третьим входом элемента ИЛИ 17, выход которого является вторым выходом вычислительной ячейки.
1
2
3
1
2
Устройство работает следующим образом. На первые и вторые входы вычислительных ячеек 1, 2, …, 3 подается код куба К[1:n], на третьи и четвертые входы - код куба К[1:n]. На выходах вычислительных ячеек вырабатывается код куба К[1:n]=К[1:n]∨К[1:n], являющийся результатом кубической операции ИЛИ. Поскольку ячейки устройства являются комбинационными автоматами, то их работа полностью определена таблицей истинности (табл. 1) с учетом принятого двоичного кодирования (табл. 2) координат {0, 1, X}.
1
2
Повышение производительности вычислительного процесса с применением операции кубического ИЛИ, реализуемой заявляемым устройством, из-за за жесткости законов функционирования аналогов, не позволяющей реализовывать кубическое ИЛИ аналогами, доказуемо в сравнении с универсальным программируемым вычислительным устройством последовательной архитектуры. По сравнению с универсальным вычислительным устройством неймановской архитектуры (универсальным процессором) повышение производительности достигается тем, что заявляемое устройство реализует операцию, при условии выставления кодов кубов К[1:n] и К[1:n] на его входах, за три машинных такта, в то время, как универсальное устройство, с этой же целью, должно выполнить программный код поразрядной обработки кубов, состоящий из циклической последовательности операторов языка высокого уровня. Поскольку операция «кубическое ИЛИ» определена на 9-ти входных наборах (см. табл. 1), то циклический блок обработки таблицы 1 (напр., на С++) содержит 9 операторов if(), покрывающих все наборы таблицы:
1
2
3
1
2
3
Очевидно, что один оператор if() требует для своей реализации не менее 4-х машинных тактов, а обработка одного разряда кубов К[1:n], К[1:n] и К[1:n] требует, в среднем, выполнения 9/2=4,5 операторов if(). Следовательно, обработка всех разрядов кубов К[1:n], К[1:n] и К[1:n] потребует не менее 4×4,5×n машинных тактов, где n - разрядность обрабатываемых кубов. То есть, выигрыш В по времени реализации кубического ИЛИ заявляемым устройством составит порядка 18×n/3 раз, где n - длина (размерность) обрабатываемых кубов. Так, для n=32, выигрыш составит В≥192 раз, а для n=64, выигрыш составит В≥384 раз.