Switch memory architectures

• US 7,412,586 B1
• Filed: 07/29/2004
• Issued: 08/12/2008
• Est. Priority Date: 07/29/2003
• Status: Active Grant

• Current Assignee: Colorado State University Research Foundation (Colorado State University System)
• Original Assignee: Colorado State University Research Foundation (Colorado State University System)
• Inventors: Renganarayana, Lakshminarayanan, Gupta, Gautam, Rajopadhye, Sanjay
• Primary Examiner(s): Chan; Eddie P
• Assistant Examiner(s): Fennema; Robert E
• Application Number:
  US10/901,102
• Time in Patent Office: 1,475 Days
• Field of Search: 712/10
• US Class Current: 712/10
• CPC Class Codes: G06F 15/167 using a common memory, e.g. mailbox
• CPC Class Codes: G06F 15/8015 One dimensional arrays, e.g. rings, linear arrays, buses

Abstract

The present invention provides a switch memory architecture (SMA) consisting of: (i) processing elements (PE) (ii) memory banks (MB), and (iii) interconnect switches (ISWITCH). The present invention allows for efficient, potentially unbounded data transfer between two adjacent processes by passing a memory handle and the status registers (memory control information) of the MB. This function may be performed by the ISWITCH.

Claims

1. A machine with switch memory architecture comprising:

a d-dimensional grid of N processing elements (PEs), where d and N are arbitrary integers;

at least one d-dimensional grid of N memory banks (MBs); and

at least one programmable interconnection switch (ISWITCH) having a (d+1)-dimensional grid of switching elements (SEs) configurable to interconnect the N PEs to N MBs, such that each memory bank (MB) of the N MBs is mapped local to one processing element (PE) of the N PEs, wherein the ISWITCH being reconfigurable to remap the interconnection of N PEs to N MBs such that each memory bank (MB) becomes local to a different PE of the N PEs;

wherein each SE transfers its state to a neighbor SE to remap the interconnection of N PEs to N MBs in a single clock cycle.

2. The machine of claim 1, wherein the ISWITCH interconnects the N PEs with N MBs such that each memory bank MB of the N MBs is local to no more than one processing element (PE) of the N PEs at any one time.

3. The machine of claim 1, wherein the machine is of the Single Instruction Multiple Data (SIMD) type, such that said N PEs are not independently programmable, and where the grid has N₁×

N₂×

. . . N_d PEs (where N₁, N₂ . . . N_d, are arbitrary integers).

4. The machine of claim 1, wherein said N PEs, contain memory control information for accessing N MBs.

5. The machine of claim 1, wherein the ISWITCH is reconfigurable in a single clock cycle to rotationally reconnect each MB of the N MBs to a different PE of the N PEs;

wherein rotationally reconnecting is reconnection such that where MB_(i) is disconnected from PE_(i) and connected to PE<sub>(i+δ

)</sub> modulo N for an integer i, δ

, and N.

6. The machine of claim 1, wherein each SE further comprises r(d+1) wires for passing through each switching element (SE), wherein r is an arbitrary integer.

7. The machine of claim 1, wherein the ISWITCH connects N^d inputs to N^d outputs and has (N^d+1) switching elements (SEs).

8. The machine of claim 1, wherein the ISWITCH comprises a defined PE-MB mapping of source to destination interconnection paths, each of which is extendable by a constant distance, δ

, during reconfiguration to remap the interconnection of the N PEs to the N MBs.

9. The machine of claim 1, wherein the PE-to-MB interconnections are invariant with time.

10. The machine of claim 1, wherein interconnections achieved by the ISWITCH are dynamic.

11. The machine of claim 1, the at least one d-dimensional grid of N MBs comprising a plurality of d-dimensional grids of N MBs, each MB of each of the grids of N MBs being connected to a PE of the d-dimensional grid of N PEs through one of a plurality of ISWITCHES.

12. The machine of claim 11, wherein the ISWITCH has r (d+1) wires for passing through each switch element (SE), where r is an arbitrary integer.

13. The machine of claim 11, wherein the ISWITCH may be configured to have broadcast interconnections such that one MB is local to a set of destination N PEs.

14. The machine of claim 1, the reconfiguration of the ISWITCH to remap the interconnection between N PEs and N MBs serving to transfer data from a first PE to which an MB is initially local to a second PE to which the MB becomes local upon the reconfiguration.

15. A method for implementing a machine with switch memory architecture, comprising:

configuring a programmable interconnection switch (ISWITCH) to interconnect a plurality of N processing elements (PEs) in a d-dimensional grid, where d is an arbitrary integer, with a plurality of N memory banks (MBs) organized as at least one d-dimensional grid such that each memory bank (MB) of each of the at least one N MBs is local to only one processing element (PE) of the N PEs at any one time;

reconfiguring the ISWITCH to rotationally reconnect each MB to a different PE in a single clock cycle;

wherein the ISWITCH comprises a (d+1) dimensional array of switching elements (SEs); and

wherein each SE transfers its state to a neighbor SE to remap the interconnection of N PEs to N MBs in a single clock cycle.

16. The method of claim 15, further comprising the step of reconfiguring the ISWITCH for remapping the interconnection of N PEs to N MBs such that each MB becomes local to a different PE.

17. The method of claim 16, wherein the step of reconfiguring ISWITCH for remapping the interconnection serves to transfer data from a PE to a MB was initially local to the PE to which the MB becomes local.

18. The method of claim 15, wherein there are a plurality of d-dimensional of N MBs, each of the grids of the N MBs being interconnected to the d-dimensional grid of N PEs through an ISWITCH.

19. The method of claim 15, wherein the reconnection is a rotational reconnection such that where MB_(i) is disconnected from PE_(i) and connected PE_(i+δ

) modulo N for an integer i, δ

, and N.