Compression Methods for Structured Floating-Point Data and their Application in Climate Research

The use of new technologies, such as GPU boosters, have led to a dramatic
increase in the computing power of High-Performance Computing (HPC)
centres. This development, coupled with new climate models that can better
utilise this computing power thanks to software development and internal
design, led to the bottleneck moving from solving the differential equations
describing Earth’s atmospheric interactions to actually storing the variables.
The current approach to solving the storage problem is inadequate: either
the number of variables to be stored is limited or the temporal resolution
... mehr
of the output is reduced. If it is subsequently determined that another vari-
able is required which has not been saved, the simulation must run again.
This thesis deals with the development of novel compression algorithms
for structured floating-point data such as climate data so that they can be
stored in full resolution.
Compression is performed by decorrelation and subsequent coding of
the data. The decorrelation step eliminates redundant information in the
data. During coding, the actual compression takes place and the data is
written to disk. A lossy compression algorithm additionally has an approx-
imation step to unify the data for better coding. The approximation step
reduces the complexity of the data for the subsequent coding, e.g. by using
quantification. This work makes a new scientific contribution to each of the
three steps described above.
This thesis presents a novel lossy compression method for time-series
data using an Auto Regressive Integrated Moving Average (ARIMA) model
to decorrelate the data. In addition, the concept of information spaces and
contexts is presented to use information across dimensions for decorrela-
tion. Furthermore, a new coding scheme is described which reduces the
weaknesses of the eXclusive-OR (XOR) difference calculation and achieves
a better compression factor than current lossless compression methods for
floating-point numbers. Finally, a modular framework is introduced that
allows the creation of user-defined compression algorithms.
The experiments presented in this thesis show that it is possible to in-
crease the information content of lossily compressed time-series data by
applying an adaptive compression technique which preserves selected data
with higher precision. An analysis for lossless compression of these time-
series has shown no success. However, the lossy ARIMA compression model
proposed here is able to capture all relevant information. The reconstructed
data can reproduce the time-series to such an extent that statistically rele-
vant information for the description of climate dynamics is preserved.
Experiments indicate that there is a significant dependence of the com-
pression factor on the selected traversal sequence and the underlying data
model. The influence of these structural dependencies on prediction-based
compression methods is investigated in this thesis. For this purpose, the
concept of Information Spaces (IS) is introduced. IS contributes to improv-
ing the predictions of the individual predictors by nearly 10% on average.
Perhaps more importantly, the standard deviation of compression results is
on average 20% lower. Using IS provides better predictions and consistent
compression results.
Furthermore, it is shown that shifting the prediction and true value leads
to a better compression factor with minimal additional computational costs.
This allows the use of more resource-efficient prediction algorithms to
achieve the same or better compression factor or higher throughput during
compression or decompression. The coding scheme proposed here achieves
a better compression factor than current state-of-the-art methods.
Finally, this paper presents a modular framework for the development
of compression algorithms. The framework supports the creation of user-
defined predictors and offers functionalities such as the execution of bench-
marks, the random subdivision of n-dimensional data, the quality evalua-
tion of predictors, the creation of ensemble predictors and the execution of
validity tests for sequential and parallel compression algorithms.
This research was initiated because of the needs of climate science, but
the application of its contributions is not limited to it. The results of this the-
sis are of major benefit to develop and improve any compression algorithm
for structured floating-point data.

