Model widełkowo-łączny - Fork–join model

Ilustracja paradygmatu fork-join, w którym trzy regiony programu umożliwiają równoległe wykonywanie różnokolorowych bloków. Wykonanie sekwencyjne jest wyświetlane na górze, podczas gdy odpowiednik wykonania z połączeniem rozwidlającym znajduje się na dole.

W obliczeniach równoległych model fork-join jest sposobem konfigurowania i wykonywania programów równoległych, tak że wykonanie rozgałęzia się równolegle w wyznaczonych punktach w programie, aby „dołączyć” (scalić) w kolejnym punkcie i wznowić wykonywanie sekwencyjne. Sekcje równoległe mogą się rekursywnie rozwidlać, aż do osiągnięcia określonej szczegółowości zadania. Połączenie widełkowe można uznać za równoległy wzorzec projektowy . Powstał już w 1963 roku.

Zagnieżdżając rekurencyjnie obliczenia typu fork-join, uzyskuje się równoległą wersję paradygmatu dziel i rządź , wyrażoną następującym pseudokodem : 

solve(problem):
    if problem is small enough:
        solve problem directly (sequential algorithm)
    else:
        for part in subdivide(problem)
            fork subtask to solve(part)
        join all subtasks spawned in previous loop
        return combined results

Przykłady

Proste równoległe scalanie w CLRS to algorytm rozwidlania. 

mergesort(A, lo, hi):
    if lo < hi:                     // at least one element of input
        mid = ⌊lo + (hi - lo) / 2⌋
        fork mergesort(A, lo, mid)  // process (potentially) in parallel with main task
        mergesort(A, mid, hi)       // main task handles second recursion
        join
        merge(A, lo, mid, hi)

Pierwsze wywołanie rekurencyjne jest „rozwidlone”, co oznacza, że ​​jego wykonanie może przebiegać równolegle (w osobnym wątku) z następną częścią funkcji, aż do złączenia, które powoduje synchronizację wszystkich wątków. Chociaż połączenie może wyglądać jak bariera , jest inaczej, ponieważ wątki będą nadal działać po barierze, a po połączeniu tylko jeden wątek będzie kontynuowany.

Drugie wywołanie rekurencyjne nie jest rozwidleniem w powyższym pseudokodzie; jest to celowe, ponieważ zadania rozwidlenia mogą wiązać się z kosztami. Gdyby oba wywołania rekurencyjne zostały skonfigurowane jako podzadania, zadanie główne nie miałoby żadnej dodatkowej pracy do wykonania przed zablokowaniem przy łączeniu .

Realizacje

Implementacje modelu fork-join zazwyczaj rozwidlą zadania , włókna lub lekkie wątki , a nie wątki lub procesy „ciężkie” na poziomie systemu operacyjnego , i użyją puli wątków do wykonania tych zadań: prymityw rozwidlenia pozwala programiście określić potencjalną równoległość , które implementacja następnie mapuje na rzeczywiste wykonanie równoległe. Powodem tego projektu jest to, że tworzenie nowych wątków zwykle wiąże się ze zbyt dużym obciążeniem.

Lekkie wątki używane w programowaniu typu fork-join zazwyczaj mają swój własny program planujący (zwykle taki, który kradnie pracę ), który mapuje je na podstawową pulę wątków. Ten harmonogram może być znacznie prostszy niż w pełni funkcjonalny, wywłaszczający harmonogram systemu operacyjnego: ogólne harmonogramy wątków muszą radzić sobie z blokowaniem dla blokad , ale w paradygmacie rozwidlenia-połączenia wątki blokują się tylko w punkcie złączenia.

Fork-join jest głównym modelem wykonywania równoległego w ramach OpenMP , chociaż implementacje OpenMP mogą, ale nie muszą obsługiwać zagnieżdżania sekcji równoległych. Jest również obsługiwany przez strukturę współbieżności Java , bibliotekę zadań równoległych dla platformy .NET i bloki konstrukcyjne wątków firmy Intel (TBB). Cilk język programowania posiada wsparcie dla języka na poziomie rozwidlenia i dołączyć, w formie z spawni syncsłów kluczowych, lub cilk_spawni cilk_syncw Cilk Plus .

Zobacz też

Bibliografia

Linki zewnętrzne