Мултипроцесорски системи/К2 2021 - Историја измена

Etfsibg: /* Rešenje */

2023-12-05T09:04:35Z

Rešenje

← Старија измена		Верзија на датум 5. децембар 2023. у 11:04
Ред 129:		Ред 129:

	=== Rešenje ===		=== Rešenje ===
	''Napomena:'' Uzeli smo pretpostavku da operacija flush samo upiše ažuran podatak u memoriju i uopšte ga ne prosledi drugom kešu koji ga je tražio, već će on morati da pristupi memoriji da bi pročitao tu vrednost. Moguća je i drugačija implementacija kod koje bi procesor koji uradi flush takođe i prosledio odmah procesoru koji je tražio podatak tu vrednost i onda taj drugi procesor uopšte ne bi pristupao memoriji jer bi imao taj podatak u svom kešu - tada bismo kod njega imali RH umesto RM pri pristupu tom podatku. Ako isprobate sekvence pristupa iz zadatka u Vivio simulatoru 5.1 videćete da flush funkcioniše ovako.

	{\| class="wikitable"		{\| class="wikitable"
	! CPU		! CPU

Etfsibg: /* Rešenje */

2023-12-03T19:55:45Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:55
Ред 46:		Ред 46:
	* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i u okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.		* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i u okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
	* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.		* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
	* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem ~~upisu~~ upisu prešlo sa ažuriranja na invalidaciju, drugi proces na drugom procesoru bi pronašao podatak u svom kešu). Kao što je bilo i očekivano, na osnovu rezultata simulacija zaključeno je da je bolje da se prelazi sa ažuriranja na invalidaciju tek pri trećem upisu i to samo kada svi procesori koji imaju kopiju tog podatka detektuju upisni niz dužine tri upisa (može se desiti da su neki procesori detektovali upisni niz dužine tri upisa, a da npr. jedan procesor prekine taj upisni niz tako što će da pročita taj podatak, pa je onda za njega upisni niz dužine nula upisa - u tom slučaju će se nastaviti sa primenom ažurirajućeg protokola sve dok nisu svi procesori (osim, naravno, onog koji upisuje u podatak) detektovali upisni niz dužine tri upisa, i tada će se preći na poništavajući protokol zbog čega će se onda invalidovati kopije u njihovim keševima).		* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu prešlo sa ažuriranja na invalidaciju, drugi proces na drugom procesoru bi pronašao podatak u svom kešu). Kao što je bilo i očekivano, na osnovu rezultata simulacija zaključeno je da je bolje da se prelazi sa ažuriranja na invalidaciju tek pri trećem upisu i to samo kada svi procesori koji imaju kopiju tog podatka detektuju upisni niz dužine tri upisa (može se desiti da su neki procesori detektovali upisni niz dužine tri upisa, a da npr. jedan procesor prekine taj upisni niz tako što će da pročita taj podatak, pa je onda za njega upisni niz dužine nula upisa - u tom slučaju će se nastaviti sa primenom ažurirajućeg protokola sve dok nisu svi procesori (osim, naravno, onog koji upisuje u podatak) detektovali upisni niz dužine tri upisa, i tada će se preći na poništavajući protokol zbog čega će se onda invalidovati kopije u njihovim keševima).

	== 5. zadatak ==		== 5. zadatak ==

Etfsibg: /* Rešenje */

2023-12-03T19:47:32Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:47
Ред 44:		Ред 44:

	=== Rešenje ===		=== Rešenje ===
	* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.		* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i u okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
	* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.		* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
	* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces na drugom procesoru bi pronašao podatak u svom kešu). Kao što je bilo i očekivano, na osnovu rezultata simulacija zaključeno je da je bolje da se prelazi sa ažuriranja na invalidaciju tek pri trećem upisu i to samo kada svi procesori koji imaju kopiju tog podatka detektuju upisni niz dužine tri upisa (može se desiti da su neki procesori detektovali upisni niz dužine tri upisa, a da npr. jedan procesor prekine taj upisni niz tako što će da pročita taj podatak, pa je onda za njega upisni niz dužine nula upisa - u tom slučaju će se nastaviti sa primenom ažurirajućeg protokola sve dok nisu svi procesori (osim, naravno, onog koji upisuje u podatak) detektovali upisni niz dužine tri upisa, i tada će se preći na poništavajući protokol zbog čega će se onda invalidovati kopije u njihovim keševima).		* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces na drugom procesoru bi pronašao podatak u svom kešu). Kao što je bilo i očekivano, na osnovu rezultata simulacija zaključeno je da je bolje da se prelazi sa ažuriranja na invalidaciju tek pri trećem upisu i to samo kada svi procesori koji imaju kopiju tog podatka detektuju upisni niz dužine tri upisa (može se desiti da su neki procesori detektovali upisni niz dužine tri upisa, a da npr. jedan procesor prekine taj upisni niz tako što će da pročita taj podatak, pa je onda za njega upisni niz dužine nula upisa - u tom slučaju će se nastaviti sa primenom ažurirajućeg protokola sve dok nisu svi procesori (osim, naravno, onog koji upisuje u podatak) detektovali upisni niz dužine tri upisa, i tada će se preći na poništavajući protokol zbog čega će se onda invalidovati kopije u njihovim keševima).

