POLITECHNIKA OPOLSKA

Programowanie współbieżne i rozproszone

Kierunek studiów:	Informatyka studia II-go stopnia	Rok studiów:	I
Rok akademicki:	2014 / 2015	Semestr:	I

Temat:
Ćwiczenie 3: Eliminacja macierzy metodą Gaussa

Lp.	Imię	Nazwisko	Sprawozdanie oddano dnia:	Ocena:
1.	Adam	Czech	26.05.2015

Termin zajęć:		Prowadzący:
dzień:	Wtorek	^dr hab. inż. J. Sadecki Prof. PO
godzina:	17:50
grupa:	L1

1. Cel ćwiczenia

Ćwiczenie ma celu napisanie programu, który spowoduje eliminację macierzy. Na potrzeby tego zadania wybrana została metoda Gaussa.

2. Wstęp teoretyczny

Metoda (eliminacji) Gaussa - jedna z najszybszych metod rozwiązywania układów równań liniowych, obliczania rzędu macierzy, obliczania macierzy odwrotnej oraz obliczania wartości wyznacznika. Nazwa metody pochodzi od nazwiska niemieckiego matematyka Carla Friedricha Gaussa.

3. Kod programu

#include <unistd.h>

#include <stdio.h>

#include <stdlib.h>

#include <sys/times.h>

#include <time.h>

//funkcja obliczając czas wykonania algorytmu

void doit(char *str, clock_t time)

{

long tps = sysconf(_SC_CLK_TCK);

printf("%s: %6.2f secs\n", str, (float)time/tps);

}

int main(int argc, char *argv[])

