6. Стековая память

Стековая память работает по принципу «последним пришел – первым обслужился» (LIFO – Last In First Out). Память с подобной организацией для запоминания и восстановления содержимого регистров процессора при отработке подпрограмм и прерываний. На рисунке 4.6 представлен принцип работы стековой памяти.

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

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

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

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

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

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

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

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

Если имеет место совпадение признака ячейки с запрашиваемым адресом, то производится обращение (по чтению или по записи) в информационное поле этой ячейки АСОЗУ, обращение к ОЗУ при этом блокируется. Если требуемый адрес не найден в АСОЗУ, то инициируется (или продолжается) обращение к ОЗУ, в АСОЗУ создается копия ячейки ОЗУ, к которой обратился процессор. Повторное обращение процессора по этому адресу будет реализовано в АСОЗУ (на порядок быстрее, чем в ОЗУ).

Таким образом, в АСОЗУ создаются копии тех ячеек ОЗУ, к которым в данный момент обращается процессор в надежде, что «в ближайшее время » произойдет новое обращение по этому адресу.

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

Конкретная архитектура АЗУ определяется сочетанием четырех факторов: вида поиска информации, техники сравнения признаков, способа считывания информации при множественных совпадениях, способа записи информации.

В каждом конкретном применении АЗУ задача поиска информации может формулироваться по-разному в зависимости от:

• вида поиска информации;

• способа опроса содержимого запоминающего массива;

• способа выборки при множественных совпадениях;

• способа записи информации.

Из-за относительно высокой стоимости АЗУ редко используется как самостоятельный вид памяти.

8. КЭШ-память.

Основная память, реализуемая на микросхемах динамической памяти слишком медленна, требует тактов ожидания процессора (wait states) в циклах обращения к памяти. Статическая память, построенная, как и процессор на триггерных ячейках, способна догонять процессор по быстродействию, но она дорогая и имеет малую плотность упаковки. Экономически приемлемое решение этой проблемы было предложено М. Уилксом в 1965 году в процессе разработки ВМ Atlas и заключается оно в использовании двухуровневой памяти, когда между ОП и процессором размещается небольшая быстродействующая буферная память. В процессе работы такой системы в буферную память копируются те участки ОП, к которым производится обращение со стороны процессора. Основная идея – в кэш-памяти находятся слова, которые чаще всего используются. Если процессору требуется какое-либо слово, то сначала он обращается в кэш-память. Только если слова там нет, он обращается к основной памяти. Эффективность кэш-памяти зависит от того, какая часть слов находится в ней. Кэш-память (cache - убежище, тайник) является подчиненным видом памяти, она обычно скрыта от программиста в том смысле, что он не может ее адресовать.

Одной из самых эффективных технологий одновременного увеличения пропускной способности и уменьшения времени ожидания является применение нескольких блоков кэш-памяти, при этом:

1. вводятся отдельные кэш-памяти для команд и данных, имеющие независимый доступ к основной памяти, с объёмом от 16 до 64Кбайт.

2. между разделенной кэш-памятью и основной памятью помещается объединенная (программа + данные) кэш-память 2-ого уровня. Она соединяется с процессором скоростным трактом данных. Её объём от 512 Кбайт до 1Мбайта. Находится в одном корпусе с процессором.

3. кэш-память 3-его уровня находится на одной плате с процессором, обычно состоит из статического ОЗУ в несколько Мбайт.

4. обычно всё содержимое кэш-памяти 1-ого уровня находится в кэш-памяти 2-ого уровня, а всё содержимое кэш-памяти 2-ого уровня находится в кэш-памяти 3-его уровня.

На рисунке 4.8 представлена схема размещения трехуровневой кэш-память на системной плате ВМ. Реальная эффективность использования кэш-памяти зависит от характера решаемых задач, однако, установлено, что для большинства задач близкой к оптимальной является кэш-память емкостью от 1 до 512 Кбайт.

Во всех типах кэш-памяти основную память разделяют на блоки фиксированного размера, которые называются строками кэш-памяти, именно этими строками и оперирует контроллер кэш-памяти.

Строка кэш-памяти состоит из нескольких последовательных байтов. Наиболее близким к оптимальному считается размер строки, равный 4 – 8 адресуемым единицам. На практике размер строки обычно выбирают равным ширине шины данных. Строки нумеруются, начиная с нуля, т.е. если размер строки 32 байта, то строка 0 – это байты с 0 по 31, строка 1 – это байты с 32 по 63 и т.д. С каждой строкой кэш-памяти связана информация об адресе скопированного в неё блока основной памяти и признаки её состояния.

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

На рис.4.9 приведена структура системы с основной и кэш-памятью. Основная память состоит из 2ⁿ адресуемых слов, где каждое слово имеет свой уникальный n-разрядный адрес. Эта память рассматривается как М блоков фиксированной длины по К слов в каждом (М=2ⁿ /К). Кэш-память состоит из С блоков аналогичного размера, причём С значительно меньше М. При считывании слова из какого-либо блока ОП этот блок копируется в определённую строку кэша. Поскольку число блоков ОП больше числа строк, отдельная строка не может быть выделена постоянно одному и тому же блоку ОП. Каждой строке кэш-памяти соответствует тег (признак), содержащий сведения о том, копии какого блока ОП в данный момент хранится в данной строке. Номеру блока соответствует номер тега (уникальное 16-битное значение, указывающее соответствующую строку памяти, из которой поступили данные).

В зависимости от способа определения взаимного соответствия строки кэш-памяти и области основной памяти различают три архитектуры кэш-памяти:

• кэш-память прямого отображения (direct-mapped cache);

• полностью ассоциативная кэш-память (fully associative cache);

• комбинация первых 2-х - частично или наборно-ассоциативная кэш-память (set associative cache).

9. Кэш-памяти прямого отображения.

Для каждого блока оперативной памяти, имеющего фиксированный размер, выделяется одна строка. Последовательные строки основной памяти помещаются в последовательные элементы кэш-памяти. Адрес строки i кэш-памяти, на которую может быть отображен блок j из ОП, однозначно определяется выражением: i = j mod m, где m – общее число строк в кэш-памяти. В примере, приведенном на рис. 4.10, количество строк равно 128, номер строки i = j mod 128, где i может принимать значения от 0 до 127, адрес блока j – от 0 до 16383. В строке i может быть отображен каждый 128-й блок ОП, если отсчет начинать с блока, номер которого равен i. На рисунке 4.10 основная память представлена в виде двухмерного массива блоков, в котором количество рядов равно числу строк в кэш-памяти, а в каждом ряду последовательно перечислены блоки, переадресуемые на одну и ту же строку кэш-памяти.

Каждая строка кэш-памяти состоит из трех частей:

• бит достоверности определяет, есть ли достоверные данные в строке или нет. Когда система загружается, то все элементы маркируются как недостоверные;

• тег состоит из уникального 16-битного значения, указывающего соответствующую строку памяти, из которой поступили данные;

• данные содержат копию данных основной памяти, вмещает одну строку кэш-памяти в K слов (один блок).

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

Примерный алгоритм поиска данных в кэш-памяти (приведен на рис. 4.11):

• формирование номера строки из величины конкретного адреса;

• доступ к нужному слову очень быстрый, так как известен адрес и точное нахождение слова в КЭШе (если оно имеется в КЭШе). Слово считывается из строки;

• проверка достоверности строки - заполнена ли требуемая строка;

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

• если слова нет в кэш-памяти, то ведется его поиск в ОЗУ. При наличии коррекции информации в «старой» строке она переписывается в ОЗУ. Производится перезагрузка элемента кэш-памяти.

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