Причины структурных конфликтов.
1. Не полностью конвейерная структура процессора, при которой некоторые ступени отдельных команд выполняются более одного такта.
Пусть этап выполнения команды i+1 занимает 3 такта. Тогда диаграмма работы конвейера будет иметь вид, представленный в таблица 2.3.
| Таблица 2.3 | |||||||||
| Команда | Такт | ||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| i | IF | ID | OR | EX | WB | ||||
| i+1 | IF | ID | OR | EX | EX | EX | WB | ||
| i+2 | IF | ID | OR | O | O | EX | WB | ||
| i+3 | IF | ID | OR | O | O | EX | |||
| i+4 | IF | ID | OR | O | O | ||||
При этом в работе конвейера возникают так называемые "пузыри" (обработка команд i+2 и следующих за ней, начиная с такта 6), которые снижают производительность процессора.
Эту ситуацию можно было бы ликвидировать двумя способами. Первый предполагает увеличение времени такта до такой величины, которая позволила бы все этапы любой команды выполнять за один такт. Однако при этом существенно снижается эффект конвейерной обработки, так как все этапы всех команд будут выполняться значительно дольше, в то время как обычно нескольких тактов требует выполнение лишь отдельных этапов очень небольшого количества команд. Второй способ предполагает использование таких аппаратных решений, которые позволили бы значительно снизить затраты времени на выполнение данного этапа (например, использовать матричные схемы умножения). Но это приведет к усложнению схемы процессора и невозможности реализации на этой БИС других функционально более важных узлов. Так как представленная в таблице 2.3 ситуация возникает при реализации команд, относительно редко встречающихся в программе, то обычно разработчики процессоров ищут компромисс между увеличением длительности такта и усложнением того или иного устройства процессора.
2. Недостаточное дублирование некоторых ресурсов.
Одним из типичных примеров служит конфликт из-за доступа к запоминающим устройствам. Из таблицы 2.1 видно, что в случае, когда операнды и команды находятся в одном запоминающем устройстве, начиная с такта 3, работу конвейера придется постоянно приостанавливать, поскольку различные команды в одном и том же такте обращаются к памяти на считывание команды, выборку операнда, запись результата.
Борьба с конфликтами такого рода проводится путем увеличения количества однотипных функциональных устройств, которые могут одновременно выполнять одни и те же или схожие функции. Например, обычно разделяют кэш-память для хранения команд и кэш-память данных, а также используют многопортовую схему доступа к регистровой памяти, при которой к регистрам можно одновременно обращаться по одному каналу для записи, а по другому - для считывания информации. Конфликты из-за исполнительных устройств обычно сглаживаются введением в состав процессора дополнительных блоков.
В суперскалярных процессорах реализована конвейерная обработка и параллельное выполнение команд. Несколько команд одновременно могут выполниться в течение одного такта. В таблице 2.4 представлена последовательность выполнения команд в процессоре, имеющем два конвейера, при условии, что команде К1 требуется 3 такта на этапе EX.
| Таблица 2.4 | ||||||||||||||
| Этап | Такт | |||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||||||
| IF | K1 | K2 | K3 | K4 | K5 | K6 | K7 | K8 | K7 | K9 | K7 | K10 | K11 | K12 |
| ID | K1 | K2 | K3 | K4 | K5 | K6 | K5 | K8 | K5 | K9 | K7 | K10 | ||
| OR | K1 | K2 | K3 | K4 | K3 | K6 | K3 | K8 | K5 | K9 | ||||
| EX | K1 | K2 | K1 | K4 | K1 | K6 | K3 | K8 | ||||||
| WB | K2 | K4 | K1 | K6 | ||||||||||
При этом команды будут завершаться в последовательности К2-К4-К1-К6-...
Следовательно, может нарушиться исходный порядок завершения команд программы. Недостатком суперскалярных процессоров является необходимость синхронного продвижения команд в каждом из конвейеров. При возникновении затора в одном из конвейеров должны приостанавливать свою работу и другие. Но такие приостановки существенно снижают быстродействие процессора. Разрешение этой ситуации состоит в том, чтобы дать возможность выполняться командам в одном конвейере вне зависимости от ситуации в других конвейерах. Это приводит к неупорядоченному выполнению команд. При этом команды, стоящие в программе позже, могут завершиться ранее команд, стоящих впереди. Аппаратные средства процессора должны гарантировать, что результаты выполненных команд будут записаны в приемник в том порядке, в котором команды записаны в программе. Для этого в процессоре результаты этапа выполнения команды обычно сохраняются в специальном буфере восстановления последовательности команд. Запись результата очередной команды из этого буфера в приемник результата проводится лишь после того, как выполнены все предшествующие команды и записаны их результаты.
Конфликты по управлению возникают при конвейеризации команд переходов и других команд, изменяющих значение счетчика команд.
Суть конфликтов этой группы наиболее удобно проиллюстрировать на примере команд условного перехода. Пусть в программе, представленной в таблице 2.1, команда i+1 является командой условного перехода, формирующей адрес следующей команды в зависимости от результата выполнения команды i. Команда i завершит свое выполнение в такте 5. В то же время команда условного перехода уже в такте 3 должна прочитать необходимые ей признаки, чтобы правильно сформировать адрес следующей команды. Если конвейер имеет большую глубину (например, 20 ступеней), то промежуток времени между формированием признака результата и тактом, где он анализируется, может быть еще большим. В инженерных задачах примерно каждая шестая команда является командой условного перехода, поэтому приостановки конвейера при выполнении команд переходов до определения истинного направления перехода существенно скажутся на производительности процессора.
Наиболее эффективным методом снижения потерь от конфликтов по управлению служит предсказание переходов. Суть данного метода заключается в том, что при выполнении команды условного перехода специальный блок процессора определяет наиболее вероятное направление перехода, не дожидаясь формирования признаков, на основании анализа которых этот переход реализуется. Процессор начинает выбирать из памяти и выполнять команды по предсказанной ветви программы (так называемое исполнение по предположению, или "спекулятивное" исполнение). Однако так как направление перехода может быть предсказано неверно, то получаемые результаты с целью обеспечения возможности их аннулирования не записываются в память или регистры (то есть для них не выполняется этап WB), а накапливаются в специальном буфере результатов.
В современных процессорах вероятность правильного предсказания направления переходов достигает 90% [6,11].
Конфликты по данным возникают в случаях, когда выполнение одной команды зависит от результата выполнения предыдущей команды. При обсуждении этих конфликтов будем предполагать, что команда i предшествует команде j[11].
Все виды зависимостей по данным могут быть классифицированы по типу ассоциаций: RAR — «чтение после чтения», WAR — «запись после чтения» и WAW — «запись после записи», RAW — «чтение после записи».
Некоторые из зависимостей по данным могут быть устранены. RAR, по сути дела, соответствует отсутствию зависимости, поскольку в данном случае порядок выполнения команд не имеет значения. Действительной зависимостью является только «чтение после записи» (RAW), так как необходимо прочитать предварительно записанные новые данные, а не старые.
Лишние зависимости по данным появляются в результате «записи после чтения» (WAR) и «записи после записи» (WAW). Лишние зависимости появляются по нескольким причинам: не оптимизированный программный код, ограничение количества регистров, стремление к экономии памяти, наличие программных циклов. Важно отметить, что запись может быть произведена в любой свободный ресурс, а не только тот, который указан в программе[1].
1. Конфликты типа RAW (Read After Write): команда j пытается прочитать операнд прежде, чем команда i запишет на это место свой результат. При этом команда j может получить некорректное старое значение операнда.
Проиллюстрируем этот тип конфликта на примере выполнения команд, представленных в таблице 2.1. Пусть выполняемые команды имеют следующий вид:
| i | ADD R1,R2 | R1 = R1+R2 |
| i+1=j | SUB R3,R1 | R3 = R3-R1 |
Команда i изменит состояние регистра R1 в такте 5. Но команда i+1 должна прочитать значение операнда R1 в такте 4. Если не приняты специальные меры, то из регистра R1 будет прочитано значение, которое было в нем до выполнения команды i.
Уменьшение влияния конфликта типа RAW обеспечивается методом обхода (продвижения) данных. В этом случае результаты, полученные на выходах исполнительных устройств, помимо входов приемника результата передаются также на входы всех исполнительных устройств процессора. Если устройство управления обнаруживает, что данный результат требуется одной из последующих команд в качестве операнда, то он сразу же, параллельно с записью в приемник результата, передается на вход исполнительного устройства для использования следующей командой.
Конфликты типа RAW обусловлены именно конвейерной организацией обработки команд.
Главной причиной двух других типов конфликтов по данным является возможность неупорядоченного выполнения команд в современных роцессорах, то есть выполнение команд не в том порядке, в котором они записаны в программе.