Устройство для табличной реализации многоместных логических функций Советский патент 1983 года по МПК G06F17/10 

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

шестого элементов И, выходы третьего четвертого и пятого элементов И

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

Изобретение относится к вычислительной и управляющей технике. Мини и микро-ЭВМ находят широкое применение в системах управления технологическими процессами и промышленными установками. Основные пре образователи при этом выполняются в арифметико-логическом устройстве, приспособленном для выполнения двухместных арифметических операций с . многозарядными переменными, а также двухместных поразрядных логических операций. Однако при реализации алгоритмов управления часто возникает задача выполнения многоместных логических функций и систем функций от нескольких двоичных переменных, упакованных в одно слово и образующих вектор двоичных переменных. Функ ции эти могут отличаться большим раз нообразием и изменяться как по виду так и по числу аргументов от задачи к задаче. Поэтому использование комбинационных схем с жесткой структуро программируемых логических матриц ли бо функциональных преобразователей на основе. ПЗУ оказывается неэффектив ным. Известен процессор данных, содержащий обрабатывающее ПЗУ и стек для хранения промежуточных результатов, содержащий ПЗУ для логической обработки 1 . Недостатком его является необходимость использования сравнительно дорогого дополнительного блока ПЗУ с обрамлением, что снижает зкономичность устройства. Кроме того, программирова1 е ПЗУ для настройки его применительно к решению различных задач является более трудоемкой операцией, чем программирование ОЗУ. Известно устройство хранения и преобразования информации, в котором обеспечивается табличная реализация поразрядных двухместных логических функций в накопителе ОЗУ 2 Однако для реализации многоместных логических функций от вектора двоичных переменных при использовании этого устройства также потребуется программный метод на основе команд условного перехода, недостатком которого является сложность программирования, большой объем программ и констант, необходимых для выделения переменных и вычисления логических функций и низкая производительность. С целью устранения этих недостатков предлагается: использовать устройство, обеспечивающее реализацию многоместных логических функций от вектора двоичных переменных на основе таблиц, хранимых в накопителе блока памяти. Это способствует повышению экономичности, так как основу составляют наиболее дешевые, надежные и технологичные элементы - запоминающие элементы единого блока памяти, используемого и для других целей (хранение программ, констант данных). Кроме того, хранение таблиц в блоке памяти позволяет легко их из менйть. Смена таблиц менее трудоемка, чем изменение программ при программн Л реализации логических функций. Предлагаемое устройство обеспе.чивает реализацию функций с помощью одной команды, выполняемой за два обращения к блоку памяти, что существнно повышает производитель- ность в сравнении с программным способом. Цель изобретения,- повышение производительности устройства. Поставленная цель достигается тем, что устройство для табличной реализации многоместных логических функций, содержащее блок памяти,, выход которого подключен к информационным входам регистра операнда и регистра команд, И1 ормацйойный вход подключен к первому входу устройства, а адресный вход - к выхкэду коммутатора адреса, первый инфорндционный вход которого подключен к второму входу устройства, второй инфс рмационн1з1й вход - к выходу адреса первого операнда регистра команд, третий и четвертый информационные входы коммутатора адреса соединены с выходом адреса второго операнда регистра команд и третьим входом устройства соответственно, выходы мпа/рих разрядов регистра операнда соединены с пятым информационным вхо дом коммутатора адреса, шестой информационный вход которого соединен с выходом номера сегмента регистра команд, Дополнительно содержит блок микропрограммного управления , элементов ИЛИ, коммутатор разрядов дан иых и триггер результата, причем вы ход Kofia операций регистра команд подключен к входу блока микропрограм много у правления:, первый, втррЫ1«тре Ti, четвертый и пятый выходы которого подключены соответственно к уп равляющим входам регистра команд, коммутатора адреса, регистр операнд блока памяти и триггера результата, выход которого подключен к выхо/ устройства, а установочный вход к выходу коммутатора разрядов данных, информационнЁ й вход которого со с выходом блока памяти, выход старших разрядов регистра операнда подключены к первым входам элементов ИЛИ группы, вторые входы которы соединены с выходом адреса таблицы в сегменте, выходы элементов ИЛИ группы подключены к информационному входу, коммутатора адреса, выход номера разряда регистра команд соединен с управляющим входом коммутатора разрядов данных. Блок микропрограммного управления содержит блок памяти микропрограмм, регистр МИКРОКОМ5Г.НД, регистр адреса микрокоманд, генератор тактовых импульсов и шесть элементов И, причем выходы первого и второго элементов И подключены к первому и второму управляющим входам регистра адреса микроко манд, первая группа выходов регистра микрокоманд соединена с .первым информационным входом регистра адреса микрокоманд, второй информационный вход которого соединен с входом блока, а выход - с адресным входом блока памяти микропрограмм, управляющий вход которого соединен с первым выходом генератора тактовых импульсов, второй выход которого соединен с управляющим входом регистра микрокоманд, информационный вход которого соединен с выходом блока памяти микропрограмм, вторая группа выходов регистра микрокоманд соединена с вторым выходом блока, третий выход генератора тактовых импульсов соединен с первыми входами .первого, второго, третьего, четвертого и пятого элементов И, четвертый выход генератора тактовых импульсов подключен к первому входу шестого элемента И, выход которого подключен к четвертому выходу б тока, третья группа выходов регистра микрокоманд подключена к вторым входам, первого, второго, третьего, четвертого, пятого и шестого элементов И выходы третьего, четвертого и пятого элементов И подключены соответственно к первому, третьему и пят ому выходам блока. На фиг.1 показана функциональная схема предлагаемого устрсмства; на фиг12 - пример реализации коммута тора ауЕ)реса; на фиг.3 - пример реализации коммутатора разрядов данных; на фиг. - .функциональная схема генератора тактошх импульсов; на фиг.5 временная диаграмма работы устройства; на фиг.6 - преобразования, связанныес Формированием адреса. Устройство содержит блок J памяти с выходом 2, адресным входом 3, управляющим входом 4 и информационным $ входом 5t регистр 6 операнда с выходом 7 младших разрядов, выходом 8 старших разрядов, информационным вхо дом 9 и управляющим входом 10, регистр 11 команд с выходом 12 кода операций, выходом 13 адреса первого операнда, выходом 1k номера разряда выходом 15 номера сегмента, выходом 16 адреса таблицы в сегменте, информационным входом 17 управляющим вхо дом 18 и выходом 19 адреса второго операнда, включающего выходы Й-16, коммутатор 20 адреса с информационными входами 21-23 и входом 2k, вклю чающим информационные входы 25-28, управляющим входом 29 и выходом 30, группу элепентов ИЛИ 31 с выходами 32, выход 33 устройства, коммутатор З разрядных данных с информационным входом 33, управляющим входом Зб и информационным выходом 37- Триггер 38 результата с управляющим входом 39, блок kQ микропрограммного управления, содержащий регистр Ц адреса микрокоманд с информационными входами k2 и 43, управляющим входом kk, блок памяти микропрограмм с адрес ным входом , управляющим входом 47, регистр 48 микрокоманд с информационным входом 9, управляющим вхо дом 50, первой группой выходов 51, второй и третьей группами выходов 52 и 53, первый, второй, третий, чет вертый, пятый и шестой элементы И 54-59. генератор 60 тактовых импульсов с выходами 61-б. Коммутатор 20 (фиг.2) содержит : группу Мультиплексоров б5, коммутато 3 (фиг.З) мультиплексоры 66-68, генератор 60 (фиг.) содержит генератор б9 импульсов, элемент 70 задержки с входом 71 и выходами 72-7 и элементы И 75 и 7б. Работа устройства синхронизируетс импульсными сигналами на выходах 616 генератора 60 тактовых импульсов. Временная диаграмма цикла Т работы устройства (фиг. 5) зависит от особен ностей блока 1 памяти, блока kS памяти микропрограмм и задержек исполь .зуемых элементов. Цикл работы можно разбить, например, на 4 такта (1 , t ,f, Т): 1 такт - чтение микрокоманды из блока 5 памяти микропрограмм; П такт - запись кода микрокоманды в регистр микрокоманды, фор мирование кода адреса на входе 3 блока 1 памяти; llj такт - чтение из блока 1 памяти; 1У такт - запись ко55да, считанного из блока 1 памяти;, в один из регистров, В соответствии с этим сигнал на выходе 61 соответствует Т-ому и И-ому тактам, на выходе 62 - 1 У-ому такту, на выходе 63 -W-ьему и 1У-ому тактам, на выходе 6 - |У-ому такту.Выход 61 генератора 60 тактовых импульсов подключен к управляющему входу 7 блока kS памяти микропрограмм,выход 62 - к управляющему входу 50 ре- . гистра t8 микрокоманд, выход 63 - к второму входу элемента И 59, выход б - к вторым входам элементов и . Устройство работает следующим образом . Из счетчика команд (не показан на вход 21 поступает код адреса команды реализации функции f(x,X2, х).Команда считывается из блока 1 памяти по адресу, подаваемому на вход 3 через коммутатор 20 с входа 21, « записывается в регистр 11 команд. В регистр по входу k2 записывается код адреса 1-ой микропрограммы реализации многоместных логических функций. По адресу,поступающему с выхода 3 регистра 11 команд, из блока 1 памяти считывается операнд (вектор .1) и записывается в регистр 6 операнда. В регистр адреса микрокоманд по входу k3 записывается адрес П-ой микрокоманды. В соответствии с приведенными на Фиг.1 соединениями код на входе 2 Коммутатора 20 адреса состоит из k-x частей: X,&«H C2gCvHig:f3oXi-,i:w2. OX2 i:Vyii6-.43o) где C gt ze- Ф РОванный код, подаваемый на . ВХОД 28; Xj.,,i.,HD г V jgCHii -.ll, (т. Ьб t 63-Y,fetMi 6-43,8 CvMeM, (№4 101 g); i3-Yiitim-,: 13, СкитгИ1.), де - код на i-м входе; V: - код J, 1ф - номера позиций э фиг1; о - знак конкатенации, Числа разрядов у выделенных групп еременных должны выбираться из слеующих условий: Oeog,NC }Г-- °еа с -. e l TMOKc , 1- «a5 i-,, где Ы, n - число ямеек и число разря дов в блоке 1 памяти; af - целое удовлетворяющее неравенствам as3att Q4 i тмакс мми максимальное и минимальное число разрядов в векторе двоичных переменных, для которого можно вычислять логическую функ цию табличным способом. Рассмотрим пример выбора чисел разрядов. Пусть N 2 ijK ячеек,m 3, n; 32. Тогда получим: m 3eog- Nt-n КУ)г5 1 Ь Wg-5 ч Необходимость вычисления различ«« ных многоместных логических функций более чем от 8-ми переменных в задачах управления возникает сравнительно редко. Таблицы при 8 становятся громоздкими и выделение сегментов ОЗУ для их хранения экономически нёоправдлны. При необходимос ти, в тех случаях, когда число аргументов 40 8,логические функции можно реализовать программно-таблич ным методом. Используя выделение переменных и команды условного перехода по их значениям, задача может быть Сведена к вычислению нескольких восьместных функций. Двухместные функции можно реализовать программным способом либо ис пользовать избыточное представление в виде: U,,x.i)(x-,,Xa( записи таблиц реализуемых функций используются один или несколько сегментов.накопителя блока 1 памяти, содержащих по N 2-гмок ячеек. ., 8, N, 256 ячее Таблица восьмиместной функции ра Метается в запоминающих элементах, принадлежащих одному разряду Сегме та из 256 ячеек. Адрес ячейки в се 1 8 менте соответствует набору двоичных переменных, на которых определена функция, В одном разряде этого же сегмента могут быть размещены 2 таблицы семиместных, k таблицы - шеСтиместных, 8 таблиц .- пятиместных, 1б таблиц четырёхместных и 32 таблицы трехместных функций. Всего в одном cei- менте может быть записано следующее число таблиц: KgisG+k ne k К К.,,, где Кц - число таблиц - местных функций, f 3-8, Максимальное число сегментов накопителя блока 1 памяти, которое может быть использовано для записи таблиц реализуемых функций, определяется одомис,а 2, В рассмотренном примере УСТРОЙСТВО может выполнять команду реализации многоместной логической функции от вектора двоичных переменных. При этом используется следующий фэрмат .команды, имеющей 5 полей соответственно числу выходов в регистре 11 команд. В поле выхода 12 указывается код операции; в поле выхода 13 - адрес операнда; в поле выхода 1 - номер разряда накбпителя, в котором записана таблица реализуемой функции; в поле выхода 15 номер требуемого сегмента накопите-: ля из числа выделенных для хранения таблиц; в поле выхода 1б - адрес таблицы внутри сегмента при числе аргументов о Т монетеКод : 1 1 У бС5:ГЗ адреса таблицы внутри сегмента, указываемый в формате команды, определяется следующим образом. При числе аргументов т., 8: Y-16 5-Ч QOO QПри Пд 7: Y eL5:lD , о 256(0,1. В одном разряде сегмента ОЗУ из 256 ячеек может быть записано 2 таблицы семиместных функций. Старший разряд 2- кода Y определяет положение требуемой аблицы в выделенном 9 сегменте. Сегмент выбивается кодом ° 27 3. прй1% .43-2524000 , Wa l5Z425(OA-f a5: fl6t5H3-j приWvQ-i-4ibt5:43- 25Z4Z Z,3,Z,Z5i4 aZiGM8 последнем случае код Y| может указывать положение одной из 32 таблиц трехместной логической функции. Таким образом, код в формате команды и группа 31 элементов ИЛИ обеспечивают адресацию таблиц функций от различного числа переменных при упакорке этих таблиц в сегменте из 256 ячеек. Следует отметить, что при старше 8 - т разрядов в регистре 6 операнда содержит нули. А в коде Y. (5:t) могут быть отличными от нуля только те разряды, которые соответствуют отсутствующим в регистре б двоичным переменным старших разрядов. Работу устройства при выполнении команды реализации многоместной логи ческой функции рассмотрим на примере используя иллюстрацию преобразований связанных с формированием адреса и в делением разряда считанного слова из сегмента таблиц, представленную на фиг.6. Пусть требуется реализовать трехместную функцию: 1 XiCBV-i Пусть код вектора х., х, ) хранит , ся в ячейке с адресом А1. Допустим, что блок.. 1 памяти имеет емкость N. К и для хранения таблиц реализуемых функций используется послед ний сегмент, содержащий 256 ячеек с двоичными адресами: (111.100.000.000 ..(ri1.111.111.111). Таблица реализуемой функции занимает 8 ячеек. Допустим, что для ее хранения используется 17-ый разряд выделенного сегмента. В этом разряде, 256 бит, и могут быть размещены и другие таблицы. Пусть под таблицу ре ализуемой функции в выбранном сегмен те выделены 8 ячеек с номерами: (11. 000),... (11 .111). .6 схема 55 тически показано положение таблицы в накопителе блока 1 памяти. В поле }g команды-должен быть указан код адреса таблицы реализуемой функции f в выделенном сегменте из 256 ячеек. В нашем случае это код номера восьмерки ячеек (одной из 32-ух. В соответствии с принятым местом положения таблицы XifitSr-D-OOOH. В поле команды до.пжен быть указан код номера сегмента из 256 йчеек, который исгюльзован для хранения таблиц. При числе разрядов этого поля можно указать различных сегмента. Поскольку для записи таблицы функции f использован последний сегмент с номером 11, то Y (2:1)11. В поле команды указывается код номера разряда, в котором записана таблица. В нашем примере- это код 17-го разряда: 10001 .Поскольку принято, что для хранения таблиц отводится конец накопи,теля, то фиксированный код на входе 28: C2.g2:1 П. Этот код определяет область памяти в примере емкостью tK , в которой могут быть выделены сегменты по 256 ячеек для хранения таблиц. Рассмотрим эффект, связанный с повышением производительности. При програм(1ном способе реализации вычисление функции от 6-и аргументов потребуется при распаковке аргументов не менее 6 команд, каждая из которых потребует не менее 3-х обращений к ОЗУ, при вычислении ФУН.КЦИИ потребуется не менее 6-и команд условного перехода, выполнение каждой из которых потребуется не менее 2-х обращений к ОЗУ. Таким образом, время вычисления шестиместной функции можно представить так: (Щ -ЬOro, где Тд - время цикла обращения к ОЗУ. В предлагаемом устройстве выполнение команды реализации шестиместной логической функции, включая выборку команды, потребует .

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

T Pit- c - U-POt

Ср,

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

t - среднее время выполнения

Р одной операции. Примем t(-p , R, 0,01. Получим Т 0,01-30 ч- (1-0,01) ц TO it,26 V

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

,,)tcp-Л 9Toг5

,15

В

п

11

65

65

15

35

66

Фиг.З

.

65

65

Фиг.1

68

§3

gif

ФигЛ

«« 4v

«ч «л

Tl

Фчг 5