Основы организации вычислительных систем

Основы организации вычислительных системПроцессоры Архитектура системы команд. Классификация процессоров CISC и RISC Термин архитектура системы часто употребляется как в узком, так и в широком смысле этого слова. В узком смысле под архитектурой понимается архитектура набора команд. Архитектура набора команд служит границей между аппаратурой и программным обеспечением и представляет ту часть системы, которая видна программисту или разработчику компиляторов.Следует отметить, что это наиболее частое употребление этого термина.

В широком смысле архитектура охватывает понятие организации системы, включающее такие высокоуровневые аспекты разработки компьютера как систему памяти, структуру системной шины, организацию ввода вывода и т.п. Двумя основными архитектурами набора команд, используемыми компьютерной промышленностью на современном этапе развития вычислительной техники являются архитектуры CISC и RISC. Основоположником CISC-архитектуры можно считать компанию IBM с ее базовой архитектурой 360, ядро которой используется с 1964 года и дошло до наших дней, например, в таких современных мейнфреймах как IBM ES 9000. Лидером в разработке микропроцессоров c полным набором команд CISC - Complete Instruction Set Computer считается компания Intel со своей серией x86 и Pentium.

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

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

Эту традицию упрощения архитектуры С. Крэй с успехом применил при создании широко известной серии суперкомпьютеров компании Cray Research.Однако окончательно понятие RISC в современном его понимании сформировалось на базе трех исследовательских проектов компьютеров процессора 801 компании IBM, процессора RISC университета Беркли и процессора MIPS Стенфордского университета.

Разработка экспериментального проекта компании IBM началась еще в конце 70-х годов, но его результаты никогда не публиковались и компьютер на его основе в промышленных масштабах не изготавливался.В 1980 году Д.Паттерсон со своими коллегами из Беркли начали свой проект и изготовили две машины, которые получили названия RISC-I и RISC-II. Главными идеями этих машин было отделение медленной памяти от высокоскоростных регистров и использование регистровых окон. В 1981 году Дж. Хеннесси со своими коллегами опубликовал описание стенфордской машины MIPS, основным аспектом разработки которой была эффективная реализация конвейерной обработки посредством тщательного планирования компилятором его загрузки.

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

Чтобы упростить логику декодирования команд использовались команды фиксированной длины и фиксированного формата.Среди других особенностей RISC-архитектур следует отметить наличие достаточно большого регистрового файла в типовых RISC-процессорах реализуются 32 или большее число регистров по сравнению с 8 - 16 регистрами в CISC-архитектурах , что позволяет большему объему данных храниться в регистрах на процессорном кристалле большее время и упрощает работу компилятора по распределению регистров под переменные.

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

Ко времени завершения университетских проектов 1983-1984 гг. обозначился также прорыв в технологии изготовления сверхбольших интегральных схем. Простота архитектуры и ее эффективность, подтвержденная этими проектами, вызвали большой интерес в компьютерной индустрии и с 1986 года началась активная промышленная реализация архитектуры RISC. К настоящему времени эта архитектура прочно занимает лидирующие позиции на мировом компьютерном рынке рабочих станций и серверов.

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

Следует отметить, что в последних разработках компании Intel имеются в виду Pentium и Pentium Pro , а также ее последователей-конкурентов AMD R5, Cyrix M1, NexGen Nx586 и др. широко используются идеи, реализованные в RISC-микропроцессорах, так что многие различия между CISC и RISC стираются.Однако сложность архитектуры и системы команд x86 остается и является главным фактором, ограничивающим производительность процессоров на ее основе.

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

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

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

Для иллюстрации основных принципов построения процессоров мы будем использовать простейшую архитектуру, содержащую 32 целочисленных регистра общего назначения R0, ,R31 , 32 регистра плавающей точки F0, ,F31 и счетчик команд PC. Будем считать, что набор команд нашего процессора включает типичные арифметические и логические операции, операции с плавающей точкой, операции пересылки данных, операции управления потоком команд и системные операции.

