Устройство реализации кубической операции "Дополнение" Российский патент 2023 года по МПК G06F7/57 G06F7/38 

Изобретение относится к вычислительной технике и может быть использовано при создании специализированной ЭВМ (специализированного сопроцессора для универсальной ЭВМ), реализующих операции кубического исчисления, используемые в алгоритмах моделирования, диагностирования и синтеза дискретных устройств [см. Миллер Р. Теория переключательных схем. - М.: Наука, 1970. Т.1; Проектирование цифровых вычислительных машин. Под ред. С.А. Майорова. Учебн. пособ. для вузов. М.: Высшая школа, 1972; Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - Л.: Энергия, Ленингр. отд., 1979. - 232 с.; Луцик Ю.А., Лукьянова И.В. Арифметические и логические основы вычислительной техники: Учеб. пособие - Минск: БГУИР, 2014. - 174 с.].

Известно устройство («Ячейка одномерной однородной вычислительной среды») реализации кубической операции d-пересечения [А.с. SU 1173406 А, авторы: Альбеков А.Ш., Герасимов Е.Р., Чикалов А.Н., 1985]. Устройство содержит логические элементы И, ИЛИ, ИЛИ-НЕ, ЗАПРЕТ, восемь входов и семь выходов и реализует таблицу истинности кубической операции d-пересечения [Чжен Г., Мэннинг Е., Метц Г. Диагностика отказов цифровых вычислительных машин. - М.: Мир, 1972]. Недостатком данного устройства является реализация всего одной кубической операции d-пересечения n-мерных кубов.

Известно устройство реализации кубической операции х-произведение [А.с. SU 1656522 А1, авторы: Альбеков А.Ш., Герасимов Е.Р., 1991]. Устройство содержит n вычислительных ячеек, каждая из которых содержит элементы И, ИЛИ-НЕ, ИЛИ, по четыре входа и по три выхода и один решающий узел, содержащий 3n входов, 3n выходов и элементы ИЛИ, ЗАПРЕТ, мажоритарный элемент и реализует таблицу истинности кубической операции х-произведение [Миллер Р. Теория переключательных схем. - М.: Наука, 1970. Т. 1; Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - Л.: Энергия, Ленингр. отд., 1979. - 232 с.]. Недостатком данного устройства также является реализация всего одной кубической операции х-произведение n-мерных кубов.

Наиболее близким (прототипом) к патентуемому изобретению является устройство реализации кубической операции И [решение о выдаче патента от 19.04.2022 г. по заявке №2021120275, автор: Альбеков А.Ш., 2022]. Устройство является комбинационным, с жесткой логикой, содержит η вычислительных ячеек, каждая из которых содержит элементы И, ИЛИ, по четыре входа, по два выхода и реализует таблицу истинности кубической операции И n-мерных кубов [studall.org/all3-26567.html].

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

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

Техническим результатом изобретения является возможность схемного выполнения заявляемым устройством кубической операции «Дополнение» над n - мерными кубами. N - мерный куб К[1:n] представляет собой вектор, содержащий η координат (компонент), каждая из которых принимает значение на троичном множестве {0, 1, X}.

Операция «Дополнение» осуществляется над n-разрядным кубом К₁[1:n] в соответствии с троичной таблицей истинности табл. 1 [см. studall.org/all3-26567.html; studfile.net/preview/7014248/page:5].

Результатом выполнения операции является n-разрядный куб К₂[1:n], координаты которого также определены на троичном множестве {0, 1, X}.

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

С целью схемного представления троичных значений координат кубов предлагается двухпозиционное представление b[i] и x[i] (табл. 2) координат кубов К_j[1:n], j=1, 2, где b[i] - позиция, кодирующая бинарные значения 0 и 1 из табл. 1; x[i] - позиция, кодирующая значение X из табл. 1.

Поскольку значения координат куба-результата К₂[1:n] независимы друг от друга и полностью определяются таблицей истинности (табл. 1), устройство содержит n независимых вычислительных ячеек, каждая из которых реализует табл. 1 с учетом принятой двоичной кодировки (табл. 2) значений координат, и не содержит решающего узла (блока), имеющегося в аналогах. Извлечение из таблиц 1 и 2 аналитических формул логических функций, реализуемых ячейками устройства, дает следующую систему уравнений, записанных в ДНФ на языке микроопераций (регистровых передач):

- кодовые значения бинарных (0, 1) координат кубов К_{1, 2}[1:n], - кодовые значения Х-координат кубов К_{1, 2}[1:n], i (i=1, 2, …, n) - номер кубической координаты.

