Supermodelling

Bits are cool, but we’d really like more expressive data types to help us do more interesting work. We satisfy this desire by grouping bits together in bunches and inventing ways of interpreting these bit vectors.

One way to treat a vector of bits as a unit is to note that there are 2^N possible combinations of N bit values. So, just like a particular bit value can be interpreted as a choice between two options, a particular N-bit value can be interpreted as a choice among 2^N options.

There are lots of different ways to use this idea. We could use 3 bits to represent 8 different colors. We could use a bunch of bits to represent the letters of the alphabet. And so on.

We can also use N bits to represent 2^N different numbers. The most natural way (yes, that’s a pun) is to represent a range of integers. Note that there are lots of other sensible ways of mapping bit patterns onto numbers. For example, we might like to represent fractional numbers (”floating point” or “fixed point”).

Two major ways of picking a range of numbers are most common. 8 bits either map to the values 0..255 or -128..127 (”unsigned” or “signed” integers).

It’s a pretty expensive and drastic thing to do — given a 128-bit register, as bits it can represent 128 different things. But as a single 128-bit integer (with a very large range of potential values), it represents just one thing — a two order-of-magnitude hit on memory use and possible computation speed. C’est la vie: integers are useful so we pay the price. However, there is some significant payoff in using smaller bit vectors rather than larger ones if the smaller vector can represent the range of values needed for some particular task. This is why my CPUs have lots of different instructions for dealing with 8-bit, 16-bit, 32-bit, 64-bit, and 128-bit integers.

An XMM register can hold 16 8-bit integers, which are operated on in a pairwise fashion, just like bits were in a previous post. And also just like bits, addressing individual values is a problem. There are a LOT of instructions for loading, storing, shuffling, and swapping the integer-vectors contained in registers, but the efficiency of information processing algorithms goes up a lot if we don’t have to do that very much. It’s a lot better if we can usefully build meaningful data types that use vectors of integers instead of just individual integers, or if our algorithms can be written in a “data parallel” way — in this case performing 16 parallel computations on 16 mini-registers. I think this is really important for trying to choose efficient representations from the universe of possibilities.

Integers can be used for a lot of different things. They can represent counts of things, (approximate) measurements of physical properties like mass, distances along axes in multidimensional space, and many other mappings. Finally, just like having representations of bits gives us access to abstract systems like boolean logic, having representations of integers gives us access to vast abstract mathematical systems built on top of integers. To make that work, the CPUs include instructions for the basic mathematical operations such as addition, subtraction, multiplication, and division.

I won’t go into the gory details of the instructions themselves or their encoding, but I’ll make a couple of observations. First, the data types are not completely orthogonal — for example, I do not believe that there is an 8-bit multiply. That means a tedious amount of checking processor features will be necessary when making decisions about data types. Second, it’s important to note that not just the vector processors are capable of dealing with integers. The “normal” instruction set has plenty of instructions for working on values stored in “normal” CPU registers. I focus on the SSE subsystem because of the potential performance boost but shuttling data back and forth to the special XMM registers is not always the right way to do things.

Finally, there is an interesting and curious special type of operation available on 16-bit integers (and somewhat on 8-bit) called “saturated” arithmetic. Suppose we have two unsigned 8-bit numbers: 210 and 83. Adding them up should produce the answer 293, but 293 cannot be represented in 8 bits. So what happens? In normal computer arithmetic, the “overflow” is noted in a status register and the high bit is simply discarded, which means that the stored answer is 37. It would be rare for that to be a desirable outcome, so avoiding overflow is usually highly desirable. “Saturated” arithmetic says that since 255 is the biggest value representable, that value should be the result of any computation that overflows to a larger value. Invented for use in DSP applications like audio processing, I think this graceful nonlinear response is really interesting and maps pretty well onto intuitions about numbers. There might be interesting mathematical properties for saturated arithmetic as well that arise from the nonlinearity which could make it an interesting component of some modelling methods.