В арифметических командах используется трехадресный формат, типичный для RISC-процессоров, а для обращения к памяти используются операции загрузки и записи содержимого регистров в память.Выполнение типичной команды можно разделить на следующие этапы выборка команды - IF по адресу, заданному счетчиком команд, из памяти извлекается команда декодирование команды выборка операндов из регистров - ID выполнение операции вычисление эффективного адреса памяти - EX обращение к памяти - MEM запоминание результата - WB. На рисунке 3.1 представлена схема простейшего процессора, выполняющего указанные выше этапы выполнения команд без совмещения.

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

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

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

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

В предельном случае длительность такта можно уменьшить до суммы накладных расходов и перекоса сигналов синхронизации, однако при этом в такте не останется времени для выполнения полезной работы по преобразованию информации.Рис. 3.1. Схема неконвейерного целочисленного устройства Номер команды Номер такта 1 2 3 45 6 7 8 9 Команда i IF ID EX MEMWB Команда i 1 IF ID EXMEM WB Команда i 2 IF IDEX MEM WB Команда i 3 IFID EX MEM WB Команда i 4 IF ID EX MEM WB Рис. 3.2. Диаграмма работы простейшего конвейера При реализации конвейерной обработки возникают ситуации, которые препятствуют выполнению очередной команды из потока команд в предназначенном для нее такте.

Такие ситуации называются конфликтами. Конфликты снижают реальную производительность конвейера, которая могла бы быть достигнута в идеальном случае.Существуют три класса конфликтов 1. Структурные конфликты, которые возникают из-за конфликтов по ресурсам, когда аппаратные средства не могут поддерживать все возможные комбинации команд в режиме одновременного выполнения с совмещением. 2. Конфликты по данным, возникающие в случае, когда выполнение одной команды зависит от результата выполнения предыдущей команды. 3. Конфликты по управлению, которые возникают при конвейеризации команд переходов и других команд, которые изменяют значение счетчика команд.

Конфликты в конвейере приводят к необходимости приостановки выполнения команд pipeline stall . Обычно в простейших конвейерах, если приостанавливается какая-либо команда, то все следующие за ней команды также приостанавливаются.

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

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

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

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

Чтобы разрешить эту ситуацию, можно просто приостановить конвейер на один такт, когда происходит обращение к памяти за данными. Подобная приостановка часто называются конвейерным пузырем pipeline bubble или просто пузырем, поскольку пузырь проходит по конвейеру, занимая место, но не выполняя никакой полезной работы.Команда Номер такта 1 2 3 45 6 7 8 9 10 Команда загрузки IF ID EX MEMWB Команда 1 IF ID EXMEM WB Команда 2 IF IDEX MEM WB Команда 3 stallIF ID EX MEM WB Команда 4 IF ID EX MEM WB Команда 5 IF ID EX MEM Команда 6 IF ID EX Рис. 3.3. Диаграмма работы конвейера при структурном конфликте При всех прочих обстоятельствах, машина без структурных конфликтов будет всегда иметь более низкий CPI среднее число тактов на выдачу команды . Возникает вопрос почему разработчики допускают наличие структурных конфликтов? Для этого имеются две причины снижение стоимости и уменьшение задержки устройства.

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

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

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

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

Рассмотрим конвейерное выполнение последовательности команд на рисунке 3.4. В этом примере все команды, следующие за командой ADD, используют результат ее выполнения. Команда ADD записывает результат в регистр R1, а команда SUB читает это значение.Если не предпринять никаких мер для того, чтобы предотвратить этот конфликт, команда SUB прочитает неправильное значение и попытается его использовать.

На самом деле значение, используемое командой SUB, является даже неопределенным хотя логично предположить, что SUB всегда будет использовать значение R1, которое было присвоено какой-либо командой, предшествовавшей ADD, это не всегда так. Если произойдет прерывание между командами ADD и SUB, то команда ADD завершится, и значение R1 в этой точке будет соответствовать результату ADD. Такое непрогнозируемое поведение очевидно неприемлемо.ADD R1,R2,R3 IF ID EXMEM WB SUB R4,R1,R5 IF IDEX MEM WB AND R6,R1,R7 IFID EX MEM WB OR R8,R1,R9 IF ID EX MEM WB XOR R10,R1,R11 IF ID EX MEM WB Рис. 3.4. Последовательность команд в конвейере и ускоренная пересылка данных data forwarding, data bypassing, short circuiting Проблема, поставленная в этом примере, может быть разрешена с помощью достаточно простой аппаратной техники, которая называется пересылкой или продвижением данных data forwarding , обходом data bypassing , иногда закороткой short-circuiting . Эта аппаратура работает следующим образом.

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

