CAMPUS HAGENBERG 1

Parallel Computing
Grundlagen

Studiengang Hardware-Software-Design
Campus Hagenberg

Michael Bogner
CAMPUS HAGENBERG 2

Software-Threads vs Hardware-Threads
-> diese beiden Thread-Begriffe haben unterschiedliche Bedeutung:

Software-Threads = Threads der Applikation bzw. des Betriebssystems

-> also die Main- und Workerthreads, die auch im
Taskmanager angezeigt werden

Hardware-Threads = die parallelen HW-Einheiten der CPU

-> also echte Kerne bzw. logische Kerne durch HT

Beispiel: Quadcore-CPU mit Hyperthreading (HT) hat 8 Hardware-Threads

-> durch Hyperthreading kommt es zu sog. logischen Kernen
-> diese log. Kerne existieren nicht physisch, keine 2. ALU
-> aber man kann pro log. Kern einen Software-Thread absetzen
-> HT macht typischerweise aus einem Kern 2 logische Kerne
CAMPUS HAGENBERG 3

Hyperthreading (HT)
Problem heutiger Prozessoren:
• langsame Peripherie (Hauptspeicher, L3-Caches, SSD) bremst die CPU ein
• Kerne wartet auf Daten und sind idle, übrige Threads werden blockiert

Idee hinter HT:

• 2 (oder n) logische Kerne werden pro CPU-Kern realisiert
• keine zweite ALU, sondern zweiter Registersatz + Interrupt Controller
• das Warten blockiert zweiten Thread nicht mehr -> höherer Durchsatz bis zu 25%

Fazit:
Es entsteht durch HT keine echte Parallelität pro Kern. Die CPU übernimmt
das Scheduling der beiden Threads pro Kern selbst und exekutiert beide quasi-parallel.
Damit kann ein zweiter Thread am Kern ausgeführt werden, etwa wenn der erste Threads
wg. fehlender Daten im L1-Cache blockiert wird. Der Durchsatz steigt. Umseitige Grafik zeigt das.
CAMPUS HAGENBERG 4

(c) Intel/techpowerup
Hyperthreading macht aus einem physischen Kern zwei logische Kerne.
Dadurch kann trotz Blockaden oder Wartezeiten eines Threads der Kern durch den zweiten Thread verwendet werden, etwa bei:
• Wartezeiten, wenn Daten nicht im Cache liegen sondern im Hauptspeicher /HDD
• Blockaden durch Pipestalls oder interne Abhängigkeiten in der Berechnung

Weiters können unterschiedliche Recheneinheiten am Chip damit gleichzeitig genutzt werden,

etwa wenn ein Thread nur die Integer-Einheit und der andere Thread nur die Floatingpoint-Einheit benötigt.
CAMPUS HAGENBERG 5

Scheduling
Zweck: Faire Ressourcenzuteilung

Sind mehrere Prozesse zur selben Zeit aktiv, muss das Betriebssystem den
einzelnen Prozessen die Resourcen möglichst fair zuteilen.

Definition: Scheduler = zentrale Komponente des OS, welche die aktiven Threads
den CPU-Kernen zuteilt

Charakteristik:
• Nur 'aktive' Threads werden dem Scheduler zugeführt
• Versch. Scheduling-Varianten (preemptive, non-preemptive)
• Versch. Scheduling-Algorithmen (=Vergabestrategien f. Ressourcen)
• bei Multicore-CPUs zusätzl. HW-Scheduling direkt auf der CPU
(wg. Auslastung & HT)
• heutige Betriebssysteme verwenden kombinierte Algorithmen:
Round Robin + Priority + Aging-Sonderform

Zustände der Threads/Prozesse (Prinzipbild)

CAMPUS HAGENBERG 6

Context Switching
Def.: Context-Switching = Umschalten der CPU zwischen lauffähigen Threads

Zwischen den Threads der Prozesse muss umgeschalten werden, um diese

verzweigt abzuarbeiten. Dieses Umschalten bezeichnet man mit dem Begriff
Context Switching.

-> Aufwand für Prozesswechsel (P) ist

größer als für Threadwechsel (T)

