Hardware - разное

       

ПРОГРАММНО КОНВЕЙЕРИЗОВАННЫЕ ЦИКЛЫ


Cовременные оптимизирующие компиляторы суперскалярных RISC-процессоров активно используют технику SWP ([4]). Аппаратная поддержка SWP в IA-64 имеет принципиальное значение для увеличения производительности и эффективности использования оперативной памяти.

SWP-циклы аналогичны обычным аппаратным конвейерам. В таком цикле также имеется три фазы. В фазе заполнения конвейера (пролог) новая итерация цикла запускается на выполнение на каждой стадии. В фазе ядра на каждой стадии запускается одна итерация, и одна итерация завершается (конвейер заполнен). В фазе эпилога новых итераций не запускается, а завершается выполнение ранее запущенных итераций (см. Пример 3).

Пример 3.

Фрагмент программы в фортрановском представлении: DO I=1,N IND(I)=JND(I)+K ENDDO

в ассемблерном: Lbl:ld8 r8=[r5],8;; //Загрузка JND(I) add r9=r8,r7;; //r9=r8+r7 st8 [r6]=r9,8 //Запись IND(I) br.cloop Lbl;; //Переход по счетчику SWP-аналог: mov lc=99 //Установка LC mov ec=4 //Установка EC mov pr.rot=1<<16 //Установка PR Lbl: (p16) ld8 r32=[r5],8;; //Загрузка JND(I) (p18) add r35=r34,r7;; //r35=r34+r7 (p19) st8 [r6]=r36,8 //Запись IND(I) br.ctop Lbl;;

Число тактов T между запуском последовательных итераций цикла называется интервалом инициации. Мы рассмотрим только случай постоянного числа тактов. В простейшем случае T равно 1, очередная итерация цикла может запускаться на каждом такте.

Каждой стадии цикла должен быть выделен PR-регистр из области вращения, определяющий, следует ли выполнять команды данной стадии. В простейшем случае стадия цикла включает одну команду. При использовании раскрутки (unrolling) циклов, которую часто необходимо применять для эффективного использования ресурсов процессора, каждая стадия включает несколько однотипных команд (скажем, для четных и нечетных итераций - при двухкратной раскрутке). В этом случае для каждой команды стадии кодируется один и тот же PR-регистр.

Пример 4.

Фрагмент программы в фортрановском представлении: DO I=1,N S=S+A(I)*B(I) ENDDO

SWP-аналог: Lbl: (p16) ldfd f50=[r5],8 //Загрузка A(I) (p16) ldfd f60=[r6],8 //Загрузка B(I) (p25) fma f41=f59,f69,f46 //f41=f59*f69+f46 br.ctop.sptk Lbl;; fadd f7=f42,f43 //Частичная сумма 1 fadd f8=f44,f45;; //Частичная сумма 2 fadd f9=f7,f8;; //Их сумма fadd f10=f9,f46 //Окончательная сумма


SWP поддерживается как для исходных циклов со счетчиком, использующих команду br.cloop, так и для циклов while. Для циклов со счетчиком на первой стадии цикла должен применяться PR16, а для циклов while - любой PR-регистр из области вращения. Предикаты последующих стадий должны иметь более высокие номера PR. Инициализация предикативных стадий возложена на программиста.

Как мы увидим, применение PR-регистров, вращаемых регистров GR и FR и специальных SWP-команд перехода позволяет не увеличивать размер кода SWP-цикла, что характерно для оптимизации циклов в RISC-процессорах. Вращение на одну регистрную позицию вышеупомянутых регистров осуществляется аппаратно при выполнении SWP-команды перехода (br.ctop - для циклов со счетчиком при расположении команды перехода в конце тела цикла).



Таблица 2. Прокрутка SWP-цикла (Пример 3(в)) по тактам

Номер такта Команды и порты Значения регистров перед br.ctop
M I M B p16 p17 p18 p19 LC EC
1 ld8     br.ctop 1 0 0 0 99 4
2 ld8     br.ctop 1 1 0 0 98 4
3 ld8 add   br.ctop 1 1 1 0 97 4
4 ld8 add st8 br.ctop 1 1 1 1 96 4
... ... ... ... ... ... ... ... ... ... ...
99 ld8 add st8 br.ctop 1 1 1 1 0 4
100   add st8 br.ctop 0 1 1 1 0 3
101   add st8 br.ctop 0 0 1 1 0 2
102     st8 br.ctop 0 0 0 1 0 1
...         0 0 0 0 0 0
При выполнении такой команды вращение регистров осуществляется путем их переименования благодаря уменьшению на 1 базовых значений в CFM - соответственно полей CFM.rrb.gr, CFM.rrb.fr и CFM.rrb.pr. Вообще изменение полей rrb, приводящее к переименованию регистров, происходит при выполнении команд очистки rrb (clrrrb, clrrrb.pr) и переходов типа вызова процедур/возврата (br.call/br.ret) и SWP-переходов, в том числе br.ctop. Файлы вращаемых регистров с точки зрения их переименования зациклены: регистр с максимальным номером после вращения переходит в регистр с минимальным номером из области вращения.


Так, PR63 после вращения становится PR16.

Рассмотрим теперь, как организовывается работа SWP-цикла со счетчиком. При этом используется регистр LC, в который помещается значение N-1 (N - число итераций цикла), и регистр ЕС, куда надо поместить число стадий в теле цикла. Пока LC больше 0, br.ctop продолжает выполнение цикла, уменьшая LC на 1 и вращая регистры на 1 путем уменьшения rrb. Команда br.ctop, принявшая решение о продолжении цикла, устанавливает в 1 регистр PR63, который после вращения становится PR16.

