Оптимизация программ под архитектуру CONVEX C

М. П. Крутиков



Введение

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

Первое с чего следует начать, это вопрос: а стоит ли тратить усилия на оптимизацию и чего этим можно достичь? Дело в том, что чем сильнее вы будете адаптировать вашу программу к заданной архитектуре, тем, с одной стороны, вы достигнете лучших результатов, а, с другой стороны, ваша программа не будет хорошо работать на других платформах. Более того, ``глубокая'' оптимизация может потребовать значительных усилий. Все это требует от пользователя точного понимания чего он хочет добиться и какой ценой.

Следующие архитектурные возможности могут использоваться при оптимизации:

Программное обеспечение CONVEX включает оптимизирующие компиляторы с языков C и FORTRAN а также набор оптимизированных на ассемблерном уровне математических библиотек.

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

Конечно, к приведенной классификации следует относиться творчески и понимать, что никто не мешает вам комбинировать приведенные методы для достижения наилучшего результата.

Наконец, перечислим возможные уровни оптимизации программы и соответствующие этим уровням ключи командной строки компиляторов (компиляторы C и FORTRAN имеют одинаковые опции оптимизации). Каждый последующий уровень оптимизации включает в себя предыдущий.

Вместе с ключом -O3 полезно использовать ключ -ep, позволяющий явно указать число процессоров, например ключи в команде

% fc -O3 -ep 4 -o setka setka.f

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

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

1 Цикл оптимизации

Цикл разработки и оптимизации расчетной программы должен быть таким

2 Это важно знать

Основные принципы векторной и параллельной оптимизации сводятся к следующему:

Векторизации подлежат циклы

Циклы являются единственным объектом векторной и параллельной оптимизации. Если в вашей программе нет циклов, то и не имеет смысла давать ключи оптимизации выше -O1. Когда компилятор встречает цикл, он пытается определить не представляет ли цикл какой-либо векторной операции. Если да, то компилятор преобразует цикл, выделяя из него векторную часть. Обработанный таким образом цикл рассматривается далее как кандидат на параллелизацию.

Что считается векторным циклом

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

Циклы длиной 128 это хорошо

Длина каждого векторного регистра данных процессора - 128 чисел по 64 бит в каждом. Векторная операция производит то или иное действие сразу над всем вектором (поэлементно). Поэтому идеальным для компилятора является цикл длиной 128 или кратный этому числу. Цикл длиной 129 плох, поскольку при оптимизации он будет разбит на два цикла: первый - длиной 128, а второй - длиной 1. Каждый из подциклов будет заменен соответствующей векторной операцией (если, конечно, таковая существует) На вычисление двух таких циклов уйдет точно столько же времени, как и на обработку двух подциклов по 128 элементов в каждом. Вывод: старайтесь иметь критические циклы длиной кратной 128.

Меньше 5 это плохо

Каждая векторная операция занимает в 2-5 раз больше времени, чем соответствующая скалярная. Поэтому эффективность векторизации падает при уменьшении размера вектора. И, если ваша задача оперирует с векторами длины 5 или менее, положительного результата от векторизации ждать не приходится. Постарайтесь переформулировать задачу таким образом, чтобы размер векторов был как можно ближе к 128. Автоматические средства оптимизации не будут рассматривать циклы длиной 4 и менее как кандидитуры для векторизации.

Параллельность задачи благое пожелание операционной системе

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

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

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

Вообще говоря, не очень вредно оптимизировать задачу на большее число процессоров, чем имеется в системе. Все, что вы теряете - это небольшие накладные расходы на создание лишних параллельных ветвей. Зато такую задачу можно будет запустить и в более многопроцессорной системе. Так, в кластере компьютеров CONVEX имеется два мощных компьютера серии C-3: C-3820, имеющий два процессора, и C-3440 с четырьмя CPU. При параллельной оптимизации рекомендуем пользователям задавать число процессоров равным четырем (даже для тех задач, которые компилируются на C-3820). При запуске задачи в пакетном режиме она может быть отправлена на выполнение на C-3440, где это и пригодится.

3 Архитектура векторного процессора серии C CONVEX

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

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

PSW слово состояния процессора. Изменяется при операциях сравнения. Используется в условных операциях с регистрами данных.