Context Switching zwischen den Threads

Begriff "Oversubscription": von 2 Prozessen

bezeichnet die Situation, dass es mehr aktive SW-Threads als logische Kerne gibt
-> viele Contextswitches nötig
-> ungünstig, wirkt Parallelität entgegen

Ziel: max. soviele Threads wie logische Kerne im Programm verwenden

-> damit (theoret.) kein Contextswitch auf der CPU nötig
CAMPUS HAGENBERG 7

Prioritäten - 1
-> die Prioritätenvergabe erfolgt je nach Anforderung, zB:
• spontane Reaktion nötig,
• Reihenfolge (bei Realtime-Systemen),
• niederpriorer Hintergrundprozess (Druckdienst), etc.

-> generell gilt:

Wenn ein Thread bzw. Prozess sofort reagieren muss, dann ist eine hohe Priorität
nötig, damit die CPU sofort zugeteilt wird.

-> typisches Aktivitätsmuster hochpriorer Threads:

=> kurze Laufzeit, aber hoch reaktiv

CAMPUS HAGENBERG 8

Prioritäten - 2
-> Exekutionsprinzip:
• Prioritäten sind für Threads und Prozesse getrennt definierbar
• Scheduler verwaltet für jede Priorität eine eigene Queue mit
Threads im Status "ready"
• alle Threads bekommen gleiches Zeitquantum (Round Robin)
• niedrig priore Threads laufen erst, wenn hochpriore inaktiv sind

Prioritäten in Windows-Systemen:
• 32 verschiedene Prioritäten: 0 (niedrig) bis 31 (hoch)
• effektive Thread-Priorität setzt sich zusammen aus der
+ Priority Class vom Prozess
+ Priority Level des Threads innerhalb des Prozesses

Priority Class + Priority Level => Base Priority

= effektive Priorität

• Prio 0 hat nur der Zero-Page-Thread

(= Systemthread, der Speicherseiten mit 0 überschreibt)

Prinzipskizze: Prioritäten in Linux:

Scheduler mit Round Robin und Prioritäten • von -20 (hoch) bis 20 (niedrig), Prio 0 = Default-Prio
CAMPUS HAGENBERG 9

Prioritäten - 3

Bildung der
Gesamtpriorität
eines Threads
IDLE_PRIORITY_CLASS THREAD_PRIORITY_IDLE
im Prozess: BELOW_NORMAL_PRIORITY_CLASS THREAD_PRIORITY_LOWEST
NORMAL_PRIORITY_CLASS THREAD_PRIORITY_BELOW_NORMAL
ABOVE_NORMAL_PRIORITY_CLASS THREAD_PRIORITY_NORMAL
HIGH_PRIORITY_CLASS THREAD_PRIORITY_ABOVE_NORMAL
REALTIME_PRIORITY_CLASS THREAD_PRIORITY_HIGHEST
THREAD_PRIORITY_TIME_CRITICAL

Base Process Priority Class Thread Priority Level

1 IDLE_PRIORITY_CLASS THREAD_PRIORITY_IDLE
1 BELOW_NORMAL_PRIORITY_CLASS THREAD_PRIORITY_IDLE
1 NORMAL_PRIORITY_CLASS THREAD_PRIORITY_IDLE
....
12 ABOVE_NORMAL_PRIORITY_CLASS THREAD_PRIORITY_HIGHEST
12 HIGH_PRIORITY_CLASS THREAD_PRIORITY_BELOW_NORMAL
13 HIGH_PRIORITY_CLASS THREAD_PRIORITY_NORMAL
14 HIGH_PRIORITY_CLASS THREAD_PRIORITY_ABOVE_NORMAL
15 HIGH_PRIORITY_CLASS THREAD_PRIORITY_HIGHEST
15 HIGH_PRIORITY_CLASS THREAD_PRIORITY_TIME_CRITICAL
15 IDLE_PRIORITY_CLASS THREAD_PRIORITY_TIME_CRITICAL
15 BELOW_NORMAL_PRIORITY_CLASS THREAD_PRIORITY_TIME_CRITICAL
15 NORMAL_PRIORITY_CLASS THREAD_PRIORITY_TIME_CRITICAL
15 ABOVE_NORMAL_PRIORITY_CLASS THREAD_PRIORITY_TIME_CRITICAL
16 REALTIME_PRIORITY_CLASS THREAD_PRIORITY_IDLE
...
24 REALTIME_PRIORITY_CLASS THREAD_PRIORITY_NORMAL
...
26 REALTIME_PRIORITY_CLASS THREAD_PRIORITY_HIGHEST
...
31 REALTIME_PRIORITY_CLASS THREAD_PRIORITY_TIME_CRITICAL
CAMPUS HAGENBERG 10

