Programowanie współbieżne i rozproszone
laboratorium
Kierunek studiów: |
Informatyka studia II-go stopnia |
Rok studiów: |
I |
Rok akademicki: |
2010/2011 |
Semestr: |
I |
Temat: |
|
|
Ćwiczenie 2: Operacje na macierzach |
Lp. |
Imię |
Nazwisko |
Sprawozdanie oddano dnia: |
Ocena: |
1. |
Kajetan |
Dutkiewicz |
10.05.2011 |
|
Termin zajęć: |
Prowadzący: |
|
dzień: |
Wtorek |
dr hab. inż. J. Sadecki Prof. PO |
godzina: |
12:50 |
|
grupa: |
L2 |
|
1. Cel ćwiczenia
Celem ćwiczenia było przygotowanie programu wykonującego obliczenia na macierzach. Do obliczeń należą: mnożenie macierzy, mnożenie macierzy przez skalar oraz dodawanie macierzy. Program miał być wykonany w taki sposób, aby obliczenia były przeprowadzane na wielu rdzeniach.
2. Wstęp teoretyczny
Macierz to układ zapisych w postaci prostokątnej tablicy danych. Określona na tym zbiorze struktura algebraiczna umożliwia wprowadzenie działań algebraicznych na macierzach. Najczęściej współczynniki macierzy są elementami pewnego ciała bądź pierścienia przemiennego, jednak w ogólności wystarczy dowolna abstrakcyjna struktura, której wielkości można dodawać i mnożyć.
Macierze wykorzystuje się do opisu układów równań liniowych, przechowywania współczynników przekształceń liniowych. Macierze bada dział matematyki nazywany teorią macierzy. Dzięki swoim algebraicznym własnościom są one kluczowym pojęciem algebry liniowej.
Słowo „macierz” oznacza najczęściej macierz dwuwskaźnikową (tablicę dwuwymiarową), jednak rozważa się również macierze wielowskaźnikowe. Macierze jednowskaźnikowe, czyli tablice jednowymiarowe utożsamia się zwykle z wektorami, patrz niżej. W informatyce odpowiednikiem macierzy jest tablica dwuwymiarowa.
3. Kod źródłowy:
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>
#include <time.h>
//włączenie odmierzania czasu
start = times(&t_start);
printf("Alokuje pamieć...\nwielkość macierzy:\nA[%d][%d]\nB[%d][%d]\nC[%d][%d]",N,M,M,K,N,K);
// alokacja pamięci
A = (double**)malloc(N * sizeof(double*));
B = (double**)malloc(M * sizeof(double*));
C = (double**)malloc(N * sizeof(double*));
for (i = 0; i < N; i++){
A[i] = (double*)malloc(M * sizeof(double));
}
for (i = 0; i < M; i++){
B[i] = (double*)malloc(K * sizeof(double));
}
for (i = 0; i < N; i++){
C[i] = (double*)malloc(K * 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();
}
}
for (i = 0; i < M; i++) {
for ( j = 0; j < K; j++ ){
B[i][j] = rand();
}
}
//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);
//algorytm sekwencyjny mnożenia macierzy
//wyłączenie odmierzania czasu
end = times(&t_end);
doit("\nCzas wykonania mnozenia macierzy przez wektor przy użyciu algorytmu równoległego -1 wątek", end - start);
printf("Czyszcze macierz wynikową------------------------------------");
for (i = 0; i < N; i++) {
for ( j = 0; j < K; j++ ){
C[i][j] = 0;
}
}
//--------------------------------------------------------
//równoległy 2 wątki
start = times(&t_start);
// C = A*B.
#pragma omp parallel for shared(A, B, C, N, M, K) private(i, j,k)num_threads(2)
for (i=0; i<N; i++){
for (k=0;k<K;k++){
C[i][k] = 0;
for(j=0; j<M; j++)
C[i][k] += A[i][j] * B[j][k];
}
}
end = times(&t_end);
doit("\nCzas wykonania mnozenia macierzy przez wektor przy użyciu algorytmu równoległego -2 wąteki", end - start);
printf("Czyszcze macierz wynikową------------------------------------");
for (i = 0; i < N; i++) {
for ( j = 0; j < K; j++ ){
C[i][j] = 0;
}
}
//--------------------------------------------------------
//równoległy 3 wątki
start = times(&t_start);
// C = A*B.
#pragma omp parallel for shared(A, B, C, N, M, K) private(i, j,k)num_threads(3)
for (i=0; i<N; i++){
for (k=0;k<K;k++){
C[i][k] = 0;
for(j=0; j<M; j++)
C[i][k] += A[i][j] * B[j][k];
}
}
end = times(&t_end);
doit("\nCzas wykonania mnozenia macierzy przez wektor przy użyciu algorytmu równoległego -3 wąteki", end - start);
printf("Czyszcze macierz wynikową------------------------------------");
for (i = 0; i < N; i++) {
for ( j = 0; j < K; j++ ){
C[i][j] = 0;
}
}
//--------------------------------------------------------
//równoległy 4 wątki
start = times(&t_start);
// C = A*B.
#pragma omp parallel for shared(A, B, C, N, M, K) private(i, j,k)num_threads(4)
for (i=0; i<N; i++){
for (k=0;k<K;k++){
C[i][k] = 0;
for(j=0; j<M; j++)
C[i][k] += A[i][j] * B[j][k];
}
}
end = times(&t_end);
doit("\nCzas wykonania mnozenia macierzy przez wektor przy użyciu algorytmu równoległego -4 wąteki", end - start);
printf("Czyszcze macierz wynikową------------------------------------\n\n");
for (i = 0; i < N; i++) {
for ( j = 0; j < K; j++ ){
C[i][j] = 0;
}
}
//--------------------------------------------------------------
// DODAWANIE MACIERZY
printf("DODAWANIE MACIERZY\n");
// SEKWENCYJNIE
start = times(&t_start);
for (i=0; i<N; i++){
for (k=0;k<K;k++){
C[i][k] = A[i][k] + B[i][k];
}
}
//wyłączenie odmierzania czasu
end = times(&t_end);
//wyswietlenie czasu inicjalizacji macierzy
doit("\nCzas wykonania dodawania macierzy przy użyciu algorytmu sekwencyjnego", end - start);
//Czyszczenie macierzy C (wynikowej)
printf("Czyszcze macierz wynikową ------------------------------------");
for (i = 0; i < N; i++) {
for ( j = 0; j < K; j++ ){
C[i][j] = 0;
}
}
// zwolnienie pamięci
for (i = 0; i < N; i++)
free(A[i]);
for (i = 0; i < M; i++)
free(B[i]);
for (i = 0; i < N; i++)
free(C[i]);
free(A);
free(B);
free(C);
return 0;
}
//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);
}
Fragment kodu odpowiedzialny za wykonanie operacji dodawania macierzy w programie:
// 1 WĄTEK
start = times(&t_start);
#pragma omp parallel for shared(A, B, C, N, M, K) private(i, j,k)num_threads(1)
for (i=0; i<N; i++){
for (k=0;k<K;k++){
C[i][k] = A[i][k] + B[i][k];
}
}
//wyłączenie odmierzania czasu
end = times(&t_end);
Fragment kodu odpowiedzialny za wykonanie operacji mnożenia macierzy przez skalar:
// 1 WĄTEK
start = times(&t_start);
#pragma omp parallel for shared(A, B, C, N, M, K) private(i, j,k)num_threads(1)
for (i=0; i<N; i++){
for (k=0;k<K;k++){
C[i][k] = A[i][k] * skalar;
}
}
//wyłączenie odmierzania czasu
end = times(&t_end);
WYNIKI POMIARÓW:
Dodawanie macierzy
Algorytm |
Czas wykonania operacji |
Sekwencyjny |
1,24s |
1 wątek |
1,22s |
2 wątki |
0,64s |
3 wątki |
0,48s |
4 wątki |
0,46s |
Mnożenie macierzy przez skalar
Algorytm |
Czas wykonania operacji |
Sekwencyjny |
1,9s |
1 wątek |
1,4s |
2 wątki |
0,7s |
3 wątki |
0,62s |
4 wątki |
0,58s |
Mnożenie macierzy
Algorytm |
Czas wykonania operacji |
Sekwencyjny |
126,55s |
1 wątek |
127,43s |
2 wątki |
64,32s |
3 wątki |
40,63s |
4 wątki |
38,09s |
5. Wykresy:
6. Wnioski
Wykresy zależności czasu pracy rdzeni od ich liczby wskazują zwiększenie wydajności przy wskazanych poleceniach. Zadanie zostało wykonane prawidłowo. Można zauważyć największy wzrost wydajności przy zmianie trybu pracy z jednego rdzenia na dwa.
POLITECHNIKA OPOLSKA
WYDZIAŁ ELEKTROTECHNIKI, AUTOMATYKI I INFORMATYKI