пятница, 25 июля 2008 г.

[ЭВМ] Архитектура процессоров. CISC и RISC

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

Через тридцать с небольшим лет процессоры усложнились до такой степени, что разработка хоть сколько-нибудь быстрого по современным меркам кристалла требует огромной армии инженеров, гигантских инвестиций и целого моря времени. И дело здесь отнюдь не в тонких кремниевых технологиях и стоящих миллиарды долларов полупроводниковых фабриках - просто уже в восьмидесятых годах разработка принципиально нового CPU требовала двух-трех, а в девяностых - пяти-шести лет напряженной работы. Те же китайцы, даже располагая подробной информацией о тридцатилетней истории проектирования процессоров, владея новейшими фабриками по производству кремниевых кристаллов и не стремясь изобретать что-то новое, потратили на разработку собственного простейшего MIPS32-подобного процессора Godson (примерно эквивалентного по производительности i486) несколько лет. Это не считая еще одного года, когда новый кристалл отлаживали. А на разработку MIPS64-подобной архитектуры с приемлемой производительностью (~Pentium III 500–600 МГц) у китайской Академии наук ушло еще четыре года, - четыре года, потраченных только на то, чтобы повторить успех более чем двенадцатилетней давности. Но почему все получается так сложно? Чтобы ответить на этот вопрос нам придется вернуться на 30-40 лет в прошлое.

Шаг 1. CISC

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

Надо признать, что достигнутые на этом пути успехи действительно впечатляли - в последних версиях ЭВМ выразительность ассемблерного листинга зачастую не уступала выразительности программы, написанной на языке высокого уровня. Одной-единственной машинной инструкцией можно было сказать практически все, что угодно. К примеру, такие машины, как DEC VAX, аппаратно поддерживали инструкции "добавить элемент в очередь", "удалить элемент из очереди" и даже "провести интерполяцию полиномом" (!); а знаменитое семейство процессоров Motorola 68k почти для всех инструкций поддерживало до двенадцати (!) режимов адресации памяти, вплоть до взятия в качестве аргумента инструкции "данных, записанных по адресу, записанному вон в том регистре, со смещением, записанным вот в этом регистре". Отсюда и общее название соответствующих архитектур: CISC - Complex Instruction Set Computers ("компьютеры с набором инструкций на все случаи жизни").

На практике это привело к тому, что подобные инструкции оказалось сложно не только выполнять, но и просто декодировать (выделять из машинного кода новую инструкцию и отправлять ее на исполнительные устройства). Чтобы машинный код CISC-компьютеров из-за сложных инструкций не разрастался до огромного размера, машинные инструкции в большинстве этих архитектур имели неоднородную структуру (разное расположение и размеры кода операции и ее операндов) и сильно отличающуюся длину (в x86, например, длина инструкций варьируется от 1 до 15 байт). Еще одной проблемой стало то, что при сохранении приемлемой сложности процессора многие инструкции оказалось принципиально невозможно выполнить "чисто аппаратно", и поздние CISC-процессоры были вынуждены обзавестись специальными блоками, которые "на лету" заменяли некоторые сложные команды на последовательности более простых. В результате все CISC-процессоры оказались весьма трудоемкими в проектировании и изготовлении. Но что самое печальное, к моменту расцвета CISC-архитектур стало ясно, что все эти конструкции изобретались в общем-то зря - исследования программного обеспечения того времени, проведенные IBM, наглядно показали, что даже программисты, пишущие на ассемблере, все эти "сверхвозможности" почти никогда не использовали, а компиляторы языков высокого уровня - и не пытались использовать.

К началу восьмидесятых годов классические CISC полностью исчерпали себя. Расширять набор инструкций в рамках этого подхода дальше не имело смысла, наоборот - технологи столкнулись с тем, что из-за высокой сложности CISC-процессоров оказалось трудно наращивать их тактовую частоту, а из-за "тормознутости" оперативной памяти тех времен зашитые в память процессора расшифровки сложных инструкций зачастую работают медленнее, чем точно такие же цепочки команд, встречающиеся в основной программе. Короче говоря, стало очевидным, что CISC-процессоры нужно упрощать - и на свет появился RISC, Reduced Instruction Set Computer.

