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

"Мбиблиотека йЪДе ОПИСАНИЕ ИЗОБРЕТЕН ИЯ Союз СоветсюаСоциалистическихРеспублик(22) Заявлено 11.07.73 (21) 1941466/2 51) М. Кл.и 60679/00 присоединением заявки23) Приоритет Гасударственный омитет Сооотв Миотрав СССР оо делам иэобрвтеиий и открытий(72) Авторы изобретени В. Игнатущенко и Л. В. Караванова 71) Заявитель ена Л на институт проблем управлени СТРОИСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПОСЛЕДОВАТ ОДНОИМЕННЫХ ОПЕРАЦИЙ ЬНОСТЕ 1 2Изобретение относится к автоматике и , кальной шинами матрицы, распределитель, вы- явычислительной технике и предназначено длит ходы которого соединены с вертикальными определения последовательностей одноимен- шинами матрицы, пепи блокировки триггеров : ных операций в ветвях решаемых задач, Не- и цепь блокировки индикаторов ассоциативныхобходимость этого механизма возникает приячеек, выполненные на элементах ИЛИ и решении задач в многопроцессорных управ- НЕ.ляюших и вычислительных системах, в кото- Белью изобретения является повышение рых все процессоры могут вьшолнятьз один быстродействия устройства для определении и тот же момент времени только одну последовательностей одноименных операций. и ту же (одноименную) операцию над данны О В описываемом устройстве это достигается1ми, относящимися к различным параллельным тем, что выход индикатора совпадения,1-й гветвям одной задачи или разных задач ячейки ассоциативндй памяти соединен с соЭффективное совмещение одноименных опера- ответствующей горизонтальной шиной матриций в параллельных ветвях позволяет резко цы и со входом 1-го элемента ИЛИ цепи повысить производительность систем эа счет 1 к блокировки индикаторов, другой вход того жех уменьшения времени простоев процессоров. элемента "ИЛИ" соединен с выходом ( +1 ргИзвестно устройство для определения по- элемента ИЛИ" цепи блокировки индикаторов, слелователвнсстей опноименнмх оперений, соединенным через соответствующий элемент сопержа пее блок ассопиатнвной памяти со "Но со вхопом блокировки инпнкатора 1 й входным регистром, выходы которого соеди О ячейки ассоциат.я,вной памяти,выход цепи бло-,. нены с ячейками ассоциативной памяти этого кировки индикаторов соединен со входом расблока, каждая иэ которых содержит индика- пределителя,.выход Ьго триггера -го столбтор совпадения, матрицу триггеров, вход каж ца матрицы соединен со входом 1-го элемен, дого из которых соединен через элементИ", та "ИЛИ цепи блокировки триггеров -гос соответствующими горизонтальной и верти-ф 1.столбца матрицы, другой вход того же элек атор 7 ячейки 10 АП вырабатывает сигналсовпадения (поскольку в этой ячейке запи-сан код операции с первой ветви). Сигнал с цепи блокировки индикаторов включает цепьпродвижения распределителя 14, сигнал разрешения появляется на второй вертикальнойошине 15 (сигнал разрешения остается и на первой вертикальной шине 15), В результа те включаются триггеры 1, соответствующие ячейке 10 АП и соединенные через элементы И"2 с первой и второй вертикальны) ми шинами 15, Таким образом, возможно .совяешение операций "в и с первой ветви с одноименными операциями второй ветви, а также совмещение обеих ветвей только по ;операции "с.В четвертом цикле работы на входной ;регистр 13 подается кодследующей опе;рации второй ветви а. Включается инди,катор 7 ячейки 12 АП, в.которой записанкода. Сигнал с цепи блокировки индика например, при подаче(на входной регистр 13 щ1кода операции "в", включается индикатор 7ичейки 11 АП, что приводит к выключению .индикатора 7 ячейки 9, содержащей такжеиод операции в", оставляя для последующихсравнений операции, коды которых записаныи ячейках 8, 9 и 10 АП, Аналогично оргаиизуется цепь блокировки триггеров 1 запоминания совпавших операций. При включении,1 -го триггера 1 в данном цикле сравнеиия через элементы "ИЛИ 4 и НЕ 7, 3 запи авдаются схемы "И "2, блокируя входы тригге ров 1 от ( 1+1)-го до верхнего (см, фиг, 1),еоединенные с одной и той же вертикальнойшиной 15,При работе устройства на входной регистру13 подается код первой операции "в". Индикаторы 7 ячеек 9 и 11 АП вырабатываютсигналы совпадения, которые поступают вцаиь блокировки индикаторов, В результатеэтого индикатор 7 ячейки 9 АП выключается 60 5215673мейтаИЛИ соединен с выходом (-1)-го и на четвертую (снизу) горизонтальную шнэлемента "ИЛИ" цепи блокировки триггеров . ну 6 выдается сигнал совпадения. Имнул -, тего же столбца матрицы, соединенным че- сами продвижения распределителя 4 являрез соответствуюший элементНЕ", со вхо- ются сигналы с цепи блокировки индикатора;л элемента "И" -го триггера фго столб ров. Таким образом, при включении указан фЬ.матрипы, ных выше индикаторов распределитель 14подает сигнал разрешения на первую (слева)го устройства, когда одна з Р шийся на пересечении первой вертикальнойт йства когда одна из с авниваемыхветвейсодержит не более пяти операций,шины 5 и четвертой горизонтальной шины 16,а , гая - Йе более четы ех; на фиг. 2 - 10"устанавливается в и подает сигнал ввв с авнивае . е , Рцепь блокировки триггеров так что для повв с авниваеые ветви, в которых выполняются опе ации с именами а", в", "с",ф - , ванными через элементыИЛИ 4, НЕЗ иустройство содержит матрицу триггеров ,И 2 все триггеры, соединенные через элеи 2 НЕ 3 "ИЛИ" 4 и 5, "НЕ 6 16ме тменты И 2 с первой вертикальной шиной 15индикато ы совпадений 7 ячеек ассоциативФ Фтриггера. Следовательно, появляется возмож;: ной памяти АП 8-12, входной регисто 13,ность . совмещения операции горизонтальные шины 16 ЭлементыНЕ 3нивавмых ветвей.и ИЛИ 4 образу т цепь ро р а После к,ждого цикла рабо ы устройстваров 1. Элементы " Л р у, на индикаторы 7 всех ячеек АП подаетсяов . Элементы "ИЛИ"5 и "НЕ 6 образуютцепьблокировки индик Рди импудьс сброса (если индикатор содержит,ы 7 вы а тывают импульс при совпадениипомимо схемы совпадения, запоминаюшийкода операции, подаваемого на входной ре- элемент),гистр 13, с кодом, содержащимся вданнойВо втором цикле работы устройства навходной регистршвй операции второй ветви "е . Посколькуписываются в соответствуюшиФ ячейки 8-121 йн одна из ячеек АП не содержит кода е,блока ассоциативной памяти 17 так, что кодто ни один из индикаторов 7 не включается,последней операции ветви "М" записываетсяпоследней операции вв "Й э " 36 и .состояние распределители 14 не изменив я.ейку 8 (см. фиг. 2). Индикаторы 7 соется.вместно с элементамиИ 5 и "НЕ 6 обра.- еуют цепь блокировки, работаюшую так, что Отметим, что после появления раэрешаири включении -го индикатора 7 выключа-, юшего сигнала на какой-либо вертикальнойются (блокируются) индикаторы всех ячеек щ шине 15, этот сигнал остается на этой шиАП от ячейки 8 до (-1)-й, Это позволя не до конца сравнения всех операций второйет выбирать из нескольких одноименных опе ветви,раций ветви ту операцию, которая оставляет В третьем цикле работы на входной Рв 6 ольший ресурс для дальнейшегопоиска, Так, гистр 13 подается код операции с". Инди821567 6изооретения каторов соединен со входом распределителятвыход Х -го триггера-го столбпа матрицы соединен со входом-го элементаИЛИ пепи блокировки триггеров-го столб,па матрипы, другой вход того же элементаИЛИсоединен с выходом ( В -Х)-го эле-,мента ИЛИ пепи блокировки триггеров тохго же столбца матрипысоединенным черезсоответствующий элемент фНЕсо входом. элемента И 1,-го триггера-го столбпа1 матрипы. первой комбинации число совмещенных операций оказалось большим, то эта комбина, пия и выбирается для склеивания ветвей. Таким образом, устройство для сравнения ветви с числом операций Иъ с ветвью с числом операций й содержит 4 я ячеек АП и не болееразрядов распределителя и Ж И триггеров. Время полного сравне , нии обеих ветвей 1 не более д пиклов (тж т 0 в). бторов включает цепь продвижения распреде Ф о р м у л а лителя 14, сигналразрешения появляетсяна третьей вертикальной шине 15 (сигналы Устройство дляопределения последователь-. разрешения остаются на первой и второй . ностей одноименных опера, рцнй соде жащее вертикальных шинах 15). В результате боклюблок ассоциативной памяти со входным речаетоя триггер 1, соответствуюпптй ячейке 12 гистром, выходы которого соединены с ячейАП и соединенный через элемент И 2 с охами ассоциативной памяти этого бпокат третьей вертикальной шиной 15. Следова- каждая из которых содержитийдикаторсоэ-, тельно, возможно совмещение сравниваемых падения, матрицу 1 триггеро,т игге ввход каждого 1 ветвей только по операции "а", Триггеры 1,из которых соедйнен через элемент "И ссоответствующие той же ячейке 12 АП, но . 1, соответствующими горизонтальной и верти соедийениые через элементыИ 2 с первой калькой шинами матрипы, распределитель, и второйвеРтпальными шинами 151 не вклю выходы которого соединены с вертикальны чаются из-за наличия сигналов блокировки ми шинами матрицы, цепи блокировки триги триггеров, соединенных, через элементы й геров и цепь блокировки индикаторов ассо- И а а теын ы манама в вхпюченных в 1, 1 ннатнввых ачеек, выпоаневные ва евемевтах пр 6 Ьидущфк ииклах работы устройства; " . ИЛИ и фНЕ, о т л и ч а ю щ е е с ятем, чтс;сцелью повышения быстродейГаижм образом, несмотря на то, что в, ствия, выход индикатора совпадения обедах ветвях существуют три одноименныеячейки ассоциативной памяти соединен с"операции а .в и с" ветви могут быть соответствующей горизонтальной шиной мФшиной маъ 1 1совмещены в следующих комбинациях: по в рины и со входом-го элемента ИЛ и с; по сф; по "а, Совмещение вида "а, пепи блокировки индикаторов, другой вход "в", с" невозможно, таж как это не соо 1 х 1" того же элемента "ИЛИ" соединен с выхо/ д хветствует порядку выполнения операпий втэк,; дом, ( 1 +1)-го элемента ИЛИ пепирой ветви. ;Эбровки индикаторов 1 ,соединенным через соПосаедним этапом работы является очи ".ответствующий, элемент НЕ со входом бло , тыване кодов тех апррапий, по которым 1 кйровки индикатора В -й ячейки ассопФа-, возможно совмешеиие ветвей. Поскольку втивной памяти, выход пепи блокировки ииди