Palestra: Rede de Sensores sem fio para Monitorar o meio Ambiente.
Document Actions
Palestra: Estratégias de Ordenação Concorrente.
Prof. Dr. Rogério Drummond Burnier Pessoa de Mello Filho do Instituto de Computação - UNICAMP, na Série de Seminários 2010 da Pós-Graduação, dia 17/09/2010, às 14:00 h, Auditório do IC, Sala 85 - IC 2.
| What | Palestra |
|---|---|
| When |
17/09/2010 from 14:00 to 15:00 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
vCal
iCal
|
Com a disponibilidade de processadores multicore se faz necessário
o desenvolvimento de novos algoritmos paralelos para poder tirar
proveito dos cores disponíveis. Por outro lado o monitoramento de
dispositivos móveis gera uma enorme massa de dados que tem que ser
processada para se extrair estatísticas relevantes. Esta massa de
dados tem que ser ordenada neste processo. É essencial mecanismos
que acelerem este processamento.
Apresentamos duas estratégias para ordenação interna e externa.
A ordenação interna é paralela e escalável com o número de
processadores igual a potências de 2. Para 4 processadores o
algoritmo faz n/4 log(n) + log(n) comparações.
A ordenação externa é utilizada quando o arquivo a ser ordenado
não cabe em memória. Neste caso se utiliza o MergeSort com um ou
mais níveis de intercalação. O objetivo primordial é reduzir o
número de seeks necessários para a ordenação.
Nossa estratégia é usar predição da distribuição dos dados para
diminuir o número de seeks. Em casos extremos conseguimos reduzir
em até 70% o número de seeks.
Num resultado anterior implementamos um novo MergeSort no MySQL
multithread, com pool de buffers compartilhados entre leitura,
processamento e escrita. Nosso MergeSort apresenta ganhos de até
80% em relação a implementação da ordenação externa do MySQL.
Com a incorporação de predição a solução para o MySQL deve ficar
ainda melhor. No entanto, este teste ainda não foi realizado.
==================================================
Graduação e Mestrado no IC–Unicamp, PhD Cornell
Areas de atuação: programação concorrente, programação distribuída,
orientação a objetos.
==================================================
Organizadora: Profª. Drª. Ariadne Maria Brito Rizzoni Carvalho
(ariadne@ic.unicamp.br)
IC -- Unicamp
Fone: (019) 3521-5864
==================================================
VII WTD do IC 2012
