Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-06-10
2004-07-20
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S105000, C711S154000, C345S530000, C345S536000, C345S539000, C345S540000, C345S558000, C345S559000, C345S564000, C345S613000, C345S614000
Reexamination Certificate
active
06766410
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to computer systems. More particularly, the present invention relates to a system and method of processing graphics-related data through re-ordering fragment data based on rasterization direction to line up with a DDR-SDRAM addressing order.
2. Description of the Related Art
In traditional graphics rendering, the last stage of rendering is referred to as rasterization. The rasterization stage of rendering converts transformed primitives into pixel values, and generally stores them in a frame buffer. Rasterization requires the calculation of each primitive's contribution to each pixel. In a software rendering system, rasterization can be performed in two orders: primitive by primitive (object order), or pixel by pixel (image order). Most systems rasterize in object order, using a z-buffer algorithm to computer visibility.
In high data rate applications such as graphics rendering, processing data is preferably handled through fast data transfer components, such as a Double-Data-Rate (DDR) Synchronous Dynamic Random Access Memory (DDR-SDRAM or DDR). A DDR SDRAM differs from a standard DRAM (or SDRAM) in that it uses a separate strobe signal by which some or all of its data timing is referenced, and both the rising and the falling edges of the strobe signal are used to clock data into its destination. Using both edges of the strobe signal to transfer data thus doubles the amount of data transferred in a given time interval.
In rasterization with a DDR SDRAM, a problem arises in that the DDR SDRAM is only provided one address per clock cycle. Accordingly, the data received from the DDR SDRAM will typically come from the first address (n) and then from the next logical address (n+1). However, in some applications, the data does not logically flow from the addresses n to n+1, and the second data fragment read on the trailing edge clock signal will be discarded. This problem is particularly acute in graphics rendering because different kinds of objects are being drawn which are not likely to have pure linear or otherwise intuitive data flow, or in other words, the objects may not be drawn in the same direction during rendering. The speed advantage of a DDR SDRAM can thus be lost in a graphics rendering application because the data read at n+1 is not the correct data required following the read of n and the data fragment read from n+1 must be flushed from the pipeline.
Accordingly, it would be advantageous to provide a system and method that increases efficiency though providing accurate data from the DDR SDRAM when a processor is drawing in a direction not well oriented to the DDR SDRAM addressing. Such system and method should be compatible with the rasterization data in graphics rendering whereby the data fragments can be reordered such that the correct data fragment is present at the read occurring on the trailing edge of the clock signal. It is to the provision of such a system and method of reordering data fragments that the present invention is primarily directed.
SUMMARY OF THE INVENTION
The present invention is a system and method for reordering data fragments to facilitate reads from a DDR SDRAM where the data fragments are placed into a first and second data fragment buffer such that the data fragments are in sequential addresses whereby the second data read on the trailing edge of the DDR SDRAM clock cycle will read the proper data fragment. In particular, the system includes a first data fragment buffer (n) and a second data fragment buffer (n+1), and upon presentation of a first data fragment having an address and second data fragment having an address, the system compares the first data fragment address with the second data fragment address and if the second data fragment address is the next sequentially readable data address after the first data fragment address, the system stores the first data fragment in the first data fragment buffer and the second data fragment in the second data fragment buffer. Or, if the second data fragment address is sequentially readable before the first data fragment address, the system stores the second data fragment in the first data fragment buffer and the first data fragment in the second data fragment buffer. Otherwise, if the first data fragment address and second data fragment address are non-sequentially readable, the system flushes the first (oldest) data fragment.
The system preferably flushes the first and second data fragments once they are stored in sequential order and obtains a new first and second fragment for comparison. Alternately, the system can also flush solely the first data fragment once stored, make the second data fragment the first data fragment, and obtain a new data fragment. In other words, when the second data fragment is stored in the second data fragment buffer (n+1), the system can make the second data fragment the first data fragment prior to obtaining a new data fragment to become the second data fragment. Otherwise, if the system stores the second data fragment in the first data fragment buffer (n) and stores the first data fragment in the second data fragment buffer (n+1), it can likewise make the second data fragment the first data fragment and iterate the reordering process and obtain a new second data fragment. However, the system preferably flushes both fragments upon proper sequential ordering of the fragments in the data buffers and obtains two new fragments to become the first and second data fragments and iterates the ordering process.
The first and second data fragment buffers are preferably first-in-first-out buffers. Moreover, the DDR SDRAM can read data directly from the first data fragment buffer and second data fragment buffer, or the first data fragment buffer and second data fragment buffer can each store data fragments in another storage location, prior to the data fragments being read from a DDR SDRAM.
The present invention further provides a method for reordering data fragments to facilitate reads from a DDR SDRAM using a first data fragment buffer and a second data fragment buffer including the steps of presenting a first data fragment having and address where the first data fragment is intended to be read by a DDR SDRAM, presenting a second data fragment having an address where the second data fragment is intended to be read by a DDR SDRAM, and comparing the first data fragment address with the second data fragment address. If the second data fragment address is the next sequentially readable data address after the first data fragment address, the method includes the step of storing the first data fragment in the first data fragment buffer and the second data fragment in the second data fragment buffer. And if the second data fragment address is sequentially readable before the first data fragment address, the method includes the step of storing the second data fragment in the first data fragment buffer and the first data fragment in the second data fragment buffer. Otherwise, if the first data fragment address and second data fragment address are non-sequentially readable, the method includes the step of flushing the second data fragment. The method further preferably includes the step of obtaining new data fragments to become the first and second data fragments after the data fragments have been stored in the first and second buffers.
Preferably, upon the step storing the second data fragment in the first data fragment buffer and the first data fragment in the second data fragment buffer, the method further includes the step of either flushing the first and second data fragment and obtaining two new fragments for comparison and sequencing, or making the second data fragment the first data fragment prior to obtaining a new data fragment to become the second data fragment. If so embodied, the steps of storing the first data fragment and second data fragment are storing the first data fragment and second data fragment in first first-in-first-out buffer
3Dlabs Inc. Ltd.
Arnall Golden & Gregory LLP
Truong Bao Q.
Wang Li K.
LandOfFree
System and method for reordering fragment data based upon... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for reordering fragment data based upon..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for reordering fragment data based upon... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3237082