Основы вычислительных конвейеров, страница 9

Помеха возникает, когда к объекту данных, внутри ЭВМ (например, к регистру, ячейке памяти или флажку) обращаются или его модифицируют две различные команды, столь близко расположенные в программе, что конвейеризация перекрывает их исполнение. Имеются три класса таких помех, формально называемых помехой чтение после записи (RAW), помехой запись после чтения (WAR) и помехой запись после записи (WAW). Для демонстрации различий между помехами рассмотрим следующий фрагмент программы:

.

.

.

STORE                    X

.

.

.

ADD                        X

STORE                    X

.

.

.

STORE                    X

.

.

.

Помеха RAW между командами i и j (предполагается, что команда j логически следует за командой i) возникает, когда команда j пытается читать некоторый объект, модифицируемый командой i. Если та операция в команде i, которая модифицирует этот объект, не завершена до того, как команда j начинает к нему обращаться, то команда j прочитает неправильное значение этого объекта. В приведенном выше фрагменте программы помеха RAW потенциально существует между первой командой STORE (записать в ячейку Х) и командой ADD (сложить с содержимым ячейки Х). Если команда ADD читает из ячейки памяти раньше, чем первая команда STORE успела обновить ее содержимое, то к соответствующему регистру ЦП будет прибавлено неправильное значение. Команда j получила значение, которое является «слишком старым».

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

Помеха WAW существует, когда обе команды i и j пытаются обновить один и тот же объект, но i-е запоминание может наступить только после j-го. В результате после того, как обе команды завершены, в соответствующей ячейке может остаться промежуточное значение (от команды i), а не окончательное (от команды j). В нашем примере это может случиться между двумя последними командами STORE. Если вторая команда STORE завершается после третьей, то содержимое ячейки Х не будет таким, какое ожидает программист.

По симметрии является и четвертая возможность – чтение после чтения. Однако само по себе такое состояние не является помехой.

Более формальное и строгое определение помех можно найти в работе Келлера [61]. Его формулировки основаны на двух определениях.

Определение 6.1. Область определения команды i, обозначаемая D(i), - это множество всех объектов (регистров, ячеек памяти и флажков), содержимое которых влияет тем или иным способом на исполнение команды i.

Определение 6.2. Множество значений команды i, обозначаемое R(i), - это всех объектов (регистров, ячеек памяти и флажков), содержимое которых может быть изменено за счет исполнения команды i.

Таким образом, D(i) – это множество всех объектов, читаемых командой i, а R(i) – множество всех объектов, модифицируемых ею. Помня об этом, заметим, что возможность возникновения помехи между командой i и логически более поздней командой j имеет место тогда, когда удовлетворяется хотя бы одно из следующих условий*:

Условие 1 (RAW):

Условие 2 (WAR):

Условие 3 (WAW):

*Запись X∩Y означает пересечение множеств, т.е. элементы, общие для X и Y;