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

 

Изобретение относится к области вычислительной техники и может быть использовано для обработки данных в реальном масштабе времени. Целью, изобретения является увеличение производительности устройства. С этой целью в устройство, содержащее входной регистр, блок ассоциативной памяти , блок синхронизации и дешифратор строк, ввЁдены блок триггеров и коммутатор условий, а блок синхронизации включает генератор импульсов, триггер, элемент И, счетчик и дв& одновибратора. 1 з.п. ф-лЬ1, 8 ил-. с СО с ND СО со ,41 isd СП

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК g g G 06 F 15/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМ,К СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3685126/24-24 (22) 04.01.,84 . (46) 23.06.36. Б . 9 23 (72) А.П. Малышев, С.M. Окулов и А.Я. Волков (53) 681 ° 325(088.8) (56) Авторское свидетельство СССР

У 771719, кл. G 11 С 15/00, 1980

Авторское свидетельство СССР

В 883972, кл. G 11 С 15/00, 1981.

Абрамова Н.А., Попова F.È. Использование ассоциативного процессора . в системах управления и контроля.

Сб. Вопросы кибернетики. — И.: 1981, с. 111..„Я0„„1239725 А1 (54) УСТРОЙСТВО ОБРАБОТКИ ДАННЫХ (57) Изобретение относится к области вычислительной техники и может быть использовано для обработки данных в реальном масштабе времени. Целью, изобретения является увеличение производительности устройства. С этой целью в устройство, содержащее входной регистр, блок ассоциативной памяти, блок синхронизации и дешифратор строк, введены блок триггеров и коммутатор условий, а блок синхронизации включает генератор импульсов, триггер, элемент И, счетчик и два одновибратора. 1 з.п. ф-лы, 8 ил.

1239725

Изобретение относится к вычислительной технике и может быть использовано для обработки данных в реаль- ном масштабе времени.

Цель изобретения — увеличение производительности устройства., На фиг. 1 представлена структурная схема устройства обработки данных; на фиг. 2 — функциональная схема элемента ассоциативной памяти; на 16 фиг„ 3 — функциональные схемы блока триггеров и регистра маски; на фиг.4 функциональная схема блока.синхронизации; на фиг. 5 — функциональная схема коммутатора условий; на фиг,6 — 15, функциональная схема дешифратора строк; на фиг. 7 — временные диаграммы работы устройства; на фиг. 8 — алгоритм работы устройства. б

Устройство обработки данных (фиг. 1) содержит входной регистр 1, блок 2 ассоциативной памяти, состоящий из элементов 3, регистр 4 маски, блок 5 триггеров, блок 6 синхронизации, коммутатор 7 условий, дешифратор 8 строк и имеет шины 9 и 10 записи, шины 11 и 12 считывания-записи, шины 13 и 14 .сброса. Информационный вход и выход регистра 1 соединены

30 соответственно с информационным входоМ устройства и информационным входом блока 2. Вход маски и информационный выход блока 2 подключены соответственно к выходу регистра 4 и инфор- мационному выходу устройства, Инфор- З5 мационный вход, первый, второй и третий информационные выходы коммутатора 7 соединены соответственно с выходом сравнения блока 2, информационным входом дешифратора 8, синхровхо- @ дом блока 5 и входом начальной установки блока 6. Вход пуска и первый выход блока 6 подключены соответственно к информационному входу устрой ства и синхровходу регистра 1, кроме того, первый, второй и третий выходы блока 6 соединены соответственно с входом сброса регистра 4, управляющим входом коммутатора 7 и управляющим входом дешифратора 8, Первый, второй и третий выходы дешифратора 8 подклю.чены соответственно к синхровходу и входу установки регистра 4 и входу сброса блока 5, а выход последнего соединен с информационным входом регистра 4.

Элемент 3 блока 2 (фиг. 2) содер" жит первый и второй элементы И-ИЛИ

15 и 16, два .триггера .17 и 18, дв . элем.нта НЕ 19 и 20, третий и че-:вертый элементы И-KIN 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) содержит триггер 5? и три элемента И 58-60, Блок 6 синхронизации (фчг. 4) с.одержит триггер 61. генератор 62 импульсов, элемент И 63, счетчик 64 и два одновибратора 65 и 66, Коммутатор 7 условий (фиг. 5) содержи .. n г р у п п,, к аж .д,а я Hиз которых содержит элемент И 67, два элемента

ИЛИ 68 и 69 и два элемента И 70 и 71.

Дешифратор 8 строк (фиг. 6) содержит элементы И 72-89 и элементы ИЛ4

90-93, 1

Временные диаграммы на фиг,. 7 отображают посгедовательность 94 кодов, поступающих на регистр 1 (изображаются в виде импульсов), после-довательность 95 открытых и = акрытых состояний входов в регистре 1, пос едовательность 96 импульсов на вьг;-оц триггера 61 блока 6, длительность «и::пульса А t< определяет время выполнения микрооперации поиска в блоке 2, импульс 97,, формируемый на выходе счетчика 64 в блоке 6 при работе устройства, определяет время микроопер--:-ций записи-считывания и поиска в блс-ке 2„ тактовые импульсы 98 и 99 (ТИ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, образующих

1239725 столбец блока 2. Информационные ды 29 элементов 3 первой строки жат устано. очными входами блока

Элемент,3 блока 2 реализует дующие логические функции: вхослу2. сле10

35 (4) ! <

z =z 0 v н,на выходах 43-45 всех элементов 3

m-го столбца блока 2 и

Ен Ев (5) на выходах 43-45 одного из элементов

3 m-го столбца блока 2, Дешифратор 8 формирует управляю щие сигналы на шинах 9-14 для каждой строки блока 2 по состоянию выходов

43-45 элементов 3 m-ro столбца блока

2 и выходов коммутатора 7 (b<, b ...

° ° ° р ) у ° ° ° th<< у С< р С t ° ° ° s Cks ° т ° < Сн) °

Управляющие сигналы на шинах 9-14 возникают при выполнении условий

Ен 1 в Ък ск О (6) или Е = у = О, 2в = 1, bk=c„= О (7) или 2н 1, Е = V = ОэЪк= 1,С„=О (8) или Е„= < = О, Zв 1,Ъ„= О,с„= 1 (9) на выходах 43-45 m-ro элемента 3 k-й

