3 ms·
Pretty interesting concept, though as other commenters have pointed out the efficiency gains likely break down once your program doesn’t fit onto the mesh all a
by variadix 1y ago
Pretty interesting concept, though as other commenters have pointed out the efficiency gains likely break down once your program doesn’t fit onto the mesh all at once. Also this looks like it requires a “sufficiently smart compiler”, which isn’t a good sign either. The need to do routing etc. reminds me of the problems FPGAs have during place and route (effectively the minimum cut problem on a graph, i.e. NP), hopefully compilation doesn’t take as long as FPGA synthesis takes.
- kyboren 1y ago> The need to do routing etc. reminds me of the problems FPGAs have during place and route (effectively the minimum cut problem on a graph, i.e. NP) I'd like to take this opportunity to plug the FlowMap paper, which describes the polynomial-time delay-optimal FPGA LUT-mapping algorithm that cemented Jason Cong's 31337 reputation: https://limsk.ece.gatech.edu/book/papers/flowmap.pdf https://limsk.ece.gatech.edu/book/papers/flowmap.pdf Very few people even thought that optimal depth LUT mapping would be in P. Then, like manna from heaven, this paper dropped... It's well worth a read.
- almostgotcaught 1y agoI don't what this has to do with what you're responding to - tech mapping and routing are two completely different things and routing is known NP complete.
- ethan_smith 1y agoThis is essentially a CGRA (Coarse-Grained Reconfigurable Array) architecture, which historically has shown impressive efficiency in academic research but struggled with compilation complexity and commercial adoption precisely because of the NP-hard routing problems you've identified.