Analiza komutativnosti

Povzetek

 

Vzporedni stroji ponujajo obljubo o znatnem povečanju zmogljivosti, saj omogočajo več procesorjev hkrati izvajati različne dele računanja. Programatorji so tradicionalno razvili aplikacije za vzporedne stroje, ki uporabljajo eksplicitno vzporedne jezike. Za razliko od serijskih programskih jezikov, eksplicitno vzporedni jeziki predstavljajo kompleksen programski model, za katerega so značilni takšni pojavi kot zastoj, nedeterministična izvedba in na strojih, ki prenašajo sporočila, potrebo po neposrednem upravljanju gibanja podatkov z računanjem. Očitne prednosti programiranja sekvenčne imperativnega programskega paradigma so zato navdihnile razvoj analiznih tehnik in prevajalnikov, ki so avtomatično vzporedni s serijskimi programi.

Tekoči vzporedni prevajalniki ohranjajo semantiko izvirnega serijskega programa, tako da ohranijo podatkovne odvisnosti. Ti prevajalniki poskušajo identificirati neodvisne dele računanja (dva dela računanja sta neodvisni, če ne piše podatkov, ki jih drugi dostopa), nato pa ustvarjajo kodo, ki hkrati izvaja neodvisne elemente. Pomembna omejitev tega pristopa je težava opravljanja analize odvisnosti, ki je dovolj natančna, da razkrije znatne količine vzporednosti. Medtem ko so raziskovalci lahko razvili razumno učinkovite algoritme za zanke, ki manipulirajo z gostimi matricami z uporabo afinitetnih funkcij dostopa, je bil dosežen majhen napredek pri uspešni avtomatični analizi programov, ki manipulirajo na podatkovnih strukturah, ki temeljijo na kazalcu. Raziskovalci so poskušali zgraditi popolnoma avtomatske sisteme, vendar najbolj obetavni pristopi zahtevajo od programerja, da zagotovi opombe, ki določajo informacije o globalni topologiji manipuliranih podatkovnih struktur. Druga, bolj temeljna omejitev pristopov, ki temeljijo na podatkih, je nesposobnost, da se izračuni, ki manipulirajo z grafičnimi strukturami podatkov, paralelirajo. Pomenki, ki so prisotni v teh podatkovnih strukturah, onemogočajo statično odkritje neodvisnih kosov kode, s čimer se prevajalnik generira serijska koda. Nazadnje, ohranjanje podatkovnih odvisnosti za programe, ki redno posodabljajo strukture podatkov v skupni rabi, lahko umetno omejijo količino izpostavljene vzporednosti, ker naloge morajo odložiti posodobitve, dokler niso prepričani, da vsaka posodobitev ne bo spremenila relativnega reda bral in zapisala v podatkovno strukturo v skupni rabi .

Analiza komutativnosti je okvir statične analize za odkrivanje komutacijskih operacij. Dve operaciji premikata, ko ustvarjajo enake rezultate, ne glede na vrstni red, v katerem jih izvajajo. Analiza komutativnosti odpravlja številne omejitve obstoječih pristopov, ki temeljijo na podatkih. Namesto ohranjanja relativnega reda posameznih branij in zapisov na posamezne besede pomnilnika, analiza komutativnosti agregira podatke in računanje v velike enote zrn. Nato statično analizira izračun na tej granularnosti, da odkrije, kdaj se deli računanja premikajo, tj. Ustvarjajo enake rezultate, ne glede na vrstni red, v katerem jih izvajajo. Če so vsi postopki, potrebni za izvedbo določenega računanja, prevajalnik samodejno ustvari vzporedno kodo. Medtem ko vzporedni program, ki je posledica tega, lahko krši podatkovne odvisnosti prvotnega serijskega programa, še vedno zagotavlja enak rezultat.

Ta pristop ima več zanimivih lastnosti. Ker se analiza komutativnosti ne zanaša na informacije o topologiji manipuliranih podatkovnih struktur, prevajalnik, ki uporablja analizo komutativnosti, ni treba analizirati delov kode, ki gradijo podatkovno strukturo. Analiza komutativnosti je zato primerna za nepopolne izračune, kot so aplikacije, ki manipulirajo s trajnimi podatki (npr. Objektno usmerjene aplikacije baz podatkov) ali aplikacije, ki manipulirajo z geografsko razpršenimi podatki (npr. Mobilne izračune v svetovnem spletu). V teh primerih koda, ki je prvotno zgradila podatkovno strukturo, morda ni na voljo ali morda ne bo več. Analiza komutativnosti je še posebej primerna za izračune, ki manipulirajo z grafi. To je pomemben vidik analize komutativnosti, saj so izračuni, ki manipulirajo s temi podatkovnimi strukturami, sami po dosegu analize podatkovne odvisnosti.

Vzeli smo sistemsko usmerjen pristop, ki je ocenil sposobnost analize komutativnosti, da bi v celoti izkoristil in izkoristil znatne količine vzporednosti v celotnih aplikacijah. Izdelali smo vzporedni prevajalnik, ki uporablja analizo komutativnosti kot svojo glavno paradigmo analize. Ta prevajalnik ima kot vhod neenotiran zaporedni program, zapisan v podmnožici C + + in generira vzporedno kodo za multiprocesor v skupni pomnilnik. S pomočjo tega vzporednega prevajalnika samodejno vzporedimo več aplikacij, vključno s kodo za reševanje Barnes-Hut N-body, simulacijsko kodo za tekočo vodo in seizmično modelno kodo. Pri vseh teh aplikacijah, analiza komutativnosti lahko razkrije znatno količino vzporednosti in ustvarjena vzporedna koda kaže zelo dobre rezultate. Na 16 procesorjih samodejno vzporedna različica Barnes-Hut teče med 11 in 12-krat hitrejšo od prvotne zaporedne različice; za aplikacijo za simulacijo vode samodejno vzporedna različica poteka med 7 in 8-krat hitrejšo od prvotne zaporedne različice; za aplikacijo seizmičnega modeliranja samodejno vzporedna različica poteka približno 12-krat hitrejša od prvotne zaporedne različice.

Ti poskusni rezultati so zelo spodbudni. Te aplikacije so zelo dinamične narave – bodisi manipulirajo s sofisticiranimi podatkovnimi strukturami na kazalniku ali kažejo zelo nepravilne vzorce dostopa do podatkov. Izkoriščanje grobega paralelizma v aplikacijah s temi značilnostmi je bilo prepoznano kot zelo težka težava. Ne poznamo nobene druge metode prevajanja ali kompilacije, ki bi lahko izrabila znatne količine vzporednosti za te izračune. Poleg tega pozitivni eksperimentalni rezultati vsebujejo konkretne dokaze o praktičnem pomenu analize komutativnosti kot tehnike za avtomatske vzporedne prevajalce.

 


Sorodne publikacije

 

Original: https://www.isi.edu/~pedro/CA/commutativity.html

Leave a Reply

Your email address will not be published. Required fields are marked *