Z н=7,„(5 х

Z V,Å вЂ” обозначают соответственно выходы 43-45 элемента 3; н в а,а — значения разрядов (триггеры 17 и 18) сон ответственно нижней А„ в и верхней А „ границы числового интервала в k-ой строке блока ?, Ак <к як «к .в в в в

А =а,а,...,а,,к, k=1п;

k <к 2К 25

Х+, х — значения разрядов Х + 1, Х вЂ” 1 (информационные входы 31 и 32), полученные соответственно при сложе нии и вычитании "единицы" из двоичного числа Х = Х,, Х . .к (информаци- 30 онные входы 30), Х + 1 = х,, х,..., <

Ь

Х, Х - 1 =x<,х,,...,х„„.

ITl

Коммутатор 7 позволяет провести анализ условий строки блока 2 и k-х выходах коммутатора 7.

Устройство работает следующим образом.

Допустим, что в некоторых строках блока 2 хранятся числовые интервалы, заданные верхней А и нижней А" границами, а следовательно, в соответствующих этим строкам модулях блока 5 на выходе триггера 57 присутствует сигнал "1". Первоначально проводится подготовка устройства к работе подачей сигналов "0" на установочные входы блоков 2, на третьи входы элементов 68 и 69 соответственно первой и и-й групп коммутатора 7, сигналов

"1" на установочные входы регистра 4, блока 5, на второй вход элемента 67 первой группы коммутатора 7. При этом в блоке 5 помечается первая незанятая строка блока 2, а на входы 40-42 первых элементов 3 строк блока 2, занятых информацией, с выходов элементов 48-50 соответствующих Модулей регистра 4 подаются сигналы Z „ = Ев =

1, Ч = О.

Первая свободная строка блока 2 определяется следующим образом, ПриMFM что строки блока 2 с первой по (k — 1)-ю заняты информацией (на выхо-, де триггера 57 модулей с первого по (k — i)-й блока 5 присутствует сигнал " 1"), k-я строка свободна, а состояние остальных строк безразлично.

Тогда сигнал "1" от установочного входа блока 5 распространяется по элементам 60 до k-ro модуля, где на выходе триггера 57 присутствует сигнал "0"<, а на инверсном выходе элемента 60, а также на двух входах элемечта 59 — сигнал "1". Таким образом, только в k-м модуле подготавливаются условия для записи, которая производится при появлении сигнала "1";. на первых входах элементов 59 всех модулей блока 5.

С приходом на регистр 1. двоичного числа входы этого регистра закрываются на время обработки поступившего кода (позиция 95 на фиг. 7) . В регистре 1 выполняются операции сложения и вычитания константы "1" из поступившего двоичного числа Х, а величины Х, Х +1, Х вЂ” 1 хранятся на специальных регистрах, выходы которых соединены соответственно с входами

30-32 блока 2 поразрядно. В блоке 6 запускается счетчик 64 на время да<, определяемое длительностью микрооперации поиска в блоке 2, которая выполняется только в строках, где показана маска ZI, = ZI, = 1, V = О. По истечении времени II,tf на выходе счетчика 64 появляется сигнал "1", пс которому в блоке 6 сбрасывается триггер 61, одновибраторы 65 и 66 вырабатывают соответственно сигналы TNI и ТИ2, а в коммутаторе 7 открываются 1« элементы 70 и 71. Результатом поиска

f . 1 являются значения 7„, Хе, V «a zIIходах 43-45 элементов 3 m-го столбца блока 2. В зависимости от совокупности этих значений различают несколько случаев Дальнейшей обработки двоичного числа, хранящегося на регистре 1.

Первый случай — A = Х + 1 в 1с-й строке блока. 2. Тогда согласно (1) сигнал Z = 1 с входа первого элеН мента 3 через элементы 21 проходит на выход 43 тп-го элемента 3 k-й строI ки блока 2, т,е. 2 = 1, Е, = 17 =. О.

После этого дешифратор 8 по k-й стро- 2 ке согласно (6) формирует сигнал "1" на шине 13, который поступает на триг-. гер 53 k-ro модуля регистра 4. Сигналом " 1" на вь1ходе этого триггера, поступающим на входы 38, сбрасываются триггеры 17 элементов 3 k-й строки блока 2, Через некоторую задержку 7 определяемую длительностью ТИ1, сигнал "1" появляется на шине 9 и через элемент 46 поступает на вход тригге2 ра 51 k-го модуля регистра 4, а с вы- о хода этого триггера — на входы 34 элеме«тов 3 k-й còðîêè. Таким образом, значение Х записывается на место А " т.е. числовой интервал в 1<-й строке увеличивается на 1единицу11за н счет уменьшения значения А „

Вт рой случай — А = Х вЂ” i в k-й строке блока 2 ° Тогда согласно (2)

) и подоб«о первому случаю сигнал 7 появляется на выходе 45 m-гс эле-! мента 3 этой строки, а 7„ -- V = О.

После этого дешифратор 8 согласно (7) по k-й строке формирует сигнал на шине 14, а через время f, — на шине 10. На выходах триггеров 54 и

56 k-гс модуля регистра 4 устанавливаются сигналы "1", которыми через соответствующие входы 35 и 39 производится сброс триггеров 18 элементов

3 k-й строки блока 2, а затем — запись значения Х на место А . Таким I образом числовой интервал в k-й стро7?5 б ке увеличивается на "единицу" за счет

8 увеличе«ия значения А„. в"

И

Третий случай — А „> Х вЂ” 1, А „с Х +