Эта техника обходов может быть обобщена для того, чтобы включить передачу результата прямо в то функциональное устройство, которое в нем нуждается результат с выхода одного устройства пересылается на вход другого, а не с выхода некоторого устройства только на его вход. Конфликты по данным, приводящие к приостановке конвейера К сожалению не все потенциальные конфликты по данным могут обрабатываться с помощью механизма обходов . Рассмотрим следующую последовательность команд рисунок 3.5 Команда LW R1,32 R6 IF ID EXMEM WB ADD R4,R1,R7 IF IDstall EX MEM WB SUB R5,R1,R8 IF stall ID EX MEM WB AND R6,R1,R7 stall IF ID EX MEM WB Рис. 3.5. Последовательность команд с приостановкой конвейера Этот случай отличается от последовательности подряд идущих команд АЛУ. Команда загрузки LW регистра R1 из памяти имеет задержку, которая не может быть устранена обычной пересылкой . Вместо этого нам нужна дополнительная аппаратура, называемая аппаратурой внутренних блокировок конвейера pipeline interlook , чтобы обеспечить корректное выполнение примера.

Вообще такого рода аппаратура обнаруживает конфликты и приостанавливает конвейер до тех пор, пока существует конфликт.

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

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

Например, для оператора А B С компилятор скорее всего сгенерирует следующую последовательность команд рисунок 3.6 LW R1,В IF ID EX MEMWB LW R2,С IF ID EXMEM WB ADD R3,R1,R2 IF IDstall EX MEM WB SW A,R3 IF stall ID EX MEM WB Рис. 3.6. Конвейерное выполнение оператора А В С Очевидно, выполнение команды ADD должно быть приостановлено до тех пор, пока не станет доступным поступающий из памяти операнд C. Дополнительной задержки выполнения команды SW не произойдет в случае применения цепей обхода для пересылки результата операции АЛУ непосредственно в регистр данных памяти для последующей записи. Для данного простого примера компилятор никак не может улучшить ситуацию, однако в ряде более общих случаев он может реорганизовать последовательность команд так, чтобы избежать приостановок конвейера.

Эта техника, называемая планированием загрузки конвейера pipeline scheduling или планированием потока команд instruction scheduling , использовалась начиная с 60-х годов и стала особой областью интереса в 80-х годах, когда конвейерные машины стали более распространенными. Пусть, например, имеется последовательность операторов a b c d e - f Как сгенерировать код, не вызывающий остановок конвейера? Предполагается, что задержка загрузки из памяти составляет один такт. Ответ очевиден рисунок 3.7 Неоптимизированная последовательность команд Оптимизированная последовательность команд LW Rb,b LW Rb,b LW Rc,c LW Rc,c ADD Ra,Rb,Rc LW Re,e SW a,Ra ADD Ra,Rb,Rc LW Re,e LW Rf,f LW Rf,f SW a,Ra SUB Rd,Re,Rf SUB Rd,Re,Rf SW d,Rd SW d,Rd Рис. 3.7. Пример устранения конфликтов компилятором В результате устранены обе блокировки командой LW Rc,c команды ADD Ra,Rb,Rc и командой LW Rf,f команды SUB Rd,Re,Rf . Имеется зависимость между операцией АЛУ и операцией записи в память, но структура конвейера допускает пересылку результата с помощью цепей обхода . Заметим, что использование разных регистров для первого и второго операторов было достаточно важным для реализации такого правильного планирования.

В частности, если переменная e была бы загружена в тот же самый регистр, что b или c, такое планирование не было бы корректным.

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

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

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

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

