Простейший конвейер, производительность конвейера

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

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

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

В качестве примера рассмотрим некоторый абстрактный процес­сор, имеющий типичные черты многих современных RISC-процес­соров. Основа архитектуры процессора – банк из 32 регист­ров об­щего назначения и счетчик команд. Система команд процес­сора включает типичный набор арифметических и логических ко­манд, команд с плавающей точкой, операций ветвлений. Команды имеют трехадресный формат. Данные, подлежащие обработке, должны быть предварительно размещены в регистрах процессора. Загрузка данных их памяти в регистры и запись данных в память произво­дится командами загрузки – записи. Процесс выполнения команды можно разбить на следующие независимые этапы:

1) считывание команды – IF;

2) дешифрация команды – ID;

3) вычисление адреса/выборка данных из регистров – RD;

4) выполнение команды/обращение к памяти – EX;

5) запись результата в регистр – WR.

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

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

Команда 1

Команда 2

Команда 3

IF

ID

RD

EX

WR

IF

ID

RD

EX

WR

IF

ID

RD

EX

WR

а)

№ такта
Команда 1	IF	ID	RD	EX	WR
Команда 2		IF	ID	RD	EX	WR
Команда 3			IF	ID	RD	EX	WR
Команда 4				IF	ID	RD	EX	WR
Команда 5					IF	ID	RD	EX	WR

б)

Рис 25. Диаграмма работы простейшего процессора а) в неконвейерном режиме, б) с конвейеризацией

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

IF	ID	RD	EX	WR

Максимальная длительность у этапа выполнения – 60 нс., она и определяет минимальную длительность этапа при конвейерной об­работке. Пусть дополнительные расходы на пересылку данных из блока в блок составят 5 нс. Тогда длительность каждого этапа должна быть равной 65 нс. Длительность выполнения команды в не­конвейерном режиме составит 50 + 50 + 50 + 60 + 50 = 260 нс. В конвейерном процессоре длительность выполнения одной команды составит 65 * 5 = 325 нс., т.е. время выполнения одной команды возрастет почти в полтора раза. Однако при последовательном вы­полнении команд время, требуемое для выполнения, например, 100 команд составит 100 * 260 нс. = 26 мкс. Время выполнения тех же 100 команд на конвейере при отсутствии задержек составит 325 + (100 – 1) * 65 = 6.76 мкс (время выполнения одной команды плюс длительность завершающего этапа для 99 оставшихся команд). При большом количестве выполняемых команд, каждая команда в кон­вейерном режиме будет завершаться в среднем за 65 нс.

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

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

2. Конфликты по данным, возникающие в случае, когда выпол­нение одной команды зависит от результата выполнения предыду­щей команды.

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

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

Структурные конфликты

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

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

№ такта
«Длинная» команда	IF	ID	RD	EX	EX	EX	WR
Следующая команда		IF	ID	RD	*	*	EX	WR
Следующая команда			IF	ID	*	*	RD	EX	WR

Рис 26. Простой процессора из-за структурного конфликта

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

1) блок обращения к памяти;

2) блок арифметики с фиксированной точкой;

3) блок операций целочисленного умножения / деления;

4) блок операций с плавающей точкой.

Пример такой схемы процессора показан на рис. 27.

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

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

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

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

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

Конфликты по данным

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

ADD R1,R2,R3 ; в регистр R1 помещается сумма R2 и R3

SUB R4,R2,R1 ; регистр R4 равен разности R1 и R2

MUL R5,R1,R6 ; регистр R5 равен разности R1 и R6 .

В приведенной последовательности команды вычитания и умно­жения используют результат выполнения команды сложения. Рас­смотрим процесс выполнения этих команд в конвейерной системе (см. рис. 28). Команда сложения сформирует результат в конце такта выполнения (EX в такте 4) и в такте записи (WR, такт 5) поместит его в регистр процессора. После этого новое значение станет дос­тупным для считывания. Команде вычитания потребуется обра­титься за операндом в такте RD (такт 4), однако в это время регистр

№ такта
ADD R1,R2,R3	IF	ID	RD	EX	WR
					ëданные записаны
SUB R4,R2,R1		IF	ID	RD	EX	WR
Данные считываются ì
MUL R5,R1,R6			IF	ID	RD	EX	WR

а)

№ такта
ADD R1,R2,R3	IF	ID	RD	EX	WR
SUB R4,R2,R1		IF	ID	*	*	RD	EX	WR
MUL R5,R1,R6			IF	*	*	ID	RD	EX	WR

б)

№ такта
ADD R1,R2,R3	IF	ID	RD	EX	WR
Момент пересылки данных ì
SUB R4,R2,R1		IF	ID	RD	EX	WR
	ëданные доступны
MUL R5,R1,R6			IF	ID	RD	EX	WR

в)

Рис. 28 Конфликт по данным и его разрешение: а) операнд счи­тывается до того, как он записан; б) задержка команды с потерей производительности; в) ускоренная пересылка данных.

будет все еще содержать некоторое неопределенной значение. Можно считать, что это старое значение, записанное некоторой пре­дыдущей командой (см. рис. 28 а), однако это не всегда так. Если в момент выполнения команды сложения произойдет прерывание, то перед прерыванием команда будет завершена и в регистр R1 будет помещен правильный результат.

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

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

Однако не все конфликты по данным можно преодолеть, исполь­зуя механизм ускоренной пересылки. Рассмотрим выполнение про­стого оператора A = B + C на языке высокого уровня. Скорее всего, компилятор сформирует для такого оператора приблизительно сле­дующую последовательность команд:

LOAD R1, B ;загрузка из памяти значе­ния B

LOAD R2, C ;загрузка из памяти значе­ния C

ADD R3, R1, R2 ;суммирование

STORE A, R3 ; сохранение результата.

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

Избежать потери производительности можно только если изме­нить порядок выполнения команд с учетом других выполняемых команд. Пусть, например, в программе выполняются два последова­тельных оператора A = B + C и E = D + F. Последовательность ко­манд для решения задачи будет следующей.

LOAD R1, B ;загрузка из памяти значе­ния B

LOAD R2, C ;загрузка из памяти значе­ния C

ADD R3, R1, R2 ;суммирование

STORE A, R3 ; сохранение резуль­тата A.

LOAD R1, D ;загрузка из памяти значе­ния D

LOAD R2, F ;загрузка из памяти значе­ния F

ADD R3, R1, R2 ;суммирование

STORE E, R3 ; сохранение резуль­тата E.

Можно избежать задержек, если изменить порядок выполнения команд в данной последовательности следующим образом:

LOAD R1,B ;загрузка из памяти значе­ния B

LOAD R2,C ;загрузка из памяти значе­ния C

LOAD R1,D ;загрузка из памяти значе­ния D

ADD R3,R1,R2 ;суммирование

LOAD R2,F ;загрузка из памяти значе­ния F

STORE A,R3 ; сохранение результата A.

ADD R3,R1,R2 ;суммирование

STORE E,R3 ; сохранение результата E.

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

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

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

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

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

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

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