Der Einsatz von neuen Technologien, wie GPU-Boostern, haben zu einem
dramatischen Anstieg der Rechenleistung von HPC-Zentren geführt. Diese
Entwicklung gekoppelt mit neuen Klimamodellen, welche diese Rechenleis-
tung dank Softwareentwicklungen und internem Aufbau besser auslasten
können, führte dazu, dass sich der Engpass weg von der Lösung der Differ-
entialgleichungen hin zur eigentlichen Speicherung der Variablen verschob.
Der aktuelle Ansatz zur Lösung des Speicherproblems ist unzureichend: En-
tweder wird die Anzahl der zu speichernden Variablen begrenzt oder die
... mehr
zeitliche Auflösung der Ausgabe reduziert. Sollte im Nachhinein festgestellt
werden, dass eine weitere Variable notwendig ist, welche nicht gespeichert
wurde, muss die Simulation von neuem laufen. Diese Arbeit beschäftigt
sich mit der Entwicklung neuartiger Kompressionsalgorithmen für struk-
turierte Gleitkommazahlen wie Klimadaten, damit diese in voller Auflösung
gespeichert werden können.
Komprimierung erfolgt durch Dekorrelation und anschließende
Kodierung der Daten. Der Dekorrelationsschritt eliminiert redundante
Informationen in den Daten. Bei der Kodierung findet die eigentliche
Kompression statt und die Daten werden auf die Festplatte geschrieben.
Ein verlustbehafteter Kompressionsalgorithmus hat zusätzlich einen
Annäherungsschritt, um die Daten für die Kodierung zu vereinheitlichen.
Der Annäherungsschritt reduziert die Komplexität der Daten, indem z.B.
Methoden der Quantifizierung verwendet werden. Diese Arbeit leistet zu
jedem der drei oben beschriebenen Schritte einen neuen wissenschaftlichen
Beitrag.
In dieser Dissertation wird ein neuartiges verlustbehaftetes Kompres-
sionsverfahren für Zeitreihendaten vorgestellt, welches ein Auto Regres-
sive Integrated Moving Average (ARIMA) Modell zur Dekorrelation der
Daten verwendet. Darüber hinaus wird das Konzept der Information-
sräume und -kontexte vorgestellt, um Informationen über Dimensionen
hinweg besser für die Dekorrelation zu nutzen. Weiterhin wird ein neues
Kodierungsschema beschrieben, welches die Schwächen der eXclusive-
OR (XOR)-Differenzberechnung reduziert und einen besseren Kompres-
sionsfaktor erreicht als aktuelle verlustfreie Kompressionsverfahren für
Gleitkommazahlen. Schließlich wird ein modulares Framework eingeführt,
das die Erstellung von benutzerdefinierten Kompressionsalgorithmen er-
möglicht.
Die in dieser Dissertation aufgeführten Experimente zeigen, dass es
möglich ist, den Informationsgehalt von verlustbehaftet komprimierten
Zeitreihendaten durch die Anwendung eines adaptiven Kompressionsver-
fahrens zu erhöhen. Eine Analyse für verlustfreie Kompression dieser
Zeitreihen hat keinen Erfolg gezeigt. Das hier vorgeschlagene verlustbe-
haftete ARIMA-Kompressionsmodell ist jedoch in der Lage alle relevanten
Informationen zu erfassen. Die Rekonstruktion der Daten kann die Zeitrei-
hen so weit reproduzieren, dass statistisch relevante Informationen zur
Beschreibung der Klimadynamik erhalten bleiben.
Diese Arbeit zeigt, dass eine signifikante Abhängigkeit des Kompres-
sionsfaktors von der gewählten Traversierung und dem zugrunde liegen-
den Datenmodell besteht. Der Einfluss dieser strukturellen Abhängigkeiten
auf Vorhersage-basierende Kompressionsverfahren wird in dieser Arbeit
untersucht. Es werden Möglichkeiten vorgestellt diese Abhängigkeiten zu
entdecken und den Kompressionsfaktor zu verbessern. Hierfür wird das
Konzept der Information Spaces (IS) eingeführt, welches dazu beiträgt, die
Vorhersagen der einzelnen Prädiktoren um durchschnittlich fast 10% zu
verbessern. Vielleicht noch wichtiger jedoch ist, dass die Standardabwe-
ichung der Kompressionsergebnisse um durchschnittlich über 20% ver-
ringert wird. Die Verwendung des IS-Ansatzes bietet bessere Vorhersagen
und konsistente Kompressionsergebnisse.
Weiterhin wird gezeigt, dass ein besserer Kompressionsfaktor mit min-
imalen Rechenkosten erreicht wird, wenn vor der Differenzberechnung
die Vorhersage und der wahre Wert verschoben werden. Das ermöglicht
die Verwendung von ressourcenschonenderen Vorhersagealgorithmen, um
den gleichen oder besseren Kompressionsfaktor oder einen höheren Durch-
satz während der Kompression bzw. Dekompression zu erreichen. Darüber
hinaus erreicht das hier vorgeschlagene Kodierungsschema einen besseren
Kompressionsfaktor als der aktuelle Stand der Technik.
Schließlich wird in dieser Arbeit ein modulares Framework zum Aufbau
eigener Kompressionsalgorithmen zur Verfügung gestellt. Dieses Frame-
work unterstützt die Erstellung von benutzerdefinierten Prädiktoren und
weitere Funktionen wie die Ausführung von Benchmarks, die zufällige Un-
terteilung von n-dimensionalen Daten, die Qualitätsbewertung von Prädik-
toren, die Erstellung von Ensemble-Prädiktoren und die Ausführung von
Gültigkeitstests für sequentielle und parallele Kompressionsalgorithmen.
Diese Forschung wurde durch Bedürfnisse der Klimawissenschaften be-
gründet. Letztendlich sind die Ergebnisse aber nicht auf die Klimawis-
senschaften beschränkt. Die Ergebnisse dieser Arbeit sind zur Entwicklung
und Verbesserung eines beliebigen Kompressionsalgorithmus für strukturi-
erte Gleitkommazahlen von großem Nutzen.