Abstrakt. För samtidiga och parallella språk frågar May-happen-inparallell (MHP) beslutsproblem, givet två åtgärder i programmet, om det finns en avrättning där de kan utföra parallellt. Nära relaterat, MHP beräkningsproblem frågar, med tanke på ett program, vilka par av uttalanden kan hända parallellt. MHP-analys är grunden för många programanalysproblem, som t.ex. datakapplöpningsdetektering och kontroll av determinism, och forskare har tagit fram MHP-analyser för en mängd olika programmeringsmodeller. Vi presenterar algoritmer för statisk MHP-analys av en butikslös abstraktion av X10-liknande språk som har async-finish parallellism och procedurer. För ett program av storlek n, löser vår första algoritm MHP beslutsproblem i O(n) tid, via en minskning till begränsade dynamiska pushdown nätverk (CDPNs). Vår andra algoritm löser MHP beräkningsproblemet i O(n · max(n, k) tid, där k är en statiskt bestämd övre gräns på antalet par som kan hända parallellt. Den andra algoritmen kör först en typbaserad analys som producerar en uppsättning kandidatpar, och sedan den kör beslutsförfarandet på vart och ett av dessa par. För program utan rekursion är den typbaserade analysen exakt och ger en utgångskänslig algoritm för MHP-beräkningsproblem, medan den typbaserade analysen för rekursiva program kan producera falska par som beslutsförfarandet sedan kommer att ta bort. Våra experiment på en stor svit av X10 riktmärken tyder på att vår strategi skalar väl. Våra experiment visar också att medan k är O(n 2 ) i värsta fall är k ofta O(n) i praktiken.
Lee och Al. REF föreslog algoritmer för statisk MHP-analys av X10-liknande språk som består av async-finish parallellism och förfaranden.
Efficient May Happen in Parallel Analysis for Async-Finish Parallelism
{'venue': 'SAS', 'journal': None, 'mag_field_of_study': ['Computer Science']}