PC указатель на текущую инструкцию в сегменте кода программы.

A0-A7 восемь адресных регистров. Каждый регистр имеет длину 32 бита. Используются при обмене с оперативной памятью.

S0S7 восемь регистров данных. Длиной 64 бита каждый. Эти регистры называют скалярными (по контрасту с векторными регистрами данных)

Наиболее интересными для нас являются регистры данных. Именно здесь и происходят все вычисления. Рассмотрим, например, как происходит операция сложения двух целых чисел: A=B+C. Каждой из переменных A, B, и C в вашей программе выделена определенная область памяти (где хранятся их значения). Когда скомпилирована и запущена программа с указанной строчкой сложением B и С, процессор

Все это вместе в ассемблерных мнемонических обозначениях выглядит так:
ld.w B,s0
ld.w C,s1
add.w s0,s1,s2
st.w s2,A
Совершенно аналогично производятся другие арифметические операции. Кроме арифметических операций процессор имеет довольно много ``странных'', но очень полезных операций типа побитовых логических операций. Также имеются операции сравнения и условные операции.

Теперь мы подошли к изучению векторной части процессора. Кроме указанных выше регистров, в процессоре имеются:

V0-V7 восемь векторных регистров данных. Каждый регист представляет собой 128элементный вектор, где элементом выступает 64битный скаляр. Векторные операции оперируют с векторными регистрами данных и действуют поэлементно. Например, в результате одной операции векторного сложения получим сразу 128 чисел.

VL регистр длины вектора. Содержит число от 1 до 128, представляющее длину векторов в данной операции.

VS векторный шаг (vector stride). Регистр используется при загрузке и сохранении в памяти содержимого векторных регистров. Имеет смысл расстояния (в байтах) между ячейками памяти, содержащими соседние элементы вектора.

VM маска вектора. Регистр имеет длину 128 бит, при этом каждому элементу векторного регистра соответствует свой бит. Регистр используется в операциях векторного сравнения и маскированных векторных операций (см. ниже)

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

Посмотрим как работают векторные операции на примере сложения двух векторов. Пусть A, B, и C целочисленные вектора (по 100 элементов в каждом), пусть требуется вычислить A=B+C. Для этого процессор совершит следующие действия:

Все вместе будет выглядеть таким образом:
ld.w #100,vl
ld.w #4,vs
ld.w B,v0
ld.w C,v1
add.w v0,v1,v2
st.w v2,A
Этот фрагмент очень похож на ассемблерный код, реализующий скалярную операцию сложения. Только в данном случае арифметическое действие производится одновременно над массивом из 100 элементов.

Большое значение для понимания векторных возможностей процессора имеет список векторных операций.

Арифметические операции

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

Логические побитовые векторные операции

К логическим побитовым операциям относятся: побитовое отрицание, сложение (XOR), операция AND, и OR.

Смешанные арифметические операции

Набор смешанных операций позволяет производить векторные операции между вектором и скаляром. Такая операция понимается как бинарная операция между каждым элементом вектора и скаляром.

К смешанным операциям относятся операции копирования скалярного регистра в векторный (вектор заполняется одинаковыми значениями), арифметические операции, и логические побитовые операции.

Векторное сравнение

Операция векторного сравнения понимается как поэлементное сравнение двух векторов. Результатом является вектор булевских значений длиной 128, который заносится в регистр маски VM (имеющий 128 бит: 1-true, 0-false).

Имеется смешанный вариант сравнения: сравнивается векторный регистр и скалярный регистр, результатом является значение регистра маски VM.

Операции векторного сравнения обычно используются в комбинации с маскированными векторными операциами.

Векторная редукция

Операции векторной редукции имеют ``на входе'' вектор, а ``на выходе'' - скаляр. В этих операциях проявляется архитектурно заложенная тесная связь векторного регистра с соответствующим по номеру скалярным регистром. Получаемый при обработке вектора скалярный результат заносится в ``соответствующий'' скалярный регистр.

К ним относятся следующие операции:

Операции редукции помогают векторизовать такие ``невекторные'' по природе операции, как нахождение максимума/минимума.

Векторные маскированные операции

