Устройство для вычисления логических определителей

 

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

Изобретение относится к вычислительной технике и преимущественно может найти применение при автоматизированном составлении расписаний работы детерминированных систем конвейерного типа, широко используемых в настоящее время на производстве, всех видах транспорта, учебном процессе, военной области, научных исследованиях, космической деятельности (например, при обработке телеметрической информации ракет-носителей, космических аппаратов на конвейерных вычислительных средствах) и в других областях, где технологические процессы представляют собой конвейерные системы. Конвейерные системы, как правило, содержат m≥2 процессоров (станков и т.д.).

В настоящее время известны устройства и методы [1, 2, 3] для организации решения самых различных задач на конвейерных системах в мультипрограммном режиме. Производительность последних напрямую зависит от близости полученных расписаний (порядка загрузки объектов в систему) к оптимальным. Для исследования работы конвейерных систем применяют теорию логических определителей [1]. В частности, вычисляют дизъюнктивный логический определитель А∨ (ДЛО), суммирующий логический определитель A⁺ (СЛО) и конъюнктивный логический определитель А∧ (КЛО).

Известны устройства для вычисления перечисленных логических определителей (см. например [4], рис.1.2 и [5], рис.1.1). Эти устройства содержат оперативную память, процессор и внешние устройства для ввода и вывода информации. Вычисление логических определителей (ЛО) происходит по программе, составленной на основании алгоритмов [1].

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

Известно также устройство [6], в основе работы которого лежит вычисление ДЛО A∨, содержащее блоки ввода и вывода, два блока памяти, генератор перестановок, блок вычисления функции A∧ и блок выбора наименьшего результата. Данное устройство позволяет вычислять только ДЛО A∨ и не позволяет вычислять СЛО и КЛО.

Наиболее близким к заявляемому изобретению по сущности решаемой задачи является УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИЗЪЮНКТИВНОГО ЛОГИЧЕСКОГО ОПРЕДЕЛИТЕЛЯ [7] (см. фиг.1), которое без дополнительных существенных признаков не может самостоятельно решать задачу вычисления СЛО и КЛО.

Целью изобретения является расширение функциональных возможностей устройства, позволяющего вычислять ДЛО, КЛО и СЛО.

Указанный технический результат достигается тем, что в устройство для вычисления ЛО, состоящее из блока ввода, блока синхронизации, накапливающего сумматора, (m-1) блоков вычисления дизъюнкции (где m - число строк логического определителя), блока вывода, состоящего из параллельного регистра, информационный выход которого соединен с аналогичным выходом блока вывода и с первым информационным выходом устройства - ДИЗЪЮНКТИВНЫЙ ЛОГИЧЕСКИЙ ОПРЕДЕЛИТЕЛЬ, а информационный вход - с первым информационным входом блока вывода и с информационным выходом (m-1)-го блока вычисления дизъюнкции, первые два информационных входа которого соединены между собой и с аналогичными входами остальных блоков вычисления дизъюнкции, информационным входом накапливающего сумматора и информационным выходом блока ввода, m информационных входов которого соединены соответственно с m информационными входами устройства, а (m+2) управляющих его входа соединены соответственно с первыми (m+2) выходами блока синхронизации, входы ЗАПУСКА, СИНХРОНИЗАЦИИ и УСТАНОВКИ В НУЛЬ которого соединены соответственно с одноименными входами устройства, а (m+3)-й, (m+4)-й и (m+5)-й выходы блока синхронизации соединены соответственно с 1-м, 2-м и 3-м управляющими входами накапливающего сумматора, информационный выход которого соединен с третьим информационным входом первого блока вычисления дизъюнкции, а информационный выход i-го блока вычисления дизъюнкции (i=1, ..., m-2) - с третьим информационным входом (i+1)-го блока вычисления дизъюнкции, первые три управляющих входа которого соединены соответственно с аналогичными входами остальных блоков вычисления дизъюнкции и соответственно с (m+6)-м, (m+7)-ми (m+8)-м выходами блока синхронизации, следующая k-я группа выходов (по шесть выходов в каждой) которого (k=1, ..., m-1) соединены соответственно с шестью управляющими входами k-го блока вычисления дизъюнкции, (7m+3)-й выход блока синхронизации соединен через первый управляющий вход блока вывода с синхронизирующим входом параллельного регистра этого блока, (7m+4)-й выход блока синхронизации соединен с выходом ЗАПРОСА ДАННЫХ устройства, в которое дополнительно введен блок вычитания, информационный выход которого соединен со вторым информационным входом блока вывода, второй информационный вход блока вычитания соединен с информационным выходом (m-1)-го блока вычисления дизъюнкции, а первый информационный вход - с информационным выходом накапливающего сумматора и третьим информационным входом блока вывода, второй информационный выход которого соединен со вторым информационным выходом устройства - КОНЪЮНКТИВНЫЙ ЛОГИЧЕСКИЙ ОПРЕДЕЛИТЕЛЬ, а третий информационный выход - с третьим информационным выходом устройства - СУММИРУЮЩИЙ ЛОГИЧЕСКИЙ ОПРЕДЕЛИТЕЛЬ, второй, третий, четвертый и пятый управляющие входы блока вывода соединены соответственно с (7m+5), (7m+6), (7m+7) и (7m+8)-ми выходами блока синхронизации, (7m+9), (7m+10), (7m+11), (7m+12), и (7m+13)-e выходы которого соединены соответственно с первым, вторым, третьим, четвертым и пятым управляющими входами блока вычитания, а (7m+14) - и выход блока синхронизации соединен с выходом ПОВТОРНОГО ЗАПРОСА ДАННЫХ устройства.

