Electrical computers and digital processing systems: memory – Storage accessing and control – Access timing
Reexamination Certificate
2001-06-29
2004-10-12
Portka, Gary (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Access timing
C711S158000, C710S039000, C710S040000
Reexamination Certificate
active
06804758
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method for adaptive arbitration of requests for memory access in a multi-stage pipeline engine, more particularly to a method for adaptive arbitration of requests for accessing a memory unit in a multi-stage pipeline engine that can reduce the occurrence of idling or stalling in the multi-stage pipeline engine.
2. Description of the Related Art
A pipeline architecture is commonly found in integrated circuit designs. When processing 3D graphic digital data, generation of 3D graphics includes the steps of geometry and image rendering. Since movement and operation of a large amount of pixel data are needed during processing, a 3D pipeline engine is utilized for increasing throughput of 3D commands.
Referring to
FIG. 1
, a conventional n-stage pipeline engine
10
includes an arbiter
110
, a memory unit
12
for storing different types of data, such as red, green and blue pixel values, alphavalue, Z value, texture data, etc., and a plurality of request queues
131
,
131
′,
131
″ and data buffers
130
,
130
′,
130
″ for increasing efficiency of the n-stage pipeline engine
10
. The different types of data are accessed in different stages of the n-stage pipeline engine
10
. For each request of data access, one of the request queues and a corresponding one of the data buffers are used. The request queue and the corresponding data buffer can be located in different stages, such as the request queue A
131
and the data buffer A
130
, and the request queue B
131
′ and the data buffer B
130
′, or in the same stage, such as the request queue C
131
″ and the data buffer C
130
″, of the n-stage pipeline engine
10
.
In the example of
FIG. 1
, the second and (n−3)
th
stages in the n-stage pipeline engine
10
have the request queue A
131
and the request queue B
131
′, respectively, for storing a request therein. When the arbiter
110
serves the request, data associated with the request are read from the memory unit
12
. The fourth and (n−2)
th
stages in the n-stage pipeline engine
10
have the data buffer A
130
and the data buffer B
130
′, respectively, for storing the data that is associated with the request. The n
th
stage in the n-stage pipeline engine
10
has the request queue C
131
″ and the data buffer C
130
″. When the memory unit
12
is busy or in a memory bound state, the data buffer C
130
″ stores data to be written to the memory unit
12
so as to minimize stalling while waiting for data access. Furthermore, when the operational speed of the second stage in the n-stage pipeline engine
10
is faster than that of the third stage in the n-stage pipeline engine
10
, the output data from the second stage cannot be received instantly by the third stage, thereby resulting in stalling at the second stage. Therefore, a data buffer, such as a pixel FIFO
15
, which is located between the second and third stages, is used to store pixel data from the second stage to minimize stalling at the second stage.
The arbiter
110
assigns a fixed priority to the request queues
131
,
131
′,
131
″ in a known manner. The order of the request queues
131
,
131
′,
131
″ is determined according to locations of the corresponding data buffers in the n-stage pipeline engine
10
. The arbiter
110
assigns the high-priority request queue to that whose associated data buffer is located farthest from an upstream end of the n-stage pipeline engine
10
. The following are some of the drawbacks of the fixed priority scheme of the arbiter
110
:
1. Since the arbiter
110
does not consider the nature of memory requests and the state of the memory unit
12
, reduced utilization of the memory unit
12
can result.
2. Since the arbiter
110
assigns a fixed priority to minimize stalling of the n-stage pipeline engine, bubbling (many stages in the n-stage pipeline engine
10
are idle) may occur when a data buffer located in an upstream side of the n-stage pipeline engine
10
is empty and another data buffer located in a downstream side of the n-stage-pipeline engine
10
is not empty. Referring to
FIG. 1
, when the data buffer B
130
′ located in the (n−2)
th
stage is empty and the data buffer C
130
″ located in the n
th
stage is not empty, the arbiter
110
processes data stored in the data buffer C
130
″ until the data buffer C
130
″ is empty, thereby resulting in idling of the (n−2)
th
stage. When the data buffer C
130
″ is empty, due to the idling of the (n−2)
th
stage that results in the data buffer B
130
′ still being empty, the (n−1)
th
, n
th
stages will be idle.
SUMMARY OF THE INVENTION
Therefore, an object of the present invention is to provide a method for adaptive arbitration of requests for memory access in a multi-stage pipeline engine that can reduce the occurrence of idling or stalling in the pipeline engine.
According to the present invention, a method is adapted for adaptive arbitration of requests for accessing a memory unit in a multi-stage pipeline engine that includes a plurality of request queues corresponding to the stages of the pipeline engine. The method comprises the steps of:
(a) assigning each of the request queues to one of a high-priority group and a low-priority group in accordance with an operating state of the memory unit; and
(b) processing the request queues in the high-priority group prior to the request queues in the low-priority group.
REFERENCES:
patent: 4855904 (1989-08-01), Daberkow et al.
patent: 5222223 (1993-06-01), Webb et al.
patent: 6321233 (2001-11-01), Larson
patent: 6564304 (2003-05-01), Van Hook et al.
Liao Ming-Hao
Pai Hung-Ta
Chan Raymond Y.
David & Raymond Patent Group
Portka Gary
XGI Technology Inc.
LandOfFree
Method for adaptive arbitration of requests for memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for adaptive arbitration of requests for memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for adaptive arbitration of requests for memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3282205