[C++] multithreading optimaliseren

[Arjan]

Nu de multi-core processors gemeengoed zijn geworden merk ik dat ik zelf ook meer en meer met threads werk.

Nu zijn threads erg krachtige hulpmiddelen, maar kunnen ze ook tot (heel) veel problemen leiden.
Buiten de standaard problemen als deadlocks, starvation en dergelijke, brengen threads ook overhead met zich mee. Het is deze overhead die ik graag aan wil pakken.

Als je een situatie hebt waarbij er veel threads aan het vechten zijn om een stukje cpu, ontstaat bijvoorbeeld door context switching, de situatie waarbij het behaalde rendement terugloopt.

Om dit probleem tegen te gaan heb ik een thread-pooling architectuur bedacht die ik graag eens tegen het licht zou houden.
Mijn opzet is om een generieke oplossing te maken die voor de meeste multithreading oplossingen inzetbaar is.

Ik wil mij in principe richten op de x86 architectuur, het moet werken onder windows, linux en osx.

de opzet:

De main thread start een scheduling thread, deze draait in principe op dezelfde affiniteit als de main thread.

De scheduling thread start, afhankelijk van het aantal beschikbare cores en eventueel afhankelijk van zaken als hyperthreading, een aantal threads en stelt hun affiniteit in. (lukt dit cross-platform?)
Deze thread blijft door alle jobs heen loopen en kijkt welke job de laagste nice-waarde heeft.
Als er threads vrij zijn (geen job aan het runnen) dan worden de jobs met de laagste nice-waarde aan de vrije threads toegekend. Een nice waarde van 1 betekend dat een job niet ingepland wordt.

De jobs hebben dus een nice-value, die loopt van [0,1]. Deze nice waarde hangt bijvoorbeeld af van hoeverre een bepaalde buffer gevuld is.
Elke job heeft een 'run' functie, deze moet er in principe voor zorgen dat de nice waarde oploopt.
Een job kan niet onderbroken worden zodra deze aan een thread is toegewezen.

De threads worden dus door de scheduling thread beheerd en kunnen één job per keer uitvoeren.

graag hoor ik jullie op- of aanmerkingen over deze opzet.
Ik wil in principe pthread gaan gebruiken voor de onderliggende thread functies. Mocht dit idee tot uitvoer komen dan wordt het natuurlijk gewoon open source beschikbaar

[Alarmnummer]

Arjan schreef op zaterdag 16 augustus 2008 @ 20:30:
Nu de multi-core processors gemeengoed zijn geworden merk ik dat ik zelf ook meer en meer met threads werk.

Nu zijn threads erg krachtige hulpmiddelen, maar kunnen ze ook tot (heel) veel problemen leiden.
Buiten de standaard problemen als deadlocks, starvation en dergelijke, brengen threads ook overhead met zich mee. Het is deze overhead die ik graag aan wil pakken.

Leuk idee, maar vergeet niet dat andere mensen zoals cpu en operating system designers zich hier ook mee bezig houden. Het kan maar zo zijn dat een developer zijn optimalisatie juist een van het os/cpu tegenwerkt.

Java heb je bv biased locking waarbij iedere intrinsic lock een lieveling thread heeft en daardoor veel minder os-call hoeft te doen. Als je allerlei extra werk zou verrichten om deze 'extra' lock te verzeilen, zou je uiteindelijk wel eens duurder uit kunnen komen.

Als je een situatie hebt waarbij er veel threads aan het vechten zijn om een stukje cpu, ontstaat bijvoorbeeld door context switching, de situatie waarbij het behaalde rendement terugloopt.

Dat ligt er heel erg aan. Sommige cpu's die kicken juist op het feit dat er veel threads zijn om uit te voeren. Als je bv kijkt naar de Niagara processor van Sun, die heeft ipv een lange pipeline met complexe branche prediction (om 1 thread zo snel mogelijk te laten draaien) een veel kortere pipeline en hoopt dat er een andere thread klaar staat als de huidige thread om wat voor reden niet verder kan (bv als er naar main geheugen gegaan moeten worden ipv een cache hit).

En context swithes zijn daar binnen een groepje van 'fake cpu's' juist extra gewild om de echte cpu maar de hele tijd bezig te houden. Context switches zijn hier trouwens ook ordes van groter goedkoper (het is de nature van deze cpu)

Om dit probleem tegen te gaan heb ik een thread-pooling architectuur bedacht die ik graag eens tegen het licht zou houden.
Mijn opzet is om een generieke oplossing te maken die voor de meeste multithreading oplossingen inzetbaar is.

Ik wil mij in principe richten op de x86 architectuur, het moet werken onder windows, linux en osx.

de opzet:

De main thread start een scheduling thread, deze draait in principe op dezelfde affiniteit als de main thread.

De scheduling thread start, afhankelijk van het aantal beschikbare cores en eventueel afhankelijk van zaken als hyperthreading, een aantal threads en stelt hun affiniteit in. (lukt dit cross-platform?)
Deze thread blijft door alle jobs heen loopen en kijkt welke job de laagste nice-waarde heeft.
Als er threads vrij zijn (geen job aan het runnen) dan worden de jobs met de laagste nice-waarde aan de vrije threads toegekend. Een nice waarde van 1 betekend dat een job niet ingepland wordt.

De jobs hebben dus een nice-value, die loopt van [0,1]. Deze nice waarde hangt bijvoorbeeld af van hoeverre een bepaalde buffer gevuld is.
Elke job heeft een 'run' functie, deze moet er in principe voor zorgen dat de nice waarde oploopt.
Een job kan niet onderbroken worden zodra deze aan een thread is toegewezen.

De threads worden dus door de scheduling thread beheerd en kunnen één job per keer uitvoeren.

graag hoor ik jullie op- of aanmerkingen over deze opzet.
Ik wil in principe pthread gaan gebruiken voor de onderliggende thread functies. Mocht dit idee tot uitvoer komen dan wordt het natuurlijk gewoon open source beschikbaar

Volgens mij ben je daar coorperative multithreading aan het beschrijven met alle gevolgen van dien.

edit:

Het zou cooperative zijn als de taken uit-gescheduled kunnen worden. Jouw architectuur heeft problemen met taken die lang bezig zijn omdat die taken de kans niet meer geven aan andere threads. Dus als je 4 werkerthreads hebt en 4 lang lopende taken, zal je systeem geen andere taken meer uitvoeren met alle gevolgen van dien.

Het lijkt ook wel een beetje op de actor based approach van Erlang. Iedere thread kan een aantal actors bedienen: als een actor input binnen krijgt of weg wil schrijven, kan een thread hem oppakken en het tijdelijk draaien. Jouw taken lijken dan veel op actors.

Hou er trouwens rekening mee dat je wellicht wilt voorkomen dat je een taak op iedere cpu gaat uitvoeren. Het kan maar zo zijn dat je dan steeds cache misses gaat krijgen.

Ik juig trouwens alle experimenten omtrend concurrency toe, maar zorg er wel voor dat je uiteindelijk moet gaan meten om te controleren of het ook echt beter is. En verder: lies, damn lies and statistics Benchmarks maken die jouw software goed laten lijken zijn eenvoudig gemaakt dan benchmarks waarmee je echt een onafhankelijke vergelijking kunt maken.

ps
Kijk trouwens ook eens naar de Intel Thread building blocks library

[ Voor 4% gewijzigd door Alarmnummer op 16-08-2008 22:05 ]

[H!GHGuY]

^^ with smartass

Lees je eens in in de CFS van Linux. Dan moet je er enkel nog voor zorgen dat je je threads gebalanceerd aan het werk zet. Eventueel kun je ook de nice-waarde dynamisch aanpassen.

Ik zou zeker niet beginnen met een scheduler bovenop een scheduler te schrijven. Dat geeft bijna geheid problemen.

[Arjan]

Alarmnummer schreef op zaterdag 16 augustus 2008 @ 21:40:
[...]

Leuk idee, maar vergeet niet dat andere mensen zoals cpu en operating system designers zich hier ook mee bezig houden. Het kan maar zo zijn dat een developer zijn optimalisatie juist een van het os/cpu tegenwerkt.

daar ben ik me goed van bewust, vandaar ook dit topic alvorens een regel code te schrijven

[...]

