How to pack ternary numbers in 8-bit bytes(compilade.net) |
How to pack ternary numbers in 8-bit bytes(compilade.net) |
And missed it by one letter. <jk>
The article is well-written and illustrated. The technique described is used in llama.cpp for running language models like BitNet b1.58 whose weights are stored as ternary types.
> ..in which every single parameter (or weight) of the LLM is ternary {-1, 0, 1}
> significantly more cost-effective in terms of latency, memory, throughput, and energy consumption
The original paper on this technique was published in Feb 2024. (Also linked from the article)
The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits - https://arxiv.org/abs/2402.17764
However, since then there have only been a few other models using ternary weights. I get the impression that there are factors not considered in the paper which make it less practical than it seemed.
Hy-MT2 also came out with a 1.25bit model using a technique called Sherry, where weights are trits with the additional constraint that exactly one trit in a group of four is 0. Four possible positions for the 0 times 2^3 possibility for the other three positions = 32 possibilities, so it fits in 5 bits exactly. You can also exploit the sign symmetry by factoring out a sign bit and you have sixteen possibilities for a group where the first non-zero trit is +1. Unpacking can then be done with a 16 bytes lookup table, which is small enough to do really fast with SIMD.
You can beat the efficiency of 5 trits in 8 bits (1.6) with as few as 17 trits in 27 bits (~1.588), but once you account for rounding up to a whole number of bytes for practical reasons, then beating the efficiency requires going to at least 111 trits in 176 bits (~1.586), or perhaps more practically for fast unpacking, 161 trits in 256 bits (~1.59).
At that level, even if you have, say, 27B trits, the more efficient encodings would save something like 38-45MB (theoretical limit ~48MB), likely at the cost of some slowdown.
Ironically, x86 has an instruction, XLATB, that does almost exactly this (looking up a byte in a 256-byte table) -- but using it is actually slower than using an equivalent MOVZX RAX,AL; MOV AL,[RBX+RAX] sequence on modern CPUs.
Obviously, it partly depends on the implementation machine, how big a hole the tables blow in your cache, how fast the multiplies are, etc.
But it probably also hugely depends on the format that you want your trits in. If you use them unpacked, e.g. one trit per byte, then even if you're using tables, you still have to do a lot of manipulation (e.g. either shifting and oring, or having different tables, and a table lookup per trit and adding together to get the binary).
ETA: If you're prepared to waste a byte per entry so that entries are 4 bytes wide, on x86 you can use effective address calculation to do the multiplication for you, letting you decode 3 trits in 1 CPU instruction:
MOV EAX,[RBX+RCX*4]so valid arturo code can be like (picked from their in-a-nutshell documentation)
i1: true
i2: false
i3: maybe
The article suggests using 8 bits (=256 values) to pack 5 trits (=243 values).
If you use 16 bits (=65536 values) then you can pack at most 10 whole trits (=59049 values). 11 trits (=177147 values) won't fit.
The current top comment, by JoshTriplett, analyses what you would need to beat the efficiency.
I ended up feeling that ternary is just icky, because the "middle value" doesn't have an "opposite"
Maybe we should do what quaternions did to complex numbers and just jump from 2 to 4: Quaternary CPUs
I couldn't understand half of the words it spat out but it turns out that using pairs of "quits" as the atomic computation unit to represent complex numbers and/or 2x2 matrices could be ideal for AI etc.
> a diagram that shows that dividing 0x7F (127) by 243 and then multiplying by 256 results in 0x86 (134)
How... how does that help with anything?
> Now digits can be easily extracted from the top two bits of the resulting 10-bit number when multiplying this 8-bit byte by 3.
What? Why? How? This is supposed to be the most insightful part of the post, and it's literally just "Behold!" from that one proof of Pythagorean theorem. Could someone please elaborate it for a non-genius like me?
1. Convert to a fixed-point fraction: We scale our integer N into a fixed-point representation (e.g., using a 32-bit integer to represent the fraction). We do this by multiplying N by a precomputed reciprocal of 243.
2. Multiply by the base: Multiply the fraction by 3.
3. Extract: The integer portion of the result is your most significant trit.
4. Mask: Keep only the fractional remainder, and repeat.
The only operations here are multiplication, bitwise shift, and bitwise AND, i.e. perfectly suited for SIMD.
(in step 1 we replace the division with a multiplication by using the reciprocal. SIMD uses fixed-point integer arithmetic, not floating-point decimals)
[1] behold my misspent youth: https://tunguska.sf.net/
In any case, if there were 3 trits, I'm not sure what the practical difference between a single table you describe and 3 different 256 byte tables, again depending on the architecture.
Yes a single table would have better cache effects for a single read, but presumably? you're doing a lot of reads in an unpacking phase.
(As an aside, I found the characterisation of null as being a “billion dollar mistake” to be unfair. Those who don’t acknowledge null are doomed to reimplement it, probably poorly, or to have the unknowns in their logic remain unknown unknowns.)
Languages that correct the problem have two separate types (eg: Foo & Option<Foo>) meaning "definitely a Foo" and "a Foo but it might have no data". Java just has Foo, meaning "a Foo but it might have no data" but no way to represent "definitely a Foo".