SISTEMAS OPERACIONAIS
ROGER ROBERTO ROCHA DUARTE – GRR 20084281
THIAGO HENRIQUE DOS SANTOS PICHARSKI – GRR2008
Introdução
Visando buscar sempre o máximo de desempenho, tanto na resolução do problema em si, mas
também para o bem uso de memória e CPU, o problema foi pensado várias vezes de forma que, a
execução fosse o mais rápido possível buscando a utilização mínima memória e a máxima dos
processadores.
Em si, o sistema foi montado para sempre trabalhar, ou seja, ficar parado o mínimo possível diante
das contagens de distâncias repetidas, ou do acesso do buffer global do sistema.
Arquitetura do Sistema
Como bem dito na introdução, o sistema foi elaborado visando a velocidade, estabilidade e
consumo adequado de memória.
Levando em conta esses conceitos, o sistema foi elaborado da seguinte forma:
Cálculos:
– Para efetuar os diversos cálculos, o modelo mais simples foi escolhido, ou seja,
colocamos as N Threads em ordem, logo a thread 0 faz a contagem de 0 até 1,2,3...m; a
thread 1 faz a contagem de 1 até 2, 3, 4...m, e assim por diante. Quando a thread 0
completa a contagem, esta pula para a linha N (0 +N), a thread 1 pula para a linha N+1,
e assim por diante.
– Essas threads que fazem os cálculos são chamadas de threads contadoras.
Gerência de Threads:
– Para cada thread contadora, existe uma outra thread, com a função de contar as
distâncias repetidas e colocar no buffer.
Para 4 Threads Contadoras:
Thread Wait
Thread Wait
Thread Wait
Thread Wait
Thread Contadora 0 Thread Contadora 1 Thread Contadora 2 Thread Contadora 3
O exemplo acima, mostra o detalhamento das gerências de Threads.
Memória:
– Na elaboração do sistema, procuramos dispersar bem memória cedida pela máquina.
– O sistema possui uma estrutura global para armazenar os dados sumarizados, ou seja,
com as distâncias e com números que cada Thread calculou.
– Cada Thread contadora possui N pequenos buffers. Quando um enche a thread passa
automaticamente a usar o outro buffer. Nesse mesmo instante a thread contadora dona
desse buffer avisa a sua Thread Wait que este buffer está cheio, então a Thread Wait
calcula as distâncias repetidas e, assim que possível, coloca esse resultado na estrutura
de sumarizada.
Gerencia de Memória:
– Para os buffer de cada Thread foi utilizado uma tabela Hash.
– A escolha desse modelo, foi pensando no número de buscas e inserções que o sistema
teria que fazer no futuro. E como, busca e inserção podem ser O(1) – quando não
ocorrem colisões ou algo do gênero, Hash foi uma estrutura viável. No começo foi
pensado na utilização de uma árvore B e de uma árvore AVL (ou rubro-negra), porém,
com o uso de ponto flutuante, ficou inviável a utilização dessas estruturas – já que essas
utilizam muitas comparações, operações nas quais poderiam acarretar em erros.
Evolução do Sistema:
– A primeira versão elabora foi seqüencial. A estrutura contida era uma lista sequencial,
para uma entrada de 5000 elementos, o sistema demora cerca de 15 ~20 segundos para
execução – o que na última versão é praticamente instantâneo.
– A segunda versão, foi elaborado um sistema com N Thread e com um buffer global para
o resultado. Cada thread tinha um pequeno buffer, porém quando esse se enchia, a
própria thread tinha que elaborar os cálculos de repetidos e etc – deixando assim, parte
do sistema parado.
– Com o passar do tempo, a segunda versão foi sem melhorada, até que chegarmos na
arquitetura final.
Experimentos
Estruturas:
– Foi testadas várias estruturas que seriam utilizadas para armazenar em memória os
buffers das threads e resultado sumarizado das mesmas. Numa primeira idéia foi testada
uma árvore AVL, a qual não foi viável devido ao número de inserções seqüenciais
causar um grande overhead nas rotações da árvore.
– Em seguida pensamos no uso da árvore B que é uma estrutura muito robusta, mas usa-la
não era justificável ao comparar sua complexidade à simplicidade dos dados que seriam
armazenados.
– Em fim foi decidido usar tabela de dispersão que resolve facilmente o problema com
pontos flutuantes e tem um custo de inserção e busca extremamente rápido. O grande
problema do uso da tabela de dispersão é quando ocorre muitas colisões, pensando nisso
foi adotada uma função de dispersão com uma certa complexidade, a divisão de
polinômios CRC-32, que diminui consideravelmente as colisões, usamos arvores AVL
no lugar de listas em nas linhas da tabela para diminuir o custo de busca, em caso de
colisões.
Threads:
– Em uma primeira implementação foi usado 4 threads sumarizando as linhas múltiplas do
seu próprio ID, essas mesmas threads escreviam na estrutura principal com uso de
semáforo para manter a consistência, essa versão não era eficiente devido as threads
terem que parar para inserirem na estrutura causando um enorme gargalo no fluxo de
execução.
– Em uma segunda ideia foi adicionado um buffer em cada thread que era alimentado
pelas threads já citadas acima e um pool de threads consumindo o buffer e sumarizando
na estrutura principal, usando os semáforos da mesma forma. Melhorou
significativamente o desempenho, mas ainda sim as threads produtoras ficavam
aguardando por ter enchido o buffer e a thread consumidora não ter conseguido
consumir o buferr por estar esperando o semáforo.
– Para minimizar o problema anterior foi usado vários níveis de buffers, assim quando o
um buffer enche as threads continuam escrevendo nos buffers seguintes equanto os
anteriores esperam para serem consumidos, retornando a usar os anteriores assim que
stes estiverem vazios. Isto melhorou o fluxo do programa e mantem as threads
funcionando quase que em tempo integral.
Conclusão
Com a evolução para a programação paralela, podemos sentir a real diferença na resolução
do problema. Nos testes, a mudança de 4 para 6 e posteriormente para 8 threads, verificamos uma
mudança realmente significativa no tempo de execução.
O conjunto de estruturas de dados escolhidas também causaram enorme impacto no
desempenho do programa. O gargalo do programa está localizado na estrutura compartilhada que
todas as threads escrevem, sendo necessária a proteção com semáforos para manter a consistência,
com isto foi primordial o uso de baixo custo, analisando casos gerais de execução, o melhor
equilíbrio entre os experimentos já citados foi tabela de dispersão + árvore AVL.