13 ms·

I have this weird architecture I'm emulating that I call a bit-grid.[1] The basic idea is an FPGA with NO routing fabric at all... just a 2d grid of look up tab

I have this weird architecture I'm emulating that I call a bit-grid.[1] The basic idea is an FPGA with NO routing fabric at all... just a 2d grid of look up tables that take a single bit input from each neighbor, and output a single bit to each, which means each look up table holds 64 bits (4*16 possible input states) of "program". Clocking is in two phases (like the colors of a chess board) to prevent all manner of grief, and make it easier to think about. Each phase is NOT Turning Complete, but the grid is. So, I can emulate this thing on my desktop PC at about 28 nSec/cell using some Pascal code[2]. I'm thinking that if I upgrade to a machine with AVX512 instructions, it might get radically faster. What I can't figure out is how this instruction actually works, and what gains I would actually get. The Intel documentation on this instruction is as clear as mud. There's no example with all the bits shown and worked through, leading the reader to have no ledge on which to make some intellectual purchase towards understanding. Questions: If I were to fork over the cash for a machine with AVX512 instructions, how many of these instructions can actually execute/second? Wouldn't moving a bunch of values to/from memory basically empty out all the caches and make this thing really slow anyway? Does anyone have a worked out example with bits shown for all the sources and destinations before/after the instruction, so I can see what it does? [1] https://esolangs.org/wiki/Bitgrid https://esolangs.org/wiki/Bitgrid [2] https://github.com/mikewarot/Bitgrid https://github.com/mikewarot/Bitgrid

foota 3y ago
Does the shape of the grid matter? If not, I think you'd benefit from constraining the width such that the data for three rows fits within L1, so that iterating over one row leaves the data from the start of the next row in L1 by the time you get to it.
- foota 3y ago
  Edit: Actually... what if you broke the grid up in to N by N blocks, and simulated 2N half time steps (each decreasing the side length by 2) of that block? You'd need to do a similar sort of chess grid over the blocks, and emit like "partial outputs" from each block, then run a pass going the reverse direction, consuming the partial outputs and initial inputs. This way, you can fit a block entirely within a cores L1 for N time steps, and naturally get parallelism by simulating multiple blocks at once. You should be able to simulate N time steps like this with just 2 loads of the data (program and state) instead of 2 * N.
deleted 3y ago
[deleted]
Matumio 3y ago
> Wouldn't moving a bunch of values to/from memory basically empty out all the caches and make this thing really slow anyway? It's probably the same issues as with neural networks: they have to work on a whole batch of inputs to be efficient. They load only a few weights at a time into registers, then use those on the whole batch before loading the next weights. So my guess would be: If you only run a single grid, and the grid is large, you may end up memory-bound and you can afford running inefficient instructions. (Btw. sounds like bitgrid would map 1:1 into the LUTs of an FPGA. Might be a fun project to generate VHDL for it and then let it actually run in parallel. The less straight-forward part being the logic to get the data out of the FPGA again.)
tkanarsky 3y ago
You could rent a VPS with AVX512 support and tinker around with it. I believe GCP has a few instance types that support it, AWS surely has some too.
- mikewarot 3y ago
  That's a great idea! It would only cost a few bucks to find out. The interesting idea about the bitgrid is that you can spread the emulation across cores, as none of the cells are Turing complete. Do all of phase A, then all of phase B, repeat.
- Grimburger 3y ago
  It's quite variable even in instance types, I've emailed some VPS providers asking and the response was always it's not guaranteed, you'll have to test and see. I'm guessing there some out there, but it's not the people I have accounts with.
less_less 3y ago
You might already be able to get good acceleration with SSSE3 or AVX2 or NEON, which also has a 4-bit-input permutation instruction. The problem is that you're doing parallel lookup into many different tables, whereas NEON/SSSE3's lookups are 16x in parallel into the same table (and AVX2 is two copies of the SSSE3 one in parallel I think). So it's not as useful unless you're simulating the same grid on several different inputs for bulk testing. It might still be faster than scalar but I'm not sure.
cjs_ac 3y ago
Disclaimer: I'm not am expert. For your first question, the instructions are documented on the Intel website[0]. Many instructions have Latency and Throughput figures, which indicate how many cycles they take to execute. These are not straightforward to interpret due to instruction pipelining. As for cache exhaustion, that depends on how quickly you consume more data from memory. It's worth noting that the registers are an entire cache line in width, and that Latency figures are given for the instructions that load from memory into the AVX registers. [0] https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#techs=AVX_512&ig_expand=50 https://www.intel.com/content/www/us/en/docs/intrinsics-guid...
Const-me 3y ago
About micro-optimizations, I don’t know AVX512 but with AVX2 you could compute 4 nodes in parallel, an example in C++, untested https://gist.github.com/Const-me/90a52f291c1fcb06142307facdb8e54e https://gist.github.com/Const-me/90a52f291c1fcb06142307facdb... Here’s another idea how to optimize. Instead of a single 2D array, I would rework the memory layout. Specifically, make 6 2D arrays. Two with uint64_t values, for even/odd cells in the lookup tables. Two with bits for even/odd cells in the old grid state. Two with bits for even/odd cells in the new grid state. This improves RAM access patterns because any half of the cycle loads / stores half as many cache lines. After the complete cycle, swap old state with new state. Gathering inputs from neighbors, and scattering output to them could be a bit tricky this way, but you can simplify if you can limit grid size to even number in both X and Y direction. At least the even/odd halves will be of the equal size this way.

