Home

Context Navigation

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

Last change on this file since 1041 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	<!--
7	function footer(){
8	Datum = new Date();
9	document.writeln("<HR>");
10	document.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> ©</TD><TD width=50% align=right bgcolor=orange><I>Letzte Ä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ö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
41	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.<BR>
42	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.
43
44	<H2><A NAME="as-h2-1853319">Theorie:</A></H2>
45	Nach 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ä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ängig)<TD>B
52	</TABLE>
53	Eine 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ä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.
58
59	<H2><A NAME="as-h2-1853320">Das Verfahren:</A></H2>
60	<H3><A NAME="as-h3-1853321">Einleitung:</A></H3>
61	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.<BR>
62
63	<H3><A NAME="as-h3-1853322">Genauigkeits-Skalierung:</A></H3>
64	Bleiben wir beispielhaft bei dem obigen Temperaturfeld.
65	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<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ägt dann -345, das Maximum +2224.<BR>
66
67	<H3><A NAME="as-h3-1853323">Minimums-Skalierung:</A></H3>
68	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.<BR>
69	<TABLE ALIGN=center>
70	<TR><TD>F<SUB>neu</SUB> = F<SUB>alt</SUB> - Min(F<SUB>alt</SUB>)
71	</TABLE>
72	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<BR>
73
74	<H3><A NAME="as-h3-1853324">Berechnung der benötigten Bitzahl:</A></H3>
75	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:<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
81	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<SUP>6</SUP>-1).
82	Der Vergleich kö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ötigt werden. Für das verwendete Beispiel bedeutet dies, daß 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äsentiert (zumeist 64 Bit = 8 Byte), so erhält man - freilich auf Kosten eines gewissen Genauigkeitsverlusts - einen Kompressionsfaktor von 5,3.<BR>
93	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.<BR>
94
95	<H3><A NAME="as-h3-1853325">Bitverschiebung:</A></H3>
96	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 <TT>nsize</TT> 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).
97	Diese Bits muß 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. <<-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 <TT>nfrei=32-nsize</TT> Bits der ersten Integerzahl im Packfeld frei. Für <TT>nsize < nfrei</TT> paß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ährt man fort, bis keine weitere Zahl mehr ganz auf die Integerzahl des Packfeldes paßt.<BR>
98	Danach stehen für die folgende Zahl nur noch <TT>32-(nnsize)</TT> Bits zur Verfügung, wobei <TT>n</TT> 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 (<TT>nfrei=32-212=8</TT>). 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 <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ü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 <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ür alle weiteren Zahlen verfahre man analog.<BR>
99	Dies liest sich sicher sehr verwirrend an, ist aber in der programmtechnischen Realisierung recht einfach. Eine F90-Unterroutine könnte z.B. so aussehen:<BR>
100	<TABLE FRAME=box ALIGN=center BGCOLOR="lightgrey">
101	<TR><TD>
102	<PRE>
103	MODULE 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
111	END MODULE bpack
112
113	subroutine 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	!
158	END 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>
162	Ein Problem bei der Verwendung dieses Kompressionsverfahrens mit Modellen fü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ß 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 <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ä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ä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.
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	<!--
179	footer();
180	//-->
181	</SCRIPT>
182	</BODY>
183	</HTML>

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

| Impressum | ©Leibniz Universität Hannover |