Некоторые простейшие принципы автовекторизации

[denim]

все шикарно в интеловском компиляторе, кроме цены.

[blueboar2]

У вас ссылка на инструкции SSSE почему-то названа SSEE

[andrei_an]

Спасибо, описался.

[datacompboy]

void Calculate(float * restrict a, int n) {
  for(int i=0;i<n;i+=2) {
      a[i] = a[i]+1;
  }
  return;
}

void Calculate2(float * restrict a, int n) {
  for(int i=0;i<n;i+=2) {
      a[i] = a[i]+1;
      a[i+1] = a[i+1];
  }
  return;
}

void Calculate3(float * restrict a, int n) {
  for(int i=0;i<n;i++) {
      a[i] = a[i]+1-i%2;
  }
  return;
}

Все три функции по факту делают одно и то же 1-в-1.
Однако, третий смог векторизоваться O_O

datacompboy@nuuzerpogodible:~$ gcc  -c -O3 -march=native -std=c99 -mfpmath=sse -ftree-vectorizer-verbose=2 a.c

Analyzing loop at a.c:2

2: not vectorized: complicated access pattern.
2: not vectorized: complicated access pattern.
a.c:1: note: vectorized 0 loops in function.

Analyzing loop at a.c:9

9: not vectorized: complicated access pattern.
9: not vectorized: complicated access pattern.
a.c:8: note: vectorized 0 loops in function.

Analyzing loop at a.c:17

17: not vectorized: relevant stmt not supported: patt.51_34 = i_22 < 0 ? 1 : 0;


Vectorizing loop at a.c:17

17: LOOP VECTORIZED.
a.c:16: note: vectorized 1 loops in function.

как с этим icc справится последний?

[andrei_an]

icc все эти циклы векторизует.

[datacompboy]

можно листинг итога векторизации?
желательно с указанием «выровнено, безпроблемно, всегда кратно»

[andrei_an]

icc -c -std=c99 -vec_report3 -xhost test.c

test.c(2): (col. 3) remark: LOOP WAS VECTORIZED
test.c(9): (col. 3) remark: LOOP WAS VECTORIZED
test.c(17): (col. 3) remark: loop was not vectorized: vectorization possible but seems inefficient

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

[datacompboy]

а если её записать в форме (i&1)?
но я ожидал что он в состоянии оптимизроват (1-i%2) сам.

но под листингом я понимал итоговый ассемблерный код.

[andrei_an]

Оценочный механизм icc не считает векторизацию выгодной. #pragma vector always помогает и векторизация выглядит вполне разумно. Возможно оценочный механизм не прав.

[datacompboy]

сильно код у этих 3х случаев отличаются?

[andrei_an]

Очень сильно.
Наверное, компилятор мог бы сам векторизовать такие случаи и использовать последовательный доступ к массиву А, но делать маскированные вычисления, т.е. через элемент. И это было бы красивее и выгоднее, разве только в реальных вычислениях такой доступ редко случается и тратить на такой изыск время разработчики не захотят.

[datacompboy]

да вот например подготовка черезстолбцовой обработки для стерео3Dпары.
вполне себе работа с [i] и [i+1] по-разному.
сходу не вспомню что еще обрабатывал аналогичным образом, но точно помню что работа по разному с четными и нечетными элементами — не ультра редкая ситуация.
впрочем, могу ошибаться, у меня статистики нет.

[DmitryBabokin]

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

[datacompboy]

операция %(2^x) оптимизируются настолько просто, что это первая же оптимизация, которую реализуют во всех доморощенных оптимизирующих компиляторах :)

[DmitryBabokin]

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

Вообще, программисты, которые заботятся о производительности ибегают % пока это возможно.

[datacompboy]

я знаю. просто «логически» выглядит естественным, что код максимально оптимизируется скалярно, а потом уже отдаётся векторному.

мне вот очень интересно разницу в векторизации icc первого и второго варианта увидеть — но andrei_an тщательно скрывает итоговый листинг :(

[DmitryBabokin]

Практика в теории выглядит просто, а вот теория на практике… :) Поверьте на слово, там есть объективные сложности (кроме банального руки не дошли, которое тоже имеет место быть в любом большом продукте). Это я про общий случай, не про этот конкретный.

