bloghoved ole tange

Paralleliseringsproblemer

Det er næppe noget chok for nogen, at jeg er udvikler af GNU Parallel og derfor også hører om nørdede paralleliseringsproblemer, som folk støder på.

Her er et af dem.

Det er ikke altid, at ting går hurtigere af at bliver paralleliseret. Hvis man f.eks. bruger almindelige harddiske, så er det ret langsomt at flytte læsearmen, men relativt hurtigt at læse en ekstra megabyte. Så hvis man læser i parallel flere steder fra disken (f.eks. flere filer samtidigt), så kan det nemt være langsommere end at læse indholdet fra en ende af (f.eks. læse en fil af gangen).

Men der er alligevel situationer, hvor man bliver overrasket over, at det bliver langsommere af at parallelisere.

Tesseract er software til at konvertere grafik til tekst (OCR). Det fungerer ret nemt. Stik den en grafikfil og så prøver den at få tekst ud af den:

$ tesseract foo.jpg foo

En af GNU Parallels brugere tænkte: "Jamen jeg har jo flere cores, så jeg starter da bare en tesseract per core. Så kan jeg hurtigt få konverteret mine scanninger."

Men ak. Han blev skuffet: Det tog længere tid hvis man kører flere Tesseract i parallel. Ikke bare lidt, men meget.

Jeg reproducerede problemet på min laptop med nyeste tesseract kode fra git. Tesseract har indbygget noget parallelisering, men man kan tvinge Tesseract til at bruge een tråd med 'export OMP_THREAD_LIMIT=1'.

$ find | grep jpg | time parallel -j1 tesseract {} foo
Tesseract Open Source OCR Engine v5.0.0-alpha-781-gb19e3 with Leptonica
:
Tesseract Open Source OCR Engine v5.0.0-alpha-781-gb19e3 with Leptonica
44.29user 1.05system 0:16.43elapsed 275%CPU (0avgtext+0avgdata 83392maxresident)k
460538inputs+0outputs (0major+311928minor)pagefaults 0swaps
 
$ find | grep jpg | time parallel tesseract {} foo
Tesseract Open Source OCR Engine v5.0.0-alpha-781-gb19e3 with Leptonica
:
Tesseract Open Source OCR Engine v5.0.0-alpha-781-gb19e3 with Leptonica
1416.10user 6.00system 7:39.97elapsed 309%CPU (0avgtext+0avgdata 83376maxresident)k
460538inputs+0outputs (0major+311900minor)pagefaults 0swaps
 
$ export OMP_THREAD_LIMIT=1
$ find | grep jpg | time parallel tesseract {} foo
Tesseract Open Source OCR Engine v5.0.0-alpha-781-gb19e3 with Leptonica
:
Tesseract Open Source OCR Engine v5.0.0-alpha-781-gb19e3 with Leptonica
25.30user 1.28system 0:09.53elapsed 278%CPU (0avgtext+0avgdata 83364maxresident)k
460538inputs+0outputs (0major+311855minor)pagefaults 0swaps

Så på min 2C4T Core i5 siger tiderne:

ProgramTidTid som x (x=10 sec)
Single threaded (ST) Tesseract kørt i parallel9.5 sx
Multi threaded (MT) Tesseract kørt en af gangen16.4 sxx
Multi threaded (MT) Tesseract kørt i parallel460 sxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Så det bliver ikke blot en smule langsommere, men 30x langsommere at køre MT Tesseract i parallel end at køre MT Tesseract i seriel og 50x langsommere end at køre ST Tesseract i parallel.

Nu har jeg jo også en 64C64T maskine, så jeg testede også lige hvor lang tid det tager at køre fra 1 til 80 MT og ST Tesseract i parallel. 64 cores giver muligheden for at tegne en graf som denne (sekunder vs antal parallelle processer):

Illustration: (CC-By-SA) Ole Tange

Hvis jeg kører færre end 20 processer i parallel, er MT hurtigst; ved 20-30 er de ca. lige hurtige, og ved over 30 i parallel er ST hurtigst.

Grafen for ST Tesseract er præcis som jeg forventer ved parallelisering af single trådede programmer, der CPU-tunge. Men halen af MT-grafen er godt nok vild; Hvordan hulen kan ST Tesseract i parallel være 50x hurtigere end MT Tesseract i parallel? Det må jo betyde, at MT Tesseract på en eller anden måde går i vejen for sig selv, hvis der kører flere i parallel.

strace giver et hint: Når tiderne går helt amok for MT, udføres der en masse futex, som fejler. De fejler ikke, når tiderne er lave. Så det ser ud til, at futex går i vejen for sig selv.

Nu er jeg ikke den store futex-ekspert, men jeg havde regnet med at futex var begrænset til den enkelte bruger. Men det er ikke tilfældet her. Grafen ovenfor gælder også, hvis processerne udføres som forskellige brugere.

I praksis er der kun 2 realistiske brugsscenarier: Enten vil du gerne have processet een fil hurtigst muligt, og så skal du vælge MT Tesseract og køre een process, eller også har du en bunke filer og vil gerne udnytte alle dine cores og så skal du køre en ST Tesseract per core i parallel.

Jeg har skrevet til Tesseract og bedt dem overveje, om de automatisk kunne skifte mellem MT og ST, f.eks. ved at Tesseract starter som ST, hvis der kører andre Tesseract samtidigt og kører MT hvis der ikke kører andre Tesseract processer.

Nu får vi se, om det kommer med i næste version af Tesseract, så man kan bruge Tesseract med GNU Parallel uden at skulle kende til grafen ovenfor.

Kommentarer (13)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#1 Magnus Jørgensen

Problemet ligger vel i at der er for meget ram der deles med futex. OCR skulle da være nærmest 100% parralleliserbart, hvis man altså først har opdelt opgaven. Da burde opgaven kunne deles ud til hver process således at de kan løse opgaven uden at dele ram.

  • 0
  • 0
#2 Troels Henriksen

En futex bruges som regel bare til at implementere en lås, så mit gæt er at MT Tesseract har intern synkronisering af en eller anden delt resurse (stdout? Allokator? Input?), som der er alt for høj contention på. Hvis man har flere ST Tesseract-processer har de hver deres kopi af resursen, og derfor intet behov for synkronisering.

Jeg har kun lige søgt overfladisk rundt i koden, men når jeg ser sådan noget her, så bliver jeg bekymret. Det er en basal getter-metode der alligevel lige tager en lås mens den læser et trivielt felt fra objektet. Mit gæt er at Tesseract oprindeligt var enkelttrådet, og da man så paralleliserede det senere, gjorde man det på en ret brutal måde ved at over-låse forskellige dele af dets interne datastrukturer.

Det er stort set altid nemmere og mere effektivt at parallelisere over forskellige stykker input (sådan som GNU Parallel gør det), end det er at parallelisere internt i ét job, sådan som Tesseract ser ud til at gøre det.

  • 11
  • 0
#3 Sune Marcher

I praksis er der kun 2 realistiske brugsscenarier: Enten vil du gerne have processet een fil hurtigst muligt, og så skal du vælge MT Tesseract og køre een process, eller også har du en bunke filer og vil gerne udnytte alle dine cores og så skal du køre en ST Tesseract per core i parallel.

Der kunne vel også være noget med M processer med N tråde per proces, muligvis core-pinned... men det kommer super meget an på det workload man kører.

Og hvis Troels' lock-eksempel er gennemgribende for kodebasen, så... ugh.

  • 2
  • 0
#4 Poul-Henning Kamp Blogger

Der kunne vel også være noget med M processer med N tråde per proces, muligvis core-pinned... men det kommer super meget an på det workload man kører.

Problemet er at de atomic instruktioner man implementerer locks mellem threads med er globale, de kan ikke vide hvilke andre cores der kører relevante threads på, så de har performance impact på alle andre cores.

Derfor er N×ST formodentlig det optimale, når man har væsentlig flere cores end programmet selv kan udnytte fornuftigt.

  • 4
  • 0
#5 Sune Marcher

Problemet er at de atomic instruktioner man implementerer locks mellem threads med er globale, de kan ikke vide hvilke andre cores der kører relevante threads på, så de har performance impact på alle andre cores.

Hvis du har en eller anden shared cloud resource hvor du ikke aner hvad der ellers kører, well... :-)

Hvis du har dedikeret hardware kan du selv styre hvad du launcher på hvilke cores, men det kræver naturligvis at det giver mening med dit workload, at du ved hvad du laver og at softwaren er designet til det.

Det lader det ikke umiddelbart til at Tesseract er :-)

  • 2
  • 0
#6 Troels Henriksen

Hvis du har dedikeret hardware kan du selv styre hvad du launcher på hvilke cores, men det kræver naturligvis at det giver mening med dit workload, at du ved hvad du laver og at softwaren er designet til det.

Selv med min egen hardware, så har jeg ikke specielt meget kontrol over hvad der kører hvor, når jeg starter noget data-analyse i nogle baggrundsprocesser, mens jeg starter min browser op for at trolle på Version 2. Det er ret få programmer der kan antage at de køres på dedikeret maskineri, og det er bestemt ikke nemt at lave en form for dynamisk styring af hvor mange tråde der skal bruges til beregningsintensive opgaver på et delt system. Faktisk er jeg ikke bekendt med nogen der bare er i nærheden af at have et godt greb om hvordan det skal løses.

  • 5
  • 0
#7 Sune Marcher

Selv med min egen hardware, så har jeg ikke specielt meget kontrol

Jeg er delvis enig – altså, det er forholdsvist nemt at kontrollere hvad der kører hvor, men det risikerer at give dårligere i stedet for bedre performance.

Hård performance-tuning er svært, fordi der er forbandet mange parametre der har indflydelse. Og med det de fleste af os laver til dagligt, er den mest fornuftige løsning at holde koden simpel og så skalere ud :-)

  • 1
  • 0
#8 Nis Schmidt

Hvis man kører flere ST (single thread) processer samtidigt med uafhængige data kan det sagtens være hurtigere end at køre flere MT (multi-thread) under de samme forhold.

Hvis en MT-process f.eks. kan udnytte samtlige kerner 100%, får man næppe noget ud af at køre flere MT-processor samtidigt.

Præcis hvad der går galt kan være svært at afgøre. Det kan være cache-koherens der kikser, men det kan også være så simpelt som adgang til L1-cache linjer. Det er kun 512 CL til rådighed (1024 på AMD) per core.

Derfor har nogle (IBM z13 og senere) større L1-caches.

For nylig havde jeg et køretidsproblem, som viste sig at bunde i 8-byte integers vs 4-byte. Det tog 3+ så lang tid med 8-byte integers. Der mistænker jeg cache-problemer.

De tider hvor man kunne glemmer at compilere med /MU (multi-user) er jo forlængst forbi.

  • 1
  • 0
#9 Sune Marcher

Hvis en MT-process f.eks. kan udnytte samtlige kerner 100%, får man næppe noget ud af at køre flere MT-processor samtidigt.

Jep... men du kan vel risikere at det der bliver rapporteret som 100% usage på én core i virkeligheden staller i stedet for at lave noget fornuftigt? – hvis du kigger på dit OS's task manager og ikke fx VTune.

I de gode gamle Pentium-dage var det forholdsvist trivielt at optimere – du havde instruction cycle counts og U og V pipes... fra PPro og fremefter blev det mere og mere black magic, og selv med godt arkitekturkendskab og håndkodet assembly er du i dag nødt til at have lowlevel profiling.

Hvis man kan lide at nørde den slags, kan jeg anbefale at fidne Fabian Giesen (også kendt som ryg/Farbrausch)'s blog og eventuelt følge ham på Twitter – der har været nogle ret interessante indlæg :-)

  • 1
  • 0
#11 Ole Tange Blogger

Hvis en MT-process f.eks. kan udnytte samtlige kerner 100%, får man næppe noget ud af at køre flere MT-processor samtidigt.

[...cache problemer...]

Jeg startede selv ned af den tankerække. Men jeg kan ikke få det til at passe med grafen.

MT Tesseract bruger 2-3 cores, når den kører alene på en 64C64T maskine. Det passer godt med grafen, hvor den bedste performance for MT ligger på 20-30 samtidige processer.

Grafen for ST Tesseract stopper ved 90, men den fortsætter med at ligge på samme lave niveau ved både 128, 192, 256, 512 og 1024 processer i parallel.

Hvis Tesseract smadrer cachen, så ville jeg forvente, at mange samtidige ST Tesseract også smadrer cachen. Og da 1 MT Tesseract bruger 2-3 processer, så ville jeg forvente, at 64 MT Tesseract ville være lige så langsom som 128-192 ST Tesseract kørt i parallel.

Dette er ikke tilfældet.

  • 0
  • 0
#12 Ivo Santos

Er det en tråd per billede, eller er det flere tråde per billede?

Jeg kom til at tænke på cpu cache problematikken i denne youtube video code::dive conference 2014 - Scott Meyers: Cpu Caches and Why You Care

Citat fra følgende side "https://github.com/tesseract-ocr/tesseract/issues/1600":

If your computer has only two CPU cores, then running four threads will slow down things significantly and it would be better to use a single thread or maybe a maximum of two threads! Using a single thread eliminates the computation overhead of multithreading and is also the best solution for processing lots of images by running one Tesseract process per CPU core.

Når man tænker på at alle tråde i en processor deler det samme cache hukommelse, så passer det vel med at det tager længere tid når man benytter, hvad der svarer til, mere end i tråd per processor. Det burde vel så også passe med at det køre langsomere når man benytter over 64 tråde i en 64 core processor.

I teorien burde det være hurtigere at gennemgå 80 billeder med en tråd per billede i forhold til at gennemgå 20 billeder, med 4 tråde per billede, af gangen, da man med en tråd per billede ungår at bruge en en lås som kan koste på tiden vel fordi de fire tråde vel gemmer til den samme delte hukommelse, hvilken en tråd per billede ikke gør. Og så skal man vel også tænke på at de 2 tråde deler den samme cache, så i teorien har man kun 16 kilobyte per tråd når man f.eks. kører 128 tråde på en 64 core processor. Til gengæld, så har man 32 kilobyte per tråd når man kører med 64 tråde på en 64 core processor.

  • 0
  • 0
#13 Nis Schmidt

Hej Ole!

Den blå kurve er et skoleeksempel på MT "cache collision" (som forklaret af #12), men den røde kurve???

Hvad havde du gjort? jeg gætter på talrige STer med samme input fil;)

2+ tråde per kerne er i praksis "timeshare" og virker kun i sameksistens med rigelig I/O.

  • 0
  • 0
Log ind eller Opret konto for at kommentere