Módulo IV
Técnicas de Otimização I
Otimizações Gerais usando uma Linguagem Compilada
Computação de Constantes no Laço
LoopInvar(int size,int step,int ratio)
{
int gradient;
for ( i = 0; i < size/step; i += step )
{
gradient = step*ratio;
sort[i] *= gradient;
}
Este cálculo é uma
return;
}
O compilador
não consegue
otimizar esta
operação, assim
temos um valor
constante sendo
calculado
sempre e sem
necessidade
constante, mas o
compilador o trata como
uma equação qualquer,
processando-a a cada
iteração no laço
Computação de Constantes em Laços
LoopInvar(int size,int step,int ratio)
{
int gradient;
int limit;
gradient = step * ratio;
limit = size/step;
for ( i = 0; i < limit; i += step )
{
sort[i] *= gradient;
}
return;
}
Uso de variáveis
temporárias pode
ajudar o
compilador na
otimização do
código
Computação de Constantes em Laços: Desvios (Branches)
InvarBranch(int size, int mode, int offset){
for (int i = 0; i < size; i += 1)
if (mode & DIV_OFST)
data[i] /= offset;
else
data[i] += offset;
return;
}
Desvios no código não
combinam com
desempenho, então
por que fazer um
desvio a cada passo
dentro do laço?
O valor de mode pode mudar a
cada chamada dessa função, mas
não dentro do laço. Uma vez
dentro do laço, toda iteração é
igual, não precisamos do desvio
Computação de Constantes em Laços: Desvios (Branches)
InvarBranch(int size, int mode, int offset) {
if (mode & DIV_OFST)
for (i = 0; i < size; i += 1)
data[i] /= offset;
else
for (i = 0; i < size; i += 1)
data[i] += offset;
return;
}
Mais código,
menos intuitivo
e mais rápido!
Laços com Contagem: Decrementando em um Laço
CountDown(int size) {
int i;
for (i = 0; i < size; i++)
array[i] = 0;
return;
}
É mais simples para
o processador
comparar a variável i
com zero!
Laços com Contagem: Um Solução
CountDown(int size) {
int i;
for (i = size-1; i >= 0; i--)
array[i] = 0;
return;
}
A comparação com
zero é mais eficiente,
no decremento ao
passar por zero o
indicador de zero do
processador é ativado,
nenhuma comparação
é necessária com outro
valor para resolver
esta condição
Agrupando Variáveis
int ClusterVar( int offset, int ratio, int size) {
int i, gradient, delta;
gradient = offset * ratio;
gradient é calculado
pelos valores de offset
e ratio
for (i = 0; i < size; i++)
array[i] = 0;
delta = offset – ratio;
return delta + gradiente;
}
delta também é
calculado pelos
valores de offset e
ratio
Agrupando Variáveis de maneira Eficiente
int ClusterVar(int offset, int ratio, int size){
int i, gradient, delta;
for ( i = 0; i < size; i++)
array[i] = 0;
gradient = offset * ratio;
delta = offset – ratio;
return delta + gradiente;
}
A utilização agrupada
das variáveis facilita a
tarefa de otimização
ao compilador
Interpretando e Simplificando uma Função
int IsEven(int value) {
int result;
result = value / 2;
if (result * 2 == value)
return 1;
else
return 0;
}
O objetivo desta
função é determinar
se o parâmetro é par.
Se for retorna 1.
Uma Solução mais Simples
int IsEven(int value) {
return !(value & 0x1);
}
Toda representação
binária de um número
par termina com zero e
esta função utiliza esse
fato
Simplificando ainda mais
__inline int IsEven(int value)
{
return (~value)&0x1;
}
Agora a função é tão
simples que devemos
considerar o uso de
inline ou macro
Inlining
 Otimização muito oportuna para eliminar a sobrecarga
da chamada e do retorno de uma função
int IsEven(int value)
int IsEven(int value)
{
int result;
Simplificando
{
return (~value)&0x1;
}
result = value / 2;
if ( result * 2 == value )
{
return 1;
}
else
{
return 0;
}
}
Usando __inline na função
__inline int IsEven(int value)
{
return (~value)&0x1;
}
Ponteiros: Indexação
BasePtr(int *ptr, int *cmask, int section, int limit) {
int i;
for (i = 0; i < limit; i++) {
*(ptr + section * secsize + i) &= *cmask;
cmask++;
}
return;
}
Uma parte do cálculo
deste ponteiro não
varia dentro deste
laço, logo é possível
implementações mais
eficientes
Ponteiros: Indexação
BasePtr(int
Poderíamos ir
além dessa
otimização?
*ptr, int *cmask, int section, int limit)
{
int *auxptr, i;
auxptr = ptr + section * secsize;
for (i = 0; i < limit; i++) {
*(auxptr + i ) &= *cmask;
cmask++;
}
return;
}
Calculando a parte do
ponteiro que é
independente de
qualquer valor do laço,
resta uma parte de
cálculo bem mais
simples para ser
executada dentro dele.
Ponteiros: Mais otimizações
int BasePtr(int *ptr,int *cmask,
int section,int limit)
{
int i;
Ajustamos nossos
ponteiros para o último
elemento, assim podemos
contar decrementando
int *auxptr;
auxptr = ptr + section * secsize;
auxptr += limit – 1;
cmask += limit – 1;
Fazer o laço decrementar
até zero tira vantagem do
conjunto de instruções do
processador ARM
for ( i = limit - 1; i >=; 0 i-- )
*(auxptr--) &= *(cmask--);
return;
}
Pós-decremento dos
ponteiros torna mais fácil
para o compilador o uso de
instruções de load/store
com pós-decremento.
Redução de Desvios (Branches)
Void MultBranch(void) {
//iniciação de mask e shiftbits
if (mode & TRANSPNT ) {
Iniciação de
shiftbits e
mask
mask = 0x0110;
shiftbits = 4;
} else {
Iniciação
de limit
mask = 0x1100;
shiftbits = 8;
}
//ajustando limite
limit = 5;
if (mode & TRANSPNT) limit = 9;
...
Existe
alguma
maneira de
reduzirmos
os ifs e os
desvio?
Redução de Desvios (Branches)
void MultBranch(void) {
//iniciação de mask, shiftbits e limit
if (mode & TRANSPNT ) {
limit = 5;
mask = 0x0110;
shiftbits = 4;
Iniciação de shiftbits e
mask, além de alterar o
valor de limit, tudo em
um só if.
} else {
limit = 9;
mask = 0x1100;
shiftbits = 8;
}
...
Evitar
desvios em
um código é
uma prática
saudável!
Localidade de Referência de Memória
int Image[128][128];
void ImageFilter(void) {
Estamos percorrendo a
matriz imagem pela
coluna, embora ela
seja armazenada na
memória em função de
suas linhas
int i, j, k, sum;
// Percorre as colunas
for ( i = 0; i < 128; i++ ) {
sum = 0;
for ( j = 0; j < 128; j++ ) {
sum = 0;
for ( k = 0; k < 8; k++ ) {
sum += Image[j][i] * filter[j];
}
Image[j][i] = sum;
}
}
}
// Percorre as linhas
for ( i = 0; i < 128; i++ )
Pensando como os dados são
armazenados na cache vemos
que essa não é uma boa maneira
de se trabalhar com um array...
Localidade de Referência de Memória
TransmuteArray(Image,0);
for ( i = 0; i < 128; i++ ) {
sum = 0;
for ( j = 0; j < 128; j++ ) {
sum = 0;
for ( k = 0; k < 8; k++ )
Reordene a matriz
antes de processá-la
de maneira a transpor
as linhas pelas
colunas. Depois reprocesse novamente a
matriz
sum += Image[i][j] * filter[j];
Image[i][j] = sum;
}
}
TransmuteArray(Image,1);
Essa é uma maneira
muito mais eficiente de
se percorrer a matriz
Uso Eficiente de Bibliotecas
void OutputMethod(HANDLE JavaSource, HANDLE JavaBin)
{
unsigned char BCode;
int EndMethod;
EndMethod = 0;
A rotina write é
chamada para todos os
bytecodes pela JIT
while( !EndMethod )
{
EndMethod =
GenByteCode(JavaSource, &BCode);
write(JavaBin,&BCode,1);
}
}
A função write realiza
várias verificações no
handle do arquivo e no
seu estado (e faz isso a
cada chamada da
função) Ela pode
armazenar ou não as
escritas internamente
Uso Eficiente de Bibliotecas - Otimização
#define BSIZE 128
EndMethod = GenByteCode(JavaSource,
void OutputMethod(
HANDLE JavaSource,
HANDLE JavaBin)
&BCode);
*pBuff++ = BCode;
if (BuffLeft-- <= 0 )
{
{
write(JavaBin,buffer,BSIZE);
unsigned char *pBuff;
BuffLeft = BSIZE;
unsigned char buffer[BSIZE];
pBuff = buffer;
int BuffLeft;
int EndMethod;
/* write out bytecodes till
we reach the end of method */
EndMethod = 0;
}
} // end of while…
if ( BuffLeft < BSIZE )
{
write(JavaBin,buffer,
pBuff = buffer;
BuffLeft = BSIZE;
while( !EndMethod )
{
BSIZE – BuffLeft);
}
} // end of function OutputMethod
Uso Eficiente de Bibliotecas - Otimização
Agora a função write é
usada muito mais
eficientemente
EndMethod = GenByteCode(JavaSource,
&BCode);
*pBuff++ = BCode;
if (BuffLeft-- <= 0 )
{
Observe esse ponteiro
pós-incrementado: Uma
única instrução assembly
STR é capaz de
armazenar e atualizar o
ponteiro
write(JavaBin,buffer,BSIZE);
BuffLeft = BSIZE;
pBuff = buffer;
}
} // end of while…
if ( BuffLeft < BSIZE )
{
write(JavaBin,buffer,
Veja que a variável
BuffLeft é decrementada
até Zero
BSIZE – BuffLeft);
}
} // end of function OutputMethod
Uso Eficiente de Bibliotecas
 Use cada função com mais eficiência, pois fazer
menos chamadas implica:
 Menor sobrecarga da chamada da função
 Menor sobrecarga de verificação de erros
 Menos acessos a dispositivos físicos
 Compreenda as limitações dos dispositivos
 Eficiência na escrita em Flash
 Limitação da Biblioteca
Desenrolamento de Laço
void LoopUnRoll(int limit,int translate)
int i;
for ( i = 0; i < limit, i++ ) {
{
De 2 a 3 instruções a
cada iteração do laço do
for
array[i] += translate;
}
De 3 a 4 instruções para
executar o corpo do laço
}
A sobrecarga para
percorrer o laço prejudica
o desempenho!
Implementação do Desenrolamento de Laço
void LoopUnRoll(int limit,int translate)
int i;
{
De 2 a 3 instruções a cada
iteração do laço do for
for ( i = 0; i < limit, i += 4 ) {
array[i] += translate;
array[i + 1] += translate;
array[i + 2] += translate;
array[i + 3] += translate;
De 12 a 16 instruções para
executar o corpo do laço
}
}
E a escrita consegutiva para dados contíguos pode
aproveitar mais uma característica do processador
XScale: Write Coalescing
Usando Comentários no Código como Técnica de Medição
 Se você gostaria de saber o quanto uma linha
ou pedaço de código contribuem para o
desempenho de execução de uma função...
 Considere comentar a linha ou bloco de código a ser
analisado.
 Tenha certeza que o código ao redor não é
demasiadamente sem importância a ponto do
otimizador do compilador simplesmente descartá-lo.
 Substitua algo muito simples que o compilador não
possa otimizar.
Usando Comentários no Código como Técnica de Medição
Sx = 0;
for ( col = 0; col < numCols; col++) {
Exemplo:
for ( row = 3; row < (numRows – 3);row++) {
ploc1 = in + (row*numCols + col);
ploc2 = ploc1 + 1;
Comente a linha que
contém sqrt
Substitua esta linha
com algo que evite que
o compilador altere
drasticamente o código
compilado.
Kr = ((*(ploc1-adj3) ...
Ks = ((*(ploc2 – adj3)....
}
if (Kr < 0 ) Kr = -Kr;
if (Ks < 0 ) Ks = -Ks;
// Sx += (S16Word)sqrt( Kr +Ks );
Sx += Kr + Ks;
}
Módulo IV
Técnicas de Otimização II
O que é PreLoad?
 PreLoad coloca o dado a ser utilizado
processador dentro da memória cache.
pelo
 Suporte na extensão ARM .v5 DSP do compilador
Microsoft na versão 4.0
 Dado um endereço, o PreLoad inicia a carga dos 32
bytes da memória que inclui o endereço para a
memória cache.
O que é PreLoad?
 Os 5 bits inferiores de endereço são ignorados, desde
que as linhas da cache são alinhadas em 32 bytes.
 Não há o conceito de largura. Não se pode carregar o
conteúdo de um valor de tamanho maior que 32 bytes
usando PreLoad, pois ele ultrapassa o tamanho da
linha de cache (32 bytes).
 Leitura sem atribuição para um registrador de destino,
não ocupa o pend buffer.
 Endereços inválidos de memória não geram exceções,
são ignorados.
Quando o PreLoad é eficiente?
 Quando o processamento de dados contíguos são
repetido dentro de um laço
 Quando o endereço de elementos em uma iteração
posterior são facilmente determinados
 O dado provavelmente não está na cache
 É muito grande em bytes para caber inteiro na cache
 O dado não foi recentemente gerado ou preparado em
outro estágio
Por que usar PreLoad?
 Buscar um dado na memória é uma operação cara
em qualquer tipo de processador
 Dados presentes na memória cache são
manipulados mais rapidamente
 PreLoad busca o dado e o coloca na cache. Se bem
usado, pode economizar tempo do processador na
utilização de um dado da memória
PreLoad irá ajudar?
 Utilize o VTune
Taxa alta de
Cache Miss
Cache Miss
= 28,76%
 Procure por funções onde há uma taxa alta de “cache miss”
Alterações no Código para Incrementar a
Eficiência de PreLoad
 Otimize o uso da Cache
 Os dados devem preferencialmente estar próximos na
memória
 Use dados em posições contíguas de memória
 Para listas encadeadas, onde todos os elementos
estão “embaralhados”
 Use um ponteiro especial que aponta para ‘n’
elementos a frente
Alterações no Código para Incrementar a
Eficiência de PreLoad
 Para matrizes de estruturas onde somente alguns
membros são usados em algum laço
 Faça duas matrizes de estruturas, com os membros mais
usados em uma estrutura e o resto em outra matriz
 Permite que as estruturas com os dados usados mais
freqüentemente fiquem contidas em uma única linha da
memória cache
Ajustando o PreLoad
 Quantos dados devem ser colocados na cache por
“antecipação de uso”?
 Tente usar o método empírico
 Depende da complexidade do código executado no laço
entre sucessivas execuções do PreLoad
 O PreLoad deve carregar os dados na cache com 40 a 80
clocks de instrução antes de usá-los
 Faça do valor de antecipação do PreLoad uma constante
que possa ser alterada no seu código
Eficiência máxima do PreLoad
 Melhor se houve apenas um PreLoad por linha de cache
 (Tempo do processamento por item de dado) * (Número
de itens por linha de cache) deve ser aproximadamente
tempo de acesso externo
 Senão, faça PreLoad
32 conjuntos
no número apropriado
de linhas de cache
Via 0
Linha de cache
 Não exceda 4 linhas
Via 1
Linha de cache
com PreLoad de uma
vez
Ender.
Dados
Via 31
Linha de cache
Eficiência máxima do PreLoad
 Considere que outros dados também receberão acesso
(leitura e escrita à memória). Lembre-se do fill buffer.
 A taxa de alimentação deve ser igual a taxa de consumo
 Se o tempo de processamento por uma linha de cache é
menor do que o tempo entre PreLoads, então é
necessário fazer o PreLoad de um endereço mais a
frente
Riscos ao Usar o PreLoad
 A instrução de PreLoad consome um ciclo de clock, se ele
não melhorar o desempenho, ele poderá piorá-lo
 Evite algoritmos que demandem muito custo
computacional para descobrir qual endereço que o
PreLoad usará
 Não exagere no uso de PreLoad colocando-o em todo o
código, pois ele também usa um buffer de preenchimento
 O processador ficará em espera se o buffer de preenchimento
estiver cheio
Exemplo de PreLoad
Inclua o Protótipo
void __PreLoad(void *ptr);
void UsePreLoad(int array[], int limit) {
int i;
PreLoad chamado para
for (i = 0; i < limit; i++) {
carregar na cache
/*Carrega elemento antecipadamente
elementos do array com 10
10 iterações a frente*/
iterações de antecedência
__PreLoad(&(array[i+10]));
/* Código de processamento do array[i] aqui */
}
return;
}
PreLoad será chamado a cada iteração
do laço mesmo que o elemento do array
já esteja na linha da cache.
Exemplo de PreLoad: Melhoria
void __PreLoad(void *ptr);
void UsePreLoad(int array[], int limit){
int i;
for (i = 0; i < limit; i +=8) {
O laço é estendido para
poder processar todos
/*Carrega elemento antecipadamente
os elementos do vetor
10 iterações a frente*/
que estão presentes na
__PreLoad(&(array[i+10]));
/* código para array[i]*/
linha de cache
/* código para array[i+1]*/
carregada da memória
/* código para array[i+2]*/
/*
/*
/*
/*
/*
código
código
código
código
código
}
return;
}
para
para
para
para
para
array[i+3]*/
array[i+4]*/
array[i+5]*/
array[i+6]*/
array[i+7]*/
Isso reduz o número de
chamadas que são feitas ao
PreLoad com o dado já
presente na linha de cache
Use PreLoad cuidadosamente
 O bom senso é necessário para balancear
 quantos itens estão presentes na linha de cache,
 qual o tempo para processar os elementos na linha de cache
 determinar o futuro uso de memória que PreLoad precisa
carregar
 qual o tempo necessário para a carga da cache
 Se o PreLoad for chamado a cada iteração do laço
carregando linhas da cache não necessárias, junto aos
acessos normais do processamento, poderá resultar em
esperas devido a falta de entradas vazias no buffer de
preenchimento
Módulo IV
Laboratório