Besonderheit: Scheduling auf Multicore-CPUs - 1

-> zusätzlich zum Betriebssystem führt die CPU ein Scheduling durch
-> HW-Scheduling teilt die lauffähigen Threads den parallelen HW-Einheiten zu
• für bessere Kernauslastung (zB. bei Memory Stalls, I/O-Blockaden, ...)
• Energiesparen
• für HT-Systeme (Zuordnung der Threads logischer Kerne auf physische Kerne)

-> 2 versch. HW-Implementierungen in der CPU

• grobgranulares Multithreading
-> HW schaltet nur bei sehr langen Blockaden auf andere Threads um, etwa bei Mem-Stalls
-> Threadwechsel ist aufwändig: Pipeline muss mit Instruktionen des neuen Threads gefüllt werden

• freingranulares Multithreading
-> CPU-Architektur unterstützt ein Threadswitching auf Instruktionsebene
-> HW ist dafür optimiert, Aufwand ist verglechsweise gering
CAMPUS HAGENBERG 11

Besonderheit: Scheduling auf Multicore-CPUs - 2

Erläuterung grobgranular/feingranulares MT am Chip:
Multicore Scheduling There are two ways to multithread a processor :
In multicore processors multiple processor cores are places on the same Coarse-Grained Multithreading – In coarse grained multithreading
physical chip. Each core has a register set to maintain its architectural a thread executes on a processor until a long latency event such as a
state and thus appears to the operating system as a separate physical memory stall occurs, because of the delay caused by the long latency
processor. SMP systems that use multicore processors are faster and event, the processor must switch to another thread to begin execution.
consume less power than systems in which each processor has its own The cost of switching between threads is high as the instruction
physical chip. pipeline must be terminated before the other thread can begin
However multicore processors may complicate the scheduling execution on the processor core. Once this new thread begins execution
problems. When processor accesses memory then it spends a significant it begins filling the pipeline with its instructions.
amount of time waiting for the data to become available. This situation Fine-Grained Multithreading – This multithreading switches
is called MEMORY STALL. It occurs for various reasons such as cache between threads at a much finer level mainly at the boundary of an
miss, which is accessing the data that is not in the cache memory. In instruction cycle. The architectural design of fine grained systems
such cases the processor can spend upto fifty percent of its time waiting include logic for thread switching and as a result the cost of switching
for data to become available from the memory. To solve this problem between threads is small.
recent hardware designs have implemented multithreaded processor
cores in which two or more hardware threads are assigned to each
core. Therefore if one thread stalls while waiting for the memory, core Copyright
can switch to another thread. Silberschatz, Galvin, Gagne: Operating System Principles, Wiley, 2006
CAMPUS HAGENBERG 12

Besonderheit: Scheduling auf Multicore-CPUs - 3

Energiesparen:
Energiesparen auf Quadcore mit Hyperthreading -> 8 logische Kerne, 8 logische Threads

-> Threads werden unter Teillast nicht verteilt, sondern gruppiert.

-> Abkühlung erlaubt Übertaktung der Kerne
CAMPUS HAGENBERG 13

Besonderheit: Scheduling auf Multicore-CPUs - 4

Seiteneffekte:
-> Prioritäten werden tw. unwirksam auf Mehrkern-CPUs

Singlecore Multicore (Quadcore):

-> Ergebnis auf Multicore: Scheduler teilt hochprioren Threads eigenen Kern zu,
andere Kerne arbeiten niedrigpriore Threads zeitgleich ab
CAMPUS HAGENBERG 14