Etfsibg: /* Rešenje */

2023-12-03T19:42:38Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:42
Ред 7:		Ред 7:

	=== Rešenje ===		=== Rešenje ===
	~~Dva moguća~~ načina:		Do problema keš koherencije čak i kada se radi o privatnim podacima može doći na sledeća dva načina:
	* <b>Migracija procesa:</b> Do problema keš koherencije može doći čak i kada je reč o privatnim podacima zbog migracije procesa sa jednog procesora na drugi - to se može dogoditi npr. kada raspoređivač procesa pokuša da poboljša balans opterećenja u sistemu. Neka postoji podatak na adresi A0 u operativnoj memoriji sa vrednošću 0 i neka ga trenutno nijedan procesor nema u svom kešu. Neka se proces P0 nalazi na procesoru Proc1 sa keš memorijom C0. On može da dovuče podatak u keš i izmeni mu vrednost na 1 samo u svom kešu tako da podatak u memoriji sada nije ažuran. Neka se sada dogodi migracija procesa P0 sa procesora Proc0 na procesor Proc1 sa keš memorijom C1. Ako proces P1 sada pokuša da pročita podatak, prvo će ga potražiti u kešu C1, pa pošto ga tu neće pronaći pročitaće ga iz memorije, a pošto podatak u memoriji nije ažuran, sistem će ući u nekonzistentno stanje i time upravo nastaje problem keš koherencije.		* <b>Migracija procesa:</b> Do problema keš koherencije može doći čak i kada je reč o privatnim podacima zbog migracije procesa sa jednog procesora na drugi - to se može dogoditi npr. kada raspoređivač procesa pokuša da poboljša balans opterećenja u sistemu. Neka postoji podatak na adresi A0 u operativnoj memoriji sa vrednošću 0 i neka ga trenutno nijedan procesor nema u svom kešu. Neka se proces P0 nalazi na procesoru Proc1 sa keš memorijom C0. On može da dovuče podatak u keš i izmeni mu vrednost na 1 samo u svom kešu tako da podatak u memoriji sada nije ažuran. Neka se sada dogodi migracija procesa P0 sa procesora Proc0 na procesor Proc1 sa keš memorijom C1. Ako proces P1 sada pokuša da pročita podatak, prvo će ga potražiti u kešu C1, pa pošto ga tu neće pronaći pročitaće ga iz memorije, a pošto podatak u memoriji nije ažuran, sistem će ući u nekonzistentno stanje i time upravo nastaje problem keš koherencije.
	* <b>Lažno deljenje:</b> Do problema keš koherencije može doći čak i kada je reč o privatnim podacima zbog pojave "lažne deljivosti". Neka proces na procesoru Proc0 upisuje u podatak koji je u memoriji na adresi A0 i neka ga ima u svom kešu. Neka proces na procesoru Proc1 upisuje u podatak koji je u memoriji na adresi A1 i neka ga ima u svom kešu. Neka je veličina jednog bloka koji keševi dohvataju i smeštaju u jednu keš liniju veličine dve susedne memorijske lokacije. To bi značilo da, iako procesor Proc0 menja samo podatak sa adrese A0, a procesor Proc1 samo podatak sa adrese A1 (dakle, različite podatke) svaka takva modifikacija biće detektovana kao problem keš koherencije koji treba razrešiti iako tog problema uopšte nema, pa onda dolazi do bespotrebnog poništavanja ili ažuriranja podataka u zavisnosti od protokola koji se koristi za obezbeđivanje keš koherencije. Ovog problema ne bi bilo kada bi veličina bloka koji dohvataju keševi bila veličine jedne memorijske reči, ali je onda pitanje koliko bi bilo korisno takvo keširanje - zato je potrebno dobro razmisliti pri projektovanju keš memorije kolika bi trebalo da bude veličina jedne keš linije kako bi se istovremeno što bolje iskoristilo keširanje, ali isto tako i smanjila pojava "lažnog deljenja".		* <b>Lažno deljenje:</b> Do problema keš koherencije može doći čak i kada je reč o privatnim podacima zbog pojave "lažne deljivosti". Neka proces na procesoru Proc0 upisuje u podatak koji je u memoriji na adresi A0 i neka ga ima u svom kešu. Neka proces na procesoru Proc1 upisuje u podatak koji je u memoriji na adresi A1 i neka ga ima u svom kešu. Neka je veličina jednog bloka koji keševi dohvataju i smeštaju u jednu keš liniju veličine dve susedne memorijske lokacije. To bi značilo da, iako procesor Proc0 menja samo podatak sa adrese A0, a procesor Proc1 samo podatak sa adrese A1 (dakle, različite podatke) svaka takva modifikacija biće detektovana kao problem keš koherencije koji treba razrešiti iako tog problema uopšte nema, pa onda dolazi do bespotrebnog poništavanja ili ažuriranja podataka u zavisnosti od protokola koji se koristi za obezbeđivanje keš koherencije. Ovog problema ne bi bilo kada bi veličina bloka koji dohvataju keševi bila veličine jedne memorijske reči, ali je onda pitanje koliko bi bilo korisno takvo keširanje - zato je potrebno dobro razmisliti pri projektovanju keš memorije kolika bi trebalo da bude veličina jedne keš linije kako bi se istovremeno što bolje iskoristilo keširanje, ali isto tako i smanjila pojava "lažnog deljenja".

