Increased performance of graphics memory using page sorting fifos
First Claim
1. A sorting fifo for use in a memory controller, comprising:
- an input bus for receiving a sequence of data references each comprising an address having a page portion wherein data references having a same page portion appear non-sequentially in said received sequence of data references; and
means for re-ordering the sequence of data references for output to an output bus such that the data references having common page portions are grouped together to form a second sequence of data references in which data references having a same page portion appear sequentially therein.
3 Assignments
0 Petitions
Accused Products
Abstract
A sorting fifo for use in a memory controller of a graphics system is provided to rearrange the order of an incoming stream of pixels such that groups of pixels to the same page are grouped together. By rearranging the order of pixels before they are forwarded to a frame buffer memory, the repaging delays at the frame buffer memory may be minimized, and the overall performance of the graphics system is increased. The sorting fifo may include, for example, a pair of fifos coupled to a common controller. The controller is also coupled to the input address bus. The controller compares the page addresses of data received on the input address bus against page addresses of data references stored in the fifos. When there is a match, the data reference is forwarded to the appropriate fifo. The controller also controls the reading of data out of the fifo, to ensure that the rearranged order is preserved.
99 Citations
20 Claims
-
1. A sorting fifo for use in a memory controller, comprising:
-
an input bus for receiving a sequence of data references each comprising an address having a page portion wherein data references having a same page portion appear non-sequentially in said received sequence of data references; and means for re-ordering the sequence of data references for output to an output bus such that the data references having common page portions are grouped together to form a second sequence of data references in which data references having a same page portion appear sequentially therein. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A sorting buffer for use in a memory controller comprising:
-
a pair of buffers coupled to an input bus, each of said buffers having an input location and an output location; and a control unit, coupled to said pair of buffers and to said input bus, for storing data references received on said input bus into a selected one of said input locations of said pair of buffers, said input location selected responsive to an address of each of said data references, said control unit also for forwarding data from each of said output locations of said pair of buffers, said output location selected responsive to addresses of data references in said output locations of said pair of buffers. - View Dependent Claims (9, 10, 11, 12)
-
-
13. A sorting fifo for use in a graphics memory controller comprising:
-
a pair of fifos coupled to an input bus, each of said pair of fifos having an input register and an output register; a first register for storing an address of said first data reference in said input register of a first one of said first pair of fifos; a second register for storing an address of said first data reference in said input register of a second one of said pair of fifos; a third register, for storing an address of a second data reference in said output register of said first one of said pair of fifos; a fourth register, for storing an address of a second data reference in said output register of said second one of said pair of fifos; a first pair of comparators, each one of said first pair of comparators having a first input coupled to said input bus and a second input coupled to a different one of said first and second registers; a second pair of comparators, each one of said second pair of comparators having a first input coupled to a corresponding one of said output registers of said pair of fifos and a second input coupled to a different one of said first and second registers; a multiplexer, coupled to said pair of fifos, to provide data from one of said pair of fifos onto an output data bus; and a control unit, coupled to outputs of said first and second pair of comparators and to said pair of fifos, for controlling the reading and writing of fifos such that data references received on said input bus having similar address are written to a common one of said pair of fifos. - View Dependent Claims (14)
-
-
15. A method of optimizing frame buffer memory performance to reduce paging, the method including the steps of:
-
a) receiving a stream of data references for storage in said frame buffer memory on an input data bus, each of said received data references comprising an address having a row portion identifying a row of the frame buffer memory in which said data reference is to be stored; b) rearranging the order of said stream of data references to form a rearranged stream of data references, wherein data references having matching row portions are grouped together in said rearranged stream of data references; and c) providing said rearranged stream of data references to said frame buffer controller, thereby reducing operations associated with writing to a different row of the frame buffer memory to only those occurrences where there is a transition between said groups of data references in said rearranged stream of data references.
-
-
16. A method of optimizing frame buffer memory performance to reduce the amount of paging using a sorting buffer, the sorting buffer receiving a stream of data references, each of said data references comprising an address, said address comprising a page portion, said sorting fifo including a first fifo and a second fifo, the method comprising the steps of:
-
loading data references from an input bus into said first fifo until there is a mismatch between a page portion of said address on said input bus and a page portion of an address in said first fifo; loading data references from said input bus into said second fifo until there is a mismatch between said page portion of said address on said input bus and a page portion of an address in said second fifo; and when there is a mismatch between a page portion of said address on said input bus and a page portion of said address either of the first or second fifos, comparing said page portion of the address in said other fifo against said page portion of said address on said input bus, and responsive to a match, writing said data reference in said other fifo.
-
-
17. A method of optimizing frame buffer memory performance to reduce the amount of paging using a sorting buffer, the sorting buffer receiving a stream of data references, each of said data references comprising an address comprising a page portion, said sorting buffer including a first fifo and a second fifo, the method comprising the steps of:
-
A) loading said first fifo with a first data reference, and storing said row address portion of said first data reference in a first register; B) receiving a next data reference; C) comparing said page address portion of said next data reference to said row address portion in said first register; D) responsive to a match at step D), repeating steps A) through C); and E) responsive to no match at step C), loading said second fifo with said next data reference, and storing said row address portion of said first data reference in a second register. - View Dependent Claims (18, 19)
-
-
20. A method of emptying a pair of buffers comprising a plurality of data references, where the contents of the pair of buffers have been sorted such that data references to common pages are grouped together, and wherein each of the pair of buffers has an output register, comprising the steps of:
-
A) selecting a first one of said pair of buffers as a data source; B) unloading a first data reference from said output register of said selected buffer when data is ready at said output register; C) storing, with said selected buffer, a page address of said unloaded first data reference; D) comparing a page address of a next data reference from said output register of said selected buffer against said stored page address; E) continuing to unload next data references from said output register of said selected buffer until no data is ready at said output register or said step of comparing indicates that said page address of a next data reference from said output register of said selected buffer does not match said stored page address; F) repeating steps B) through F), wherein said selected buffer is the other buffer of the pair.
-
Specification