Большинство из выше перечисленных операций могут выполняться в режиме маскирования. При этом, в операции участвуют лишь те элементы, у которых соответствующий бит в регистре маски VM имеет указанное значение. Например, маскированная арифметическая операция сложения add.t v2,v1,v0 будет вычислять сумму только тех элементов в векторах, у которых значение соответствующего бита маски установленов 1 (true). Прочие элементы векторных регистров не участвуют в операции и их значение не меняется.

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

     DO 1 I=1,100                        for(i=0;i? 100;i++)
     IF(A(I).EQ.B(I)) A(I)=0;              if(a[i]==b[i]) a[i]=0;
1    CONTINUE
Может быть представлено следующим набором инструкций:
ld.w #100,vl
ld.w #4,vs
ld.w B,v0
ld.w A,v1
eq.w v1,v0
ld.w.t #0,v1
st.w v1,A
после операции сравнения eq.w v1,v0 изменяется содержимое регистра маски: для элементов вектора, для которых выполнено условие будут выставлено значение 1 (true), в прочих битах маски - 0.

В качестве примера, покажем, как решается задача построения вектора A, элементы которого являются модулями элементов исходного вектора B. Длина векторов 100.

ld.w #100,vl
ld.w #4,vs
ld.w B,v0
lt.w v0,#0
mv.w.f v1,v0
neg.w.t v1,v0
st.w v1,A
Операция lt.w v0,#0 является векторной операцией сравнения регистра V0 со скалярным значением 0. Результат выставляет нужное значение регистра маски VM, который далее неявно используется в маскированных операциях копирования mv.w и смены знака neg.w.

4 Использование векторных библиотек

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

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

FORTRAN versus C

Имеется очень близкое родство между оптимизирующим модулем компилятора FORTRAN и компилятора C. Более того, директивы и в том и другом случае совершенно одинаковы. Это позволяет нам провести дальнейшее изложение не привязываясь к какому-либо одному языку. Все имеющиеся особенности будут перечислены в данном разделе.

С точки зрения синтаксиса языка, директивы выглядят как комментарии и определенной структурой. Это обеспечивает переносимость программ с директивами на другие платформы (содержание директив при таком переносе, конечно, теряется).

В FORTRANе директива выглядит так:

C $DIR directive params

где directive - имя директивы, params - параметры директивы (если таковые есть).

В языке C директива устанавливается с помощью специального средства - прагмы:

#pragma _CNX directive params

Регистр букв не имеет значения в имени директивы.

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

5 Автоматическая векторизация

Автоматическая векторная оптимизация производится компилятором при использовании в командной строке ключа -O2.

Векторизация как преобразование циклов

Уже известно, что векторная оптимизация имеет своим объектом цикл (и ничего, кроме цикла). Встречая в тексте программы оператор цикла, компилятор пытается его проанализировать и, в ряде случаев, совершает оптимизацию. Оптимизация в данном контексте есть не что иное как преобразование цикла. После такого преобразования компилятор заменяет некоторые куски цикла векторными операциями (если сие возможно). На этом векторная оптимизация и заканчивается.

Дальнейшее изложение будет направлено на классификацию циклов и указание типов преобразований, производимых над циклами.

Смертельно для векторизации

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

Разбиение цикла (Strip mining)

Типичным преобразованием является разбиение основного цикла на два вложенных с таким расчетом, чтобы внутренний новый цикл имел длину не выше 128. Наверное, уже понятно, что магическое число 128 диктуется размером векторных регистров процессора.

Пример добавления внешнего цикла: исходный текст

C    *** original ***            /*** original ***/
      DO 1 I=1,N                 for(i=0;i? n;i++) a[i]=b[i]+c[i];
1     A(I)=B(I)+C(I)
Будет преобразован в двойной цикл
C    *** optimized ***           /*** optimized ***/
      DO 2 K=1,N,128
      IMAX=MIN(128,N-K)          for(k=0;k? n;k+=128){
      DO 1 I=K,IMAX                 imax=128+k? n?128:n-k-128;
1     A(I)=B(I)+C(I)                for(i=k;i? imax;i++) a[i]=b[i]+c[i];
2     CONTINUE                      }
После чего, внутренний цикл будет заменен соответствующим набором векторных инструкций.

