3 ms·

> many algorithms can be expressed as matrix multiplication I wonder if this can be applied to something like the 3n+1 problem, or Conway's Game of Life?

• gwern 5y ago
  It's a grid and has a famous APL 1-liner, and there's GPU-accelerated GoL implementations, so one assumes so.
  • dragontamer 5y ago
    GPUs don't always perform matrix multiplications. GPUs are just massive SIMD machines, which happen to be pretty good at matrix-multiplication. But systolic arrays (also known as "Tensor Cores" these days) are even better at the job, which is why Google put so much money into TPUs, and NVidia has created special "Tensor Cores" (really, systolic arrays) in their GPUs. The number of applications that use systolic array matrix multiplications is rather slim: pretty much just the deep learning fellows. Otherwise, those matrix-multiplication routines in the GPU are largely executed using plain-old SIMD programming. -------- If I were to write a GPU Conway of Life simulator, I'd just do it the same way as before. Counting up each pixel one-by-one and creating a state-transition from old-state to new-state, synchronizing the states / parallel calculation to ensure that there's no race conditions. -------- To rewrite the Game of Life as a matrix-multiplication would be grossly inefficient. I actually argue the opposite needs to happen. That is: we need more matrix multiplications written as if they were computer programs. (See my other post in this topic: https://news.ycombinator.com/item?id=29083898 https://news.ycombinator.com/item?id=29083898). It is clear that matrix-multiplications and graphs are related, but we process graphs with say... CPU-branch predictors (aka: following the instruction-pointer graph across the computer program graph). You __COULD__ implement that as matrix multiplications. But that'd be a gross waste of energy. Instead, more matrix-multiplications (especially sparse matrix multiplications) should be written to take advantage of branch-predictors and other such features of modern CPUs. ------------ There's absolutely an equivalency between matrix multiplies and graphs. But this post is drawing the precisely opposite conclusion from reality IMO. Matrix multiplications are incredibly dense and power-hungry. There are faster, cheaper, more efficient algorithms for performing these computations _IF_ you know the matricies are in a certain format. (Ex: tri-diagonal, sparse, or other such setups). Detecting these special forms (especially very common special forms) and optimizing on those is the goal for faster computers these days.