Шаг 2. RISC

Точно так же, как когда-то CISC-процессоры проектировались под нужды asm-программистов, RISC проектировался в расчете на типовой код, генерируемый компиляторами. Для начала разработчики свели к минимуму набор инструкций и к абсолютному минимуму - количество режимов адресации памяти; упаковав все, что осталось, в простой и удобный для декодирования регулярный машинный код. В частности, в классическом варианте RISC из инструкций, обращающихся к оперативной памяти, оставлены только две (Load - загрузить данные в регистр и Store - сохранить данные из регистра; так называемая Load/Store-архитектура), и нет ни одной инструкции вроде вычисления синуса, косинуса или квадратного корня (их можно реализовать "вручную"), не говоря уже о более сложных[Канонический пример - инструкция INDEX, выполнявшаяся на VAX медленнее, чем вручную написанный цикл, выполняющий ровно тот же объем работы]. Да что там синус с косинусом - в некоторых RISC-процессорах пытались отказаться даже от трудно реализуемого аппаратного умножения и деления! Правда, до таких крайностей ни один коммерческий RISC, к счастью, не дошел, но как минимум две попытки (ранние варианты MIPS и SPARC) предприняты были.

Второе важное усовершенствование RISC-процессоров, целиком вытекающее из Load/Store-архитектуры, - увеличение числа GPR (регистров общего назначения). Варианты, у которых меньше шестнадцати GPR, - большая редкость, причем почти все эти регистры полностью равноправны, что позволяет компилятору свободно распоряжаться ими, сохраняя большую часть промежуточных данных именно там, а не в стеке или оперативной памяти. В некоторых архитектурах, типа SPARC, "регистровость" возведена в абсолют, в некоторых - оставлена на разумном уровне; однако почти любой RISC-процессор обладает куда большим набором регистров, чем даже самый продвинутый CISC. Для сравнения: в классическом x86 IA-32 всего восемь регистров общего назначения, причем каждому из них приписано то или иное "специальное назначение" (скажем, в ESP хранится указатель на стек) затрудняющее или делающее невозможным его использование.

Среди прочих усовершенствований, внесенных в RISC, - такие нетривиальные идеи, как условные инструкции ARM или режимы работы команд. Например, некий модификатор в архитектуре PowerPC и некоторых других показывает, должна ли инструкция выставлять по результатам своего выполнения определенные флаги, которые потом может использовать инструкция условного перехода, или не должна. Это позволяет разнести в пространстве инструкцию, выполняющую вычисление условия, и инструкцию собственно условного перехода - что в конвейерных архитектурах зачастую позволяет процессору не "гадать", будет совершен переход или нет, а сразу достоверно это знать. В классическом CISC они почти не встречаются, поскольку на момент разработки соответствующих наборов инструкций ценность этих решений была сомнительной (они выйдут на сцену только в конвейеризированных процессорах).

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

Шаг 3. Введение конвейера

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

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

  • Выборка инструкции (FETCH) из памяти. Из программы извлекается инструкция, которую нужно выполнить.
  • Декодирование инструкции (DECODE). Процессор "соображает", что от него хотят, и переправляет запрос на нужное исполнительное устройство.
  • Подготовка исходных данных для выполнения инструкции.
  • Собственно выполнение инструкции (EXECUTE).
  • Сохранение полученных результатов.

Конвейеризация потенциально применима к любой процессорной архитектуре, независимо от набора команд и положенных в ее основу принципов. Даже самый первый x86-процессор, Intel 8086, уже содержал своеобразный примитивный "двухстадийный конвейер" - выборка новых инструкций (FETCH) и их исполнение осуществлялись в нем независимо друг от друга. Однако реализовать что-то более сложное для CISC-процессоров оказалось трудно: декодирование неоднородных CISC-инструкций и их очень сильно различающаяся сложность привели к тому, что конвейер получается чересчур замысловатым, катастрофически усложняя процессор. Подобных трудностей у RISC-архитектуры гораздо меньше (а SPARC и MIPS, например, и вовсе были специально оптимизированы для конвейеризации), так что конвейеризированные RISC-процессоры появились на рынке много раньше, чем аналогичные x86.

