ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6693
Скачиваний: 8
78 Глава 2. Организация компьютерных систем
счета контрольных разрядов допустимы только 2
Ш
из 2" кодированных слов. Если
в памяти обнаруживается недопустимое кодированное слово, компьютер знает, что
произошла ошибка. При наличии алгоритма для подсчета контрольных разрядов
можно составить полный список допустимых кодированных слов и из этого спис-
ка найти два слова, для которых интервал Хэмминга будет минимальным. Это ин-
тервал Хэмминга полного кода.
Свойства проверки и исправления ошибок определенного кода зависят от его
интервала Хэмминга. Чтобы обнаружить d ошибок в битах, необходим код с ин-
тервалом d+1, поскольку d ошибок не могут изменить одно допустимое кодиро-
ванное слово на другое допустимое кодированное слово Соответственно, чтобы
исправить d ошибок в битах, необходим код с интервалом 2d+l, поскольку в этом
случае допустимые кодированные слова так сильно отличаются друг от друга, что
даже если произойдет d изменений, изначальное кодированное слово будет ближе
к ошибочному, чем любое другое кодированное слово, поэтому его без труда можно
будет определить.
В качестве простого примера кода с обнаружением ошибок рассмотрим код,
в котором к данным присоединяется один бит четности. Бит четности выбирается
таким образом, что число битов со значением 1 в кодированном слове четное (или
нечетное). Интервал этого кода равен 2, поскольку любая ошибка в битах приво-
дит к кодированному слову с неправильной четностью. Другими словами, доста-
точно двух ошибок в битах для перехода от одного допустимого кодированного
слова к другому допустимому слову. Такой код может использоваться для обнару-
жения одиночных ошибок. Если из памяти считывается слово, содержащее невер-
ную четность, поступает сигнал об ошибке. Программа не сможет продолжаться,
но зато не будет неверных результатов.
В качестве простого примера кода с исправлением ошибок рассмотрим код с
четырьмя допустимыми кодированными словами:
0000000000,0000011111, ШИОООООи 1111111111
Интервал этого кода равен 5 Это значит, что он может исправлять двойные
ошибки. Если появляется кодированное слово 0000000111, компьютер знает, что
изначальное слово должно быть 0000011111 (если произошло не более двух оши-
бок). При наличии трех ошибок, если, например, слово 0000000000 изменилось на
0000000111, этот метод недопустим.
Представим, что мы хотим разработать код с m битами данных и г контрольных
разрядов, который позволил бы исправлять все ошибки в битах. Каждое из 2
т
до-
пустимых слов имеет п недопустимых кодированных слов, которые отличаются от
допустимого одним битом. Они образуются инвертированием каждого из п битов
в n-битном кодированном слове. Следовательно, каждое из 2
т
допустимых слов
требует п+1 возможных сочетаний битов, приписываемых этому слову (п возмож-
ных ошибочных вариантов и один правильный). Поскольку общее число различ-
ных сочетаний битов равно 2
П
, то (п+1)2
га
<2
п
. Так как n-ш+г, следовательно,
(т+г+ 1)<2
Г
. Эта формула дает нижний предел числа контрольных разрядов, необ-
ходимых для исправления одиночных ошибок. В табл 2.2 показано необходимое
количество контрольных разрядов для слов разного размера.
Основная память
79
Таблица 2.2.
Число контрольных разрядов для кода, способного исправлять
одиночные ошибки
Размер Количество контрольных Общий размер На сколько процентов
слова разрядов увеличилась длина слова
8
16
32
64
128
256
512
4
5
6
7
8
9
10
12
21
38
71
136
265
522
50
31
19
11
6
4
2
Этого теоретического нижнего предела можно достичь, используя метод Ричар-
да Хэмминга. Но прежде чем обратиться к этому алгоритму, давайте рассмотрим
простую графическую схему, которая четко иллюстрирует идею кода с исправле-
нием ошибок для 4-битных слов. Диаграмма Венна на рис. 2.11 содержит 3 круга,
А, В и С, которые вместе образуют семь секторов. Давайте закодируем в качестве
примера слово из 4 битов 1100 в сектора АВ, ABC, AC и ВС, по одному биту в каж-
дом секторе (в алфавитном порядке). Кодирование показано на рис. 2.11,
а.
Рис. 2 . 1 1 .
Кодировка числа 1100 (а); добавляются биты четности
(б);
ошибка в секторе АС (в)
Далее мы добавим бит четности к каждому из трех пустых секторов, чтобы по-
лучилась положительная четность, как показано на рис. 2.11,
б.
По определению
сумма битов в каждом из трех кругов, А, В, и С, должна быть четной. В круге А
находится 4 числа: 0, 0, 1 и 1, которые в сумме дают четное число 2. В круге В
находятся числа 1, 1, 0 и 0, которые также при сложении дают четное число 2.
То же имеет силу и для круга С. В данном примере получилось так, что все суммы
одинаковы, но вообще возможны случаи с суммами 0 и 4. Рисунок соответствует
кодированному слову, состоящему из 4 битов данных и 3 битов четности.
Предположим, что бит в секторе АС изменился с 0 на 1, как показано на
рис. 2.11,
в.
Компьютер видит, что круги А и С имеют отрицательную четность.
Единственный способ исправить ошибку, изменив только один бит, — возвраще-
ние биту АС значения 0. Таким способом компьютер может исправлять одиноч-
ные ошибки автоматически.
А теперь посмотрим, как может использоваться алгоритм Хэмминга при созда-
нии кодов с исправлением ошибок для слов любого размера. В коде Хэмминга к
80 Глава 2. Организация компьютерных систем
слову, состоящему из m битов, добавляется г битов четности, при этом образуется
слово длиной т+г битов. Биты нумеруются с единицы (а не с нуля), причем первым
считается крайний левый. Все биты, номера которых — степени двойки, являются
битами четности; остальные используются для данных. Например, к 16-битному
слову нужно добавить 5 битов четности. Биты с номерами 1, 2, 4, 8 и 16 — биты
четности, а все остальные — биты данных. Всего слово содержит 21 бит (16 битов
данных и 5 битов четности). В рассматриваемом примере мы будем использовать
положительную четность (выбор произвольный).
Каждый бит четности проверяет определенные битовые позиции. Общее число
битов со значением 1 в проверяемых позициях должно быть четным. Ниже указа-
ны позиции проверки для каждого бита четности:
Бит 1 проверяет биты 1, 3, 5,7, 9,11, 13,15,17,19, 21.
Бит 2 проверяет биты 2, 3, 6, 7,10,11,14,15,18,19.
Бит 4 проверяет биты 4, 5,6, 7,12,13,14,15, 20, 21.
Бит 8 проверяет биты 8,9,10, И, 12,13,14, 15.
Бит 16 проверяет биты 16,17,18,19, 20, 21.
В общем случае бит b проверяется битами
Ъ
и
Ь
2
,...,
b
Jt
такими что bi+b
2
+... +b,=b.
Например, бит 5 проверяется битами 1 и 4, поскольку 1+4=5. Бит 6 проверяется
битами 2 и 4, поскольку 2+4=6 и т. д.
На рис. 2.12 показано построение кода Хэмминга для 16-битного слова
1111000010101110 Соответствующим 21-битным кодированным словом являет-
ся 001011100000101101110. Чтобы увидеть, как происходит исправление ошибок,
рассмотрим, что произойдет, если бит 5 изменит значение из-за резкого скачка
напряжения на линии электропередачи. В результате вместо кодированного слова
001011100000101101110 получится 001001100000101101 ПО. Будут проверены
5 битов четности. Вот результаты проверки:
Бит четности 1 неправильный (биты 1, 3, 5, 7,9, 11, 13, 15, 17, 19, 21 содержат
пять единиц).
Бит четности 2 правильный (биты 2, 3, 6,7,10,11,14,15,18,19 содержат шесть
единиц).
Бит четности 4 неправильный (биты 4,5,6,7,12,13,14,15,20,21 содержат пять
единиц).
Бит четности 8 правильный (биты 8,9,10,11,12,13,14,15 содержат две единицы).
Битчетности 16 правильный (биты 16,17,18,19,20,21 содержат четыре единицы).
Общее число единиц в битах 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 и 21 должно быть
четным, поскольку в данном случае используется положительная четность. Непра-
вильным должен быть один из битов, проверяемых битом четности 1 (а именно 1,
3,5,7,9,11,13,15,17,19 и 21). Бит четности 4 тоже неправильный. Это значит, что
изменил значение один из следующих битов: 4,5,6,7,12,13,14,15,20,21. Ошибка
должна быть в бите, который содержится в обоих списках. В данном случае общими
являются биты 5,7,13,15 и 21. Поскольку бит четности 2 правильный, биты 7 и 15
исключаются. Правильность бита четности 8 исключает наличие ошибки в бите 13.
Наконец, бит 21 также исключается, поскольку бит четности 16 правильный. В итоге
остается бит 5, в котором и содержится ошибка. Поскольку этот бит имеет значе-
ние 1, он должен принять значение 0. Именно таким образом исправляются ошибки.
Основная память 81
Слово памяти 1111000010101110
1 2 3 4 5 6
7 8
9 10 11 12 13 14 15 16
17 18
19
20
21
Рис. 2.12.
Построение кода Хэмминга для слова 1111000010101110с помощью
добавления 5 контрольных разрядов к ,16 битам данных
Чтобы найти неправильный бит, сначала нужно подсчитать все биты четности.
Если они правильные, ошибки нет (или есть, но больше одной). Если обнаружились
неправильные биты четности, то нужно сложить их номера. Сумма, полученная
в результате, даст номер позиции неправильного бита. Например, если биты четнос-
ти 1 и 4 неправильные, а 2,8 и 16 правильные, то ошибка произошла в бите 5 (1+4).
Кэш-память
Процессоры всегда работали быстрее, чем память. Процессоры и память совер-
шенствовались параллельно, поэтому это несоответствие сохранялось. Поскольку
на микросхему можно помещать все больше и больше транзисторов, разработчики
процессоров использовали эти преимущества для создания конвейеров и супер-
скалярной архитектуры, что еще больше повышало скорость работы процессоров.
Разработчики памяти обычно использовали новые технологии для увеличения ем-
кости, а не скорости, что еще больше усугубляло проблему. На практике такое не-
соответствие в скорости работы приводит к следующему: после того как процес-
сор дает запрос памяти, должно пройти много циклов, прежде чем он получит слово,
которое ему нужно. Чем медленнее работает память, тем дольше процессору при-
ходится ждать, тем больше циклов должно пройти.
Как мы уже говорили выше, есть два пути решения этой проблемы. Самый про-
стой из них — начать считывать информацию из памяти, когда это необходимо, и
при этом продолжать выполнение команд, но если какая-либо команда попытает-
ся использовать слово до того, как оно считалось из памяти, процессор должен
приостанавливать работу. Чем медленнее работает память, тем чаще будет возни-
кать такая проблема и тем больше будет проигрыш в работе. Например, если от-
срочка составляет 10 циклов, весьма вероятно, что одна из 10 следующих команд
попытается использовать слово, которое еще не считалось из памяти.
Другое решение проблемы — сконструировать машину, которая не приостанав-
ливает работу, но следит, чтобы программы-компиляторы не использовали слова
до того, как они считаются из памяти. Однако это не так просто осуществить на
практике. Часто при выполнении команды загрузки машина не может выполнять
другие действия, поэтому компилятор вынужден вставлять пустые команды, кото-
рые не производят никаких операций, но при этом занимают место в памяти. В дей-
ствительности при таком подходе простаивает не аппаратное, а программное обес-
печение, но снижение производительности при этом такое же.
82 Глава 2. Организация компьютерных систем
На самом деле эта проблема не технологическая, а экономическая. Инженеры
знают, как построить память, которая будет работать так же быстро, как и процес-
сор, но при этом ее приходится помещать прямо на микросхему процессора (по-
скольку информация через шину поступает очень медленно). Установка большой
памяти на микросхему процессора делает его больше и, следовательно, дороже, и
даже если бы стоимость не имела значения, все равно существуют ограничения в
размерах процессора, который можно сконструировать. Таким образом, приходится
выбирать между быстрой памятью небольшого размера и медленной памятью боль-
шого размера. Мы бы предпочли память большого размера с высокой скоростью
работы по низкой цене.
Интересно отметить, что существуют технологии сочетания маленькой и быст-
рой памяти с большой и медленной, что позволяет получить и высокую скорость
работы, и большую емкость по разумной цене. Маленькая память с высокой ско-
ростью работы называется
кэш-памятью
(от французского слова cacher «прятать»
1
;
читается «кэш»). Ниже мы кратко опишем, как используется кэш-память и как
она работает. Более подробное описание см. в главе 4.
Основная идея кэш-памяти проста: в ней находятся слова, которые чаще всего
используются. Если процессору нужно какое-нибудь слово, сначала он обращает-
ся к кэш-памяти. Только в том случае, если слова там нет, он обращается к основ-
ной памяти. Если значительная часть слов находится в кэш-памяти, среднее время
доступа значительно сокращается.
Таким образом, успех или неудача зависит от того, какая часть слов находится
в кэш-памяти. Давно известно, что программы не обращаются к памяти наугад.
Если программе нужен доступ к адресу А, то скорее всего после этого ей понадо-
бится доступ к адресу, расположенному поблизости от А. Практически все коман-
ды обычной программы (за исключением команд перехода и вызова процедур)
вызываются из последовательных участков памяти. Кроме того, большую часть
времени программа тратит на циклы, когда ограниченный набор команд выполня-
ется снова и снова. Точно так же при манипулировании матрицами программа ско-
рее всего будет обращаться много раз к одной и той же матрице, прежде чем перей-
дет к чему-либо другому.
То, что при последовательных отсылках к памяти в течение некоторого проме-
жутка времени используется только небольшой ее участок, называется
принци-
пом локальности.
Этот принцип составляет основу всех систем кэш-памяти. Идея
состоит в следующем: когда определенное слово вызывается из памяти, оно вмес-
те с соседними словами переносится в кэш-память, что позволяет при очередном
запросе быстро обращаться к следующим словам. Общее устройство процессора,
кэш-памяти и основной памяти показано на рис. 2.13. Если слово считывается или
записывается к раз, компьютеру понадобится сделать 1 обращение к медленной
основной памяти и к-1 обращений к быстрой кэш-памяти. Чем больше к, тем выше
общая производительность.
В английском «cash* получило значение «наличные (карманные) деньги», то есть то, что под рукой
А уже из него и образовался термин «кэш», который относят к сверхоперативной памяти. —
Примеч
научн, ред.