Uma Interface de ProgramaÃÃo DistribuÃda para AplicaÃÃes em OtimizaÃÃo CombinatÃria / A Programming Interface for Distributed Applications in Combinatorial Optimization

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

12/09/2011

RESUMO

Este trabalho foi motivado pela necessidade da exploraÃÃo do potencial do paralelismo distribuÃdo em aplicaÃÃes em OtimizaÃÃo CombinatÃria. Para tanto, propomos uma interface de programaÃÃo distribuÃda, na qual prezamos dois requisitos principais: eficiÃncia e reuso. O primeiro advÃm da necessidade de aplicaÃÃes de CAD exigirem mÃximo desempenho possÃvel. Assim sendo, especificamos esta interface como uma extensÃo da biblioteca MPI, a qual à assumida como eficiente para aplicaÃÃes distribuÃdas. O requisito reuso deve tornar compatÃveis duas caracterÃsticas importantes: assincronismo e operaÃÃes coletivas. O assincronismo deve estar presente na interface, uma vez que as aplicaÃÃes em OtimizaÃÃo CombinatÃria, em sua maioria, possuem uma natureza assÃncrona. OperaÃÃes coletivas sÃo funcionalidades que devem estar disponÃveis na interface, de modo que possam ser utilizadas por aplicaÃÃes em suas execuÃÃes. Tendo em vista atender o requisito reuso, baseamos esta interface nos Modelos de ComputaÃÃo DistribuÃda Dirigidos por Eventos e por Pulsos, pois os mesmos sÃo assÃncronos e permitem a incorporaÃÃo de operaÃÃes coletivas. Implementamos parcialmente a inteface definida neste trabalho. Tendo em vista validar uso desta inteface por aplicaÃÃes em OtimizaÃÃo CombinatÃria, selecionamos duas aplicaÃÃes e as implementamos utilizando a interface. SÃo elas a tÃcnica Branch-and-Bound e o Problema do Conjunto Independente MÃximo (CIM). Fornecemos tambÃm alguns resultados experimentais.

ASSUNTO(S)

interface de programas aplicativos (software) ciencia da computacao paralelismo algoritmos distribuÃdos otimizaÃÃo combinatÃria parallelism, distributed algorithms, combinatorial optimization otimizaÃÃo combinatÃria programaÃÃo (computadores) algorÃtmos computacionais

ACESSO AO ARTIGO

Documentos Relacionados