Ассоциативная память эвм. Ассоциативная память. Развитие ассоциативной памяти. Общие сведения и классификация устройств памяти

Способы организации памяти

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

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

АДРЕСНАЯ ПАМЯТЬ

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

На рис. 5.2 изображена обобщенная структура адресной памяти.

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

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

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

Необходимость в операции очистки ячейки перед записью, так же как и в операции регенерации информации при считывании, определяется типом используемых ЗЭ, способами управления, особенностями электронной структуры БИС памяти, в связи с этим в полупроводниковых памятях эти операции могут отсутствовать.

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

АССОЦИАТИВНАЯ ПАМЯТЬ

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

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

При очень больших объёмах памяти на определœенных классах задач ассоциативный поиск существенно ускоряет обработку данных и уменьшает вероятность сбоя в ЭВМ. Вместе с тем, ассоциативные ЗУ с блоками соответствующих комбинационных схем позволяют выполнить в памяти достаточно сложные логические операции: поиск максимального или минимального числа в массиве, поиск слов, заключенных в определœенные границы, сортировку массива и т.д.

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

В некоторых специализированных ЭВМ ОП или его часть строится таким образом, что позволяет реализовать как ассоциативный, так и адресный поиск информации.

Упрощенная структурная схема ассоциативной памяти, в которой всœе ЗЭ ЗМ снабжены однобитовыми процессорами, приведена на рис. 5.3.

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

По входной информационной шинœе в РгАП поступает n-разрядный ассоциативный запрос, ᴛ.ᴇ. заполняются разряды от 0 до n-1. Одновременно в РгМ поступает код маски поиска, при этом n-й разряд РгМ устанавливается в 0. Ассоциативный поиск производится лишь для совокупности разрядов РгАП, которым соответствуют 1 в РгМ (незамаскированные разряды РгАП). Важно заметить, что для слов, в которых цифры в разрядах совпали с незамаскированными разрядами РгАП, КС устанавливает 1 в соответствующие разряды РгСв и 0 в остальные разряды.

Комбинационная схема формирования результата ассоциативного обращения ФС формирует из слова, образовавшегося в РгСв, как минимум три сигнала:

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

A 1 – наличие одного такого слова;

A 2 – наличие более чем одного слова.

Возможны и другие операции над содержимым РгСв, к примеру подсчет количества единиц, ᴛ.ᴇ. подсчет слов в памяти, удовлетворяющих ассоциативному запросу, и т.п.

Формирование содержимого РгСв и a 0 , a 1 , a 2 по содержимому РгАП, РгМ, ЗМ и принято называть операцией контроля ассоциации.

Считывание. Сначала производится контроль ассоциации по признаку в РгАП.

A 0 = 1 – считывание отменяется из-за отсутствия искомой информации;

A 1 = 1 – считывается в РгИ найденное слово, после чего выдается на ШИ вых;

A 2 = 1 – считывается слово, имеющее, к примеру, наименьший номер среди ячеек, отмеченных 1 в РгСв, после чего выдается на ШИ вых.

Запись. Сначала отыскивается свободная ячейка (полагаем, что в разряде занятости свободной ячейки записан 0). Для этого выполняется контроль ассоциации при РгАП=111...10 и РгМ=000...01, ᴛ.ᴇ. n-й разряд РгАП устанавливается в 0, а n-й разряд РгМ – в 1. При этом свободная ячейка отмечается 1 в РгСв. Для записи выбирают свободную ячейку, к примеру, с наименьшим номером. В нее записывается слово, поступившее с ШИ вх в РгИ.

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

СТЕКОВАЯ ПАМЯТЬ (МАГАЗИННАЯ)

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

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

Запись нового слова, поступившего с ШИ вх, производится в верхнюю (нулевую) ячейку, при этом всœе ранее записанные слова (включая слово в ячейке 0) сдвигаются вниз, в сосœедние ячейки, номера которых на единицу больше. Считывание возможно только из верхней (нулевой) ячейки памяти. Основной режим - ϶ᴛᴏ считывание с удалением. При этом всœе остальные слова в памяти сдвигаются вверх, в сосœедние ячейки с меньшими номерами. В такой памяти реализуется правило: последний пришел – первый ушел . Стеки подобного типа принято называть стеками LIFO (Last In – First Out).

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

О первом слове, посылаемом в стек, говорят, что оно располагается на дне стека . О последнем посланном (по времени) в стек слове говорят, что оно находится в вершинœе стека . Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, ячейка N-1 – дно стека, а ячейка 0 – вершина.

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

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

В отличие от аппаратного стека данные, размещенные в программном стеке, при записи нового числа или считывании не перемещаются. Запись каждого нового слова осуществляется в ячейку памяти, следующую по порядку за той, адрес которой содержится в указателœе стека. После записи нового слова содержимое указателя стека увеличивается на единицу (см. рис. 6.5). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, в программном стеке перемещаются не данные, а вершина стека. При считывании слова из стека происходит обратный процесс. Слово считывается из ячейки, адрес которой находится в указателœе стека, после чего содержимое указателя стека уменьшается на единицу.

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

Чем удобна такая форма организации памяти? Забегая вперед, можно отметить, что любая команда, выполняемая в процессоре, в общем случае должна содержать код операции (КОП), адрес первого и второго операндов и адрес занесения результата. Для экономии памяти и сокращения времени выполнения машинной команды процессором желательно уменьшить длину команды. Пределом такого уменьшения является длина безадресной команды, ᴛ.ᴇ. просто КОП. Именно такие команды оказываются возможными при стековой организации памяти, так как при правильном расположении операндов в стеке достаточно последовательно их извлекать и выполнять над ними соответствующие операции.

Помимо рассмотренной выше стековой памяти типа LIFO в ЭВМ используются стековые памяти другого типа, реализующие правило: первый пришел – первый ушел . Стеки подобного типа принято называть стеками FIFO (First In – First Out). Такая стековая память широко используется для организации различного рода очередей (команд, данных, запросов и т.д.). Обобщенная структура аппаратного стека типа FIFO представлена на рис. 5.4, б.

Как и в предыдущем случае, ячейки стековой памяти образуют одномерный массив, в котором сосœедние ячейки связаны друг с другом разрядными цепями передачи слов. Запись нового слова, поступившего с ШИ вх, осуществляется в верхнюю (нулевую) ячейку, после чего оно сразу перемещается вниз и записывается в последнюю по счету незаполненную ячейку. В случае если стек перед записью был пустой, слово сразу попадает в ячейку с номером N-1, ᴛ.ᴇ. на дно стека. Считывание возможно только из нижней ячейки с номером N-1 (дно стека). Основной режим - ϶ᴛᴏ считывание с удалением. При этом всœе последующие (записанные) слова сдвигаются вниз, в сосœедние ячейки, номера которых на единицу больше. При заполнении стека счетчик (СчСт) запрещает дальнейшие операции записи в стек.

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, в отличие от стека LIFO, в стеке FIFO перемещается не дно, а вершина. Записываемые в стек FIFO слова постепенно продвигаются от вершины ко дну, откуда и считываются по мере крайне важно сти, причем темп записи и считывания определяются внешними управляющими сигналами и не связаны друг с другом.

Программная реализация стека FIFO в настоящем разделœе не рассматривается, поскольку на практике используется достаточно редко.

Способы организации памяти - понятие и виды. Классификация и особенности категории "Способы организации памяти" 2017, 2018.

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

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

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

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

Рис.4.2.Структура адресной памяти.

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

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

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

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

Блок управления БУП генерирует необходимые последова­тельности управляющих сигналов, инициирующих работу от­дельных узлов памяти. Цепи передачи управляющих сигналов показаны тонкими линиями на рис. 4.2.

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

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

