Sortowanie tablicy w wątkach

Sortowanie tablicy w wątkach
BR
  • Rejestracja:prawie 11 lat
  • Ostatnio:ponad 10 lat
  • Postów:2
0

Witam wszystkich,

mam problem związany z zaprojektowaniem aplikacji wielowątkowej. W uproszczeniu: chcę posortować dużą tablicę (długości N~10^6) obiektów w M wątkach (np. poprzez scalanie). Każdy z wątków operuje na swoim zakresie tablicy, zakresy nie zachodzą na siebie. Po zakończeniu działania wątków usługowych, uzyskuję tablicę częściowo posortowaną, którą już tylko scalam w wątku głównym.

Najprościej byłoby mi operować na 1 wspólnej tablicy, tym bardziej, że i tak taka tablica będzie mi potrzebna w innej części programu. Moje pytanie dotyczy wydajności takiego rozwiązania i ewentualnych błędów.

  1. Czy każdy z wątków może otrzymać kopię całej tablicy w pamięci lokalnej? Obawiam się, że to znacznie zwiększyłoby zużycie pamięci.
  2. Czy w wyniku synchronizacji (happens before) mogę utracić zmiany wprowadzone w części wątków? Wytłumaczę dokładniej:
Kopiuj
//watek glowny
volatile MyObject[] tablica = new MyObject[N];
//....inicjalizacja tablicy
Worker[] watki = new Worker[M];
//...przydzielanie zakresow
for(int i=0;i<M;++i)watki[i].start();
for(int i=0;i<M;++i)watki[i].join();

//poniżej synchronizacja przez volatile
tablica = tablica;
//tablica widziana w wątku głównym będzie zawierała wszystkie zmiany
//czy tylko zmiany z ostatniego wątku usługowego (poprzednie zostaną nadpisane?)

//.....Watek uslugowy
private class Worker extends Thread{
public void run(){
//.....sortowanie na zakresie tablicy: tablica
}

Podsumowując, w przypadku kiedy każdy wątek posiada swoją kopię zmiennej w pamięci lokalnej, po czym następuje synchronizacja w zewnętrznym wątku, to która wartość jest widziana? I jak to się ma do zmian wprowadzonych na rozłącznych zakresach jednej tablicy?

Proszę o podpowiedź, bo utknąłem i nie wiem czy powinienem szukać innych rozwiązań.

Atlas500
  • Rejestracja:około 11 lat
  • Ostatnio:prawie 9 lat
  • Postów:82
0

Sortowanie przez scalanie odbywa się rekurencyjnie, czyli liczysz się z utworzeniem, w najlepszym wypadku dla 106 elementów 106/2 wątków, czy chodzi o rekursję problemu i wybranie sobie jakiejś rozsądnej liczby wątków (np. kilku)?
Jeżeli będziesz kopiował tablicę do każdego wątku to, jak najbardziej zwiększy to zużycie pamięci, a jeżeli wątki będą sortować po kawałku zsynchronizowanej tablicy to jaki jest cel? Monitor i tak zezwoli na działanie jednego wątku na raz, czyli wynik będzie jeszcze gorszy, bo przeskakiwanie między wątkami też zużywa zasoby.


"Jeżeli człowiek to wymyślił, człowiek może to zrozumieć." Sochacki
edytowany 6x, ostatnio: Atlas500
__krzysiek85
  • Rejestracja:ponad 18 lat
  • Ostatnio:ponad 9 lat
  • Postów:1019
0

A po co chcesz cokolwiek synchronizować?
Niech każdy z wątków posortuje swoją część tablicy, a na końcu sortowanie możesz dokończyć jednym wątkiem.

Moim zdaniem jednak lepiej zastosować mechanizm fork and join z Javy 7+ (http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html).
Jeżeli nie wiesz jak, to zobacz implementację metody parallelSort:
http://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#parallelSort-int:A-


Registered Linux user #456405 | SCJP 6 | SCWCD 5 | SCBCD 5
edytowany 2x, ostatnio: __krzysiek85
BR
  • Rejestracja:prawie 11 lat
  • Ostatnio:ponad 10 lat
  • Postów:2
0

@Atlas500 wątków będzie tyle ile dostępnych rdzeni procesora. Na niższym poziomie posortowanie dowolnym algorytmem w czasie O((N/M)log2(N/M)) w głównym wątku scalanie O(Nlog2M) w sumie (N/M)(log2(NM(M-1)) < Nlog2N zawsze to jakiś zysk. Tym bardziej, że wątki będą odpalone już wcześniej, a sortowanie jest tylko jedną (ostatnią) z operacji, które wykonuje na tej tablicy.

__krzysiek85 napisał(a):

A po co chcesz cokolwiek synchronizować?
Niech każdy z wątków posortuje swoją część tablicy, a na końcu sortowanie możesz dokończyć jednym wątkiem.

Moim zdaniem jednak lepiej zastosować mechanizm fork and join z Javy 7+ (http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html).
Jeżeli nie wiesz jak, to zobacz implementację metody parallelSort:
http://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#parallelSort-int:A-

Nie miałem jeszcze okazji stosować tych nowych rozwiązań, a chętnie spróbowałbym: ) Niestety, w sieci na której będę odpalał symulację jest zainstalowana wersja 6, tak że muszę się ograniczyć.

Masz rację synchronizacja w trakcie pracy wątków usługowych nie jest potrzebna (nawet jest niepożądana ze względu na wydajność). Moje pytanie dotyczy synchronizacji po zakończeniu działania wątków. Dokładnie o sensowność memory barrier za pomocą zmiennej volatile. Oczywiście sama referencja do tablicy nie musi być volatile można wykorzystać w tym celu dodatkową flagę. O ile rozumiem działanie zasady happens-before w przypadku prymitywów, to nie mam pewności jak to się ma do tablic. W każdym wątku zostaje zmodyfikowany (rozłączny) zakres tablicy, pozostałe indeksy są niezmienione. Wątki mają prawo posiadać swoją lokalną kopię tablicy. W efekcie może się zdarzyć taka sytuacja, że w pamięci istnieje M różnych wersji tablicy. W jaki sposób są one scalane przy napotkaniu memory barrier? Zwykłe nadpisanie najnowszą wersją prowadzi do sytuacji, w której zmiany wykonane w innych wątkach są tracone (bo tylko jedna z nich jest najnowsza). Być może jednak mechanizm jest inteligentniejszy? Tego nie wiem.
Nie wiem też czy wątki uzyskują swoje kopie lokalne tablicy. Dla dużych tablic byłoby to duże obciążenie pamięci, więc może kompilator JIT nie wprowadza takiej optymalizacji?

Oczywiście testowałem kod na moim komputerze. Uzyskałem prawidłowe wyniki z użyciem volatile i bez. Z tym, że z referencją volatile do tablicy czas wykonania był znacznie dłuższy. Nadal jednak nie rozumiem zasady i nie mogę mieć pewności czy kod zadziała bezbłędnie na innym sprzęcie.

Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)