Недостатки конвейера неочевидны, но, как обычно и бывает, из-за нескольких "мелочей" реализовать грамотно организованный конвейер совсем не просто. Основных проблем три.

  • Необходимость наличия блокировок конвейера. Дело в том, что время исполнения большинства инструкций может очень сильно варьироваться. Скажем, умножение (и тем более деление) чисел требуют (на стадии EXECUTE) нескольких тактов, а сложение или побитовые операции - одного такта; а для операций Load и Store, которые могут обращаться к разным уровням кэш-памяти или к оперативной памяти, это время вообще не определено (и может достигать сотен тактов). Соответственно, должен быть какой-то механизм, который бы "притормаживал" выборку и декодирование новых инструкций до тех пор, пока не будут завершены старые. Методов решения этой проблемы много, но их развитие приводит к одному - в процессорах прямо перед исполнительными устройствами появляются специальные блоки-диспетчеры (dispatcher), которые накапливают подготовленные к исполнению инструкции, отслеживают выполнение ранее запущенных инструкций и по мере освобождения исполнительных устройств отправляют на них новые инструкции. Даже если исполнение займет много тактов - внутренняя очередь диспетчера позволит в большинстве случаев не останавливать подготавливающий все новые и новые инструкции конвейер[Новые инструкции тоже не каждый такт удается декодировать, так что возможна и обратная ситуация: новых инструкций за такт не появилось, и диспетчер отправляет инструкции на выполнение "из старых запасов"]. Так в процессоре возникает разделение на две независимо работающие подсистемы: Front-end (блоки, занимающиеся декодированием инструкций и их подготовкой к исполнению) и Back-end (блоки, собственно исполняющие инструкции).
  • Необходимость наличия системы сброса процессора. Поскольку операции FETCH и EXECUTE всегда выделены в отдельные стадии конвейера, то в тех случаях, когда в программном коде происходит разветвление (условный переход), зачастую оказывается, что по какой из веток пойти - пока неизвестно: инструкция, вычисляющая код условия, еще не выполнена[Вот здесь-то и нужны те самые режимы выставления флагов PowerPC, о которых шла речь в сноске 2]. В результате процессор вынужден либо приостанавливать выборку новых инструкций до тех пор, пока не будет вычислен код условия (а это может занять очень много времени и в типичном цикле страшно затормозит процессор), либо, руководствуясь соображениями блока предсказания переходов, "угадывать", какой из переходов скорее всего окажется правильным.
  • Наконец, конвейер обычно требует наличия специального планировщика (scheduler), призванного решать конфликты по данным. Если в программе идет зависимая цепочка инструкций (когда инструкция-2, следующая за инструкцией-1, использует для своих вычислений данные, только что вычисленные инструкцией-1), а время исполнения одной инструкции (от момента запуска на стадию EXECUTE и до записи полученных результатов в регистры) превосходит один такт, то мы вынуждены придержать выполнение очередной инструкции до тех пор, пока не будет полностью выполнена ее предшественница. К примеру, если мы вычисляем выражение вида A•B+C с сохранением результата в переменной X (XfA•B+C), то процессор, выполняя соответствующую выражению цепочку из двух команд типа R4fR1•R2; R0fR3+R4, должен вначале дождаться, пока первая инструкция сохранит результат умножения A•B, и только потом прибавлять к полученному результату число С. Цепочки зависимых инструкций в программах - скорее правило, нежели исключение, а исполнение команды с записью результата в регистры за один такт - наоборот, скорее исключение, нежели правило, поэтому в той или иной степени с проблемой зависимости по данным любая конвейерная архитектура обязательно сталкивается. Оттого-то в конвейере и появляются сложные декодеры, заранее выявляющие эти зависимости, и планировщики, которые запускают инструкции на исполнение, выдерживая паузу между запуском главной инструкции и зависимой от нее.

Ну как вам список проблем? Идея конвейера в процессоре очень красива на словах и в теории, однако реализовать ее даже в простом варианте чрезвычайно трудно. Но выгода от конвейеризации столь велика и несомненна, что приходится с этими трудностями мириться, ведь ничего лучшего до сих пор не придумано.

