Method and system to allocate resources within an interconnect device according to a resource allocation table
View Patent ↗A method and apparatus to allocate resource capacity within an interconnect device in accordance with a resource allocation table (e.g., a priority list) facilitate identification of a resource consumer to be allocated a portion of the resource capacity in an efficient manner. The resource allocation table stores a number of allocation entries indicating an allocation of the resource capacity to a number of resource consumers (e.g., virtual lanes). A ranking vector corresponding to a first allocation entry within the allocation table is retrieved. A pending request vector, indicating for which of the plurality of resource consumers a resource request is pending, is generated. A selected resource consumer to consume at least a portion of the resource capacity is selected, the selection being performed utilizing the ranking vector and the pending request vector. The ranking vector is derived from the resource allocation table and comprises a list of resource consumers of the plurality of resource consumers, the list being ordered in accordance to an order of appearance of a first allocation entry for a respective resource consumer within the resource allocation table.
1. A method performed in an interconnect device to allocate resource capacity, the method including:
generating a resource allocation table including a plurality of allocation entries indicating an allocation of the resource capacity to a plurality of resource consumers comprising a plurality of data streams supported by the interconnect device, wherein the resource capacity comprises bandwidth on a physical link shared by the plurality of data streams supported by the interconnect device;
retrieving a ranking vector corresponding to a first allocation entry within the allocation table;
generating a pending request vector indicating for which of the plurality of resource consumers a resource request is pending; and
selecting a selected resource consumer to consume at least a portion of the resource capacity, the selection being performed combinatorially utilizing the ranking vector and the pending request vector,
wherein the ranking vector is derived from the resource allocation table and comprises a list of resource consumers of the plurality of resource consumers, the list being ordered in accordance with an order of appearance of a first allocation entry for a respective resource consumer within the resource allocation table.
2. The method of claim 1 wherein the order of appearance is determined in a first direction within the resource allocation table from the first allocation entry.
3. The method of claim 1 wherein the ranking vector is retrieved from a ranking table, the ranking table comprising a plurality of ranking vectors, each of which corresponds to an entry within the resource allocation table.
4. The method of claim 3 wherein the retrieval of the ranking vector includes utilizing a resource allocation table index pointer, identifying the first allocation entry within the resource allocation table, to retrieve the ranking vector from the ranking table.
5. The method of claim 1 wherein a second allocation entry within the resource allocation table records the allocation of none of the resource capacity to a second resource consumer, and wherein the second allocation entry is excluded from consideration as a first entry for the second resource consumer within the resource allocation table.
6. The method of claim 1 wherein the resource allocation table includes multiple allocation entries for a first resource consumer of the plurality of resource consumers.
7. The method of claim 1 wherein the selection of the selected resource consumer is performed utilizing combinational logic that selects a highest order resource consumer, within the ranking vector and for which a request is pending, as the selected resource consumer.
8. The method of claim 7 wherein the selection of the selected resource consumer performed utilizing the combinational logic is performed in one clock cycle.
9. The method of claim 1 wherein the generation of the pending request vector includes examining a respective request queue associated with each of the plurality of resource consumers to determine whether the respective request queue includes a resource request associated with the respective resource consumer.
10. The method of claim 1 including, subsequent to the selection of the selected resource consumer, updating a resource allocation table index pointer to point to a second allocation entry within the resource allocation table.
11. The method of claim 10 wherein the second allocation entry corresponds to the selected resource consumer if the resource capacity allocated to the selected resource consumer is not consumed by at least one resource request associated with the selected resource consumer.
12. The method of claim 11 wherein the second allocation entry corresponds to a further resource consumer, downstream of the selected resource consumer within the resource allocation table, if the resource capacity allocated to the selected resource consumer is consumed by at least one resource request associated with the selected resource consumer.
13. The method of claim 10 wherein the updating of the resource allocation table index pointer includes retrieving a first resource allocation table bit vector associated with the selected resource consumer, the first resource allocation table bit vector including a bit entry corresponding to each allocation entry within the resource allocation table, at least one of the bit entries being set to flag at least one allocation entry for the selected resource consumer within the resource allocation table.
14. A system in an interconnect device, the system configured to allocate resource capacity within the interconnect device, the system including:
a memory to store a resource allocation table and a ranking table, and to output a ranking vector, from the ranking table, corresponding to a first allocation entry within the allocation table, the resource allocation table including a plurality of allocation entries indicating an allocation of the resource capacity to a plurality of the resource consumers comprising a plurality of data streams supported by the interconnect device, wherein the resource capacity comprises bandwidth on a physical link shared by the plurality of data streams supported by the interconnect device;
a resource allocator to generate a pending request vector indicating for which of the plurality of resource consumers a resource request is pending; and
a selector having combinational logic to select a selected resource consumer to consume at least a portion of the resource capacity, the selection being performed by the selector combinatorially utilizing the ranking vector and the pending request vector,
wherein the ranking vector is derived from the resource allocation table and comprises a list of resource consumers of the plurality of resource consumers, the list being ordered in accordance with an order of appearance of a first allocation entry for a respective resource consumer within the resource allocation table.
15. The system of claim 14 wherein the order of appearance is determined in a first direction within the resource allocation table from the first allocation entry.
16. The system of claim 14 wherein the ranking table comprises a plurality of ranking vectors, each of which corresponds to an entry within the resource allocation table.
17. The system of claim 16 wherein the memory maintains a resource allocation table index pointer, and wherein the ranking vector is outputted from the memory utilizing the resource allocation table index pointer, the resource allocation table index pointer identifying the first allocation entry within the resource allocation table.
18. The system of claim 14 wherein a second allocation entry within the resource allocation table records the allocation of none of the resource capacity to a second resource consumer, and wherein the second allocation entry is excluded from consideration as a first entry for the second resource consumer within the resource allocation table.
19. The system of claim 14 wherein the resource allocation table includes multiple allocation entries for a first resource consumer of the plurality of resource consumers.
20. The system of claim 14 wherein the combinational logic enables the selector to select a highest order resource consumer, within the ranking vector and for which a request is pending, as the selected resource consumer.
21. The system of claim 20 wherein the selector operates to select the selected resource consumer within one clock cycle.
22. The system of claim 14 wherein the resource allocator is to examine a respective request queue associated with each of the plurality of resource consumers to determine whether the respective request queue includes a resource request associated with the respective resource consumer.
23. The system of claim 14 including a further selector, subsequent to the selection of the selected resource consumer, to update a resource allocation table index pointer to point to a second allocation entry within the resource allocation table.
24. The system of claim 23 wherein the second allocation entry corresponds to the selected resource consumer if the resource capacity allocated to the selected resource consumer is not consumed by at least one resource request associated with the selected resource consumer.
25. The system of claim 24 wherein the second allocation entry corresponds to a further resource consumer, downstream of the selected resource consumer within the resource allocation table, if the resource capacity allocated to the selected resource consumer is consumed by at least one resource request associated with the selected resource consumer.
26. The system of claim 23 wherein the updating of the resource allocation table index pointer by the further selector includes retrieving a first resource allocation table bit vector associated with the selected resource consumer, the first resource allocation table bit vector including a bit entry corresponding to each allocation entry within the resource allocation table, at least one of the bit entries being set to flag at least one allocation entry for the selected resource consumer within the resource allocation table.
27. A machine-readable storage medium storing instructions executed by a computer, said machine readable storage medium comprising:
instructions for allowing a memory to store a resource allocation table and a ranking table, and to output a ranking vector, from the ranking table, corresponding to a first allocation entry within the allocation table, the resource allocation table including a plurality of allocation entries indicating an allocation of the resource capacity to a plurality of the resource consumers comprising a plurality of data streams wherein the resource capacity comprises bandwidth on a physical link shared by the plurality of data streams;
instructions for allowing a resource allocator to generate a pending request vector indicating for which of the plurality of resource consumers a resource request is pending; and
instructions for allowing a selector having combinational logic to select a selected resource consumer to consume at least a portion of the resource capacity, the selection being performed by the selector combinatorially utilizing the ranking vector and the pending request vector,
wherein the ranking vector is derived from the resource allocation table and comprises a list of resource consumers of the plurality of resource consumers, the list being ordered in accordance with an order of appearance of a first allocation entry for a respective resource consumer within the resource allocation table.
28. The machine-readable storage medium of claim 27 wherein the description comprises a behavioral level description of the circuit.
29. The machine-readable storage medium of claim 28 wherein the behavioral level description is compatible with a Very high speed integrated circuit Hardware Description Language (VHDL) format.
30. The machine-readable storage medium of claim 28 wherein the behavioral level description is compatible with a Verilog format.
31. A system in an interconnect device, the system configured to allocate resource capacity within the interconnect device in accordance with a resource allocation table, the resource allocation table including a plurality of allocation entries indicating an allocation of the resource capacity to a plurality of resource consumers comprising a plurality of data streams supported by the interconnect device, wherein the resource capacity comprises bandwidth on a physical link shared by a plurality of data streams supported by the interconnect device, the system comprising:
first means for storing the resource allocation table and a ranking table, and for outputting a ranking vector, from the ranking table, corresponding to a first allocation entry within the allocation table;
second means for generating a pending request vector indicating for which of the plurality of resource consumers a resource request is pending; and
third means having combinational logic for selecting a selected resource consumer to consume at least a portion of the resource capacity, the selection being performed by the third means combinatorially utilizing the ranking vector and the pending request vector,
wherein the ranking vector is derived from the resource allocation table and comprises a list of resource consumers of the plurality of resource consumers, the list being ordered in accordance with an order of appearance of a first allocation entry for a respective resource consumer within the resource allocation table.