Когда LC становится равным 0, начинается фаза эпилога. В ней br.ctop будет продолжать цикл, уменьшая EC на 1 - до тех пор, пока EC не обнулится. Тогда br.ctop завершит цикл, передав управление на следующую команду.

Проиллюстрируем сказанное выше на конкретном примере SWP-цикла (в примере 3 мы незначительно модернизировали соответствующий пример из [1]).

Предположим, что все целые величины - 64-разрядные.

Предполагается, что в регистре GR5 лежит адрес начала массива IND, а в GR6 - адрес начала JND; K загружена в GR7. Первая команда ld8 загружает 8 байт из адреса, указанного в GR5, в GR8. В конце ее выполнения к GR5 прибавляется 8. Команда add складывает GR8 и GR7, помещая результат в GR9. Команда st8 записывает содержимое этого регистра в память, адрес которой находится в GR6, и в конце выполнения увеличивает его на 8.

В [1] соответствующий пример относится к 32-разрядным целым и предполагается, что команда ld4 занимает два такта. Это типично для микропроцессоров, и мы предполагаем, что ld8 также занимает два такта. Можно предположить, что в теле цикла (без br.cloop) остальные команды занимают один такт, тогда это тело состоит из четырех стадий, вторая из которых - пустая (ожидание завершения ld8 на втором такте).

Вследствие наличия большого числа ФИУ и соответствующих портов, команды цикла, представленные в примере 3, могли бы в принципе выполняться одновременно, если бы они работали с разными регистрами (т.е. не было бы взаимозависимости). Это хорошо видно из табл. 2, в которой нетрудно разглядеть аналогии с заполнением аппаратных конвейеров.



На тактах 1-3 происходит заполнение конвейера (пролог), такты 4-5 относятся к фазе ядра, такты 6- 8 отвечают эпилогу. Если бы не было взаимозависимости, команды ld8, add и st8 могли бы работать параллельно в фазе ядра (предполагается, что имеется два порта памяти). Скажем, когда add начинает работу, ld8 могла бы начать новую загрузку, но уже в другой GR-регистр. В суперскалярных RISC-процессорах для достижения подобных целей приходится создавать отдельные коды для пролога и эпилога, раскручивать циклы, что приводит к увеличению длины кода.

В IA-64 эти проблемы решены элегантно и эффективно. Нет необходимости вручную заниматься переименованием регистров, чтобы избавиться от взаимозависимости - для этого есть вращение регистров. Не нужно писать пролог и эпилог - все автоматизировано за счет применения PR-регистров и SWP-команд.

SWP-аналог примера 3 использует команду br.ctop. Соответственно первой стадии (команда ld8) выделяется PR16, второй (add) - PR18, четвертой (st8) - PR19. Вместо статических GR7-9 мы будем использовать вращаемые регистры, начиная с GR32. Перед началом выполнения цикла в LC загружается значение N-1 (99), а в EC - 4 (на 1 больше числа стадий эпилога). Кроме того, нужно установить вращаемые PR-регистры, что делается сразу для всех предикативных регистров командой mov pr.rot.

Вследствие вращения регистров величина JND(I), загружаемая в GR32, двумя тактами позднее (по завершению ld8) уже оказывается в GR34. Аналогично, IND(I)+K, помещаемая в GR35, по завершению команды add (один такт) окажется в GR36. Эти "измененные" номера регистров должны кодироваться в программе.

Приведем, наконец, завершающий пример - цикл, рассчитывающий скалярное произведение векторов [1]. В примере 4 адреса начал A и B лежат в GR5 и GR6; предполагается, что ldfd используют два порта памяти, а времена выполнения ldfd и fma составляют 9 и 5 тактов соответственно (в [1] предполагается 9 тактов на ldfs). В команде br.ctop.sptk последняя компонента мнемокода - статическая "подсказка": статическое предсказание, что переход будет осуществлен.



В цикле вычисляются пять частичных сумм: A(1)*B(1)+A(6)*B(6)+..., A(2)*B(2)+ A(7)*B(7)+..., ..., A(5)*B(5)+A(10)*B(10)+... , и все эти суммирования идут с шагом 5. В этом можно убедиться, если прокрутить вручную первые итерации цикла и учесть, что каждый раз при br.ctop происходит переименование регистров FR (как и PR). Поэтому A(I) попадает в f50 при ldfd, и девять итераций (девять тактов) спустя будет в f59, а B(I) из f60 окажется в f69, и т.д.

В примере 4 опущено обнуление регистров частичных сумм и другие подобные "мелочи" (до начала цикла). По завершению цикла пять частичных сумм складываются, и результирующая сумма S оказывается в f10. Если проанализировать этот исходно простой пример, отследив, почему используются те или иные номера регистров, то станет ясно, что SWP-оптимизация требует от программиста большой тщательности и знания времен выполнения команд. Более того, такая привязка означает, что если в процессорах IA-64 нового поколения изменятся времена выполнения команд (например, при переходе от Merced к McKinley), то оптимизированную программу для достижения высокой производительности необходимо переделать. Однако компактность и эффективность оптимизированных кодов несомненны.

IA-64 в первом приближении

Некоторые приведенные в статье данные о времени выполнения команд (ldfd/ldfs, fma), основанные на примерах в [1], могут оказаться иными в конкретной реализации Itanium. Однако если предположить, что оценки эти окажутся близкими к реальности, становится понятным высказывавшееся мнение о том, что Itanium будет эффективно работать с векторизуемыми кодами. Действительно, в этом случае большие задержки команд типа ldfs или fma будут исключены благодаря использованию SWP.

В рамках одной журнальной статьи трудно дать полное введение в такую сложную архитектуру, как IA-64. Автор же постарался представить наиболее важные отличительные особенности IA-64.


Содержание раздела