Qual é o custo computacional de

Uma das principais questões com as quais temos de lidar em simulações moleculares é o cálculo de forças dependentes da distância. Se pudermos restringir as funções de força e distância para ter potências iguais da distância de separação , podemos calcular o quadrado da distância r 2 = r ⋅ r e não precisar nos preocupar com r . Se existem poderes ímpares, no entanto, precisamos lidar com r = $r$$r^2 = {\bf r \cdot r}$$r$ .$r = \sqrt{r^2}$

Minha pergunta é: quanto custa a computação conforme implementado nas bibliotecas de linguagens comuns (C / C ++, Fortran, Python), etc.? Há realmente muitas melhorias de desempenho ajustando manualmente o código para arquiteturas específicas?$\sqrt{x}$

Como uma extensão da resposta de moyner , o on-chip sqrté geralmente um rsqrt, ou seja, uma raiz quadrada recíproca que calcula . Portanto, se em seu código você usar apenas1/r(se estiver fazendo dinâmica molecular), poderá calculardiretamente e salvar a divisão. A razão pela qualé computada em vez deé que sua iteração de Newton não tem divisões, apenas adições e multiplicações.$a \rightarrow 1/\sqrt{a}$$1/r$r = rsqrt(r2)rsqrtsqrt

Como observação, as divisões também são computadas iterativamente e são quase tão lentas quanto rsqrtno hardware. Se você procura eficiência, é melhor tentar remover divisões supérfluas.

Algumas arquiteturas mais modernas, como as arquiteturas POWER da IBM, não fornecem rsqrtper se, mas uma estimativa precisa de alguns bits, por exemplo, FRSQRTE . Quando um usuário chama rsqrt, isso gera uma estimativa e, em seguida, uma ou duas (quantas forem necessárias) iterações do algoritmo de Newton ou Goldschmidt usando multiplicações e adições regulares. A vantagem dessa abordagem é que as etapas da iteração podem ser canalizadas e intercaladas com outras instruções sem bloquear a FPU (para uma visão geral muito boa desse conceito, embora em arquiteturas mais antigas, consulte a tese de doutorado de Rolf Strebel ).

Para potenciais de interação, a sqrtoperação pode ser totalmente evitada usando um interpolante polinomial da função potencial, mas meu próprio trabalho (implementado em mdcore) nesta área mostra que, pelo menos nas arquiteturas do tipo x86, a sqrtinstrução é rápida o suficiente.

Atualizar

Como essa resposta parece estar recebendo bastante atenção, eu também gostaria de abordar a segunda parte da sua pergunta, ou seja, vale a pena tentar melhorar / eliminar operações básicas como sqrt?

No contexto de simulações de Dinâmica Molecular, ou qualquer simulação baseada em partículas com interações limitadas por corte, há muito a ser ganho com os melhores algoritmos para encontrar vizinhos. Se você estiver usando listas de células , ou algo semelhante, para encontrar vizinhos ou criar uma lista de Verlet , estará computando um grande número de distâncias falsas aos pares. No caso ingênuo, apenas 16% dos pares de partículas inspecionados estarão realmente dentro da distância de corte um do outro. Embora nenhuma interação seja computada para esses pares, o acesso aos dados das partículas e o cálculo da distância espúria dos pares acarreta um custo alto.

Meu próprio trabalho nesta área ( aqui , aqui e aqui ), bem como o de outros (por exemplo, aqui ), mostra como esses cálculos espúrios podem ser evitados. Esses algoritmos de localização de vizinhos até superam as listas Verlet, conforme descrito aqui .

O ponto que quero enfatizar é que, embora possa haver algumas melhorias a serem obtidas com o melhor conhecimento / exploração da arquitetura de hardware subjacente, também existem ganhos potencialmente maiores para repensar os algoritmos de nível superior.

A raiz quadrada é implementada no hardware na maioria dos processadores, ou seja, há instruções de montagem específicas e o desempenho deve ser comparável na maioria dos idiomas, pois é muito difícil estragar a implementação. Você provavelmente nunca será capaz de vencer a instrução FSQRT, pois ela foi projetada por algum designer de hardware inteligente.

O modo como ele é implementado no hardware pode variar, mas provavelmente é algum tipo de iteração de ponto fixo, por exemplo, o método de Newton-Raphson que faz um número específico de iterações até que o número de dígitos necessários seja computado. Os métodos iterativos no hardware são geralmente muito mais lentos do que outras operações, uma vez que vários ciclos precisam ser concluídos antes que o resultado esteja pronto.

Existem também algumas instruções de streaming SIMD que podem ser usadas nos registradores XMM para cálculos vetoriais rápidos, encontrados aqui . Esses registros são relativamente pequenos, mas se você tiver um número conhecido de coordenadas (por exemplo, um sistema de coordenadas cartesianas tridimensionais), elas podem ser um pouco mais rápidas.

Se o seu idioma tiver um nível baixo o suficiente, você sempre poderá converter para uma precisão menor ou usar um número de precisão menor para suas coordenadas. Geralmente, a precisão única é mais do que suficiente e, pelo que me lembro, será mais rápida ao calcular raízes quadradas, pois as iterações podem ser encerradas anteriormente.

Deve ser fácil o suficiente para comparar idiomas diferentes: basta escrever uma longa série de números aleatórios em um arquivo, carregá-lo usando idiomas diferentes e depois cronometrar as raízes quadradas.

Pode haver aprimoramentos de desempenho, mas o primeiro deve ser o perfil para saber que calcular o inverso do sqrt é o gargalo da garrafa (e não, digamos, carregar as posições e salvar as forças).

O projeto GROMACS MD surgiu de uma idéia de explorar os detalhes do formato de ponto flutuante IEEE para propagar um esquema de iteração de Newton-Raphson para calcular uma aproximação aceitável ao recíproco da raiz quadrada (consulte o Apêndice B.3 de http: / /www.gromacs.org/Documentation/Manual ), mas não há CPUs HPC em uso onde o GROMACS ainda usa essa idéia.