System and method for establishing priorities in transferring data in burst counts from a memory to a plurality of FIFO stages, each having a low, intermediate, and high region

Abstract

Each of a plurality of FIFO has (1) a low region indicating a minimum number of words for FIFO storage, (2) a burst count indicating the number of words involved in each transfer to such FIFO and (3) a high region where a word count transfer into the FIFO is not initiated. However, a burst count transfer initiated before the beginning of a FIFO high region may be completed in the FIFO high region. Each FIFO is initially filled from a memory by a memory controller to the low FIFO region. Upon word transfer from each FIFO, the memory controller establishes a priority to provide an additional burst count to the FIFO low region. When the memory controller is otherwise idle and the number of words in such FIFO is in a region intermediate the FIFO low and high regions, a burst count for each FIFO may be transferred into the intermediate FIFO region. The memory controller and each FIFO respectively remember the number of words transferred into and from such FIFO. The difference between the number of words transferred into and from each FIFO indicates whether the words in such FIFO are in the low, intermediate or high region. The individual value of the number of words for each FIFO low region and the burst count for such FIFO help to establish the controller priority in transferring burst counts at any instant to such FIFO relative to burst count transfers at such instant to other FIFO.

We claim: 
     
       1. A method of providing a priority in reading words from a memory, including the steps of: providing a plurality of FIFO's each having input and output ends and constructed to receive words at the input end and to pass the words from the output end in the same order as received at the input end, the information represented by the words in each FIFO being different from the information represented by the words in the other FIFO's,   allocating within each FIFO a low region indicating the minimum number of words that should be stored in the FIFO at all times,   maintaining a word count for each FIFO indicating the number of words introduced to such FIFO upon each such introduction of words to such FIFO,   allocating within each FIFO a high region indicating where a burst count is not to be initiated for introduction to such FIFO,   allocating within each FIFO an intermediate region between the low and high regions for introducing words from memory into the FIFO on a lower priority basis than a priority basis for introducing words into the low region individual to each FIFO, and   prioritizing the introduction of burst counts to each individual one of the FIFO's in accordance with the values established for the low region and the burst count for such individual one of the FIFO's.   
     
     
       2. A method as set forth in claim 1 wherein each of the FIFO receives burst counts in at least the low region for such FIFO on a priority basis to fill the low region of such FIFO.   
     
     
       3. A method as set forth in claim 1 wherein the introduction of a burst count to each of the FIFO is not initiated for such FIFO when the number of words in such FIFO is within the high region of such FIFO.   
     
     
       4. A method as set forth in claim 1 wherein the transfer to each individual one of the FIFO of each increment of the word count for such FIFO is provided by a memory controller and wherein   the memory controller provides a cumulative indication of the number of words transferred at each instant into such individual one of the FIFO.   
     
     
       5. A method as set forth in claim 1 wherein each individual one of the FIFO provides an indication on a cumulative basis of the number of the words transferred from the FIFO at each instant.   
     
     
       6. A method as set forth in claim 2 wherein the introduction of a burst count to each of the FIFO is not initiated for such FIFO when the number of words in such FIFO is within the high region of such FIFO,   the transfer to each individual one of the FIFO of each increment of the word count for such FIFO is provided by a memory controller and wherein   the memory controller provides a cumulative indication of the number of words transferred at each instant into such individual one of the FIFO and wherein   each individual one of the FIFO provides an indication on a cumulative basis of the number of the words transferred from the FIFO at each instant.   
     
     
       7. A method of providing a priority in reading words from a memory, including the steps of: providing a plurality of FIFO's each having input and output ends and each constructed to read words into the FIFO at the first end and to transfer words from the FIFO at the second end,   operating each of the FIFO's on a recirculating basis,   allocating within each of the FIFO's a first region having a particular number of words for providing for a transfer of words from the memory into the FIFO on a priority basis individual to such FIFO,   maintaining for each of the FIFO's a burst count indicating a particular number of words to be transferred from the memory in each such transfer, the burst count being adjustable for prioritizing the introduction of burst counts to each individual ones of the FIFOs in accordance with the value established for the burst count,   allocating within each of the FIFO's a second region which has a second particular number of words and in which a transfer of the burst count of the particular number of words into the FIFO is not to be initiated, and   transferring from the memory into each individual ones of the FIFO's of burst counts for such FIFO dependent upon the number of words in such individual one of the FIFO's relative to the first particular number of words in the first region in such individual one of The FIFO's and relative to the second particular number of words in the second region in such individual one of the FIFO's.   
     
     
       8. A method as set forth in claim 7, including the step of: transferring burst counts on a priority basis from the memory to each individual one of the FIFO's to fill the first region of such FIFO with words.   
     
     
       9. A method as set forth in claim 7 wherein the priority provided for each of the FIFO in filling the first region of such FIFO is dependent upon the number of words capable of being filled in the first region of such FIFO and dependent upon the burst count for such FIFO.   
     
     
       10. A method as set forth in claim 7 wherein the burst counts for each FIFO are transferred into the input end of such FIFO to fill any region in such FIFO between the first and second regions during the times when words are not being transferred from the memory to any of the FIFO.   
     
     
       11. A method as set forth in claim 7 wherein the transfer of the burst counts for each FIFO from the memory into the FIFO is initiated in the portion of the FIFO other than the second region in the FIFO and is continued into the second region in the FIFO when such transfer is initiated from a position outside of the second region of the FIFO.   
     
     
       12. A method as set forth in claim 11 wherein the burst counts for each FIFO are prevented from being transferred from the memory into the second region in the FIFO when such transfer is initiated from a position in the second region in the FIFO.   
     
     
       13. A method as set forth in claim 8 wherein the priority provided for each of the FIFO in filling the first region of such FIFO is dependent upon the number of words capable of being filled in the first region of such FIFO and dependent upon the burst count for such FIFO,   the burst count for each FIFO are transferred into the input end of such FIFO to fill any region in such FIFO between the first and second regions during the times when words are not being transferred from the memory to any of the FIFO,   the transfer of the count for each FIFO from the memory into the FIFO is initiated in the portion of the FIFO other than the second region in the FIFO and is continued into the second region in the FIFO when such transfer is initiated from a position outside of the second region of the FIFO, and   the burst counts for each FIFO are prevented from being transferred from the memory into the second region in the FIFO when such transfer is initiated from a position in the second region in the FIFO.   
     
     
       14. A method of providing a priority in reading words from a memory, including the steps of: providing a memory controller,   providing a data fetch interface,   providing a plurality of FIFO's each having an input end for receiving words from the memory controller through the data fetch interface and each having an output end for transferring words from the FIFO in the same order as the words are received at the input end of the FIFO,   maintaining in the data fetch interface for each FIFO a count of the number of words to be transferred in a burst from the memory controller through the data fetch interface to such FIFO in each transfer of words to the FIFO,   allocating within each FIFO a first region for receiving bursts of words on a priority basis until such first region in such FIFO becomes fall with words, the first region in each FIFO becoming refilled on a priority basis with bursts of words when words are transferred from the first region,   allocating within each FIFO a second region wherein the initiation of transfers of bursts of words into the region is prevented,   allocating within each FIFO a third region between the first and second regions for the transfer of the words in each burst for such FIFO into the third region on a lower priority basis than the priority basis for the transfer of bursts of words into the first region for such FIFO when the memory controller would otherwise be idle,   communicating at each instant from the data fetch interface to the memory controller the address of the FIFO for receiving the word transfer in each burst and the count of such word transfer in each burst, and   transferring the words in each burst from the memory controller through the data fetch interface to each FIFO in accordance with requests from the data fetch interface to the memory controller for such FIFO.   
     
     
       15. In a method as set forth in claim 14, including the steps of: communicating a request from the data fetch interface to the memory controller for each of the FIFO's for the transfer to such FIFO of the words in each burst for such FIFO, and   communicating an acknowledgment from the memory controller to the data fetch interface of the request from the data fetch interface to the memory controller for the transfer to each of the FIFO's of the words in each burst for such FIFO.   
     
     
       16. A method as set forth in claim 15 wherein the words in each burst for each FIFO are transferred from the memory controller through the data fetch interface to such FIFO after the acknowledgment from the memory controller to the data fetch interface of the request from the data fetch interface to the memory controller for the transfer to each of the FIFO of the words in each burst for such FIFO.   
     
     
       17. A method as set forth in claim 14 wherein each FIFO is provided with a first region for receiving words in each burst on a priority basis until such first region in such FIFO becomes filled with words and wherein   the priorities for the different FIFO are dependent upon the number of words capable of being provided in the first region for such FIFO and upon the number of words in each burst for such FIFO.   
     
     
       18. A method of providing a priority in reading words from a memory including the steps of: providing a plurality of FIFO's each having an input end for transferring words into the FIFO and having an output end for transferring words from the FIFO,   providing a memory controller for transferring words into the input end of the FIFO,   maintaining a first count in the memory controller of the number of words transferred into the input end of each FIFO,   maintaining a second count of the words transferred from the output end of the FIFO,   allocating a first region in each FIFO with a particular number of words,   determining at each instant from the first count and the second count whether the first region in such FIFO is full,   transferring words on a priority basis to the input end of each FIFO to maintain the first region in such FIFO full, and   maintaining for each of the FIFOs a burst count indicating a particular number of words to be transferred from the memory in each such transfer, the burst count being adjustable for prioritizing the word transfers to each individual ones of the FIFOs in accordance with the value established for the burst count.   
     
     
       19. A method as set forth in claim 18, including the steps of; allocating within each FIFO a second region for indicating that such FIFO has a number of words greater by a particular amount than the maximum number of words in the first region,   determining at each instant from the count by the memory controller of the number of words transferred into the input end of each FIFO and from the count of the words transferred from such FIFO whether the number of words in the FIFO is in the second region, and   inhibiting the initiation of the transfer of words from the memory controller to each FIFO when the words in such FIFO are in the second region in the FIFO prior to the initiation of the transfer of the words from the memory controller to such FIFO.   
     
     
       20. A method as set forth in claim 19, including the steps of: allocating a third region in each FIFO between the first and second regions in such FIFO and   filling such third region in each FIFO with words on a lower priority basis than the priority for filling the first region in such FIFO with words.   
     
     
       21. A method as set forth in claim 18, including the steps of: establishing priorities in accordance with a data fetch interface for the transfer of words from the memory controller through the data fetch interface to such individual one of the FIFO's to fill the first region of such FIFO with words on a priority relative to the other FIFO's established by the data fetch interface.