Ассоциативное оперативное запоминающее устройство

 

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Целью изобретения является упрощение устройства. Устройство содержит первый 1 и второй 21 коммутаторы, регистр числа 3, блок 7 модификации кода опроса старших разрядов, блок 27 модификации кода опроса младших разрядов, регистры маски старших 9 и младших 28 разрядов, блоки памяти старших 11 и младших 12 разрядов, блок управления 14, группу 5 элементов И, группу 6 элементов НЕРАВНОЗНАЧНОСТЬ, блок памяти 19 ссылок, блок памяти 20 свободных ячеек, реверсивный счетчик 22, индексный регистр 24, элемент ИЛИ 25, элемент НЕ 26, регистр 29 старших разрядов адреса. Работа устройства аналогична функционированию ассоциативного запоминающего устройства на основе дешифратора адреса, однако память выполняется из двух частей и вместо полного дешифратора используется двухступенчатый. 8 ил.

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

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

РЕСПУБЛИК

{19) {11) {s»s G 11 С 15/00

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4491414/24 (22) 10.10.88 (46) 30.07.91. Бюл. N 28 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) В.И.Корнейчук, А.П.Марковский, Е.А.Маслянчук (SU) и Сиала Халед (TN)

ЦБЗ) 681.327.6 (088.8) (56) Авторское свидетельство СССР

ЛВ 1324071, кл. 6 11 С 15/00, 1987.

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

