Prever tempos de execução para álgebra linear densa

9

Gostaria de prever tempos de execução para operações de álgebra linear densa em uma arquitetura específica usando uma biblioteca específica. Eu gostaria de aprender um modelo que se aproxima da função

$F_{op} \;::\;$ tamanhos de entrada tempo de execução $\rightarrow$

para operações como multiplicação de matrizes, adição por elementos, resolução triangular, etc.

Suspeito que esses tempos de execução sejam principalmente previsíveis devido à regularidade das operações, uma vez que você ultrapassa os tamanhos de problemas que cabem confortavelmente no cache.

Questões:

Essa suposição é realista? É provável que a função de tempo de execução seja quase determinística?
Posso assumir que essa função será polinomial nos tamanhos das entradas? (ou seja, espero que a matriz densa multiplique parecida com para e algum coeficiente escalar) $\alpha n\times k\times m$ $A_{nk}\times B_{km}$ $\alpha$
Existe trabalho preexistente sobre isso em algum lugar?
Meu plano atual é fazer a regressão de mínimos quadrados com um regularizador . Alguma outra sugestão? $L_1$

Editar: para ficar claro, estou procurando tempos de execução, não FLOPs ou qualquer outra métrica de desempenho comum. Estou disposto a me restringir a uma arquitetura específica.

linear-algebra machine-learning MRocklin
fonte

10

Eu tenho trabalhado recentemente exatamente nesse tópico. Você pode dar uma olhada no nosso artigo: http://arxiv.org/abs/1209.2364 .

Por que você está interessado na previsão de tempo de execução de rotinas de álgebra linear? Você pretende usar o modelo para uma determinada finalidade?

Elmar Peise
fonte

Obrigado pelo link. Vou dar uma olhada. Estou interessado nisso, pois suspeito que você seja o mesmo. Seleção e programação automatizadas de algoritmos para expressões matriciais. Muitos problemas impossíveis deveriam ser possíveis nesse domínio altamente regular e previsível.

MRocklin

6

Há muito trabalho preexistente. A maioria dos desenvolvedores de bibliotecas de álgebra linear publica resultados de desempenho em termos de desempenho de ponto flutuante que podem ser convertidos em tempos de execução.

A pesquisa no Google "desempenho DGEMM", por exemplo, gera o seguinte: http://math-atlas.sourceforge.net/timing/3_5_10/index.html .

Geralmente, você pode esperar que as respostas não sejam uniformes. Haverá saltos ou picos nas proximidades de determinados tamanhos de problemas (que estão relacionados aos tamanhos de cache). Você também deve esperar platôs nas taxas e, portanto, nas regiões lineares para uma ampla variedade de tamanhos de problemas. Não espero que ajustes polinomiais sejam muito úteis.

Dado um amplo esforço de benchmarking, pode ser mais fácil tabular resultados e interpolar conforme necessário. Qual é o seu objetivo?

Bill Barth
fonte

11

DGEMM

n^{3}

$n^3$

Converter fracassos em tempos de execução é, na minha experiência, difícil. Eu realmente só me importo com tempos de execução no meu caso. Estou testando a viabilidade do agendamento estático.

21712

Na minha experiência, picos / platôs ocorrem apenas para tamanhos de problemas pequenos. Depois de sair do cache, as coisas ficam bem suaves. Concordo que a adição de funções por partes provavelmente melhoraria o ajuste.

21712 MR12lin12:

Prever tempos de execução para álgebra linear densa

Respostas: