КЭШ, ассоциативный по множеству (set-associative)

Подробности

Родительская категория: Память. Нижний уровень

Категория: КЭШ-память

Синонимы: наборно-ассоциативный, множественно-ассоциативный.

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

Схема КЭШ-памяти, ассоциативной по множеству

Обнаружение и исправление ошибок

Подробности

Родительская категория: Память. Нижний уровень

Категория: Микросхемы памяти

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

Схема памяти с обнаружением и исправлением ошибок

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

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

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

Пример корректирующего кода

Здесь D — биты данных, С — столбец битов паритета строк, К — строка битов паритета столбцов, Р — бит паритета, контролирующий столбец С и строку К. Таким образом, к 64 битам данных нужно добавить 17 бит паритета: по 8 бит на строки и столбцы и один дополнительный бит для контроля строки и столбца битов паритета. Если в одной строке и одном столбце обнаружено нарушение паритета, для исправления ошибки достаточно просто инвертировать бит на пересечении этих строки и столбца. Если ошибка паритета выявлена только в одной строке или только одном столбце либо одновременно в нескольких строках и столбцах, фиксируется многобитовая ошибка и формируется признак невозможности коррекции.

Недостаток рассмотренного приема в том, что он требует большого числа дополнительных разрядов. Более эффективным представляется код, предложенный Ричардом Хэммингом и носящий его имя (код Хэмминга).

Алгоритмы обеспечения когерентности системы памяти

Подробности

Родительская категория: Память. Нижний уровень

Категория: КЭШ-память

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

Рассмотрим, что следует сделать, если когерентность нарушается при модификации КЭШ-строки. В этом случае требуется:

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

Для записи модифицированного данным процессором значения из его КЭШа в основную память используются две стратегии: сквозная запись (write-through) и обратная запись (write-back).

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

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

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

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

Недостатки обратной записи:

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

Последний недостаток можно частично устранить, используя упреждающую обратную запись: строка-кандидат на замену определяется заранее, переносится из КЭШа в ОЗУ в интервалах, когда шина свободна, и затем объявляется в данном КЭШе недостоверной. В результате в КЭШ-памяти почти всегда имеется свободная строка, которую можно без задержки использовать при КЭШ-промахе. Для обеспечения когерентности в сложных системах с несколькими КЭШами разработан и стандартизован протокол обеспечения когерентности, называемый MESI по названиям состояний, в которых может находиться КЭШ-строка: Modified, Exclusive, Shared, Invalid.

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

•Shared. Строка в КЭШе содержит достоверные данные и совпадает с содержимым основной памяти. Обращение будет внутренним (в данный КЭШ) и не приведет к активизации внешней шины.

•Exclusive. Строка достоверна, находится в КЭШе, совпадает с содержимым основной памяти, а экземпляры этой строки, находящиеся в других КЭШах, являются недостоверными.

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

Замечание 1: Строка достоверна, если она находится в состояниях S, E или M.

Замечание 2: Если строка находится в состоянии I, это означает, что она свободна.

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

Basic MESI State Transitions

 

Схема изменения MESI-состояний

ФЛЭШ-память

Подробности

Родительская категория: Память. Нижний уровень

Категория: Микросхемы памяти

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

ФЛЭШ-память строится на однотранзисторных элементах памяти (с "плавающим" затвором), что обеспечивает плотность хранения информации даже несколько более высокую, чем в динамической оперативной памяти. Существуют различные технологии построения базовых элементов ФЛЭШ-памяти, разработанные ее основными производителями. Эти технологии отличаются количеством слоев, методами стирания и записи данных, а также структурной организацией, что отражается в их названии. Наиболее широко известны NOR и NAND типы ФЛЭШ-памяти, запоминающие транзисторы в которых подключены к разрядным шинам, соответственно, параллельно и последовательно. Первый тип имеет относительно большие размеры ячеек и быстрый произвольный доступ (порядка 70 нс), что позволяет выполнять программы непосредственно из этой памяти. Второй тип имеет меньшие размеры ячеек и быстрый последовательный доступ, обеспечивая скорость передачи до 16 Мбайт/с), что более пригодно для построения устройств блочного типа, например, "твердотельных дисков".

Способность сохранять информацию при выключенном питании, малые размеры, высокая надежность и приемлемая цена привели к широкому распространению ФЛЭШ-памяти. Этот вид памяти применяется для хранения BIOS, построения так называемых "твердотельных" дисков (memory stick, memory drive и др.), карт памяти различного назначения и т.п. Причем, устройства на основе ФЛЭШ-памяти используются не только в ЭВМ, но и во многих других областях.

Элементы памяти ФЛЭШ-ЗУ организованы в матрицы, как и в других видах полупроводниковой памяти. Разрядность данных для микросхем составляет 1-2 байта. Операция чтения из ФЛЭШ-памяти выполняется как в обычных ЗУ с произвольным доступом (оперативных ЗУ или КЭШ). Однако запись сохраняет в себе некоторые особенности, аналогичные свойствам постоянных ЗУ. Перед записью данных в ЗУ ячейки, в которые будет производиться запись, должны быть очищены (стерты). Стирание заключается в переводе элементов памяти в состояние единицы и возможно только сразу для целого блока ячеек (в первых микросхемах предусматривалось стирание только для всей матрицы сразу). Выборочное стирание невозможно. Фактически при операции записи производится два действия: запись и считывание, но управление этими операциями производится внутренним автоматом и "прозрачно" для процессора.