Nov algoritem za boljši izkoristek procesorjev s številnimi jedri

Strokovnjaki že lep čas opozarjajo, da je izdelava učinkovitih programov za sodobne procesorje, ki imajo vse večje število jeder, zelo zahtevna in težavna naloga. Zapleta se, ko je opravila treba dodeliti prostim jedrom, pri tem pa dosegati čim večji izkoristek, a obenem čim manj zastojev in konfliktov.

Pri procesorjih z razmeroma majhnim številom jeder se tipično uporablja čakalne vrste in dodeljevanje procesov prostim jedrom po principu FCFS (first come, first served). Tak pristop se danes množično uporablja v programski opremi za procesorje, ki premorejo dve, štiri, šest ali osem jeder.

Praktični preizkusi pa kažejo, da postanejo tovrstni algoritmi in režimi izvajanja neučinkoviti, ko imamo opravka s procesorji z več kot osmimi jedri. Takšni so današnji Intelovi procesorji, ki premorejo so 18 jeder. Obet pa je, da bomo že v bližnji prihodnosti naleteli na procesorje s tja do 80 jedri.

V univerzi MIT je skupina strokovnjakov razvila nov algoritem imenovan SprayList, ki se tega problema paralelizma izvajanja loteva na povsem drugačen način. Verjeli ali ne, temelj novega algoritma je domala naključno dodeljevanje procesov prostim jedrom, kar se je pri praktičnih preizkusih pokazalo nadvse učinkovito.

Na prvi pogled se zdi nelogično, saj naključno dodeljevanje lahko privede do konfliktov, napačne sekvence obdelave opravil itd. Toda algoritem zato ne potrebuje čakalne vrste, vodenje evidence vrstnega reda procesov, kar pri procesorjih z več kot osmimi jedri postane resna zavora.

SprayList opravila sicer ne izvaja povsem naključno, saj podpira razporejanje opravil v prioritetne razrede, s čimer lahko kljub vsemu zagotovimo pravočasnost obdelave kritičnih nalog. Laboratorijski preizkusi so pokazali, da se algoritem po pričakovanjih slabše odreže od čakalne vrste pri številu procesnih niti, ki je manjše od osem. Od tam dalje pa hitrost izvajanja povečuje linearno in predvsem bolj učinkovito od današnjih algoritmov.