A Programming Interface for Distributed Applications in Combinatorial Optimization

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.This work was motivated by the need of exploiting the potential of distributed paralelism in combinatorial optimization applications. propose a distributed programming interface, To achieve this goal, we in which we cherish two main requirements: eciency and reuse. The rst stems from the need of HPC (High applications require maximum possible performance. Performance Computing) Therefore, we specify our interface as an extension of the MPI library, which is assumed to be ecient for distributed applications. The reuse requirement must make compatible two important features: asynchronism and collective operations. Asynchronism must be present at our interface, once most of combinatorial optimization applications have an asynchronous nature. Collective operations are features that should be available in the interface, so that they can be used by applications in their execution. In order reach the reuse requirement, we based this interface on the Event- and Pulse-driven Models of Distributed Computing, once they are asynchronous and allow the incorporation of collective operations. We implemented partially the interface dened in this work. In order to validate the use of the inteface by combinatorial optimization applications, we selected two applications and implemented them using our interface. They are the Branch-and-Bound technique and the Maximum Stable Set Problem (MSSP). We also provide some experimental results