Ranking de listas enlazadas en procesadores multicore
Résumé
En este estudio hemos revisado la implementaci 'on 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'usqueda, ...). 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'on por recursos compartidos y por lo tanto, continua siendo un importante desaf'ıo dise˜nar algoritmos eficientes para esta aplicaci 'on. Tras explorar distintas alternativas, nos hemos centrado en el algoritmo de Helman y J'aj'a. Como plataforma experimental hemos seleccionado un servidor de memoria compartida con dos procesadores Intel Westmere de seis cores. Se han analizado dos implementaciones, una de ellas siguiendo el modelo de ejecuci'on convencional fork-join soportado por el est'andar OpenMP, y otra que utiliza la librer'ıa TBB (Threading Building Blocks) de Intel, con la que es posible repartir trabajo utilizando work stealing. Como principal aportaci'on mostramos como es posible mejorar la implementaci'on est'andar de Helman y J'aj'a reduciendo el n'umero de accesos a memoria no consecutivos. Las mejoras son notables con ambos modelos, aunque son especialmente significativas para la versi'on basada en Intel TBB, cuya implementaci'on est'andar no consigue aceleraciones respecto al algoritmo secuencial. Palabras clave-- List Ranking, Helman y J'aj'a, Algoritmos irregulares, OpenMP, Intel TBB, Workstealing.