Благодаря новым отличительным признакам предложенное устройство позволяет с наименьшими аппаратурными затратами реализовать выполнение двух дополнительных функций: вычисление СЛО и КЛО (А⁺ и А∧). Последнее, в свою очередь, позволит с использованием дешевых аппаратурных средств наиболее глубоко проводить исследования работы конвейерных систем в мультипрограммном режиме и обеспечивать большую близость полученных расписаний загрузки объектов в систему к оптимальным. Производительность конвейерной системы в этом случае будет максимальной. Расширение функций устройства позволит также проводить научные эксперименты по поиску и апробации новых методов повышения производительности конвейерных систем.

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

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

Работа устройства состоит из трех основных последовательно выполняемых этапов.

1-й этап. Вычисление суммирующего логического определителя А⁺.

2-й этап. Вычисление дизъюнктивного логического определителя А∨.

3-й этап. Вычисление конъюнктивного логического определителя А∧.

Для простоты опишем работу устройства, когда число строк матрицы времен выполнения операций равно трем, m=3 (см. фиг.10).

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

Перед началом работы устройства на вход 24 (см. фиг.2 и 6) подают сигнал для установки триггера и двоичного счетчика БС 2 в нулевые состояния. Затем на вход 26 подают сигнал для начального запуска устройства. Первый тактовый импульс задающего генератора задает считывание информации из первой многоразрядной ячейки элемента памяти. В этой ячейке, как и в других, предварительно записанная информация позволяет получать на соответствующих выходных линиях элемента памяти импульсы. Перечень выполняемых операций устройством в зависимости от номера тактового импульса ГТИ БС 2 (циклограмма работы устройства) приведен в таблице 2.

Из таблицы видно, что, начиная со 2-го тактового импульса и заканчивая (6N+1)-м тактовым импульсом, производится накопление в накапливающем сумматоре 3 всех чисел матрицы (см. фиг.10), тем самым за этот начальный промежуток времени происходит вычисление СЛО А⁺ (см.[1] с.110, 113, 116...119) и вывод его значения на выход устройства и в первый параллельный регистр блока 4 вычитания. На этом же последнем тактовом импульсе проводится повторный запрос данных этой же матрицы (см. фиг.10). Начиная с (6N+2)-го тактового импульса и заканчивая L-м тактовым импульсом (в зависимости от числа N), производится вычисление ДЛО А∨. Порядок его вычисления совпадает с порядком вычисления, описанным в [7]. На последнем L-м тактовом импульсе происходит так же получение КЛО и вывод результатов A∨ и A∧ на выход устройства. Здесь же формируется запрос данных очередной матрицы и процесс вычисления A⁺, A∨ и A∧ повторяется по вышеописанному порядку. Заметим, что на вычисление всех трех ЛО можно было бы значительно сократить время, если бы для вычисления СЛО А⁺ ввели дополнительный накапливающий сумматор и вычисление A⁺ вели параллельно во времени с вычислением А∨. Однако время вычисления можно значительно сократить повышением частоты ГТИ в БС 2 или применением более быстродействующей элементной базы.

Благодаря введению в известное устройство [7] всего одного блока 4 вычитания и установлению новых вышеописанных связей между элементами получено значительное расширение функциональных возможностей устройства при минимальных аппаратурных затратах.

ЛИТЕРАТУРА

1. Левин В.И. Структурно-логические методы исследования сложных систем с применением ЭВМ. - М.: Гл. ред. физ. - мат. лит., 1987 - 304с.

2. Танаев B.C., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. - М.: Наука, 1989. - 328 с.

3. Пашкеев С. Д. Основы мультипрограммирования для специализированных вычислительных систем. -М.: Сов. радио, 1972. - 184 с.

4. Майоров С.А., Новиков Г.И. Принципы организации цифровых машин. - М.: Машиностроение, 1974.

5. Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин. - М.: Машиностроение, 1979.

6. Новиков А.Н., Новиков В.А. Устройство для мультипрограммирования конвейерных систем. Патент №2127898.

7. Новиков А.Н. и др. Устройство для вычисления дизъюнктивного логического определителя. Патент №2060537.

Формула изобретения

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

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

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

РИСУНКИРисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10