c++ více vláken, stejná cache

přestane platit cache

co??? Ziadna cache neprestane platit. Mas chybu v programe.

BTW. vies co to je critical section? Ak nie tak to je ta chyba.

Vím co je to kritická sekce.

Program funguje bez problému, nejsou tam žádné chyby. Jen je pomalejší, když vytvořím více než jedno vlákno.

int promenna = 0;

void vlakno(){
while(nejaka podmínka){
...nejaky kod;

LOCK();
promenna = promenna + 1;
UNLOCK();
}
}

Pokud mám jedno vlákno, tak to jedno vlákno má uloženou proměnnou "promenna" v cachce a nemusí sahat vůbec do paměti. Program je pak o něco rychlejší kvůli tomu.

Když mám dvě vlákna, tak každé vlákno má svoji vlastní cachce. Pokaždé když se tedy změní proměnná "promenna", musí ji jedno vlákno uložit do paměti, a druhé má neplatnou cache, a tak ji musí zase načíst z paměti. Program je potom mnohem pomalejší. (cache je rychlejší než paměť).

Proto by bylo vhodné nějak zařídit aby ty sdílené proměnné byli i ve stejné cache.

cache je rychlejší než paměť

to je asi každému jasné...

Program je potom mnohem pomalejší

o aké presne spomalenie ide? Meral si to? Načítať data z RAM namiesto cache - nebavím sa o nejakých mili-micro sekundách...

No testuju program na 16 jádrovým procesoru.

Napíšu dobu trvání a počet jader (pokaždé program vypočítá stejnou věc, ale to je snad jasný)

1 Vlákno: 0.5 sekundy
2 Vlákna: 0.9 sekundy
4 Vlákna: 2.5 sekundy
8 Vláken: 5.8 sekundy
16 Vláken: 9.0 sekundy
32 Vláken: 9.1 sekundy
64 Vláken: 9.3 sekundy
128Vláken: 9.5 sekundy

Takže je zjevný, že na čím větším počtu jader program běží, tím je pomalejší (tím častěji mu nějaké jiné vlákno změní data, které on má v cache(musí je načíst znova)).
Při použití více jak 16ti vláken se program nezpomaluje, neb se o tu práci dělí 16 jader s 16ti cache paměťmi.

Tvoj program sa síce spomalí, ale ako si prišiel na to, že za to môže nejaká cache? Skutočne si myslíš, že pri 128 vláknach je možné, aby nejaká cache spomalila beh programu z 0,5 sekundy na 9,5 sekundy? Len pre predstavu, načítanie premennej z pamäte (bez cache) môže trvať odhadom tak 40 nanosekúnd. Problém bude teda zrejme niekde inde - bez konkrétneho kódu ale ťažko povedať, že kde. Ako prvé by som na tvojom mieste skontroloval, či nedržíš nejaký zámok dlhšie, než potrebuješ.

Tak mi teda vysvětlete, jakto že se program přestane zpomalovat, když je tam více než 16 jader??

Když má každé jádro svoji vlastní cache, tak je zřejmé, že pokaždé, když:

1. vlákno chce přistoupit do cache, tak zjistí že je neplatná

1. musí požádat 2. vlákno aby tu chache nahrála do paměti

2. vlákno nahraje cache do paměti

1. vlákno teprve teď může přistoupit k cache.

Takže ano, zpomalí se to kvůli cache.

Zkusím to změřit znovu, a použít jedno jádro, a více vláken, a potom opět 16 jader, a více vláken...

Spuštění programu na jednom jádru (taskset 0x00000001 ./xyz)
1 Vlákno: 0.5 sec
2 Vlákno: 0.5 sec
4 Vlákno: 0.6 sec
8 Vlákno: 0.5 sec
16 Vlákno: 0.6 sec
32 Vlákno: 0.6 sec
64 Vlákno: 0.6 sec
128 Vlákno: 0.7 sec
10 000 Vl.: 0.7 sec