Dat ligt er heel erg aan. Sommige cpu's die kicken juist op het feit dat er veel threads zijn om uit te voeren. Als je bv kijkt naar de Niagara processor van Sun, die heeft ipv een lange pipeline met complexe branche prediction (om 1 thread zo snel mogelijk te laten draaien) een veel kortere pipeline en hoopt dat er een andere thread klaar staat als de huidige thread om wat voor reden niet verder kan (bv als er naar main geheugen gegaan moeten worden ipv een cache hit).

En context swithes zijn daar binnen een groepje van 'fake cpu's' juist extra gewild om de echte cpu maar de hele tijd bezig te houden. Context switches zijn hier trouwens ook ordes van groter goedkoper (het is de nature van deze cpu)

Arjan schreef op zaterdag 16 augustus 2008 @ 20:30:
[...]

Ik wil mij in principe richten op de x86 architectuur, het moet werken onder windows, linux en osx.

[...]

ik ben mij zeer bewust van de enorme verschillen die andere architecturen met zich mee kunnen brengen, vandaar deze regel.

offtopic:
ik mag binnenkort waarschijnlijk voor m'n werk met de cell processor gaan spelen \o/ ben erg benieuwd hoe deze multithreading gaat reageren..

[...]

Hou er trouwens rekening mee dat je wellicht wilt voorkomen dat je een taak op iedere cpu gaat uitvoeren. Het kan maar zo zijn dat je dan steeds cache misses gaat krijgen.

cache misses doordat je één taak op één cpu uitvoert? is het niet net andersom?

Ik juig trouwens alle experimenten omtrend concurrency toe, maar zorg er wel voor dat je uiteindelijk moet gaan meten om te controleren of het ook echt beter is. En verder: lies, damn lies and statistics Benchmarks maken die jouw software goed laten lijken zijn eenvoudig gemaakt dan benchmarks waarmee je echt een onafhankelijke vergelijking kunt maken.

ps
Kijk trouwens ook eens naar de Intel Thread building blocks library

ga ik doen

H!GHGuY schreef op zaterdag 16 augustus 2008 @ 21:53:
^^ with smartass

Lees je eens in in de CFS van Linux. Dan moet je er enkel nog voor zorgen dat je je threads gebalanceerd aan het werk zet. Eventueel kun je ook de nice-waarde dynamisch aanpassen.

Ik zou zeker niet beginnen met een scheduler bovenop een scheduler te schrijven. Dat geeft bijna geheid problemen.

Ik heb het wellicht niet duidelijk gemaakt, maar de nice waarde moet absoluut dynamisch zijn.
bijvoorbeeld, als je een encoder als job hebt, dan zou de nice waarde omgekeerd evenredig kunnen zijn met z'n packet queue. Hoe meer packets er klaar staan om geencodeerd te worden, hoe lager de nice waarde.
Het idee is dat je de functie om de nice waarde te berekenen zelf schrijft voor elke job (virtuele functie overriden). Zo kun je de voorkeur op job niveau regelen.

[Alarmnummer]

Arjan schreef op zaterdag 16 augustus 2008 @ 22:27:
ik ben mij zeer bewust van de enorme verschillen die andere architecturen met zich mee kunnen brengen, vandaar deze regel.

In mindere mate geld hetzelfde voor hyperthreads. Hyperthreads geven pas meerwaarde als er behoefte is aan context switching. Een hyperthread architectuur is eigelijk niet anders dan meerdere logische executie eenheden over 1 fysieke. Als er 2 cpu intensieve threads zijn, zal het systeem met hyperthreads niet sneller gaan dan een systeem zonder.

cache misses doordat je één taak op één cpu uitvoert? is het niet net andersom?

Als ik je verhaal goed begrijp zal een taak in verloop van tijd meerdere keren aan bod kunnen komen. Welke garantie geeft jouw oplossing dat tijdens zo'n ronde de taak niet iedere keer op een andere cpu aan de slag gaat.

Volgens mij moet je het verhaal mbt het in en uit schedulen van een taak beter toelichten want het is mij niet duidelijk. Je zei dat een job als die een keer uitgevoerd gaat worden niet meer onderbroken gaat worden, maar waarom heb je die nice waardes? Het doel daarvan lijkt mij dat zo gauw een taak om wat voor reden gaat blokkeren en dus geen progres meer kan boeken, dat een andere taak weer een beurt krijgt.