Внешний цикл не создается в случае

Директива MAX_TRIPS очень полезна в подпрограммах, имеющих дело с массивами переменной длины. По умолчанию компилятор будет рассматривать такие циклы как ``длинные'', создавая общую конструкцию с внешним циклом. Если этого не требуется, используйте директиву MAX_TRIPS непосредственно перед циклом, например
C$DIR MAX_TRIPS (80)              #pragma _CNX max_trips (80)
      DO 1 I=1,N                    for(i=0;i? n;i++) a[i]=b[i]+c[i];
1     A(I)=B(I)+C(I)

Распределение цикла (Distribution)

Компилятор векторизует лишь те вложенные циклы, в которых все вычисления производятся внутри самого глубокого цикла. Если это не так, оптимизатор будет пытаться разбить весь вложенный цикл на несколько циклов с таким расчетом, чтобы выделенные циклы уже поддавались векторизации. Пример:
      DO 1 I=1,N                    for(i=0;i? n;i++) {
      B(0,I)=0                        b[i][0]=0;
      DO 1 J=1,M                      for(j=0;j? m;j++)
       A(I)=A(I)+B(J,I)*C(J,I)          a[i]+=b[i][j]*c[i][j];
      D(I)=E(I)+A(I)                  d[i]=e[i]+a[i];
1     CONTINUE                        }
Будет распределен в три независимых цикла
      DO 1 I=1,N                    for(i=0;i? n;i++)
1     B(0,I)=0                        b[i][0]=0;

      DO 2 I=1,N                    for(i=0;i? n;i++)
      DO 2 J=1,M                      for(j=0;j? m;j++)
2     A(I)=A(I)+B(J,I)*C(J,I)          a[i]+=b[i][j]*c[i][j];

      DO 3 I=1,N                    for(i=0;i? n;i++)
3     D(I)=E(I)+A(I)                  d[i]=e[i]+a[i];
каждый из которых будет векторизован.

Перестановка циклов (Loop interchange)

Оптимизатор будет пытаться переставить местами вложенные циклы чтобы внутренний цикл был наиболее удобен для векторизации, точнее, желательно, чтобы: В следующем примере оптимизатор переставит местами циклы, чтобы внутренним оказался более длинный цикл - это выгоднее для векторизации:
C     *** original ***             /*** original ***/
      DO 1 I=1,100                 for(i=0;i? 100;i++)
      DO 1 J=1,5                      for(j=0;j? 5;j++)
1     A(I,J)=B(I,J)*C(I,J)              a[i][j]=b[i][j]*c[i][j];
После обработки:
C     *** optimized ***            /*** optimized ***/
      DO 1 J=1,5                   for(j=0;j? 5;j++)
      DO 1 I=1,100                    for(i=0;i? 100;i++)
1     A(I,J)=B(I,J)*C(I,J)                a[i][j]=b[i][j]*c[i][j];
Внутренний цикл далее заменяется соответствующими векторными инструкциями.

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

Следующий пример иллюстрирует перестановку цикла, чтобы элементы вектора (т.е. внутреннего цикла) располагадись в оперативной памяти подряд. Напомним, что в FORTRANе подряд идут элементы вида A(1,I) A(2,I) A(3,I) ..., т.е. самый левый индекс является наиболее удобным для предствления в виде вектора. В языке C, наоборот, быстрее всего изменяется самый правый индекс и элементы аналогичного массива располагаются в памяти в следующем порядке: a[i][0] a[i][1] a[i][2] ....

C     *** original ***             /*** original ***/
      DO 1 I=1,N                   for(i=0;i? n;i++)
      DO 1 J=1,M                      for(j=0;j? m;j++)
1     A(I,J)=B(I,J)+C(I,J)               a[j][i]=b[j][i]+c[j][i];
C     *** optimized ***            /*** optimized ***/
      DO 1 J=1,M                   for(j=0;j? m;j++)
      DO 1 I=1,N                      for(i=0;i? n;i++)
1     A(I,J)=B(I,J)+C(I,J)               a[j][i]=b[j][i]+c[j][i];

Вынос операции сохранения за тело цикла (Hoist and sink)

