Round robin scheduler using a scheduler carry operation for arbitration

• US 5,367,679 A
• Filed: 12/30/1992
• Issued: 11/22/1994
• Est. Priority Date: 12/30/1992
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Khaira, Manpreet S.
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): PAYNE, MATTHEW
• Application Number:
  US07/998,555
• Time in Patent Office: 692 Days
• Field of Search: 395/650, 395/325, 395/725, 364/DIG. 1, 364/DIG. 2
• US Class Current: 718/103
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines

Abstract

A scheduler for scheduling communication by a plurality of clients who compete to use a shared resource. Each client asserts a request bit to request use of the shared resource, and receives a grant bit from the scheduler that is asserted when the client is scheduled to use the shared resource. The scheduler includes a SC generation unit in which the request bits are inverted, the bit at the previous scheduling cycle grant is forced, and a scheduler carry operation is performed on the inverted request bits and grant bits to supply carry bits. The carry bits are "AND"ed with the forced, inverted request bits to supply a SC result and a carryout bit. The carryin bit is initially assumed to be zero, and the SC generation unit performs an initial operation. If the carryout bit from the final generation unit is zero, then the SC result bits for the initial operation provide the .grant word for the current scheduling cycle. However, if the carryout bit is one, the SC generation unit performs a second operation assuming a carryin bit of one to supply the grant word for the current scheduling cycle. To increase speed of operation, parallel branches may be provided so that the initial and the second operations can proceed in parallel and the correct grant word can be selected after the carryout bit is known. The second operation can be implemented with a hifind operation. Priority between clients can be implemented by allowing clients with priority to disable the scheduler.

Claims

1. A scheduler carry (SC) unit in a scheduler that performs a scheduling cycle to schedule use of a shared resource to one of a pinrail of clients in a predetermined order, each client supplying a request bit that is asserted to request use of the shared resource, each client also having an input for receiving a grant bit and circuitry responsive to an asserted grant bit for using the shared resource during a subsequent communication cycle, said SC unit comprising:

an inverter coupled to receive said request bits from said clients with said predetermined order and to output request bits having said predetermined order;

a scheduler carry (SC) generation unit coupled to receive said request bits and the grant bits previously selected for the current scheduling cycle, said SC generation unit for generating and outputting a plurality of carry bits having said predetermined order, said carry bits including an asserted bit at the position in said predetermined order corresponding to a client who will be granted use of said shared resource; and

a plurality of AND gates arranged in said predetermined order, said AND gates having inputs for receiving said carry bits and said request bits, each AND gate having an input for receiving a carry bit paired with a request bit at the same bit position in said predetermined order, each of said AND gates having an output coupled to provide the corresponding grant bit for each predetermined client.

2. A round robin scheduler for performing a scheduling cycle to grant use of a shared resource to one of a plurality of clients during a subsequent communication cycle, each client supplying a request bit that is asserted to request use of the shared resource, each client having an input for receiving a grant bit and circuitry responsive to an asserted grant bit for using the shared resource during the subsequent communication cycle, said request bits being combined in a predetermined order to define a request word and said grant bits being combined in said predetermined order to provide a grant word, said round robin schedular comprising:

a schedular carry (SC) branch including

an inverter coupled to receive said request word and to output a request word,

a scheduler carry (SC) generation unit coupled to receive said request word and the grant word previously selected for the current scheduling cycle, said SC generation unit for generating and outputting a carry word and a carryout bit, and

a plurality of AND gates, each gate having an input for receiving one bit of said carry word and an input for receiving the associated bit of the request word and an output defining an SC result bit, said plurality of AND gates providing an SC result word defined by said SC result bits arranged in said predetermined order, said SC result word having a single asserted SC result bit to indicate a next client to be granted use of said shared resource;

a hifind branch including a hifind unit for receiving said request word and generating and outputting a hifind result word that includes a bit asserted at a first asserted position in said request word, all other bits in said hifind result word being unasserted; and

a multiplexer coupled to select one of said SC result word and said hifind result word responsive to said carryout bit, said multiplexer selecting said SC result word if the carryout bit is "0"and otherwise selecting said hifind result word to supply an output defining said grant word for the subsequent communication cycle.

3. The round robin scheduler of claim 2 further comprising:

a request input latch coupled to said plurality of clients for receiving and latching said plurality of request bits for a scheduling cycle, said

request input latch defining a request word from said predetermined order of the plurality of request output bits; and

a grant output latch coupled to said plurality of clients for supplying a grant word whose bits are coupled in said predetermined order to the grant inputs of said clients.

4. The round robin scheduler of claim 2 further comprising a priority asserting means including a scheduler disabling circuit coupled to a first priority client, so that said first priority client can disable said scheduler.

5. A scheduler carry generation method implemented in a computer to generate a scheduler carry result word for use by a scheduler that schedules use of a communication resource shared by a plurality of clients each of which asserts a request bit when use of said shared resource is being requested, said request bits being arranged in a predetermined order to define a request word, each said client receiving a grant bit indicative of whether said client is scheduled to use said communication resource during a communication cycle, said grant bits being arranged in said predetermined order to define a grant word, said scheduler carry generation method comprising the steps of:

(a) inverting said request word to supply a request word;

(b) selecting a carryin bit to be "0";

(c) performing a scheduler carry (SC) operation on said request word and grant word for the most recently scheduled communication cycle, utilizing said carryin bit from the step (b), to supply a carry word and carry out bit;

(d) performing a bitwise AND operation on said carry word and said request word to supply a SC result word;

(e) if the resultant carryout bit from the SC operation in step (c) is "0", then applying the result of step (d) to be said grant word supplied to the clients, otherwise performing step (f); and

(f) if the resultant carryout bit from step (c) is "1", then selecting said carryin bit in the step (b) to be "1" and repeating steps (c) and (d) and then applying the result to be the grant word supplied to the clients.

6. The SC generation method of claim 5, wherein said step (c) includes

(c)(1) processing said request word of step (a) by asserting the bit position held by a client who was scheduled to use said shared resource in a previous scheduling cycle, to define a request word*;

and

(c)(2) performing a carry operation on said request word* and a previously scheduled grant word, so that a carry bit from any bit position becomes the carry bit for a next bit position.

7. The method of claim 5 further comprising the step of:

(g) if one of said clients has use of said shared resource and asserts a disable signal to said scheduler on a disable line, then regardless of the results of said steps (e) and (f), again supplying said most recently scheduled grant word to be the grant word supplied to said clients.

8. A scheduler carry generation method implemented in a computer to generate a scheduler carry result word for use by a scheduler that schedules use of a communication resource shared by a plurality of clients each of which asserts a request bit when use of said shared resource is being requested, said request bits being arranged in a predetermined order to define a request word, each said client receiving a grant bit indicative of whether said client is scheduled to use said communication resource during a communication cycle, said grant bits being arranged in said predetermined order to define a grant word, said scheduler carry generation method comprising the steps of:

(a) inverting said request word to supply a request word;

(b) selecting a carryin bit to be "0";

(c) performing a scheduler carry (SC) operation, on said request word and a grant word for the most recently scheduled communication cycle, utilizing said carryin bit from the step (b), to supply a carry word and a carry out bit;

(d) performing a bitwise AND operation on said carry word and said request word to supply a SC result word;

(e) when the carryin bit in the step (b) is "0", then the SC result word of step (d) defines a SC0 result word;

(f) performing the steps (b), (c), and (d), selecting the carryin bit in the step (b) to be "1" such that the SC result word of the step (d) defines a SC1 result word; and

(g) if the carryout bit from said SC operation in step (c) is "0", then selecting said SC0 result word to be the grant word supplied to said clients, otherwise selecting said SC1 result word to be said grant word supplied to said clients.

9. The scheduler carry SC generation method of claim 8, wherein said step (c) includes

(c)(1) processing said request word of step (a) by asserting the bit position held by a client who was scheduled to use said shared resource in a previous scheduling cycle, to define a request word*;

and

(c)(2) performing a carry operation on said request word* and a previously scheduled grant word, so that a carry bit from any bit position becomes the carry bit for a next bit position.

10. The method of claim 9 further comprising the step:

(h) if one of said clients has use of the shared resource and asserts a disable signal on a disable line, then regardless of the results of step (g), again supplying said most recently scheduled grant word to be the grant word supplied to the clients.

11. A round robin scheduling method implemented in a computer to schedule use of a communication resource shared by a plurality of clients each receiving a grant bit of a grant word that defines use of a shared communication resource, said scheduling method comprising the steps of:

(a) asserting a request bit for each said client who is requesting use of said shared resource, otherwise leaving said request bit unasserted;

(b) arranging said request bits from the plurality of said clients in said predetermined order to define a request word;

(c) performing a hifind operation on said request word to supply a hifind result word;

(d) performing an SC0 branch operation in parallel with the step (c), including

(d)(1) inverting said request word to supply a request word,

(d)(2) performing a scheduler carry (SC) operation, assuming a carryin of "0", on the request word and the grant word for a current communication cycle to supply a carry word and a carry out bit,

(d)(3) performing an AND operation on said carry word and said request word to supply a SC result word;

(e) if the carryout bit from said SC operation in step (d)(2) is "0", then selecting said hifind result word to be a grant word supplied to said clients for a subsequent communication cycle, otherwise selecting said SC result word to be said grant word; and

(f) supplying, to each said client, a predetermined bit of said grant word, said predetermined bit being indicative of whether said client is scheduled to use said communication resource for said subsequent communication cycle.

12. The method of claim 11 further comprising the step

(g) if one of said clients has use of said shared resource and asserts a disable signal to said scheduler on a disable line, then regardless of the results of said step if) again supplying said most recently scheduled grant word to be the grant word supplied to said clients in the step (f).

13. A scheduler carry (SC) operation for a scheduler implemented in a computer that grants use of a shared resource to one of N clients, said SC operation defining a SC word responsive to a carry word defined by a plurality of CBITs defined by bits CBIT₁ to CBIT_N, and defining a carryout bit by CBIT_N+1, said SC operation using a currently scheduled grant word defined by the bits GNTBIT₁ , . . . GNTBIT_N, and a request word defined by the bits REQBIT₁ , . . . , REQBIT_N, comprising the steps of:

(a) defining the CBIT₁ with a carryin bit;

(b) for CBIT₂ through CBIT_N+1, defining each CBIT_i from i=2 to i=N+1 by the following algorithm beginning with CBIT₂

(b)(1) set CBIT_i+1 equal to "1" if the GNTBIT_i equals "1";

(b)(2) if the GNTBIT_i does not equal "1", then set CBIT_i+1 equal to "1" if the CBIT_i equals "1" and the request bit i equals "1", otherwise, set CBIT_i+1 equal to "0".

14. A round robin scheduler for performing a scheduling cycle to grant use of a shared resource to one of a plurality of clients during a subsequent communication cycle, each client supplying a request bit that is asserted to request use of the shared resource, each client having an input for receiving a grant bit and circuitry responsive to an asserted grant bit for using the shared resource during the subsequent communication cycle, said request bits being combined in a predetermined order to define a request word and said grant bits being combined in said predetermined order to provide a grant word, said round robin scheduler comprising:

a scheduler carry (SC) branch coupled to receive said request word and the grant word previously selected for the current scheduling cycle, including circuitry responsive thereto for generating an SC result word defined by said SC result bits arranged in said predetermined order, said SC result word having a single asserted SC result bit to indicate a next client to be granted use of said shared resource;

a hifind branch including a hifind unit for receiving said request word and generating and outputting a hifind result word that includes a bit asserted at a first asserted position in said request word, all other bits in said hifind result word being unasserted; and

a multiplexer coupled to select one of said SC result word and said hifind result word responsive to said carryout bit, said multiplexer selecting said SC result word if the carryout bit is "0" and otherwise selecting said hifind result word to supply an output defining said grant word for the subsequent communication cycle.

15. The round robin scheduler of claim 14 further comprising:

a request input latch coupled to said plurality of clients for receiving and latching said plurality of request bits for a scheduling cycle, said request input latch defining a request word from said predetermined order of the plurality of request output bits; and

a grant output latch coupled to said plurality of clients for supplying a grant word whose bits are coupled in said predetermined order to the grant inputs of said clients.

16. The round robin scheduler of claim 14 further comprising a priority asserting means including a scheduler disabling circuit coupled to a first priority client, so that said first priority client can disable said scheduler.