Priority logic for selecting and stacking data

• US 5,970,253 A
• Filed: 01/09/1997
• Issued: 10/19/1999
• Est. Priority Date: 01/09/1997
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Purdham, David M.
• Primary Examiner(s): Auve, Glenn A.
• Assistant Examiner(s): JEAN, FRANTZ B
• Application Number:
  US08/780,966
• Time in Patent Office: 1,013 Days
• Field of Search: 395/729, 395/728, 395/472, 395/732, 370/85.1, 370/94.1
• US Class Current: 710/244
• CPC Class Codes: G06F 13/36 for access to common bus or bus system

Abstract

A method and apparatus for setting a priority sequence among a plurality of requesters using a common destination within a computer system. An advantage is that all requesters contending for the common destination will have timely access with respect to all other competing requesters. In a first exemplary embodiment of the present invention, a priority controller can use a two-level priority scheme to select the next requester. The first level of priority alternates between an external requester and an on-card requester where every other set of data is from the external requester. The second level of priority alternates between on-card modules during an on-card priority cycle. In an alternative exemplary embodiment, the priority controller can stack a request to transfer acknowledge and data information from an external requester if it is busy. The priority controller also prevents sending an acknowledgment/data cycle out to an external source to prevent sending more data than the FIFO stacks can accommodate. The data may also consist only of acknowledgements.

Claims

1. In a computer apparatus having a shared resource and a plurality of requesters wherein the plurality of requesters are divided into a plurality of requester categories including a first requester category having one or more requestors and a second requestor category having one or more requesters, and wherein the plurality of requesters share the use of the shared resource and wherein each of said one or more requesters of said second requester category is physically located on a card external to and more remote from said shared resource than each of said one or more requesters of said first requester category whereby the circuit time delay attendant to a first desired request of said shared resource by each of said one or more requesters of said second requester category is greater than the corresponding circuit time delay attendant to a second desired request of said shared resource by each of said one or more requesters of said first requester category, wherein the improvement comprises:

priority controller means coupled to the plurality of requesters for selecting one of the plurality of requesters from the plurality of requesters desiring access to the shared resource according to a priority determination protocol which assigns a first pre-determined priority to requesters from the first requester category which is different than a second pre-determined priority assigned to the second requester category and wherein the difference between said first pre-determined priority and said second pre-determined priority compensates for the difference between said circuit time delay and said corresponding circuit time delay.

2. An improvement according to claim 1, wherein said priority controller means utilizes said priority determination protocol to alternatively grant pre-determined priorities to one of the one or more requesters in said first requester category and to one of the one or more requesters in said second requester category.

3. An improvement according to claim 2, wherein said priority controller means comprises a send acknowledge means coupled to the plurality of requesters for receiving a plurality of send acknowledgement signals from the plurality of requesters, wherein each of the plurality of send acknowledgement signals is asserted when a requester desires access to the shared resource;

wherein one of said plurality of send acknowledgement signals corresponds to one of the plurality of requesters selected from said plurality of requesters desiring access to said shared resource.

4. An improvement according to claim 3, wherein said send acknowledgement means coupled to the one or more requesters in the second requester category comprises a send acknowledgement storage means for storing one or more send acknowledgement requests from the one or more requesters in the second requester category if one of the plurality of send acknowledgement signals corresponding to one of the plurality of requesters selected from the plurality of requesters desiring access is currently being output to said shared resource.

5. An improvement according to claim 4, wherein said priority controller means comprises a data means coupled to the plurality of requesters for receiving a plurality of data signals from the plurality of requesters;

wherein one of the plurality of data signals corresponding to one of the plurality of requesters selected from the plurality of requesters desiring access is currently being output to said shared resource.

6. An improvement according to claim 5, wherein said data means coupled to the one or more requesters in the second requester category comprises a data storage means for storing one or more data from the one or more requesters in the second requester category if one of the plurality of data lines corresponding to one of the plurality of requesters selected from the plurality of requesters desiring access is currently being output to said shared resource.

7. An improvement according to claim 6, wherein said priority controller means comprises a read acknowledgement output means coupled to the one or more requesters in the second requester category for indicating to the one or more requesters in the second requester category that another one or more send acknowledgement requests and another one or more data can be sent.

8. An improvement according to claim 7, wherein said read acknowledgement output means indicates to the one or more requesters in the second requester category that a predetermined one or more send acknowledgement requests and predetermined one or more data can be sent.

