Algorithm to achieve optimal layout of instruction tables for programmable network devices
AssigneeCavium, Inc.
InventorsAjeer Salil Pudiyapura, Kishore Badari Atreya, Ravindran Suresh
Life of this patent
Estimating the term…
Abstract
A processing network including a plurality of lookup and decision engines (LDEs) each having one or more configuration registers and a plurality of on-chip routers forming a matrix for routing the data between the LDEs, wherein each of the on-chip routers is communicatively coupled with one or more of the LDEs. The processing network further including an LDE compiler stored on a memory and communicatively coupled with each of the LDEs, wherein the LDE compiler is configured to generate values based on input source code that when programmed into the configuration registers of the LDEs cause the LDEs to implement the functionality defined by the input source code.
Claims34
A processing network comprising:
- a plurality of processing elements on a programmable microchip, wherein each of the processing elements have one or more instruction tables each including one or more blocks;
- and
- a compiler stored on a non-transitory computer-readable memory and comprising an instruction table mapper that maps one or more instructions derived from assignments of a source code into one or more lines of the blocks of the instruction tables, wherein the mapping of the instructions comprises a combining process including iteratively grouping a plurality of the instructions into a group based on one or more grouping parameters, wherein in each iteration of the combining process a size value equals the number of the groups in that iteration plus the number of the instructions that have not yet been grouped in that iteration, and further wherein in at least one iteration of the combining process the size value is less than the size value of the previous iteration of the combining process.
A compiler stored on a non-transitory computer-readable medium and configured to generate values based on input source code that when programmed into one or more configuration registers of one or more processing elements on a programmable microchip cause the processing elements to implement the functionality defined by the input source code, wherein the compiler comprises an instruction table mapper that maps one or more instructions derived from assignments of a source code into one or more lines of one or more blocks of instruction tables within the processing elements, wherein the mapping of the instructions comprises a combining process including iteratively grouping a plurality of the instructions into a group based on one or more grouping parameters, wherein in each iteration of the combining process a size value equals the number of the groups in that iteration plus the number of the instructions that have not yet been grouped in that iteration, and further wherein in at least one iteration of the combining process the size value is less than the size value of the previous iteration of the combining process.
A method of implementing a compiler stored on a non-transitory computer-readable medium, the method comprising:
- providing a source code including one or more assignment statements, wherein one or more instructions are configured when executed to perform one or more of the assignment statements;
- and
- mapping the one or more instructions with an instruction table mapper, wherein the instructions are mapped into one or more lines of one or more blocks of instruction tables within one or more processing elements, wherein the mapping of the instructions comprises a combining process including iteratively grouping a plurality of the instructions into a group based on one or more grouping parameters, wherein in each iteration of the combining process a size value equals the number of the groups in that iteration plus the number of the instructions that have not yet been grouped in that iteration, and further wherein in at least one iteration of the combining process the size value is less than the size value of the previous iteration of the combining process.
Dependencies are inferred from the claim text.