По входной информационной шине ШИВх в регистр ассо­циативного признака РгАП в разряды 0-и-1 поступает п- разрядный ассоциативный запрос, а в регистр маски РгМ - код маски поиска, при этом п-й разряд РгМ устанавли­вается в 0. Ассоциативный поиск производится лишь для сово­купности разрядов РгАП, которым "соответствуют 1 в РгМ (незамаскированные разряды РгАП). Для слов, в которых цифры в разрядах совпали с незамаскированными разрядами РгАП, комбинационная схема КС устанавливает 1 в соответ­ствующие разряды регистра совпадения РгСв и 0 в остальные разряды. Таким образом, значение j-ro разряда в РгСв опреде­ляется выражением

РгСв (j) =

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

Комбинационная схема формирования результата ассоциа­тивного обращения ФС формирует из слова, образовавшегося в РгСв, сигналы  0 ,  1 ,  2 , соответствующие случаям отсутствия слов в ЗМ, удовлетворяющих ассоциативному признаку, нали­чию одного и более чем одного такого слова. Для этого ФС реализует следующие булевы функции:

 0 =

 1 = РгСв

 2 =  0  1

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

При считывании сначала производится контроль ассоциа­ции по ассоциативному признаку в РгАП. Затем при  0 = 1 считывание отменяется из-за отсутствия искомой информации, при  1 = 1 считывается в РгИ найденное слово, при  2 = 1 в РгИ считывается слово из ячейки, имеющей наименьший номер среди ячеек, отмеченных 1 в РгСв. Из РгИ счи­танное слово выдается на ШИВых.

Рис. 4.3. Структура ассоциа­тивной памяти

При записи сначала оты­скивается свободная ячейка. Для этого выполняется опе­рация контроля ассоциации при РгАП= 111. ..10 и РгМ == 00... 01. При этом свободные ячейки отмечают­ся 1 в РгСв. Для записи вы­бирается свободная ячейка с наименьшим номером. В нее записывается слово, посту­пившее с ШИВх в РгИ.

Рис. 4.4. Стековая память

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

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

Стековая память, так же как и ассоциативная, является без­адресной. В стековой памяти (рис. 4.4) ячейки образуют одно­мерный массив, в котором соседние ячейки связаны друг с дру­гом разрядными цепями передачи слов. Запись нового слова производится в верхнюю ячейку (ячейку 0), при этом все ранее записанные слова (включая слово, находившееся в ячейке 0), сдвигаются вниз, в соседние ячейки с большими на 1 номера­ми. Считывание возможно только из верхней (нулевой) ячейки памяти, при этом, если производится считывание с удалением, все остальные слова в памяти сдвигаются вверх, в соседние ячейки с большими номерами. В этой памяти порядок считыва­ния слов соответствует правилу: последним поступил - первым обслуживается. В ряде устройств рассматриваемого типа пре­дусматривается также операция простого считывания слова из нулевой ячейки (без его удаления и сдвига слова в памяти). Иногда стековая память снабжается счетчиком стека СчСт, по­казывающим количество занесенных в память слов. Сигнал СчСт = 0 соответствует пустому, стеку, СчСт = N - 1 - заполненному стеку.

Часто стековую память организуют, используя адресную память. Широкое применение стековая память нахо­дит при обработке вложенных структур данных.

В последующих параграфах главы описываются различные типы ЗУ с адресной организацией. Ассоциативная память ис­пользуется в аппаратуре динамическо­го распределения ОП, а также для построения КЭШ-памяти.

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

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

1) поиск максимального или минимального числа в ЗУ;

2) поиск слов, заключенных в определенные границы;

3) поиск слов, ближайших к ассоциативному признаку, как с большей, так и с меньшей стороны и т.д.

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

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

По входной ШД в регистр ассоциативного признака RGП поступает n-разрядный признак, а в регистр маски RGМ – код маски поиска. При этом n-ый разряд регистра RGМ устанавливается в 0. Ассоциативный поиск производится лишь по тем разрядам признака, которым соответствует «1» в регистре маски, то есть по так называемым незамаскированным разрядам RGМ. Таким образом, задавая код маски М, можно произвольно выбирать те разряды признака, по которым ведется поиск.

