Storage Supplement 1: Matrices

Overview

In this lecture, we play with the processor cache.

Full lecture notes on storage — Textbook readings

Processor cache

• Processor caches divide primary memory into blocks of 64–256 aligned bytes
  • 128 bytes on some machines
• Processor implements prefetching strategies
  • Sequential access often beneficial
  • User can help: prefetch x86-64 instruction

accessor.cc

• Initialize array of N integers
• Sum up N elements of the array in one of three orders
  • -u (up order): 0…(N-1)
  • -d (down order): (N-1)…0
  • -r (random order): N random choices from [0, N-1)

Question

• What is the relative speed of these orders, and why?

list-inserter.cc

• Initialize sorted linked list of N integers
• Insert N elements in one of three orders
  • -u (up order): 0…N-1
  • -d (down order): N-1…0
  • -r (random order): N random choices from [0, N-1)

Question

• What is the relative speed of these orders, and why?

Machine learning

Machine learning Matrix multiplication

• Matrix is 2D array of numbers
• m\times n matrix M has m rows and n columns
  • M_{ij} is the value in row i and column j
• Product of two matrices C = A \times B
  • If A is m\times n, then B must have dimensions n\times p (same number of rows as A has columns), and C has dimensions m \times p
  • C_{ij} = \sum_{0\leq k < n} A_{ik}B_{kj}

Pictorial matrix multiplication

Matrix storage

• How to store a 2D matrix in “1D” memory?
• Row-major order
  • Store row values contiguously in memory
• Single-array representation
  • MxN matrix stored in array m[M*N]
  • Matrix element M_{ij} stored in array element m[i*N + j]
  • 4x4 matrix: A_{0,0} := a[0]; A_{0,1} := a[1]; A_{0,2} := a[2]; …; A_{3,2} := a[14]; A_{3,3} := a[15]

Implementing matrix multiplication

    // clear `c`
    for (size_t i = 0; i != c.size(); ++i) {
        for (size_t j = 0; j != c.size(); ++j) {
            c.at(i, j) = 0;
        }
    }

    // compute product and update `c`
    for (size_t i = 0; i != c.size(); ++i) {
        for (size_t j = 0; j != c.size(); ++j) {
            for (size_t k = 0; k != c.size(); ++k) {
                c.at(i, j) += a.at(i, k) * b.at(k, j);
            }
        }
    }

Question

• Can you speed up matrixmultiply.cc by 10x?

Forking, piping, and stdio

• fork1
• fork2
• fork3
  • ./fork3
  • ./fork3 | less
• forkmix