Thesis defence of Valentin Isaac-Chassande (MADMAX team): Design of a Memory System for Sparse Data Processing

Valentin ISAAC-CHASSANDE - MADMAX team

Thesis direction
Frédéric ROUSSEAU - Thesis director - Full professor - TIMA Laboratory
Adrian EVANS - Thesis co-supervisor - Research engineer - CEA LETI

Rapporteurs
Roselyne CHOTIN - Rapporteure - Full professor - LIP6 - Sorbonne University
Olivier SENTIEYS - Rapporteur - Full professor - University of Rennes, IRISA, INRIA

Composition of the jury
Frédéric ROUSSEAU - Thesis director - Full professor - TIMA Laboratory
Roselyne CHOTIN - Rapporteure - Full professor - LIP6 - Sorbonne University
Olivier SENTIEYS - Rapporteur - Full professor - University of Rennes, IRISA, INRIA
Benoît DUPONT DE DINECHIN - Examinator - Engineer - KALRAY
Yves ROBERT - Examinator - Full professor - École Normale Supérieure de Lyon
Adrian EVANS - Guest - Research engineer - CEA LETI

Title: Design of a Memory System for Sparse Data Processing 
Keywords: memory system, scientific computing, sparse data
Abstract: SPARSE matrices are ubiquitous in data-intensive applications such as scientific computing, graph analytics, and machine learning, yet their irregular memory access patterns pose significant challenges for traditional computing architectures. This thesis addresses the core challenge of designing hardware and architectural mechanisms to efficiently support sparse data processing, focusing on scalability, adaptability, and high performance. We analyze the fundamental algorithms for sparse matrix multiplication, Inner-Product, Outer-Product, and Gustavson’s, and identify their hardware challenges, separated into the gather and scatter problems. Gustavson’s algorithm emerges as the most promising for hardware implementation due to its balanced trade-offs, while the Outer-Product algorithm is well suited for Matrix-Vector kernels. Our main contribution is SpDCache, a region-based architecture that optimizes memory transactions for sparse data by leveraging the structural properties of banded matrices. SpDCache partitions cache memory into sparse and dense regions, significantly reducing memory traffic compared to generic caches. Key contributions include:
• Architectural Design and Modeling: A Python-based simulation model and a probabilistic C-based model analyze SpDCache’s memory transactions, revealing the importance of coarse-grain matrix structure (ex., banded matrices).
• Microarchitectural Implementation: RTL-level simulations validate SpDCache’s effectiveness in reducing memory traffic and improving cache utilization, with virtual partitioning ensuring flexibility and adaptability. Further analysis reveals the importance of fine-grain matrix structure in optimizing performance (e.g., cache-line density).
• Optimizations and Scalability: Extensions to sparse Matrix-Matrix kernels and multicore architectures position SpDCache as a versatile, scalable solution for modern sparse matrix processing.
This thesis advances the state-of-the-art in cache architectures for sparse data, emphasizing intrinsic understanding and adaptive, structure-aware design for high-performance hardware solutions.

Titre : Conception d'un Système Mémoire pour Traitement de Données Creuses
Mots-clés : calcul scientifique, données creuses, système mémoire
Résumé : Les matrices creuses sont omniprésentes dans les applications gourmandes en données, telles que le calcul scientifique, l’analyse de graphes et l’apprentissage automatique.
Pourtant, leurs schémas d’accès mémoire irréguliers posent des défis majeurs pour les architectures d’ordinateurs et de mémoires traditionnelles. Cette thèse aborde le défi central de la conception de mécanismes matériels et architecturaux pour prendre en charge efficacement le traitement des données creuses, en mettant l’accent sur la scalabilité, l’adaptabilité et les hautes performances. Nous analysons les algorithmes fondamentaux de multiplication de matrices creuses, à savoir Inner-Product, Outer-Product et Gustavson, et identifions leurs défis matériels, séparés en problèmes de gather (recherche d’intersections) et de scatter (réductions aléatoires). L’algorithme de Gustavson s’impose comme le plus prometteur pour une implémentation matérielle en raison de ses compromis équilibres, tandis que l’algorithme Outer-Product est particulièrement adapte aux opérations matrice-vecteur. Notre contribution principale est SpDCache, une architecture de cache de réduction basée sur des régions qui optimise les transactions mémoire pour les données creuses en exploitant les propriétés structurelles des matrices bandées. SpDCache partitionne la mémoire cache en régions denses et creuses, réduisant significativement le trafic mémoire par rapport aux caches génériques. Les contributions clés incluent :
• Conception architecturale et modélisation : Un modèle de simulation basé sur Python et un modèle probabiliste en C analysent les transactions mémoire de SpDCache, révélant l’importance de la structure matricielle a gros grain (par exemple, les matrices bandées).
• Implémentation micro architecturale : Des simulations au niveau RTL valident l’efficacité de SpDCache dans la réduction du trafic mémoire et l’amélioration de l’utilisation du cache, avec un partitionnement virtuel de la mémoire garantissant flexibilité et adaptabilité. Une analyse approfondie révèle l’importance de la structure matricielle a grain fin pour optimiser les performances (en particulier la densité des lignes de cache).
• Optimisations et scalabilité : Des extensions aux multiplications matrice-matrice et aux architectures multicœurs positionnent SpDCache comme une solution polyvalente et évolutive pour le traitement moderne des matrices creuses.
Cette thèse fait progresser l’état-de-l ’art des architectures de cache pour les données creuses, en mettant l’accent sur une compréhension intrinsèque et une conception adaptative et sensible a la structure pour des solutions matérielles hautes performances.