hh 1363307, кл. 0 11 С 15/00, 1987. (54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Целья изобретения является упрощение устройства. Устройство, содержит первый 1 и второй 21 коммутаторы, регистр числа 3, блок 7 модификации кода опроса старших разрядов, блок 27 модификации кода опроса младших разрядов, регистры маски старших 9 и младших 28

1667155 разрядов, блоки памяти старших 11 и младших 12 разрядов, блок 14 управления, группу 5 элементов И, группу 6 элементов

НЕРАВНОЗНАЧНОСТЬ, блок памяти 19 ссылок, блок памяти 20 свободных ячеек, реверсивный счетчик 22, индексный регистр

24, элемент ИЛИ 25, элемент НЕ 26, регистр

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

Цель изобретения — упрощение устройства.

На фиг.1 представлена структурная схема ассоциативного оперативного запоминающего устройства. на фиг,2 — структурная схема блока модификации кода опроса (вариант выполнения); на фиг,3 — структурная схема блока управления (вариант выполнения); на фиг. 4 — граф-схема алгоритма записи информации в устройство; на фиг,5— граф-схема алгоритма стирания информации; на фиг.б — граф-схема алгоритма ассоциативного поиска по совпадению; на фиг.7 — граф-схема алгоритма поиска экстремума; на фиг,8 — граф-схема алгоритма поиска ближайшего к заданному.

VcTpoAcTBo (фиг,1) содержит ItepBblA коммутатор 1, входы первой группы которого являются информационными входами

2.1-2.п устройства (где и -- разрядность числа), регистр числа 3 с информационными выходами 4.1-4,п, группу 5 элементов И, группу 6 элементов НЕРАВНОЗНАЧНОСТЬ, блок 7 модификации кода опроса старших разрядов, управляющие входы которого соединены с выходами 8,1-8,п-g (где

g — количество младших разрядсв) регистра маски старших 9 разрядов, выходы блока 8 модификации кода старших разрядов соединены с входами адреса 10,1-10.п-9+1 блока памяти старших разрядов 11, блок памяти младших разрядов 12 с информационным входом 13, блок 14 управления с выходами записи блока 15 памяти старших разрядов, записи блока 16 памяти младших разрядов, записи блока 17 памяти ссылок и записи блока памяти 18 свободных ячеек, блок памяти 19 ссылок, блок памяти 20 свободных ячеек, второй коммутатор 21, реверсивный счетчик 22 с выходом переполнения

23, индексный оегистр 24, элемент ИЛИ 25, элемент НЕ 26, блок 27 модификации кода

29 старших разрядов адреса. Работа устройства аналогична функционированию ассоциативного запоминающего устройства на основе дешифратора адреса, однако память выполняется из двух частей и вместо полного дешифратора используется двухступенчатый, 8 ил. опроса младших разрядов, регистр 28 маски младших разрядов, регистр 29 старших разрядов адреса. Блок управления (фиг.1, фиг.3) имеет выходы; 30 — установка регистра числа, 31 — сброс регистра числа, 32— запись в регистр числа, 33 — управление первым коммутатором, 34- управление вторым коммутатором, 35- установка старшего разряда и сброс остальных разрядов, 36— установка младшего разряда и сброс остальных разрядов индексного регистра, 37, 38 — управление сдвигом влево и вправо индексного регистра, 39 — установка (и-g)-го разряда и сброс остальных разрядов индексного регистра, 40 — положительный результат поиска, 41 — отрицательный результат поиска, 42 .— установка регистров 28 маски младших и старших 9 разрядов, 43 — установка старшего разряда и сброса остальных разрядов регистров 28 маски младших и старших 9 разрядов, 44, 45 управление сдвигом вправо и влево регистра 9 маски старших разрядов, 46, 47 — управление сдвигом вправо и влево регистра 28, маски младших разрядов, 48, 49- управление прямым и обратным счетом реверсивного счетчика 22, 50 — сброс реверсивного счетчика

22, 51 — запись в регистр старших разрядов адреса.

Блок управления (фиг.1, фиг,3) имеет входы: 52- запись, 53 стирание,54- экстремум, 55 — ближайшее к заданному, 56 — максимум-минимум, 57 — равенство, 58— начальная установка, 59,60 — анализа прямого и инверсного значений младшего разряда признака поиска, 61, 62 — первый и второй входы результата поиска, 63-66— информационные входы (п-g)-ro, (n-g+1)ro, первого и и-го разрядов индексного регистра.

Блок 14 управления (фиг.3) содержит блок 67 постоянной памяти начальных адресов, блок 68 элементов ИЛИ, счетчик адреса микрокоманд 69, блок постоянной памяти микропрограмм 70, регистр микрокоманд

71, мультиплексор условий ветвления 72, элемент И 73, элемент ИЛИ 74.

1667155

Блок 7 модификации кода опроса старших разрядов и блок 27 модификации кода опроса младших разрядов представляютсобой комбинационные схемы, которые могут быть, например, реализованы в соответст- 5 вии со схемой, представленной на фиг.2 и содержат группы элементов И 75, элементы

И 76, элементы НЕ 77, элементы ИЛИ 78.

Применительно к блоку 7 модификации кода опроса старших разрядов К на схеме, 10 представленной на фиг.2, равно n-g, применительно к блоку 27 модификации кода onроса младших разрядов K=g.

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

Перед началом работы устройства выполняется цикл начальной установки, инициируемый подачей единичного потенциала на вход 58 устройства. По получении указанного сигнала блок 14 управле- 20 ния формирует последовательность сигналов, обеспечивающих заполнение всех m ячеек блока 20 памяти свободных ячеек (m — количество слое, записываемых в ассоциативное оперативное запоминаю- 25 щее устройство).

Цикл начальной установки начинается выдачей блоком 15 управления сигнала с выхода 50, которым реверсивный счетчик 22 сбрасывается в нуль. Затем производится 30 запись содержимого счетчика 22 через второй коммутатор 21 в ячейку блока 20 памяти свободных. ячеек, адресуемых кодом с выходов счетчика 22 под действием единичных сигналов с выходов 17, 34 блока 14 управле- 35 ния, Затем сигналом с выхода 48 блока 14 осуществляется прибавление единицы к содержимому счетчика 22 и вновь повторяются описанные выше два последних такта до тех пор, пока после m-того увеличения со-40 держимого счетчика 22, последний формирует сигнал переполнения, поступающий на . вход 23 блока 14 управления и свидетельствующий о том, что цикл начальной установки завершен. 45

Ассоциативное оперативное запоминающее устройство позволяет реализовать следующие команды "Запись слова", "Исключение слова", "Поиск по совпадению", "Поиск экстремума", "Поиск ближайшего 50 (большего или меньшего) к заданному".

При выполнении команды "Запись" единичный сигнал подается на вход 52 устройства, а само слово — на входы 2 устройства. Блок 14 управления формирует55 последовательность сигналов в соответствии с алгоритмом, представленном на фиг.4. Выполнение команды "Запись" начинается выдачей блоком i4 управления единичного сигнала на выходе 42, которым устанавливаются все разряды регистров 9, 28 маски в единицу выдаваемый одновременно единичный сигнал с выхода 33 управляет прохождением кода записываемого слова со входов 2 через коммутатор 1 на регистр 3 числа, где по сигналу с выхода 32 блока 14 управления оно фиксируется. Одновременно формируемый на выходе 35 блока 14 управления сигнал устанавливает в единицу старший разряд и сбрасывает в нуль все остальные разряды индексного регистра 24. С прямых выходов регистра 3 числа п-9 старших разрядов (и — Разрядность записываемых слав) записываемого слова поступают на первые входы 4.1-4я-g блока 7 модификации кода опроса старших разрядов, на другие входы которого поступает (и-9)-разрядный код с регистра 9 маски старших разрядов, а à выходах 10.1-10.п9+1 которого формируется {n-g+1)-разрядный модифицированный код опроса старших разрядов, причем последний разряд формируется следующим образом: код маски состоит из группы единиц, занимающих t старших разрядов t Q (О,п-9); модифицированный код опроса имеет в своем г-том разряде нуль (r=- +1), в разрядах с номерами, меньшими г т.е. в разрядах с 1-го по (r-1)-й, — единицы, в разрядах с (г+1)-го по (и-g+1)-ый — t старших разрядов немодифицированного кода опроса (кода, подаваемого на входы блока модификации кода опроса старших разрядов). Например если код маски имеет вид 11110000, то (n-g=8, t=4), а код на регистре — 11001010, то г=5 и модифицированный код опроса имеет вид 111101000, если код маски имеет вид 11111111, то модифицированный код опроса будет иметь вид

01100 t010 (r=1, t=0). Модифицированный код опроса с выхода блока поступает на адресные входы блока 11 памяти старших разрядов. Под действием нулевого сигнала с выхода 15 блока управления в первом такте осуществляется цикл считывания из Gnoка 11 памяти по адресу, состоящему из нуля в старшем разряде и (и-g)-разрядного кода совпадающего с (и-g) старшими разрядами записываемого слова.

Ecn no указанному appecy p блоке 11 памяти хранится единичный бит, что соответствует ситуации, когда до записи, в памяти хранились слова, совпадающие с записываемым в (n-g) старших разрядов, то обработка старших разрядов окончена в указанный выше адрес поступает на адресные входы блока 19 памяти ссылок. Поддействием сигнала, поступающего с выхода 17 блока 14 управления на вход записи-чтения блока 19 памяти ссылок код ссылки считывается на регистр 29 старших разрядов ад1667155 реса. Далее следует:цикг записи в блок 12 памяти младших разрядов.

Если по адресу, состоящего из нуля и (ni-g) старших разрядов записываемого слоВа в блоке 11 памяти старших разрядов хранится нулевой бит, то под действием нулевого сигнала с выхода 18 и единичных сигналов с Выходов 17, 51, 49 блока 14 управления Осуществляется считывание иэ блока 20 памяти кода ccblnKN и запись его В блок памяти 19 ссылок по адресу, Определяемому кодом на выходах 10 блока 7 модификации кода спроса с последующим считыванием упомянутого кода ссылки из блока памяти 19 нэ регистр 29 и уменьшением на единицу содер>кимого реверсивноГО СЧЕТЧИКЭ 22, СчИТЭННЫЙ Код ССЫЛКИ Hà регистр 29 предс-авляет собой старшие разряды адреса для блока 12 памяти младших разрядов, Далее (фи Г.4) слеДует цик, 1 записи ста рших разрядов числа в блок 11 памяти старших разрядов„а по Окон 1энии его, как и В случае, кОГдэ до записи н памяти хоанллись слова, сов п ада lощие с за и исы Наемы м В (и-g)

cTBpLUN>c разрядoF. пооизводится зэпись младших разрядов числа В блок 72 памяти младших разрядов.

Зэписb -.тарших pBзргдов слова состоит

В записи епиниц В (n-g) Ячеек блока 11 памяти cTBp Бих разряд >В, адреса которых Одно" значно определяются Ъ-g) старшими разрядами записывэемОГО слова. СООтвет" ственно, Г1 роцесс. записи длитс>1 (и" g) TBKT08, причем В каждом такте производится сдВиГ

Влево Hp.: opNH разряд регистра 9 Mаски стBрших разрядов под действием единичного сигнала с выхода 44 блока 14 управления, а также сдвиг вправо индексного регистра 24 пОд действием единичноГО сигнэлс1 с выхода

38 блока 14 управления с заполн íèåì освободившихся разрядов указанных регистрОВ 9 и 24 нулями, С изменением маски (и-g} раз меняется модифицирс ванный код опроса старших разрядов на выходах 10, образуя последовательность адресов, nG которым в блок 17 г1амяти осуществляется запись единицы. В (n-а)-ом такте с (n-g}-го разряда индексного регистра 24 на вход 64 блока 14 управления поступает единичный сигнал, и после записи еДиницы В блок 11 памяти старших разрядов по адресу, состоящему из старшего разряда записываемого слова в (и-g)-см разряде, нуля — В In-g-1)-ом разряде и единиц- Ва всехостальных разрядах, цикл записи в блок 11 памяти заканчивается, Запись младших разрядОВ слова cocTQ" ит В записи единиц в g ячеек блок= 12 памяTN младшиK p88pRpGB, TBpU>N8 разрядbl адреса которых Однозначно опрецеляются

П5

Ф ) 5

