24 4 Глава5. Память
Стековая память
Стековая память обеспечивает такой режим работы, когда информация записы­вается и считывается по принципу «последним записан — первым считан* (LIFO-Last In First Out). Память с подобной организацией широко применяется для запо­минания и восстановления содержимого регистров процессора (контекста) при об­работке подпрограмм и прерываний. Работу стековой памяти поясняет рис. 5.18, а.
Рис. 5.18. Организация стековой памяти: а — логика работы; б — аппаратно-программный стек
Когда слово А заносится в стек, оно располагается в первой свободной ячейке. Каждое следующее записываемое слово перемещает все содержимое стека на одну ячейку вверх и занимает освободившуюся ячейку. Запись очередного кода, после Н, приводит к переполнению стека и потере кода А. Считывание кодов из стека осуществляется в обратном порядке, то есть начиная с кода Н, который был запи­сан последним. Отметим, что доступ к произвольному коду в стеке формально не­допустим до извлечения всех кодов, записанных позже.
Наиболее распространенным в настоящее время является внешний или аппа­ратно-программный стек, в котором для хранения информации отводится область ОП. Обычно для этих целей отводится участок памяти с наибольшими адресами, а стек расширяется в сторону уменьшения адресов. Поскольку программа обычно загружается, начиная с меньших адресов, такой прием во многих случаях позволя­ет избежать перекрытия областей программы и стека. Адресация стека обеспечи­вается специальным регистром — указателем стека (SP — stack pointer), в кото­рый предварительно помещается наибольший адрес области основной памяти, отведенной под стек (рис. 5.18, б).
При занесении в стек очередного слова сначала производится уменьшение на единицу содержимого указателя стека (УС), которое затем используется как ад­рес ячейки, куда и производится запись, то есть указатель стека хранит адрес той ячейки, к которой было произведено последнее обращение. Это можно описать в виде: УС:= УС -1; ОП[(УС)]:=ШД.
При считывании слова из стека в качестве адреса этого слова берется текущее содержимое указателя стека, а после того как слово извлечено, содержимое УС
Ассоциативная память 2 4 5
увеличивается на единицу. Таким образом, при извлечении слова из стека реали­зуются следующие операции: ЩЦ:= ОП[(УС)]; УС := УС +1.
Ассоциативная память
В рассмотренных ранее видах запоминающих устройств доступ к информации тре­бовал указания адреса ячейки. Зачастую значительно удобнее искать информа­цию не по адресу, а опираясь на какой-нибудь характерный признак, содержащийся в самой информации. Такой принцип лежит в основе ЗУ, известного как ассоциа­тивное запоминающее устройство (АЗУ). В литературе встречаются и иные на­звания подобного ЗУ: память, адресуемая по содержанию (content addressable memory); память, адресуемая по данным (data addressable memory); память с па­раллельным поиском (parallel search memory); каталоговая память (catalog memory); информационное ЗУ (information storage); тегированная память (tag memory). Ассоциативное ЗУ — это устройство, способное хранить информацию, сравнивать ее с некоторым заданным образцом и указывать на их соответствие или несоответ­ствие друг другу. Признак, по которому производится поиск информации, будем называть ассоциативным признаком, а кодовую комбинацию, выступающую в роли образца для поиска, — признаком поиска. Ассоциативный признак может быть ча­стью искомой информации или дополнительно придаваться ей. В последнем слу­чае его принято называть тегом или ярлыком.
Рис. 5.19. Структура ассоциативного запоминающего устройства
Один из вариантов построения ассоциативной памяти показан на рис. 5.19. АЗУ включает в себя:
•   запоминающий массив для хранения N /и-разрядных слов, в каждом из кото­рых несколько младших разрядов занимает служебная информация;
•   регистр ассоциативного признака, куда помещается код искомой информации (признак поиска). Разрядность регистра к обычно меньше длины слова т;
24 6 Глава5. Память
•   схемы совпадения, используемые для параллельного сравнения каждого бита всех хранимых слов с соответствующим битом признака поиска и выработки сигналов совпадения;
•   регистр совпадений, где каждой ячейке запоминающего массива соответствует один разряд, в который заносится единица, если все разряды соответствующей ячейки совпали с одноименными разрядами признака поиска;
•   регистр маски, позволяющий запретить сравнение определенных битов;
•   комбинационную схему, которая на основании анализа содержимого регистра совпадений формирует сигналы, характеризующие результаты поиска инфор­мации.
При обращении к АЗУ сначала в регистре маски обнуляются разряды, которые не должны учитываться при поиске информации. Все разряды регистра совпаде­ний устанавливаются в единичное состояние. После этого в регистр ассоциатив­ного признака заносится код искомой информации (признак поиска) и начинает­ся ее поиск, в процессе которого схемы совпадения одновременно сравнивают первый бит всех ячеек запоминающего массива с первым битом признака поиска. Те схемы, которые зафиксировали несовпадение, формируют сигнал, переводя­щий соответствующий бит регистра совпадений в нулевое состояние. Так же про­исходит процесс поиска и для остальных незамаскированных битов признака по­иска. В итоге единицы сохраняются лишь в тех разрядах регистра совпадений, которые соответствуют ячейкам, где находится искомая информация. Конфигура­ция единиц в регистре совпадений используется в качестве адресов, по которым производится считывание из запоминающего массива.
Из-за того что результаты поиска могут оказаться неоднозначными, содержи­мое регистра совпадений подается на комбинационную схему, где формируются сигналы, извещающие о том, что искомая информация:
•   аО — не найдена;
•  а 1 — содержится в одной ячейке;
•   а2 — содержится более чем в одной ячейке.
Формирование содержимого регистра совпадений и сигналов аО, al, а2 носит название операции контроля ассоциации. Она является составной частью опера­ций считывания и записи, хотя может иметь и самостоятельное значение.
При считывании сначала производится контроль ассоциации по аргументу по­иска. Затем, при аО=1 считывание отменяется из-за отсутствия искомой инфор­мации, при al = 1 считывается слово, на которое указывает единица в регистре совпадений, а при а2= 1 сбрасывается самая старшая единица в регистре совпаде­ний и извлекается соответствующее ей слово. Повторяя эту операцию, можно по­следовательно считать все слова.
Запись в АП производится без указания конкретного адреса, в первую свобод­ную ячейку. Для отыскания свободной ячейки выполняется операция считыва­ния, в которой не замаскированы только служебные разряды, показывающие, как давно производилось обращение к данной ячейке, и свободной считается либо пу­стая ячейка, либо та, которая дольше всего не использовалась.
Ассоциативная память 2 4 7
Главное преимущество ассоциативных ЗУ определяется тем, что время поиска информации зависит только от числа разрядов в признаке поиска и скорости оп­роса разрядов и не зависит от числа ячеек в запоминающем массиве.
Общность идеи ассоциативного поиска информации отнюдь не исключает раз­нообразия архитектур АЗУ. Конкретная архитектура определяется сочетанием четырех факторов: вида поиска информации; техники сравнения признаков; спо­соба считывания информации при множественных совпадениях и способа записи информации.                           '
В каждом конкретном применении АЗУ задача поиска информации может фор­мулироваться по-разному (рис. 5.20.).
Рис. 5.20. Классификация АЗУ по виду поиска информации в запоминающем массиве
При простом поиске требуется полное совпадение всех разрядов признака по­иска с одноименными разрядами слов, хранящихся в запоминающем массиве.
При соответствующей организации АЗУ способно к более сложным вариантам поиска, с частичным совпадением. Можно, например, ставить задачу поиска слов с максимальным или минимальным значением ассоциативного признака. Много­кратное выборка из АЗУ слова с максимальным или минимальным значением ас­социативного признака (с исключением его из дальнейшего поиска), по существу, представляет собой упорядоченную выборку информации. Упорядоченную выбор­ку можно обеспечить и другим способом, если вести поиск слов, ассоциативный признак которых по отношению к признаку опроса является ближайшим боль­шим или меньшим значением.
Еще одним вариантом сложного поиска может быть нахождение слов, числен­ное значение признака в которых больше или меньше заданной величины. Подоб­ный подход позволяет вести поиск слов с признаками, лежащими внутри или вне заданных пределов..                           . > ■■■.-..,.. . ......
Очевидно, что реализация сложных методов поиска; связана- с соответствую­щими изменениями в архитектуре АЗУ, в частности с усложнением схемы ЗУ и введением в нее дополнительной логики.
24 8 Глава 5. Память
При построении АЗУ выбирают из четырех вариантов организации опроса со­держимого памяти (рис. 5.21). Варианты эти могут комбинироваться параллельно по группе разрядов и последовательно по группам. В плане времени поиска наибо­лее эффективным можно считать параллельный опрос как по словам, так и по раз­рядам, но не все виды запоминающих элементов допускают такую возможность.
Рис. 5.21. Классификация АЗУ по способу опроса содержимого запоминающего массива
Важным моментом является организация считывания из АЗУ информации, когда с признаком поиска совпадают ассоциативные признаки нескольких слов. В этом случае применяется один из двух подходов (рис. 5.22).
Рис. 5.22. Классификация АЗУ по способу выборки совпавших слов при множественных совпадениях
Цепь очередности реализуется с помощью достаточно сложного устройства, где фиксируются слова, образующие многозначный ответ. Цепь очередности позво­ляет производить считывание слов в порядке возрастания номера ячейки АЗУ независимо от величины ассоциативных признаков.
При алгоритмическом способе извлечения многозначного ответа выборка про­изводится в результате серии опросов. Серия опросов может формироваться пу-
Кэш-память 249
тем упорядочивания тех разрядов, которые были замаскированы и не участвовали в признаке поиска. В другом варианте для этих целей выделяются специальные разряды. Существует целый ряд алгоритмов, позволяющих организовать упоря­доченную выборку из АЗУ. Подробное их описание и сравнительный анализ мож­но найти в [14].
Существенные отличия в архитектурах АЗУ могут быть связаны с выбранным принципом записи информации. Ранее был описан вариант с записью в незаня­тую ячейку с наименьшим номером. На практике применяются и иные способы (рис. 5.23), из которых наиболее сложный — запись с сортировкой информации на входе АЗУ по величине ассоциативного признака. Здесь местоположение ячейки, куда будет помещено новое слово, зависит от соотношения ассоциативных при­знаков вновь записываемого слова и уже хранящихся в АЗУ слов.
Из-за относительно высокой стоимости АЗУ редко используется как самосто­ятельный вид памяти.
Кэш-память
Как уже отмечалось, в качестве элементной базы основной памяти в большинстве ВМ служат микросхемы динамических ОЗУ, на порядок уступающие по быстро­действию центральному процессору. В результате процессор вынужден простаи­вать несколько тактовых периодов, пока информация из ИМС памяти установит­ся на шине данных ВМ. Если ОП выполнить на быстрых микросхемах статической памяти, стоимость ВМ возрастет весьма существенно. Экономически приемлемое решение этой проблемы было предложено М. Уилксом в 1965 году в процессе раз­работки ВМ Atlas и заключается оно в использовании двухуровневой памяти, ког­да между ОП и процессором размещается небольшая, но быстродействующая бу­ферная память. В процессе работы такой системы в буферную память копируются те участки ОП, к которым производится обращение со стороны процессора. В обще­принятой терминологии — производится отображение участков ОП на буферную память. Выигрыш достигается за счет ранее рассмотренного свойства локальнос­ти — если отобразить участок ОП в более быстродействующую буферную память
Hosted by uCoz