Loading…
Thumbnail Image

Accelerating approximate data analysis with parallel processors

Kiefer, Martin

Approximate data analysis trades off accuracy for faster or cheaper results. Instead of performing data analyses on the entire data, space-efficient summaries are constructed and evaluated. Applications from various domains, such as databases, computational biology, and machine learning, require accepting a loss in accuracy to gain the desired throughput and response times with limited resources. Specialized parallel processors, such as graphics processing units (GPUs) and field-programmable gate arrays (FPGAs), promise substantial gains in the efficiency of approximate analyses. However, exploiting these architectures is challenging as it requires considering an architecture's properties and explicitly designing and implementing for parallelism. In this thesis, we investigate novel approaches to maintaining and evaluating data summaries on parallel processors: First, we propose kernel density models for GPU-accelerated join selectivity estimation in relational databases. Our estimators do not require common error-prone assumptions and typically provide higher accuracy than the state of the art. Furthermore, the estimators fit the massively parallel computations supported by modern GPUs. In contrast to central processing units (CPUs), our approach allows for larger model sizes and more accurate estimates within the same time budget. Second, we propose Scotch, a holistic approach to implementing FPGA-accelerated sketching at the full rate of the interconnect. The framework generates hardware descriptions for a broad class of sketches based on a common abstraction and domain-specific language. Furthermore, Scotch automatically maximizes the sketch size to boost accuracy. As these tasks commonly require an FPGA expert, Scotch makes FPGA-accelerated sketching more accessible to software engineers. Third, we propose an optimistic data-parallel architecture for FPGA-accelerated sketch summary maintenance. We share resources among inputs instead of pessimistically replicating all resources for every input. Thus, our optimistic architecture reduces the resources required to achieve given throughput for applications that tolerate stalls in processing due to resource congestion. Overall, this thesis shows that specialized parallel processors can substantially increase the efficiency of approximate data analysis while the entry barrier for using them can be lowered substantially by systems and abstractions.
Approximative Datenanalyse ermöglicht es die Genauigkeit von Ergebnissen gegen schnellere oder günstigere Berechnungen einzutauschen. Anstelle der Durchführung von Datenanalysen auf der Gesamtheit der Daten, werden speichereffiziente Zusammenfassungen erzeugt und ausgewertet. Anwendungen aus diversen Bereichen, wie Datenbanken, Bioinformatik und maschinellem Lernen, erfordern diesen Verlust von Genauigkeit, um Anforderungen bezüglich Durchsatz und Antwortzeiten mit begrenztem Ressourcenaufwand zu erreichen. Der aktuelle Trend zu spezialisierten parallelen Rechenarchitekturen wie Grafikprozessoren (GPUs) und Field-Programmable Gate Arrays (FPGAs) verspricht diesen Austausch zusätzlich zu verbessern. Jedoch ist die Verwendung dieser Architekturen nicht trivial, da sie es erfordert, die Eigenschaften der verwendeten Architektur einzubeziehen und Parallelität explizit beim Entwurf und der Implementierung zu berücksichtigen. In dieser Arbeit werden Ansätze zur Erzeugung und Auswertung von Datenzusammenfassungen mit Hilfe paralleler Rechenarchitekturen vorgestellt: Als Erstes stellen wir Kerndichtemodelle für GPU-beschleunigte Schätzung von Joinselektivitäten in relationalen Datenbanken vor. Unsere Schätzer benötigen hierzu keine der gängigen Annahmen und liefern bessere Ergebnisse als der Stand der Technik. Darüber hinaus passen die Schätzer gut zu den von modernen GPUs unterstützten massivparallelen Berechnungen, was im Vergleich zu Hauptprozessoren (CPUs) größere Modelle und dadurch genauere Schätzungen im selben Zeitbudget ermöglicht. Als Zweites stellen wir Scotch vor, einen holistischen Ansatz für die Implementierung FPGA-beschleunigter Erzeugung von Sketchzusammenfassungen mit der vollen Rate des verwendeten Interconnects. Das Framework generiert Hardwarebeschreibungen für eine umfassende Klasse von Sketchingalgorithmen basierend auf einer gemeinsamen Abstraktion und einer entsprechenden domänenspezifischen Sprache. Darüber hinaus maximiert Scotch die Größe der Sketchzusammenfassung automatisch, um die Genauigkeit der Ergebnisse zu maximieren. Da diese Aufgaben üblicherweise einen FPGA-Experten erfordern, macht Scotch das FPGA-beschleunigte Erzeugen von Sketchzusammenfassungen zugänglicher für Softwareentwickler. Als Drittes stellen wir eine optimistische Architektur für die FPGA-beschleunigte datenparallele Erzeugung von Sketchzusammenfassungen vor. Wir schlagen vor, Ressourcen zwischen parallelen Eingabewerten zu teilen, statt pessimistisch alle Ressourcen für jeden Eingabewert zu replizieren. Unsere optimistische Architektur verringert den Verbrauch von Ressourcen, um einen hohen Durchsatz über Datenparallelität zu erreichen, sofern die Anwendung Unterbrechungen durch Überlastung von Ressourcen toleriert. Insgesamt zeigt diese Arbeit, dass spezialisierte parallele Rechenarchitekturen die Effizienz von approximierten Datenanalysen erheblich verbessern können und dass die Eintrittsbarriere für ihre Nutzung durch geeignete Systeme und Abstraktionen gesenkt werden kann.