Exame de Qualificação: Otimização e Aceleração de rotinas de álgebra Linear com a Técnica de Overthreading

Hora: 14h

Orientadores:
Carla Osthoff Ferreira de Barros - Laboratório Nacional de Computação Científica - LNCC
Sanderson Lincon Gonzaga de Oliveira

Banca Examinadora:
José Karam Filho - Laboratório Nacional de Computação Científica - LNCC (presidente)
Roberto Pinto Souto - Laboratório Nacional de Computação Científica - LNCC
Diego Nunes Brandão - Centro Federal de Educação Tecnológica Celso Suckow da Fonseca - CEFET-RJ

Suplentes:
Renato Simões Silva - Laboratório Nacional de Computação Científica - LNCC

Resumo:

UM DOS MAIORES DESAFIOS DA TECNOLOGIA ATUAL DE COMPUTAÇÃO CIENTÍFICA É DIMINUIR O TEMPO DE EXECUÇÃO ATRAVÉS DA DIVISÃO DO TRABALHO ENTRE OS MÚLTIPLOS NÚCLEOS FÍSICOS DE UMA ARQUITETURA DE MÚLTIPLOS PROC ESSADORES. NÃO É SEMPRE QUE SE CONSEGUE UM GANHO SIGNIFICATIVO DE DESEMPENHO AO SE PARALELIZAR UMA APLICAÇÃO. UM DOS MOTIVOS PARA ISSO É QUE QUANDO O CÓDIGO POSSUI POUCO TRABALHO PARA SER EXECUTADO EM PARALELO OS GASTOS GERADOS PARA GERENCIAR AS MÚLTIPLAS THREADS ACABAM SENDO MAIORES QUE OS GANHOS CAUSADOS PELA DIVISÃO DO TRABALHO. A TÉCNICA OVERTHREADING (THREAD OVERSUBSCRITION) CONSISTE EM FAZER O NÚMERO DE THREADS EXCEDER O NÚMERO DE NÚCLEOS DE PROCESSAMENTO DISPONÍVEIS NA CPU. APESAR DE GERAR OVERHEAD AO PONTO DE ATRAPALHAR O DESEMPENHO DA MAIORIA DAS APLICAÇÕES, FOI DEMONSTRADO POR CABRAL ET AL. [1] QUE ELA PERMITE O GANHO DE DESEMPENHO EM UM MÉTODO NUMÉRICO PARA UMA EQUAÇÃO DIFERENCIAL. AO SE FAZER A DIVISÃO DE TRABALHO DE FORMA EXPLÍCITA (EXPLICIT WORK SHARING – EWS), O OVERTHREADING PERMITE QUE AO SE REDUZIR O TAMANHO DO SUBDOMÍNIO ALOCADO A CADA THREAD, ESSE SUBDOMÍNIO CABE NA MEMÓRIA CACHE DE NÍVEL 1 E POTENCIALMENTE DE OUTROS NÍVEIS TAMBÉM E PORTANTO, REDUZ A TAXA DE CACH E MISSES, AUMENTANDO SENSIVELMENTE O DESEMPENHO DA APLICAÇÃO. A PROPOSTA DO PRESENTE TRABALHO É AVALIAR O USO DA TÉCNICA OVERTHREADING PARA ACELERAR ROTINAS DE ÁLGEBRA LINEAR COMO SOMA DE MATRIZES, MULTIPLICAÇÃO DE MATRIZES, PRODUTO DE KRONECKER (PRODUTO TENSORIAL) DENTRE OUTRAS ROTINAS. EM EXPERIMENTOS REALIZADOS ATÉ O MOMENTO, CONSEGUIU-SE UM GANHO DE DESEMPENHO DE MILHARES DE VEZES NA MULTIPLICAÇÃO DE MATRIZES QUADRADAS DENSAS QUANDO COMPAROU-SE A EXECUÇÃO COM 1000, 2000, 5000, 10000 E 15000 THREADS COM A EXECUÇÃO SERIAL (1 THREAD). ESTES MESMOS EXPERIMENTOS SUGEREM QUE ESTE GANHO DE MILHARES DE VEZES SE DÁ POR CONTA DA REDUÇÃO DAS TAXAS DE CACHE MISSES DE TODOS OS NÍVEIS (L1, L2 E L3), AO SE AUMENTAR A LOCALIDADE DOS DADOS. OS MELHORES RESULTADOS OCORREM QUANDO SE ATRIBUI UMA THREAD POR LINHA DA MATRIZ, POIS AO MESMO TEMPO QUE SE AUMENTA A LOCALIDADE, GARANTE-SE O MELHOR BALANCEAMENTO DE CARGA, JÁ QUE TODAS A THREADS POSSUEM A MESMA QUANTIDADE DE TRABALHO. O USO EFICIENTE DA M EMÓRIA CACHE É CRUCIAL PARA UM BOM DESEMPENHO DOS PROGRAMAS, UMA VEZ QUE O ACESSO A ELA PODE CHEGAR A CENTENA DE VEZES MAIS RÁPIDO DO QUE O ACESSO À MEMÓRIA PRINCIPAL DRAM, AO MESMO TEMPO QUE É UM GRANDE DESAFIO TER UM ALGORITMO QUE A USE A DE FORMA EFICIENTE POIS EM GERAL SÃO MENORES E MAIS CARAS DO QUE À MEMÓRIA DRAM [3], [4], [5], [6]. A TÉCNICA OVERTHREADING É FREQUENTEMENTE USADA PARA ESCONDER A LATÊNCIA QUE SURGE QUANDO THREADS ENTRAM EM ESTADO DE STALL POR TEREM DE ESPERAR QUE DADOS NECESSÁRIOS VENHAM DA MEMÓRIA. ASSIM, ENQUANTO UMA THREAD ESTÁ AGUARDANDO SEUS DADOS, OUTRAS PODEM SER EXECUTADAS [7]. OUTRO USO IMPORTANTE É O AUMENTO DA ELASTICIDADE DE CPU EM www.mcti.gov.br | www.lncc.br. APLICAÇÕES EM CLOUD COMPUTING [8]. OUTROS TRABALHOS MOSTRAM O DESAFIO DO USO DE OVERTHREADING EM APLICAÇÕES QUE USAM SINCRONIZAÇÃO POR MUTEXES DO SO, LEVANDO A POTENCIAIS COLAPSOS NA VAZÃO (THOUGHPUT) DE INSTRUÇÕES [9] E [10] SUGEREM QUE COMPARTILHAMENTO EXTENSIVO DE RECURSOS PODE NÃO BENEFI CIAR ADEQUADAMENTE APLICAÇÕES DE COMPUTAÇÃO DE ALTO DESEMPENHO OPENMP. NO CAMPO DA ÁLGEBRA LINEAR COMPUTACIONAL, A APLICAÇÃO DA TÉCNICA DE OVERTHREADING PARECE AINDA INEXPLORADA, UMA VEZ QUE ELA É CONHECIDA PELO OVERHEAD CAUSADO, QUE PODERIA EM PRINCÍPIO PREJUDICAR O DESEMPENHO. ASSIM SENDO,O GANHO QUE PODE SER CAUSADO PELA INSIGNIFICATIVA REDUÇÃO DAS TAXAS DE CACHE MISS PARECEM AINDA NÃO TER SIDO PERCEBIDO E EXPLORADO, O QUE COLOCA O PRESENTE TRABALHO POTENCIALMENTE NO ESTADO DA ARTE DAS APLICAÇÕES DO OVERTHREADING PARA ACELERAR ROTINAS DE ÁLGEBRA LINEAR.