Cvičenie 3 - Multithreading
Pri riešení tohto cvičenia Vám, možno pomôžu:
Úloha:

Násobenie matíc je matematická operácia nad maticami, jej matematický popis nájdete napríklad tu:
https://sk.wikipedia.org/wiki/Matica_(matematika)
https://cs.wikipedia.org/wiki/N%C3%A1soben%C3%AD_matic

Vašou úlohou je sparalelniť program na násobenie matíc tak, aby sa použilo niekoľko threadov ("worker threads") kde jedna úloha každého threadu je vypočítať jeden prvok výslednej matice.
Násobenie matíc sa zvykne nazývať "Hello, World!" multithreadingu.

Vytvorte projekt typu Windows Console Application vo Visual Studiu a skopírujte doň tento kód (pre Linux alebo Clion s GCC viď poznámky pod ním):

#include <iostream>
#include <time.h>

#define MAXN 1000
#define MAXT 8

typedef double Matica[MAXN][MAXN];

Matica m1 = { {1,2}, {3,4} };
Matica m2 = { {1,2}, {1,2} };
Matica vysl;
int n;  // velkost vsetkych troch matic (su stvorcove)

double nasobRS(int r, int s) {
    int i;
    double sum;
    sum = 0;
    for (i = 0; i < n; i++)
        sum = sum + m1[r][i] * m2[i][s];
    return sum;
}

void nasobMatice() {
    int r, s;
    for (r = 0; r < n; r++)
        for (s = 0; s < n; s++)
            vysl[r][s] = nasobRS(r, s);
}

void vypisMaticu(Matica m) {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            printf("%f ", m[i][j]);
        printf("\n");
    }
}

void vyplnMaticu(Matica m) {
    int i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            m[i][j] = (float)rand()/RAND_MAX;

}

int main()
{
    clock_t t1, t2;

    n = 2;

    //vyplnMaticu(m1);
    //vyplnMaticu(m2);

    t1 = clock();
    nasobMatice();
    t2 = clock();
   
    printf("time = %.3f\n", ((float)(t2 - t1) / CLOCKS_PER_SEC));

    vypisMaticu(m1);
    vypisMaticu(m2);
    vypisMaticu(vysl);

    return 0;
}


Pre gcc v Linxe aleo v CLione treba zmeniť len prvé riadky s príkazmi include takto:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

Postupne plňte tieto podúlohy:
  1. Skompilujte a spustite program (vyriešte prípadné problémy, ak sa to hneď nedá).

  2. Preštudujte si program, zistite, čo robia jednotlivé funkcie.
    Čo znamená vypísaný výsledok?
    Zistite ako sa dá zmeniť rozmer matíc, ktoré program násobí.
    Aký je rozdiel medzi n a MAXN?
    Čo robí funkcia VyplnMaticu (ktorej volania sú zatiaľ zakomentované)?

  3. Zmeňte program tak, aby využíval viac threadov
  4. Naprogramujte testovanie správnosti výsledku - funkciu void test(), ktorá si zapamätá maticu vysl do iného poľa (to musí byť globálna premenná, lebo zásobník nie je dosť velký na uloženie lokálnej premennje typu Matica), potom vynuluje maticu vysl (to je dôležité z dôvodu ladenia programu) a potom vyvolá pôvodné jednothreadové násobenie (funkciu nasobMatice) a porovná výsledky. Vypíše ok alebo zle (zle má vypísať len raz nie toľkokrát koľko je zlých prvkov). Pridajte volanie test do hlavného programu a odlaďte (pre jeden thread to musí byť vždy ok).

  5. Zmeňte hlavný program aby násobil náhodne vytvorené matice 200x200 a nevypisoval ich hodnoty, ale len testoval, takto:
    int main()
    {
        clock_t t1, t2;

        n = 200;        // zmena

        vyplnMaticu(m1); // zmena
        vyplnMaticu(m2); // zmena

        t1 = clock();
        nasobMatice_t(2); // zmena, dva thready
        t2 = clock();
       
        printf("time = %.3f\n", ((float)(t2 - t1) / CLOCKS_PER_SEC));

        //vypisMaticu(m1);  // zmena
        //vypisMaticu(m2);  // zmena
        //vypisMaticu(vysl);  // zmena
       
        test();      // zmena

        return 0;
    }
    Skúste zmenený program, vypisuje stále ok?
    (Ak stále ok, tak asi máte v programe nejaký problém, možno nesprávne testujete výsledok alebo ste nesprávne naprogramovali

  6. Nájdite kritickú sekciu a vyriešte vzájomné vylúčenie pomocou objektu CRITICAL_SECTION (resp pthread_mutex_t v Linuxe), viď ukážka z prednášky (funkcia vyber_semafor, pre Windows  nezabudnite skopírovať aj volanie InitializeCriticalSection z funkcie main()).
    Otestujte - test musí dať vždy ok.

  7. Zmeňte v hlavnom programe n na 1000 a zapíšte si časy pre počet threadov 1, 2, 3, 4, 5 a 6 (spúšťajte program postupne s rôznou hodnotou parametra funkcie nasobMatice_th alebo naprogramujte cyklus v main).
    Zrýchli sa výpočet použitím dvoch threadov? A čo troch, štyroch...? Vidíte súvis medzi zrýchlením pre nejaký počet threadov a počtom jadier procesora daného počítača?
    Zapíšte namerané časy a odpovede do komentárov na konci v programu.