2 ms·

Already been done, IIRC. Algotronix had a similar nearest-neighbor architecture FPGA in the form of the CAL1024 back in 1989†. http://citeseerx.ist.psu.edu/vi

Already been done, IIRC. Algotronix had a similar nearest-neighbor architecture FPGA in the form of the CAL1024 back in 1989†. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.152.6623&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.152... (See p. 16) https://www.algotronix.com/company/Photo%20Album.html https://www.algotronix.com/company/Photo%20Album.html That architecture never really was particularly successful. I vaguely seem to recall that the issue was that not having long routing lines mean that huge swaths of the grid had to be wasted to do routing of signals. † As an aside, Xilinx acquired Algotronix and evolved their design into the XC6200, which was notable for being one of the earliest run-time reconfigurable FPGAs

mikewarot 7y ago
If you have a symmetric grid, you can quickly rotate, flip, and otherwise transform the program. Since all the outputs are independent, you can have computation in a cell that has results flowing into the chip, and back out to the edge at the same time. Delays are simply a matter of counting how many cells a result passes, and thus a good signal to feed to an optimizing algorithm.
- ohazi 7y ago
  The general version of the thing you're describing is a 2d systolic array. Designs like this already map reasonably well to standard FPGAs. The problem with the 4:4 LUT you described above is that you almost always want the compute cell part of your design to have inputs and outputs that are wider than a single bit. For example, if you were designing an FIR filter as a systolic array, you might want one filter coefficient to come from the top of each cell, and your signal to pass through the cells from left to right. A realistic design might have a 16 bit signal and 10 bit coefficients. This would require 160 LUTs per cell just to size the signals correctly. You'd need a lot more in practice, because in addition to fitting your compute cell logic, state machine logic, and arithmetic logic, you also need to waste extra LUTs to route the arithmetic carry chains and state machine signals across this LUT grid. And even if you manage to do all that, you're still left with a bit-serial design that needs to be clocked an order of magnitude faster than a design with wider inter-cell transfer sizes to get similar performance. When you start thinking about ways to get around some of these limitations while keeping designs with high "spacial locality" efficient, you get something that looks a lot like a modern FPGA.
  - mikewarot 7y ago
    If you had a systolic array that was generic and routless, you could very easily compile (at run time) the filter coefficients directly into the logic, updating as you go. I'd feed inputs from the left, passing them through towards the right, then reflect them back in a manner that would keep timing right. Sums would accumulate and appear as outputs on the left. If you clocked the whole array with a 2 phase clock, you'd get an answer out every cycle, once all the pipelines were filled.

mikewarot 7y ago

If you have a symmetric grid, you can quickly rotate, flip, and otherwise transform the program. Since all the outputs are independent, you can have computation in a cell that has results flowing into the chip, and back out to the edge at the same time. Delays are simply a matter of counting how many cells a result passes, and thus a good signal to feed to an optimizing algorithm.

ohazi 7y ago
The general version of the thing you're describing is a 2d systolic array. Designs like this already map reasonably well to standard FPGAs. The problem with the 4:4 LUT you described above is that you almost always want the compute cell part of your design to have inputs and outputs that are wider than a single bit. For example, if you were designing an FIR filter as a systolic array, you might want one filter coefficient to come from the top of each cell, and your signal to pass through the cells from left to right. A realistic design might have a 16 bit signal and 10 bit coefficients. This would require 160 LUTs per cell just to size the signals correctly. You'd need a lot more in practice, because in addition to fitting your compute cell logic, state machine logic, and arithmetic logic, you also need to waste extra LUTs to route the arithmetic carry chains and state machine signals across this LUT grid. And even if you manage to do all that, you're still left with a bit-serial design that needs to be clocked an order of magnitude faster than a design with wider inter-cell transfer sizes to get similar performance. When you start thinking about ways to get around some of these limitations while keeping designs with high "spacial locality" efficient, you get something that looks a lot like a modern FPGA.
- mikewarot 7y ago
  If you had a systolic array that was generic and routless, you could very easily compile (at run time) the filter coefficients directly into the logic, updating as you go. I'd feed inputs from the left, passing them through towards the right, then reflect them back in a manner that would keep timing right. Sums would accumulate and appear as outputs on the left. If you clocked the whole array with a 2 phase clock, you'd get an answer out every cycle, once all the pipelines were filled.