English
Menu

What is Array?

A data structure that stores values of the same type in sequence and identifies each element by an index. Because the elements are stored contiguously in memory, the position of any element can be computed from its index, so any element can be read or written in constant time. Some languages start indices at 0, while some notations start them at 1.

Japanese name: 配列

Array appears in 75 practice questions across 14 topics, including Programming Basics (Pseudocode Tracing), Data Structures and Algorithms, GPU Programming.

Field: Programming Basics (Pseudocode Tracing)

Try it: questions about Array

In a direct-mapped cache, elements of two arrays map to the same cache location and evict each other on every alternating access. How is this miss classified?

  1. ACompulsory miss
  2. BCapacity miss
  3. CConflict miss
Show answer and explanation

Answer: C. Conflict miss

Misses where two pieces of data fight over the same set and evict each other, even though the cache as a whole has room, are conflict misses. Raising associativity so a set can hold both, or offsetting one array so it maps to different sets, reduces them. Capacity misses arise because the working set exceeds the whole cache and persist even with full associativity. Compulsory misses happen on first access and do not describe repeated accesses.

When each row of a 2D array is 4,096 bytes (a power of two), walking down a column can cause many misses even though the cache has spare capacity. Which countermeasure is effective?

  1. APadding each row so its size is not a power of two
  2. BChanging the element type to a different type of the same size
  3. CRelocating the whole array so it starts on a large power-of-two address boundary
Show answer and explanation

Answer: A. Padding each row so its size is not a power of two

With rows exactly 4096 bytes long, elements down a column are spaced by multiples of 4096, so the index bits within the low 12 address bits are identical and the elements crowd into a few sets (all into the same set in an L1 cache with 4 KB or less per way). When more rows than the associativity map to one set, conflict misses occur even with capacity to spare. Padding each row by about one line shifts the set for each element and spreads them out. Aligning to a power of two leaves the problem intact, and a same-sized type changes nothing.

Array in the explanations

Questions that mention Array (75)

  1. a0 holds the start address of an int (4-byte) array a, and a1 holds an index i. What does the code above load into a2?
  2. Scanning the 2D C array a[i][j] with j in the inner loop, as above, tends to be faster than with i in the inner loop. Why?
  3. In a direct-mapped cache, elements of two arrays map to the same cache location and evict each other on every alternating access. How is this miss classified?
  4. In the loop above, an int is 4 bytes, a cache line is 64 bytes, and the array is not cached and starts on a line boundary. Without prefetching, what is the miss rate for reading the array?
  5. For a loop that sums only the x coordinates as above, why does converting to a structure of arrays (a separate array per field) tend to be faster?
  6. When each row of a 2D array is 4,096 bytes (a power of two), walking down a column can cause many misses even though the cache has spare capacity. Which countermeasure is effective?
  7. Why does traversing the linked list above tend to be much slower than reading an array with the same number of elements in order?
  8. False sharing occurs with an array of per-thread counters such as "long cnt[8];". What is the most suitable fix?
  9. When several threads sum all elements of an array, which approach performs well?
  10. To process a 1000-element array with one element per thread and 256 threads per block, how many blocks should be launched?
  11. With i as each thread's index, reading the array every 32 elements as above is slower than reading a[i]. What is the main reason?
  12. Sending data to a GPU for light work such as adding array elements once can be slower than computing on the CPU. What is the main reason?
  13. When a GPU performs element-wise addition of two large arrays (c[i] = a[i] + b[i]), what mainly determines performance?
  14. On a GPU you want to compact only the elements meeting a condition into another array (each thread outputs 0 or 1 items). Which parallel computation is commonly used to determine each thread's write position?
  15. For an array of n elements, what is the time complexity of comparing every pair of distinct elements exactly once (a double loop that compares element i with every element after it, advancing i one step at a time)?

Books on Programming Basics (Pseudocode Tracing) Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Pointer Variable GPU Linked list CUDA Prefetching Argument Stack Cache line SIMD

Back to the glossary