POLITECHNIKA OPOLSKA
LABORATORIUM
Przedmiot: Programowanie współbieżne i rozproszone |
|
|
|
Kierunek studiów: INFORMATYKA |
Rok studiów: I |
|
Rok akademicki: 2010/2011 |
|
|
Temat: Eliminacja metodą Gaussa
|
|
|
|
|
|
Wykonał: inż. Kajetan Dutkiewicz |
|
|
|
|
|
|
|
1. 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. Metoda Gaussa używa operacji elementarnych. Nazwa metody pochodzi od nazwiska niemieckiego matematyka Carla Friedricha Gaussa.
2. 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;
}
3. Zrzut ekranowy
4. Wykresy
1) Zależność czasu obliczania od ilości wątków:
2) Wzrost przyspieszenia wykonywania programu na wątkach.
5. Podsumowanie
Obliczenia wykonane zostały na komputerze uczelnianym. Jak można było zaobserwować zastosowanie wielowątkowości przyspieszyło działanie programu.
Wyszukiwarka