Processamento Coseqüencial e ordenação de arquivos grandes Ordenação Externa

  • Published on
    16-Apr-2015

  • View
    106

  • Download
    0

Embed Size (px)

Transcript

  • Slide 1
  • Processamento Coseqencial e ordenao de arquivos grandes Ordenao Externa
  • Slide 2
  • Operaes Coseqenciais Envolvem o processamento coordenado (simultneo) de duas ou mais listas de entrada seqenciais, de modo a produzir uma nica lista como sada Exemplo: merging (intercalao) ou matching (interseco) de duas ou mais listas mantidas em arquivo
  • Slide 3
  • Modelo para implementao de processos coseqenciais Lista 1 Adams Carter Chin Davis Foster Garwich Rosewald Turner Lista 2 Adams Anderson Andrews Bech Rosewald Schmidt Thayer Walker Willis
  • Slide 4
  • Modelo para implementao de processos coseqenciais Algoritmo de intercalao l um nome de cada lista, e compara se ambos so iguais, copia o nome para a sada e avana para o prximo nome da lista em cada arquivo se o nome da Lista1 menor, ele copiado para a sada, e avana na Lista1 se o nome da Lista1 maior, copia o nome da Lista2 para a sada e avana na Lista2
  • Slide 5
  • Programa: Merge (versao 1) Intercala2Listas(lista1,lista2, lsaida, lsaida) { // As listas de entrada so objetos organizados em um vetor iniciaLista(1, Lista1); // inicia lista1 ao primeiro elemento do vetor de lista iniciaLista(2, lista2); iniciaSaida(lsaida); // inicia a lista de saida maisitens1 = proximoItemList(1); // retorna true se ainda existe um elemento valido na lista maisitens2 = proximoItemList(2); enquanto (maisitens1 ou maisitens2) { if (Item(1) < Item(2)) { ProcesssaItem(1); maisitens1 = proximoItemList(1); } else if (Item(1) = Item(2)) { ProcesssaItem(1); maisitens1 = proximoItemList(1); maisitens2 = proximoItemList(2); } else { // Item(1) > Item (2) ProcesssaItem(2); maisitens2 = proximoItemList(2); } FinishUp(); // fecha os arquivos... }
  • Slide 6
  • Programa: Merge (verso 2) call initialize() call input() to get NAME_1 from LIST_1 and NAME_2 from LIST_2 while(MORE_NAMES_EXIST) if (NAME_1 < NAME_2) write NAME_1 to OUT_FILE call input() to get NAME_1 from LIST_1 else if (NAME_1 > NAME_2) write NAME_2 to OUT_FILE call input() to get NAME_2 from LIST_2 else /* match names are the same */ write NAME_1 to OUT_FILE call input to get NAME_1 from LIST_1 call input to get NAME_2 from LIST_2 finish_up()
  • Slide 7
  • Procedure INPUT (verso 2) Argumentos de entrada INP_FILE: descritor do arquivo de entrada (LIST_1 ou LIST_2) PREVIOUS_NAME: nome lido da lista no passo anterior OTHER_LIST_NAME: ltimo nome lido da outra lista Argumentos de sada NAME nome lido MORE_NAMES_EXIST - flag para indicar a parada
  • Slide 8
  • Procedure INPUT (verso 2) read next NAME from INP_FILE If (EOF) and (OTHER_LIST_NAME == HIGH_VALUE) MORE_NAME_EXIST := FALSE /* fim das duas listas else if (EOF) NAME:=HIGH_VALUE /* essa lista acabou else if (NAME
  • Two-Way Merge Sort Externo Em cada passo l-se e escreve-se cada pgina no arquivo. Custo = N pginas no arquivo => o nmero de passos Custo total: Problema: no maximiza o uso do buffer, gerando um grande nro de passos. Input file 1-page runs 2-page runs 4-page runs 8-page runs PASSO 0 PASSO 1 PASS 2 PASS 3 9 3,4 6,2 9,48,75,63,1 2 3,45,62,64,97,8 1,32 2,3 4,6 4,7 8,9 1,3 5,62 2,3 4,4 6,7 8,9 1,2 3,5 6 1,2 2,3 3,4 4,5 6,6 7,8
  • Slide 14
  • Intercalao em k-vias No h motivo para restringir o nmero de entradas na intercalao a 2 Podemos generalizar o processo para intercalar k corridas simultaneamente k-Way MergeSort
  • Slide 15
  • Intercalao em k-vias Esta soluo pode ordenar arquivos realmente grandes gerao das corridas envolve apenas acesso seqencial aos arquivos a leitura das corridas e a escrita final tambm s envolve acesso seqencial aplicvel tb. a arquivos mantidos em fita, j que E/S seqencial Usar o buffer disponvel para reduzir o nmero de passos.
  • Slide 16
  • Intercalao em k-vias B pginas no buffer, e arquivo de N pginas: Passo 0: gerar runs com B pginas cada. Passo 1,2, , etc.: (B-1) merge. B Main memory buffers INPUT 1 INPUT B-1 OUTPUT Disk INPUT 2... * Mais que 3 buffers. Como utiliz-los?
  • Slide 17
  • Custo do K way merge sort externo Nmero de passos: Custo = 2N * (# de passos) Ex. com 5 pginas de buffer p/ ordenar arquivo com 108 pginas: Passo 0: = 22 runs ordenadas de 5 pgs. cada (ltima run tem somente 3 pginas) Passo 1: = 6 runs ordenadas de 20 pgs. cada (ltima run tem somente 8 pginas) Pass 2: 2 runs, (80 pgs e 28 pgs.) Pass 3: arquivo ordenado de 108 pginas
  • Slide 18
  • Nmero de passos.
  • Slide 19
  • Qual o custo (tempo) do MergeSort ? Supondo Arquivo com 8 000 000 milhes de registros, 100 bytes cada registro (800 MB) Chave do registro: 10 bytes. Memria disponvel para operao= 10 MB 10 MB RAM 100.000 registros Arquivo armazenado em reas contguas do disco (extents), extents alocados em mais de uma trilha, de tal modo que um nico rotational delay necessrio para cada acesso Caractersticas do disco tempo mdio para seek: 18 ms atraso rotacional: 8.3 ms taxa de transferncia: 1229 bytes/ms tamanho da trilha: 200.000 bytes
  • Slide 20
  • Qual o custo (tempo) do MergeSort ? Quatro passos a serem considerados leitura dos registros, do disco para a memria, para criar as corridas escrita das corridas ordenadas para o disco leitura das corridas para intercalao escrita do arquivo final em disco
  • Slide 21
  • Leitura dos registros e criao das corridas L-se 10MB de cada vez, para produzir corridas de 10 MB Sero 80 leituras, para formar as 80 corridas iniciais O tempo de leitura de cada corrida inclui o tempo de acesso a cada bloco (seek + rotational delay) somado ao tempo necessrio para transferir cada bloco
  • Slide 22
  • Leitura dos registros e criao das corridas seek = 8ms, rot. delay = 3ms, total 11ms Tempo total para a fase de ordenao: 80*(tempo de acesso a uma corrida) + tempo de transferncia de 80MB Acesso: 80*(seek+rot.delay= 11ms) = 1s Transferncia: 800 MB a 14500 bytes/ms = 60s Total: 61s
  • Slide 23
  • Escrita das corridas ordenadas no disco Idem leitura! Sero necessrios outros 61s para se escrever as 80 corridas (runs)
  • Slide 24
  • Leitura das corridas do disco para a memria (para intercalao) Tem-se 10MB de MEMRIA para armazenar 80 buffers de entrada Dividi-se 10MB em 80 partes para bufferizar 80 corridas portanto, cada buffer armazena 1/80 de uma corrida (125.000 bytes). Logo, cada corrida deve ser acessada 80 vezes para ser lida por completo 80 acessos para cada corrida X 80 corridas 6.400 seeks considerando acesso = seek + rot. Delay 11ms X 6.400 = 70s Tempo para transferir 800 MB = 60s
  • Slide 25
  • Escrita do arquivo final em disco Precisamos saber o tamanho dos buffers de sada. Nos passos 1 e 2, a MEMRIA funcionou como buffer, mas agora a MEMRIA est armazenando os dados a serem intercalados Para simplificar, assumimos que possvel alocar 2 buffers de 200.000 bytes para escrita dois para permitir double buffering, 200.000 porque o tamanho da trilha no nosso disco hipottico
  • Slide 26
  • Escrita do arquivo final em disco Com buffers de 200.000 bytes, precisaremos de 800.000.000 bytes / 20.000 bytes por seek = 4.000 seeks Como tempo de seek+rot.delay = 11ms por seek, 4.000 seeks usam 4.000 X 11, e o total de 44s. Tempo de transferncia 60s
  • Slide 27
  • Tempo total leitura dos registros para a memria para a criao de corridas: 61s (seeks = 800) escrita das corridas ordenadas para o disco: 61s (seeks = 800) leitura das corridas para intercalao: 70 + 60 = 130 s (seeks = 6400) escrita do arquivo final em disco: 44 + 60 = 104 s (seeks = 4000) Tempo total do Mergesort = 356 s (seeks = 10560)
  • Slide 28
  • Comparao Quanto tempo levaria um mtodo que no usa intercalao? Se for necessrio um seek separado para cada registro, i.e, 8.000.000 seeks a 11ms cada, o resultado seria um tempo total (s para seek) = 88.000s = 24 horas, 26 minutos e 40s !
  • Slide 29
  • Ordenao de um arquivo com 80.000.000 de registros Anlise - arquivo de 8000 MB Na fase de ordenao no possvel melhorar I/O Fase de merge Passo de leitura: o maior responsvel Passo de escrita: no influenciado pelo modo da organizao das runs. O arquivo aumenta, mas a memria no! Em vez de 80 corridas iniciais, teremos 800 Portanto, seria necessrio uma intercalao em 800-vias no mesmo 10 MB de memria, o que implica em que a memria seja dividida em 800 buffers na fase de intercalao
  • Slide 30
  • Ordenao de um arquivo com 80.000.000 de registros Cada buffer comporta 1/800 de uma corrida, e cada corrida acessada 800 vezes 800 corridas X 800 seeks/corrida = 640.000 seeks no total O tempo total agora superior a 2 horas e 24 minutos, aproximadamente 25 vezes maior do que o arquivo de 800 MB (que 10 apenas vezes menor do que este)
  • Slide 31
  • Ordenao de um arquivo com 80.000.000 de registros Definitivamente: necessrio diminuir o tempo gasto obtendo dados na fase de intercalao
  • Slide 32
  • O custo de aumentar o tamanho do arquivo A grande diferena de tempo na intercalao dos dois arquivos (de 800 e 8000 MB) conseqncia da diferena nos tempos de acesso s corridas (seek e rotational delay) Em geral, para uma intercalao em K-vias de K corridas, em que cada corrida do tamanho da MEMRIA disponvel, o tamanho do buffers para cada uma das corridas de: (1/K) x tamanho da MEMRIA = (1/K) x tamanho de cada corrida
  • Slide 33
  • Compl