Структура и функционирование конвейера

Параллелизм ассемблерного уровня реализуется двумя способами:

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

Одновременная работа этих блоков позволяет параллельно обрабатывать сразу несколько смежных команд.

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

2. В виде многопроцессорной системы, где совокупность процессоров обрабатывает в каждом такте один ярус ЯПФ некоторого выражения. Обычно в каждом процессоре используется и конвейерная обработка. Поэтому в суперскалярном процессоре одновременно обрабатывается m * n команд, где m - число этапов в конвейере, а n - число конвейеров; в каждом такте вырабатывается n результатов. Если в идеальном случае для конвейера принять:

Δt=t/m

где Δt - время одного такта, а t - время выполнения одной команды, то быстродействие конвейера будет:

V = m/Δt = (m*n)/t

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

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

Конвейеры можно разделить на две большие группы:

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

С точки зрения скалярного параллелизма интерес представляют преимущественно скалярные конвейеры. В качестве примера такого конвейера рассмотрим наиболее распространенный конвейер микропроцессора типа CISC (за прототип взят конвейер МП "Пентиум" из семейства МП 80x86).

Рис. 4.1. Целочисленный и плавающий конвейер CISC-процессора

Целочисленный конвейер содержит следующие ступени (рис. 4.1):

• ступень предвыборки PF (Prefetch), которая осуществляет предварительную упреждающую выборку группы команд в соответствующий буфер;
• ступень декодирования полей команды D1 (Decoder 1);
• ступень декодирования D2 (Decoder 2), на которой производится вычисление абсолютного адреса операнда, если операнд расположен в памяти;
• на ступени исполнения EX (Execution) производится выборка операндов из РОН или памяти и выполнение операции в АЛУ;
• наконец, на ступени записи результата WR (Write Back) производится передача полученного результата в блок РОН.

Плавающий конвейер имеет общие с целочисленным конвейером ступени PF, D1, D2, но кроме того, имеет еще 5 дополнительных ступеней (переход показан пунктирной стрелкой):

• на ступени EX производится чтение из памяти или регистров или запись в память;
• на ступени X1 выполняется часть плавающей операции (фаза 1) или запись в плавающий РОН. Возможен обход (bypass) на ступени EX;
• на ступени X2 выполняется продолжение обработки (фаза 2);
• на ступени WF производится округление и обратная запись результата в блок РОН;
• на ступени ER (Error Reporting) выводится сообщение о наличии ошибок.

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

Однако получению максимального быстродействия в CISC-конвейере препятствуют следующие обстоятельства:

• Простои конвейера из-за наличия команд, которые требуют многотактного исполнения в АЛУ или на других ступенях конвейера.
• Простои конвейера из-за зависимости по данным между соседними командами.
• Простои конвейера из-за очистки и повторной загрузки конвейера в случае ошибки при предварительном выборе направления условного перехода.
• Ограничения пропускной способности аппаратных средств: РОН, памяти различных видов, шин связи.

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

Многотактные команды. В таблице 4.1 представлено время нахождения некоторых типичных команд в целочисленном конвейере на этапе EX, поскольку на остальных этапах на выполнение команды затрачивается только один такт. (Здесь и далее рассматриваются команды семейства 80x86).

Таблица 4.1.

Длительность некоторых команд в целочисленном конвейере

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

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

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

Таблица 4.2.

Длительность некоторых команд в плавающем конвейере

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

Из таблицы 4.2 следует, что большинство команд находятся в АЛУ (ступени EX, X1, X2) несколько тактов (время в скобках), однако на каждом этапе задерживаются только 1 такт.

Следовательно, темп выполнения в конвейере - 1 такт на команду (команды FLD, FADP, FMUL). Некоторые команды могут на одном этапе находиться несколько тактов, приостанавливая на это время конвейер.

Поскольку целочисленное (ступень EX) и плавающее АЛУ работают независимо, то прием команд на вход общей части конвейера приостанавливается только в следующих случаях:

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

Зависимость по данным. Рассмотрим пример выполнения в процессоре с плавающей запятой следующего отрезка программы:

1 FLD [M1]
2 FMUL [M2]
3 FADD [M3] (4.6)
4 FST [M4]

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

На рис. 4.2 представлена временная диаграмма выполнения этого отрезка программы.

Рис. 4.2. Диаграмма работы конвейера

Из рис. 4.2, а следует, что ступень EX простаивает 7 тактов из 12:

• В такте 1 ступень EX не работает, так как результат команды 1 является операндом команды 2, поэтому в такте 2 он записывается в стек и только в такте 3 может быть считан командой 2.
• Аналогично команда 3 ожидает такты 4, 5, 6, пока результат команды 2 на ступени WF не окажется в стеке, и только в такте 7 может считать этот результат из стека.
• Зависимость между командами 3 и 4 также дает такты простоя 8, 9 и 10 ступени EX.

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

Обход 2 позволяет послать результат арифметической операции со ступени WF на приемную ступень EX одновременно с записью этого результата в стек.

