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:
- Skompilujte a spustite program (vyriešte prípadné problémy, ak
sa to hneď nedá).
- 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é)?
- Zmeňte program tak, aby využíval viac threadov
- napíšte novú funkciu void nasobMatice_th(int pocet_t),
ktorá urobí nevyhnutnú inicializáciu pre násobenie (čo to
presne je, to zistíte neskôr keď naprogramujete telo
threadu) vytvorí pocet_t threadov, spustí ich a počká
kým skončia
Rady:
- Na vytvorenie threadov použite vzor z ukážkového programu
z prednášky. Ale musíte ho vhodne prepracovať.
- Upravte prebratý kód tak, aby vytváral viac threadov
(koľko ich treba?) nie dva.
- V našom prípade nepotrebujeme prenášať parametre z
hlavného programu do tela threadu, preto 4. parameter
CreateThread (resp. pthread_create) má byť
NULL
- Nepotrebujeme spustiť thread až neskôr, preto pre Windows
5. parameter CreateThread môže byť 0 a ResumeThread
vôbec netreba volať.
- Výsledná matica sa bude vytvárať po jednotlivých prvkoch
riadok za riadkom. Zadeklarujte dve globálne celočíselné
premenné riadok a stlpec, v ktorých budú
uložené súradnice prvého prvku výslednej matice, ktorý
ešte žiadny thread nepočíta resp. nepočítal. Na začiatku
to má byť (0,0) - zabezpečte to vo funkcii nasobMatice_th
(nestačí to zapísať v deklarácii premennej, lebo riadok a
stĺpec potrebujeme nulovať vždy keď ideme počítať ďalši
súčin).
- Naprogramujte telo threadu (funkciu MojThread
z ukážok) podľa tohto návodu:
- Bude mať dve lokálne celočíselne premenné r a s,
v ktorých budú uložené súradnice prvku výslednej matice,
ktorý sa práve počíta.
- Zvyšok tela je nekonečný cyklus.
- Najprv do r priradí riadok a do s
priradí stlpec.
- Potom zmení riadok a stlpec tak, aby tieto
ukazovali na ďalší prvok v tom istom riadku alebo, ak by sme
tým "vyšli" z matice, tak na prvý prvok v nasledujúcom
riadku.
- Ak je r >= n (testujte r, nie riadok!),
tak thread skončí lebo už je celá matica vypočítaná.
- Vypočíta jeden prvok výslednej matice s indexom r
a s pomocou volania funkcie nasobRS podobne
ako to robí pôvodná verzia programu vo funkcii nasobMatice.
- V hlavnom programe zmeňte volanie funkcie nasobMatice
na volanie nasobMatice_th(1) (teda sa má vytvoriť len
jeden thread) a odlaďte program tak, aby dával správny
výsledok (rovnaký ako pôvodný program).
- 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).
- 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
- 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.
- 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.