Danksagung

Ich möchte mich bei allen Personen bedanken, die mich bei der Bearbeitung der BELL unterstützt haben, unter anderem bei meinen Eltern für das Korrekturlesen der Arbeit und Herrn Bamme für die schulische Betreuung.

Besonderer Dank gilt meinem externen Betreuer Dr. Andreas Westfeld, der mir von der Themenwahl an bis zur Anfertigung der Arbeit viele wichtige Hinweise und Hilfestellungen gab ohne die ich die Arbeit nicht hätte in dieser Form anfertigen können.

Inhaltsverzeichnis 3

Inhaltsverzeichnis   

1  EINLEITUNG.  5

1.1  WET PAPER CODES  5

1.2  ZIEL DER ARBEIT  7

1.3  DIE ARBEITSWEISE DES ZU UNTERSUCHENDEN ALGORITHMUS  8

2  VORGEHENSWEISE.  11

2.1  GESAMTBETRACHTUNG.  11

2.2  AUFGLIEDERUNG DES ALGORITHMUS.  11

3  METHODEN.  13

3.1  AUSZÄHLEN DER ADDITIONEN  13

3.2  MESSTECHNISCHE ANALYSE MIT GPROF  13

3.3  MESSTECHNISCHE ANALYSE MIT RPROF.  14

4  ANALYSE-ERGEBNISSE  16

4.1  GESAMTBETRACHTUNG DES ALGORITHMUS.  16

4.2  LADEN DER MATRIX  19

4.2.1  Mathematische Analyse  20

4.2.2  Messanalyse.  21

4.3  GAUß-ELIMINATION.  23

4.3.1  Mathematische Analyse  24

4.3.2  Messtechnische Analyse.  31

4.4  VERTAUSCHEN DER SPALTEN.  33

4.4.1  Mathematische Analyse  34

4.4.2  Messtechnische Analyse.  35

4.4.3  Optimierungsmöglichkeit.  38

5  DISKUSSION DER ERGEBNISSE UND AUSBLICK  41

5.1  ZUSAMMENFASSUNG  41

5.2  BEURTEILUNG DER ERGEBNISSE  42

5.3  PERSÖNLICHE ERFAHRUNGEN  43

5.4  AUSBLICK  44

6  LITERATURVERZEICHNIS  45

CD-Verzeichnis

Begleit-CD

readme.txt (enthält CD-Verzeichnis)

├BELL (enthält schriftliche Fassung der BELL in verschiedenen Formaten) BELL.doc BELL.ps BELL.pdf

├Messtabellen (enthält Messwerttabellen für alle Untersuchungen) creatematrix.xls eliminate.xls gesamt.xls swap.xls

├Programmdateien (enthält alle gemessenen Programme/verwendete Quelltexte) ├C-Implementierungen für R ├dll

├skript solvescript.R src

Teiluntersuchungen ├creatematrix solve_P1.c ├eliminate solveElim.c solve_P2.c swap solveOpt.c solve_P3.c

Quellen (enthält alle im Literaturverzeichnis angegebenen Quellen) Bogdanov, Mertens, Paar, Pelzl, Rupp(2006).pdf Böhler(2007).pdf

Fridrich, Goljan, Soukal, Lisonek(2004).pdf Hommel(2004).pdf Mayer(2006).pdf Strassen(1968).pdf

www.mikrocontroller.net - Digitaltechnik.URL www.numerik.mathematik.uni-mainz.de - LR-Zerlegung.URL

1 Einleitung

Die Steganographie beschäftigt sich mit dem Verstecken von Nachrichten in Trägerobjekten unter dem Ziel Botschaften geheim an einen Empfänger zu übermitteln. In dieser Arbeit wird ein Algorithmus einer Methode untersucht, die den so genannten Wet Paper Codes ¹ von Jessica Fridrich, Miroslav Goljan, David Soukal und P. Lisoněk zuzuordnen ist.

1.1 Wet Paper Codes

Mithilfe von Wet Paper Codes soll es dem Angreifer wesentlich erschwert werden, zu erkennen, ob eine Nachricht in einem Trägerobjekt versteckt ist, bzw. welche Stellen im Trägerobjekt modifiziert wurden. Nur der Empfänger soll die Nachricht extrahieren können. Um auszuschließen, dass ein möglicher Angreifer entdeckt, dass eine Nachricht verschickt wurde, wird zuvor ein Schlüssel zwischen Sender und Empfänger ausgetauscht, der dazu dient bestimmte Stellen in den Trägerobjekten zu bestimmen, die während der Nachrichteneinbettung geändert werden müssen.

Anhand der Abbildung 1 soll die Metapher von Wet Paper Codes veranschaulicht werden. Vor dem Nachrichtenaustausch geschieht ein Schlüsselaustausch, wobei Sender und Empfänger den gleichen Schlüssel besitzen. Der Sender besitzt nun das wet paper (dt. "nasses Papier"). Da einige Stellen auf dem Dokument nass sind, kann der Sender nur auf von ihm ausgewählte trockene Stellen schreiben. Denn beim Schreiben auf nasse Stellen würde die Tinte verlaufen und ein Angreifer könnte später nachvollziehen welche Stellen verändert wurden. Der Sender benutzt den Schlüssel um diejenigen trockenen Stellen zu bestimmen, welche geändert werden müssen um die Nachricht einzubetten. Während die Nachricht verschickt wird, trocknen die nassen Stellen aus. Einem möglichen Angreifer und dem Empfänger sind nicht bekannt, welche Stellen schon zu Anfang an trocken waren und somit möglicherweise verändert wurden. Der Empfänger jedoch kann mit dem Schlüssel die Nachricht aus dem versendeten Trägerobjekt extrahieren.

¹ J. Fridrich, M. Goljan, D. Soukal, P. Lisoněk: Perturbed Quantization Steganography with Wet Paper Codes

Anhand eines Beispiels soll nun die genaue Funktionsweise von Wet Paper Codes verdeutlicht werden. Das Beispiel ist an die Vorstellung von Wet Paper Codes von Tobias Hommel ² angelehnt. Da mit Bits gerechnet wird, erfolgen Additionen als Additionen modulo 2. Zunächst benötigt der Sender eine Nachricht m, die er übermitteln möchte. Die Nachricht besitzt die Länge q.

  1   0 m = mit der Nachrichtenlänge q = 3     0

Sender und Empfänger haben zuvor einen Schlüssel ausgetauscht mit dem der Sender eine pseudozufällige binäre Matrix D generiert, die q Zeilen und n Spalten besitzt.

 1 0 1 1 0  1 1 1 0 0 D =   1 0 0 1 1

Als nächstes benötigt der Sender das Trägerobjekt (wet paper). JPEG-Dateien werden wegen ihrer verlustbehafteten Kompression für das Einbetten von Nachrichten bevorzugt. Während der Kompression werden Werte gebildet, die später aufgerundet werden. Darunter sind Werte deren Nachkommateil nahe 0,5 liegt. Diese Werte eignen sich besonders für das Einbetten, da je nach einzubettendem Nachrichtenbit entschieden werden kann, ob auf- oder abgerundet wird. Sie dienen somit als trockene Stellen im wet paper. Würde man versuchen die anderen Werte (nasse Stellen) zum Einbetten zu verwenden, dann verändert man damit das Wahrscheinlichkeitsmuster der Pixelwerte (die Tinte verläuft), womit ein Angreifer erkennt ob etwas eingebettet wurde. Der Sender extrahiert nun den folgenden Vektor b aus dem Trägerobjekt. Dieser Vektor der Länge n enthält die Pixel-LSBs ³ des Trägerobjektes.

1   0   0 b = mit der der Länge n = 5   1 0

Aus b werden nun Pixelwerte ausgewählt, die das oben genannte Kriterium nicht erfüllen. Da die Nachrichtenlänge nur 3 Bit lang ist, können aus den 5 verfügbaren LSBs auch zwei gestrichen werden. In dem Fall sind das b 2 und b 5 . Nun müssen die entsprechenden Spalten der Matrix D gestrichen werden, welche mit den gestrichenen Elementen aus b korrespondieren. Es wird also die 2. und 5. Spalte aus D gestrichen, wodurch eine neue quadratische Matrix H entsteht.

 1 1 1  1 1 0 H =   1 0 1

Das folgende Gleichungssystem muss nun nach v aufgelöst werden. Alle Einsen in v zeigen die Stellen an, welche in b geändert werden müssen. Es ist zu beachten, dass in v genau diejenigen Elemente nicht vorhanden sind, welche in b ausgewählt und gestrichen wurden.

² Hommel, Tobias: Wet Paper Codes

³ LSB: least significant bit (dt. "niedrigstwertige Bit")

  1 1 1   1 1 0 v =   ´¨¨¨¨¨¨¨≠¨¨¨¨¨¨¨Æ   1 0 1

H

 v ¹   1 1 1    v 3 1 1 0  

1 0 1    v 4

Entsprechend dem Ergebnis für v muss also das 3. Element in b geändert werden. So erhält man den Vektor b' der nun die Pixel-LSBs enthält, welche sich in dem zu versendendem Trägerobjekt befinden.

1   0   1 b' =   1 0

Die echte "Magie" von Wet Paper Codes zeigt sich beim Entpacken der Nachricht. Der Empfänger erhält nun das Trägerobjekt und kann die Pixel-LSBs des Trägerobjektes als b' extrahieren. Das sind genau q Elemente. Anschließend kann er mithilfe des zuvor ausgetauschten Schlüssels dieselbe Matrix D mit n Zeilen und q Spalten erzeugen. Es wird davon ausgegangen, dass der Empfänger die Nachrichtenlänge q kennt. Das Produkt von D und b' liefert die Nachricht m.

 1 0 1 1 0  1 1 1 0 0 m =   1 0 0 1 1 ´¨¨¨¨¨¨¨¨¨¨¨≠¨¨¨¨¨¨¨¨¨¨¨Æ D

Der Empfänger besitzt keinerlei Kenntnisse über die Stellen, welche aus dem Trägerobjekt gestrichen wurden (bzw. nass waren). Dennoch konnte die Nachricht an den Empfänger exakt übermittelt werden.

1.2 Ziel der Arbeit

Wie im obigen Beispiel für Wet Paper Codes ersichtlich wurde, muss der Sender ein lineares Gleichungssystem A • x = b im Polynomkörper GF(2 ⁿ ) lösen um herauszubekommen, welche

Stellen im Trägerobjekt geändert werden müssen. Dabei ist die Matrix A zum einen quadratisch und besitzt somit genauso viele Spalten wie Zeilen (sie besitzt den Rang der Nachrichtenlänge q). Zum anderen muss A invertierbar sein, damit das Gleichungssystem gelöst werden kann. Wie im Verlauf der Arbeit ersichtlich wird, hat das Lösen der Gleichung eine kubische Laufzeitkomplexität O(n ³ ) wenn n als Rang der Matrix A definiert ist. Das Lösen des linearen Gleichungssystems ist somit der rechenaufwendigste Prozess im gesamten Aus-tauschvorgang. Für längere Nachrichten z.B. im Kilobyte-Bereich kann das Lösen dieses Gleichungssystems schon sehr lang dauern. Dennoch sollte in der Praxis nicht darauf ver-

