Circuits, systems and methods for preventing queue overflow in data processing systems

• US 5,590,304 A
• Filed: 06/13/1994
• Issued: 12/31/1996
• Est. Priority Date: 06/13/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Covex Computer Corporation
• Inventors: Adkisson, Richard W.
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): DAVIS JR, WALTER D
• Application Number:
  US08/258,761
• Time in Patent Office: 932 Days
• Field of Search: 395/425, 395/800, 395/550, 395/500, 395/478, 395/325, 364/DIG. 1, 370/94.1, 370/85.6
• US Class Current: 711/100
• CPC Class Codes: G06F 13/1642 with request queuing
• CPC Class Codes: G06F 5/06 for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor G06F7/78 takes precedence

Abstract

A processing system is provided which includes circuitry for generating memory requests at a first clock rate. Input queuing circuitry which includes at least one queue receives the memory requests from the circuitry at the first clock rate and outputs such memory requests at a second clock rate. A memory system stores and retrieves data in response to the memory requests, the memory system outputting data in response to read requests received from input queuing circuitry. An output queue is provided which receives data output from memory at the second clock rate and outputs such data at the first clock rate. Queuing control circuitry is provided which prevents overflow of output queue by controlling the number of memory requests sent in bursts from the input queuing system to the memory system and by controlling the wait time between such bursts.

Claims

1. Circuitry for controlling the transfer of memory requests from a requesting device to a particular memory of a plurality of memories, said particular memory operating in response to a memory clock having a memory clock rate comprising:

queuing circuitry comprising;

a first queue for receiving said memory requests; and

a second queue coupled in series with said first queue said second queue holding said memory requests when contention for access to said particular memory occurs;

a counter;

control circuitry operable

in an idle state, clear said counter;

shift from said idle state to a send state when said queue circuitry starts sending requests to said memory;

in said send state, increment the count in said counter by a rate value, proportionate to the difference between an input rate at which said queuing circuitry receives memory requests and said memory clock rate, each time a read request is sent from said queuing circuitry to said memory and decrement the count in said counter each time a write request is sent from said queuing circuitry to said memory;

shift from said send state to said idle state when said queuing circuitry is done sending read memory requests to said memory and the count in said counter is less than or equal to an overhead value representing processing overhead time;

shift from said send state to a wait state when said queuing circuitry is done sending all memory requests to said memory and the count in said counter is greater than said overhead value;

in said wait state, decrement the count in said counter by said rate value in response to said memory clock; and

shift from said wait state to said idle state when the count in said counter decrements to a value less than or equal to said overhead value.

2. The circuitry of claim 1 and further comprising a second counter, said control circuitry further operable to increment the count in said second counter by one each time a memory request is sent from said queuing circuitry to said memory.

3. The circuitry of claim 2 wherein said queuing circuitry is done sending read requests when the count in said second counter is equal to a value representing a number of memory request to be sent to said memory in a burst and all read requests have been sent from said queuing circuitry to said memory.

4. The circuitry of claim 2 wherein said queuing circuitry is done sending all memory requests when the count in said second counter is equal to a value representing a number of said memory requests to be sent to said memory in a burst and all memory requests have been sent from said queuing circuitry to said memory.

5. The circuitry of claim 1 wherein said control circuitry comprises a plurality of logic circuits.

6. The circuitry of claim 1 wherein said control circuitry comprises at least a portion of a gate array.

7. The circuitry of claim 1 wherein said control circuitry comprises a state machine.

8. The circuitry of claim 1 and further comprising queue modeling circuitry for tracking the transfer of said memory requests from said queuing circuitry to said memory.

9. The circuitry of claim 8 wherein said queue modeling circuitry is further operable to track the request type of each memory request transferred from said queuing circuitry to said memory.

10. The circuitry of claim 1 wherein said rate value is equal to said memory clock rate divided by said input clock rate with one deducted from the result.

11. Circuitry for controlling the transfer of memory requests from a requesting device to a particular memory of a plurality of memories, said memory operating in response to a memory clock of a selected rate comprising:

queuing circuitry comprising;

a first queue for receiving said memory requests; and

a second queue coupled in series with said first queue for sending said memory requests to said particular memory, said second queue holding said memory requests when contention for access to said particular memory occurs;

a wait counter;

a register for holding an I/O rate value proportionate to the difference between an input rate at which said queuing circuitry receives said memory requests and said memory clock rate;

a register for holding an overhead value representing processing overhead time;

control circuitry operable to;

in an idle state, clear said wait counter;

shift from said idle state to a send state when said queuing circuitry starts sending requests to said memory;

in said send state;

increment the count in said wait counter by said I/O rate value with each read request send from said queuing circuitry to said memory; and

decrement the count in said wait counter with each non-read request sen from queuing circuitry to said memory;

shift from said send state back to said idle state when said queuing circuitry is done sending read requests to said memory and the count in said wait counter is less than or equal to said overhead value;

shift from send state to a wait state when said queuing circuitry is done sending memory requests to said memory and the count in said wait counter is greater than said overhead value;

in said wait state, decrement the count in said wait counter with each cycle of said memory clock; and

shift from said wait state to said idle state when the count in said wait counter decrements to a value less than or equal to said overhead value.

12. The circuitry of claim 11 wherein said I/O rate=(memory clock rate/input clock rate)-1.

13. The circuitry of claim 11 and further comprising:

a send counter;

a register for holding a send value representing a maximum number of said memory requests to be sent to said memory from said queuing circuitry in a burst; and

wherein said control circuitry is further operable to increment the count in said send counter by one with each memory request sent from said queuing circuitry to said memory.

14. The circuitry of claim 11 and further comprising queue modeling circuitry operable to:

track the input and output of memory request to and from said second queue; and

maintain bits indicative of a type of each memory request held in said second queue.

15. The circuitry of claim 14 wherein said queuing circuitry is done sending read requests when the count in said wait counter is equal to said send value and all read requests have been output from said second queue to said memory.

16. The circuitry of claim 14 wherein said queuing circuitry is done sending read requests when said first queue is empty and all read requests have been output from said second queue to said memory.

17. The circuitry of claim 14 wherein said queuing circuitry is done sending all memory requests when the count in said send counter is equal to said send count and all memory requests have been output from said second queue to said memory.

18. The circuitry of claim 14 wherein said queuing circuitry is done sending all memory requests when said first queue is empty and all memory requests have been output from said second queue to said memory.

19. A processing system comprising:

circuitry for generating memory requests at a first clock rate;

input queuing circuitry comprising;

a first queue for receiving said memory requests from said circuitry for generating at said first clock rate; and

a second queue coupled in series with said first queue for holding said memory requests when contention for access to a particular memory unit occurs and for outputting said memory requests at a second clock rate;

a memory system containing said particular memory unit for storing and retrieving data in response to said memory requests, said memory system outputting data at said second clock rate in response to read requests from said input queuing circuitry;

an output queue for receiving data from said memory at said second clock rate and outputting said data at said first clock rate; and

queuing control circuitry associated with said input queuing circuitry for preventing overflows of said output queue by controlling a number of said memory requests sent in bursts from said input queuing system to said memory system and by controlling wait time between ones of said bursts.

20. The system of claim 19 wherein said first clock rate is less than said second clock rate.

21. The system of claim 19 wherein each said memory request includes an address portion and a data portion, said at least one queue comprising parallel address and data queues for queuing said address and data portions respectively.

22. The system of claim 19 wherein said queue control circuitry comprises:

a counter;

control circuitry operable to;

in an idle state, clear said counter;

shift from said idle state to a send state when said input queuing circuitry starts sending requests to said memory;

in said send state, increment the count in said counter by a rate value, proportionate to the difference between said first clock rate and said second clock rate each time a read request is sent from said queuing circuitry to said memory system and decrement the count in said counter each time a read request is not sent from said queuing circuitry to said memory system;

shift from said send state to said idle state when said queuing circuitry is done sending read memory requests to said memory and the count in said counter is less than or equal to an overhead value representing processing overhead time;

shift from send state to a wait state when said queuing circuitry is done sending all memory requests to said memory and the count in said second counter is greater than said overhead value;

in said wait state, decrement the count in said counter in response to said memory clock timing the operation of said memory; and

shift from said wait state to said idle state when the count in said counter decrements to a value less than or equal to said overhead value.

23. The circuitry of claim 22 and further comprising a second counter, said control circuitry further operable to increment the count in said second counter by one each time a memory request is sent from said queuing circuitry to said memory.

24. The circuitry of claim 23 wherein said queuing circuitry is done sending read requests when the count in said second counter is equal to a value representing a maximum number of memory request to be sent to said memory in a burst and all read requests have been sent from said queuing circuitry to said memory.

25. The circuitry of claim 23 wherein said queuing circuitry is done sending all memory requests when the count in said second counter is equal to a value representing a maximum number of said memory requests to be sent to said memory in a burst and all memory requests have been sent from said queuing circuitry to said memory.

26. A method of controlling the transfer of memory requests from queuing circuitry having a first queue coupled in series with a second queue to a memory, the first queue receiving memory requests at a first clock rate and the second queue outputting memory requests at a second clock rate, comprising the steps of:

holding the memory requests in the second queue when contention for access to the memory occurs;

in an idle state, clearing a counter associated with the queuing circuitry;

shifting from the idle state to a send state when the queuing circuitry starts sending requests to said memory;

in the send state, incrementing the count in the counter by a rate value, proportionate to the difference between the first and second clock rates, when a read request is sent from the queuing circuitry to the memory;

in the send state, decrementing the count in the counter when a non-read request is sent from the queuing circuitry to the memory;

shifting from the send state to the idle state when the queuing circuitry is done sending read memory requests to the memory and the count in the counter is less than or equal to an overhead value representing processing overhead time;

shifting from the send state to a wait state when the queuing circuitry is done sending all memory requests to the memory and the count in the counter is greater than the overhead value;

in the wait state, decrementing the count in the counter in response to the memory clock timing the operation of the memory; and

shift from the wait state to the idle state when the count in said counter decrements to a value less than or equal to the overhead value.

27. The circuitry of claim 26 further comprising the step of incrementing the count in a second counter associated with the queuing circuitry by one when a memory request is sent from the queuing circuitry to the memory.

28. The circuitry of claim 27 wherein the queuing circuitry is done sending read requests when the count in the second counter is equal to a value representing a number of memory requests to be sent to the memory in a burst and all read requests have been sent from the queuing circuitry to said memory.

29. The circuitry of claim 27 wherein the queuing circuitry is done sending all memory requests when the count in the second counter is equal to a value representing a number of memory requests to be sent to the memory in a burst and all memory requests have been sent from the queuing circuitry to the memory.

30. A method of controlling a memory comprising the steps of:

generating memory requests at a first clock rate;

inputting the memory requests into an input queue at the first clock rate;

transferring the memory requests to a crossbar queue coupled in series with the input queue;

holding the memos requests in the crossbar queue when contention for access to the memory occurs;

outputting the memory requests from the crossbar queue at a second clock rate;

addressing a memory system with the memory addresses output from the crossbar queue, the memory system outputting at the second clock rate in response to read memory requests;

inputting the data output from the memory into an output queue at the second clock rate;

outputting said data at said first clock rate; and

preventing overflows of the output queue by controlling the number of memory requests sent in bursts from the input queue to the memory system and by controlling wait time between the bursts.