В 1991-92 годах корпорация Intel, освоив производство сложнейших кристаллов с более чем миллионом транзисторов, выпустила i486 - классический CISC-процессор архитектуры x86, но с пятистадийным конвейером. Чтобы вы смогли оценить этот рывок, приведу две цифры: тактовую частоту по сравнению с i386 введение конвейера позволило увеличить втрое, а производительность на единицу частоты - вдвое. В i386 многие инструкции выполнялись за несколько тактов; а в i486 среднее "время" исполнения инструкции в тактах удалось снизить почти вдвое. Правда, расплатой за это стала чудовищная сложность ядра i486; но такие "мелочи" по меркам индустрии центральных процессоров - пустяк: быстро растущие технологические возможности кремниевой технологии уже через пару лет позволили освоить производство i486 всем желающим. Но к тому моменту RISC-архитектуры сделали еще один шаг вперед - к суперскалярным процессорам.

Блок предсказания переходов

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

При неправильном предсказании конвейер обычно приходится "сбрасывать", каким-то образом восстанавливая состояние процессора, предшествующее моменту неправильного перехода. А ведь пока исполнялась неправильная ветка, там ого-го сколько всего могло случиться! Неправильный опкод (нераспознаваемая машинная инструкция), обращение к виртуальной памяти (провоцирующее исключение в процессоре), некстати распознанное деление на ноль (тоже ошибка). Все это приходится тщательно отслеживать и проверять, причем это не шутки: одно время из-за ошибки в реализации конвейера процессора AMD K5, программист, написавший конструкцию если x A 0, то y = 1/x, иначе y = 0, запросто мог получить при x @ 0 на, казалось бы, ровном месте ошибку "деление на ноль", вызванную неправильным предсказанием перехода. А в OoO-процессорах ситуация еще сложнее - пока "тормозит" не вовремя отправившаяся за операндами в оперативную память инструкция, процессор успевает пропустить вперед, выполнить и едва ли не сохранить результат вычисления десятков инструкций неправильной ветки: попробуй за всем этим уследить!

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

Точность предсказания современных блоков составляет на тестах SPEC порядка 98-99%. Может показаться, что совершенствовать блок не имеет смысла, но это не совсем так. Дело в том, что на производительности гораздо больше сказывается процент ошибок, а не верных предсказаний. А переход от 98-процентной точности к 99-процентной означает двукратное снижение ошибок - с 2% до 1%! Поэтому если вы внимательно почитаете пресс-релизы о новых CPU, то заметите, что "усовершенствованный блок предсказания переходов" упоминается в них почти всегда.

В архитектуре IA-64 техника предсказания переходов сделала значительный шаг вперед - эти процессоры умеют одновременно вычислять несколько веток программного кода. То есть, встретив инструкцию условного перехода, процессор начинает "охотиться за двумя зайцами" - просчитывать оба варианта развития событий вплоть до того момента, пока не станет ясно, какой из них правильный. Поскольку инструкции "разных вариантов" практически не зависят друг от друга, а исполнительные устройства Itanium обычно загружены далеко не полностью, то исполнять побочную ветку нередко удается практически с той же скоростью, что и основную, так что даже при неправильном предсказании условного перехода происходит не остановка процессора на пару десятков тактов, а всего лишь снижение производительности на небольшом участке кода.

Шаг 4. Суперскалярные и Out-of-Order-процессоры

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

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

Процессоры, использующие первую технику, называются суперскалярными. К примеру, сугубо теоретически, по числу исполнительных устройств, Pentium 4 может выполнять семь инструкций за такт, а Athlon 64 - девять. Реальные цифры, конечно, гораздо скромнее и определяются трудностью полноценной загрузки всех исполнительных устройств, однако Pentium 4 все же способен исполнять в устоявшемся режиме две (при некоторых условиях - четыре), а Athlon 64 - три инструкции за такт, одновременно производя две (A64 - три) операции по адресации и выборке данных из оперативной памяти. Может показаться, что реализация суперскалярного процессора очень проста (достаточно со стадии schedule просто распределять инструкции по разным исполнительным устройствам), однако такой лобовой подход обычно упирается в то, что Front-end процессора перестает успевать загружать исполнительные блоки работой. Поэтому на практике хорошо сделанные суперскалярные архитектуры, подобные AMD K7/K8, приходится специально "затачивать" под суперскалярность.

