nerooc/mpi-cannon-algorithm

Cannon's algorithm implemented in C with MPI

Gabriel Chęć, Tomasz Gajda

Mnożenie macierzy (MPI)

Algorytm Cannon'a

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

Algorytm Cannon’a:

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.
4. Przesuwamy wszystkie podmacierze A(i, j) w lewo o i kroków i wszystkich podmacierzy B(i, j) w górę o j kroków.
5. Wykonujemy mnożenie bloków lokalnych.
6. Każdy blok A przesuwamy o jeden krok w lewo, a każdy blok B przesuwamy o jeden krok w górę.
7. Wykonujemy mnożenie kolejnych bloków, dodajemy do wyniku częściowego i powtarzamy to, aż wszystkie bloki zostaną pomnożone.

Przykład obliczania jednego z elementów macierzy wynikowej

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 obsługuje flagę -v (verbose). Po uruchomieniu programu z tą flagą możemy zobaczyć wypisane w sposób macierze mnożone oraz macierz wynikową.

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

4. Zawartość katalogu

• main.c - program obsługujący zadanie,
• makefile - plik make pozwalający na łatwe uruchamianie,
• A.csv - pierwsza mnożona macierz,
• B.csv - druga mnożona macierz,
• Result.csv - przykład docelowej wynikowej macierzy,
• Dokumentacja.pdf - opis i dokumentacja projektu.

5. Materiały

• Prezentacja - LINK
• GitHub - LINK