55 кодом ссылки, который в свою очередь однозначно определяется старшими разрядами записываемого слова, а младшие разряды адреса которых однозначно определяются младшими разрядами записываемого слова. Соответственно, процесс записи длится g тактов и аналогичен процессу записи В блок 11 памяти старших разрядов, за тем исключением, что в каждом такте происходит сдвиг влево на один разряд регистра 28 маски младших разрядов под действием единичного сигнала с выхода

46 блока 74 управления, а модифицированный код опроса формируется на выходах блока 27 модификации кода опроса младших разрядов, По окончании процесса записи слова (на Вход 66 блока 14 управления поступает единичный сигнал с младшего разряда индексного регистра 24} формируется единичный сигнал на выходе 40 блока

14 управления.

При выполнении команды "Исключение слова" единичный сигнал подается на вход

53 устройства, под действием которого блок

14 управления формирует последовательность управляющих сигналов, реализующих стирание слова, подаваемого на входы 2 устройства. Алгоритм процедуры стирания представлен на фиг.5. Указанная последовательность начинается выдачей блоком 14 управления единичного сигнала с выхода 33 и единичного сигнала с выхода 32, по которым стираемое слово с входов 2 через первый коммутатор 1 записывается в регистр 3 числа. Единичными сигналами с выхода 42 блока 14 управления все разряды регистров

