O método de dobramento recursivo para imersão em hipercubos e suas aplicações

• Ano de defesa: 1998
• Autor(a) principal: Takemoto, Carla Yayoi
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Arquitetura E Organização De Computadores
• Link de acesso: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021544/

A imersão de uma rede de interconexão em outra é uma questão muito importante no desenvolvimento e na análise de algoritmos paralelos. Através destas imersões, os algoritmos originalmente desenvolvidos para uma determinada arquitetura podem sermapeados para uma outra arquitetura. Os resultados de imersão de um m-cubo r-ário em um hipercubo já são conhecidos na literatura. Neste trabalho, apresentaremos o método do código de Gray de Saad e Schultz e o método do dobramento recursivoproposto por Song e Hamdi para este tipo de imersão. Este segundo método possui uma propriedade que possibilita a identificação imediata de todos os subcubos menores de um m-cubo r-ário. Nas publicações anteriores sobre o método do dobramentorecursivo, entretanto, não há exemplos que ilustrem a aplicabilidade e utilidade desta propriedade. Mostramos neste trabalho que o método do dobramento recursivo pode ser útil para uma classe de problemas matriciais resolvidos com algoritmos dotipo divisão e conquista. Mais especificamente, apresentaremos três algoritmos recursivos, para os problemas de obtenção da transposta de uma matriz, multiplicação de matrizes e ordenação por intercalação Par-Ímpar, propostos para dar um m-cubor-ário que necessitem de todos os subcubos menores