Wielowątkowe mnożenie macierzy

0

Witam wszystkich ponownie. Tym razem mam problem z wielowątkowym mnożeniem macierzy. Mianowicie, zrobiłem sobie już funkcję, która oblicza pojedynczy wpis w macierzy wynikowej. Jako że każdy element macierzy wynikowej można obliczyć niezależnie, w pętli wywołuje ExecutorService tyle razy ile jest obliczeń. ExecutorService przy tworzeniu przyjmuje określoną ilość wątków. Poniżej uproszczony kod. Problem w tym, że:

  1. Jak dam exec.shutdown() skąd mam wiedzieć kiedy wątki zakończą działanie? na razie dałem sleepa i jako tako działa. Ale może jest bardziej elegancka metoda.
  2. Mierzę czas wykonywania tak jak poniżej. Co dziwne, dla 1 albo 10 wątków czas jest prawie taki sam;/ Czemu tak się dzieje?
 public class Main implements Runnable{

    public static void main(String[] args){

        Thread t = new Thread(new Main());
        t.start();
    }

public void run(){

Macierz m1, m2;
m1.init();
m2.init();

ExecutorService exec = Executors.newFixedThreadPool(10);

long start=System.currentTimeMillis();

        for(int i=0;i<ileObliczen;i++){
            exec.execute(new MnoznikMacierzy(parametry));
            }

exec.shutdown();    
while(!exec.isTerminated()) Thread.sleep(1);
long stop=System.currentTimeMillis(); -> Wypisanie tego czasu

}

Klasa macierz nie jest tutaj istotna, ale kolejna:
oczywiście zawiera wszelakie potrzebne dane przekazywane w konstruktorze

 class MnoznikMacierzy implements Runnable{

 public void run(){

        for(int i=0; i< m.kolumn;i++)
            out.macierz[wiersz][kolumna] += m.macierz[wiersz][i] * m1.macierz[i][kolumna];

    }
}

Z góry dziękuje za odpowiedź

Co ciekawe, teraz sprawdziłem. Jeśli pomnoże macierze w pętli normalnie to czas jest 2x krótszy niż przy użyciu wątków.

0

Po pierwsze czas jest średnim wyznacznikiem wydajności. Tworzenie i zarządzanie wątkami też trwa zatem nie ma nic dziwnego, że program wielowątkowy działa wolniej.
Co do kończenia wątków warto użyć CountDownLatch - blokady zliczającej.

0

Aby było szybciej użyj dużej macierzy np 1000x1000, stwórz tylko kilka wątków a nie setki, musisz mieć procesor 2 lub więcej rdzeni.

0

Czemu tak się dzieje?

Przy pracy na wielu wątkach przyspieszenie możliwe jest do uzyskania tylko i wyłącznie gdy jakieś obliczenia są przeprowadzane równolegle. Aby tak się działo musisz mieć kilka procesorów lub kilka rdzeni jednego procesora (lub kombinację kilku wielordzeniowych CPU). Ale to nie wszystko. Czy poszczególnym wątkom zostaną przydzielone różne rdzenie zależne jest od managera zadań systemu operacyjnego - a nad tym nie ma żadnej kontroli z poziomu programu (tym bardziej z poziomu programu w Javie, u którego wszystko działa poprzez JVM).
Jeżeli masz procesor np. czterordzeniowy, to aby cokolwiek było szybciej muszą zostać spełnione takie warunki:

  1. Cztery różne wątki będą pracować równocześnie nad jakimiś zadaniami.
  2. Działanie żadnego nie zależy od działania innego - na przykład żaden z nich nie konkuruje z innym o wspólne (np. synchronizowane) dane. Tu trzeba zwrócić uwagę czy dostęp do elementów tablicy/kontenera jest blokowany globalnie, czy na poziomie komórki/wiersza/kolumny - bo jeżeli jest globalnie, to jeden wątek będzie czekał na zwolnienie zasobu przez inny. Konkurowanie istnieje czasem nawet jeżeli nie ma żadnej synchronizacji - po prostu dwa rdzenie nie mogą jednocześnie zapisywać tej samej komórki pamięci - jeden z nich poczeka w sposób całkowicie zależny od sprzętu.
  3. Każdy z wątków musi zostać rozmieszczony na osobnym rdzeniu procesora (współczesne systemy potrafią przerzucać wątek pod kontrolę innego rdzenia lub procesora jeżeli tak korzystniej rozkłada się obciążenie rdzeni - ale nie ma nad tym kontroli). Dlatego wątki muszą działać odpowiednio długo aby system zdążył odpowiednio rozłożyć zadania (stąd efekty widać dopiero na dużych tablicach/danych).
  4. Maksymalne teoretyczne przyspieszenie jest zależne od ilości równomiernie obciążonych rdzeni/procesorów. Przy procesorze czterordzeniowym całość zadania zakończyłoby się w 1/4 czasu (pracy procesora jednordzeniowego) - czyli przyspieszenie maks. niby 400% gdyby radośnie przyjąć, że samo działanie wątków i synchronizacja nie zajmuje czasu, a wszystkie zadania rozpoczną się równocześnie i równocześnie się zakończą.
    W praktyce sama obsługa wątków/rdzeni jest trochę czasochłonna, zależność jednych wątków od innych jest spora, a żadne zadania nie rozpoczynają się w tym samym czasie.
    Na procesorze jednordzeniowym program kilku wątkowy działa nieco wolniej niż taki sam napisany jako jednowątkowy.

Żeby pisać sobie współbieżnie powinieneś pobierać od systemu/JVM ilość fizycznych rdzeni/procesorów (np. w Windows byłaby to zmienna środowiska NUMBER_OF_PROCESSORS) i wstawiać go do swoich zadań jako parametr mający wpływ na ilość równocześnie uruchamianych wątków. Na nie będziesz musiał sobie w miarę równomiernie rozdzielić konkretne zadanie do wykonania/obliczenia. W praktyce ilość wątków silnie obciążonych niezależną pracą nie powinna przekraczać liczby takich jednostek (lub być o 1 mniejsza ze względu na to że współczesne systemy i procesy mogą wykonywać w tle całkiem sporo pracy). Na przykład przy mnożeniu macierzy i wykorzystaniu 3 wątków każdy z nich powinien obrabiać co trzecie obliczenie cząstkowe na każdym etapie po którym zebrane dane posłużą do dalszej obróbki również w trzech wątkach.
Trzeba też będzie wkrótce uwzględniać, że w czasie pracy programu ilość procesorów może się zmienić (sic!) - szczególnie w sytuacji działania na maszynach wirtualnych, które fizycznie będą składać się z wielu komputerów połączonych w sieci.

ps. Aby pobrać liczbę procesorów wystarczy użyć metody Runtime.availableProcessors().

0

Przy mnożeniu macierzy bardzo ważne jest rozsądne korzystanie z pamięci podręcznej procesora, tzn zminimalizowanie dostępów do RAMu i zmaksymalizowanie stopnia wykorzystania danych leżących w pamięci podręcznej. Poszczególne wątki powinny też dzielić jak najwięcej danych między sobą. Ogólnie temat jest obszerny, trzeba poszukać o tym na necie. Inaczej zrównoleglanie niewiele da, bo wąskim gardłem będzie podsystem pamięci.

1 użytkowników online, w tym zalogowanych: 0, gości: 1