Topologias de Infra-Estrutura de Comunicacao

  • Published on
    25-Oct-2015

  • View
    18

  • Download
    0

Embed Size (px)

Transcript

<ul><li><p>Topologias deArquiteturas de Comunicao Prof. Csar Augusto M. MarconARQUITETURA DE COMPUTADORES II</p><p>* / 34</p><p>ndice1. Introduo2. Topologias3. Exerccios </p><p>* / 34</p><p>ObjetivoProver a funcionalidade de comunicao desejada para o sistema. E.g. onde colocar um servidor de impresso, visto que metade das mquinas deseja utiliz-lo, e o fluxo de informao muito grande?Topologia fsica a forma com que nodos e conexes esto organizados uma informao estrutural do sistemaTopologia lgica a forma como os sinais trafegam sobre a topologia fsica uma informao comportamental do sistemaFatores decisivos na escolha da topologiaRelao custo/desempenhoAdequao aos requisitos da aplicaoNo caso ideal, a interconexo da topologia corresponde exatamente ao padro de comunicao da aplicaoExemplo: rvore binria favorece algoritmos de diviso e conquistaTopologias de Infra-estruturas de Comunicao</p><p>* / 34</p><p>Compreenso de ConceitosDiferencie a topologia fsica da topologia lgica de uma infraestrutura de comunicao possvel implementar uma topologia lgica em uma topologia fsica completamente diferente? Qua(l)/(is) a(s) consequncia(s)?Qual das alternativas abaixo melhor descrevem uma topologia?O processo de transferncia de um pacote Uma forma de roteamentoMltiplos tipos de redeO arranjo fsico das mquinas e conexes ou o arranjo lgico do trafego de mensagens nos fiosComo a aplicao alvo pode influenciar na escolha da topologia de rede?</p><p>* / 34</p><p>Critrios bsicos para avaliao de topologiasComplexidade de conexesNmero total de ligaes entre componentesGrau do nNmero de ligaes diretas que cada componente possuiDimetroMaior distncia entre dois componentesEscalabilidadeCapacidade da rede interligar novos componentes mantendo as caractersticas originais da redeDesempenhoCapacidade e velocidade de transferir informaesIndicadores so vazo e latnciaRedundnciaExistncia de caminhos alternativos que permitem novos caminhos para as mensagens em caso de falha ou congestionamentoTopologias de Infra-estruturas de Comunicao</p><p>* / 34</p><p>Compreenso de ConceitosRelacione alguns critrios bsicos descritos (consequncia do aumento de um frente ao outro). Justifique as relaesGrau do n x Desempenho da redeGrau do n x EscalabilidadeGrau do n x DimetroDimetro x Desempenho da redeComplexidade das conexes x EscalabilidadeRedundncia x Complexidade das conexesDesempenho x Redundncia</p><p>* / 34</p><p>ndice1. Introduo2. Topologias3. Exerccios </p><p>* / 34</p><p>CaractersticaTodos os nodos esto diretamente conectados a meio fsico compartilhadoRede dinmica, multiponto, temporalEscalabilidade reduzida a uma centena de nodosUtilizado em multiprocessadores com nmero moderado de nodos (&lt; 100)Comprimento do meio fsico e nmero mximo de nodos determinado pela atenuao do sinal e pela qualidade da interface de HW (entre nodo e meio fsico)Grau2Dimetro1Nmero de conexes1ComunicaoNodos se comunicam diretamente atravs do barramento compartilhadoProblema de sobrecarga do barramentoRedundncia de comunicaoFalha em conexo local no afeta a redeFalha no barramento o problema em alguma interface bloqueia o funcionamento de todo o sistemaBarramento</p><p>* / 34</p><p>CaractersticaTodos os nodos esto diretamente conectados a meios fsicos compartilhados e estes meios fsicos podem estar conectados Rede dinmica, ponto-a-ponto (ligao entre segmentos) e multiponto (em cada segmento), espao-temporalEscalabilidade reduzida a uma centena de nodos por segmentoGrau2DimetroDependente do nmero de segmentosNmero de conexesNmero de segmentosComunicaoNodos se comunicam diretamente atravs de barramentos compartilhadosRedundncia de comunicaoFalha em conexo local no afeta a redeFalha em um segmento pode particionar a redeProblema em alguma interface bloqueia o funcionamento de um segmentoBarramento SegmentadoFGHAdaptador</p><p>* / 34</p><p>Redes LinearCaractersticaCada mquina diretamente a uma ou duas mquinasRede dinmica ou esttica, ponto a ponto, espacial ou espao-temporalEscalabilidade alta, embora grande nmero de nodos acarrete baixo desempenhoGrau2 (nas pontas) ou 4 (demais) todas as conexes so bidirecionaisDimetron 1 (n o nmero de ns)Nmero de conexes2 (n 1)ComunicaoEm geral lenta depende muito do mapeamento de tarefas nos nsRedundncia de comunicaoMuito baixa a quebra de apenas uma conexo j particiona a rede</p><p>* / 34</p><p>CaractersticaCada nodo diretamente conectado com todos os demaisRede esttica, ponto a ponto, espacialEscalabilidade muito reduzida devido ao grau dos nodosGrau2 (n - 1)Dimetro1Nmero de conexes</p><p> ou n2 - n</p><p>ComunicaoMuito rpida somente uma conexoRedundncia de comunicaoMuito alta muitas conexes precisam falhar para o sistema ser particionado em subsistemas no comunicantesRede Totalmente Conectada</p><p>* / 34</p><p>CaractersticaNodos so organizados como uma rvoreRede dinmica ou esttica, ponto a ponto, espacial ou espao-temporalConfigurao comum para redes corporativas: escritrios individuais so conectados ao escritrio principalEscalabilidade limitada em largura, mas livre em profundidadeComunicaoDireta entre pais e filhosDemais comunicaes exigem mquinas intermediriasRedundncia de comunicaoFalha de um pai implicaparticionamento da redeRede Hierrquica</p><p>* / 34</p><p>CaractersticaCada nodo pai est conectado a exatamente dois nodos filhosRede dinmica ou esttica, ponto a ponto, espacial ou espao-temporalEscalabilidade alta, embora aumento da profundidade reduza o desempenho da redeGrau2 (folhas), 4 (raz) ou 6 (demais nodos)</p><p>DimetroDimetro cresce de forma linear em relao altura da rvoreDimetro cresce de forma logartmica em relao ao nmero de ns2 log2(n + 1) - 2 (para rvores binrias completas)Nmero de conexes2 (n 1)ComunicaoTodo fluxo de dados entre a sub-rvore esquerda e direita passa pela raiz (gargalo da rede) Inadequada para muitas aplicaesRedundncia de comunicaoMuito baixa Falha de um nodo resulta perda da ligao com toda a sub-rvore abaixorvores Binrias</p><p>* / 34</p><p>CaractersticaUm nodo se conecta a todos os demais. No existe qualquer outra conexo entre os demais nodosRede dinmica ou esttica, ponto a ponto, espacial ou espao-temporalNmero de nodos limitado pelo nodo centralFcil de colocar novas conexes e modificar conexes existentesEscalabilidade baixa limitada pelo nodo centralGrau2 (n 1) (raiz) e 2 (demais nodos)Dimetro1 ou 2Nmero de conexes2 (n 1)ComunicaoToda comunicao tem apenas e sempre um nodo intermedirio (nodo central). Esse esquema de transferncia no garante rapidez visto que o nodo central pode estar sobrecarregadoRedundncia de comunicaoQuebra em uma nica conexo afetar apenas nodo a ela conectadoQuebra de nodo central derruba toda redeUsualmente confivelRede Estrela</p><p>* / 34</p><p>CaractersticaCada nodo sempre conectado a exatamente outros dois nodosRede dinmica ou esttica, ponto a ponto, espacial ou espao-temporalAlta escalabilidade embora comprometa o desempenho da redeGrau2 (unidirecional), 4 (bidirecional)Dimetron / 2 (bidirecional)n 1 (unidirecional)Nmero de conexesn (unidirecional), 2 n (bidirecional)ComunicaoUnidirecionalUma conexo de entrada e outra de sada. Quebra de uma conexo derruba redeBidirecionalcada nodo pode transmitir informao para ambos vizinhos. Suporta quebra de uma conexo. Quebra de mais de uma conexo particiona a rede Rede Anel</p><p>* / 34</p><p>CaractersticasNodos podem ter mais de duas conexesRedes dinmica ou esttica, ponto a ponto, espacial ou espao-temporalRedundncia e custos da comunicao aumentam com o nmero de cordasEscalabilidade menor que a rede anel simples dependente do nmero de cordas</p><p>Rede Anel (Outras topologias)Anel DuploAnel Chordal</p><p>* / 34</p><p>Malha 2DCaractersticaNodos se conectam de forma a gerar uma forma matricialRede dinmica ou esttica, ponto a ponto, espao-temporalAlta escalabilidadeAplicadas em reas que requerem um grande poder de processamentoGrau4, 6 e 8 (todos os nodos centrais)Dimetro2 (sqrt(n) - 1) Nmero de conexes4 (n - sqrt(n)) ComunicaoExistncia de caminhos alternativos entre ns aumenta confiabilidade e diminui risco de gargalosRedundncia de comunicaoA rede tem que quebrar em vrios pontos para ser particionada</p><p>* / 34</p><p>Toro Dobrado 2DCaractersticaNodos se conectam de forma a gerar uma forma matricial com comunicao entre os limites da matrizRede dinmica ou esttica, ponto a ponto, espao-temporalAlta escalabilidadeAplicadas em reas que requerem um grande poder de processamentoGrau8Dimetrosqrt(n) 1Nmero de conexes4 nComunicaoExistncia de caminhos alternativos entre ns aumenta confiabilidade e diminui risco de gargalosRedundncia de comunicaoA rede tem que quebrar em vrios pontos para ser particionada</p><p>* / 34</p><p>Hipercubo 3DCaractersticaCada nodo se conecta a exatamente outros trs, formando um cuboRede dinmica ou esttica, ponto a ponto, espao-temporalNo escalvelGrau6Dimetrolog2(n) = 3Nmero de conexes3 n = 24ComunicaoEstrutura adequada para comunicaes entre mquinas que requerem alto paralelismoRedundncia de comunicaoMuito alta diversas conexes tem que quebrar para particionar a rede</p><p>* / 34</p><p>CaractersticaCada nodo se conecta a exatamente outros quatro, formando cubos totalmente conectadosRede dinmica ou esttica, ponto a ponto, espao-temporalNo escalvelGrau8Dimetrosqrt(n) = 4Nmero de conexes4 n = 64ComunicaoEstrutura adequada para comunicaes entre mquinas que requerem alto paralelismoRedundncia de comunicaoMuito alta diversas conexes tem que quebrar para particionar a redeHipercubo 4D</p><p>* / 34</p><p>CaractersticasInfraestrutura de comunicao de alto custoPermite chaveamento entre dois nodos quaisquerRede dinmica, ponto a ponto ou multiponto, espacialNo bloqueanteSem contenoBaixa escalabilidadeO que limita o nmero de portasPermite acrscimo de nodos aos paresGrau2Dimetro1Nmero de conexes2 n2ComunicaoInviabiliza, por razes econmicas, sua utilizao para interconexo de muitos processadoresUsoInfraestrutura de comunicao unilateral para ligar processadores a memrias em um multiprocessadorinfraestrutura de comunicao bilateral para interligar processadores de um multicomputadorMatriz de Chaveamento (crossbar)</p><p>* / 34</p><p>CaractersticasDiversos nveis de chaveadores (matrizes de chaveamento) so utilizados para conectar nodosGrau2DimetroDepende do nmero de nveisNmero de conexesDepende do nmero de nveis, conectividade do chaveador e nmero de nodosAplicao para redes hierrquicas de matrizes de chaveamentoRedes de permutao multinvelIdia bsicaLigao de pequenas matrizes de chaveamento (normalmente de tamanho 2 2) em vrios nveis consecutivosConectar de forma a reduzir a probabilidade de conflitos entre conexes de diferentes paresLatncia Igual para qualquer par comunicanteCresce logaritmicamente com o nmero de possveis conexesRedes Multinvel</p><p>* / 34</p><p>Rede Multinvel megaCaracterstica das conexesNmero de linhas dado pela metade do nmero de nodosLog2 n matrizes de chaveamento por caminhoExiste apenas um caminho possvel entre entrada e sadaA escolha do caminho muito eficiente e pode ser feita de forma descentralizadaEssa falta de redundncia torna a rede bloqueante</p><p>* / 34</p><p>Composio de TopologiasTambm chamadas de topologias hbridasCaso mais comum para grandes corporaes e WANs</p><p>Rede Hbrida (Barramento-estrela)</p><p>* / 34</p><p>Caractersticas Topolgicas(preencha o que falta)</p><p>RedesGrau do nDimetro da redeNmero conexesLinear2 e 4???2 (n 1)Totalmente conectada???1n2 nrvore binria (completa)2, 4 e 62 log2(n + 1) 2 ???Estrela2 e 2 (n 1)???2 (n 1)Anel simples (bi)4n / 2???Malha 2D (quadrada)???2 ( 1) 4 (n )Toro dobrado 2D8 1???Hipercubo 3D6log2(n) 3 n Hipercubo 4D84 n Barramento211Crossbar (bi)212 n2Rede Omega433 n</p><p>* / 34</p><p>Compare latncia e desempenho para cada redeCaractersticas Topolgicas</p><p>RedesGrau do nDimetro da redeNmero conexesLinear2 e 4n 12 (n 1)Totalmente conectada2 (n 1)1n2 nrvore binria (completa)2, 4 e 62 log2(n + 1) 2 2 (n 1)Estrela2 e 2 (n 1)1 ou 22 (n 1)Anel simples (bi)4n / 22 nMalha 2D (quadrada)4, 6 e 82 ( 1) 4 (n )Toro dobrado 2D8 14 n Hipercubo 3D6log2(n) 3 n Hipercubo 4D84 n Barramento211Crossbar (bi)212 n2Rede Omega433 n</p><p>* / 34</p><p>Eficincia Topolgica para Diferentes Requisitos de Escritores e Leitores</p><p>Redes1-para-1(Unicast)Todos-para-11-para-todos(Broadcast)MximosimultneoLinearn 1(n2 n) / 2n 12 (n 1)Total. conectada111n2 nrvore binria2 (log2(n+1) 1) n 12 (log2(n+1) 1) 2 (n 1)Estrela2n 122 (n 1)Anel simples (bi)n / 2 n / 2 n / 2 2 nMalha 2D2 ( 1) n / 2 2 ( 1) 4 (n )Toro dobrado 2D4 n Hipercubo 3Dlog2(n) log2(n) log2(n) 3 n Hipercubo 4D+ 1 4 n Barramento1n 111Crossbar (bi)1112 (n 1)Rede Omegalog2(n)n log2(n)log2(n)n</p><p>* / 34</p><p>ndice1. Introduo2. Topologias3. Exerccios </p><p>* / 34</p><p>ExercciosCite algumas topologias fsicas de redesQuais as semelhanas entre a topologia tipo barramento e a topologia de rede estrela?Compare diversas topologias de rede em termos de redundncia de caminhos de comunicaoCompare duas topologias com relao ao quesito tolerncia a falhasCompare a rede malha com a rede mega com relao conteno de pacotes</p><p>* / 34</p><p>ExercciosEm uma arquitetura de 6 processadores, calcule o tempo total para cada processador enviar uma mensagem para os outros 5 processadores, com infraestruturas de comunicao do tipo: (a) barramento, (b) anel bidirecional simples, (c) crossbar e (d) torus 2D. Desenhe as infraestruturas de comunicaoQuando se deseja uma maior flexibilidade de interconexo, se utilizam redes dinmicas. Apresente uma rede dinmica do tipo bloqueante e outra do tipo no bloqueante. Qual a mais utilizada, e por qual razo?Desenhe uma infraestrutura de comunicao que possua grau 4 para interligar 7 processadores Defina os parmetros "grau do n" e "dimetro de uma rede" em arquiteturas tipo MIMD conectada por uma rede. De o grau dos ns e o dimetro das seguintes redes:</p><p>RedeGrau Dimetro Anel simples bidirecionalrvore binria completaToro 2D</p><p>* / 34</p><p>Voc foi contratado para projetar uma rede para os seguintes ambientes descritos a seguir. Quais configuraes de rede voc ir utilizar? JustifiqueUm campus universitrio eUm andar de dormitriosExplique como a escolha de uma infraestrutura de comunicao pode aumentar o desempenho de uma aplicao. possvel que uma infraestrutura de comunicao tenha um timo resultado em uma aplicao e ruim em outra?(ENADE 2005 Eng. II - 52) Considere os seguintes custos para os componentes de uma rede de computadores: R$ 1000,00 para um n, R$ 200,00 para uma placa adaptadora entre uma conexo bidirecional e um n, e R$ 100,00 para estabelecer uma conexo fsica bidirecional entre dois ns. Foram implementadas trs redes (R1, R2 e R3), conectando-se quatro ns em trs topologias distintas: R1 em estrela, R2 em anel e R3 totalmente conectada. Os custos das redes R1, R2 e R3, respectivamente, sero:R$ 6000,00, R$ 6000,00 e R$ 6000,00R$ 6000,00, R$ 5200,00 e R$ 6200,00R$ 5500,00, R$ 6000,00 e R$ 7000,00R$ 5000,00, R$ 7000,00 e R$ 7800,00R$ 5500,00, R$ 7000,00 e R$ 7000,00</p><p>Exerccios</p><p>* / 34</p><p>Voc foi contratado para projetar uma rede para os seguintes ambientes descritos a seguir. Quais configuraes de rede voc ir utilizar? JustifiqueUm campus universitrio eUm andar de dormitriosExplique como a escolha de uma infraestrutura de comunicao pode aumentar o desempenho de uma aplicao. possvel que uma inf...</p></li></ul>