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

摘要

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.

主权项

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; andfor 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.