[edit]
Als je taken blijven doorlopen tot het einde, en die nice waarde alleen bedoelt is om aan het begin een te pakken met de hoogste effecitiveits kans, dan krijg je volgens mij problemen om je taken klein genoeg te krijgen. Volgens mij zou dat geen prettige architectuur voor developer zijn.

[ Voor 10% gewijzigd door Alarmnummer op 16-08-2008 23:31 ]

[Arjan]

Alarmnummer schreef op zaterdag 16 augustus 2008 @ 23:20:
[...]

Als ik je verhaal goed begrijp zal een taak in verloop van tijd meerdere keren aan bod kunnen komen. Welke garantie geeft jouw oplossing dat tijdens zo'n ronde de taak niet iedere keer op een andere cpu aan de slag gaat.

goed punt, er zal een factor bij moeten komen die ervoor zorgt dat taken waar mogelijk op dezelfde processor gescheduled worden.

Volgens mij moet je het verhaal mbt het in en uit schedulen van een taak beter toelichten want het is mij niet duidelijk. Je zei dat een job als die een keer uitgevoerd gaat worden niet meer onderbroken gaat worden, maar waarom heb je die nice waardes? Het doel daarvan lijkt mij dat zo gauw een taak om wat voor reden gaat blokkeren en dus geen progres meer kan boeken, dat een andere taak weer een beurt krijgt.

[edit]
Als je taken blijven doorlopen tot het einde, en die nice waarde alleen bedoelt is om aan het begin een te pakken met de hoogste effecitiveits kans, dan krijg je volgens mij problemen om je taken klein genoeg te krijgen. Volgens mij zou dat geen prettige architectuur voor developer zijn.

ik ben bij het bedenken van deze structuur inderdaad niet uitgegaan van iemand die als job het volgende schrijft.

code:

void job() {
    while(1) decodePacket();
}

Ik had voor ogen dat je job er dan zo uit zou zien

code:

void job() {
    decodePacket();
}

Ik zie dat ik hier niks over beschreven heb in de ts
Maar het idee was dat jobs zichzelf opnieuw kunnen inplannen op basis van hun return waarde. Zolang een job bv. true returned, wordt deze steeds opnieuw ingeplanned.

Multi threading problemen die niet op te delen zijn in kleine stukken, laten zich inderdaad niet optimaliseren door mijn oplossing..
Ik zie niet direct in hoe je die situatie überhaupt zou kunnen ondersteunen en nog steeds iets bieden dat meer doet dan de standaard scheduling, dus wellicht dat deze oplossing minder general purpose is dan ik aanvankelijk dacht. Moet ik er wel bij zeggen dat ik me tot op heden eigenlijk geen real-life situaties kan herinneren waarbij het probleem niet op te delen was in kleine stukken.

Sowieso heb je alleen maar voordeel van deze opzet als je heel veel threads hebt. zolang je threadcount lager ligt dan twee keer het aantal cores denk ik dat er niks te winnen is ten opzichte van de systeem scheduler. Hetzelfde geldt voor single of dual core machines. Ik denk dat er pas echt wat te winnen valt zodra je naar systemen gaat kijken waar ook daadwerkelijk veel threads concurrent bezig kunnen zijn.
Dat is natuurlijk ook pas het moment waarop de overhead van thread scheduling echt mee gaat tellen

[oeLangOetan]

Misschien heb ik het verkeerd maar ik heb het gevoel dat je het wiel aan het heruitvinden bent. Dit lijkt heel sterk op actor gebaseerde systemen (zoals in erlang, scala, kilim+java) ook wel eens fork/join genoemd. Ik zou beginnen met papers te lezen van bestaande implementaties ipv er onmiddellijk in te springen.

http://lamp.epfl.ch/~phaller/doc/ActorsTutorial.html
http://cis.poly.edu/muller/CS623/FORKJOIN.htm
http://www.malhar.net/sriram/kilim/

[ Voor 18% gewijzigd door oeLangOetan op 17-08-2008 22:51 ]

