Hierarchical multi-core processor and method of programming for efficient data processing
A multi-core processor includes a tree-like structure having a plurality of computing cores arranged in hierarchical levels, the cores all having the same logical architecture. Each core can include computing, interconnecting, and/or storage elements. The functionality of an individual element can be supplied by an entire core in a lower level. A method for programming the processor includes hierarchically decomposing an application into interconnected sub-functions, mapping the sub-functions onto groups of cores at appropriate levels of the processor, and interconnecting the mapped sub-functions so as to hierarchically compose the complete application. Sub-functions can be sequential, concurrent, and/or pipelined. Interconnections can be static or dynamically switchable under program control. Interconnect elements can also be used to implement flow control as needed in pipelined operations to maintain data coherency. The decomposing and mapping process can be iterated on sub-functions so as to optimize load balancing, software performance, and hardware efficiency.
1. A multi-core processor, comprising:
a plurality of processing cores, referred to herein as computing planes,
the computing planes being arranged in a hierarchy of levels including a highest level and a lowest level, each of the levels including at least one computing plane,
each of the computing planes including a control plane and an associated datapath,
each of the control planes including a sequencing instruction memory that is able to store configuration and control information applicable to its associated data path, the configuration information including instructions that control manipulation and routing of data by its associated datapath,
each of the control planes being able to receive status information from its associated data path, and being able to provide configuration and control information to its associated data path,
each of the datapaths including at least one data input, at least one data output, and at least one element, the element being one of a compute element that is able to manipulate data, an interconnect element that is able to route data, and a storage element that is able to store data, and
for at least one of the elements that is in a level above the lowest level, the functionality of the element being provided by a computing plane in a level below the level of the element.
2. The processor of claim 1 , wherein at least one of the compute elements includes an internal buffer register that is able to provide temporary storage for intermediate results.
3. The processor of claim 1 , wherein at least one of the storage elements is able to perform at least one data processing function.
4. The processor of claim 3 , wherein the data processing function is one of:
computing an address from data;
rounding of data;
saturating of data; and
adding or subtracting of two consecutive data inputs.
5. The processor of claim 1 , wherein at least one of the interconnect elements is able to form a static connection between two other elements.
6. The processor of claim 1 , wherein at least one of the interconnect elements is able to form dynamic connections between pairs of other elements, the dynamic connections being changeable under control of the configuration instructions supplied by the control plane.
7. The processor of claim 1 , wherein at least one of the interconnect elements includes both a signal transmission channel and a data transmission channel, the signal transmission channel being able to transmit a flow control signal in parallel with data transmitted by the data transmission channel, the flow control signal being usable for controlling timing of the flow of data from the data transmission channel.
8. A method for programming the processor of claim 1 to perform a large algorithmic function by mapping the algorithmic function onto the computing planes of the processor, the method comprising:
partitioning the large algorithmic function into a first layer of sub-functions with data flow between the sub-functions and associated flow control;
if one of the sub-functions is not suitable for mapping onto a computing plane of the processor, partitioning the sub-function into a lower layer of sub-functions having data flow between the sub-functions and associated flow control;
repeating the step of partitioning the sub-functions into lower layers of sub-functions until all of the lowest level sub-functions are suitable for mapping onto computing planes of the processor;
allocating processor time slots and hardware resources to the sub-functions so as to approximately match the processor resources with relative computational and data flow complexities of the sub-functions; and
configuring interconnects of the processor according to the data flows between the sub-functions.
9. The method of claim 8 , further comprising configuring at least some of the interconnects for data transmission with flow control so as to maintain synchronicity of data during execution of the algorithmic function.
10. The method of claim 8 , further comprising appending null operations to at least one of the sub-functions so as to eliminate a data dependency of an execution time of the sub-function.
11. The method of claim 8 , wherein the steps of partitioning the large algorithmic function and partitioning the sub-functions are carried out by an automatic software tool.
12. The method of claim 8 , wherein the step of partitioning the sub function includes partitioning any sub-function having a data dependent execution time into sub-functions that do not have data dependent execution times.
13. The method of claim 8 , wherein allocating processor time slots and hardware resources to a hierarchy of sub-functions includes:
selecting a level of the processor to be a highest level of allocation to the hierarchy of sub-functions; and
mapping each of the sub-functions in the hierarchy onto a computing plane that is at a level of the processor at the same offset below the highest level as the offset of the sub-function below the highest layer of the sub-functions in the hierarchy.
14. The method of claim 8 , further comprising repeating the step of allocating processor time slots and hardware resources so as to achieve load balancing of the hardware resources.
15. The method of claim 8 , wherein configuring the interconnects of the processor according to the data flows between the sub-functions includes combining sub-functions having fixed execution times and providing flow control mechanisms so as to compose functions having data-dependent execution times.
16. The method of claim 15 , further comprising estimating the data-dependent execution times based on an input data range and the data flow pattern.
17. The method of claim 16 , further comprising estimating at least one of an upper bound, a lower bound, and a distribution of the execution times.
18. The method of claim 8 , wherein configuring the interconnects of the processor according to the data flows between the sub-functions includes combining sub-functions according to at least one of sequential composition, concurrent composition, and pipelined composition.
19. The method of claim 8 , wherein configuring the interconnects of the processor according to the data flows between the sub-functions includes using buffer storage to absorb a difference between a rate of data production of a first element and a rate of data consumption of a second element.
20. The method of claim 19 , wherein the buffer storage is configured to produce a “back pressure” signal when an amount of data stored in the buffer storage exceeds a specified watermark amount, the back pressure signal causing the first element to temporarily stop producing output data.
21. The method of claim 8 , wherein the step of allocating processor time slots and hardware resources to the sub-functions further includes using a scheduling tool to schedule overlapping execution of sub-function epilogues and prologues when possible.