К счастью, существуют аппаратные методы, позволяющие изменить порядок выполнения команд программы так, чтобы минимизировать приостановки конвейера.Эти методы получили общее название методов динамической оптимизации в англоязычной литературе в последнее время часто применяются также термины out-of-order execution - неупорядоченное выполнение и out-of-order issue - неупорядоченная выдача . Основными средствами динамической оптимизации являются 1. Размещение схемы обнаружения конфликтов в возможно более низкой точке конвейера команд так, чтобы позволить команде продвигаться по конвейеру до тех пор, пока ей реально не потребуется операнд, являющийся также результатом логически более ранней, но еще не завершившейся команды.

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

В этом случае команды могут выдаваться на выполнение не в том порядке, в котором они расположены в программе, однако аппаратура обнаружения и устранения конфликтов между логически связанными командами обеспечивает получение результатов в соответствии с заданной программой. 3. Соответствующая организация коммутирующих магистралей, обеспечивающая засылку результата операции непосредственно в буфер, хранящий логически зависимую команду, задержанную из-за конфликта, или непосредственно на вход функционального устройства до того, как этот результат будет записан в регистровый файл или в память short-circuiting, data forwarding, data bypassing - методы, которые были рассмотрены ранее . Еще одним аппаратным методом минимизации конфликтов по данным является метод переименования регистров register renaming . Он получил свое название от широко применяющегося в компиляторах метода переименования - метода размещения данных, способствующего сокращению числа зависимостей и тем самым увеличению производительности при отображении необходимых исходной программе объектов например, переменных на аппаратные ресурсы например, ячейки памяти и регистры . При аппаратной реализации метода переименования регистров выделяются логические регистры, обращение к которым выполняется с помощью соответствующих полей команды, и физические регистры, которые размещаются в аппаратном регистровом файле процессора. Номера логических регистров динамически отображаются на номера физических регистров посредством таблиц отображения, которые обновляются после декодирования каждой команды.

Каждый новый результат записывается в новый физический регистр.

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

В процессе выполнения программы генерируется множество временных регистровых результатов.

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

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

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

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

Команда перехода IF ID EX MEMWB Следующая команда IF stall stallIF ID EX MEM WB Следующая команда 1 stall stallstall IF ID EX MEM WB Следующая команда 2 stallstall stall IF ID EX MEM Следующая команда 3 stall stall stall IF ID EX Следующая команда 4 stall stall stall IF ID Следующая команда 5 stall stall stall IF Рис.3.8. Приостановка конвейера при выполнении команды условного перехода Например, если конвейер будет приостановлен на три такта на каждой команде условного перехода, то это может существенно отразиться на производительности машины.

При частоте команд условного перехода в программах, равной 30 и идеальном CPI, равным 1, машина с приостановками условных переходов достигает примерно только половины ускорения, получаемого за счет конвейерной организации.

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

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

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

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

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

Поведение конвейера выглядит так, как будто ничего необычного не происходит.Однако, если условный переход на самом деле выполняется, то необходимо просто очистить конвейер от команд, выбранных вслед за командой условного перехода и заново повторить выборку команд рисунок 3.9 . Невыполняемый условный переход IF IDEX MEM WB Команда i 1 IFID EX MEM WB Команда i 2 IF ID EX MEM WB Команда i 3 IF ID EX MEM WB Команда i 4 IF ID EX MEM WB Выполняемый условный переход IF IDEX MEM WB Команда i 1 целевая команда IFIF ID EX MEM WB Целевая команда 1 stall IF ID EX MEM WB Целевая команда 2 stall IF ID EX MEM WB Целевая команда 3 stall IF ID EX MEM Рис. 3.9. Диаграмма работы модернизированного конвейера Альтернативная схема прогнозирует переход как выполняемый.

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

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

Задержанные переходы Четвертая схема, которая используется в некоторых машинах называется задержанным переходом . В задержанном переходе такт выполнения с задержкой перехода длиною n есть команда условного перехода следующая команда 1 следующая команда 2 следующая команда n целевой адрес при выполняемом переходе Команды 1 - n находятся в слотах временных интервалах задержанного перехода.

