Ассоциативная запоминающая матрица

 

Изобретение относится к вычислительной технике и может быть использовано для проектирования и создания специализированных систем хранения, поиска и сортировки данных. Целью изобретения является увеличение быстродействия при осуществлении алгоритмов поиска и упорядоченной выборки, основанных на использовании механизма индикации битовых срезов, за счет выполнения на каждом этапе одного опроса ассоциативной матрицы. Матрица состоит из элементов памяти 1, со входами с первого 2 по пятый 6 и с выходами с первого 7 по третий 9. Матрица также содержит адресные шины 10, первые 11 и вторые 12 разрядные шины записи; первые 13 и вторые 14 разрядные шины опроса; выходные шины 15 результатов опроса; выходные разрядные шины прямого 16 и инверсного 17 сравнения; логические блоки, выполненные на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ 18. 2 ил.

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

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

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

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

Поставленная цель достигается тем, что в ассоциативной запоминающей матрице, содержащей элементы памяти и логические блоки по числу столбцов матрицы, причем входы и выходы элементов памяти каждой строки матрицы соответственно объединены и подключены к соответствующим адресным шинам и шинам результатов опроса, входы элементов памяти каждого столбца матрицы соответственно объединены и подключены к соответствующим разрядным шинам записи и опроса, первые выходы элементов памяти каждого столбца матрицы соответственно объединены и подключены к соответствующей выходной разрядной шине прямого сравнения и первому входу соответствующего логического блока, выход которого подключен к выходной разрядной шине инверсного сравнения, каждый логический блок выполнен на элементе ИСКЛЮЧАЮЩЕЕ ИЛИ, первый вход которого является первым входом логического блока, выходом которого является выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого соединен со вторыми выходами элементов памяти соответствующего столбца матрицы.

На фиг.1 представлена схема ассоциативной запоминающей матрицы; на фиг.2 схема элемента памяти.

Матрица размером mxn (фиг.1) состоит из элементов памяти 1, со входами с первого 2 по пятый 6 и с выходами с первого 7 по третий 9. Значение B (i, j) хранится в элементе памяти 1 (i, j) i-й строки и j-го столбца матрицы. Матрица также содержит адресные шины А(i) 10; первые 11 и вторые 12 разрядные шины записи; первые 13 и вторые 14 разрядные шины опроса; выходные шины М(i) 15 результатов опроса; выходные разрядные шины прямого 16 и инверсного 17 сравнения; логические блоки, выполненные на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ 18.

На фиг. 2 приведена схема элемента памяти 1, состоящего из R-S-триггера 19 с инверсными входами установки в "1" и "0", элементов И-НЕ с первого 20 по четвертый 23, элемента 2И-ИЛИ-НЕ 24. На фиг.2 также представлены не показанные на фиг.1 ограничительные элементы 25 в виде резисторов.

При маскируемой записи в матрицу по заданному адресу на первые 11 и вторые 12 разрядные шины записи и, следовательно, на входы 3 и 4 всех элементов памяти 1 поступает одна из следующих комбинаций сигналов: "10" - запись единицы; "01" запись нуля; "00" маскирование записи. Затем на соответствующую адресную шину 10 подается высокий логический уровень, инициирующий запись соответствующих значений по заданному адресу.

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

Сущность алгоритмов поиска и упорядоченной выборки на основе использования механизма индикации битовых срезов, реализуемых в предложенном устройстве, заключается в следующем. Одновременно с проведением ассоциативного поиска среди слов, участвующих в опросе на данном этапе алгоритма, по размаскированной части поискового аргумента осуществляется анализ и выделение совпавших битовых срезов этих слов. Таким образом, будут определены разряды, которые исключаются из дальнейшего анализа (т.е. разряды, по которым не требуется проводить размаскирования поискового аргумента при выполнении последующих шагов алгоритмов поиска).

При осуществлении ассоциативного поиска среди слов, участвующих в опросе на данном этапе алгоритма, на соответствующие адресные шины 10 подается высокий логический уровень; а с первых 13 и вторых 14 разрядных шин опроса на 5 и 6 входы всех элементов памяти 1 поступит одна из следующих комбинаций сигналов: "10" сравнение с единицей; "01" сравнение с нулем; "00" - маскирование сравнения, инициируя сравнение с содержимым соответствующих элементов 1 выбранных строк. Если произошло несовпадение, то на выходе 7 данного элемента памяти 1, и, следовательно, на соответствующей выходной шине 15 появится уровень логического нуля, стробирующий посредством элементов И-НЕ 22 и 23 элементов памяти 1 данной строки анализ хранимых значений битов. Если произошло совпадение, то выход 7 этого элемента памяти 1, а следовательно, и соответствующая выходная шина 15 сохранит уровень логической единицы, который посредством элементов И-НЕ 22 и 23 элементов памяти 1 данной строки разрешит анализ хранимых значений битов. Таким образом, условием инициализации сравнения битовых срезов в активизированных для ассоциативного опроса строках матрицы является их совпадение с поисковым аргументом.

В этом случае с выхода j-го логического блока 18 для любого j=1.m} на соответствующие выходные разрядные шины 17 инверсного сравнения будет подан уровень сигнала, определяемый следующим соотношением: , где k=i/A(i)=1 AND M(i)=1, 1 ≅i≅ m} Единичный уровень сигналов на шинах 17 укажет на совпадение соответствующих битовых срезов в тех активизированных для ассоциативного опроса строках матрицы, которые совпали с поисковым аргументом.

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

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

Ассоциативная запоминающая матрица, содержащая элементы памяти и логические блоки по числу столбцов матрицы, причем входы и выходы элементов памяти каждой строки матрицы соответственно объединены и подключены к соответствующим адресным шинам и шинам результатов опроса, входы элементов памяти каждого столбца матрицы соответственно объединены и подключены к соответствующим разрядным шинам записи и опроса, первые выходы элементов памяти каждого столбца матрицы соответственно объединены и подключены к соответствующей выходной разрядной шине прямого сравнения и первому входу соответствующего логического блока, выход которого подключен к выходной разрядной шине инверсного сравнения, отличающаяся тем, что каждый логический блок выполнен на элементе ИСКЛЮЧАЮЩЕЕ ИЛИ, первый вход которого является первым входом логического блока, выходом которого является выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого соединен с вторыми выходами элементов памяти соответствующего столбца матрицы.

РИСУНКИ

Рисунок 1, Рисунок 2