Particionamento de grafos de aplicações e mapeamento em grafos de arquiteturas heterogêneas
dc.contributor.advisor | Diverio, Tiaraju Asmuz | pt_BR |
dc.contributor.author | Carvalho, Elias César Araújo de | pt_BR |
dc.date.accessioned | 2007-06-06T17:34:42Z | pt_BR |
dc.date.issued | 2002 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/10183/4206 | pt_BR |
dc.description.abstract | Esta pesquisa visa a modelagem de clusters de computadores, utilizando um modelo analítico simples que é representado por um grafo valorado denominado grafo da arquitetura. Para ilustrar tal metodologia, exemplificou-se a modelagem do cluster Myrinet/SCI do Instituto de Informática da UFRGS, que é do tipo heterogêneo e multiprocessado. A pesquisa visa também o estudo de métodos e tecnologias de software para o particionamento de grafos de aplicações e seu respectivo mapeamento sobre grafos de arquiteturas. Encontrar boas partições de grafos pode contribuir com a redução da comunicação entre processadores em uma máquina paralela. Para tal, utilizou-se o grafo da aplicação HIDRA, um dos trabalhos do GMCPAD, que modela o transporte de substâncias no Lago Guaíba. Um fator importante é o crescente avanço da oferta de recursos de alto desempenho como os clusters de computadores. Os clusters podem ser homogêneos, quando possuem um arquitetura com nós de mesma característica como: velocidade de processamento, quantidade de memória RAM e possuem a mesma rede de interconexão interligando-os. Eles também podem ser heterogêneos, quando alguns dos componentes dos nós diferem em capacidade ou tecnologia. A tendência é de clusters homogêneos se tornarem em clusters heterogêneos, como conseqüência das expansões e atualizações. Efetuar um particionamento que distribua a carga em clusters heterogêneos de acordo com o poder computacional de cada nó não é uma tarefa fácil, pois nenhum processador deve ficar ocioso e, tampouco, outros devem ficar sobrecarregados Vários métodos de particionamento e mapeamento de grafos foram estudados e três ferramentas (Chaco, Jostle e o Scotch) foram testadas com a aplicação e com a arquitetura modeladas. Foram realizados, ainda, vários experimentos modificando parâmetros de entrada das ferramentas e os resultados foram analisados. Foram considerados melhores resultados aqueles que apresentaram o menor número de corte de arestas, uma vez que esse parâmetro pode representar a comunicação entre os processadores de uma máquina paralela, e executaram o particionamento/mapeamento no menor tempo. O software Chaco e o software Jostle foram eficientes no balanceamento de carga por gerarem partições com praticamente o mesmo tamanho, sendo os resultados adequados para arquiteturas homogêneas. O software Scotch foi o único que permitiu o mapeamento do grafo da aplicação sobre o grafo da arquitetura com fidelidade, destacando-se também por executar particionamento com melhor qualidade e pela execução dos experimentos em um tempo significativamente menor que as outras ferramentas pesquisadas. | pt_BR |
dc.format.mimetype | application/pdf | |
dc.language.iso | por | pt_BR |
dc.rights | Open Access | en |
dc.subject | Arquitetura de computadores | pt_BR |
dc.subject | Cluster | pt_BR |
dc.subject | Teoria : Grafos | pt_BR |
dc.title | Particionamento de grafos de aplicações e mapeamento em grafos de arquiteturas heterogêneas | pt_BR |
dc.type | Dissertação | pt_BR |
dc.identifier.nrb | 000348535 | pt_BR |
dc.degree.grantor | Universidade Federal do Rio Grande do Sul | pt_BR |
dc.degree.department | Instituto de Informática | pt_BR |
dc.degree.program | Programa de Pós-Graduação em Computação | pt_BR |
dc.degree.local | Porto Alegre, BR-RS | pt_BR |
dc.degree.date | 2002 | pt_BR |
dc.degree.level | mestrado | pt_BR |
Este item está licenciado na Creative Commons License
-
Ciências Exatas e da Terra (5103)Computação (1758)