zichtet werden größere Informationsmengen wie z.B. Dateien einzubetten und zu verschicken. Zum einen versucht man den Rechenprozess zu beschleunigen indem man das Trägerobjekt in viele kleine Teile zerlegt und für jeden Teil die Gleichung einzeln löst. Zum anderen könnte man versuchen den Algorithmus zur Lösung des Gleichungssystems zu verbessern. Als ich mich über verschiedene Lösungsverfahren von linearen Gleichungssystemen informiert habe, bin ich auf die LR-Zerlegung ⁴ gestoßen. Für den Fall das die Matrix A konstant bleibt und sich nur der Vektor b verändert, muss die Matrix A nur ein einziges mal invertiert werden, wobei A in das Produkt einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix R zerlegt wird. Alle restlichen Berechnungen für verschiedene b erfolgen dann in quadratischer Laufzeit, da L und R lediglich auf den jeweiligen Vektor bezogen rücksubstituiert werden müssen. In der Praxis bedeutet das, dass man für das Einbetten immer denselben Schlüssel und dieselbe Trägerdatei verwendet (beides beeinflusst die Matrix A). Lediglich die Nachricht auf der rechten Seite des Gleichungssystems darf verändert werden. Jedoch sollte das in der Praxis vermieden werden, da ein Angreifer anhand von mehreren ursprünglich gleichen Trägerobjekten und verschieden eingebetteten Nachrichten Rückschlüsse auf die veränderten (trockenen) Stellen schließen kann.

Während der Arbeit wurde im Sinne der Effizienzverbesserung ebenfalls eine Methode von Volker Strassen in Betracht gezogen, die die Komplexität von Matrizenmultiplikationen und Matrizeninversionen von O(n ³ ) auf O(n ^2,07 ) senkt ⁵ . Jedoch erwies sich diese bei genaueren Betrachtungen als unvorteilhaft, denn Strassen versucht durch weniger Multiplikationen und viel mehr Additionen dasselbe Ergebnis zu erzielen. Da Multiplikationen im Normalfall viel länger dauern als Additionen bringt das tatsächlich eine Verringerung der Komplexität. Im zu untersuchenden Algorithmus werden jedoch Additionen durch XOR- und Multiplikationen durch AND-Verknüpfungen realisiert. Da man davon ausgehen kann, dass XOR- und AND-Verknüpfungen gleich schnell ausgeführt werden, bringt die Methode von Strassen in diesem Fall keine Vorteile.

In meiner Arbeit möchte ich eine Laufzeitbetrachtung an dem Algorithmus zur Lösung dieses Gleichungssystems vornehmen. Die Lösung des Gleichungssystems wird in dem zu untersuchenden Algorithmus mit dem Gaußschen Eliminationsverfahren und einer anschließenden Rücksubstitution realisiert. Diese Arbeit beschränkt sich auf die alleinige Betrachtung des Eliminationsverfahrens (ohne Rücksubstitution). Die Elemente der Matrix A werden während des Lösungsverfahrens in Blöcke gepackt und auch Blockweise behandelt. Eine Möglichkeit der Effizienzverbesserung liegt in der Laufzeitbetrachtung für verschiedene Blockgrößen, sowie für den Sonderfall, dass jedes Bit einzeln behandelt wird. In dieser Arbeit sollen diese Varianten miteinander unter dem Ziel verglichen werden, die beste Variante in Abhängigkeit der Blockgröße zu ermitteln und es soll geprüft werden, ob die Laufzeitkomplexität des Algorithmus in Abhängigkeit der Blockgröße verringert werden kann.

1.3 Die Arbeitsweise des zu untersuchenden Algorithmus

Die Ausführungen in diesem Abschnitt beziehen sich vollständig auf den Algorithmus in der Methode gf2_solve() im Quelltext von solve.c ⁶ . Dabei handelt es sich um eine C-Implementierung für die Skriptsprache R ⁷ . Der Algorithmus wurde von den Autoren mit Kommentaren versehen um die anschließenden Schritte besser nachvollziehen zu können. Abbildung 2 stellt die Lösungsschritte für ein Beispiel dar, auf das während der Ausführungen Bezug genommen wird. Das Packen der Bits in Blöcke wird in dem Beispiel jedoch ignoriert.

⁴ Siehe: www.numerik.mathematik.uni-mainz.de: LR-Zerlegung

⁵ Vgl. Volker Strassen: Gaussian Elimination is not optimal

⁶ solve.c: Entwickelt von David Soukal und später ergänzt von Rainer Böhme, Begleit-CD:\Programmdateien\Rimplementierungen\src\solve.c

⁷ R: frei verfügbare Statistik-Umgebung, Entwickler: The R Foundation for Statistical Computing

Abbildung 2: Eliminationsverfahren nach solve.c für eine 3ä 3 Matrix

1. Vorbereitung

Im ersten Abschnitt werden die als R-Objekte übergebenen Parameter (Koeffizientenmatrix A, Vektor b) überprüft. Die Matrix A muss quadratisch sein und der Vektor b sollte genau so viele Elemente besitzen wie die Matrix Spalten besitzt. Zusätzlich wird ein entsprechendes Speicherfeld für die zu bearbeitende Matrix A reserviert. Dieses Speicherfeld besteht aus N * NB Speicherzellen, wobei N dem Rang der Matrix A entspricht. NB ist gleich dem Rang N dividiert durch die verwendete Blockgröße BITS_PER_BLOCK in Bits (kurz: BPB) plus 1. Die Größe NB gibt also an, wie viele Blöcke für N Spalten pro Zeile benötigt werden, wenn jeder Block mit BITS_PER_BLOCK Bits der Matrix A gefüllt wird. Die Addition mit 1 geschieht deshalb, weil zusätzlich ein Element des Vektors b in jede Zeile muss. Anschließend werden Permutationsvektoren definiert und initialisiert, in denen die später vorgenommenen Spaltenpermutationen festgehalten werden. Die Zuweisung des Permutations-vektors perm_c2o[1] = 2 (c2o - "current to original") bedeutet z.B., dass die 1. Spalte im Speicher nun der 2. Spalte in der Ausgangsmatrix entspricht.

2. Laden der Matrix

Der Algorithmus bearbeitet alle Teilschritte während der Eliminierung für jede Zeile. So wird bei jedem neuen Zeilendurchlauf eine neue Zeile der Matrix A in den Speicher geladen. Im Algorithmus werden die Elemente dabei in Blöcke gepackt und blockweise gespeichert. Da während des Lösungsverfahrens Spalten vertauscht werden, müssen Spaltenpermutationen beim Übertragen von Elementen berücksichtigt werden. Im Beispiel wurden vor dem zweiten

Schleifendurchlauf die Spalte 1 und 2 im Speicher miteinander vertauscht. Also wird das Element in Zeile 2 und Spalte 1 im Speicher in Spalte 2 geschrieben. Das Element in Zeile 2 und Spalte 2 wird im Speicher in Spalte 1 geschrieben.

3. Gauß-Elimination

Um eine erfolgreiche Rücksubstitution zu garantieren, müssen alle Elemente links der Hauptdiagonale eliminiert werden. Für jede Zeile wird also geprüft ob ein Element vor dem diagonalen Element den Wert 1 besitzt. Im Beispiel besitzt im 2. Durchlauf nach dem Laden der Zeile das Element in Zeile 2 und Spalte 0 den Wert 1. Um dieses Element zu "nullen" muss die Zeile 0 von Zeile 1 abgezogen werden. Das entspricht im Polynomkörper GF(2 ⁿ ) einer Addition ⁸ modulo 2, bzw. einer XOR-Verknüpfung. Zu beachten ist, dass bei jeder Zeilenaddition jedes Zeilenelement der Zeile 1 mit jedem Zeilenelement der Zeile 0 addiert werden muss.

4. Spalten vertauschen

Da alle Elemente in der Hauptdiagonale vor der Rücksubstitution den Wert 1 besitzen müssen, muss etwas unternommen werden, wenn das diagonale Element nach der Elimination ungleich 1 ist. Im Beispiel ist während des 2. Durchlaufes das diagonale Element gleich 0. Also muss ein Element in der Zeile gefunden werden, dessen Wert gleich 1 ist. Wenn keins gefunden wird, gibt es zwei Optionen.

A. Ist das Element vom Vektor b in der entsprechenden Zeile 0, dann darf das diagonale Element gleich 1 gesetzt werden

B. Ist das Element vom Vektor b in der entsprechenden Zeile 1, dann ist die Matrix nicht invertierbar, denn 0*x 1 + 0*x 2 + ... + 0*x n = 1 ist eine falsche Aussage. Es wird bei den Betrachtungen in der Arbeit jedoch immer davon ausgegangen, dass ein entsprechendes Element gefunden wird. Im Beispiel befindet sich dieses Element beim 2. Durchlauf in Spalte 2. Also werden die 1. und 2. Spalte vertauscht. Die Permutation wird im Permutationsvektor perm_c2o festgehalten.

5. Rücksubstitution

Nach allen bisherigen Schritten kann nun von der letzten bis zur ersten Zeile rücksubstituiert werden. Da die erhaltenen Lösungselemente jedoch durch die Spaltenpermutation ebenfalls vertauscht sind, müssen diese über den Permutationsvektor wieder zurück vertauscht werden.

⁸ Siehe: Elmar Böhler: Der Polynomkörper GF(2 ⁿ )

2 Vorgehensweise

Da in der Arbeit anfänglich die Betrachtung von Optimierungsmöglichkeiten im Gaußschen Eliminationsverfahren im Vordergrund stand, habe ich mir zunächst unabhängig vom zu untersuchenden Algorithmus eine Übersicht über alternative Lösungsverfahren zum Lösen linearer Gleichungen verschafft. Da sich jedoch das Gaußsche Eliminationsverfahren, wie es im Algorithmus umgesetzt wird, als die beste Variante erwies, begann ich den Algorithmus selbst genauer zu untersuchen.

Da der Algorithmus durch die besondere Eigenschaft gekennzeichnet ist, dass er die zu verarbeitenden Elemente blockweise packt und behandelt, erschien mir eine Betrachtung für verschiedene Blockgrößen und den Sonderfall, dass die Bits einzeln behandelt werden, günstig für eine Möglichkeit der Laufzeitverbesserung.

Um den Einfluss der Blockgröße auf den Algorithmus zu untersuchen habe ich zunächst den Algorithmus in seiner Gesamtheit für verschiedene Blockvarianten gemessen (Gesamtbetrachtung) und anschließend in Teile zerlegt, die ich genauer untersucht habe.

2.1 Gesamtbetrachtung

Der originale Algorithmus arbeitet mit einer Blockgröße von 32 Bit. Um den Algorithmus für verschiedene Blockgrößen zu untersuchen, wurden zunächst drei weitere Versionen erstellt, die sich in der Blockgröße unterscheiden. Eine vierte Version wurde ebenfalls programmiert, bei der die Bits nicht in Blöcke gepackt, sondern einzeln gespeichert und behandelt wurden. Für die Messung des gesamten Algorithmus standen insgesamt die folgenden C-Implementierungen ⁹ zur Verfügung. Blockgröße von 64 Bit: solveUINT64.c Blockgröße von 32 Bit: solve.c (originale Version) Blockgröße von 16 Bit: solveUINT16.c Blockgröße von 8 Bit: solveUINT8.c 1 Bit pro Block: solveBPB.c (bei 32-Bit-Blöcken)

Für jede dieser C-Implementierungen wurde mithilfe von R eine dll-Datei ¹⁰ erzeugt, welche anschließend in die R-Umgebung eingebunden wurde. Mittels eines erstellten Testskripts wurde für alle Implementierungen bei der gleichen Matrix A die Laufzeit gemessen und in eine Ausgabedatei "Rprof.out" geschrieben. Mit Rprof (Profiler von R) konnte die Ausgabedatei geöffnet und die Laufzeiten eingesehen werden.

2.2 Aufgliederung des Algorithmus

Nach der Gesamtbetrachtung wurde der Algorithmus in drei Teile aufgegliedert. Die folgenden Abschnitte im Algorithmus wurden in C als Methoden programmiert ¹¹ und einzeln untersucht. 1) Laden der Matrix 2) Gauß-Elimination 3) Vertauschen der Spalten

⁹ Alle Quelltexte der C-Implementierungen für R befinden sich auf der Begleit-CD: \Programmdateien\C-Implementierungen für R\src

¹⁰ Alle erzeugten dll-Dateien befinden sich auf der Begleit-CD:\Programmdateien\C-Implementierungen für R\dll

