Credit-based resource allocator circuit

摘要

A high-speed credit-based allocator circuit receives an allocation request to make an allocation to one of a set of a processing entities. The allocator circuit maintains a chain of bubble sorting module circuits for the set, where each bubble sorting module circuit stores a resource value and an indication of a corresponding processing entity. A bubble sorting operation is performed so that the head of the chain tends to indicate the processing entity of the set that has the highest amount of the resource (credit) available. The allocation requested is made to the processing entity indicated by the head module circuit of the chain. The amount of the resource available to each processing entity is tracked by adjusting the resource values as allocations are made, and as allocated tasks are completed. The allocator circuit is configurable to maintain multiple chains, thereby supporting credit-based allocations to multiple sets of processing entities.

主权项

1. A method comprising:
(a) operating an allocator circuit in a sequence of output determining phases and bubble sorting phases, wherein each output determining phase is followed by a bubble sorting phase, and wherein each bubble sorting phase is followed by an output determining phase; (b) maintaining, on the allocator circuit, 1) a resource value for each of a plurality of processing entities and 2) an indication of a processing entity for each of the resource values, wherein the allocator circuit comprises a bubble sorting module circuit comprised of combinatory logic and a state machine to form one or more chains, wherein each chain corresponds to a set of processing entities, wherein the resource value for a processing entity is indicative of an amount of a resource the processing entity has available, wherein the plurality of processing entities includes the set of processing entities; (c) receiving onto the allocator circuit an allocation request, wherein the allocation request is indicative of: 1) an amount of the resource requested, and 2) the set of processing entities; (d) in a first output determining phase, 1) determining, based at least in part on a bubble sort output, one processing entity from the set of processing entities, and 2) adjusting the resource value for the determined processing entity, wherein the resource value is adjusted in (d) by the amount of the resource indicated by the allocation request; (e) sending an allocation command from the allocator circuit to the processing entity determined in (d); (f) in a bubble sorting phase bubble sorting indications of processing entities of the set of processing entities based on the resource values of the processing entities and thereby determining a bubble sort output for the set of processing entities; (g) receiving onto the allocator circuit an allocation response, wherein the allocation response is indicative of: 1) the determined processing entity, and 2) the amount of the resource; and (h) in a second output determining phase, adjusting the resource value of the determined processing entity indicated by the allocation response, wherein the resource value is adjusted in (h) by the amount of the resource indicated by the allocation response, and wherein (b) through (h) are performed by the allocator circuit.