Return to search

Implementação do Algoritmo Paralelo para o Problema de Roteamento de Dados no Computador Paralelo IBM-SP2 / Not available

Nesta dissertação apresentamos e implementamos um método de relaxamento para resolver o problema de roteamento de dados em redes de comutação. Este problema pode ser formulado como um problema de multifluxo, a critério convexo. O algoritmo apresentado resolve iterativamente o problema de multifluxo, decompondo-o da forma mais independente possível em subproblemas de simples fluxo. Esta independência entre os cálculos permite que a resolução dos subproblemas seja simultânea; isto nos permitiu a implementação em paralelo. Os resultados do algoritmo paralelo foram usados para estabelecer uma comparação com o algoritmo seqüencial e assim analisar o speedup. A biblioteca paralela utilizada foi o PVM. / In this thesis we present and implement a relaxation method for solving the routing problem in packet-switched communication networks. This problem can be formulated as a multicommodity flow problem, using the convex criterion. The algorithm presented here solves iteratively the multiflow problem, decomposing it in the most independent fonn possible, in subproblems of single flow commodities. That independence between the calculations allows that the resolution of the subproblems be simultaneous, this allowed us the implementation in parallel. The results of the parallel algorithm were used to establish a comparison with the sequencial algorithm and thus to analyse the speedup. The parallel library used was the PVM.

Identiferoai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-06032018-104542
Date17 June 1999
CreatorsHernandes, Fábio
ContributorsRibeiro, Cassilda Maria
PublisherBiblioteca Digitais de Teses e Dissertações da USP
Source SetsUniversidade de São Paulo
LanguagePortuguese
Detected LanguageEnglish
TypeDissertação de Mestrado
Formatapplication/pdf
RightsLiberar o conteúdo para acesso público.

Page generated in 0.0017 seconds