Design of scalable PGAS collectives for NUMA and manycore systems

Abstract

[Resumen] El número de núcleos por procesador está creciendo, convirtiendo a los sistemas multinúcleo en omnipresentes. Esto implica lidiar con múltiples niveles de memoria en sistemas NUMA, accesibles a través de complejas jerarquías para procesar las crecientes cantidades de datos. La clave para un movimiento eficiente y escalable de datos es el uso de operaciones de comunicación colectivas que minimizen el impacto de los cuellos de botella. Usar comunicaciones unilaterales se vuelve más importante en estos sistemas, para evitar sincronizaciones entre pares de procesos en operaciones colectivas implementadas usando funciones punto a punto bilaterales. Esta tesis propone una serie de algoritmos que proporcionan buen rendimiento y escalabilidad en operaciones colectivas. Estos algoritmos usan árboles jerárquicos, solapamento de comunicaciones unilaterais, pipelining de mensajes y afinidad NUMA. Se ha desarrollado una implementación para UPC, un lenguaje PGAS cuyo rendimiento también ha sido evaluado en esta tesis. Para comprobar el rendimiento de estos algoritmos una nueva herramienta de microbenchmarking fue diseñada e implementada. La evaluación de los algoritmos, realizada en 6 sistemas representativos, con 5 arquitecturas de procesador y 5 redes de interconexión diferentes, ha mostrado en general un buen rendimiento y escalabilidad, mejor que los algoritmos líderes en MPI en muchos casos, lo que confirma el potencial de los algoritmos desarrollados para arquitecturas multi- y manycore.

[Resumo] O número de núcleos por procesador está crecendo, convertindo aos sistemas multinúcleo en omnipresentes. Isto implica lidiar con múltiples niveis de memoria en sistemas NUMA, accesibles a través de complexas xerarquias para procesar as crecentes cantidades de datos. A clave para un movemento eficiente e escalable de datos é o uso de operacións de comunicación colectivas que minimizen o impacto dos colos de botella. Usar comunicacións unilaterais vólvese máis importante nestes sistemas, para evitar sincronizacións entre pares de procesos en operacións colectivas implementadas usando funcións punto a punto bilaterais. Esta tese propón unha serie de algoritmos que proporcionan bo rendemento e escalabilidade en operacións colectiivas. Estes algoritmos usan árbores xerárquicas, solapamento de comunicacións unilaterais, pipelining de mensaxes e afinidade NUMA. Desenvolveuse unha implementación para UPC, unha linguaxe PGAS cuxo rendemento tamén foi avaliado nesta tese. Para comprobar o rendemento destes algoritmos unha nova ferramenta de microbenchmarking foi deseñada e implementada. A avaliación dos algoritmos, realizada en 6 sistemas representativos, con 5 arquitecturas de procesador e 5 redes de interconexión diferentes, mostrou en xeral un bo rendemento e escalabilidade, mellor que os algoritmos líderes en MPI en moitos casos, o que confirma o potencial dos algoritmos desenvoltos para arquitecturas multi-e manycore.

[Abstract] The increasing number of cores per processor is turning multicore-based systems in pervasive. This involves dealing with multiple levels of memory in NUMA systems, accessible via complex interconnects in order to dispatch the increasing amount of data required. The key for efficient and scalable provision of data is the use of collective communication operations that minimize the impact of bottlenecks. Leveraging one-sided communications becomes more important in these systems, to avoid synchronization between pairs of processes in collective operations implemented using two-sided point to point functions. This Thesis proposes a series of collective algorithms that provide a good performance and scalability. They use hierarchical trees, overlapping one-sided communications, message pipelining and NUMA binding. An implementation has been developed for UPC, a PGAS language whose performance has been also assessed in this Thesis. In order to assess the performance of these algorithms a new microbenchmarking tool has been designed and implemented. The performance evaluation of the algorithms, conducted on 6 representative systems, with 5 di erent processor architectures and 5 di erent interconnect technologies, has shown generally good performance and scalability, outperforming leading MPI algorithms in many cases, which con rms the suitability of the developed algorithms for multi- and manycore architectures.