Deutsch
Menü

Was ist Array?

Eine Datenstruktur, die Werte desselben Typs nacheinander speichert und jedes Element über einen Index anspricht. Weil die Elemente zusammenhängend im Speicher liegen, lässt sich die Position jedes Elements aus seinem Index berechnen, sodass jedes Element in konstanter Zeit gelesen oder geschrieben werden kann. Manche Sprachen beginnen die Indizes bei 0, manche Schreibweisen bei 1.

Japanische Bezeichnung: 配列

„Array“ kommt in 56 Übungsfragen aus 12 Themen vor, z. B. Grundlagen der Programmierung (Pseudocode nachverfolgen), Datenstrukturen und Algorithmen, GPU-Programmierung.

Fachgebiet: Grundlagen der Programmierung (Pseudocode nachverfolgen)

Jetzt üben: Fragen zu Array

In einem Array von Zählern je Thread wie „long cnt[8];“ tritt False Sharing auf. Welche Gegenmaßnahme ist am besten geeignet?

  1. ADen Zählertyp von long auf int ändern und das Array verkleinern
  2. BZwischen den Zählern Füllbytes einfügen oder sie ausrichten, sodass sie in verschiedenen Cache-Zeilen liegen
  3. CDie Zahl der Threads erhöhen, um die Wartezeiten zu verteilen
Antwort und Erläuterung anzeigen

Antwort: B. Zwischen den Zählern Füllbytes einfügen oder sie ausrichten, sodass sie in verschiedenen Cache-Zeilen liegen

Bei 8 Byte großem long passen die 8 Zähler in eine Zeile von 64 Byte, und alle Threads streiten um dieselbe Zeile. Fügt man Füllbytes ein, sodass jeder Zähler auf einer 64-Byte-Grenze liegt, oder richtet man die Struktur an der Größe der Cache-Zeile aus, kann jeder Thread eine eigene Zeile nutzen. Wirksam ist auch, dass jeder Thread in einer lokalen Variablen zählt und erst am Ende einmal auf den gemeinsamen Speicherplatz addiert.

Ein Array mit 1000 Elementen soll mit 256 Threads pro Block verarbeitet werden, wobei jeder Thread ein Element bearbeitet. Wie viele Blöcke müssen gestartet werden?

  1. A3
  2. B4
  3. C1000
Antwort und Erläuterung anzeigen

Antwort: B. 4

1000÷256≈3,9; bei Abrunden auf 3 Blöcke würden nur 256×3=768 Elemente verarbeitet, und der Rest bliebe unbearbeitet. Es werden daher aufgerundet 4 Blöcke (1024 Threads) gestartet, und die 24 überzähligen Threads tun nichts. Allgemein wird mit „(n + 256 - 1) / 256“ aufgerundet. Damit die überzähligen Threads nicht außerhalb des Arrays lesen oder schreiben, muss im Kernel die Nummer geprüft werden.

„Array“ in den Erläuterungen

Fragen mit „Array“ (56)

  1. Wird ein zweidimensionales C-Array a[i][j] wie oben mit j als innerer Schleife durchlaufen, ist dies tendenziell schneller als mit i als innerer Schleife. Was ist der Grund?
  2. In der obigen Schleife ist int 4 Byte groß und die Cache-Zeile 64 Byte; das Array liegt nicht im Cache, und sein Anfang ist an der Zeilengrenze ausgerichtet. Wie hoch ist die Miss-Rate beim Lesen des Arrays ohne Prefetch?
  3. Warum wird die oben gezeigte Summierung nur der x-Koordinaten tendenziell schneller, wenn sie auf eine Struktur von Arrays umgeschrieben wird (jede Komponente in einem eigenen Array)?
  4. In einem Array von Zählern je Thread wie „long cnt[8];“ tritt False Sharing auf. Welche Gegenmaßnahme ist am besten geeignet?
  5. Ein Array mit 1000 Elementen soll mit 256 Threads pro Block verarbeitet werden, wobei jeder Thread ein Element bearbeitet. Wie viele Blöcke müssen gestartet werden?
  6. Wird, wie oben gezeigt, mit der Thread-Nummer i ein Array in Abständen von 32 Elementen gelesen, ist dies langsamer als das Lesen von a[i]. Was ist der Hauptgrund?
  7. Bei einer leichten Verarbeitung, die jedes Array-Element nur einmal addiert, kann das Senden der Daten an die GPU langsamer sein als die Berechnung auf der CPU. Was ist der Hauptgrund?
  8. Auf der GPU sollen nur die Elemente eines Arrays, die eine Bedingung erfüllen, herausgenommen und kompakt in ein anderes Array geschrieben werden (jeder Thread gibt 0 oder 1 Wert aus). Welche parallele Berechnung wird häufig verwendet, um die Schreibadresse jedes Threads zu bestimmen?
  9. Welche Zeitkomplexität hat bei einem Array mit n Elementen ein Verfahren, das jedes Paar zweier verschiedener Elemente genau einmal vergleicht (eine doppelte Schleife, die das i-te Element mit allen dahinterliegenden Elementen vergleicht und i schrittweise erhöht)?
  10. Eine lineare Suche vergleicht die Elemente eines Arrays mit 100 verschiedenen Werten der Reihe nach von vorn, um einen Zielwert zu finden. Der Zielwert ist immer im Array enthalten und steht mit gleicher Wahrscheinlichkeit an jeder Position. Wie viele Vergleiche sind im Mittel nötig?
  11. Welche Aussage beschreibt eine verkettete Liste (eine Liste, in der jedes Element einen Zeiger auf das nächste Element enthält) im Vergleich zu einem Array richtig?
  12. Eine binäre Suche sucht 38 im aufsteigend sortierten Array a[0] bis a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Der Suchbereich beginnt mit lo = 0 und hi = 9, und die mittlere Position ist (lo + hi) ÷ 2 abgerundet. Welche Folge gibt die Elemente, die mit 38 verglichen werden, in der richtigen Reihenfolge an?
  13. Das Array 5, 3, 8, 1, 4 wird mit Bubblesort aufsteigend sortiert. Wie sieht das Array nach einem Durchlauf aus, bei dem benachbarte Elemente von vorn bis zum Ende verglichen und vertauscht werden, wenn das linke größer ist?
  14. Das Array 29, 10, 14, 37, 13 wird mit Selectionsort aufsteigend sortiert: Das Minimum des unsortierten Teils wird gesucht und mit dem ersten Element des unsortierten Teils vertauscht. Wie sieht das Array aus, nachdem dieser Schritt zweimal ausgeführt wurde?
  15. Ein Array mit 10 Elementen wird mit Insertionsort aufsteigend sortiert. Jedes Element ab dem zweiten wird herausgenommen und mit den Elementen links davon verglichen, beginnend beim linken Nachbarn, bis ein Element gefunden wird, das kleiner oder gleich ist, oder der Anfang erreicht ist. Wie viele Vergleiche sind nötig, wenn das Array bereits aufsteigend sortiert ist, und wie viele, wenn es absteigend sortiert ist?

Verwandte Begriffe

Zeiger (Pointer) GPU Cache-Zeile (Cache Line) Verkettete Liste (Linked List) SIMD Binäre Suche (Binary Search) CUDA TLB (Translation Lookaside Buffer) Vektorisierung False Sharing

Zur Glossarübersicht