Ваша основная цель с развертыванием — упростить обработку инструкций конвейером инструкций ЦП. Несколько инструкций могут выполняться одновременно, и различные факторы могут прерывать плавный поток. Например, зависимости данных: если более поздней инструкции необходимо загрузить данные, и эти данные изменяются более ранними инструкциями, более поздняя инструкция должна ждать на этапе загрузки, пока более ранние инструкции не сохранят эти данные. Это называется застой конвейера.
См. комментарии о том, почему зависимость от данных является основным узким местом в этом примере.
Пример учебника, приведенный в Вопросе, кажется в основном упражнением для ознакомления с ручным развертыванием циклов и не предназначен для исследования каких-либо проблем с производительностью.
Ваш первый набросок кода развертывания выглядит так, но вы получите нежелательные случаи
for (i=1; i < n; i+=3) {
v = last_v + a[i];
p[i] = v ;
last_v = v;
v = last_v + a[i+1];
p[i+1] = v ;
last_v = v;
v = last_v + a[i+2];
p[i+2] = v ;
last_v = v;
}
Нежелательные случаи — обратите внимание, что последним индексом, который вы хотите обработать, является (n-1)
| n |
Unwanted cases |
| 5 |
Array indexes 1,2,3 then 4,5,6 => the unrolled code processes 2 unwanted cases, index 5 and 6 |
| 6 |
Array indexes 1,2,3 then 4,5,6 => the unrolled code processes 1 unwanted case, index 6 |
| 7 |
Array indexes 1,2,3 then 4,5,6 => no unwanted cases |
См. также Обработка остатка развернутого цикла
Итак, удалите последний цикл, если есть какие-либо нежелательные случаи, и тогда у вас будет
// `nn` is the adjusted loop limit to avoid an extra loop with unwanted cases
int nn = n;
if ( (n-1)%3 != 0 ) nn = n - 3;
for (i=1; i < nn; i+=3) {
v = last_v + a[i];
p[i] = v ;
last_v = v;
v = last_v + a[i+1];
p[i+1] = v ;
last_v = v;
v = last_v + a[i+2];
p[i+2] = v ;
last_v = v;
}
На этом этапе нам нужно обработать оставшиеся/отсутствующие случаи:
| n |
nn |
values of iterator i |
| 5 |
2 |
1,4 => final i = n - 1 |
| 6 |
3 |
1,4 => final i = n - 2 |
| 7 |
7 |
1,4,7 => final i = n |
Если i = n - 1, у вас есть 1 пропущенный случай, т.е. индекс n-1
Если i = n - 2, у вас есть 2 пропущенных случая, т.е. индекс n-2 и n-1
Если i = п, все готово
if ( i == n - 1 ) { // 1 missing case
v = last_v + a[n-1]
p[n-1] = v;
}
if ( i == n - 2 ) { // 2 missing cases
v = last_v + a[n-2]
p[n-2] = v;
last_v = v;
v = last_v + a[n-1]
p[n-1] = v;
}
person
John D
schedule
28.06.2021
for (x=1;x+3 < n; x+=3) ..., изменив также строку 6 (с необходимостью обработки остатка n%3 !=0). Изменение строк с 7 по 9 означает только то, что такжеnозначает, что теперь кратно 3, а строки 7,8,9 необходимо скопировать три раза с правильным расчетом индекса. - person Aki Suihkonen schedule 28.06.2021x < n-2илиx+2 < n. Илиx+3 <= n. Я предпочитаюx < n-2, чтобы компилятору было проще поднять инвариант цикла, поскольку +2 не совпадает с приращением счетчика.<=может быть в порядке; UB со знаком-переполнением сообщает компилятору о завершении. Ваше управление циклом оставит невыполненными 1..3 элемента, а не 0..2. (Очевидное доказательство того, что ручное развертывание цикла сложно; даже опытные люди склонны ошибаться; лучше всего использоватьclang -O3и позволить ему разворачиваться, когда это целесообразно, потому что автоматическая векторизация обычно лучше работает с идиоматическими циклами). - person Peter Cordes schedule 28.06.2021i+=2иif() break;в тело цикла, в основном обходя бессмысленное требование изменять только тело цикла, а не элемент управления. Если количество элементов массива не должно бытьn*3в развернутой версии, поэтому вы просто делаетеi*3 + 0..2. - person Peter Cordes schedule 28.06.2021vиlast_vне приносят никакой пользы. Я бы упростил это доv += a[i]. (Что будет компилировать то же самое, но будет проще для людей.) Возможно, они хотят, чтобы вы предположили ассоциативную FP, поэтому вы могли бы сделатьtmp = a[x + 0] + ... + a[x+2], чтобы переносимая циклом зависимость была простоv += tmp, с промежуточнымиvзначениями, вычисленными из старого v , Таким образом, вы выполняете избыточную работу, чтобы избежать задержки. - person Peter Cordes schedule 28.06.2021