# Patent

## Title
Field effect semiconductor device having dipole barrier

## Abstract

The present invention provides a first-in-first-out (FIFO) memory device comprising a first latch array, a second latch array, a write pointer device, a first read pointer device, and a second read pointer device. Preferably, the FIFO memory device of the present invention is implemented in a graphics memory system having a two-bank architecture for reducing paging overhead. The second latch array is used for storing row addresses for bank0 and bank1 of the frame buffer memory of the graphics memory system. The first latch array is used for storing column addresses and any other related data for bank0 and bank1 of the frame buffer memory. When the row addresses are loaded into the second latch array, the row addresses are tagged with a bank bit that indicates which bank the row address will access. Additionally, row addresses that require re-paging of either bank0 or bank1 are tagged with a paging bit. The second read pointer device determines which of the row addresses has been tagged with a paging bit to determine which row addresses are candidates for bank0 and bank1 transactions. The second read pointer device then prioritizes the bank0 candidates and the bank1 candidates to determine which of the bank0 candidates is a dump candidate and which of the bank1 candidates is a dump candidate. The second read pointer device then prioritizes the dump candidates and selects the row address corresponding to the dump candidate that was loaded first and that will be required first. This row address is then sent to a row port output register. Once this row address has been unloaded from the row port output register, the row address corresponding to the next dump candidate can then be sent to the row port output register. This aspect of the present invention allows a row address for one bank to be loaded into the row port output register while transactions for the other bank are being processed, thus allowing re-paging to be "hidden".

## Background
The present invention relates to a graphics memory system and, more particularly, to a graphics memory system that utilizes a first-in-first-out (FIFO) architecture with built-in intelligence for paging the frame buffer memory, which allows re-paging of banks of the frame buffer memory to be "hidden" such that paging overhead is reduced.

Many high performance graphics memory systems utilize synchronous graphics random access memory (SGRAM) for the frame buffer memory. These devices typically utilize a two-bank architecture where a page of a bank, i.e., a particular row address in the bank, can be closed and then re-opened(re-paged) while a page in the other bank is being accessed. In order for the memory controller to anticipate the requests for both banks, which are typically referred to as bank0 and bank1,the requests are normally sorted and separated into separate banks. Specifically, the bank0 requests are stored in one FIFO memory element (FIFO) and the bank1 requests are stored in a different FIFO memory element (FIFO). The memory controller then receives the output of each of the FIFO memory elements (FIFOs) and performs row comparisons to determine whether either bank will need to be re-paged so that the memory controller can open a new page in one bank as a page in the other bank is being accessed. Therefore, as soon as the page in one bank is finished being accessed, the memory controller can immediately begin accessing the page in the other bank since it has already been opened, thereby allowing re-paging to be hidden and paging overhead to be reduced.

Although the paging overhead associated with the current two-bank architecture of the frame buffer memory is less than that which would occur if each bank was required to wait until the transaction for the other bank was complete before opening a new page, there are several disadvantages associated with this paging technique. First of all, the current paging technique requires the use of two FIFOs for separately grouping the bank0 and bank1 requests. Secondly, the steps of sorting the bank0 and bank1 requests disrupts the processing order of the pixels. This disruption may not be significant in all cases, but when the transactions being requested by the memory controller are read transactions, coherency and ordering difficulties arise. The coherency issues are dealt with by performing "flushing". Flushing is performed by allowing prior write transactions to occur before a read transaction is attempted in order to ensure that the contents of the frame buffer memory do not become stale. The ordering issues are dealt with by implementing hardware in the graphics memory system that reconstructs the order of the data for read requests transactions.

Accordingly, a need exists for a graphics memory system that utilizes a two-bank architecture and that allows paging overhead to be hidden and reduced without requiring that the bank0 and bank1 requests be separately grouped in different FIFOs.

The present invention provides a first-in-first-out (FIFO) memory device comprising a first memory element, a second memory element, a write pointer device, a first read pointer device, and a second read pointer device. The first memory element receives a first set of entries from an input port of the FIFO memory device and stores each of the entries in a storage location in the first memory element. The second memory element receives a second set of entries from the input port of the FIFO memory device and stores each of the entries of the second set in a storage location in the second memory element. The entries are stored at storage locations in the first and second memory elements that are addressed by the write pointer. The first read pointer device determines addresses in the first memory element for reading entries out of storage locations in the first memory element which are eventually output from the FIFO memory device via a first output port of the FIFO memory device. The second read pointer device determines whether any of the entries of the second set are tagged entries. The second read pointer device calculates addresses in the second memory element based on these tagged entries and reads them out of the second memory element. These entries are eventually output from the FIFO memory device via a second output port of the FIFO memory device.

Only the tagged entries in the second memory element are output from the FIFO memory device, whereas preferably all of the entries stored in the first memory element are output from the FIFO memory device. In accordance with the preferred embodiment of the present invention, the selected tagged entry in the second memory element causes an offset to be generated. The offset value depends on the relative location of the tagged entry that caused it to be generated. The offset value is then combined with the first read pointer address to generate the second read pointer address. The second read pointer address corresponds to the location in the second memory element that is associated with the tagged entry that caused the offset to be generated.

In accordance with the preferred embodiment of the present invention, the FIFO memory device of the present invention is implemented in a graphics memory system having a two-bank architecture for reducing paging overhead. Preferably, the first and second memory elements are first and second latch arrays, respectively. In accordance with this embodiment, the second latch array is used for storing row addresses and other related data for bank0 and bank1 of the frame buffer memory of the graphics memory system. The first latch array is used for storing column addresses and other related data for bank0 and bank1 of the frame buffer memory. When the row addresses are loaded into the second latch array, the row addresses are tagged with a bank bit that indicates which bank the row address will access. Additionally, row addresses that require re-paging of either bank0 or bank1 are tagged with a paging bit.

The second read pointer device determines which of the row addresses has been tagged with a paging bit to determine which row addresses are candidates for bank0 and bank1 re-paging. The second read pointer device then prioritizes the bank0 candidates and the bank1 candidates to determine which of the bank0 candidates is a dump candidate and which of the bank1 candidates is a dump candidate. A dump candidate for a particular bank corresponds to a row address in the second latch array that has no other row addresses ahead of it in the second latch array for the same bank. The second read pointer device then prioritizes the two dump candidates and selects the dump candidate that was loaded first and that will be required first. This row address is then sent to a row port output register.

