Zamiana wyrazów w ciągach - algorytm równległy - devPytania

Zamiana wyrazów w ciągach - algorytm równległy

2010-01-11T08:00:04Z

Witam. Mam pewien problem z wymyśleniem sensownego algorytmu równoległego rozwiązującejgo następujące zagadnienie.

Dane są dwa ciągi liczb {xi} i {yi} i=1,2,...,n o wyrazach dodatnich. Wymień pierwszy element przysty z ciągu x z pierwszym elementem nieparzystym ciągu y, drugi element parzysty z ciągu x z drugim elementem nieparzystym z ciągu y, etc... aż do wyczerpania elementów z jednego ciągu

Ponieważ jest to czysto akademickie zagadnienie rozwiązanie równoległe wcale nie musi być opłacalne. Wymyśliłem kilka algorytmów, ale żaden nie wygląda sensownie. Z góry dziękuję za wszystkie pomysły

edit: do mortala i rafka. jest jakiś problem z edytowanie tagów :)

Answer by manek..pl for Zamiana wyrazów w ciągach - algorytm równległy

2010-01-11T13:36:30Z

Pierwszy pomysł i chyba najmniej skomplikowany to taki, że tworzysz dwa procesy. Jeden czyta ciąg {x}, aż do napotkania prawidłowej liczby(czyli parzystej). Drugi czyta ciąg {y} aż do napotkania liczby nieparzystej. Proces 1 wysyła liczbę do procesu 2 a ten ją zapisuje w odpowiednim miejscu. I tak aż do wyczerpania liczb.

Co masz na myśli przez sensowny algorytm? Można tutaj zrobić wiele procesów(więcej niż dwa) ale może być problem z synchronizacją i zapewnieniem prawidłowej kolejności wymiany liczb.

Answer by lqc for Zamiana wyrazów w ciągach - algorytm równległy

2010-01-11T14:33:06Z

Z góry mówię, że poniższy algorytm działa, ale nie koniecznie jestem z niego dumny :) Nie jestem pewien czy da się rozwiązać ten problem w złożoności lepszej niż O(n), nawet używając n procesorów. Z chęcią się dowiem.

Dane wejściowe:

x[n], y[n], # tablice indeksuję od 0
procesory P(1..n), 
pomocnicze tablice xi[n+1], yi[n+1]

Kod dla procesora P(i):

v = x[i-1]
if v % 2 == 0:
    xi[i] = i
else:
    xi[i] = -1

# tutaj jest wąskie gardło
n.times do:
  v = xi[i]

  if xi[i-1] < 0:
      xi[i-1] = v
      xi[i] = -1
  else:
      xi[i-1] = -1
      xi[i] = v

# analogicznie używając y i yi
# i na koniec zamieniamy:
j = xi[i]
k = yi[i]

if j > 0 and k > 0:
    x[j-1] = y[k-1]

Nie potrzebny jest żaden mechanizm synchronizacji pod warunkiem, że wszystkie operację są wykonywane równolegle w tym samym tempie (model PRAM).

Answer by bodziec for Zamiana wyrazów w ciągach - algorytm równległy

2010-01-11T14:59:00Z

Może coś takiego (podobnie jak pisze manek-pl):

Jeden proces szuka w jednej tablicy, drugi w drugiej Oba zgłaszają trzeciemu procesowi żądanie wymiany liczb na podanych przez nich pozycjach.

Trzeci proces działałby w taki sposób że buforuje indeksy przekazywane z wątków 1 i 2 (ponieważ jeden z nich może znaleźć kilka liczb szybciej (bo będą na początku) niż drugi jedną która np będzie na końcu) i jeżeli jest conajmniej jedna para to można je wymienić

Przeszukiwane tablice można podzielić na n podtablic i na nich równolegle szukać parzystych/nieparzystych ale z warunkiem że na wyniku ich pracy 3 wątek może działać tylko jak skończy działać na poprzedniej parze podtablic.

Takie moje przemyślnia ;-)

Answer by bigfun for Zamiana wyrazów w ciągach - algorytm równległy

2010-02-09T00:18:59Z

Mój pomysł

Mamy dwa wątki(procesy), każdy z wątków zajmuje się swoim ciągiem. Każdy wątek ma dwie kolejki FIFO. Jedna kolejka przechowuje indeksy kolejno znalezionych liczb we własnym ciągu, druga przechowuje wartości liczb otrzymanych od drugiego wątku.

Praca poszczególnych wątków

Wątek szuka kolejnej liczby parzystej/nieparzystej, w zależności od ciągu na którym operuje.
Po znalezieniu liczby, wysyła jej wartość do drugiego wątku oraz: a) Jeśli kolejka z liczbami otrzymanymi od drugiego wątku była pusta, dodaje indeks znalezionej liczby do kolejki na indeksy. b) Jeśli kolejka z liczbami otrzymanymi od drugiego wątku nie była pusta, pobiera pierwszy element z tej kolejki i ustawia jego wartość w ciągu pod indeksem liczby, którą właśnie znalazł.
Wątek otrzymuje liczbę od drugiego wątku. Jeśli: a) Kolejka z indeksami nie jest pusta, to pobiera pierwszy element z tej kolejki, i otrzymaną liczbę umieszcza w ciągu pod tym indeksem. b) Kolejka z indeksami jest pusta, to otrzymaną liczbę dodaje do kolejki na liczby otrzymane od drugiego wątku.
Po przeszukaniu całego ciągu wysyła wartość -1 informując o zakończeniu przeszukania, oraz oczekuje na wartość -1 od drugiego wątku, aby móc zakończyć działanie.

Należy zorganizować komunikację między wątkami (np. poprzez sockety), tak aby nie występowało zawieszanie wątku związane z oczekiwaniem na dane od drugiego wątku.

Jeśli mamy więcej komputerów/procesów/wątków - mamy ich n, to dzielimy ciągi na n-1 podciągów, które są przeszukiwane przez n-1 wątków. Wątki te wrzucają dane do własnych kolejek, a ostatni wątek zajmie się "scaleniem" kolejek wątków szukających oraz będzie zamieniał liczby w ciągach. Zamiast scalać kolejki można też utworzyć kolejkę priorytetową, w której priorytetem będzie nr podciągu. Dzięki temu wątki szukające będą wrzucać dane od razu do tej głównej kolejki, bez generowania zbędnych własnych kolejek.

EDIT: Jest jedno ale - wątek zamieniający musiałby czekać, aż kolejna para wątków szukających dla podciągu X i podciągu Y zakończy pracę, i dokonać liczby zamian równej mniejszej z ilości znalezionych elementów dla podciągu Xi i podciągu Yi. Dlatego wydaje mi się, że większa ilość wątków niż 2 nie przyspieszy pracy.

Answer by Tomek for Zamiana wyrazów w ciągach - algorytm równległy

2010-03-01T10:27:18Z

To można rozwiązać za pomocą sum prefiksowych w czasie O(log n) na O(n) procesorach (to akurat można zmniejszyć do O(n/logn) ale to już technikalia):

http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_13