Для слов из ЗМ, в которых все цифры совпали с незамаскированными разрядами RGП, комбинированная схема КС 1 устанавливает «1» в соответствующие разряды регистра совпадения RGC. Таким образом, если произошло совпадение цифры j-го слова с незамаскируемыми разрядами признака, то в j-ом разряде регистра RGC будет записана «1», в противном случае «0». Запись «1» в j-ом разряде RGC означает, что j-ое слово соответствует признаку, т.е. является тем словом, которое собственно и ищется в ЗМ.

В регистр маски записывается слово, разрешающее запрос по всем или только некоторым разрядам ассоциативного признака, применение маски позволяет сократить или расширить область поиска.

Поиск информации производится параллельно по всем ячейкам путем сравнения запроса с ассоциативным признаком каждой ячейки.

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

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

При записи информации сначала находится свободная ячейка. Для этого выполняется операция ассоциативного поиска по признаку, имеющему во всех разрядах «0», а в регистре маски «0» записаны во всех разрядах, кроме младшего n-го разряда.

Таким образом, определяются те ячейки ЗМ, у которых в n-ом разряде записан «0», что означает незанятость ячейки. В свободную ячейку с наименьшим номером записывается слово из регистра информации RGI.

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

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

Стековая организация памяти

Если запись и чтение производится через один и тот же регистр, то такое устройство называется стековой памятью, работающей по принципу "первым вошел - последним вышел" (FILO-First Input, Last Output).

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

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

Рассмотрим организацию стековой памяти, как памяти, образованной из связанных между собой ячеек памяти, в которых информация при записи в стек нового слова смещается вниз (Рис.2). Обмен информацией осуществляется только через верхнюю ячейку памяти. При считывании слов из стека, слово может удаляться из стековой памяти или сдвигаться по кольцу, в зависимости от организации стека. Режим чтения – последним вошел, первым вышел - называют LIFO (Last In First Out).

Рис.2.Организация стековой памяти.

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

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

Особо отметим, что при таком запросе возможен один из трех результатов:

1. имеется в точности одна строка с заданным тегом;
2. имеется несколько строк с заданным тегом;
3. нет ни одной строки с заданным тегом.

Поиск записи по признаку - это действие, типичное для обращений к базам данных, и поиск в базе зачастую чвляется ассоциативным поиском. Для выполнения такого поиска следует просмотреть все записи и сравнить заданный тег с тегом каждой записи. Это можно сделать и при использовании для хранения записей обычной адресуемой памяти (и понятно, что это потребует достаточно много времени - пропорционально количеству хранимых записей!). Об ассоциативной памяти говорят тогда, когда ассоциативная выборка данных из памяти поддержана аппаратно. При записи в ассоциативную память элемент данных помещается в СтрАП вместе с присущим этому элементу тегом. Для этого можно использовать любую свободную СтрАП. Рассмотрим разновидности структурной организации КЭШ-памяти или способы отображения оперативной памяти на КЭШ .

Полностью ассоциативный КЭШ

Схема полностью ассоциативного КЭШа представлена на рисунке (см. рисунок ниже).

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

Если следующие выборки возможны из этого участка, они будут сделаны уже из КЭШа (быстро) - "КЭШ-попадание". Если же окажется, что нужного элемента в КЭШе нет, - "КЭШ-промахом". В этом случае обращение происходит к ОЗУ (медленно), и при этом одновременно заполняется очередная КЭШ-строка.

Схема полностью ассоциативной КЭШ-памяти

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

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

Если произошел КЭШ-промах, а в КЭШе нет свободных строк, необходимо заменить одну строку КЭШа на другую строку.

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

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

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

Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU - Least Recently Used ), при котором замещается та строка КЭШ-памяти, к которой дольше всего не было обращения. Проводившиеся исследования показали, что алгоритм LRU, который "смотрит" назад, работает достаточно хорошо в сравнении с оптимальным алгоритмом, "смотрящим" вперед.

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

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

Другой возможный алгоритм замещения - алгоритм, работающий по принципу "первый вошел, первый вышел" (FIFO - First In First Out ). Здесь заменяется строка, дольше всего находившаяся в КЭШ-памяти. Алгоритм легко реализуется с помощью рассмотренной ранее очереди, с той лишь разницей, что после обращения к строке положение соответствующей ссылки в очереди не меняется.