На фиг. 1 представлена структурная схема устройства реализации кубической операции «Дополнение», на фиг. 2 - функциональная схема вычислительной ячейки 1 устройства. Каждая вычислительная ячейка устройства 2, 3, как и ячейка 1, реализует систему логических функций (1) и идентична ячейке 1.

Устройство (фиг. 1) содержит n вычислительных ячеек 1, 2, …, 3; 2×n входов, соответствующих координатам куба К₁[1:n]; и 2×n выходов, соответствующих координатам куба-результата К₂[1:n].

Вычислительная ячейка 1 устройства (фиг. 2), имеет два входа, помеченные как b₁[1], x₁[1]; два выхода, помеченные как b₂[1], х₂[1] и содержит инверторы НЕ 4, 5, и двухвходовые элементы И 6, 7. Причем, первый вход ячейки соединен с входом элемента НЕ 4, а второй вход ячейки соединен с входом элемента НЕ 5 и вторым входом элемента И 7. Выход элемента НЕ 4 соединен с первыми входами элементов И 6 и 7. Выход элемента НЕ 5 соединен с вторым входом элемента И 6. Выход элемента И 6 является первым выходом вычислительной ячейки, помеченным как b₂[1], а выход элемента И 7 является вторым выходом вычислительной ячейки, помеченным как х₂[1].

Устройство работает следующим образом. На первые и вторые входы вычислительных ячеек 1, 2, …, 3 подается код куба К₁[1:n]. На выходах вычислительных ячеек вырабатывается код куба К₂[1:n], являющийся результатом кубической операции «Дополнение». Поскольку ячейки устройства являются комбинационными автоматами, то их работа полностью определена таблицей истинности (табл. 1) с учетом принятого двоичного кодирования (табл. 2) координат {0, 1, X}.

Повышение производительности вычислительного процесса с применением операции кубического «Дополнения», реализуемой заявляемым устройством, из-за жесткости законов функционирования аналогов, доказуемо в сравнении с универсальным программируемым вычислительным устройством последовательной архитектуры. По сравнению с универсальным вычислительным устройством неймановской архитектуры (универсальным процессором) повышение производительности достигается тем, что заявляемое устройство реализует операцию, при условии выставления кода куба К₁[1:n] на его входах, за два машинных такта (в синхронном режиме работы), в то время, как универсальное устройство, с этой же целью, должно выполнить программный код поразрядной обработки кубов, состоящий из циклической последовательности операторов языка высокого уровня. Поскольку кубическая операция «Дополнение» определена на 3-х входных наборах (см. табл. 1), то циклический блок обработки таблицы 1 (напр., на С++) содержит 3 оператора if(), покрывающих все наборы таблицы истинности:

Очевидно, что один оператор if() требует для своей реализации не менее 2-х машинных тактов, а обработка одного разряда кубов К₁[1:n] и К₂[1:n] требует, в среднем, выполнения 3/2=1,5 операторов if(). Следовательно, обработка всех разрядов кубов К₁[1:n] и К₂[1:n] потребует не менее 2×1,5×n машинных тактов, где n - разрядность обрабатываемых кубов. То есть, выигрыш В по времени реализации кубического «Дополнения» заявляемым устройством составит порядка 3×n/2 раз, где n - длина (размерность) обрабатываемых кубов. Так, для n=32, выигрыш составит В≥48 раз, а для n=64, выигрыш составит В≥96 раз.

Изобретение относится к области вычислительной техники, реализующей операции кубического исчисления. Техническим результатом изобретения является реализация схемного выполнения заявляемым устройством кубической операции «Дополнение» над n-мерным кубом. Технический результат достигается за счет того, что устройство содержит n однотипных вычислительных ячеек, каждая i-тая вычислительная ячейка имеет два входа, два выхода и содержит два элемента НЕ и два элемента И, за счет специального соединения входов и выходов элементов вычислительных ячеек, реализуется троичная таблица истинности кубической операции «Дополнение». 2 ил., 2 табл.

Устройство реализации кубической операции «Дополнение», содержащее n вычислительных ячеек, где n – размерность обрабатываемых устройством кубов, отличающееся тем, что каждая из n вычислительных ячеек имеет два входа и два выхода, а все устройство имеет, соответственно, 2×n входов и 2×n выходов, причем каждая i-тая вычислительная ячейка содержит два элемента НЕ и два элемента И, при этом первый вход ячейки соединен с входом первого элемента НЕ, выход которого соединен с первыми входами первого и второго элементов И; второй вход ячейки соединен с входом второго элемента НЕ и вторым входом второго элемента И, выход которого является вторым выходом i-той вычислительной ячейки; выход второго элемента НЕ соединен со вторым входом первого элемента И, выход которого является первым выходом i-той вычислительной ячейки.