Cell Processor

Transcrição

Cell Processor

Hausarbeit
im Labor des Studienfachs
Rechnerstrukturen
zum Thema
Cell-Prozessor
Betreuer:
Prof. Dr. Thomas Risse
Autoren:
René Büst
(152400)
Manuel Bohlken
(153469)
Florian Brunkhorst
(151581)
Version
2.0
Semester:
Wintersemester 2007 / 2008
Semesterverband:
I7I
Ort, Datum:
Bremen, den 17.März 2008
Rechnerstrukturen
Inhaltsverzeichnis
I.
Inhaltsverzeichnis
I.
Inhaltsverzeichnis ...................................................................................................II
II.
Abbildungsverzeichnis........................................................................................... IV
III.
Quellenverzeichnis................................................................................................. V
IV.
Literaturverzeichnis ............................................................................................. VII
V.
Abkürzungen ........................................................................................................ IX
1.
Einführung .............................................................................................................1
1.1.
Die Entwicklung des Cell-Prozessors .................................................................................... 1
2.
Aufbau des Cell-Prozessors......................................................................................4
3.
Elemente des Cell-Prozessors...................................................................................7
3.1.
Power Processing Element (PPE) ......................................................................................... 7
3.2.
Synergistic Processing Elements (SPE)................................................................................ 10
3.3.
Element Interconnet Bus (EIB) .......................................................................................... 16
3.4.
Memory Interface Controller (MIC) ................................................................................... 16
3.5.
Bus Interface – FlexIO ...................................................................................................... 17
4.
Einsatzgebiete des Cell-Prozessors .........................................................................19
4.1.
Sony Playstation 3 ........................................................................................................... 19
4.2.
Playstation 3 Cluster........................................................................................................ 20
4.3.
Crackstation ................................................................................................................... 22
4.4.
Videoverarbeitung........................................................................................................... 24
4.4.1.
Einführung.................................................................................................................. 24
4.4.2.
Arbeitsablauf des VPR-Systems ..................................................................................... 25
4.4.3.
Programmiermodelle des VPR-Systems.......................................................................... 26
4.4.4.
Block Matching Algorithmus ......................................................................................... 27
4.4.5.
Parallelisierung des Block Matching Algorithmus............................................................. 28
4.4.6.
Ergebnisse der Parallelisierung des Block Matching Algorithmus....................................... 30
4.4.7.
OpenMP..................................................................................................................... 31
4.5.
Adaptive Echtzeitfilterung für digitale Röntgenanwendungen .............................................. 33
4.5.1.
Hintergrund ................................................................................................................ 33
4.5.2.
Hardware ................................................................................................................... 34
4.5.3.
Funktionsweise ........................................................................................................... 35
4.5.4.
Ergebnisse .................................................................................................................. 35
17.März 2008
Seite II
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Inhaltsverzeichnis
4.6.
Objekterkennung in Echtzeit............................................................................................. 36
4.6.1.
Hintergrund ................................................................................................................ 36
4.6.2.
boosting-based detection............................................................................................. 37
4.6.3.
histogram-based tracking ............................................................................................. 38
4.6.4.
Implementierung auf einem Cell-Simulator .................................................................... 39
4.6.5.
Ergebnisse der Implementierung auf einem Cell-Simulator............................................... 40
4.6.6.
Ergebnisse der Implementierung auf einer Playstation 3.................................................. 41
4.7.
SSL-Beschleunigung unter Verwendung der Cell Broadband Engine ...................................... 43
4.7.1.
Einführung.................................................................................................................. 43
4.7.2.
Hintergrund ................................................................................................................ 43
4.7.3.
Der Einsatz des Cell-Prozessors als ein Hardware-Security-Model ..................................... 45
4.7.4.
OpenSSL ..................................................................................................................... 46
4.7.5.
Implementierung......................................................................................................... 47
4.7.6.
Ergebnisse .................................................................................................................. 48
17.März 2008
Seite III
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Abbildungsverzeichnis
II.
Abbildungsverzeichnis
Abbildung 1 Beschriftetes Die-Foto des Cell-Prozessors [@03]................................................5
Abbildung 2 Schematische Darstellung eines Cell-Prozessors [@04] ........................................6
Abbildung 3 Befehlspipeline des PPE [@05] ..........................................................................9
Abbildung 4 Schema des SPEs [@04]..................................................................................10
Abbildung 5 Datenformate in den Registern der SPU [L04] ...................................................11
Abbildung 6 Aufteilung der Befehle auf Execution-Pipelines der SPU [L04].............................12
Abbildung 7 Pipeline der SPU [L01] ....................................................................................13
Abbildung 8 Beispiel für Streamed Processing [@01] ...........................................................14
Abbildung 9 Kommunikation über den MFC [@02] ..............................................................15
Abbildung 10 Konfigurationsmöglichkeiten des Cell-Prozessors [L01] ....................................17
Abbildung 11 Überblick über ein Framework zur Videoverarbeitung und Bereitstellung [L05]..25
Abbildung 12 Videoverarbeitung: (a) Service Modell und (b) Streaming Modell [L05] .............26
Abbildung 13: Block Matching [L05] ...................................................................................27
Abbildung 14: Geschwindigkeitsanalyse des Block Matching Algorythmus [L05].....................30
Abbildung 15 3D-Computertomographie [@21] ..................................................................33
Abbildung 16: Dual Cell Based Board [L10]..........................................................................34
Abbildung 17 (a) Originalaufnahme, (b) gefiltertes Röntgenbild [L10]....................................35
Abbildung 18 Klassifizierung von Versicherungsnehmern [@23] ...........................................37
Abbildung 19 Verfolgung von Gesichtern mittels Histogramm [@25] ....................................38
Abbildung 20: Parallele Erkennung von mehreren SPEs [L09]................................................39
Abbildung 21: Verarbeitungszeit der Objekterkennung und Objektverfolgung [L09] ...............40
Abbildung 22: Versuchsaufbau mit einer Playstation 3 [L09].................................................41
Abbildung 23: Verarbeitungszeit auf der Playstation 3 [L09] .................................................42
Abbildung 24: Objekterkennung und Objektverfolgung [L09]................................................42
Abbildung 25 Prozess zur Erstellung der SPE und PPE Programme [L11] ................................44
Abbildung 26: Zusammenspiel zwischen dem PPE und den SPEs [L11]...................................47
Abbildung 27 Entschlüsselungsdauer von 4096-bit Schlüsseln als Simulation (ein SPE) [L11]....48
Abbildung 28 Entschlüsselungsdauer 1 PPU vs. 1 SPU einer Playstation [L11].........................49
Abbildung 29 Entschlüsselungsdauer 1 PPU vs. 1 SPU einer Playstation [L11].........................49
Abbildung 30 Entschlüsselungsdauer 2 PPU vs. 16 SPU eines Cell-Blade-Centers [L11] ............49
17.März 2008
Seite IV
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Quellenverzeichnis
III.
Quellenverzeichnis
[@01] Nicholas Blachford: Cell Architecture Explained Version 2; 10.12.2007
http://www.blachford.info/computer/Cell/Cell0_v2.html
[@02] Yaegashi Takeshi: Basics of Cell Architecture; 04.01.2008
http://ps3.keshi.org/dsk/20061208/doc/
[@03] Frank Hüber: Test: Sony PlayStation 3; 13.01.2008
http://www.computerbase.de/artikel/hardware/multimedia/2007/ test_sony_playstation_3/
[@04] Autor Unbekannt: Wikipedia – Cell (Prozessor); 16.01.2008
http://de.wikipedia.org/wiki/Cell_%28Prozessor%29
[@05] Thomas Chen, Ram Raghavan, Jason Dale, Eiji Iwata: Cell Broadband Engine Architecture
and its first implementation; 10.12.2007
http://www.ibm.com/developerworks/power/library/pa-cellperf/
[@06] Autor unbekannt: Wikipedia – Simultaneous Multithreading; 17.03.2008
http://de.wikipedia.org/wiki/Simultaneous_Multithreading
[@07] Autor unbekannt: Playstation 3 Hardware; 17.03.2008
http://www.ps3station.de/hardware.php
[@08] Autor unbekannt: Wikipedia – AltiVec; 17.03.2008
http://de.wikipedia.org/wiki/AltiVec
[@09] Daniel Bachfeld: CrackStation statt PlayStation; 13.01.2008
http://www.heise.de/security/CrackStation-statt-PlayStation--/news/meldung/99754
[@10] Dr. Frank Mueller: Sony PS3 Cluster (IBM Cell BE); 12.01.2008
http://moss.csc.ncsu.edu/~mueller/cluster/ps3/
[@11] Oliver Lau: Erster Supercomputer mit Playstation-3-Knoten; 17.03.2008
http://www.heise.de/newsticker/Erster-Supercomputer-mit-Playstation-3-Knoten--/meldung/86534
[@12] Autor unbekannt: Hacker Uses Sony PlayStation 3 to Crack Passwords; 17.03.2008
http://www.pcworld.com/printable/article/id,140064/printable.html
[@13] Autor unbekannt: PlayStation speeds password probe; 17.03.2008
http://news.bbc.co.uk/2/hi/technology/7118997.stm
[@14] Britta Widmann: Hacker nutzt Playstation 3 als Passwortknacker; 17.03.2008
http://www.zdnet.de/security/news/0,39029460,39159393,00.htm
[@15] Patrick Gray: PlayStation a hacker's dream; 17.03.2008
http://www.theage.com.au/news/security/playstation-a-hackersdream/2007/11/26/1196036813741.html
17.März 2008
Seite V
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Quellenverzeichnis
[@16] Autor unbekannt: Wikipedia – Rainbow Tables; 17.03.2008
http://de.wikipedia.org/wiki/Rainbow_table
[@17] Autor unbekannt: Wikipedia – Brute Force (Informatik); 17.03.2008
http://de.wikipedia.org/wiki/Brute_force#Informatik
[@18] Ulrika Hedquist: Kiwicon demo uses PlayStation 3 to crack passwords; 14.03.2008
http://computerworld.co.nz/news.nsf/scrt/C50D36EFEC2B482ACC2573A00070EF83,
[@19] Björn Eisert: Was ist MPEG?; 14.03.2008
http://www.cybersite.de/german/service/Tutorial/mpeg/
[@20] OpenMP Architecture Review Board: OpenMP C and C++ Application Program Interface;
17.03.2008
http://www.openmp.org/mp-documents/cspec20.pdf
[@21] Mercury Computer Systems: Computed Tomography Reconstruction; 14.03.2008
http://www.mc.com/uploadedFiles/Cell-Perf-Simple.pdf
[@22] Magdalena Szczot: Boosting schwacher Lerner; 17.03.2008
http://www.informatik.uni-ulm.de/ni/Lehre/SS05/HauptseminarMustererkennung/ausarbeitungen/Szczot.pdf
[@23] Prof. Dr. Stefan Conrad: Klassifikation; 17.03.2008
http://www.dbs.informatik.uni-muenchen.de/buecher/Kap4.Klassifikation.ppt
[@24] Autor unbekannt: Wikipedia – Histogramm; 17.03.2008
http://de.wikipedia.org/wiki/Histogramm
[@25] Stan Birchfield: Elliptical Head Tracking Using Intensity Gradients and Color Histograms;
17.03.2008
http://www.ces.clemson.edu/~stb/presentations/headtracker_cvpr1998.ppt
[@26] Autor unbekannt: Wikipedia – OpenSSL; 17.03.2008
http://en.wikipedia.org/wiki/Openssl
[@27] Autor unbekannt: Wikipedia – Transport Layer Security; 17.03.2008
http://en.wikipedia.org/wiki/Transport_Layer_Security
[@28] Autor unbekannt: Wikipedia – Chinese Remainder Theorem; 17.03.2008
http://en.wikipedia.org/wiki/Chinese_remainder_theorem
[@29] John Stokes: Introducing the Cell Processor – Part2: The Cell Architecture; 12.12.2007
http://arstechnica.com/articles/paedia/cpu/cell-2.ars
[@30] John Stokes: Introducing the IBM/Sony/Toshiba Cell Processor – Part1: the SIMD
processing units; 12.12.2007
http://arstechnica.com/articles/paedia/cpu/cell-1.ars
17.März 2008
Seite VI
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Literaturverzeichnis
IV.
[L01]
Pham, D., Asano, S., Bolliger, M., Day, M.N., Hofstee, H.P., Johns, C., Kahle, J., Kameyama, A.,
Keaty, J., Masubuchi, Y., Riley, M., Shippy, D., Stasiak, D., Suzuoki, M., Wang, M., Warnock, J.,
Weitzel, S., Wendel, D., Yamazaki, T., Yazawa, K (2005): The Design and Implementation of a
First-Generation CELL Processor. In: Proc. IEEE International Solid- State Circuits Conference,
pp. 184–185. IEEE Computer Society Press, Los Alamitos
[L02]
Andreas Stiller (2007) Zelluläre Strukturen – Die Architektur der Cell Broadband Engine,
Zeitschrift: C’t magazin für computer technik, Ausgabe: 12/2007, Seite 196 - 201
[L03]
IBM Systems and Technology Group (2007): Cell Broadband Engine Architecture Version 1.02,
11. Oktober 2007
[L04]
IBM Systems and Technology Group (2007): Synergistic Processing Unit Instruction Set
Architecture Version 1.2, 27. Januar 2007
[L05]
Yu, Junqing, Wei, Haitao (2007) Video Processing and Retrieval on Cell Processor Architecture
(Ausgabe: 4740/2007
[L06]
Liu, F., Chaudhary, V. (2003): Extending OpenMP for Heterogeneous Chip Multiprocessors. In:
Proc. 32nd International Conference on Parallel Processing
[L07]
Eichenberger, A.E., O’Brien, K., O’Brien, K., Wu, P., Chen, T., Oden, P.H., Prener, D.A., Shepherd,
J.C., So, B., Sura, Z., Wang, A., Zhang, T., Zhao, P., Gschwind, M. (2005): Optimizing Compiler for
a CELL Processor. In: Proc. 14th International Conference on Parallel Architectures and
Compilation Techniques
17.März 2008
Seite VII
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
[L08]
Wei, H., Yu, J. (2007): Mapping OpenMP to Cell: A Effective Compiler Framework for
Heterogeneous Multi-Core Chip. In: Proc. International Workshop on OpenMP
[L09]
Sugano, Hiroki, Miyamoto Ryusuke (2007) A Real-Time Object Recognition System on Cell
Broadband Engine
[L10]
Bockenbach, Olivier, Mangin, Michel, Schuberth, Sebastian (2006) Real Time Adaptive Filtering
for Digital X-Ray Applications
[L11]
Costigan, N., Scott, M (2007), Accelerating ssl using the vector processors in ibm’s cell
broadband engine for sony’s playstation 3
[L12]
Zhao Iyer Srihari Makineni Laxmi Bhuyan. Anatomy and performance of SSL processing. In Proc.
IEEE Int. Symp. Performance Analysis of Systems and Software, pages 197–206, 2005.
17.März 2008
Seite VIII
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Abkürzungen
V.
Abkürzungen
CBE
Cell Broadband Engine
DCBB
Dual Cell-Based Blade
DMA
Direct Memory Access
DRM
Digital Rights Management
EIB
Element Interconnect Bus
GPGPU
General Purpose Graphic Processing Unit
IPC
Instructions per Cycle
MFC
Memory Flow Controller
MIC
Memory Interface Controller
PPE
Power Processor Element
SIMD
Single Instruction Multiple Data
SPE
Synergistic Processing Element
SSL
Secure Socket Layer
STI
Sony Toshiba IBM
VPR
Video processing and retrieval
XDR
Extreme Data Rate
17.März 2008
Seite IX
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Einführung
1.
Einführung
Der Cell-Prozessor wurde Anfang des Jahres 2005 erstmals der Öffentlichkeit als Cell Broadband
Engine Architecture bzw. kurz Cell BE vorgestellt. Die Idee dieses Prozessors geht aber bereits
auf das Jahr 1999 zurück. Sonys Ken Kuratagi, der Vater der Playstation, hatte die Idee eines
Prozessors, der wie Zellen in einem biologischen System agiert, indem sich mehrere Zellen
verbinden und gemeinsam arbeiten können.
Bereits im darauf folgenden Jahr begannen die Arbeiten an der Konzeption und Entwicklung
eines solchen Prozessors, dessen erstes Einsatzgebiet im Multimedia- und Gaming-Bereich
bereits feststand. Der Cell-Prozessor sollte in der Playstation3 Einsatz finden und die Leistung
seines Vorgänger-Prozessors aus der Playstation2 um den Faktor 100 übertreffen. Für die
Entwicklung schlossen sich die Firmen Toshiba und Sony, die bereits an der Entwicklung des
Prozessors für die Playstation2 zusammen arbeiteten, sowie IBM zusammen und formten nun
die „STI Aliance“. (vgl. [@01])
1.1.
Die Entwicklung des Cell-Prozessors
Innerhalb der „STI Aliance“ gab es zwischen den Herstellern unterschiedliche Anforderungen an
den neu zu entwickelnden Prozessor. Sony und Toshiba hatten insbesondere ein Interesse an
Energieeffizienz und Zuverlässigkeit, da der Prozessor auch im Embedded- sowie im HomeEntertainment-Bereich, zu dem unter anderem die Playstation3 zählt, Verwendung finden soll.
IBM hatte bei der Entwicklung die Anforderung, dass der Prozessor mehrprozessorfähig ist,
zudem sollte er binär kompatibel zu vorherigen PowerPC-Prozessorgenerationen sein. Hierbei
zielte IBM insbesondere auf den Einsatz des Cell-Prozessors in Server-Systemen ab. (vgl. [@01])
Aus diesen Anforderungen entstanden die folgenden Ziele in der Entwicklung: (vgl. [L01])
Ø Sehr hohe Rechenleistung – insbesondere für Spiele und Multimedia-Anwendungen
Ø Echtzeit-Antwortzeiten an den Anwender und dem Netzwerk
o Kontinuierliche Rückmeldung an den Anwender/Spieler z.B. durch eine
kontinuierlich in Echtzeit aktualisierte virtuelle Umgebung
o Unterstützung von Echtzeit-Betriebssystemen
o Aber auch Unterstützung von Nicht-Echtzeit-Betriebssystemen zur Ausführung
von Anwendungen zur Verbindung mit dem Internet
17.März 2008
Seite 1
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Einführung
o Somit auch Verarbeitung von kommunikationsorientierten Daten
o Aber auch Unterstützung von weiteren im Internet vorkommenden Daten – z.B.
Digital Rights Management (DRM)
Ø Anwendbar auf verschiedene Plattformen
o Entwicklung der Broadband-Architektur wurde getrieben von der Entwicklung
eines Prozessors für die nächste Entertainment-System-Generation
o Broadband-Architektur aber auch interessant für Anwendungen außerhalb des
Entertainment-Segments
o Zur Erreichung einer breiteren Entwickler-Gemeinschaft für die BroadbandArchitektur
wurde
eine
offene
Linux
basierende
Software-
Entwicklungsumgebung entwickelt
Ø Niedriger Energiebedarf
o Das Hochfrequenzdesign der Broadband-Architektur reduziert die Anzahl der
Gatter, welche pro Zyklus durchlaufen werden müssen
o Ermöglicht dem Prozessor mit niedrigerer Spannung und Leistungsaufnahme zu
arbeiten.
Insbesondere die hohe Rechenleistung in Kombination mit niedrigem Energiebedarf sind dabei
in der Vergangenheit eher widersprüchliche Ziele gewesen, wurde hohe Rechenleistung doch
oft durch spekulative Hardware erzielt, die den Energiebedarf jedoch in die Höhe trieb. Dabei
brachte der Einsatz spekulativer Hardware nicht in jedem Fall die gewünschten
Performancesteigerungen. Zur Erreichung dieser Ziele ging man bei der Entwicklung des CellProzessors daher einen etwas anderen Weg. Es wurde die Komplexität des Prozessors
reduziert, indem auf die spekulative Hardware verzichtet wurde. Hierdurch konnte der
Energiebedarf gesenkt werden. Durch die nun geringere Abwärme des Prozessors ist eine
Erhöhung der Taktraten möglich geworden, um so das Ziel der hohen Rechenleistung erreichen
zu können. (vgl. [@01], [L02])
17.März 2008
Seite 2
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Einführung
Der aus der Entwicklung resultierende und wie bereits eingangs erwähnt im Jahr 2005
vorgestellte erste Cell BE-Prozessor wies dabei folgende Eigenschaften auf:
Ø 3,2 Ghz Taktrate
Ø 90nm Fertigungsprozess
Ø 1 Power Prozessing Element (PPE)
Ø 8 Synergistic Processing Elements (SPE)
Der Cell-Prozessor soll laut IBM in vielen Aufgaben bis zu 10x schneller sein als bisherige CPUs.
Diese Aussage ist jedoch kritisch zu betrachten, da es vielleicht auf verfügbare Desktop-CPUs
zutrifft, jedoch nicht auf Prozessoren, wie sie z.B. auf aktuellen Grafikkarten verwendet werden.
Diese aktuellen GPUs sind auch in der Lage, nicht-grafische Aufgaben zu erledigen (Stichwort
GPGPU) und dies in der gleichen Geschwindigkeit wie der Cell-Prozessor oder sogar schneller.
Wenn man betrachtet, das die Architektur des Cell-Prozessors der von GPUs ähnelt, wobei es
sich anstelle der SPEs um Pixel-/Vertexshader-Units handelt, relativiert sich die hohe
Leistungsfähigkeit. Jedoch ist anzumerken, dass der Cell-Prozessor für sehr viel mehr Aufgaben
einsetzbar ist als GPGPUs. Zudem liefert er mit dem PPE sozusagen einen Hauptprozessor mit,
welcher bei den GPGPUs noch fehlt. Des Weiteren ist der Cell-Prozessor aufgrund der sehr viel
allzwecktauglicheren Auslegung im Vergleich zu den GPGPUs, bei welchen primär die
Grafikberechnung im Vordergrund steht, einfacher zu programmieren. (vgl. [@01])
Seit März 2007 wird der Cell-Prozessor in 65nm gefertigt, weiterhin mit einer Taktrate von
3,2Ghz.
17.März 2008
Seite 3
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Aufbau des Cell-Prozessors
2.
Ein wesentliches Merkmal des Cell-Prozessors ist, dass er aus mehreren unterschiedlichen
parallel arbeitenden Kernen besteht, welche mit einem Bussystem verbunden sind. Dabei gibt
es einen Hauptprozessor, das so genannte PPE, welches den Hauptprogrammfluss steuert
(Betriebssystem, Programmsteuerung etc.) und untergeordnete spezialisierte Recheneinheiten,
die so genannten SPEs, denen Aufgaben vom PPE zugewiesen werden, welche sie dann
bearbeiten. Diese Spezialisierung der SPEs hat den Vorteil, dass sie nur einen geringen
Platzbedarf auf dem Chip und einen geringen Strombedarf besitzen. (vgl. [L02])
Laut Spezifikation kann ein Cell-Prozessor aus einem oder mehreren PPEs und einem oder
mehreren SPEs aufgebaut sein, welche durch den Element Interconnect Bus, dem Bussystem im
Cell-Prozessor, verbunden sind. Die erste Generation des Cell-Prozessors besteht jedoch, wie in
der Einführung bereits erwähnt, aus nur einem PPE und 8 SPEs. Die hohe Anzahl dieser parallel
arbeitenden Prozessoren ist ein entscheidender Grund für die hohe Performance des CellProzessors. (vgl. [@01])
Auch andere Prozessorhersteller sind dazu übergegangen, mehrere Prozessorkerne auf einem
Chip unterzubringen (z.B. Intels Core2Duo, AMDs Opteron), da man bei der Verkleinerung der
Chipstrukturen an die Grenzen der Frequenzerhöhung gestoßen ist. Dabei kam es aufgrund von
hohen Leckströmen bei den kleiner werdenden Strukturen zu enorm ansteigendem
Strombedarf und entsprechend hohem Kühlbedarf der Prozessoren. Im Gegensatz zum CellProzessor verwenden die anderen Mehr-Kern-Architekturen jedoch identische Prozessorkerne.
(vgl. [@02])
Ein weiterer im wahrsten Sinne zentraler Bestandteil des Cell-Prozessors ist der bereits
erwähnte Element Interconnect Bus (EIB). Dieser besteht aus vier in beide Richtungen
laufenden Ringbussen. Er verbindet dabei den L2-Cache des PPE mit den DMA-Controllern der 8
SPEs, wie auch aus der schematischen Darstellung in Abbildung 1 ersichtlich wird.
Neben dem PPE und den SPEs werden auch die zwei ebenfalls auf dem Chip befindlichen
Controller (Speicher-Controller und I/O-Controller) über den EIB mit den anderen
Komponenten des Cell-Prozessors verbunden. Die Controller verbinden den Cell-Prozessor mit
der Peripherie. Mit dem Speicher-Controller wird der Prozessor über das von Rambus
17.März 2008
Seite 4
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
entwickelte XDRAM™ Interface an den Dual Channel Rambus XDR-Speicher (extreme Data Rate)
angebunden. (vgl. [@29], [L02])
Der I/O-Controller dient zur Kommunikation des Prozessors mit der restlichen Hardware des
Systems. Zur Anbindung des Prozessors an die Hardware greift der I/O-Controller auf das von
ebenfalls Rambus entwickelte FlexIO-Interface zu. (vgl. [L02])
In der folgenden Abbildung ist ein Die des Cell-Prozessors abgebildet, in welchem die einzelnen
Elemente des Prozessors gekennzeichnet sind.
Abbildung 1 Beschriftetes Die-Foto des Cell-Prozessors [@03]
17.März 2008
Seite 5
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Die dunklen Bereiche innerhalb der SPEs in Abbildung 1 stellen dabei deren 256KByte großen
Local Store dar. Daran ist gut zu sehen, wie viel Platz der Speicher im Verhältnis zur restlichen
Hardware auf einem Chip beansprucht.
Da aus Abbildung 1 die Verbindungen der einzelnen Elemente nicht hervorgehen, hilft hier die
schematische Darstellung des Cell-Prozessors. Anhand dieser Grafik ist auch zu erkennen, dass
der I/O-Controller doppelt am EIB angebunden ist.
Abbildung 2 Schematische Darstellung eines Cell-Prozessors [@04]
In Abbildung 2 wird der EIB „On-chip coherent bus“ genannt. Diese Bezeichnung begründet sich
darin, als das es sich bei dem EIB um einen kohärenten Bus handelt, welcher es ermöglicht, das
ein einzelner Adressraum von dem PPE und den SPEs geteilt wird, um so die Kommunikation
effizienter zu machen und die Programmierung zu erleichtern. (vgl. [L01])
Im folgenden Kapitel sollen die einzelnen Elemente des Cell-Prozessors näher erläutert werden.
17.März 2008
Seite 6
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Elemente des Cell-Prozessors
3.
3.1.
Power Processing Element (PPE)
Beim PPE handelt es sich im Grunde um eine 64Bit PowerPC-Architektur, die im Wesentlichen
aus zwei Teilen besteht. Zum einen aus der PowerPC Processing Unit (PPU), welche die
Berechnungen durchführt, inkl. jeweils einem 32KByte großen Level-1 Cache für Daten und
Instruktionen. Zum anderen aus dem PowerPC Processor Storage Subsystem (PPSS) mit einem
512KByte großen Level-2 Cache, welches Speicheranfragen von der PPU und Anfragen von den
SPEs oder den I/O-Geräten an das Power Processing Element bearbeitet. (vgl. [@01], [L01])
Diese Architektur ist eine Load/Store-RISC Architektur mit 32 General-Purpose und 32 FloatingPoint Registern. Zudem besitzt das PPE die in der Kurzform VMX genannte Vector Media
Extension, welche auch unter der Markenbezeichnung Altivec™ bekannt ist. Über diese wird
dem PPE die Single Instruktion Multiple Data(SIMD)-Funktionalität bereitgestellt. Somit ähnelt
das PPE vom Konzept den noch in Apples verwendeten G5 Prozessoren inkl. dessen 32Bit und
64Bit Befehlssatz. (vgl. [@05], [@30])
Die Implementierung unterscheidet sich jedoch grundlegend von den heute üblichen RISCProzessoren. So wurde auf out-of-order Hardware verzichtet, welche Befehle in den
Ausführungseinheiten eines Prozessors außerhalb der Programmreihenfolge auszuführen
würde, um die Pipelines möglichst gut auszulasten. Die Befehle werden im PPE daher nur inorder ausgeführt. Zudem wird auch nur eine sehr einfache Logik für die Sprungvorhersage
verwendet.
Die Befehlsausführung out-of-order und eine aufwändige Sprungvorhersage bringen zwar einen
Performancegewinn, welcher allerdings mit hohem Platzverbrauch auf dem Chip sowie
stärkerer Hitzeentwicklung durch die zusätzliche Hardware erkauft wird. Um den Verzicht auf
diese Technologien zu kompensieren, hat man sich einfacher Lösungen bedient. Anstelle einer
aufwändigeren Sprungvorhersage auf dem Chip kann der Compiler mit Branch Hint
Instruktionen die Wahrscheinlichkeit für eine teure Neubefüllung der Ausführungspipeline
deutlich senken, und so den Leistungsverlust im Vergleich zu einer aufwändigeren
Sprungvorhersage zumindest annähernd ausgleichen. (vgl. [@01], [@05], [L01], [L02])
17.März 2008
Seite 7
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Die Performance-Einbußen durch den Verzicht auf out-of-order Hardware werden zu einem
großen Teil durch ein Dual-Threaded-Design des PPEs wettgemacht. Durch die out-of-order
Befehlsausführung wird zwar die Anzahl der Instructions per Cycle (IPC) erhöht, aber durch
Daten- und andere Abhängigkeiten werden in realen Anwendungen meist nur Werte kleiner als
zwei Instructions per Cycle erreicht. Das Dual-Threaded-Design des PPE erlaubt ebenfalls zwei
Instructions per Cycle, jedoch aus zwei verschiedenen Threads, so dass der Leistungsverlust
durch Verzicht auf die out-of-order Hardware kompensiert werden kann. (vgl. [L03])
Die Technologie hinter dem Dual-Threaded-Design wird Simultaneous Multi-Threading (SMT)
genannt und ähnelt in der Funktion dem von Intel verwendeten Hyperthreading – die wohl
bekannteste Umsetzung von SMT. Ziel von SMT ist es, die bereits aufgrund der PipelineArchitektur redundant vorhandenen Ressourcen eines Prozessors noch besser auszulasten, als
es bei der Pipeline-Architektur ohnehin möglich ist. SMT bezeichnet die Fähigkeit eines
Mikroprozessors, mittels getrennter Pipelines und zusätzlicher Registersätze mehrere Threads
gleichzeitig auszuführen. (vgl. [@06])
Für die Ausführung von zwei Threads nach dem SMT-Konzept im PPE steht jedem Thread ein
kompletter Registersatz zur Verfügung. Dies sind jeweils 32 Integer-, 32 FPU-, 32 VMX- sowie
ein paar Steuerregister. Die restlichen Ressourcen wie Caches, Queues und Funktionseinheiten
werden
jedoch
geteilt.
Normalerweise
wird
der
Befehlsnachschub
aus
dem
L1-
Instruktionscache mit jedem Takt gewechselt. Muss jedoch ein Thread lange auf den Speicher
warten, so läuft der andere während dessen weiter.
Beim PPE handelt es sich also um einen einfachen RISC-Prozessor, ähnlich der bekannten 64 Bit
PowerPC-Architektur, wodurch die Portierung und Ausführung von bestehenden Programmen
erleichtert wird. Hierbei ist es auch nicht zwingend notwendig, dass die Berechnungen auf die
SPE’s verteilt werden. Das PPE kann Programme auch vollkommen selbstständig ausführen. Um
die Leistung des Cell-Prozessors ausschöpfen zu können, ist eine Verteilung der Berechnung
jedoch unabdingbar. In der Cell-Architektur dient der PPE daher vorwiegend als Organisator, ist
also für Aufgaben des Betriebssystems und für die Zuweisung der Aufgaben an die SPEs
zuständig. (vgl. [L02])
17.März 2008
Seite 8
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Da der Cell-Prozessor für hohe Taktraten ausgelegt sein soll, musste bei der Entwicklung auch
auf die Gatterlaufzeiten der Pipelinestufen geachtet werden. Die Laufzeit pro Pipelinestufe
konnte beim PPE auf elf Gatterlaufzeiten reduziert werden. Hierfür musste jedoch die Pipeline
etwas länger werden, so dass sie nun beim PPE für load/store Instruktionen aus 23 Stufen
besteht. Dies ist jedoch z.B. im Vergleich zum Prescott (Pentium 4) mit 31 Pipelinestufen immer
noch wenig. Die niedrige Anzahl an Pipelinestufen ist dabei auch auf den Verwendung der inorder Technik zurückzuführen. (vgl. [L01], [L02])
Eine kurze Pipeline ist unter anderem auch daher wichtig gewesen, da lange Pipelines eine
aufwändige Sprungvorhersage erfordern, damit die Pipeline selbst nicht ineffizient wird. Auf
eine solche Sprungvorhersage ist aber, wie bereits erwähnt, verzichtet worden.
Wie auch bei anderen Prozessoren üblich, teilt sich die Pipeline des PPE in Front- und Backend
auf. Im Frontend werden dabei die Pipelinestufen aufgeführt, welche alle Befehle gemeinsam
durchlaufen – Instruction Fetch, Decode und Dispatch. Im Backend sind entsprechend die für
die Befehlstypen unterschiedlichen Pipelinestufen aufgeführt – Register-File-Access, Execute
und WriteBack. (vgl. [L02])
Abbildung 3 Befehlspipeline des PPE [@05]
17.März 2008
Seite 9
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
3.2.
Synergistic Processing Elements (SPE)
Jeder der auf dem Cell-Prozessor befindlichen SPEs besteht aus drei Teilen. Diese sind der
parallel arbeitende Rechenkern, welcher Synergistic Processing Unit (SPU) genannt wird, der
256KByte große Local Store und der Memory Flow Controller (MFC), mit welchem die SPEs an
den EIB zur Kommunikation mit den anderen Systemkomponenten angebunden sind – wie auch
in Abbildung 4 zu sehen ist. In dieser Abbildung wird der MFC jedoch, wie auch oft in der
Literatur, als DMA-Unit bezeichnet, was die Kommunikationsweise der SPEs verdeutlicht.
Abbildung 4 Schema des SPEs [@04]
Bei SPUs handelt es sich um eine 128Bit SIMD Architektur mit 128 Registern. Diese Register
können sowohl für Integer- als auch für Floating-Point-Werte verwendet werden. Wie das PPE
ist auch die SPU ein in-order Prozessor mit zwei Threads, verfügt aber im Gegensatz zur PPE
über keine Branch Prediction. Das Instruction Set ist spezialisiert und die SPU verfügt im
Normalbetrieb über keinerlei Zugriffsschutzmechanismen wie einen Supervisor Modus oder
Speicherschutz. (vgl. [@02], [@05], [L02])
17.März 2008
Seite 10
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Das Befehlsformat der SPU ist ein 32Bit Format mit fester Länge. Die SPU hat eine Load-Store
Architektur, jedoch kann nur auf Daten im Local Store der SPE zugegriffen werden. Auch
Instruktionen können nur aus dem Local Store geholt werden. Die arithmetischen Operationen
arbeiten auf Vektoren aus 8, 16 oder 32Bit Integer-Werten und auf Vektoren aus 32 oder 64Bit
Floating-Point-Werten. Einen skalaren Datentyp, wie z.B. einen 32Bit Integer oder FloatingPoint kennt die SPU hardwareseitig gar nicht. Grundsätzlich werden Operationen immer über
die gesamte Datenbreite von 128Bit ausgeführt, auch wenn beispielsweise nur ein kleiner 8Bit
Zähler benötigt wird. Ebenso finden auch Zugriffe auf den Local Store ausschließlich über die
128Bit-Breite statt. Der Compiler sorgt jedoch mit einem Software-Layer durch Schiebe- und
Maskierungsoperationen dafür, dass man wie gewohnt skalare Datentypen nutzen kann. (vgl.
[L04])
Zusätzlich sind im Instruction Set Befehle zum Ausgleich für die fehlende Branch Prediction
enthalten. Dies sind „Hint-for-Branch“ und „Conditional-Move“ Befehle. (vgl. [L04])
Abbildung 5 Datenformate in den Registern der SPU [L04]
Die Register sind in vier 32Bit Slots eingeteilt, von denen der erste Slot, der so genannte
„preferred“ Slot, die Ergebnisse von skalaren Operationen erhält und zur Übergabe von
Adressen verwendet wird. Abbildung 5 zeigt das Datenformat in den Registern der SPU. Bei
Load-/Store-Operationen werden die letzten vier Bits der Adresse auf Null gesetzt, so dass alle
Zugriffe auf 128Bit-Grenzen ausgerichtet sind. Außerdem wird bei Zugriffen mit zu großen
Adressen die tatsächliche Größe des Speichers subtrahiert (wrap-around), so dass beim
Speicherzugriff keine Fehler auftreten können. (vgl. [L04])
17.März 2008
Seite 11
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Die beiden Threads des SPU sind asymmetrisch organisiert und werden als „even“- und „odd“pipe bezeichnet. In der odd pipe werden Load-/Store-Befehle und Branches ausgeführt, in der
even pipe Integer- und Floating-Point-Arithmetik. Eine genaue Übersicht über die Aufteilung
der Befehle auf die beiden Execution-Pipelines zeigt die folgende Abbildung.
Abbildung 6 Aufteilung der Befehle auf Execution-Pipelines der SPU [L04]
Die Pipeline selbst besteht wie die Pipeline des PPE aus 23 Stufen und ist auch hier in Frontend
und Backend aufgeteilt. Im Frontend werden 12 Stufen und im Backend 6 - 9 Stufen
durchlaufen. Das Write-Back in die Register wird bei allen Instruktionen im 23. Taktzyklus
durchgeführt. Da aber nicht alle Instruktionen gleich viele Taktzyklen benötigen, wurden in die
Pipeline Wartezyklen eingefügt (blaue leere Kästchen in Abbildung 7). Auf die Ergebnisse der
Instruktionen aus der Execute-Phase kann aber schon per Forwarding zugegriffen werden
(senkrechte Pfeile am Ende der Execution-Phase in Abbildung 7). Eine Ausnahme bilden jedoch
Branch-Instruktionen. Die Branches werden maximal mit 18 Stufen durchlaufen, so dass eine
falsch vorhergesagte Verzweigung maximal eine Wartezeit von 18 Takten nach sich zieht. (vgl.
[L01], [L02])
17.März 2008
Seite 12
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Abbildung 7 Pipeline der SPU [L01]
Der Local Store kann als eine Art expliziter, vollständig unter der Kontrolle des Programmierers
stehender Cache angesehen werden, da die SPUs selber über keinen Cache verfügen. Dieser
schnelle lokale Speicher kann dabei pro Takt 16Byte zwischen sich und SPU austauschen – dies
entspricht pro SPE einer Bandbreite von 50GByte/s bei dem gegenwärtigen Takt von 3,2Ghz.
Auf die Local Stores der einzelnen SPEs kann von außerhalb des SPE im shared memoryVerfahren über virtuelle Adressen zugegriffen werden. So kann das PPE und auch andere SPEs
in den Speicher eines SPE schreiben. Dadurch ist es möglich, komplexe Aufgaben in einzelne
Teile zu zerlegen, welche nun von unterschiedlichen SPEs bearbeitet werden. Dieses Vorgehen
wird Streamed Processing genannt. In folgender Abbildung wird dieses Vorgehen am Beispiel
des Decodierens digitaler Fernsehsignale gezeigt. (vgl. [@01])
17.März 2008
Seite 13
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Abbildung 8 Beispiel für Streamed Processing [@01]
Der Zugriff auf den Local Store kann aber auch verhindert werden. Dies geschieht im so
genannten Isolation Mode. Dabei wird ein digital signiertes Programm in den SPE geladen und
mittels eines im Prozessor vorhandenen Schlüssels überprüft. Nur wenn diese Überprüfung
erfolgreich war, wird der Code ausgeführt. Anderenfalls wird die Ausführung des Codes
verhindert. So lange sich das SPE im Isolation Mode befindet, kann von Außen nicht auf dessen
Local Store zugegriffen werden. Anwendungsgebiete hierfür sind z.B. DRM oder kryptografische
Anwendungen. (vgl. [L01], [L03])
Der MFC dient im SPE zur Kommunikation mit den anderen Komponenten des Systems. Er dient
zum einen zum Transfer der benötigten Daten in den Local Store des SPE und zur Übermittlung
der Ergebnisse, und verfügt zweitens über Mailboxen, als weiteres Kommunikationsverfahren
neben dem zuvor bereits beschriebenen shared memory-Verfahren, die eine einfache
Kommunikation zwischen der SPU und anderen Einheiten gestatten. Zusätzlich verfügt der MFC
über Status- und Kontrollregister, die den Zustand der SPU kontrollieren. (vgl. [L03])
17.März 2008
Seite 14
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Abbildung 9 Kommunikation über den MFC [@02]
Datentransfers werden dabei über Queues eingeleitet, wovon je eine durch die SPU und eine
mittels memory-mapped IO (MMIO) durch externe Einheiten verwendet werden kann. Der
Memory Flow Controller (MFC) verfügt über einen DMA-Controller und benachrichtigt die
Einheit, die den Transfer angefordert hat, sobald er abgeschlossen ist. Die Mailboxen und die
Kontrollregister sind ebenfalls über MMIO zugreifbar. (vgl. [L03])
Das hier beschriebene Kommunikationsverfahren über Mailboxen wird üblicherweise für die
Übertragung von Speicheradressen verwendet, wohingegen das shared memory-Verfahren zur
Übertragung von Daten verwendet wird.
Die SPU kommuniziert mit dem zugehörigen MFC über Kanäle. Diese sind read-only oder writeonly Datenkanäle, auf die mit speziellen Instruktionen zugegriffen werden kann. Teilweise sind
diese Zugriffe blockierend, speziell dann, wenn die SPU warten müsste, bis auf der Gegenseite
die Daten abgerufen oder bereitgestellt wurden. Dies ist effizienter als ein Polling-Verfahren,
weil bei einem blockierenden Zugriff die Stromzufuhr zur SPU extrem gedrosselt werden kann.
(vgl. [L03])
17.März 2008
Seite 15
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
3.3.
Element Interconnet Bus (EIB)
Der EIB verbindet die einzelnen Komponenten des Cell-Prozessors. In dem gegenwärtig
veröffentlichten Cell-Prozessor sind es insgesamt 12 Elemente, die darüber verbunden werden.
Der EIB ist in einer Ringtopologie aufgebaut und besteht aus vier Ringen mit je 128Bit Breite,
wobei die einzelnen Ringe zur Reduzierung von Interferenzen gegenläufig ausgelegt sind –
somit existieren je zwei Ringe pro Richtung. Dies hat auch den Vorteil, dass bei einer
Übertragung zwischen den Elementen, die maximale Entfernung 6 Elemente (bezogen auf den
Cell-Prozessor mit 12 Elementen) beträgt. Der EIB ist mit dem halben Prozessortakt getaktet also 1,6Ghz. Abhängig von der relativen Lage der Partner einer Übertragung gibt es jedoch
verschiedene Laufzeiten und die Gesamtbandbreite ist davon abhängig, wer mit welchem Ring
verbunden ist. Wenn z.B. vier SPE-Paare gegenseitig den Local Store des Partners lesen und
somit acht gleichzeitige Transfers durchführen, dann kann die gemessene Bandbreite je nach
Auswahl der Partner zwischen 78 GByte/s und 197 GByte/s variieren. Die theoretische
Gesamtbandbreite des EIB liegt bei 204 GByte/s. (vgl. [@02], [L01], [L02])
Die Daten werden von einem SPE zum Nächsten übertragen, in denen jeweils ein Repeater mit
einem Bus Interface die Verbindung in die SPE darstellt. Die Daten werden somit in mehreren
Schritten von einer SPE zur nächsten weitergereicht. Ein Nebeneffekt dieses Aufbaus ist, dass
die Anzahl der SPEs beliebig gesteigert oder verringert werden kann, ohne dass die
Busarchitektur verändert werden müsste, führt jedoch auch dazu, dass die Latenz steigt. (vgl.
[@01], [L01])
3.4.
Memory Interface Controller (MIC)
Der MIC des Cell-Prozessors ist über zwei 32Bit Kanäle (Dual-Channel) mit dem Rambus XDRSpeicher verbunden, die bei einer maximalen Taktrate von 3,2GHz arbeiten. Jeder der Kanäle
kann dabei maximal 256 MB ansprechen, so dass insgesamt 512 MB verwendet werden
können. Die Speicherbandbreite des Controllers beläuft sich dabei auf 25,6 GByte/s, bzw. 12,8
GByte/s pro Kanal. Somit kommt nur einer der beiden Kanäle bereits auf die Bandbreite von
parallel arbeitendem DDR2 – PC6400.
Dennoch ist in Zukunft – IBM plant dies bereits beim „Cell eDP“ (enhanced Double Precision),
der im Jahr 2008 erwartet wird - ein Wechsel auf DDR2 oder bereits DDR3 angedacht, um
größere Speicherkapazitäten ansprechen zu können. (vgl. [L01], [L02])
17.März 2008
Seite 16
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
3.5.
Bus Interface – FlexIO
Mittels des ebenfalls von Rambus stammenden Bus Interface „FlexIO“ können mehrere CellProzessoren verbunden werden, oder andere Einheiten wie beispielsweise der Grafikprozessor
RSX in der Playstation 3 angebunden werden. Das FlexIO-Interface ist asymetrisch aufgebaut
und bietet 7 ausgehende und 5 eingehende Leitungen mit jeweils 8Bit Breite. Das Interface
erlaubt eine direkte Verbindung von maximal zwei Einheiten. Mehrere Einheiten können über
einen Switch verbunden werden, wie in Abbildung 10 am Beispiel mehrerer Cell-Prozessoren
gezeigt wird.
Dieses Beispiel zeigt auch, dass es über das FlexIO-Interface möglich ist, zwei Cell-Prozessoren
direkt („glue-less“) zu verbinden. So lassen sich zwei Cell-Prozessoren in einem zwei-wegesymmetrischen Multiprozessor-Konzept (Abbildung 10 (b)) in einem gemeinsamen Adressraum
betreiben, ohne dass weitere Hardware benötigt wird. Hierfür wird eines der beiden FlexIOInterfaces (IOIF) als Broadband Interface (BIO) konfiguriert, welches den EIB sozusagen
durchschleift. (vgl. [@02], [L01], [L02])
IOIF = input-output interface
BIO = broadband interface
Abbildung 10 Konfigurationsmöglichkeiten des Cell-Prozessors [L01]
17.März 2008
Seite 17
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Das FlexIO-Interface arbeitet unabhängig vom Kerntakt mit zwei differenziellen Leitungen pro
Bit, die laut Rambus bis zu 8Gbit pro Sekunde übertragen können. Diese hohe Datenrate ist
aber auch nur über eine begrenzte Entfernung möglich. So darf die Verbindung zum
angeschlossenen Partner maximal 37cm betragen. Zudem ist die Datenrate beim FlexIOInterface nicht konstant (VDR: Variable Data Rate), sondern sie lässt sich zwischen dem ein- und
zehnfachen des Bustaktes einstellen. Beim aktuellen Cell-Prozessor arbeitet das FlexIOInterface mit einem Takt von 500 Mhz, was maximal 5Gbit pro Sekunde pro Signalpaar
ermöglicht – zum Vergleich: bei PCIExpress sind es 2,5Gbit pro Sekunde. Bezogen sind diese
Werte jedoch auf die Bruttodatenrate, sodass die tatsächliche Nettodatenrate je nach
verwendeter Technik (Taktgenerierung, Protokoll, Fehlersicherung) deutlich unter diesen
Werten liegen kann. Durch die Verwendung einer separaten Taktleitung beim FlexIO-Interface
sollen laut Rambus die Brutto- und Nettodatenrate jedoch nahe beieinander liegen. (vgl. [L01],
[L02])
Beim FlexIO-Interface wird zudem nur ein recht kleiner und somit stromsparender Signalpegel
von 200mV verwendet, sowie die neue „FlexPhase“ genannte Technologie zur Synchronisierung
der Phasenlage zwischen den Signalpaaren. Mit Flexphase kann das Boarddesign vereinfacht
werden, da es nicht mehr notwendig ist, die Signalleitungen künstlich zu verlängern um
Laufzeitunterschiede auszugleichen. (vgl. [L01], [L02])
17.März 2008
Seite 18
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Einsatzgebiete des Cell-Prozessors
4.
4.1.
Sony Playstation 3
Wie auch in der Einführung dieser Ausarbeitung schon erwähnt, wurde der Cell-Processor
ursprünglich für die Spielekonsole Playstation 3 von Sony entwickelt. (vgl. [@01])
Entsprechend wird auch der in den vorangegangenen Kapiteln beschriebene Cell BE in der
Playstation 3 verwendet, jedoch mit einer kleinen Änderung.
Die Besonderheit bei der Playstation 3 liegt im Detail. Der Cell Processor der Playstation 3
verfügt über sieben der im eigentlichen Cell-Processor verfügbaren acht Synergistic Processing
Elements (SPE). Der Grund soll die Erhöhung der Produktionsausbeute bei der Herstellung des
Cell Processors sein. Eine weitere SPE wird in einem speziellen Modus der Konsole betrieben
und von dem Hypervisor kontrolliert. Der Hypervisor wird für die Steuerung der Treiberzugriffe
des PS3-Linux-Kernels auf die virtuellen Geräte verwendet. Damit will Sony sicherstellen, dass
das Sicherheitssystem der Playstation 3 nicht angegriffen und verändert wird. Befindet sich eine
Linux Installation auf der Playstation 3, ist diese vom eigentlichen Konsolensystem vollständig
getrennt. (vgl. [@09])
Somit stehen der Sony Playstation 3 noch insgesamt sechs der ursprünglich acht SPEs für die
Verarbeitung von Spielen sowie für das Ausführen des Linux-Betriebssystems zur Verfügung.
17.März 2008
Seite 19
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.2.
Playstation 3 Cluster
Dr. Frank Mueller von der North Carolina State University entwickelte einen Playstation 3
Cluster, indem er acht Playstation 3 zu einem Verbund zusammengeschlossen hat. Dieser
Cluster ist der erste akademische Cluster seiner Art und wird von Dr. Mueller mit Gesamtkosten
von nur 5000 US-Dollar für das gesamte System beziffert: im Vergleich zu ähnlich
leistungsstarken Supercomputern ein sehr kostengünstiges System. (vgl. [@10])
Ein Nachteil der Playstation 3 ist die Ausstattung mit nur 256 MB Arbeitsspeicher plus 256 MB
Speicher für Graphikanwendungen pro Clustereinheit. Dadurch wird der Einsatzbereich dieses
Clusters stark eingeschränkt. Laut Dr. Mueller ist es bestimmt möglich, die Playstation 3 mit
mehr Arbeitsspeicher auszustatten, allerdings habe er bisher die Gehäuse der Geräte noch
nicht geöffnet und arbeitet daher mit der Hardwaregrundkonfiguration, die jedermann für den
Heimgebrauch erwerben kann.
Ein weiterer Nachteil des Cell-Processors in der Playstation 3 ist die Tatsache, dass dieser seine
hohe Geschwindigkeit nur bei Gleitkommaberechnungen mit einfacher Genauigkeit richtig
ausnutzen kann. Für wissenschaftliche Berechnungen werden in der Regel aber
Gleitkommaberechnungen mit doppelter Genauigkeit benötigt. Aus diesem Grund eignet sich
dieser Cluster nur eingeschränkt für wissenschaftliche Aufgaben. (vgl. [@11])
17.März 2008
Seite 20
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Auf
die
nachstehende
persönliche
Anfrage
per
E-Mail
an
Dr.
Frank
Mueller
([email protected]) bezüglich genauerer technischer Information blieb die Reaktion
seinerseits leider aus.
Dear Dr. Mueller,
I am studying at the University of Applied Science Bremen in Germany. For my lecture
computer architecture I have to write an elaboration about the IBM Cell BE and his uses. During
my inquiries I found your project about the Playstation 3 Cluster. It is a very absorbing project.
On the day of my presentation of my elaboration I talk about your Playstation 3 Cluster to my
professor. He was very excited and ask me to write more about your project in the essay.
So I would like to ask you, if you could send me more 'technical' information about the project,
which I could use for my elaboration? I found these links so far.
http://moss.csc.ncsu.edu/~mueller/cluster/ps3/
http://moss.csc.ncsu.edu/~mueller/cluster/ps3/coe.html
Thanks a lot!
best regards,
René Büst
-------------------------------René Büst
Hochschule Bremen
E-Mail: [email protected]
--------------------------------
17.März 2008
Seite 21
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.3.
Crackstation
Der Sicherheitsberater der Firma Security-Assessment Nick Breese zeigte auf der
neuseeländischen Hackerkonferenz Kiwicon, wie er mit einer Playstation 3 die schnelle
Berechnung von MD5 Hashes durchführen konnte. (vgl. [@12], [@13], [@14], [@15])
Mit diesem Verfahren können sehr große Tabellen, welche auch Rainbow Tables genannt
werden, sehr schnell errechnet werden. Die Rainbow Table wurde von Phillipe Oechslin
entwickelt. Es handelt sich dabei um eine Datenstruktur, welche eine schnelle nicht
deterministische Entschlüsselung von Hash-Werten ermöglicht. Dabei werden durch einen
erhöhten Speicheraufwand Geschwindigkeitsvorteile erreicht. (vgl. [@16])
Diese werden z.B. für eine Brute Force Attacke (vgl. [@17]) verwendet, um aus Wörterbüchern
oder Zeichenketten das Klartextpasswort zu einem bestehenden Hash zu ermitteln. Nach
eigenen Angaben von Breese kann die Playstation 3 bis zu 1.4 Milliarden Iterationen pro
Sekunde (wobei eine MD5-Iteration ca. 50 Zyklen benötigt) verarbeiten. (vgl. [@18])
Ein Intel Core2 Duo Processor ist laut Breese nur in der Lage, 8 Millionen Iterationen pro
Sekunde zu verarbeiten. Die hohe Geschwindigkeit ist einzig und allein auf die SIMD-Architektur
des Cell-Processors zurückzuführen. Die Playstation 3 spielt dabei eher eine untergeordnete
Rolle. Vector-Verarbeitung bzw. SIMD sind ideal für die Verarbeitung von großen
zusammenhängenden Datenmengen, ganz im Gegenteil zu kleinen einzelnen Datenmengen, wo
diese Technik kaum Vorteile bringt. Vector-Verarbeitung ermöglicht die parallele Berechnung
kryptographischer Methoden. (vgl. [@12])
Während der Berechnung der MD5-Hashes berechnet jede SPE des Cell Processors zu jeder Zeit
ein eigenes Passwort. (vgl. [@13]) Da jede SPE vier Berechnungen parallel durchführen kann
und 6 SPEs innerhalb der Playstation 3 aktiviert sind, können somit 24 Kalkulationen gleichzeitig
verarbeitet werden.
17.März 2008
Seite 22
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Auf die nachstehende persönliche Anfrage per E-Mail an Nick Breese ([email protected]) bezüglich genauerer technischer Information blieb die Reaktion seinerseits
leider aus.
Dear Sir or Madam,
I am studying at the University of Applied Science Bremen in Germany. For my lecture
computer architecture I have to write an elaboration about the IBM Cell BE and his uses. During
my inquiries I found the project of Nick Breese about the "Crackstation". He is an employee of
your company. It is a very absorbing project. On the day of my presentation of my elaboration I
talk about the Crackstation to my professor. He was very excited and ask me to write more
about the project in the essay.
So I would like to ask you, if you could send me the email address of Nick Breese?
Thanks a lot!
best regards,
René Büst
-------------------------------René Büst
Hochschule Bremen
E-Mail: [email protected]
--------------------------------
17.März 2008
Seite 23
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.4.
Videoverarbeitung
4.4.1.
Einführung
Mit der rapiden Entwicklung in der Netzwerktechnik und im Multimediabereich ist auch die
Menge an verfügbarem Videomaterial gestiegen. Digitales Videomaterial nimmt immer mehr
einen
dominierenden
Stellenwert
im
Bereich
Unterhaltung,
Bildung
und
Informationsgewinnung ein. Um den Benutzer bei der Suche nach dem richtigen Videomaterial
zu unterstützen, werden Systeme erforderlich, die das Videomaterial hinsichtlich ihres Inhalts
analysieren und kategorisieren. Diese Systeme werden unter dem Synonym VPR (Video
processing and retrieval) geführt.
An der Huazhong University of Science & Technology in Wuhan, China wurde dazu ein
Forschungsprojekt ins Leben gerufen, welches die Portierung eines VPR-Systems auf den CellProzessor untersuchte. Dabei sollte geprüft werden, wie man die Aufgaben auf die einzelnen
SPEs aufteilen kann und welche Leistungssteigerung durch parallele Datenverarbeitung erreicht
werden kann. (vgl. [L05])
Zum Einsatz kam dabei der IBM Cell Simulator V2.0. Mit diesem war es möglich, die
Ausführungszeiten zu messen, die die unterschiedlichen Konfigurationen mit einer
unterschiedlichen Anzahl SPEs benötigten.
Die Ergebnisse des Projekts zeigten, dass die Geschwindigkeit der VPR-Verarbeitung durch den
Cell Processor stark beschleunigt werden kann. (vgl. [L05] S. 255)
17.März 2008
Seite 24
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.4.2.
Arbeitsablauf des VPR-Systems
VPR-Systeme unterstützen den Benutzer auf einfache Art und Weise beim Durchsuchen und bei
der Verwaltung von Videomaterial. Die Hauptkomponenten sind Extraktion von Video- oder
Audiomaterial,
Umrisserkennung,
automatische
Zerlegung
des
Materials
in
zusammenhängende Szenen, strukturelle Zusammenfassung, Kommentierung, Indexierung und
inhaltsbasierte Videowiedergabe. Im oben erwähnten Projekt werden dazu einfache
Sportvideos verwendet, die vom System erfasst, analysiert und indexiert werden. (vgl. [L05] S.
256)
Wie in Abbildung 11 zu erkennen ist, besteht das Framework aus den fünf Stufen low level
feature extraction, mid level feature extraction, high level feature extraction, representation,
browsing und retrieval. Innerhalb dieser fünf Stufen wird an geeigneten Stellen die Parallelität
ausgenutzt, z.B. bei der feature extraction. (vgl. [L05] S. 257)
Abbildung 11 Überblick über ein Framework zur Videoverarbeitung und Bereitstellung [L05]
17.März 2008
Seite 25
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.4.3.
Programmiermodelle des VPR-Systems
Ein VPR-System zeichnet sich durch eine hohe Anzahl an Prozessen sowie einer großen Anzahl
an Berechnungen aus. Als strukturelle Programmiermodelle sind das Service-Modell sowie das
Streaming-Modell am Besten dafür geeignet. (vgl. [L05] S. 257)
Abbildung 12 Videoverarbeitung: (a) Service Modell und (b) Streaming Modell [L05]
In Abbildung 12a ist das Service-Modell dargestellt. Hierbei weist der Hauptprozessor (PPE) den
Co-Prozessoren (SPE) die unterschiedlichen Dienste zu. Der Hauptprozess des PPE signalisiert
dem entsprechenden SPE, wenn ein bestimmter Dienst benötigt wird. Die Grundlage und ein
wichtiger Schritt der Videoverarbeitung ist die Extraktion von Eigenschaften, beispielsweise die
Extraktion des Audio-Signals. Jede einzelne Extraktion wird dabei als ein eigener Dienst
betrachtet, welcher einem oder mehreren Co-Prozessoren zugewiesen wird. Eine statische
Zuweisung bestimmter Dienste an bestimmte Co-Prozessoren wird dabei vermieden. (vgl. [L05]
S. 257)
Beim Streaming-Modell in Abbildung 12b agiert der Hauptprozessor (PPE) als ein StreamController und die Co-Prozessoren (SPE) als Stream-Data-Prozessoren mit einer seriellen oder
parallelen Pipeline. Innerhalb der Videoverarbeitung hat jede Prozedur signifikante
Verarbeitungsstufen, welche einem SPE zugewiesen werden. In Abbildung 12b decodiert das
erste SPE beispielsweise den eingehenden raw Videodatenstream und gibt anschließend den
decodierten Videodatenstream aus. Das zweite SPE nimmt den decodierten Videodatenstream
in der zweiten Stufe entgegen und extrahiert das „Feature 1“. Am Ende extrahiert das dritte SPE
das „Feature 2“ und gibt die fertig verarbeiteten Daten an den Hauptprozessor zurück. (vgl.
[L05] S. 257)
17.März 2008
Seite 26
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.4.4.
Block Matching Algorithmus
Der Block Matching-Algorithmus ist ein wichtiger Schritt innerhalb der Videoverarbeitung. Er
wird verwendet, um die große Menge an in Video-Sequenzen enthaltenen zeitlichen und
räumlichen Redundanzen zu eliminieren. Dazu wird das Bild (Frame i) in mehrere Blöcke
aufgeteilt und es wird im nachfolgenden Bild (Frame i+1) geprüft, ob dieser Block enthalten ist.
Einige Kompressionsverfahren, beispielsweise MPEG, nutzen diese Technik, indem sie
redundante Blöcke entfernen und die entfernten Blöcke aus den vorangegangenen Frames
rekonstruieren. (vgl. [L05] S. 257 und [@19])
Abbildung 13: Block Matching [L05]
Wie Abbildung 13 zeigt, wird jeder Block innerhalb eines bestimmten Suchfensters im
nachfolgenden Frame j mit dem gesuchten Block aus Frame i verglichen. Gesucht wird dabei
nach dem Block mir der kleinsten Abweichung vom gesuchten Block.
17.März 2008
Seite 27
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.4.5.
Parallelisierung des Block Matching Algorithmus
Der sequentielle Algorithmus verwendet vier verschachtelte Schleifen zur Berechnung der
minimalen Abweichung. Die Arrays Block[8][8] und Frame[M][N] sind dem aktuellen
Suchblock bzw. dem Suchfenster zugewiesen. Bei jedem Suchschritt wird in der Variable diff
die absolute Differenz gespeichert. Der kleinste absolute Differenzwert und die Bewegung des
gesuchten Blocks werden in den Variablen min, x und y gespeichert.
…
for(i=0; i<M-7; i++) {
for(j=0; j<N-7; j++){
for(k=0; k<8; k++) {
for(l=0; l<8; l++) {
diff += abs(Block[k][l] - Frame[k+i][l+j]);
}
}
}
if(diff < min) {
min=diff;
x=i;
y=j;
}
}
…
Dieser sequentielle Algorithmus muss zur optimalen Nutzung der Ressourcen des CellProzessors dahingehend umgewandelt werden, dass eine parallele Datenverarbeitung möglich
ist. Neben der Nutzung spezieller VMX-Befehle müssen die Daten und die Arbeitspakete vom
PPE dann noch auf die einzelnen SPEs verteilt werden. (vgl. [L05] S. 258 – 259)
Der Hauptprozessor teilt dazu das Suchfenster in einige Unterfenster ein und weist
anschließend die Übereinstimmungsprozedur aus jedem Suchfenster den einzelnen SPEs zu, um
die minimale lokale Abweichung und den lokalen Bewegungsvektor zu ermitteln. Am Ende
vergleicht der Hauptprozessor die Arbeitsergebnisse der einzelnen SPEs und sucht die minimale
globale Abweichung sowie den dazugehörenden Bewegungsvektor.
Die Co-Prozessoren (SPE) erhalten das Unterfenster und den aktuellen Block vom
Hauptprozessor. Sie suchen die beste lokale Übereinstimmung (die minimale lokale
Abweichung) und den dazugehörenden Bewegungsvektor. Anschließend schicken die SPEs das
Ergebnis an den Hauptprozessor zurück und warten auf den nächsten Arbeitsauftrag.
17.März 2008
Seite 28
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
PPE Code:
…
//correspond to ‘fork’ in OpenMP
for(i=0,offset=0; i<SPE_THREADS; i++,offset+=P) {
// Create SPE thread passing the context as a parameter.
spe_ids[i] = spe_create_thread(0, &match_multi_spu, &ctx[i], NULL, -1, 0);
}
…
// correspond to ‘join’ in OpenMP
for(i=0; i<SPE_THREADS; i++) {
(void)spe_wait(spe_ids[i],&status,0);
}
//find the globe minimum, coordinate x,y
for (i=0; i<SPE_THREADS; i++) {
if(diff[i]<globemin) {
globemin=diff[i];
x=posx[i];
y=posy[i];
}
}
…
SPE Code:
…
//gain the data from ppe
spu_mfcdma32(…, MFC_GET_CMD);
…
//compute the local minimum and coordinates x,y with spu-SIMD instruction.
uschRowAbs_v[k] = spu_absd(model_v[k], uschRow_v[k]);
if(diff[k]<localmin) {
localmin=diff[i];
x=posx[k];
y=posy[k];
}
…
//return the results
spu_mfcdma32(…, MFC_PET_CMD);
…
Der oben aufgeführte PPE-Code erzeugt in der Subroutine spe_create_thread einen
Gruppenthread, der auf den SPEs ausgeführt wird. Die Adresse der Daten wird über den
Parameter ctx übertragen. Nachdem die Threads erstellt sind, wird die Subroutine spe_wait
aufgerufen, welche wartet, bis alle Threads beendet sind, also alle SPEs mit iher Arbeit fertig
sind. Im SPE-Code erhält jedes SPE durch eine DMA-Übertragung die Daten vom
Hauptprozessor. Danach ermitteln sie die minimale lokale Abweichung und den
Bewegungsvektor unter Verwendung der SIMD-Befehle der SPEs. Abschließend sendet jedes
SPE ihre Ergebnisse durch eine DMA-Übertragung zurück an den Hauptprozessor. (vgl. [L05] S.
259)
17.März 2008
Seite 29
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Abbildung 14: Geschwindigkeitsanalyse des Block Matching Algorythmus [L05]
4.4.6.
Ergebnisse der Parallelisierung des Block Matching Algorithmus
Wie Abbildung 14 zeigt, erhöht Parallelisierung die Geschwindigkeit mit zunehmender
Auflösung drastisch. Bei einer Auflösung von 2000x1500 kann die Berechnungszeit durch die
Verwendung der SPEs und der parallelen Berechnung ungefähr um den Faktor fünf reduziert
werden (210ms vs. 40ms), im Gegensatz zu einer Auflösung von 800x600, wo der
Beschleunigungsfaktor nur bei zwei liegt (40ms vs. 20ms).
Dies liegt daran, dass in kleineren Bildern der gesuchte Block nicht so häufig vorkommen kann
und daher die weniger häufig vorkommenden parallel laufenden Vergleiche den
Kommunikationsoverhead nicht kompensieren können. Die Geschwindigkeit erreicht je nach
Auflösung einen Höchstwert bei fünf bis sieben verwendeten SPEs. Die Geschwindigkeit kann
sich jedoch auch durch „Überparallelität“ bei zunehmender Anzahl SPEs wieder verschlechtern.
(vgl. [L05] S. 260)
17.März 2008
Seite 30
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.4.7.
OpenMP
Wie die Implementierung des Block Matching Algorithmus aus Kapitel 4.4.5 gezeigt hatte,
waren vom Programmierer ein hoher Kenntnisstand bezüglich Cell-Architektur, Befehlssätze
von PPE und SPE, DMA-Transfers, Registern usw. erforderlich, um für parallele Berechnungen
optimierten Code zu erstellen.
Aus diesem Grund wurde im Rahmen des Forschungsprojekts ebenfalls untersucht, inwiefern
OpenMP auf einem Cell-Prozessor verwendet werden kann. Bei OpenMP handelt es sich um
einen Industriestandard für „shared memory parallel programming“, welcher durch ein
Konsortium von Software- und Hardwareherstellern vereinbart wurde. (vgl. [@20]) Es besteht
aus einer Sammlung von Compilerrichtlinien, Bibliotheksroutinen und Umgebungsvariablen,
welche ohne große Schwierigkeiten für die VPR-Programmierung auf dem Cell Processor
verwendet werden kann. (vgl. [L06])
Ladestrategie
Die parallele Berechnung muss zwischen dem PPE und den SPEs aufgeteilt werden. Die
Parallelität wird in OpenMP durch entsprechende Direktiven dargestellt. Der Hauptprozessor
und die SPEs werden hier als eine Gruppe von Threads betrachtet. Durch Datenzuteilung weist
der Hauptprozessor die SPE gleichzeitig an, spezifische Datenbereiche zu bearbeiten und zu
berechnen. Das PPE führt den Datenbereich als der Masterthread der Gruppe aus. Am Ende des
parallelen Bereichs wartet der Hauptprozessor, bis alle SPEs ihre zugewiesenen Aufgaben
erledigt haben, und sammelt die benötigten Daten von jedem SPE wieder ein. (vgl. [L07], [L08],
[L05] S. 260-261)
17.März 2008
Seite 31
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Lokalität
Die gemeinsam verwendeten Daten sind im Hauptspeicher des PPE abgelegt und können über
die atomaren Operationen des Cell-Processors erreicht werden. Um eine Operation auf die
gemeinsam verwendeten Daten durchzuführen, muss jedes SPE die lokale Speicheradresse in
die effektive Speicheradresse übersetzen. Dann wird via DMA-Transfer eine Kopie der zu
verarbeitenden Daten aus dem Hauptspeicher des PPE im lokalen Speicher der SPEs abgelegt.
Wenn die lokale Kopie der gemeinsam verwendeten Daten durch die Berechnungen eines SPEs
verändert wurde, werden die geänderten Daten am Ende des parallelen Abschnitts über den
DMA-Controller zurück in den Hauptspeicher geschrieben. (vgl. [L05] S. 260-261)
Synchronisation
Die Synchronisation paralleler Prozesse ist durch die Mechanismen „memory tag polling“ und
„event trigger“ auf dem Cell-Prozessor implementiert. Die erste Methode besteht darin, eine
Speichermarke für jedes einzelne SPE mit dem Wert 0 zu initialisieren. Der Hauptprozessor
weckt jedes SPE auf, indem die dazugehörige Marke auf 1 gesetzt wird. Nach Erkennung der
Änderung dieser Marke auf 1 startet jedes SPE sofort mit der Abarbeitung der zugewiesenen
Aufgaben. Nach Beendigung der Berechungen wird die Marke auf 2 gesetzt, um dem
Hauptprozessor das Ende der Tätigkeit zu signalisieren. Wenn alle Marken den Wert 2 haben
kann der Hauptprozessor die Ergebnisse auswerten und anschließend die Marken wieder auf 1
setzen, um mit der Bearbeitung der nächsten Aufgabe fortzufahren.
Die zweite Methode ist die Nutzung des Briefkastens. Der Hauptprozessor verteilt einen
Prozess, indem er jedem SPE das Signal „start“ sendet. Nach Erhalt des Signals „start“ beginnt
jedes SPE mit der Abarbeitung der der zugewiesenen Tätigkeiten. Hat das SPE seine Arbeit
beendet, sendet es dem Hauptprozessor das Signal „completion“ und wartet anschließend auf
das nächste Signal „start“. Sobald der Hauptprozessor von allen SPEs das Signal „completion“
erhalten hat, kann mit der Bearbeitung der nächsten Aufgabe fortgefahren werden. (vgl. [L05]
S. 260-261)
17.März 2008
Seite 32
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.5.
Adaptive Echtzeitfilterung für digitale Röntgenanwendungen
4.5.1.
Hintergrund
In den letzten zehn Jahren sind viele Methoden zur adaptiven Filterung von Datenströmen
entwickelt worden, wobei die adaptive Filterung in den Bereich der sehr rechenintensiven
Algorithmen gehört. Im Fall von Röntgenaufnahmen in Echtzeit, wie sie in der Chirurgie
eingesetzt werden, müssen die Systeme einen Durchsatz von 30 Bildern pro Sekunde
bereitstellen können. Zum Einsatz kommen meistens Kombinationen aus Hochpass- und
Tiefpassfilter. Um ein optimales Ergebnis bei der Aufbereitung dieser Bilder zu erzielen, werden
die Bilder mit mehreren unterschiedlichen Filtern bearbeitet und anschließend per Programm
bezüglich Schärfe und Kontrast analysiert. Daraufhin kann dann der optimale Filter angewandt
werden. Zudem kann der Benutzer in einem gewissen Rahmen (siehe Abbildung) die
Filterparameter modifizieren.
Abbildung 15 3D-Computertomographie [@21]
Der Nutzen dieser Filter liegt darin, dass die Bildqualität (Schärfe, Kontrast) gesteigert werden
kann, ohne dass die Dosis an Röntgenstrahlen erhöht werden muss und damit die
gesundheitliche Belastung für den Patienten steigt.
17.März 2008
Seite 33
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
In einer Studie nahmen die Entwickler Olivier Bockenbach, Michel Mangin und Sebastian
Schuberth (Mercury Computer Systems Deutschland und Frankreich) ein verallgemeinertes
Filter-Konzept und implementierten es auf einem Cell BE Processor. Das System ist in der Lage,
Bilder mit einem Durchsatz von mehr als 40 Bildern pro Sekunde zu filtern. Des Weiteren
besteht die Möglichkeit, in Echtzeit Parameter ändern zu können. (vgl. [L09] S. 578 – 579)
4.5.2.
Hardware
Die Systemhardware basiert auf einem Mercury Cell Technology Evaluation System (CTES),
welches aus einem IBM BladeCenter besteht. Dieses beinhaltet ein Dual Cell-Based Blade
(DCBB). Die Steuerung der Visualisierungsanwendungen und die adaptive Kombination der
Filter wurden auf einen Standard-PC ausgelagert. Beide Rechner wurden über Gigabit-Ethernet
miteinander verbunden. Der Visualisierungsserver kann wie ein Standard-PC betrachtet werden
und arbeitet mit dem Betriebssystem Microsoft Windows XP. Das DCBB ist um die Architektur
einer Cell Broadband Engine (CBE) aufgebaut und wurde so konstruiert, dass es mit anderen
Boards (DCBBs) innerhalb eines BladeCenters zusammenarbeiten kann. Ein DCBB Board ist mit
zwei CBE Prozessoren im Symmetric Multi Processor (SMP) Mode bestückt. Diese Prozessoren
arbeiten mit einer Taktrate von 3GHz. Jeder CBE Prozessor verfügt über 512 MB Rambus (XDR)
Arbeitsspeicher. Der Aufbau ist Abbildung 16 zu entnehmen. (vgl. [L10] S. 582)
Abbildung 16: Dual Cell Based Board [L10]
17.März 2008
Seite 34
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.5.3.
Funktionsweise
Die Cell-Prozessoren des DCBB empfangen den Bilderstrom über das Gigabit Netzwerk. Die
Bilder werden anschließend zur Berechnung (Anwendung der unterschiedlichen Filter) auf die
SPEs verteilt. Nach den Berechnungen werden die Bilder über das Netzwerk zum
Visualisierungsserver geschickt, wo von einer speziellen Software die Glättung und die adaptive
Kombination der Filter erfolgt, um ein optimales Bild anzuzeigen. Die Anwendung auf dem
Visualisierungsserver erfasst dazu die vom Benutzer festgelegten Werte und die von den SPEs
zurückgelieferten Bilder und berechnet daraus das optimale anzuzeigende Bild. (vgl. [L10] S.
583)
4.5.4.
Ergebnisse
Wie in Abbildung 17 zu sehen ist, kann durch die Anwendung verschiedener Filter die Qualität
der Bilder deutlich gesteigert werden. Bei dieser Implementierung wurde für Bilder mit einer
Auflösung von 1024 x 1024 Pixel eine Bildwiederholrate von 41 Bildern pro Sekunde erreicht.
Abbildung 17 (a) Originalaufnahme, (b) gefiltertes Röntgenbild [L10]
Die eingesetzte multiparallele Technologie erleichtert und beschleunigt, wie die Versuche
zeigten, die Echtzeitberechnungen großer Datenmengen. Es wäre somit ohne große
Schwierigkeiten möglich, Bilder mit unterschiedlichen Filtern auf mehreren Monitoren
darzustellen, und zusätzlich die Filterparameter in Echtzeit verändern zu können. Ein weiterer
Anwendungsbereich dieser Technik könnte die Echtzeitdarstellung für Anwendungen im
Bereich der Computertomographie sein. (vgl. [L10] S. 585 – 587)
17.März 2008
Seite 35
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.6.
Objekterkennung in Echtzeit
4.6.1.
Hintergrund
Die präzise Erkennung von Objekten auf Grundlage der Bildverarbeitung wird in vielen
eingebetteten Anwendungen benötigt, wo eine präzise Erkennung und Verarbeitung in Echtzeit
erwartet wird. In einem gemeinsamen Forschungsprojekt der Kyoto University und dem Nara
Institute of Science and Technology wurde zu dieser Thematik ein System entwickelt, welches
in Echtzeit sowohl Objekterkennung als auch Objektverfolgung realisiert. Aufgrund der
bestehenden Parallelität der Aufgabenstellung wurde das System auf einem Cell-Prozessor
basierend entwickelt. (vgl. [L09] S. 932)
Mit dem System ist es möglich, bei einer Bildwiederholrate von 22 Bildern pro Sekunde
gleichzeitig die Objekterkennung eines bestimmten Objekts und die Objektverfolgung von drei
unterschiedlichen Objekten zu realisieren. Bei einer Reduzierung der Bildwiederholrate auf 18
Bildern ist es möglich, gleichzeitig die Objekterkennung eines bestimmten Objekts und die
Objektverfolgung von sieben unterschiedlichen Objekten zu realisieren. Die Bildgröße lag bei
diesen Messungen bei 320x240 Pixeln, also ein Viertel der Standard-VGA-Auflösung. (vgl. [L09]
S. 932)
Die dabei zum Einsatz kommenden Verfahren lauten „boosting-based detection“ und
„histogram-based tracking“, welche im Folgenden kurz erläutert werden.
17.März 2008
Seite 36
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.6.2.
boosting-based detection
Boosting (engl. „Verstärken“) ist ein Algorithmus der automatischen Klassifizierung, der
mehrere schlechte Klassifikatoren zu einem einzigen guten Klassifikator verschmilzt. Boosting
kann überall dort verwendet werden, wo eine automatische Klassifikation in zwei Gruppen
benötigt wird, beispielsweise um Bilder von Gesichtern in „bekannt“ und „unbekannt“ oder
Produkte auf einem Fließband als „in Ordnung“ oder „fehlerhaft“ einzustufen. Vorgegeben sind
eine Reihe von Objekten und eine Reihe schwacher Klassifikatoren. Gesucht ist ein Klassifikator,
der die Objekte möglichst fehlerfrei in zwei Klassen einteilt. Boosting kombiniert die
vorhandenen schwachen Klassifikatoren, sodass der entstehende neue Klassifikator möglichst
wenige Fehler macht. Schwache Klassifikatoren sind sehr einfach aufgebaut und
berücksichtigen meist nur ein einziges Merkmal der Objekte. Für sich genommen liefern sie
deswegen einerseits schlechte Ergebnisse, können aber andererseits sehr schnell ausgewertet
werden. Boosting führt alle schwachen Klassifikatoren mit einer Gewichtung so zusammen,
dass die stärkeren unter den schwachen Klassifikatoren besonders berücksichtigt werden, die
wirklich schwachen hingegen ignoriert werden. [L09]
Als Beispiel für das Funktionsprinzip des Boosting sei hier die automatische Klassifizierung von
Versicherungsnehmern bei einer KFZ-Versicherung genannt. Um das Risikopotential eines
Verkehrsteilnehmers einschätzen zu können, gibt es keine komplexe aber allgemeingültige
Regel. Es ist viel einfacher, anhand mehrerer „Faustregeln“ und deren Kombination auf das
richtige Ergebnis zu kommen. (siehe [@22] und [@23])
Alter
23
17
43
68
32
Autotyp
Familie
Sport
Sport
Familie
LKW
Risiko
hoch
hoch
hoch
niedrig
niedrig
Abbildung 18 Klassifizierung von Versicherungsnehmern [@23]
Anhand einfacher Klassifikatoren werden in diesem Beispiel die Versicherungsnehmer in
Risikogruppen unterteilt:
if Alter > 50 then Risikoklasse = Niedrig;
if Alter ≤ 50 and Autotyp = LKW then Risikoklasse = Niedrig;
if Alter ≤ 50 and Autotyp ≠ LKW then Risikoklasse = Hoch;
17.März 2008
Seite 37
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.6.3.
histogram-based tracking
In der digitalen Bildverarbeitung versteht man unter einem Histogramm die statistische
Häufigkeit der Grauwerte bzw. der Farbwerte in einem Bild. Das Histogramm eines Bildes
erlaubt eine Aussage über die Häufigkeit der vorkommenden Grau- bzw. Farbwerte und über
Kontrast und Helligkeit des Bildes. Die Anzahl der Farbkanäle in einem Bild ist abhängig vom
Modus, d.h. pro Farbauszug gibt es einen Kanal. (vgl. [@24])
Ein Histogramm visualisiert die Verteilung der Helligkeitswerte eines Bildes. Über einer Achse,
die den Wertebereich der Farbwerte darstellt, sind als Balken die einzelnen Häufigkeiten des
Vorkommens der Farbwerte aufgetragen. Je höher der Balken über einem Farbwert ist, desto
häufiger kommt dieser Farbwert im Bild vor. (vgl. [@24])
Anhand des Histogramms wird versucht, die gesuchten Objekte auf den Bildern zu finden und
damit „zu verfolgen“. Dazu wird das zu untersuchende Bild in mehrere Segmente unterteilt und
mit einem vorher definierten Muster-Histogramm verglichen, welches die charakteristischen
Merkmale des Objekts aufweist. Im Fall der Verfolgung von Gesichtern sind dies beispielsweise
die mögliche Haut- und Haarfarbe. Der Bereich mit der größten Schnittmenge ist dann das
Bildsegment, welches das gesuchte Gesicht enthält, sofern diese Schnittmenge einen gewissen
Schwellwert überschreitet. (vgl. [@25])
Abbildung 19 Verfolgung von Gesichtern mittels Histogramm [@25]
17.März 2008
Seite 38
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.6.4.
Implementierung auf einem Cell-Simulator
Um die Leistungsfähigkeit des Cell-Prozessors nutzen zu können, wurde der Gesamtprozess in
mehrere unabhängige Teile getrennt, um diese dann von den einzelnen SPEs parallel
bearbeiten zu lassen. Die Erstellung und Skalierung der Teilbilder sowie die Festlegung des zu
suchenden Musters (Kenndaten) wird vom PPE übernommen. Die Suche nach den Kenndaten
wird von den SPEs übernommen. (vgl. [L09] S. 936)
Abbildung 20: Parallele Erkennung von mehreren SPEs [L09]
Dazu wird das Bild zunächst in mehrere Teilbilder unterteilt. Anschließend werden die Teilbilder
nach allen Eigenschaften des gesuchten Musters durchsucht. Werden alle Eigenschaften des
Musters gefunden, wird das Bild verkleinert und die Suche startet erneut. Es tritt also eine
sukzessive Verkleinerung des Bildes und damit eine Eingrenzung des gesuchten Musters auf.
(vgl. [L09] S. 937)
Innerhalb der SPEs wird die Suche nach Kenndaten parallel ausgeführt, indem eine SIMD
Operation durchgeführt wird. Die Erkennung wird beschleunigt, indem das Suchfenster zu den
benachbarten Koordinaten verschoben wird. In dieser Phase können vier Suchoperationen
parallel ausgeführt werden, da der SIMD-Vector der SPE auf vier Integer-Variablen simultan
operieren kann. (vgl. [L09] S. 938 - 939)
17.März 2008
Seite 39
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.6.5.
Ergebnisse der Implementierung auf einem Cell-Simulator
Die folgenden Ergebnisse wurden ermittelt, indem die zu bearbeitenden Bilder vorher in
Graustufen-Bilder mit 7 Bit Farbtiefe umgewandelt und statisch im Speicher des
Hauptprozessors abgelegt wurden. Die Größe der zu verarbeitenden Bilder betrug 320 x 240
Pixel und die Größe der zu suchenden bzw. zu verfolgenden Kenndaten betrug 24 x 24 Pixel. Die
eben genannten Werte wurden experimentell ermittelt. Um eine optimale Auslastung der
Hardware zu erreichen, wurden Messungen der Objekterkennung und der Objektverfolgung
durchgeführt. Die Ergebnisse können Abbildung 21 entnommen werden.
Abbildung 21: Verarbeitungszeit der Objekterkennung und Objektverfolgung [L09]
Die Ergebnisse zeigen, dass die Verarbeitungszeit der Objekterkennung mit der Zunahme der
SPEs abnimmt. Allerdings steigt die Verarbeitungszeit, wenn die Anzahl der SPEs größer als drei
wird. Ab einer Anzahl von 3 SPEs wird der Aufwand des PPE vermutlich zu hoch, die Bilder in
Teilbilder zu unterteilen, zur Weiterverarbeitung an die SPEs weiterzugeben, sowie die
Ergebnisse der SPEs wieder auszuwerten. Die Verarbeitungszeit der Objektverfolgung nimmt
mit der Zunahme der SPEs ebenfalls ab. Allerdings steigt auch hier vermutlich aus den gleichen
Gründen die Verarbeitungszeit, wenn die Anzahl der SPEs größer als vier wird. Da die
Messungen einen Anstieg der Verarbeitungszeiten mit zunehmender Anzahl SPEs ab einer
bestimmten Anzahl ergeben haben, wurden die Messungen mit 6 SPEs gar nicht mehr
durchgeführt. (vgl. [L09] S. 940)
In Anbetracht der Verarbeitungszeiten und der zur Verfügung stehenden Ressourcen (6 SPEs in
der Playstation 3) sind für den kombinierten Betrieb (gleichzeitige Erkennung und Verfolgung
von Objekten) mehrere Szenarien möglich:
Bei einer Verwendung von zwei SPEs für die Objekterkennung und vier SPEs für die
Objektverfolgung können sieben unterschiedliche Objekte von den dazu zur Verfügung
stehenden vier SPEs verfolgt werden (7 x 7,32 ms = 51,24 ms), während die zwei SPEs für die
Objekterkennung ein bestimmtes Objekt im Bild suchen (51,4 ms). Diese Aufteilung ermöglicht
17.März 2008
Seite 40
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
eine theoretische Bildwiederholrate von 19,46 Bildern pro Sekunde (1000 / 51,4 = 19,455253),
praktisch wurde eine Bildwiederholrate von 18 Bildern pro Sekunde erreicht.
Werden drei SPEs für die Objekterkennung und drei SPEs für die Objektverfolgung verwendet,
können drei unterschiedliche Objekte von den dazu zur Verfügung stehenden drei SPEs verfolgt
werden (3 x 12,11 ms = 36,33 ms), während die drei SPEs für die Objekterkennung ein
bestimmtes Objekt im Bild suchen (45,06 ms). Diese Aufteilung ermöglicht eine theoretische
Bildwiederholrate von 22,19 Bildern pro Sekunde (1000 / 46,06 = 22,192632), praktisch wurde
eine Bildwiederholrate von 22 Bildern pro Sekunde erreicht. (vgl. [L09] S. 940 – 941)
4.6.6.
Ergebnisse der Implementierung auf einer Playstation 3
Basierend auf den Ergebnissen der Simulation wurde ein Objekterkennungssystem entwickelt,
welches unter Verwendung der Playstation 3 in Echtzeit Objekte erkennt und verfolgt.
Abbildung 22: Versuchsaufbau mit einer Playstation 3 [L09]
Folgende Aufgaben müssen zusätzlich zu den in der Simulation aufgeführten Tätigkeiten
durchgeführt werden:
Ø Bilder in der Größe 640x480 (RGB) von der USB-Kamera laden
Ø Die Bilder auf die Größe 320x240 Pixel verkleinern und in Graustufen umwandeln
17.März 2008
Seite 41
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Abbildung 23 zeigt die benötigte Verarbeitungszeit für die eben genannten Operationen.
Abbildung 23: Verarbeitungszeit auf der Playstation 3 [L09]
Mit
diesen
zusätzlichen
Verarbeitungszeiten
erreicht
das System nur
noch
eine
Bildwiederholrate von 7 Bildern pro Sekunde. Das Abholen der Bilddaten von der USB-Kamera
spielt in dieser Implementierung eine entscheidende Rolle. (vgl. [L09] S. 941 - 942)
Abbildung 24: Objekterkennung und Objektverfolgung [L09]
Abbildung 24 zeigt die Ergebnisse der Objekterkennung und Objektverfolgung mit dem zuvor
beschriebenen System. Die weißen bzw. grünen Quadrate entsprechen der Objekterkennung
bzw. der Objektverfolgung. Nachdem das System konfiguriert ist, erkennt es die Testperson als
zu erkennendes und zu verfolgendes Zielobjekt. (Frame 60) Daher befinden sich beide Quadrate
über dem Gesicht, da die Erkennung sowie die Verfolgung des Zielobjekts erfolgreich sind. In
den Frames 152, 192 und 248 ist die Objekterkennung fehlgeschlagen, aber die
Positionsbestimmung des zu verfolgenden Objekts durch die Objektverfolgung wurde
erfolgreich durchgeführt. Im Frame 263 ist das Zielobjekt wieder erfolgreich erkannt und die
Position erfolgreich bestimmt worden. (vgl. [L09] S. 942)
17.März 2008
Seite 42
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.7.
SSL-Beschleunigung unter Verwendung der Cell Broadband Engine
4.7.1.
Einführung
Die Weiterentwicklung von spezieller Hardware für Spiele wird im Vergleich zu einem
gewöhnlichen Prozessor immer einen merkbaren Leistungsgewinn erbringen. Numerische
Berechnungsverfahren mit einfacher oder doppelter Genauigkeit, welche in der Kryptographie
verwendet werden, haben mit dem Bereich der Hardwareentwicklung für Spiele jedoch nicht
sehr viel zu tun. (vgl. [L11] S. 1)
Neil Costigan und Michael Scott (School of Computing, Dublin City University, Ireland)
beschreiben die Leistungssteigerung für SSL (Secure Socket Layer) und die dazugehörige
Implementierung unter der Verwendung des Vektor Prozessors der Cell Broadband Engine. Sie
zeigen damit, dass noch große Verbesserungen durch die Verwendung von Hardware, die in
erster Linie für andere Zwecke entwickelt wurde, möglich sind.
4.7.2.
Hintergrund
Trotz der riesigen Leistungssteigerung in Bezug auf die Rechenleistung und Bandbreite ist SSL
nach wie vor die am weitesten verbreitete Verschlüsselungstechnik, um eine sichere
Kommunikation über das Internet, z.B. für Passwortanmeldungen und Kreditkartenzahlungen,
zu gewährleisten. Auch wenn für SSL bereits zahlreiche Sicherheitsprobleme bekannt sind,
gehört es zum de facto Standard für sichere Kommunikationslösungen. Krypthographische
Kommunikationsprotokolle wie SSL werden aber leider nur sehr selten eingesetzt. Das liegt
unter anderem daran, dass diese die Bandbreite sowie die Prozessorleistung auf dem Server
sehr stark belasten. Dieses führt wiederum zu Verzögerungen auf der Clientseite. (vgl. [L11] S. 1
– 2)
Ein interessantes Problem der unterschiedlichen Architekturen des PPE und der SPEs der Cell BE
ist der Bedarf an Programmen mit Multi-Instructions. Herkömmliche Anwendungen
kompilieren einzelne Quellmodule. Anschließend verknüpfen sie die Ergebnisse, um Variablen
und Funktionen miteinander zu verbinden. Für die SPEs muss allerdings ein eigener
Programmcode entwickelt werden, da die SPEs mit einem anderen Instruction Fetch arbeiten
als die PPEs und deren Speicher physikalisch separiert ist. Der Programmcode der PPE
Applikation ist des Weiteren für 64-Bit optimiert. Im Inneren der Anwendung ist ein Dateiobjekt
integriert, welches Befehle und Daten beinhaltet. Dieses Objekt wird über eine
17.März 2008
Seite 43
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
createthread() Funktion vom Compiler der PPE aufgerufen und damit zur SPE übertragen.
Dieser Prozess umfasst zwei getrennte Compiler und Linker. Der ELF-Code der SPE wird mittels
eines embedspu Befehls, welcher eine Hülle bildet, mit PPE kompatiblen Eigenschaften
markiert. Am Ende verbindet eine letzte Verknüpfungsstufe alle ausführbaren Programmteile
miteinander. (vgl. [L11] S. 4) In Abbildung 25 ist die Erstellung der Programme für die SPEs und
der PPEs dargestellt.
Abbildung 25 Prozess zur Erstellung der SPE und PPE Programme [L11]
17.März 2008
Seite 44
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.7.3.
Der Einsatz des Cell-Prozessors als ein Hardware-Security-Model
Der Cell-Prozessor wurde nach einer speziellen Sicherheitsarchitektur konzipiert. In erster Linie
wird die Verwaltung der digitalen Rechte (Digital Rights Management, DRM) unterstützt.
Allerdings
existiert
eine
offene
Schnittstelle
für
Entwickler,
um
zusätzliche
Sicherheitsfunktionen in den auf den SPEs ausgeführten Programmcode zu implementieren.
Diese Architektur kann dazu verwendet werden, um sicherheitskritischen Programmcode
innerhalb einer geschützten Umgebung, wie eines Hardware Security Models, auszuführen. Die
meisten kommerziellen Anbieter von SSL-Beschleunigern verwenden Hardware Security Models
auf Basis von High-End Hardware.
Um den kritischen SSL-Code in einer geschützten Umgebung zu betreiben, kann dieser auf
einem SPE im isolated mode ausgeführt werden. Für einen SSL-Beschleuniger ist es daher
möglich, dass jeder Schüsselgenerierungsprozess die Möglichkeit hat, auf einen sicheren
kryptographischen Zahlengenerator zuzugreifen. Des Weiteren können die Schlüsseldaten vor
anderen Prozessen innerhalb des Cell Prozessors geschützt werden. Außerdem können
Schlüsseldaten in den Bereichen des gemeinsamen genutzten Speichers chiffriert werden und
der Programmcode kann deren Integrität überprüfen.
Der Cell Prozessor erreicht dieses Sicherheitslevel, indem man einen hardwarebasierten
Prozess verwendet. Dieser kann wie folgt charakterisiert werden:
1. Der Programmcode und die Daten innerhalb einer SPE können nur im physikalisch
abgetrennten Speicherbereich ausgeführt werden.
2. Es existiert ein hardwarebasiertes Codesignierungsverfahren, welches die Integrität des
auszuführenden Programmcodes verifiziert.
3. In einer SPU isolierter Programmcode hat die Möglichkeit, aus den Seriennummern der
eingebauten Hardwarekomponenten Schlüssel zur Ver- bzw. Entschlüsselung von Daten
zu generieren. Diese Funktion kann nur von verifiziertem Code genutzt werden.
4. Der Zufallszahlengenerator kann so konfiguriert werden, dass er eine physikalische
Quelle wie z.B. die Platine des Cell Prozessors zur Generierung von Zufallszahlen
verwendet. (Diese Funktion ist auf der Playstation 3 beschränkt)
Diese zusätzliche Sicherheit wirkt sich allerdings negativ auf die Leistung aus. Die Initialisierung
wird durch das sichere Hochfahren beeinträchtigt. Wenn die Daten außerhalb der SPE
gespeichert werden, führt das zu einer höheren Laufzeit während der Entschlüsselung. (vgl.
[L11] S. 4 – 5)
17.März 2008
Seite 45
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.7.4.
OpenSSL
„OpenSSL ist eine freie Implementierung des SSL/TLS-Protokolls und bietet darüber hinaus
weitergehende
Funktionen
zur
Zertifikatsverwaltung
und
zu
unterschiedlichen
kryptographischen Funktionen. Es basiert auf dem SSLeay-Paket, das von Eric A. Young und Tim
Hudson entwickelt wurde, und derzeit von einer unabhängigen Gruppe weiterentwickelt wird.
OpenSSL umfasst verschiedene Applikationen, beispielsweise zur Erzeugung von Zertifikaten,
von Zertifizierungsanträgen und zur Verschlüsselung. Die verschiedenen Applikationen sind
zusammengefasst im Kommandozeilen-Programm openssl.“ (vgl. [@26])
SSL arbeitet in zwei Phasen: Einem intial handshake und einer bulk encryption phase. Der
Handshake dient zur Identifikation und Authentifizierung der Kommunikationspartner auf Basis
asymmetrischer Verschlüsselungsverfahren und Public-Key-Kryptografie. Des Weiteren müssen
die eingesetzten kryptographischen Algorithmen und Schlüssel ausgehandelt werden. (vgl.
[@27])
Ein asymmetrisches Verschlüsselungsverfahren benötigt auf Grund des gemeinsamen
Geheimnisses
einen
höheren
Rechenaufwand
als
ein
symmetrisches
Verschlüsselungsverfahren. Daher wird der Schlüsselaustausch verwendet.
Durch die Analyse von Clock Cycles haben Zhao et al. (vgl. [L12]) herausgefunden, dass 90,4%
der
SSL-Handshakes
auf
x86
Prozessoren
aus
Public-Key
Operationen
bestehen.
Kryptographische Operationen beanspruchen in etwa 95% der gesamten Prozessorlast. Die
restliche Last verteilt sich auf die übrigen Arbeiten abseits der krypthographischen
Verarbeitung. (vgl. [L11] S. 6 – 7)
17.März 2008
Seite 46
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.7.5.
Implementierung
Für die Implementierung wurde eine PPE Bibliothek entwickelt, welche in OpenSSL integriert
werden kann. Das Herzstück dieser Bibliothek bildet ein SPU-ELF-Programm, welches Zugriff auf
die 128-Bit Register hat und die MPM Bibliothek von IBM verwendet. Dabei handelt es sich um
eine für Vektoren optimierte Mathematik-Bibliothek (vector optimised multi-precision Math
library). Dieses SPU Programm (Programmcode und Daten) benötigt lediglich 256KB und passt
daher vollständig in den lokalen Speicher der SPEs. Das PPE wird als ein Steuerelement
eingesetzt und verteilt unter Verwendung von Double Buffering die Daten sowie den Code an
die einzelnen SPEs. Damit alle SPEs dauerhaft und ohne Pausen beschäftigt sind, wird die
Funktion RSA_mod_exp() überladen. Damit kann die vollständige Leistung der RSAEntschlüsselung unter Verwendung des Chinese Remainder Theorem (vgl. [@28]) verwendet
werden. In Abbildung 26 ist das Zusammenspiel zwischen dem PPE und den SPEs graphisch
verdeutlicht.
Abbildung 26: Zusammenspiel zwischen dem PPE und den SPEs [L11]
17.März 2008
Seite 47
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
4.7.6.
Ergebnisse
In der nachstehenden Tabelle sind die Messergebnisse des Versuchs dargestellt. Die
erforderlichen Operationen zur Entschlüsselung von 4096Bit Schlüsseln wurden dabei von
lediglich einem SPE durchgeführt. Die Tabelle zeigt, dass der Cell-Prozessor bei der Verwendung
eines SPE in der Lage ist, 14,87 4096Bit Schlüssel pro Sekunde zu entschlüsseln. Werden diesem
Ergebnis die Kombinationsmöglichkeiten von 24096 gegenübergestellt, ist dieses eine enorme
Leistung. Durch den Einsatz der restlichen 5 SPEs steigert sich die Entschlüsselung um das
Sechsfache auf 89,22 4096Bit Schlüssel pro Sekunde.
Abbildung 27 Entschlüsselungsdauer von 4096-bit Schlüsseln als Simulation (ein SPE) [L11]
Die Simulation kann aufgrund der Komplexität den PPE-Overhead und die DMA-Transferzeiten
nicht berücksichtigen. Die Autoren (vgl. [L13]) gehen davon aus, dass die Ergebnisse der
Simulation nur geringfügig von der Realität abweichen. Die Messergebnisse der realen
Anwendung findet man in Abbildung 28. Die Abweichung der Simulation von der Realität
beträgt dabei knapp 5,5% (14,1s vs. 14,87s). Des Weiteren ist ersichtlich, dass das
Leistungspotential erst bei längeren Schlüsseln zur Geltung kommt, da hier das Verhältnis von
Nutzlast zu Overhead wesentlich besser ist. Auch die Delegation der Berechnungen an die SPU
lohnt sich erst bei Schlüsseln, die länger sind als 2048Bit.
17.März 2008
Seite 48
René Büst
Manuel Bohlken
Florian Brunkhorst
Rechnerstrukturen
Abbildung 28 Entschlüsselungsdauer 1 PPU vs. 1 SPU einer Playstation [L11]
Abbildung 29 Entschlüsselungsdauer 1 PPU vs. 1 SPU einer Playstation [L11]
Abbildung 29 verdeutlicht noch besser, wie leistungsstark das System bei der Verwendung aller
verfügbaren SPUs in der Playstation wird. Den 11 Entschlüsselungsvorgängen einer einzigen
PPU pro Sekunde stehen hier fast 84 Vorgänge durch die 6 SPUs gegenüber. Das entspricht
mehr als dem siebenfachen der PPU-Leistung.
Abbildung 30 Entschlüsselungsdauer 2 PPU vs. 16 SPU eines Cell-Blade-Centers [L11]
Abbildung 30 listet schließlich die Messergebnisse auf, die mit einem Cell-Blade-Center
ermittelt wurden, welches aus 2 Cell-Prozessoren und damit aus 2 PPUs und 16 SPUs besteht.
Auch hier wird wieder mehr als das siebenfache der PPU-Leistung erzielt.
17.März 2008
Seite 49
René Büst
Manuel Bohlken
Florian Brunkhorst

Cell Processor

Transcrição

Documentos relacionados

www.wieistmeineip.de 2

Bericht Andreas M. Siry

- SPES 2020

hochzeitswunsch.ch knackt die Millionengrenze

TSV Oberzell

Geschenke im Wert von über 5 Millionen Franken über

Einstellung und Überprüfung Zündzeitpunkt

Sitzplatz Name Sitzplatz Name Reihe 2, Platz 19

Schweizer schenken 140 Franken zur Hochzeit

lesen - Pfeifer Protocol