Once this row address has been unloaded from the row port output register, the row address corresponding to the next dump candidate can then be sent to the row port output register. This aspect of the present invention allows a row address for one bank to be loaded into the row port output register while transactions for the other bank are being processed, thus allowing re-paging to be "hidden". A RAM controller of the graphics memory system controls the unloading of the row address from the row port output register by sending an unload signal to the row port output register.

The column addresses stored in the first latch array that correspond to re-paging transactions are also tagged with paging synchronization bits. Each of the column addresses contained in the first latch array are sent to a column port output register of the first latch array in first-in-first-out order. The RAM controller determines whether the column address contained in the column port output register has a paging synchronization bit associated with it before unloading the column address. If it does, the RAM controller ensures that the page of memory for the bank being addressed by the column address has been "opened" before unloading the column address from the column port output register. If that page has not been "opened," the RAM controller will do so using information from the row port output register before unloading the column address from the column port output register.

Whenever the second read pointer device selects a dump candidate, the second read pointer device calculates an offset that has a value that depends on the location at which the paging bit associated with the dump candidate is stored in a shift register. This offset value is added to the first read pointer address in order to generate the second read pointer address. The second read pointer address corresponds to the storage location in the second latch array where the associated row address is stored. Using this address, the second read pointer device causes the selected row address to be sent to the row port output register.

In accordance with an alternative embodiment of the present invention, multiple batches of column and row addresses can be stored in the first and second latch arrays, respectively. In accordance with this embodiment, in addition to the tags mentioned above, each entry in the second latch array is tagged with a batch indicator that functions as a batch delimiter. The second read pointer device uses the batch indicator to inhibit any row addresses not associated with the current batch from being sent to the row port output register.

Other features and advantages of the present invention will become apparent from the following discussion, drawings and claims.

FIG. 1 is a block diagram of a computer graphics display system incorporating the graphics memory system of the present invention.

FIG. 2 is a block diagram of the graphics memory system of the computer graphics display system shown in FIG. 1.

FIG. 3 is a block diagram of the frame buffer controller of the graphics memory system shown in FIG. 2 in accordance with the preferred embodiment of the present invention.

FIG. 4 is a block diagram of one of the memory controllers of the frame buffer controller shown in FIG. 3 in accordance with the preferred embodiment of the present invention.

FIG. 5 is a block diagram of the FIFO of the present invention that demonstrates the ports of the FIFO and the types of information being input to or output from the ports.

FIG. 6 is a block diagram of the FIFO shown in FIG. 5 that demonstrates the built-in intelligence of the FIFO for reducing paging overhead.

FIGS. 7A-C are block diagrams of shift registers utilized by the FIFO of the present invention.

FIG. 8 is a table containing entries which demonstrate the logic comprised in the intelligent FIFO shown in FIG. 6 for reducing paging overhead.

FIG. 9 is a block diagram of a shift register utilized for indicating the batch that transactions are associated with in accordance with an alternative embodiment.

FIG. 10 is a block diagram of the intelligent FIFO of the present invention in accordance with an alternative embodiment which utilizes the shift register of FIG. 9.

FIG. 11 is a table containing entries which demonstrate the logic comprised in the intelligent FIFO shown in FIG. 10.

FIG. 1 is a block diagram of the computer graphics display system 10 of the present invention. The computer graphics display system 10 comprises a host CPU 12, a host memory device 14, a local bus 18, an input/output (I/O) controller device 25, an advanced graphics port/peripheral component interconnect (AGP/PCI) interface bus 16, a graphics memory system 20, and a monitor 21 for displaying graphics information output from the graphics memory system 20.

The host CPU 12 processes input received from the console (not shown) of the computer graphics display system 10 and outputs commands and data over the local bus 18 to the I/O interface controller 25. The I/O interface controller 25 formats the commands and data utilizing the protocols of the PCI/AGP interface bus 16. The information received over the PCI/AGP interface bus 16 is input to the graphics memory system (GMS) 20. The graphics memory system 20 then processes this information and causes graphics images to be displayed on the monitor 21.

FIG. 2 is a block diagram of the graphics memory system 20 of the present invention in accordance with the preferred embodiment. The host interface unit (HIU) 32, the 2D and 3D macro-function units (MFUs) 34, 36, the object function unit (OFU) 38, the frame buffer controller (FBC) 40 and the display controller 43 of the graphics memory systems 20 are typical components in graphics display systems. Therefore, only a cursory explanation of the functions of these components will be provided herein since persons skilled in the art will understand the types of operations that are performed by these components.

The host interface unit 32 fetches command data packets and texture maps from the host memory 14 via the PCI/AGP bus 16. The host interface unit 32 then provides graphics 2D information to the 2D macro-function unit 34 and 3D information to the 3D macro-function unit 36. The 2D macro-function unit 34 generates 2D vectors, text and rectangle spans. The 3D macro-function unit 36 performs triangle setup, 3D rastorization, and texture mapping.

The output from the 2D and 3D macro-function units 34 and 36 is received by the object function unit 38. The object function unit 38 performs rectangle clipping, patterning, frame buffer-to-frame buffer block transfers and rectangle span fills. The output of the object function unit 38 is received by the frame buffer controller (FBC) 40. The frame buffer controller 40 dispatches requests to the memory controllers (MC0 and MC1) 41 and 42 to cause memory controller 41 and memory controller 42 to write and read pixel colors and Z coordinates to and from RAM 45 and RAM 46. The frame buffer controller 40 also fetches display information which is sent to the display controller 43. The display controller 43 receives the display information and converts it into red, green and blue (RGB) analog data and sends it to the display monitor 21.

FIG. 3 is a block diagram of the frame buffer controller 40 of the present invention in accordance with the preferred embodiment. The object receiver 51 and the object builder 55 are both in communication with the object function unit 38. The object builder 55 receives pixel data from the memory controllers 41 and 42 read out of RAM 45 and RAM 46, respectively, and provides the read data to the object function unit 38. The object builder 55 receives 32-bit data from each of the memory controllers 41 and 42 and reformats the data if necessary and builds 64-bit objects for use by the object function unit 38. The object receiver 51 receives X, Y and Z screen coordinates and Y, U, V or R, G, B color data from the object function unit 38, converts the color data into R, G, B format if necessary, and provides the coordinate and R, G, B color data to the tile builder 56. The tile builder 56 builds tiles, which are 32-bit words of Z coordinate data and color data, and maps the X and Y screen coordinates into tile row and column addresses corresponding to locations in the RAM 45 and RAM 46.

The tile builder 56 outputs tiles of Z data and color data along with their corresponding row and column addresses to the memory controllers 41 and 42. The tile builder 56 also inserts a batch delimiter after the last tile of the coherent batch of pixels (i.e., no two pixels within a batch having the same X, Y address). In accordance with the preferred embodiment of the present invention, two memory controllers and two RAM memory devices are implemented in the graphics memory system 20. However, it will be understood by those skilled in the art that the present invention is not limited with respect to the number of memory controllers that are implemented in the graphics memory system 20. The use of multiple memory controllers enhances the performance of the graphics memory system 10 of the present invention, as will be understood by those skilled in the art. The batching architecture and technique of the present invention can be used with a single memory controller and a single frame buffer memory element.

Each of the memory controllers 41 and 42 receives Z row and column addresses, pixel row and column addresses, and pixel color data. Each of the RAM memory elements 45 and 46 comprises an image buffer storage area (not shown) and a Z buffer storage area (not shown). The pixel color data is stored in the image buffer storage area and the Z coordinate data is stored in the Z buffer storage area. Thus, the present invention utilizes detached Z buffering in that the Z coordinates are not interleaved with the color values, but rather are stored in a separate area of RAM.

In accordance with the preferred embodiment of the present invention, Z coordinate data is read out of RAM 45 and RAM 46 by memory controllers 41 and 42 in batches so that the bus turn around time, i.e., the number of states required for the RAM bus 61 or 62 to switch between read and write transactions, is amortized over a plurality of pixels. By amortizing the bus turn around time over a plurality of pixels, any processing latencies associated with detached Z buffering are minimized. Furthermore, re-paging is also amortized over a plurality of pixels, thereby reducing paging overhead.

The batching architecture and technique of the present invention in accordance with the preferred embodiment will now be described with respect to only memory controller 41 and RAM element 45, since the memory controllers 41 and 42 function identically. It should be noted that the memory controllers 41 and 42 are capable of processing batches of data simultaneously. Therefore, operations which are identical to the operations discussed below of the memory controller 41 in conjunction with RAM 45 may be concurrently performed by memory controller 42 in conjunction with RAM 46.

Memory controller 41 compares a batch of new Z coordinate data received from the tile builder 56 with a batch of Z coordinate data read out of RAM 45. As each Z coordinate is compared, the Z comparison results are queued in the Z Compare Results FIFO 58 for use by either of the memory controllers 41 and 42 to determine whether the new color corresponding to the Z coordinate compared must be written into the RAM of the respective memory controller or whether the new color can be discarded. The purpose of the Z Comparison Results FIFO 58 is discussed in more detail below with respect to FIG. 4.

Re-paging overhead will be reduced in most cases due to the fact that a large number of pixels will be processed within a batch. Most of the time, for small batches, re-paging occurs only when accesses are switched from pixel color writes to Z coordinate data reads, or from Z coordinate data writes to pixel color writes. For large batches, when re-paging is required within a batch of Z reads, Z writes, color reads, or color writes, the extra re-paging can be "hidden" and, therefore, generates little or no overhead.

FIG. 4 is a detailed block diagram of the memory controller 41 shown in FIG. 3. The batching technique of the present invention in accordance with the preferred embodiment will now be discussed with respect to FIG. 4. A batching sequence begins when the tile builder 56 writes a pixel color and its corresponding Z coordinate data to the memory controller 41. The Z coordinate is written to the New Z FIFO 71 and the corresponding Z coordinate row/column address is written to the Read Z FIFO 86. The new pixel color row/column address and color data are written to the New Pixel FIFO 75. These writes continue until the New Z FIFO 71 and the New Pixel FIFO 75 fill up. This allows multiple batches of data to be queued up while the current batch is being processed.

In accordance with the preferred embodiment of the present invention, a batch will consist of a group of write requests that is limited in size to ensure data coherency and to prevent the FIFOs of the memory controller 41 from being overflowed. Each request of the batch will correspond to a different address in RAM 45. The boundaries of the batches are identified by batch delimiters which notify the memory controller 41 that the end of a batch has occurred. The batch boundaries are defined in the computer graphics display system 10 in accordance with a predetermined criterion, which is selected by the system designer in accordance with practical considerations, as will be understood by those skilled in the art. Batch delimiters are generally known in the art and, therefore, a detailed discussion of their use with the present invention will not be provided herein. It will be understood by those skilled in the art that the present invention is not limited to any particular technique for identifying the boundaries of a batch.

In accordance with the preferred embodiment of the present invention, the memory controller 41 uses the batch delimiter for control during batch processing. Batch delimiters are written to the New Pixel FIFO 75, to the Read Pixel FIFO 83, and to the Read Z FIFO 86. Once the Z address has be written to the Read Z FIFO 86, the RAM controller 91 will read the contents of the Read Z FIFO 86 and cause the corresponding Z coordinate data to be read out of RAM 45 onto the memory bus 61 and written from the memory bus 61 into the Z test component 73. For all Z coordinate data transferred from RAM 45 into the Z test component 73, corresponding new Z coordinate data is transferred from the New Z FIFO 71 into the Z test component 73. The Z test component 73 compares these values and, if the comparison passes, the new Z coordinate data is written into the Write Z FIFO 84.

Once the RAM controller 91 detects the batch delimiter in the Read Z FIFO 86, a switch is made to the Write Z FIFO 84, which stores any new Z coordinate data that passed the Z comparison test for the batch. Any valid data in the Write Z FIFO 84 is then written into RAM 45 by the RAM controller 91. Since it is possible for some or all of the Z comparisons to fail, some type of mechanism is needed to inform the RAM controller 91 when to stop looking for Z write data. Preferably, a "timeout" mechanism is used by the RAM controller 91 to determine when to stop looking for new Z write data.

The results of the Z comparison test also are written by the Z test component 73 into the Z Compare Results FIFO 58 simultaneously with the writes into the Z Write FIFO 84. The results stored in the Z Compare Results FIFO 58 are provided to the pixel modifier component 77 of both the memory controllers 41 and 42. The pixel modifier component 77 uses the Z compare results provided to it to determine whether to pass the corresponding new pixel color, which is contained in the New Pixel FIFO 75, down the pipe of the pixel modifier component 77 or whether to discard it. Any pixel color and its corresponding address that is passed through the pixel modifier component 77 ultimately is loaded into the Write Pixel FIFO 81.

When the "timeout" period mentioned above has expired and the Write Z FiFO 84 becomes empty, the RAM controller 91 switches from the Write Z FIFO 84 to the Write Pixel FIFO 81 and the new pixel colors are written by the RAM controller 91 into RAM 45. By the time the RAM controller 91 switches to the Write Pixel FIFO 81, pixel color write requests will have already been queued up so that the batch of pixel addresses and colors stored in the Write Pixel FIFO 81 are ready to be written into RAM 45.

The pixel modifier component 77 can also perform read-modify-write (RMW) operations, such as blending, on the new pixel color. RMW operations require the use of the old pixel color corresponding to the same screen coordinates as the new pixel color. To accomplish these RMW functions, the pixel address that is written by the tile builder 56 into the New Pixel FIFO 75 is also written into the Read Pixel FIFO 83. When one of these types of operations is to be performed, the RAM controller 91 will switch to the Read Pixel FIFO 83 before any switch is made to the Write Pixel FIFO 81. The old pixel color corresponding to the address stored in the Read Pixel FIFO 83 is fetched for the pixel modifier component 77. The modified pixel color is then written into the Write Pixel FIFO 81. These fetches are continued for the entire batch while modified pixel colors are queued in the Write Pixel FIFO 81. When the RAM controller 91 detects a batch delimiter in the Read Pixel FIFO 83, the RAM controller 91 will stop fetching and switch to the Write Pixel FIFO 81 and the modified pixel colors stored in the Write Pixel FIFO 81 will be stored in RAM 45.

The RAM controller 91 will continue writing new or modified pixel colors until a "write-pipe-empty" indicator (not shown) indicates completion of the current batch. When this occurs, the RAM controller 91 will switch as necessary to begin processing of the next batch.

In accordance with the preferred embodiment of the present invention, the Write Pixel FIFO 81, the Read Pixel FIFO 83, the Write Z FIFO 84 and the Read Z FIFO 86 preferably implement the FIFO architecture of the present invention having built-in intelligence for reducing paging overhead. FIG. 5 is a block diagram of the FIFO 100 of the present invention that demonstrates the ports of the FIFO 100 and information being input to or output from the ports. The FIFO 100 preferably has one input port 101 and two output ports, namely, the row output port 102 and the column output port 103. The output ports 102 and 103 function independently of one another, as described in detail below with respect to FIGS. 6-8.

The input port 101 of the FIFO 100 is connected to whatever device is feeding the FIFO 100. As shown in FIG. 4, the various FIFOs 81, 83, 84 and 86 are fed by, respectively, the pixel modifier component 77, the tile builder 56, the Z Test component 73, and the tile builder 56. The input port 101 receives a paging bit ("P-bit"), a bank bit ("bank") and row and column addresses via a bus 104. In some circumstances, depending on the implementation of the FIFO 100, commands and data will also be received at the input port 101 of the FIFO 100 via a bus 105. Control lines 107 and 108 are connected to the input port 101 of the FIFO 100 and to the device feeding the FIFO 100. Line 107 outputs a "space" indication to the device feeding the FIFO 100 indicating that the FIFO 100 has space available in it for holding more information. When the device feeding the FIFO 100 receives the "space" indication from the FIFO 100, the device feeding the FIFO 100 sends a load signal on line 108 to the FIFO 100 that causes the FIFO 100 to load the information at its input port 101.

The output port 102 of the FIFO 100 unloads the row address "ROW" and the corresponding bank of the row "b" onto bus 112 at the appropriate time, which will be discussed in detail below with respect to FIGS. 6-8. The row address and row bank are unloaded when the FIFO 100 receives the unload signal "UNLD" on line 116 from the RAM controller of memory controller utilizing the FIFO 100. The page synchronization bit "PS", the column address "COL", any commands "CMD" and data "DATA", and the corresponding column bank "COL BANK" are unloaded from the FIFO 100 onto bus 118 when the unload signal "UNLD" on line 121 is received by the FIFO 100. As stated above, in accordance with the preferred embodiment of the present invention, the FIFO 100 is implemented within the memory controllers 41 and 42 shown in FIG. 3. Therefore, in accordance with the preferred embodiment, the output ports 101 and 103 of the FIFO 100 are connected to the RAM controller within the memory controller in which the FIFO 100 is being implemented. Since the memory controllers and their respective RAM controllers preferably are identical, the FIFO 100 will only be discussed herein with respect to one RAM controller and one RAM device, namely, RAM controller 91 and RAM controller 45, as shown in FIGS. 3 and 4.

The RAM controller 91 comprises logic for determining when the information at the output port 102 should be unloaded onto bus 112 and when the information at the output port 103 of the FIFO 100 should be unloaded onto bus 118, respectively. The unloading of the information onto bus 112 is independent of the unloading of the information onto bus 118. The RAM controller 91 outputs the unload signals on lines 116 and 121 to the output ports 102 and 103 of the FIFO 100 to cause the information to be unloaded from the FIFO 100 onto buses 112 and 118. Preferably, a state machine is implemented in the RAM controller 91 for determining when the column and row addresses should be unloaded from the FIFO 100. Preferably, a first state machine for performing this task is implemented in the RAM controller 91 for transactions directed to bank0 of RAM 45, and a second state machine, which is identical to the first state machine, is implemented for transactions directed to bank1 of RAM 45. The functionality of the state machine will be discussed in more detail below with respect to FIG. 8. The purpose of the page synchronization bit (PS), ROW BANK and COL BANK will be discussed in detail below with respect to FIGS. 6-11.

FIG. 6 is a block diagram of the internal functional components of the FIFO 100 that demonstrates the built-in intelligence of the FIFO 100 for reducing paging overhead. The buses shown in FIG. 5 have been, in some cases, replaced with individual lines in order to illustrate the manner in which the information received in the FIFO 100 is utilized by the various components of the FIFO 100. The FIFO 100 comprises a row latch array 131 for storing row addresses and a main latch array 146 for storing P bits and column addresses, and for storing any commands and data that exist. The FIFO 100 also comprises a write pointer component 135, a row read pointer component 134 and a main read pointer component 153. The write pointer component 135 is utilized by both the row latch array 131 and the main latch array 146. The write pointer component 135 points to locations in the latch arrays 131 and 146 where information is to be stored. The main read pointer component 153 points to a location in the main latch array where information is stored which is to be read from the main latch array 146. The row lead pointer component 134 points to a location in the row latch array 131 where information is stored which is to be read from the row latch array 131.

The row read pointer component 134 utilizes information from three separate shift registers for determining which row address is to be transferred, as well as for determining when the row address is to be transferred, from its memory location in the row latch array 131 into a row port output register 136. These registers are shown in FIGS. 7A, 7B and 7C. The P shift register 180 shown in FIG. 7A contains the paging bits "P" for each associated row and column entry. Each paging bit contained in the register 180 indicates whether the associated address will require its specified bank in the RAM 45 to be re-paged. When the P register 180 is loaded from the bottom up, the paging bit from the input port 101 is stored via line 183 in the location in the register 180 immediately above the locations in register 180 that contain valid entries (described below) when the input is loaded into the FIFO 100. These entries are shifted down one position each time a column address is unloaded from the column port output register 138. In accordance with the preferred embodiment, a paging bit having a value of 1 indicates that re-paging will be required for the transaction whereas a value of 0 indicates that re-paging will not be required for the transaction.

In accordance with the preferred embodiment, the FIFO 100 has a depth of 16 or 32 storage locations, which requires that the shift registers also have a depth of 16 or 32 storage locations, respectively. However, it will be understood by those skilled in the art that the present invention is not limited to any particular size for the FIFO 100 or the shift registers. For purposes of simplicity, the registers in FIGS. 7A, 7B and 7C are shown as having a depth of 8 storage locations, which means that FIFO 100 will also have a depth of 8 storage locations in this exemplary illustration.

The b shift register 203 shown in FIG. 7B contains the bank bits "b" for each of the associated row and column entries. Each of the bank bits indicates whether the address is for bank0 or bank1 in the RAM 45. In accordance with the preferred embodiment, a bank bit having a value of 0 indicates that the transaction relating to the associated address is directed to bank0 whereas a bank bit having a value of 1 indicates that the transaction relating to the associated address is directed to bank1. When the b shift register 203 is loaded from the bottom up, the bank bit from the input port is stored via line 204 in the location in the register 203 immediately above the locations containing valid entries (described below) in the shift register 203 when the input is loaded into the FIFO 100. These entries are shifted down one position each time a column address is unloaded from the column port output register 138.

The V shift register 230 shown in FIG. 7C contains valid bits "V". Each of the valid bits is associated with one entry in the P shift register 180 and with one entry in the b shift register 203 and indicates whether the associated entries in the P and b shift registers 180 and 203 are valid. In accordance with the preferred embodiment, a V bit value of 0 in a storage location in the V shift register 230 indicates that the corresponding entries in the other shift registers 180 and 203 are not valid. A V bit value of 1 in a storage location in the V-bit shift register 230 indicates that the corresponding entries in the other shift registers 180 and 203 are valid. When the input port 101 is loaded, a value of 1 is stored via line 232 in the location in the register 230 immediately above the locations containing the other V bits having values of 1. These entries are shifted down one position each time a column address is unloaded from the column port output register 138.

The P bit that is loaded into the P shift register 180 is also stored in the main latch array 146 along with the column address. Each column address stored in the main latch array is associated with one entry in the P shift register 180. When a column address is unloaded from the column port output register 138, the corresponding P bit (PS) is also unloaded from the main latch array 146, which is used for paging synchronization. The manner in which the P bits, the b bits and the V bits are utilized by the FIFO 100 will now be discussed with respect to FIGS. 6-8.

FIG. 8 is a table containing entries that demonstrate the logic comprised in the intelligent FIFO 100 for reducing paging overhead. Column 262 in the table contains eight valid paging bit (P) entries. The V bits that validate these entries are not shown for ease of illustration. Each entry in column 262 of the table corresponds to a storage location in the shift register 180. For example, the P bit entry located in column 262 and row 271 of the table corresponds to the P bit stored at location 185 in the P shift register 180. Similarly, the P bit entry located in column 262 and row 282 corresponds to the P bit stored at location 196 in the P shift register 180. Therefore, the entries closer to the bottom of the table were loaded earlier in time than the entries above them in the table.

The bank (b) bit entries in the table also correspond to locations in the b-bit shift register 203. The b bit entries in column 263 of the table in the bottom four rows of the table having values of 0 correspond to transactions for bank0. The next two entries in the table in rows 274 and 276 having values of 1 correspond to transactions for bank1. The top two entries in the table in rows 271 and 272 having values of 0 correspond to transactions directed to bank0. The P bit entries having a value of 1 in column 262, rows 282, 276 and 272 of the table indicate that the RAM 45 will have to be re-paged in order to perform the transaction corresponding to the associated row addresses contained in the row latch array 131.

The CAND0 column 265 in the table corresponds to transactions that are re-paging candidates for bank0. In accordance with the preferred embodiment, a 0 in this column indicates that corresponding row address is not a re-paging candidate for a bank0 transaction and a 1 in this column indicates that the corresponding row address is a re-paging candidate for a bank0 transaction.

The CAND1 column 266 in the table corresponds to transactions that are re-paging candidates for bank1. In accordance with the preferred embodiment, a 0 in this column indicates that the corresponding row address is not a re-paging candidate for a bank1 transaction. A 1 in this column indicates that the corresponding row address is a re-paging candidate for a bank1 transaction. Alternatively, A 0 in this column could be used to indicate that the corresponding row address is not a re-paging candidate for a bank1 transaction and a 1 in this column could be used to indicate that the corresponding row address is a re-paging candidate for a bank1 transaction.

Assuming all of the entries in the P and b columns 262 and 263, respectively, are for valid transactions, as indicated by all of the entries contained in the valid shift register 230 shown in FIG. 7C being set to 1, the candidate entries in the table are those associated with the P bit having a value of 1 in column 262 of the table, rows 282, 276 and 272. Therefore, a candidate transaction is a transaction for which the corresponding paging bit and valid bit have been set to 1. The re-paging candidates are priority encoded so that only a re-paging candidate for bank0 that has no other transactions for bank0 below it in the table will continue to be considered in the row selection process. Likewise, only a re-paging candidate for bank1 that has no other transactions for bank1 below it in the table will continue to be considered in the row selection process.