9, 28 маски устанавливаются в единицу, а единичным сигналом с выхода 36 блока 14 управления все разряды индексного регистра 24, кроме младшего (n-го), в который записывается единица, устанавливаются в нуль. Процесс стирания слова состоит в записи нулей в ячейки, единицы в которых отражали факт хранения только данного числа. Для этого вначале производится под действием единичного сигнала с выхода 17 и единичного сигнала с выхода 32 блока 14 управления считывание на регистр 29 из блока 119 памяти кода старших разрядов адреса для блока 12 памяти младших разрядов, хранящегося по адресу, состоящему из (n-g) старших разрядов искл ючаемого слова.

Затем выполняется операция стирания слова из блока 12 памяти младших разрядов.

Как следует из описания процесса записи, единица, заг1исанная в ячейках блока 12 памяти младших разрядов, старшие разряды Bдреса которых совпада1от с кОдОм ссьlлки (код ссылки однозначно определяется старшими разрядами числа), а младшие на1667155 с0 чинаются с нуля, свидетельствует о хранении в устройстве числа, совпадающего младшими g разрядами с кодом, следую-. щим в адресе после указанного нуля. Соответственно, каждая указанная ячейка соответствует только одному информационному слову. В то же время ячейки, в номерах которых после кода ссылки, упоминавшегося выше, следует комбинация 10, соответствуют двум числам, отличающимся в младшем разряде и т.д. При стирании числа обнуление ячеек производится только тогда, когда единица s данной ячейке обусловлена наличием в памяти только данного числа. В первом такте операции стирания по адресу старшие разряды которого зафиксированы на регистре 29, а младшие определяются модифицированным кодом опроса, при установленных в единицу всех разрядах 28 маски младших разрядов. В следующем такте сигналами с выходов 33 и

