Das Kompressionsverfahren der Bitverschiebung

Inhalt:

Einleitung:
Theorie:
Das Verfahren:
Anmerkungen zur Verwendung mit dem Parallelen LES-Modell Palm-1
Index der verwendeten Variablen:

Einleitung:

An dieser Stelle soll ein Kompressionsverfahren beschrieben werden, das verwendet werden kann , um Gleitkommazahlen (einfacher oder doppelter Genauigkeit) zu komprimieren. Geeignet ist das Verfahren allerdings nur für Daten, bei denen es nicht auf eine hohe Genauigkeit ankommt. Dies kann z.B. für Daten zur grafischen Darstellung der Fall sein. Z.B. reichen zur Darstellung eines Temperaturfeldes häufig 1 oder 2 Nachkommastellen.
Das hier beschriebene Verfahren beruht auf einem Prototyp von Dr. Alexander Beck-Ratzka, dem an dieser Stelle ein herzlicher Dank ausgesprochen werden soll. Dieser Prototyp wurde den hier gegebenen Problemen entsprechend modifiziert und erweitert.

Theorie:

Nach dem 1985 festgelegten Binary Floating Point Arithmetic Standard (754-1985) des IEEE (Institute for Electrical and Electronic Engineers) wird eine long real-Zahl durch eine 64-bit-Darstellung repräsentiert:

Bits	Bitzahl	Bedeutung	Abk.
64	1	Vorzeichen	s
63-53	11	Exponent	E
52-1	52	Mantisse	M
-	-	Basis (Rechnerabhängig)	B

Eine Zahl wird dann in der Form

(-1)^s*B^E-1023*(1+M)

dargestellt. Diese Darstellung gewährt eine Genauigkeit von 15 bis 16 Dezimalstellen bei Normalisierung (keine 0 an führender Nachkommastelle). Diese Genauigkeit ist häufig nicht notwendig, die 15. Nachkommastelle eines Temperaturwertes läßt sich auch mit den heutigen technischen Möglichkeiten nicht bestimmen. Zur grafischen Darstellung ist es oft ausreichend, nur eine oder zwei Nachkommastellen zu berücksichtigen. Eine derart reduzierte Zahl bedarf aber keiner 64 Bit-Darstellung.

Das Verfahren:

Einleitung:

Angenommen es existiert ein Datensatz von 1000 Temperaturmeßwerten zwichen -3.453 und +22.236 °C. Alle diese Werte sind auf doppeltgenauer Zahlendarstellung gespeichert. Dann belegen diese 1000 Werte 8000 Byte Speicherplatz. Bei den heute durchgeführten numerischen Simulationen werden aber weitaus größere Zahlen von Datenpunkten verwandt (ich rechne z. Zt. mit 120x120x80 = 1152000 Datenpunkte zu je 8 Byte , also fast 9MB Speicherplatz pro Datensatz). Bei steigender Anzahl von Datensätzen steigt der benötigte Speicherplatz rasch in GigaByte-Bereiche. Neben der Datenlagerung ist aber auch die Verarbeitungsgeschwindigkeit ein Kriterium, das die Datenkompression geraten erscheinen läßt.

Genauigkeits-Skalierung:

Bleiben wir beispielhaft bei dem obigen Temperaturfeld. Zunächst wählt man die Genauigkeit, die die Zahlenwerte nach der Kompression noch haben soll, sagen wir p = 2 (p:precision) Nachkommastellen interessieren uns. Dann multipliziert man jeden Datenpunkt mit 10^p=10²=100. Das entstandene Feld speichert man auf ein Inetegerfeld um, wodurch Nachkommastellen abgeschnitten werden. Genauer ist jedoch eine Umwandlung von Gleitkomma- in Integerwerte mit Rundung. Das Minimum des neuen Feldes beträgt dann -345, das Maximum +2224.

Minimums-Skalierung:

Im nächsten Schritt skaliert man das entstandene Integerfeld, indem man von jedem Datenwert das Minimum subtrahiert. Man verschiebt sozusagen die Zahlenachse, bis das Minimum des Ausgangsfeldes auf der Null zu liegen kommt.

F_neu = F_alt - Min(F_alt)

Das Feldminimum ist ein Parameter, der für die Dekomprimierung des Feldes benötigt wird. Das auf diese Weise skalierte Integerfeld hat als Minimum nun 0, als Maximum den Wert 2569

Berechnung der benötigten Bitzahl:

Im 3. Schritt wird die Anzahl der Bits bestimmt, mit der jeder Datenwert dargestellt werden kann. Dabei ist der Maximalwert des Feldes ausschlaggebend. Kann er durch eine bestimmte Anzahl von Bits dargestellt werden, so kann es auch jeder andere Wert des Feldes. Die Bestimmung der notwendigen Bitzahl geschieht am einfachsten durch einen Vergleich des Maximalwertes mit den Werten eines Feldes von Bitmasken, die folgendermaßen definiert wird:

mask_i = 2ⁱ-1= 1,3,7,15,31,63,127,255,511,... (i=1,...,32)

Diese Masken repräsentieren Ganzzahlen, bei denen jeweils alle Bits 1-i gesetzt sind, wobei Bit 1 das am weitesten rechts stehende bezeichne (z.B. 63 dezimal = 111111 binär = 2⁶-1). Der Vergleich könnte in Fortran90 dann wie folgt aussehen:

  nsize = 1
  DO WHILE (mask(nsize) < ampl)
     nsize = nsize + 1
  END DO

nsize gibt dabei die Anzahl von Bits an, die zur Darstellung des Maximums des skalierten Integerfeldes benötigt werden. Für das verwendete Beispiel bedeutet dies, daß jede Zahl des Datensatzes durch 12 Bit (2¹²-1=4095) dargestellt werden kann. Wurde die Zahl ehemals durch eine doppelt genaue Gleitkommazahl repräsentiert (zumeist 64 Bit = 8 Byte), so erhält man - freilich auf Kosten eines gewissen Genauigkeitsverlusts - einen Kompressionsfaktor von 5,3.
Nun stellt sich aber das Problem, daß kaum eine Programmiersprache (gibt es überhaupt eine?) Variablen beliebiger Bitgröße zuläßt. Man behilft sich nun damit, daß man sich ein Feld bereitstellt, dessen minimale Größe sich aus dem Produkt der Anzahl der Datenpunkte mit der benötigten Bitzahl ergibt. Beispiel: Für 1000 Datenpunkte zu je 12 Bit benötigt man 12000 Bit = 1500 Byte. Beträgt die Größe eines Integers 4 Byte, so stelle man Speicher für 375 Integerwerte bereit. In manch anderem Fall mag diese Rechnung nicht glatt aufgehen. Wäre die benötigte Bitzahl pro Wert z.B. 13, so wäre ein Feld von 406.25 Integern vonnöten, um alle komprimierten Datenpunkte zu erfassen. In einem solchen Fall wähle man die nächst höhere Ganzzahl und nehme ein paar unbenutzte Bits am Ende des Datensatzes in Kauf.

Bitverschiebung:

Wie bekommt man nun aber die Zahlen in das neu bereitgestellte Feld? Zur Beantwortung dieser Frage muß man wissen, daß in der binären Zahlendarstellung jedes Datenpunktes des skalierten Integerfeldes jeweils nur die nsize am weitesten rechts stehenden Bits von Null verschieden sein können (Durch die Minimumskalierung enthält das Feld nur positive Werte. Somit kann auch das Vorzeichenbit nicht gesetzt sein). Diese Bits muß man nun um eine entsprechende Zahl (32-nsize) nach links verschieben. Dies ist mit geeigneten Unterprogrammen und Funktionen der verwendeten Programmiersprache (z.B. <<-Operator in C oder ISHFT in Fortran90) möglich oder aber, wenn solche Funktionen nicht zur Verfügung stehen, dann mache man von der Eigenschaft gebrauch, daß in binärer Zahlendarstellung eine Verschiebung um 1 Bit nach links einer Multiplikation der Zahl mit 2 entspricht (schneller ist allerdings die direkte Bit-Verschiebung). Hat man die Verschiebung für die erste Zahl durchgeführt, so hat man noch die rechten nfrei=32-nsize Bits der ersten Integerzahl im Packfeld frei. Für nsize < nfrei paßt dort also noch mindestens eine weitere Zahl ganz hinein. Die zweite Zahl wird also um 32-2*nsize Bits nach links verschoben und auf die erste Zahl des Packfeldes addiert. So fährt man fort, bis keine weitere Zahl mehr ganz auf die Integerzahl des Packfeldes paßt.
Danach stehen für die folgende Zahl nur noch 32-(n*nsize) Bits zur Verfügung, wobei n die Anzahl der bereits gepackten Zahlen ist. Für unser Beispiel bedeutet dies, daß, nachdem zwei Zahlen gepackt worden sind, keine weitere Zahl ganz in den Speicherbereich der ersten Zahl des Packfeldes paßt; nur 8 Bit sind noch frei (nfrei=32-2*12=8). Die folgende Zahl muß also aufgeteilt werden: die letzten 4 Bit werden in den Speicherbereich der folgenden Zahl des Packfeldes ganz nach links geschrieben, während die Bits 5-12 noch in die verbleibenden 8 Bit passen. Hier wird es etwas kompliziert. Es kommen erneut die Bitmasken zum Einsatz. Man wähle die Bitmaske mask(nfrei), verschiebe diese um nsize-nfrei Bits nach links, mache einen Bitweisen UND-Vergleich und verschiebe das Resultat wieder um nsize-nfrei Bits zurück (nach rechts). Dann braucht man nur noch diese Zahl auf die erste Zahl des Packfeldes zu addieren und man hat diese vollständig beschrieben. Nun schneide man die letzten 4 Bit des Datenwertes aus (bitweises UND von mask(4) und dem Wert), verschiebe das entstehende Bitmuster um 32-4 Bits nach links und schreibe dies auf die zweite Zahl des Packfeldes. Für alle weiteren Zahlen verfahre man analog.
Dies liest sich sicher sehr verwirrend an, ist aber in der programmtechnischen Realisierung recht einfach. Eine F90-Unterroutine könnte z.B. so aussehen:

MODULE bpack
  INTEGER, PARAMETER ::  ip4 = SELECTED_INT_KIND ( 9 )
  integer(ip4) imask (16) !! Feld fuer Bitmasken.
  integer(ip4), dimension(:), allocatable :: feld, feldabw, packfeld
  integer :: feldmax = 0, feldmin = 0, ampl = 0
  integer :: npack = 0, nsize = 1, offset = 0, lbits = 0, size = 15
  integer laenge
  real :: faktor = 1.0
END MODULE bpack

subroutine bitpack
  !****************************************************************
  USE bpack
  !
  !----- Deklarationen
  !
  IMPLICIT NONE
  !
  !----- Interna.
  !
  INTEGER :: i,ii,dummy1,dummy2,anfpos,nfrei
  INTEGER(ip4) :: mask
     !
     !----- Das Packen.
     !
     anfpos = 0
     ii = 1
     !
     DO i=1,laenge
        !
        dummy1 = IAND(feld(i),imask(nsize))
        !
        nfrei = 32 - anfpos - nsize
        IF (nfrei > 0) THEN ! Info in Wort ii anfuegen.
           anfpos = anfpos + nsize
           dummy2 = ISHFT(dummy1,nfrei)
           packfeld(ii) = packfeld(ii) + dummy2
        ELSE IF (nfrei .EQ. 0) THEN ! Mit neuem Info ist Wort ii voll!
           packfeld(ii) = packfeld(ii) + dummy1
           ii = ii+1
           anfpos = 0
        ELSE ! Info muss auf ii und ii+1 verteilt werden.
           dummy2 = ISHFT(dummy1,nfrei)
           packfeld(ii) = packfeld(ii) + dummy2 
           packfeld(ii+1) = ISHFT(dummy1, 32+nfrei)
           ii = ii+1
           anfpos = -nfrei
        ENDIF
        !
     END DO
     !
  RETURN
  !
  !---- Ende von *bitpack*
  !
END SUBROUTINE bitpack

Anmerkungen zur Verwendung mit dem Parallelen LES-Modell Palm-1

