Архитектура памяти с произвольным доступом

16. Адресная память (запоминающие устройства с произвольным доступом).

ЗУ содержит множество одинаковых запоминающих элементов (ЗЭ), образующих запоминающий массив (ЗМ). ЗМ разделен на отдельные ячейки. Каждая ячейка предназначена для хранения двоичного кода, число разрядов в котором определяется шириной выборки памяти, – слова памяти.

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

Типичная структура ЗУ с произвольным доступом (рис. 22) содержит ЗМ, состоящий из N n-разрядных ячеек, регистр адреса РА, имеющий k = log₂ N разрядов, регистр информации РИ, блок адресной выборки БАВ, блок устройств считывания БУС, блок устройств записи БУЗ и блок управления памятью БУП.

Рисунок 22 – Структура ЗУ с произвольным доступом

По коду адреса в РА БАВ формирует в соответствующей ячейке памяти сигналы, позволяющие произвести в ячейке считывание или запись слова. Блок управления памятью БУП генерирует необходимые последовательности управляющих сигналов, инициирующих работу отдельных блоков ЗУ.

Цикл обращения к памяти инициируется поступлением в БУП сигнала Обращение. Общая часть цикла обращения начинается с прием в РА с шины адреса ША адреса ячейки. Далее БАВ дешифрирует адрес и выбирает заданную адресом ячейку ЗМ. Одновременно осуществляется прием в БУП и расшифровка управляющего сигнала Операция, указывающего вид запрашиваемой операции (чтение или запись).

Далее при чтении БУП посылает сигналы считывания в заданную адресом ячейку ЗМ. При этом код записанного в ячейке слова считывается устройствами считывания БУС и передается в РИ. Операция чтения завершается выдачей слова из РИ на выходную информационную шину ШИВЫХ. В памяти с разрушающим считыванием (при считывании все ЗЭ ячейки устанавливаются в нулевое состояние) производится регенерация информации в ячейке путем записи в нее из РИ считанного слова.

При записи производится прием записываемого слова с входной информационной шины ШИВХ в РИ. Затем в выбранную БАВ ячейку с помощью устройств записи БУЗ записывается слово из РИ.

Для приема в ЗУ записываемых данных и выдачи из ЗУ считанных данных может использоваться одна двунаправленная информационная шина ШИВХ/ВЫХ. Для этого ШИВХ и ШИВЫХ объединяются с помощью буфера данных БД. Этот буфер подключает выходы РИ к ШИВХ/ВЫХ только при выполнении операции чтения из ЗУ. При выполнении операции записи выходы РИ отключены от ШИВХ/ВЫХ, что обеспечивает прием входных данных в РИ.

17. Ассоциативная память.

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

В основе ассоциативной памяти лежит ассоциативная обработка.

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

Таким образом, ассоциативная память – память, аппаратные средства которой ориентированы на реализацию ассоциативной обработки. Ассоциативное ЗУ – это устройство, способное хранить информацию, сравнивать ее с некоторым заданным образцом и указывать на их соответствие или несоответствие друг другу. Признак, по которому производится поиск информации, будем называть ассоциативным признаком, а кодовую комбинацию, выступающую в роли образца для поиска, – признаком поиска. Ассоциативный признак может быть частью искомой информации или дополнительно придаваться ей. В последнем случае его принято называть тегом или ярлыком.

Типичная структура ассоциативного ЗУ (рис. 23) содержит запоминающий массив ЗМ, регистр ассоциативного признака РАП, регистр маски РМ, регистр информации РИ, блок сравнения БС, регистр совпадений РС и блок формирования результата ассоциативного обращения БР.

Рисунок 23 – Структура ассоциативного ЗУ

ЗМ содержит N (n+1)-разрядных ячеек. Для указания занятости ячейки используется служебный n-й разряд (0 – ячейка свободна, 1 – в ячейке записано слово).

По входной информационной шине ШИВХ в РАП поступает ассоциативный запрос (признак поиска), а в РМ – код маски поиска. Ассоциативный поиск производится только для тех разрядов РАП, которым соответствует 1 в РМ (незамаскированные разряды РАП). Блок сравнения БС состоит из N схем совпадения, которые используются для параллельного сравнения каждого бита всех хранимых слов с соответствующим битом признака поиска и выработки сигналов совпадения. В регистре совпадений РС каждой ячейке запоминающего массива соответствует один разряд. Для слов, в которых разряды совпадают с незамаскированными разрядами РАП, блок сравнения БС устанавливает 1 в соответствующих разрядах РС и 0 в остальных разрядах.

Блок формирования результата ассоциативного обращения БР формирует из слова, образовавшегося в РС, сигналы a0, a1, a2, соответствующие случаям:

• a₀ – отсутствие слов в ЗМ, удовлетворяющих ассоциативному признаку;

• a₁ – наличие одного слова в ЗМ, удовлетворяющего ассоциативному признаку;

• a₂ – наличие нескольких (более чем одного) слов в ЗМ, удовлетворяющих ассоциативному признаку.

Формирование содержимого РС и сигналов a0, a1, a2 по содержимому РАП, РМ и ЗМ называется операцией контроля ассоциации. Эта операция является составной частью операций чтения и записи.

• производится контроль ассоциации по признаку поиска в РАП;

• проверяются признаки a0, a1, a2. При a0 = 1 считывание не производится из-за отсутствия искомой информации, при a1 = 1 в РИ считывается найденное слово (слово, на которое указывает 1 в регистре совпадений), при a2 = 1 в РИ считывается слово из ячейки, имеющей наименьший номер среди ячеек, отмеченных 1 в РС. При этом соответствующий разряд в РС сбрасывается в 0. Повторяя эту операцию, можно последовательно считать все слова.

Запись производится в первую свободную ячейку. Для этого:

• отыскиваются свободные ячейки путем выполнения операции контроля ассоциации при РАП = ххх…х0 и РМ = 000…01. При этом свободные ячейки отмечаются 1 в РС;

• для записи выбирается ячейка с наименьшим номером;

• в выбранную ячейку записывается слово, поступившее в РИ с ШИВХ.

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

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

Для построения ассоциативной памяти необходимы ЗЭ, допускающие считывание без разрушения записанной в них информации. Это связано с тем, что при ассоциативном поиске считывание производится по всему ЗМ для всех незамаскированных разрядов и негде сохранять временно разрушаемую считыванием информацию.

Главное преимущество ассоциативных ЗУ определяется тем, что время поиска информации зависит только от числа разрядов в признаке поиска и скорости опроса разрядов и не зависит от числа ячеек в запоминающем массиве.

Различают два вида поиска информации в ассоциативных ЗУ:

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

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

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

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

Источник

Вопрос 16. Организация запоминающих устройств с произвольной выборкой

ЗУ содержит, как правило, множество одинаковых запоминающих элементов, образующих запоминающий массив (ЗМ). ЗМ разделен на отдельные ячейки. Каждая ячейка предназначена для хранения двоичного кода, число разрядов в котором определяется шириной выборки памяти, – слова памяти.

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

Типичная структура ЗУ с произвольным доступом (рис. 18) содержит ЗМ из N n-разрядных ячеек, регистр адреса РА, имеющий k = log₂ N разрядов, регистр информации РИ, блок адресной выборки БАВ, блок устройств считывания БУС, блок устройств записи БУЗ и блок управления памятью БУП.

Р ис. 18

По коду адреса в РА БАВ формирует в соответствующей ячейке памяти сигналы, позволяющие произвести в ячейке считывание или запись слова. Блок управления памятью БУП генерирует необходимые последовательности управляющих сигналов, инициирующих работу отдельных блоков ЗУ.

Цикл обращения к памяти инициируется поступлением в БУП сигнала Обращение. Общая часть цикла обращения начинается с прием в РА с шины адреса ША адреса ячейки. Далее БАВ дешифрирует адрес и выбирает заданную адресом ячейку ЗМ. Одновременно осуществляется прием в БУП и расшифровка управляющего сигнала Операция, указывающего вид запрашиваемой операции (чтение или запись).

Далее при чтении БУП посылает сигналы считывания в заданную адресом ячейку ЗМ. При этом код записанного в ячейке слова считывается устройствами считывания БУС и передается в РИ. Операция чтения завершается выдачей слова из РИ на выходную информационную шину ШИ_ВЫХ. В памяти с разрушающим считыванием (при считывании все ЗЭ ячейки устанавливаются в нулевое состояние) производится регенерация информации в ячейке путем записи в нее из РИ считанного слова.

При записи производится прием записываемого слова с входной информационной шины ШИ_ВХ в РИ. Затем в выбранную БАВ ячейку с помощью устройств записи БУЗ записывается слово из РИ.

Для приема в ЗУ записываемых данных и выдачи из ЗУ считанных данных может использоваться одна двунаправленная информационная шина ШИ_ВХ/ВЫХ. Для этого ШИ_ВХ и ШИ_ВЫХ объединяются с помощью буфера данных БД. Этот буфер подключает выходы РИ к ШИ_ВХ/ВЫХ только при выполнении операции чтения из ЗУ. При выполнении операции записи выходы РИ отключены от ШИ_ВХ/ВЫХ, что обеспечивает прием входных данных в РИ.

Вопрос 17. Ассоциативная память

В памяти с адресной организацией размещение и поиск информации в запоминающем массиве основаны на использовании адреса хранения слов. Адресом служит номер ячейки запоминающего массива, в которой это слово размещается. При записи или чтении слова в запоминающем массиве инициирующая эту операцию команда должна указывать номер ячейки, по которому производится обращение, т. е. в рассмотренных ранее видах запоминающих устройств доступ к информации требовал указания адреса ячейки. Однако часто значительно удобнее искать информацию не по адресу, а опираясь либо на какой-нибудь характерный признак, содержащийся в самой информации, либо на положение слова в запоминающем массиве относительно других хранящихся там слов. Такой подход лежит в основе безадресной памяти, к которой относятся ассоциативная память, стековая память и память типа FIFO.

В основе ассоциативной памяти (associative memory) лежит ассоциативная обработка.

Ассоциативная обработка основана на извлечении данных из памяти по их содержимому, т. е. обращение к данным происходит не на основании указания физического положения информации – адреса, а по некоторым признакам этих данных. При этом обращение (поиск) производится путем сравнения и сопоставления.

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

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

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

Таким образом, ассоциативная память – память, аппаратные средства которой ориентированы на реализацию ассоциативной обработки. Ассоциативное ЗУ – это устройство, способное хранить информацию, сравнивать ее с некоторым заданным образцом и указывать на их соответствие или несоответствие друг другу. Признак, по которому производится поиск информации, будем называть ассоциативным признаком, а кодовую комбинацию, выступающую в роли образца для поиска, – признаком поиска. Ассоциативный признак может быть частью искомой информации или дополнительно придаваться ей. В последнем случае его принято называть тегом или ярлыком.

Типичная структура ассоциативного ЗУ (рис. 19) содержит запоминающий массив ЗМ, регистр ассоциативного признака РАП, регистр маски РМ, регистр информации РИ, блок сравнения БС, регистр совпадений РС и блок формирования результата ассоциативного обращения БР.

Р ис. 19

ЗМ содержит N (n+1)-разрядных ячеек. Для указания занятости ячейки используется служебный n-й разряд (0 – ячейка свободна, 1 – в ячейке записано слово).

По входной информационной шине ШИ_ВХ в РАП поступает ассоциативный запрос (признак поиска), а в РМ – код маски поиска. Ассоциативный поиск производится только для тех разрядов РАП, которым соответствует 1 в РМ (незамаскированные разряды РАП). Блок сравнения БС состоит из N схем совпадения, которые используются для параллельного сравнения каждого бита всех хранимых слов с соответствующим битом признака поиска и выработки сигналов совпадения. В регистре совпадений РС каждой ячейке запоминающего массива соответствует один разряд. Для слов, в которых разряды совпадают с незамаскированными разрядами РАП, блок сравнения БС устанавливает 1 в соответствующих разрядах РС и 0 в остальных разрядах.

Значение j-го разряда в РС определяется следующим выражением

,

где РАП[i]. РМ[i] и ЗМ[j, i] – значения i-го разряда соответственно РАП, РМ и j—й ячейки ЗМ.

Блок формирования результата ассоциативного обращения БР формирует из слова, образовавшегося в РС, сигналы α₀, α₁, α₂, соответствующие случаям:

α₀ – отсутствие слов в ЗМ, удовлетворяющих ассоциативному признаку;

α₁ – наличие одного слова в ЗМ, удовлетворяющего ассоциативному признаку;

α₂ – наличие нескольких (более чем одного) слов в ЗМ, удовлетворяющих ассоциативному признаку.

Для этого БР реализует следующие логические функции:

;

;

.

Формирование содержимого РС и сигналов α₀, α₁, α₂ по содержимому РАП, РМ и ЗМ называется операцией контроля ассоциации. Эта операция является составной частью операций чтения и записи.

производится контроль ассоциации по признаку поиска в РАП;

проверяются признаки α₀, α₁, α₂. При α₀ = 1 считывание не производится из-за отсутствия искомой информации, при α₁ = 1 в РИ считывается найденное слово (слово, на которое указывает 1 в регистре совпадений), при α₂ = 1 в РИ считывается слово из ячейки, имеющей наименьший номер среди ячеек, отмеченных 1 в РС. При этом соответствующий разряд в РС сбрасывается в 0. Повторяя эту операцию, можно последовательно считать все слова.

Запись производится в первую свободную ячейку. Для этого:

отыскиваются свободные ячейки. Для этого выполняется операция контроля ассоциации при РАП = ххх…х0 и РМ = 000…01. При этом свободные ячейки отмечаются 1 в РС;

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

в выбранную ячейку записывается слово, поступившее в РИ с ШИВХ.

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

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

Для построения ассоциативной памяти необходимы ЗЭ, допускающие считывание без разрушения записанной в них информации. Это связано с тем, что при ассоциативном поиске считывание производится по всему ЗМ для всех незамаскированных разрядов и негде сохранять временно разрушаемую считыванием информацию.

Главное преимущество ассоциативных ЗУ определяется тем, что время поиска информации зависит только от числа разрядов в признаке поиска и скорости опроса разрядов и не зависит от числа ячеек в запоминающем массиве.

Различают два вида поиска информации в ассоциативных ЗУ:

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

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

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

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

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

Источник