Method and apparatus for performing complex calculations in a multiprocessor array

• US 20090132794A1
• Filed: 11/16/2007
• Published: 05/21/2009
• Est. Priority Date: 11/16/2007
• Status: Active Grant

• Current Assignee: Array Portfolio LLC
• Original Assignee: VNS Portfolio LLC
• Inventors: Wu, Chiakeng (Jack), Snively, Leslie O., Ebert, Paul Michael
• Granted Patent: US 7,996,454 B2
• Time in Patent Office: Days
• US Class Current: 712/225
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A method and apparatus for performing complex mathematical calculations. The apparatus includes a multicore processor 10 where the cores 15 are connected 20 into a net with the processors on the periphery 15a primarily dedicated to input/output functions and distribution of tasks to the central processors 15b-h of the net. The central processors 15b-h perform calculations substantially simultaneously, far exceeding the speed of conventional processors. The method 100, which may be implemented by an instruction set to the processor nodes, informs the processor nodes how to divide the work and conduct the calculations. The method includes steps dividing the data into subsets 110 directing the subsets to predetermined nodes 115, performing the calculations 120 and outputting the results 125.

Claims

1. A method of mapping complex computations on complex data to multiple computer nodes to achieve higher execution speed, comprising the steps of:

dividing said complex data into subsets of data, directing a subset of data to a node, and, routing each subset of data to other individual nodes and processing each subset of data in the node said subset was directed to, collecting the result of each calculation and transferring said collected results to an output.

2. A method of mapping complex computations on complex data to multiple computer nodes to achieve higher execution speed as in claim 1, wherein said complex calculations are butterfly calculations.

3. A method of mapping complex computations on complex data to multiple computer nodes to achieve higher execution speed as in claim 2, wherein said dividing step divides the data into subsets determined the time domain data are rearranged, with reference to the sequence index of each point, into a decomposed FFT signal pattern.

4. A method of mapping complex computations to multiple computers to achieve higher execution speed as in claim 1, further comprising the step of rearranging the time domain data.

5. A method of mapping complex computations on complex data to multiple computer nodes to achieve higher execution speed as in claim 4, wherein said rearrangement step is accomplished in an external device.

6. A method of mapping complex computations to multiple computers to achieve higher execution speed as in claim 4, further comprising the step of exchanging the intermediate results from the first two steps, between two sets of nodes.

7. A method of mapping complex computations to multiple computers to achieve higher execution speed as in claim 6, wherein said nodes are selected to be in close physical proximity to minimize data transfer time between nodes.

8. A system for performing complex mathematical calculations comprising, an input, and an output, a plurality of microprocessors on a substrate wherein each microprocessor includes its own ROM and RAM and is connected directly to at least two other microprocessors by a data path, and an instruction set for conveying data to individual microprocessors, and routing each subset of data to other individual microprocessors, and processing each subset of data in the microprocessor said subset was directed to, and collecting the result of each calculation and transferring said collected results to said output.

9. A system for performing complex mathematical calculations as in claim 8, wherein said complex calculations are butterfly calculations.

10. A system for performing complex mathematical calculations as in claim 9, wherein said instruction set conveys data to processors in close proximity to each other for minimizing calculation time.

11. A system for performing complex mathematical calculations as in claim 8, wherein at least two of those cores on the periphery of said chip are devoted to I/O functions.

12. A system for performing complex mathematical calculations as in claim 11, wherein said complex calculations are performed by those cores in the center of said chip.

13. A system for performing complex mathematical calculations as in claim 12, wherein said complex calculations are performed by multiple cores in the center of said chip, and wherein the time domain data is rearranged, with reference to the sequence index of each point, into a decomposed FFT signal pattern.

14. A system for performing complex mathematical calculations as in claim 13, wherein the central cores calculating the time domain data with reference to the sequence index of each point, into a decomposed FFT signal pattern are selected to be in close physical proximity.

15. A set of instructions for use in a processor array having a plurality of microprocessors mapping complex computations on complex data, comprising:

instructions for dividing said complex data into subsets of data, and directing a subset of data to a node, and routing each subset of data to other individual nodes, and processing each subset of data in the node said subset was directed to, collecting the result of each calculation and transferring said collected results to an output.

16. A set of instructions for use in a processor array having a plurality of microprocessors mapping complex computations on complex data as in claim 15, wherein said complex calculations are butterfly calculations.

17. A set of instructions for use in a processor array having a plurality of microprocessors mapping complex computations on complex data as in claim 16, wherein said dividing step divides the data into subsets, the time domain data are rearranged, with reference to the sequence index of each point, into a decomposed FFT signal pattern.

18. A set of instructions for use in a processor array having a plurality of microprocessors mapping complex computations on complex data as in claim 15, further comprising the operation of rearranging the time domain data.

19. A set of instructions for use in a processor array having a plurality of microprocessors mapping complex computations on complex data as in claim 18, wherein said rearrangement operation is accomplished in an external device.

20. A set of instructions for use in a processor array having a plurality of microprocessors mapping complex computations on complex data as in claim 18, further comprising the operation of exchanging the intermediate results from between two sets of nodes.

21. A set of instructions for use in a processor array having a plurality of microprocessors mapping complex computations on complex data as in claim 20, wherein said nodes are selected to be in close physical proximity to minimize data transfer time between nodes.