9. An improvement according to claim 8, wherein said predetermined one or more send acknowledgement requests and said predetermined one or more data is determined from a data storage capacity of said data storage means and from a send acknowledgement request storage capacity of said send acknowledgement storage means.

10. An improvement according to claim 7, wherein said priority controller means comprises a read acknowledgement input means coupled to said shared resource for indicating that one of said plurality of send acknowledgement signals and that one of said plurality of data lines corresponding to one of the plurality of requesters selected from the plurality of requesters desiring access can be output to said shared resource.

11. An improvement according to claim 10, wherein the second requester category is comprised of a single requester.

12. An improvement according to claim 11, wherein priority is granted in a predetermined order to each particular one of the plurality of requesters in the first requester category.

13. An improvement according to claim 12, wherein said send acknowledgement storage means comprises a First-In-First-Out memory.

14. An improvement according to claim 13, wherein said data storage means comprises a First-In-First-Out memory.

15. An apparatus having a shared resource comprising:

a. a plurality of requesters wherein the plurality of requesters are divided into a plurality of requester categories, including a first requester category having one or more requesters and a second requestor category having one or more requestors, and share the use of the shared resource wherein each of said one or more requestors of said second requestor category is physically located on a card external to and more remote from said shared resource than each of said one or more requestors of said first requestor category whereby the circuit time delay attendant to a first desired request of said shared resource by each of said one or more requesters of said second requester category is greater than the corresponding circuit time delay attendant to a second desired request of said shared resource by each of said one or more requesters of said first requester category; and

b. priority controller means coupled to said plurality of requesters for selecting one of the plurality of requesters from a plurality of requesters desiring access to the shared resource according to a priority determination protocol which assigns a first pre-determined priority to requesters from the first requestor category which is different than the second pre-determined priority assigned to the second requestor category wherein the difference between said first pre-determined priority and said second pre-determined priority compensates for the difference between said circuit time delay and said corresponding circuit time delay.

16. An apparatus according to claim 15, wherein said priority controller means utilize said priority determination protocol to alternatively grant predetermined priorities to one of said one or more requesters in said first requester category and to one of said one or more requesters in said second requester category.

17. An apparatus according to claim 16, wherein said priority controller means comprises a send acknowledge means coupled to said plurality of requesters for receiving a plurality of send acknowledgement signals from said plurality of requesters;

each of said plurality of send acknowledgement signals is asserted when a requester desires access to the shared resource;

wherein one of said plurality of send acknowledgement lines corresponds to one of said plurality of requesters selected from said plurality of requesters desiring access to the shared resource.

18. An apparatus according to claim 17, wherein said send acknowledgement means coupled to said one or more requesters in said second requester category comprises a send acknowledgement storage means for storing one or more send acknowledgement requests from said one or more requesters in said second requester category if one of said plurality of send acknowledgement signals corresponding to said one of said plurality of requesters selected from said plurality of requesters desiring access is currently being output to the shared resource.

19. An apparatus according to claim 18, wherein said priority controller means comprises a data means coupled to said plurality of requesters for receiving a plurality of data signals from said plurality of requesters;

wherein one of said plurality of data signals corresponding to one of said plurality of requesters selected from said plurality of requesters desiring access is currently being output to the shared resource.

20. An apparatus according to claim 19, wherein said data means coupled to said one or more requesters in said second requester category comprises a data storage means for storing one or more data from said one or more requesters in said second requester category if one of said plurality of data lines corresponding to one of said plurality of requesters selected from said plurality of requesters desiring access is currently being output to the shared resource.

21. An apparatus according to claim 20, wherein said priority controller means comprises a read acknowledgement output means coupled to said one or more requesters in said second requester category for indicating to said one or more requesters in said second requester category that another one or more send acknowledgement requests and another one or more data can be sent.

22. An apparatus according to claim 21, wherein said read acknowledgement output means indicates to said one or more requesters in said second requester category that a predetermined one or more send acknowledgement requests and a predetermined one or more data can be sent.

23. An apparatus according to claim 22, wherein said predetermined one or more send acknowledgement requests and said predetermined one or more data is determined from a data storage capacity of said data storage means and from a send acknowledgement request storage capacity of said send acknowledgement storage means.

24. An apparatus according to claim 21, wherein said priority controller means comprises a read acknowledgement input means coupled to the shared resource for indicating that one of said plurality of send acknowledgement signals and that one of said plurality of data lines corresponding to one of said plurality of requesters selected from said plurality of requesters desiring access can be output to the shared resource.

25. An apparatus according to claim 24, wherein said second requester category is comprised of a single requester.

26. An apparatus according to claim 25, wherein priority is granted in a predetermined order to each one of said plurality of requesters in said first requester category.

27. An apparatus according to claim 26, wherein said send acknowledge storage means comprises a First-In-First-Out memory.

28. An apparatus according to claim 27, wherein said data storage means comprises a First-In-First-Out memory.

29. A method of selecting a requester from a plurality of requesters desiring access to a shared resource, wherein the plurality of requesters are divided into a plurality of requester categories, including a first requester category having one or more requesters and a second requester category having one or more requesters, and wherein the plurality of requesters share the use of the shared resource, and wherein each of said one or more requesters of said second requester category is physically located on a card external to and more remote from said shared resource than each of said one or more requesters of said first requester category whereby the circuit time delay attendant to a first desired request of said shared resource by each of said one or more requesters of said second requester category is greater than the corresponding circuit time delay attendant to a second desired request of said shared resource by each of said one or more requesters of said first requester category, comprising:

a. selecting one of the plurality of requesters from the plurality of requesters desiring access to the shared resource according to a priority determination protocol which assigns a first pre-determined priority to requesters from the first requester category which is different than a second pre-determined priority assigned to the second requester category whereby the difference between said first pre-determined priority and said second pre-determined priority compensates for the difference between said circuit time delay and said corresponding circuit time delay.

30. A method of selecting a requester from a plurality of requesters desiring access to a shared resource, wherein the plurality of requesters are divided into a plurality of requester categories, and wherein the plurality of requesters share the use of the shared resource, comprising:

a. providing a priority determination protocol to assign a priority to requesters from a particular one of a plurality of requester categories which is different than the priority assigned to requesters from another particular one of a plurality of requester categories;

b. receiving one or more send acknowledgement signals from the plurality of requesters;

c. receiving one or more data signals from the plurality of requesters;

d. determining if another particular one of the plurality of requesters is currently being output to the shared resource;

e. outputting the send acknowledgement and data signal to the shared resource if only one send acknowledgement signal was received;

f. selecting a particular one of the plurality of requesters from the plurality of requesters desiring access to the shared resource according to the priority determination protocol if more than one send acknowledgement was received;

g. outputting the send acknowledgement signal and data signal corresponding to the selected particular one of the plurality of requesters to the shared resource; and

h. repeating steps (b)-(g) until the send acknowledgement signal and data signal corresponding to each particular one of the plurality of requesters desiring access to the shared resource have been output to the shared resource.

31. A method of selecting a requester from a plurality of requesters desiring access to a shared resource, wherein the plurality of requesters are divided into two requester categories, and wherein the plurality of requesters share the use of the shared resource, comprising:

a. providing a priority determination protocol to alternatively grant priority to a particular one of the one or more requesters in the first requester category and to a particular one of the one or more requesters in the second requester category;

b. receiving one or more send acknowledgement signals from the plurality of requesters;

c. receiving one or more data signals from the plurality of requesters;

d. determining if another particular one of the plurality of requesters is currently being output to the shared resource;

e. outputting the send acknowledgement and data signal to the shared resource if not other particular one of the one or more send acknowledgement lines or data lines is currently being output to the shared resource;

f. storing the one or more send acknowledgement signals from the one or more requesters in the second requester category if another particular one of the plurality of send acknowledgement lines is currently being output to the shared resource;

g. storing the one or more data signals from the one or more requesters in the second requester category if another particular one of the plurality of data lines is currently being output to the shared resource;

h. selecting a particular one of the plurality of requesters from the plurality of requesters desiring access to the shared resource according to the priority determination protocol if more than one send acknowledgement was received;

i. receiving a read acknowledgement input to indicate whether the send acknowledgement signal and data signal corresponding to the selected particular one of the plurality of requesters can be output to the shared resource if the selected particular one of the plurality of requesters selected is from the second requester category;

j. outputting the send acknowledgement signal and data signal corresponding to the selected particular one of the plurality of requesters to the shared resource if the selected particular one of the plurality of requesters is from the first requester category or if step (i) indicates that the send acknowledgement signal and data signal corresponding to the selected particular one of the plurality of requesters from the second requester category can be output to the shared resource; and

k. repeating steps (b)-(j) until the send acknowledgement signal and data signal corresponding to each particular one of the plurality of requesters desiring access to the shared resource have been output to the shared resource.