43) Блок-схема ассоциативного зу (сам)
8.3. Архитектура и функционирование азу
DO
Рис. 8.1. Блок-схема АЗУ
COM – блок местного управления
RGDI – регистр хранения кода признака опроса
DI – индикатор данных
M – маска
RGM – регистр маски
AM – ассоциативный накопитель
RGWS – регистр выбора слов
RGSR – регистр результата поиска
RGDO – регистр хранения выходной информации
CRI – блок индикаторов числа совпадений
MRR – распределитель многокритериальных совпадений
INS – команда
NR – этот выход означает, что нет совпадений
В элементах памяти ассоциативного накопителя АМ АЗУ хранятся М n-разрядных двоичных слов
В соответствующие разрядные шины,
объединяющие одноименные разряды всех
слов в столбцы матрицы АМ, из регистра
RGDI задается код признака
опроса
.
Код может иметь произвольное число
разрядов, от одного до n
(n-максимальное число
разрядов). Если код признака используется
полностью, то он без изменения поступает
на схему сравнения. Если же необходимо
использовать только часть кода, то
ненужные разряды маскируются с помощью
регистра маски.
Для сравнения содержимого элемента
памяти и кода признака каждый элемент
памяти матрицы АМ дополняется схемой
эквивалентности. В АЗУ с логикой
совпадения в каждом элементе памяти
j-го разряда слов выполняется
операция равнозначности между qij
и xj
с последующей конъюнкцией всех разрядов
каждой строки от 1 до n:
(
).
В АЗУ с логикой несовпадения выполняется операция неравнозначности с последующей дизъюнкцией результатов поиска по каждому разряду:
(
).
Если при адресной организации ЗУ выбор слов по номеру является однозначным, то ассоциативный принцип построения памяти приводит к возможности неоднозначного выбора. Возникает специфическая для АЗУ проблема разделения многозначного ответа — последовательная выборка слов из выделенного подмножества. В общем случае регистр результата поиска может содержать произвольную двоичную информацию (все нули, одна или несколько единиц), что соответствует отсутствию или наличию в памяти одного или нескольких слов информации, отвечающей критерию опроса.
В некоторых случаях для эффективного использования АЗУ часто требуется точный подсчет количества совпадений. Эту функцию выполняет узел CRI. Кроме подсчета найденных при поиске слов часто возникает необходимость получить их из памяти в определенной последовательности. Для организации обработки многозначного результата поиска (опроса) вводится в АЗУ блок MMR, определяющий очередность выбора из множества отвечающих признаку опроса слов в соответствии с выбранной системой их приоритетов. В течение каждого цикла обращения к АЗУ распределитель многократных совпадений указывает слово, имеющее наивысший приоритет при выборе, в то время как остальные слова, оказавшиеся отмеченными при ассоциативном опросе строках матрицы АМ, временно игнорируются. Выбранные слова из дальнейшего просмотра исключаются.
С формальной точки зрения можно сказать, что для множества всех подмножеств слов в ассоциативной памяти рассматриваемые специальные средства представляют собой механизм, обеспечивающий выполнение аксиомы выбора. Отсюда с необходимостью следует, что указанные средства, которыми надо снабдить ассоциативную память, должны быть таковы, чтобы задавать на множестве ее числовых линеек (строк) отношение упорядочения. Это можно сделать либо путем введения цепочки очередности, связывающей слова ассоциативной памяти, либо путем использования адресного дешифратора, который осуществляет отображение множества числовых линеек на некоторый отрезок натурального ряда.
Недостатками цепочки очередности являются малая скорость работы и большое количество элементов. В связи с этим в АЗУ вводят адресную систему, наличие которой является одним из важнейших свойств быстродействующих АЗУ большой емкости. Это придает АЗУ все свойства обычной адресной памяти и может быть эффективно использовано не только при разделении многозначного ответа, но и в целом ряде других ассоциативных операций.
Если конструкция дешифратора в адресных ЗУ обычно допускает обращение только к одному слову в одно и то же время, то в случае АЗУ дешифратор должен обеспечить возможность одновременного обращения к группе слов; при этом адрес можно рассматривать как переменный ассоциативный признак, отдельные разряды которого могут быть замаскированы. АЗУ с таким дешифратором является эквивалентным полностью ассоциативному ЗУ без дешифратора, имеющему для каждого слова увеличенное число разрядов, в которые внесен номер данного слова. Таким образом, проблема разделения многозначного ответа сводится к проблеме упорядоченной выборки слов по содержанию разрядов, хранящих номера этих слов. Хотя обычно выборка рассматривается в порядке возрастания или убывания номеров, ввиду взаимной независимости разрядов, ее можно производить в любом лексикографическом порядке. На основе методов упорядоченной выборки слов в ассоциативной памяти можно производить поиск информации по критериям более сложным, чем простое совпадение; например, поиск максимального (минимального) числа, поиск ближайшего большего (меньшего) в заданных пределах и т. п.
Для построения АЗУ используются главным образом ЭП, реализующие операцию сравнения без разрушения хранимой в них информации, хотя в принципе возможно построение АЗУ также на элементе памяти с разрушением информации. Использование ЭП без разрушения информации позволяет выполнять операцию сравнения одновременно во всех разрядных сечениях и ЯП АЗУ и не требует построения сложных цепей восстановления исходной информации.
Наряду с цепями управления ассоциативным поиском АЗУ содержит цепи записи и считывания. Обычно один из разрядов в каждой ячейке используется для указания ее занятости, то есть если ячейка свободна для записи, то в этом разряде записан “0”. В этом случае при записи в АЗУ новой информации устанавливается признак “0” в соответствующем разряде регистра ассоциативных признаков и определяются все ячейки запоминающего массива, которые свободны для записи информации. Регистр выбора слов RGWS обеспечивает обращение к нужной строке матрицы на время цикла записи или чтения.
Требования к элементу памяти БИС АЗУ:
Для осуществления ассоциативного поиска элемент памяти должен обеспечить сохранение информации и ее обработки (в нашем случае: выполнить операцию логического сравнения).
Т.к. обращение идет ко всем словам одновременно, то потребление мощности каждым элементом должно быть минимальным.
Для объединения ассоциативных элементов памяти в матрицу АМ, в схеме каждого элемента памяти должны быть предусмотрены цепи управления по разрядным и словарным шинам, а также цепи выдачи соответствующих сигналов в общую для элементов памяти каждого слова шину результатов сравнения.
Создание ЗУ ассоциативного типа возможно на основе самых разнообразных физических принципов. С этой точки зрения были изучены практически все типы магнитных запоминающих элементов, полупроводниковые схемы, сверхпроводниковые устройства, оптические системы, различные линии задержки и т. д. Двадцатилетний опыт исследований и разработок в области микроэлектроники в нашей стране и за рубежом показал, что для построения оперативных быстродействующих АЗУ большой емкости (объемом >107 бит и с временем ассоциативного обращения <1 мксек) наиболее благоприятная перспектива — использование сверхпроводниковых элементов.