{

double **A, **B, t;

int N = 2499, M = 2500;

//zmienne indeksujące

int i, j, k, m;

//zmienne przechowujace czas wywołania

clock_t start, end;

struct tms t_start, t_end;

printf("Macierz A[%d][%d]",N,M);

//włączenie odmierzania czasu

start = times(&t_start);

// alokacja pamięci

A = (double**)malloc(N * sizeof(double*));

B = (double**)malloc(M * sizeof(double*));

for (i = 0; i < N; i++){

A[i] = (double*)malloc(M * sizeof(double));

}

for (i = 0; i < N; i++){

B[i] = (double*)malloc(M * sizeof(double));

}

//losowanie i wpisanie wartości do macierzy

for (i = 0; i < N; i++){

for (j = 0; j < M; j++ ){

A[i][j] = rand();

B[i][j] = A[i][j];

}}

//wyłączenie odmierzania czasu

end = times(&t_end);

//wyswietlenie czasu inicjalizacji macierzy

doit("\nCzas wykonania inicjalizacji i losowania liczb macierzy", end - start);

//włączenie odmierzania czasu

start = times(&t_start);

//eliminacja wspolczynnikow - sekwencyjnie

for(i = 0; i < N - 1; i++){

for(j = i + 1; j < N; j++){

m = -A[j][i] / A[i][i];

for(k = i + 1; k < M; k++)

A[j][k] += m * A[i][k];

}}

//obliczanie niewiadomych - sekwencyjnie

for (i = N - 1; i >= 0; --i) {

A[i][N] = A[i][N] / A[i][i];

A[i][i] = 1;

for (j = i - 1; j >= 0; --j) {

A[j][N] -= A[j][i] * A[i][N];

A[j][i] = 0;

}}

//wyłączenie odmierzania czasu

end = times(&t_end);

doit("Eliminacja Gaussa - sekwencyjnie", end - start);

printf("Czas wykonania - sekwencyjnie\n");

for (i = 0; i < N; i++){

for (j = 0; j < M; j++ ){

A[i][j] = B[i][j];

}}

printf("Czyszcze macierz wynikową------------------------------------\n");

//włączenie odmierzania czasu

start = times(&t_start);

//eliminacja wspolczynnikow - rownolegle

for(i = 0; i < N - 1; i++){

#pragma omp parallel for shared(A, N, M) private(j,k,m)num_threads(1)

for(j = i + 1; j < N; j++){

m = -A[j][i] / A[i][i];

for(k = i + 1; k < M; k++)

A[j][k] += m * A[i][k];

}}

//obliczanie niewiadomych - rownolegle

#pragma omp parallel for shared(A, N) private(i,j)num_threads(1)

for (i = N - 1; i >= 0; --i) {

A[i][N] = A[i][N] / A[i][i];

A[i][i] = 1;

for (j = i - 1; j >= 0; --j) {

A[j][N] -= A[j][i] * A[i][N];

A[j][i] = 0;

}

}

//wyłączenie odmierzania czasu

end = times(&t_end);

doit("Eliminacja Gaussa - 1 wątek", end - start);

printf("Czas wykonania - 1 wątek\n");

for (i = 0; i < N; i++){

for (j = 0; j < M; j++ ){

A[i][j] = B[i][j];

}

}

printf("Czyszcze macierz wynikową------------------------------------\n");

//włączenie odmierzania czasu

start = times(&t_start);

//eliminacja wspolczynnikow - rownolegle

for(i = 0; i < N - 1; i++){

#pragma omp parallel for shared(A, N, M) private(j,k,m)num_threads(2)

for(j = i + 1; j < N; j++){

m = -A[j][i] / A[i][i];

for(k = i + 1; k < M; k++)

A[j][k] += m * A[i][k];

}

}

//obliczanie niewiadomych - rownolegle

#pragma omp parallel for shared(A, N) private(i,j)num_threads(2)

for (i = N - 1; i >= 0; --i) {

A[i][N] = A[i][N] / A[i][i];

A[i][i] = 1;

for (j = i - 1; j >= 0; --j) {

A[j][N] -= A[j][i] * A[i][N];

A[j][i] = 0;

}

}

//wyłączenie odmierzania czasu

end = times(&t_end);

doit("Eliminacja Gaussa - 2 wątek", end - start);

printf("Czas wykonania - 2 wątek\n");

for (i = 0; i < N; i++){

for (j = 0; j < M; j++ ){

A[i][j] = B[i][j];

}

}

printf("Czyszcze macierz wynikową------------------------------------\n");

//włączenie odmierzania czasu

start = times(&t_start);

//eliminacja wspolczynnikow - rownolegle

for(i = 0; i < N - 1; i++){

#pragma omp parallel for shared(A, N, M) private(j,k,m)num_threads(3)

for(j = i + 1; j < N; j++){

m = -A[j][i] / A[i][i];

for(k = i + 1; k < M; k++)

A[j][k] += m * A[i][k];

}

}

//obliczanie niewiadomych - rownolegle

#pragma omp parallel for shared(A, N) private(i,j)num_threads(3)

for (i = N - 1; i >= 0; --i) {

A[i][N] = A[i][N] / A[i][i];

A[i][i] = 1;

for (j = i - 1; j >= 0; --j) {

A[j][N] -= A[j][i] * A[i][N];

A[j][i] = 0;

}

}

//wyłączenie odmierzania czasu

end = times(&t_end);

doit("Eliminacja Gaussa - 3 wątek", end - start);

printf("Czas wykonania - 3 wątek\n");

for (i = 0; i < N; i++){

for (j = 0; j < M; j++ ){

A[i][j] = B[i][j];

}

}

printf("Czyszcze macierz wynikową------------------------------------\n");

//włączenie odmierzania czasu

start = times(&t_start);

//eliminacja wspolczynnikow - rownolegle

for(i = 0; i < N - 1; i++){

#pragma omp parallel for shared(A, N, M) private(j,k,m)num_threads(4)

for(j = i + 1; j < N; j++){

m = -A[j][i] / A[i][i];

for(k = i + 1; k < M; k++)

A[j][k] += m * A[i][k];

}

}

//obliczanie niewiadomych - rownolegle

#pragma omp parallel for shared(A, N) private(i,j)num_threads(4)

for (i = N - 1; i >= 0; --i) {

A[i][N] = A[i][N] / A[i][i];

A[i][i] = 1;

for (j = i - 1; j >= 0; --j) {

A[j][N] -= A[j][i] * A[i][N];

A[j][i] = 0;

}

}

//wyłączenie odmierzania czasu

end = times(&t_end);

doit("Eliminacja Gaussa - 4 wątek", end - start);

//zwolnienie pamieci

for (i = 0; i < N; i++)

free(A[i]);

for (i = 0; i < N; i++)

free(B[i]);

free(A);

free(B);

return 0;

}

4. Wyniki

Wyniki przeprowadzonego ćwiczenia zostały umieszczone w tabeli

Eliminacja macierzy metodą Gaussa
Liczba wątków	Czas wykonania
Sekwencyjnie	48,75
1 wątek	56,86
2 wątki	30,23
3watki	20,32
4 wątki	16,64

5. Wykresy

1. Wykres liniowy czasu względem liczby wątków
   

2. Wykres zależności czasu obliczeń od ilości wątków (słupkowy)

6. Wnioski

Zastosowanie wielowątkowości dało zamierzony skutek, czyli wzrost przyspieszenia obliczeń. Można to zaobserwować na przedstawionych w pkt 5 wykresach. Wykres słupkowy zależności czasu obliczeń od ilości wątków, znakomicie przedstawia różnicę w czasie obliczeń z wykorzystanie 1 wątku i 2 wątków, tutaj skok czasowy jest największy.

WYDZIAŁ ELEKTROTECHNIKI, AUTOMATYKI I INFORMATYKI

7

Opole 2015

WYDZIAŁ ELEKTROTECHNIKI, AUTOMATYKI I INFORMATYKI

Opole 2015

---