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

1. Wątek szuka kolejnej liczby parzystej/nieparzystej, w zależności od ciągu na którym operuje.

2. 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ł.

3. 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.

4. 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.

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.

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).

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 ;-)

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