3 ms·

> 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

> 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.

mikewarot 2y ago
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.

mikewarot 2y ago

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.