Устройство обработки данных

СООЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 80123972 06 Г 15/О ИСАНИЕ ИЗОБРЕТЕНИ АВТОРСК СВИДЕТЕЛЬСТВ 24(54) УСТРОЙСТВ (57) Изобретен вычислительной использовано д реальном масшт изобретения яв Бюл. У 23ев, С.М. Окулов.СССР 1980 ССР 1981.Исвидетельство11 С 15/00,идетельство С11 С 15/00,Попова Г.Ициативного пления и конт оцессораоля.1981,етики. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) АвторскоеУ 771719, кл. САвторское свВ 883972, кл. САбрамова Н.Апользование ассв системах упраСб. Вопросы кибс, 111. изводительности целью в устройс ной регистр, бл мяти, блок синх тор строк, введ коммутатор усло зации включает триггер, элемен одновибратора. ОБРАБОТКИ ДАННЫХ е относится к области техники и может быть я обработки данных в бе времени, Целью, яется увеличение проустройства. С этой тво, содержащее входок ассоциативной паронизации и дешифраены блок триггеров и вий, а блок синхронигенератор импульсов, т И, счетчик и два 1 з,п. ф-лы, 8 ил.1239725 Составитель Г, ВиталиевТехРед О.сопко Корректор И Муска Редактор Е. Папп Тираж б 71 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб д. 4/51239725 Изобретение относится к вычислительной технике и может быть использовано для обработки данных в реаль-ном масштабе времени.Цель изобретения - увеличение производительности устройстваНа фиг. 1 представлена структурная схема устройства обработки данных," на фиг, 2 - функциональная схемаэлемента ассоциативной памяти; на 16фиг 3 - функциональные схемы блокатриггеров и регистра маски; на Фиг.4Функциональная схема блока.синхронизации; на Фиг. 5 - функциональнаясхема коммутатора условий; на Фиг,6 - 15,Функциональная схема дешифраторастрок; на Фиг, 7 - временные диаграммы работы устройства; на фиг. 8 - алгоритм работы устройства.ЮУстройство обработки данных(Фиг. 1) содержит входной регистрблок 2 ассоциативной памяти, состоящий из элементов 3, регистр 4 маски,блок 5 триггеров, блок 6 синхронизации, коммутатор 7 условий, дешифратор 8 строк и имеет шины 9 и 10 записи, шины 11 и 12 считывания-записи,шины 13 и 14 сброса. Информационныйвход и выход регистра 1 соединеныЗОсоответственно с информационным входоМ устройства и информационным входом блока 2, Вход маски и информационный выход блока 2 пОдключены соответственно к выходу регистра 4 и инфор-мационному выходу устройства, Инфор- З 5Вмационный вход, первый, второй и третий информационные выходы коммутатора 7 соединены соответственно с выхо"дом сравнения блока 2, информационным входом дешифратора 8, синхровхо- фдом блока 5 и входом начальной установки блока 6. Вход пуска и первыйвыход блока 6 подключены соответственно к информационному входу устройства и синхровходу регистра 1, крометого, первый, второй и третий выходыблока 6 соединены соответственно свходом сброса регистра 4, управляющимвходом коммутатора 7 и управляющимвходом дешифратора 8, Первый, второйи третий выходы дешифратора 8 подклю,чены соответственно к синхровходу ивходу установки регистра 4 и входусброса блока 5, а выход последнегосоединен с информационным входом регистра 4.Элемент 3 блока 2 (фиг. 2) содержит первый и второй элементы И"ИЛИ 215 и 16, два .триггера .17 и 18, дв .элем"нта НЕ 19 и 20, третий и че.вертый элементы И-ИГА 21 и 22, четыреэлемента И 23-26, два элемента ИНИ27 и 28 и имеет информационные входы29-32 и выход 33, управляющие входы34-39, информационные входы 40-42 ивыходы 43-45.Регистр 4 маски (Фиг. 3) содержитдва элемента ИЛИ 46 и 47, два элемента И 48 и 49, элемент И-НЕ 50 и шестьтриггеров 51-56,Блок 5 триггеров (фиг. 3) содергзгт триггер 57 и три элемента И 58-60,.Блок 6 синхронизации (Фчг. 4)содержит триггер 61, генератор 62импульсов, элемент И 63, счетчик 64и два одновибратора 65 и 66,Коммутатор 7 условий (Фиг, 5)содержи,. и групп, каждая из которыхсодержит элемент И 67, два элементаИЛИ 68 и 69 идва элемента И 70 и 71.Дешифратор 8 строк (фиг, 6) содержит элементы И 72-89 и элементы ИгИ90-93,1 Временные диаграммы на фиг 7 отображают посгедовательность 94 кодов, поступающих на регистр 1 (изображаются в виде импульсов), последовательность 95 открытых и закрытых состояний входов в регистре 1 последовательность 96 импульсов на ",ьг;.од триггера 61 блока 6, длительность и:- пульса Лопределяет время выполнения микрооперации поиска в блоке 2, импульс 97 Формируемый на вь:ходе счетчика 64 в блоке 6 при работе устройства, определяет время микроопера ций записи-считывания и поиска в блоке 2 тактовые импульсы 98 и 99 (7 И 1 и ТИ 2) длительностьюна выходе соответственно одновибраторов 65 и 66 блока 6, состояния 100 и 101 выходов триггеров 51-56 регистра 4, импульс 102 сброса,. Формируемый на первом выходе коммутатора .При формировании из элементов 3 ассоциативной матрицы размером гп и вьгходы 43-45 каждого элемента 3 соединяются соответственно с входами 40-42 соседнего справа элемента 3, а информационный выход 33 - с информационным входом 29 соседнего снизу элемента 3, При. этом управляющие входы 34-39 являются общими для всех элементов 3, образующих строку, а информационные входы 30-32 - общими для всех элементов 3, образующихПервый случай - А ", = Х + 1 в 1 с-й строке блока 2. Тогда согласно (1) сигнал Х = 1 с входа первого элеНмента 3 через элементы 21 проходит на выход 43 ш-го элемента 3 1-й стро 1ки блока 2, те, Е =1, Ев=17 =О. После этого дешифратор 8 по 1 с-й стро ке согласно (6) Формирует сигнал "1" на шине 13, который поступает на триггер 53 к-го модуля регистра 4. Сигналом " 1" на вь 1 ходе этого триггера, поступающим на входы 38, сбрасываются триггеры 17 элементов 3 1 с-й строки блока 2, Через некоторую задержку 7 определяемую длительностью ТИ 1, сигнал "1" появляется на шине 9 и через элемент 46 поступает на вход триггера 51 1 с-го модуля регистра 4, а с вы- " хода этого триггера - на входы 34 элементов 3 1-й строки. Таким образом, значение Х записывается на место А " т,е, числовой интервал в 1-й строке увеличивается на "единицу" зансчет уменьшения значения А20 Второй случай - А в = Х - 1 в К-й строке блока 2Тогда согласно (2)Я и подобно первому случаю сигнал 7 впоявляется на выходе 45 ш"го элемента 3 этой строки, а 7 = Ч = О, После этого дешиФратор 8 согласно (7) по 1-й строке Формирует сигнал на шине 14, а через время 1," - на шине 10, На выходах триггеров 54 и 56 -го модуля регистра 4 устанавливаются сигналы 1которымк через соответствующие входы 35 и 39 производится сброс триггеров 18 элементов 3 Е-й строки блока 2, а затем - запись значения Х на место А. Таким образом числовой интервал в 1 с-й строопределяемое длительностью микрооперации поиска в блоке 2, которая выполняется только в строках, где показана маска 2, = Ев = 1 7 = О, По истечении времени 61, на выходесчетчика 64 появляется сигнал "1", по которому в блоке 6 сбрасывается триггер 61, одновибраторы 65 и 66 вырабатывают соответственно сигналы ТИ 1.и ТИ 2, а в коммутаторе 7 открываются 10 элементы 70 и 71. Результатом поиска1являются значения 7, Хв, Ч на выходах 43-45 элементов 3 ш-го столбца блока 2. В зависимости от совокупности этих значений различают несколько случаев Дальнейшей обработки двоичного числа, хранящегося на регистре 1. 75бке увеличивается на "единицу" за счет увеличения значения А.ИТретий случай - АХ - 1, Ас Х+ + 1 в 1 с-й строке блока 2., Тогда согласно (1)-(3) на выходах 43-45 ш-го элемента 3 Е - й строки появля;отся сигналы 7. = "7 =: 7, = О, т.". значение двоичного числа Х попадает в чксло 1 вой,интервал, заданный границами А, А, включая и сами границы. В результате согласно (5) с выхода элемента 70 коммутатора 7 на вход блока 6 поступает сигнал 1 , по которому в блоке 6 сбрасывается счетчик 64 и Формируется сигнал сброса элементов памяти регистра 1 и регистра 4. После этого открывается вход регистра 1 для приема следующего двоичного числа Х, - Четвертый случай - Ав с Х - 1 илк А ) Х + 1 в Е-й строке блока 2 Пред"в положим что значение Х - " .= А илиН1 Х + 1 = А, не во всех элементах 3 (разряда ), а лишь в нескольких (старших), после них имеется элемент 3, в которомав = О,М = 1, 7 = 1,что ривсдит согласно (2) к появленкк 11сигнала Е = О на выходе 45 этогоВэлемента 3, т.е, сигнал в цепи Евисчезает. Однако согласно (3) на выходе элемента 26, а соответственно и на выходе элемента 28 данного эле/мента 3 появляется сигнал Ч = 1, который по цели Ч проходит до выхода 44 ш-го элемента 3 Е-й строки, Еслиже сигнал 17 . =: 1 на выходе ш-го элемента 3 не появляется при исчезновении сигнала в цепи Е 1 с-й строки, что возможно при О = 1,х = Ор 2 внто он появляется при д "= 1, К = О, 7, = 1 на выходе элемента 28 одного из последующих элементов 3, а следовательно, и в цепи 7 Е-й строки. Сигнал 7 -.= 1 на выходе 44 ш-го элемента 3 к-й строки указывает на то, что значение Х не принадлежкт числовому интервалу, хранящемуся в этой строке и не может быть к нему присоединено корв нректировкой границ А , А , так как отличается от них больше, чем на "единицу" Если на выходах 43-45 всех элементов 3 ш-го столбца блока 27,=. О, Ч = 1, Ев = О, то согласно (4) на выходе элемента 71 коммутатора 7 появляется сигнал "1", которьп проу.ходит через элемент 59 блока 5, соответствующего отмеченной строке блока 2, а в регистре 4 - через элементы .46 и 47 на вьгод триггеров 51 и 56.7 12397Появление сигнала "1" на входах 34 и 35 элементов 3 разрешает запись значения Х в триггеры 17 и 18 отмеченной строки блока 2, Таким образом, в первой свободной строке блока 2 фор мируется новый числовой интервал сн вграницами А = А = Х. После этого в блоке 5 снова отмечается первая свободная строка.Пятый случай - А = А - 1 в 1-й 10нстроке а А = Х + 1 в (1 с+Й) - й строф кеке блока 2, где к. = 1, ш - 1 с, а ш1 с. Тогда согласно (2) на выходе 45 ш-го элемента 3 1-й строки появляетсясигнал Е = 1, а согласно (1) на вы ходе 43 т-го элемента Ь+б)-й строки1сигнал Е = 1, При этом значения 5 и Сц на соответствующих выходах коммутатора 7 определяют порядок следования строк, в К-й строке 5 к = О, 0= 1, 20 а в (1 с+О-й строке Ь,= 1, ек,= О. Тогда согласно (8) и (9) появляются сигналы " 1" на шине 11 по ТИ 1, а следовательно, на выходе триггера 52 Е-го модуля регистра 4 и входе 36 25 первого элемента 3 к-й строки, на шине 13, а следовательно, на выходе триггера 53 Ь+к)-го модуля регистра 4 и .входе 38 первого элемента 3 Ь+1)-й строки блока 2, По этим сигнкалам значение Ак с выходов триггеров.17 Е-й строки поразрядно через элемен ты 23 поступает в цепи переноса по столбцам (элемент 27),а значение А, сбрасывается, Через некоторое время, определяемое величиной , по ТИ 2, /Ъю35 возникают сигналы "1" на шинах 13 и 14, по которым сбрасываются триггеры 17 и 18 в элементах 3 к-й строки блока 2, а также триггер 57 Е-го модуля 40 блока 5. Причем, если значение М меньше номера первой свободной строки блока 2, то 1-я строка помещается в блоке 5, как первая свободная. Одновременно возникает сигнал "1" на шине 11, а соответственно, на выходе триггера 52 %+1)-го модуля регистра 4, по которому разрешается запись в триггеры 17 элементов 3 (1+1)-й строки блока 2 (поразрядно) значения А, .50 Таким образом, происходит объединение двух числовых интервалов, хранящихся в Е-й и В+1)-й строках блока 2, в один новый, записываемый в %+1)-ю блока 2.Если А = Х + 1 А = Х - 1 в строяк ф к+вках блока 2, то новый числовой интервал также формируется в (к+В)-й стро 25 8ке, но корректируется уже значение ефА , При этом с выхода дешифратора 8 кЕ11 1поступают сигналы 1 для Е-й строки на шины 12 - 14, а для (1+к)-й строки - на шины 12 и 14.Во всех рассмотренных случаях сигналы "1" на выходах дешифратора 8 и элементов 70 и 71 коммутатора 7 появляются только тогда, когда счетчик 64 в блоке 6 достигает значения Ьй По окончании корректировок границ интервалов в операции поиска в строках. блока 2 (случаи 1, 2, 4 и 5) на выходах 43-45 ш-го элемента 3 строки, в которую производилась запись, появ 1ляются сигналы Е = 7 = Ев = 0 (по-добно случаю 3), Тогда согласно (5) с выхода элемента 70 коммутатора 7 на вход блока 6 поступает сигнал "1", по которому сбрасывается счетчик 64 и формируется сигнал сброса элементов памяти регистра 1 и регистра 4. После этого открывается вход регистра 1 для приема следующего двоичного числа Х.Формула изобретения.1, Устройство обработки данных, содержащее входной регистр, блок ассоциативной памяти, блок синхронизации и дешифратор строк, причем информационный вход и выход входного регистра соединены соответственно с информационным входом устройства и информационным входом блока ассоциативной памяти, вход маски и информационный выход которого подключенысоответственно к выходу регистра маски и информационному выходу устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения производительности, оно содержит блок триггеров и комму- . татор условий, информационный вход, первый, второй и третий информационные выходы которого соединены соответственно с выходом сравнения блока ассоциативной памяти, информационным входом дешифратора строк, синхровходом блока триггеров и входом начальной установки блока синхронизации, вход пуска и первый выход блока синхронизации подключены соответственно к информационному входу устройства и синхровходу входного регистра,кроме того, первый, второй и третий выходы блока синхронизации соединены соответственно с входом сброса реги9 1239725 стра маски, управляющим входом ком- че мутатора условий и управляющим входом ка дешифратора строк, первый, второй и ра третий выходы которого подключены вт соответственно к синхровходу и входу 5 тр установки регистра маски и входу ки сброса блока, триггеров, а выход бло- кл ка триггеров соединен с информацион- бл ным входом регистра маски. вх 102, Устройство по п.1, о т л и - . ч а ю щ е е с я тем, что блок синхронизации содержит генератор импульсов, триггер, элемент И, счетчик и два одновибратора, причем входы пер вого и второго одновибраторов подклю 1 Оны соответственно к выходу счетчии первому выходу первого одноь 1 б-,тора, второй выход которого и выходорого одновибратора соединены сетьим выходом блока, вход установвход сброса и выход триггера подючены соответственно к входу пускаока выходу счетчика и первомуоду элемента И, второй вход и выход которого соединены соответственно с выходом генератора импульсов и счетным входом счетчика, выход счетчика соединен с вторым выходом блока, а вход установки счетчика подключен к входу начальной установки и первому выходу блока.