Autor Wątek: Maksymalnie równoległa praca programu  (Przeczytany 2950 razy)

pu_sp_no_name

  • Gość
# Marzec 21, 2006, 19:11:26
Dzisiaj starałem sie zrozumieć istotę działania programów – algorytmów w kontekście wykonywania równoległego, czyli, czy da się wykonać np. funkcje w pełni równolegle (w jednym momencie) ?
Chciał bym poznać wasze opinie na ten temat. Proszę o podawanie uzasadnień.

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

pu_sp_no_name

  • Gość
# Marzec 21, 2006, 19:19:14
Funkcje w pełni równolegle da się jedynie wykonać na maszynach z więcej niż jednym układem wykonawczym. Co tu więcej mówić :) Jeśli chodzi o użycie wspólnych danych, to w tym miejscu jest problem. Pół biedy, jeśli procedury jedynie czytają dane - może powstać jedynie konflikt dostępu do tych samych lokacji pamięci - jednak to są zagadnienia na poziomie sprzętowym. Przykładowo procesor Motorola 68040 nadaje się bardzo dobrze do pracy SMP, bo jeśli wykryje, że ma w cache nowsze dane niż są w RAM, i wykryje że inny procesor chce uzyskać dostęp do tych danych, to sam mu wystawia te dane na szynę zamiast kontrolera pamięci. Gdy potrzebna jest modyfikacja danych, trzeba synchronizować dostęp do danych, np. semaforami.
Jeśli chodziło ci o co innego, to może lepiej sformułuj pytanie.



Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Marzec 21, 2006, 20:16:14
Najfajniej to jest na procesorach wektorowych - każdy element wektora liczony jest niezależnie, coś a'la SIMD

za AJ: sformułuj dokładnie o co ci chodzi, bo są jeszcze zagadnienia typu klastry, użycie narzędzi typu LINDA tudzież PVM...

pu_sp_no_name

  • Gość
# Marzec 21, 2006, 20:25:02
Nie chodziło mi o zwykłą prace równoległą. Chodzi mi o wykonywanie programu (jeśli są dostępne wszystkie dane, jeśli nie to jeden takt na nowa porcje danych) w ciągu tj. jednego taktu procesora. Tzn. wykonywanie programu za pomocą układów kombinacyjnych niezależnych od czasu.

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Marzec 21, 2006, 20:33:25
No to jeśli mówimy o prockach Intel'a i ogólnie o tych naszych domowych PC'tach to przede wszystkim SIMD'y : MMX, 3DNow! itp, druga rzecz to wszelkiej maści koprocesory (FPU, GPU).

pu_sp_no_name

  • Gość
# Marzec 21, 2006, 20:58:39
Nie sadze a zeby to oczym mowie istnialo :)
Pytam poprostu: co o tym myslicie ?

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Marzec 21, 2006, 22:21:08
Najwyraźniej nie do końca wiemy co dokładnie masz na myśli.

co to znaczy: "wykonać funkcje w pełni równolegle (w jednym momencie) "

chodzi ci o to, żeby dwie funkcje wykonały się równolegle, niezależnie od siebie? Wszystkie wieloprocesorowe maszynki powinny być w stanie coś takiego zrobić.

pu_sp_no_name

  • Gość
# Marzec 21, 2006, 22:23:27
Oczywiście, że da się zrealizować NIEKTÓRE algorytmy za pomoca układów kombinacyjnych. Koszt implementacji takiego algorytmu byłby bardzo duży, a sam algorytm działałby jedynie dla danych o stałym rozmiarze. Wiele algorytmów wymaga podtrzymania poprzednich stanów a także użycie tych danych w razie potrzeby. Nawet przy nieskończenie małym czasie propagacji bramek, układ taki musiałby posiadać podtrzymanie pamięci.
Wyszukiwanie w zbiorze n elementów można zrobić na koderze o n wejściach i n komparatorach, czyli nie ma sensu dla zbiorów składających się z milionów elementów.
Na przykład generacja obrazu dla monitora VGA wymaga wielu cykli generacji impulsów synchronizacji H i V oraz wartości R, G, B. Albo obliczanie mediany ze zbioru liczb wymagałoby bardzo wielu stopni obliczających wyniki pośrednie, czyli praktycznie nie jest do zrealizowania.

pu_sp_no_name

  • Gość
# Marzec 22, 2006, 14:04:26
Ciesze sie ze ktoś wreszcie zrozumiał o co mi chodzi :P

Ajent_j: Po części masz racje, ale można te problemy w pewien sposób ominąć, dlatego będę kontynuował ...

