Ask HN: How do I program a BitGrid? | Hacker News Reader

Ask HN: How do I program a BitGrid?

5 pointsmikewarot7 comments

I've come up with an architecture[1,2] that I think could be quite useful. But I've been stuck on how to actually compile "code" for it for far too long. (Decades, actually) It's my hobby horse, and I want to ride it before I die.

I need to take expressions, or programs, and break them down to a directed acyclic graph of binary logical operations.

In the end.... a cell has 4 inputs, and needs 4 outputs for each possible combination, a total of 64 bits (or 16 nibbles).

Heck, I'd settle for a good way to express said tree in a plain text file as a kick start.

[1] https://esolangs.org/wiki/Bitgrid

[2] https://github.com/mikewarot/Bitgrid

View on HN

Have you reached out to the person who wrote those quines?

https://gist.github.com/int-e/c1b40dbed8a39a20dfc1d94fc25226...

By sheer coincidence, you appear to be the protagonist of a hard sci-fi novel:

https://www.amazon.com/dp/B0CJHQ4LZN

From the article author of a recent submission today:

https://news.ycombinator.com/item?id=41087873

No, I haven't reached out to them, hadn't seen them before, thanks!

> I need to take expressions, or programs, and break them down to a directed acyclic graph of binary logical operations.

This strikes me as not quite a correct description of the problem. What you described in that sentence above is closer to a description of compiling a combinational subset (just expressions, no state) of a hardware description language to logic gates.

The BitGrid has two differences from that. One, you have state registers after every cell: essentially it's pipelined at the single-cell level. Two, the routing of signals is fixed to be able to reach nearest-neighbors only. That means you end up needing to spend logic cells for routing and incur a one cycle delay for every hop away that you need to reach (whereas that's essentially "free" in gates).

Those make the problem significantly more complicated because you're not just mapping a function on to logic, but needing to do routing and a kind of delay analysis ("which cycle is this input signal from?) at the same time.

My suggestion would be to simplify the problem first. For example, allow routing any cell's input to any cell's output in the first stage of complication, then do a phase where you insert the routing.

To me, the level of pipelining and nearest-neighbor restriction makes it hard to approach the problem: the seeming simplicity ends up making it hard to wrap your mind around a larger computation. The routing is nontrivial; using cells for plain routing wastes logic resources; and the one-cycle delays become a complex problem to be worked around instead of a feature. It's interesting to think about but if it were my project, I'd think about changes to the model first to make life simpler.

I understand how adding delays at every step seems like a really bad idea, especially when coming from a world of FPGAs and trying to squeeze out every nanosecond of latency.

What you get in trade, is an architecture that doesn't have any fiddly timing issues. You also get something that is inherently pipelined. So, in theory, you could shove data in one side of the fabric at the full clock rate, and get results out the other side at that same rate. I assume that it should be feasible to run a BitGrid at 1 Ghz, which means that if it's big enough, you could run real time FFTs, signal processing, etc... sure the latency sucks, but the throughput is enormous.

I understand that wasting gates, instead of having dedicated routing hardware also seems like a horrible idea.

What you get in trade, is freedom from the routing issues that always arise when you have a lumpy fabric with special functions in fixed locations. In theory (as all I have right now is theory), it should be trivial to move a whole section of the flow graph over 1 cell, or rotate, flip the flow, etc. Routing around a bad cell is going to incur a small penalty, perhaps as low as 1 full clock cycle in most cases.

---

Do those trade-offs make sense? Maybe... or not.

What exactly is the ask here? Do you want input for a programming model? Practical advise for building a compiler? Do you want to target real hardware or a software simulator?

> I'd settle for a good way to express said tree in a plain text file

What you are referring to is commonly called an IR (intermediate representation). Compilers typically take the AST generated by the parser and translate (“lower”) it into increasingly hardware-near and optimized IRs before performing instruction selection.

I briefly browsed through the links you provided. IIUC, BitGrid is essentially one of the Turing-complete 2-D cellular automata. This Reddit thread might be interesting to you [0].

[0]: https://www.reddit.com/r/computerscience/s/IE5WRIrKsR

>What exactly is the ask here?

I wasn't sure, just a kick in the pants to get me out of the rut I was stuck in.

>Do you want input for a programming model?

Any suggestions are great

>Practical advise for building a compiler?

Yes, or even hints as to the right direction.

>Do you want to target real hardware or a software simulator?

I was just targeting real hardware, and started learning Verilog using YOSYS. Then it dawned on me that if you have a compiler, and you can break code into a huge directed acyclic graph of operations, you can spilt it up into chucks rather trivially. The compiler becomes a universal solvent for code.

If you have BitGrid chips, then can execute parts of the grid quickly in parallel (1 nanosecond or less cycles across the chip), if all you have is CPUs with a lot of RAM, you can execute parts of a huge grid very slowly (about 60 nanoSeconds/cell on my PC, single threaded, I should be able to get an 8x speedup on my 8 thread machine)

I'd like to eventually run GNU Radio flowgraphs at better than real time through a BitGrid. I should be able to do it with audio now, for small graphs, using my simulator.

I'd also like to figure out how to make a backend for GeoHot's TinyGrad that outputs a BitGrid graph.

>[0]: https://www.reddit.com/r/computerscience/s/IE5WRIrKsR

Oh my... the x86 Move instruction really has a lot of power built into it. [1] I'll be digging through the GitHub repo he mentioned[2] for a while, it looks quite interesting.

Thanks for your help!

[1] https://www.youtube.com/watch?v=R7EEoWg6Ekk

[2] https://github.com/reMath

I suspect the answer is somehow related to this wikipedia page

https://en.wikipedia.org/wiki/Static_single-assignment_form

Reply on news.ycombinator.com