Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/16976
Título: Uma Interface de Programação Distribuída para Aplicações em Otimização Combinatória
Título em inglês: A Programming Interface for Distributed Applications in Combinatorial Optimization
Autor(es): Dantas, Allberson Bruno de Oliveira
Orientador(es): Corrêa, Ricardo Cordeiro
Palavras-chave: Ciência da computação
Paralelismo
Algoritmos Distribuídos
Otimização Combinatória
Parallelism, Distributed Algorithms, Combinatorial Optimization
Otimização Combinatória
Programação (Computadores)
Algorítmos computacionais
Interface de programas aplicativos (Software)
Data do documento: 2011
Citação: DANTAS, A. B. O. (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.
Abstract: 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: e ciency 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 e cient 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 de ned 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.
Descrição: DANTAS, Allberson Bruno de Oliveira. Uma Interface de Programação Distribuída para Aplicações em Otimização Combinatória. 2011. 79 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Programa de Pós-Graduaçõa em Ciência da Computação, Fortaleza-CE, 2011.
URI: http://www.repositorio.ufc.br/handle/riufc/16976
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2011_dis_abodantas.pdf786,47 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.