Процессоры, использующие вторую технику, называются процессорами с внеочередным исполнением инструкций (Out-of-Order processors, OoO). Техника переупорядочивания инструкций замечательна тем, что резко ослабляет негативные эффекты от медленной оперативной памяти и от наличия зависимых цепочек инструкций. Если, например, инструкция A обратилась к оперативной памяти, а нужных данных в кэше не оказалось или если A занимается ожиданием результатов выполнения какой-то другой инструкции, то OoO-процессор сможет пропустить вперед другие инструкции, не зависящие от результатов выполнения инструкции A. Кроме того, продвинутый планировщик OoO-процессора иногда может использоваться для реализации специфических деталей той или иной архитектуры - например, для спекулятивного исполнения по данным в случае Pentium 4 или одновременного исполнения нескольких веток программного кода в IA-64. Реализация OoO-процессоров не требует специальной оптимизации всего конвейера - это всего лишь усложнение схемы планировщиков, запускающих готовые к исполнению инструкции на исполнительные устройства в другом порядке, нежели они на планировщики поступили, плюс усложнение схем сброса конвейера и сохранения полученных результатов: результат выполнения прошедших вне очереди инструкций все равно должен сохраняться в последовательности, строго соответствующей расположению инструкций в изначальном коде[Это связано с тем, что если случится какая-то ошибка, то результаты выполнения запущенных вперед очереди инструкции придется аннулировать].

На сегодняшний день не существует ни одного суперскалярного или OoO CISC-процессора. Дело в том, что поскольку для нормальной реализации навороченных диспетчеров и планировщиков все равно требуется длительная и тщательная подготовка инструкций, причем желательно - до такого простого состояния, чтобы эти функционирующие на огромных частотах модули особенно не "задумывались" над тем, что такая хитрая последовательность байтов означает и куда ее следует направить (проблем у них и без того хватает), то любой исходный машинный код Front-end процессоров превращает перед исполнением в некое внутреннее, упрощенное и "разжеванное", состояние. То есть на этом этапе развития различия между RISC- и CISC-архитектурами почти стираются - просто у RISC’ов декодер, превращающий исходный машинный код в содержимое очередей планировщиков, устроен гораздо проще, чем "расковыривающий" хитро упакованные x86-инструкции CISC-подобный декодер AMD Athlon и Intel Pentium. Так что можно сказать, что фактически все современные x86-процессоры "в глубине души" являются полноценными RISC’ами - ведь исходный x86-код они в любом случае преобразуют на лету во внутреннее RISC-подобное представление. Правда, разной сложностью декодеров дело не ограничивается: все-таки классический RISC-код не только проще преобразовывать, но и результирующий внутренний код из него получается лучше - планировщикам гораздо легче его обрабатывать (в нем меньше зависимостей и операций с оперативной памятью). Вот и появляются в x86 все новые и новые расширенные наборы инструкций (от 3Dnow! до SSE): это всего-навсего "внешняя ширма", упрощающая работу декодерам инструкций и позволяющая им сгенерировать более эффективный внутренний код. Специального блока обработки того же упакованного 128-битного формата SSE нет ни в одном современном процессоре, так что когда в программном коде x86 встречается, скажем, инструкция сложения двух регистров SSE по четыре числа в каждом - декодер банально генерирует код из четырех явно независимых (вот за что боролись!) инструкций сложения, которые планировщику потом будет легко разбросать по исполнительным устройствам. Но какого-либо "специального блока SSE", одновременно выполняющего запрошенные одной инструкцией четыре сложения, ни в Athlon, ни в Pentium 4 нет.

Фактически развитие собственно "архитектуры" x86-процессоров долгое время стояло на месте: что древний Pentium Pro, что новейший Pentium M - все они основаны на одной и той же старой-престарой архитектуре P6. Вылизанной, оптимизированной, но старой - ибо повода для ее смены до сих пор просто не было; "внутреннее представление" x86-кода, несмотря на все внесенные в x86 новации, с тех самых древних времен "чистой IA-32" вплоть до появления технологии AMD64 практически не изменялось.


Источник: www.terralab.ru

Комментариев нет: