Rápido 4x4 Matrix Multiplicação em C
https://stackoverflow.com/questions/1674005
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou tentando encontrar uma implementação otimizada C ou Assembler de uma função que multiplica duas matrizes 4x4 com o outro. A plataforma é um iPhone baseado ARM6 ou ARM7 ou iPod.
Atualmente, estou usando uma abordagem bastante normal -. Apenas um pouco de loop-desenrolado
#define O(y,x) (y + (x<<2))
static inline void Matrix4x4MultiplyBy4x4 (float *src1, float *src2, float *dest)
{
*(dest+O(0,0)) = (*(src1+O(0,0)) * *(src2+O(0,0))) + (*(src1+O(0,1)) * *(src2+O(1,0))) + (*(src1+O(0,2)) * *(src2+O(2,0))) + (*(src1+O(0,3)) * *(src2+O(3,0)));
*(dest+O(0,1)) = (*(src1+O(0,0)) * *(src2+O(0,1))) + (*(src1+O(0,1)) * *(src2+O(1,1))) + (*(src1+O(0,2)) * *(src2+O(2,1))) + (*(src1+O(0,3)) * *(src2+O(3,1)));
*(dest+O(0,2)) = (*(src1+O(0,0)) * *(src2+O(0,2))) + (*(src1+O(0,1)) * *(src2+O(1,2))) + (*(src1+O(0,2)) * *(src2+O(2,2))) + (*(src1+O(0,3)) * *(src2+O(3,2)));
*(dest+O(0,3)) = (*(src1+O(0,0)) * *(src2+O(0,3))) + (*(src1+O(0,1)) * *(src2+O(1,3))) + (*(src1+O(0,2)) * *(src2+O(2,3))) + (*(src1+O(0,3)) * *(src2+O(3,3)));
*(dest+O(1,0)) = (*(src1+O(1,0)) * *(src2+O(0,0))) + (*(src1+O(1,1)) * *(src2+O(1,0))) + (*(src1+O(1,2)) * *(src2+O(2,0))) + (*(src1+O(1,3)) * *(src2+O(3,0)));
*(dest+O(1,1)) = (*(src1+O(1,0)) * *(src2+O(0,1))) + (*(src1+O(1,1)) * *(src2+O(1,1))) + (*(src1+O(1,2)) * *(src2+O(2,1))) + (*(src1+O(1,3)) * *(src2+O(3,1)));
*(dest+O(1,2)) = (*(src1+O(1,0)) * *(src2+O(0,2))) + (*(src1+O(1,1)) * *(src2+O(1,2))) + (*(src1+O(1,2)) * *(src2+O(2,2))) + (*(src1+O(1,3)) * *(src2+O(3,2)));
*(dest+O(1,3)) = (*(src1+O(1,0)) * *(src2+O(0,3))) + (*(src1+O(1,1)) * *(src2+O(1,3))) + (*(src1+O(1,2)) * *(src2+O(2,3))) + (*(src1+O(1,3)) * *(src2+O(3,3)));
*(dest+O(2,0)) = (*(src1+O(2,0)) * *(src2+O(0,0))) + (*(src1+O(2,1)) * *(src2+O(1,0))) + (*(src1+O(2,2)) * *(src2+O(2,0))) + (*(src1+O(2,3)) * *(src2+O(3,0)));
*(dest+O(2,1)) = (*(src1+O(2,0)) * *(src2+O(0,1))) + (*(src1+O(2,1)) * *(src2+O(1,1))) + (*(src1+O(2,2)) * *(src2+O(2,1))) + (*(src1+O(2,3)) * *(src2+O(3,1)));
*(dest+O(2,2)) = (*(src1+O(2,0)) * *(src2+O(0,2))) + (*(src1+O(2,1)) * *(src2+O(1,2))) + (*(src1+O(2,2)) * *(src2+O(2,2))) + (*(src1+O(2,3)) * *(src2+O(3,2)));
*(dest+O(2,3)) = (*(src1+O(2,0)) * *(src2+O(0,3))) + (*(src1+O(2,1)) * *(src2+O(1,3))) + (*(src1+O(2,2)) * *(src2+O(2,3))) + (*(src1+O(2,3)) * *(src2+O(3,3)));
*(dest+O(3,0)) = (*(src1+O(3,0)) * *(src2+O(0,0))) + (*(src1+O(3,1)) * *(src2+O(1,0))) + (*(src1+O(3,2)) * *(src2+O(2,0))) + (*(src1+O(3,3)) * *(src2+O(3,0)));
*(dest+O(3,1)) = (*(src1+O(3,0)) * *(src2+O(0,1))) + (*(src1+O(3,1)) * *(src2+O(1,1))) + (*(src1+O(3,2)) * *(src2+O(2,1))) + (*(src1+O(3,3)) * *(src2+O(3,1)));
*(dest+O(3,2)) = (*(src1+O(3,0)) * *(src2+O(0,2))) + (*(src1+O(3,1)) * *(src2+O(1,2))) + (*(src1+O(3,2)) * *(src2+O(2,2))) + (*(src1+O(3,3)) * *(src2+O(3,2)));
*(dest+O(3,3)) = (*(src1+O(3,0)) * *(src2+O(0,3))) + (*(src1+O(3,1)) * *(src2+O(1,3))) + (*(src1+O(3,2)) * *(src2+O(2,3))) + (*(src1+O(3,3)) * *(src2+O(3,3)));
};
Será que eu benefício de usar o Straßen- ou o algoritmo de Coppersmith-Winograd?
Solução
Não, o Strassen ou algoritmo Coppersmith-Winograd não faria muita diferença aqui. Eles começam a pagar apenas para matrizes maiores.
Se a sua matriz de multiplicação é realmente um gargalo que você poderia reescrever o algoritmo usando instruções SIMD NEON. Isso seria apenas ajuda para ARMv7 como ARMv6 não tem esta extensão embora.
Eu esperaria uma aceleração fator 3 sobre o C-código compilado para o seu caso.
EDIT: Você pode encontrar uma boa implementação em ARM-NEON aqui: http: // código .google.com / p / math-neon /
Para o seu código C, há duas coisas que você poderia fazer para acelerar o código:
-
Do not linha da função. Sua multiplicação de matrizes gera um pouco de código, como é desenrolado, ea ARM tem apenas um cache de instrução muito pequena. inlining excessiva pode tornar o código mais lento porque a CPU será código de carregamento ocupado no cache em vez de executá-lo.
-
Use a restringir palavra-chave para dizer ao compilador que os ponteiros Source- e de destino não se sobrepõem na memória. Atualmente o compilador é forçado para recarregar a cada valor de origem da memória sempre que um resultado é escrito porque tem que assumir que a origem eo destino podem se sobrepor ou mesmo apontam para a mesma memória.
Outras dicas
Apenas picuinhas. Eu me pergunto por que as pessoas ainda ofuscar seu código voluntarly? C já é difícil de ler, não há necessidade de adicionar a ele.
static inline void Matrix4x4MultiplyBy4x4 (float src1[4][4], float src2[4][4], float dest[4][4])
{
dest[0][0] = src1[0][0] * src2[0][0] + src1[0][1] * src2[1][0] + src1[0][2] * src2[2][0] + src1[0][3] * src2[3][0];
dest[0][1] = src1[0][0] * src2[0][1] + src1[0][1] * src2[1][1] + src1[0][2] * src2[2][1] + src1[0][3] * src2[3][1];
dest[0][2] = src1[0][0] * src2[0][2] + src1[0][1] * src2[1][2] + src1[0][2] * src2[2][2] + src1[0][3] * src2[3][2];
dest[0][3] = src1[0][0] * src2[0][3] + src1[0][1] * src2[1][3] + src1[0][2] * src2[2][3] + src1[0][3] * src2[3][3];
dest[1][0] = src1[1][0] * src2[0][0] + src1[1][1] * src2[1][0] + src1[1][2] * src2[2][0] + src1[1][3] * src2[3][0];
dest[1][1] = src1[1][0] * src2[0][1] + src1[1][1] * src2[1][1] + src1[1][2] * src2[2][1] + src1[1][3] * src2[3][1];
dest[1][2] = src1[1][0] * src2[0][2] + src1[1][1] * src2[1][2] + src1[1][2] * src2[2][2] + src1[1][3] * src2[3][2];
dest[1][3] = src1[1][0] * src2[0][3] + src1[1][1] * src2[1][3] + src1[1][2] * src2[2][3] + src1[1][3] * src2[3][3];
dest[2][0] = src1[2][0] * src2[0][0] + src1[2][1] * src2[1][0] + src1[2][2] * src2[2][0] + src1[2][3] * src2[3][0];
dest[2][1] = src1[2][0] * src2[0][1] + src1[2][1] * src2[1][1] + src1[2][2] * src2[2][1] + src1[2][3] * src2[3][1];
dest[2][2] = src1[2][0] * src2[0][2] + src1[2][1] * src2[1][2] + src1[2][2] * src2[2][2] + src1[2][3] * src2[3][2];
dest[2][3] = src1[2][0] * src2[0][3] + src1[2][1] * src2[1][3] + src1[2][2] * src2[2][3] + src1[2][3] * src2[3][3];
dest[3][0] = src1[3][0] * src2[0][0] + src1[3][1] * src2[1][0] + src1[3][2] * src2[2][0] + src1[3][3] * src2[3][0];
dest[3][1] = src1[3][0] * src2[0][1] + src1[3][1] * src2[1][1] + src1[3][2] * src2[2][1] + src1[3][3] * src2[3][1];
dest[3][2] = src1[3][0] * src2[0][2] + src1[3][1] * src2[1][2] + src1[3][2] * src2[2][2] + src1[3][3] * src2[3][2];
dest[3][3] = src1[3][0] * src2[0][3] + src1[3][1] * src2[1][3] + src1[3][2] * src2[2][3] + src1[3][3] * src2[3][3];
};
Você tem certeza que seu código desenrolado é mais rápido do que a abordagem baseada em loop explícita? Mente que os compiladores são geralmente melhor do que os seres humanos realizando otimizações!
Na verdade, eu apostaria há mais chances para um compilador para emitir instruções SIMD automaticamente a partir de um circuito bem escrito do que de uma série de declarações "não relacionadas" ...
Você também pode especificar os tamanhos matrizes na declaração argumento. Então você pode usar a sintaxe suporte normais para acessar os elementos, e também pode ser uma boa dica para o compilador para fazer suas otimizações também.
São estas matrizes arbitrárias ou que eles têm quaisquer simetrias? Se assim for, essas simetrias pode muitas vezes para explorados para melhorar o desempenho (por exemplo, em matrizes de rotação).
Além disso, concordo com fortran acima, e iria fazer alguns testes de tempo para verificar se o seu código desenrolado mão é mais rápido do que um compilador de otimização pode criar. No mínimo, você pode ser capaz de simplificar o seu código.
Paul
O seu produto tradicional e completamente desenrolado é provável muito rápido.
Sua matriz é muito pequeno para superar a Overheard de gerir uma multiplicação Strassen em sua forma tradicional, com índices explícitas e código de particionamento; você provavelmente perder qualquer efeito sobre a otimização para que a sobrecarga.
Mas se você quiser rápido, eu usaria instruções SIMD se eles estiverem disponíveis. Eu ficaria surpreso se os chips ARM estes dias não tê-los. Se o fizerem, você pode gerenciar todos os produtos em linha / colum em uma única instrução; se o SIMD é 8 de largura, que você pode gerenciar 2 multiplica linha / coluna em uma única instrução. Definir os operandos até fazer que a instrução pode exigir alguma dança ao redor; instruções SIMD será fácil pegar suas linhas (valores adjacentes), mas não vai pegar as colunas (não contíguas). E isso pode levar algum esforço para calcular a soma dos produtos em uma linha / coluna.
