Устройство обработки данных Советский патент 1986 года по МПК G06F15/00 

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

Цель изобретения - увеличение про изводительности устройства.

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

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

ТОГО, первый, второй и третий выходы блока 6 соединены соответственно с входом сброса регистра 4, управляюшдм входом коммутатора 7 и управляюш;им входом дешифратора 8. Первый;, второй и третий выходы дешифратора 8 подклю- чены соответственно к синхровходу и входу установки регистра 4 и вкоду сброса блока 5, а выход последнего соединен с информащюнным входом регистра 4. .

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

1.5 и 16, два .триггера ..17 и 18, ДЕ элемента ПЕ 19 и 20, третий и че-- верт1э1й элементы И-ИЛИ 21 и 22, четыре элемента И 23-26, два элемента ИЛИ 27 и 28 и имеет информационные входы . 29-32 и выход 33, управляюпц-;е входы 34-393 информационные входы 40-42 и выходы 43-45.

Регистр 4 каски (фиг, 3) -содержит два элемента ИЛИ 46 и 47, два элемента И 48 и 49, элемент И-НЕ 50 и шесть триггеров

Блок 5 триггеров (фиг, 3) содер- Ж1Т триггер 57 и три элемента И 58-6С.

- Блок 6 синхронизации (фиг„ 4) содержит триггер 61, генератор 62 H., элемент И 63, счетчик 64 и два одновибратора 65 и 66,

Коммутатор 7 условий (фиг. 5) содержит п групп, каждая из которьпс содержит Эдтемент И 67, два элемента ЖИ 68 и 69 и два элемента И 70 и 71,

Дешифратор 8 строк (фиг, 6} содержит элементы И 72-89 и элементы 1ШИ 90-93.

i

Временные диаграммь) на фиг, 7

отображают последовательность 94 кодов, поступающих на регистр 1 (изображаются в виде импульсов) , после-- довательность 95 открытых и закрь тьсс состояний входов в регистре 1, последовательность 96 импульсов на ЕЬКОДЭ триггера 61 блока 6, длительность HJ.;- пульса л t( определяет время выполнения о операции поиска в блоке 2, 1-1Мпульс 97,

фо}эмируемый на выходе счетиика 64 в блоке 6 при работе уст™ ройст за, определяет время микроопераций записи-считывания и поиска в бло-- ке 2,, тактовые импульсы 98 и 99 .(ТИ1 и ТИ2) длительностью на выходе соответственно одновибраторов 65 и 66 блока 6, состояния 100 и 101 выходов триггеров 51-56 регистра 4, импульс

102 сбросаj. формируемый на перв ом выходе коммутатора 7,

При формировании из элементов 3 ассоциативной матрицы размером m п . 43-45 к ждого элемента 3 соединяются соответственно с входами 40-42 соседнего справа элемента 3, а информационный выход 33 - с информационным входом 29 соседнего снизу элемента 3„ При этом управляющие

входы 34-39 являются общими для всез элементов 3, образуюгдих строку, а нформационные входы 30-32 - с б1п;ими ля всех элементов 3, образующих

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

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

у 7 f ; . V V г.

Li С,1,СЛ X VU л /5

.ZJo,

к;

Z,(.X-);

v -VvZu-q -xNz,

а х

де Ец,У,Ец - обозначают соответст- I венно входы 40-42 элемента 3;

Zjj,V,Zg - обозначают соответственно выходы 43-45 элемента 3; С ,а - значения разрядов

(триггеры 17 и 18) соц

ответственно нижней А..

8

И верхней А границы числового интервала в k-ой строке блока 2, н

к

тк

. .в в в в 1 - К и гк - тк J - I п;

X, У - значения разрядов X + 1, X - 1 (информационные входы 31 и 32), полученные соответственно при сложе- нрш и в.ычитании единицы из двоичного числа X J,,X.z .,.. .х„(информационные входы 30),,xt,...,

I , .

m

X - 1 X,

,Х,

Коммутатор 7 позволяет провести анализ условий

г z о, V 1 (4)

|На выходах 43-45 всех элементов 3 та-го столбца блока 2 и

40

ZH 4 V. О (5) на выходах 43-45 одного из элементов 3 т-го столбца блока 2,

