Methods and apparatus for signal flow graph pipelining that reduce storage of temporary variables
View Patent ↗A system for pipelining signal flow graphs by a plurality of shared memory processors organized in a 3D physical arrangement with the memory overlaid on the processor nodes that reduces storage of temporary variables. A group function formed by two or more instructions to specify two or more parts of the group function. A first instruction specifies a first part and specifies control information for a second instruction adjacent to the first instruction or at a pre-specified location relative to the first instruction. The first instruction when executed transfers the control information to a pending register and produces a result which is transferred to an operand input associated with the second instruction. The second instruction specifies a second part of the group function and when executed transfers the control information from the pending register to a second execution unit to adjust the second execution unit's operation on the received operand.
1. A network of nodes organized in stages according to dimensions of a row (R) by column (C) by plane (P) matrix that forms an R×C×P array having connectivity according to adjacency of connections between elements in corresponding dimensions of the R×C×P array which includes wrap around adjacent elements, the connectivity within the stages includes connections between nodes in the same position, the network comprising:
p planes of R×C arrays of A r,c,p nodes and p planes of R×C arrays of R r,c,p nodes having a different p that is the same for an R×C array of A r,c,p nodes and a corresponding R×C array of R r,c,p nodes, p ∈ {0, 1, . . . , P−1}, each R×C array of A r,c,p nodes and each R×C array of R r,c,p nodes having a different r that is the same for each row r, r ∈ {0, 1, . . . , R−1}, and for each row r, c varies as the column number c ∈ {0, 1, . . . , C−1}, each A r,c,p node in each plane p is operable to output a data value, and each R×C array of R r,c,p nodes is directly coupled to a corresponding R×C array of A r,c,p nodes according to a 1 to N adjacency of nodes in a first dimension, N a positive odd integer, and R≧N and C≧N, wherein each R r,c,p node is operable to select a data value solely from directly coupled nodes A r,c−└N/2┘,p , . . . , A r,c−2,p , A r,c−1,p , A r,c,p , A r,c+1,p , A r,c−2,p , . . . , A r,c+└N/2┘,p and to output the R r,c,p node selected data value, wherein for a selected value of N, the A r,c−└N/2┘,p , . . . , A r,c−2,p , A r,c−1,p sequence of nodes has └N/2┘ nodes and for N>1 the last node is A r,c−└N/2┘,p and the A r,c+1,p , A r,c+2,p , . . . , A r,c+└N/2┘,p sequence of nodes has └N/2┘ nodes and for N>1 the last node is A r,c+└N/2┘,p , wherein └N/2┘ is the floor of N/2 which is the largest integer less than N/2;
p planes of R×C arrays of S r,c,p nodes having a different p that is the same for an R×C array of R r,c,p nodes and a corresponding R×C array of S r,c,p nodes, p ∈ {0, 1, . . . , P−1}, each R×C array of S r,c,p nodes having a different r that is the same for each row r, r ∈ {0, 1, . . . , R−1}, and for each row r, c varies as the column number c ∈ {0, 1, . . . , C−1}, each R×C array of S r,c,p nodes in each plane p is directly coupled to a corresponding R×C array of R r,c,p nodes according to a 1 to M adjacency of nodes in a second dimension, M a positive odd integer, and R≧M and C≧M, wherein each S r,c,p node is operable to select a data value solely from directly coupled nodes R r−└M/2┘,c,p , . . . , R r−2,c,p , R r−1,c,p , R r,c,p , R r+1,c,p , R r+2,c,p , . . . , R r+└M/2┘,c,p and to output the S r,c,p node selected data value, wherein for the selected value of M, the R r−└M/2┘,c,p , . . . , R r−2,c,p , R r−1,c,p sequence of nodes has └M/2┘ nodes and for M>1 the last node is R r−└M/2┘,c,p , the R r+1,c,p , R r+2,c,p , . . . , R r+└M/2┘,c,p sequence of nodes has └M/2┘ nodes and for M>1 the last node is R r+└M/2┘,c,p , wherein └M/2┘ is the floor of M/2 which is the largest integer less than M/2; and
p planes of R×C arrays of V r,c,p nodes having a different p that is the same for an R×C array of S r,c,p nodes and a corresponding R×C array of V r,c,p nodes, p ∈ {0, 1, . . . , P−1}, each R×C array of V r,c,p nodes having a different r that is the same for each row r, r ∈ {0, 1, . . . , R−1}, and for each row r, c varies as the column number c ∈ {0, 1, . . . , C−1}, and each V r,c,p node is directly coupled to P S r,c,p nodes having the same r and c as the V r,c,p node, p ∈ {0, 1, . . . , P−1}, wherein each V r,c,p node is operable to select a data value from directly coupled P S r,c,p nodes and to output the V r,c,p node selected data value.
2. The network of claim 1 further comprising:
a plurality of B r,c,p nodes, each B r,c,p node directly coupled to a corresponding V r,c,p node.
3. The network of claim 2 , wherein each B r,c,p node is overlaid upon a corresponding A r,c,p node.
4. The network of claim 1 , wherein M≠N.
5. The network of claim 1 , wherein R, C, and P are individually selected, wherein in a first implementation R=C=P, in a second implementation R≠C≠P, in a third implementation R=C≠P, in a fourth implementation R=P≠C, and in a fifth implementation R≠C=P.
6. The network of claim 1 , wherein each A r,c,p node is a processor that is operable to select a path through a directly coupled R r,c,p node to communicate the R r,c,p node selected data value, to select a path through a directly coupled S r,c,p node to communicate the S r,c,p node selected data value, and to select a path through a directly coupled V r,c,p node to communicate the V r,c,p node selected data value in response to the A r,c,p processor executing a memory access instruction.
7. The network of claim 1 , wherein each A r,c,p node is a storage node that is operable to select a path through a directly coupled R r,c,p node to communicate the R r,c,p node selected data value, to select a path through a directly coupled S r,c,p node to communicate the S r,c,p node selected data value, and to select a path through a directly coupled V r,c,p node to communicate the V r,c,p node selected data value in response to the A r,c,p storage node executing a memory access instruction.
8. The network of claim 1 , wherein the R r,c,p nodes, the S r,c,p nodes, and the V r,c,p nodes each separately comprise:
a plurality of function units, each function unit selectively operable to execute a function on one or more data values received from the directly coupled nodes to produce an output data value.
9. The network of claim 2 , wherein each B r,c,p node is a processor that is operable to select a path through a directly coupled R r,c,p node to communicate the R r,c,p node selected data value, to select a path through a directly coupled S r,c,p node to communicate the S r,c,p node selected data value, and to select a path through a directly coupled V r,c,p node to communicate the V r,c,p node selected data value in response to the B r,c,p processor executing a memory access instruction.
10. The network of claim 2 , wherein each B r,c,p node is a storage node that is operable to select a path through a directly coupled R r,c,p node to communicate the R r,c,p node selected data value, to select a path through a directly coupled S r,c,p node to communicate the S r,c,p node selected data value, and to select a path through a directly coupled V r,c,p node to communicate the V r,c,p node selected data value in response to the B r,c,p storage node executing a memory access instruction.
11. The network of claim 1 , wherein the A r,c,p nodes, the R r,c,p nodes, and the S r,c,p nodes are physically arranged for each value of p, p ∈ {0, 1, . . . , P−1}, in a two dimensional (2D) row by column array which creates P 2D row by column arrays.
12. The network of claim 11 , wherein the connections between the A r,c,p nodes and the R r,c,p nodes are physically placed by row in each P 2D row by column array and the connections between the the R r,c,p nodes and the S r,c,p nodes are physically placed by column in each P 2D row by column array.
13. The network of claim 11 , wherein the P row by column arrays are overlaid and the connections between the V r,c,p nodes and the P S r,c,p nodes are local to each group of V r,c,p nodes and the S r,c,p nodes having the same r, the same c, and different p values.