source: palm/trunk/DOC/tec/methods/bit_compression/bit_compression.html @ 2397

Last change on this file since 2397 was 481, checked in by raasch, 15 years ago

file structure of technical documentation revised; documents concerning numerical methods added

File size: 17.0 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
2<HTML>
3<HEAD>
4 <TITLE>Kompressionsverfahren</TITLE>
5<SCRIPT LANGUAGE="JavaScript1.1">
6<!--
7function footer(){
8Datum = new Date();
9document.writeln("<HR>");
10document.writeln("<TABLE width=100%><TD width=50% align=left bgcolor=orange><I>Layout: <A Href=\"mailto:harbusch@muk.uni-hannover.de\">Guido Harbusch</I></A> &copy;</TD><TD width=50% align=right bgcolor=orange><I>Letzte &Auml;nderung: "+document.lastModified+"</I></TH></TABLE>");
11}
12//--></SCRIPT>
13</HEAD>
14
15<BODY BGCOLOR="antiquewhite">
16<HR>
17<H1>Das Kompressionsverfahren der Bitverschiebung</H1>
18<HR>
19<!-- AS-TOC_BEGIN{ -->
20<H1>Inhalt:</H1>
21
22<OL>
23        <LI><A HREF="#as-h2-1853318">Einleitung:</A>
24        <LI><A HREF="#as-h2-1853319">Theorie:</A>
25        <LI><A HREF="#as-h2-1853320">Das Verfahren:</A>
26        <UL>
27                <LI><A HREF="#as-h3-1853321">Einleitung:</A>
28                <LI><A HREF="#as-h3-1853322">Genauigkeits-Skalierung:</A>
29                <LI><A HREF="#as-h3-1853323">Minimums-Skalierung:</A>
30                <LI><A HREF="#as-h3-1853324">Berechnung der ben&ouml;tigten Bitzahl:</A>
31                <LI><A HREF="#as-h3-1853325">Bitverschiebung:</A>
32        </UL>
33        <LI><A HREF="#as-h2-1853326">Anmerkungen zur Verwendung mit dem Parallelen LES-Modell Palm-1</A>
34        <LI><A HREF="#as-h2-1853327">Index der verwendeten Variablen:</A>
35</OL>
36<!-- AS-TOC_END} -->
37
38
39<H2><A NAME="as-h2-1853318">Einleitung:</A></H2>
40
41An 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&uuml;r Daten, bei denen es nicht auf eine hohe Genauigkeit ankommt. Dies kann z.B. f&uuml;r Daten zur grafischen Darstellung der Fall sein. Z.B. reichen zur Darstellung eines Temperaturfeldes h&auml;ufig 1 oder 2 Nachkommastellen.<BR>
42Das 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.
43
44<H2><A NAME="as-h2-1853319">Theorie:</A></H2>
45Nach dem 1985 festgelegten <EM>Binary Floating Point Arithmetic Standard (754-1985)</EM> des IEEE (<B>I</B>nstitute for <B>E</B>lectrical and <B>E</B>lectronic <B>E</B>ngineers) wird eine <I>long real</I>-Zahl durch eine 64-bit-Darstellung repr&auml;sentiert:<BR>
46<TABLE BORDER="1" FRAME=border RULES=all CELLPADDING="2" ALIGN=center BGCOLOR="lightgrey">
47<TR ALIGN=center><TH>Bits<TH>Bitzahl<TH>Bedeutung<TH>Abk.
48<TR ALIGN=center><TD>64<TD>1<TD>Vorzeichen<TD>s
49<TR ALIGN=center><TD>63-53<TD>11<TD>Exponent<TD>E
50<TR ALIGN=center><TD>52-1<TD>52<TD>Mantisse<TD>M
51<TR ALIGN=center><TD>-<TD>-<TD>Basis (Rechnerabh&auml;ngig)<TD>B
52</TABLE>
53Eine Zahl wird dann in der Form <BR>
54<TABLE ALIGN=center>
55<TR><TD>(-1)<SUP>s</SUP>*B<SUP>E-1023</SUP>*(1+M)
56</TABLE>
57 dargestellt. Diese Darstellung gew&auml;hrt eine Genauigkeit von 15 bis 16 Dezimalstellen bei Normalisierung (keine 0 an f&uuml;hrender Nachkommastelle). Diese Genauigkeit ist h&auml;ufig nicht notwendig, die 15. Nachkommastelle eines Temperaturwertes l&auml;&szlig;t sich auch mit den heutigen technischen M&ouml;glichkeiten nicht bestimmen. Zur grafischen Darstellung ist es oft ausreichend, nur eine oder zwei Nachkommastellen zu ber&uuml;cksichtigen. Eine derart reduzierte Zahl bedarf aber keiner 64 Bit-Darstellung.
58
59<H2><A NAME="as-h2-1853320">Das Verfahren:</A></H2>
60<H3><A NAME="as-h3-1853321">Einleitung:</A></H3>
61Angenommen es existiert ein Datensatz von 1000 Temperaturme&szlig;werten zwichen -3.453 und +22.236 &deg;C. Alle diese Werte sind auf doppeltgenauer Zahlendarstellung gespeichert. Dann belegen diese 1000 Werte 8000 Byte Speicherplatz. Bei den heute durchgef&uuml;hrten numerischen Simulationen werden aber weitaus gr&ouml;&szlig;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&auml;tzen steigt der ben&ouml;tigte Speicherplatz rasch in GigaByte-Bereiche. Neben der Datenlagerung ist aber auch die Verarbeitungsgeschwindigkeit ein Kriterium, das die Datenkompression geraten erscheinen l&auml;&szlig;t.<BR>
62
63<H3><A NAME="as-h3-1853322">Genauigkeits-Skalierung:</A></H3>
64Bleiben wir beispielhaft bei dem obigen Temperaturfeld.
65Zun&auml;chst w&auml;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<SUP>p</SUP>=10<SUP>2</SUP>=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&auml;gt dann -345, das Maximum +2224.<BR>
66
67<H3><A NAME="as-h3-1853323">Minimums-Skalierung:</A></H3>
68Im n&auml;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.<BR>
69<TABLE ALIGN=center>
70<TR><TD>F<SUB>neu</SUB> = F<SUB>alt</SUB> - Min(F<SUB>alt</SUB>)
71</TABLE>
72Das Feldminimum ist ein Parameter, der f&uuml;r die Dekomprimierung des Feldes ben&ouml;tigt wird. Das auf diese Weise skalierte Integerfeld hat als Minimum nun 0, als Maximum den Wert 2569<BR>
73
74<H3><A NAME="as-h3-1853324">Berechnung der ben&ouml;tigten Bitzahl:</A></H3>
75Im 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&szlig;en definiert wird:<BR>
76<TABLE ALIGN=center>
77<TR><TD>mask<SUB>i</SUB> = 2<SUP>i</SUP>-1= 1,3,7,15,31,63,127,255,511,... (i=1,...,32)
78</TABLE>
79
80
81Diese Masken repr&auml;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&auml;r = 2<SUP>6</SUP>-1).
82Der Vergleich k&ouml;nnte in Fortran90 dann wie folgt aussehen:<BR>
83<TABLE ALIGN=center BGCOLOR="lightgrey">
84<TR><TD><PRE>
85  nsize = 1
86  DO WHILE (mask(nsize) < ampl)
87     nsize = nsize + 1
88  END DO
89</PRE>
90</TABLE>
91
92<TT>nsize</TT> gibt dabei die Anzahl von Bits an, die zur Darstellung des Maximums des skalierten Integerfeldes ben&ouml;tigt werden. F&uuml;r das verwendete Beispiel bedeutet dies, da&szlig; jede Zahl des Datensatzes durch 12 Bit (2<SUP>12</SUP>-1=4095) dargestellt werden kann. Wurde die Zahl ehemals durch eine doppelt genaue Gleitkommazahl repr&auml;sentiert (zumeist 64 Bit = 8 Byte), so erh&auml;lt man - freilich auf Kosten eines gewissen Genauigkeitsverlusts - einen Kompressionsfaktor von 5,3.<BR>
93Nun stellt sich aber das Problem, da&szlig; kaum eine Programmiersprache (gibt es &uuml;berhaupt eine?) Variablen beliebiger Bitgr&ouml;&szlig;e zul&auml;&szlig;t. Man behilft sich nun damit, da&szlig; man sich ein Feld bereitstellt, dessen minimale Gr&ouml;&szlig;e sich aus dem Produkt der Anzahl der Datenpunkte mit der ben&ouml;tigten Bitzahl ergibt. Beispiel: F&uuml;r 1000 Datenpunkte zu je 12 Bit ben&ouml;tigt man 12000 Bit = 1500 Byte. Betr&auml;gt die Gr&ouml;&szlig;e eines Integers 4 Byte, so stelle man Speicher f&uuml;r 375 Integerwerte bereit. In manch anderem Fall mag diese Rechnung nicht glatt aufgehen. W&auml;re die ben&ouml;tigte Bitzahl pro Wert z.B. 13, so w&auml;re ein Feld von 406.25 Integern vonn&ouml;ten, um alle komprimierten Datenpunkte zu erfassen. In einem solchen Fall w&auml;hle man die n&auml;chst h&ouml;here Ganzzahl und nehme ein paar unbenutzte Bits am Ende des Datensatzes in Kauf.<BR>
94
95<H3><A NAME="as-h3-1853325">Bitverschiebung:</A></H3>
96Wie bekommt man nun aber die Zahlen in das neu bereitgestellte Feld? Zur Beantwortung dieser Frage mu&szlig; man wissen, da&szlig; in der bin&auml;ren Zahlendarstellung jedes Datenpunktes des skalierten Integerfeldes jeweils nur die <TT>nsize</TT> am weitesten rechts stehenden Bits von Null verschieden sein k&ouml;nnen (Durch die Minimumskalierung enth&auml;lt das Feld nur positive Werte. Somit kann auch das Vorzeichenbit nicht gesetzt sein).
97Diese Bits mu&szlig; man nun um eine entsprechende Zahl <TT>(32-nsize)</TT> nach links verschieben. Dies ist mit geeigneten Unterprogrammen und Funktionen der verwendeten Programmiersprache (z.B. &lt;&lt;-Operator in C oder ISHFT in Fortran90) m&ouml;glich oder aber, wenn solche Funktionen nicht zur Verf&uuml;gung stehen, dann mache man von der Eigenschaft gebrauch, da&szlig; in bin&auml;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&uuml;r die erste Zahl durchgef&uuml;hrt, so hat man noch die rechten <TT>nfrei=32-nsize</TT> Bits der ersten Integerzahl im Packfeld frei. F&uuml;r <TT>nsize &lt; nfrei</TT> pa&szlig;t dort also noch mindestens eine weitere Zahl ganz hinein. Die zweite Zahl wird also um <TT>32-2*nsize</TT> Bits nach links verschoben und auf die erste Zahl des Packfeldes addiert. So f&auml;hrt man fort, bis keine weitere Zahl mehr ganz auf die Integerzahl des Packfeldes pa&szlig;t.<BR>
98Danach stehen f&uuml;r die folgende Zahl nur noch <TT>32-(n*nsize)</TT> Bits zur Verf&uuml;gung, wobei <TT>n</TT> die Anzahl der bereits gepackten Zahlen ist. F&uuml;r unser Beispiel bedeutet dies, da&szlig;, nachdem zwei Zahlen gepackt worden sind, keine weitere Zahl ganz in den Speicherbereich der ersten Zahl des Packfeldes pa&szlig;t; nur 8 Bit sind noch frei (<TT>nfrei=32-2*12=8</TT>). Die folgende Zahl mu&szlig; also aufgeteilt werden: die letzten 4 Bit werden in den Speicherbereich der folgenden Zahl des Packfeldes ganz nach links geschrieben, w&auml;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&auml;hle die Bitmaske <TT>mask(nfrei)</TT>, verschiebe diese um <TT>nsize-nfrei</TT> Bits nach links, mache einen Bitweisen UND-Vergleich und verschiebe das Resultat wieder um <TT>nsize-nfrei</TT> Bits zur&uuml;ck (nach rechts). Dann braucht man nur noch diese Zahl auf die erste Zahl des Packfeldes zu addieren und man hat diese vollst&auml;ndig beschrieben. Nun schneide man die letzten 4 Bit des Datenwertes aus (bitweises UND von <TT>mask(4)</TT> und dem Wert), verschiebe das entstehende Bitmuster um 32-4 Bits nach links und schreibe dies auf die zweite Zahl des Packfeldes. F&uuml;r alle weiteren Zahlen verfahre man analog.<BR>
99Dies liest sich sicher sehr verwirrend an, ist aber in der programmtechnischen Realisierung recht einfach. Eine F90-Unterroutine k&ouml;nnte z.B. so aussehen:<BR>
100<TABLE FRAME=box ALIGN=center BGCOLOR="lightgrey">
101<TR><TD>
102<PRE>
103MODULE bpack
104  INTEGER, PARAMETER ::  ip4 = SELECTED_INT_KIND ( 9 )
105  integer(ip4) imask (16) !! Feld fuer Bitmasken.
106  integer(ip4), dimension(:), allocatable :: feld, feldabw, packfeld
107  integer :: feldmax = 0, feldmin = 0, ampl = 0
108  integer :: npack = 0, nsize = 1, offset = 0, lbits = 0, size = 15
109  integer laenge
110  real :: faktor = 1.0
111END MODULE bpack
112
113subroutine bitpack
114  !****************************************************************
115  USE bpack
116  !
117  !----- Deklarationen
118  !
119  IMPLICIT NONE
120  !
121  !----- Interna.
122  !
123  INTEGER :: i,ii,dummy1,dummy2,anfpos,nfrei
124  INTEGER(ip4) :: mask
125     !
126     !----- Das Packen.
127     !
128     anfpos = 0
129     ii = 1
130     !
131     DO i=1,laenge
132        !
133        dummy1 = IAND(feld(i),imask(nsize))
134        !
135        nfrei = 32 - anfpos - nsize
136        IF (nfrei > 0) THEN ! Info in Wort ii anfuegen.
137           anfpos = anfpos + nsize
138           dummy2 = ISHFT(dummy1,nfrei)
139           packfeld(ii) = packfeld(ii) + dummy2
140        ELSE IF (nfrei .EQ. 0) THEN ! Mit neuem Info ist Wort ii voll!
141           packfeld(ii) = packfeld(ii) + dummy1
142           ii = ii+1
143           anfpos = 0
144        ELSE ! Info muss auf ii und ii+1 verteilt werden.
145           dummy2 = ISHFT(dummy1,nfrei)
146           packfeld(ii) = packfeld(ii) + dummy2
147           packfeld(ii+1) = ISHFT(dummy1, 32+nfrei)
148           ii = ii+1
149           anfpos = -nfrei
150        ENDIF
151        !
152     END DO
153     !
154  RETURN
155  !
156  !---- Ende von *bitpack*
157  !
158END SUBROUTINE bitpack
159</PRE>
160</TABLE>
161<H2><A NAME="as-h2-1853326">Anmerkungen zur Verwendung mit dem Parallelen LES-Modell Palm-1</A></H2>
162Ein Problem bei der Verwendung dieses Kompressionsverfahrens mit Modellen f&uuml;r massiv parallele Recher mit verteiltem Speicher wie <A HREF="http://www.muk.uni-hannover.de/institut/people/raasch/PALM-1/intro.html">PALM-1</A>, die mit einer Gebietszerlegung arbeiten, ist, da&szlig; 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&szlig; sich das Feld Problemlos wieder zusammenf&uuml;gen, indem auf diese Koordinaten zugegriffen wurde. Im komprimierten Feld ist diese Zuordnung nun aber nicht mejr m&ouml;glich, da jetzt mehrere Datenpunkte und teilweise sogar Bruchteile davon auf einem Integer-Wert abgelegt sind. Dazu kommt noch, da&szlig; 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&uuml;&szlig;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 &uuml;ber die Koordinaten nicht problematisch, diese entf&auml;llt nun aber. Zudem k&ouml;nnen letzter x-Wert zum einen und erster x-Wert zum nachfolgenden y nun auf einem Integer liegen, was eine sp&auml;tere Zuordnung noch erschwert. Hier bieten sich nun mehrere L&ouml;sungsm&ouml;glichkeiten an. Eine elegante, aber programmieraufwendige M&ouml;glichkeit besteht darin, auf den einzelnen Prozessoren jeweils Schnittfl&auml;chen des GEsamtgebietes zu sammeln, diese zu komprimieren und auszugeben. Dazu w&auml;re aber ein umfangreicher Datenaustausch zwischen den Prozessorelementen n&ouml;tig. Daf&uuml;r h&auml;tte man die M&ouml;glichkeit, die Dateien einfach in der richtigen Reihenfolge aneinander zu h&auml;ngen. Aus zeitgr&uuml;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&szlig;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&auml;r auspackt, die Teilvolumen einliest, dekomprimiert und in die richtige Reihenfolge ordnet. Ansonsten ist das Modul <TT><A HREF="Modules/read_compressed_field.html">read compressed field</A></TT> mit dem Standard-AVS-Modul <TT>read field</TT> vergleichbar, wenngleich auch nicht so umfangreich ausgestattet. Zus&auml;tzlich existiert ein weiteres Modul, <TT><A HREF="Modules/write_compressed_field.html">write compressed field</A></TT>, 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&auml;lt man eine Datei, die das gesamte komprimierte Feld in der exakten Reihenfolge beinhaltet. Dies spart das tempor&auml;re entpacken der Tar-Datei und das Neuordnen des Feldes.
163
164<H2><A NAME="as-h2-1853327">Index der verwendeten Variablen:</A></H2>
165<TABLE BORDER="2" FRAME=box RULES=all CELLPADDING="1">
166<TR><TH>Name<TH>Typ<TH>Bedeutung
167<TR><TD>anfpos<TD>Integer<TD>Position ab der Informationen auf den Speicherbereich eines Elementes des Packfeldes geschrieben werden soll
168<TR><TD>feld<TD>Integer()<TD>Feld auf dem die skalierten (Genauigkeits- und Minimumskalierung) Daten abliegen
169<TR><TD>feldmax<TD>Integer<TD>Wertemaximum des auf die zu verwendende Genauigkeit skalierten Feldes
170<TR><TD>feldmin<TD>Integer<TD>Werteminimum des auf die zu verwendende Genauigkeit skalierten Feldes
171<TR><TD>laenge<TD>Integer<TD>Anzahl der verwendeten Datenpunkte
172<TR><TD>nfrei<TD>Integer<TD>Die im Speicherbereich eines Elementes des Packfeldes noch unbenutzten Bits
173<TR><TD>nsize<TD>Integer<TD>Anzahl der Bits, durch die alle Datenwerte des gepackten Feldes dargestellt werden
174<TR><TD>packfeld<TD>Integer()<TD>Feld, in dem die komprimierten Daten abgelegt werden
175</TABLE>
176
177<SCRIPT>
178<!--
179footer();
180//-->
181</SCRIPT>
182</BODY>
183</HTML>
Note: See TracBrowser for help on using the repository browser.