Во многих вложенных циклах, можно выделить векторный массив, который играет роль накопителя для внешнего цикла. В этом случае можно не записывать на каждом шаге внешнего цикла значение векторного регистра в память. Достатночно инициализировать его значение перед входом во внешний цикл (hoist) и сохранить после выхода (sink). Например,
      DO 1 I=1,N                   for(i=0;i? n;i++)
      DO 1 J=1,N                      for(j=0;j? n;j++)
1     A(I)=A(I)+B(J,I)                     a[i]+=b[i][j];
Поскольку вектор A играет роль чистого накопителя, компилятор не будет на каждом шаге внешнего цикла записывать его значение в оперативную память.

Вынос граничных присвоений (Peeling)

Иногда программисты присваивают значения граничным элементам массива прямо внутри цикла с помощью условного оператора. Надо сказать, что такие действия являются плохим стилем даже и без разговоров о векторизации. С точки зрения векторной оптимизации такой стиль выглядит еще неприятнее, поскольку убивает возможность оптимизации (помним, что условный оператор внутри цикла запрещает его векторизацию). Однако, для таких случаев, специалисты CONVEX предусмотрели специальное оптимизирующее преобразование ``вынос граничных присвоений''. Рассмотрим пример
C     *** original ***                      /* original */
C     *** ugly ****                         /* ugly */
      DO I=1,II                              for(i=0;i? ii;i++){
      IF(I.EQ.1) THEN                          if(i==0) a[i]=b[i];
       A(I)=B(I)                               else
      ELSE IF (I.EQ.II) THEN                   if(i==ii-1) a[i]=c[i];
       A(I)=C(I)                               else
      ELSE                                       a[i]=-a[i];
       A(I)=-A(I)                              }
      ENDIF
      ENDDO
После обработки:
C     *** optimized ***                   /* optimized */
      A(1)=B(1)                           a[0]=b[0];
      DO I=2,II-1                         for(i=2,i? ii-1;i++)
       A(I)=-A(I)                              a[i]=-a[i];
      ENDDO                               a[ii-1]=c[ii-1];
      A(II)=C(II)
После такой обработки новый текст будет векторизован.

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

Выкидывание ненужных проверок (Redundant test elimination)

Компилятор пытается найти внутри цикла те условные выражения, которые можно просто выкинуть. После такого преобразования у цикла больше шансов на векторизацию. Пример:
C     *** original ***                      /* original */
      DO I=1,II                             for(i=0;i? ii;i++){
      IF(I.GT.0) THEN                          if(i? =0) {
       DO J=1,JJ                                 for(j=0;j? jj;j++)
        A(I,J)=0                                   a[i][j]=0;
       ENDDO                                     }
      ENDIF                                 }
      ENDDO
C     *** optimized ***                    /* optimized */
      DO I=1,II                             for(i=0;i? ii;i++){
       DO J=1,JJ                                 for(j=0;j? jj;j++)
        A(I,J)=0                                   a[i][j]=0;
       ENDDO                                     }
      ENDDO

Вынос условного оператора за тело цикла (Test promotion)

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

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

C     *** original ***                /*** original ***/
      F=FUNC(X)                       f=func(x);
      DO 1 I=1,II                     for(i=0;i? ii;i++)
      IF(F.LT.0) A(I)=D(I)+F*B(I)        if(f? 0.) a[i]=d[i]+f*b[i];
      IF(F.GE.0) A(I)=D(I)-F*B(I)        else     a[i]=d[i]-f*b[i];
1     CONTINUE
После обработки:
C     *** optimized ***
      F=FUNC(X)                    f=func(x);
      IF(F.LT.0) THEN              if(f? 0.)
      DO 1 I=1,II                    for(i=0;i? ii;i++)
1     A(I)=D(I)+F*B(I)                     a[i]=d[i]+f*b[i];
      ENDIF                        else
      IF(F.GE.0) THEN                for(i=0;i? ii;i++)
      DO 2 I=1,II                          a[i]=d[i]-f*b[i];
2     A(I)=D(I)-F*B(I)
      ENDIF
Директива PROMOTE_TEST указывает компилятору, что условный оператор можно вынести за тело цикла. Поместите эту директиву сразу перед циклом, если компилятор затрудняется сделать соответствующее преобразование цикла сам.

