RAID-массивы

Производительность процессоров за последнее десятилетие значительно возрос­ла, увеличиваясь почти вдвое каждые 1,5 года. Однако с производительностью дисков дело обстоит иначе. В 70-х годах среднее время поиска в мини-компьюте­рах составляло от 50 до 100 мс. Сейчас время поиска составляет около 10 мс. Во многих технических отраслях (например, в автомобильной или авиационной промышленности) повышение производительности в 5 или 10 раз за два десяти­летия считалось бы грандиозным, но в компьютерной индустрии эти цифры вы­зывают недоумение. Таким образом, разрыв между производительностью про­цессоров и дисков все это время продолжал расти.

Как мы уже видели, для того чтобы увеличить быстродействие процессора, используются технологии параллельной обработки данных. Уже на протяжении многих лет разным людям приходит в голову мысль, что было бы неплохо сде­лать так, чтобы устройства ввода-вывода также могли работать параллельно. В 1988 году в статье [162] было предложено 6 разных вариантов организации дисковой памяти, которые могли использоваться для повышения производи­тельности, надежности или того и другого. Эти идеи были сразу заимствованы производителями компьютеров, что привело к появлению нового класса уст­ройств ввода-вывода под названием RAID. Изначально аббревиатура RAID рас­шифровывалась как Redundant Array of Inexpensive Disks (избыточный массив недорогих дисков), но позже буква I в аббревиатуре вместо изначального Inexpensive (недорогой) стала означать Independent (независимый). Может быть, это дало производителям законное право делать диски неоправданно доро­гими? RAID-массиву противопоставлялся диск SLED (Single Large Expensive Disk — один большой дорогостоящий диск).

Основная идея RAID состоит в следующем. Рядом с компьютером (обычно большим сервером) устанавливается бокс с дисками, контроллер диска замеща­ется RAID-контроллером, данные копируются в RAID-массив, а затем произво­дятся обычные действия. Иными словами, операционная система воспринимает RAID как SLED, при этом у RAID-массива выше производительность и надеж­ность. Поскольку SCSI-диски обладают высокой производительностью при до­вольно низкой цене и при этом один контроллер может управлять несколькими дисками (до семи дисков на 8-разрядных моделях SCSI и до 15 на 16-разряд­ных), большинство RAID-устройств состоит из SCSI-контроллера, предназна­ченного для управления RAID-массивом, и бокса SCSI-дисков, которые опера­ционная система воспринимает как один большой диск. Таким образом, чтобы использовать RAID-массив, не требуется никаких изменений в программном обеспечении, что очень выгодно для многих системных администраторов.

RAID-системы имеют несколько достоинств. Во-первых, как уже отмечалось, программное обеспечение воспринимает RAID-массив как один большой диск. Во-вторых, данные на всех дисках RAID-массива распределены по дискам таким образом, чтобы можно было осуществлять параллельные операции. Несколько различных вариантов распределения данных, предложенных в [162], сейчас из­вестны как RAID-массив уровня 0, RAID-массив уровня 1 и т. д., вплоть до RAID-массива уровня 5. Кроме того, существует еще несколько уровней, кото­рые мы не будем обсуждать. Термин «уровень» несколько неудачный, поскольку здесь нет никакой иерархической структуры. Просто существуют 6 разных вари­антов организации дисков.

RAID-массив уровня 0 показан на рис. 2.19, а. Он представляет собой вирту­альный диск, разделенный на полосы (strips) по k секторов каждая, при этом сек­торы с 0 по k - 1 занимают полосу 0, секторы с k по 2k - 1 — полосу 1 и т. д. Для k = 1 каждая полоса — это сектор, для k = 2 каждая полоса — это два сектора и т. д. В RAID-массиве уровня 0 полосы последовательно записываются по кругу, как показано на рис. 2.19, а. Это называется распределением данных (striping) по дискам. На рисунке изображен RAID-массив с четырьмя дисками. Например, если программное обеспечение вызывает команду для считывания блока дан­ных, состоящего из четырех последовательных полос и начинающегося на грани­це между полосами, то RAID-контроллер разбивает эту команду на 4 отдельные команды, каждую для одного из четырех дисков, и выполняет их параллельно. Таким образом, мы получаем устройство параллельного ввода-вывода без изме­нения программного обеспечения.

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

RAID-массив уровня 0 хуже всего работает с операционными системами, которые время от времени запрашивают небольшие порции данных (по одному сектору за обращение). В этом случае результаты окажутся, конечно, правиль­ными, но не будет никакого параллелизма и, следовательно, никакого выигры­ша в производительности. Другой недостаток такой структуры состоит в том, что надежность у нее потенциально ниже, чем у SLED-диска. Например, рас­смотрим RAID-массив, состоящий из четырех дисков, на каждом из которых могут происходить сбои в среднем каждые 20 ООО часов. То есть сбои в таком RAID-массиве будут случаться примерно через каждые 5000 часов, при этом все данные могут быть утеряны. У SLED-диска сбои происходят также в сред­нем каждые 20 000 часов, но, так как это всего один диск, его надежность в 4 раза выше. Поскольку в описанной разработке нет никакой избыточности, это «ненастоящий»¹ RAID-массив.

Следующая разновидность — RAID-массив уровня 1. Он показан на рис. 2.19, б и, в отличие от RAID-массива уровня 0, является настоящим RAID-массивом². В этой структуре дублируют все диски, таким образом получается 4 исходных диска и 4 резервные копии.

¹ На самом деле настоящий, но нулевого уровня. — Примеч. научн. ред.

² На рис. 2.19, б изображен RAID уровня 0 + 1, а не уровня 1. — Примеч. научн. ред.

Рис. 2.19. RAID-массивы с нулевого по пятый уровень. Резервные копии и диски четности

закрашены серым цветом

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