Задача программного обеспечения заключается в том, чтобы сделать команды, следующие за командой перехода, действительными и полезными. Аппаратура гарантирует реальное выполнение этих команд перед выполнением собственно перехода. Здесь используются несколько приемов оптимизации.Планирование задержанных переходов осложняется 1 наличием ограничений на команды, размещение которых планируется в слотах задержки и 2 необходимостью предсказывать во время компиляции, будет ли условный переход выполняемым или нет. Рисунок 3.10 дает общее представление об эффективности планирования переходов для простейшего конвейера с одним слотом задержки перехода при использовании простого алгоритма планирования.

Он показывает, что больше половины слотов задержки переходов оказываются заполненными.При этом почти 80 заполненных слотов оказываются полезными для выполнения программы. Это может показаться удивительным, поскольку условные переходы являются выполняемыми примерно в 53 случаев.

Высокий процент использования заполненных слотов объясняется тем, что примерно половина из них заполняется командами, предшествовавшими команде условного перехода, выполнение которых необходимо независимо от того, выполняется ли переход, или нет. Рис. 3.10. Частота заполнения одного слота задержки условного перехода Проблемы реализации точного прерывания в конвейереОбработка прерываний в конвейерной машине оказывается более сложной из-за того, что совмещенное выполнение команд затрудняет определение возможности безопасного изменения состояния машины произвольной командой.

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

Как и в неконвейерных машинах двумя основными проблемами при реализации прерываний являются 1 прерывания возникают в процессе выполнения некоторой команды 2 необходим механизм возврата из прерывания для продолжения выполнения программы.Например, для нашего простейшего конвейера прерывание по отсутствию страницы виртуальной памяти при выборке данных не может произойти до этапа выборки из памяти MEM . В момент возникновения этого прерывания в процессе обработки уже будут находиться несколько команд.

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

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

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

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

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

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

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

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

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

Мы начнем с рассмотрения методов, позволяющих снизить влияние конфликтов по данным и по управлению, а затем вернемся к теме расширения возможностей процессора по использованию параллелизма, заложенного в программах.Для начала запишем выражение, определяющее среднее количество тактов для выполнения команды в конвейере CPI конвейера CPI идеального конвейера Приостановки из-за структурных конфликтов Приостановки из-за конфликтов типа RAW Приостановки из-за конфликтов типа WAR Приостановки из-за конфликтов типа WAW Приостановки из-за конфликтов по управлению CPI идеального конвейера есть не что иное, как максимальная пропускная способность, достижимая при реализации.

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

Это выражение позволяет также охарактеризовать различные методы, которые будут рассмотрены в этой главе, по тому компоненту общего CPI, который соответствующий метод уменьшает.На рисунке 3.11 показаны некоторые методы, которые будут рассмотрены, и их воздействие на величину CPI. Метод Снижает Разворачивание циклов Приостановки по управлению Базовое планирование конвейера Приостановки RAW Динамической планирование с централизованной схемой управления Приостановки RAW Динамическое планирование с переименованием регистров Приостановки WAR и WAW Динамическое прогнозирование переходов Приостановки по управлению Выдача нескольких команд в одном такте Идеальный CPI Анализ зависимостей компилятором Идеальный CPI и приостановки по данным Программная конвейеризация и планирование трасс Идеальный CPI и приостановки по данным Выполнение по предположению Все приостановки по данным и управлению Динамическое устранение неоднозначности памяти Приостановки RAW, связанные с памятью Рис. 3.11. Прежде, чем начать рассмотрение этих методов, необходимо определить концепции, на которых эти методы построены. Параллелизм уровня команд зависимости и конфликты по данным Все рассматриваемые в этой главе методы используют параллелизм, заложенный в последовательности команд.

Как мы установили выше этот тип параллелизма называется параллелизмом уровня команд или ILP. Степень параллелизма, доступная внутри базового блока линейной последовательности команд, переходы из вне которой разрешены только на ее вход, а переходы внутри которой разрешены только на ее выход достаточно мала. Например, средняя частота переходов в целочисленных программах составляет около 16 . Это означает, что в среднем между двумя переходами выполняются примерно пять команд.

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

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

Этот тип параллелизма часто называется параллелизмом уровня итеративного цикла.Ниже приведен простой пример цикла, выполняющего сложение двух 1000-элементных векторов, который является полностью параллельным for i 1 i 1000 i i 1 x i x i y i Каждая итерация цикла может перекрываться с любой другой итерацией, хотя внутри каждой итерации цикла практическая возможность перекрытия небольшая.

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

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

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

