Switching systems and methods using wildcard searching
View Patent ↗In some embodiments, a hardware linked-list manager includes a wildcard search controller for generating corresponding queue-specific read requests from wildcard read requests. The linked-list manager may be part of an on-chip interagent switch for allowing a plurality of agents to communicate with each other. The interagent switch may include a crossbar switch and a plurality of hardware linked-list managers integrated on the chip, connected to a random access memory, and connected to the crossbar switch such that the crossbar switch is capable of connecting each of the linked-list managers to each of the agents. Each linked-list manager sends agent-generated data to the memory for storage in the memory as a linked-list element, and retrieves linked-list elements from memory in response to agent read requests. A shared free-memory linked-list manager may maintain a linked list of free memory locations, and provide free memory address locations to a linked list manager upon request.
1. An integrated circuit comprising a hardware wildcard search controller for generating a queue-specific read request from a wildcard read request, the queue-specific read request comprising an identifier of a non-empty target linked-list queue selected from a linked-list queue segment comprising a plurality of linked-list queue sets, each linked-list queue set comprising a plurality of linked-list queues, the wildcard search controller comprising:
a segment request state controller configured to:
receive an agent wildcard read request,
identify a search-start linked-list queue,
transmit an identifier of the search start linked-list queue,
receive an identifier of the non-empty target linked-list queue,
assign the non-empty target linked-list queue to be an updated search start linked-list queue for a subsequent wildcard read request;
a zoom-out search controller connected to the segment request state controller, configured to:
receive the identifier of the search start linked-list queue from the segment request state controller,
employ the identifier of the search start linked-list queue to identify a search target linked-list queue set, and
transmit an identifier of the search target linked-list queue set; and
a zoom-in search controller connected to the zoom-out search controller, configured to:
receive the identifier of the search target linked-list queue set,
identify the non-empty target linked-list queue by retrieving linked-list queue states for linked-list queues belonging to the search target linked-list queue set, and
transmit the identifier of the non-empty target linked-list queue.
2. The integrated circuit of claim 1 , wherein identifying the search target linked-list queue set comprises retrieving linked-list queue set states for the plurality of linked-list queue sets, a state of a linked-list queue set identifying a number of non-empty linked-list queues in the linked-list queue set.
3. An integrated circuit comprising a wildcard search controller for generating a queue-specific read request from a wildcard read request received over an agent-side interface of the wildcard search controller, the queue-specific read request comprising an identifier of a non-empty target linked-list queue selected from a segment comprising a plurality of linked-list queues, the wildcard search controller comprising:
a zoom-out search controller for generating a search target linked-list queue set identifier in response to receipt of the wildcard read request; and
a zoom-in search controller connected to the zoom-out search controller, for receiving the search target linked-list queue set identifier and generating the identifier of the non-empty target linked-list queue by retrieving linked-list queue states for linked-list queues belonging to the search target linked-list queue set.
4. An integrated circuit comprising a wildcard search controller for generating a queue-specific read request from a wildcard read request received over an agent-side interface of the wildcard search controller, the queue-specific read request comprising an identifier of a non-empty target linked-list queue selected from a segment comprising a plurality of linked-list queues, the wildcard search controller comprising:
means for generating a search target linked-list queue set identifier in response to receipt of the wildcard read request; and
means for generating the identifier of the non-empty target linked-list queue by retrieving linked-list queue states for linked-list queues belonging to the search target linked-list queue set.
5. A wildcard read method for generating a linked-list queue-specific read request at a wildcard search controller from a wildcard read request received over an agent-side interface of the wildcard search controller, the wildcard search controller forming part of an integrated circuit, the linked-list queue-specific read request comprising an identifier of a non-empty target linked-list queue selected from a segment comprising a plurality of linked-list queues, the wildcard read method comprising:
generating a search target linked-list queue set identifier in response to receipt of the wildcard read request; and
generating the identifier of the non-empty target linked-list queue by retrieving linked-list queue states for linked-list queues belonging to the search target linked-list queue set.
6. The method of claim 5 , further comprising performing a read operation on the non-empty target linked-list queue.
7. An integrated circuit comprising a wildcard search controller for generating a queue-specific read request from a wildcard read request received over an agent-side interface of the wildcard search controller, the queue-specific read request comprising an identifier of a non-empty target queue selected from a segment comprising a plurality of queues, the wildcard search controller comprising:
a zoom-out search controller for generating a search target queue set identifier in response to receipt of the wildcard read request; and
a zoom-in search controller connected to the zoom-out search controller, for receiving the search target queue set identifier and generating the identifier of the non-empty target queue by retrieving queue states for queues belonging to the search target queue set.