Arhitektura računala 2, vježba 3
Utjecaj arhitekture na programsku podršku

Predmet ove vježbe su utjecaji arhitektonskih svojstava računala na izvođenje programa u višem programskom jeziku. Po mogućnosti izvedite vježbe na različitim arhitekturama (x86, ARM, ...) te usporedite rezultate.

1. uređaj bajtova u riječi (endianness)

Napisati program kojim se testira način uređenja bajtova u riječi računala. Odrediti kakav uređaj bajtova koristi arhitektura x86 te, po mogućnosti, neka druga arhitektura (npr. ARM).

Uputa: sadržaj pojedinačnih bajtova riječi otkrijte prikladnim pokazivačem.

2. priručne memorije

Cilj vježbe je analizirati utjecaj priručne memorije na performansu programa. Zadatak riješiti po slijedećim točkama:

1. Odrediti strukturu priručnih memorija (L1, L2) ciljnog računala, tj, kapacitet, širinu linije, i asocijativnost.

   Uputa: Sasvim općenito, model procesora može se odrediti prema modelu računala ili prema računu za računalo kupljeno po komponentama. Parametri priručnih memorija mogu se pronaći na mrežnim stranicama modela procesora ili na specijaliziranim stranicama poput http://wikichip.org.

   Na računalima pod Linuxom tu informaciju možemo dobiti i od operacijskog sustava. Dovoljno je pročitati sistemsku datoteku /proc/cpuinfo ili datoteke iz kazala /sys/devices/system/cpu/ (npr. datoteku cpu0/cache/index2/size).

   cat /proc/cpuinfo

   Još jedna mogućnost je osloniti se na specijalizirane aplikacijske programe. Primjeri takvih programa na inuxu su: hwinfo, lshw , lscpu ili dmidecode. Na Windowsima postoje CPU-Z, System information viewer i x86info. Nedostatak ovog pristupa je potreba za instalacijom programa.

   BONUS Na procesorima s modernim varijantama arhitekture x86, ovaj zadatak možete riješiti i vlastitim programom koji poziva instrukciju CPUID (Wikipedia, Intel).

2. Napisati program u C-u ili C++-u koji će pokazati razliku brzine pristupa podatcima:

   • u priručnoj memoriji L1,
   • u priručnoj memoriji L2,
   • u priručnoj memoriji L3,
   • izvan priručnih memorija (dakle - u RAM-u).

   Uvedimo sljedeće oznake:

   • s1 ... veličina priručne memorije L1;
   • b1 ... veličina linije priručne memorije L1;
   • s2, b2 ... analogno za priručnu memoriju L2;
   • s3, b3 ... analogno za priručnu memoriju L3.

   Program treba izmjeriti prosječnu ostvarenu propusnost pristupa bajtovima spremnika tijekom velikog broj izvođenja svakog od sljedeća četiri potprograma:

   • potprogram A: svi bajtovi memorijskog spremnika veličine s1 redom se uvećavaju za jedan
   • potprogram B: za jedan se uvećava svaki b1-ti bajt memorijskog spremnika veličine 2*s1
   • potprogram C: za jedan se uvećava svaki b2-ti bajt memorijskog spremnika veličine 2*s2
   • potprogram D: za jedan se uvećava svaki b3-ti bajt memorijskog spremnika veličine 2*s3

   Potprogrami B i C koriste memorijski spremnik koji je veći od priručne memorije čije promašaje analiziramo (L1, L2 ili L3), ali ipak manji od kapaciteta memorije na sljedećoj hijerarhijskoj razini (dakle, ako testiramo L1, spremnik je manji od L2).

   Svaki od navedenih potprograma treba pozivati velik broj puta, u programskoj petlji. Vidimo da će potprogram A generirati promašaj priručne memorije L1 relativno rijetko (jednom u b1 pristupa). Potprogram B će generirati promašaj priručne memorije L1 u svakom pristupu, ali će velika većina tih pristupa biti unutar priručne memorije L2. Potprogram C će generirati promašaj priručne memorije L2 u svakom pristupu, ali će velika većina tih pristupa biti unutar priručne memorije L3. Potprogram D će generirati promašaj priručne memorije L3 u svakom pristupu.

   Za svaki potprogram potrebno je odrediti prosječno vrijeme pristupa pojedinom podatku, kao i postignutu propusnost u MB/s. Na temelju dobivenih podataka ocijeniti omjer vremena pristupa pojedinim elementima memorijske hijerarhije: t(L2)/t(L1), t(L3)/t(L2), t(RAM)/t(L3).

   Upute:
   

   • prije obavljanja mjerenja, inicijalizirajte sve bajtove spremnika na 0 (kako bismo spremnik učitali u najbržu priručnu memoriju koja je veća od njega te kako optimizirajući prevoditelj ne bi pomislio da mi radimo nešto beskorisno);
   • mjerenje izvedite procedurom clock (<time.h>);
   • kako bi mjerenje bilo pouzdanije, eksperiment ponovite u petlji tako da trajanje bude reda veličine sekunde;
   • nakon mjerenja, pozbrajajte sve elemente spremnika i ispišite rezultat (kako bismo uvjerili prevoditelja da nam je stalo do rezultata);
   • pri prevođenju koristite optimizaciju (za gcc: -O3 -march=native);
   • onemogućite pretpribavljanje podataka povećanjem pomaka u petlji; npr. za potprogram B možete preskakati delta*b1 umjesto b1 bajtova uz delta=8; obratite pažnju da u tom slučaju i veličinu spremnika morate pomnožiti s istim faktorom;
   • BONUS: Provjerite da li su naše pretpostavke o promašajima i pogotcima priručne memorije opravdane. To se može napraviti konfiguriranjem i propitivanjem odgovarajućih internih brojača procesora, pri čemu nam od pomoći može biti biblioteka PAPI.
   • BONUS2: Napišite program za određivanje širine linije i ukupnog kapaciteta cacheva (L1i, L1d, L2) procesora instrukcijske arhitekture x86.

3. Česti su programi koji 2D matrice implementiraju linearnim spremnicima. Ako je buf adresa spremnika, i i j indeksi retka i stupca, a rows i cols dimenzije matrice, onda odgovarajućem elementu pristupamo s buf[i*cols+j]. Često je potrebno istu operaciju primijeniti nad svim elementima matrice u dvostrukoj petlji, npr pri operaciji zbrajanja matrica. Postavlja se pitanje što je bolje, prvo petljati po i pa onda po j ili obratno. Zadatak je eksperimentalno utvrditi ovu činjenicu za velike matrice koje ne mogu stati u memoriju L2. Komentirati rezultate.

   Upute

   • Kreirati polje N * M slučajnih cjelobrojnih podataka (int), tako da M * sizeof(int) bude jednak veličini memorije L2.
   • Kvalificirati sve pokazivače na polje ključnom rječju volatile kako prevoditelju ne bi palo na pamet izmijeniti redoslijed obilaska polja.
   • Inicijalizirati sve elemente polja na 0.
   • Izmjeriti trajanje izvođenja potprograma koji vraća zbroj svih elemente ulaznog polja.
   • Izmjeriti trajanje alternativnog potprograma u kojem su zamijenjeni redosljedi petlji po retcima i stupcima.
   • Kao i ranije, koristiti optimizaciju, za svaki slučaj na kraju ispisati povratne vrijednosti potprograma, te ispisati omjer postignutih performansi.
   • BONUS Ponoviti sve ovo za slučaj pisanja (npr. inicijalizacija matrice) te čitanja i pisanja (npr. zbrajanje dvaju matrica). Komentirati ostvarene rezultate.

3. utjecaj tipa podataka na performansu programa

Cilj vježbe je analizirati utjecaj (i) ugrađenog tipa podataka te (ii) odabir elementarne operacije na performansu programa. Vezano uz program iz 2c), potrebno je napraviti sljedeće:

• operaciju uvećavanja za jedan treba zamijeniti sa zbrajanjem, množenjem odnosno dijeljenjem s proizvoljno zadanom konstantom (npr. 23).
• kako biste omeli prevoditelja da emitira kod koji je prilagođen množenju s našom konstantom, broj 23 smjestite u varijablu kvalificiranu kao volatile (npr. volatile int magic=23;)
• odredite trajanje izvođenja petlji s tri različite operacije, za tri različite veličine spremnika i za sve elementarne tipove podataka (int, char, short, float i double).
• tri veličine spremnika treba odabrati na način da:
  1. najmanja veličina bude nešto manja od osmine priručne memorije L1,
  2. srednja veličina bude nešto manja od osmine priručne memorije L2,
  3. najveća veličina bude veća od priručne memorije L2.
• obratite pažnju na sljedeće važne detalje:
  1. trebate dojaviti prevoditelju da koristi maksimalnu optimizaciju i SSE (na gcc-u: -O3 -msse4)
  2. spremnik treba poravnati na 16 bajta ili više, i to na način da to bude jasno i prevoditelju; to možete postići na način da ga alocirate statički ili korištenjem posebnog alokatora (na POSIX-u: posix_memalign)
• program treba sastaviti na način da se sve tražene vrijednosti ispisuju na ekran u tabličnom obliku

4. Upute za predaju u sustav Ferko

Ako procesor kojeg ispitujete ima priručnu memoriju L3, u komentaru uključite i parametre s3, b3, te odredite t(RAM)/t(L3) te t(L3)/t(L2).

Preporučujemo da napravite cijelu pripremu kako biste bili spremni za kolokviranje vježbe.