Устройство для табличной реализации многоместных логических функций

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН все) G 06 F 15/ 1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И АВТОРСМОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

f10 ДЕЛАМ ИЗОБРЕТЕНИЙ И О ГНРЬ1ТИЙ (21) 3374383/18-24 (22) 04.01.82 (46) 23 ° 05.83 ° Бюл. Н 19 (72) В.Ф.Иелехин (71) Ленинградский ордена Ленина политехнический институт им. Н.И.Калинина (53) 681.32(088.8) (56) 1. Патент CI0A Н 4092730, кл. G 06 F 15/00, опублик. 1978.

2. Авторское свидетельство СССР

Н 640300, кл. G 06 F 15/00, 1978

{прототип). (54)(57) 1.УСТРОЙСТВО ДЛЯ ТАБЛИЧНОЙ

РЕАЛИЗАЦИИ ИНОГОИЕСТНЫХ ЛОГИЧЕСКИХ

ФУНКЦИЙ, содержащее блок памяти, выход которого подключен к информационным входам регистра операнда и регистра команд, информационный. вход подключен к первому входу устройства, а адресный вход - к выходу коммутатора адреса, первый информационный вход ксторого подключен к второму входу устройства, второй информационный вход - к выходу адреса первого операнда регистра команд, третий и чет.вертый информационные входы коммутатора адреса соединейы с выходом адреса второго операнда регистра команд . и третьим входом устройства соответственно, выходы младших разрядов регистра операнда соединены с пятым информационным входом коммутатора адреса, шестой информационный вход которого соединен с выходом номера сегмента регистра команд,.о т л ич а ю щ е е с я тем, что, с целью повышения производительности устройства, оно дополнительно содержит,SU„„ I 019455 A

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

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

1019455

35 вход которого соединен с входом блока, а выход " с адресным входом блока памяти микропрограмм, управляющий вход которого соединен с первым . выходом генератора тактовых импульсов. второи выход которого соединен с управляющим входом регистра микроко. манд, информационный вход которого соединен с выходом блока памяти микропрограмм, вторая группа выходов регистра микрокоманд соединена с вторым выходом блока, третий выход генератора тактовых импульсов соединен с первыми входами первого, второИзобретение относится к вычислительной и управляющей технике.

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

1 программируемых логических матриц ли- р бо функциональных преобразователей на основе. ПЗУ оказывается неэффектив. ным.

Известен процессор данных, содержащий обрабатывающее ПЗУ и стек для хранения промежуточных результатов, содержащий ПЗУ для логической обработки f1 ).

Недостатком его является необхо- димость использования сравнительно дорогого дополнительного блока ПЗУ с обрамлением, что снижает экономичro, третьего, четвертого и пятого элементов И, четвертый выход генератора тактовых импульсов подключен к первому входу шестого элемента И, выход которого подключен к четвертому выходу блока, третья группа выходов регистра микрокоманд подключена к вторым входам первого, второго, третьего, четвертого, пятого и шестого элементов И, выходы третьего, четвертого и пятого элементов И подключены соответственно к первому, третьему и пятому выходам блока. ность. устройства. Кроме того, программирование ПЗУ для настройки его применительно к решению различных задач является более трудоемкой операцией, чем программирование ОЗУ.

Известно устройство хранения и преобразования информации, в котором обеспечивается табличная реализация поразрядных двухместных логических функций в накопителе ОЗУ (2 )

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

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

19455 4

Цель изобретения - повышение про" изводительности устройства

Поставленная цель достигается тем, что устройство для табличной реализации многоместных логических функций, содержащее блок памяти, выход которого подключен к.информационным входам регистра операндаи регистра команду информационный вход подключен к первому входу устройства, а адресный вход - к выходу коммутатора адреса, первый информационный вход которого подключен к второму входу. устройства, второй .ин.формационный вход - к выходу адреса первого операнда регистра команд, третий и четвертый информационные входы коммутатора адреса соединены с выходом адреса второго операнда регистра команд и третьим входом устройства соответственно, выходы .младших разрядов регистра операнда. Соединены с пятым информационным вхо" дом коммутатора адреса, шестой .информационный вход которого соедйнен . с выходом номера сегмента регистра команд, дополнительно содержит блок микропрограммиогоуправления,груупу злементовИЛИ;коммутатор разрядов данных и триггер результата, причем выход нофа операций регистра команд подключен < входу. блока микропрограм= много управления;первый, второй,тре"

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

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

Блок микропрограммного управления содержит блок памяти микропрограмм, регистр микрокоманд, регистр адреса

>0 микрокоманд, генератор тактовых импульсов и шесть элементов И, причем выходы первого и второго элементов И подключены к первому и второму управ:ляющим входам регистра адреса микроко манд, первая группа выходов регистра микрокоманд соединена с .первым информационным входом регистра адреса микрокоманд, второй информационный вход которого соединен с-входом блока,. а выход - с адресным входом блока памяти микропрограмм, управляющий вход которого соединен с первым выходом генератора тактовых импульсов, вто. рой выход которого соединен с управ25 ляющим входом регистра микрокоманд, информационный вход которого соединен с выходом блока памяти микропрограмм, вторая группа выходов регистра микрокоманд соединена с вторым выходом блока, третий выход генератора тактовых импульсов соединен с первыми входами первого, второго, третьего, четвертого и пятого элементов И, четвертый выход генератора так овых импульсов подключен к первому входу

35 шестого элемента И, выход которого подключен к четвертому выходу б юка, третья группа выходов регистра микрокоманд подключена к вторым входам nepsoro, второго, третьего, четвертого, пятого .и шестого элементов

И, выходы третьего, четвертого и пятого элементов И подключены соответственно к первому, третьему и пятому выходам блока.

На фиг.1 показана фуНкциональная схема предлагаемого устройства; нафиг.2 - пример реализации коммутатора адреса; на фиг.3 " пример реализации коммутатора разрядов данных; на фиг.4 - функциональная схема генератора тактовых импульсов; на фиг.5 " временная диаграмма работы устройства; на фиг.б - преобразования, связанныес фюрмированием адреса.

Устройство содержит блок 1 памяти с выходом 2, адресным входом 3, управляющим входом 4 и информационным

1019455

55 входом 5, регистр 6 операнда с выходом 7 младших разрядов, выходом 8 старших разрядов, информационным входом 9 и управляющим входом !0, регистр 11 команд с выходом 12 кода операций, выходом 13 адреса первого операнда, выходом 14 номера разряда, выходом 15 номера сегмента, выходом

16 адреса таблицы в сегменте, информационным входом 17, управляющим входом 18 и выходом 19 адреса второго операнда, включающего выходы 14- 16, коммутатор 20 адреса с информационными входами 21-23 и входом 24, включающим информационные входы 25-28, управляющим входом 29 и выходом 30, группу элементов ИЛИ 31 с выходами

32, выход 33 устройства, коммутатор

34 разрядных данных с информационным. входом 35, управляющим входом 36 и информационным выходом 37. Триггер

38 результата с управляющим входом

39, блок 40 микропрограммного управления, содержащий регистр 4 1 адреса микрокоманд с информационными входами 42 и 43, управляющим входом 44, блок 45 памяти микропрограмм с адресным входом 46, управляющим входом

47, регистр 48 микрокоманд с информационным вхрдом 49, управляющим входом 50, первой группой выходов 51, второй и третьей группами выходов

52 и 53, первый, второй, третий, чет вертый,пятый и шестой элементы И

54-59, генератор 60 тактовых импульсов с выходами 61-64.

Коммутатор 20 (фиг.2) содержит группу мультиплексоров 65, коммутатор

34 (фиг.3) - мультиплексоры 66-68, генератор 60 (фиг.4) содержит генератор 69 импульсов, элемент 70 задержки с входом 71 и выходами 72-74 и элементы И 75 и 76.

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

