List ranking on multicore systems

Abstract

En este proyecto hemos revisado la implementación de algoritmos paralelos para el ranking de listas enlazadas en procesadores multicore. Este tipo de algoritmos exhibe patrones de acceso a memoria fuertemente irregulares que no se benefician de los mecanismos agresivos que integran las arquitecturas actuales para ocultar los costosos accesos a memoria (caches, mecanismos de prebúsqueda, ...). Debido a esta característica intrínseca, el rendimiento de cualquier algoritmo para el ranking de listas esta limitado por los accesos a memoria no consecutivos. En los algoritmos paralelos los problemas de rendimiento se agravan ya que los patrones de acceso irregular suelen provocar mayor contención por recursos compartidos y por lo tanto, continua siendo un importante desafío disear algoritmos eficientes para esta aplicación. Desde comienzos de los 80 se han propuesto un buen número de alternativas para obtener algoritmos paralelos eficientes, pero recientemente ha aumentado el interés debido al auge de muchas aplicaciones, muchas de ellas relacionados con Internet, donde se manejan grandes cantidades de datos almacenadas en estructuras de datos tipo listas enlazadas. Algunos artículos recientes han analizado la implementación de estos algoritmos en GPUs, pero los sistemas basados en procesadores multicore todavía dominan ampliamente el mercado de servidores para muchas de estas aplicaciones. Nos hemos centrado en el algoritmo de Helman y Jájá’s, ya que los intentos por obtener resultados satisfactorios con otros algoritmos, como ha sido el caso de la conocida técnica de pointer jumping propuesta por Wyllie no ha dado resultados atisfactorios. Como principal aportación mostramos como es posible optimizar el algoritmo standard de Helman y Jájá’s para reducir el número de accesos a memoria no consecutivos. También sugerimos una implementación dinámica basada en el paradigma de work-stealing paradigm, aunque todavía, los resultados preliminares no son satisfactorios. [ABSTRACT] In this project we have revisited the implementation of parallel linked-list ranking algorithms on modern Multicore processors. This computation exhibits highly irregular memory referencing patterns, which do not typically benefit from the aggressive mechanisms that integrate current architectures to hide the large latency of main-memory accesses (cache hierarchies, data pre-fetching, ...). Because of this intrinsic characteristic, the performance of any List Ranking algorithm on modern cache-based processors is seriously limited by non-contiguous memory accesses. On a parallel setting, performance is further aggravated since concurrent irregular memory access patterns usually cause more contention for shared memory resources and as such, List Ranking represents a challenging problem for parallel computing. The development of parallel algorithms for List Ranking has received significant attention in previous literature dating back to the early 80’s but most recently, the emerge of many Internet applications that involve extremely large amount of data with linked structures has renewed the interest in List Ranking. Some recent papers have discussed the implementation of these algorithms on modern GPUs but multicore systems still dominate the server market for many applications. We have focused on the Helman and Jájá’s algorithm, since any attempt to achieve satisfactory results with other algorithms such as the famous Wyllie’s pointer jumping technique have proven to be ineffective. As main contribution we have shown how the standard Helman and J´aj´a’s implementation can be optimized to reduce the number of non-contiguous memory access. We have also suggested a dynamic parallel version based on the work-stealing paradigm, although preliminary results are still unsatisfactory.