Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/259565
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Algoritmos distribuidos para localização de falhas e difusão de mensagens em hipercubos defeituosos
Author: Nascimento, Saulo Rodrigues do
Advisor: Henriques, Marco Aurelio Amaral, 1963-
Abstract: Resumo: Após investigação das soluções existentes na literatura para o problema da difusão de mensagens em máquinas paralelas tipo hipercubo com falhas de enlace e de nó, este trabalho faz uma análise detalhada das mesmas comparando os fatores que determinam qual é mais adequada para cada tipo de aplicação. Em seguida, efetua-se uma pesquisa sobre os métodos existentes para a detecção e localização de falhas em sistemas multicomputadores. Como resultado, constata-se a ausência de um método específico para hipercubos e propõe­se um algoritmo distribuído que explora as propriedades desta topologia na detecção e localização de enlaces e nós falhos. Finalmente, é proposto um algoritmo tolerante a falhas para difusão eficiente de mensagens, reunindo e superando as características positivas dos melhores algo ritmos existentes. O algoritmo proposto tolera até n-l falhas, sendo elas de enlaces, nós ou uma combinação de ambas, e realiza todo o processo de difusão em no máximo n+2 etapas, para um hipercubo de dimensão n. Um grande número de testes efetuados em um hipercubo comercial atesta a correção desta solução e a sua posição de vantagem em relação às existentes

Abstract: In this work, it is made a detailed analysis of the solutions found in the literature for the problem of broadcasting in hypercube parallel machines with link and node failures, and all the aspects that determine which one fits better to a specific environment and application are compared. Following that, the existing methods used to detect and locate failures in multicomputer systems - major concern in a broadcasting process - are analyzed as well. Based on this research, it is realized the absence of a specific method for hyper­cubes and a new and distributed algorithm is proposed to fill in this gap. This algorithm takes advantage of the hypercube topology in order to detect and locate faulty links and nodes efficiently. Finally, it is proposed a new and efficient fault tolerant algorithm for broadcasting in hypercube systems, gathering and surpassing the most positive features of the former solutions. This algorithm treats up to n-l failures (links, nodes or both) and finishes the whole process in no more than n+2 broadcasting steps, for an n-dimensional hypercube. Several tests performed on a commercial version of a hypercube-based machine confirms the correctness of this solution and its higher quality compared to the other ones
Subject: Tolerância à falha (Computação)
Hipercubo
Language: Português
Editor: [s.n.]
Date Issue: 2000
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Nascimento_SauloRodriguesdo_M.pdf4.24 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.