Временная диаграмма цикла Т работы устройства (фиг.5) зависит от особенностей блока 1 памяти, блока 45 памяти микропрограмм и задержек исполь.зуемых элементов. Цикл Работы можно разбить, например, на 4 такта ((. (-, (y, Т ): 1 такт - чтение микрокоманды из блока 45 памяти микропрограмм; П такт - запись кода микрокоманды в регистр 48 микрокоманды, формирование кода адреса на входе 3 блока 1 памяти; !! такт - чтение из блока 1 памяти; 1У такт - запись кода, считанного из блока 1 памяти „. в один из регистров.

В соответствии с этим сигнал на выходе 61 соответствует 1-ому и !1-ому

5 тактам, на выходе 62 - 1У-ому такту, на выходе 63 -!11-ьему и 1У-ому тактам, на выходе 64 - 1У-ому такту.Выход 61 генератора 60 тактовых импульсов подключен к управляющему входу 0 47 блока 45 памяти микропрограмм,выход 62 - к управляющему входу 50 регистра 48.микрокомаид, выход 63 - к второму входу элемента И 59, выход

64 - к вторым входам элементов

И 54-58.

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

Из счетчика команд (не показан ) на вход 21 поступает код.адреса ко20 манды реализации функции f(x„,õ х ).Команда считывается из блока 1 памяти по адресу, подаваемому. на вход 3 через коммутатор 20 с входа 2 1, и записывается в регистр

11 команд. B регистр 41 по входу

42 записывается код адреса 1-ой микропрограммы реализации многоместных логических функций.

По адресу, поступающему с выхода

З0 13 регистра ll команд, из блока 1 памяти считывается операнд (вектор х х х1) и записывается в регистр

6 операнда. В регистр 41 адреса микрокоманд по входу 43 эаписываетз5 ся адрес П-ой микрокоманды.

В соответствии с приведенными на фиг. l соединениями код на входе

24 коммутатора 20 адреса состоит из

4-х частей:

Х2 Ъ:43= С28 Ф В:4 30Х,д 1-!я,„.Л g

«О Х СМ26 ° 1ДОХ г 1!т1 <. 3, где С 1т! . 11 - фиксированный код, подаваемый на вход 28;

Х . С1л : !1=1 Си1л5 .13 (п7л"! пл6)

% 6, 7 0 Ç = („6 Стиль: л 3 ч У8 Г т18:л 3, (п1л6 "18))

251"я 2.6 " = 11Е т1 л3, (w 1=1 я 2.5)р где Х„ - код íà i-м входе; 1 - код 1 на J-N выходе; 1,ь - номера позиций на фигl; о - знак конкатенации.

Числа разрядов у выделенных групп переменных должны выбираться из следующих условий:

1019455

1=)ЕО@НС

14 1 16 в„=ЗЕо иС

П 1э = т .Г мин 5

- +тпр = и) т мокс

В 16 26

7 25

15 12 где и и - число ячеек и число разря- 0 дов в блоке 1 памяти; 1а1 - целое удовлетворяющее неравенствам

Q «)gg«g+q штн<с m г„,„„- максимальное и минимальное чйсло разрядов в векторе двоичных переменных, для которого можно вычислять логическую функ. цию табличным способом.

Рассмотрим пример выбора чисел .разрядов.

Пусть N = 2 = 4К ячеек,m =8, m = 3, и; 32.

Тогда получим:

> 3Ро NC=4< „4=6

""1 - п1В =б а„ =2

Необходимость вычисления раэлич ных многоместных логических функций более чем от 8-ми переменных в зада30 чах управления возникает сравнительно редко. Таблицы при m m = 8 становятся громоздкими и выделение сегментов ОЗУ для их хранения экономически неоправданы. При необходимости, в тех случаях, когда число аргументов е 8,логические функции можно реализовать программно-табличным методом. Используя выделение переменных и команды условного .перехода bio их значениям, задача может быть сведена к вычислению нескольких восьместных функций.

Двухместные функции можно реализовать программным способом либо ис-. польэовать избыточное представление в виде:

f. (Х1 X2)=%(X1,.Х .)(Х q Х3). Для записи таблиц реализуемых з0 функций используются один или несколько сегментов накопителя блока

1 памяти, содержащих по N = 2 т„, „

Ячеек. пРи111. = 8, йо = 256 Ячеек

niaw

Таблица восьмиместной функции раэ- йещается в запоминающих элементах, принадлежащих одному- разряду сегмента из 256 ячеек. Адрес ячейки в cerменте соответствует набору двоичных переменных, на которых определена функция.

В одном разряде этого же сегмента могут быть размещены 2 таблицы семиместных, 4 таблицы - шестиместных, 8 таблиц .- пятиместных, 16 таблиц четырехместных и 32 таблицы - трехместных функций. Всего в одном сегменте может быть записано следующее число таблиц:

К 2-66+ К- Щ+ "6 64 К 32+ К < 6+ К Я 256 и, где К„ - число таблиц — местных функций, i = 3-8.

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

YA qq ренном примере и смоке

Устройство может выполнять команду реализации многоместной логической функции от вектора двоичных переменных. При этом используется следующий Формат .команды, имеющей 5 полей соответственно числу выходов в регистре 11 команд. В поле выхода 12 указывается код операции; в поле выхода 13 - адрес операнда; в поле выхода .4 - номер разряда накопителя, в котором записана таблица реали- . зуемой функции; в поле выхода 15номер требуемого сегмента накопите-. ля из числа выделенных для хранения таблиц; в поле выхода 16 - адрес таблицы внутри сегмента при числе аргументов код у щ. 6 .1).= Т16 E5: 1 ) адреса таблицы внутри сегмента, указываемый в Формате команды, определяет.сл следующим образом.

При чи е аргументов mà = 8 „z (5 1) = ооооо.

При а т16 |,5:1j = 2 0000, 2 E (0,1.

В одном разряде сегмента ОЗУ из

256 ячеек может быть записано 2 таблицы семиместных функций. Старший разряд 2- кода У< определяет положение требуемой эблицы в выделенном 1019455

10 сегменте. Сегмент выбиоается кодом С28 oX <> С вь Фю

При о 6: Y„t5:43=2в24000 Z.,,Z4C(O<); пРи 111 =g: У„<5:l3» а ь

=2 142 ОО Х «42 6(01)» при yylQ= 5. :Y Гб:13-

I .... 2, 14 ZqZZOZ

Z. 24 3 g 2„7g242,322Z6 (0,1) .

8 последнем случае код $6 может указывать положение одной из 32 таблиц трехместной логической функ ции.

Таким образом, код У, в Формате команды и группа 31 элементов ИЛИ обеспечивают. адресацию таблиц функций от различного числа переменных при "упаковке" этих таблиц в сегменте из 256 ячеек.

Следует отметить, что при в,<8 старше 8 - m> разрядов в ре тре 25

6 операнда содержит нули. А в коде (5:1) могут быть отличными от нуля толька те разряды, которые соответствуют "отсутствующим" в регистре 6 двоичным переменным старших разрядов.

Работу устройства при выполнении команды реализации многоместной логи-. ческой Функции рассмотрим на примере, используя иллюстрацию преобразований, связанных с формированием адреса и вы делением разряда считанного слова из сегмента таблиц, представленную на фиг.6.

Пусть требуется реализовать трехместную функцию: х„Е х ® ;,. Пусть код вектора (x>, х, х )хранит-, ся в ячейке с адресом А1. Допустим, что блок,. 1 памяти имеет емкость ,М,=. 4К и для хранения таблиц реализуемых функций используется последний сегмент, .содержащий 256 ячеек с двоичными адресами: (111.100.000.000) ..(111.111.111.111).

Таблица реализуемой функции занимает 8 ячеек. Допустим, что для ее хранения используется 17-ый разряд выделенного сегмента. В этом разряде, 256 бит, и могут быть размещены и другие таблицы. Пусть под таблицу ре- . ализуемой функции в выбранном сегменте выделены 8 ячеек с номерами: (11.000),...(11.111). На фиг.6 схематически показано положение таблицы в накопителе блока 1 памяти.

В поле У команды .должен быть ука. эан код адреса таблицы реализуемой функции в выделенном сегменте иэ

256 ячеек. В нашем случае это код номера восьмерки ячеек (одной иэ

32-yx).

8 соответствии с принятым местом положения таблицы 16 (б: 1) = 000 И.

В поле У„< команды должен быть указан код йомера сегмента из 256 ячеек, который использован для хранения таблиц. При числе разрядов этого поля m = 2 можно указать

4 различных сегмента. Поскольку для записи таблицы функции f использован последний. сегмент с номером

11, то У., (2:1)-11.

В поле У14 команды указывается код номера разряда, в котором записана таблица. И нашем примере- это код 17-го разряда: Y = 10001.Поскольку принято, что для хранения таблиц отводится "конец" накопителя, то фиксированный код на входе

28: С В 2:1 = 11. Этот код определяет область памяти в примере емкостью 1К, в которой могут быть выделены сегменты по 256 ячеек для хранения таблиц.

Рассмотрим эффект, связанный с повышением производительности. При программном способе реализации вычисление функции от 6-и аргументов потребуется при "распаковке" аргументов не менее 6 команд, каждая иэ которых потребует не менее 3-х обращений к ОЗХ, при вычислении

Функции потребуется не менее 6-и команд условного перехода, выполнение каждой иэ которых потребуется не менее 2-х обращений к ОЗУ.

Таким образом, время вычисления шестиместной функции можно предста-. вить так:.<„ = (a s + -e. 2) T©.->o Tb, где То - время цикла обращения к 03У.

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

1 цр= 1о.

1019455

Среднее время Т выполнения операции в известном устройстве;

T =РАл + 4-Р„)pep, где Р . - вероятность появления в программах задачи вычисления многоместных логических функций;

t — среднее время выполнения одной операции.

Примем йср = 4Т,„ Р„ = 0,01.

Получим T = (0,01 30 +.(1-0,01)

4 То= 4,26 То

Аналогично в предлагаемом устройстве

T iT = Р.HЛФ+(1-Р.НР=Ъ, 997о

1019455

10l9455

1lgf ячейки

ВНИИПИ Заказ 3706

Тираж 706 Подписное

» »»»»»

Филиал" ППП "Патент", г. Ужгород, ул.Проектная,4