Astro 585 discussion 6


17 February 2014 astro585

Now we are getting to the most interesting part of the curse.

Q: How are matrices stored in memory?

It really helps knowing to know how matrices are stored in memory. Are they colum-major, or row-major? Julia is like Fortran, storing matrices as column-major data structures; while C uses row-major data structures.

So then in your implementation of the simulation of Life, the Universe, and Everything, then might need to have big matrices; and you might save a lot of Big-Thought's computing time by knowing if it is faster to traverse your Big-Matrix by the columns-first, or by rows-first.

Q: What about sparse matrices?

If you have a lot of 0 entries in your matrix, then instead of allocating a big rectangular block of memory for it, then rather store it as a list of non-zero entries instead. For example, if you had a diagonal-matrix you really would only need one vector to store the data, right? And similarily, a tri-diagonal one would need 3.

The power of views

A powerful example: What's a clever algorithm to transpose a matrix? Just flip the indices!

Cache associativity

When you have data in the big memory and you want it in the cache - what do you do? Where can it be? The main philosophy here is: How do we reuse data that is already in the cache?

Non-associative cache?

It might go something like this:

  • Byte-1 of main memory can only go to Byte-1 in the cache

  • Byte-2 of main memory can only go to Byte-2 in the cache

...

  • Byte-1024 of main memory can only go to Byte-1024 in the cache

  • Byte-1025 of main memory can only go to Byte-1 in the cache

Reading a cache like this is very fast, as you don't have to search for the data too long - every byte has a fixed and known location. But the main downside is: you rarely use the whole cache!

Solution to this is called padding.

Latency-Bandwidth diagram


Ergonomically handwritten code, with a little help from my friends; vim, jekyll and twitter bootstrap