Тема_8_2010 Планирование работы конвейера (542608), страница 2
Текст из файла (страница 2)
Рассмотрим зависимость оператора4S1 от более ранней итерации S1. Эта зависимость (loop-carried dependence)означает, что между различными итерациями цикла существует зависимость поданным. Более того, поскольку оператор S1 зависит от самого себя,последовательные итерации оператора S1 должны выполняться упорядочено.Вторая зависимость (S2 зависит от S1) не передается от итерации к итерации.Таким образом, если бы это была единственная зависимость, несколько итерацийцикла могли бы выполняться параллельно, при условии, что каждая параоператоров в итерации поддерживается в заданном порядке.Имеется третий тип зависимостей по данным, который возникает в циклах, какпоказано в следующем примере.Рассмотрим цикл:for (i=1; i<=100; i=i+1){ A[i] = A[i] + B[i]; /* S1 */B[i+1] = C[i] + D[i]; /* S2 */}Оператор S1 использует значение, которое присваивается оператором S2 впредыдущей итерации, так что имеет место зависимость между S2 и S1 междуитерациями.Несмотря на эту зависимость, этот цикл может быть сделан параллельным.
Как и вболее раннем цикле эта зависимость не циклическая: ни один из операторов независит сам от себя и хотя S1 зависит от S2, S2 не зависит от S1. Цикл являетсяпараллельным, если только отсутствует циклическая зависимость.Хотя в вышеприведенном цикле отсутствуют циклические зависимости, чтобывыявить параллелизм, он должен быть преобразован в другую структуру. Здесьследует сделать два важных замечания:1. Зависимость от S1 к S2 отсутствует. Если бы она была, то в зависимостяхпоявился бы цикл и цикл не был бы параллельным. Вследствие отсутствиядругих зависимостей, перестановка двух операторов не будет влиять навыполнение оператора S2.2.
В первой итерации цикла оператор S1 зависит от значения B[1],вычисляемого перед началом цикла.Эти два замечания позволяют заменить выше приведенный цикл следующейпоследовательностью:A[1] = A[1] + B[1];for (i=1; i<=99; i=i+1) {B[i+1] = C[i] + D[i];A[i+1] = A[i+1] + B[i+1];}B[101] = C[100] + D[100];5Теперь итерации цикла могут выполняться с перекрытием, при условии, чтооператоры в каждой итерации выполняются в заданном порядке. Имеетсямножество такого рода преобразований, которые реструктурируют цикл длявыявления параллелизма.Более подробно рассмотрим метод выявления параллелизма уровня команд.Зависимости по данным в откомпилированных программах представляют собойограничения, которые оказывают влияние на то, какая степень параллелизма может бытьиспользована.
Вопрос заключается в том, чтобы подойти к этому пределу путемминимизации действительных конфликтов и связанных с ними приостановок конвейера.Методы ориентированы на использование всего доступного параллелизма приподдержании истинных зависимостей по данным в коде программы.Как компилятор, так и аппаратура здесь играют свою роль: компилятор стараетсяустранить или минимизировать зависимости, в то время как аппаратура стараетсяпредотвратить превращение зависимостей в приостановки конвейера.Основы планирования загрузки конвейера и разворачивание цикловДля поддержания максимальной загрузки конвейера должен использоватьсяпараллелизм уровня команд, основанный на выявлении последовательностейнесвязанных команд, которые могут выполняться в конвейере с совмещением.Чтобы избежать приостановки конвейера зависимая команда должна бытьотделена от исходной команды на расстояние в тактах, равное задержке конвейерадля этой исходной команды.Способность компилятора выполнять подобное планирование зависит как отстепени параллелизма уровня команд, доступного в программе, так и от задержкифункциональных устройств в конвейере.Будем рассматривать задержки (см.
рис.1), если явно не установлены другиезадержки.Предположим, что условные переходы имеют задержку в один такт, так чтокоманда следующая за командой перехода не может быть определена в течениеодного такта после команды условного перехода.Предположим, что функциональные устройства полностью конвейеризованыили дублированы (столько раз, какова глубина конвейера), так что операциялюбого типа может выдаваться для выполнения в каждом такте и структурныеконфликты отсутствуют.Команда,Команда, использующаявырабатывающаяЗадержка в тактахрезультатрезультатОперация АЛУ с ПТОперация АЛУ с ПТДругая операция АЛУ с ПТЗапись двойного слова32Загрузка двойного словаЗагрузка двойного словаДругая операция АЛУ с ПТЗапись двойного слова106Рис. 1Рассмотрим, каким образом компилятор может увеличить степень параллелизмауровня команд путем разворачивания циклов?Для иллюстрации этих методов используем простой цикл, которыйдобавляет скалярную величину к вектору в памяти:For i:=1 to n doA[i]:=A[i]+pОчевидно, что это параллельный цикл, поскольку зависимость междуитерациями цикла отсутствует.
Предположим, что первоначально в регистре R1находится адрес последнего элемента вектора (например, элемент с наибольшимадресом), а в регистре F2 - скалярная величина, которая должна добавляться ккаждому элементу вектора. Программа для машины, не рассчитанная наиспользование конвейера, будет выглядеть примерно так:Loop: LD F0,0(R1) ; F0=элемент вектораADDD F4,F0,F2 ; добавляет скаляр из F2SD 0(R1),F4 ; запись результатаSUBI R1,R1,#8 ; пересчитать указатель ;8 байт (в двойном слове)BNEZ R1, Loop ;переход R1!=нулюДля упрощения положим, что массив начинается с ячейки 0. Если бы он находилсяв любом другом месте, цикл потребовал бы наличия одной дополнительнойцелочисленной команды для выполнения сравнения с регистром R1.Рассмотрим работу этого цикла при выполнении на простом конвейере сзадержками, определенными на рис.
1.Если не делать никакого планирования, работа цикла будет выглядеть следующимобразом:Такт выдачиLoop: LD F0,0(R1)приостановкаADDD F4,F0,F2приостановкаприостановкаSD 0(R1),F4SUBI R1,R1,#8BNEZ R1,Loopприостановка1234567897Для его выполнения потребуется 9 тактов на итерацию: одна приостановка длякоманды LD, две для команды ADDD, и одна для задержанного перехода. Можноспланировать цикл так иначе, чтобы получить меньшее время для выполнения:Loop: LD F0,0(R1)1приостановка2ADDD F4,F0,F23SUBI R1,R1,#84BNEZ R1,Loop ;задержанный переход 5SD 8(R1),F4 ;команда изменяется, когда 6;меняется местами с командой SUB1Время выполнения уменьшилось с 9 до 6 тактов.Заметим, что для планирования задержанного перехода компилятор долженопределить, что он может поменять местами команды SUB1 и SD путем измененияадреса в команде записи SD: Адрес был равен 0(R1), а теперь равен 8(R1). Это нетривиальная задача, поскольку большинство компиляторов будут видеть, чтокоманда SD зависит от SUB1, и откажутся от такой перестановки мест.
Болееизощренный компилятор смог бы рассчитать отношения и выполнитьперестановку. Цепочка зависимостей от команды LD к команде ADDD и далее ккоманде SD определяет количество тактов, необходимое для данного цикла.В вышеприведенном примере мы завершаем одну итерацию цикла ивыполняем запись одного элемента вектора каждые 6 тактов, но действительнаяработа по обработке элемента вектора отнимает только 3 из этих 6 тактов(загрузка, сложение и запись). Оставшиеся 3 такта составляют накладные расходына выполнение цикла (команды SUB1, BNEZ и приостановка).
Чтобы устранитьэти три такта, нам нужно иметь больше операций в цикле относительно числакоманд, связанных с накладными расходами.Одним из наиболее простых методов увеличения числа команд поотношению к команде условного перехода и команд, связанных с накладнымирасходами, является разворачивание цикла.
Такое разворачивание выполняетсяпутем многократной репликации (повторения) тела цикла и коррекциисоответствующего кода конца цикла.Разворачивание циклов может также использоваться для улучшенияпланирования. В этом случае, мы можем устранить приостановку, связанную сзадержкой команды загрузки путем создания дополнительных независимых командв теле цикла. Затем компилятор может планировать эти команды для помещения вслот задержки команды загрузки. Если при разворачивании цикла мы простореплицируем команды, то результирующие зависимости по именам могутпомешать эффективно спланировать цикл.
Таким образом, для разных итерацийхотелось бы использовать различные регистры, что увеличивает требуемоечисло регистров.Представим теперь этот цикл развернутым так, что имеется четыре копии телацикла, предполагая, что R1 первоначально кратен 4. Устраним при этом любые8очевидные излишние вычисления и не будем пользоваться повторно никакимирегистрами.Ниже приведен результат, полученный путем слияния команд SUB1 ивыбрасывания ненужных операций BNEZ, которые дублируются приразворачивании цикла.Loop: LD F0,0(R1) (2 такта)ADDD F4,F0,F2 (3 такта)SD 0(R1),F4 ;выбрасывается SUB1 и BNEZLD F6,-8(R1) (2 такта)ADDD F8,F6,F2 (3 такта)SD -8(R1),F8 ;выбрасывается SUB1 и BNEZLD F10,-16(R1) (2 такта)ADDD F12,F10,F2 (3 такта)SD -16(R1),F12 ;выбрасывается SUB1 и BNEZLD F14,-24(R1) (2 такта)ADDD F16,F14,F2 (3 такта)SD -24(R1),F16SUB1 R1,R1,#32BNEZ R1, Loop (2 такта)Мы ликвидировали три условных перехода и три операциидекрементирования R1.Адреса команд загрузки и записи были скорректированы так, чтобы позволитьслить команды SUB1 в одну команду по регистру R1.
При отсутствиипланирования за каждой командой здесь следует зависимая команда и это будетприводить к приостановкам конвейера. Этот цикл будет выполняться за 27 тактов(на каждую команду LD потребуется 2 такта, на каждую команду ADDD - 3, наусловный переход - 2 и на все другие команды 1 такт) или по 6.8 такта на каждыйиз четырех элементов. Хотя эта развернутая версия в такой редакции медленнее,чем оптимизированная версия исходного цикла, после оптимизации самогоразвернутого цикла ситуация изменится. Обычно разворачивание цикловвыполняется на более ранних стадиях процесса компиляции, так что избыточныевычисления могут быть выявлены и устранены оптимизатором.Если аналогично вышеприведенному примеру рассмотреть пример цикла длясуммирования двух векторов, то накладные расходы на организацию цикласоставят около ½ времени выполнения. Кроме того команды тела цикла зависят поуправлению от команд управления циклом.
Одним из наиболее простых методовувеличения числа команд по отношению к командам, связанным с накладнымирасходами, и является разворачивание цикла (многократное повторение операторови соответствующая коррекция завершения).В реальных программах мы обычно не знаем верхней границы цикла.Предположим, что она равна n и мы разворачиваем цикл так, чтобы иметь k копийтела цикла.
Тогда, вместо единственного развернутого цикла мы генерируем паруциклов. Первый из них выполняется (n mod k) раз и имеет тело первоначального9цикла. Развернутая версия цикла окружается внешним циклом, которыйвыполняется (n div k) раз.В вышеприведенном примере разворачивание цикла увеличиваетпроизводительность этого цикла путем устранения команд, связанных снакладными расходами цикла, хотя при этом заметно увеличивается размерпрограммного кода.Насколько увеличится производительность, если цикл оптимизировать?Ниже представлен развернутый цикл из предыдущего примера после оптимизации.Loop: LD F0,0(R1)LD F6,-8(R1)LD F10,-16(R1)LD F14,-24(R1)ADDD F4,F0,F2ADDD F8,F6,F2ADDD F12,F10,F2ADDD F16,F14,F2SD 0(R1),F4SD -8(R1),F8SD -16(R1),F12SUB1 R1,R1,#32BNEZ R1, LoopSD 8(R1),F16 ; 8 - 32 = -24Время выполнения развернутого цикла снизилось до 14 тактов или до 3.5 тактовна элемент, по сравнению с 6.8 тактов на элемент до оптимизации, и посравнению с 6 тактами при оптимизации без разворачивания цикла.Выигрыш от оптимизации развернутого цикла даже больше, чем отоптимизации первоначального цикла! Это произошло потому, чторазворачивание цикла выявило больше вычислений, которые могут бытьоптимизированы для минимизации приостановок конвейера (приведенный вышепрограммный код выполняется без приостановок).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