В отличие от уровней 0 и 1, которые работают с полосами секторов, RAID-массив уровня 2 оперирует словами, а иногда даже байтами. Представим, что каждый байт виртуального диска разбивается на два фрагмента по 4 бита, за­тем к каждому из них добавляется код Хэмминга, и таким образом получается слово из 7 бит, у которого 1, 2 и 4 — биты четности. Затем представим, что 7 дис­ков, изображенные на рис. 2.19, в, синхронизированы по позиции кронштейна и позиции вращения. Тогда за одну операцию можно записать слово из 7 бит с кодом Хэмминга на 7 дисков, по одному биту на диск.

Подобная схема использовалась в так называемых думающих машинах СМ-2. К 32-разрядному слову с данными добавлялось 6 бит четности (код Хэмминга). В результате получалось 38-разрядное кодовое слово, к которому добавлялся до­полнительный бит четности, и это слово записывалось на 39 дисков. Общая про­изводительность была огромной, так как одновременно могло записываться 32 сектора данных. При утрате одного из дисков проблем также не возникало, поскольку потеря одного диска означала потерю одного бита в каждом 39-раз­рядном слове, а с этим код Хэмминга справлялся моментально.

Однако подобная схема требует, чтобы все диски были синхронизированы по вращению. Кроме того, ее имеет смысл использовать, только если имеется доста­точно большое количество дисков (даже при наличии 32 дисков для данных и 6 дисков для битов четности накладные расходы составляют 19 %). К тому же имеет место большая нагрузка на контроллер, поскольку он должен вычислять контрольную сумму кода Хэмминга при передаче каждого бита.

RAID-массив уровня 3 представляет собой упрощенную версию RAID-масси­ва уровня 2. Он изображен на рис. 2.19, г. Здесь для каждого слова данных вы­числяется 1 бит четности и записывается на диск четности. Как и в RAID-масси­ве уровня 2, диски должны быть точно синхронизированы, поскольку каждое слово данных распределено по нескольким дискам.

На первый взгляд может показаться, что один бит четности позволяет только обнаруживать, но не исправлять ошибки. Если речь идет о произвольных ошиб­ках, это наблюдение верно. Однако если речь идет о сбое диска, бит четности обеспечивает исправление ошибки в одном бите, поскольку позиция неправиль­ного бита известна. Если происходит сбой, контроллер выдает информацию, что все биты равны 0. Если в слове возникает ошибка четности, бит с диска, на кото­ром произошел сбой, должен быть равен 1, и, следовательно, он исправляется. Хотя RAID-массивы уровней 2 и 3 обеспечивают очень высокую скорость пере­дачи данных, число запросов от устройств ввода-вывода в секунду не больше, чем при наличии одного диска.

RAID-массивы уровней 4 и 5, как и RAID-массивы начальных уровней, рабо­тают с полосами, а не со словами, имеющими биты четности, и не требуют син­хронизации дисков. RAID-массив уровня 4 (см. рис. 2.19, д) устроен так же, как RAID-массив уровня 0, с тем различием, что у RAID-массива уровня 4 есть до­полнительный диск, на который записываются полосы четности. Например, пусть каждая полоса состоит из k байт. Все полосы должны находиться в отношении ИСКЛЮЧАЮЩЕГО ИЛИ, и полоса четности для проверки этого отношения также должна состоять из k байт. Если происходит сбой на диске, утраченные байты могут быть вычислены заново при помощи информации с диска четности.

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

Такие трудности при загрузке данных на диск четности могут быть препятст­вием для достижения высокой производительности. Эта проблема устраняется в RAID-массиве уровня 5, в котором биты четности распределяются равномерно по всем дискам и записываются по кругу, как показано на рис. 2.19, е. Однако в случае сбоя диска восстановить содержание утраченного диска достаточно слож­но, хотя и можно.

Источник: Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.

Кэш-память

 

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

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

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

На самом деле эта проблема не технологическая, а экономическая. Инженеры знают, как создать память, которая работает так же быстро, как процессор. Одна­ко ее приходится помещать прямо на микросхему процессора (поскольку инфор­мация через шину поступает очень медленно). Размещение памяти большого объема на микросхеме процессора делает его больше и, следовательно, дороже, и даже если бы стоимость не имела значения, все равно существуют ограничения на размеры создаваемых процессоров. Таким образом, приходится выбирать между быстрой памятью небольшого объема и медленной памятью большого объема. (Мы, естественно, предпочли бы иметь быструю память большого объе­ма и к тому же дешевую.)

Интересно отметить, что существуют технологии, объединяющие небольшую и быструю память с большой и медленной, что позволяет по разумной цене по­лучить память и с высокой скоростью работы, и большой емкости. Память не­большого объема с высокой скоростью работы называется кэш-памятью (от французского слова «сасЬег» — «прятать»¹; читается «кашэ»). Далее мы кратко опишем, как используется кэш-память и как она работает. Более подробное опи­сание вы найдете в главе 4.

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

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

¹ В английском языке слово «cash» получило значение «наличные (карманные) деньги», то есть то, что под рукой. А уже из него и образовался термин «кэш», который относят к сверхоперативной па­мяти. — Примем, научн. ред.

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

Ситуация, когда при последовательных обращениях к памяти в течение неко­торого промежутка времени используется только небольшая ее область, назы­вается принципом локальности. Этот принцип составляет основу всех систем кэш-памяти. Идея состоит в том, что когда определенное слово вызывается из памяти, оно вместе с соседними словами переносится в кэш-память, что позво­ляет при очередном запросе быстро обращаться к следующим словам. Общее устройство процессора, кэш-памяти и основной памяти иллюстрирует рис. 2.13. Если слово считывается или записывается k раз, компьютеру требуется сделать 1 обращение к медленной основной памяти и k - 1 обращений к быстрой кэш-па­мяти. Чем больше тем выше общая производительность.