Ein Problem bei der Verwendung dieses Kompressionsverfahrens mit Modellen für massiv parallele Recher mit verteiltem Speicher wie PALM-1, die mit einer Gebietszerlegung arbeiten, ist, daß ein Prozessor jeweils nur ein Teilgebiet behandelt, und auch nur dieses Teilgebiet im Speicher hat. Will man den Vorteil der parallelen Abarbeitung auch fuer den Kompressionsalgorithmus nutzen, so hat man es mit einigen Schwierigkeiten zu tun: Zum einen schriebt jeder Prozessor seine eigene Ausgabedatei. Im unkomprimierten Fall war das nicht das Problem, da jeder Wert eines Teilfeldes ein wohldefiniertes Koordinatentriple (x,y,z) hatte. Auf diese Weise ließ sich das Feld Problemlos wieder zusammenfügen, indem auf diese Koordinaten zugegriffen wurde. Im komprimierten Feld ist diese Zuordnung nun aber nicht mejr möglich, da jetzt mehrere Datenpunkte und teilweise sogar Bruchteile davon auf einem Integer-Wert abgelegt sind. Dazu kommt noch, daß die im Gesamtfeld nebeneinander im Speicher liegen sollten durch die Gebietsaufteilung getrennt werden. Dazu ein Beispiel: Es liegen alle x-Werte eines Teilgebiets zu einem y-Wert nacheinander im Speicher, dann folgen alle x-Werte zum naechsten y-Wert, usw.. Der betrachtete Prozessor habe noch einen Nachbar-Prozessor in x-Richung. Um im Gesamtfeld die exakte Reihenfolge der Daten zu erhalten müßten aber alle x-Werte aller Prozessoren nacheinander im Speicher liegen, gefolgt von allen x-Werten aller Prozessoren zum nachfolgenden y-Wert. Im unkomprimierten Fall ist das wegen der einfachen Zuordnung über die Koordinaten nicht problematisch, diese entfällt nun aber. Zudem können letzter x-Wert zum einen und erster x-Wert zum nachfolgenden y nun auf einem Integer liegen, was eine spätere Zuordnung noch erschwert. Hier bieten sich nun mehrere Lösungsmöglichkeiten an. Eine elegante, aber programmieraufwendige Möglichkeit besteht darin, auf den einzelnen Prozessoren jeweils Schnittflächen des GEsamtgebietes zu sammeln, diese zu komprimieren und auszugeben. Dazu wäre aber ein umfangreicher Datenaustausch zwischen den Prozessorelementen nötig. Dafür hätte man die Möglichkeit, die Dateien einfach in der richtigen Reihenfolge aneinander zu hängen. Aus zeitgründen haben wir uns im Fall PALM-1 aber zu einem anderen Verfahren entschlossen. Dabei komprimiert jeder Prozessor sein Teilvolumen und gibt diese auf Datei aus. In einer anschließenden Nachbehandlung werden diese Dateien mit dem Tar-Kommando archiviert. Da 3D-Daten von uns vornehmlich mit AVS visualisiert werden, wurde ein Modul entwickelt, das die entstandene Tar-Datei temporär auspackt, die Teilvolumen einliest, dekomprimiert und in die richtige Reihenfolge ordnet. Ansonsten ist das Modul read compressed field mit dem Standard-AVS-Modul read field vergleichbar, wenngleich auch nicht so umfangreich ausgestattet. Zusätzlich existiert ein weiteres Modul, write compressed field, das ein 3D-AVS-Feld mit dem beschriebenen Verfahren komprimiert und auf Datei schreibt (weitere Informationen unter dem Link). Durch einfache Kombination read_compressed_field und write_compressed_field erhält man eine Datei, die das gesamte komprimierte Feld in der exakten Reihenfolge beinhaltet. Dies spart das temporäre entpacken der Tar-Datei und das Neuordnen des Feldes.

Index der verwendeten Variablen:

Name	Typ	Bedeutung
anfpos	Integer	Position ab der Informationen auf den Speicherbereich eines Elementes des Packfeldes geschrieben werden soll
feld	Integer()	Feld auf dem die skalierten (Genauigkeits- und Minimumskalierung) Daten abliegen
feldmax	Integer	Wertemaximum des auf die zu verwendende Genauigkeit skalierten Feldes
feldmin	Integer	Werteminimum des auf die zu verwendende Genauigkeit skalierten Feldes
laenge	Integer	Anzahl der verwendeten Datenpunkte
nfrei	Integer	Die im Speicherbereich eines Elementes des Packfeldes noch unbenutzten Bits
nsize	Integer	Anzahl der Bits, durch die alle Datenwerte des gepackten Feldes dargestellt werden
packfeld	Integer()	Feld, in dem die komprimierten Daten abgelegt werden