grzesiusprawko2, Semestr 8-9


0x01 graphic

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);

  1. WYNIKI POMIARÓW: