УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИЗЪЮНКТИВНОГО ЛОГИЧЕСКОГО ОПРЕДЕЛЕНИЯ Российский патент 1996 года по МПК G06F7/00 G06F17/00 

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

Известны устройства для вычисления дизъюнктивного логического определителя (ДЛО), используемые как для мультипрограммирования вычислительных средств, так и составления расписаний в широких областях народного хозяйства (транспорте, производственно-технологических процессах, учебном процессе и т.д.).

Устройство содержит оперативную память, процессор и внешние устройства для ввода и вывода информации. Вычисление ДЛО происходит по программе, составленной на основании алгоритма.

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

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

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

Целью изобретения является расширение области применения устройства путем его упрощения.

Это достигается тем, что в устройство, содержащее блок синхронизации, накапливающий сумматор, блок ввода, состоящий из m,n-разрядных параллельных регистров (где m число строк дизъюнктивного логического определителя, n-разрядность вводимых чисел), m групп элементов И по n элементов И в каждой и n элементов ИЛИ, (m-1) блоков вычисления дизъюнкции и блок вывода, выход которого соединен с выходом устройства, m информационных входов которого соединены соответственно с информационными выходами m параллельных регистров блока ввода, каждый из блоков вычисления дизъюнкции состоит из узла вычисления максимального числа и двух сумматоров, причем первый и второй выходы блока синхронизации соединены соответственно с объединенными входами синхронизации и объединенными входами установки в нуль m параллельных регистров блока ввода, выход i-го разряда j-го регистра блока ввода (где i 1,n, j 1,m) соединен с первым входом i-го элемента И j-й группы блока ввода, выход которого соединен с соответствующим входом -го элемента ИЛИ блока ввода, j-й выход блока синхронизации, начиная с третьего выхода, соединен с объединенными вторыми входами элементов И j-й группы, выходы всех элементов ИЛИ блока ввода соединены с информационным входом накапливающего сумматора и первым и вторым информационными входами каждого из (m-1) блоков вычисления дизъюнкции, выход накапливающего сумматора соединен с третьим информационным входом первого блока вычисления дизъюнкции, выход l-го блока вычисления дизъюнкции (l 1,m-2) соединен с третьим информационным входом (l+1)-го блока вычисления дизъюнкции, выход (m-1)-го блока вычисления дизъюнкции соединен с информационным входом блока вывода, (m+3)-й выход блока синхронизации соединен с объединенными входами установки в нуль первых сумматоров (m-1) блоков вычисления дизъюнкции, входы разрешения ввода и вывода данных первого сумматора k-го блока вычисления дизъюнкции (k 1,m-1) соединены соответственно с (k+m+3)-м выходом и (k+2m+2)-м выходом блока синхронизации, (3m+2)-й выход которого соединен с объединенными входами установки в нуль вторых сумматоров (m-1) блоков вычисления дизъюнкций.

Входы разрешения ввода и вывода данных второго сумматора k-го блока вычисления дизъюнкции соединены соответственно с (k+3m+2)-м выходом и (k+4m+1)-м выходом блока синхронизации, первый и второй управляющие входы узла вычисления максимального числа k-го блока вычисления дизъюнкции соединены соответственно с (k+5m)-м выходом и (k+6m-1)-м выходом блока синхронизации, (7m-1)-й выход которого соединен с третьим управляющим входом узла вычисления максимального числа каждого блока вычисления дизъюнкции, (7m)-й, (7m+1)-й и (7m+2)-й выходы блока синхронизации соединены соответственно с входами установки в нуль, разрешения ввода и вывода данных накапливающего сумматора. Входы запуска, синхронизации и установки в нуль блока синхронизации соединены соответственно с входом запуска, синхронизации и установки в нуль устройства, выход запроса данных которого соединен с (7m+3)-м выходом блока синхронизации, (7m+4)-й выход которого соединен с входом синхронизации блока вывода. Блок синхронизации содержит задающий генератор, двоичный счетчик, триггер, элемент И, три элемента ИЛИ, группу элементов И и элемент памяти, (7m+5)-й выход которого соединен с первыми входами второго и третьего элементов ИЛИ, (7m+4)-й выход элемента памяти соединен с (7m+4)-м выходом блока, (7m+3)-й выход которого соединен с (7m+3)-м выходом элемента памяти и вторым входом второго элемента ИЛИ, первый вход которого соединен с третьим входом блока и вторым входом третьего элемента ИЛИ, а выход с входом установки в нуль триггера, информационный вход которого соединен с выходом первого элемента ИЛИ, первый и второй входы которого соединены соответственно с первым и вторым входами блока, прямой выход триггера соединен с первым входом элемента И и первыми входами элементов И группы, вторые входы которых соединены с соответствующими выходами двоичного счетчика, вход установки в нуль и информационный вход которого соединены соответственно с выходами третьего элемента ИЛИ и элемента И, второй вход которого соединен с выходом задающего генератора, выходы элементов И группы соединены с соответствующими адресными входами элемента памяти, выходы с первого по (7m+2)-й которого соединен соответственно с выходами с первого по (7m+2)-й блока.

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

На фиг.1 представлена программа вычисления ДЛО; на фиг.2 блок-схема устройства; на фиг. 3 схема блока ввода; на фиг.4 схема блока синхронизации (БС); на фиг.5 блок-схема блока вычисления дизъюнкции; на фиг.6 схема узла вычисления максимального числа (УВМЧ); на фиг.7 фрагмент схемы устройства для вычисления ДЛО с числом строк m 3; на фиг.8 временные диаграммы работы устройства для случая m 3.

В табл.1 приведено назначение входных и выходных линий БС (для дополнения фиг. 2 и фиг. 7) для m 3; в табл.2 выполнение функций устройством для каждого тактового импульса (см. также фиг.2,7,8), когда m 3.

Нумерация входов и выходов элементов устройства (фиг.2 и фиг.7) приведена для m 3.

Устройство (см. фиг.2) содержит блок ввода 1 (фиг.3), БС 2 (фиг.4), накапливающий сумматор 3, блоки вычисления дизъюнкции 4 (фиг.5,6), блок вывода 5. В качестве параллельных регистров блока ввода и схемы выбора максимального числа могут быть использованы микросхемы К155ИР1. Сумматор является накапливающим. Элемент памяти БС может быть реализован, например, на микросхемах К155РЕ3.

Двоичный счетчик БС может быть реализован на микросхемах К155ИЕ7, компаратор на микросхемах К555СП1. В качестве задающего генератора БС может быть использована микросхема К531ГГ1. Элементы И, ИЛИ и триггеры могут быть также реализованы на микросхемах, например, серии К155.

Устройство работает следующим образом.

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

, где m количество чисел в столбце (строк ДЛО), а l текущий номер столбца (l ). После ввода всех r столбцов получаем искомый результат Avmr ДЛО.

Для удобства понимания работы устройства (фиг.2) предлагается рассмотреть его для случая, когда число строк ДЛО равно трем (m 3).

Перед началом работы устройства на вход 19 (см. фиг.2,4,8) подают сигнал для установки триггера и двоичного счетчика БС в нулевое состояние. Затем на вход 16 подают сигнал для начального запуска БС. Первый тактовый импульс задающего генератора задает считывание информации из первой многоразрядной ячейки элемента памяти. В этой ячейке, как и в других, предварительно записанная информация позволит получить на соответствующих выходных линиях элемента памяти сигналы (см. фиг.8) (перечень выполняемых функций в зависимости от номера тактового импульса см. в табл.2). После ввода последнего r-го столбца ДЛО и выполнения над ним соответствующих операций, например, аналогичных с 10-го по 16-й тактовый импульс (см. фиг.8 и табл.2), из элемента памяти поступает сигнал на 17, 24 (см. фиг.2,7) выходные линии, а также на первые входы третьего и второго элементов ИЛИ БС (см. фиг.4). В результате это искомое значение A3rv

из сумматора 8₁ второго блока вычисления дизъюнкции 4 передается в блок вывода 5 (например, на параллельный регистр), триггер и счетчик БС устанавливаются в нуль, работа прекращается.

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

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

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

Изобретение относится к вычислительной технике и преимущественно может быть использовано для составления расписаний работы конвейерных систем. Цель изобретения состоит в расширении области применения устройства. Устройство содержит блоки ввода и вывода, соответственно входы и выходы которых соединены с входной и выходной шинами устройства, сумматор, блоки вычисления дизъюнкции, число которых на единицу меньше числа строк логического определителя и генератора синхронизирующих импульсов. 1 з. п. ф-лы, 8 ил., 2 табл.

