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

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

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), однако в это время регистр

а)

б)

в)

Рис. 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). Он получил свое название от широко применяющегося в компиляторах метода переименования - метода размещения данных, способствующего сокращению числа зависимостей и тем самым увеличению производительности при отображении необходимых исходной программе объектов (например, переменных) на аппарат­ные ресурсы (например, ячейки памяти и регистры).

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

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

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

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