Departamento de Ciência da Computação - USP
Date: 26 de maio de 2002
TERCEIRO EXERCÍCIO-PROGRAMA PRAZO DE ENTREGA: ATÉ 17/06/02
Em computação paralela, uma das estruturas de mais sucesso no início dos anos 90 foi o hipercubo. Através desta estrutura pode-se interconectar vários nós de um computador para formar-se um computador paralelo. Alguns exemplos de hipercubos podem ser vistos abaixo:
A definição do hipercubo pode ser feita da seguinte forma: Dado , inteiro. Os vértices do hipercubo são os nós da forma . Dois nós e são adjacentes se eles diferem em apenas uma posição, ou bit.
Além de poder ser definida de forma recursiva, o hipercubo também tem outras propriedades interessantes. Dado um hipercubo com (potência de 2), nós cada nó está ligado a nós e a distância máxima entre dois nós é .
Naturalmente, uma das operações mais usadas em computação paralela é a troca de mensagens, operação que pode ser feita de maneira muito simples, usando apenas passos. Basicamente o algoritmo utilizado é o seguinte.
para i de 1 até k faça troque mensagens entre os nós adjacentes na dimensão i
Podemos ver na figura 2 as diversas etapas de troca de mensagem para um hipercubo de 8 nós.
Observando-se a figura vemos que uma mensagem do nó com destino ao nó passa pelos nós , até chegar ao seu destino final.
Dados , e um nó do hipercubo faça uma função que retorna uma árvore com os nós atingíveis a partir do nó .
A partir do nó mudando a primeira dimensão temos . A partir do nó mudando a segunda dimensão temos: , e a partir de , . Desta forma teremos em cada nível da árvore os nós a uma distância dada do nó .
O seu programa também deve ser capaz de imprimir esta árvore de forma conveniente.
Em um cenários mais complexo, podemos fornecer uma matriz , , que representa mensagens a serem transmitidas no hipercubo. Podemos supor que as mensagens na coluna 1 correspondem às mensagens que o nó deve enviar. Na linha 1 teremos as mensagens destinadas a ele mesmo, na 2 as mensagens ao nó , e assim por diante.
Usando o esquema de comunicação por dimensões, dados , uma matriz de comunicação e uma aresta do hipercubo imprima a soma de todas as mensagens que passarão por ela.
3 010 0 2 3 4 5 6 7 8 9 0 11 12 13 14 15 16 17 18 0 20 21 22 23 24 25 26 27 0 29 30 31 32 33 34 35 36 0 38 39 40 41 42 43 44 45 0 47 48 49 50 51 52 53 54 0 56 57 58 59 60 61 62 63 0 111 110Onde a primeira linha indica o tamanho do hipercubo (no caso do exemplo com nós) e a segunda linha o nó a partir do qual a árvore deve ser desenhada. A partir da terceira linha são dados os tamanhos das mensagens a serem enviadas pelos processadores, e finalmente, na última linha são dados dois vértices que determinam uma aresta do hipercubo. Para o cálculo da soma das mensagens você deve obrigatoriamente usar a primeira parte do EP.
Para este exemplo a saída do seu programa deve ser algo como:
010 011 001 101 111 000 100 110Que representa a seguinte árvore:
Além disto o programa também deve imprimir (ops ainda não calculei..) (que corresponde a ).
This document was generated using the LaTeX2HTML translator Version 99.2beta6 (1.42)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html ep3 -split 0
The translation was initiated by Alfredo Goldman on 2002-05-27