¹¹ Alle für die Messungen der Teilbereiche verwendeten C-Quelltexte befinden sich für jeden Teilbereich geordnet auf der Begleit-CD:\Programmdateien\Teiluntersuchungen

Die Betrachtungen in dieser Arbeit erfolgten für alle drei Teilbereiche des Algorithmus. Der Schwerpunkt jedoch lag auf der Gauß-Elimination. Die anderen beiden Teile sind trotzdem ein wesentlicher Bestandteil während des Eliminationsverfahrens und wurden deshalb ebenso analysiert.

In allen drei Teilbereichen wurden zwei grundlegende Versionen gegenübergestellt: zum einen die Bit-pro-Block-Variante (BPB-Variante) in welcher die Bits einzeln behandelt werden und zum anderen die Block-Variante für verschiedene Blockgrößen, bei der die Bits in Blöcken behandelt werden.

Für jeden Teilbereich erfolgte die Analyse auf zwei verschiedene Weisen. Bei der mathematischen Analyse wurde die Zahl an Operationen in Abhängigkeit von N und der Blockgröße ermittelt. Die gewonnenen Formeln wurden mit einzelnen Messungen (Mitzählen der Schleifendurchläufe) auf ihre Richtigkeit überprüft. In der messtechnischen Analyse wurde (nach der Kompilierung der einzelnen Quelltexte) die Laufzeit für die Bit-pro-Block-Variante und die Block-Variante mit GProf gemessen. Für das Laden der Matrix und das Vertauschen der Spalten wurden auch für die Bit-pro-Block-Variante verschiedene Blockgrößen getestet. Da ich mich bei der Eliminierung auf den Einfluss der Blockgröße in der Block-Variante konzentrieren wollte, habe ich die Bit-pro-Block-Variante nur für die Standard-Blockgröße von 32 Bit getestet.

3 Methoden

3.1 Auszählen der Additionen

Für die Block- und die Bit-pro-Block-Variante wurden jeweils die Zahl an Operationen in dem jeweiligen Teilbereich bestimmt. Für die Block-Variante ergab sich ebenso eine Abhängigkeit von der Blockgröße, die mit BPB ("Bits per Block") bezeichnet wurde. Um die genaue Zahl an Operationen in Abhängigkeit von der Eingabegröße N (Rang der Matrix A) zu bestimmen, wurde dafür zunächst eine mathematische Formel durch allgemeine Überlegungen oder Betrachtungen anhand von Beispielmatrizen bzw. Beispieleingaben für N aufgestellt. Mit der programmierten Methode des jeweiligen Teilbereichs wurde anhand dieser Beispielmatrizen gedanklich nachvollzogen wie oft alle Schleifen in der Methode durchgeführt werden um dann aus verschiedenen Beispielen eine allgemeine Formel zu entwickeln. Um die Formeln zu überprüfen wurden einzelne Versionen der Methoden erzeugt, in denen die Operationenzahl durch Zählvariablen gemessen und ausgegeben wurde (s. Beispiel in Abbildung 3). Dabei wurden zunächst für verschiedene N die Schleifendurchläufe mithilfe der Formel berechnet und anschließend geprüft ob das Ergebnis mit den Ausgabedaten übereinstimmt.

3.2 Messtechnische Analyse mit Gprof

Der theoretisch-mathematischen Betrachtung folgte eine Messanalyse bei der die Laufzeit für alle Varianten bestimmt wurde. Alle Programme wurden mit der 32 Bit C/C++ Entwicklungsumgebung DJGPP ¹² kompiliert und gemessen. Das Übersetzen geschah in der DOS-Konsole über

¹² DJGPP (Ver. 2.03): http://www.delorie.com/djgpp/

C:\gcc\mystuff> gcc solve_P1.c gcc solve_P1.c --o solve_P1.exe o solve_P1.exe --pg pg pg pg gcc solve_P1.c gcc solve_P1.c - -o solve_P1.exe o solve_P1.exe - - Dabeiwurde lediglich die Profilingfunktion (-pg) genutzt. Es wurden keine Optimierungsfunktionen des Compilers verwendet, sodass die am Quelltext vorgenommenen theoretischen Überlegungen möglichst unverfälscht durch die Messungen repräsentiert werden konnten. Nach dem Ausführen des Programms konnte die erzeugte Ausgabedatei des Profilers mit Gprof analysiert werden:

C:\gcc\mystuff> solve_P1.exe solve_P1.exe solve_P1.exe solve_P1.exe C:\gcc\mystuff> Gp Gprof solve rof solve_P1 _P1 _P1 _P1.exe .exe .exe .exe Gp Gp rof solve rof solve

Abbildung 4 zeigt wie eine Analyse mit Gprof aussehen könnte. In der Spalte "self s/call" befindet sich die Laufzeit der aufgerufenen Methode in Sekunden.

Abbildung 4: Beispiel für Laufzeituntersuchung mit Gprof

In den meisten Fällen wurde die Laufzeitanalyse für verschiedene Eingabegrößen vorgenommen. Die Eingabegröße wurde jeweils im Quelltext bestimmt (int N = 100;). Wenn nicht anders angegeben, setzen sich alle dargestellten Messwerte aus 5 Messproben zusammen, von denen jeweils der kleinste Messwert für die Analyse verwendet wurde um so den Störeinfluss gering zu halten.

Alle Messungen wurden unter folgenden Systemvoraussetzungen durchgeführt:

Betriebssystem: Microsoft Windows XP Professional, Version 2002, Servicepack 2 Prozessor: AMD AthlonXP 3000+ (2,17 GHz) RAM: 1 GB

3.3 Messtechnische Analyse mit Rprof

Die Gesamtbetrachtung des Algorithmus wurde innerhalb der Statistik-Umgebung R (Ver. 2.4.1) durchgeführt. Dazu wurde zunächst für alle Programme mithilfe von R in eine dll-Datei erzeugt:

C:\Program Files\R2\R-2.4.1\bin> R CMD SHLIB solve.c R CMD SHLIB solve.c R CMD SHLIB solve.c R CMD SHLIB solve.c

Nach dem Einfügen der dll-Dateien in das Hauptverzeichnis (C:\Program Files\R2\R- 2.4.1) wurde die Statistik-Umgebung gestartet.

Mithilfe des Testskripts solvescript.R ¹³ wurden zuerst die dll-Dateien geladen, danach eine Matrix A und ein Vektor b für ein beliebiges N generiert und anschließend die Tests für alle Varianten ausgeführt:

> loaddlls()

> A <- creatematrix(32) > b <- createvector(32) > solvetest(A, b) Variante: original, Bits_per_Block: 32 Variante: verändert, Bits_per_Block: 8 Variante: verändert, Bits_per_Block: 16 Variante: verändert, Bits_per_Block: 32 Variante: verändert, Bits_per_Block: 64 Variante: verändert, 1 Bit pro Block [1] 0.4785156 >

Innerhalb der Funktion solvetest() werden alle Varianten gestartet und gemessen. Mit Rprof kann die Ausgabedatei eingesehen werden (s. Abbildung 5). Die Laufzeit der jeweiligen Variante findet man in der Spalte "self seconds".

Abbildung 5: Beispiel für Laufzeituntersuchung mit Rprof

Für alle Messungen, die mit Rprof stattgefunden haben, wurde genau ein Messwert erzeugt und verwendet. Das gilt insbesondere für die Gesamtbetrachtung des Algorithmus.

¹³ solvescript.R: Begleit-CD:\Programmdateien\R-implementierungen\skript\solvescript.R

4 Analyse-Ergebnisse

4.1 Gesamtbetrachtung des Algorithmus

Tabelle 1: Messwerte für die Bit-pro-Block-Variante und für alle Blockvarianten

Um sich einen Gesamtüberblick zu verschaffen ist es erst einmal interessant, sich die Laufzeit des gesamten Algorithmus für alle Varianten und verschiedene Eingabegrößen anzusehen. Tabelle 1 zeigt die entsprechenden Messwerte, die mit Rprof ermittelt wurden. In Abbildung 6 wird die Bit-pro-Block-Variante mit der Block-Variante für 32 Bit pro Block grafisch verglichen.

Die Einzelbehandlung der Bits kostet scheinbar vielmehr Zeit als mehrere Bits in Blöcke zu packen und blockweise zu behandeln, obwohl dafür einige Zusatzoperationen notwendig sind, die die Bits in Blöcke hineinpacken oder einzeln auslesen. In beiden Fällen scheint der Algorithmus das Problem in polynominaler Zeit zu lösen. Der Anstieg des Graphen für die Bit-pro-Block-Variante scheint deutlich größer zu sein als der Anstieg des Graphen für die Block-Variante. Wenn die gemessene Laufzeitkomplexität beider Algorithmen gleich ist, dann lassen sich die Laufzeitwerte von solve.c mit einem konstanten Faktor multiplizieren und müss- ten dann in etwa alle mit den Laufzeitwerten von solveBPB.c übereinstimmen.

In Abbildung 7 wurde ein Faktor ermittelt, sodass der Graph von F*solve.c den Graphen von solveBPB.c an der Stelle N = 3000 schneidet (F =19,01 / 1,16 = 16,388). Der entstandene Graph verläuft ab N = 3000 deutlich steiler nach oben als der Graph für die Messwerte von solveBPB.c. Damit wäre die Komplexität für die Bit-pro-Block-Variante geringer als für die Block-Variante. Diese Schlussfolgerung ist jedoch mit Vorsicht zu genießen, da sich der Graph aus lediglich 5 Messwerten zusammensetzt, wobei zusätzlich Messfehler existieren könnten. Außerdem ist in Abbildung 7 deutlich erkennbar, dass die Laufzeit von solve.c bereits bei einem N von 4000 so weit unterhalb der Laufzeit von solveBPB.c liegt, dass sich die Graphen bei unterschiedlicher Komplexität erst für so große N schneiden würden, dass eine Ausführung der Algorithmen in der Praxis schon längst nicht mehr akzeptabel ist, da wohl fast der gesamte Anteil an Speicherressourcen ausgeschöpft und die Laufzeit zu groß wäre.

Abbildung 7: Graphische Betrachtung der Komplexität für beide Methoden

In Abbildung 8 ist die Block-Variante für verschiedene Blockgrößen dargestellt. Die Unterschiede zwischen den Blockvarianten sind wesentlich kleiner, als der Unterschied zwischen Block- und Bit-pro-Block-Variante.

Abbildung 8: Die Block-Variante für alle Blockgrößen im Vergleich

Dennoch sind Unterschiede im Laufzeitverhalten sichtbar, die mit wachsender Eingabegröße zunehmen. Die schnellste Variante ist der originale Algorithmus mit einer Blockgröße von 32 Bit. Nun könnte man vermuten, dass sich mit sinkender Blockgröße die Laufzeit verlängert. Jedoch liegt die Laufzeit für die 64-Bit-Variante zwischen der Laufzeit der 8-Bit-Variante und der Laufzeit der 16-Bit-Variante. Diese Erscheinungen lassen sich anhand einer Metapher gut veranschaulichen.

Die zu verarbeitende Menge an Daten (Matrix A, Vektor b) sei ein Sandhaufen. Der Sandhaufen soll in einer Mischmaschine verarbeitet werden. Diese Mischmaschine ist der 32-Bit-Pro-zessor auf dem alle Varianten getestet wurden. Die Mischmaschine benötigt für jeden Misch-vorgang eine konstante Zeit (Rechenzyklus), es können jedoch nur maximal 32 Einheiten an Sand in der Maschine pro Zyklus verarbeitet werden. Die Blockgröße sei nun die Größe der Schaufel, mit der der Sandhaufen in die Mischmaschine geschaufelt wird. Wird nun der Sand mit einer 8-Bit-Schaufel in die Maschine befördert, dann benötigt man viel mehr Zeit als wenn man den Sand mit einer 32-Bit-Schaufel in die Mischmaschine transportiert. In beiden Fällen benötigt die Maschine nämlich die gleiche Zeit pro Schaufel. Packt man jedoch nur 8 Sandeinheiten in die Mischmaschine hinein, dann ist die Maschine natürlich nicht ausgelastet und man muss viel mehr (länger) schaufeln um den Sandhaufen zu bearbeiten. Verwendet man eine 64-Bit-Schaufel, dann ist die Mischmaschine zu klein. Also müssen zusätzliche Aktionen unternommen werden um den 64-Bit-Haufen auf der Schaufel für die Bearbeitung in der Mischmaschine aufzubereiten. Dadurch ist die 64-Bit-Variante zwar schneller als die 8-Bit-Variante, aber durch die zusätzlich verlorene Zeit langsamer als die 16-Bit-Variante. Es ist absehbar, wie das Messergebnis auf einer 64-Bit-Maschine aussehen würde. Die drei Teile des Gaußschen Eliminationsverfahrens sollen nun genauer in Abhängigkeit der Blockgröße untersucht werden, denn diese allgemeine Betrachtung reicht nicht aus um den Algorithmus zu analysieren.

4.2 Laden der Matrix

Wie bereits beschrieben wurde ist der originale Algorithmus, welcher in dieser Arbeit untersucht werden soll, eine C-Implementierung für die Skriptsprache R. Das Programm hantiert also im Praxisfall mit R-Objekten. Es erwartet zunächst zwei R-Objekte als Eingabe (Matrix A und Vektor b). Diese Objekte werden dann gepackt in Blöcken in den Speicher übertragen um dort später blockweise bearbeitet zu werden. Das Laden der Matrix in den Speicher (siehe Abbildung 9) findet zeilenweise vor jeder Eliminierung statt und ist ebenso ein wichtiger Be-standteil im Algorithmus, der genauer untersucht werden soll.

Die folgende Abbildung soll die Arbeitsweise beider Varianten verdeutlichen. Es wurde angenommen, dass die Größe einer Speicherzelle, bzw. die Blockgröße 8 Bit beträgt.

Abbildung 10: Arbeitsweise beim Laden der Matrix mit 8 Bit pro Block

Während bei der Bit-pro-Block-Variante Zeile für Zeile jedes Element in eine Speicherzelle kopiert wird (Z.5-8), schiebt die Block-Variante die Elemente als Bits zunächst in einen Block "shift" (Z. 21-22), wobei die Reihenfolge der Elemente innerhalb des Blockes umgekehrt wird. Da die Zugriffe auf diese Elemente im gesamten Algorithmus auf diese Umkehrung innerhalb der Blöcke abgestimmt sind, sei diese Tatsache hier nur erwähnt und wird in weiteren Betrachtungen außer Acht gelassen. In Abbildung 10 ist der entsprechende Befehl

vom originalen Quelltext oben mit abgebildet. In Zeile 24 wird geprüft ob der Block voll ist. Wenn das der Fall ist, dann wird der volle Block in die Speicherzelle gleicher Blockgröße geladen (Z. 24). Der Block "shift" kann anschließend wieder genullt werden um neue Elemente aufzunehmen (Z. 27).

Allein die Abbildung 10 lässt erkennen, dass die Bit-pro-Block-Variante mehr Speicher benötigt als die Block-Variante, jedoch keine zusätzlichen Operationen verbraucht. In der folgenden mathematischen Analyse soll diese Tatsache verdeutlicht werden.

4.2.1 Mathematische Analyse

Da darauf abgezielt wird, den Unterschied zwischen beiden Methoden zu ergründen, genügt es in diesem Fall diejenigen Operationen zu betrachten, welche charakteristisch für die jeweilige Variante sind. Die Erhöhungen der Schleifenvariablen (row++; col++) können daher ignoriert werden. Es wird davon ausgegangen, dass jedes Element der Matrix A den Wert 1 besitzt. So wird auch in jedem Fall die Bedingung if(Matrix [row][col] gleich 1) positiv ausfallen und eine Operation geschehen (Worst Case ¹⁴ ). Dabei ist zu beachten, dass bei der Bit-pro-Block-Variante das Element sowieso immer in den Speicher geschoben wird, während in der Block-Variante das Positionieren des Bits in den Block nur geschieht, wenn das Element der Matrix eine 1 ist.

In der Bit-pro-Block-Variante wird einer Speicherzelle auf die der Zeiger zeigt genau N*Nmal (für jedes Element der Matrix) ein Wert zugewiesen und die Adresse des Zeigers ebenso N ² -mal erhöht (Z.10).

Bei der Block-Variante geschehen im Worst Case zunächst N ² -mal eine OR-, eine Shift- und eine AND-Operation, bei der das jeweilige Bit der Matrix A an eine entsprechende Stelle im Block shift positioniert wird (Z. 22). Da jedes Mal geprüft werden muss ob der Block shift voll ist und keine Elemente mehr hineinpassen, finden zusätzlich N ² -mal eine AND- und eine Vergleichsoperation statt. Der im Originalquelltext vorkommende Ausdruck (BITS_PER_BLOCK -1) wird als Konstante betrachtet und wird in dieser Arbeit daher nicht als Operation behandelt.

Wenn der Block voll ist muss dieser in den Speicher übertragen werden. Dabei wird in Zeile

24 genau N*NB = N*

zugewiesen und der Zeiger wird um 1 erhöht (Z. 25).

Die folgende Tabelle fasst alle Operationen für beide Varianten zusammen.

Tabelle 2: Zahl an Operationen beim Laden der Matrix

Da die Zahl an Operationen in der Block-Variante deutlich überwiegt, stellt sich die Vermutung ein, dass die Bit-pro-Block Variante schneller ist. In der Praxis jedoch ist die Zahl

¹⁴ Worst Case (hier): Fall bei dem der Algorithmus die maximale Laufzeit in Anspruch nimmt

an Operationen nur ein wichtiges Element neben vielen anderen Elementen, die die Laufzeit beeinflussen können, wie es in der folgenden Messanalyse deutlich wird.

4.2.2 Messanalyse

Die Laufzeiten der beiden in Abbildung 9 dargestellten Methoden werden in folgendem Diagramm miteinander für verschieden große N und Blockgrößen verglichen. Um die Messungen unabhängig von einem R-Objekt mit Gprof zu gestalten wurde statt zu prüfen, ob das Element der Matrix eine 1 ist, geprüft ob die Spaltennummer eine ungerade Zahl ist. Da sich beide Varianten im Prüfen des Wertes eines Elements der Matrix nicht unterscheiden, kann eine Vereinfachung angewandt werden. Ebenso wurde zur Vereinfachung die Übertragung des Vektors b in den Speicher bei Messungen ignoriert.

Abbildung 11: Messwerte für creatematrixBPB() und creatematrix()

Betrachtet man zunächst nur die Laufzeiten von creatematrixBPB() für verschiedene Blockgrößen, so fällt auf, dass mit sinkender Blockgröße auch die Laufzeit geringer wird. Die Zahl an Zeigerzuweisungen bzw. Additionen ist jedoch unabhängig von der Blockgröße. Dieser scheinbare Widerspruch lässt sich trotzdem erklären und leicht an einem Beispiel nachvollziehen.

Eine Matrix mit 8000*8000 Elementen soll im Hauptspeicher abgelegt werden. Bei einer Blockgröße von 32 Bit wird jedes Element in einem 32 Bit Block (4 Bytes) gespeichert. Insgesamt wird also auf 8000*8000*4 / (1024*1024) = 244,141 MB zugegriffen. Die Daten landen sehr wahrscheinlich zunächst im Pufferspeicher (Cache). Der Cache kann jedoch keine 244,141 MB aufnehmen. Somit muss immer wenn der Cache voll ist neuer "nachgeladen" werden. Der Zugriff auf den Cache ist relativ schnell, aber das "nachladen" kostet wiederum relativ viel Zeit. Werden die Elemente nur noch in 8 Bit Blöcken (1 Byte) gespeichert, dann ist die Datenmenge nur noch 8000*8000*1 / (1024*1024) = 61,035 MB, also ein Viertel mal

so groß. Unabhängig von diesem Beispiel könnten für sehr große N ebenfalls Auslagerungen auf der Festplatte stattfinden, die auch zusätzlich viel Zeit benötigen. Für N = 8000 wurden die Messungen für die Block-Variante ohne eine Erhöhung der Zeigervariable wiederholt. Dadurch wird nicht mehr als eine Speicherzelle zur Speicherung verbraucht. Es ergab sich unabhängig von der Blockgröße eine konstante Zeit. Diese Zeit wurde von der Laufzeit aus Abbildung 11 (für N = 8000) abgezogen um die für die Zeigererhöhung (und Zuweisung) benötigte Zeit festzustellen. Die Ergebnisse findet man in Tabelle 3.

Betrachtet man die Differenzen, so kann behaupten werden, dass bei halber Blockgröße nur halb so viele Male der Cache nachgeladen werden muss (wenn man davon ausgeht, dass die gesamte Restzeit nur für diese Operation verbraucht wird). Genau genommen wird die Laufzeit bei einer Halbierung der Blockgröße sogar mehr als nur halbiert. Eine minimale Blockgröße von 8 Bit scheint daher für die Bit-pro-Block-Variante am geeignetsten. Dennoch wird in dieser Arbeit für weitere Betrachtungen (wenn nicht anders angegeben) für die Bit-pro-Block-Variante eine Blockgröße von 4 Byte angenommen.

Betrachtet man die Block-Variante so stellt man fest, dass sich mit sinkender Blockgröße die Laufzeit vergrößert. Da in der Block-Variante alle Elemente optimal gespeichert werden, gibt es keine unterschiedlichen Speichermengengrößen in Abhängigkeit von der Blockgröße. Es ist egal ob 64 Elemente in 4 16-Bit-Blöcken oder in 2 32-Bit-Blöcken gespeichert werden, denn für beide Varianten werden insgesamt 8 Byte benötigt. Man könnte annehmen, dass der Laufzeitunterschied auf die von der Blockgröße abhängigen Zeigererhöhungen bzw. Zugriffe zurückzuführen ist. Messungen bei denen auf die Übertragung von shift in den Speicher verzichtet wurde (siehe Messwerttabelle ¹⁵ auf der Begleit-CD), belegen jedoch, dass diese Operationen nicht ins Gewicht fallen. Dementsprechend ist die Laufzeiterhöhung auf die vielen zusätzlichen Bitoperationen in der Wertzuweisung von shift (shift |= (1 << (col & (BITS_PER_BLOCK -1)));) und in der if-Bedingung (if((col & (BITS_PER_BLOCK-1)) == (BITS_PER_BLOCK-1))) zurückzuführen. Interessant hierbei ist, dass eine Erhöhung der Blockgröße diese Operationen schneller macht. Vermutlich können 32 Bit Blöcke besser verarbeitet werden als z.B. 8 Bit Blöcke, da bei 8 Bit Blöcken erst der jeweilige Block aus dem Speicher ausgeschnitten werden muss um im 32 Bit Prozessor verarbeitet zu werden.

Die Messergebnisse bestätigen also die vorangegangenen Vermutungen, wobei die Gründe für das unterschiedliche Laufzeitverhalten z.B. in der Bit-pro-Block-Variante nicht durch die Zahl an Operationen zu erklären sind. Die zusätzlichen Operationen um die Elemente der Matrix in die Variable shift zu übertragen verbrauchen in der Block-Variante mehr Laufzeit als das "nachladen" des Cache in der Bit-pro-Block-Variante. Zusammenfassend kann man sagen, dass die Bit-pro-Block-Variante für das Laden der Matrix schon ab einer Blockgröße von 16 Bit schneller ist als die Block-Variante für alle Blockgrößen, wobei gilt: Je kleiner die Blockgröße bei der Bit-pro-Block-Variante ist, desto geringer ist die Laufzeit.