The P bit having a value of 1 in column 262, row 282 indicates that the transaction associated with that entry will require re-paging and the b-bit value of 0 in column 263, row 282 indicates that bank0 will have to be re-paged in order for the transaction to be performed. These values result in a CAND0 value of 1 in column 265, row 282 of the table, indicating that the corresponding transaction is a bank0 re-paging candidate. The bank bit having a value of 1 in column 263, row 276 indicates that the corresponding transaction is for bank1. The P bit in column 262, row 276 having a value of 1 indicates that the corresponding transaction will require re-paging of bank1. These P and b-bit values result in a CAND1 value 1 in column 266, row 276 of the table, indicating that the corresponding transaction is a candidate transaction for re-paging bank1.

The bank bit having a value of 0 in column 263, row 272 indicates that the transaction is for bank0. The associated P bit in column 262, row 272 is set to 1 indicating that the corresponding transaction will require bank0 to be re-paged. The CAND0 value of 1 in column 265, row 272 indicates that the transaction is a candidate for re-paging bank0.

As stated above, once the candidates for bank0 and bank1 have been determined, the candidates are priority encoded so that only a candidate for a particular bank that has no other transactions for that bank below it in the table becomes the "dump" candidate for that bank. As shown in FIG. 8, the CAND1 entry in column 266, row 276 has a value of 1 and no other transactions for bank1 are below it in the table. Therefore, this entry is a dump candidate for bank1. However, since there are bank0 transactions below the CAND0 entry in row 272, this candidate cannot participate in the row selection process until all bank0 transactions below it in the table, namely, those corresponding to the entries in rows 282, 281, 279 and 278 of the table, have been processed. The transaction associated with the entries in row 282 of the table is a dump candidate for bank0 and, since there are no bank0 transactions below it in the table, it will continue to participate in the row selection process.

At this point in this example, there are two dump candidates remaining that can participate in the row selection process, one for bank0,namely, row 282, and one for bank1,namely, row 276. These dump candidates are priority encoded so that the one below the other in the table is finally selected. In accordance with the preferred embodiment of the present invention, the dump candidate selected, which is CAND0 in row 282 in this example, causes an offset to be generated. The magnitude of the offset depends on the position of the selected candidate in the shift registers 180, 203 and 230. Each possible position of a selected candidate will encode a particular offset value that corresponds to its position. For example, row 276 is in position 4 and will encode an offset of 4. The offset is added to the main read pointer value delivered via line 155 to the row read pointer component 134 to generate the row read pointer when the corresponding clump candidate is selected. The row read pointer component 134 addresses the row latch array 131 using this row read pointer to cause the selected row address to be dumped and transferred to the row port output register 136. It will be understood by those skilled in the art that this row read pointer can be produced in a variety of ways and that the present invention is not limited to any particular manner for generating the row read pointer.

Once the final candidate has been selected and the row address has been dumped, the corresponding P bit in the P shift register 180 is cleared so that it does not participate in the selection process a second time. Once bank0 has been re-paged for the transaction in row 282 and the row address associated with the entry in row 282 has been unloaded from the row port output register 136, the row address associated with row 276 in the table, which is for bank1, can now be selected and put into the row port output register 136. This allows bank1 to be re-paged while the transactions for bank0 corresponding to the entries in rows 281, 279 and 278 are being processed, thereby allowing the re-paging of bank1 to be "hidden."

Once all bank0 transactions below the transaction corresponding to CAND0 in row 272 are unloaded, the transaction corresponding to CAND0 row 272 can then participate in the final row selection process. Once the P bit corresponding to CAND1 in row 276 is cleared, CAND0 in row 272 can finally be selected. This allows bank0 to be re-paged while the bank1 transactions corresponding to rows 276 and 274 in the table are being processed, thereby allowing re-paging of bank0 to be "hidden."

In accordance with the preferred embodiment of the present invention, the intelligence of the FIFO 100 operates in conjunction with logic comprised in the RAM controller 91 to hide re-paging of the banks of RAM 45. Preferably, the logic comprised by the RAM controller 91 for this purpose is implemented in the form of two state machines (not shown), one for bank0 transactions and one for bank1 transactions. These two state machines function identically and, therefore, the operations of only one of the state machines will be described in detail. Also, since the state machines operate identically for bank0 and bank1, the operations of the state machine will be describe only with respect to bank0 transactions.

The state machine has three states, namely, state 0, state 1 and state 2. State 0 corresponds to the state in which no page has been opened for the bank. This state usually occurs at startup. Once a page has been opened, the state machine enters state 1. In state 1, a page has been opened, but the column address corresponding to that page has not yet been unloaded from the column port output register 138. When the corresponding column address has been output from the column port output register 138 onto bus 158, the RAM controller 91 processes the column address and the state machine enters state 2. In state 2, no column address for bank0 having a paging synchronization bit (PS) associated with it can be unloaded from the column port output register. The RAM controller 91 does, however, cause the column addresses which do not have a paging synchronization bit (PS) associated with them to be unloaded from the column port output register 138. These column addresses are then processed by the RAM controller 91. When a new row address for that bank is unloaded from the row port output register 136 onto bus 157, the state machine re-enters state 1 and waits for the corresponding column address to be unloaded from the column port output register 138.

A command dispatcher (not shown) comprised in the RAM controller 91 manages the unloading of the row port output register 136 and of the column port output register 138 by monitoring the row and column valid indicators on lines 114 and 119, the ROW BANK, the COL BANK, and the paging synchronization bit (PS), and by monitoring the state machine for each bank to determine when the information either in the row port and column port output registers is to be unloaded. Once a page has been opened, i.e., once the row address has been output from the row port output register 136 onto the bus 157, the state machine enters state 1. If the column port output register contains a valid column address having a paging synchronization bit (PS) associated with it, the command dispatcher will only unload the column port output register 138 onto bus 158 when the state machine is in state 1. The command dispatcher will only unload a column address that does not have a paging synchronization bit (PS) associated with it when the state machine for that bank is in state 2.

