Dissertação

Scalable and Performance-Critical Data Structures for Multicores EVALUATED

Neste trabalho estudamos a escalabilidade, desempenho de estruturas de dados fundamentais como queues, para potenciar o seu desempenho e escalabilidade com vista à próxima geração de sistemas multicore. Propomos dois algoritmos para uma queue concorrente. O primeiro, uma queue wait-free, permite substituir com mais eficiência uma queue lock-free. Esta última é considerada muito eficiente mas não oferece garantias de progresso a todas as threads numa computação concorrente, além de ter mau desempenho sob carga elevada. A nossa queue wait-free, não só oferece as garantias de progresso referidas como também obtém alto desempenho e escalabilidade sob carga elevada. O nosso segundo algoritmo, uma queue com consistência sequencial, consegue atingir desempenho ainda superior através da modificação do modelo de consistência. Todos os algortimos cumprem linearizability, que ordena as operações globalmente. Contudo, a nossa queue com consistência sequencial ordena as operações de acordo com a ordem no programa, que apenas é local a cada thread. Os resultados experimentais revelam que os nossos algoritmos ultrapassam o desempenho do estado da arte por um factor de 10 a 15.
Multicore, Linearizability, Consistência seqüencial, Lock-Free, Wait-Free, Queue

Junho 28, 2013, 17:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Luís Manuel Antunes Veiga

Departamento de Engenharia Informática (DEI)

Professor Auxiliar