Etfsibg: /* Rešenje */

2023-12-03T19:19:53Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:19
Ред 46:		Ред 46:
	* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.		* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
	* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.		* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
	* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces na drugom procesoru bi pronašao podatak u svom kešu).		* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces na drugom procesoru bi pronašao podatak u svom kešu). Kao što je bilo i očekivano, na osnovu rezultata simulacija zaključeno je da je bolje da se prelazi sa ažuriranja na invalidaciju tek pri trećem upisu i to samo kada svi procesori koji imaju kopiju tog podatka detektuju upisni niz dužine tri upisa (može se desiti da su neki procesori detektovali upisni niz dužine tri upisa, a da npr. jedan procesor prekine taj upisni niz tako što će da pročita taj podatak, pa je onda za njega upisni niz dužine nula upisa - u tom slučaju će se nastaviti sa primenom ažurirajućeg protokola sve dok nisu svi procesori (osim, naravno, onog koji upisuje u podatak) detektovali upisni niz dužine tri upisa, i tada će se preći na poništavajući protokol zbog čega će se onda invalidovati kopije u njihovim keševima).

	== 5. zadatak ==		== 5. zadatak ==

Etfsibg: /* Rešenje */

2023-12-03T19:12:35Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:12
Ред 46:		Ред 46:
	* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.		* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
	* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.		* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
	* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces bi pronašao podatak u svom kešu).		* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces na drugom procesoru bi pronašao podatak u svom kešu).

	== 5. zadatak ==		== 5. zadatak ==

Etfsibg: /* Rešenje */

2023-12-03T19:12:15Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:12
Ред 46:		Ред 46:
	* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.		* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
	* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.		* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
	* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces bi pronašao podatak u svom kešu).		* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 od strane istog procesa na istom procesoru - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces bi pronašao podatak u svom kešu).

	== 5. zadatak ==		== 5. zadatak ==

Etfsibg: /* Rešenje */

2023-12-03T19:10:31Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:10
Ред 46:		Ред 46:
	* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.		* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
	* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.		* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
	* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi ~~dužina upisnog niza bila npr. tri upisa~~, drugi proces bi pronašao podatak u svom kešu).		* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi se tek pri trećem upisu upisu prešlo sa ažuriranja na invalidaciju, drugi proces bi pronašao podatak u svom kešu).

	== 5. zadatak ==		== 5. zadatak ==

Etfsibg: /* Rešenje */

2023-12-03T19:09:15Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:09
Ред 46:		Ред 46:
	* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.		* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
	* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.		* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
	* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi dužina upisnog niza bila tri upisa, drugi proces bi pronašao podatak u svom kešu).		* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi dužina upisnog niza bila npr. tri upisa, drugi proces bi pronašao podatak u svom kešu).

	== 5. zadatak ==		== 5. zadatak ==

