Fast first-come first served arbitration method

• US 5,574,867 A
• Filed: 07/08/1994
• Issued: 11/12/1996
• Est. Priority Date: 07/08/1994
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Khaira, Manpreet S.
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): Travis, John
• Application Number:
  US08/273,027
• Time in Patent Office: 858 Days
• Field of Search: 395/725, 395/325, 395/293, 395/287, 395/303, 395/732
• US Class Current: 710/113
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A first-come-first-serve ("FCFS") scheduler that routes requests from two or more clients to a single resource. The FCFS scheduler contains a time stamp mechanism which provides a time stamp for each request. The scheduler provides resource access to the client with the oldest generated request and under a predetermined priority scheme in the event of simultaneous requests. The time stamps are generated by adders which add the current value of a time stamp counter with the number of client requests. The time stamp counter is incremented by the output of the adders. The updated value of the counter is decoded into a time stamp output value stored within time stamp registers. A hifind circuit reads the registers and generates an output signal associated with the set of registers, and corresponding client request, with the lowest time stamp. The output signal allows the client to access the resource.

Claims

1. A first come first serve scheduler mechanism for a plurality of clients that generate access request for a resource, comprising:

a signal conversion circuit which converts a plurality of requests into a plurality of associated time stamp input signals;

a time stamp generation circuit which receives said time stamp input signals and generates coded time stamp output values that correspond to an order of receipt of said time stamp input signals, said time stamp generation circuit includes a time stamp counter which counts each time stamp input signal when said time stamp input signal is generated by said signal conversion Circuit and decrements one unit after a client has released the resource;

a plurality of time stamp registers that receive and store said coded time stamp output values; and

,

a hifind circuit that reads said plurality of time stamp registers and generates an output signal in accordance with a predetermined hierarchy and which allows a client access to the resource.

2. The mechanism as recited in claim 1, wherein the requests are received by said signal conversion circuit at a first time and a second time which is later than said first time, wherein said hierarchy includes generating said output signal that corresponds to said request at said first time and then generates a subsequent output signal that corresponds to said request at said second time.

3. The mechanism as recited in claim 1, wherein said time stamp generation circuit includes a first adder that adds said time stamp input signals and generates a first adder output value, and a second adder that adds said first adder output value to a first time stamp counter value and generates a second adder output value which increments said time stamp counter to a second time stamp counter value.

5. The mechanism as recited in claim 3, wherein said signal conversion circuit includes a request latch that latches said request and generates a plurality of time stamp input signals that are provided to said first adder and said plurality of time stamp registers, and a mask circuit that can mask said time stamp input signals.

6. The mechanism as recited in claim 1, wherein said hifind circuit reads a least significant bit of each of said plurality of time stamp registers.

4. The mechanism as recited in claim 4, wherein said time stamp generation circuit includes a decoder which converts said second time stamp counter value to said time stamp output value.

7. A computer system with a first come first serve mechanism, the computer system comprising:

a resource;

a plurality of clients including

a first client that generates a first request for access to said resource, and

a second client that generates a second request for access to said resource; and

a scheduler mechanism coupled to said resource and said plurality of clients, said scheduler includes

a signal conversion circuit which converts said requests into a plurality of associated time stamp input signals,

a time stamp generation circuit which receives said time stamp input signals and generates coded time stamp output values that correspond to an order of receipt of said time stamp input signals, said time stamp generation circuit includes a time stamp counter which counts each time stamp input signal when said time stamp input signal is generated by said signal conversion circuit and decrements one unit after a client has released the resource,

a plurality of time stamp registers that receive and store said coded time stamp output values, and,

a hifind circuit that reads said plurality of time stamp registers and generates an output signal in accordance with a predetermined hierarchy, said output signal being provided to a client to allow access to said resource.

8. The system as recited in claim 7, wherein said first request is received by said signal conversion circuit at a first time and said second request is received at a second time which is later than said first time, wherein said hierarchy includes generating said output signal that corresponds to said request at said first time and then generates a subsequent output signal that corresponds to said request at said second time.

9. The system as recited in claim 7, wherein said time stamp generation circuit of said scheduler mechanism includes a first adder that adds said time stamp input signals and generates a first adder output value, and a second adder that adds said first adder output value to a first time stamp counter value and generates a second adder output value which increments said time stamp counter to a second time stamp counter value.

10. The system as recited in claim 9, wherein said time stamp generation circuit of said scheduler mechanism includes a decoder which converts said second time stamp counter value to said time stamp output value.

11. The system as recited in claim 9, wherein said signal conversion circuit of said scheduler mechanism includes a request latch that latches said request and generates a plurality of time stamp input signals that are provided to said first adder and said plurality of time stamp registers, and a mask circuit that can mask said time stamp input signals.

12. The system as recited in claim 7, wherein said hifind circuit of said scheduler mechanism reads a least significant bit of each of said time stamp registers.

13. A first come first serve scheduler mechanism for a plurality of clients that generate access request for a resource, comprising:

signal conversion circuit means for converting the requests into a plurality of associated time stamp input signals;

time stamp generation circuit means for receiving said time stamp input signals and for generating coded time stamp output values that correspond to an order of receipt of said time stamp input signals, said time stamp generation circuit means includes a time stamp counter means for counting each time stamp input signal when said time stamp input signal is generated by said signal conversion circuit means and decrements one unit after a client has released a resource;

time stamp register means for receiving and storing said coded time stamp output values; and

,

hifind circuit means for reading said time stamp registers and for generating an output signal in accordance with a predetermined hierarchy and which allows a client access to the resource.

14. The mechanism as recited in claim 13, wherein said requests are received by said signal conversion circuit means at a first time and a second time which is later than said first time, wherein said hierarchy includes generating said output signal that corresponds to said request at said first time and then generates a subsequent output signal that corresponds to said request at said second time.

15. The mechanism as recited in claim 13, wherein said time stamp generation circuit means includes first adder means for adding said time stamp input signals and generating a first adder output value, and second adder means for adding said first adder output value to a first time stamp counter value and generating a second adder output value which increments said time stamp counter means to a second time stamp counter value.

16. The mechanism as recited in claim 15, wherein said time stamp generation circuit means includes decoder means for converting said second time stamp counter value to said time stamp output value.

17. The mechanism as recited in claim 15, wherein said signal conversion circuit means includes request latch means for latching said requests and generating a plurality of time stamp input signals that are provided to said first adder means and said time stamp register means, and masking means for masking said time stamp input signals.

18. The mechanism as recited in claim 13, wherein said hifind circuit means reads a least significant bit of each of said time stamp registers means.

19. A computer system with first come first serve mechanism, comprising:

a resource;

a plurality of clients including

a first client that generates a first request for access to said resource, and

a second client that generates a second request for access to said resource; and

scheduler means for enabling at least one of said plurality of clients access to said resource, said scheduler means includes

signal conversion circuit means for converting said requests into a plurality of associated time stamp input signals,

time stamp generation circuit means for receiving said time stamp input signals and for generating coded time stamp output values that correspond to an order of receipt of said time stamp input signals, said time stamp generation circuit means includes a time stamp counter means for counting each time stamp input signal when said time stamp input signal is generated by said signal conversion circuit means and decrements one unit after a client has released the resource,

time stamp register means for receiving and storing said coded time stamp output values, and,

hifind circuit means for reading said time stamp register means and for generating an output signal that in accordance with a predetermined hierarchy, said output signal being provided to a client to allow access to said resource.

20. The system as recited in claim 19, wherein said requests are received by said signal conversion circuit means at a first time and a second time which is later than said first time, wherein said hierarchy includes generating said output signal that corresponds to said request at said first time and then generates a subsequent output signal that corresponds to said request at said second time.

21. The system as recited in claim 19, wherein said time stamp generation circuit means includes first adder means for adding said time stamp input signals and generating a first adder output value, and second adder means for adding said first adder output value to a first time stamp counter value and generating a second adder output value which increments said time stamp counter means to a second time stamp counter value.

22. The system as recited in claim 21, wherein said time stamp generation circuit means includes decoder means for converting said second time stamp counter value to said time stamp output value.

23. The system as recited in claim 21, wherein said signal conversion circuit means includes request latch means for latching said requests and generating a plurality time stamp input signals that are provided to said first adder means and said time stamp register means, and masking means for masking said time stamp input signals.

24. The system as recited in claim 19, wherein said hifind circuit means reads a least significant bit of each of said time stamp register means.