Шина

Рис. 2.13. Кэш-память по логике вещей должна находиться между процессором и основной памятью. В действительности существует три возможных варианта размещения кэш-памяти

Мы можем сделать и более строгие вычисления. Пусть с — время доступа к кэш-памяти, т — время доступа к основной памяти и h — коэффициент кэш-по­паданий (hit ratio), который показывает соотношение числа обращений к кэш памяти и общего числа всех обращений к памяти. В нашем примере h = (k - l)/k. Некоторые авторы выделяют коэффициент кэш-промахов (miss ratio), равный 1 -h.

Таким образом, мы можем вычислить среднее время доступа: Среднее время доступа = с + (1 - К) т.

Если h —> 1, то есть все обращения делаются только к кэш-памяти, то время доступа стремится к с. С другой стороны, если h —» 0, то есть каждый раз нужно обращаться к основной памяти, то время доступа стремится кс + ш: сначала тре­буется время с для проверки кэш-памяти (в данном случае безуспешной), а за­тем — время т для обращения к основной памяти. В некоторых системах обра­щение к основной памяти может начинаться параллельно с исследованием кэш-памяти, чтобы в случае кэш-промаха цикл обращения к основной памяти уже начался. Однако эта стратегия требует способности останавливать процесс обращения к основной памяти в случае кэш-попадания, что усложняет разработ­ку подобного компьютера.

Основная память и кэш-память делятся на блоки фиксированного размера с учетом принципа локальности. Блоки внутри кэш-памяти обычно называют строками кэша (cache lines). При кэш-промахе из основной памяти в кэш-па­мять загружается вся строка, а не только необходимое слово. Например, если строка состоит из 64 байт, обращение к адресу 260 влечет за собой загрузку в кэш-память всей строки (байты с 256 по 319) на случай, если через некоторое время понадобятся другие слова из этой строки. Такой путь обращения к памяти более эффективен, чем вызов каждого слова по отдельности, потому что одно кратный вызов k слов происходит гораздо быстрее, чем вызов одного слова k раз.

Кэш-память очень важна для высокопроизводительных процессоров. Однако здесь возникает ряд вопросов. Первый вопрос — объем кэш-памяти. Чем больше объем, тем лучше работает память, но тем дороже она стоит. Второй вопрос — размер строки кэша. Кэш-память объемом 16 Кбайт можно разделить на 1024 строки по 16 байт, 2048 строк по 8 байт и т. д. Третий вопрос — механизм орга­низации кэш-памяти, то есть то, как она определяет, какие именно слова нахо­дятся в ней в данный момент. Устройство кэш-памяти мы рассмотрим подробно в главе 4.

Четвертый вопрос — должны ли команды и данные находиться вместе в об­щей кэш-памяти. Проще всего разработать объединенную кэш-память (unified cache), в которой будут храниться и данные и команды. В этом случае вызов ко­манд и данных автоматически уравновешивается. Однако в настоящее время существует тенденция к использованию разделенной кэш-памяти (split cache), когда команды хранятся в одной кэш-памяти, а данные — в другой. Такая архи­тектура также называется гарвардской (Harvard architecture), поскольку идея использования отдельной памяти для команд и отдельной памяти для данных впервые воплотилась в компьютере Marc III, который был создан Говардом Айкеном (Howard Aiken) в Гарварде. Современные разработчики пошли по это му пути, поскольку сейчас широко распространены конвейерные архитектуры, а при конвейерной организации должна быть возможность одновременного дос­тупа и к командам, и к данным (операндам). Разделенная кэш-память позволяет осуществлять параллельный доступ, а общая — нет. К тому же, поскольку коман­ды обычно не меняются во время выполнения программы, содержание кэша ко­манд не приходится записывать обратно в основную память.

Наконец, пятый вопрос — количество блоков кэш-памяти. В настоящее время очень часто кэш-память первого уровня располагается прямо на микросхеме процессора, кэш-память второго уровня — не на самой микросхеме, но в корпусе процессора, а кэш-память третьего уровня — еще дальше от процессора.

Источник: Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.

Код исправления ошибок

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

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

Для любых двух кодовых слов, например 10001001 и 10110001, можно опре­делить, сколько соответствующих битов в них различаются. В данном примере таких бита три. Чтобы определить количество различающихся битов, нужно над двумя кодовыми словами произвести логическую операцию ИСКЛЮЧАЮЩЕЕ ИЛИ и сосчитать количество битов со значением 1 в полученном результате. Число битовых позиций, по которым различаются два слова, называется интер­валом Хэмминга [85]. Если интервал Хэмминга для двух слов равен d, значит, что достаточно d битовых ошибок, чтобы превратить одно слово в другое. На­пример, интервал Хэмминга для кодовых слов 11110001 и 00110000 равен 3, по­скольку для превращения первого слова во второе достаточно 3 битовые ошибки.

Память состоит из m-разрядных слов, следовательно, существуют 2^т вариан­тов сочетания битов. Кодовые слова состоят из п бит, но из-за способа подсчета контрольных разрядов допустимы только 2^т из 2^п кодовых слов. Если в памяти обнаруживается недопустимое кодовое слово, компьютер знает, что произошла ошибка. При наличии алгоритма подсчета контрольных разрядов можно соста­вить полный список допустимых кодовых слов, и из этого списка найти два сло­ва, для которых интервал Хэмминга будет минимальным. Это интервал Хэммин­га для полного кода.

Возможности проверки и исправления ошибок определенного кода зависят от его интервала Хэмминга. Чтобы обнаружить d ошибок в битах, необходим код с интервалом d + 1, поскольку d ошибок не могут превратить одно допустимое кодовое слово в другое допустимое кодовое слово. Соответственно, чтобы испра­вить d ошибок в битах, необходим код с интервалом 2d + 1, поскольку в этом случае допустимые кодовые слова настолько сильно отличаются друг от друга, что, даже если произойдет d изменений, изначальное кодовое слово окажется ближе к ошибочному, чем любое другое кодовое слово, поэтому его без труда можно будет выявить.

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

