ВС для ГОС (ПИ) / Орлов, Цилькер - Организация ЭВМ (2004)

2 3 6 Глава 5. Память

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

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

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

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

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

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

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

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

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

•Нe обнаружено ни одной ошибки. Извлеченные из ячейки данные подаются на выход памяти.

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

•Обнаружена ошибка, и она не может быть исправлена. Выдается сообщение

онеисправимой ошибке.

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

Рис. 5.15 Общая схема обнаружения и исправления ошибок [200]

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

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

В основе корректирующих кодов лежит достаточно простая идея [39]. Для контроля двоичного информационного кода длиной М бит добавим к ней К дополнительных контрольных разрядов так, что общая длина последовательности теперь будет равна М + К разрядам. В этом случае из возможных N= 2М+К комбинаций интерес представляют только L = 2м последовательностей, которые называют разрешенными. Оставшиеся N- L последовательностей назовем запрещенными. Если при обработке (записи в память, считывании или передаче) разрешенной кодовой последовательности произойдут ошибки и возникнет одна из запрещенных последовательностей, то тем самым эти ошибки обнаруживаются. Если же ошибки превратят одну разрешенную последовательность в другую, то такие ошибки не могут быть обнаружены. Для исправления ошибок необходимо произвести разбиение множества запрещенных последовательностей на L непересекающихся подмно-

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

Рис. 5.16. Иллюстрация кода Хэмминга для четырехразрядного слова

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

Для пояснения концепции, положенной в основу кода Хэмминга, построим код, обнаруживающий и исправляющий однобитовые ошибки в 8-разрядных словах (пример взят из [47]).

Сначала определим требуемую длину корректирующего кода. В соответствии с рис. 5.15, на вход схемы сравнения поступают два К-разрядных значения. Сравнение производится путем поразрядной операции «исключающее ИЛИ» (сложение по модулю 2) над входными кодами. Результатом является так называемое слово синдрома. В зависимости от того, было ли совпадение входных кодов или нет, соответствующий бит синдрома будет равен 0 или 1.

Слово синдрома состоит из К разрядов, то есть его возможные значения лежат в диапазоне от 0 до 2К - 1. Значение 0 соответствует случаю, когда ошибки не обнаружено, остальные 2К - 1 случая свидетельствуют о наличии ошибки и указывают

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

Таким образом, для рассматриваемого случая значения контрольных разрядов вычисляются по следующим правилам:

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

Предположим, что данные в бите 3 содержат ошибку и там вместо 0 находится 1. После пересчета контрольных разрядов имеем

Путем сложения по модулю двух результатов старой и новой проверок получим слово синдрома (S8S4S2S1):

Результат 01102 (610) означает, что в разряде 6, содержащем третий бит данных, присутствует ошибка.

Описанный код называется кодом с исправлением одиночной ошибки (SEC — Single Error Correcting). В большинстве микросхем памяти используется код с исправлением одиночной и обнаружением двойной ошибки (SECDED — Single Error Correcting, Double Error Detecting). Из табл. 5.2 видно, что, по сравнению с SEC, такой код требует одного дополнительного контрольного разряда.

Коды с исправлением ошибок применяются в большинстве ВМ. Например, в основной памяти ВМ типа IBM ЗОхх используется 8-разрядный код SECDED на каждые 64 бита данных, то есть емкость памяти примерно на 12% больше, чем имеет в своем распоряжении пользователь. В ВМ типа VAX на каждые 32 разряда данных добавлен 7-разрядный код SECDED, следовательно, избыточность составляет 22%.

242 Глава 5. Память

Структура одного из вариантов построения устройства для обнаружения одинарных и двойных ошибок с коррекцией одинарных ошибок приведена на рис. 5.17. Схема предназначена для контроля 16-разрядных данных и размещается между процессором и памятью. Из табл. 5.2 видно, что код SECDED предполагает шесть дополнительных разрядов. Таким образом, из процессора и в процессор поступают 16-разрядные коды (UD15...UD0), а в память заносятся 22-разрядные данные (M21... M0). Хранящаяся в ячейках памяти информация состоит из 16 бит информации (MD15... MD0) и 6 контрольных битов (MP5... MР0). В последующем первые буквы в обозначении разрядов могут быть опущены, при этом D будет означать информационный разряд кода, а Р — контрольный разряд.

Система размещения основных и контрольных разрядов была рассмотрена ранее, и для данной схемы она приведена в табл. 5.4.

Таблица 5.4. Распределение информационных и контрольных разрядов в 22-разрядном слове

Особенность рассматриваемой схемы состоит в способе формирования контрольного разряда Р5. Он вычисляется путем суммирования по модулю 2 всех остальных 21 разрядов кода (D15... D0 и МР4... MР0). По мнению авторов рассматриваемой схемы, это облегчает фиксацию факта неисправимой двойной ошибки.

При чтении из памяти формирователем синдрома вычисляется синдром S4... S0:

Здесь Р4... Р0 — контрольные разряды, вычисленные генератором контрольных разрядов на основании информационных битов считанного из памяти кода (MD15...

MD0). MP5... MР0 — такие же контрольные разряды, полученные тем же генератором, но перед записью информации в память и хранившиеся там вместе с основ-

Ассоциативная память 2 4 5

увеличивается на единицу. Таким образом, при извлечении слова из стека реализуются следующие операции: ШД:= ОП[(УС)]; УС := УС +1.

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

В рассмотренных ранее видах запоминающих устройств доступ к информации требовал указания адреса ячейки. Зачастую значительно удобнее искать информацию не по адресу, а опираясь на какой-нибудь характерный признак, содержащийся в самой информации. Такой принцип лежит в основе ЗУ, известного как ассоциативное запоминающее устройство (АЗУ). В литературе встречаются и иные названия подобного ЗУ: память, адресуемая по содержанию (content addressable memory); память, адресуемая по данным (data addressable memory); память с параллельным поиском (parallel search memory); каталоговая память (catalog memory); информационное ЗУ (information storage); тегированная память (tag memory). Ассоциативное ЗУ — это устройство, способное хранить информацию, сравнивать ее с некоторым заданным образцом и указывать на их соответствие или несоответствие друг другу. Признак, по которому производится поиск информации, будем называть ассоциативным признаком, а кодовую комбинацию, выступающую в роли образца для поиска, — признаком поиска. Ассоциативный признак может быть частью искомой информации или дополнительно придаваться ей. В последнем случае его принято называть тегом или ярлыком.

Рис. 5.19. Структура ассоциативного запоминающего устройства

Один из вариантов построения ассоциативной памяти показан на рис. 5.19. АЗУ включает в себя:

•запоминающий массив для хранения N m-разрядных слов, в каждом из которых несколько младших разрядов занимает служебная информация;

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