При генерации кода для кластерных архитектур возникает проблема минимизации обмена данных между регистровыми файлами разных кластеров. Решение этой проблемы предлагается в [54], где планирование совмещается с назначением кластеров. Аналогичный подход используется в [43].
Глобальное планирование
Преимущество глобального планирования заключается в том, что оно применяется к более крупным фрагментам программы, состоящим из нескольких линейным участкам. В результате появляется возможность более эффективного использования аппаратных средств параллельного исполнения. Для того чтобы это преимущество реально работало, необходимо уметь перемещать команды вокруг точек ветвления. Рассмотрим более подробно соответствующие проблемы и решения.
Перенос команды ниже точки ветвления является частным случаем миграции команд, которая описана выше в разд. 6.2. Более интересен случай переноса команды выше предшествующей точки ветвления. Этот вид переноса может быть полезен по двум причинам:
в предшествующем линейном участке, возможно, имеется свободная позиция в одном из командных слов, куда можно поместить рассматриваемую команду;
если команда имеет задержку (т.е. ее результат можно использовать только по истечению некоторого числа тактов), то выгодно запланировать ее выполнение как можно раньше, в особенности, если она находится на критическом пути.
Перенос команд выше точки ветвления можно назвать упреждающим выполнением (в англоязычной литературе используется термин speculative execution или control speculation), поскольку команда выполняются раньше, чем становится известно, будет ли передано управление в участок, где она изначально находилась.
Рассмотрим ограничения, которые должны соблюдаться при переносе команд выше точки ветвления, на примере (рис. 13).
Рис. 13. Перенос команды C выше точки ветвления B
Перенос команды C выше точки ветвления B (в участок ЛУ1) возможен при соблюдении двух ограничений (см. [30], [35], [48]):
Ограничение 1. Прежнее значение регистра, в который C записывает свой результат, не требуется больше ни одной команде в ЛУ1 или в других участках, куда может быть передано управление из ЛУ1.
Ограничение 2. Команда C не может вызвать прерывание, которое приведет к завершению программы.
Некорректность переноса команды при несоблюдении второго ограничения можно проиллюстрировать на простом примере рис. 14.
Рис. 14. Перенос команды "C=A/B" выше команды ветвления некорректен, так как это приведет к аварийному завершению программы при B=0
Планирование с соблюдением обоих ограничений называют "ограниченной фильтрацией" (restricted percolation). При соблюдении обоих ограничений число команд, перенос которых реально возможен, оказывается невелико, что значительно снижает эффективность глобального планирования. Поэтому важное значение имеют методы, позволяющие снять эти ограничения.
Ограничение 1 можно снять путем переименования регистров - для значения, которое вычисляется в команде C, назначается другой регистр.
Для снятия ограничения 2 необходимы средства аппаратной поддержки, описанные в следующем разделе.
Аппаратная поддержка глобального планирования
Упреждающее выполнение применяется как в динамическом (аппаратном) планировании в суперскалярных процессорах с неупорядоченной выдачей команд, так и в статическом планировании во время компиляции. Здесь будут рассмотрены характерные для EPIC-архитектур аппаратные расширения, которые позволяют планировать упреждающее выполнение команд во время компиляции. Существуют две модели поддержки упреждающего выполнения - модель неограниченной фильтрации (general percolation, см. [35]) и модель защищенного планирования (sentinel scheduling, см. [48]).
Первая модель предполагает наличие в аппаратуре непрерываемых версий всех команд. Если планировщик переносит команду выше точки ветвления, то он использует ее непрерываемую версию. Упреждающее выполнение записей в память не допускается. Исключительные ситуации, если они возникают, игнорируются. Получаемые при этом неправильные результаты могут сказаться на дальнейшем выполнении, например, привести позднее к прерываниям или просто к неверным результатам.
Вторая модель обеспечивает корректность статического планирования с применением упреждающего выполнения и включает следующие аппаратные расширения:
1. В кодировку команд добавляется бит упреждающего выполнения. Если он установлен, то говорят, что команда выполняется в режиме упреждающего выполнения, в котором прерывания не выдаются. Если возникает исключительная ситуация, то в регистре результата устанавливается бит прерывания. То же происходит, если бит прерывания установлен хотя бы в одном из регистров-операндов. При выполнении команд в обычном режиме должны выдаваться прерывания, если хотя бы один из входных регистров имеет установленный бит прерывания (или если исключительная ситуация возникла при выполнении самой команды).
2. К каждому регистру добавляется бит прерывания, который устанавливается при выполнении команд в режиме упреждающего выполнения, если возникает исключительная ситуация, и может быть опрошен при помощи специальной команды check_exception(R). С каждым регистром связывается также поле диагностики, в которое заносится программный адрес возникновения исключительной ситуации. Бит прерывания вместе с полем данных должны сохраняться и восстанавливаться при временном сохранении регистра в памяти.
3. К системе команд добавляется команда для опроса бита прерывания заданного регистра check_exception(R). Если бит установлен, то возникает прерывание.
При наличии перечисленных средств компилятор получает возможность закодировать упреждающее выполнение команды C следующим образом:
в новой позиции команды C (выше точки ветвления) помещается ее вариант с битом упреждающего выполнения;
в прежней позиции команды C помещается команда check_exception, для того чтобы обеспечить прерывание, если оно должно произойти. Если имеется команда, выполняемая в обычном режиме и использующая результат команды C, то команда check_exception не генерируется.
Пример из [48], показанный на рис. 15, демонстрирует применение указанных средств при планировании.
| A: if (r2==0) goto L1 | *B: r1 = mem(r2) |
| B: r1 = mem(r2) | *C: r3 = mem(r4) |
| C: r3 = mem(r4) | *D: r4 = r1+1 |
| D: r4 = r1+1 | *E: r5 = r3*9 |
| E: r5 = r3*9 | A: if (r2==0) goto L1 |
| F: mem(r2+4) = r4 | F: mem(r2+4) = r4 |
| G: check_exception(r5) | |
| a) | b) |
Рис. 15. Планирование команд с упреждающим выполнением: a) исходный код; b) код, полученный в результате планирования. Буквы A-G служат для идентификации команд. Символом * отмечены команды с признаком упреждающего выполнения
На рис. 15 показан код до и после планирования (в предположении, что исключительные ситуации возможны только при обращениях к памяти). Команды F и G обеспечивают проверку исключительных ситуаций, которые могли возникнуть при упреждающем выполнении команд B, C.
Для того чтобы разрешить упреждающее выполнение команд записи в память, предусматривается аппаратное расширение, основанное на введении дополнительных полей в элементы буфера записи в память.
Важным преимуществом модели защищенного планирования является поддержка адекватной диагностики исключительных ситуаций с указанием адреса фактического возникновения, даже если команда-источник выполнялась в упреждающем режиме.
По результатам тестов, приведенным в [48], применение защищенного планирования по сравнению с ограниченной фильтрацией на задачах нечисловой обработки дает существенное ускорение результирующих программ. Например, для процессора с темпом выдачи 8 команд на такт коэффициент ускорения при использовании защищенного планирования был от 18 до 135% (в среднем на 57%) выше, чем при планировании с ограниченной фильтрацией.
Для численных приложений, не содержащих большого числа условных переходов во внутренних циклах (таких как операции над матрицами), разница коэффициентов ускорения оказалась незначительной. Коэффициенты ускорения для этих приложений оказались достаточно высокими уже при ограниченной фильтрации. Для двух численных приложений с значительным количеством условных переходов во внутренних циклах улучшение коэффициента ускорения составило 36-38%.
Другое аппаратное расширение, предназначенное для поддержки глобального планирования - средства условного выполнения команд ([15], [58]). Например, процессор TM1000 [32] позволяет задавать в команде предикатный операнд, в качестве которого может выступать любой из 128 регистров. В зависимости от значения младшего бита этого операнда результат операции будет записан или проигнорирован. Аналогичные возможности поддерживаются в процессоре IA-64 ([36], [60]) и др.
Компилятор может слить условно выполняемый линейный участок с объемлющим участком, заменив составляющие его инструкции условно выполняемыми (рис. 16). В результате зависимости по управлению фактически заменяются зависимостями по данным, которые существенно удобнее с точки зрения планировщика.
c:= вычислить(условие) c:= вычислить(условие) [c] goto then_label [c] B_THEN
B_ELSE [!c] B_ELSE
goto join_label
then_label: B_THEN
join_label: ...
a) b)
Рис. 16. Реализация конструкции "if (условие) then B_THEN else B_ELSE" при помощи условных переходов (a) и условным выполнением (b). Обозначение [c] указывает, что команда будет выполнена только если предикат c имеет значение "истина"