AMD Ryzen 7 2700X och Ryzen 5 2600X "Pinnacle Ridge"

Du blandar inte ihop "work-stealing" med "work sharing / job scheduler"?

Är en egentligen överförenkling att hävda att spel specifikt använder "work-stealing", det är bara en av fler varianter av metoder där man designar sitt system så en dynamiskt varierande parallellism kan spridas över en statisk konfiguration av CPU-kärnor/trådar (statisk för varje specifikt system, men som varierar mellan system).

För diskussionen som pågick ovan kvittar det vilken av dessa som används, alla har samma huvudsyfte: automatiskt använda de CPU-kärnor / trådar som finns i system, något som i praktiken bara händer om det finns tillräckligt med dynamisk parallellism (tillräckligt hög "parallel slackness").

Jeff Preshing (som jobbar på Ubisoft Montreal och är deras "multicore expert") har ett gäng YouTube videos ute där han pratar om hur Ubisofts motorer är designade ur denna aspekt. Deras motorer är mer "work sharing" jämfört med "work stealing".

Fördelen med den förra är enklare implementation, men den har precis de nackdelar du påpekar kring att den i praktiken får problem med skalning när antalet kärnor kliver upp. Metoden har också inget vettigt sett att hantera asymmetri i HW.

Work stealing har under relativt lång tid används i superdatorer med enormt många CPU-kärnor och NUMA-problematik. Givet tillräckligt med dynamisk parallellism så är huvudpoängen med work-stealing över work-sharing att den förra är relativt enkel att skriva så den tar hänsyn till asymmetri. De jag gjort har tagit hänsyn till allt från cache-hierarki, till NUMA till SMT/icke-SMT, det utan att applikationen på något sätt behövts ändras.

Så teoretisk följer alla nämnda metoder samma regler, i praktiken är "work-stealing" mer framtiden. Bra stället att börja läsa för den som vill gräva ner sig i teori

Angående Windows och flytta runt saker mellan kärnor. Problemet med de flesta spel är att de är allt för ivriga med att utnyttja alla CPU-trådar som finns. Ett spel som Far Cry 5 har inte lika många trådar som CPU-trådar, det har fler än så! Detta blir ett problem för Windows i lägen där man momentant råkar ha fler trådar som vill köra än det finns CPU-trådar i systemet. I det läget är Windows extremt aggressiva med att försöka schemalägga varje tråd så snabbt som möjligt, även om det betyder att tråden måste köra på en annan CPU-kärnan än den kördes på precis innan (dåligt ur cache-lokalitetssynpunkt).

Effekten när man tittar i aktiviteteshanteraren blir då att alla CPU-trådar har viss last, det optimala hade varit att färre hade legat närmare 100 %.

Såg att du redan fått ett svar här. Handlar alltså om att när man har klockfrekvenser i GHz nivå har signalerna mindre än en nanosekund på sig att hinna propagera.

I praktiken har dagens CPUer lite "relativitetseffekt" i form av att flanken på klocksignalerna kommer passera olika delar av kretsen vid lite olika tid. Denna effekt är så pass stor att de som designar lite större kretsar (och en modern high-end x86 är definitivt en sådan "större krets") måste ta hänsyn till denna effekt.

Saker som detta leder till är att man måste hantera saker över flera cykler -> ger latens.

Man kan bara koppla ihop saker rent elektriskt förutsatt att dessa punkter har väldigt snarlik fördröjning av klockflanken, signalen måste ibland ta en längre väg än den logiskt kortaste -> ger latens.

En modern CPU har flera klockdomäner, det måste finnas en viss säkerhetsmarginal (någon form av buffert på typiskt några cykler) mellan klockdomäner -> ger latens. T.ex. så går CPU-kärnan och Infinity fabric på olika klockdomäner i Zen (kärnan och ringbussen går på olika klockdomäner i Core, i all fall sedan Haswell).

Så tiden för att kommunicera mellan kärnor är absolut begränsad av att hastigheten signaler kan breda ut sig är begränsad på ett sätt som spelar roll vid nanosekundnivå! Än värre blir det om man ska gå via RAM, det kostar ett par hundratals CPU-cykler idag!

Kanske inte du som blandat ihop något då, låter som din referens / dina referenser från KTH gjort det.

Känner till Mats Brorsson som verkar på KTH. Han verkar leda ett team som tvärtom pratar om fördelarna hos OpenMP (som precis som t.ex. Cilk som blev produkter från länken jag listade ovan och Intels TBB)

Från en 2015 års publikation från KTH gänget

