Processor with dynamic table-based scheduling using multi-entry table locations for handling transmission request collisions
View Patent ↗A processor includes scheduling circuitry for scheduling data blocks for transmission from a plurality of transmission elements. The scheduling circuitry has at least one time slot table accessible thereto, and is configured for utilization of the time slot table in scheduling the data blocks for transmission. The time slot table includes a plurality of locations, with each of the locations corresponding to a transmission time slot and being configurable for storing identifiers of at least two of the transmission elements. In an illustrative embodiment, a given one of the locations in the time slot table stores in a first portion thereof an identifier of a first one of the transmission elements that has requested transmission of a block of data in the corresponding time slot, and stores in a second portion thereof an identifier of a second one of the transmission elements that has requested transmission of a block of data in the corresponding time slot. Furthermore, additional transmission elements generating colliding requests for the given location can be linked between the first and second transmission elements using a linking mechanism. The use of multi-entry time slot table locations to accommodate collisions between transmission element requests considerably facilitates the maintenance of desired traffic shaping requirements.
1. A processor comprising:
scheduling circuitry for scheduling data blocks for transmission from a plurality of transmission elements;
the scheduling circuitry having at least one time slot table accessible thereto;
wherein the scheduling circuitry is configured for utilization of the at least one time slot table in scheduling the data blocks for transmission, the time slot table comprising a plurality of locations, a given one of the locations corresponding to a transmission time slot and being configurable for storing identifiers of at least two of the transmission elements that have generated colliding requests to transmit respective data blocks in the corresponding time slot; and
wherein less than all of said at least two transmission elements that have their respective identifiers stored in the given location and have generated the colliding requests are permitted to transmit a data block in the corresponding time slot.
2. The processor of claim 1 wherein the time slot table is stored at least in part in an internal memory of the processor.
3. The processor of claim 1 wherein the time slot table is stored at least in part in an external memory coupled to the processor.
4. The processor of claim 1 wherein a given one of the locations in the time slot table stores in a first portion thereof an identifier of a first one of the transmission elements that has requested transmission of a block of data in the corresponding time slot and stores in a second portion thereof an identifier of a second one of the transmission elements that has requested transmission of a block of data in the corresponding time slot.
5. The processor of claim 1 wherein one or more of the data blocks comprise data packets.
6. The processor of claim 1
wherein the scheduling circuitry provides dynamic maintenance of the time slot table such that identifiers of requesting transmission elements are entered into the table locations on a demand basis.
7. The processor of claim 1
wherein the identifiers of the transmission elements comprise a structure for allowing a given one of the transmission element identifiers to be linked to another of the transmission element identifiers.
8. A processor comprising:
scheduling circuitry for scheduling data blocks for transmission from a plurality of transmission elements;
the scheduling circuitry having at least one time slot table accessible thereto;
wherein the scheduling circuitry is configured for utilization of the at least one time slot table in scheduling the data blocks for transmission, the time slot table comprising a plurality of locations, each of the locations corresponding to a transmission time slot and being configurable for storing identifiers of at least two of the transmission elements;
wherein the identifiers of the transmission elements comprise a structure for allowing a given one of the transmission element identifiers to be linked to another of the transmission element identifiers; and
wherein in the event of a collision between multiple transmission elements requesting a given one of the time slots, an identifier of a first one of the requesting transmission elements is entered into a first portion of the corresponding location in the time slot table, an identifier of a final one of the requesting elements is entered into a second portion of the corresponding location in the time slot table, and an identifier of an additional one of the requesting elements is linked to at least one of the identifier of the first requesting element and the identifier of the second requesting element, a linked list of the multiple requesting elements thereby being created for the corresponding location in the time slot table.
9. The processor of claim 8 wherein upon transmission of a data block from one of the requesting transmission elements in the linked list of elements, a determination is made as to whether there are any further elements linked to that element, and for a given such further element the transmission of a data block therefrom is scheduled.
10. The processor of claim 1
wherein the scheduling circuitry maintains a set of pointers for the time slot table, the set of pointers comprising one or more of:
an actual pointer pointing to a location in the time slot table corresponding to actual time;
a head pointer pointing to a first element of a linked list of multiple requesting transmission elements associated with a given time slot; and
a tail pointer pointing to a final element of the linked list of multiple requesting transmission elements associated with the given time slot.
11. The processor of claim 10 wherein the actual pointer advances by one table location for each of the data blocks transmitted.
12. A processor comprising:
scheduling circuitry for scheduling data blocks for transmission from a plurality of transmission elements;
the scheduling circuitry having at least one time slot table accessible thereto;
wherein the scheduling circuitry is configured for utilization of the at least one time slot table in scheduling the data blocks for transmission, the time slot table comprising a plurality of locations, each of the locations corresponding to a transmission time slot and being configurable for storing identifiers of at least two of the transmission elements;
wherein the scheduling circuitry maintains a set of pointers for the time slot table, the set of pointers comprising one or more of:
an actual pointer pointing to a location in the time slot table corresponding to actual time;
a head pointer pointing to a first element of a linked list of multiple requesting transmission elements associated with a given time slot; and
a tail pointer pointing to a final element of the linked list of multiple requesting transmission elements associated with the given time slot; and
wherein the head pointer and tail pointer collectively define a dynamic waiting room for at least a subset of the multiple requesting transmission elements associated with the given time slot.
13. A processor comprising:
scheduling circuitry for scheduling data blocks for transmission from a plurality of transmission elements;
the scheduling circuitry having at least one time slot table accessible thereto; and
wherein the scheduling circuitry is configured for utilization of the at least one time slot table in scheduling the data blocks for transmission, the time slot table comprising a plurality of locations, each of the locations corresponding to a transmission time slot and being configurable for storing identifiers of at least two of the transmission elements; and
wherein the scheduling circuitry maintains a set of pointers for the time slot table, the set of pointers comprising one or more of:
an actual pointer pointing to a location in the time slot table corresponding to actual time;
a head pointer pointing to a first element of a linked list of multiple requesting transmission elements associated with a given time slot; and
a tail pointer pointing to a final element of the linked list of multiple requesting transmission elements associated with the given time slot;
wherein the processor further comprises a counter which specifies a number of times a set of one or more of the multiple requesting transmission elements are placed in one or more linked lists of such elements associated with one or more of the time slots.
14. The processor of claim 13 wherein a given requesting transmission element is assigned to a location in the time slot table in accordance with the following equation:
Assigned Time Slot=AP−Waiting Room Depth+Requested Time Slot Interval,
where AP denotes the actual pointer, the waiting room depth is the value of the counter, and the requested time slot interval is the time slot interval requested by the requesting transmission element.
15. The processor of claim 1 further comprising a transmit queue having traffic shaping circuitry coupled thereto, the transmit queue being coupled to the scheduling circuitry and supplying time slot requests from transmission elements to the scheduling circuitry in accordance with a traffic shaping requirement established by the traffic shaping circuitry.
16. The processor of claim 1 wherein the processor comprises the at least one time slot table.
17. The processor of claim 1 wherein the processor comprises a network processor configured to provide an interface for data block transfer between a network and a switch fabric.
18. The processor of claim 1 wherein the processor is configured as an integrated circuit.
19. A method for use in a processor, the method comprising:
scheduling data blocks for transmission from a plurality of transmission elements;
wherein the scheduling step utilizes at least one time slot table to schedule the data blocks for transmission, the time slot table comprising a plurality of locations, a given one of the locations corresponding to a transmission time slot and being configurable for storing identifiers of at least two of the transmission elements that have generated colliding requests to transmit respective data blocks in the corresponding time slot; and
wherein less than all of said at least two transmission elements that have their respective identifiers stored in the given location and have generated the colliding requests are permitted to transmit a data block in the corresponding time slot.
20. An article of manufacture comprising a computer-readable storage medium for use in conjunction with a processor, the medium storing one or more software programs for use in scheduling data blocks for transmission from a plurality of transmission elements, utilizing at least one time slot table, the time slot table comprising a plurality of locations, a given one of the locations corresponding to a transmission time slot and being configurable for storing identifiers of at least two of the transmission elements that have generated colliding requests to transmit respective data blocks in the corresponding time slot;
wherein less than all of said at least two transmission elements that have their respective identifiers stored in the given location and have generated the colliding requests are permitted to transmit a data block in the corresponding time slot; and
wherein the one or more programs when executed implement the step of scheduling the data blocks for transmission from the plurality of transmission elements.