Mnożenie macierzy

Algorytm Cannon’a

Wstęp teoretyczny

Algorytm Cannon’a jest rozproszonym algorytmem mnożenia macierzy dla siatek dwuwymiarowych, który po raz pierwszy opisany został w 1969 r. przez Lynn’a Elliot’a Cannon’a.

• Algorytm jest efektywny jedynie dla struktury kwadratowej,
• Działających w algorytmie procesorów jest tyle jaki jest rozmiar macierzy

Przebieg algorytmu:

1. Oznaczamy mnożone macierze jako A i B, macierz wynikową jako C, macierz procesów jako P.
2. Proces P(i, j) początkowo przechowuje A(i, j), a B(i, j) oblicza blok C(i, j) macierzy wynikowej.
3. Przekształcamy A i B w taki sposób, aby każdy proces mógł niezależnie rozpocząć mnożenie swoich lokalnych podmacierzy - przesuwamy wszystkie podmacierze A(i, j) w lewo o i kroków i wszystkie podmacierze B(i, j) w górę o j kroków.
4. Wykonujemy mnożenie bloków lokalnych.
5. Każdy blok A przesuwamy o jeden krok w lewo, a każdy blok B przesuwamy o jeden krok w górę.
6. Wykonujemy mnożenie kolejnych bloków, dodajemy do wyniku częściowego i powtarzamy to, aż wszystkie bloki zostaną pomnożone i dodane.

C(1, 2) = A(1, 0) * B(0, 2) + A(1, 1) * B(1, 2) + A(1, 2) * B(2, 2)

C(1, 2) = A(1, 0) * B(0, 2) + A(1, 1) * B(1, 2) + A(1, 2) * B(2, 2)

Implementacja

Program został napisany w języku C. Korzystamy z jednej struktury danych o nazwie matrix_data. �Struktura składa się z:

• mat - spłaszczonej, jednowymiarowej tablicy elementów macierzy w postaci zmiennoprzecinkowej,
• row - ilość rzędów macierzy,
• col - ilość kolumn macierzy�

W programie możemy znaleźć 4 funkcje:

• main - główna funkcja zajmująca się przebiegiem algorytmu, czyli obliczeniami i przekształceniami,
• print_matrix - funkcja wypisująca macierz do konsoli w sposób sformatowany,
• initialize_matrix - funkcja inicjalizująca macierz poprzez wczytanie jej z pliku .csv, zaalokowanie pamięci i zapisanie w postaci struktury matrix_data,
• save_matrix - funkcja zapisująca macierz w postaci pliku .csv, używają

Program

Przejście przez kod

Uruchomienie

Do przygotowania i uruchomienia rozwiązania służy plik makefile, w którym zdefiniowane są następujące komendy:

• build - komenda kompiluje nasz program,
• build_valgrind - j.w korzystając z valgrinda,
• nodes - tworzy plik z węzłami,
• run - uruchamia program korzystając z wielu komputerów,
• run_one - uruchamia program na jednym komputerze,
• run_one_verb - jw. z parametrem verbose,
• run_one_valgrind - jw. korzystając z valgrinda,
• clean - usuwa utworzone przy uruchamianiu pliki.

Koniec

Dziękujemy za uwagę!