» »

Nov algoritem za učinkovito izrabo jeder

Nov algoritem za učinkovito izrabo jeder

Slo-Tech - Raziskovalci na bostonskem MIT so razvili nov algoritem za paralelizacijo procesov, ki obljublja bistvene pohitritve pri srednje velikem številu jeder. Ugotovili so, da z naraščajočim številom jeder klasično zaporedno dodeljevanje procesov jedrom glede na čas zahtevka (first come first served) ne daje tako dobrih rezultatov kot preizkušeni, stari random.

Proizvajalci procesorjev so se v zadnjih letih posvetili povečevanju števila jeder v procesorjih, kar prinaša svojevrstne izzive za programerje. Tega ne počnejo, da bi nagajali, temveč ker jih je po glavi udarila fizika. Več kot nekaj gigahercev se iz posameznega jedra ne da iztisniti, zato je edini način za povečevanje zmogljivosti večanje števila jeder. Od programerjev pa je odvisno, kako bodo to vojsko paralelnih vojščakov zaposlili.

Danes večjedrni procesorji večinoma jedrom dodeljujejo procese po sistemu kdor prej pride, prej melje. Na prvo prosto jedro se preseli proces, ki je prvi v čakalni vrsti (seveda se upoštevajo tudi prioritete). To za manjše število jeder deluje dobro, pri večjem številu jeder pa postaneta ozko grlo sinhronizacija čakalnih vrst med jedri ter primeri, ko isti proces istočasno zahtevata dve jedri. Dodatne težave povzroča predpomnilnik na jedru, ki se mora ob vsaki spremembi prvega procesa osvežiti na vseh jedrih, kar upočasni sistem. Osemnajstjedrni procesorji so za ovinkom, zato je težava čedalje bolj pomembna.

MIT-ovi raziskovalci so v svojem članku nov algoritem poimenovali SprayList. Če prostemu jedru nov proces dodelimo naključno iz vrste vseh čakajočih, je to pri manjšem številu jeder seveda neoptimalna rešitev. Toda ko število jeder preseže deset, postane ta način hitrejši od klasične čakalne vrste. Trkov je namreč precej manj, kar prihrani precej mrtvega teka, ki je prej šel za sinhronizacijo čakalnih vrst in predpomnilnika po jedrih.

23 komentarjev

Tr0n ::

Pise kje koliko hitreje je tole v primerjavi s staro metodo?

pegasus ::

Odvisno od tega kaj in kako to počneš.
Also če ne znaš sam izmeriti, potem se ti verjetno ni potrebno ukvarjati s tem :)

Tr0n ::

Jah, da pac pozenejo isto multithreaded aplikacijo in gledajo, kako hitro sprocesira nek task na istem stevilu jeder z razlicnima algoritma. :)

Zgodovina sprememb…

  • spremenilo: Tr0n ()

jype ::

To ni dobra metodologija. Načeloma hočeš scheduler, ki zna CPU bound threade pinat na core...

OK, naj poskusim še enkrat: Načeloma hočeš razvrščevalnik, ki zna procesorsko intenzivne niti prilepit na jedra in tako dalj časa ohraniti vsebino predpomnilnika. Za ostale niti (tiste, ki večino časa čakajo na zunanje dogodke kot so diski, tipkovnice, mreža in podobne) je verjetno naključno razporejanje dovolj dobro.

pegasus ::

Eno luštno orodje, ki ga priporočam za tovrstno igranje in eksperimentiranje je likwid - like i know what i'm doing :D

_Dormage_ ::

Tr0n je izjavil:

Pise kje koliko hitreje je tole v primerjavi s staro metodo?

V članku.

Jarno ::

Ne vidim neke revolucije, bolj evolucijo.
Sicer pa bi lahko operacijski sistem izbiral med načini razvrščanja, glede na število jeder pač.

pegasus ::

To dela že sedaj, precej dobro za večino primerov. Za tiste redke izjeme rečeš kernelu "laufaj na samo teh dveh corih in pusti ostale pri miru" ter potem sam ročno delaš process placement na core. To počnejo recimo HFT ljudje, ker jim tistih nekaj mikrosekund migracije procesa iz enega cora na drugega lahko odnese miljone $ ;)

Qushaak ::