Дешифратор 8 формирует управляю- пще сигналы на шинах 9-14 для каждой 45 строки блока 2 пр состоянию выходов 43-45 элементов 3 т-го столбца блока 2 и выходов коммутатора 7 (Ь, ,Ь2,;. (,C| jC ,...,C|,.,.,,(j,J. Управляющие сигналы на шинах 9-14 возникают при выполнении условий

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

С приходом на регистр 1 двоичного числа входы этого регистра закрываются на время обработки поступившего 50 кода (позиция 95 на фиг. 7). В регистре 1 выполняются операции сложения ,и вычитания константы 1 из поступившего двоичного числа X, а величины X, X +1, X - 1 хранятся на спе- или Z 1, Z V 0,Ък О (8) 55 циальных регистрах, выходы которых

„( „I л г, , л . /„ч соединены соответственно с входами или Z,. V О, ZR 1,b 0,C,, 1 (9) ол от г: от, / в 30-32 блока 2 поразрядно. Б блоке 6

на выходах 43-45 га-го элемента 3 k-й запускается счетчик 64 на время it,,

Z H 1, ZB V О, Ь,с, Ci (6)

или Z

п

V о, z 1,Ъ c о (7)

2397254

строки блока 2 и k-x выходах татора 7.

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

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

10 на выходе триггера 57 присутствует сигнал l. Первоначально проводится подготовка устройства к работе подачей сигналов О на установочные входы блоков 2, на третьи входы элемен15 тов 68 и 69 соответственно первой и п-й групп коммутатора 7, сигналов 1 на установочные входы регистра 4, блока 5, на второй вход элемента 67 первой группы коммутатора 7. При этом

20 Б блоке 5 помечается первая незанятая строка блока 2, а на входы 40-42 первых элементов 3 строк блока 2, занятых информацией, с выходов элементов 48-50 соответствующих Модулей

25 регистра 4 подаются сигналы Ъ Zg 1, V 0.

Первая свободная строка блока 2 определяется следующим образом. Примем, что строки блока 2 с первой по

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

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

определяемое длительностью микрооперации поиска в блоке 2, которая выполняется только в строках, где по- казана маска Z,. Z,,

ке увеличивается на единицу увеличения значения Ац.

3 а сче т

II

1, V О. По истечении времени на выходе счетчика 64 появляется сигнал 1, по которому в блоке 6 сбрасывается триггер 61J одновибраторы 65 и 66 вырабатывают соответственно сигналы ТИ1. и ТИ2, а в коммутаторе 7 открываются элементы 70 и 71. Результатом поиска являются значения Z,,, Zg, v на выходах 43-45 элементов 3 т-го столбца блока 2. Б зависимости от совокупности этих значений различают несколько случаев Дальнейшей обработки двоичного числа, хранящегося н-а регистре 1 .

Первый случай - А ,, X + 1 в k-й строке блока 2/ Тогда согла.сно (1) сигнал Ец 1 с входа первого элемента 3 через элементы 21 проходит на выход 43 то-го элемента 3 k-E строТретий случай - - 1,. + -S- 1 Е: k-й строке блока 2, Тогда сог- 5 ласно (1)-(3) на выходах 43-45 т-го элемента 3 k-й строки появляются сигналы Zj - V Zg О, т.е. значение двоичного числа X попадает в числовой, интервал, заданный границами ,

I O А°, включая и сами границы. В результате согласно (5) с выхода элемента 70 коммутатора 7 на вход блока 6 поступает сигнал 1, по которому в блоке 6 сбрасывается счетчик 64 и

fS форм1-фуется сигнал сброса элементов памяти регист1)а 1 и регистра 4. После этого открывается вход регистра 1 для приема следующего двоичного числа X.

20

Четвертьй случай

А

А1 X 1 или

X + 1 в k-й строке блока 2. Иред

положим, X 4- 1 А

что значение

и

X

А j, или

ки блока 2, т.е.

2

1, Z. V 0.

не во всех элементах 3 (paзpядa г) , а лишь в нескольких

После этого дешифратор 8 по k-й стро- 25 (старших),, после них имеется элемент

ке согласно (6) формирует сигнал 1 на шине 13, который поступает на триггер 53 k-ro модуля регистра 4, Сигналом 1 на выходе этого триггера, поступающим на входы 38, сбрасывают- ся триггеры 17 элементов 3 k-й строки блока 2. Через некоторую задержку Т з определяемую длительностью ТИ1, сигнал 1 появляется на шине 9 и через элемент 46 поступает на вход триггера 51 k-ro модуля регистра 4, а с выхода этого триггера - на входы 34 элементов 3 k-й строки. Таким образом, значение. X записывается на место А , т.е. числовой интервал в k-й строке увеличивается на единицу за счет уменьшения значения А к

3, в которому

0

0,х Is Zg 1,что (2) к появлению

.35

40

приводит согласно сигнала Zg О на выходе 45 этого элемента 3, т.е. сигнал в цепи Zg исчезает. Однако согласно (3) на вьгхо де элемента 26, а соответственно и на выходе элемента 28 данного элемента 3 появляетсясигнал V 1s который по цегш V проходит до выхода 44 т-го элемента 3 k-й строки. Если же сигнал V , 1 на выходе т-го элемента 3 не появляется при исчезновении сигнала в цепи Zg k-й строки, что возможно приа 1 О, Zg 1, то он появляется при 0 1,Х О,

Z,

1 на выходе элемента 28 одного из последующих элементов 3, а следовательно, и в цепи V k-й строки. Сигнал V 1 на выходе 44 т-го элемента 3 k-й строки заказывает на то, что зна чение X не принадлежит числовому ин- тервсшу, хранящемуся в этой строке и н,е может быть к нему присоединено кор

Второй случай А | X - 1 в k-й строке блока 2. Тогда согласно (2) и подобно первому случаю сигнал Zg 1 появляется на выходе 45 т-го элемента 3 этой строки, а ZH v Ot После этого дешифратор 8 согласно (7) по k-й строке формирует сигнал 1 на шине 14, а через время ( - на шине 10. На выходах триггеров 54 и 56 модуля регистра -4 устанавливаются сигналы 1, которыми через соответствующие входы 35 и 39 производится сброс триггеров 18 элементов 3 k-й строки блока 2, а затем - запись значения X на место А ., . Таким

л

образом числовой интервал в k-й строке увеличивается на единицу увеличения значения Ац.

3 а сче т

Третий случай - - 1,. + -S- 1 Е: k-й строке блока 2, Тогда сог- ласно (1)-(3) на выходах 43-45 т-го элемента 3 k-й строки появляются сигналы Zj - V Zg О, т.е. значение двоичного числа X попадает в числовой, интервал, заданный границами ,

А°, включая и сами границы. В результате согласно (5) с выхода элемента 70 коммутатора 7 на вход блока 6 поступает сигнал 1, по которому в блоке 6 сбрасывается счетчик 64 и

форм1-фуется сигнал сброса элементов памяти регист1)а 1 и регистра 4. После этого открывается вход регистра 1 для, приема следующего двоичного числа X.

Четвертьй случай

А

А1 X 1 или

X + 1 в k-й строке блока 2. Иред

положим, X 4- 1 А

что значение

и

X

А j, или

не во всех элементах 3 (paзpядa г) , а лишь в нескольких

(старших),, после них имеется элемент

25 (старших),, после них имеется элемент

3, в которому

0

0,х Is Zg 1,что (2) к появлению

5

0

приводит согласно сигнала Zg О на выходе 45 этого элемента 3, т.е. сигнал в цепи Zg исчезает. Однако согласно (3) на вьгхо- де элемента 26, а соответственно и на выходе элемента 28 данного элемента 3 появляетсясигнал V 1s который по цегш V проходит до выхода 44 т-го элемента 3 k-й строки. Если же сигнал V , 1 на выходе т-го элемента 3 не появляется при исчезновении сигнала в цепи Zg k-й строки, что возможно приа 1 О, Zg 1, то он появляется при 0 1,Х О,

Z,

5

1 на выходе элемента 28 одного из последующих элементов 3, а следовательно, и в цепи V k-й строки. Сигнал V 1 на выходе 44 т-го элемента 3 k-й строки заказывает на то, что значение X не принадлежит числовому ин- тервсшу, хранящемуся в этой строке и н,е может быть к нему присоединено корректировкой границ А

к S

А

так как ,

0

5

отличается от них больше, чем на единицу „ Если на выходах 43-45 всех элементов 3 т-го столбца блока 2 ZH О, V 1, Zg О, то согласно (4) на выходе элемента 71 коммутатора 7 появляется сигнал 1, которгЖ проз- ходит через элемент 59 блока 5, соот- ,ветствующего отмеченной строке блока 2, а в регистре 4 - через элементы . 46 и 47 на вькод триггеров 51 и 56,

71239725

Появление сигнала 1 на входах ЗА и 35 элементов 3 разрешает запись значения X в триггеры 17 и 18 отмеченной строки блока 2. Таким образом.

8

ке, но корректируется А р. При этом с выхода поступают сигналы 1 на шины 12 - 14, а для

в первой свободной строке блока 2 фор-5 ки - на шины 12 и 14.

мируется новый числовой интервал с

Н В

границами А А X. После этого в блоке 3 снова отмечается первая свободная строка.

в k-й

,в

Пятый случай - А А - 1 строке, а А X + 1 в ()-й строке блока 2, где К 1, m-k, , Тогда согласно (2) на выходе 45 т-го элемента 3 k-й строки появляется сигнал ZP 1, а согласно (1) на выходе 43 т-го элемента (k+6)-й строки сигнал 2ц 1. При этом значения bj. и

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

10 являются только тогда, когда счетчик 64 в блоке 6 достигае.т значения ut, . По окончании корректировок границ интервалов в операции поиска в строках- блока 2 (случаи 1, 2, 4 и 5) на выхр-

15 дах 43-45 т-го элемента 3 строки, в которую производилась запись, появляются сигналы Z V Zg О (подобно случаю 3), Тогда согласно (5) с выхода элемента 70 коммутатора 7

Сц на соответствующих выходах коммутатора 7 определяют порядок следования строк, в k-й строке Ь| 0,Ci. 1, 20 «а вход блока 6 поступает сигнал 1, а в (k+0-й строке 1, 0. по которому сбрасывается счетчик 64

-и формируется сигнаш сброса элементов памяти регистра 1 и регистра 4.

Тогда согласно (8) и (9) появляются

30

35

сигналы 1 на шине 11 по ТИ1, а следовательно, на выходе триггера 52 k-ro модуля регистра 4 и входе 36 первого элемента 3 k-й строки, на шине 13, а следовательно, на выходе триггера 53 (k+E)-ro модуля регистра 4 и -входе 38 первого элемента 3

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

17 k-й строки поразрядно через элементы 23 поступает в цепи переноса по столбцам (элемент 27),а значение сбрасывается. Через некоторое время, определяемое величиной С , по ТИ2 возникают сигналы 1 на шинах 13 и 14, по которым сбрасываются триггеры 17 и 18 в элементах 3 k-й строки блока 2, а также триггер 57 k-ro модуля Q блока 5. Причем,если значение k меньше номера первой свободной строки . блока 2, то k-я строка помещается в блоке 5, как первая свободная. Одновременно возникает сигнал 1 на шине 11, а соответственно, на выходе триггера 52 (k+t)-ro модуля регистра 4, по которому разрешается запись в триггеры 17 элементов 3 ()-й строПосле этого открывается вход регист- 25 ра 1 для приема следующего двоичного числа X.

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

45

ки блока 2 (поразрядно) значения А

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

50

55

1. Устройство обработки данных, содержащее входной регистр, блок ассоциативной памяти, блок синхронизации и дешифратор строк, причем информационный вход и выход входного регистра соединены соответственно с информационным входом устройства и информационным входом блока ассоциативной памяти, вход маски и информаци- онньш выход которого подключены соот- :ветственно к выходу регистра маски И информационному выходу устройства, отличающ ееся тем, что, с целью увеличения производительности, оно содержит блок триггеров и коммутатор условий, информационный вход, первый, второй и третий информационные выходы которого соединены соответственно с выходом сравнения блока ассоциативной памяти, информационным входом дешифратора строк, синхровхо- дом блока триггеров и входом начальной установки блока синхронизации, вход пуска и первый выход блока синхронизации подключены соответственно к информационному входу устройства и синхровходу входного регистра,кроме того, первый, второй и третий выходь блока синхронизации соединены соответственно с входом сброса региЕсли А X -f 1, X - 1

в строках блока 2, то новый числовой интервал также формируется в ()-й стро

8

ке, но корректируется уже значение А р. При этом с выхода дешифратора 8 поступают сигналы 1 для k-й строки на шины 12 - 14, а для (k+)-ft строВо всех рассмотренных случаях сигналы 1 на выходах дешифратора 8 и элементов 70 и 71 коммутатора 7 по-

являются только тогда, когда счетчик 64 в блоке 6 достигае.т значения ut, . По окончании корректировок границ интервалов в операции поиска в строках- блока 2 (случаи 1, 2, 4 и 5) на выхр-

дах 43-45 т-го элемента 3 строки, в которую производилась запись, появляются сигналы Z V Zg О (подобно случаю 3), Тогда согласно (5) с выхода элемента 70 коммутатора 7

«а вход блока 6 поступает сигнал 1, по которому сбрасывается счетчик 64

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

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

30

35

Q

45

50

55

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

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

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

которого соединены соответственно с выходом генератора импульсов и счетным входом счетчика, выход счетчика соединен с вторым выходом блока, а вход установки счетчика подключен к

входу начальной установки и первому выходу.блока.

.1

Фиг2

ФмгЛ

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

/

fl J-5

S, JK

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

ш.З

Составитель Г. Виталиев

Техред о.Сопко .Корректор И. Муска

.Заказ 3398/50Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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