Manycore Architectures and SIMD Optimizations for High Performance Computing

Abstract

[Resumo] Nos últimos cincuenta anos a arquitectura de computadores estivo marcada pola capacidade de aumentar o número de transistores nos microchips segundo a Lei de Moore. Esta corrente cambiou drasticamente na última década. O paralelismo xoga un factor clave nos deseños modernos: dende un punto de vista hardware aumentando o número de CPUs, e dende unha perspectiva software explotando as capacidades arquitectónicas con especial énfase nas unidades vectoriais. Nesta Tese poñemos o foco en dúas dimensións ortogonais: a análise e optimización do tráfico de coherencia en arquitecturas manycore, e o desenvolvemento de optimizacións vectoriais. Na primeira dimensión desenvolvemos técnicas estáticas e dinámicas para mellorar a afinidade entre as CPUs e os datos naquelas arquitecturas que implementan redes de interconexión en malla. A nosa proposta reduce a contención nesas mallas mellorando a localidade dos datos de acordo á distribución física dos compoñentes. Na segunda dimensión desenvolvemos un compilador fonte-a-fonte para vectorizar códigos con patróns de acceso a memoria irregulares. Presentamos dúas contribucións: estratexias para recuperar de forma vectorial direccións de memoria non contiguas, e a fusión de reducións independentes. Desenvolvemos un sistema SMT para a xeración de alternativas de empaquetado de operandos aleatorios baseadas no conxunto de instrucións da arquitectura subxacente, e unha ferramenta para a caracterización de arquitecturas. A nosa avaliación mostra potenciais beneficios nestes códigos irregulares aplicando as nosas propostas.

[Resumen] En los últimos cincuenta años la arquitectura de computadores estuvo condicionada por la capacidad de aumentar el número de transistores en los microchips siguiendo la Ley de More. Esta tendencia cambió drásticamente en la última década. El paralelismo es ahora un factor clave en los diseños modernos: desde una perspectiva hardware aumentando el número de CPUs, y desde un punto de vista software explotando las capacidades arquitecturales con especial énfasis en las unidades vectoriales. En esta Tesis ponemos el foco en dos dimensiones ortogonales: el análisis y optimización del tráfico de coherencia caché en arquitecturas manycore, y el desarrollo de optimizaciones vectoriales. Para la primera dimensión hemos desarrollado técnicas estáticas y dinámicas para mejorar la afinidad entre las CPUs y los datos en arquitecturas con redes de interconexión en malla. Nuestra propuesta reduce la contención en las mallas mejorando la localidad de los datos siguiendo la distribución física de los componentes. En la segunda dimensión hemos desarrollado un compilador fuente-a-fuente para vectorizar códigos con patrones de acceso a memoria irregulares. Presentamos dos contribuciones: estrategias para recuperar de forma vectorial direcciones de memoria no contiguas, y la fusión de reducciones independientes. Hemos desarrollado un sistema SMT para la generación de alternativas de empaquetamiento de operandos aleatorios basadas en el conjunto de instrucciones de la arquitectura subyacente, y una herramienta para la caracterización de arquitecturas. Nuestra evaluación muestra potenciales beneficios en estos códigos irregulares aplicando nuestras propuestas.

[Abstract] For the past fifty years computer architecture has been driven by the ability to etch more transistors onto a single die following the Moore’s Law. This trend changed in the past decade. Parallelism is now a key factor in modern designs: from the hardware side by scaling the number of cores, and from the software side by exploiting the capabilities available in the architecture, emphasizing on the SIMD units. In this Thesis we focus on two orthogonal dimensions: the analysis and optimization of coherence traffic in modern manycores, and the development of SIMD optimizations. For the first dimension we develop static and dynamic techniques for enhancing core-to-data affinity for manycores featuring mesh interconnection networks. Our approach reduces the contention on these meshes by improving data locality according to the physical layout. For the second dimension we develop a source-to-source compiler for vectorizing codes presenting irregular access patterns. We present two main contributions: strategies for gathering non-contiguous memory addresses, and fusing independent reductions. We have developed an SMT-based system to generate alternatives for packing random operands from memory based on the host ISA, and a profiling framework for characterizing platforms. Our evaluation shows promising speedups when applying these SIMD optimizations to those codes.