"We identify that both data distribution and locality-aware task scheduling improves performance compared to default policies while still providing an architecture-oblivious approach for the programmer."

Fetmarkerade är det kritiska och är här "work stealing" har fördelar över "job schedulering / work sharing" (där hade man ett quad-socket AMD Opteron system). Samma grupp beskriver även samma grundteknik för en lite mer extrem design när det kommer till asymmetri mellan kärnor, TilePro64 (64-kärnor multicore krets med rejäl asymmetrisk RAM latens och potentiellt väldigt hög kostnad för att läsa "fel" cache).

Alla dessa tekniker lämpar sig för "fork-join", dock är det inte det enda de stödjer (där dock exakt vad OpenMP och Cilk men inte nödvändigtvis TBB använder detta till). De system där jag designat "work-stealing scheduler" har varit helt köbaserade där "work-stealing" använts för att avgöra vilken CPU-resurs som ska hantera en viss kö, där varje kö innehåller jobb som inom en kö måste utföras sekventiellt, medan jobb på olika köer kan utföras parallellt.

I Ubisofts programvara kommer det kontext som ger upphov till någon ny form av isolerad beräkning distribuerar jobbet, d.v.s. en form av "push" där avsändaren inte vet något om vilken CPU-kärna/NUMA-zon mottagaren befinner sig på. Specifikt i Ubisofts fall använder man sig av ett gäng köer som signaleras via Win32 "Event objects".

Självklart kommer sådan få problem med NUMA-system, fast hur vanliga är de som spelmaskiner? Vidare kör Ubisoft med "broadcast", d.v.s. logiskt sett väcker man upp alla "worker-threads" som temporärt inte hade något att göra och den som är snabbast "vinner" och tar hand om jobbet. Inte heller helt optimalt när man börjar få riktigt många kärnor (men hur många spelmaskiner har det?).

I "work-stealing" så postas alla nya jobba alltid på den lokala kön för den kontext som skapade jobbet. Verkar kanske skumt, det ger ju ingen parallellism... Fördelen med detta är att om alla CPU-trådar har något att göra ger detta upphov till noll kommunikation mellan CPU-trådar -> perfekt skalning!

Spel och de flesta applikationer utanför superdatorer kommer in ha i närheten så mycket dynamisk parallellism att alla CPU-trådar har något att göra hela tiden. En CPU-tråd som får slut på jobb vet (om man kör med hård CPU-thread affinity, vilket inte alltid är fallet men är ett krav om man vill hantera asymmetri i HW) exakt vilken NUMA-zon den befinner sig på, den vet (då OS som Windows och Linux har APIer för detta) vilka andra CPU-trådar t.ex. L3$ delas med.

Här kan man då enkelt införa heuristik: stjäl i första hand arbete från CPU-kärnor som är "billigt" att kommunicera med, de i samma CCX i Ryzen fallet. Stjäl i andra hand från de på samma NUMA-zon och i sista hand från andra NUMA-zoner (den "andra" kretsen hos ThreadRipper).

Vet man om att arbetet stjäls från en annan NUMA-zon kan man också lägga in annan heuristik, t.ex. att man gör en "deep copy" av "working-set" för jobbet. Potentiellt dyrt , men gör att jobbet sedan utförs mer effektivt. (Att kopiera data är billigare än de flesta tror och är förvånansvärt ofta värt det i multicore-system då man slipper mycket av synkroniseringsproblemen).

Att artikeln jag länkade till är 20 år gammal: visar väl att tekniken är relevant då vi fortfarande pratar om den
Alla lite större förändringar tar väldigt sällan mindre en ett decennium att slå igenom. I detta fall spenderades säker 10 år enbart kring forskning och de senare 10 åren har spenderats till att få in tekniken i kompilatorer, bibliotek och slutligen applikationer.

Tyvärr löser inte den här tekniken huvudproblem för spel: hur extraheras tillräckligt med dynamisk parallellism för 6-8 C modeller på ett sätt som är effektivt? Det går ju ändå framåt, vi ser ju faktiskt en liten vinst med 6C över 4C idag!

Sedan finns det även spel som har lite att jobba på... Råkade köra "process explorer" på Fortnite. Varför har detta spel över 40 trådar som var och en drar någon enstaka procent varje frame (det på en 4C/8T CPU)? Här har vi ett exempel på hur man inte ska designa något om det ska skala bra. Windows eller Linux scheduler, är irrelevant för ingen av dessa har någon chans att göra något riktigt optimalt i detta fall, blir riktigt karusell av trådar som hoppar mellan kärnor