Algorithm to achieve optimal layout of decision logic elements for programmable network devices

Patent metadata

Field	Value
Publication number	US-9582251-B2
Application number	US-201514675682-A
Country	US
Kind code	B2
Filing date	Mar 31, 2015
Priority date	Nov 14, 2014
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

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.

First claim

We claim:

1. A processing network for receiving a source code having one or more code paths that are each associated with one or more conditions and one or more assignments of the source code, the network comprising:
a plurality of processing elements on a programmable microchip, wherein each of the processing elements comprise one or more instruction tables and a logic cloud including a grid of logic devices, wherein a first column of the grid receives logic cloud input and a last column of the grid transmits logic cloud output;
a plurality of on-chip routers on the microchip for routing the data between the processing elements, wherein each of the on-chip routers is communicatively coupled with one or more of the processing elements; and
a compiler stored on a non-transitory computer-readable memory and comprising a logic cloud mapper that, based on the grid of logic devices, assigns functions to one or more of the logic devices and routes operable connections between the one or more of the logic devices such that the logic cloud, in conjunction with the instruction tables, implement the conditions and the assignments of the code paths of the source code,
wherein each function corresponds to one or more device input values and a device output value, and further wherein the logic device assigned one of the functions will output the device output value in response to inputting the device input values,
wherein the device input values and the device output value are selected from the group consisting of primary inputs that are to be received from the logic cloud input, intermediate results that are to be received from one of the logic devices or primary outputs that are the logic cloud output to be transmitted to the instruction tables,
wherein the logic cloud mapper determines all possible serial chains of the functions that can be formed such that:
the device input values of the function at the start of each of the chains are one or more of the primary inputs;
the device output value of the function at the end of each of the chains is one of the primary outputs; and
for every pair of the functions that are adjacent within each of the chains, the device output value of the preceding function of the pair matches at least one of the device input values of the other function of the pair.

2. The network of claim 1 , wherein for each of the functions the logic cloud mapper determines a longest chain of the chains that includes the function.

3. The network of claim 2 , wherein, for each of the functions, the logic cloud mapper determines which column or columns within the grid that the logic device to which the function is assigned can be located such that the longest chain that includes the function can fit within the logic devices of a single row of the grid.

4. The network of claim 3 , wherein of the column or columns within the grid that the logic device to which the function is assigned can be located, the logic cloud mapper assigns the function to one of the logic devices in the column closest to the first column whose logic devices have not all already been assigned one of the functions.

5. The network of claim 4 , wherein the logic cloud mapper prioritizes the order of assignment of the functions based on the number of column or columns within the grid that the logic device to which the function is assigned can be located such that, for each column of the grid, the functions with a smaller number of column or columns within the grid that the logic device to which the function is assigned can be located are assigned first.

6. A processing network for receiving a source code having one or more code paths that are each associated with one or more conditions and one or more assignments of the source code, the network comprising:
a plurality of processing elements on a programmable microchip, wherein each of the processing elements comprise one or more instruction tables and a logic cloud including a grid of logic devices, wherein a first column of the grid receives logic cloud input and a last column of the grid transmits logic cloud output;
a plurality of on-chip routers on the microchip for routing the data between the processing elements, wherein each of the on-chip routers is communicatively coupled with one or more of the processing elements; and
a compiler stored on a non-transitory computer-readable memory and comprising a logic cloud mapper that, based on the grid of logic devices, assigns functions to one or more of the logic devices and routes operable connections between the one or more of the logic devices such that the logic cloud, in conjunction with the instruction tables, implement the conditions and the assignments of the code paths of the source code, wherein routing the operable connections between the one or more of the logic devices comprises:
except for the first column, for each of the device input values of each of the functions assigned to one of the logic devices in one of the columns of the grid, coupling a matching device output value of the device output values of the functions assigned to the logic devices in an immediately preceding column of the grid if possible; and
for any of the device input values of the functions assigned to the logic devices of the last column that do not match any of the device output values of the functions of the immediately preceding column, coupling each of the any of the device input values to a bypass output of a bypass device in the immediately preceding column.

7. The network of claim 6 , wherein the bypass output of the bypass devices is equal to a bypass input of the bypass devices.

8. The network of claim 7 , wherein routing the operable connections between the one or more of the logic devices comprises:
except for the first column, for each of the bypass devices of each of the immediately preceding columns whose bypass output is coupled to one of the any of the device input values, coupling to the bypass input a device output value of the device output values of the functions assigned to the logic devices in the immediately preceding column of the grid that matches the one of the any of the device input values if possible; and
for any of the any of the device input values of the functions assigned to the logic devices of the last column that do not match any of the device output values of the functions of the immediately preceding column, coupling each of the any of the any of the device input values to a bypass output of a bypass device in the immediately preceding column.

9. The network of claim 8 , wherein the logic cloud mapper starts with the last column and proceeds through the columns of the grid in order toward the first column when routing the operable connections between the one or more of the logic devices.

10. The network of claim 1 , wherein each of the logic devices comprise one or more multiplexors coupled with a lookup table.

11. A compiler stored on a non-transitory computer-readable medium and configured to generate values based on 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 source code, wherein:
the source code has one or more code paths that are each associated with one or more conditions and one or more assignments of the source code;
each of the processing elements comprise one or more instruction tables and a logic cloud including a grid of logic devices, wherein a first column of the grid receives logic cloud input and a last column of the grid transmits logic cloud output; and
the compiler comprises a logic cloud mapper that, based on

Assignees

• Cavium Inc

Inventors

• Pudiyapura Ajeer Salil
• Atreya Kishore Badari
• Suresh Ravindran

Classifications

• G06F8/427

  Parsing · CPC title

• G06F8/33 Primary

  Intelligent editors · CPC title

• G06F8/443 Primary

  Optimisation · CPC title

• G06F15/7825

  Globally asynchronous, locally synchronous, e.g. network on chip · CPC title

• G06F8/447

  Target code generation · CPC title