Original: https://www.isi.edu/~pedro/CA/commutativity.html
Sažetak
Paralelne mašine nude obećanje o značajnom povećanju performansi omogućujući višestrukim procesorima da istovremeno izvršavaju različite dijelove računanja. Programeri su tradicionalno razvijali aplikacije za paralelne mašine koje koriste izričito paralelne jezike. Za razliku od serijskih programskih jezika, izričito paralelni jezici predstavljaju složen model programiranja karakteriziran takvim pojavama kao što su zastoj, neefikasno izvršavanje i, na strojevima za prijenos poruka, potreba za direktnim upravljanjem kretanjem podataka računanjem. Očigledne programske prednosti sekvencijalne imperativne programske paradigme pokrenule su, dakle, razvoj tehnika analize i prevodilaca dizajniranih za automatsku paralelizaciju serijskih programa.
Trenutni paralelni prevoditelji čuvaju semantiku izvornog serijskog programa čuvanjem ovisnosti podataka. Ovi prevoditelji pokušavaju identificirati neovisne dijelove izračuna (dva dijela računanja su neovisna ako niti jedan ne upiše dio podataka koji drugi pristupaju), a zatim generiraju kod koji istodobno izvršava nezavisne dijelove. Značajno ograničenje ovog pristupa je poteškoća u provođenju analize ovisnosti koja je dovoljno precizna da se razotkriju znatne količine istodobnosti. Dok su istraživači uspjeli razviti razumno efikasne algoritme za petlje gnijezda koja manipuliraju gustim matricama koristeći funkcije srodnih pristupa, ostvaren je mali napredak u uspješnoj automatskoj analizi programa koji manipuliraju strukturama podataka zasnovanim na pokazivačima. Istraživači su pokušali da izgrade potpuno automatske sisteme, ali najperspektivniji pristupi zahtijeva od programera da dostavi napomene koje određuju informacije o globalnoj topologiji manipuliranih struktura podataka. Drugo, temeljnije ograničenje pristupa zasnovanih na zavisnosti od podataka je nemogućnost paralelizacije računanja koja manipuliraju strukturama podataka sličnih grafovima. Nadimci koji su inherentno prisutni u tim strukturama podataka onemogućavaju statičko otkrivanje neovisnih dijelova koda, prisiljavajući prevodilac da generira serijski kod. Konačno, očuvanje ovisnosti podataka za programe koji periodično ažuriraju zajedničke strukture podataka može umjetno ograničiti količinu izložene istodobnosti, jer zadaci moraju odgoditi ažuriranja sve dok nisu sigurni da svako ažuriranje neće promijeniti relativni redoslijed čitanja i upisivanja u zajedničku strukturu podataka.
Analiza komutativnosti je okvir statičke analize za otkrivanje operacija na putu do posla. Dvije operacije mijenjaju se kad generiraju isti rezultat bez obzira na redoslijed kojim se izvršavaju. Analiza komutativnosti eliminira mnoga ograničenja postojećih pristupa utemeljenih na podacima, umjesto očuvanja relativnog poretka pojedinačnih čitanja i upisivanja u pojedinačne memorijske riječi, komutativnost analizom objedinjuje i podatke i izračunavanje u velike jedinice zrna. Zatim statistički analizira izračunavanje pri ovoj preciznosti kako bi otkrio kada komadi računanja tvore, tj. Generiraju isti rezultat bez obzira na redoslijed kojim se izvršavaju. Ako su sve operacije potrebne za obavljanje određenog računanja, prevodilac može automatski generirati paralelni kôd. Iako rezultirajući paralelni program može narušiti podatkovne ovisnosti izvornog serijskog programa, još uvijek je zajamčeno da će stvoriti isti rezultat.
Ovaj pristup ima nekoliko zanimljivih svojstava. Budući da se analiza komutativnosti ne oslanja na informacije o topologiji manipuliranih struktura podataka, prevodilac koji koristi analizu komutativnosti ne mora analizirati dijelove koda koji grade strukturu podataka. Analiza komutativnosti je stoga pogodna za nepotpune proračune, poput aplikacija koje manipuliraju postojanim podacima (npr. Objektno orijentirane baze podataka) ili aplikacije koje manipuliraju geografski disperziranim podacima (npr. Mobilni računi na World Wide Webu). U tim slučajevima kôd koji je izvorno izgradio strukturu podataka možda neće biti dostupan ili možda više ne postoji. Analiza komutativnosti je posebno pogodna za računanja koja manipuliraju grafovima. Ovo je važan aspekt analize komutativnosti, jer su računi koji manipulišu ovim podacima podataka suštinski izvan dosega analize ovisnosti podataka.
Koristili smo sistemski orijentisan pristup da bismo procijenili sposobnost analize komutativnosti za izdvajanje i iskorištavanje značajnih količina paralelizma u kompletnim aplikacijama. Izgradili smo paralelni kompajler koji koristi komutativnost kao svoju primarnu paradigmu analize. Ovaj prevodilac uzima kao ulaz nenajavljeni sekvencijalni program napisan u podskupini C++ i generira paralelni kod za višeprocesor zajedničke memorije. Koristeći ovaj paralelizator prevodilac, automatski paraleliziramo nekoliko aplikacija, uključujući Barnes-Hutov N-body solver, kôd za simulaciju tečne vode i seizmički model modeliranja. Za sve ove aplikacije analiza komutativnosti može otkriti znatnu količinu istodobnosti, a generirani paralelni kod pokazuje vrlo dobre performanse. Na 16 procesora, automatski paralelna verzija Barnes-Huta radi između 11 i 12 puta brže od izvorne sekvencijalne verzije; za aplikaciju za simulaciju vode, automatski paralelna verzija radi između 7 i 8 puta brže od izvorne sekvencijalne verzije; za seizmičku primjenu modeliranja, automatski paralelna verzija radi oko 12 puta brže od izvorne sekvencijalne verzije.
Ovi eksperimentalni rezultati su vrlo ohrabrujući. Ove su aplikacije vrlo dinamične prirode – ili manipuliraju sofisticiranim strukturama podataka zasnovanim na pokazivačima ili pokazuju vrlo nepravilne obrasce pristupa podacima. Iskorištavanje paralelnosti krupnog zrna u aplikacijama s ovim karakteristikama prepoznato je kao vrlo težak problem. Nismo svjesni niti jednog drugog prevoditelja ili tehnike sastavljanja koji bi mogao izvući značajne količine istodobnosti za ta izračunavanja. Nadalje, pozitivni eksperimentalni rezultati pružaju konkretne dokaze o praktičnom značaju analize komutativnosti kao tehnike automatske paralelizacije kompajlera.