title: Fine-grained reuse and feature transformations in machine learning systems
Creators: name: Phani, Arnab
Publisher: name: Technische Universität Berlin
Year: 2025
Subjects: subject: 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
subject: data management
subject: ML systems
subject: data management for data science
subject: data management for ML
subject: caching
subject: reuse
subject: feature transformations

description: Machine learning (ML) and data science workflows are inherently exploratory. Data scientists pose hypotheses, integrate the necessary data, and run ML pipelines of data cleaning, feature engineering, model selection, and hyperparameter tuning. The repetitive nature of these workflows, and their hierarchical composition from building blocks, cause high computational redundancy. This redundancy can be addressed by reusing already computed intermediates. Existing reuse approaches are coarse-grained, treating entire algorithms as black boxes. As a result, they fail to eliminate fine-grained redundancy and to handle internal non-determinism. This coarse-grained view also prevents enabling internal parallelization and optimization within complex, monolithic ML workloads, such as feature transformations. Feature transformations, which convert raw data into numerical matrices for training or scoring, involve multiple passes and expensive string processing, requiring special handling for efficient execution. Modern ML systems leverage multiple backends, including CPUs, GPUs, and distributed execution platforms like Apache Spark or Ray. Depending onworkload and cluster characteristics, these systems typically compile an ML pipeline into hybrid plans of in-memory CPU, GPU, and distributed operations. Prior work applied tailor-made techniques for reusing intermediates in specific backend scenarios. However, achieving efficient holistic reuse in multi-backend ML systems remains a challenge due to its tight coupling with other aspects such as memory management, data exchange, parallelization strategies, and operator scheduling. In this thesis, we introduce a principled framework for efficient, fine-grained lineage tracing and holistic, application-agnostic, multi-backend reuse and memory management, as well as fine-grained task scheduling for feature transformations. The lineage trace of an intermediate exactly identifies that intermediate, facilitating reuse. However, fine-grained lineage tracing introduces challenges, such as the high memory usage overhead. We address the large size of lineage traces with lineage deduplication for loops and functions, and we exploit full and partial reuse opportunities across the program hierarchy. The core component of our framework is a hierarchical lineage-based reuse cache, which acts as a unified abstraction and manages reuse, memory recycling, data exchange, and cache eviction across backends. To address backend-related challenges such as lazy evaluation, asynchronous data exchange, and memory allocation overheads, we devise a suite of cache management policies. Moreover, to efficiently execute feature transformation workloads, we construct a fine-grained task-graph for a set of transformations and optimize the plan according to data characteristics. At runtime, we execute this plan in a cache-conscious manner while performing sub-operator-level reuse of internal intermediates. Finally, we extend an optimizing ML system compiler by special operators for asynchronous exchange, speculative cache management, and related operator ordering for concurrent execution. Our experiments across diverse ML tasks and pipelines show significant improvements compared to state-of-the-art ML systems and specialized frameworks.
description: Workflows des maschinellen Lernens (ML) und der Datenwissenschaften sind inhärent explorativ. Datenwissenschaftler erstellen Hypothesen, integrieren die erforderlichen Daten und führen ML-Pipelines aus, welche aus Datenbereinigung, Feature-Engineering, Modell-Auswahl und Hyperparameter-Tuning bestehen. Die wiederholende Natur dieser Workflows sowie ihre hierarchische Komposition aus Grundbausteinen resultieren in hochgradig redundanten Berechnungen. Dieser Redundanz kann durch die Wiederverwendung bereits berechneter Zwischenergebnisse begegnet werden. Existierende Ansätze zur Wiederverwendung von Berechnungen arbeiten grob-granular, indem sie einen gesamten Algorithmus als Black-Box betrachten. Infolgedessen verfehlen sie das Ziel, Redundanz fein-granular zu eliminieren und internen Nichtdeterminismus zu behandeln. Diese grob-granulare Sicht verhindert außerdem die interne Parallelisierung und Optimierung komplexer, monolithischer ML-Workflows, wie beispielsweise Feature-Transformationen. Feature-Transformationen, welche Rohdaten in für das Training und Scoring geeignete numerische Matrizen umwandeln, arbeiten in mehreren Pässe und beinhalten aufwendige Zeichenketten- Verarbeitung, weshalb ihre effiziente Ausführung spezielle Aufmerksamkeit erfordert. Moderne ML-Systeme nutzen mehrere Backends, wie beispielsweise CPUs, GPUs und verteile Ausführungs-Plattformen wie Apache Spark oder Ray. In Abhängigkeit von Workload- und Cluster-Eigenschaften kompilieren diese Systeme ML-Pipelines typischerweise zu hybriden Plänen von Hauptspeicher-zentrischen CPU-, GPU- und verteilten Operationen. Frühere Arbeiten bedienen sich maßgeschneiderter Techniken zur Wiederverwendung von Zwischenergebnissen in spezifischen Backend-Szenarien. Die ganzheitliche Wiederverwendung in ML-Systemen mit mehreren Backends verbleibt dabei jedoch aufgrund der engen Kopplung mit anderen Aspekten, wie Hauptspeicher-Verwaltung, Datenaustausch, Parallelisierungs-Strategien und Operator- Scheduling, als eine wesentliche Herausforderung. Die vorliegende Arbeit stellt ein fundiertes Framework für effizientes und fein-granulares Lineage-Tracing und die ganzheitliche, anwendungs-agnostische, multi-backend-fähige Wiederverwendung und Hauptspeicher-Verwaltung, sowie für fein-granulares Task-Scheduling für Feature-Transformationen vor. Ein Zwischenergebnis wird eindeutig durch seinen sogenannten Lineage-Trace identifiziert, welcher eine Wiederverwendung ermöglicht. Fein-granulares Lineage-Tracing bringt jedoch spezielle Herausforderungen mit sich, wie beispielsweise einen erhöhten Hauptspeicher-Bedarf. Wir adressieren die besondere Größe von Lineage-Traces mit Lineage-Deduplikation für Schleifen und Funktionen und nutzen Möglichkeiten zur vollen und partiellen Wiederverwendung über die komplette Programm-Hierarchie hinweg. Das Kernstück unseres Frameworks ist ein hierarchischer Lineage-basierter Wiederverwendungs- Cache, welcher als eine einheitliche Abstraktion fungiert und die Wiederverwendung von Zwischenergebnissen, das Recycling von Hauptspeicher, den Datenaustausch und die Cache-Verdrängung über verschiedene Backends hinweg regelt. Zur Adressierung backend-bezogener Herausforderungen, wie beispielsweise Lazy Evaluation, asynchronen Daten-Austauschs sowie des Mehraufwands für Speicher-Allokationen, entwickeln wir eine Reihe von speziellen Cache- Verwaltungs-Strategien. Für die effiziente Ausführung von Feature-Transformation-Workloads wird ein fein-granularer Task-Graph für eine Menge von Transformationen erstellt und unter Einbeziehung der Dateneigenschaften optimiert. Zur Laufzeit wird dieser Plan auf eine Cachebewusste Weise ausgeführt, wobei die Wiederverwendung von Zwischenergebnissen auf einer Sub-Operator-Ebene stattfindet. Wir erweitern den optimierenden Compiler eines ML-Systems um spezielle Operatoren für asynchronen Datenaustausch, spekulative Cache-Verwaltung und entsprechendes Operator-Ordering für die nebenläufige Ausführung. Unsere Experimente mit diversen ML-Aufgaben und -Pipelines belegen signifikante Verbesserungen im Vergleich zu hochmodernen ML-Systemen und spezialisierten Frameworks.