Pesquisa em Computação Paralela

Áreas de interesse

Linhas de pesquisa

• A principal linha de pesquisa é o projeto de algoritmos paralelos escaláveis para computadores de memória distribuída. Aplicações em máquinas paralelas estão ainda restritas a problemas trivialmente paralelizáveis, onde os requisitos de comunicação são baixos. Por outro lado, existe uma grande quantidade de literatura sobre projeto de algoritmos paralelos para muitos problemas não triviais. Os resultados, entretanto, deixam a desejar pela inexistência de um modelo conveniente de paralelismo que esteja suficientemente próximo das máquinas existentes, para permitir uma predicção razoável do desempenho da implementação. O problema é óbvio para algoritmos paralelos baseados no modelo PRAM, mas mesmo algoritmos baseados em modelos de rede são frequentemente muito problemáticos e a velocidade obtida com a implementação de tais algoritmos num multiprocessador comercial é muitas vezes despapontadora. É portanto imperativo projetar modelos e algoritmos de tal maneira que as análises teóricas de complexidade sejam próximas aos tempos observados na implementação real. Nessa linha estamos projetando algoritmos paralelos escaláveis para vários problemas: o problema de posicionamento de elementos numa lista linear (``list ranking''), o problema de determinação de componentes conexos em um grafo, resolução de sistemas tridiagonais, etc.

• Uma outra linha de pesquisa é a paralelização de laços uniformes. Particularmente, temos trabalhado no problema de encolhimento de ciclos (``cycle shrinking'') para tratar ciclos de dependências de fluxo. O grupo de Computação Paralela e Distribuída obteve já vários importantes resultados inclindo dois novos métodos: um combinando o método de encolhimento de ciclo seletivo generalizado e deslocamento de índices, o outro propondo um novo método denominado redução de dependências (trabalho de doutorado).

• Temos ainda pesquisado um tipo especial de algoritmos paralelos chamado algoritmo sistólico, adequado para implementação em circuitos integrados VLSI.

O grupo de Computação Paralela faz parte do LCPD - Laboratório de Computação Paralela e Distribuída.