Arbitrating FIFO implementation which positions input...

Details Arbitrating FIFO implementation which positions input... Arbitrating FIFO implementation which positions input...

1998-09-11

2001-06-26

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output access regulation

C710S040000, C710S054000, C710S244000, C711S158000

Reexamination Certificate

active

06253262

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The present invention relates generally to a graphics processing system and more particularly relates to a system and method for ordering a request for access to a system memory using a re-ordering buffer or FIFO.
BACKGROUND OF THE INVENTION
Computer applications are continuously being developed and many of these application are utilizing three dimensional (3-D) graphics. Providing the necessary lifelike 3-D graphics requires a continuous series of processor-intensive geometry calculations which delineate the position of an object in 3-D space. Generally, such calculations are performed by a system processor which is capable of executing the necessary floating point operations. Simultaneously, a graphics controller must process texture data in order to generate surfaces and shadows to make the object appear three dimensional. One important aspect of processing the texture data is the processing of texture maps, which are bit maps that describe the surfaces of the objects.
Texture map processing may include the retrieval of texels (e.g., texture elements) from a bit map, averaging the texels together based on a mathematical approximation of the location of the object which is needed in the image to generate data constituting a pixel, and writing the resulting pixel data as a frame to a local memory such as a frame buffer. The processing of texture maps was previously provided in a computer system
10
as illustrated in prior art FIG.
1
and involved five basic steps.
At Step
1
, texture maps are read from a memory
12
such as a hard drive or disk drive into a system memory
14
via a bus
16
(such as a PCI bus) and a logic chip
18
(often called the core logic). When the texture map is to be used in Step
2
, it is read from the system memory
14
into a CPU
20
which executes point-of-view type transformations on the texture map data and stores the results in cache. In Step
3
, additional transforms, such as lighting and view point transforms, are applied to the cached texture map data and subsequently written back to the system memory
14
. At Step
4
, a graphics controller
22
reads the transformed texture data from the system memory
14
and writes it to a local video memory
24
such as a frame buffer over the PCI bus
16
. At Step
5
, the graphics controller
22
reads the texture data plus two dimensional color information from the frame buffer
24
and provides a frame which is written back to the frame buffer
24
. The frame data is then read by a D/A converter within the graphics controller
22
to drive a display
26
with a 3-D image.
The prior art system
10
of processing texture maps has several undesirable features. First, texture data must be stored in both the system memory
14
and the frame buffer
24
, thus resulting in redundant copies of the texture data and an inefficient utilization of memory resources. Second, the storing of the texture data in the frame buffer
24
limits the size of the texture data which is undesirable since demand is growing for more highly detailed textures which necessitates an expensive increase in the size of the frame buffer memory. Lastly, the bandwidth of the PCI bus
16
is limited to 132 Mbytes/second which limits the rate at which the texture map data can be transferred from the system memory
14
to the graphics controller
22
. In addition, since various subsystems also utilize the PCI bus
16
, the transfer of texture data must share the available PCI bandwidth, thus further limiting the 3-D graphics performance.
To address the above concerns with 3-D graphics performance, the PC platform now includes an accelerated graphics port (AGP) architecture. AGP relieves the above-described graphics bottleneck by adding a dedicated, high speed bus
30
between the core logic
18
and the graphics controller
22
, as illustrated in the system
32
of prior art FIG.
2
. The addition of the AGP bus
30
removes the bandwidth intensive 3-D and video traffic from the limitations of the PCI bus
16
. In addition, AGP allows the texture data to be accessed directly by the graphics controller
22
from the system memory
14
rather than being prefetched to the frame buffer
24
, thus requiring fewer texture maps to be stored in the local memory and eliminating the size constraints on the texture data.
In addition to the above benefits, the AGP bus
30
supports a data transfer rate of 533 Mbytes/second as opposed to 132 Mbytes/second by using both the rising and falling edges of the clock and managing the data transfer more efficiently. Furthermore, the texture data in the system memory
14
is dynamically allocated which enables the graphics controller
22
to see a virtual continuous space in the system memory
14
when in fact the pages are disjointed. This allocation allows the graphics controller
22
to access the texture data more efficiently. Consequently, AGP has been widely adopted and greatly improves the 3-D graphics performance.
The ordering rules for the processing of requests by the graphics controller in AGP differ from the CPU and PCI ordering rules. AGP supports two levels of access priority: high priority and low priority. For high priority requests, write and read requests are ordered separately. Consequently, the ordering of high priority read requests are made only with respect to other high priority read requests. Similarly, the ordering of high priority write requests are made only with respect to other high priority write requests and high priority read and write requests are handled independently. Low priority requests, however, are handled differently than the high priority requests. For low priority transactions, there is a relationship between read and write requests; particularly, write data is allowed to pass previously queued low priority read requests (e.g., read requests “push” write requests).
In order to implement the above AGP ordering rules, four separate queues are utilized in the control logic, wherein the queues store the high priority read requests, high priority write requests, low priority read requests and low priority write requests, respectively, as illustrated in prior art FIG.
3
. As illustrated in prior art
FIG. 3
, the core logic
18
includes four separate access request queues
32
,
34
,
36
and
38
, respectively. New access requests are stored in the appropriate queue according to its status (i.e., whether a read or a write request and whether the request is a high priority or a low priority request). Each queue
32
,
34
,
36
and
38
outputs its associated access request to an arbitration circuit
40
its earliest request, respectively (each queue operating as a first-in, first-out (FIFO) memory) and the arbitration circuit
40
uses the above-discussed ordering rules to select the proper access request. The post-queue arbitration methodology, however, results in an extra clock cycle of latency which degrades the performance of the 3-D data transfers.
It would be desirable to implement the AGP ordering rules without the disadvantages of the prior art.
SUMMARY OF THE INVENTION
The present invention is directed to a system for automatically ordering a request for access to a system memory. The system includes a re-ordering buffer and a set of pointers which identify the location for entry of a new access request based on whether the request is a high priority or a low priority request. Therefore arbitration of access requests is dynamically performed while being queued in a single buffer instead of having multiple queues for different priorities and performing arbitration after requests are enqueued as in the prior art. The present invention thus eliminates an extra buffer, saves silicon space and eliminates a clock cycle of latency due to the elimination of the post-queue arbitration logic.
According to one aspect of the present invention, the re-ordering buffer or FIFO has a data input and a data output. Associated with the re-ordering buffer are a set of pointers, a high priority pointer and a low priority pointer, which indicat

Affiliated with

Also associated with

Rating

Arbitrating FIFO implementation which positions input... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Arbitrating FIFO implementation which positions input..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitrating FIFO implementation which positions input... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2486724