2 ms·

Wow, this is fascinating. I wonder if hardware could be designed to do this really efficiently.

• skohan 4y ago
  It already is right? A GPU is basically a purpose-built linear algebra machine.
  • mandarax8 4y ago
    From the abstract: > (In the common case that one matrix is known ahead of time,) our method also has the in- teresting property that it requires zero multiply-adds. These results suggest that a mixture of hashing, aver- aging, and byte shuffling—–the core operations of our method—–could be a more promising building block for machine learning than the sparsified, factorized, and/or scalar quantized matrix products that have re- cently been the focus of substantial research and hard- ware investment.` This is not at all what modern gpus are optimized for.
• ffast-math 4y ago
  Definitely. On CPUs, you could make this 2x faster pretty easily with just another execution port for vpshufb / vtbl and a 4bit lo and hi unpack instruction. Though the real speedup would be allowing dense matmul ASICs to operate on 16-byte tables and 4-bit indices as operands. The reason Bolt and MADDNESS end up so fast is that they produce "sparse" representations that are still contiguous, strided arrays in memory. So the kernels and access patterns are just like those of dense GEMMs (and therefore vectorize-able, etc), but with lookup-adds instead of multiply-adds. Hopefully-clarifying image: https://imgur.com/a/trOB69U https://imgur.com/a/trOB69U
  • nynx 4y ago
    Fascinating, might try implementing this on an FPGA.