Устройство реализации кубической операции И Российский патент 2022 года по МПК G06F7/552 

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

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

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

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

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

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

Операция «кубическое И» осуществляется над двумя n-разрядными кубами К₁[1:n] и К₂[1:n] в соответствии с таблицей истинности табл. 1 [см. stud-file.net/preview/7014248/page:5; studall.org/all3-26567.html; dl.nure.ua/plugin-file.php/534/mod_resource/content/2/ content/example 1.html].

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

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

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

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

где b_k - кодовые значения бинарных (0, 1) координат кубов К[1:n], x_k - кодовые значения Х-координат кубов К[1:n].

На фиг. 1 представлена структурная схема устройства реализации кубической операции И, на фиг. 2 - функциональная схема i-той вычислительной ячейки Я[i] устройства. Каждая i-тая вычислительная ячейка реализует систему логических функций (1). Совокупность значений, вырабатываемых на всех 2×n структурных выходах всех n ячеек образует значение куба К₃[1:n] в бинарном представлении.

Устройство (фиг. 1) содержит n вычислительных ячеек Я[i]. Каждая i-тая вычислительная ячейка (фиг. 2) содержит двухвходовые элементы И 1, 2, 3, 4 и трехвходовый элемент ИЛИ 5. Причем, вход 1 ячейки соединен с первыми входами элементов И 1 и 2; вход 2 ячейки соединен со вторым входом элемента И 3 и первым входом элемента И 4; вход 3 ячейки соединен со вторым входом элемента И 1 и первым входом элемента И 3; вход 4 ячейки соединен со вторым входом элемента И 2 и вторым входом элемента И 4. Выход элемента И 2 соединен с первым входом элемента ИЛИ 5; выход элемента И 3 соединен со вторым входом элемента ИЛИ 5; выход элемента И 4 соединен с третьим входом элемента ИЛИ 5. Выход элемента И 1 является первым выходом 5 вычислительной ячейки, а выход элемента ИЛИ 5 является вторым выходом 6 вычислительной ячейки.

Устройство работает следующим образом. На первый и второй входы 1 и 2 каждой i-той вычислительной ячейки подается код куба K₁[1:n], на третий и четвертый входы 3 и 4 - код куба К₂[1:n]. На выходах 5 и 6 вычислительных ячеек вырабатывается код куба К₃[1:n]=К₁[1:n] & К₂[1:n], являющийся результатом кубической операции И. Поскольку ячейки устройства являются комбинационными автоматами, то их работа полностью определена таблицей истинности (табл. 1) с учетом принятого двоичного кодирования (табл. 2) координат {0,1,Х}.

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

Очевидно, что один оператор 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 раз, где n - длина (размерность) обрабатываемых кубов. Так, для n=32, выигрыш составит В ≥ 576 раз, а для n=64, выигрыш составит В ≥ 1152 раз.

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

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