Современные высокопроизводительные компьютеры


Аппаратные средства поддержки большой степени распараллеливания - часть 5


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

for (p=head; p <> nil; *p=*p.next) {

*p.value = *p.value+1;

}

Подобно циклам for, с которыми мы встречались в более ранних разделах, разворачивание этого цикла не увеличит степени доступного параллелизма уровня команд. Действительно, каждая развернутая итерация будет содержать оператор if и выход из цикла. Ниже приведена последовательность команд в предположении, что значение head находится в регистре R4, который используется для хранения p, и что каждый элемент списка состоит из поля значения и следующего за ним поля указателя. Проверка размещается внизу так, что на каждой итерации цикла выполняется только один переход.

J looptest

start: LW R5,0(R4)

ADDI R5,R5,#1

SW 0(R4),R5

LW R4,4(R4)

looptest: BNEZ R4,start

Развернув цикл однажды можно видеть, что разворачивание в данном случае не помогает:

J looptest

start: LW R5,0(R4)

ADDI R5,R5,#1

SW 0(R4),R5

LW R4,4(R4)

BNEZ R4,end

LW R5,0(R4)

ADDI R5,R5,#1

SW 0(R4),R5

LW R4,4(R4)

looptest: BNEZ R4,start

end:

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

  • Первая команда в итерации цикла (LW R5,0(R4)) зависит по управлению от обоих условных переходов. Таким образом, команда не может выполняться успешно (и безопасно) до тех пор, пока мы не узнаем исходы команд перехода.

  • Вторая и третья команды в итерации цикла зависят по данным от первой команды цикла.

  • Четвертая команда в каждой итерации цикла (LW R4,4(R4)) зависит по управлению от обоих переходов и антизависит от непосредственно предшествующей ей команды SW.




    Начало  Назад  Вперед



    Книжный магазин