Jakie pośrednie reprezentacje można zastosować do uzasadnienia współbieżności?

Próbuję lepiej zrozumieć, co byłoby wymagane, aby kompilator mógł dokonywać inteligentnych wyborów dotyczących współbieżności w imieniu programisty. Zdaję sobie sprawę, że istnieje wiele trudnych aspektów tego problemu, na przykład:

• Zapewnienie, że nie ma warunków wyścigu

• Zapewnienie, że kod, który ma być uruchamiany jednocześnie, nie będzie miał skutków ubocznych, które wpływają na semantyczne znaczenie kodu

• Zdecydowanie, czy narzut związany z rozpinaniem wątków jest opłacalny, biorąc pod uwagę stopień równoległości dostępnej w kodzie

Rozumiem, że dwa główne reprezentacje pośrednie stosowane we współczesnych kompilatorach to statyczne pojedyncze przypisanie dla języków proceduralnych i obiektowych oraz kontynuacja stylu dla języków funkcjonalnych. Rozumowanie któregokolwiek z wyżej wymienionych problemów wydaje się trudne przy użyciu tych pośrednich form. Nawet języki, które teoretycznie powinny mieć najlepszą szansę na automatyczną równoległość (języki funkcjonalne, takie jak Haskell z gwarancją braku efektów ubocznych), poczyniły ograniczone postępy w tej dziedzinie.

Tak więc moje pytanie brzmi, jakie pośrednie reprezentacje wykorzystano do rozwiązania tego problemu? Czy istnieją inne reprezentacje, które zostały wykorzystane w badaniach akademickich, o których nie wiem, które lepiej pasują do tego zadania? Czy ten problem zasadniczo musi zostać rozwiązany przez interfejs użytkownika kompilatora poprzez manipulowanie abstrakcyjnym drzewem składni, zanim kompilacja osiągnie pośrednią reprezentację?

Można by założyć, że modelowanie współbieżności w reprezentacji pośredniej (IR) było koniecznym wymogiem. Tak więc jedną odpowiedzią byłoby: „każda IR używana do programów sekwencyjnych z dodatkiem niektórych operacji współbieżności”, np. „Fork and join”, „parallel x y”. Dodanie ich umożliwia uzasadnienie niektórych rodzajów współbieżności, ale niekoniecznie łatwo. Nie jest też oczywiste, jak zapewnić pewne właściwości (płynność wyścigu danych) bez przejścia do w pełni funkcjonalnej reprezentacji (co utrudnia użyteczne modelowanie równoległości).

Prawdopodobnie kolorowe sieci Petriego (CPN) są dobrym wyborem do reprezentowania programów współbieżnych. (Tokeny w CPN są „pokolorowane” [mają typ] i mogą przenosić wartości; „przejścia” do stanów mogą wykonywać dowolną arytmetykę na przychodzących tokenach, aby wygenerować ewentualnie różnie kolorowy token o obliczonej wartości w „miejscu”). Jeśli myślisz o miejscach jako obliczonych wynikach i przejściach jako operatorach modelowania (w tym o specjalnym dostępie do pamięci), to daje to, co stanowi wykres przepływu danych, z którym można modelować programy. Możesz to łatwo wykorzystać do formalnej interpretacji klasycznych reprezentacji kompilatora, takich jak trójki [operator, wejście1, wejście2, wyjście].

Istnieje wiele narzędzi do analizy takich wykresów CPN, w tym właściwości obliczeniowe, takie jak brak zakleszczenia, ograniczenie liczby tokenów w miejscach itp. Heirarchiczne CPN pozwalają modelować funkcje i procedury oraz pojęcie „połączeń”.

To, co te reprezentacje nie robią wyraźnie, ułatwia zrozumienie, gdzie można równolegle złożyć wniosek. Trywialnie, dwa podliczenia mogą być równoległe, jeśli nie powodują współdzielenia operandów (dlatego niektórzy ludzie uwielbiają programy / reprezentacje funkcjonalne). Jeśli reprezentacja programu modeluje pamięć współużytkowaną, możesz zamodelować ją jako monolit i uzyskać zwykły zestaw problemów związanych z rozumowaniem interakcji w pamięci współużytkowanej, w tym adresowaniem aliasowym itp. Jednym ze sposobów uniknięcia tego jest traktowanie pamięci jako oddzielnych fragmentów za pomocą większy stan programu to niektóre z nich (drzewiaste); możesz prawdopodobnie przekazać te fragmenty w swojej reprezentacji pośredniej. Nie ma interakcji między dwoma równoległymi obliczeniami, jeśli nie współużytkują porcji (np. Poddrzewa pamięci).