32 блока 14 управления в регистр 3 числа записывается исключаемое слово, и-ый разряд которого инвертирован подразрядным сложением по модулю два в элементах 6

НЕРАВНОЗНАЧНОСТЬ содержимого регистра 3 числа и индексного регистра 24, все разряды которого, кроме и-го обнулены.

Формируемым в этом случае модифицированным кодом опроса производится опрос соответствующей ячейки блока 12 памяти младших разрядов. Если в этой ячейке записана единица, то процесс стирания на этом завершается, а если нуль, то сигналами с выходов 46 и 39 блока 14 управления производится сдвиг влево соответственно регистра 28 маски младших разрядов и индексного регистра 24 с заполнением нулями освободившихся разрядов, По адресу, определяемому кодом ссылки и модифицированным кодом опроса в блоке 12 памяти записывается нуль, затем по способу, описанному выше инвертируется (и-1)-ый разряд регистра 3 числа и процесс исключения продолжается по способу, описанному выше, Если в процессе стирания информации в блоке 12 памяти будет найдено слово, совпадающее с исключаемым в более чем (и-g) старших разрядах, то операция стирания заканчивается. В противном случае, по окончании процесса стирания в блоке 12 памяти под действием единичных сигналов с выходов

39 и 48 блока 14 управления производится сдвиг влево индексного регистра 24 и к содержимому реверсивно о счетчика 22 прибавляется единица. Затем под действием единичного сигнала с выходов 34 и 18 блока

14 управления осуществляется запись содержимого регистра 29 старших разрядов адреса в блок 20 памяти свободных ячеек по

55 адресу, определяемому содержимым счетчика 22, и запись нуля в блок 11 памяти старших разрядов по адресу, состоящему из нуля в старшем разряде и (и-g) старших разрядов признака опроса. Далее процесс стирания продолжается в блоке 11 памяти старших разрядов аналогично процессу стирания в блоке 12 памяти младших разрядов, отличающийся тем, что в каждом такте под действием сигнала с выхода 44 блока управления производится сдвиг влево содержимого регистра 9 маски старших разрядов, а адрес для блока 11 памяти старших разрядов формируется нэ выходах блока 7 модификации када опроса старших разрядов и определяется старшими разоядами числа.

При выполнении команды "Поиск по совпадению" признак опроса подается на входи 2 устройства одновременно с подачей единичного сигнала на вход 57 устройства, который инициирует формирование блоком 14 управления последовательности управляющих сигналов в соответствии с алгоритмом поиска, представленном на фиг.6.

Блок 14 управления формирует единичные сигчалы на выходах 33 и 32, под управлением которых признак опроса со входов 2 записывается и на выходе 42, по которому устанавливаются в нуль все разряды регистров 9 и 28 маски. Затем сигналом с выхода

15 блока управления инициируется считывание из блока 11 памяти содержимого ячейки, адрес которой состоит из нуля в старшем разряде и (r.-g) старших разрядов слова— признака опроса. Одновременно по адресу, идентичному коду (n-g) старших разрядов признака опроса сигналами с выходов 17 и

51 блока 14 управления производится о6ра ev e;i блоку 19 памяти ссылок с фиксацией считанного кода на регистре 29. Если считанный из блока 11 памяти старших разрядов бит равен единице, — o производится обращение к блоку 12 памяти младших разрядов оо ад осу, сватовскому ва кода ссыяки, зафиксированного на регистре 29 старших разрядов адреса, нуля и g младших разрядов признака опроса под действием нулевого сигнала с выхода 16 блока 14 управления, Если в соответствующей ячейке блока 12 памяти младших разрядов записана единица, то единичный сигнал формируется на выходе 40 устройства, в противном случае, как и в ситуации, когда считанный из блока 11 памяти старших разрядов бит равен нулю, единичный сигнал формируется на выхсда 41 устройства.

При выполнении команды "Поиск экстремума" из числа хранящихся в устройстве, на его вход 54 подается единичный сигнал и единичный (нулевой) сигнал — на вход 56, 166 Л55

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