Once bank0 has been opened for the transaction associated with the first dump candidate in row 282, the second dump candidate, which is in row 276, is sent to the row port output register 136. Once bank1 has been opened for the transaction associated with the second dump candidate and all of the bank0 transactions below the third dump candidate have been unloaded, the third dump candidate, which is in row 272, is sent to the row port output register 136. Therefore, in the example demonstrated by FIG. 8, only three row addresses are unloaded from the row port, namely, one address for each re-paging requirement, whereas eight column addresses are unloaded namely, one for each corresponding transaction.

In accordance with an alternative embodiment of the present invention, the intelligent FIFO 100 of the present invention can have multiple batches queued in it so that when processing of the first batch is complete, processing of the second batch can begin. Preferably, the Read Z FIFO 86 and the New Z FIFO 71 are designed in accordance with this embodiment as intelligent FIFOs 100 to handle multiple batches. In accordance with the preferred embodiment, the FIFO 100 utilizes the BATCH (B) shift register 300 shown in FIG. 9 to enable the FIFO to distinguish between the current batch and the next batch to be processed. For purposes of illustration, the shift register 300 is shown as having eight storage locations for an eight word deep FIFO. However, preferably the FIFO 100 is sixteen or thirty-two words deep, requiring the B shift register 300 to have sixteen or thirty-two bits of storage locations. However, it will be understood by those skilled in the art that the present invention is not limited to any particular depth.

Each location in the shift register 300 functions as a batch ID to indicate whether a particular entry is associated with a particular batch. The batch ID is inverted for each new batch. For example, if the batch ID is 0 for the current batch, the batch ID will be one for the next batch to be processed. When the processing of the current batch is finished, the next batch becomes the current batch and the current batch will have a batch ID of 1. Therefore, the batch ID is toggled for each new batch and serves as a delimiter between batches for the selection process.

As shown in FIG. 10, the row read pointer 321 in accordance with this embodiment is very similar to the row read pointer 134 shown in FIG. 6. The row read pointer 321 also utilizes the information from the shift registers 180, 203 and 230 for determining which row address is to be transferred, as well as for determining when the row address is to be transferred, from its memory location in the row latch array 131 into a row port output register 136. The output of the row read pointer 321 is also the same as the output of the row read pointer 134. As with the row read pointer 134, the row read pointer 321 also calculates an offset that is added to the main read pointer 158. The manner in which this is accomplished is substantially identical to the manner in which the row read pointer 134 performs this task. However, the row read pointer 321 performs the selection process for selecting a dump candidate in such a way that only entries associated with the current batch participate in the selection process.

In addition to the other information received by the row read pointer 321 discussed above, the row read pointer 321 also utilizes information from the B shift register 300 shown in FIG. 9, which is indicated by line 320 in FIG. 10 and by the uppercase "B". Additionally, the row read pointer 321 also receives a "current batch" indicator 322 from the RAM controller 91. The manner in which the "current batch" indicator is utilized by the row read pointer 321 is demonstrated below with respect to the table shown in FIG. 11.

The table shown in FIG. 11 is similar to the table shown in FIG. 8 except that it contains additional columns and the entries in the tables are different. The manner in which the columns 332, 333, 335 and 336 are utilized is identical to that discussed above with respect to FIG. 8. Column 331 in FIG. 11 is the "batch" column, which corresponds to the entries in the batch shift register 300. In this example, all of the entries in the batch column 331 are 0 except for one entry having a value of 1. In this example, the current batch ID is 0. Therefore, the entry in column 331, row 346 having a value of 1 indicates that the corresponding transaction is a member of a different batch and the entry below row 346 is the last entry of the current batch. The "MEM" column 334 contains entries which correspond to a logical operation performed on the current batch ID (which is 0 in this example) input to the row read pointer 321 from the RAM controller 91 via line 322 and the transaction batch ID's (B) input into the row read pointer 321 via line 320. An exclusive NOR (XNOR) operation is used to compare each Transaction batch ID (B) with the current batch ID to generate a MEM entry for that transaction. Therefore, the entries in column 334, rows 352, 351, 349 and 348 are all 1s because the current batch ID provided from the RAM controller 91 is 0 and the batch ID provided from the B shift register 300 is 0, as indicated by the entries in rows 352, 351, 349 and 348 in column 331.

The entry in column 331, row 346 is a 1, but the current batch ID from the RAM controller 91 continues to be 0. Therefore, the result of the XNOR operation is 0, as shown in the MEM column 334, row 346. This 0 entry indicates that the transaction corresponding to the entry in column 331, row 346 is not part of the current batch. This 0 entry in the MEM column 334 causes inhibit signals, denoted as INH0 and INH1 in columns 338 and 339, to be generated. These inhibit signals prevent any row address corresponding to candidates above this entry in the table from being sent to the row port output register 136 until the entries above this entry actually become members of the current batch. Only paging candidates from the lower four locations (candidate in row 352 for this example) will be sent to the row port. The CAND1 entry in column 336, row 344 having a value of 1 will not be sent to the row port output register 136 until the transactions corresponding to the bottom five entries in the table have been processed. Once the lower four transactions corresponding to the current batch have been unloaded, the RAM controller 91 will toggle the current batch ID to 1 allowing the fifth transaction, row 346, with a batch ID of 1 to become a member of the current batch. Once this transaction is unloaded, the RAM controller 91 will toggle the current batch ID back to 0 allowing the top four entries to become members of the current batch.

The entries in column 333 also cause the inhibit signals to be generated. Valid entries for bank0 cause inhibit 0 (INH0) signals to be generated as shown in column 338, rows 352, 351, 349 and 348, which prevent any bank0 row addresses corresponding to entries above these entries from being sent to row port output register 136. However, since these entries do not involve bank1, bank1 is not inhibited, as indicated by the 0s in column 339, rows 352, 351, 349 and 348.

Similarly, valid entries for bank1 cause an inhibit 1 (INH1) signal to be generated as shown in column 339, rows 344, 342 and 341, which prevents any bank1 row addresses corresponding to entries above these entries from being sent to the row port output register 136. Since these entries do not involve bank0, bank0 is not inhibited, as indicated by zeros in column 338, rows 344, 342, and 341.

