Exercicios
Escrever uma implementação de ponto fixo do gerador Mandelbrot.
a.
Vocará que o desempenho é inconsistente entre diferentes pixels e diferentes frames. Por que isso?
b.
Qual é a intensidade aritmética do corpo do loop mais interno, em operações por byte acessado a partir da memória? Qual é o desempenho correspondente para a sua CPU ARM? Como se compara ao seu desempenho observado?
c.
Medir as seguintes métricas de desempenho para o corpo mais interno do loop:
▪
instruções por iteração
▪
instruções por operação
▪
CPI
▪
cache miss rate
d.
Utilizar a montagem em linha para implementar o corpo mais interno do laço e medir o impacto da performance em relação às métricas da parte c. Qual é a velocidade em relação ao código gerado pelo compilador?
Paralelizar o gerador do conjunto Mandelbrot usando OpenMP. Aplique a diretiva paralela para o laço mais externo (linha).
a.
Medir o número médio de ciclos necessários para cada iteração do laço mais interno (para avaliar o polinômio) para uma rosca e duas roscas para o frame inicial. Use estas medidas para calcular a velocidade, em termos de pixels por segundo, de duas roscas sobre uma thread.
b.
Medir o tempo para calcular todos os pixels no primeiro frame ao usar a programação dinâmica em comparação com a programação estática.
O que torna difícil a aplicação da operação SIMD para o gerador do conjunto Mandelbrot? Qual é o método mais eficiente para aplicar a operação SIMD para o gerador do conjunto Mandelbrot?
Medir a taxa de escrita efetiva para o Framebuffer do Linux. É equivalente à taxa de transferência de escrita para um array de memória alocado a partir do heap?
Calcular a intensidade aritmética do programa de transformação de imagem em operações por pixel. Qual é a sua performance vinculada dada a efetiva taxa de transferência de memória da sua CPU ARM? Como se compara ao seu desempenho observado?
Utilizar OpenMP para adicionar suporte multicondutor ao programa de transformação de imagem de ponto fixo. Para fazer isso, aplique o paralelo para pragma ao laço mais externo (linha).
Measure seu desempenho em uma CPU ARM de quatro núcleos. Como sua performance é escalada quando executada com um, dois, três e quatro threads?
Utilizar intrínsecos para adicionar suporte NEON SIMD à versão de ponto fixo do programa de transformação de imagens. Use operações em quatro direções para calcular os seguintes cálculos para um grupo de quatro pixels: localização do pixel fonte, extração de fração e cálculo de peso. Até que ponto isso melhora o desempenho?
Não podemos otimizar facilmente o programa gerador Mandelbrot usando instruções SIMD, já que os pixels vizinhos podem requerer um número diferente de avaliações polinomiais e cada iteração do polinômio é dependente da avaliação anterior. Uma abordagem alternativa é implementar o loop na montagem em linha, desenrolar por pelo menos quatro, e depois usar o software pipelining para melhorar o CPI do loop. Neste caso, devemos evitar ramificações condicionais dentro do loop desenrolado. Uma vez que os valores c divergentes continuarão a divergir com as avaliações subsequentes, podemos esperar para verificar a condição de saída do loop após cada grupo de quatro iterações. No entanto, realizando avaliações polinomiais adicionais após um Pc() potencialmente divergente fora do círculo do raio-2, será necessário que tenhamos em conta os requisitos de intervalo adicional para o nosso formato de ponto fixo. Recalcular os requisitos de alcance de ponto fixo para esta otimização e determinar até que ponto isso reduzirá o nível máximo de zoom.
As principais vantagens do ponto fixo são a redução na latência de operação e a capacidade de evitar conversões de tipo em certos tipos de códigos gráficos. O capítulo 2 destaca um programa de exemplo cujo desempenho é sensível à latência de operação, o método de Horner. Assumindo que podemos tolerar as limitações de alcance do ponto fixo no código do nosso método de Horner, será que convertendo-o em ponto fixo melhoraria o desempenho? Explique sua resposta.
Secção 3.6.5 mostrou duas implementações diferentes de uma macro de pré-processador de adição de ponto fixo generalizada. A primeira foi gerada pelo gcc sob otimização máxima, a segunda foi codificada manualmente usando linguagem de montagem em linha. Ambas as implementações exigiram aproximadamente o mesmo número de instruções.
a.
Mostrar as dependências de dados de leitura-e-escrita em ambas as implementações. Assumindo que o processador usa uma única instrução, em questão de ordem, e assumindo que a latência de todas as operações aritméticas inteiras é de quatro ciclos, quantos comparam o número de ciclos de espera de dados necessários para ambas as implementações.
b.
Reescrever a versão inline assembly da macro de adição de pontos fixos para agendar as instruções de modo que as instruções dependentes sejam separadas o máximo possível. Até que ponto as paradas são reduzidas, assumindo a latência dada na parte a?
c.
Código de escrita que demonstra como todas as três implementações (compilador gerado, montagem inline e montagem inline programada) podem ser caracterizadas para performance.
Nesta questão nós examinamos a implementação inline assembly da multiplicação generalizada de pontos fixos descrita na Seção 3.6.6.
a.
Como se compara, em termos de número de instruções e performance em tempo de execução, com o código equivalente gerado pelo compilador para:
res = (((long)op1 * (long)op2) >> (rp1>rp2?rp1:rp2)) +(rp1>rp2 ? ((((long long)op1 * (long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long)op2) >> (rp2-1))&1));
Certifique-se de usar as chaves “-O3” e “-marm” ao compilar com o gcc.
b.
Escalonhe as instruções da versão de montagem em linha da macro de multiplicação para minimizar a dependência de dados. Meça seu desempenho em relação à versão dada na Seção 3.6.6.
c.
Para a implementação da montagem inline, quanto mais ao longo do tempo é alcançado se alterada de forma que as posições dos pontos de radix sejam fixas ao invés de variáveis como no código? Para esta questão, use tanto o número de instruções quanto o comportamento real do tempo de execução.
Calcular os valores de pixel para um conjunto Mandelbrot requer uma função para converter a contagem de iteração para os canais de cor R, G e B. Ajustando os três canais para o mesmo valor irá gerar uma imagem cinzenta, assim a inclinação de cada função de canal de cor deve ser única, e qualquer inclinação que seja maior irá determinar a tonalidade da imagem.
Como descrito na Secção 3.8.1, o número de avaliações polinomiais pode exceder o valor que excede a gama de um canal de cor. Para evitar um potencial transbordamento, você deve usar aritmética saturadora ao calcular cada valor de pixel. Desta forma, se o valor calculado exceder o valor máximo permitido, configure-o para o valor máximo.
Escreva uma macro C que executa um multiplicador saturatório de 8 bits sem assinatura. A função tomará dois operandos de 8 bits e produzirá um produto de 8 bits definido para 255 se o produto exceder 255. A macro não deve incluir instruções de ramificação e ser programada para dependências de dados.
Este exercício explorará aumentar a precisão dos tipos de pontos fixos para o gerador Mandelbrot para 64-bit.
a.
Usar uma taxa de zoom de 1,5zoom, até que nível o quadro pode ser ampliado antes de exceder esta precisão?
b.
Definir uma macro em C para adicionar dois (64,56) valores de pontos fixos. A macro pode realizar a adição de 128 bits usando quatro adições de 32 bits e usar a bandeira de transporte para implementar as carretas de cada grupo de 32 bits para o próximo grupo de 32 bits mais significativo.
c.
Definir uma macro em C para multiplicar dois (64,56) valores de ponto fixo. Construa esta macro no topo da macro de 64 bits adicionar macro a partir da parte b.
Como mostrado na Figura 3.6, uma maneira simples de executar uma multiplicação de 64 bits é executar uma série de quatro operações de multiplicação/deslocamento/acumulação de 32 bits que cada uma produz um resultado de 64 bits.
Figure 3.6. Um multiplicador de 8 bits implementado com multiplicadores de 4 bits.
Na figura, dois valores de retenção de 4 bits A e B 1110 e 1410 estão separados em duas porções superiores e inferiores de 2 bits, denominadas A1, A0 e B1 e B0. Assumindo que os produtos são de 4 bits, o produto de 8 bits é calculado como (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Para aplicar isto a uma multiplicação de 64 bits, cada um dos dois valores de 64 bits deve ser mantido em dois registos de 32 bits. Cada multiplicação gera um resultado de 64 bits, permitindo um produto final de 128 bits.
d.
Usando estas macros, implemente um gerador de conjunto Mandelbrot de 64 bits e meça a diferença de desempenho resultante.
e.
Implemente ambas as macros na linguagem de montagem em linha e meça a velocidade do resultado do gerador Mandelbrot em comparação com o da parte d.