Под дейстивем этих управляющих сигналов блок 14 управления формирует последовательность управляющих сигналов, обеспечивающих выполнение процедуры поиска экстремума (фиг.7). Сигналами с выходов 35,43,30,31 блока управления устанавливаются в единицу первые разряды индексного регистра 24 и регистров маски старших 9 и младших 28 разрядов, все остальные разряды которых устанавливаются в нуль; все разряды регистра числа устанавливаются в единицу (нуль), Сначала производится цикл поиска в блоке 11 памяти старших разрядов. В первом такте производится считывание информации из блока 11 памяти старших разрядов по адресу, определяемому модифицированным кодом onроса старших разрядов. Если по данному адресу в блоке 11 памяти старших разрядов записан нуль, соответствующий отсутствию числа с единицей (нулем) в старших разрядах, то сигналами с выходов 33, 32 блока 14 управления на регистр 3 числа с выходов элементов неравнозначность 6, через коммутатор 1 записывается код, ранее хранившийся на регистре 3 числа, но с инвертированным старшим разрядом. Если по упомянутому выше адресу в блоке 11 памяти старших разрядов записана единица, соответствующая наличию хотя бы одного числа среды хранящихся в устройстве с единицей (нулем) в старшем разряде, то цикл инвертирования отдельного разряда регистра 3 опускается. Затем по сигналам с выходов 45 и 38 блока 14 управления производится сдвиг вправо содержимого регистра 9 маски старших разрядов, с заполнением освободившегося разряда единицей, и индексного регистра 24, с заполнением освободившегося разряда нулем, Описанный выше процесс повторяется

{n-g) раз, т.е. пока на входе 65 блока 14 управления не появится единичный сигнал

c(n-9+1)-го разряда индексного ре истра 24

После чего по адресу, определяемому (n-g) старшими разрядами кода, сформированного в результате поиска экстремума в блоке 11 памяти старших разрядов и зафиксированного в старших разрядах регистра 3 числа, осуществляется обращение к блоку 19 памяти ссылок под действием сигнала с выхода 18 блока 14 управления.

Считанный иэ блока 19 памяти ссылок код фиксируется на регистре 29 старших раэря5

11

35 дов адреса и определяет значение старших разрядов адреса при поиске экстремума в блоке 11 памяти. Процесс поиска экстремума в блоке 12 памяти младших разрядов осуществляется аналогично процессу поиска экстремума в блоке 11 памяти старших разрядов и повторяется g тактов. Отличительным является то, что в каждом такте происходит сдвиг вправо, с заполнением единицей освободившегося разряда регистра маски 28 младших разрядов под действием сигнала с выхода 47 блока 14 управления.

Таким образом после окончания поиска экстремума в регисре 3 числа фиксируется максимальное (минимальное) из чисел, которое может быть считано с выходов 4 устройства при появлении единичного сигнала на выходе 40 устройства. Последний формируется при наличии на входе 66 блока 14 управления единичного сигнала.

При выполнении команды поиска ближайшего большего (меньшего) к заданному из чисел, хранящихся в устройстве, единич ный сигнал подается на вход 55 и соответствующий потенциал, при поиске ближайшего большего — единичный, а при поиске ближайшего меньшего — нулевой, подается на вход 56, эти сигналы инициируют выдачу блоком 14 управления последовательности управляющих сигналов, обеспечивающих поиск ближайшего, к заданному (фиг.8), которое подается на входы устройства. В соответствии с упомянутым алгоритмом блок

14 управления формирует единичные сигналы на выходах 33,32,37,42, которыми заданное слово с входов 2 через первый коммутатор 1 записывается в регистр 3, (ng)-ый разряд индексного регистра 24 устанавливается в единицу, а все остальные его разряды в нуль. Все разряды регистров маски старших 9 и младших 28 разрядов устанавливаются в единицу, Одновременно нулевым сигналом с выхода 15 блока управления производится считывание из блока 11 памяти старших разрядов, на адресные входы которого подается код, состоящий иэ нуля в старшем разряде и кода заданного слова в разрядах с первого по (n-9)-ый. Если с выхода блока t1 памяти старших разрядов считывается сигнал нулевого уровня (соответствует отсутствию чисел„совпадающих с заданным s старших разрядах), блоком управления анализируются сигналы на входах

