Устройство для определения последовательностей одноименных операций

 

к;

"М библиотека МАК т в

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

Союз Советснию

Социалистииесних

Республик (11) 521567 (61) Дополнительное к авт. свид-ву (22) Заявлено 11.07.73 (21) 1941466/24 с присоединением заявки № (23) Приоритет (43) Опубликовацо 15.07.76.Бюллетень № 2 (45) Дата опубликования описания 20.09.76 (51) М. КлР б06 «.9/00

Гасударственный «омнтет

Совета Мнннстрав СССР оо делам нэобретеннй

И OTKPblTN« (53) УДК 681.З25 (088. 8) (72) Авторы изобретения

В. В. Игнатущенко и Л. В. Караванова (71) Заявитель

Ордера Ленина институт проблем управления (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

ОДНОИМЕННЫХ ОПЕРАЦИЙ

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

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

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

Известно устройство для определения послеловаталвнсстей опноименнык оперений, солержащее блок ассопиатнвной памяти со

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

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

НЕ .

Целью изобретения является повышение быстродействия устройства для определении последовательностей одноименных операций.

В описываемом устройстве это достигается тем, что выход индикатора совпадения,t-й ячейки ассоциативндй памяти соединен с соответствующей горизонтальной шиной матрицы и со входом L-го элемента ИЛИ" цепи блокировки индикаторов, другой вход того же элемента "ИЛИ соединен с выходом (t +1)г< элемента ИЛИ" цепи блокировки индикаторов, соединенным через соответствующий элемент

"НЕ" со входом блокировки индикатора t,-й ячейки ассоциатьвной памяти, выход цепи бло-, кировки индикаторов соединен со входом распределителя, .выход -го триггера )-го столб,ца матрицы соединен со входом 1-го элемен, та "ИЛИ цепи блокировки триггеров g-ro

l-столбца матрицы, другой вход того же элек атор 7 ячейки 10 АП вырабатывает сигнал совпадения (поскольку в атой ячейке запи- сан код операции с первой ветви). Сигнал с цепи блокировки индикаторов включает цепь продвижения распределителя 14, сигнал разрешения появляется на второй вертикальной о шине 15 (сигнал разрешения остается и на первой вертикальной шине 15). В результа те включаются триггеры 1, соответствующие ячейке 10 АП и соединенные через элементы И"2 с первой и второй вертикальны-! ми шинами 15, Таким образом, возможно ..совмещение операций "в» и с первой ветI ви с одноименными операциями второй ветви а также совмещение обеих ветвей только по ,:операции "с .

В четвертом цикле работы на входной

;регистр 13 подается код)следующей опе;рации второй ветви "а . Включается инди.,катор 7 ячейки 12 АП, в.которой записан код а . Сигнал с цепи блокировки индикаl например, при подаче)на входной регистр 13 щ

1 кода операции "в", включается индикатор 7 ячейки 11 АП, что приводит к выключению . индикатора 7 ячейки 9, содержащей также

@on операции в", оставляя для последующих сравнений операции, коды которых записаны,д в ячейках 8, 9 и 10 АП. Аналогично оргамизуется цепь блокировки триггеров 1 запоминания совпавших операций. При включении, ф -го триггера 1 в данном цикле сравнения через элементы "ИЛИ 4 и НЕ 3 запи- у паются схемы "И "2, блокируя входы тригге; фов 1 от { +1)-го до верхнего (см. фиг. 1), . еоединенные с одной и той же вертикальной шиной 15.

При работе устройства на входной регистру 13 подается код первой операции "в". Индикаторы 7 ячеек 9 и 11 АП вырабатывают сигналы совпадения, которые поступают в щрнь блокировки индикаторов. Б результате а ого индикатор 7 ячейки 9 АП выключается 60

521567

5 мента "ИЛИ» соединен с выходом (t -1)-ro и на четвертую (снизу) горизонтальную шнэлемента "ИЛИ" цепи блокировки триггеров . ну 16 выдается сигнал совпадения. Имлул,—

I, тего же столбца матрицы, соединенным че- сами продвижения распределителя 14 являрез соответствующий элемент "НЕ", со вхо- ются сигналы с цепи блокировки нидикатодМл элемента "И" L-ro триггера го столб- б ров. Таким образом, при включении указан, 3ф мВтрицы. ных выше индикаторов распределитель 14 подает сигнал разрешения на первую (слева) щийся на пересечении первой вертикальной

T йства когда одна из с авниваемых