Po uzyskaniu odpowiedniego schematu logicznego takiego algorytmu, możemy go znacznie uprościć, tak ze niektóre funkcje mogą zawierać znacznie mniej elementów niż początkowo (praktycznie nieskończenie wiele razy). Do uruchomienia tego programu potrzebny będzie specjalny procesor który posiada dużą ilość bramek, które możemy dowolnie, dynamicznie ze sobą łączyć. Po uproszczeniu, w zależności od wielkości procesora (ilości bramek jakie można ze sobą dowolnie połączyć) trzeba podzielić ten wielki układ na małe części zawierające dokładnie tyle bramek ile posiada ten procesor (przy założeniu ze na danym procesorze pracuje jeden program). Aby wykonać cały program należy wykonać wszystkie części w taki sposób, ze po obliczeniu pierwszej (tej najbliżej wejść danych), zapisuje sie wyniki logiczne na końcówkach (tam gdzie układ został rozłączony). Następnie uruchamiając następną część układu podaje sie na wejścia odpowiednie wcześniej zapisane stany logiczne. Proces powtarza sie wielokrotnie aż wszystkie elementy zostaną wykonane. Dzięki temu na wyjściu uzyskujemy dane wyjściowe. Oczywiście nie bez znaczenia jest tutaj czas opóźnienia jaki wywołują bramki. Czym większy jest układ tym będzie działał on wolniej. Na szczęście szybkość działania i ilość bramek nie będzie tworzyć funkcji liniowej (nie będą proporcjonalne), lecz przy wzroście złożoności, prędkość będzie spadała znacznie wolniej (aż do pewnej granicy). Dzięki temu całość ma jakiś sens. Czym więcej bramek będzie w procesorze tym  generalnie będzie on szybszy. Dzięki temu możliwe stanie sie uruchamianie niezwykle złożonych programów w czasie rzeczywistym. Oczywiście jego prędkość jest ograniczona. Wywołane jest to czasem propagacji bramki. Programista pisząc jakiś algorytm nie będzie musiał przywiązywać wagi do wydajności swoje algorytmu. Powinno zależeć mu wyłącznie na tym żeby ten algorytm działał poprawnie. Po zapisaniu to w postaci układu kombinacyjnego i uproszczeniu powinno uzyskać sie maksymalnie wydajne rozwiązanie.
Edit:
Nie bez znaczenia jest to że wykonywanie takiego programu nie wymaga pamięci RAM ;) gdyż wszystko jest zapisane w połączeniach miedzy bramkami, a jakakolwiek pamięć potrzebna jest tylko w przypadku gdy program jest dzielony na części, co wyżej opisałem.
Głównymi zaletami tego rozwiązania będą:
- samo optymalizowanie się programów
- samo dopasowywanie się ilości tj. wątków
« Ostatnia zmiana: Marzec 22, 2006, 16:08:21 wysłana przez pu_sp_no_name »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Marzec 22, 2006, 16:52:12
pu_sp_no_name: Zastanawia mnie tylko, jak zamierzasz w takim układzie zrealizować pętle warunkowe. :)


Cytuj
Oczywiście jego prędkość jest ograniczona. Wywołane jest to czasem propagacji bramki. Programista pisząc jakiś algorytm nie będzie musiał przywiązywać wagi do wydajności swoje algorytmu. Powinno zależeć mu wyłącznie na tym żeby ten algorytm działał poprawnie.
Pierwsze dwa zdania trochę się gryzą z dwoma ostatnimi. ;) Wiele algorytmów ma złożoność wykładniczą i już przy niewielkiej ilości danych ilość operacji staje się tak duża, że żadna rozsądna ilość bardzo szybkich bramek nie jest w stanie wykonać algorytmu w rozsądnym czasie (czyli na przykład krótszym niż 100 lat). :)

pu_sp_no_name

  • Gość
# Marzec 22, 2006, 17:54:02
Krzysiek K. nie gryzą się :)
Miałem na myśli to, ze programista nie musi przywiązywać wagi do tego aby jego algorytm był optymalny (miał możliwie najmniejsza złożoność). Nie chodziło mi o to ze programista nie musi sie martwić wymaganiami programu.

Pętla warunkowa wyglądała by najprawdopodobniej tak, ze jeśli każda interakcja była by oddzielnym układem to wyjście jednego z układów połączone było by do wejścia kolejnego. Na samym wejściu układu był by układzik testujący (warunek) jeśli był by spełniony to układ testujący przekazywał by parametry do dalszej części układu interakcji. Jeśli warunek nie był by spełniony to parametry były by przekazane na wyjście na sam koniec pętli. Powtarzało by sie to dla wszystkich układów interakcji pętli.

Takie rozwiązanie nie dawało by nic poza maksymalnym wykorzystaniem prędkości działania bramek i wykonywaniem pracy równoległej gdy to tylko jest możliwe.
Teraz nasuwa sie pytanie: czy jest jakiś sposób na całkowite zrównoleglenie obliczeń czy należy jedynie dążyć do maksymalnego skrócenia czasu trwania elementarnego zadania ?  :-\

Jeszcze jedno w związku z wyżej wspomnianym upraszczaniem. Czy są jakieś metody na upraszczanie algorytmów na poziomie kodu źródłowego ?

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Marzec 22, 2006, 18:42:47
Cytuj
Miałem na myśli to, ze programista nie musi przywiązywać wagi do tego aby jego algorytm był optymalny (miał możliwie najmniejsza złożoność). Nie chodziło mi o to ze programista nie musi sie martwić wymaganiami programu.
Cytuj
Oczywiście jego prędkość jest ograniczona. Wywołane jest to czasem propagacji bramki.
Ponieważ prędkość układu jest ograniczona programista musi się martwić złożonością algorytmu.


Przykład: problem komiwojażera - jest dane N miast, pomiędzy którymi znamy odległości. Komiwojażer musi odwiedzić każde miasto dokładnie raz i wrócić do punktu wyjścia. Różnych kolejności odwiedzania jest w przybliżeniu N! (N silnia). Chcemy przejrzeć wszystkie konfiguracje, żeby znaleźć optymalną trasę. Zakładamy, że nasz superkomputer potrafi wygenerować i sprawdzić 100 miliardów konfiguracji miast na sekundę. Zakładamy, że mamy do dyspozycji milion takich superkomputerów. Chcemy zrobić banalną rzecz - sprawdzić wszystkie trasy komiwojażera dla 30 miast. Niestety, naszemu megaclusterowi superkomputerów zajęło by to trochę ponad 84 miliony lat. Złożoność wykładnicza jest w stanie dobić każdy komputer. :)


Cytuj
Teraz nasuwa sie pytanie: czy jest jakiś sposób na całkowite zrównoleglenie obliczeń czy należy jedynie dążyć do maksymalnego skrócenia czasu trwania elementarnego zadania ?
Można zastosować inne algorytmy. Wiadomo, że sortowania nie da się wykonać szybciej na pojedynczym procesorze niż w czasie O(N log N) bez czynienia dodatkowych założeń. Jednak na N procesorach można zastosować algorytm sortujący działający w czasie O(log^2 N). Zastosowanie tego algorytmu na pojedynczym procesorze było by nieoptymalne i dało czas rzędu O( N log^2 N).

pu_sp_no_name

  • Gość
# Marzec 22, 2006, 19:14:05
Krzysiek K. chyba nie zrozumiałeś o co mi chodzi. Pytałem czy istnieje metoda która pozwala na uproszczenie dowolnego algorytmu (tak jak to jest np. z minimalizacja funkcji logicznych metodą Karnaugh'a) ? Domyślam się że nie ma, więc zastanawiam się czy miało by sens zapisanie algorytmu w postaci układu logicznego i zminimalizowanie go za pomocą metody minimalizacji tego typu układów, bez wgłębiania się w sam algorytm.

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Marzec 22, 2006, 19:18:30
Problem leży raczej w tym, że to z reguły nie są układy kombinacyjne a raczej sekwencyjne. Poza tym to co ty próbujesz tu analizować było by możliwe raczej tylko do ograniczonego zestawu algorytmów (z prostym mapowanie WE-WY) inaczej robi ci się układ sekwencyjny...

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Marzec 22, 2006, 19:25:25
w sumie można by się zastanowić jakby się uprościło sortowanie bąbelkowe dla [powiedzmy] 8 elementów (ilu bitowych? :D) Trochę ta analiza pracy będzie kosztować, ale czemu nie spróbować. Problem tylko z czym to porównać. Tylko zauważ - sortowanie bąbelkowe, to jest kilka powtórzeń pojedyńczego mapowania WE-WY, jak będziesz je optymalizował? OK - porównania elementów wykonają ci się równolegle, ale i tak czas trwania będzie zależał liniowo od ilości sortowanych elementów (bo to przełoży się bezpośrednio na liczbę warstw) - złożoność wychodzi lepsza. A co np. z sortowaniem przez wstawianie? Ilość warstw ZAWSZE będzie musiała być równa ilość warstw dla przypadku pesymistycznego (tak mi się wydaje), więc o ile złożoność pesymistyczna rozwiązania 'równoległego' będzie lepsza niż średnia 'źródłowego' to będie jakiś zysk - tylko jakim kosztem? :)