Opisan algoritem spada v "kategorijo" s tistim, da se ohranja stopnja kompresije s povečevanjem števila jeder, ki kompresirajo naenkrat. :) Orenk doprinos na tem področju bi bilo zrelo za Nobelovo nagrado.

pegasus ::

Na tem področju se dela ogromno, a so zadeve relativno akademske in težko prodrejo do nekega consumer segmenta. Batch job scheduling je aktualna tema že vsaj od šestdesetih let ... Trenutno so zanimive rešitve, ki analizirajo data flow med jobi, iz tega naredijo DAGe in na podlagi teh potem delajo scheduling z namenom, da se celota izvede kar se da hitro.

Če bi cpu ukazi imeli dovolj metapodatkov, da bi se tak razmislek lahko izvedlo tudi med njimi, bi bilo danes marsikaj drugače ;)

noraguta ::

pegasus je izjavil:

To dela že sedaj, precej dobro za večino primerov. Za tiste redke izjeme rečeš kernelu "laufaj na samo teh dveh corih in pusti ostale pri miru" ter potem sam ročno delaš process placement na core. To počnejo recimo HFT ljudje, ker jim tistih nekaj mikrosekund migracije procesa iz enega cora na drugega lahko odnese miljone $ ;)

procesno afiniteto dolofjo kar lepo programsko.
Pust' ot pobyedy k pobyedye vyedyot!

Qushaak ::

pegasus je izjavil:

Na tem področju se dela ogromno, a so zadeve relativno akademske in težko prodrejo do nekega consumer segmenta. Batch job scheduling je aktualna tema že vsaj od šestdesetih let ... Trenutno so zanimive rešitve, ki analizirajo data flow med jobi, iz tega naredijo DAGe in na podlagi teh potem delajo scheduling z namenom, da se celota izvede kar se da hitro.

Če bi cpu ukazi imeli dovolj metapodatkov, da bi se tak razmislek lahko izvedlo tudi med njimi, bi bilo danes marsikaj drugače ;)

Z vsem se strinjam, samo taki procesorji so sedaj tudi v najnižjem cenovnem segmentu (v šestdesetih je bil pa to itak samo "mainframe segment").

AndrejO ::

jype je izjavil:

To ni dobra metodologija. Načeloma hočeš scheduler, ki zna CPU bound threade pinat na core...

OK, naj poskusim še enkrat: Načeloma hočeš razvrščevalnik, ki zna procesorsko intenzivne niti prilepit na jedra in tako dalj časa ohraniti vsebino predpomnilnika. Za ostale niti (tiste, ki večino časa čakajo na zunanje dogodke kot so diski, tipkovnice, mreža in podobne) je verjetno naključno razporejanje dovolj dobro.

Zeh, to že imamo (zahvala gre Ingi Molnarju). Pa lahko bi bil dosleden in lepo povedal, da je težava v pomnilniško intenzivnih procesih, ne pa nitih. Če boš eno nit pomotoma sprožil na napačnem jedru, potem lahko rečeš adijo vsem prihrankom iz naslova "vročega" L2 predpomnilnika. L3 je pa na namizjih tako ali tako deljen med vsemi jedri in bo zadovoljivo "požrl" x264 kodiranje tudi, če se bo to sprehajalo med jedri.

Sicer pa je razvrščanje procesov med procesorje zelo dobra vaja za vse, ki si mislijo, da obvladajo strukture in algoritme. Konkreten primer je tako pokazal kakšno je tveganje bolj kompleksnih algoritmov, če jim časovna zahtevnost prekomerno narašča z večanjem števila razpoložljivih ponorov za vrsto ali vrste.

Brane22 ::

Čudne razlage v članku.

Tudi ni jasno, zakaj bi v taki many-core mašini uporabljal klasični scheduler.

V majhnih strojčkih, ki so vezani na človeški čut za real-time je nekako jasno zakaj se taski menjajo na par do pardeset ms. Ampak zakaj bi tako na drobno sekal timeslote na many-core mašini ?

Če so pa taskswitchi bistveno redkejši, potem ej tudi možnih sinhronizacij manj.

Tudi ni jasno pojasnjeno, kako naj bi ta metoda pokrila stalno refilanje cachejev, vsakič na nekem random coreu...