Spuštění programu na ctyřech jádrech (taskset 0x0000000F ./xyz)
1 Vlákno: 0.5 sec
2 Vlákno: 0.9 sec
4 Vlákno: 2.6 sec
8 Vlákno: 3.0 sec
16 Vlákno: 2.9 sec
32 Vlákno: 3.0 sec
64 Vlákno: 3.0 sec
128 Vlákno: 3.1 sec
10 000 Vl.: 3.2 sec

Spuštění programu na osmi jádrech (taskset 0x000000FF ./xyz)
1 Vlákno: 0.4 sec
2 Vlákno: 0.9 sec
4 Vlákno: 2.6 sec
8 Vlákno: 5.7 sec
16 Vlákno: 6.0 sec
32 Vlákno: 5.6 sec
64 Vlákno: 6.3 sec
128 Vlákno: 6.2 sec
10 000 Vl.: 6.4 sec

Spuštění programu na šestnácti jádrech (taskset 0x0000FFFF ./xyz)
1 Vlákno: 0.5 sec
2 Vlákno: 0.9 sec
4 Vlákno: 2.5 sec
8 Vlákno: 5.9 sec
16 Vlákno: 9.5 sec
32 Vlákno:10.6 sec
64 Vlákno:10.3 sec
128 Vlákno:10.0 sec
10 000 Vl.: 9.4 sec

Ten program s 10000 vlákny je pokaždý uplně stejný, jen jednou běží na jednom jádru, a doba trvání je 0.7, a podruhé na šestnácti, a doba trvání je 9.4

Takže naprosto vážně je chyba v cache

Ak je teda chyba v cache, tak vytvor pre každé jadro vlastnú frontu a požiadavky do nich rozdeľuj podľa nejakého algoritmu. Ja si ale nemyslím, že by si mal problém s cache.

Je kopec vecí, ktoré ovplyvňujú správanie viacvláknových aplikácií:
- Akým spôsobom vytváraš nové vlákna? Je čas vytvárania vláken zahrnutý do meraného času?
- Aká je povaha úloh, ktoré sú spracovávané vo viacerých vláknach? Ide o úlohy zaťažujúce CPU, alebo sa vykonáva veľa I/O operácií?
- Ako presne robíš synchronizáciu medzi vláknami? Čo presne vykonávaš vo vnútri kritických sekcií?

Tie časy, ktoré si odmeral, bolo pre spracovanie koľkých úloh? Spravil by som si štatistiku, že koľko požiadaviek spracujú jednotlivé vlákna - výsledok ti možno dá odpoveď na to, prečo sa spracovanie nespomalí v prípade behu na jednom jadre.

Jednou vytvořím vlákna a dohromady spočítají asi 500 000 úloh. (když jich je 10 000 tak každé vlákno spočítá +- 50 úloh)

Jinak nepoužívat společnou frontu je dobrý nápad, vyzkouším.

To dotazovatel: Tvoje predstavy o cache su absolutne mylne. Tak to nefunguje, a tvoj problem neni cache. A vlakno nema ziadnu vlastnu cache. Tvoj problem je najskor to, ze mas neoptimalne urobenu critical section. To je ale problem programatora, ne cache.

Pokud ti program funguje rychleji bez vlaken, proc se jej snazis delat s vlakny? Pokud prinasi obsluha vlaken vyssi rezii nez vlastni prinos vicevlaknove aplikace, pak nema smysl to vlakny resit.

Možno to testuje na jednojadrovom CPU...

Cache funguje na HW urovni a nezaujimaju ju ziadne vlakna. Ked ti program nefunguje tak jak ma alebo tak jak ocakavas, tak mas v nom chybu (alebo v koncepte). Nechce sa mi lustit teraz tvoj program (ani si tu ziaden nedal, len splietas nezmysly)

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

#define THREADS_NUMBER 4

using namespace std;


pthread_mutex_t mx = PTHREAD_MUTEX_INITIALIZER;
int x = 0;

//vlakno
void * func(void * nic){
    while(x < 1000000){
        pthread_mutex_lock(&mx);
        x = x + 1;
        pthread_mutex_unlock(&mx);
    }
}

// The main progam.
int main() {
    clock_t t1,t2;
    t1=clock();
    //vytvoreni vlaken
    pthread_t main_thread[THREADS_NUMBER];
    for(int i = 0; i < THREADS_NUMBER; i++){
        pthread_create(&main_thread[i], NULL, &func, (void*)&x);
    }
    //cekani na dokonceni prace vlaken
    for(int i = 0; i < THREADS_NUMBER; i++){
        pthread_join(main_thread[i], NULL);
    }
    t2=clock();
    cout << ((float)t2-(float)t1)  << endl;
    return 0;
}

Příklad kódu na kterým je to nejvíce vidět.

pokaždé jsou v programu 4 vlákna, všechny udělají stejný počet operací, ale pokud program pustíte na jednom jádře, tak bude výrazně rychlejší než když povolíte všechny jádra. (správce úloh >> podrobnosti >> spřažení >> jedno jádro pro příkazovej řáek ze kterýho to budete spouštět.)

Asi jsem se minule někde upsal, ale myslel jsem to tak, že každé jádro má vlastní cache.
Když tedy běží čtyři vlákna na jednom jádře procesoru - sdílí stejnou cache.
Když běží čtyři vlákna na čtyřech jádrech procesoru - mají každou svoji vlastní cache.

Ještě k tomu, když bych snad vytvářel vlákna nějak špatně, a kvůli tomu by se to zpomalilo. Proč to zpomalení není vidět v případě, kdy program běží na jednom jádře procesoru (jedna cachce pro všechny vlákna) a vytváří 10 000 vláken ??

Kazde jadro ma svoju L1 cache, L2 cache je spolocna. Vsetko je vec HW a neda sa to zmenit.
V tom programe nic neratas a vpodstate vsetky thready vkuse cakaju na lock. Za normalnych okolnosti thready maju robit ulohu ktora je XYZXYZ x narocnejsia jak lock. potom sa to neprejavuje.
P.S. a to je ta tvoja "chyba" (koncept pri multiprocesingu)

Ale jak píšu, když program běží v jednom jádře procesoru, (jedna L1 cachce) tak se problém neprojeví

Ale ty nemas program, ty mas prazdny lock a unlock. Jasne ze synchronizacia medzi core ma nejaku reziu. To neni problem, to je fakt ktory ma vediet kazdy programator. Az napises program normalny, ktory pracuje XYx dlhsie jak synchronizuje, tak nebudes mat ziaden problem.
P.S. uz pred 20rokmi sa to ucilo na vyske, bol o tom cely semester. Rezii sa nevyhnes, musis programovat tak aby to nevadilo alebo aby dopad bol minimalny. Napr. tak ze zoberes pre kazdy thread na vysokej urovni programu vacsi kus ulohy a unlocknes a makas, a nebudes to lockovat furt na najnizsej urovni.

Alebo napr. mozes mat frontu pre kazdy thread svoju, a ten kto vklada do fronty to rozdeluje do ciastkovych front apod. (a budes mat pevny pocet threadov napr. 4) ak to vkladanie neni casto apod.(zavisi od toho co riesis a k tomu treba urobit koncept). Alebo thready robia kazdy nieco ine. Ciel je minimalizovat synchronizaciu medzi cores. A je nezmysel vytvarat 10000 threadov, synchronizacia threadov ma vzdy overhead. Ktory si prave zmeral.

P.S. 2core spolu NEurobia nikdy tolko ako 1core 2xrychlejsie. To sa uci snad ako prve.

Ak tvoj program vyzerá podobne, tak potom áno, v spomalení zohráva svoju rolu aj cache na jednotlivých jadrách CPU. Všetky vlákna prakticky neustále súperia o vstup do kritickej sekcie. V tejto ukážke vlákna v podstate nerobia nič iné, než len sa medzi sebou synchronizujú.

Za normálnych okolností spracovanie z fronty vyzerá tak, že sa z nej vyberú dáta o úlohe a tá sa potom spracuje samostatne, bez potreby ďalšej synchronizácie. Synchronizovaný je len výber z fronty, ktorý zvyčajne trvá oproti spracovaniu zanedbateľný čas.

Ak sa nevieš vyhnúť tomu, aby sa tvoj program podobal tejto ukážke, tak to zadanie potom nie je vhodné na paralelizovanie a bude lepšie to spracovávať sekvenčne.