Dividend-and-conquer algoritmer är lämpliga för moderna parallella maskiner, tenderar att ha stora mängder inneboende parallellism och fungerar bra med caches och djupa minneshierarkier. Bland annat, lista homomorfismer är en klass av rekursiva funktioner på listor, som passar mycket bra med splitter-och-konquer paradigm. Men direkt programmering med lista homomorfism är en utmaning för många programmerare. I detta dokument föreslår och genomför vi ett nytt system som automatiskt kan härleda kostnadsoptimala lista homomorfismer från ett par sekventiella program, baserat på den tredje homomorfismen teorem. Vår idé är att minska utvinningen av listan homomorfismer till härledning av svaga höger inverser. Vi visar att en svag höger invers alltid finns och kan automatiskt genereras från en bred klass av sekventiella program. Vi demonstrerar vårt system med flera icke-triviala exempel, inklusive maximal prefix summa problem, prefix summa beräkning, maximal segment summa problem, och line-ofsight problem. De experimentella resultaten visar praktisk effektivitet av vår automatiska parallelliseringsalgoritm och goda hastighetsförbättringar av de genererade parallella programmen.
Ett nytt verk REF använder den tredje homomorfismen teorem och byggandet av den svaga högern invers för att härleda parallella program.
Automatic inversion generates divide-and-conquer parallel programs
{'venue': "PLDI '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}