Директива PROMOTE_TEST_ALL указывает компилятору, что условный оператор обязательно следует вынести за тело цикла.

Директива NO_PROMOTE_TEST запрещает вынос.

Рекуррентность

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

Избегайте рекуррентных выражений при программировании для векторных машин. Более того, старайтесь рекуррентные алгоритмы заменять операциями с массивами (векторами). Рассмотрим типы рекуррентности. Рекуррентность может появиться, если в некотором операторе используется результат предыдущего оператора (или предыдущего шага цикла). Вот пример рекуррентного выражения:

      DO 1 I=2,II                    for(i=1;i? ii;i++)
      A(I)=A(I-1)+3.1415               a[i]=a[i-1]+3.1415;
1     CONTINUE
Компилятор пытается проанализировать выражения такого типа. Некоторые не являются рекуррентными по сути и их можно векторизовать, например:
      DO 1 I=1,II-1                  for(i=0;i? ii-1;i++)
      A(I)=A(I+1)+3.1415               a[i]=a[i+1]+3.1415;
1     CONTINUE
Этот цикл будет векторизован.

Часто компилятор затрудняется определить является ли выражение действительно рекуррентным или нет. Следующие два примера демонстрируют это:

      DO 1 I=1,II-1                  for(i=0;i? ii-1;i++)
      A(I)=A(I+K)+3.1415               a[i]=a[i+k]+3.1415;
1     CONTINUE
      DO 1 I=1,II-1                  for(i=0;i? ii-1;i++)
      A(J(I))=A(K(I))+1.               a[j[i]]=a[k[i]]+1.;
1     CONTINUE
Если вы знаете, что рекуррентности нет, подскажите это компилятору с помощью директивы NO_RECURRENCE

Векторная редукция (Reduction)

Мы видели, что набор элементарных векторных операций шире, чем просто арифметические операции. Поэтому имеется возможность использовать векторную архитектуру CONVEX для вычисления циклов, вовсе не представляющих какую-либо операцию линейной алгебры. Компилятор опознает ограниченное количество языковых конструкций, которые могут быть заменены на векторные инструкции. Сюда относятся прежде всего операции редукции. Например,
      SUM=0.0                         sum=0.;
      DO 1 I=1,II                     for(i=0;i? ii;i++)
      SUM=SUM+A(I)                      sum+=a[i];
1     CONTINUE
Будет заменен одной операцией векторной редукции. Аналогично опознаются операции нахождения минимума/максимума вектора и др.

6 Автоматическая параллелизация

Автоматическая векторно-параллельная оптимизация производится компилятором при использовании в командной строке ключа -O3.

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

Очень часто параллелизуются циклы, порожденные компилятором при векторной оптимизации: Например,

C     original                         /* original */
      DO 1 I=1,320                     for(i=0;i? 320;i++)
      B(I)=C(I)+A(I)                      b[i]=c[i]+a[i];
1     CONTINUE
на этапе векторной оптимизации сие будет преобразовано в двойной цикл:
C     vector opt.                   /* vector opt. */
      DO 1 J=128,320,128              for(j=128;j? 320;j+=128){
      IMAX=MIN(J,320)                   imax=min(j,320);
      DO 1 I=J-128,IMAX                 for(i=j-128;i? imax;i++)
      B(I)=C(I)+A(I)                    b[i]=c[i]+a[i];
1     CONTINUE                          }
Внутренний цикл заменится одной векторной инструкцией. Внешний цикл будет кандидатурой ни параллелизацию.

Не подлежат параллельному исполнению циклы в которых:

Вызов функции в теле цикла

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

Если функция оперирует лишь внутренними переменными, не изменяет значения параметров (для FORTRANa), не пользуется статическими переменными (для C), то вы можете с уверенностью включать директиву FORCE_PARALLEL, что заставит компилятор провести параллелизацию. Однако, надо обязательно перерекомпилировать текст самой вызываемой функции с опцией -re, что заставит компилятор сделать ее пригодной для одновременного вызова разными процессорами.

Параллельная оптимизация вне циклов

Компилятор в режиме автоматической параллельной оптимизации рассматривает лишь циклы. Вы можете разбить свой текст на параллельно исполняемые блоки ``вручную'' используя директива BEGIN_TASKS, NEXT_TASK, и END_TASKS следующим образом:
C$DIR BEGIN_TASKS                    #pragma _CVX begin_tasks
  ? statement 1?                         ? statement 1? 
C$DIR NEXT_TASK                      #pragma _CVX next_task
  ? statement 2?                         ? statement 2? 
  ? statement 3?                         ? statement 3? 
C$DIR NEXT_TASK                      #pragma _CVX next_task
  ? statement 4?                         ? statement 4? 
C$DIR END_TASKS                      #pragma _CVX end_tasks
При этом компилятор приведет данное выражение к циклу, который затем будет параллелизован:
C$DIR FORCE_PARALLEL                 #pragma _CVX force_parallel
     DO I=1,3                        for(i=0;i? 3;i++)
     IF(I.EQ.1) THEN                   switch(i){
     ? statement 1?                      case 0: ? statement 1? 
     ELSE IF(I.EQ.2) THEN                     break;
     ? statement 2?                      case 1: ? statement 2? 
     ? statement 3?                              ? statement 3? 
     ELSE                                     break;
     ? statement 4?                      case 2: ? statement 4? 
     ENDIF                                    break;
     ENDDO                             }

7 Другие приемы оптимизации

Раскатка цикла (Unroll)

Организация цикла требует определенных накладных расходов: инициализация и инкременирование переменной цикла и др. Поэтому, если у вас в программе многократно встречаются небольшие циклы (тело которых вычисляется очень быстро), полезно вместо организации цикла просто перечислить в программе все шаги цикла. Такое преобразование называется раскаткой цикла. Вы можете заставить компилятор на этапе оптимизации раскатать тот или иной цикл с помощью директивы UNROLL. Например,
C$DIR UNROLL                 #pragma _CVX unroll
     DO I=1,3                        for(i=0;i? 3;i++)
     A(I)=B(I)*3.1415;                 a[i]=b[i]*3.1415;
     ENDDO
Будет преобразовано в
     A(1)=B(1)*3.1415;                 a[0]=b[0]*3.1415;
     A(2)=B(2)*3.1415;                 a[1]=b[1]*3.1415;
     A(3)=B(3)*3.1415;                 a[2]=b[2]*3.1415;
Такое преобразование может сильно увеличить размер вашей программы (исполняемого кода), поэтому не стоит раскатывать длинные циклы.

Оптимальное обращение к памяти

Компьютеры серии C CONVEX устроены так, что каждая адресная операция требует восьми тактов. Для ускорения адресных операций, они начинаются заранее - до того как потребуется соответствующее значение, что позволяет свести реальное время доступа к одному такту. Однако при циклическом обращении к памяти могут возникнуть конфликты, которые замедлят обращение к памяти. Что все это значит для пользователя?

Существует параметр - interleave-фактор памяти (зависит от конфигурации компьютера и имеет значение не менее 4). Узнать его легко с помощью команды getsysinfo. Для машин Центра это значение таково:

Память организована так, что невыгодно подряд считывать из памяти элементы, разделенные этим количеством байт.

Следует соблюдать следующие правила:

Динамический выбор способа выполнения цикла

Компилятор способен делать так, что решение о том, в каком режиме будет выполняться код (скалярный, векторный, параллельный) будет принято во время исполнения программы (т.е. динамически) в зависимости от длины цикла.

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

Управляет динамическим выбором оптимизации директива SELECT. В следующем примере скалярный вариант будет работать при длине цикла от 1 до 4, параллельный вариант от 5 до 20, векторный при длине цикла от 21 до 200, и далее будет использован векторно-параллельный вариант.

C$DIR SELECT(10,4,20)            #pragma _CVX select(10,4,20)

8 Листинг оптимизации

Указав компилятору опцию -or с параметром, вы можете получить отчет (листинг) оптимизации.

Следующие параметры могут задаваться опцией -op:

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

Пример листинга оптимизации приведен ниже. Рассмотрим следующую программу:

1     PROGRAM EXAMPLE1             extern double a[200][201];
2     REAL  A(201,200)             extern double b[200][201];
3     REAL B(201,200)              extern double c[200][201];
4     REAL C(201,200)              void example1(){
5     INTEGER I,J,K                int i,j,k;
6
7     DO I=1,200                   for(i=0;i? 200;i++){
8     DO J=1,200                     for(j=0;j? 200;j++){
9     C(J,I)=0.0                       c[i][j]=0.;
10    DO K=1,200                       for(k=0;k? 200;k++)
11    C(J,I)=C(J,I)+A(K,I)*B(J,K)      c[i][j]+=a[i][k]*b[k][j];
12    ENDDO                           }
13    ENDDO                          }
14    ENDDO                         }
Скомпилируем ее с опцией автоматической векторной оптимизации:
% fc -c -O2 -or all example.f    % cc -c -O2 -or all example.c
Получим листинг вида:
 Optimization by Loop for Routine example1

Line   Id   Iter. Reoderind      New   Optimizing / Special Exec.
Num.   Num. Var.  Transformation Loops Transformation       Mode
-----------------------------------------------------------------
   7        i     Dist
   7-1      i     Scalar
   7-2      i     Scalar
   8-1      j     FULL VECTOR
   8-2      j     FULL VECTOR Inter
  10-2      k     Scalar

Line   Iter.    Analysis
Num.   Var.
------------------------------------------------------------------
   8-2 j         Interchanged to innermost

   Array references for Routine example1

Line Var.    Optimi-   Dependencies
Num. Name    zation
------------------------------------------------------------------
 11  c       Sunk
 11  c       Hoist
Компилятор сообщает о проделанных над циклом преобразованиях, ссылаясь на номер строки в котором начинается цикл. Первая таблица является основной - это перечень встреченных циклов. Последующие таблицы содержат дополнительную справочную информацию.

В первой строке листинга сообщается, что цикл, начинающийся на строке 7 исходного текста программы (с переменной цикла i) был распределен. При этом возникло два цикла по переменной i, которые не были векторизованы (т.к. внутренний цикл по j векторизован).

Далее, цикл по переменной j был распределен на два цикла и каждый из них полностью векторизован (причем была произведена перемена мест цикла по j и k).

Наконец, цикл по k не векторизован: поскольку векторизован (ставший внутренним после перестановки) цикл по j.

Вторая таблица поясняет, что цикл на строке 8 был переставлен таким образом, что он оказался самым глубоким.

Наконец, в последней таблице сообщается, что над переменной c произведен вынос присвоения начальных и конечных значений за тело цикла. Действительно, массив c при каждом значении k является накопителем, что и позволяет заменить его внутри цикла на векторный регистр.

Разберем более подробно что может появиться в таблице.

Таблица циклов

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

Поле Reodering information может содержать:

Поле Optimizing/Special transformation может содержать:

9 Список директив оптимизации

Директивы действуют на цикл, непосредственно следующий за строкой с директивой. Если директива стоит перед вложенным циклом, то она действует только на самый внешний цикл.

10 Ассемблерная оптимизация

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

Тем не менее, небольшие экскурсы в ассемблер вы можете совершать относительно бескровным способом, используя ассемблерные возможности компилятора C (и FORTRAN). Именно, компилятор имеет опцию -s, которая используется аналогично опции -c, но выдает не объектный код, а текстовый файл с ассемблерным кодом вашей программы. Такой файл получит стандартное расширение .s. Например,

% fc -s foo.f bar.f % cc -s foo.c bar.c породит два файла с ассемблерным текстом - foo.s и bar.s.

После редактирования текста, вы можете скомпилировать ассемблерный текст обычным способом:

% fc -c foo.s bar.s % cc -c foo.s bar.s

Если вы созрели для ассемблерной оптимизации, начните с простого - ассемблируйте тестовую подпрограмму, максимально похожую на настоящую, но поддающуюся автоматической оптимизации. Сделайте то же самое с разными ключами оптимизации и проанализируйте тексты в каждом случае. Как только вы поймете, что делает компилятор, вы можете переходить к настоящей подпрограмме. Желаем удачи.


The file was converted from TeX source by FunnyTeX utility by Mike Krutikov     ( http://www.csa.runnet.ru/CSA/tutor/opti/)