nÃo hà / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:5138 |
| Date | 12 September 2011 |
| Creators | Allberson Bruno de Oliveira Dantas |
| Contributors | Ricardo Cordeiro CorrÃa, Francisco Heron de Carvalho Junior, Maria Cristina Silva Boeres |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds