Устройство для организации мультиветвления процессов в электронной вычислительной машине Советский патент 1982 года по МПК G06F9/50 

(5) УСТРОЙСТВО ДЛЯ ОРГАНИЗАЦИИ МУЛЬТИВЕТВЛЕНИЯ ПРОЦЕССОВ В ЭЛЕКТРОННОЙ ВЫЧИСЛИТЕЛЬНОЙ Изобретение относится к вычисли.тельной технике и может использовать ся в электронных вычислительных маши нах (ЭВМ), для логических преобразований, связанных с управлением внешними объектами, например, технологическими процессами, станками и т.д управлением процессами в самой ЭВМ, преобразованиями структур данных трансляцией, распределением ресурсов и др. Известно устройство, содержащее блок фиксации запросов, блок хранения текущих приоритетов, блок установки приоритета, в котором с целью увеличения гибкости введена матрица коммутирующих элементов, блок анализа состояний матрицы, группы регистров, логических элементов и дешифраторов по числу абонентов 1. Недостатками устройства являются большие аппаратурные затраты и жесткость схемы управления. МАШИНЕ Известно устройство, в котором с целью обеспечения возможности изменения приоритета дополнительно используются три регистра, три счетчика, три триггера и достаточно сложная логическая схема 21. Недостатками устройства являются большие аппаратурные затраты, недостаточная универсальность. Наиболее близким по технической сущности к изобретению является устройство, содержащее блок памяти, подключенный к шине данных, коммутатор адреса, выход которого подключен к блоку памяти, регистр., команд, входы которого связаны с шиной данных, а выходы разделены на шесть групп, блок микропрограммного управления, входы которого подключены к первой группе выходов регистра команд, а выходы подключены ко входам кода номера канала коммутатора адреса и к управляющим входам всех операционных элементов устройства. входы первого канала коммутатора адреса подключены ко второй группе выходов, а второго канала - к треть четвертой, пятой и шестой группам выходов регистра команд. В этом устройстве для выполнения многоместных логических функций и мультиветвления используются программные методы. При этом для выделения двоичных переменных из вектора-строки используются операции мае кирования и сравнения с нулем, а также СДВИГИ. Для вычисления логических функций и ветвления использу ются команды условных переходов 3 , Использование таких средств позволяет решать все рассматриваемые задачи , но требует значительных затрат памяти для хранения программ отличается сложностью программирования и значительными затратами машинного времени. Цель изобретения - повышение про изводительности и экономичности. Поставленная цель достигается тем, что в устройство, содержащее блок памяти, регистр команд, блок микропрограммного управления и многоканальный коммутатор адреса, выход которого соединен с адресным входом блока памяти, а вход выбора Номера канала соединен с первым выходом блока микропрограммного управления первый вход которого является управляющим входом устройств гторой вход подключен к первому выходу регистра команд, информационными 8ХОД которого соединен с информационным выходом блока памяти, информационный вход которого является первым входом устройства, вход первого канала многоканального коммута тора адреса подключен к второму выходу регистра команд, входы второго санЁ/1а соединены соответственно с третьим, четвертым, пятым и шестым зыход ми регистра команд, управляюц м входы блока памяти, многоканаль ого коммутатора адреса и регистра команд соединены с вторым выходом блока микропрограммного управления, введены регистр результата, коммутаторы информации и регистр операнда, управляющие входы которых соеди нены с вторым выходом блока микропрограммного управления, информацио ные входы регистра операнда и комму т аторовминформации соединены с 1 информа14ионным выходом блока памя434ти, выходы коммутаторов информации соединены соответственно с входами регистра результата, выход которого соединен с первым входом пятого канала многоканального коммутатора адреса, первый выход регистра операнда подключен к первым входам третьего и четвертого каналов многоканального коммутатора адреса, второй вход третьего канала которого соединен с вторым выходом регистра операнда, второй вход четвертого канала подключен к четвертому выходу регистра команд, третьи входы третьего и четвертого каналов многоканального коммутатора адреса подключены к шестому выходу регистра команд, четвертые входы соединены с вторым входом устройства, второй вход пятого канала многоканального коммутатора адреса соединен с пятым выходом регистра команд, третий вход является третьим входом устройства, входы кода номера канала коммутаторов информации соединены с третьим выходом регистра команд. Кроме того, в устройстве блок микропрограммного управления содержит узел памяти микрокрограмм, генератор тактовых импульсов, регистр адреса микрокоманд, регистр микрокоманд, дешифратор кода управления, модификатор адреса, первый вход которого является первым входом блока, первый вход регистра адреса микрокоманд является вторым входом блока, второй вход соединен -с адресным выходом регистра микрокоманд, сметный вход регистра адреса микрокоманд подключен к выходу модификатора адреса, выход регистра адреса микрокоманд соединен с адресным входом узла памяти микропрограмм, информа14ионный выход которого соединен с информационным входом регистра микрокоманд, выход кода управления которого соединен с информационным входом дешифратора кода управления, первый и второй выходы которого являются соответственно первым и вторым выходами блока, третий и четвертый выходы соединены соответственно с вторым входом модификатора адреса и с третьим входом регистра адреса микрокоманд, тактовые входы узла памяти микропрограмм, регистра микрокоманд и дешифратора кода управления подключены к выходу генератора тактовых импульсов. На фиг. 1 представлена схема устройства; на фиг. 2 - схема блока мик ропрограммного управления. Устройство содержит блок 1 памяти f управляющий вход 2 устройства, много канальный коммутатор 3 адреса, регис k команд, выходы регистра , блок 11 микропрограммного управления регистр 12 операнда; выходы 13 и 1 регистра 12, коммутаторы 15-18 инфор мации, регистр 19 результата, информационные входы 20-23 коммутаторов 15-18, входы кода номера канала , вход 28 вьК5ора номера канала коммутатора 3, выход 29 блока 11, входы коммутатора 3 входы 3 Ц устройства, выход kS блока 11, уп равляющие входы 6-5 составных частей устройства, узел 55 памяти микропрограмм, регистр 5б адреса микрокоманд, регистр 57 микрокоманд, дешифратор 58 кода управления, модификатор 59 адреса, выходы 60, 61 peгистра 57, входы 62, 63-регистра 5б, вход 64 модификатора 59, тактовые входы б5-б7 составных частей бло ка, вход 68 регистра 56, вход б9 мод фикатора 59..генератор 70 тактовых импульсов. Входы коммутатора 3 образуют несколько каналов: 30-1-й канал, 31 2-й канал, 32 - 35 входы 3-го канала-, 36-39 - входы k-ro кана ла, - входы пятого канала. Каж дый канал, как и выход коммутатора 3 имеет m двоичных разрядов, m - число разрядов в коде адреса блока 1 памяти. Выделеннэе входы , подключенные к другим частям устройства, позволяют реализовать в 3-м, t-M и 5-м каналах коммутатора 3 следующие функции BjC« -1 35t 35- 34l 34- 43t 33- :i° w.l X jgtrr,, .IfcC bb- ft6t«4l-.,j;.,t H oX4o ffl4o.M;i, где BV - код на входах i-го канала коммутатора 3; ОД из i-й группе входов ( - номер позиции на фиг. 1), содержащий т разрядов. Аналогично . B rmv11 X3-,rm-.1 Согласно фиг. 1 1 т: j K-« V e 9l 9- Vno-1 ) 44K- - 3eI j8 l V iO-4 Kvl- 14 f4- ha- l- Kb-t- i д 14н - 9 9Ч ЧаКа 44 где Cj - константа на j-м входе коммутатора 3; YJ - код на J-M выходе составных частей , 12, 19; j - номер позиции на фиг. 1. Коммутатор 3 адреса выполняет функции мультиплексирования сигналов, подаваемых на его входы: при . 1 при X5a OOrYjfm;n Bntmtl при Y tmv1 B3lm:13 при X,0il Y3im-. при X.18 100 Y,..-l. где X - код на входе 28, YI - код на выходе коммутатора. В устройстве (фиг. 1) могут быть вычислены системы К восьмиместных либо четырехместных логических функций. Таблицы вычисляемых функций хранятся в одном или нескольких cei- ментах Накопителя блока 1 памяти, каждый из которых содержит 2 256 ячеек. При этом в младших К разрядах сегмента размещаются таблицы для одной системы 8-местных функций, либо 16 таблиц для систем -местных функций. Аналогичным образом используются и следующие группы сегмента с таблицами. Устройство можно использовать для реализации 2-3 местных; а также 5-7 местных функций, представляя их как неполностью определенные k и 8-местные функции. Адресация части накопителя, в которой расположены таблицы реализуемых логических функций, осуществляется фиксированным кодом на входе устройства. Для осуществления мультиветвления в устройстве можно выполнять два типа команд: мультиветвление по результату вычисления системы из К восьмиместных логическихфункций и мультиветвления по результату вычисления К четырехместных логических функций. При этом может осуществляться переход к одной из Р42 команд. Рассмотрим формат команд мультиветвления по результату вычисления системы четырехместных и восьмимест ных логических функций. Выделенным полям команды (фиг. 1 соответствуют выходы 5-10 регистра команд. Назначение этих полей команды:. 5- код операции; 6- код адреса операнда; 7- код группы из К разрядов накопителя, в которой размещены табли цы реализуемых функций; 8- код номера одной из 16 таблиц реализуемой системы четырехмест кмх логических функций; при выполне нии команды с реализацией восьмимес ных функций это поле команды не используется и в него может быть запи сан код 0000; 9- код номера сегмента из 2 ячеек с адресами команд, к которым возможен переход при мультиветвлений;to - код номера сегмента, в кото ром размещены таблицы реализуемых функций; если все таблицы могут быт размещены в одном сегменте накопите ля,.то это поле может отсутствовать к Группы по 2 ячеек с адресами ко манд, к которым возможен переход в результате мультиветвлений размещаются подряд в сегменте накопителя, содержащем ячеек. Адресация к этому сегменту осуществляется фикси рованным кодом, поданным на вход ЦЦ устройства.J Рассмотрим работу устройства при выполнении команды мультиветвления по результату вычисления системы из К З-местных логических функций. Команда считывается по адресу, код которого находится в регистре адреса команд (на фиг. 1 не показан) и записывается в регистр k команд. Код операции с выхода 5 поступает в блок 11 микропрограммного управления Под управлением блока 11 выполняется следующая последовательность микрокоманд. а). Считывание операнда по адресу, поступающему с выходов 6 регистра команд Ц через первый (30) канал коммутатора 3 запись его в регистр операнда 12. 3,8 б). Считывание накопителя по адресу, сформированному в 3-м канале (32-35) коммутатора 3, включение коммутаторов 15-18 сигналами на входах 50-33 запись результата вычисления системы логических функций с выходов коммутаторов в регистр 19 под действием управляющего сигнала на входе в). Считывание ячейки накопителя по адресу, сформированному в пятом канале ( коммутатора 3, и запись находящегося в ней адреса следующей команды в регистр адреса микрокоманд (на фиг. 1 не показан). При выполнении команды мультиветвления по результату вычисления системы из четырехместных логических функций работа происходит аналогичным образом, только во второй микрокоманде используется не третий, а четвертый(36-39) канал коммутатора адреса. При выполнении микрокоманды (а) на вход 28 коммутатора 3 из блока 11 поступает сигнал , на управляющий вход 46 блока 1 памяти, поступает сигнал, обеспечивающий работу блока 1 в режиме считывания на управляющий вход ЦЭ регистра 12 операнда поступает сигнал (строб) разрешение записи кода, подаваемого на его информационные входы. На структурном уровне представления устройства его работа рассматривается в дискретном времени, за, дискрет принят цикл TQ обращения к блоку 1 Памяти. В зависимости от крнкретной реализации блока 1, в частности от типа больших интегральных схем, цикл Тд может быть различным и ему соответствует различная временная диаграмма сигналов на управляющем входе k6 и сигнала на выходе накопителя. При выполнении 2-й микрокоманды (б) подаются управляющие сигналы: Х. ,, соответствующий режиму считывания блока 1, (j на вход 5 подается сигнал , разрешающий запись в регистр 19 кода, поступающего с выходом коммутаторов . При этом ri.XQ 6st«-- 3« 4VV «- l- 4l H-l-«C «V полученном коде адреса старшие m:93 Разрмов . 1 onределяют положение сегмента накопителя блока 1, в котором хранятся таблицы реализуемых функций. Младшие 8 разрядов Г 114-П 13 13-5 ° ответствуют набору двоичных переменных реализуемой системы логических функций и определяют адрес ячейки в выбранном сегменте. В этой ячейке за писаны результаты реализуемых функций. Допустим, что таблицы реализуемых функций записаны в младших -х разрядах блока 1 памяти. Тогда в поле команды, соответствующем выходу 7 записан код Yf ., ,00. Рассматриваемой микрокоманде соот ветствуют следующие микрооперации: Y( 4-Н(А) ...00; -. При выполнении 3-й микрокоманды (в) подаются управляющие сигналы: X(j соответствующий ре жиму считывания блока 1 (сигнал раз решения записи в регистр адреса команд (РАК) не показанный на фиг. 1 При этом , ftjln .- C -X lm Hj-X grA-M Х ГПИ}- - Н(А}-. ,. Код C j -YgCmg; 1 определяет положен сегмента из 16 ячеек в блоке 1 памя ти, в котором записаны адреса переходов, соответствующие рассматриваемой, команде мультиветвления. Выбор 1-й из 16-ти ячеек осуществляет ся кодом , соответствующим результатам реализованной системы функций. Блок 11 микропрограммного управления работает следующим образом. После считывания очередной команды и записи ее в регистр команд код операции с выхода 5 поступает на вход б2 для записи в регистр 5б адреса микрокоманд (фиг. 2). Этот код соответствует адресу начальной микрокоманды соответствующей микропрограммы, По этому адресу считывается кОд микрокоманды из узла 55 и записывается в регистр 57- . В соответствии с кодом на выходе 61 в дешифраторе 58 формируется набор управляющих сигналов, определяющих работу операционных частей устройства, С выхода 60 код адреса следующий микрокоманды записывается в регистр 5б- Если возможно разветвление в микропрограмме, управляющим сигналом на входе 69 инициируется работа модификатора 59- При этом в зависимости от кода на входе 69 анализируется один из сигналов на входе б и в соответствии с его значением формируется выходной сигнал, поступающий на вход 63 регистра 5б, Если этот сигнал равен 1 то к содержимому регистра 56 прибавляется 1, если сигнал равен О ТО содержимое регистра 56 не меняется. Возможны и другие подходы к организации блока 11, например, в виде автомата с жесткой логикой на Интегральных схемах либо на программируемых логических матрицах. Рассмотрим правила размешения начальных команд в сегменте. Обозначим Р - количество ветвей в i-м мультиветвлении программы. Тогда множеству мультиветвлении, которые необходимо реализовать, .можно сопоставить множество (Р . Разобьем это множество на подмножества А: таким образом, чтобы сумма элементов каждого подмножества не превосходила 2 . (Для устройства на фиг, 1 1б). Каждому подмножеству А; сопоставим свой сегмент, содержащий 2 ячеек. Номер ячеек выделенного сегмента по порядку присвоим всем ветвям мультиветвлении соответствующего подмножества Aj. Поясним приведенные правила на примере. Пусть CP-,.5,4.7,12,5,9 (Р. . PQ. PV Р4. Pj,Pfe, Р-,) АЛ IP-I, Р|. Рд 2Р; t) PF Vpie- -,p; ,- .. Таким образом, для реализации заданного множества мультиветвлений потребуется 3 сегмента по 16 ячеек для хранения адресов начальных команд всех образованных ветвей. Присвоим камера ячеек первого сегмента ветвям, образованным в результате мультиветвлений, вошедших в подмножество А. Обозна- . чим а ; j-10 ветвь в i-мультиветвлении. Обозначим двоичный.код номера ячейки aj(t a.a .a Q- a ( 4. Аналогичным образом присваиваются номера ячеек ветвям в подмножест вах А ij и А 2. Рассмотрим теперь правила состав ления таблиц реализуемых логических функций. Исходными/ анными для этого являются условия для каждого мультиветвления и принятые номера ячеек для различных ветвей. Допустим что вектор содержит четыре двоичных переменных. На наборах этих переменных определены условия мультиветЬлений. Обозначим F -,характеристическую функцию точек соответствую щего булева пространства: .. /1, если номер набора есть I 0 если номер набора не есть Обозначим fj.;; (х) - логическую функцию от переменных (Хз Xj, Х;|, XQ) , которая принимает .единичное значение на тех наборах; которым соответствует переход к f-й ветви программы в S-M мультиветвлёнии. s.n)-J(i . где Tgij- множество номеров набора, на котдрых fs-i 1. Тогда функции

NBul..o..l..2.-LJ-5..§..Z.J.-2-.10-ll.-12..1L.l..15. 32 (Ю ,3 можно представить Т1 . - .. . yp-s К VeBp.5 f Ур- функция, соответствующая двоичной переменнойур кода номера ячейки с адресом начальной команды в S-M мультиветвлении, P-s множество номеров ветвей i в S-M мультиветвленииi в соответствующем коде номера которых переменная Ур 1, р 0,3 Таким образом, для каждого мультиветвления S получим систему четырех четырехместных логических функций .-(x,,x,,x,,a): Поясним изложенную методику на примере описания функции для первого мультиветвления из рассмотренного выше примера кодирования номеров ячеек, соответствующих ветвями в мультиветвлениях. Пусть заданы следующие условия первого мультиветвления на наборах (Xj, Х, Х, Хр): M) 1.4) Тогда, приняв во внимание таблицу кодирования номеров ветвей, полу- . чим 3 о..г+ f 1-4 FJ+ F74 Ffl+ F-,4F + Fii- i3 fi4 -fr; 3,., f .3 f ;,.4 F 4Fi+ F Fg F F F7 f9 p o 4yia Vfi4y-l-1 3-1 0; Соответствующая таблица функций (X) будет иметь следующий вид Аналогично рассмотренному составляются таблицы для 8-местных функций если условия мультиветвления определ ны на наборах из восьми двоичных переменных:. X(Xi, Х, Xg, Х. Xj, Х, Х, XQ) Аналогично рассмотренному выполня ется мультиветвление и при реализаци функций устройства приоритета. Отличие заключается только в том, что операнд считывается не из ячейки накопителя, а из регистра заявок, не показанного на фиг. 1. Команда для этого не требуется, так как определение приоритетной заявки обычно выполняется . на микропрограммном уровне. Следует отметить, что в устройстве функция приоритета задается в виде таблицы, хранимой в накопителе. Позтому возможно задание любой функции и изменение заданных функций программным путем. Это обеспечивает гибкость и универсальность при существенной экономии аппаратурных затрат. Рассмотрим возможности организации в устройстве иерархической системы ёыявления приоритетных заявок. Одноступенчатая система позволяет определить приоритетную заявку не более, чём из 8-и соответственно принятому числу разрядов в регистре 12 операндов. Поэтому при большом числе абоненте, запрашиваюьчих ЭВМ, следует организовать иерархическую систему выявления приоритетных заявок. При этом двухступенчатая система позволит обслуживать 8 X 8 6 заявки, а S ступенчатая система 8 заявок. Возможности организации иерархической системы обслуживания заявок рассмотрим на примере двухступенчатой системы. Для ,этого все заявки следует разбить на 7 групп с определением функций прйоритётов F между группами и Fj внутри группы между заявками. Для приема заявок должны бь1ть регистры заявок (8 регистров по 8 разрядов) и регист групп заявок (8-ми разрядный), & котором фиксируется наличие заявок, отнесенных к соответствующим группам Выявление приоритетной заявки и пере ход к ее обслуживанию производится в две ступени. Сначала считывается регистр групп заявок и по его содержимому в соответствии с заданной функцией приоритетов FT выявляется группа заявок с наивысшим приоритегтом. Выполняется переход к ветви обслуживания этой группы заявок. Решение этой задачи осуществляется аналогично рассмотреному выше. Выбранная ветвь программы содержит команду считывания регистра заявок, соответствующего выбранной группе, и выполнения мультиветвления по его содержимому в соответствии с функцией приоритетов F. В результате осуществляется переход к одной из возможных 8-и ветвей программы, соответствующей обслуживанию заявки с наивысшим приоритетом в выбранной группе. Используемая при этом команда мультиветвления соответствует рассмотренной выше команде. Для выполнения разветвлений, соответствующих выявлению приоритетной заявки из возможных , потребуется 72 ячейки памяти для хранения адресов начальных команд (8 на первой ступени выбора и на второй втупени выбора) и 12 X 256 бит в сегменте таблиц из 256 ячеек для хранения таблиц 3- систем 8-местных функций. В первом сегменте начальных адресов размещаются 8 адресов команд мультиветвления по каждому из 8 регистров заявок. В каждом из следующих U-X сегментов по 16 ячеек хранятся адреса начальных команд 16-и программ обработки 1б-и заявок, в 2-х регистрах заявок (четном и нечетном) . Первая из систем 8-местных функций задает функцию приоритета групп заявок. Вторая система функций задает функцию приоритета заявок в группе и обеспечивает адресацию ячеек с номерами 0-7. Третья система функций задает функцию приоритета заявок в группе и обеспечивает адресацию ячеек с но- мерами 8-15. Указание необходимого сегмента начальных адресов осуществляется в команде мультибетвления в поле, которо- . му соответствует выход 9 регистра команд.4. Применение.предлагаемого устройства позволяет исключить достаточно сложную схему приоритета, обеспечивая при этом большую гибкость и универсальность, позволяет упростить программирование процессов с мультиветвленйями и уменьшить затраты ячеек блока памяти для хранения программ, позволяет увеличить быстродействия за счет убыстрения реализации мультиветвлений. 15 изобретения Формула 1. Устройство для организации мультиветвления процессов в электронной вычислительной машине, содержащее блок.памяти, регистр команд, блок микропрограммного управления и многоканальный коммутатор адреса, выход которого соединен с адресным входом блока памяти, а вход выбора номера канала соединен с первым выходом блока микропрограммного управления, первый вход которого является управляющим входом устройства, второй вход подключен к первому выходу регистра команд, информационный вход которог соединен с информационным выходом блока памяти, информационный вход которого является первым входом уст ройства, вход первого канала многоканального коммутатора адреса подключен к второму выходу регистра ко манд, входы второго канала соединены соответственно с третьим, четвер тым, пятым и шестым выходами регис ра команд, управляющие входы блока памяти, многоканального коммутатора адреса и регистра команд соединены с вторым выходом блока микропрограм много управления, отличающ ее с я тем, что, с целью повыше ния Производительности и экономичности, в него введены регистр резул тата, коммутаторы информации и регистр операнда, управляющие входы к торых соединены с вторы) выходом бл ка микропрограммного управления, ин формационные входы регистра операнд и.коммутаторов информации соединены с информационным выходом блока памяти, выходы коммутаторов информации соединены соответственно с входами регистра ре.зультата, выход которого-соединен с первым входом пят го канала многоканального коммутато адреса, первый выход регистра операнда подключен к первым входам третьего и четвертого каналов много канального коммутатора адреса, второй вход третьего канала которого соединен с вторым выходом регистра операнда, второй вход четвертого канала подключен к четвертому выходу регистра команд, третьи входы третьего и четвертого каналов многоканального коммутатора адреса подключены к шестому выходу регистра команд, четвертые входы соединены с вторым входом устройства, второй вход пятого канала многоканального коммутатора адреса соединен с пятым {ВЫХОДОМ регистра команд, третий вход является третьим входом устройства, входы кода номера канала коммутаторов информации соединены с третьим выходом регистра команд. 2.Устройство по п. 1, отличающееся тем, что блок микропрограммного управления содержит узел памяти микропрограмм, генератор тактовых импульсов, регистр адреса микрокоманд, регистр микрокоманд, дешифратор кода управления, модификатор адреса, первый вход которого является первым входом блока, первый вход регистра адреса микрокоманд является вторым входом блока, второй вход соединен с адресным выходом регистра микрокоманд, счетный вход регистра адреса микрокоманд подключен к выходу модификатора адреса, выход регистра адреса микрокоманд соединен с адресным входом узла памяти микропрограмм, информационный выход которого соединен с информационным входом регистра микрокоманд, выход кода управления которого соединен с информационным входом дешифратора кода управления, первый и второй выходы которого являются соответственно первым и вторым выходами блока, третий и четвертый выходы соединены соответственно с вторым вхрдом модификатора адреса и с третьим входом регистра адреса микрокоманд, тактовые входы узла памяти микропрограмм, регистра микрокоманд и дешифратора кода управления подключены к выходу генератора тактовых импульсов. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР N 638963, кл, G Об F , 1976. 2 Авторское свидетельство СССР If 6А0295, кл. G Об F 9/«6, 1976. 3.Таненбаум Э. Многоуровневая организация ЭВМ , М., Мир, 1979 (прототип).