Вы, кстати, сами можете скачать триальную версию и всё проверить. Триал полностью функционален, только ограничен по времени.

[datacompboy]

Конечно, вот только это дольше, чем просто прочитать листинг от человека, у кого всё уже настроено :)
Завтра как дотянусь попробую заняться этим.

[DmitryBabokin]

>icpc -c -O3 foo.c -restrict -vec_report=3 -xSSE4.2
foo.c(2): (col. 3) remark: loop was not vectorized: vectorization possible but seems inefficient.
foo.c(9): (col. 3) remark: loop was not vectorized: vectorization possible but seems inefficient.
foo.c(17): (col. 3) remark: loop was not vectorized: vectorization possible but seems inefficient.

>icpc -c -O3 foo.c -restrict -vec_report=3 -xAVX
foo.c(2): (col. 3) remark: LOOP WAS VECTORIZED.
foo.c(9): (col. 3) remark: LOOP WAS VECTORIZED.
foo.c(17): (col. 3) remark: loop was not vectorized: vectorization possible but seems inefficient.

Вот ассемблер: http://pastebin.com/pmSc5jGP

[datacompboy]

то есть первый и второй векторизованы одинаково 1-в-1 — выкинув попытку сказать компилятору о непрерывности цикла.

можно перед третьим циклом воткнуть #pragma vector aligned и показать результат?

[DmitryBabokin]

Ничего не изменилось.

[datacompboy]

habrahabr.ru/company/intel/blog/171439/#comment_6018161
Странно. Придётся самому скачать icc.

[andrei_an]

Тут проблема в непоследовательном доступе к массиву a. Из-за того, что i+=2 на первой итерации используется a[0], на второй a[2] и т.д. Поэтому считать данные из памяти за одну операцию не получается и приходится их записывать в регистр поэлементно. Поэтому с первым и вторым циклом векторизатору нужно напрягаться. В третьем цикле вы забыли про это и автовекторизатор смог справиться.
Кстати, во всяких вычислительных задачах, особенно на Фортране, часто встречаются вычисления, в которых часть массивов доступается поэлементно, а часть — нет. Но векторизация очень выгодна. Поэтому плохо, что непоследовательный доступ препятствует работе автовекторизатора gcc.

[datacompboy]

не совсем так. в первом цикле да, обращение только к четным элементам.
для этого во втором случае я четко написал — можно трогать все элементы.
и там вполне себе последоваельный доступ — первая итерация трогает 0й и 1й, вторая 2й и 3й, и так далее.

А в последнем записано то же самое, только вместо константы — зависимость от переменной i через остаток от деления. что отдельный привет, однако почему-то помогло векторизовать O_O

[andrei_an]

Возможно, вы ошиблись в примере. Остаток от деления не участвует в вычислении индекса для массива A. Здесь у вас скалярное выражение с i. И автовекторизатору нужно скалярную переменную преобразовать в векторную. Автовекторизатор создаст вектор [i:i+N] и будет его векторно делить и получать векторный результат для остатка от деления. Причем, перед векторным циклом будет создан вектор [0:N] и каждый последующий будет вычисляться на каждой итерации сложением с вектором [N,..,N]. Наверное, для автовекторизатора это не сложно. Проблема именно в заполнении векторных регистров из памяти.

[datacompboy]

Давайте циклы развернём? Для n=8.
Первый цикл:
a[0] = a[0] + 1;
a[2] = a[2] + 1;
a[4] = a[4] + 1;
a[6] = a[6] + 1;

Второй цикл:
a[0] = a[0] + 1;
a[1] = a[1];
a[2] = a[2] + 1;
a[3] = a[3];
a[4] = a[4] + 1;
a[5] = a[5];
a[6] = a[6] + 1;
a[7] = a[7];

Третий цикл:
a[0] = a[0] + 1 — 0%2;
a[1] = a[1] + 1 — 1%2;
a[2] = a[2] + 1 — 2%2;
a[3] = a[3] + 1 — 3%2;
a[4] = a[4] + 1 — 4%2;
a[5] = a[5] + 1 — 5%2;
a[6] = a[6] + 1 — 6%2;
a[7] = a[7] + 1 — 7%2;

Теперь эквивалентность всех трёх циклов видна?
Теперь видно, что МОЖНО последовательно использовать все элементы?