g шины 15 и четвертой горизонтальной шины 1 6, а,гая - Йе более четы ех; на фиг. 2 - 10 устанавливается в "1" и подает сигнал в (вв с авнивае.. е, р l цепь блокировки триггеров так что для повв с авниваелые ветви, в которых выполняются опе ации с именами а", в", "с", ванными через элементы "ИЛИ 4, НЕ"3 и

УстРойство содеРжит матРнцУ тРиггеРов, »И"2 е триг ры, соединенные че э элеэлементы И 2 "НЕ" 3 "ИЛИ" 4 и 5, "HE 6, Ы менты И"2 с первой вертикальной шиной 15 .индикато ы совпадений 7 ячеек ассоциатив» Ф триггера. Следовательно, появляется возмож;: ной памяти АП 8-12, входной регистр 13, ность. совмещения операци .и горизонтальные шины 16 Элементы НЕ» 3 нивавмых ветвей.

После каждого цикла работы устройства на индикаторы 7 всех ячеек АП подается ов . Элементы "ИЛИ"5 и "HE 6 образуют импульс сброса (если индикатор содержит, ы 7 вы а тывают импульс при совпадении помимо схемы совпадения, запоминающий кода операции, п »даваемого на входной реэлемент). гистр 13, с кодсм, шперк дантюй щ входной регистр швй операции второй ветви е . Поскольку писываются в соответствующими ячейки 8-12

»» йн одна из ячеек АП не содержит кода е, блока ассоциативной памяти 17 так, что код то ни один из индикаторов 7 не включается, последней операции ветви "М" записывается

m-состояние расцрвдвлитвля 14 не изменя

s я-ейку 8 (см. фиг. 2). Индикаторы 7 соется. вместно с элементами "И"5 и "НЕ 6 обра.эуют цепь блокировки, работающую так, что Отметим, что после появления раэрешвири включении -го индикатора 7 выключа-, ющвго сигнала на какой-либо вертикальной ются (блокируются) индикаторы всех ячеек щ шине 15, этот сигнал остается на этой шиАП от ячейки 8 до (i -1)-й. Это позволя I не до конца сравнения всех операций второй ет выбирать из нескольких одноименных опе ветви, раций ветви ту операцию, которая оставляет В третьем цикле работы на входной рв 6ольший ресурс для дальнейшего поиска. Так, гистр 13 подается код операции с . Инди521567

6 изооретени я

КатОРОВ СОЕДИНЕН CO ВХОДОМ РаСПРЕДЕЛИтЕЛЯв

1 . I выход i. -го триггера ) -го столбца матрицы соединен со входом t -го элемента

ИЛИ» цепи блокировки три1теров J -го cmm6»: ца матрипы, другой вход того же элемента

ИЛИ соединен с выходом (В -Х)-го эле-, мента ИЛИ цепи блокировки триггеров то го же столбца матрицы,,соединенным через соответствующий элемент»HE со входом . элемента «И» 1,-го триггера j-ro столбпа

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

Таким образом, устройство для сравнения ветви с числом операций 11 с ветвью с числом операций t1 содержит 4m ячеек

АП и не более разрядов распределителя и Ю" tt тржтеров. Время полного сравне«, НИИ ОбЕИХ Вэтне| Н8 бОЛЕЕ Гв ЦИКЛОВ (Tax«« тОв). б торов включает цепь продвижения распреде, ф о р м у л а лителя 14, сигнал разрешения появляется на третьей вертикальной шине 15 (cm-палы Устройство для ) определения последователь.. разрешения остаются на первой и второй . ностей одноименных операций, содержащее ве икальных шинах 15). В результате дщю блок ассоциативной памяти со входным ре- r чается триггер 1, соответствующий ячейке 12 I ècòpoì, выходы которого соединены с ячей-1

АП и соединенный через элемент»И"2 с . охами ассоциативной памяти этого блока, третьей вертикальной шиной 15. следова- каждая из которых содержит|ийдикатор(сои-, т игге в, вход каждого тельно, возможно совмещение сравниваежых падения, матрицу 1 триггеро, ветвей только по операции "а". Триггеры 1, из которых соедйнен через элемент И" с . соответствующие той же ячейке 12 АП, но . (, соответствующими горизонтальной и верти соедийениые через элементы И 2 с первой калькой шинаМи матрицы, распределитель, и второй веРт п альными шинами 15, не вклю выходы которого соединены с вертикальны

ы епи бло нровки тригчаю ся из-за наличия сигналов блокировки ми шинами матрицы, цепи т гро риг н х е Teat хы ыннвмн н вхпюченных в 1,:,. кнетнвных вчеек, выпопненные нв епементвх прМыдуаак циклах работы устройства.- " . ИЛИ" и "НЕ", о т л и ч а ю щ е е с я е тем, чтс ;с целью повышения быстродей ®ижм обРазом. несмотря на то, что в; ствия, выход индикатора совпадени обеяк ®етвях сущес вуют три одноименные,: ячейки ассоциативной памяти соединен с - . опефации а в и с В8ТВН могут быть cooTBeTCTB 1681 горизонтальной шинОй Ф шиной маъэ емента ИЛИ" ледующих комбинациях по B. Рицы и co BxogoM .го элемента и с; по c»; no а . Совмещение вида "e»,- цепи блокировки индикаторов, другой вход невозможно так как это не соор " того же элемента ИЛИ соединен с в тх

» ° н с выхоФ тствуе™орядку выполнения .операций вто- ; дом (, +1 у-го элемента ИЛИ пепи рой ветви, (po < индикаторов, соединенным через соФ

° ° » cue«BM этапом Работы является очи - .. l Ответствующий элемент HE со входом бло, тыва не кодов тех операций, по которым. кйровки индикатора -й ячейки ассой(а; возможно совмешение ветвей. Поскольку в: тивной памяти, выход цепи блокировки няди (, ° >r I 1 . I! > Jil j, (y " llf B

Редакюу Л. Твуаиж II.

Задсав 4789/527 и л Лсченбваве

МНИИ11И Гес щ рствí íí: tа i«» т д, ;:;и-"м Мик@® вуов СССР

МЮ Д ИИ & t :, 4 ) 4 i,,, " Т r s в tf 6 И У Г г ф)И Т Ий

11З035, p4eewsa, . Ф -."5 ° t лу.и(:кем млб., л. 4/,Ч б» Я

Филиал ППП Илтевч, i . Уме мума, уа. Йреектеам, 4