Nov algoritem za učinkovito izrabo jeder

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.