Cell Broadband Engine CellSs: ein Programmiermodel … · effektiv mit der Frequenz ... Abhängige Tasks möglichst in der selben SPE ausführen ... Folie 1 Created Date:

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]

mailto:[email protected]




Cell Broadband Engine Übersicht

Motivation

Architektur

Merkmale

Power Processor Element

Synergistic Processor Element

Element Interconnect Bus


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 :


Cell Architektur


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


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 +


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


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


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

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


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


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


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


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


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


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


Struktur & Architektur


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);…

}


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]],...);

}


Ü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


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)


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


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


Beispiel (1)


Beispiel (2)


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)


Performance Vergleich des Speedup bei verschiedenen Anwendungen

Blockweise Matrix-Multiplikation (matmul) Travelling Salesman Problem (TSP) Blockweise Cholesky-Faktorisierung (cholesky)

Documents

Cell Broadband Engine CellSs: ein Programmiermodel … · effektiv mit der Frequenz ... Abhängige Tasks möglichst in der selben SPE ausführen ... Folie 1 Created Date: