Nederlands
Menu

Wat is Array?

Een datastructuur die waarden van hetzelfde type achter elkaar opslaat en elk element aanwijst met een index. Omdat de elementen aaneengesloten in het geheugen staan, kan de positie van elk element uit de index worden berekend, zodat elk element in constante tijd kan worden gelezen of geschreven. Sommige talen laten indexen bij 0 beginnen, sommige notaties bij 1.

Japanse benaming: 配列

“Array” komt voor in 71 oefenvragen uit 14 onderwerpen, bijv. Basis van programmeren (pseudocode traceren), Datastructuren en algoritmen, GPU-programmeren.

Vakgebied: Basis van programmeren (pseudocode traceren)

Nu oefenen: vragen over Array

Bij een direct-mapped cache komen elementen van twee arrays op dezelfde cachepositie uit en verdringen elkaar bij elke afwisselende toegang. Tot welke categorie behoort deze miss?

  1. ACompulsory miss (eerste referentie)
  2. BCapaciteitsmiss
  3. CConflictmiss
Antwoord en toelichting tonen

Antwoord: C. Conflictmiss

Een miss waarbij twee gegevens om dezelfde set concurreren en elkaar verdringen terwijl er in de cache als geheel nog ruimte is, is een conflictmiss. Deze kan worden verminderd door de associativiteit te verhogen zodat twee of meer gegevens in dezelfde set passen, of door het begin van een array te verschuiven zodat deze op een andere set uitkomt. Een capaciteitsmiss wordt veroorzaakt doordat de working set groter is dan de hele cache en verdwijnt ook bij volledige associativiteit niet. Een compulsory miss treedt op bij de eerste toegang en past niet bij herhaalde toegangen.

Wanneer een rij van een tweedimensionale array 4096 byte (een macht van 2) groot is, kunnen er bij het langs de kolom doorlopen van elementen veel misses optreden, ook als de cache voldoende capaciteit heeft. Welke maatregel is daartegen effectief?

  1. AAan het einde van elke rij opvulling toevoegen, zodat de rijgrootte afwijkt van een macht van 2
  2. BHet type van de array wijzigen in een ander type van dezelfde grootte
  3. CDe hele array opnieuw plaatsen op een grote adresgrens die een macht van 2 is
Antwoord en toelichting tonen

Antwoord: A. Aan het einde van elke rij opvulling toevoegen, zodat de rijgrootte afwijkt van een macht van 2

Bij rijen van precies 4096 byte liggen de adressen van langs de kolom doorlopen elementen steeds een veelvoud van 4096 uit elkaar, hebben dezelfde indexbits binnen de onderste 12 adresbits en concentreren zich in zeer weinig sets (bij een L1-cache met ten hoogste 4 KB per weg allemaal in dezelfde set). Als meer rijen in één set terechtkomen dan de associativiteit toelaat, treden conflictmisses op waarbij elementen elkaar verdringen, ook bij ruime capaciteit. Met opvulling (padding) van ongeveer één regel per rij verschuift de bijbehorende set per element en wordt de belasting gespreid. Uitlijnen op een adres dat een macht van 2 is verandert het probleem niet, en een type van dezelfde grootte heeft geen effect.

“Array” in de toelichting

Vragen met “Array” (71)

  1. a0 bevat het beginadres van een array a van het type int (4 bytes) en a1 bevat de index i. Wat leest de bovenstaande code in a2?
  2. Een tweedimensionale C-array a[i][j] wordt doorlopen met j als binnenste lus. Dit is doorgaans sneller dan met i als binnenste lus. Wat is de reden?
  3. Bij een direct-mapped cache komen elementen van twee arrays op dezelfde cachepositie uit en verdringen elkaar bij elke afwisselende toegang. Tot welke categorie behoort deze miss?
  4. In bovenstaande lus is een int 4 byte, een cacheregel 64 byte, staat de array niet in de cache en begint hij op een regelgrens. Wat is, zonder prefetching, de missratio bij het lezen van de array?
  5. Waarom wordt een bewerking die alleen de x-coördinaten optelt vaak sneller wanneer een array van structs wordt omgeschreven tot een structuur van arrays (elke component in een eigen array)?
  6. Wanneer een rij van een tweedimensionale array 4096 byte (een macht van 2) groot is, kunnen er bij het langs de kolom doorlopen van elementen veel misses optreden, ook als de cache voldoende capaciteit heeft. Welke maatregel is daartegen effectief?
  7. Waarom is het doorlopen van bovenstaande gekoppelde lijst doorgaans veel trager dan het sequentieel lezen van een array met evenveel elementen?
  8. Bij een array van tellers per thread zoals 'long cnt[8];' treedt false sharing op. Welke maatregel is het meest geschikt?
  9. Welke methode is geschikt voor de prestaties bij het berekenen van de som van alle elementen van een array met meerdere threads?
  10. Een array van 1000 elementen moet worden verwerkt met 256 threads per block en één element per thread. Welk aantal blocks dat moet worden gestart is juist?
  11. Als zoals hierboven elke 32 elementen van de array wordt gelezen, waarbij i het nummer van elke thread is, is dat trager dan het lezen van a[i]. Wat is de belangrijkste reden?
  12. Bij lichte bewerkingen zoals het één keer optellen van array-elementen kan het sturen van data naar de GPU trager zijn dan rekenen op de CPU. Wat is de belangrijkste reden?
  13. Wat bepaalt hoofdzakelijk de prestaties wanneer op een GPU twee grote arrays elementgewijs worden opgeteld (c[i] = a[i] + b[i])?
  14. Op een GPU wil men alleen de elementen die aan een voorwaarde voldoen uit een array halen en in een andere array compact wegschrijven (elke thread levert 0 of 1 uitvoer). Welke parallelle berekening wordt veel gebruikt om het schrijfadres van elke thread te bepalen?
  15. Wat is de tijdcomplexiteit van een bewerking die in een array van n elementen elk paar van twee verschillende elementen precies één keer vergelijkt (een dubbele lus die element i vergelijkt met alle elementen erna en i telkens één stap verder zet)?

Verwante termen

Variabele Pointer Gelinkte lijst (linked list) GPU Cacheregel (cache line) Prefetching Struct (C-structuur) Stack (stapelgeheugen) Tijdcomplexiteit (O-notatie) Binair zoeken (binary search)

Naar de woordenlijst