Computer graphics processing and selective visual display system – Computer graphics display memory system – For storing condition code – flag or status
Reexamination Certificate
1999-03-10
2002-08-13
Tung, Kee M. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics display memory system
For storing condition code, flag or status
C345S558000
Reexamination Certificate
active
06433787
ABSTRACT:
BACKGROUND AND SUMMARY OF THE INVENTION
The present invention relates to processing information received from a microprocessor, particularly to reordering out-of-order data by means of a table structure.
Background: First-In, First-Out (FIFO) Structures
FIFO structures are used in computers for various functions such as buffering and pipelining. A FIFO structure is one in which the first object put into the structure is also the first object that must come out. A physical example is rolling marbles through a pipe. The first marble that goes into the pipe is also the first one that must come out the other end. Thus the pipe can be thought of as a FIFO structure.
Background: Video Graphics Terminals
Since the first computer display was attached to MIT's Whirlwind computer in 1950, enormous advances have been made in the systems generating graphical pictures and in the display hardware which enables users of the system to view and interact with the pictures. Because the graphics display forms a large part of the physical user interface of the system, the evolution of display technology has been a major contributing factor in the growth of the computer industry.
Video graphics terminals, also known as graphics displays, show pictures and text. Familiar examples are computer monitors or television sets. Visually, one may think of a screen of the video display as constructed of many small “dots” called pixels. The smallest object that can be shown on the video display screen is one pixel.
A modern computer monitor, for example, may have a rectangular screen 1,280 pixels wide by 1,024 pixels high. Therefore the screen would contain over one million pixels (1,024×1,024). In a video terminal, each pixel generally requires storage or transmission of data about its properties, such as its color and brightness. For some computer monitors, a pixel's properties may be stored in one byte. Because one byte usually allows only 256 color choices, other monitors a and graphics processors may use more than one byte of memory to store information about a pixel. In any event, more than one million bytes might have to be transmitted over a computer bus to update a 1280×1024 computer screen one time. The computer screen might be updated thirty times each second if full-motion video is displayed. This means that at least thirty million bytes of pixel information might cross the computer bus every second for display of full-motion video.
Background: Write-Combine-Operations
Sending thirty million bytes of pixel information per second over the computer bus is not desirable because it ties up the bus. The computer cannot use the bus for other purposes while the pixel-bytes are being transmitted. For example, on a 66 MHz byte-wide bus, almost half the available transmission capability would be used. Further complicating the matter is the fact that each pixel-byte usually has “overhead” bytes transmitted along with it. The “overhead” bytes contain addressing information to make sure that the pixel-byte gets to the correct destination. The overhead bytes use even more of the bus transmission capability, leaving little or no room for the computer's other communication needs.
One solution to the problem of these extra “overhead” bytes is to chain several related pixel-bytes together and transmit them in one transaction (known as a burst transaction). This is called write-combining because several individual bus writes have been combined into one bus write. The number of pixel-bytes is not reduced but the number of “overhead” bytes is reduced. A write-combine transmission may only require the same number of overhead bytes as a single pixel-byte transmission. As an example, currently some microprocessors may combine thirty-two pixel-bytes into one write-combine transmission. Thus thirty-two pixel-bytes are transmitted with approximately a ninety-seven percent reduction in “overhead” bytes.
The individual pixel-bytes are stored, one at a time, in a write-combine buffer. When certain conditions are satisfied, the contents of the buffer are evicted onto the computer bus. One feature of write-combine buffers, for example in the INTEL PENTIUM II architecture, is that if the size of the write-combine buffer is larger than the size of a discrete transfer on a bus, the order in which contents of the buffer are evicted to the bus is generally undefined. In essence, this means that the contents of the buffer are not necessarily put on the bus in the order in which they were written.
This re-ordering of the write-combine buffer contents generally does not matter when writing to memory, such as a frame buffer, because the final result will be the same. However, the re-ordering becomes important when writing to a FIFO buffer because the output of the FIFO must be used in sequence. In other words, when writing to an array of memory such as a frame buffer, the write order doesn't necessarily matter because the memory may only be accessed after all the writes are finished. When writing to a FIFO, order matters because the current output must be used sequentially before the next one becomes available (returning to the pipe example, the marble showing at the end of the pipe must be removed before the next one can come out).
FIG. 2
displays a typical write-combine buffer, as implemented in an INTEL PENTIUM PRO processor. In the embodiment shown, a write-combining buffer
200
is comprised of a single line having a data portion
210
, a tag portion
220
and a validity portion
230
. The data portion
210
can store up to 32 bytes of user data. The validity portion
230
is used to store valid bits corresponding to each data byte of data portion
210
. The valid bits indicate which of the bytes of data portion
210
contain useful data.
When a microprocessor writes to a location in a write-combine buffer that is already occupied, the contents of the buffer are evicted. Some eviction (aka flushing) schemes, such as employed by the INTEL PENTIUM PRO, allow for partial eviction of the write-combine buffer. For example, instead of evicting the contents of its entire 32 byte buffer, a microprocessor may only evict 8 bytes. What this means is that it is possible for writes to be evicted to the bus out-of-order. The evicted 8 bytes in the example above could “jump” ahead of other contents of the write-combine buffer.
Background: Frame Buffers
A frame buffer is memory that contains a digital representation of an image to be displayed on a monitor. A typical frame buffer will contain one byte of color information about each pixel in the monitor screen. A microprocessor writes the image data into the frame buffer, creating a virtual image. When the frame buffer is filled, the virtual image is output to the monitor through video circuitry to produce a viewed image on the monitor. Because the frame buffer is not used until it is full, it does not matter in what sequence the pixel color bytes are written to the frame buffer.
Background: Memory-mapped I/O
A common method for microprocessors to communicate with Input-Output (I/O) devices is memory-mapping. Essentially memory-mapped I/O means that certain areas of a microprocessor's memory address space are reserved for communications with I/O devices. A video graphics card is one example of an I/O device that is generally memory-mapped. For the purpose of writing data, memory-mapping allows the microprocessor to treat the I/O device as if it were memory.
Background: Graphics Processors
Originally, calculations needed to display graphics were handled exclusively by the microprocessor. As video graphics demands became greater, the microprocessor devoted a larger percentage of its time to handling graphics calculations. To ease this burden on the to microprocessor, a separate graphics processor is generally used to handle graphics calculations.
The graphics processor is often a memory-mapped device. When writing to a graphics processor, microprocessors typically “see” the graphics processor as frame buffer memory. This means that the microprocessor “thinks” th
LandOfFree
Dynamic write-order organizer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic write-order organizer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic write-order organizer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2973314