В качестве простого примера кода исправления ошибок рассмотрим код с че­тырьмя допустимыми кодовыми словами: 0000000000, 0000011111, 1111100000 и 1111111111.

Интервал Хэмминга для этого кода равен 5. Это значит, что он может исправ­лять двойные ошибки. Если появляется кодовое слово 0000000111, компьютер знает, что изначально это слово выглядело как 0000011111 (если произошло не более двух ошибок). При появлении трех ошибок (например, слово 0000000000 меняется на 0000000111) этот метод не подходит.

Представим, что мы хотим разработать код, в котором т бит данных и г кон­трольных разрядов, позволяющий исправлять все одиночные битовые ошибки. Каждое из 2^т допустимых слов имеет п недопустимых кодовых слов, которые от­личаются от допустимого одним битом. Они образуются инвертированием каж­дого из п бит в и-разрядном кодовом слове. Следовательно, каждое из 2^т допус­тимых слов требует п + 1 возможных сочетаний битов, приписываемых этому слову (п возможных ошибочных вариантов и один правильный). Поскольку общее число различных сочетаний битов равно 2^W, то (п + 1) 2^т < 2^п. Так как п = т + г, то (т + г + 1) < 2^Г. Эта формула дает нижний предел числа контрольных разря­дов, необходимых для исправления одиночных ошибок. В табл. 2.2 показано не­обходимое количество контрольных разрядов для слов разного размера.

Таблица 2.2. Число контрольных разрядов для кода, способного исправлять одиночные ошибки

Размер исходного	Количество	Общий размер	Процент
слова	контрольных разрядов	слова	увеличения слова
8	4	12	50
16	5	21	31
32	6	38	19
64	7	71	11
128	8	136	6
256	9	265	4
512	10	522	2

Этого теоретического нижнего предела можно достичь, используя метод Ри­чарда Хэмминга [85]. Но прежде, чем обратиться к указанному алгоритму, да­вайте рассмотрим простую графическую схему, которая четко иллюстрирует идею кода исправления ошибок для 4-разрядных слов. Диаграмма Венна на рис. 2.11 содержит 3 круга, Л, В и С, которые вместе образуют семь секторов. Да­вайте закодируем в качестве примера слово из 4 бит 1100 в сектора АВ, ABC, АС и ВС, по одному биту в каждом секторе (в алфавитном порядке). Подобное коди­рование иллюстрирует рис. 2.11, а.

а                                           б                                        в

Рис. 2.11. Кодирование числа 1100 (а); добавляются биты четности (б); ошибка в секторе АС (е)

Далее мы добавим бит четности к каждому из трех пустых секторов, чтобы сумма битов в каждом из трех кругов, Д В, и С, получилась четной, как показано на рис. 2,11, б. В круге А находится 4 числа: 0, 0, 1 и 1, которые в сумме дают чет­ное число 2. В круге В находятся числа 1, 1, 0 и 0, которые также при сложении дают четное число 2. Аналогичная ситуация и для круга С. В данном примере получилось так, что все суммы одинаковы, но вообще возможны случаи с сумма­ми 0 и 4. Рисунок соответствует кодовому слову, состоящему из 4 бит данных и 3 бит четности.

Предположим, что бит в секторе АС изменился с 0 на 1, как показано на рис. 2.11, в. Компьютер обнаруживает, что круги А и С являются нечетными. Един­ственный способ исправить ошибку, изменив только один бит, — возвращение значения 0 биту в секторе АС. Таким способом компьютер может исправлять одиночные ошибки автоматически.

А теперь посмотрим, как может использоваться алгоритм Хэмминга при соз­дании кодов исправления ошибок для слов любого размера. В коде Хэмминга к слову, состоящему из т бит, добавляются г бит четности, при этом образуется слово длиной т + г бит. Биты нумеруются с единицы (а не с нуля), причем пер­вым считается крайний левый. Все биты, номера которых — степени двойки, являются битами четности; остальные используются для данных. Например, к 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, И, 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.

В общем случае бит Ъ проверяется битами Ь_ь Ь₂,fy, такими, что b_t + b₂ + ... + + bj = b. Например, бит 5 проверяется битами 1 и 4, поскольку 1+4 = 5. Бит 6 проверяется битами 2 и 4, поскольку 2 + 4 = 6 и т. д.