59 и 60, представляющие прямое и инверсное значение (п-g)-i.o разряда заданного слова. Если укаэанный разряд заданного слова равен нулю (единице), то с выхода 33 на коммутатор 1 подается сигнал, открывающий коммутатор 1 так, что в регистр 3 перезаписывается заданное слово с инвер13

1667155 тированным тем разрядом, которому B индексном регистре 24 соответствует единица (для первого такта (и-g) ü é разряд), после чего опять производится опрос блока 11 памяти старших разрядов. Если в соответствующей ячейке блока 11 памяти старших разрядов записана единица, то микропрограмма продолжается с метки 1 (фиг.8). Иначе, как и в случае когда (n-g)-ый разряд заданного слова равен единице (нулю), производится сдвиг, сигналами с выходов 44,39 блока 14 управления, влево содержимого регистров 24, 9, описанная процедура продолжается да тех пор, пока не будет осуществлен переход по метке 1, либо не будет сформирован сигнал с выхода 41. Этот сигнал формируется в том случае, если в режиме поиска ближайшего большего . (меньшего) к заданному в запоминающем устройстве хранятся числа, каждое из которых меньше (больше) заданного. Микропрограмма, начинающаяся с метки 1, реализует поиск минимального (максимального) из множества чисел, найденных на описанном выше этапе поиска, На каждом шаге этой процедуры сдвигается вправо содержимое регистров 9 и 24 сигналами с выходов 45, 37 блока 14 управления и производится опрос соответствующей ячейки блока 11 памяти старших разрядов. Если при опросе с выходов блока 11 памяти старших разрядов считывается нуль, то производится инвертирование разряда регистра 3, причем позиция инвертируемого разряда определяется положением единицы в индексном регистре 24. По окончании указанного поиска (на входе 64 блока 14 управления появляется единичный сигнал), производится установка младшего разряда индексного регистра 24 в единицу, а всех остальных его разрядов в нуль сигналом с выхода 36 блока 14 управления и далее, как и в случае, когда в первом такте с выхода блока 11 памяти старших разрядов считывается единица. Это соответствует тому, чта в устройстве хранится число, совпадающее с заданными старшими разрядами, производится обращение к блоку 19 памяти ссылок.

Адрес совпадает с (п-g) старшими разрядами кода найденного в предыдущем цикле поиска и запись содержимого соответствующей ячейки в регистр 29 старших разрядов под действием сигналов с выходов 18 и 51 блока управления. Далее процесс поиска ближайшего большего,ìåíüøåãî) осуществляется в блоке 12 памяти младших разрядов, аналогично описанному выше.

Процесс поиска заканчивается либо выдачей блоком 14 управления на выход 11 единичного сигнала, который соответствует

50 отсутствию в устройстве чисел больших или равных (меньших или равных заданному}, либо выдачей единичного сигнала на выхсд

40, который свидетельствует о там, чта ближайшее большее (меньшее) найдено и зафиксировано на регистре 3 числа.

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

Ассоциативное оперативное запоминающее устройства, содержащее блок управления, блок памяти старших разрядов, регистр числа, регистр маски старших разрядов, индексный регистр, блок мадиф:гкации када опроса старших разрядов, первый комм,татар, группу элементов И, группу элементов НЕРАВНОЗНАЧНОСТЬ, элемент ИЛИ, элемент НЕ, выходы регистра числа являются информационными выходами усг райства, информационные входы блока модификации кода опрсса старших разрядов соединены с выходами регистра числа с первого па (и-g)-й разряд, где n— разрядность числа, g — число младших разрядов, выходы регистра маски старших разрядов соединены соответственно с управляющими входами блока модификации кода опрооса старших разрядов, выходы которого соединены с адресными входами блока памяти старших разрядов, информационный вход и вход записи которога соединены с саответствуюшими выходами блока управления, первый вход результата поиска которого соединен с информационным выходом блока памяти старших оазрядов, выходы регистра числа поразрядно соединены с первыми входами элементов И группы и первыми входами элементов НЕРАВНОЗНАЧНОСТЬ группы, вторые входы которых соединены соответственно с вторыми входами элементов И группы и с выходами индексного регистра, входы установки старшего разряда, установки младшего разряда, управления сдвигам вправо, управления сдвигом влево котарога соединены с соответствующими выходами блока управления, входы "Запись", "Стирание", "Экстремум", "Ьлижайшие к заданному", "Максимум-минимум", "Равенства" которого являются соответствующими входами устройства, выходы зпементов НЕРАВНОЗНАЧНОСТЬ гр пы соединены с информационными входами первой группы первого коммутатора, информационные входы второй группы которага являются информационными входами