AndrejO ::

Brane22 je izjavil:

Čudne razlage v članku.

S-T povzetku ali v originalu? Ker original se mi bere čisto razumljivo.

Brane22 je izjavil:

Tudi ni jasno, zakaj bi v taki many-core mašini uporabljal klasični scheduler.

Ker je prihodnost v takšnih "many-core mašinah". Algoritem pa je en izmed možnih današnjih. Če želiš biti tudi v prihodnosti učinkovit (da ne rečem konkurenčen), potem moraš že danes ugotavljati kaj bo potrebno zamenjati, kaj pa ne.

Brane22 je izjavil:

V majhnih strojčkih, ki so vezani na človeški čut za real-time je nekako jasno zakaj se taski menjajo na par do pardeset ms. Ampak zakaj bi tako na drobno sekal timeslote na many-core mašini ?

Zato, ker se proučuje današnje algoritme, da se ugotovi, če so primerni za prihodnjo strojno opremo.

Brane22 je izjavil:

Če so pa taskswitchi bistveno redkejši, potem ej tudi možnih sinhronizacij manj.

Ker se hitrosti enega jedra več ne more večati, se bo moralo delati paralelne algoritme, ti pa se morajo med seboj praviloma sinhronizirati, pri temu pa tudi izmenjevati podatke.

Ker bo navideznih procesov M vedno več, kot pa razpoložljivih jeder N, bo problem ostal aktualen, ker verjetno ne boš želel v nedogled oziroma predolgo odlašati z izvrševanjem naslednjega procesa v vrsti.

Brane22 je izjavil:

Tudi ni jasno pojasnjeno, kako naj bi ta metoda pokrila stalno refilanje cachejev, vsakič na nekem random coreu...

Scheduling nima ničelnega stroška iz vidka porabe ciklov in pomnilnika. Pri nekaterih algoritmih lahko ta strošek z večanjem števila niti preseže strošek obnavljanja predpomnilnika pri večjem številu slabo razporejenih niti.

Brane22 ::

AndrejO je izjavil:


Brane22 je izjavil:

Tudi ni jasno, zakaj bi v taki many-core mašini uporabljal klasični scheduler.

Ker je prihodnost v takšnih "many-core mašinah". Algoritem pa je en izmed možnih današnjih. Če želiš biti tudi v prihodnosti učinkovit (da ne rečem konkurenčen), potem moraš že danes ugotavljati kaj bo potrebno zamenjati, kaj pa ne.


Saj to vem. Ampak zakaj bi bila prihodnost v klasičnem schedulerju ?

Zakaj točno moraš menjati task na vsakem coreu na xxx ms ?

Za mnogo taskov in par corev, ki morajo dati lokalni opici občutek, da tečejo sočasno, to razumem.

Zakaj naj bi bilo to potrebno na takih strojih ?

Brane22 ::

AndrejO je izjavil:


Zato, ker se proučuje današnje algoritme, da se ugotovi, če so primerni za prihodnjo strojno opremo.



Ker se hitrosti enega jedra več ne more večati, se bo moralo delati paralelne algoritme, ti pa se morajo med seboj praviloma sinhronizirati, pri temu pa tudi izmenjevati podatke.


To ni odgovor na moje vprašanje. Vedno imaš ta problem, od prvih strojev do danes. Moje vprašanje je bilo, zakaj bi moral imeti scheduler, kis talno rpemetava procese na takem stroju. Razumem da alociraš izbrani core glede na pričakovani I/O, počiš gor program in poženeš zadevo. Zakaj bi jo med delom moral intenzivno premetavati po siliciju, mi ni jasno.


Ker bo navideznih procesov M vedno več, kot pa razpoložljivih jeder N, bo problem ostal aktualen, ker verjetno ne boš želel v nedogled oziroma predolgo odlašati z izvrševanjem naslednjega procesa v vrsti.


V bistvu ne bo vedno. Če bo ta presežek procesov odvisen od človekovih reakcij, potem ja. Lahko ga bom zaprl v neko majhno grupo in tam izvajal žongliranje. Prestanek več ali manj komot dela, dokler ne konča.

Ni nobene prednosti v žngliranju programov, da dajejo videz sočasnosti, če v to ne zre človek, kateri bi jo lahko dojel.


Scheduling nima ničelnega stroška iz vidka porabe ciklov in pomnilnika. Pri nekaterih algoritmih lahko ta strošek z večanjem števila niti preseže strošek obnavljanja predpomnilnika pri večjem številu slabo razporejenih niti.


A. Tam nek corner case. Who cares.

AndrejO ::

Brane22 je izjavil:

Saj to vem. Ampak zakaj bi bila prihodnost v klasičnem schedulerju ?

Kolikor jaz vidim, ne obstaja "klasičen scheduler", obstaja več različnih, ki so se s časom izkazali za uporabne.

Brane22 je izjavil:

Zakaj točno moraš menjati task na vsakem coreu na xxx ms ?

Schedulerji že danes več niso tako tako zelo naivni.

Brane22 je izjavil:

Za mnogo taskov in par corev, ki morajo dati lokalni opici občutek, da tečejo sočasno, to razumem.

Zakaj naj bi bilo to potrebno na takih strojih ?

Hkrati pa še vedno ohranjajo "kvant", preprosto zato, ker je za vnaprej neznano število število procesov, z neznanimi lastnostmi takšne lažje implementirati, saj v povprečju enako neoptimalno oddelajo karkoli jim vržeš v obraz.

"Takšni stroji" so še vedno splošnonamenski kalkulatorji. Splošnonamenski je tukaj ključen pridevnik. Če imaš vnaprej znane lastnosti dela, ki ga bodo posamezni procesi opravljali, lahko seveda spišeš lasten algoritem, ki jih bo razporedil bistveno bolj optimalno.

Brane22 je izjavil:

To ni odgovor na moje vprašanje. Vedno imaš ta problem, od prvih strojev do danes. Moje vprašanje je bilo, zakaj bi moral imeti scheduler, kis talno rpemetava procese na takem stroju. Razumem da alociraš izbrani core glede na pričakovani I/O, počiš gor program in poženeš zadevo. Zakaj bi jo med delom moral intenzivno premetavati po siliciju, mi ni jasno.

Do sedaj se je ta pristop pokazal za najbolj uporabnega, kadar moraš M procesov stlačiti na N procesrojev, pri čemer ne veš kaj počno, kako to počno in kaj bodo počeli naslednji trenutek, pri temu pa poskušaš biti "pošten". Za vse ostalo imaš RTOS, ki teh zgodb nima.

Brane22 je izjavil:

V bistvu ne bo vedno. Če bo ta presežek procesov odvisen od človekovih reakcij, potem ja. Lahko ga bom zaprl v neko majhno grupo in tam izvajal žongliranje. Prestanek več ali manj komot dela, dokler ne konča.

Na mojem namizju ta trenutek teče več kot 50 procesov. Odprtih imam nekaj oken spletnih brskalnikov, e-pošto in putty.

Brane22 je izjavil:

Ni nobene prednosti v žngliranju programov, da dajejo videz sočasnosti, če v to ne zre človek, kateri bi jo lahko dojel.

Na drugi strani je vedno človek, ki čaka na rezultat. Pri temu operacijski sistem nima pojma kakšen rezultat in kakšnega procesa. Splošnonamenski pomeni tudi "neoptimalen".

Brane22 je izjavil:

A. Tam nek corner case. Who cares.

Očitno tisti, ki jih zanima kaj bo delovalo na namiznem "stroju", ko bo ta imel 20+ jeder.

Zgodovina sprememb…

  • spremenil: AndrejO ()

Brane22 ::

AndrejO je izjavil:


Kolikor jaz vidim, ne obstaja "klasičen scheduler", obstaja več različnih, ki so se s časom izkazali za uporabne.


Ki so. glede na to kar bo potrebno, "klasika".


Brane22 je izjavil:

Zakaj točno moraš menjati task na vsakem coreu na xxx ms ?

Schedulerji že danes več niso tako tako zelo naivni.


Točno. In če ti tega ni treba, kje je potem schedulerja ?


Hkrati pa še vedno ohranjajo "kvant", preprosto zato, ker je za vnaprej neznano število število procesov, z neznanimi lastnostmi takšne lažje implementirati, saj v povprečju enako neoptimalno oddelajo karkoli jim vržeš v obraz.