Рисунок 2.12 иллюстрирует построение кода Хэмминга для 16-разрядного слова 1111000010101110. Соответствующим 21-разрядным кодовым словом является 001011100000101101110. Чтобы понять, как происходит исправление ошибок, рас­смотрим, что произойдет, если бит 5 изменит значение (например, из-за резкого скачка напряжения). В результате вместо кодового слова 001011100000101101110 получится 001001100000101101110. Будут проверены 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, И, 13, 15, 17, 19 и 21 должно быть четным, поскольку в данном случае используется проверка на четность. Непра­вильным должен быть один из битов, проверяемых битом четности 1 (а именно 1, 3, 5, 7, 9, И, 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. Именно та­ким образом исправляются ошибки.

Слово 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 добавлением к битам

данных пяти контрольных разрядов

Чтобы найти неправильный бит, сначала нужно подсчитать все биты четно­сти. Если они правильные, ошибки нет (или есть, но ошибка не однократная). Если обнаружились неправильные биты четности, нужно сложить их номера. Сумма, полученная в результате, даст номер позиции неправильного бита. На­пример, если биты четности 1 и 4 неправильные, а 2, 8 и 16 правильные, то ошибка произошла в бите 5(1 +4).

 

Источник: Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.

Матричные компьютеры

 

Многие задачи в физических и технических науках предполагают использование массивов или других упорядоченных структур. Часто одни и те же вычисления могут производиться над разными наборами данных в одно и то же время. Упо­рядоченность и структурированность программ, предназначенных для выполне­ния такого рода вычислений, очень удобны в плане ускорения вычислений за счет параллельной обработки команд. Существует две схемы ускоренного вы­полнения больших научных программ. Хотя обе схемы во многих отношениях схожи, одна из них предполагает расширение единственного процессора, другая — добавление параллельного вычислителя.

Матричный процессор (array processor) состоит из большого числа сходных процессоров, которые выполняют одну и ту же последовательность команд при­менительно к разным наборам данных. Первым в мире таким процессором был ILLIAC IV (Университет Иллинойс). Схематически он изображен на рис. 2.6 [29]. Первоначально предполагалось сконструировать машину, состоящую из че­тырех квадрантов, каждый из которых содержал матрицу размером 8 х 8 из бло­ков процессор/память. Для каждого квадранта имелся один блок контроля. Он рассылал команды, которые выполнялись всеми процессорами одновременно, при этом каждый процессор использовал собственные данные из собственной памяти (загрузка данных происходила при инициализации). Это решение, зна­чительно отличающееся от стандартной фон-неймановской машины, иногда на­зывают архитектурой SIMD (Single Instruction-stream Multiple Data-stream — один поток команд с несколькими потоками данных). Из-за очень высокой стоимости был построен только один такой квадрант, но он мог выполнять 50 млн операций с плавающей точкой в секунду. Если бы при создании машины использовалось четыре квадранта, она могла бы выполнять 1 млрд операций с плавающей точкой в секунду, и вычислительные возможности такой машины в два раза превышали бы возможности компьютеров всего мира.

Рис. 2.6. Матричный процессор ILLIAC IV

С точки зрения программиста, векторный процессор (vector processor) очень похож на матричный. Как и матричный, он чрезвычайно эффективен при выпол­нении последовательности операций над парами элементов данных. Однако в отличие от матричного процессора, все операции сложения выполняются в од­ном блоке суммирования, который имеет конвейерную структуру. Компания Cray Research, основателем которой был Сеймур Крей, выпустила множество моделей векторных процессоров, начиная с модели Сгау-1 (1974). Компания Cray Research в настоящее время входит в состав SGI.

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

Матричные процессоры в настоящее время не выпускаются, но принцип, на котором они основаны, по-прежнему актуален. Аналогичная идея применяется в наборах ММХ- и SSE-команд процессоров Pentium 4, и она успешно решает задачу ускоренного выполнения мультимедийных программ. В этом отноше­нии компьютер ILLIAC IV можно считать одним из прародителей процессора Pentium 4.

Источник: Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.

Суперскалярные архитектуры

 

Один конвейер — хорошо, а два — еще лучше. Одна из возможных схем процес­сора с двумя конвейерами показана на рис. 2.4. В ее основе лежит конвейер, изо­браженный на рис. 2.3. Здесь общий блок выборки команд вызывает из памяти сразу по две команды и помещает каждую из них в один из конвейеров. Каждый конвейер содержит АЛУ для параллельных операций. Чтобы выполняться па­раллельно, две команды не должны конфликтовать из-за ресурсов (например, регистров), и ни одна из них не должна зависеть от результата выполнения дру­гой. Как и в случае с одним конвейером, либо компилятор должен гарантировать отсутствие нештатных ситуаций (когда, например, аппаратура не обеспечивает проверку команд на несовместимость и при обработке таких команд выдает не­корректный результат), либо за счет дополнительной аппаратуры конфликты должны выявляться и устраняться непосредственно в ходе выполнения команд.

Рис. 2.4. Сдвоенный пятиступенчатый конвейер с общим блоком выборки команд

Сначала конвейеры (как сдвоенные, так и обычные) использовались только в RISC-компьютерах. У процессора 386 и его предшественников их не было. Конвейеры в процессорах компании Intel появились, только начиная с модели 486¹. Процессор 486 имел один пятиступенчатый конвейер, a Pentium — два та­ких конвейера. Похожая схема изображена на рис. 2.4, но разделение функций между второй и третьей ступенями (они назывались декодер 1 и декодер 2) было немного другим. Главный конвейер (u-конвейер) мог выполнять произвольные команды. Второй конвейер (v-конвейер) мог выполнять только простые коман­ды с целыми числами, а также одну простую команду с плавающей точкой (FXCH).

Имеются сложные правила определения, является ли пара команд совмести­мой в отношении возможности параллельного выполнения. Если команды, вхо­дящие в пару, были сложными или несовместимыми, выполнялась только одна из них (в u-конвейере). Оставшаяся вторая команда составляла затем пару со следующей командой. Команды всегда выполнялись по порядку. Таким образом, процессор Pentium содержал особые компиляторы, которые объединяли совмес­тимые команды в пары и могли порождать программы, выполняющиеся быстрее, чем в предыдущих версиях. Измерения показали, что программы, в которых

Необходимо отметить, что параллельное функционирование отдельных блоков процессора имело место и в предыдущем микропроцессоре (386). Этот механизм стал прообразом 5-ступенчатого кон­вейера микропроцессора 486. — Примеч. научн. ред.

применяются операции с целыми числами, при той же тактовой частоте на Pen­tium выполняются почти в два раза быстрее, чем на 486 [168]. Вне всяких сомне­ний, преимущество в скорости было достигнуто благодаря второму конвейеру.

Переход к четырем конвейерам возможен, но требует громоздкого аппаратно­го обеспечения (отметим, что компьютерщики, в отличие от фольклористов, не верят в счастливое число три). Вместо этого используется другой подход. Основ­ная идея — один конвейер с большим количеством функциональных блоков, как показано на рис. 2.5. Pentium II, к примеру, имеет сходную структуру (подробно мы рассмотрим ее в главе 4). В 1987 году для обозначения этого подхода был введен термин суперскалярная архитектура [5]. Однако подобная идея нашла воплощение еще тридцатью годами ранее в компьютере CDC 6600. Этот компьютер вызывал команду из памяти каждые 100 не и помещал ее в один из 10 функцио­нальных блоков для параллельного выполнения. Пока команды выполнялись, центральный процессор вызывал следующую команду.

Рис. 2.5. Суперскалярный процессор с пятью функциональными блоками

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

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

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

Отметим, что на выходе ступени 3 команды появляются значительно быст­рее, чем ступень 4 способна их обрабатывать. Если бы на выходе ступени 3 ко­манды появлялись каждые 10 не, а все функциональные блоки делали свою ра­боту также за 10 не, то на ступени 4 всегда функционировал бы только один блок, что сделало бы саму идею конвейера бессмысленной. В действительности большинству функциональных блоков ступени 4 (точнее, обоим блокам доступа к памяти и блоку выполнения операций с плавающей точкой) для обработки ко­манды требуется значительно больше времени, чем занимает один цикл. Как видно из рис. 2.5, на ступени 4 может быть несколько АЛУ.

Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.

Конвейеры

 

Уже много лет известно, что главным препятствием высокой скорости выполне­ния команд является необходимость их вызова из памяти. Для разрешения этой проблемы можно вызывать команды из памяти заранее и хранить в специальном наборе регистров. Эта идея использовалась еще в 1959 году при разработке ком­пьютера Stretch компании IBM, а набор регистров был назван буфером выбор­ки с упреждением. Таким образом, когда требовалась определенная команда, она вызывалась прямо из буфера, а обращения к памяти не происходило.

В действительности при выборке с упреждением команда обрабатывается за два шага: сначала происходит вызов команды, а затем — ее выполнение. Еще боль­ше продвинула эту стратегию идея конвейера. При использовании конвейера команда обрабатывается уже не за два, а за большее количество шагов, каждый из которых реализуется определенным аппаратным компонентом, причем все эти компоненты могут работать параллельно.

На рис. 2.3, а изображен конвейер из пяти блоков, которые называются сту­пенями. Первая ступень (блок С1) вызывает команду из памяти и помещает ее в буфер, где она хранится до тех пор, пока не потребуется. Вторая ступень (блок С2) декодирует эту команду, определяя ее тип и тип ее операндов. Третья ступень (блок СЗ) определяет местонахождение операндов и вызывает их из ре­гистров или из памяти.

Рис. 2.3. Пятиступенчатый конвейер (а); состояние каждой ступени в зависимости от количества пройденных циклов (б). Показано 9 циклов

Четвертая ступень (блок С4) выполняет команду, обычно проводя операнды через тракт данных (см. рис. 2.2). И наконец, блок С5 записывает результат об­ратно в нужный регистр.

На рис. 2.3, б мы видим, как действует конвейер во времени. Во время цикла 1 блок С1 обрабатывает команду 1, вызывая ее из памяти. Во время цикла 2 блок С2 декодирует команду 1, в то время как блок С1 вызывает из памяти ко­манду 2. Во время цикла 3 блок СЗ вызывает операнды для команды 1, блок С2 декодирует команду 2, а блок С1 вызывает команду 3. Во время цикла 4 блок С4 выполняет команду 1, СЗ вызывает операнды для команды 2, С2 декодирует ко­манду 3, а С1 вызывает команду 4. Наконец, во время цикла 5 блок С5 записыва­ет результат выполнения команды 1 обратно в регистр, тогда как другие ступени конвейера обрабатывают следующие команды.

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

Возвратимся к нашему конвейеру на рис. 2.3. Предположим, что время цикла у этой машины — 2 не. Тогда для того, чтобы одна команда прошла через весь конвейер, требуется 10 не. На первый взгляд может показаться, что такой компь­ютер будет выполнять 100 млн команд в секунду, в действительности же ско­рость его работы гораздо выше. В течение каждого цикла (2 не) завершается вы­полнение одной новой команды, поэтому машина выполняет не 100, а 500 млн команд в секунду!

Конвейеры позволяют добиться компромисса между временем запаздывания (время выполнения одной команды) и пропускной способностью процессора

(количество команд, выполняемых процессором в секунду). Если время обраще­ния составляет Т не, а конвейер имеет п ступеней, время запаздывания составит пГнс.

Поскольку одна команда выполняется за одно обращение, а за одну секунду таких обращений набирается 10⁹/Г, количество команд в секунду также состав­ляет 10⁹/Г. Скажем, если Т = 2 не, то каждую секунду выполняется 500 млн ко­манд. Для того чтобы получить значение MIPS, нужно разделить скорость вы­полнения команд на 1 миллион; таким образом, (10⁹/Г)/10⁶ = 1000/Г MIPS. В принципе, скорость выполнения команд можно измерять и в миллиардах опе­раций в секунду (Billion Instructions Per Second, BIPS), но так никто не делает, и мы не будем.

Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.

Системы RISC и CISC

 

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

В компании IBM этой тенденции противостояла группа разработчиков во главе с Джоном Коком (John Cocke); они попытались воплотить идеи Сеймура Крея, создав экспериментальный высокоэффективный мини-компьютер 801. Хо­тя компания IBM не занималась сбытом этой машины, а результаты экспери­мента были опубликованы только через несколько лет [170], весть быстро раз­неслась по свету, и другие производители тоже занялись разработкой подобных архитектур.

В 1980 году группа разработчиков в университете Беркли во главе с Дэвидом Паттерсоном (David Patterson) и Карло Секвином (Carlo Sequin) начала разра­ботку не ориентированных на интерпретацию процессоров VLSI [161, 164]. Для обозначения этого понятия они придумали термин RISC, а новый процессор назвали RISC I, вслед за которым вскоре был выпущен RISC II. Немного позже, в 1981 году, Джон Хеннеси (John Hennesy) в Стенфорде разработал и выпустил другую микросхему, которую он назвал MIPS [91]. Эти две микросхемы разви­лись в коммерчески важные продукты SPARC и MIPS соответственно.

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

В то время, когда разрабатывались эти простые процессоры, всеобщее внима­ние привлекало относительно небольшое количество команд (обычно около 50). Для сравнения: число команд в компьютерах VAX производства DEC и больших компьютерах производства IBM в то время составляло от 200 до 300. Компьютер RISC (Reduced Instruction Set Computer — компьютер с сокращенным набором команд) противопоставлялся системе CISC (Complex Instruction Set Compu­ter — компьютер с полным набором команд). В качестве примера машины ти­па CISC можно привести компьютер VAX, который доминировал в то время в университетской среде. На сегодняшний день мало кто считает, что главное отличие RISC и CISC состоит в количестве команд, но названия сохраняются до сих пор.

С этого момента началась грандиозная идеологическая война между сторон­никами RISC и разработчиками VAX, Intel и мэйнфреймов IBM. По мнению первых, наилучший способ разработки компьютеров — включение туда неболь­шого количества простых команд, каждая из которых выполняется за один цикл тракта данных (см. рис. 2.2), то есть производит над парой регистров какую-либо арифметическую или логическую операцию (например, сложение или операцию логического И) и помещает результат обратно в регистр. В качестве аргумента они утверждали, что, даже если системе RISC приходится выполнять 4 или 5 ко­манд вместо одной, которую выполняет CISC, RISC все равно выигрывает в ско­рости, так как RISC-команды выполняются в 10 раз быстрее (поскольку они не интерпретируются). Следует также отметить, что к этому времени быстродейст­вие основной памяти приблизилось к быстродействию специальных командных ПЗУ, поэтому недостатки интерпретации были налицо, что еще более подни­мало популярность компьютеров RISC.

Учитывая преимущества RISC в плане производительности, можно было предположить, что на рынке такие компьютеры, как Alpha компании DEC, долж­ны доминировать над компьютерами CISC (Pentium и т. д.). Однако ничего по­добного не произошло. Возникает вопрос: почему?

Во-первых, компьютеры RISC несовместимы с другими моделями, а многие компании вложили миллиарды долларов в программное обеспечение для про­дукции Intel. Во-вторых, как ни странно, компания Intel сумела воплотить те же идеи в архитектуре CISC. Процессоры Intel, начиная с процессора 486, содержат

RISC-ядро, которое выполняет самые простые (и обычно самые распространен­ные) команды за один цикл тракта данных, а по обычной технологии CISC ин­терпретируются более сложные команды. В результате обычные команды вы­полняются быстро, а более сложные и редкие — медленно. Хотя при таком «гибридном» подходе производительность ниже, чем в архитектуре RISC, новая архитектура CISC имеет ряд преимуществ, поскольку позволяет использовать старое программное обеспечение без изменений.

Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.

Устройство центрального процессора

 

Внутреннее устройство тракта данных типичного фон-неймановского процессо­ра иллюстрирует рис. 2.2. Тракт данных состоит из регистров (обычно от 1 до 32), арифметико-логического устройства (АЛУ) и нескольких соединительных шин. Содержимое регистров поступает во входные регистры АЛУ, которые на рис. 2.2 обозначены буквами А и В. В них находятся входные данные АЛУ, пока АЛУ производит вычисления. Тракт данных — важная составная часть всех ком­пьютеров, и мы обсудим его очень подробно.

АЛУ выполняет сложение, вычитание и другие простые операции над вход­ными данными и помещает результат в выходной регистр. Содержимое этого выходного регистра может записываться обратно в один из регистров или сохра­нятся в памяти, если это необходимо. Рисунок 2.2 иллюстрирует операцию сло­жения. Отметим, что входные и выходные регистры есть не у всех компьютеров.

Большинство команд можно разделить на две группы: типа регистр-память и ти­па регистр-регистр. Команды первого типа вызывают слова из памяти, помещают их в регистры, где они используются в качестве входных данных АЛУ (слова — это такие элементы данных, которые перемещаются между памятью и регистрами²). Словом может быть целое число. Организацию памяти мы обсудим далее в этой главе. Другие команды этого типа помещают регистры обратно в память.

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

¹ Используется также термин «указатель команд». — Примеч. научн. ред.

² На самом деле размер слова обычно соответствует разрядности регистра данных. Так, у 16-разряд­ных микропроцессоров 8086 и 8088 слово имеет длину 16 бит, а у 32-разрядных микропроцессо­ров — 32 бита. — Примеч. научн. ред.

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

Рис. 2.2. Тракт данных обычной фон-неймановской машины

Выполнение команд

Центральный процессор выполняет каждую команду за несколько шагов:

1. Вызывает следующую команду из памяти и переносит ее в регистр команд.

2. Меняет положение счетчика команд, который после этого указывает на сле­дующую команду¹.

3. Определяет тип вызванной команды.

4. Если команда использует слово из памяти, определяет, где находится это слово.

5. Переносит слово, если это необходимо, в регистр центрального процессора².

Это происходит после декодирования текущей команды, а иногда и после ее выполнения. — Примем, научн. ред.

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

6. Выполняет команду.

7. Переходит к шагу 1, чтобы начать выполнение следующей команды.

Такая последовательность шагов (выборка — декодирование — выполнение)

является основой работы всех компьютеров.

Описание работы центрального процессора можно представить в виде про­граммы. В листинге 2.1 приведена такая программа-интерпретатор на языке Java. В описываемом компьютере есть два регистра: счетчик команд с адресом следующей команды и аккумулятор, в котором хранятся результаты арифмети­ческих операций. Кроме того, имеются внутренние регистры, в которых хранит­ся текущая команда (instr), тип текущей команды (instr_type), адрес операнда команды (datajloc) и сам операнд (data). Каждая команда содержит один адрес ячейки памяти. В ячейке памяти находится операнд, например фрагмент дан­ных, который нужно добавить в аккумулятор.

Листинг 2.1. Интерпретатор для простого компьютера (на языке Java)

public class Interp{

static mt PC; // PC содержит адрес следующей команды

static int AC; // Аккумулятор, регистр для арифметики

static int instr; // Регистр для текущей команды

static int instr_type; // Тип команды (код операции)

static int dataJ ос: // Адрес данных или -1, если его нет

static int data; // Текущий операнд

static boolean run_bit = true; // Бит, который можно сбросить,

// чтобы остановить машину

public static void interpret(int memory[], int starting_address{
// Эта процедура интепретирует программы для простой машины,
// которая содержит команды только с одним операндом из
// памяти. Машина имеет регистр АС (аккумулятор). Он
// используется для арифметических действий. Например,
// команда ADD суммирует число из памяти с АС. Интерпретатор
// работает до тех пор, пока не будет выполнена команда
// HALT, вследствие чего бит run_bit поменяет значение на
// false. Машина состоит из блока памяти, счетчика команд, бита
// run bit и аккумулятора АС. Входные параметры представляют собой
// копию содержимого памяти и начальный адрес.

PC=starting_address;

while (run_bit) { instr=memory[PC]; // Вызывает следующую команду в instr РС=РС+1; // Увеличивает значение счетчика команд

instr_type=get_instr_type(instr); // Определяет тип команды data_loc=find_data(instr, instr_type); // Находит данные (-1,

// если данных нет) if(data_loc>=0) // Если data_lock=-l, значит, операнда нет

data=memory[data_loc]; // Вызов данных

execute(instr_type,data); // Выполнение команды

}

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

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

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

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

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

К концу 50-х годов компания IBM, которая лидировала тогда на компьютер­ном рынке, решила, что производство семейства компьютеров, каждый из кото­рых выполняет одни и те же команды, выгоднее и для самой компании, и для по­купателей. Чтобы охарактеризовать этот уровень совместимости, компания IBM ввела термин архитектура. Новое семейство компьютеров должно было иметь единую архитектуру и много разных моделей, различающихся по цене и скорости, но «умеющих» выполнять одни и те же программы. Но как построить дешевый компьютер, который сможет выполнять все сложные команды, предназначенные для высокоэффективных дорогостоящих машин?

Решением проблемы стала интерпретация. Эта технология, впервые предложен­ная Уилксом в 1951 году, позволяла разрабатывать простые дешевые компьютеры, которые тем не менее могли выполнять большое количество команд. В результа­те компания IBM создала архитектуру System/360 — семейство совместимых компьютеров, различающихся по цене и производительности. Аппаратное обес­печение, позволяющее работать без интерпретации, использовалось только в са­мых дорогих моделях.

Простые компьютеры с интерпретаторами команд имели свои достоинства. Наиболее важными среди них являлись:

♦ возможность исправлять неправильно выполненные команды или даже ком­пенсировать ошибки аппаратного обеспечения;

♦ возможность добавлять новые команды при минимальных затратах, при­чем при необходимости уже после покупки компьютера;

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

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

К концу 70-х годов интерпретаторы стали применяться практически во всех моделях, кроме самых дорогих машин с очень высокой производительностью (на­пример, Сгау-1 и компьютеров серии Control Data Cyber). Интерпретаторы обес­печивали реализацию сложных команд без использования дорогостоящей аппа­ратуры, поэтому разработчики могли вводить все более и более сложные коман­ды, а также (и даже в особенности) расширять способы определения операндов.

Эта тенденция достигла своего апогея в компьютере VAX, разработанном ком­панией DEC; у него было несколько сот команд и более 200 способов определе­ния операндов в каждой команде. К несчастью, архитектура VAX с самого нача­ла разрабатывалась с ориентацией на интерпретатор, а производительности уде­лялось мало внимания. Это привело к появлению большого количества команд второстепенного значения, которые сложно было реализовать непосредственно. Данное упущение стало фатальным как для VAX, так и для его производителя (компании DEC). Компания Compaq купила DEC в 1998 году (правда, тремя го­дами позже сама компания Compaq вошла в структуру Hewlett-Packard).

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

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

Успех системы Motorola 68000 с большим набором интерпретируемых ко­манд и одновременный провал компьютера Zilog Z8000, у которого был столь же обширный набор команд, но не было интерпретатора, продемонстрировали все преимущества интерпретации при разработке новых машин. Этот успех был до­вольно неожиданным, учитывая, что компьютер Z80 (предшественник Zilog Z8000) пользовался большей популярностью, чем Motorola 6800 (предшественник Motorola 68000). Конечно, важную роль здесь играли и другие факторы, напри­мер то, что компания Motorola много лет занималась производством микросхем, а торговая марка Zilog принадлежала Exxon — крупной нефтяной компании.

Еще один фактор в пользу интерпретации — существование быстродействую­щих постоянных запоминающих устройств для хранения интерпретаторов (так называемых командных ПЗУ). Предположим, что для выполнения обычной ин­терпретируемой команды интерпретатору компьютера Motorola 68000 нужно выполнить 10 команд (они называются микрокомандами), по 100 не на каждую, и произвести 2 обращения к оперативной памяти, по 500 не на каждое. Общее время выполнения команды составит, следовательно, 2000 не, всего лишь в два раза больше, чем в лучшем случае могло бы занять непосредственное выполне­ние этой команды без интерпретации. А если бы не было специального быстро­действующего постоянного запоминающего устройства, выполнение этой коман­ды заняло бы целых 6000 не. Таким образом, значимость командных ПЗУ очевидна.

Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.