55 устройства, выходы первого коммутатора соединены с информационными входами регистра числа, вход установки и вход сброса которого соединены с соответствующими выходами блока управления, выход управления первым коммутатором которого саединен с управляющим входом первого коммутатора, Выходы элементов И группы соединены с входами элемента ИЛИ, выход которого соединен с входом элемента КЕ, выход которого и выход элемента ИЛИ соединены соответственно с входами анализа инверсного и прямого значений младшего разряда и признака поиска блока управления, выходы которого "Положительнный результат поиска" и "Отрицательный результат поиска" являются соответствующими Выходами устройства, Входы управления сдвигом вправо, управления сдвигом влево, установки старшего разряда, установки всех разрядов регистра маски старших разрядов соединены с соответствующими выходами блока управления, о т л и ч а ю щ е е-с я тем, что, с целью упрощения устройства, В него введены регистр маски младших разрядов, блок модификации кода опроса младших разрядов, блок памяти ссылок, регистр старших разрядов адреса, блок памяти младших разрядов, 1. второй коммутатор, реверсивный счетчик, блок памяти свободных ячеек, информационные Входы блока модификации кода Опроса младших разрядОВ соединены с выходами с О-га по л-ый регистра числа, выходы регистра .маски младших разрядов соединены с управляющими входами блока модификации кода опроса младших разрядов, Выходы которого соединены с входами адреса первой группы блока памяти младших разрядов, ВхОды адреса Второй группы которого cîeäèl-Iåíbl с выходами регистра старших разрядов адреса и с информационными входами первой группы второго коммутатора, информационные входы второй группы которого соединены с Выходами реВерсивного счетчика и с входами адреса блока памяти свободных ячеек, информационные входы которого соединены с выходами Второго коммутатора, управляющий вход

K0Top0fQ сОединен с Выходом управления вторым коммутатором блока управления, 5 l0

16

Щ

40 выход записи блока памяти свободных ячеек которого соединен с входом записи блока памяти свободных ячеек, выходы которого соединены с информационными входами блока памяти ссылок, адресные входы которого соединены с входами адреса блока памяти старших разрядов, кроме старшего, выходы блока памяти ссылок соединены с информационными входами регистра старших разрядов, вход записи которого соединен с соответствующим выходом блока управления, второй вход результата поиска которого соединен с выходом блока памяти младших разрядов, вход записи которого соединен с соответствующим выходом блока управления, выходы управления сдвигом вправо, управления сдвигом влево, установки старшего разряда, установки младшего разряда регистра маски младших разрядов которого соединены с соответствующими входами регистра маски младших разрядов, информационный вход блока памяти старших разрядов соединен с информационным входом блока памяти младших разрядов, входы сброса, прямого и обратного счета реверсивного счетчика соединены с соответствующими выходами блока управления, вход анализа переполнения реверсивного счетчика которого соединен с выходом переполнения реверсивногосчетчика, входустаноаки (n-g)-го разряда индексного регистра соединен с соответствующим выходом блока управления, выход записи регистра числа коюрого соединен с входом записи регистра числа, вход записи блока памяти ссылок соединен с соответствующим выходом блока управления, вход "Начальная установка" которого является соответствующим входом устройства, выходы (и g) ã0, (и-д+1)-го, (и)-го и первого разрядов индексного регистра соединены с соответствующими входами блока управления.

М .К.Z и- Фк

23 Я 6061 62 ИИ6566

1667155

1667155

Фиг. 5

1667155

1667155

Составитель М, Ла пушкин

Техред M.Mîðãåêòàë Корректор О. Ципле

Редактор Н, Химчук

Заказ 2529 Тираж 348 Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101