Abstract:
In a method 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, each of the request queues is assigned to one of a high-priority group and a low-priority group in accordance with operating state of the memory unit. The request queues in the high-priority group are then processed prior to the request queues in the low-priority group.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    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.  
           [0003]    2. Description of the Related Art  
           [0004]    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.  
           [0005]    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 .  
           [0006]    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.  
           [0007]    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 :  
           [0008]    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.  
           [0009]    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.  
           [0010]    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  
         [0011]    Therefore, the 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.  
           [0012]    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:  
           [0013]    (a) assigning each of the request queues to one of a high-priority group and a low-priority group in accordance with operating state of the memory unit; and  
           [0014]    (b) processing the request queues in the high-priority group prior to the request queues in the low-priority group.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]    Other features and advantages of the present invention will become apparent in the following detailed description of the preferred embodiment with reference to the accompanying drawings, of which:  
         [0016]    [0016]FIG. 1 is a schematic circuit block diagram illustrating a conventional n-stage pipeline engine;  
         [0017]    [0017]FIG. 2 is a flow chart illustrating how an arbiter of the pipeline engine assigns the request queues into a high-priority group and a low-priority group in the preferred embodiment of a method for adaptive arbitration of requests for memory access according to this invention;  
         [0018]    [0018]FIG. 3 is a flow chart illustrating how the arbiter processes the request queues when the memory unit is in a memory bound state in accordance with the method of the preferred embodiment; and  
         [0019]    [0019]FIG. 4 is a flow chart illustrating how the arbiter processes the request queues when the memory unit is not in the memory bound state in accordance with the method of the preferred embodiment. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0020]    The preferred embodiment of a method according to the present invention is shown in FIGS.  2  to  4 . The method of the preferred embodiment is to be applied to the conventional n-stage pipeline engine  10  shown in FIG. 1, and is adapted for adaptive arbitration of requests for accessing the memory unit  12  in the conventional n-stage pipeline engine  10 .  
         [0021]    Referring to FIG. 2, there is shown a flow chart to illustrate how the arbiter  110  assigns the request queues to one of a high-priority group and a low-priority group according to the method of the preferred embodiment. In step  20 , the arbiter  110  detects whether the memory unit  12  is in a memory bound state. Then, in step  21 , when the memory unit  12  is in the memory bound state, the arbiter  110  detects whether a number of requests in each of the request queues  131  is greater than a predetermined threshold. The detection is conducted from a downstream end of the pipeline engine  10  to an upstream end of the pipeline engine  10 . In step  22 , for the request queues  131  that have the number of requests therein greater than the predetermined threshold, the arbiter  110  assigns such request queues  131  to the high-priority group. In step  22 , for the request queues  131  that have the number of requests therein not greater than the predetermined threshold, the arbiter  110  assigns such request queues  131  to the low-priority group. It is noted that the predetermined threshold can vary for the different request queues in the method of the preferred embodiment. In step  24 , when the memory unit  12  is not in the memory bound state, the arbiter  110  detects whether a service waiting time for each of the request queues  131  is greater than a predetermined waiting threshold. The detection is conducted from a downstream end of the pipeline engine  10  to an upstream end of the pipeline engine  10 . If yes, the flow proceeds to step  22 . In step  25 , after step  24 , for the other request queues that have the service waiting time thereof not greater than the predetermined waiting threshold, the arbiter  110  detects whether a volume of data associated with each of the other request queues, is greater than a predetermined volume threshold. If yes, the flow goes to step  22 . Otherwise, the flow proceeds to step  23 . It should be noted that the predetermined waiting and volume thresholds can be designed so as to be different for the different request queues in the method of the preferred embodiment.  
         [0022]    If the priority of a queue is changed, the queue is added to the respective priority group behind the last queue in said priority group. Otherwise, the queue maintains its position in the original priority group. Referring to FIG. 3, there is shown a flow chart to illustrate how the arbiter  110  processes the request queues  131  when the memory unit  12  is in the memory bound state according to the method of the preferred embodiment. In step  30 , the arbiter  110  initially inspects whether the high-priority group is empty. Then, in step  31 , when the high-priority group is not empty, the arbiter  110  inspects whether a first request queue in the high-priority group is empty. If yes, the first request queue is moved to the last position in the high-priority group (step  37 ), and the flow goes back to step  20 . In step  32 , when the first request queue in the high-priority group is not empty, the arbiter  110  serves a first request in the first request queue in the high-priority group. In step  33 , the arbiter  110  inspects whether a page miss event occurred during serving. If yes, the first request queue is moved to the last position in the high-priority group (step  37 ), and the flow goes back to step  20 . Otherwise, the flow goes back to step  31 . In step  34 , when the high-priority group is empty, the arbiter  110  inspects whether a first request queue in the low-priority group is empty. If yes, the first request queue is moved to the last position in the low-priority group (step  38 ), and the flow goes back to step  20 . In step  35 , when the first request queue in the low-priority group is not empty, the arbiter  110  serves a first request in the first request queue in the low-priority group. In step  36 , the arbiter  110  inspects whether a page miss event occurred during serving. If yes, the first request queue is moved to the last position in the low-priority group (step  38 ), and the flow goes back to step  20 . Otherwise, the flow goes back to step  34 .  
         [0023]    Referring to FIG. 4, there is shown a flow chart to illustrate how the arbiter  110  processes the request queues  131  when the memory unit  12  is not in the memory bound state according to the method of the preferred embodiment. In step  40 , the arbiter  110  initially inspects whether the high-priority group is empty. Then, in step  41 , when the high-priority group is not empty, the arbiter  110  inspects whether a first request queue in the high-priority group is empty. If yes, the first request queue is moved to the last position in the high-priority group (step  45 ), and the flow goes back to step  20 . In step  42 , when the first request queue in the high-priority group is not empty, the arbiter  110  serves a first request in the first request queue in the high-priority group, the first request queue is moved to the last position in the high-priority group (step  45 ), and the flow goes back to step  20 . In step  43 , when the high-priority group is empty, the arbiter  110  inspects whether a first request queue in the low-priority group is empty. If yes, the first request queue is moved to the last position in the low-priority group (step  46 ), and the flow goes back to step  20 . In step  44 , when the first request queue in the low-priority group is not empty, the arbiter  110  serves a first request in the first request queue in the low-priority group, the first request queue is moved to the last position in the low-priority group (step  46 ), and the flow goes back to step  20 .  
         [0024]    Referring to FIG. 1, when the data buffer C  130 ″ is not empty but the service waiting time of the request queue B  131 ′ is greater than the predetermined waiting threshold, the arbiter  110  processes the request queue B  131 ′ prior to the request queue  131 ″ according to the method of this invention. Therefore, the occurrence of stalling as encountered in the prior art can be reduced.  
         [0025]    While the present invention has been described in connection with what is considered the most practical and preferred embodiment, it is understood that this invention is not limited to the disclosed embodiment but is intended to cover various arrangements included within the spirit and scope of the broadest interpretation so as to encompass all such modifications and equivalent arrangements.