Scaleable hardware arbiter

Details Scaleable hardware arbiter Scaleable hardware arbiter

2000-06-09

2004-12-07

Wiley, David (Department: 2143)

Electrical computers and digital processing systems: multicomput

Computer-to-computer session/connection establishing

Network resources access controlling

C370S412000, C370S416000

Reexamination Certificate

active

06829647

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to decision-making logic devices in a computing system, and specifically to arbitration devices which arbitrate between clients within the system.
BACKGROUND OF THE INVENTION
An arbiter is a computing device which is used to select one from a plurality of clients requesting access to a specific computing resource. The arbiter receives a plurality of requests from the clients, and chooses one of the requests to have access to the resource. The client whose request is chosen to have access is herein termed the arbitration-winning client. Arbiters known in the art implement a variety of different arbitration schemes, including priority schemes wherein different clients are assigned different fixed priorities.
For example, in one common type of arbitration system, incoming requests are logged in registers. Each client is assigned a register in the arbiter, so that a specific register holds pending requests for that client. Combinatorial logic is used to define the next request to be served at any time, using priority schemes as are known in the art. The logic acts as a bottleneck for the arbiter, and the size of the logic grows in proportion to the square of the number of clients.
Another type of arbitration system simply uses a first-in first-out (FIFO) memory device. Each new request is stored at the tail of the device, and the request at the head of the FIFO receives the service. This system is limited by the size of the FIFO, which depends on the number of requests, rather than the number of clients. Depending on the arbitration system, the number of requests can be orders of magnitude larger than the number of clients.
Other arbitration schemes include round-robin and time-sharing schemes. Hardware arbiters known in the art typically require combinatorial logic paths whose length, and thus the size of the logic, is directly proportional to the square of the number of clients utilizing the resource. As the size of the logic increases, the time for arbitration also increases. Depending on the application, arbiters in a computing system may receive requests from thousands of clients, necessitating arbiters having large logic sizes.
SUMMARY OF THE INVENTION
It is an object of some aspects of the present invention to provide an arbiter which utilizes reduced logic size and which is able to arbitrate efficiently between large numbers of clients.
It is a further object of some aspects of the present invention to provide an arbiter comprising logic circuitry whose size is substantially independent of the number of clients using the arbiter.
It is another object of some aspects of the present invention to provide an arbiter wherein the time taken to perform an arbitration is substantially independent of the number of clients using the arbiter.
It is yet a further object of some aspects of the present invention to provide an arbiter utilizing a memory whose size scales as substantially less than the square of the number of clients.
In preferred embodiments of the present invention, a hardware-based arbiter which arbitrates between a plurality of clients in a computing environment is implemented as a linked-list device. The plurality of clients are resident in a memory of the computing environment, and produce multiple requests for use of a specific resource of the environment. As the plurality of clients produce requests for the resource, the requests are directed to the arbiter. For each client requesting use of the resource, the arbiter updates a number-of-requests value and a next-client-to-use-the-resource pointer, hereinafter termed a next-client pointer, and enters these updated parameters into a table comprised in the arbiter. The next-client pointers link their respective clients in a uni-directional list. At times when the resource is available, the arbiter utilizes the list to arbitrate between the plurality of clients and so generate an arbitration-winning client, which client is given access by the arbiter to the resource.
The arbiter manages the table by arbiter-specific logic circuitry incorporated into the arbiter, the size of which logic is relatively small and is independent both of the number of clients and of the number of requests. The size of the arbiter is thus roughly equal to the size of the table generated by the arbiter. The size of the table is directly proportional to the number of clients requesting use of the resource, herein termed N, and to the size of the entries of the table. The size of the entries is of the order of log
2
(N), so that the total size of the arbiter is of the order of N·log
2
(N). Thus the size of the arbiter, especially for large values of N, is significantly smaller than arbiters known in the art which use combinatorial logic. Furthermore, since the timing of arbitration performed by the arbiter is a function of the size of the logic circuitry, the timing is substantially independent of the number of clients and the number of requests from the clients. While linked lists have been used in software-based arbitration, the present invention is the first practical implementation of a linked-list structure in hardware. It thus provides a substantially faster and more economical solution to the problem of arbitration among large numbers of clients than has heretofore been known in the art.
In some preferred embodiments of the present invention, one or more input devices are added to the arbiter in order to separate requests which would otherwise arrive substantially simultaneously at the arbiter.
In some preferred embodiments of the present invention, requests from different clients may be assigned to more than one priority level. Additional sets of pointers, according to the number of priority levels, are incorporated in the arbiter. The additional sets of pointers enable the arbiter to arbitrate between the different priority requests.
There is therefore provided, according to a preferred embodiment of the present invention, an arbiter which arbitrates between a plurality of clients generating requests for access to a resource in a computing environment, including:
a memory, including for each of the plurality of clients:
a request register, which is adapted to record the respective client's access requests; and
a next-client pointer, which is adapted to record an identification of another one of the clients making a subsequent request to access the resource, so as to form a linked list of the requests; and
logic circuitry which is adapted to decide, responsive to the linked list, which of the plurality of clients is given access to the resource.
Preferably, the memory includes at least one list-terminating pointer which indicates an end of the linked list.
Preferably, the at least one list-terminating pointer includes a tail pointer which indicates a last client in the linked list.
Preferably, the at least one list-terminating pointer includes a head pointer which indicates a first client in the linked list, and the logic circuitry is operative to decide, responsive to the head pointer, which of the plurality of clients is given access to the resource.
Preferably, the logic circuitry is operative to check whether a client requesting access to the resource has a pending access request, and to update a record of the number of pending access requests recorded in the respective register responsive to the check.
Preferably, the logic circuitry is operative to check whether the resource is available, and to allocate the resource responsive to the check.
Preferably, the arbiter includes at least one buffer wherein requests from a specific client are stored before being recorded in the respective request register.
Further preferably, the arbiter includes a first-in first-out memory wherein requests from the plurality of clients are stored before being transferred sequentially to the memory and the logic circuitry.
Preferably, the memory includes:
for at least some of the clients, a priority flag which is adapted to record a priority for access to the resource for the at least

Affiliated with

Also associated with

Rating

Scaleable hardware arbiter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scaleable hardware arbiter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaleable hardware arbiter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3338074