Команда, вырабатывающая результат Команда, использующая результат Задержка в тактах Операция АЛУ с ПТ Другая операция АЛУ с ПТ 3 Операция АЛУ с ПТ Запись двойного слова 2 Загрузка двойного слова Другая операция АЛУ с ПТ 1 Загрузка двойного слова Запись двойного слова 0 Рис. 3.12. В данном коротком разделе мы рассмотрим вопрос о том, каким образом компилятор может увеличить степень параллелизма уровня команд путем разворачивания циклов.

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

Программа для машины, не рассчитанная на использование конвейера, будет выглядеть примерно так Loop LD F0,0 R1 F0 элемент вектора ADDD F4,F0,F2 добавляет скаляр из F2 SD 0 R1 ,F4 запись результата SUBI R1,R1, 8 пересчитать указатель 8 байт в двойном слове BNEZ R1, Loop переход R1! нулю Для упрощения мы предполагаем, что массив начинается с ячейки 0. Если бы он находился в любом другом месте, цикл потребовал бы наличия одной дополнительной целочисленной команды для выполнения сравнения с регистром R1. Рассмотрим работу этого цикла при выполнении на простом конвейере с задержками, показанными на рисунке 3.12. Если не делать никакого планирования, работа цикла будет выглядеть следующим образом Такт выдачи Loop LD F0,0 R1 1 приостановка 2 ADDD F4,F0,F2 3 приостановка 4 приостановка 5 SD 0 R1 ,F4 6 SUBI R1,R1, 8 7 BNEZ R1,Loop 8 приостановка 9 Для его выполнения потребуется 9 тактов на итерацию одна приостановка для команды LD, две для команды ADDD, и одна для задержанного перехода.

Мы можем спланировать цикл так, чтобы получить Loop LD F0,0 R1 1 приостановка 2 ADDD F4,F0,F2 3 SUBI R1,R1, 8 4 BNEZ R1,Loop задержанный переход 5 SD 8 R1 ,F4 команда изменяется, когда 6 меняется местами с командой SUB1 Время выполнения уменьшилось с 9 до 6 тактов.

Заметим, что для планирования задержанного перехода компилятор должен определить, что он может поменять местами команды SUB1 и SD путем изменения адреса в команде записи SD Адрес был равен 0 R1 , а теперь равен 8 R1 . Это не тривиальная задача, поскольку большинство компиляторов будут видеть, что команда SD зависит от SUB1, и откажутся от такой перестановки мест. Более изощренный компилятор смог бы рассчитать отношения и выполнить перестановку.

Цепочка зависимостей от команды LD к команде ADDD и далее к команде SD определяет количество тактов, необходимое для данного цикла.В вышеприведенном примере мы завершаем одну итерацию цикла и выполняем запись одного элемента вектора каждые 6 тактов, но действительная работа по обработке элемента вектора отнимает только 3 из этих 6 тактов загрузка, сложение и запись . Оставшиеся 3 такта составляют накладные расходы на выполнение цикла команды SUB1, BNEZ и приостановка . Чтобы устранить эти три такта нам нужно иметь больше операций в цикле относительно числа команд, связанных с накладными расходами.

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

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

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

Ниже приведен результат, полученный путем слияния команд SUB1 и выбрасывания ненужных операций BNEZ, которые дублируются при разворачивании цикла.Loop LD F0,0 R1 ADDD F4,F0,F2 SD 0 R1 ,F4 выбрасывается SUB1 и BNEZ LD F6 8 R1 ADDD F8,F6,F2 SD -8 R1 ,F8 выбрасывается SUB1 и BNEZ LD F10 16 R1 ADDD F12,F10,F2 SD -16 R1 , F12 выбрасывается SUB1 и BNEZ LD F14 24 R1 ADDD F16,F14,F2 SD -24 R1 ,F16 SUB1 R1,R1, 32 BNEZ R1, Loop Мы ликвидировали три условных перехода и три операции декрементирования R1. Адреса команд загрузки и записи были скорректированы так, чтобы позволить слить команды SUB1 в одну команду по регистру R1. При отсутствии планирования за каждой командой здесь следует зависимая команда и это будет приводить к приостановкам конвейера. Этот цикл будет выполняться за 27 тактов на каждую команду LD потребуется 2 такта, на каждую команду ADDD - 3, на условный переход - 2 и на все другие команды 1 такт или по 6.8 такта на каждый из четырех элементов.

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

В реальных программах мы обычно не знаем верхней границы цикла.Предположим, что она равна n и мы хотели бы развернуть цикл так, чтобы иметь k копий тела цикла.

Вместо единственного развернутого цикла мы генерируем пару циклов. Первый из них выполняется n mod k раз и имеет тело первоначального цикла.Развернутая версия цикла окружается внешним циклом, который выполняется n div k раз. В вышеприведенном примере разворачивание цикла увеличивает производительность этого цикла путем устранения команд, связанных с накладными расходами цикла, хотя оно заметно увеличивает размер программного кода. Насколько увеличится производительность, если цикл будет оптимизироваться? Ниже представлен развернутый цикл из предыдущего примера после оптимизации.

Loop LD F0,0 R1 LD F6 8 R1 LD F10 16 R1 LD F14 24 R1 ADDD F4,F0,F2 ADDD F8,F6,F2 ADDD F12,F10,F2 ADDD F16,F14,F2 SD 0 R1 ,F4 SD -8 R1 ,F8 SD -16 R1 ,F12 SUB1 R1,R1, 32 BNEZ R1, Loop SD 8 R1 ,F16 8 - 32 -24 Время выполнения развернутого цикла снизилось до 14 тактов или до 3.5 тактов на элемент, по сравнению с 6.8 тактов на элемент до оптимизации, и по сравнению с 6 тактами при оптимизации без разворачивания цикла.

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

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

Аппаратное прогнозирование направления переходов и снижение потерь на организацию переходовБуфера прогнозирования условных переходов Простейшей схемой динамического прогнозирования направления условных переходов является буфер прогнозирования условных переходов branch-prediction buffer или таблица истории условных переходов branch history table . Буфер прогнозирования условных переходов представляет собой небольшую память, адресуемую с помощью младших разрядов адреса команды перехода.

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

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

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

Направление перехода будет неправильно предсказываться при первой и при последней итерации цикла. Неправильный прогноз последней итерации цикла неизбежен, поскольку бит прогноза будет говорить, что переход выполняемый переход был девять раз подряд выполняемым . Неправильный прогноз на первой итерации происходит из-за того, что бит прогноза инвертируется при предыдущем выполнении последней итерации цикла, поскольку в этой итерации переход был невыполняемым.Таким образом, точность прогноза для перехода, который выполнялся в 90 случаев, составила только 80 2 некорректных прогноза и 8 корректных . В общем случае, для команд условного перехода, используемых для организации циклов, переход является выполняемым много раз подряд, а затем один раз оказывается невыполняемым.

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

В двухбитовой схеме прогноз должен быть сделан неверно дважды, прежде чем он изменится на противоположное значение. На рисунке 3.13 представлена диаграмма состояний двухбитовой схемы прогнозирования направления перехода.Двухбитовая схема прогнозирования в действительности является частным случаем более общей схемы, которая в каждой строке буфера прогнозирования имеет n-битовый счетчик. Этот счетчик может принимать значения от 0 до 2n - 1. Тогда схема прогноза будет следующей Если значение счетчика больше или равно 2n-1 точка на середине интервала , то переход прогнозируется как выполняемый.

Если направление перехода предсказано правильно, к значению счетчика добавляется единица если только оно не достигло максимальной величины если прогноз был неверным, из значения счетчика вычитается единица. Если значение счетчика меньше, чем 2n-1, то переход прогнозируется как невыполняемый.Если направление перехода предсказано правильно, из значения счетчика вычитается единица если только не достигнуто значение 0 если прогноз был неверным, к значению счетчика добавляется единица.