На рис. 4.2, б представлена диаграмма той же программы, но в такте 2 результат команды 1 одновременно с записью в стек передается на ступень EX, благодаря чему может быть начата команда 2. То же происходит и в такте 5. Команда 4 не может быть начата в такте 8, так как команда FST начинает работать только после записи результата в РОН предыдущей командой.

Таким образом, обходы оказали небольшую помощь (исключены 2 такта из 12).

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

1 FLD [M1]
2 FMUL [M2]
3 НК
4 НК
5 FADD [M3] (4.7)
6 НК
7 НК
8 НК
9 FST [M4]

Рис. 4.3. Диаграмма выполнения программы с включением независимых команд

Программа (4.6) согласно рис. 4.2, б выполняется за 10 тактов, следовательно, архитектурная скорость будет равна:

z1 = 4/10 = 0,4.

Программа (4.7) также выполнится за 10 тактов, но при этом согласно рис. 4.3

z2 = 9/10 = 0,9.

2 Программа (4.7) реализует скалярную форму параллелизма в конвейерных процессорах. К сожалению, размещение независимых команд в программах с плавающей запятой в CISC-процессорах вызывает трудности из-за стековой организации файла РОН.

Условные переходы. Рассмотрим отрезок программы:

Известно, что в конвейере адрес перехода определяется только на ступени EX. Но, чтобы не допустить простоев на этапах конвейера, в (4.8) необходимо непосредственно за командой перехода 3 начинать выборку одной из ветвей, начиная с команды 4 либо с команды 11.

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

Рис. 4.4. Перезагрузка конвейера при ошибке выбора направления перехода

Потеря тактов будет больше, если команды 11 не окажется в буфере предварительной выборки.

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

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

К статическим методам относятся:

1. Исключение ветвлений в программе, если это возможно.

Для этого применяют: вычисление ветвлений на этапе компиляции; вынос ветвлений за пределы цикла; развертку итераций.

В приведенном ниже примере развертка позволяет в два раза сократить число ветвлений:

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

3. Еще один метод называется отложенным ветвлением. В примере (4.8) команда 2 не влияет на условный переход, поэтому ее можно переставить после команды 3 и всегда выполнять после команды перехода независимо от направления перехода.

Программа будет выглядеть следующим образом:

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

В динамике управление переходами осуществляется следующими способами:

1. Самый простой способ состоит в том, чтобы остановить прием команд на вход конвейера до тех пор, пока команда перехода не достигнет ступени EX и не будет вычислено реальное направление перехода. Однако этот метод, упрощая управление, не решает проблемы простоев.
2. Наиболее сложный способ заключается в том, чтобы при появлении на входе команды перехода выбирать и условно выполнять обе ветви возможных переходов. Условное выполнение обозначает, что до момента определения адреса перехода запрещается запись в регистры или память.
3. Наконец, третьим способом динамической обработки ветвлений является предсказание. Самым простым способом предсказания является выбор для выполнения той ветви, которая следует непосредственно за командой перехода (короткий переход). Но в 50% случаев этот выбор будет ошибочным.

Более эффективной является система предсказаний на основе истории процесса вычислений.

На рис. 4.1 присутствует устройство прогнозирования ветвлений. Оно содержит таблицу достаточно большого размера, например, на 256 строк. В каждой строке таблицы записан для выполнения части программы:

1. Адрес команды перехода.
2. Адрес дальнего перехода.
3. Бит "истории", который указывает, по какому направлению произошел переход при последнем использовании команды перехода.

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

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

Буфер упреждающей выборки содержит две зоны: для текущей и альтернативной ветви и переключение с зоны на зону не вызывает простоев.

Описанный механизм ветвления позволяет выбирать правильные пути ветвления с вероятностью более 80%.

КЭШ. Фактором, также ограничивающим быстродействие конвейера, является недостаточное быстродействие ресурсов, в частности, памяти. Рассмотрим некоторые требования к памяти.

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

Регистры общего назначения являются наиболее быстрым видом памяти, их число колеблется от 8 до 32. РОН используется для хранения информации, как правило, локальной для тела цикла или базового блока. Чтобы избежать конфликтов при обращении к РОН, их делают многопортовыми (многовходовыми). Число портов обычно равняется трем: два для выдачи операндов и один - для приема результата.

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

Наиболее эффективным средством ускорения обращения к памяти является локальная (для АЛУ) память небольшого размера, называемая КЭШ.

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

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

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

Отображением называется способ размещения и выборки строк основной памяти из КЭШ-памяти.

Можно выделить четыре основных типа отображения:

1. Полностью ассоциативная КЭШ-память. Любая строка основной памяти может находиться в любой строке КЭШ-памяти. Каждая строка КЭШ-памяти содержит свой компаратор (устройство сравнения). Если процессору нужна строка с определенным адресом, он должен искать ее путем сравнения адреса с тэгом всех строк КЭШ-памяти. Если такое сравнение делать последовательно, то КЭШ-память теряет смысл из-за низкого быстродействия; если сравнение делать одновременно со всеми тэгами, то такая память из-за ее сложности не может иметь большой объем.

КЭШ-память ассоциативного типа обычно имеет небольшой объем и используется для вспомогательных целей.

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

Основное достоинство состоит в том, что накопитель такой памяти имеет структуру обычной прямоадресуемой памяти и нужен всего один компаратор, следовательно, такая КЭШ-память может иметь большую емкость.

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

3. Промежуточным между полностью ассоциативным и прямым отображением является секторное отображение, вариант которого описан в § 2.1. В этом случае в КЭШ-памяти располагаются страницы основной памяти. При обращении в КЭШ-память базовые адреса страниц в КЭШ-памяти устанавливаются с помощью служебной полностью ассоциативной памяти небольшого размера, а поиск слов в странице КЭШ-памяти производится на основе прямого адресного доступа. Секторная память удобна для больших ЭВМ, где программа может целиком располагаться в одной или нескольких страницах КЭШ-памяти. Для суперскалярных процессоров, реализуемых на одном кристалле, такой подход трудно реализовать, поскольку внутрикристальная КЭШ-память реально имеет объем менее одной страницы.

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

На рис. 4.5 представлен КЭШ с двукратной ассоциацией. Это означает, что по одному смещению выбирается строка, содержащая информацию по двум разным страницам памяти. Это увеличивает вероятность удачного обращения. Обычно кратность ассоциации колеблется от единицы до четырех. Обычная длина поля тэгов до 24 или 32 разрядов, длина строки данных (одной) - от 4 до 32 байтов; число строк в КЭШе - до 256.

Рис. 4.5. Структура множественного ассоциативного КЭШа

Важной величиной является число портов в КЭШе. Как правило, число адресных портов (входы тэга) составляет 2...3, а порт данных - единственный. Объем внутрикристального КЭШа в МП колеблется в пределах от 4 до 32 килобайт, а внешнего - составляет несколько сотен килобайт.

На рис. 4.6 представлена зависимость числа попаданий от размера КЭШ-памяти с множественно-ассоциативным доступом. Из рисунка следует, что, если строка КЭШ-памяти содержит более четырех строк основной памяти, то это уже увеличивает степень попаданий незначительно.

Рис. 4.6. Влияние характеристик КЭШ-памяти на вероятность попадания

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

Однако проблема многотактных команд может быть решена только при переходе от СISC к RISC и MISC системам команд.

Этот переход позволяет:

1. Сократить систему команд за счет устранения сложных команд.
2. Увеличить количество РОН; использовать для операций АЛУ трехадресные команды, ввести файлы РОН с произвольным доступом вместо стека для плавающей запятой.
3. Использовать команды фиксированного формата.

Рассмотрим эти средства несколько подробнее.

Переход к системе команд типа RISC приводит к разрешению системы команд на две группы: одна - для работы с АЛУ, другая - для работы с памятью. Такое разделение приводит к Load/Store архитектуре, представленной на рис. 4.7.

Рис. 4.7. Load-Store архитектура RISC-процессора

В такой структуре АЛУ и память работают параллельно. Чтобы обеспечить максимальное быстродействие системы, необходимо обеспечить упреждающую работу памяти.

Число РОН в RISC-процессоре достигает величины 32, 64 и даже более, в то время как в CISC оно не превосходит 8 или 16. Увеличение числа РОН уменьшает число обращений к памяти, сокращает длину программы, позволяет устранить некоторые зависимости по данным.

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

R3 = R1 + R2
R1 = R4 + R5

существует зависимость обратного типа, а в программе

R3 = R1 + R2
R6 = R4 + R5

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

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

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

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

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

Переход к новой системе команд типа RISC требует перепрограммирования громадного объема прикладного программного обеспечения, накопленного для широко распространенных систем команд типа CISC, используемых в МП i80x86, MC 680x00, по-этому естественным является стремление получить более высокую архитектурную скорость для CISC-МП на базе приближения свойства CISC-процессоров к свойствам RISC-процессоров. Для этой цели предпринимаются следующие действия программного и аппаратного характера:

1. Новые компиляторы CISC-процессоров строятся таким образом, чтобы для генерации машинных кодов из большого списка команд CISC-процессора использовать только небольшой набор простых команд, называемый RISC-ядро.
2. Ограничение на количество РОН в CISC-процессорах (всего 8 в i80x86) преодолевается следующим образом. При проектировании нового кристалла для CISC-процессора предусматривается увеличенный файл РОН, например, 32, и эти РОН составляют виртуальный файл. В процессе выполнения команд каждому логическому РОН, описанному в команде, предоставляется свободный РОН из виртуального файла, благодаря чему, как было показано ранее, растет параллелизм исполнения.
3. Для приближения стека по способу функционирования к файлу РОН с произвольным доступом аппаратно реализуются быстрые команды адресного обмена между регистрами стека типа FXCH, благодаря которым верхушка стека в каждом такте предстает как новый РОН с требуемым номером.

Составлено по материалам книги Г.И. Шпаковский. Организация параллельных ЭВМ и суперскалярных процессоров