+ 1 в k--й - òðîêå блока 2, Тог,д,а соглас«с (I)-(3) на выходах 43 — 45 ш-го элемента 3 k — и строки появля.отся curf налы 7.„= "! =: 7, = О, т . значение двои:ного числа Х попадает в числоLI вой,интервал, заданный границами A, A„, включая и сами границы. В результате согласно (5) с выхода элемента

70 коммутатора 7 на вход блока б поступает сигнал 1, по которсму в блоке 6 сбрасывается счетчик 64 и формируется сигнал сброса элементов памяти регистра 1 и регистра 4. После этого открывается вход регистра I для г.-риема следующего двоичного числа Х. — Четвертый случай — А в с Х вЂ” 1 или

А ) Х + 1 в k-й строке блока 2„Пред«

"в положим что значение Х вЂ” ".=- А или

Н

Х + 1 = А, не во всех элементах 3 (разрядя ), а лишь в нескольких (старших). после них имеется элемент

3, в которомс = 0 х = 1, Z = 1 1то

«ривсдит согласно (2) к появлению

1 сигнала Z = О на выходе 45 э гого

8 элемента 3, т.е, сигнал в пепи Z e, исчезает. Однако согласно (3) на выходе элемента 26, а соответственно и на выходе элемент- 28 данного эле/ мента 3 появляется сигнал V = 1, ксторый по цели Ч проходит до выхода

44 m-ro элемента 3 Е-й строки. Если

1 же сигнал 17 . =- 1 на выходе и-го элемента 3 не появляется при исчезновении сигнала в цепи ZB 1с-й строки, что воз 1окнс при и = 1, х = О, Ев = 1, I тс он появляется при а "= 1, X = О, Z, = 1 на выходе элемента 28 одного из последующих элементов 3, а следовательно, и в цепи V k-й строки. Curf нал 7 == 1 на выходе 44 m-го элемента

3 k-й строки указывает на то, что значение Х не принадлежит числовому интервалу, хранящемуся в этой строке и не может быть к нему присоединено корв « ректировкой границ А „, A так как отличается от них больше, чем на "единицу". Если на выходах 43-45 всех элементов 3 m-xo столбца блока 2

Z О, V = I, Z = О, то согласно (4) «а выходе элемента 71 коммутатора

7 появляется сигнал "1", которьп! про ходит через элемент 59 блока 5, соответствующего отмеченной строке блока

?, а в регистре 4 — через элементы .

46 и 47 на вьг<од триггеров 51 и 56.

7 12397

Появление сигнала "1" на входах 34 и 35 элементов 3 разрешает запись значения Х в триггеры 17 и 18 отмеченной строки блока 2. Таким образом, в первой свободной строке блока 2 фор- 5 мируется новый числовой интервал с н в границами А = А = Х. После этого в блоке 5 снова отмечается первая свободная строка.

Пятый случай — А = А — 1 в k-й 10 н к строке а А = Х + 1 в (k+f) — и строк е ке блока 2, где 1 = 1, m — k, à m > k.

Тогда согласно (2) на выходе 45 m-го элемента 3 k-й строки появляется ! сигнал Z = 1, а согласно (1) на вы- 15 ходе 43 m-го элемента (k+6) и строки

1 сигнал Z = 1. При этом значения 5„и

