Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 1
Cell Broadband Engine
&
CellSs: ein Programmiermodel für den Cell ProzessorMark Duchon, Matthias Ziegler, Andreas Fall
Hardware-Software-Co-Design
Universität Erlangen-Nü[email protected] [email protected] [email protected]
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 2
Cell Broadband Engine Übersicht
Motivation
Architektur
Merkmale
Power Processor Element
Synergistic Processor Element
Element Interconnect Bus
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 3
Cell Broadband Engine Motivation:
Architekturen skalieren nicht sehr effektiv mit der Frequenz
Trend zu immer mehr Kernen und Threads pro Prozessor- Intel Gulftown 6 Kerne mit je 2 Threads- AMD Magny Cours mit bis zu 12
Kernen- IBM Power7: bis zu 4 Kerne mit je 4
Threads
Entwicklung von GPGPUs
Heterogener Ansatz:
CELL Broadband Engine :
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 4
Cell Architektur
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 5
Merkmale der Cell Architektur
2 Unterschiedliche Processor Elemente: Power Processor Element (PPE)
mit L2 Cache Synergistic Processor Element (SPE)
mit Local Store
Über DMA kann jedes Element auf den gesamten Adressraum (Local Store der SPEs und Hauptspeicher) zugreifen
SPEs werden vom PPE gesteuert
Alle Elemente verbunden durch einen Ringbus
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 6
Power Processor Element (PPE)
64-bit RISC PowerPC Prozessor Kern (ähnlich Power5+ nach PowerPC 2.0.2 ISA)
2-Fach Multithreaded
L1 Cache 2x32KB L2 Cache 512KB
VMX 3,2 Ghz +
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 7
Synergistic Processor Element (SPE) SPU
32-bit SIMD Local Store (256Kb SRAM)
Synergistic Memory Flow Controller (SMF) DMA Engine (Direct Memory Access)
Berechnung und Kommunikation gleichzeitig
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 8
Element Interconnect Bus (EIB) Ringbus der mit halber Prozessortaktrate läuft
4 Ringe die 16bit pro Takt Übertragen können
Jeder Busteilnehmer verfügt über je 25,6GB/s für lesen und schreiben
Der Gesamte Bus hat eine theoretische Bandbreite von 204,8GB/s
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 9
Referencen http://www.research.ibm.com/people/m/mikeg/papers/cell_isca2006.pdf
http://www.research.ibm.com/people/m/mikeg/papers/2006_ieeemicro.pdf
http://domino.research.ibm.com/comm/research_projects.nsf/pages/cellcompiler.cell.html
http://en.wikipedia.org/wiki/Cell_(microprocessor)#Element_Interconnect_Bus_.28EIB.29
http://www-03.ibm.com/press/us/en/attachment/10043.wss?fileId=ATTACH_FILE2&fileName=cellpic_1.jpg
http://www.kernel.org/pub/linux/kernel/people/geoff/cell/ps3-linux-docs/ps3-linux-docs-08.06.09/CellProgrammingTutorial/BasicsOfCellArchitecture.html
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 10
Inhalt CellsS Einleitung
Standard Cell Programmierung
Struktur & Architektur Source-to-Source Compiler Laufzeit-Bibliothek
Middleware Nutzung der lokalen Speicher Tracing
Beispiele und Ergebnisse
Ausblick & Zusammenfassung
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 11
Einleitung Hardware soll effizient genutzt werden
Höheres Modell nötig, um parallele Abläufe besser nutzen zu können
Modell nötig, um sequenziellen Programmcode zu parallelisieren
Cell superscaler (CellSs): Einfach und Flexibel Anwender schreibt sequenziellen Code Framework nutzt Nebenläufigkeit im Programmablauf
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 12
Einleitung (Forts.) Verwendung:
Über Annotations im Code werden Funktionen als parallel ausführbar deklariert
Komponenten: Source-to-Source Compiler Laufzeit Bibliothek „Locality aware“ task scheduling
PPE & SPE Compiler
Funktionsweise: Laufzeit Bibliothek erzeugt Graph aller Funktionen (Tasks)
- Abhängigkeiten zwischen Tasks werden als Kanten repräsentiert
Voneinander unabhängige Tasks werden parallel in den SPE's ausgeführt
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 13
Standard Cell Programmierung Grundlage: 'Linux-on-Cell'
OS wird auf dem PPE ausgeführt SPU's werden nicht genutzt
SPE's ohne OS Kein automatisches Speichermanagement Speichertransfers per DMA
Quellcode für PPU und SPU getrennt Übersetzung mit verschiedenen Compilern nötig
Threads müssen angelegt, parametrisiert und ausgeführt werden
Umfangreiche API zur Kontrolle der SPU's
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 14
Standard Cell Programmierung (Forts.) Kommunikation via Mailbox
System
Alternative: IBM Octopiler Parallisierung zur
Compilezeit „Automatic SIMDization“
- Single Instruction Multiple Data
- z.B. Vektoraddition c = a + b
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 15
Struktur & Architektur Source–to–Source Compiler erzeugt zwei C-Files:
Haupt-Programm: Wird im PPE ausgeführt Mit PPE-Compiler übersetzt
„Task-Programm“ Eigenständiges Programm, wird in jedem SPE ausgeführt Mit SPE-Compiler übersetzt
SPE-Programm muss ins Binary für das PPE integriert werden Beim Programmstart werden die Speicher der SPE's mit dem
ausführbaren SPE-Binary geladen
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 16
Struktur & Architektur
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 17
Source-to-Source Compiler Funktionen & Verwendung:
Funktionen werden als Task spezifiziert, die in den SPE's ausgeführt werden:- #pragma css task …
2. Richtung der Parameter muss festgelegt werden- input; output; input/output
3. Übergabe von Arrays und ihrer Länge möglich
Beispiel:#pragma css task input(a{}, b{}, index_i,
index_j) output(c{})void array_op(float a[N], float b[N], float c[N],
float c[N], int index_i, int index_j);main(){
…array_op(A, B, C, i, j);…
}
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 18
Source-to-Source Compiler (Forts.) Modifikation des Code:
Aufrufe zur Initialisierung der Laufzeit Bibliothek Aufrufe zur Registrierung der Tasks und zur Erzeugung des
Task-Graphen Task-Aufrufe werden durch Aufrufe zur entsprechenden
Execute( ) Funktion ersetzt
Für jeden Task wird ein Adapter erzeugt, der vom SPE-Hauptprogramm aufgerufen wird
void css_array_op_adapter(int *params, char *data_buffer){array_op_adapter(data_buffer[params[0]],
data_buffer[params[2]],data_buffer[params[4]],...);
}
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 19
Übersicht Teil 3 – Runtime Library
Cell SS runtime library – Was passiert während der Programmausführung?
Der Task-Graph
Locality-Aware Scheduling Policy
Beispiel
Datenübertragung an SPEs
Performance
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 20
Cell Superscalar Runtime Library Zwei Binärdateien:
Hauptprogramm für PPEs Task-Programm für SPEs (wartet auf Anfragen des
Hauptprogramms)
Aufruf einer annotierten Funktion im Hauptprogramm (execute-Aufruf): Task als Knoten in Ablaufgraph einfügen Datenabhängigkeitsanalyse Parameter Renaming (entfernt Write-Abhängigkeiten) Keine Abhängigkeiten: Ausführungsfreigabe (ready list)
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 21
Der Task-Graph Gerichteter, azyklischer Graph (DAG)
Knoten entsprechen Tasks, Kanten sind Datenabh.
Wird nach jedem Execute und jeder Task-Fertigstellung aktualisiert
Knoten ohne unberechnete Vorgängerknoten bilden die „ready list“
Verwendung des DAG: Nummerierung nach Zeitpunkt des Eintreffens Pro Scheduling-Schritt Subgraph mit max. Tiefe 2 Partitionierung Für jede SPE wird ein Task ausgewählt (ready list, Pfadlänge,
Alphabetische Reihenfolge) Nach Ende des Tasks:
- Knoten aus Graph entfernen- Zeuweisung eines neuen Tasks
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 22
Locality-Aware Scheduling Policy Datenabhängigkeiten bei der Partitionierung:
Abhängige Tasks möglichst in der selben SPE ausführen Dadurch weniger Speicherzugriffe und Datenaustausch
zwischen SPEs
Partitionen werden an SPEs geschickt
Partitionierung kann sich zur Laufzeit dynamisch ändern, workload (un)balance
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 23
Beispiel (1)
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 24
Beispiel (2)
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 25
Datenübertragung in SPEs Tasks werden als ganze Partition an SPE übermittelt
Benachrichtigung zum Start eines Tasks: Mailbox-System, ein Eintrag für jede SPE Enthält Anfrage und Adresse des task control buffer (TCB) Untätige SPEs pollen ihre Mailbox, bis Nachricht vorliegt
Datentransfer TCB enthält Speicheradressen der benötigten Parameter Laden per DMA Nach Task-Ende: Daten entweder im lokalen Speicher halten
oder zurückschreiben (laut TCB)
Friedrich-Alexander-Universität Erlangen-NürnbergMark Duchon, Matthias Ziegler, Andreas Fall 26
Performance Vergleich des Speedup bei verschiedenen Anwendungen
Blockweise Matrix-Multiplikation (matmul) Travelling Salesman Problem (TSP) Blockweise Cholesky-Faktorisierung (cholesky)