[Arjan]

Ik ben niet bekend met het actor model, maar op basis van wat ik erover lees lijkt het me niet helemaal hetzelfde.

Het is niet de bedoeling dat de afzonderlijke threads met elkaar kunnen communiceren, het gaat er puur om dat de prioriteit van de threads door de threads zelf aangegeven kunnen worden. Het is vervolgens aan de scheduler om de slimste keuze te make op basis van de bekende gegevens.
Daarnaast ligt het vast hoeveel threads er zijn en is het niet dynamisch zoals bij het actor model. (als ik het goed begrepen heb)

[MSalters]

ALs je de x86 target, dan kan er maar 1 plek zijn om te beginnen, en dat is bij Intel zelf. Intel heeft de Thread Building Blocks ontworpen, en die zijn inderdaad cross-platform. Lees om te beginnen de Tutorial, met name hoofdstuk 10 (Task Scheduler).

Ik ben benieuwd als je daarna kunt aangeven op welk (deel)gebied je denkt een betere implementatie dan Intel te kunnen maken. Eerlijk gezegd heb ik namelijk er een hard hoofd in: je verwijst oa naar pthreads, terwijl dat zeker niet cross-platform is. Intel TBB is al Open Source en Commercial, dus daar ga je ook niet winnen.

Fundamenteler zie ik een probleem met je "nice" concept. je wil de threads niet zelf schedulen,maar door de prioriteit te zetten kom je daar wel op uit. Verder hebben je jobs geen thread affiniteit. Leuk dat je threads wel een processor affiniteit hebben, maar daar schiet je dus niets mee op - je data raakt nog steeds verdeeld over verschillende processorcaches omdat je jobs dat doen.

Verder zorgt het dynamisch veranderen van nice levels juist voor scheduling overhead. Stel, ik heb 1 thread, een producer/consumer architectuur met een buffer, en beide kanten passen hun niceness dynamisch aan aan de buffergrootte. Dan bereik je op een gegeven ogenblik een evenwicht waarbij beiden dezelfde nice-ness hebben. Neem even aan dat de consumer dan 1 item uit de queue haalt, dan stijgt zijn niceness. (De producer zou juist moeten stijgen, maar kan dat niet zolang de consumer draait). Door het stijgen van de consumer niceness heeft de producer weer de laagste niceness. Er vindt dus een jobswitch plaats (zonder threadswitch, dus je processor kan geen HyperThreading doen). Je producer kan weer 1 workitem produceren, waarna de originele situatie weer ontstaat. Je hebt dus een massieve overhead omdat voor elk workitem er een niceness aanpasssing plaatsvindt die direct tot een jobswitch leidt.

Als je twee cores en twee threads hebt, dan heb je in dit voorbeeld simpelweg geen scheduling overhead. Beide threads draaien simpelweg op hun eigen core.

Wat overigens wel een interessante overweging is, is of je wel 1 producer en 1 consumer wil hebben op een dual-core machine. Is het niet verstandiger om een elke core (en dus cache) zijn eigen producer/consumer pair te geven? Dit is geen simpel probleem - en dus een software oplossing die daaebij helpt wel vernieuwend.

[Arjan]

MSalters schreef op maandag 18 augustus 2008 @ 14:54:
ALs je de x86 target, dan kan er maar 1 plek zijn om te beginnen, en dat is bij Intel zelf. Intel heeft de Thread Building Blocks ontworpen, en die zijn inderdaad cross-platform. Lees om te beginnen de Tutorial, met name hoofdstuk 10 (Task Scheduler).

Hier ga ik zeker naar kijken, maar ik vind hun examples niet echt uitblinken in eenvoud, dus daar zal ik eens uitgebreid tijd in moeten steken.

[...]

Fundamenteler zie ik een probleem met je "nice" concept. je wil de threads niet zelf schedulen,maar door de prioriteit te zetten kom je daar wel op uit. Verder hebben je jobs geen thread affiniteit. Leuk dat je threads wel een processor affiniteit hebben, maar daar schiet je dus niets mee op - je data raakt nog steeds verdeeld over verschillende processorcaches omdat je jobs dat doen.

