next_inactive up previous


MAC 2301 Laborat�rio de Estruturas de Dados

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




Troca de mensagens em um hipercubo

Introdu��o

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:

Figura: Hipercubos com dois, quatro e oito n�s.
\begin{figure}\begin{center} \epsfbox{hyp.eps}\end{center}\end{figure}

A defini��o do hipercubo pode ser feita da seguinte forma: Dado $ n = 2^k$, $ k$ inteiro. Os v�rtices do hipercubo s�o os n�s da forma $ V=\{b_1,\ldots,b_k\}$. Dois n�s $ v_1$ e $ v_2$ 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 $ n$ (pot�ncia de 2), n�s cada n� est� ligado a $ \log n$ n�s e a dist�ncia m�xima entre dois n�s � $ \log n$.

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 $ \log n$ 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.

Figura: Etapas de comunica��o em um hipercubos com oito n�s.
\begin{figure}\begin{center} \epsfbox{hyp2.eps}\end{center}\end{figure}

Observando-se a figura vemos que uma mensagem do n� $ 000$ com destino ao n� $ 111$ passa pelos n�s $ 001$, $ 011$ at� chegar ao seu destino final.

O Exerc�cio

Primeira parte

Dados $ k$, e um n� do hipercubo $ v=\{b_1,\ldots,b_k\}$ fa�a uma fun��o que retorna uma �rvore com os n�s ating�veis a partir do n� $ v$.

A partir do n� $ v$ mudando a primeira dimens�o temos $ v_{\bar{1}}=\{\bar{b_1},b_2, \ldots, b_k\}$. A partir do n� $ v$ mudando a segunda dimens�o temos: $ v_{\bar{2}}=\{b,\bar{b_2}, \ldots, b_k\}$, e a partir de $ v_{\bar{1}}$, $ v_{\bar{12}}=\{\bar{b_1},\bar{b_2}, \ldots, b_k\}$. Desta forma teremos em cada n�vel da �rvore os n�s a uma dist�ncia dada do n� $ v$.

O seu programa tamb�m deve ser capaz de imprimir esta �rvore de forma conveniente.

Segunda parte

Em um cen�rios mais complexo, podemos fornecer uma matriz $ A$, $ n\times n$, que representa mensagens a serem transmitidas no hipercubo. Podemos supor que as mensagens na coluna 1 correspondem �s mensagens que o n� $ 0\ldots 0$ deve enviar. Na linha 1 teremos as mensagens destinadas a ele mesmo, na 2 as mensagens ao n� $ 0\ldots 01$, e assim por diante.

Usando o esquema de comunica��o por dimens�es, dados $ k$, uma matriz de comunica��o $ A$ e uma aresta do hipercubo imprima a soma de todas as mensagens que passar�o por ela.

Especifica��es

O programa deve ser capaz de ler uma entrada da forma: 
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 110
Onde a primeira linha indica o tamanho do hipercubo (no caso do exemplo com $ 2^3= 8$ 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
    110
Que representa a seguinte �rvore:

Figura: �rvore a partir do n� 010.
\begin{figure}\begin{center} \epsfbox{tree.eps}\end{center}\end{figure}

Al�m disto o programa tamb�m deve imprimir (ops ainda n�o calculei..) (que corresponde a $ 63+56+\ldots$).

About this document ...

MAC 2301 Laborat�rio de Estruturas de Dados

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

next_inactive up previous
Alfredo Goldman 2002-05-27