Comment by peter_d_sherman
6 years ago
Do these operations make the memory Turing-complete?
I don't have the expertise to know...
If they don't -- then what would be needed to be done to the memory controller (in this case a custom FPGA memory controller) to make it Turing-complete?
Also... even if it isn't Turing-complete, then probably whatever functionality is missing could be implemented by the FPGA -- although at the probable cost of a memory round trip for those instructions, right?
In other words, you could probably use this for mixed-mode, hybrid, Turing-completeness via additional FPGA instructions, even if the operations on RAM aren't Turing-complete in and of themselves -- or am I missing something?
All of this sounds very promising!
Great concept, great paper -- hope you get well funded for your next round of research!
It has the functionality of the first Connection Machine, except with no network to exchange values between columns (as another comment pointed out). You can do 64K logic operations, each on one bit, at a time. You still need an external controller (which can be in the FPGA, as you suggested) to fetch instructions, do loops and things like that.
The CM-1 could do conditional execution: you tell the 64k processors to add but only those with a give flag set to 1 will actually do it while the others will execute a NOP. It is possible to simulate this on this design but it would be rather awkward, just like their 1 bit addition is awkward compared to the one clock equivalent in the CM-1.
Strictly speaking it's either turing complete already because it implements arbitrary non-acyclic boolean circuits, or it can never be turing complete because it's limited to finite memory, but two things come to mind as very useful for expanding it's practical usefulness that would probably have to done in the memory controller:
Transpose. (Take a bit-parallel array in row 0, columns 0,1,... and place it (bit-serially) in column 0, rows 0,1,... - and preferably do the same for row 1 to column 1, row 2 to column 2, etc simultaneously.)
Random access (Take a bit-serial index N in rows 1,2,... and load or store row 0 to/from row N.)