Abstract:
A cache line allocation method, wherein the cache is coupled to a graphic processing unit and the cache comprising a plurality of cache lines, each cache line stores one of a plurality of instructions the method comprising the steps of: putting the plurality of instructions in whole cache lines; locking the whole cache lines if an instruction size is less than a cache size; locking a first number of cache lines when the instruction size is larger than the cache size and a difference between the instruction size and the cache size is less than or equal to a threshold; and locking a second number of cache lines when the instruction size is larger than the cache size and a difference between the instruction size and the cache size is large than the threshold; wherein the first number is greater than the second number.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The entire contents of China Patent Application No. 201110097265.4, filed on Apr. 19, 2011, from which this application claims priority, are incorporated herein by reference. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a cache, and more particularly to a cache line allocation system and method of a three-dimensional graphic shader. 
     2. Description of Related Art 
     In ordinary electronic systems, the access speed of the system memory is much slower than the clock speed of CPU. Therefore, it always takes a lot of time waiting for the system memory when the CPU is accessing the system memory. This makes the whole system ineffective. In order to improve the system efficiency, a cache architecture is proposed. With this architecture, a small capacity cache is implemented, such as static random access memory (SRAM), to store the most recently accessed information of CPU. When the requested information has already been stored in the cache, CPU could read the information more quickly from cache instead of from the system memory. 
     There are two types of information stored in the cache which are data and instructions. In most applications, there is always a large amount of data and a small amount of instructions. The advantages of the cache are more outstanding with instructions than data, because the amount of instructions is always much smaller than the amount of data, and the instructions are more frequently read than the data. Further, for the graphic processing mechanism such as three-dimensional graphic shader, the processing of different pixel data always uses the same instruction group, so the cache architecture is more significant to this kind of graphic processing. 
     However, the capability of cache in ordinary system is not large enough to store the whole instruction group in one writing operation, which means it is impossible to read the whole instruction group in one reading operation but has to read and write repeatedly. Therefore there would not be any advantages of using the cache. For example, assume that the size of instruction group is 1-instruction-length longer than the size of cache. When processing the first pixel, the instruction group must be read from the system memory and written into the cache. As there is no room for the last instruction, the graphics processing unit must read the system memory again for that last instruction and rewrite the cache to make room for the last instruction. This must result in overwriting another instruction. When processing the second pixel, as the cache has been rewritten, not all the instructions are in the cache when doing the hit determination mechanism, so the whole instruction group must be read from the system memory again. In other words, the graphics processing unit cannot find all the instructions in the cache every time it is processing another pixel, so it must access the system memory more than once to read the whole instruction group in every processing, therefore the above-mentioned advantage becomes a disadvantage. 
     Therefore, there is a need for a novel cache line allocation system and method to improve the utility efficiency of the cache and the system memory. 
     SUMMARY OF THE INVENTION 
     The present invention provides a cache line allocation method. The cache in the present invention is coupled to a graphic processing unit and comprising a plurality of cache lines. Each cache line stores one of a plurality of instructions. The method comprises the steps of: putting the plurality of instructions in whole cache lines; locking the whole cache lines if an instruction size is less than a cache size; locking a first number of cache lines when the instruction size is larger than the cache size and a difference between the instruction size and the cache size is less than or equal to a threshold; and locking a second number of cache lines when the instruction size is larger than the cache size and a difference between the instruction size and the cache size is larger than the threshold; wherein the first number is greater than the second number. 
     According to the specific construction, a cache line allocation system comprising a cache, a graphic processing unit, and a cache controller. The cache is configured to store a batch of information. The graphic processing unit is coupled to the cache. And the cache controller is coupled to the cache. The cache controller is configured to: putting the plurality of instructions in whole cache lines; locking the whole cache lines if an instruction size is less than a cache size, locking a first number of cache lines when the instruction size is larger than the cache size and a difference between the instruction size and the cache size is less than or equal to a threshold; and locking a second number of cache lines when the instruction size is larger than the cache size and a difference between the instruction size and the cache size is larger than the threshold, and wherein the first number is greater than the second number. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  is a block diagram showing the cache line allocation system according to one embodiment of the present invention. 
         FIG. 1B  is a block diagram showing the cache line allocation system according to another embodiment of the present invention. 
         FIG. 2  is a block diagram showing the detail of the cache controller of FIG.  1 A/B according to the present invention. 
         FIG. 3  is a flow chart showing the cache line allocation method according to one embodiment of the present invention. 
         FIG. 4  is a flow chart showing the cache line allocation method according to another embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
       FIG. 1A  is a block diagram showing the cache line allocation system of the present invention. Although the embodiment gives three-dimensional graphic shader as an example, the present invention may be applied to other applications. In this embodiment, processer  10  is a graphics processing unit (GPU), which assists CPU (not shown) to accelerate the graphic processing. Processer  10  performs information accessing on cache  14  and system memory  16  via a cache controller  12 . Cache  14  may be a static random access memory (SRAM), the accessing speed of which is faster than the system memory  16  such as dynamic random access memory (DRAM). The cache controller  12  and cache  14  may be integrated on the same chip with processor  10 , but it should be understood that the disclosure is not limited thereto. In this embodiment, cache  14  is used as an instruction cache, to store the instructions used by the graphic processing unit to process a three-dimensional graph, but it should be understood that the disclosure is not limited thereto. The three-dimensional graphic shader in this embodiment adopts multithreading operations which means that processer  10  performs more than one processing on the according pixel data simultaneity since every pixel may be performed the same instructions. Further, cache  14  in this embodiment may also be a “multiway” cache, which divides the whole memory space into a plurality of blocks to reduce the complexity of the judging logical circuit. 
       FIG. 1B  is a block diagram showing the cache line allocation system according to another embodiment of the present invention. In this embodiment, the cache which is similar to the cache  14  in  FIG. 1A  may have two levels, which are a first level cache (named the L1 cache in general)  14 A and a second level cache (named the L2 cache in general)  14 B. The L1 cache and the L2 cache are controlled by a first level cache controller  12 A and a second level cache  12 B respectively. In this embodiment the cache controller as the cache controller  12  in  FIG. 1A  also has two levels: the first level cache controller  12 A and the first level cache  14 A. The first level cache controller  12 A and the first level cache  14 A may be integrated in the same chip with processor  10 , but it should be understood that the disclosure is not limited thereto. The cache allocation method of the present invention may be implemented in the first level cache controller  12 A and the first level cache  14 A, but it should be understood that the disclosure is not limited thereto. 
       FIG. 2  is a block diagram showing the detail of the cache controller  12  which includes a control logic unit  120  and a table  122 . Control logic unit  120  provides the communication interface to the controller  10 , the cache  14 , and the system memory  16 . Table  122  is coupled to the control logic unit  120 , and is used for keeping a record for all the information, such as instructions or pixel data, stored in the cache controller  12 . In this embodiment, the contents of table  122  are not only the addresses of all the information in system memory  16 , but also a lock flag and a replacement value of every line in cache  14 , wherein, the lock flag is the flag identifying whether the corresponding line in cache  14  is locked. When a line is locked, the corresponding lock flag turned to “locked” to prevent the information stored in the line from being overwritten, but the information could still be accessed by the system memory. The replacement value is the judgment basis of whether the information in an unlocked line in cache  14  should be overwritten. This embodiment uses “least recently used, LRU” algorithm, to trace the access frequency of each of the plurality of information, to get a LRU displacement value. The lock flag and the replacement value will be discussed in more detail combined with the embodiments in the following description. 
       FIG. 3  is a flow chart showing the cache allocation method of cache  14  according to one embodiment of the present invention. The flow is divided into two stages, the setting stage  310  and the operating stage  320 . 
     At first, in setting stage  310 , at step  31 , the properties of a plurality of information, such as length, the category and the distribution of the instructions, are analyzed by the CPU (not shown). In this embodiment, the information is a plurality of instructions used by the graphic processing unit to process a three-dimensional graph, but it should be understood that the disclosure is not limited thereto. Then, at step  32 , if the length of the batch of information is larger than the length of cache  14  is determined by the CPU. If the length of the batch of information is less than or equal to the length of cache  14 , cache  14  may store all the information at one time. In this case, as shown in step  33 , all the lines in cache  14  are locked, and the lock flags of all cache lines are modified to “locked.” Therefore, in the following information accessing operations, the corresponding information may be accessed directly in cache  14  without accessing the system memory  16 . Since there is not any rewriting operations in the cache lines, a hit determination mechanism of cache  14  can be turned off. The hit determination mechanism is a common method in the art, which means the CPU accessed through the whole cache until it finds the aimed information. In the embodiment, the plurality of instructions would be accessed every time processing a pixel. Therefore, in the following operations, processor  10  may access cache  14  directly and there is no need to determine every time whether these instructions can be accessed in cache  14 . The power consumption and the time spent on reading could be both decreased at the same time. If the length of the plurality of information is larger than the length of cache  14 , the process goes to step  34 . At step  34 , whether the difference between the length of the plurality of information and the length of cache  14  is greater than a presupposed critical value is determined, wherein the presupposed critical value is positive and variable. If the result of step  34  is no, the length of the plurality of information is a little bit longer than the length of cache  14 . Then, at step  35 , more than a half of all the cache lines or most of the cache lines are locked, e.g. at least one cache line in cache  14  is reserved to unlocked, and the other cache lines are locked. Therefore, the information in the locked lines could be read from cache  14  directly in the following applications without accessing the system memory, so the information transmissions of system memory could be decreased and the meaningless updating and rewriting of cache  14  could be effectively reduced. Comparing to the conventional approach in which every line is unlocked, the time spent on reading is greatly reduced and the hit rate is increased. On the other hand, the unlocked cache lines are reserved for alternatively writing the following information read from system memory  16 . If the result of step  34  is yes, the length of the plurality of information is much larger than the length of cache  14 . Then, at step  36 , less than the half of all the cache lines or a few lines in cache  14  may be locked. In some conditions, all of the lines in cache  14  may be unlocked. More cache lines, or up to all the lines in cache  14  are reserved to be unlocked to participate in alternative writing. For example, the length of the cache is 256, and the presupposed critical value is 20. If the length of the plurality of information is 270, because 270−256&lt;20, which means the length of the plurality of information is a little bit longer than the length of cache  14 , in this condition, most of the lines, for example, 240 lines may be locked, and only 30 instructions may occupy 16 unlocked lines alternatively. On the other hand, the length of the cache is still 256, the presupposed critical value is still 20, but the length of the plurality of information is 1000. 1000−256&gt;20, which means the length of the plurality of information is much longer than the length of cache  14 . In this case, if most lines, for example 240 lines, are locked, there would be 760 instructions occupying the 16 unlocked lines alternatively, then, on the contrary, the system performance may be degraded. So when the length of the plurality of information is much longer than the length of cache  14 , a few lines should be locked, for example 128 or even less. Then, the setting stage  310  ends, and the process may enter into the operating stage  320 . 
     In the operating stage  320 , first of all, at step  37 , the instructions in the locked lines may not be overwritten, and the overwriting may only be performed on the instructions in the unlocked lines. Generally, the information which has a higher using frequency would be locked. For example, if an instruction may be used by every pixel, then its using frequency may be 100%. The instructions have a higher using frequency like that should get the corresponding line locked. If an instruction is in an “if . . . else” judge branch, assume its using frequency to be 50% for simplicity, then its using frequency is lower, so its corresponding line may not be locked. The replacement value of the unlocked line may be set significant, and every time the information in the line is read, the replacement value may increase by one. Then the information that in the line with a larger replacement value may be read more frequently, and the information that in the line with a smaller replacement value may be read less frequently. The instructions in unlocked cache lines which should be replaced by the new accessing instructions from the system memory  16  may be determined upon the replacement value. The replacement value is LRU replacement value in this embodiment. Therefore, in the following writing operations, the new information may be used to overwrite the lines with the smaller replacement value in cache  14 . In this way, the information that has a high reading frequency may be replaced less often, therefore in the unlocked lines, the meaningless information updating and rewriting of the cache could also be effectively reduced, and the hit rate could also be increased. Because the whole system memory accessing frequency is reduced, the bandwidth usage effectiveness of the system memory is improved. At step  38 , whether all the pixels have been processed is determined. If the result is “no,” the process enters to step  37 . If the result is “yes,” the cache access operation for processing one graph is ended. The progress may go back to setting stage  310 , for accessing the cache  14  to processing a new graph. 
       FIG. 4  is a flow chart showing the cache allocation method according to another embodiment of the present invention. First of all, at step  41 , processor  10  may send the instruction reading request to cache controller  12 , to ask for at least one instruction. Then, at step  42 , the control logic unit  120  of cache controller  12  may determine whether the requested instruction is stored in cache  14  based on table  122 . If the result of step  42  is “yes” which means the instruction is in the cache  14 , then cache controller  12  may get the requested instruction from cache  14  to provide it to processor  10 , and in step  43 , all the instructions in cache  14  may be locked. On the other hand, if the result of step  42  is “no” which means the instruction is not in the cache  14 , then, in step  44 , cache controller  12  may access system memory  16  for the requested instruction, then provide it to processer  10 , store the instruction in cache  14  and update the table  122 . 
     Next, at step  45 , whether the length of the plurality of instructions is larger than the length of cache  14  is determined. If the result is “no,” then all the instructions wrote in step  44  may be locked. That is in step  46 , the lock flags of corresponding lines in table  122  are set to be “locked.” 
     If the result of step  45  is “yes,” then enters to step  47 , whether the difference between the length of the plurality of instructions and the length of cache  14  is greater than a presupposed critical value is determined. If the result of step  47  is “no,” the length of instructions is a little bit larger than the length of cache  14 . Then, at step  48 , a few lines, or at least one line in cache  14  are reserved unlocked, and the other instruction is locked. The unlocked cache lines, on the other hand, are used for following instructions replacement with system memory  16 . 
     If the result of step  47  is “yes,” the length of instructions is much longer than the length of cache  14 , then, a few lines in cache  14  may be locked, and most of the lines are unlocked lines. The unlocked cache lines are used for following replacement operations. When a line is determined to be an unlocked line and may perform the following replacement operations, the replacement value corresponding to that line may be set as significant. In step  49 , the instructions in unlocked cache lines that should be replaced by the new accessing instructions from the system memory  16  may be determined upon the replacement value, as discussed above reference to  FIG. 3 . 
     Using the above process flows of the embodiments of the present invention, the accessing frequency of system memory  16  is effectively reduced, and a hit rate of cache  14  is greatly increased. The hit rate is a value which expresses the rate of obtaining the aimed information from the cache in one accessing operation. Especially for the processing of different pixels or different graphs, as the same instructions may be used, the advantages of the present invention are more obvious. The following is an example showing the efficiency improvement of the present invention compared to the conventional approach. Assuming the length of the cache is 256, and the length of shader instructions is 257. Based on the allocation method of cache in conventional approach, when processing the first pixel, the first 256 instructions may be written into the cache in turn from system memory, to be processed by graphics processing unit. When it comes to the 257 th  instruction, that instruction may be written into the first cache line and the first instruction may be overwritten. When processing the second pixel, because the first instruction could not be found in the cache, the first to the 256 th  instruction must be read from the system memory a second time. For the graphic that has an analyzing degree of 1280×1024, there would be a total 1280×1240×257 times of system memory accessing, which is 336,855,040 times of accessing. For the same example, if using the embodiment of the present invention, the first 256 instructions may be written into cache  14  from system memory  16  in turn, the first 255 instructions may be locked in the first 255 cache lines, and the 256 th  instruction line may reserved to be unlocked. When it comes to the 257 th  instruction, that instruction may be written into the unlocked line in cache  14  from system memory  16 . Next, when processing the second pixel, because the first to the 255 th  instruction have already been locked in cache  14 , there only need to read the 256 th  and the 257 th  instruction in turn from system memory  16 . The third and the following pixels would have the same operations. Therefore, there are 257+(1280×1024−1)*2 times of accessing to the system memory  16 , which is 2,621,695 times of accessing. Comparing to the conventional approach, the effectiveness of the present invention has improved by 128 times. 
     The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.