Loop unrolling - Loop unrolling
O desenrolamento de loop , também conhecido como desenrolamento de loop , é uma técnica de transformação de loop que tenta otimizar a velocidade de execução de um programa em detrimento de seu tamanho binário , que é uma abordagem conhecida como compensação espaço-tempo . A transformação pode ser realizada manualmente pelo programador ou por um compilador otimizador . Em processadores modernos, o desenrolamento de loop geralmente é contraproducente, pois o tamanho do código aumentado pode causar mais perdas de cache; cf. Dispositivo de Duff .
O objetivo do desenrolamento do loop é aumentar a velocidade de um programa reduzindo ou eliminando as instruções que controlam o loop, como aritmética de ponteiro e testes de "fim de loop" em cada iteração; reduzir as penalidades das agências; bem como ocultar latências, incluindo o atraso na leitura de dados da memória. Para eliminar essa sobrecarga computacional , os loops podem ser reescritos como uma sequência repetida de instruções independentes semelhantes.
O desenrolamento de loops também faz parte de certas técnicas de verificação formal , em particular a verificação de modelo limitado .
Vantagens
A sobrecarga em loops "apertados" geralmente consiste em instruções para incrementar um ponteiro ou índice para o próximo elemento em uma matriz ( aritmética de ponteiro ), bem como testes de "fim de loop". Se um compilador ou montador de otimização for capaz de pré-calcular os deslocamentos para cada variável de matriz referenciada individualmente , eles podem ser integrados nas instruções de código de máquina diretamente, portanto, não exigindo operações aritméticas adicionais em tempo de execução.
- Ganhos significativos podem ser obtidos se a redução nas instruções executadas compensar qualquer redução de desempenho causada por qualquer aumento no tamanho do programa.
- A penalidade do ramo é minimizada.
- Se as instruções no loop forem independentes umas das outras (ou seja, onde as instruções que ocorrem antes no loop não afetam as instruções que as seguem), as instruções podem ser potencialmente executadas em paralelo .
- Pode ser implementado dinamicamente se o número de elementos do array for desconhecido em tempo de compilação (como no dispositivo de Duff ).
A otimização de compiladores às vezes executa o desenrolamento automaticamente ou mediante solicitação.
Desvantagens
- Aumento do tamanho do código do programa, o que pode ser indesejável, principalmente para aplicativos incorporados. Também pode causar um aumento nas perdas de cache de instrução, o que pode afetar negativamente o desempenho.
- A menos que seja executado de forma transparente por um compilador de otimização, o código pode se tornar menos legível .
- Se o código no corpo do loop envolver chamadas de função, pode não ser possível combinar desenrolamento com inlining , pois o aumento no tamanho do código pode ser excessivo. Portanto, pode haver uma compensação entre as duas otimizações.
- Possível aumento do uso de registro em uma única iteração para armazenar variáveis temporárias, o que pode reduzir o desempenho, embora muito dependa de possíveis otimizações.
- Além de um código muito pequeno e simples, os loops desenrolados que contêm ramificações são ainda mais lentos do que as recursões.
Desenrolamento de loop estático / manual
O desenrolamento manual (ou estático) do loop envolve o programador analisando o loop e interpretando as iterações em uma sequência de instruções que reduzirá a sobrecarga do loop. Isso está em contraste com o desenrolamento dinâmico que é realizado pelo compilador.
Exemplo manual simples em C
Um procedimento em um programa de computador é excluir 100 itens de uma coleção. Isso normalmente é realizado por meio de um for -loop que chama a função delete (item_number) . Se essa parte do programa tiver que ser otimizada e a sobrecarga do loop exigir recursos significativos em comparação com aqueles da função delete (x) , o desenrolamento pode ser usado para acelerá-lo.
| Loop normal | Após o desenrolar do loop |
|---|---|
int x;
for (x = 0; x < 100; x++)
{
delete(x);
}
|
int x;
for (x = 0; x < 100; x += 5 )
{
delete(x);
delete(x + 1);
delete(x + 2);
delete(x + 3);
delete(x + 4);
}
|
Como resultado dessa modificação, o novo programa tem que fazer apenas 20 iterações, em vez de 100. Depois disso, apenas 20% dos saltos e desvios condicionais precisam ser executados e representa, ao longo de muitas iterações, uma diminuição potencialmente significativa no sobrecarga de administração de loop. Para produzir o benefício ideal, nenhuma variável deve ser especificada no código desenrolado que requer aritmética de ponteiro . Isso geralmente requer endereçamento " base mais deslocamento", em vez de referência indexada.
Por outro lado, o desenrolamento manual do loop expande o tamanho do código-fonte de 3 para 7 linhas, que devem ser produzidas, verificadas e depuradas, e o compilador pode ter que alocar mais registradores para armazenar variáveis na iteração do loop expandido. Além disso, as variáveis de controle do loop e o número de operações dentro da estrutura do loop desenrolado devem ser escolhidos com cuidado para que o resultado seja realmente o mesmo do código original (assumindo que esta seja uma otimização posterior no código já em funcionamento). Por exemplo, considere as implicações se a contagem de iterações não fosse divisível por 5. As alterações manuais necessárias também se tornam um pouco mais complicadas se as condições de teste forem variáveis. Veja também o dispositivo de Duff .
Complexidade inicial
No caso simples, o controle de loop é meramente uma sobrecarga administrativa que organiza as declarações produtivas. O loop em si não contribui em nada para os resultados desejados, apenas poupando ao programador o tédio de replicar o código cem vezes, o que poderia ter sido feito por um pré-processador que gerava as replicações ou por um editor de texto. Da mesma forma, if -statements e outras instruções de controle de fluxo podem ser substituídas pela replicação de código, exceto que o código pode ser inchado . Os programas de computador rastreiam facilmente as combinações, mas os programadores consideram essa repetição chata e cometem erros. Considerar:
| Loop normal | Após o desenrolar do loop |
|---|---|
for i := 1:8 do
if i mod 2 = 0 then do_even_stuff(i)
else do_odd_stuff(i);
next i;
|
do_odd_stuff(1); do_even_stuff(2); do_odd_stuff(3); do_even_stuff(4); do_odd_stuff(5); do_even_stuff(6); do_odd_stuff(7); do_even_stuff(8); |
Mas, é claro, o código executado não precisa ser a invocação de um procedimento, e este próximo exemplo envolve a variável de índice na computação:
| Loop normal | Após o desenrolar do loop |
|---|---|
x(1) := 1;
For i := 2:9 do
x(i) := x(i - 1) * i;
print i, x(i);
next i;
|
x(1) := 1; x(2) := x(1) * 2; print 2, x(2); x(3) := x(2) * 3; print 3, x(3); x(4) := x(3) * 4; print 4, x(4); ... etc. |
que, se compilado, pode produzir uma grande quantidade de código ( declarações de impressão são notórias), mas a otimização é possível. Este exemplo faz referência apenas a x (i) e x (i - 1) no loop (o último apenas para desenvolver o novo valor x (i) ), portanto, dado que não há nenhuma referência posterior ao array x desenvolvido aqui, seus usos podem ser substituídos por uma variável simples. Tal mudança significaria, no entanto, uma variável simples cujo valor é alterado, ao passo que, se ficar com a matriz, a análise do compilador pode notar que os valores da matriz são constantes, cada um derivado de uma constante anterior e, portanto, transporta os valores constantes para que o código torna-se
print 2, 2; print 3, 6; print 4, 24; ...etc.
Em geral, o conteúdo de um loop pode ser grande, envolvendo uma intrincada indexação de array. Provavelmente, é melhor deixar esses casos para otimizar os compiladores para serem desenrolados. A replicação dos loops mais internos pode permitir muitas otimizações possíveis, embora produza apenas um pequeno ganho, a menos que n seja grande.
Desenrolando loops WHILE
Considere um loop WHILE de pseudocódigo semelhante ao seguinte:
| Loop normal | Após o desenrolar do loop | Loop desenrolado e "ajustado" |
|---|---|---|
WHILE (condition) DO
action
ENDWHILE
.
.
.
.
.
.
|
WHILE (condition) DO
action
IF NOT(condition) THEN GOTO break
action
IF NOT(condition) THEN GOTO break
action
ENDWHILE
LABEL break:
.
|
IF (condition) THEN
REPEAT
action
IF NOT(condition) THEN GOTO break
action
IF NOT(condition) THEN GOTO break
action
WHILE (condition)
LABEL break:
|
Neste caso, o desenrolamento é mais rápido porque o ENDWHILE (um salto para o início do loop) será executado com 66% menos freqüência.
Melhor ainda, o exemplo de pseudocódigo "ajustado", que pode ser executado automaticamente por alguns compiladores de otimização, eliminando totalmente os saltos incondicionais.
Desenrolamento dinâmico
Uma vez que os benefícios do desenrolamento do loop são frequentemente dependentes do tamanho de um array - que muitas vezes pode não ser conhecido até o tempo de execução - os compiladores JIT (por exemplo) podem determinar se devem invocar uma sequência de loop "padrão" ou, em vez disso, gerar um (relativamente curto ) sequência de instruções individuais para cada elemento. Essa flexibilidade é uma das vantagens das técnicas just-in-time versus otimização estática ou manual no contexto de desenrolamento de loop. Nessa situação, geralmente é com valores relativamente pequenos de n que a economia ainda é útil - exigindo um aumento geral bastante pequeno (se houver) no tamanho do programa (que pode ser incluído apenas uma vez, como parte de uma biblioteca padrão).
Os programadores de linguagem assembly (incluindo a otimização de escritores de compiladores) também podem se beneficiar da técnica de desdobramento de loop dinâmico, usando um método semelhante ao usado para tabelas de ramificação eficientes . Aqui, a vantagem é maior quando o deslocamento máximo de qualquer campo referenciado em uma matriz particular é menor do que o deslocamento máximo que pode ser especificado em uma instrução de máquina (que será sinalizado pelo montador se excedido).
Exemplo de Assembler (IBM / 360 ou Z / Architecture)
Este exemplo é para montadores IBM / 360 ou Z / Architecture e assume que um campo de 100 bytes (no deslocamento zero) deve ser copiado do array FROM para o array TO - ambos com 50 entradas com comprimentos de elemento de 256 bytes cada.
* The return address is in R14.
* Initialize registers R15, R0, R1, and R2 from data defined at the end of
* the program starting with label INIT/MAXM1.
LM R15,R2,INIT Set R15 = maximum number of MVC
* instructions (MAXM1 = 16),
* R0 = number of entries of array,
* R1 = address of 'FROM' array, and
* R2 = address of 'TO' array.
*
* The loop starts here.
LOOP EQU * Define LOOP label.
* At this point, R15 will always contain the number 16 (MAXM1).
SR R15,R0 Subtract the remaining number of
* entries in the array (R0) from R15.
BNP ALL If R15 is not positive, meaning we
* have more than 16 remaining entries
* in the array, jump to do the entire
* MVC sequence and then repeat.
*
* Calculate an offset (from start of MVC sequence) for unconditional branch to
* the 'unwound' MVC loop below.
* If the number of remaining entries in the arrays is zero, R15 will be 16, so
* all the MVC instructions will be bypassed.
MH R15,=AL2(ILEN) Multiply R15 by the length of one
* MVC instruction.
B ALL(R15) Jump to ALL+R15, the address of the
* calculated specific MVC instruction
* with drop through to the rest of them.
*
* MVC instruction 'table'.
* First entry has maximum allowable offset with single register = hexadecimal F00
* (15*256) in this example.
* All 16 of the following MVC ('move character') instructions use base-plus-offset
* addressing and each to/from offset decreases by the length of one array element
* (256). This avoids pointer arithmetic being required for each element up to a
* maximum permissible offset within the instruction of hexadecimal FFF
* (15*256+255). The instructions are in order of decreasing offset, so the last
* element in the set is moved first.
ALL MVC 15*256(100,R2),15*256(R1) Move 100 bytes of 16th entry from
* array 1 to array 2 (with
* drop-through).
ILEN EQU *-ALL Set ILEN to the length of the previous
* MVC instruction.
MVC 14*256(100,R2),14*256(R1) Move 100 bytes of 15th entry.
MVC 13*256(100,R2),13*256(R1) Move 100 bytes of 14th entry.
MVC 12*256(100,R2),12*256(R1) Move 100 bytes of 13th entry.
MVC 11*256(100,R2),11*256(R1) Move 100 bytes of 12th entry.
MVC 10*256(100,R2),10*256(R1) Move 100 bytes of 11th entry.
MVC 09*256(100,R2),09*256(R1) Move 100 bytes of 10th entry.
MVC 08*256(100,R2),08*256(R1) Move 100 bytes of 9th entry.
MVC 07*256(100,R2),07*256(R1) Move 100 bytes of 8th entry.
MVC 06*256(100,R2),06*256(R1) Move 100 bytes of 7th entry.
MVC 05*256(100,R2),05*256(R1) Move 100 bytes of 6th entry.
MVC 04*256(100,R2),04*256(R1) Move 100 bytes of 5th entry.
MVC 03*256(100,R2),03*256(R1) Move 100 bytes of 4th entry.
MVC 02*256(100,R2),02*256(R1) Move 100 bytes of 3rd entry.
MVC 01*256(100,R2),01*256(R1) Move 100 bytes of 2nd entry.
MVC 00*256(100,R2),00*256(R1) Move 100 bytes of 1st entry.
*
S R0,MAXM1 Reduce the number of remaining entries
* to process.
BNPR R14 If no more entries to process, return
* to address in R14.
AH R1,=AL2(16*256) Increment 'FROM' array pointer beyond
* first set.
AH R2,=AL2(16*256) Increment 'TO' array pointer beyond
* first set.
L R15,MAXM1 Reload the maximum number of MVC
* instructions per batch into R15
* (destroyed by the calculation in the
* first instruction of the loop).
B LOOP Execute loop again.
*
* Static constants and variables (these could be passed as parameters, except
* MAXM1).
INIT DS 0A 4 addresses (pointers) to be
* pre-loaded with the 'LM' instruction
* in the beginning of the program.
MAXM1 DC A(16) Maximum number of MVC instructions
* executed per batch.
N DC A(50) Number of actual entries in array (a
* variable, set elsewhere).
DC A(FROM) Address of start of array 1
* ("pointer").
DC A(TO) Address of start of array 2
* ("pointer").
*
* Static arrays (these could be dynamically acquired).
FROM DS 50CL256 Array of 50 entries of 256 bytes each.
TO DS 50CL256 Array of 50 entries of 256 bytes each.
Neste exemplo, aproximadamente 202 instruções seriam necessárias com um loop "convencional" (50 iterações), enquanto o código dinâmico acima exigiria apenas cerca de 89 instruções (ou uma economia de aproximadamente 56%). Se a matriz consistisse em apenas duas entradas, ela ainda seria executada aproximadamente ao mesmo tempo que o loop desenrolado original. O aumento no tamanho do código é de apenas cerca de 108 bytes - mesmo se houver milhares de entradas no array.
É claro que técnicas semelhantes podem ser usadas onde várias instruções estão envolvidas, desde que o comprimento da instrução combinada seja ajustado de acordo. Por exemplo, neste mesmo exemplo, se for necessário limpar o resto de cada entrada da matriz para nulos imediatamente após o campo de 100 bytes copiado, uma instrução de limpeza adicional,, XC xx*256+100(156,R1),xx*256+100(R2) pode ser adicionada imediatamente após cada MVC na sequência (onde xx corresponde a valor no MVC acima dele).
É, claro, perfeitamente possível gerar o código acima "inline" usando uma única instrução de macro assembler , especificando apenas quatro ou cinco operandos (ou alternativamente, torná-lo uma sub-rotina de biblioteca, acessada por uma simples chamada, passando uma lista de parâmetros), tornando a otimização facilmente acessível.
Exemplo C
O exemplo que se segue demonstra desdobramento de loop dinâmico para um simples programa escrito em C . Ao contrário do exemplo do montador acima, a aritmética de ponteiro / índice ainda é gerada pelo compilador neste exemplo porque uma variável (i) ainda é usada para endereçar o elemento da matriz. A otimização completa só é possível se índices absolutos forem usados nas instruções de substituição.
#include <stdio.h>
/* The number of entries processed per loop iteration. */
/* Note that this number is a 'constant constant' reflecting the code below. */
#define BUNCHSIZE (8)
int main(void)
{
int i = 0; /* counter */
int entries = 50; /* total number to process */
int repeat; /* number of while repetitions*/
int left = 0; /* remainder (process later) */
/* If the number of elements is not be divisible by BUNCHSIZE, */
/* get repeat times required to do most processing in the while loop */
repeat = (entries / BUNCHSIZE); /* number of times to repeat */
left = (entries % BUNCHSIZE); /* calculate remainder */
/* Unroll the loop in 'bunches' of 8 */
while (repeat--)
{
printf("process(%d)\n", i );
printf("process(%d)\n", i + 1);
printf("process(%d)\n", i + 2);
printf("process(%d)\n", i + 3);
printf("process(%d)\n", i + 4);
printf("process(%d)\n", i + 5);
printf("process(%d)\n", i + 6);
printf("process(%d)\n", i + 7);
/* update the index by amount processed in one go */
i += BUNCHSIZE;
}
/* Use a switch statement to process remaining by jumping to the case label */
/* at the label that will then drop through to complete the set */
switch (left)
{
case 7 : printf("process(%d)\n", i + 6); /* process and rely on drop
through */
case 6 : printf("process(%d)\n", i + 5);
case 5 : printf("process(%d)\n", i + 4);
case 4 : printf("process(%d)\n", i + 3);
case 3 : printf("process(%d)\n", i + 2);
case 2 : printf("process(%d)\n", i + 1); /* two left */
case 1 : printf("process(%d)\n", i); /* just one left to process */
case 0 : ; /* none left */
}
}
A duplicação de código pode ser evitada escrevendo as duas partes juntas, como no dispositivo de Duff .
Exemplo de desenrolamento de loop de linguagem assembly C para MIPS
O exemplo a seguir calculará um produto escalar de dois vetores A e B de 100 entradas do tipo double . Aqui está o código em C:
double dotProduct = 0;
for (int i = 0; i < 100; i++) {
dotProduct += A[i]*B[i];
}
Conversão para linguagem assembly MIPS
A seguir está o código de montagem MIPS que calculará o produto escalar de dois vetores de 100 entradas, A e B, antes de implementar o desenrolamento do loop. O código abaixo omite as inicializações de loop:
- Inicialize a contagem do loop ($ 7) para 100.
- Inicialize o produto escalar ($ f10) para 0.
A[i]Ponteiro de inicialização ($ 5) para o endereço base deA.B[i]Ponteiro de inicialização ($ 6) para o endereço base deB.
Observe que o tamanho de um elemento dos arrays (a double ) é de 8 bytes.
loop3:
l.d $f10, 0($5) ; $f10 ← A[i]
l.d $f12, 0($6) ; $f12 ← B[i]
mul.d $f10, $f10, $f12 ; $f10 ← A[i]*B[i]
add.d $f8, $f8, $f10 ; $f8 ← $f8 + A[i]*B[i]
addi $5, $5, 8 ; increment pointer for A[i] by the size
; of a double.
addi $6, $6, 8 ; increment pointer for B[i] by the size
; of a double.
addi $7, $7, -1 ; decrement loop count
test:
bgtz $7, loop3 ; Continue if loop count > 0
Desenrolando o Loop no MIPS
O seguinte é igual ao anterior, mas com o desenrolamento do loop implementado a um fator de 4. Observe novamente que o tamanho de um elemento dos arrays (a double ) é de 8 bytes; assim, os 0, 8, 16, 24 deslocamentos e os 32 deslocamentos em cada loop.
loop3:
l.d $f10, 0($5) ; iteration with displacement 0
l.d $f12, 0($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
l.d $f10, 8($5) ; iteration with displacement 8
l.d $f12, 8($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
l.d $f10, 16($5) ; iteration with displacement 16
l.d $f12, 16($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
l.d $f10, 24($5) ; iteration with displacement 24
l.d $f12, 24($6)
mul.d $f10, $f10, $f12
add.d $f8, $f8, $f10
addi $5, $5, 32
addi $6, $6, 32
addi $7, $7, -4
test:
bgtz $7, loop3 ; Continue loop if $7 > 0
Veja também
Referências
Leitura adicional
- Kennedy, Ken; Allen, Randy (2001). Otimizando compiladores para arquiteturas modernas: uma abordagem baseada em dependência . Morgan Kaufmann. ISBN 1-55860-286-0 .
links externos
- Capítulo 7, páginas 8 a 10 , de Michael Abrash do gráfico de programação Black Book é de cerca de desdobramento de loop, com um exemplo em x86 montagem.
- Loop Unrolling generalizado , fornece uma introdução concisa.
- Otimizando sub-rotinas em linguagem assembly Manual de otimizações de Agner Fog com a técnica de desenrolamento de loop (2012).