1. Устройство для вычисления дизъюнктивного логического определителя, содержащее блок синхронизации, накапливающий сумматор, блок ввода, состоящий из m n-разрядных параллельных регистров (где m число строк дизъюнктивного логического определителя, n-разрядность вводимых чисел), m групп элементов И по n элементов И в каждой и n элементов ИЛИ, m-1 блоков вычисления дизъюнкции, блок вывода, выход которого соединен с выходом устройства, m информационных входов которого соединены соответственно с информационными входами m параллельных регистров блока ввода, отличающееся тем, что каждый из блоков вычисления дизъюнкции состоит из узла вычисления максимального числа и двух сумматоров, причем первый и второй выходы блока синхронизации соединены соответственно с объединенными входами синхронизации и объединенными входами установки в "0" m параллельных регистров блока ввода, выход i-го разряда j-го регистра блока ввода (где i=1,n, j=1,m) соединен с первым входом i-го элемента И j-й группы блока ввода, выход которого соединен с соответствующим входом j-го элемента ИЛИ блока ввода, j-й выход блока синхронизации, начиная с третьего выхода, соединен с объединенными вторыми входами элементов И j-й группы, выходы всех элементов ИЛИ блока ввода соединены с информационным входом накапливающего сумматора и первым и вторым информационными входами каждого из m-1 блоков вычисления дизъюнкции, выход накапливающего сумматора соединен с третьим информационным входом первого блока вычисления дизъюнкции, выход l-го блока вычисления дизъюнкции (l=1,m-2) с третьим информационным входом (l+1)-го блока вычисления дизъюнкции, выход (m-1)-го блока вычисления дизъюнкции с информационным входом блока вывода, (m+3)-й выход блока синхронизации с объединенными входами установки в "0" первых сумматоров m-1 блоков вычисления дизъюнкции, входы разрешения ввода и вывода данных первого сумматора k-го блока вычисления дизъюнкции (k=1,m-1) соединены соответственно с (k+m+3)-м и (k+2m+2)-м выходами блока синхронизации, (3m+2)-й выход которого соединен с объединенными входами установки в "0" вторых сумматоров m-1 блока вычисления дизъюнкции, входы разрешения ввода и вывода данных второго сумматора k-го блока вычисления дизъюнкции соединены соответственно с (k+3m+2)-м и (k+4m+1)-м выходами блока синхронизации, первый и второй управляющие входы узла вычисления максимального числа k-го блока вычисления дизъюнкции соединены соответственно с (k+5m)-м и (k+6m-1)-м выходами блока синхронизации, (7м-1)-й выход которого соединен с третьим управляющим входом узла вычисления максимального числа каждого блока вычисления дизъюнкции, 7m-й, (7m+1)-й и (7m+2)-й выходы блока синхронизации соединены соответственно с входами установки в "0", разрешения ввода и вывода данных накапливающего сумматора, входы запуска, синхронизации и установки в "0" блока синхронизации соединены соответственно с одноименными входами устройства, выход запроса данных которого соединен с (7m+3)-м выходом блока синхронизации, (7m+4)-й выход которого соединен с входом синхронизации блока вывода. 2. Устройство по п.1, отличающееся тем, что блок синхронизации содержит задающий генератор, двоичный счетчик, триггер, элемент И, три элемента ИЛИ, группу элементов И и элемент памяти, (7m+5)-й выход которого соединен с первыми входами второго и третьего элементов ИЛИ, (7m+4)-й выход элемента памяти с (7m+4)-м выходом блока, (7m+3)-й выход которого соединен с (7m+3)-м выходом элемента памяти и вторым входом второго элемента ИЛИ, первый вход которого соединен с третьим входом блока и вторым входом третьего элемента ИЛИ, а выход с входом установки в "0" триггера, информационный вход которого соединен с выходом первого элемента ИЛИ, первый и второй входы которого соединены соответственно с первым и вторым входами блока, прямой выход триггера соединен с первым входом элемента И и первыми входами элементов И группы, вторые входы которых соединены с соответствующими выходами двоичного счетчика, вход установки в "0" и информационный вход которого соединены соответственно с выходами третьего элемента ИЛИ и элемента И, второй вход которого соединен с выходом задающего генератора, выходы элементов И группы соединены с соответствующими адресными входами элемента памяти, выходы с первого по (7m+2)-й которого соединены соответственно с выходами с первого по (7m+2)-й блока.