¹⁵ creatematrix.xls: Begleit-CD:\Messtabellen\creatematrix.xls (Tabelle creatematrix02)

4.3 Gauß-Elimination

Abbildung 12: Algorithmus für Gauß-Elimination

Nachdem eine Zeile der Matrix A in den Speicher geladen wurde, müssen alle Zeilenelemente vor dem diagonalen Element der Matrix eliminiert werden. Wenn beispielsweise wie in wie in Abbildung 13 nach dem Laden der Zeile 2 das erste Zeilenelement den Wert 1 besitzt, so muss dieses eliminiert werden um A in eine Dreiecksform zu bringen. Um das 1. Zeilenelement aus Zeile 2 in eine 0 umzuwandeln, wird die gesamte Zeile mit der Zeile 0 addiert, wobei das Ergebnis in Zeile 3 festgehalten wird. Die Addition versteht sich als eine Addition modulo 2, bzw. eine XOR-Verknüpfung der Bits.

Wenn ein Zeilenelement eliminiert werden muss, wird immer diejenige (obere) Zeile zur Eliminierung gewählt, von der man weiß, dass das Element der zu addierenden Zeile gleicher Spaltenzahl ebenfalls eine 1 ist, um so eine Null zu erzeugen. Deshalb wählt man zu einem zu eliminierenden Zeilenelement in der Spalte X die Zeile X, von der man weiß, dass das Diagonalenelement in der Spalte X gleich 1 ist. Würde das Programm in der nun veränderten dritten Zeile noch eine 1 in der zweiten Spalte entdecken, so müsste noch einmal die zweite Zeile zur dritten addiert werden.

Abbildung 13: Beispiel für eine Eliminierung in einer 3ä3 Matrix

Der Ergebnisvektor b soll bei der Betrachtung der Gauß-Elimination ignoriert werden. Alle Operationen werden ausschließlich für A ausgeführt. Die Funktionsweise ist für beide Algorithmen, die in Abbildung 12 dargestellt sind, gleich. Jedoch unterscheiden sich beide Algorithmen vor allem in dem Teil, wo die Zeilenelemente zweier Zeilen miteinander addiert werden. Während Variante 1 bei der Addition die Zeilenelemente einzeln addieren muss (Z. 7-10), kann die Block-Variante gleich mehrere Zeilenelemente in einer Addition zusammenfassen (Z. 55-57 bzw. 72-74). Jedoch können nur so viele Elemente gleichzeitig addiert werden, wie auch in einen Block passen (im Normalfall also 32). Allerdings müssen in der Block-Variante mehr Operationen ausgeführt werden um die Stelle der hinzu zuaddierenden Zeile zu berechnen (Z. 52, bzw.69). Da die Eliminierung das Kernstück des Algorithmus bildet, soll diese etwas ausführlicher untersucht werden.

4.3.1 Mathematische Analyse

Um die genaue Zahl an Operationen anzugeben, müssen die einzelnen Schleifendurchläufe in Abhängigkeit von N und der Blockgröße BPB berechnet werden.

Zuerst soll eine Betrachtung für die recht unkomplizierte Bit-pro-Block-Variante geschehen. Da der Algorithmus für jede Zeile durchgeführt wird, wird die row-Schleife N-mal durchlaufen.

Dagegen wird die col-Schleife erst ab der zweiten Zeile (row = 1) durchlaufen, da das diagonale Element in der ersten Zeile an erster Stelle steht. Es werden jedoch nicht für jede Zeile alle Zeilenelemente eliminiert, sondern nur diejenigen, welche sich vor dem diagonalen Ele-

ment befinden. Das sind maximal N-1 und minimal 0 viele, im Durchschnitt somit

Schleife wird also insgesamt (N-1) *

Um sich vorzustellen wie oft die k-Schleife insgesamt durchlaufen wird, kann man sich an Abbildung 14 orientieren. Die Punkte markieren ein Zeilenelement, welches "wegeliminiert"

werden muss. Da in allen Berechnungen vom ungünstigsten Fall (Worst Case) ausgegangen wird, müssen auch in dieser 4x4 Matrix alle Zeilenelemente vor dem diagonalen Element eliminiert werden. Die zu den Punkten gehörigen Linien durchlaufen alle Speicherzellen (bzw. Elemente), welche von der Eliminierung des jeweiligen Zeilenelements betroffen sind. Wird eine 1 in Zeile 2 und Spalte 0 entdeckt, so werden alle Elemente der 2. Zeile mit den entsprechenden Elementen der 0. Zeile addiert. Wird eine 1 in Zeile 2 und Spalte 1 entdeckt, so werden nur die Elemente der Spalten 1 bis 3 von Zeile 2 und Zeile 0 miteinander addiert. Die Gesamtzahl an Additionen (k-Schleifendurchläufen) wird wie folgt ermittelt:

Sum(k++) 4*4 = 3 * (4 Additionen) + 2 * (3 Additionen) + 1 * (2 Additionen) + 0 * (1 Addition) Sum(k++) 4*4 = 6

Die Zählvariable i sei die Anzahl der Additionen und (i - 1) die zugehörige Anzahl der zu eliminierenden Zeilenelemente. So ergibt sich für Sum(k++) N*N folgende Gleichung in Abhängigkeit von N (Rang von Matrix A und gleichzeitig maximale Anzahl von Additionen für ein zu eliminierendes Zeilenelement).

Sum(k++) N*N = ∑

Für beide Partialsummen erhält man die folgenden Umformungen aus dem Tafelwerk:

Sum(k++) N*N = ∑

Durch weitere Umformungsschritte ergibt sich für Sum(k++):

Sum(k++) N*N =

Die k-Schleife wird also

In folgender Tabelle ist die Gesamtzahl der einzelnen Schleifendurchläufe während der Eliminierung für die Bit-pro-Block-Variante noch einmal dargestellt. In der dritten Zeile befindet sich die Zahl an Operationen, die einem bestimmten Schleifendurchlauf zugeordnet wird (Erhöhungen der Schleifenvariablen werden mitgezählt).

Tabelle 4: Gesamtzahl an Schleifendurchläufen während der Eliminierung (solveBPB.c)

Durch die dreifache Schleifenverschachtelung (für jede Zeile werden für verschiedene Spalten Zeilenelemente auf den Wert 1 geprüft für die wiederum für jedes Element der Zeile eine Addition folgt) ergibt sich eine kubische Komplexität für die Eliminierung und somit für den gesamten Algorithmus. Deshalb wird die Eliminierung für sehr große N von allen anderen Abschnitten im Programm am längsten dauern. In der Block-Variante wird genau diese kubische Komplexität eingedämmt, da die Additionen nicht einzeln, sondern gepackt ausgeführt werden. Mehrere Elemente können somit gleichzeitig verarbeitet werden.

Um die Anzahl der Schleifendurchläufe für die Block-Variante zu ermitteln, wird zur Vereinfachung davon ausgegangen, dass N ein Vielfaches der Blockgröße BPB ist. Somit kann man davon ausgehen, dass z.B. für 128 Bits auch genau 128/32 = 4 Blöcke pro Zeile benötigt wer-

den. Als Beispielmatrix soll die in Abbildung 15 dargestellte 32ä32-Matrix dienen, wobei hierfür die Blockgröße 8 Bit beträgt.

Wie in der Bit-pro-Block-Variante benötigt diese Variante genau N-Zeilendurchläufe. Die i-Schleife durchläuft nur Blöcke, in denen kein diagonales Element enthalten ist. In Abbildung 15 sind diese Blöcke dunkelblau markiert. In den ersten 8 Zeilen (row=0 bis row =7) wird kein Block durchlaufen. Dagegen werden in den letzten 8 Zeilen NB-1 Blöcke durchlaufen.

Es gilt somit analog zur Variante 1, dass die i-Schleife (N - BPB) *

-mal durchlaufen wird.

Um alle zu eliminierenden Bits innerhalb eines Blockes aufzusuchen wird die j-Schleife pro Block genau BPB-mal durchlaufen. Die obere j-Schleife im Quelltext kümmert sich um alle Bits, die in Blöcken ohne diagonalem Element enthalten sind (blaue Blöcke), und die untere j-Schleife entsprechend um alle Bits, die in den Blöcken mit diagonalem Element enthalten sind (grüne Blöcke, somit alle Blöcke, die nicht von der i-Schleife erfasst werden). Wie in der Bit-pro-Block-Variante müssen genau alle Bits vor dem diagonalen Element pro Zeile unter-

sucht werden, sodass die j-Schleife (N - 1) *

Komplizierter wird die Betrachtung wieder für die k-Schleife. Um die Gesamtzahl an k-Durchläufen exakt berechnen zu können werden zwei Bereiche separat untersucht. Zum einen die von den blauen Bits ausgelösten Zeilenadditionen und zum anderen die von den grünen Bits ausgelösten Zeilenadditionen. Man stelle sich hierzu blaue Quadrate vor, bestehend aus 8x8 Elementen. Das oberste blaue Quadrat (A) besitzt also BPB*BPB Elemente. Ist eines dieser Elemente eine 1 (ist im Worst Case immer der Fall), dann werden alle vier (NB) Blöcke der jeweiligen Zeile mit allen 4 Blöcken einer oberen Zeile addiert. Es finden also BPB*BPB*4 k-Additionen statt. Das gleiche gilt für die Quadrate B und C. So kann man BPB*BPB*3*4 k-Additionen zusammenfassen. Für die zwei Quadrate D und F werden nur noch die letzten 3 Blöcke der entsprechenden Zeile pro Element addiert (BPB*2*3 k-Additionen). Am Beispiel der 32*32 Matrix gibt es für die blauen Elemente die folgende An- zahl an k-Schleifendurchläufen:

Sum(k++) 32*32 (1) = 8*8*(3* (4 Add.) + 2*(3 Add.) + 1*(2 Add.) + 0*(1 Add.))

Die maximale Anzahl an Additionen ist gleich NB. Für eine allgemeine N*N Matrix kann man ähnlich zur Bit-pro-Block-Variante folgende Schreibweise für k-Durchläufe wählen:

Sum(k++) N*N (1) = BPB ² * ∑

Um Sum(k++) N*N (1) in Abhängigkeit von N und BPB zu erhalten wird für NB der Term

eingesetzt:

Sum(k++) N*N (1) = BPB ² *

Um nun die Summe der von den grünen Elementen ausgelösten Zeilenadditionen zu ermitteln können im obigen Beispiel wieder vier Quadrate separat betrachtet werden (alle durch die die

Diagonale verlaufen). In diesen "halben" Quadraten befinden sich BPB*

Elemente. Für alle Elemente, die sich im 1. "halben" Quadrat befinden, werden im Worst Case genau 4 Additionen ausgeführt (alle 4 Blöcke). Für alle Elemente im 2. "halben" Quadrat werden entsprechend 3 Additionen ausgeführt, usw. Für das obige Beispiel ergibt sich für die grünen Elemente folgende Gesamtzahl an k-Schleifendurchläufen:

Sum(k++) 32*32 (2) = 8*(

Daraus lässt sich die allgemeine Gesamtzahl ableiten:

Sum(k++) N*N (2) = BPB*

Für NB kann nun wieder

Sum(k++) N*N (2) =

Addiert man nun Sum(k++) N*N (1) und Sum(k++) N*N (2) erhält man die absolute Gesamtzahl an k-Schleifendurchläufen in einer Eliminierung für eine N*N Matrix mit einer Blockgröße von BPB:

Sum(k++)

N*N

Sum(k++) N*N =

In der folgenden Tabelle ist die Gesamtzahl der einzelnen Schleifendurchläufe während der Eliminierung für die Block-Variante dargestellt. In der dritten Zeile befindet sich wieder die Zahl an Operationen für den entsprechenden Schleifendurchlauf.

Tabelle 5: Gesamtzahl an Schleifendurchläufen während der Eliminierung (solve.c)

Die Block-Variante besitzt deutlich mehr Operationen in ihrer Gesamtzahl, jedoch hat diese Variante deutlich weniger Schleifendurchläufe zu verzeichnen. Um die Überlegenheit der Block-Variante gegenüber der Bit-pro-Block-Variante während der Elimination zu demonstrieren soll rechnerisch die Differenz an Operationen pro Elimination ermittelt werden. Es soll angenommen werden, dass Additionen, Vergleiche, Divisionen und Multiplikationen gleich schnell verlaufen (was natürlich in der Praxis im Normalfall nicht stimmt). Diese Annahme erlaubt eine genaue Zahl von Operationen pro Schleifendurchlauf zu bestimmen. Bitoperationen werden aufgrund ihrer Schnelligkeit nicht hinzugezählt. Tabelle 6 zeigt die Gesamtzahl an Operationen für beide Varianten sowie die Differenz dieser Gesamtzahl.

Tabelle 6: Gesamtzahl an Operationen während der Eliminierung

Ein Rechenbeispiel (Tabelle 7) soll verdeutlichen wie gigantisch die Unterschiede zwischen beiden Varianten für große N sind. In einem Beispielprogramm solveElim.c (siehe Begleit-CD ¹⁶ ) wurden alle Schleifendurchläufe wie auch alle Operationen (Additionen, Vergleiche, Multiplikationen und Divisionen) für beide Varianten mitgezählt und am Schluss ausgegeben. Die Messungen wurden für eine Matrix mit 128*128 Elementen gemacht. Die Blockgröße betrug 32 Bits pro Block.

¹⁶ solveElim.c: Begleit-CD:\Programmdateien\Teiluntersuchungen\eliminate\solveElim.c

Die Ausgabe von solveElim.exe stimmt mit den Ergebnissen aus den hergeleiteten Formeln überein. Es wird deutlich, dass bereits bei einer Matrix von 128*128 Elementen große Unterschiede in der Operationenzahl auftreten können. In der Praxis treten jedoch noch viel größere Matrizen auf, was die Block-Variante umso bedeutungsvoller erscheinen lässt. In der folgenden Abbildung ist ein Graph dargestellt, der den prozentualen Anteil an Operationen der Block-Variante von der Bit-pro-Block-Variante darstellt.

Mit größer werdendem N werden für eliminateBPB() immer mehr Operationen im Vergleich zur Funktion eliminate() ausgeführt. Gleiches gilt für eine größer werdende Blockgröße. Es scheint jedoch einen Grenzwert zu geben. Das bedeutet, dass die Operationenzahl der Block-Variante für N Ø ¶ nur einen bestimmten minimalen Prozentsatz von der Operationenzahl der Bit-pro-Block-Variante ausmachen kann. Dieser Grenzwert kann wie folgt berechnet werden:

G = lim N Ø ¶

G =

N Ø ¶

Im Fall von 32-Bit-Blöcken beträgt der Grenzwert somit

groß N ist. Das Verhältnis

Die einzige Möglichkeit wäre nur noch die Blockgröße auf 64 Bit zu erweitern. Alle bisheri- gen Berechungen lassen jedoch außer Acht welche Hardwarevoraussetzungen gegeben sind.

Bei einem 32-Bit Prozessor wird eine Blockgröße von 64 Bit zu keinem besseren Ergebnis führen. Zudem kann man keinesfalls die Zahl der berechneten Operationen als alleiniges Laufzeitkriterium verwenden. Schließlich geschah diese Betrachtung unter der Annahme, dass z.B. Wertzuweisungen und Bitoperationen kaum Laufzeit verbrauchen und somit unter den Tisch fallen. Ebenso wurde angenommen, dass Operationen wie z.B. Multiplikation und Additionen gleich schnell verlaufen und zeitunabhängig von den Operanden sind.

4.3.2 Messtechnische Analyse

Die in Tabelle 8 dargestellten Messergebnisse sollen die vorangegangenen mathematischen Ergebnisse grob bestätigen. Es wurden die beiden Methoden eliminateBPB() und eliminate() für verschiedene N(Vielfache von 32) und verschiedene Blockgrößen getestet. Die zu bearbeitende Matrix wurde so generiert, dass möglichst viele Durchläufe in der k-Schleife geschehen, damit auch die kubische Komplexität zum Vorschein kommt. Die Anzahl der tatsächlich durchgeführten Eliminierungen (j-Schleifendurchläufe) befindet sich in der Spalte "Elim.".

Tabelle 8: Messdaten für eliminateBPB() und eliminate()

In dem in Abbildung 17 abgebildeten Graph sind die Messwerte für jede gemessene Blockgröße graphisch abgebildet. Für jede Punktserie wurde eine Kurve durch Regression ermittelt, welche jeweils eine kubische Funktion liefert. Das bestätigt die kubische Komplexität der Elimination. Es ist ebenso zu erkennen, dass gilt: Je größer die Blockgröße, desto geringer die Laufzeit.

Der durchschnittliche Prozentsatz an durchgeführten Eliminierungen im Verhältnis zur Gesamtzahl an Eliminierungen im Worst Case liegt nur bei etwa 25%. Da die Speicherklassen der Variablen, Wertzuweisungen und andere Sachen nicht berücksichtigt wurden, stimmen Berechnungen mit den ermittelten Formeln nur sehr großzügig mit der Praxis überein. In Tabelle 9 findet man den gemessenen Anteil der Laufzeiten der Blockvarianten an der gemessenen Laufzeit der Bit-pro-Block-Variante. Dem gegenübergestellt wird der Anteil, der nach folgender Formel (aus der mathematischen Analyse abgeleitet) berechnet wurde:

A =

Tabelle 9: Anteile der Laufzeiten der Block-Varianten and der Laufzeit der BPB-Variante

Je größer die Blockgröße ist, desto geringer weichen die gemessenen Prozentwerte von den berechneten ab. Jedoch kann man erkennen, dass zumindest ab einem N von 4000 in allen Fällen mit steigendem N eine Abnahme des Prozentwertes zu verzeichnen ist, wobei gleichzeitig eine Annäherung an einen Grenzwert abzusehen ist. Dieser Prozentwert wird für eine Block-Variante mit steigendem N zwar geringer, jedoch ist ab einer gewissen Größe eine Grenze erreicht. Der Vorteil der Block-Varianten ist für die Praxis deutlich erkennbar, wenn blockweises Behandeln der Matrixelemente etwa 30-mal schneller sein kann als das einzelne Behandeln aller Elemente.

4.4 Vertauschen der Spalten

Das Eliminieren aller Elemente vor dem diagonalen Element bringt die Matrix A nicht unbedingt in eine Dreiecksform. In der Dreiecksform besitzen alle diagonalen Elemente den Wert 1. Ist in einer Zeile das diagonale Element jedoch 0, so muss in der Spalte ein Element (hinter dem diagonalen Element) mit dem Wert 1 ausfindig gemacht werden. Ist das

Programm fündig geworden, dann wird die Spalte des diagonalen Elements mit der Spalte des gefundenen Elements vertauscht. Man sollte jedoch beachten, dass das Spaltenvertauschen pro Zeilendurchlauf geschieht und dass jeweils vor dem Spaltenvertauschen das Laden einer Zeile der Matrix und die Eliminierung dieser Zeile stattfinden. Es müssen also pro Spaltenvertauschung nur so viele Einzelvertauschungen durchgeführt werden, wie sich Zeilen im Speicher befinden. Auch für das Spaltenvertauschen kann der Vektor b ignoriert werden. Abbildung 19 verdeutlicht die Funktionsweise des Vertauschens von Spalten.

Abbildung 19: Allgemeine Arbeitsweise beim Vertauschen der Spalten für eine 8ä8-Matrix

Der wesentliche Unterschied zwischen der Block-Variante und der Bit-pro-Block-Variante liegt darin, dass einige Berechnungen notwendig sind, um die Spalten zu vertauschen. Für jede Zeile müssen die Bits einer bestimmten Spalte vertauscht werden. Da sich diese Bits jeweils in Blöcken befinden, müssen die Blöcke in denen sich die zu vertauschenden Bits befinden entsprechend verändert werden, schließlich gibt es keine Operation zum Vertauschen von Bits zwischen zwei Blöcken oder innerhalb eines Blocks. In der mathematischen Analyse wird deutlich, wie viele zusätzliche Operationen dafür notwendig sind.

4.4.1 Mathematische Analyse

Für das Auszählen der Operationen wird vorausgesetzt, dass die Wertzuweisung für nonzeroColumn vor dem Vertauschen der Spalten stattfindet. Wie bereits oben angedeutet, wird vom Worst Case ausgegangen. D.h. mit jedem Zeilendurchlauf findet ein Vertauschen der Spalten statt. Bei dieser Analyse kann man wie beim Laden der Matrix die Erhöhungen der Schleifenvariablen (row++, j++) ignorieren, da beide Methoden die gleiche Anzahl an Schleifendurchläufen besitzen.

In der Bit-pro-Block-Variante findet man mehr Zuweisungen und Zeigerzugriffe als Operationen. Lediglich die beiden Erhöhungen der Zeiger um zur nächsten Zeile zu springen (Z. 18-20) sind als zwei Additionen zu entdecken. Die row-Schleife wird N-mal durchlaufen. Die Zahl der Durchläufe für die j-Schleife kann man sich wie folgt herleiten: In der 1. Zeile geschieht genau eine Vertauschung. In der zweiten Zeile muss bereits zweimal vertauscht werden (Elemente der 1. und der 2. Zeile). Nachdem dieses Gedankenspiel bis zur N-ten Zeile fortgeführt wird, müssen alle Vertauschungen addiert werden und so erhält man N

N*(N+1)

∑ i = Vertauschungen (j-Schleifendurchläufe). Da in der j-Schleife genau 2

2 i=1

Additionen stattfinden, gibt es dort 2 *

In der Block-Variante werden bereits vor dem direkten Vertauschen einige Operationen durchgeführt. In Zeile 48 bis 50 müssen zwei Divisionen durchgeführt werden um die Blöcke zu lokalisieren, in welchen sich die jeweiligen Elemente befinden. In den Zeilen 52 bis 54

wird in einer Variablen test1 zunächst über eine SHIFT- und eine AND-Operation eine 1 an die Stelle des diagonalen Elements in dessen Block geschoben und anschließend wird die Variable mask1 erzeugt, die wegen der XOR-Operation komplementär zu Variablen test1 ist. Gleiches wird nun für das Element in der Spalte nonzeroColumn wiederholt. Diese Operationen geschehen innerhalb der row-Schleife genau N-mal.

Innerhalb der j-Schleife müssen bei jeder Vertauschung die zu vertauschenden Bits zunächst einzeln aus ihren Blöcken extrahiert werden (Z. 57-60). Insgesamt sind dafür 2*1 AND-Operationen, 2*1 Vergleiche und 2*1 Additionen notwendig. Das Vertauschen selbst geschieht in den Zeilen 65 und 67 mit insgesamt 2 AND- und 2 OR-Operationen. Um zur nächsten Zeile zu springen müssen beide Zeiger auf die jeweiligen Blöcke um NB erhöht werden (2 zusätzliche Additionen). Wie bei der Bit-pro-Block-Variante gibt es insgesamt N*(N+1) Vertauschungen.

2

In der Tabelle 10 sind alle Operationen noch einmal zusammengefasst dargestellt.

Tabelle 10: Zahl an Operationen beim Vertauschen der Spalten

Nach dieser Zusammenfassung könnte man wieder behaupten, dass die Block-Variante wegen der vielen Operationen deutlich langsamer ist. Da jedoch auch hier die Zahl an Operationen nicht das einzige Element ist, das die Laufzeit beeinflusst, sollte man sich nicht davon täuschen lassen.

4.4.2 Messtechnische Analyse

Die für die Messung verwendeten Algorithmen weichen in ihrer Funktionsweise etwas von den in Abbildung 18 dargestellten Algorithmen ab. Es wird in beiden Messalgorithmen der Worst Case angenommen, sodass ein Vertauschen der Spalten mit jedem Zeilendurchlauf stattfindet (Bedingung "Spalte von diagonalem Element (Spalte row) ungleich der Spalte nonzeroColumn" fehlt). Das nächste Element, welches den Wert 1 besitzt, befindet sich außerdem bei jedem Zeilendurchlauf in der letzten Spalte (nonzeroColumn = N-1), womit das Suchen eines Elements erspart bleibt.

Die Laufzeiten für die Bit-pro-Block und Block-Variante sind in dem Diagramm für ver- schieden große N und Blockgrößen in der Abbildung 20 erkennbar.

Entgegen der Erwartung kann man eine Überlegenheit der Block-Variante gegenüber der Bitpro-Block Variante feststellen. Wenn der Laufzeitunterschied sich nicht durch die unterschiedliche Anzahl an Operationen erklären lässt, muss es einen anderen großen Einflussfak-tor geben. Erneut ergibt sich ein Zusammenhang von Laufzeit und Speicherverbrauch. Denn während die Bit-pro-Block-Variante genau N-viele Speicherzellen einer bestimmten Blockgröße weiterspringen muss um für die nächste Vertauschung zur nächsten Zeile zu gelangen,

muss die Block-Variante lediglich NB =

weiterspringen (für alle Blockgrößen wird die gleiche Menge an Speicher zurückgelegt). Je größer der zurückgelegte Weg im Speicher ist, desto mehr Zeit wird benötigt um auch zu der

neuen Zeile zu gelangen. Da diese Sprünge

schied zwischen der Block- und der Bit-pro-Block-Variante quadratisch. Messungen für spezielle auf Zeigersprünge ausgerichtete Methoden ¹⁷ sollten die für einen Zeigersprung verloren gegangene Laufzeit ermitteln. Die beiden Methoden für eine Blockgröße von 32 Bit unterscheiden sich nur in der Größe des Zeigersprunges. In der Methode zeigerBitproByte() wird der Zeiger um N erhöht, in der Methode zeigerBlock()

hingegen um NB =

Vermutung, dass für größere Zeigersprünge mehr Laufzeit in Anspruch genommen wird.

Tabelle 11: Laufzeiten für zeigerBitproByte() und zeigerBlock()

¹⁷ Methoden zeigerBitproByte() und zeigerBlock() in solve_P3.c: Begleit- CD:\Programmdateien\Teiluntersuchungen\swap\solve_P3.c

Bei der Block-Variante ist zu beobachten, dass die Laufzeit für die 32-Bit-Methode am geringsten ist (bis auf die Ausnahme bei 8 Bit und N = 8000, der ein Messfehler zugrunde liegen könnte). Zwischen den Block-Varianten bestehen jedoch nicht so gigantische Laufzeitunterschiede wie zwischen der Bit-pro-Block- und der Block-Variante für 32 Bit. Schließlich wird für einen Zeilensprung dieselbe Menge an Speicher übersprungen. Ein Grund für die dennoch vorhandenen Unterschiede könnte die Ausrichtung (engl. "Alignment") der Daten für verschiedene Blockgrößen sein (s. Abbildung 21).

Der gesamte Prozessor- und Speicherbus ist in einer bestimmten Wortgröße (z.B. 32 Bit) organisiert. Der 32-Bit Prozessor, auf dem die Messungen durchgeführt wurden, benötigt bei Zugriffen auf den Speicher eine Adresse, die durch die Wortgröße (32 Bit = 4 Byte, also durch 4) teilbar ist. Schließlich möchte der 32-Bit-Prozessor gleich 32 Bit mit einem mal aus dem Speicher holen und durch den Bus schicken.

Abbildung 21: Einfluss der Adresse der Blöcke auf die Laufzeit

Bei der 32-Bit-Methode sind alle Adressen durch 4 teilbar, denn es befinden sich jeweils 4 Byte in einem Block. Somit ist die Adresse eines 32-Bit-Blocks immer ein Vielfaches von 4. Bei der 16- und 8 Bit-Methode kann es hingegen zu Zugriffen auf Blöcke kommen, deren Adresse nicht durch 4 teilbar ist. Der Zugriff auf eine nicht durch 4 teilbare Adresse (engl. "unalinged access") löst eine Ausnahmebehandlung (engl. "Trap") aus und dauert somit mehr als einen Buszyklus ¹⁸ .

Damit ergibt sich automatisch eine größere Zugriffszeit für Blockgrößen, die kleiner als die Wortgröße des jeweiligen Prozessors sind. Dieser Effekt trifft nicht nur auf das Vertauschen der Spalten zu, sondern auf alle Bereiche im zu untersuchenden Algorithmus. Denn schließlich findet in jedem Bereich in irgendeiner Art und Weise ein Zugriff auf einen Block aus dem Speicher statt.

¹⁸ Vgl. www.mikrocontroller.net: Digitaltechnik

4.4.3 Optimierungsmöglichkeit

Beim Vertauschen der Spalten habe ich eine Möglichkeit für eine Code-Optimierung entdeckt. Obwohl diese unabhängig von der Blockgröße ist, möchte ich sie in dieser Arbeit präsentieren. Um die Optimierung nachzuvollziehen, muss der Algorithmus für das Vertauschen der Spalten etwas detaillierter betrachtet werden (siehe Abbildung 22).

Abbildung 22: Beispiel für das Vertauschen von Spalten (Originalvariante)

Zunächst muss vor der Vertauschung klar sein, welche Bits extrahiert werden müssen. Die Positionen dieser Bits innerhalb der Blöcke werden durch die Variablen test1 und test2 repräsentiert. Mithilfe dieser Hilfsvariablen kann geprüft werden, was für ein Bit sich an der jeweiligen Stelle im Block befindet. Dementsprechend können Variablen (bit1 und bit2) erzeugt werden, die genau diese Bits an der zu vertauschenden Stelle besitzen. Mithilfe einer Maske (mask1 und mask2) werden alle Bits im Ausgangsblock übernommen (bis auf das zu vertauschende Bit). An der Stelle des zu vertauschenden Bits kann nun das jeweils andere Bit (welches sich in den Variablen bit1 oder bit2 befindet) durch eine OR-Verknüpfung eingesetzt werden.

Dieser Algorithmus wird für jegliche Variationen ausgeführt, selbst wenn die zu vertauschenden Bits gleich sind. Die Wahrscheinlichkeit, dass die zu vertauschenden Bits gleich sind und somit gar keine Vertauschung stattfinden muss, beträgt immerhin 50%.

Der erste Schritt in einer optimierten Variante wäre also zu prüfen, ob Bits vertauscht werden müssen. Wenn das der Fall ist, dann lässt sich ebenso voraussagen, dass sich die Bits an den jeweiligen Stellen verändern (da es nur zwei Möglichkeiten gibt). Eine 1 wird zu einer 0 oder eine 0 wird zu einer 1. Verändert man in diesem Fall einfach nur die Werte der Bits, dann müssen keine Bits herausgenommen, vertauscht und hineingepackt werden. Der in Abbildung 23 dargestellte Algorithmus veranschaulicht die Funktionsweise der optimierten Variante.

Abbildung 23: Beispiel für das Vertauschen von Spalten (optimierte Variante)

Die optimierte Variante erspart das Verwenden einer Maske "mask" (2 XOR- und 2 AND-Operationen), das Verwenden einer Zwischenvariable "bit" (2 Multiplikationen und 1 OR-Operation) sowie einen Vergleich.

Stattdessen werden zusätzlich 2 Shift-Operationen benötigt und (nur im Falle einer Vertauschung!) zwei XOR-Operationen.

Es soll nun messtechnisch geprüft werden, ob die optimierte Variante wirklich schneller ist. Dazu werden beide Methoden innerhalb der Datei solveOpt.c für N = 12000 zunächst kompiliert und ausgeführt. Mit Gprof lässt sich danach die Ausgabedatei für das ausgeführte Pro- gramm solveOpt.exe lesen. Die erhaltene Ausgabe ist in der folgenden Abbildung dargestellt.

Abbildung 24: Ausgabe für die Messungen von swapOrg() und swapOpt()

Mit einer Differenz von 0,88 Sekunden erweist sich die optimierte Variante tatsächlich als schnellere. Zwar konnte die Laufzeit für das Spalten Vertauschen bei N = 12000 nur um rund 10% gesenkt werden, jedoch wird mit steigendem N die Laufzeitdifferenz immer größer, da der Vorgang für das Spaltenvertauschen eine quadratische Komplexität besitzt.

5 Diskussion der Ergebnisse und Ausblick

5.1 Zusammenfassung

Zusammenfassend lässt sich sagen, dass die Blockgröße das Laufzeitverhalten entscheidend beeinflusst. Dabei schneidet die 1-Bit-pro-Block-Variante bei fast allen messtechnischen Betrachtungen (außer beim Laden der Matrix) eindeutig schlechter ab als die Block-Variante, wobei die Gründe dafür je nach Teilbereich im Algorithmus unterschiedlich sind. In Tabelle 11 findet man die Beobachtungen für die Gegenüberstellung der Bit-pro-Block-Variante mit der Block-Variante noch einmal zusammenfassend dargestellt.

Tabelle 12: Zusammenfassung der Beobachtungen für die Bit-pro-Block- und die Block-Variante

Da die Block-Variante sich als bessere Variante profiliert hat, schien die Betrachtung für die unterschiedlichen Blockgrößen umso interessanter. Auch hier ließ sich für jeden Teilbereich eine einfache Regel feststellen: Je geringer die Blockgröße, desto größer die Laufzeit.

Prompt könnte man daraus schlussfolgern, dass bei immer größer werdender Blockgröße der Algorithmus immer schneller wird, was jedoch nicht immer zutrifft. Denn schließlich führte die 64-Bit-Variante zu keiner Laufzeitverbesserung gegenüber der originalen (32-Bit) Variante. Da alle Messungen auf einem 32-Bit-Prozessor gemacht wurden und die 32-Bit-Variante als schnellste Variante gemessen wurde, kann man sagen, dass die Blockgröße mit der Busbreite des Prozessors übereinstimmen sollte. Das hat mehrere Gründe:

1. Einzelne Operationen können für Blöcke mit der Größe der Prozessorbusbreite schneller ausgeführt werden. Je geringer die Blockgröße ist, desto mehr Bytes müssen "ausgeschnitten werden".

2. Je mehr Bits gleichzeitig behandelt werden können (bei einem 32-Bit-Prozessor maximal 32 Bits), desto schneller wird die gesamte Datenmenge abgearbeitet. 3. Der Zugriff auf Adressen im Speicher, die irgendwo zwischen der Wortgrenze (32 Bit) liegen, kostet wegen Ausnahmebehandlungen viel mehr Zeit.

Bei der Eliminierung, welche für große N am meisten Zeit benötigt, wurde auch mathematisch gezeigt, dass eine maximale Blockgröße am geeignetsten ist, denn das kubische Lauf-

zeitverhalten kann um den Faktor

5.2 Beurteilung der Ergebnisse

In dieser Arbeit wurde der Einfluss der Blockgrößen für alle drei Teilbereiche der Eliminierung mathematisch und messtechnisch untersucht. Bei der Rekonstruierung der Zahl an Operationen wurden trotz mathematischer Vorgehensweise Vereinfachungen vorgenommen, die die später abgeleiteten Aussagen eventuell stark beeinflussen. So wurde z.B. bei der Eliminierung angenommen, dass nur bestimmte Operationen als Operationen gezählt werden. Für den Vergleich zwischen den vorgestellten Varianten genügen diese Vereinfachungen jedoch und belegen die meisten der vorgenommenen Messungen. Besonders an den Stellen, wo die mathematischen Vorüberlegungen nicht durch die Messungen bestätigt wurden (z.B. beim Vertauschen der Spalten), spielen viele verschiedene Einflussfaktoren eine Rolle, die unter anderem auf Messvoraussetzungen zurückzuführen sind. Da alle Messungen auf einem 32 Bit-Prozessor gemacht wurden, eignet sich die gesamte Prozessorarchitektur perfekt für die 32 Bit-Variante. Für 16-Bit-Prozessoren könnten beispielsweise andere Ergebnisse vorausgesagt werden.

Es wurden zwar einige Gründe für die unterschiedlichen Messergebnisse präsentiert, aber ich denke nicht, dass wirklich alle Beobachtungen dadurch zu erklären sind. So bleibt zum Beispiel offen, wie stark die einzelnen Einflussfaktoren im Verhältnis zueinander die Laufzeit beeinflussen und warum das so ist. In dieser Arbeit konnten nur Vermutungen darüber angestellt werden.

Die Arbeit orientierte sich außerdem an der Betrachtung der Laufzeit, nicht jedoch an der Betrachtung des Speicherverbrauchs. Wie man aber sehen konnte, greift die Speicherkomplexität stark in das Laufzeitverhalten ein, z.B. bei der Auslagerung von Daten auf die Festplatte. Entsprechend wäre es bei späteren Untersuchungen notwendig die Messungen in Unabhängigkeit vom Speicher durchzuführen. Da für die Bit-pro-Block-Variante sehr viel Speicher verarbeitet werden muss, könnte das Speichermanagement das Ergebnis sogar insoweit verfälscht haben, dass sich die Bit-pro-Block-Variante doch als schnellere Lösung profiliert. Unabhängig davon wurden die Messungen nur auf einem einzigen "Haus-PC" vorgenommen. Dabei beeinflussen natürlich sonstige Anwendungen, die gleichzeitig ablaufen, die zu unterschiedlichen Zeiten durchgeführten Messungen. Der Störeinfluss konnte zwar durch das Ver- wenden des kleinsten Messwerts aus einer Reihe von 5 Messwerten reduziert, aber nicht aus-

gelöscht werden. Ebenso ist unklar, ob der Compiler bei den einzelnen gemessenen Varianten kleinere Optimierungen vorgenommen hat, die bei den Einzelbetrachtungen nicht bedacht wurden, aber einen Einfluss auf die Laufzeit hatten.

Ich denke auch, dass die Organisation des Betriebssystems für die Messungen eine wichtige Rolle spielt. Daher sollten bei erneuten Betrachtungen unbedingt Messungen für verschiedene Betriebssysteme, Hardwarevoraussetzungen und Compiler angestellt werden um exaktere Ergebnisse zu erhalten. Daran angeknüpft wäre eine Betrachtung für verschiedene Optimierungsfunktionen des Compilers recht sinnvoll.

Um das gesamte Eliminationsverfahren zu analysieren wurde der Algorithmus in die drei wichtigsten Teile zerlegt, wobei jeder Teil einzeln nachprogrammiert und untersucht wurde. Dabei wurden ebenfalls Vereinfachungen vorgenommen, besonders beim Erstellen der Matrix. Für jeden Teilbereich wurden die Messungen mit ein und derselben Matrix durchgeführt. Es wurden zwar statistisch gesehen genauso viele Einsen wie Nullen in der Matrix verteilt, aber das Muster der Matrix war immer gleich (10101010...). Es wäre günstiger gewesen zufällig generierte Matrizen zu verwenden um unabhängigere Messergebnisse zu erzielen. Insgesamt konnte eine Betrachtung für verschiedene Blockgrößen geschehen und entsprechende Einflussfaktoren ermittelt werden, jedoch sind die Ergebnisse von vielen Messvoraussetzungen und vorgenommenen Vereinfachungen abhängig. Für genauere und allgemeingültigere Ergebnisse sollten daher die angegebenen Messvoraussetzungen verändert und variiert werden.

5.3 Persönliche Erfahrungen

Das Arbeiten an der BELL erwies sich für mich als besondere Herausforderung und verschaffte mir einen gewaltigen Einblick in die Welt der Hochschulinformatik. Die Funktionsweise von Wet Paper Codes, die erst 2004 entwickelt wurden, weckte bei mir großes Interesse, weshalb ich mich für diese Themenwahl entschied. Durch den zu untersuchenden Algorithmus habe ich zunächst die Statistik-Umgebung R kennen gelernt, die ich für eigene statistische Betrachtungen sehr zu schätzen gelernt habe. Die erste Betrachtung des performance-orientierten C-Quelltextes erwies sich für mich als Java-Programmierer als sehr große Schwierigkeit. Durch die Arbeit am Quelltext musste ich mich intensiv mit C auseinandersetzen und habe für mich neue Wege der Codeoptimierung entdeckt. Bei der Suche nach Performance-Verbesserungen habe ich zum ersten Mal mit Profilern experimentiert und wertvolle Erkenntnisse gewonnen, welche Einzelheiten die Laufzeit stark beeinflussen können. Ich denke nicht, dass ich ohne die BELL so schnell in Berührung mit diesen Kenntnissen gekommen wäre und bin dafür sehr dankbar. Erst jetzt ist mir bewusst, dass die fertige Programmierung eines neuen Algorithmus nicht das Ende ist, sondern bei größerer Programmlaufzeit den Anfang für Performance-Optimierungen bildet. Die gewonnenen Kenntnisse über die Komplexität von Algorithmen und die Rechnerarchitektur bilden zwar nur ein kleines Blickfenster, aber sind definitiv ausschlaggebend für eine ganz andere Herangehensweise an die Programmierung.

Neben neu gewonnenen Kenntnissen über die Informatik war für mich das Arbeiten mit wissenschaftlichen Quellen ebenso spannend wie interessant. Obwohl die meisten Fassungen englischer Sprache waren und die theoretischen Betrachtungen zunächst kompliziert erschienen, lohnt sich das zeitintensive, aber gewissenhafte Auseinandersetzen mit diesen Quellen um die gewonnenen Informationen auf das zu bearbeitende Problem anzuwenden. Aber auch das wissenschaftliche Arbeiten als Herangehensweise an die gesamte Arbeit war für mich

etwas Neues. Während der Anfertigung der Arbeit habe ich die IMRAD-Gliederung ¹⁹ für wissenschaftliche Publikationen kennen gelernt, welche in den USA als Standard-Format festgelegt wurde. Ich bin mir sicher, dass dieses Format für die Struktur kommender Arbeiten für mich eine große Hilfe sein wird.

Insgesamt hat mir die BELL unglaublich viele Einblicke verschafft, die in ihrer Gesamtheit meinen Erfahrungsschatz enorm erweiterten. Darüber hinaus hat das Arbeiten bzw. Forschen an diesem Thema sehr viel Spaß gemacht. Dabei motivierte mich jede gewonnenen Erkenntnis bzw. Idee noch mehr weiterzuforschen. Ich könnte mir somit vorstellen das Arbeiten an diesem Thema fortzusetzen um weitere ausstehende Optimierungsmöglichkeiten zu untersuchen.

5.4 Ausblick

Wet Paper Codes ermöglichen eine versteckte Nachrichtenübertragung ohne dass eine Festlegung der Auswahl der versteckten Stellen durch Sender und Empfänger geschehen muss. Damit sind Wet Paper Codes von großer Bedeutung für die Steganographie. Dementsprechend sollte auch keine Beeinträchtigung dieser Codes durch die Laufzeit der dafür verwendeten Algorithmen geschehen.

Es ist wichtig, weitere Optimierungsmöglichkeiten zu finden und den Algorithmus auf die Hardwarevoraussetzungen abzustimmen. Aufbauend auf den Ergebnissen dieser Arbeit schlage ich vor, eine Laufzeitbetrachtung auf einem 64-Bit-Rechner durchzuführen. Dabei sollte die 64-Bit-Variante deutlich schneller funktionieren als die 32-Bit-Variante auf einem 32-Bit-Rechner. Es kann dann geprüft werden, wie viel geringer die Rechenleistung auf dem 64-Bit-Rechner sein kann um mit der 32-Bit-Variante auf einem 32-Bit-Prozessor größerer Rechenleistung mitzuhalten.

Die Zahl an Mehrkernprozessoren auf dem Markt wird immer größer und entsprechend sollten sich Programmierer auf eine parallele Programmierung umstellen. Auch das Gaußsche Eliminationsverfahren im Polynomkörper GF(2 ⁿ ) kann durch Parallelisierung erheblich beschleunigt werden. SMITH ist eine Methode, die die Gaußsche Eliminierung und Rücksubstitution vereint. Während der Bearbeitung rotieren die Elemente in der Matrix so, dass alle Berechnungen von der 1. Zeile ausgehen. So können sich zwei Prozessoren die Arbeit für jede Zeile teilen. Die Entwickler dieser Methode versprechen eine Verringerung der Laufzeitkomplexität, die genauere Betrachtungen interessant erscheinen lassen ²⁰ . Das Verfahren von Strassen ist sehr vielversprechend und wird (unter anderem in R) erfolgreich eingesetzt. Obwohl ich zu dem Ergebnis gekommen bin, dass eine Anwendung auf den Polynomkörper GF(2 ⁿ ) zu keiner Verbesserung der Laufzeitkomplexität führt, meinen die Autoren von SMITH eine Verbesserung mithilfe von Strassen erzielen zu können ²¹ . Insgesamt stehen damit also noch einige interessante Betrachtungen für eine Effizienzverbesserung des Gaußschen Eliminationsverfahrens im Körper GF(2 ⁿ ) in Ausblick.

¹⁹ IMRAD: Introduction, Methodes, Results [and] Discussion, siehe Mayer, P.(2006): Publizieren in den Naturwissenschaften - Woher kommt der Vorsprung der Amerikaner und wie können deutschsprachige Wissenschaftler aufholen?

²⁰ Vgl. A. Bogdanov, M.C. Mertens, C. Paar, J. Pelzl, A. Rupp: Smith: A parallel Hardware Architecture for fast Gaussian Elimination over GF(2), S. 10-23

²¹ Vgl. ebd. S. 23

6 Literaturverzeichnis

Bogdanov, A. / Mertens, M.C./ Paar, C./ Pelzl, J. / Rupp, A. (2006): Smith: A parallel Hardware Architecture for fast Gaussian Elimination over GF(2). SHARCS '06, S. 10-23, Köln

Böhler, E. (Sommersemester 2007): Vorlesung Kryptographie. Der Polynomkörper GF(2 n ), Institut für theoretische Informatik, Universität Hannover

Fridrich, J. / Goljan, M. / Soukal, D. / Lisoněk, P. (2004): Perturbed Quantization Steganography with Wet Paper Codes. In: Security, Steganography and Watermarking of Multimedia Contents VII. S. 328-340, San Jose

Hommel, T. (2004): Wet Paper Codes. Institut für Systemarchitektur Datenschutz und Datensicherheit, TU Dresden Fakultät Informatik

Mayer, P. (2006): Publizieren in den Naturwissenschaften - Woher kommt der Vorsprung der Amerikaner und wie können deutschsprachige Wissenschaftler aufholen? In: Das Hochschulwesen, Ausgabe 3/2006, UniversitätsVerlagWebler, S. 82-88

Strassen, V. (1968): Gaussian Elimination is not Optimal. Numer. Math. 13, S. 354-356

www.mikrocontroller.net: Digitaltechnik, http://www.mikrocontroller.net/articles/Digitaltechnik (letzter Zugriff: 10. Januar 2008 16:08)

www.numerik.mathematik.uni-mainz.de: LR-Zerlegung,

http://www.numerik.mathematik.uni-mainz.de/didaktikseminar/Gruppe6/index.html (letzter Zugriff; 10. Januar 2008 16:33)