Ск на соответствующих выходах коммутатора 7 определяют порядок следования строк, в k-й строке b„ = О, 0 < = 1, 20 а в (1с+ О-й строке b„+ = 1, et„ = О.

Тогда согласно (8) и (9) появляются сигналы " 1" на шине 11 по ТИ1, а следовательно, на выходе триггера 52

k ro модуля регистра 4 и входе 36 25 первого элемента 3 k-й строки, на шине 13, а следовательно, на выходе триггера 53 (k+6)-го модуля регистра

4 и .входе 38 первого элемента 3 (k+6)-й строки блока 2, По этим сигн калам значение А с выходов триггеров.

М

17 k-й строки поразрядно через элемен ты 23 поступает в цепи переноса по столбцам (элемент 27),а значение A„,< сбрасывается. Через некоторое время, определяемое величиной, по ТИ2 гЪ

35 возникают сигналы "1" на шинах 13 и

14, по которым сбрасываются триггеры

17 и 18 в элементах 3 k-й строки блока 2, а также триггер 57 Е-го модуля 40 блока 5. Причем, если значение k меньше номера первой свободной строки блока 2, то k-я строка помещается в блоке 5, как первая свободная. Одновременно возникает сигнал "1" на шине 11, а соответственно, на выходе триггера 52 (Е+Е)-го модуля регистра

4, по которому разрешается запись в триггеры 17 элементов 3 (к+1)-й строки блока 2 (поразрядно) значения А, .

Таким образом, происходит объединение двух числовых интервалов, хранящихся в k-й и (k+I)-й строках блока 2, в один новый, записываемый в (1+1)-ю блока 2.

ЕслиА =Х+1 А =Х-1встрон к э к+е ках блока 2, то новый числовой интервал также формируется в (k+E)-й стро25 8 ке, но корректируется уже значение е

А . При этом с выхода дешифратора 8 е

II Фt поступают сигналы 1 для k-й строки на шины 12 — 14, а для (k+8)-й .строки — на шины 12 и 14.

Во всех рассмотренных случаях сигналы "1" на выходах дешифратора 8 и элементов 70 и 71 коммутатора 7 появляются только тогда, когда счетчик

64 в блоке 6 достигает значения Ьй,.

По окончании корректировок границ интервалов в операции поиска в строкахблока 2 (случаи 1, 2, 4 и 5) íà sbacoдах 43-45 m-ro элемента 3 строки, в которую производилась запись, появ1 ляются сигналы Z „= V = Z 8 = 0 (по- добно случаю 3), Тогда согласно (S) с выхода элемента 70 коммутатора 7 на вход блока 6 поступает сигнал 1, по которому сбрасывается счетчик 64 и формируется сигнал сброса элементов памяти регистра 1 и регистра 4.

После этого открывается вход регистра 1 для приема следующего двоичного числа Х.

Формула изобретения.

1. Устройство обработки данных, содержащее входной регистр, блок ассоциативной памяти, блок синхронизации и дешифратор строк, причем информационный вход и выход входного регистра соединены соответственно с информационным. входом устройства и информационным входом блока ассоциативной памяти, вход маски и информационный выход которого подключены соответственно к выходу регистра маски и информационному выходу устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения производительности, оно содержит блок триггеров и комму- . татор условий, информационный вход, первый, второй и третий информационные выходы которого соединены соответственно с выходом сравнения блока ассоциативной памяти, информационным входом дешифратора строк, синхровходом блока триггеров и входом начальной установки блока синхронизации, вход пуска и первый выход блока синхронизации подключены соответственно к информационному входу устройства и синхровходу входного регистра,кроме того, первый, второй и третий выходы блока синхронизации соединены соответственно с входом сброса реги9 1239725 стра маски, управляющим входом ком- че мутатора условий и управляющим входом ка дешифратора строк, первый, второй и ра третий выходы которого подключены вт соответственно к синхровходу и входу 5 тр установки регистра маски и входу ки сброса блока, триггеров, а выход бло- кл ка триггеров соединен с информацион- бл ным входом регистра маски. вх l0

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

1О ны соответственно к выходу счетчии первому выходу первого одноь б-, тора, второй выход которого и выход орого одновибратора соединены с етьим выходом блока, вход установвход сброса и выход триггера подючены соответственно к входу пуска ока„ выходу счетчика и первому оду элемента И, второй вход и выход которого соединены соответственно с выходом генератора импульсов и счетным входом счетчика, выход счетчика соединен с вторым выходом блока, а вход установки счетчика подключен к входу начальной установки и первому выходу блока.

1239725

Фиг.2

I239725 239725

Г

ZQ

pt

Za

8»

c„ -и

1

8 к! 239725 йьаб Ц

1239725

Составитель Г, Виталиев e>PeÀ О.Сопко

Корректор И. Муска

Редактор E. Папп

Тираж б71 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5.Заказ 3398/50

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,