102014023779 MÉTODO PARA PARALELIZAR UM LOOP DE PROGRAMA COM DEPENDÊNCIA LOOP-CARRIED
Depósito: 25/09/2014
Destaque: licenciada para Samsung
Inventor: DIVINO CÉSAR / GUIDO ARAÚJO
Titular: SAMSUNG ELETRÔNICA DA AMAZÔNIA LTDA. (BR/SP) / UNIVERSIDADE ESTADUAL DE CAMPINAS - UNICAMP (BR/SP) (BR/SP)
A invenção refere-se a um método de paralelização automática de loops de programa que possuem dependências entre iterações (loop-carried), comuns em programas de uso geral, mas de difícil paralelização com técnicas existentes como DOACROSS e DSWP. O método proposto divide o corpo do loop em estágios com base nos Componentes Fortemente Conectados (SCCs) do Grafo de Dependência do Programa (PDG). Em seguida, as iterações são agrupadas em lotes, e cada thread executa um lote de iterações de um estágio por vez, alternando entre estágios de forma cíclica. Dependências entre estágios são gerenciadas por buffers locais a cada thread, enquanto dependências loop-carried são comunicadas via memória compartilhada apenas ao final de cada lote, reduzindo significativamente a sobrecarga de comunicação. A invenção é especialmente eficiente em dispositivos multiprocessados, como smartphones e tablets, e demonstra ganhos de desempenho de até 63% em comparação com a execução sequencial, superando consistentemente as técnicas DSWP e DOACROSS em diversos benchmarks. O método não requer hardware adicional e é compatível com sistemas operacionais modernos.
Desenvolvido pelo Instituto de Computação da Unicamp em parceria com a Samsung, o "BDX-Method" é um método que acelera a execução de programas e aplicativos em dispositivos como smartphones e computadores. Ele permite dividir de forma mais eficiente as tarefas entre os núcleos do processador (cores), reduzindo significativamente a necessidade de comunicação entre eles, o que melhora o desempenho geral. O professor Guido Araújo, responsável pelo desenvolvimento, explica que a tecnologia foca em acelerar os "laços" – trechos de código que se repetem milhões de vezes e consomem a maior parte do tempo de execução. Isso não só acelera os aplicativos, como também reduz o consumo de bateria, embora estudos ainda estejam em andamento para quantificar essa economia. A pesquisa, que contou com a colaboração de alunos de doutorado e iniciação científica, sempre visou a aplicação prática no mercado. Fruto de um convênio de P&D, a tecnologia foi patentada em cotitularidade, com a Samsung obtendo os direitos de exploração. A parceria é considerada um caso de sucesso de interação universidade-empresa, com a Inova Unicamp atuando como facilitadora do licenciamento. Guido Costa Souza de Araújo recebeu o título de PhD em Engenharia Elétrica pela Universidade de Princeton (EUA) em 1997. Com uma atuação de mais de 30 anos na área de sistemas de computação, trabalhou na Fujitsu Laboratories of America em 1996 e foi consultor das empresas americanas Conexant Semiconductor Systems e Mindspeed Technologies (Califórnia, EUA) entre 1997-2001. Atualmente é Professor Titular do Instituto de Computação da UNICAMP.
Resumo: 102014023779 A presente invenção se refere a um método para paralelizar um loop de programa com dependência loop- carried compreendendo: - contruir um grafo de dependência para o loop a se paralelizado ( 510); - encontrar os componentes fortemente conectados do grafo de dependência de programa e construir grafo acíclico direcionado dos componentes fortemente conectados (520) ; - particionar em estágios (530) o garfo acíclico direcionado dos componentes fortemente conectados, correspondendo cada estágio a um grupo de linhas do loop original; - distribuir ( em forma de lote) as iterações de cada estágio (540); - torna cada estágio uma região crítica (550) de forma que cada estágio seja executado somente por uma thead/núcleo a cada momento; - adicionar uma verificaçaõ de finalização de loop (560); - adicionar um loop de continuidade em torno de todos os estágios (570); e - replicar o loop transformado/resultante em diversos processadores/núcleos/threads (580) .
Nenhum comentário:
Postar um comentário