8. Рекомендации по оптимизации программ под архитектуру Эльбрус

8.1. Рекомендации по работе со структурами данных

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

  • простые одномерные массивы.

    При регулярном считывании/записи элементов массива могут достигаться теоретически максимальные показатели темпа доступа к памяти - 32 байта в такт при попадании в L2$, 32 байта в 3 такта при гарантированном отсутствии в L2$, при условии обращения к соседним элементам, причем для считывания может применяться механизм APB; при регулярном обращении с большим шагом (>64b) APB все еще применим, но темп существенно падает (до 64 раз при побайтовой обработке);

  • одномерные массивы структур.

    При регулярной обработке применим APB, однако, следует следить за тем, чтобы набор одновременно читаемых/записываемых полей в горячих участках был как можно более компактным; весьма полезен (в ущерб наглядности) переход от массивов структур к набору массивов, хранящих отдельные поля;

  • многомерные выстраиваемые массивы.

    Многомерные массивы в языке Fortran (а также многомерные массивы в языке C при условии константных длин старших размерностей) являются одномерными по сути, но индексируемыми несколькими размерностями:

A(i,j,k) "FORTRAN" = a(i+j*dim1+k*dim1*dim2) "C"

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

for i
  for j
    for k
      A(k,j,i) // хорошо
      B(i,j,k) // плохо

  • многомерные не выстраиваемые массивы.

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

  • списки.

    Обход элементов списка представляет собой цикл с рекуррентностью (зависимостью между итерациями) вида p=p->next, иными словами, адрес, по которому производится чтение на текущей итерации, зависит от результата чтения на предыдущей итерации.

    При таком обходе темп перебора элементов списка не превышает 1 элемент на время доступа в L1$. Например, для процессора Е8С этот темп в 24 раза (!) меньше максимально возможного (при размере указателя 4 байта, и при условии, что все читаемые элементы расположены в L1$). В случае, когда все операции чтения промахиваются и в L1$, и в L2$, темп падает до 1 элемента в t_latency тактов; в связи с нерегулярностью адресов APB неприменим, но может быть эффективен механизм list-prefetch;

  • деревья.

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

  • хэш-таблицы.

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

8.2. Виды локальности данных

Виды локальности данных связаны с возможностями компилятора распознать зависимость между обращениями к этим данным. Семантика программ на императивных языках, таких как C и C++, строго последовательна; поэтому возможность распараллеливания вычислений зависит от способности компилятора обнаружить гарантированное отсутствие зависимостей между последовательностями обращения в память за данными.

Там, где логика программы не диктует необходимости определенной локальности данных, можно делать выбор в пользу одного из следующих типов локальности:

  • глобальные данные:

    • местоположение - сегмент bss кода;

    • время жизни - вся программа;

    • адрес общедоступен;

    • не конфликтуют с другими данными (отсутствие конфликтов очевидно, если не было операций взятия адреса &glob);

    • глобальные данные небольшого размера можно разместить на глобальных регистрах;

  • простые локальные данные без взятия адреса:

    • местоположение - регистры;

    • время жизни - до выхода из процедуры;

    • регистры не отображаются в память, ни с кем не конфликтуют;

  • сложные локальные данные, либо локальные данные со взятым адресом:

    • местоположение - пользовательский стек;

    • время жизни - до выхода из процедуры;

    • адрес доступен только внутри процедуры, для передачи данных в вызываемые процедуры нужно брать адрес;

    • в связи с часто необходимой операцией взятия адреса разрешение конфликтов по адресам становится более затруднительным;

  • динамические глобальные данные (malloc):

    • местоположение - динамически выделяемая память;

    • время жизни - до динамического освобождения free;

    • адрес доступен через указатели;

    • конфликты по адресам разрешимы с затруднениями, не разрешимы конфликты между разными экземплярами malloc в цикле;

  • динамические локальные данные (alloca):

    • местоположение - пользовательский стек;

    • время жизни - до выхода из процедуры;

    • адрес доступен через указатели;

    • конфликты по адресам разрешимы с затруднениями, не разрешимы конфликты между разными экземплярами malloc в цикле.

8.3. Рекомендации по оптимизации процедур

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

8.3.1. Анализ процедуры: начальный этап

Для получения кода процедуры с профилем необходимо воспользоваться дизассемблером:

ldis -I m_program my_function1

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

8.3.2. Короткая ациклическая процедура (не более 30 тактов)

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

  • плохой наполненности широких команд:

    • вследствие зацепления операций;

    • ввиду наличия длинных операций (деление, квадратный корень, вызов по косвенности);

    • вследствие конфликтов между чтениями/записями;

  • блокировки(ок) от операций чтения.

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

  • инлайн-подстановка: собирать в режиме -fwhole, использовать двухфазную компиляцию -fprofile-generate / -fprofile-use;

  • уменьшение длины зацепления;

  • принудительный разрыв конфликтов;

  • включение режима выноса чтений из процедур -fipo-invup;

  • по возможности локализация данных для лучшего использования кэш-памяти.

8.3.3. Процедура с горячими простыми циклами/гнездами циклов

Анализ процедуры сводится к анализу работы горячих циклов. Наиболее частые проблемы:

  • плохая наполненность широких команд;

  • не применился механизм apb;

  • блокировки после операций чтения из-за промахов в кэш;

  • блокировки из-за превышения пропускной способности устройства памяти.

Предлагаемые пути решения означенных проблем:

  • малое число итераций может привести к отказу от применения конвейеризации (как следствие, к слабой наполненности широких команд), к отказу от использования механизма apb; если число итераций цикла объективно невелико (<5), следует рассмотреть возможность модификации алгоритма; если число итераций объективно велико, следует использовать двухфазную компиляцию -fprofile-generate / -fprofile-use, либо добавить в исходный текст перед циклом подсказку:

#pragma loop count(100);

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

  • механизм apb не применяется из-за нерегулярного изменения адреса; рекомендуется использовать в качестве цикловых счетчиков, определяющих адрес чтения, переменные типа long (не unsigned), не производить инкрементов счетчиков под условиями;

  • механизм apb не применяется при невозможности статического определения выровненности чтений по размеру; рекомендуется пользоваться опцией -faligned (входит в состав -ffast), подразумевающей выровненность адресов по размеру читаемого объекта;

  • блокировки от операций чтения из-за кэш-промахов (BUB_E0): рекомендуется попробовать опции -fcache-opt, -flist-prefetch, включающие режим предварительной подкачки данных в кэш;

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

8.3.4. Сложный цикл с управлением, гнездо с управлением

Сложный цикл - цикл с управлением, несколькими обратными дугами. Некоторые сложные циклы при наличии точной профильной информации (-fprofile-generate / -fprofile-use) могут быть сведены к простым применениям цикловых оптимизаций loop_nesting, loop_unswitching и некоторых других.

8.3.5. Громоздкая процедура

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

  • если процедура стала громоздкой вследствие inline-подстановок других процедур, можно попробовать ограничить применение inline опциями;

  • можно произвести вручную выделение важных фрагментов в отдельные процедуры.

8.3.6. Процедура с превалирующим оператором switch

Конструкции switch с большим числом альтернатив, как правило, обрабатываются компилятором достаточно эффективно при наличии адекватного профиля (см. опции -fprofile-generate / -fprofile-use). Если конструкция switch имеет большое количество альтернатив с равномерно распределенной малой вероятностью, тогда компилятор выразит её с помощью чтения из таблицы меток и косвенного перехода. Более эффективно при этом работают конструкции switch с плотным множеством значений, т.к. в случае разреженного множества значений switch таблица будет иметь большой размер.

8.3.7. Библиотечная процедура

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