It should be noted that the present invention has been described with respect to the preferred embodiments, but that the present invention is not limited to these embodiments. The preferred embodiments have been discussed in order to demonstrate the present invention, but it will be understood by those skilled in the art that the present invention can be implemented in a variety of ways to achieve the results of the present invention discussed above with respect to the preferred embodiments. It will also be understood by those skilled in the art that the intelligent FIFO 100 of the present invention is not limited to use in graphics memory systems and that it has been discussed in the context of such a system merely to demonstrate the advantages of the intelligent FIFO 100 and its preferred use.

## Claims

1. a first-in-first-out (FIFO) memory device comprising: entries from an input port of the FIFO memory device and storing each of the entries of the first set in a storage location in the first memory element addressed by a write pointer device; of entries from the input port of the FIFO memory device and storing each of the entries of the second set in a storage location in the second memory element addressed by the write pointer device; first read pointer addresses in the first memory element, the first read pointer addresses being used to address storage locations in the first memory element for reading entries of the first set of entries out of storage locations in the first memory element, the entries read out of the first memory element being output from the FIFO memory device via a first output port of the FIFO memory device; and whether any of the entries of the second set are tagged entries, the second read pointer device calculating second read pointer addresses based on any tagged entries in the second set, the second read pointer device using the second read pointer addresses for reading the tagged entries of the second set out of their respective storage locations in the second memory element, the tagged entries read out of the second memory element being output from the FIFO memory device via a second output port of the FIFO memory device.

2. The FIFO memory device of claim 1, wherein when the second read pointer device determines that an entry of the second set of entries is a tagged entry, the second read pointer device calculates an offset, the value of the offset being based on the entry determined to be a tagged entry, the offset being added to one of the first read pointer addresses to generate one of the second read pointer addresses, wherein the second read pointer address generated corresponds to the storage location in the second memory element where the entry determined to be a tagged entry is stored.

3. The FIFO memory device of claim 2, wherein the second read pointer device prioritizes the tagged entries so that a tagged entry having a highest priority is output from the second output port of the FIFO memory device before a tagged entry having a lower priority is output from the second output port of the FIFO memory device.

4. The FIFO memory device of claim 3, wherein before a tagged entry having a highest priority is output from the second output port of the FIFO memory device, the tagged entry having the highest priority is sent to a port output register of the second latch array, wherein the tagged entry in the port output register is output from the FIFO memory device via the second output port when an unload signal is received by the second read pointer device from a controller which is external to the FIFO memory device.

5. The FIFO memory device of claim 4, wherein each of the entries of the first set stored in the first memory element is associated with one entry in the second memory element, wherein before an entry stored in the first memory element is output from the FIFO memory device via the first output port, the entry to be output is stored in a port output register of the first memory element, wherein the entry stored in the port output register of the first memory element is output from the FIFO memory device via the first output port when an unload signal is received by the first read pointer device from the controller, wherein the associated entry in the port output register of the second memory element is output to the second output port before the associated entry in the port output register of the first memory element is output from the first output port.

6. The FIFO memory device of claim 5, wherein one of the entries of the first set that is associated with a tagged entry of the second set is also tagged, and wherein the controller determines whether the entry contained in the port output register of the first memory element is a tagged entry and only sends the unload signal to the first read pointer device after an associated tagged entry contained in the port output register of the second memory element has been unloaded from the port output register of the second memory element and output from the FIFO memory device via the second output port.

7. The FIFO memory device of claim 2, wherein the FIFO memory device is implemented in a graphics memory system, the FIFO memory device being used in the graphics memory system to access a frame buffer memory device, the frame buffer memory device comprising a memory bank0 and a memory bank1, the first set of entries corresponding to column addresses in the frame buffer memory device, the column addresses comprising bank0 column addresses and bank1 column addresses, the second set of entries corresponding to row addresses in the frame buffer memory, the row addresses comprising bank0 row addresses and bank1 row addresses, wherein each of the row addresses is tagged with a bank bit which indicates whether the row address tagged with the bank bit is a bank0 row address or a bank1 row address, and wherein each bank0 row address is tagged with a paging bit which indicates whether the bank0 row address tagged with the paging bit will require bank0 to be re-paged, and wherein each bank1 row address is tagged with a paging bit which indicates whether the bank1 row address tagged with the paging bit will require bank1 to be re-paged, wherein only the bank0 and bank1 row addresses that are tagged with paging bits are output from the FIFO memory device via the second output port of the FIFO memory device.

8. The FIFO memory device of claim 7, wherein the second read pointer device prioritizes the tagged entries in accordance with a row address selection process by determining which of the bank0 row addresses stored in the second memory element that has been tagged with a paging bit has no other bank0 row addresses ahead of it in the second memory element to thereby identify a bank0 dump candidate, by determining which of the bank1 row addresses stored in the second memory element that has been tagged with a paging bit has no other bank1 row addresses ahead of it in the second memory element to thereby identify a bank1 dump candidate, and by determining which of the dump candidates has a highest priority to thereby select one of the dump candidates, the offset being calculated based on the storage location of the selected candidate in the second memory element, and wherein the row address generated using the offset is sent to the port output register of the second memory element and the paging bit corresponding to the selected candidate is cleared and the selection process is repeated to identify a next selected candidate, and wherein when an unload signal is received by the second read pointer device from the controller, the row address contained in the port output register of the second memory element is output from the port output register of the second memory element via the second output port and the row address corresponding to the next selected candidate is sent to the port output register of the second memory element.

9. The FIFO memory device of claim 8, wherein the controller is a RAM controller that controls accessing of bank0 and bank1 of the frame buffer memory device.

10. The FIFO memory device of claim 9, wherein each row address that is tagged with a paging bit has a column address associated with it that is tagged with a page synchronization bit, and wherein the first read pointer addresses generated by the first read pointer device cause the column addresses to be read out of their respective locations in the first memory element in first-in-first-out order and loaded into the port output register of the first memory element, and wherein the RAM controller determines whether the column address contained in the port output register of the first memory element has been tagged with a page synchronization bit and sends an unload signal to the first read pointer device, the unload signal being sent to the first read pointer device after the row address contained in the port output register of the second memory element that is associated with the tagged column address has been unloaded from the port output register of the second memory element and output from the FIFO memory device via the second output port.

11. The FIFO memory device of claim 9, wherein each row address stored in the second latch array has a batch indicator associated with it, the second read pointer device using the batch indicator to determine whether the row address associated with the batch indicator is a row address in the current batch, wherein the second read pointer device only sends row addresses to the port output register of the second latch array that are in the current batch.