Исследования n-битовых схем прогнозирования показали, что двухбитовая схема работает почти также хорошо, и поэтому в большинстве систем применяются двухбитовые схемы прогноза, а не n-битовые. Рис. 3.13. Диаграмма состояния двухбитовой схемы прогнозирования Буфер прогнозирования переходов может быть реализован в виде небольшой специальной кэш-памяти, доступ к которой осуществляется с помощью адреса команды во время стадии выборки команды в конвейере IF , или как пара битов, связанных с каждым блоком кэш-памяти команд и выбираемых с каждой командой.

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

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

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

Даже если эта строка соответствует совсем другой команде перехода, прогноз может быть удачным.Какую точность можно ожидать от буфера прогнозирования переходов на реальных приложениях при использовании 2 бит на каждую строку буфера? Для набора оценочных тестов SPEC-89 буфер прогнозирования переходов с 4096 строками дает точность прогноза от 99 до 82 , т.е. процент неудачных прогнозов составляет от 1 до 18 рисунок 3.14 . Следует отметить, что буфер емкостью 4К строк считается очень большим.

Буферы меньшего объема дадут худшие результаты. Рис. 3.14. Сравнение качества 2-битового прогноза Однако одного знания точности прогноза не достаточно для того, чтобы определить воздействие переходов на производительность машины, даже если известны время выполнения перехода и потери при неудачном прогнозе.Необходимо учитывать частоту переходов в программе, поскольку важность правильного прогноза больше в программах с большей частотой переходов.

Например, целочисленные программы li, eqntott, expresso и gcc имеют большую частоту переходов, чем значительно более простые для прогнозирования программы плавающей точки nasa7, matrix300 и tomcatv. Поскольку главной задачей является использование максимально доступной степени параллелизма программы, точность прогноза направления переходов становится очень важной.Как видно из рисунка 3.14, точность схемы прогнозирования для целочисленных программ, которые обычно имеют более высокую частоту переходов, меньше, чем для научных программ с плавающей точкой, в которых интенсивно используются циклы.

Можно решать эту проблему двумя способами увеличением размера буфера и увеличением точности схемы, которая используется для выполнения каждого отдельного прогноза. Буфер с 4К строками уже достаточно большой и, как показывает рисунок 3.14, работает практически также, что и буфер бесконечного размера.Из этого рисунка становится также ясно, что коэффициент попаданий буфера не является лимитирующим фактором.

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

Рассмотрим, например, небольшой фрагмент из текста программы eqntott тестового пакета SPEC92 это наихудший случай для двухбитовой схемы прогноза if aa 2 aa 0 if bb 2 bb 0 if aa! bb Ниже приведен текст сгенерированной программы предполагается, что aa и bb размещены в регистрах R1 и R2 SUBI R3,R1, 2 BNEZ R3,L1 переход b1 aa! 2 ADD R1,R0,R0 aa 0 L1 SUBI R3,R2, 2 BNEZ R3,L2 переход b2 bb! 2 ADD R2,R0,R0 bb 0 L2 SUB R3,R1,R2 R3 aa-bb BEQZ R3,L3 branch b3 aa bb . L3 Пометим команды перехода как b1, b2 и b3. Можно заметить, что поведение перехода b3 коррелирует с переходами b1 и b2. Ясно, что если оба перехода b1 и b2 являются невыполняемыми т.е. оба условия if оцениваются как истинные и обеим переменным aa и bb присвоено значение 0 , то переход b3 будет выполняемым, поскольку aa и bb очевидно равны.

Схема прогнозирования, которая для предсказания направления перехода использует только прошлое поведение того же перехода никогда этого не учтет.

Схемы прогнозирования, которые для предсказания направления перехода используют поведение других команд перехода, называются коррелированными или двухуровневыми схемами прогнозирования.Схема прогнозирования называется прогнозом 1,1 , если она использует поведение одного последнего перехода для выбора из пары однобитовых схем прогнозирования на каждый переход. В общем случае схема прогнозирования m,n использует поведение последних m переходов для выбора из 2m схем прогнозирования, каждая из которых представляет собой n-битовую схему прогнозирования для каждого отдельного перехода.

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

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

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

Например, на рисунке 3.15 в буфере 2,2 с общим числом строк, равным 64, четыре младших разряда адр