No, in tle leži področje, kjer se bodo stvari izboljševale in dorekale.


Do sedaj se je ta pristop pokazal za najbolj uporabnega, kadar moraš M procesov stlačiti na N procesrojev, pri čemer ne veš kaj počno, kako to počno in kaj bodo počeli naslednji trenutek, pri temu pa poskušaš biti "pošten". Za vse ostalo imaš RTOS, ki teh zgodb nima.


Emphasis na "do sedaj". Sedaj pa se bo to bistveno spremenilo. Stroj bo imel coreov več ko dovolj za pokritje "realtime" procesov, za primankljaj bo pa itak bistveno bolj vseeno, če se konča do izteka.

Res je, da ob skoku v kernel (klicu sistemske funkcije) lahko nujen scheduler preskok, ker stvar recimo blocka ( čakaš, da se fajl odpre recimo) ampak to je že danes urejeno (non-blocking syscalls, ali pa recimo odprtje dodatneih rezervnih delovnih threadov itd).


Na mojem namizju ta trenutek teče več kot 50 procesov. Odprtih imam nekaj oken spletnih brskalnikov, e-pošto in putty.


kar bo prdec za manycore. Imel boš recimo 2000 coreov, če sem rpav razumel in 200 jih bo pokrivalo tvoje realtime potrebe, ostali pa dela v ozadju.


Na drugi strani je vedno človek, ki čaka na rezultat. Pri temu operacijski sistem nima pojma kakšen rezultat in kakšnega procesa. Splošnonamenski pomeni tudi "neoptimalen".


ja, ampak ta človek lahko čaka,d a recimo simulator opravi svoje. Ali autorouter. Ali compiler itd. Ne čakajo njegove oči, torej je vseeno za "real-time" animacijo. Torej programi komot lahko laufajo na istem jedru, dokler ne konča ali dokler ne zafila bufferja z rezultati, potrebnimi drugje.

Ah, čaki - "_srednje_ velikem številu jeder". Šele sedaj mi je to padlo v oči.

Se pravi, to ni najava neke revolucionarne pridobitve, bolj tweak, ki bo šel v naslednji scheduler ?

Meh.

Zgodovina sprememb…

  • spremenilo: Brane22 ()

Brane22 ::

Poleg tega, nisem ziher,d a bo to končalo v naslednjem kernelu nespremenjeno.

Ali da bo bistveno, tudi če tja pride. Pravijo, da se scheduler bistveno bolje obnaša, če neke informacije o taskih nima, kot če jo ima. Če je tako, je pač sedanja implementacija v tem delu blesava.

Težko vidim argument da je bolje določenega kriterije pri odločitvah ne uprabljati kot uporabiti.

Razen, če si braindamaged in nesposoben spremembe in so se pač navadili, da je bolje, če ti ne povedo.

noraguta ::

brane sej lohk že dolg oženiš proces in procesor. se pa to ne splača počet glih za vsako inštanco chrometa. pa ni velikega haska, če je proces pretirano klepetav z drugimi procesi.
Pust' ot pobyedy k pobyedye vyedyot!

Ahim ::

... ko isti proces istočasno zahtevata dve jedri.


Kako pa jedro zahteva proces?

Prvo jedro: "Ej scheduler, jaz hocem tainta proces!"
Drugo jedro: "Tisina tam, JAZ hocem taisti proces!"

jype ::

AndrejO> Zeh, to že imamo

Ja, ampak random scheduler to ni več (in preizkus, kjer meriš čas, potreben za zaključek dalj časa trajajočega opravila, je slab).


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Nov algoritem za učinkovito izrabo jeder

Oddelek: Novice / Procesorji
236838 (3975) jype
»

Na MIT-u predstavili 36-jedrni procesor

Oddelek: Novice / Procesorji
276508 (3771) pegasus
»

Windows Phone po novem podpira štirijedrnike

Oddelek: Novice / Windows Mobile
196281 (4049) LitralSM
»

Intel pokazal koncept procesorja z neposredno komunikacijo med jedri

Oddelek: Novice / Procesorji
154160 (2923) Jst
»

Intel govori o Westmereih

Oddelek: Novice / Procesorji
204377 (3377) Dr_M

Več podobnih tem