Межкомандные зависимости и помехи.

S440

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

При конвейеризации это уже не всегда имеет место. Исполнения команд перекрываются, так что некоторые операции, нужные для команд i+1. i+2, …, могут зависеть от результатов i-й команды, которая еще не была завершена.

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

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

 

 

S441

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

Имеются три класса таких помех:

чтение после записи (RAW);

запись после чтения (WAR);

запись после записи (WAW).

 

 

S442

Для демонстрации различий между помехами рассмотрим следующий фрагмент программы:

.

.

STORE X

.

.

.

ADD X

STORE X

.

.

.

STORE X

.

.

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

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

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

 

 

S443

Более формальное и строгое определение помех ввёл Келлер. Его формулировки основаны на двух определениях.

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

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

Возможность возникновения помехи между командой i и логически более поздней командой j имеет место тогда, когда удовлетворяется хотя бы одно из следующих условий*:

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

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

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

Запись X∩Y означает пересечение множеств, т.е. элементы, общие для X и Y. Ω означает пустое множество (не содержащее никаких элементов).

 

 

S444

То же показано на рисунках:

Помеха «чтение после записи».

 

S445

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

Описанная выше модель архитектуры может не полностью представлять реальные архитектуры (например, при ассортименте косвенных адресаций), но она достаточно представительна.

 

 

S445

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

Примеры:

а) команда STORE использует содержимое некоторого индексного регистра, вычисляемое предыдущей ADD; она способна порождать помеху RAW;

б) две последовательно выполняемых команды JUMP дают помеху WAW, поскольку обе изменяю содержимое СК;

в) команда BRANCH зависит от кода состояния или значений в регистре, выработанных предыдущей ADD; она не должна зависеть от кода состояния следующей команды => помеха WAR и т.д.

 

 

S446

Разработчик обязан «научить» конвейер фактически обнаруживать помехи и устранять так, чтобы CPU работало, как того от него ожидают.

Приемов много, но в конечном итоге все сводятся к одному из стандартных классов.

Два противоположных подхода к проблеме обнаружения помехи:

1) централизовать обнаружение помех на одной ступени (обычно выборки IFETCH) и сравнивать здесь область определения и множество значений команды с соответствующими областью определения и множеством значений для команд, уже находящихся в конвейере.

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

 

S447

Два подхода и к устранению помех:

1) просто «остановить конвейер», если найдена помеха: обнаружена команда j в состоянии помехи с ранее инициированной командой i; тогда останавливаются все инициации команд j, j+1, j+2, … до тех пор, пока команда i не пройдет через точку конфликта;

2) (сложнее!!) останавливается команда j, но следующим (j+1, j+2,…) разрешается двигаться по конвейеру; они обгоняют команду j, но на всех следующих ступенях для всех этих команд проверяется наличие помех не только с теми (до j), но и с j, и если здесь обнаруживается помеха, то выполнение этих команд откладывается до тех пор, пока «первая» исходная помеха для j не будет устранена и ей будет разрешено двигаться.

 

S448

«Ускорение устранения помех типа RAW».

Идет последовательность: …STORE, ADD, … Типичная помеха: ADD обращается к ячейке памяти, изменение содержимого которой осуществлялось STORE. Опасность! Помеха! Прямое решение: задержать ADD до окончания модификации со стороны STORE, а затем продолжать ADD.

Но есть быстрый способ, даже именуется «коротким замыканием»: копия данных, подлежащих запоминанию, передается прямо ADD! Это избавляет ADD от ожидания и затем выполнения еще одного чтения READ (хотя бы и внутри ADD):

 

S449

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

а) много фиксаторов на ступенях конвейеров;

б) фиксаторы надо научить запоминать (если данных нет) индексом или тегом (указателем) за вырабатывающую их ступень;

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

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