Lookup engine with programmable memory topology
An architecture for a specialized electronic computer for high-speed data lookup employs a set of tiles each with independent processors and lookup memory portions. The tiles may be programmed to interconnect to form different memory topologies optimized for the particular task.
1. A network router for routing data packets in a network comprising:
a series of ports receiving and transmitting data packets;
a general-purpose processor communicating with the series of ports to provide for network routing functions including packet processing but exclusive of some data packet lookup functions;
a packet lookup engine communicating with the general-purpose processor to receive data therefrom and to conduct memory lookups based on the data, the packet lookup engine comprising a set of intercommunicating computational tiles each tile including:
(1) a set of lookup processors providing elemental memory lookup functions, each lookup processor associated with a program memory for holding program instructions;
(2) a lookup memory holding packet related data and accessible by the set of lookup processors executing the elemental memory lookup functions; and
(3) interconnection circuitry managing intercommunication of data between the tiles;
wherein the program instructions include:
(1) at least one instruction reading a register associated with data received at the tiles;
(2) at least one instruction reading the lookup memory associated with the tile; and
(3) at least one instruction sending data to another tile;
wherein the program instructions when executed prevent at least one of:
(i) collisions among data being transmitted among the tiles;
(ii) conflicting demands for processing by lookup processors of a tile; and
(iii) direct transmission from one tile to a nonadjacent tile.
2. The network router of claim 1 wherein an arrival of data at a lookup processor triggers execution of the program instructions from a corresponding program memory and wherein the lookup processor is idle once the program instructions have been completed until a next arrival of data at the lookup processor.
3. The network router of claim 1 wherein the lookup processors provide an instruction set having program instructions to implement a function of routing data to specific other tiles dependent on an outcome of a memory lookup of look up memory.
4. The network router of claim 1 wherein the lookup processors are sequenced so that different lookup processors handle successive arrivals of data at the tile.
5. The network router of claim 1 wherein the lookup processors provide only integer computational support without branch prediction.
6. The network router of claim 1 wherein the interconnection circuitry does not provide buffering of transmitted data.
7. The network router of claim 1 wherein the interconnection circuitry does not provide flow control that coordinates a rate of data transmission among tiles.
8. The network router of claim 1 wherein the interconnection circuitry routes data among the tiles according to a routing header applied to the data by the lookup processor according to an execution of the program instructions.
9. The network router of claim 1 wherein the interconnection circuitry routes data between the tiles according to a routing header associated with the data and the interconnection circuitry follows static programmed rules in interpreting the header to route the data.
10. The network router of claim 1 wherein the interconnection circuitry routes data among the tiles according to a routing header associated with the data and identifying a final destination tile for the data where the data will be processed by a lookup processor.
11. The network router of claim 1 wherein the interconnection circuitry routes data among the tiles according to a routing header indicating a multicasting of the data and a destination tile for the data, causing the routed data to be processed by all tiles receiving the data before the receipt of the data by the destination tile.
12. The network router of claim 1 wherein the interconnection circuitry provides at least two physically distinct channels between a tile and the other tiles to which it is connected by channels, each channel providing independent input and output pathways.
13. The electronic processor of claim 1 wherein the lookup processors are programmed so that different tiles represent different nodes of a lookup tree.
14. The electronic processor of claim 1 wherein the lookup processors are programmed so that different tiles represent different ranks of a hash table address.
15. A network router for routing data packets in a network comprising:
a series of ports receiving and transmitting data packets;
a general-purpose processor communicating with the series of ports to provide for network routing functions including packet processing but exclusive of some data packet lookup functions;
a packet lookup engine communicating with the general-purpose processor to receive data therefrom and to conduct memory lookups based on the data, the packet lookup engine comprising a set of intercommunicating computational tiles each tile including:
(1) a set of lookup processors providing elemental memory lookup functions, each lookup processor associated with a program memory for holding program instructions;
(2) a lookup memory holding packet related data and accessible by the set of lookup processors executing the elemental memory lookup functions; and
(3) interconnection circuitry managing intercommunication of data between the tiles
further including a compiler executing on a an independent electronic processor generating program instructions for each of the lookup processors, the program instructions including:
(1) at least one instruction reading a register associated with data received at the tiles;
(2) at least one instruction reading the memory associated with the tile; and
(3) at least one instruction sending data to another tile;
wherein the compiler includes a routing analyzer analyzing a path and timing of data among tiles to detect at least one of:
(i) collisions among data being transmitted among the tiles;
(ii) conflicting demands for processing by lookup processors of a tile; and
(iii) direct transmission from one tile to a nonadjacent tile.
16. A network router for routing data packets in a network comprising:
a series of ports receiving and transmitting data packets;
a general-purpose processor communicating with the series of ports to provide for network routing functions including packet processing but exclusive of some data packet lookup functions;
a data packet lookup engine communicating with the general-purpose processing program to conduct memory lookups based on information provided by the general- purpose processor, the data packet lookup engine comprising a set of intercommunicating computational tiles, each tile including at least one lookup processor and a memory comprising a portion of a look-up table accessible uniquely by the tile, wherein the tiles include interconnection circuitry and programmable memory, the programmable memory receiving instructions which provide a static topology of interconnection among the tiles through the interconnection circuitry during operation of the router
wherein the instructions in the programmable memory include:
(1) at least one instruction reading a register associated with data received at the tiles;
(2) at least one instruction reading the lookup memory associated with the tile; and
(3) at least one instruction sending data to another tile;
wherein the program instructions when executed prevent at least one of:
(i) collisions among data being transmitted among the tiles;
(ii) conflicting demands for processing by lookup processors of a tile; and
(iii) direct transmission from one tile to a nonadjacent tile.
17. The network router of claim 16 wherein each tile includes a set of lookup processors activated in a fixed sequence so that different lookup processors handle successive arrivals of data at the tile.
18. The network router of claim 16 wherein an arrival of data at a lookup processor triggers execution of the program instructions from the corresponding program memory and wherein the lookup processor is idle once the program instructions have been completed until a next arrival of data at the lookup processor.
19. The network router of claim 16 wherein the lookup processors provide only integer computational support without branch prediction.
20. The network router of claim 16 wherein the interconnection circuitry does not provide buffering of transmitted data.
21. The network router of claim 16 wherein the interconnection circuitry routes data among the tiles according to a routing header applied to the data by the lookup processor according to an execution of the program instructions.
22. The network router of claim 16 wherein the interconnection circuitry may receive data from other tiles from different directions, and wherein the interconnection circuitry establishes a priority among the different directions to accept data from a first direction and ignore data from a second direction when the data from the first and second directions arrives at the same time.