Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to pack ternary numbers in 8-bit bytes

compilade.net

Post reply on HN
Print view View original

31–40 of 55 posts

Re: How to pack ternary numbers in 8-bit bytes

#31

Post by edflsafoiewq »

lioeters wrote: post #21

Amusing that the link to an article on ternary numbers was posted by Mr Triplett. (: 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…

PrismML released a ternary model recently. However AFAICT they don't use this packing, instead packing trits as 2 bits each (as least for the GGUF).

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.

Re: How to pack ternary numbers in 8-bit bytes

#33

Post by inigyou »

abcd_f wrote: post #11
mi_lk wrote: post #6

Earlier quoted context omitted.

Had a good chuckle

If it weren't for Bool as a name, that's just 0 for OK, non-zero for errors with 1 being general failure.

TDWTF code is usually hyperbolized. It might not have been called Bool.

Re: How to pack ternary numbers in 8-bit bytes

#35

Post by JKCalhoun »

Despite my ignorance on what would be involved, I like to fantasize that companies like Apple (who own their own chip design and hardware) can put these ternary pack/unpack operations in hardware with a single instruction for each (and also instructions for performing the various matrix convolutions using ternary numbers) so that we can get on-device LLMs.

I suppose with the recent quantized Bonsai models we're already seeing on-device LLMs for phones and the like… But I (again, forgive my ignorance) assume that there is an order of magnitude or more in performance sitting out there if we get custom hardware instructions.

Re: How to pack ternary numbers in 8-bit bytes

#36

Post by entrope »

Razengan wrote: post #19

I was actually mucking with ChatGPT about possible "post-binary" architectures. 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 represe…

Base 4 isn't substantially different from base 2 except in granularity.

There's a somewhat famous result that base e gives the best expected density for representing numbers, but fractional (and especially irrational) bases are inconvenient for real-world quantities. So ternary is theoretically the best integer choice, but binary has practical advantages for electronic logic.

Re: How to pack ternary numbers in 8-bit bytes

#37

Post by moregrist »

zephen wrote: post #29
akoboldfrying wrote: post #24

Earlier quoted context omitted.

You can have a single 3x256=768-byte table -- just multiply the input byte by 3 to get the offset into the table, and read out the 3 trits (1 trit per byte) beginning at that offset. 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]

There are 5 trits. 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.

You wouldn’t need five tables. Each trit takes up two bits when unpacked into 0,1,2 values.

You can do a full unpacking-via-lookup with a uint16[256] and then do bit shifting and masking to extract the individual trits, but using an extra byte in each entry (or 3 tables) would let you extract with just two shifts.

This starts to vary a lot with the microarchitecture, and there’s the added dimension of SIMD vectorization, so accurate timing in a realistic context becomes important.

Re: How to pack ternary numbers in 8-bit bytes

#38

Post by reaperducer »

Razengan wrote: post #19

I was actually mucking with ChatGPT about possible "post-binary" architectures. 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 represe…

I was actually mucking with ChatGPT about possible "post-binary" architectures.

Ternary computers were around almost 70 years ago, and first posited well over 100 years ago.

Maybe ChatGPT isn't the best place to do research.

Re: How to pack ternary numbers in 8-bit bytes

#39

Post by zephen »

moregrist wrote: post #37
zephen wrote: post #29

Earlier quoted context omitted.

There are 5 trits. 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.

You wouldn’t need five tables. Each trit takes up two bits when unpacked into 0,1,2 values. You can do a full unpacking-via-lookup with a uint16[256] and then do bit shifting and masking to extract the individual trits, but using an extra byte in each entry (or 3 tables) would let you extract with just two shifts. This starts to vary a lot with the microarchitecture, and there’s the added dimension of SIMD vectorizat…

I agree.

But then, I'm pretty sure you haven't said anything different than what I said in the great-great-grandparent of your comment, other than slightly fleshing it out for a couple of particular scenarios.

But you haven't covered the packing, which is the primary thing I was suggesting you might need multiple tables for if you really wanted to use tables and really didn't want to do shifting or multiplication.

Re: How to pack ternary numbers in 8-bit bytes

#40

Post by ffaccount2 »

akoboldfrying wrote: post #22
Diggsey wrote: post #14

How does this packing/unpacking scheme compare to just using a lookup table?

A 256x3=768-byte lookup table will almost certainly be faster on a CPU. It will fit easily in L1 cache, and can extract 3 bytes at a time. 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.

Compared to the naive implementation presented in the blog post yes, but the PR uses AVX, which can process 256 bits (32 bytes) at a time, so I'm not so sure
Post reply on HN