Etfsibg: /* Rešenje */

2023-12-03T19:08:02Z

Rešenje

← Старија измена		Верзија на датум 3. децембар 2023. у 21:08
Ред 46:		Ред 46:
	* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.		* <b>Motivacija:</b> Ne može se reći da su generalno poništavajući protokoli za održavanje keš koherencije bolji od ažurirajućih ili obratno, zato što direktno zavisi od karakteristika same aplikacije koji tip protokola je bolje primeniti. Osnovni kriterijum koji se razmatra pri odabiru tipa protokola jeste procesorska lokalnost, tj. koliko se podaci koriste od strane samo jednog procesora. Indikator procesorske lokalnosti je dužina upisnog niza (''write run''), tj. koliko puta neki procesor uspe da upiše u dati podatak pre nego što ga neki drugi procesor zatraži za čitanje ili upis. Poništavajući protokoli su efikasniji za duže upisne nizove (npr. ako je dužina upisnog niza 20, jednom bismo javili ostalim procesorima na početku da invalidiraju svoje kopije, pa bismo onda lokalnim, jeftinim upisima u našu keš memoriju menjali podatak i onda bismo ga dostavili procesoru koji ga zatraži nakon naših 20 upisa; ovo je dosta efikasnije nego kada bismo koristili ažurirajući protokol jer bi se tada bespotrebno na svaki naš upis slala vrednost podatka svim procesorima iako nijednom ne treba ništa drugo osim vrednosti podatka nakon našeg poslednjeg, tj. 20. upisa). Ažurirajući protokoli su efikasniji za kraće upisne nizove (npr. ako je dužina upisnog niza 1, nakon svake izmene podatka u našem kešu slali bismo novu vrednost svim procesorima koji imaju kopiju tog podatka i u ovom slučaju je to odlično jer će svakako uvek neki drugi procesor zatražiti taj podatak nakon samo jednog našeg upisa, a ovako će ga tada uvek pronaći u svom kešu; ovo je dosta efikasnije nego kada bismo koristili poništavajući protokol jer bi onda vrednost podatka u ostalim procesorima nakon svakog upisa našeg procesora bila invalidirana, što znači da bi svi ostali procesori naredni put kada im zatreba taj podatak uvek promašili u svojim keševima). Sada kada znamo šta tačno znači procesorska lokalnost, jasno je da ona može biti promenljiva i okviru jedne aplikacije, što znači da je moguće da nekim delovima aplikacije više odgovaraju poništavajući protokoli, a drugim ažurirajući, pa se tako došlo do ideje o adaptivnim protokolima koji bi trebalo da kombinuju oba tipa protokola kako bi potencijalno bile ostvarene bolje performanse.
	* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.		* <b>Uobičajeni način rada:</b> Adaptivni protokoli keš koherencije obično prvo pretpostave da je dužina upisnog niza (''write run'') mala i zato prvo počnu sa primenom ažurirajućeg protokola. Ukoliko dužina upisnog niza poraste preko nekog unapred definisanog praga, onda se smatra da se tada više isplati poništavajući protokol i zato se onda prelazi na njegovo korišćenje. Pošto je ovo obično realizovano hardverski, transparentno je za programera, ali takođe povećava hardversku složenost sistema.
	* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju. Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi dužina upisnog niza bila tri upisa, drugi proces bi pronašao podatak u svom kešu).		* <b>Invalidacija u protokolu EDWP:</b> Kao preteča ''EDWP (Efficient Distributed Writing Protocol)'' protokolu prvo se pojavio ''RWB (Read and Write Broadcast)'' protokol kod kog se već za dužinu upisnog niza od dva upisa prelazi sa ažuriranja na invalidaciju (ta promena se dogodi već pri drugom upisu). Zaključeno je da je to prerano (npr. kod sinhronizacije procesa prvo se dogodi upis vrednosti 0 u deljenu promenljivu mutex, pa onda upis vrednosti 1 - tada npr. treba neki drugi proces na drugom procesoru da pročita tu vrednost mutex-a kako bi nastavio svoj rad, međutim ona je invalidirana jer je u nju pisano dva puta, pa će on promašiti u svom kešu; kada bi dužina upisnog niza bila tri upisa, drugi proces bi pronašao podatak u svom kešu).

	== 5. zadatak ==		== 5. zadatak ==