Hierarchical Reconfigurable Computer Architecture

• US 20110107337A1
• Filed: 12/22/2006
• Published: 05/05/2011
• Est. Priority Date: 12/22/2005
• Status: Active Grant

• Current Assignee: Stmicroelectronics France (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Inventors: Cambonie, Joel
• Granted Patent: US 8,799,623 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 13/368 with decentralised access control
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture
• CPC Class Codes: G06F 15/803 Three-dimensional arrays or hypercubes
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

A reconfigurable hierarchical computer architecture having N levels, where N is an integer value greater than one, wherein said N levels include a first level including a first computation block including a first data input, a first data output and a plurality of computing nodes interconnected by a first connecting mechanism, each computing node including an input port, a functional unit and an output port, the first connecting mechanism capable of connecting each output port to the input port of each other computing node; and a second level including a second computation block including a second data input, a second data output and a plurality of the first computation blocks interconnected by a second connecting means for selectively connecting the first data output of each of the first computation blocks and the second data input to each of the first data inputs and for selectively connecting each of the first data outputs to the second data output.

Claims

1. A reconfigurable hierarchical computer architecture having N levels, where N is an integer value greater than one, wherein said N levels comprise:

a first level comprising a first computation block comprising a first data input, a first data output and a plurality of computing nodes interconnected by a first connecting means, each computing node comprising;

an input port;

a functional unit; and

an output port;

the first connecting means capable of connecting each output port to the input port of each other computing node; and

a second level comprising a second computation block comprising;

a second data input;

a second data output; and

a plurality of said first computation blocks interconnected by a second connecting means for connecting a selected one of said first data output of each of said first computation blocks and said second data input to each of said first data inputs and for connecting a selected one of said first data outputs to said second data output.

2. The reconfigurable computer architecture of claim 1, wherein said first connecting means provides a time multiplexed connection, and wherein said second connecting means provides a static connection.

3. The reconfigurable computer architecture of claim 1, wherein each computer node further comprises an instruction memory and wherein said first connection means is controlled by said instruction memory.

4. The reconfigurable computer architecture of claim 1, further comprising further levels, each nth level, where n is equal to each integer value from 3 to N, comprising an nth computation block comprising:

an nth data input;

an nth data output; and

a plurality of (n−

1)th computation blocks each comprising an (n−

1)th data input and an (n−

1)th data output, said (n−

1)th computation blocks interconnected by an nth connecting means for connecting a selected one of said (n−

1)th data output of each of said (n−

1)th computing nodes and the nth data input to each of said (n−

1)th data inputs, and for connecting a selected one of said (n−

1)th data outputs to the nth data output.

5. The reconfigurable hierarchical computer architecture of claim 1, wherein each computing node further comprises at least one input buffer connected to said input port.

6. The reconfigurable hierarchical computer architecture of claim 1, wherein said at least one input buffer is connectable directly to said output port 128 of each computing node.

7. The reconfigurable hierarchical computer architecture of claim 1, wherein each computing node further comprises at least one register file for storing an output from said functional unit.

8. The reconfigurable hierarchical computer architecture of claim 1, wherein said architecture is a radix r architecture, r being an integer value greater than one, wherein said second computation block comprises r first computation blocks, and said nth computation block comprises r (n−

1)th computation blocks.

9. The reconfigurable hierarchical computer architecture of claim 8, wherein r is equal to 4.

10. The reconfigurable hierarchical computer architecture claim 1, wherein said second connecting means is a multiplexer arranged to be statically programmed in a boot phase of said computer architecture.

11. The reconfigurable hierarchical computer architecture claim 1, wherein said first connecting means comprises a crossbar.

12. The reconfigurable hierarchical computer architecture of claim 1, wherein said first connecting means comprises an input multiplexer associated with said input port of each computing node for receiving said data output of each other computing node of the plurality of computing nodes, and for receiving the data output of said second computation block.

13. The reconfigurable hierarchical computer architecture of claim 1, wherein a first computing node of a first one of said first computation blocks is connected to a second computing node of a second one of said first computation blocks via a third computing node of said first one of said first computation blocks.

14. The reconfigurable hierarchical computer architecture of claim 1, wherein each of said computing nodes receives a common clock signal such that they operate synchronously with each other.

15. A portable media device comprising at least one reconfigurable hierarchical computer architecture having N levels, where N is an integer value greater than one, wherein said N levels comprise:

a first level comprising a first computation block comprising a first data input, a first data output and a plurality of computing nodes interconnected by a first connecting means, each computing node comprising;

an input port;

a functional unit; and

an output port;

the first connecting means capable of connecting each output port to the input port of each other computing node; and

a second level comprising a second computation block comprising;

a second data input;

a second data output; and

a plurality of said first computation blocks interconnected by a second connecting means for connecting a selected one of said first data output of each of said first computation blocks and said second data input to each of said first data inputs and for connecting a selected one of said first data outputs to said second data output.

16. A method of mapping a required task onto the physical resources of a reconfigurable hierarchical computer architecture having N levels, where N is an integer value greater than one, a first level comprising a cluster comprising a plurality of interconnected computing nodes each comprising a functional unit, and a second level comprising an interconnected plurality of said clusters, said method comprising:

partitioning said task into subtasks each comprising a plurality of operations;

assigning each of said subtasks to one of said clusters;

assigning the operations of each subtask to the computing nodes in each cluster; and

scheduling the operations in the computing nodes and performing fine routing between computing nodes.

17. The method of claim 16, further comprising, after the step of assigning each of said subtasks to one of said clusters, the steps of:

performing routing between clusters.

18. The method of claim 17, wherein if routing between clusters is unsuccessful, comprising the further step of increasing the physical resources of said reconfigurable hierarchical architecture and performing again said partitioning step.

19. The method of claim 16, wherein said step of performing scheduling and fine routing comprises reducing the number of connections between clusters by providing a connection between a first computing node in a first cluster and a second computing node in a second cluster via a third computing node in said first cluster.

20. The method of claim 16, wherein said step of scheduling said operations in the computing nodes comprises scheduling, with respect to a clock signal, each operation to be performed by said functional unit of each computing node, and assigning a time slot defined by said clock signal to each data transfer between computing nodes.

21. A reconfigurable hierarchical computer architecture having N levels, where N is an integer value greater than one, a first level comprising a cluster comprising a plurality of interconnected computing nodes, a second level comprising an interconnected plurality of said clusters, each computing node comprising:

a functional unit;

an instruction memory; and

at least one buffer coupled to a first input port of said computing node.

22. The reconfigurable hierarchical computer architecture of claim 21, wherein said at least one buffer is coupled to a plurality of input ports of each of said computing nodes and to an output of said functional unit, said buffer comprising a plurality of registers each configurable to receive data values from a selected one of said input ports and the output of said functional unit.

23. The reconfigurable hierarchical computer architecture of claim 21, wherein each computing node further comprises an output port and selecting means for selectively connecting said output port directly to said at least one buffer.

24. The reconfigurable hierarchical computer architecture of claim 21, wherein each computing node further comprises an output register connected to an output of said functional unit.

25. The reconfigurable hierarchical computer architecture of claim 24, further comprising a second buffer connected to a second input port, and selecting means for selectively connecting an output of one of said first and second buffers or said output register to an input of said functional unit.

26. The reconfigurable hierarchical computer architecture of claim 21, wherein each computing node further comprises at least one input multiplexer connected to said at least one input buffer, said at least one input multiplexer also connected to an output port of each other of said plurality of computing nodes.

27. A portable media device comprising at least one reconfigurable hierarchical computer architecture having N levels, where N is an integer value greater than one, a first level comprising a cluster comprising a plurality of interconnected computing nodes, a second level comprising an interconnected plurality of said clusters, each computing node comprising:

a functional unit;

an instruction memory; and

at least one input buffer.

28. A method of mapping a required task onto the physical resources of a hierarchical reconfigurable computer architecture having N levels, where N is an integer value greater than one, a first level comprising a cluster comprising a plurality of interconnected computing nodes, and a second level comprising a plurality of interconnected clusters, said method comprising:

determining that a new connection is required between a first computing node in a first cluster and a second computing node in a second cluster;

determining whether a connection already exists between a third computing node in said first cluster and said second cluster; and

if said connection already exists connecting said first computing node to said second, computing node via said third computing node.

29. The method of claim 28, further comprising:

if no connection exists between said third computing node and said second cluster, creating a connection between said first computing node and said second computing node, and connecting at least one other computing node of said first cluster to said second cluster via said first computing node.