Еще один алгоритм - замена наименее часто использовавшейся строки (LFU - Least Frequently Used). Заменяется та строка в КЭШ-памяти, к которой было меньше всего обращений. Принцип можно воплотить на практике, связав каждую строку со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число.

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

Кроме тега и байтов данных в КЭШ-строке могут содержаться дополнительные служебные поля, среди которых в первую очередь следует отметить бит достоверности V (от valid - действительный имеющий силу) и бит модификации M (от modify - изменять, модифицировать). При заполнении очередной КЭШ-строки V устанавливается в состояние "достоверно", а M - в состояние "не модифицировано". В случае, если в ходе выполнения программы содержимое данной строки было изменено, переключается бит M, сигнализируя о том, что при замене данной строки ее содержимое следует переписать в ОЗУ. Если по каким-либо причинам произошло изменение копии элемента данной строки, хранимого в другом месте (например в ОЗУ), переключается бит V. При обращении к такой строке будет зафиксирован КЭШ-промах (несмотря на то, что тег совпадает), и обращение произойдет к основному ОЗУ. Кроме того, служебное поле может содержать биты, поддерживающие алгоритм LRU.

Оценка объема оборудования

Типовой объем КЭШ-памяти в современной системе - 8…1024 кбайт, а длина КЭШ-строки 4…32 байт. Дальнейшая оценка делается для значений объема КЭШа 256 кбайт и длины строки 32 байт, что характерно для систем с процессорами Pentium и PentiumPro. Длина тега при этом равна 27 бит, а количество строк в КЭШе составит 256К/ 32=8192. Именно столько цифровых компараторов 27 битных кодов потребуется для реализации вышеописанной структуры.

Приблизительная оценка затрат оборудования для построения цифрового компаратора дает значение 10 транз/бит, а общее количество транзисторов только в блоке компараторов будет равно:

10*27*8192 = 2 211 840,

что приблизительно в полтора раза меньше общего количества транзисторов на кристалле Pentium. Таким образом, ясно, что описанная структура полностью ассоциативной КЭШ-памяти () реализуема только при малом количестве строк в КЭШе, т.е. при малом объеме КЭШа (практически не более 32…64 строк). КЭШ большего объема строят по другой структуре.

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

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

Одна запись таблицы в ассоциативной памяти (один вход) содержит информацию об одной виртуальной странице: ее атрибуты и кадр, в котором она находится. Эти поля в точности соответствуют полям в таблице страниц .

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

Рассмотрим функционирование менеджера памяти при наличии ассоциативной памяти .

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

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

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

Предположим, например, что для определения адреса в случае кэш-промаха через таблицу страниц необходимо 100 нс, а для определения адреса в случае кэш-попадания через ассоциативную память – 20 нс . С 90% hit ratio среднее время определения адреса – 0,9x20+0,1x100 = 28 нс .

Вполне приемлемая производительность современных ОС доказывает эффективность использования ассоциативной памяти . Высокое значение вероятности нахождения данных в ассоциативной памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.

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

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

Инвертированная таблица страниц

Несмотря на многоуровневую организацию, хранение нескольких таблиц страниц большого размера по-прежнему представляют собой проблему. Ее значение особенно актуально для 64-разрядных архитектур, где число виртуальных страниц очень велико. Вариантом решения является применение инвертированной таблицы страниц (inverted page table). Этот подход применяется на машинах PowerPC, некоторых рабочих станциях Hewlett-Packard, IBM RT, IBM AS/400 и ряде других.

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

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

Размер страницы

Разработчики ОС для существующих машин редко имеют возможность влиять на размер страницы. Однако для вновь создаваемых компьютеров решение относительно оптимального размера страницы является актуальным. Как и следовало ожидать, нет одного наилучшего размера. Скорее есть набор факторов, влияющих на размер. Обычно размер страницы – это степень двойки от 2 9 до 2 14 байт.