dit was al aangehaald en ik had daar ook al op gereageerd. Jobs zullen absoluut een affiniteit moeten krijgen.

Verder zorgt het dynamisch veranderen van nice levels juist voor scheduling overhead. Stel, ik heb 1 thread, een producer/consumer architectuur met een buffer, en beide kanten passen hun niceness dynamisch aan aan de buffergrootte. Dan bereik je op een gegeven ogenblik een evenwicht waarbij beiden dezelfde nice-ness hebben. Neem even aan dat de consumer dan 1 item uit de queue haalt, dan stijgt zijn niceness. (De producer zou juist moeten stijgen, maar kan dat niet zolang de consumer draait). Door het stijgen van de consumer niceness heeft de producer weer de laagste niceness. Er vindt dus een jobswitch plaats (zonder threadswitch, dus je processor kan geen HyperThreading doen). Je producer kan weer 1 workitem produceren, waarna de originele situatie weer ontstaat. Je hebt dus een massieve overhead omdat voor elk workitem er een niceness aanpasssing plaatsvindt die direct tot een jobswitch leidt.

Zolang de jobs niet van core naar core geslingerd worden zie ik hier niet een probleem eerlijk gezegd

Als je twee cores en twee threads hebt, dan heb je in dit voorbeeld simpelweg geen scheduling overhead. Beide threads draaien simpelweg op hun eigen core.

Wat overigens wel een interessante overweging is, is of je wel 1 producer en 1 consumer wil hebben op een dual-core machine. Is het niet verstandiger om een elke core (en dus cache) zijn eigen producer/consumer pair te geven? Dit is geen simpel probleem - en dus een software oplossing die daaebij helpt wel vernieuwend.

In de software die ik aan het schrijven ben is er maar één consumer en vele producers. Meerdere consumers zou natuurlijk kunnen maar dan komt er weer (minimale) overhead bij zodat alle consumers gesynced zijn. Zeker interesant om eens na te kijken

[MSalters]

Het probleem met producer/consumer switching is dat je CPU cache net zo hard onderuit gaat bij een job switch als bij een thread switch. In beide gevallen zit je nog wel in hetzelfde process, maar je executeert andere code, die andere data gebruikt. In termen van efficiency is het dus verstandig om pas van producer naar consumer job te switchen als je buffer vol zit, en andersom als je leeg is. De buffer-level niceness is pas relevant als geen van beiden draaien, en je 1 van de 2 moet gaan starten.

Verder: Een scheduler thread? Om overhead aan te pakken? Dat lijkt me nou precies het verkeerde begin. Je worker threads moeten een main loop hebben, die de job dispatching doet. Die threads kunnen zelf samen hun werk verdelen. Als die worker threads moeten gaan wachten todat de ene scheduler thread hun een job kan geven, dan heb je een groot schalingsprobleem. Wat als je 32 worker threads hebt? Of 1 ? In geen van beide gevallen lijkt me handig om 1 scheduler thread te hebben.

Als elke workerthread gewoon de eerste job uit een lock-free priorityqueue kan halen, dan is het schedulen behoorlijk schaalbaar. Maar ook dan staan alle workerthreads op 1 shared datastructuur te hameren. Dat is wel efficienter dan dat alle workerthreads op de beslissingen van een scheduler moeten wachten, die dan de sharing van de datastructuur oplost. Je OS hoeft geen 2 threadswitches meer te doen om een nieuw workitem te bepalen en vervolgens te starten.

Een ander potentieel probleem lijkt me de dynamische niceness bepaling. Als er op een gegeven moment 1000 workitems beschikbaar zijn, en de niceness is statisch, dan kunnen ze voorgesorteerd zijn. Bij een nieuw item heb je dan een O(log(N)) insert nodig. Is de niceness dynamisch, dan moet je na elke jobcompletion opnieuw de job met de laagste niceness vinden. Dat is een O(N) operatie.

In je N->1 producer/consumer architectuur zou het inderdaad interessant kunnen zijn om de consumers zelf weer te splitsen in een per-core consumer deel die de informatie per core verzamelt en voorbewerkt, en een verzamelaar. Dan heb je namelijk per core een buffer tussen producer en consumer, wat goed is voor caches.