foota 3y ago

Does the shape of the grid matter? If not, I think you'd benefit from constraining the width such that the data for three rows fits within L1, so that iterating over one row leaves the data from the start of the next row in L1 by the time you get to it.

foota 3y ago
Edit: Actually... what if you broke the grid up in to N by N blocks, and simulated 2N half time steps (each decreasing the side length by 2) of that block? You'd need to do a similar sort of chess grid over the blocks, and emit like "partial outputs" from each block, then run a pass going the reverse direction, consuming the partial outputs and initial inputs. This way, you can fit a block entirely within a cores L1 for N time steps, and naturally get parallelism by simulating multiple blocks at once. You should be able to simulate N time steps like this with just 2 loads of the data (program and state) instead of 2 * N.

deleted 3y ago

[deleted]

Matumio 3y ago

> Wouldn't moving a bunch of values to/from memory basically empty out all the caches and make this thing really slow anyway? It's probably the same issues as with neural networks: they have to work on a whole batch of inputs to be efficient. They load only a few weights at a time into registers, then use those on the whole batch before loading the next weights. So my guess would be: If you only run a single grid, and the grid is large, you may end up memory-bound and you can afford running inefficient instructions. (Btw. sounds like bitgrid would map 1:1 into the LUTs of an FPGA. Might be a fun project to generate VHDL for it and then let it actually run in parallel. The less straight-forward part being the logic to get the data out of the FPGA again.)

tkanarsky 3y ago

You could rent a VPS with AVX512 support and tinker around with it. I believe GCP has a few instance types that support it, AWS surely has some too.

mikewarot 3y ago
That's a great idea! It would only cost a few bucks to find out. The interesting idea about the bitgrid is that you can spread the emulation across cores, as none of the cells are Turing complete. Do all of phase A, then all of phase B, repeat.
Grimburger 3y ago
It's quite variable even in instance types, I've emailed some VPS providers asking and the response was always it's not guaranteed, you'll have to test and see. I'm guessing there some out there, but it's not the people I have accounts with.

less_less 3y ago

You might already be able to get good acceleration with SSSE3 or AVX2 or NEON, which also has a 4-bit-input permutation instruction. The problem is that you're doing parallel lookup into many different tables, whereas NEON/SSSE3's lookups are 16x in parallel into the same table (and AVX2 is two copies of the SSSE3 one in parallel I think). So it's not as useful unless you're simulating the same grid on several different inputs for bulk testing. It might still be faster than scalar but I'm not sure.

cjs_ac 3y ago

Disclaimer: I'm not am expert. For your first question, the instructions are documented on the Intel website[0]. Many instructions have Latency and Throughput figures, which indicate how many cycles they take to execute. These are not straightforward to interpret due to instruction pipelining. As for cache exhaustion, that depends on how quickly you consume more data from memory. It's worth noting that the registers are an entire cache line in width, and that Latency figures are given for the instructions that load from memory into the AVX registers. [0] https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#techs=AVX_512&ig_expand=50 https://www.intel.com/content/www/us/en/docs/intrinsics-guid...

Const-me 3y ago

About micro-optimizations, I don’t know AVX512 but with AVX2 you could compute 4 nodes in parallel, an example in C++, untested https://gist.github.com/Const-me/90a52f291c1fcb06142307facdb8e54e https://gist.github.com/Const-me/90a52f291c1fcb06142307facdb... Here’s another idea how to optimize. Instead of a single 2D array, I would rework the memory layout. Specifically, make 6 2D arrays. Two with uint64_t values, for even/odd cells in the lookup tables. Two with bits for even/odd cells in the old grid state. Two with bits for even/odd cells in the new grid state. This improves RAM access patterns because any half of the cycle loads / stores half as many cache lines. After the complete cycle, swap old state with new state. Gathering inputs from neighbors, and scattering output to them could be a bit tricky this way, but you can simplify if you can limit grid size to even number in both X and Y direction. At least the even/odd halves will be of the equal size this way.