Técnicas de Algoritmos Paralelos e List Ranking

Arquitetura paralela e distribuída 1 Fontes principais 1 J Jaja An introduction to Parallel Algorithms Addison Wes ley 92 Algoritmos paralelos 2 E Cáceres H Mongeli S Song Algoritmos paralelos usan do CGMPVMMPI uma introdução httpwwwimeuspbrsongpapersjai01pdf Arquitetura paralela e distribuída 2 Técnicas de desenvolvimento de algoritmos paralelos 2 Arquitetura paralela e distribuída 3 Pointer Jumping Descrição da técnica Técnica normalmente aplicada sobre uma lista encadeada de elementos Para cada elemento da lista é associado um processador Arquitetura paralela e distribuída 4 Pointer Jumping A técnica de pointer jumping consiste de atualizar o sucessor ou seguinte de cada vértice com o sucessor do sucessor Arquitetura paralela e distribuída 5 Pointer Jumping Em um determinado passo do algoritmo resolvemos o pro blema para todos os elementos da lista que estão até uma certa distância de um elemento individual da lista Esta distância dobra a cada passo Logo depois de k passos o problema foi resolvido para todos os elementos da lista que estão até uma distância 2k Arquitetura paralela e distribuída 6 Exemplo List Ranking Distância dos elementos da lista ao fim da lista Dada uma lista encadeada de n elementos determinar a dis tância de cada elemento da lista ao fim da lista Idéia Associar um processador para cada elemento da lista A cada passo o processador responsável pelo elemento i du plica sua estimativa da distância até o fim da lista Arquitetura paralela e distribuída 7 Exemplo List Ranking Entrada n número de elementos da lista L lista encadeada proxi elemento de L seguinte ao elemento i Se i é o último então proxi nil Estrutura auxiliar pi inicialmente terá cópia de proxi Saída disti distância do elemento i ao fim de L Arquitetura paralela e distribuída 8 List Ranking Algoritmo para i L faça em paralelo pi proxi se pi nil então disti 0 senão disti 1 Arquitetura paralela e distribuída 9 List Ranking continuação para j 1 até log2 n faça para i L faça em paralelo se pi nil então disti disti distpi pi ppi Arquitetura paralela e distribuída 10 List Ranking Submodelo e complexidades Submodelo EREW Complexidades Tempo Olog2 n Processador On É eficiente Não é ótimo Arquitetura paralela e distribuída 11 Exemplo n 8 0 2 1 2 2 2 2 2 p dist j 1 nil 3 nil 2 1 6 0 5 prox nil 5 0 6 7 3 2 1 0 1 1 1 1 1 1 1 p nil 5 0 6 7 3 2 1 dist p dist j 2 0 4 1 3 4 4 2 4 nil 2 nil nil 3 0 nil 6 p dist j 3 0 5 1 3 7 4 2 6 nil nil nil nil nil nil nil nil 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Inicialização Arquitetura paralela e distribuída 12 Exemplo n 8 1 1 1 1 1 1 1 0 4 7 1 5 3 6 2 0 2 0 1 2 2 2 2 2 0 1 2 3 4 5 6 7 0 1 2 3 4 4 4 4 j 1 j 2 j 3 Inicialização Arquitetura paralela e distribuída 13 Algoritmo genérico para i L faça em paralelo pi proxi vi valori para j 1 até log2 n faça para i L faça em paralelo se pi nil então vi vi op vpi pi ppi Arquitetura paralela e distribuída 14 Exemplos análogos Máximo ou mínimo Determinar o máximo ou mínimo dos dados dos elementos da lista op máximo ou mínimo valori dado do elemento i vi máximo ou mínimo dos dados dos elementos desde o elemento i até o último elemento Arquitetura paralela e distribuída 15 Exemplos análogos Soma Determinar a soma dos dados dos elementos da lista op soma valori dado do elemento i vi soma dos dados dos elementos desde o elemento i até o último elemento Arquitetura paralela e distribuída 16 Exemplos análogos distância dos elementos ao fim da lista Determinar a distância dos elementos ao fim da lista op soma valori 1 exceto para o último elemento para o qual valori 0 vi distância do elemento i ao fim da lista Arquitetura paralela e distribuída 17 Exemplos análogos distância dos elementos ao início da lista Ideia distância ao inicio n x 1 distância ao fim x Análogo ao anterior No final vi n vi 1 para todo elemento i da lista Arquitetura paralela e distribuída 18 Construção de Sublistas Arquitetura paralela e distribuída 19 Construção de Sublistas Alguns elementos da lista estão marcados e outros não Deseja se construir uma sublista apenas com os elementos marcados Arquitetura paralela e distribuída 20 Construção de Sublistas Ideia Aplicar duplicação recursiva pulando apenas elementos não marcados Ao final deste passo a lista só possui elementos marcados com a possível exceção do primeiro elemento Se necessário então corrige o primeiro elemento da sub lista Arquitetura paralela e distribuída 21 Construção de Sublistas Entrada n o número de elementos da lista L lista de n elementos inicio ponteiro para o primeiro elemento da lista proxi ponteiro para o elemento seguinte ao elemento i em L Se i é o último elemento de L proxi nil marcai flag representando se o elemento i está marcado ou não Arquitetura paralela e distribuída 22 Construção de Sublistas Saída inicioSL ponteiro para o primeiro elemento da sublista pi inicialmente terá cópia de proxi Ao final do algo ritmo terá o ponteiro para o elemento seguinte ao elemento i na sublista Se i é o último elemento da sublista pi nil Arquitetura paralela e distribuída 23 Construção de Sublistas Algoritmo para i L faça em paralelo pi proxi inicioSL inicio para j 1 até log2 n faça para i L faça em paralelo se pi nil e not marcapi então pi ppi Arquitetura paralela e distribuída 24 continuação se not marcainicioSL então inicioSL pinicioSL para i L faça em paralelo se not marcai então pi nil Arquitetura paralela e distribuída 25 Construção de Sublistas Submodelo e complexidades Submodelo CREW leitura concorrente em marca Complexidades Tempo Olog2 n Processador On É eficiente Não é ótimo Arquitetura paralela e distribuída 26 Exemplo n 8 InicioSL InicioSL M M j 2 M InicioSL j 1 M M M InicioSL M M M j 3 InicioSL M M M Finalização Inicialização M M M Arquitetura paralela e distribuída 27 Algoritmos em Árvores Utilizando Duplicação Recursiva Arquitetura paralela e distribuída 28 Determinar raízes de uma floresta Descrição Dada uma floresta F de árvores enraizadas desejase de terminar para cada vértice i de F a raiz da árvore que contém i Arquitetura paralela e distribuída 29 Determinar raízes de uma floresta Entrada n número de vértices de F paii vértice pai do vértice i em F Se i é uma raiz paii 1 Saída raizi vértice raiz da árvore que contém o vértice i Arquitetura paralela e distribuída 30 Determinar raízes de uma floresta Idéia Aplicar duplicação recursiva sobre o pai Inicialmente cada vértice sabe o seu pai Depois de um passo cada vértice sabe o pai do seu pai e assim por diante até chegar a raiz Arquitetura paralela e distribuida 31 Determinar raizes de uma floresta Algoritmo para 0 2zn1 faca em paralelo raizi pati se raizi 1 entao raizi 1 tf Duplicacao recursiva para 0 2zn1 faca em paralelo enquanto raizi 4 raizraizi faca raizi raizraizi Arquitetura paralela e distribuida 30 Outra maneira de escrever o algoritmo Algoritmo para 0 2zin1 faca em paralelo raizi pati se raizi 1 entao raizi 1 tf Duplicacao recursiva para j 1 até logon faca para 02zn1 faca em paralelo se raizi raizraizi entao raizi raizraizi Arquitetura paralela e distribuída 33 Exemplo n 12 log2 n 4 Raízes 5 9 8 0 4 9 7 2 3 6 11 1 10 5 9 9 4 3 8 0 2 7 5 1 10 11 6 5 1 10 6 11 4 3 8 0 7 2 a b c Arquitetura paralela e distribuída 34 0 1 2 3 4 5 6 7 8 9 10 11 9 10 3 0 9 1 11 3 0 1 5 1 9 10 3 0 9 5 11 3 0 9 5 1 9 5 9 9 9 5 5 9 9 9 5 5 9 5 0 9 9 5 1 0 9 9 5 10 passo 2 passo 1 raiz raiz raiz pai Inicialmente Passos 3 e 4 se executados não fazem nada Arquitetura paralela e distribuída 35 Determinar raízes de uma floresta Submodelo e complexidades CREW Leitura concorrente em Raiz quando dois vértices apontam para um mesmo pai Tempo Olog2 n Gasta log2 h passos onde h é o máximo das alturas das árvores de F No pior caso temos uma única árvore que é uma lista logo com altura log2 n Processadores On Um processador para cada vértice É eficiente Não é ótimo Arquitetura paralela e distribuída 36 Computação de Prefixos em uma Floresta Arquitetura paralela e distribuída 37 Computação de Prefixos em uma Floresta Dada um floresta F de árvores enraizadas desejase determinar para cada vértice i de F uma computação com os pesos dos vértices no caminho de i até a raiz da árvore que contém i Arquitetura paralela e distribuída 38 Soma de Prefixos em uma Floresta Arquitetura paralela e distribuída 39 Soma de Prefixos em uma Floresta Entrada n número de vértices de F paii vértice pai do vértice em F Se i é uma raiz paii nil pesoi peso do vértice i Arquitetura paralela e distribuída 40 Soma de Prefixos em uma Floresta Estrutura auxiliar pi inicalmente terá uma cópia de paii Saída somai soma dos pesos dos vértices no caminho do vértice i até a raiz de sua árvore Arquitetura paralela e distribuída 41 Soma de Prefixos em uma Floresta Idéia Aplicar duplicação recursiva sobre o pai Inicialmente cada vértice sabe o seu peso Depois de um passo cada vértice sabe a soma do seu peso com o peso do seu pai e assim por diante até chegar a raiz Arquitetura paralela e distribuída 42 Soma de Prefixos em uma Floresta Algoritmo para 0 i n 1 faça em paralelo pi paii somai pesoi para 0 i n 1 faça em paralelo enquanto pi nil faça somai somai somapi pi ppi Arquitetura paralela e distribuída 43 6 11 1 10 5 4 1 2 3 1 6 11 1 10 5 1 7 6 4 10 4 2 8 3 0 9 7 9 2 0 5 4 3 3 6 8 7 2 10 7 9 9 2 0 5 4 3 3 6 8 7 2 10 7 9 4 2 8 3 0 9 7 6 11 1 10 5 4 2 3 5 5 4 1 5 3 5 5 4 6 11 1 10 5 1 7 6 4 11 1 3 2 3 2 4 1 Inicialmente Passo 2 Passo 3 Passo 1 Passo 4 se executado não faz nada Arquitetura paralela e distribuída 44 Soma de Prefixos em uma Floresta Submodelo e complexidades CREW Leitura concorrente em soma e p quando dois vértices apontam para um mesmo pai Tempo Olog2 n Gasta log2 n passos onde h é o máximo das alturas das árvores de F No pior caso temos uma única árvore que é uma lista logo com altura log2 n Processadores On Um processador para cada vértice É eficiente Arquitetura paralela e distribuída 45 Soma de Prefixos em uma Floresta Observação Se fazemos pesoi 1 para todo vértice i de F o algoritmo calculará o nível de cada vértice na sua árvore Arquitetura paralela e distribuída 46 Fim