Wielowątkowość w sortowaniu.

Witam, mam pytanie.

W moim programie zadaniem jest wczytanie tablicy z pliku, posortowanie jej (metodą przez wstawianie ) i zapisanie wyniku. Jak do tego dorzucić jeszcze wielowątkowość? Jeden wątek odpowiedzialny za jeden plik, wczytanie go i sortowanie? czy może kilka wątków ale różne częśći tablicy do posrotowania? Czytałem i wiem że jest funkcja w C++ to tworzenia nowych wątków, ale niezbyt ogarniam jak w praktyce przy takim problemie można to wykorzystać. Funkcja sortująca w kilku wątkach jednocześnie?

nie widze tu miejsca na wielowatkowosc

Otwierasz plik pobierasz liczbe i wpisujesz na odpowiednie miejsce do drugiego (otwartego)... tyle

Głównym celem nie jest posortowanie tego, lecz właśnie działanie na różnych wątkach. Na wyrost, ale musi ono być..

Zaimplementuj rownoleglego merge sorta. Całkiem proste z OpenMP.

Przez wstawianie to raczej słabo współbieżnie robić, ale merge czy choćby i quicksort jak najbardziej się nadają. Generalnie każdy algorytm "divide and conquer" sie nadaje.

Wiem, jeżeli będzie możliwosć to taki zrobie, ale nie wiem czy można zmienić algorytm, musze popytać odpowiednich osob.

Czy samą operacje na plikach dało by rade zrobić współbieżnie? Czytanie kilku plików na raz?

Jeżeli już dowiem się co(czy inne sort, czy operacja na plikach) to głównie chodzi mi o sam algorytm pisania takiego czegoś 'współbieżnie'...

Sortowanie Shella jest rozwinięciem sortowania przez wstawianie, a wewnętrzne pętle można zrównoleglić. Dla odstępu równego N można odpalić N wątków (lub mniej).

Nie rozumiem, jak Ty to chcesz robić. Każde n-sortowanie osobnym wątkiem? A co z elementami wspólnymi? Lock? Dla pozostałych też nie lepiej, bo false sharing zabije jakikolwiek zysk ze zrównoleglenia. Chyba że ja to źle zrozumiałem i chodziło o coś innego.

Kod w pseudkodzie (mocny miszmasz języków):

sortuj(tab) = {
  for (odstęp <- odstępy) { // gdzie odstępy to np List(100, 60, 37, 23, 17, 12, 5, 3, 2, 1)
    #pragma parallel
    for (przesunięcie <- [0..odstęp-1]) {
      sortujPrzezWstawianie(tab, odstęp, przesunięcie)
    }
  }
}

sortujPrzezWstawianie(A, G, S) dotyka tylko elementów o indeksach typu: I = n * G + S, dla n całkowitego.

False sharing prawdopodobnie zabije wydajność, ale i tak to miało być zrównoleglanie na wyrost.

freekill napisał(a):

Witam, mam pytanie.

W moim programie zadaniem jest wczytanie tablicy z pliku, posortowanie jej (metodą przez wstawianie ) i zapisanie wyniku. Jak do tego dorzucić jeszcze wielowątkowość? Jeden wątek odpowiedzialny za jeden plik, wczytanie go i sortowanie? czy może kilka wątków ale różne częśći tablicy do posrotowania? Czytałem i wiem że jest funkcja w C++ to tworzenia nowych wątków, ale niezbyt ogarniam jak w praktyce przy takim problemie można to wykorzystać. Funkcja sortująca w kilku wątkach jednocześnie?

W najprostszej wersji dzielisz te dane na 2 części, i sortujesz w oddzielnych wątkach.
A potem obie posortowane już serie scalasz w jedną, co nie jest trudne.

Analogicznie dla n części - sortujesz w n wątkach, a potem scalasz w jedną, używając stosu o rozmiarze n.