Abstract:
A binary tree based multi-level cache system for multi-core processors and its two possible implementations LogN and LogN+1 models maintaining a true pyramid is described.

Description:
BACK GROUND OF THE INVENTION 
       [0001]    1. Field of Invention 
         [0002]    This invention generally relates to a cache memory system for multi-core processors 
         [0003]    ’Discussion of Related Art 
         [0004]    The current general purpose multi-core processors [ 26 ,  30 ,  35 ] use the present 3-level (L 1 , L 2  and L 3 ) cache scheme. In this cache model every core has its own private L 1  cache. The L 2  cache may be private, shared or split. In first case L 2  is also kept private to a core. In second approach, which is more general, each core has its own private L 1  cache and shares L 2  through L 1 . And in third case L 2  cache is usually shared by half of the cores. Remaining half of the cores have their own shared L 2  cache and then all L 2  caches are connected to L 3 . 
         [0005]    To improve the multi-core system performance and to avoid memory bottlenecks, present solutions concentrate on increasing the bandwidth and/or on sharing some parts of their caches and maintaining others as private. The technology of smart cache and hyper transport technology is being used by processor vendors but these technologies have not been worked out for greater number of cores. 
         [0006]    Besides this, an attempt was made using reconfigurable cache design. But a problem with this is the additional time required to reconfigure the cache for every new problem. Also the behaviour of this solution on multiple cores executing multiple programs is yet to be explored. 
         [0007]    Another approach, which is also used, is multi-sliced bank cache. This approach has low latency and better-hit rate but doesn&#39;t specify its behaviour for larger number of cores. 
         [0008]    Also crossbar network and other processor-memory interconnections are being used to adjust the increased number of cores with existing 3-level cache system but the problems associated with this approach is very high cost of multiple read/write cache memories and the number of interconnections do not increase linearly with the number of cores. 
         [0009]    So far attempts are being made to find adjustments of the present 3-level cache system with multi-core processors. This invention presents a multi-level cache system for multi-core processors in which the true memory pyramid (Memory Hierarchy) is maintained, that is, with increase in base size (Number of Cores), its height is being adjusted accordingly (Memory Levels). 
         [0010]    For a processor with ‘N’ cores, where c i  , ( 1 ≦i≦N), be the i th  core, the binary tree based multi-level cache system is like a binary tree of ‘N’ terminals. The levels of cache are treated as intermediate nodes of the tree. 
         [0011]    Each core will have its own L 1  private cache, Two L 1  caches of neighboring cores are connected to a L 2  cache. Similarly two adjacent L 2  caches are connected to a L 3  cache and so on. The root of the tree is either the last level of cache or the main memory. These two configurations lead to two possible models “LogN+ 1 ” and “LogN” respectively. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    In the drawings 
           [0013]      FIG. 1  shows the LogN+ 1  model for binary tree based multi-level cache system. 
           [0014]      FIG. 2  shows the LogN model for binary tree based multi-level cache system. 
           [0015]      FIG. 3  shows an Atomic Block Model for LogN and LogN+ 1  Cache System 
           [0016]      FIG. 4  shows an open Queuing Network Model for LogN+ 1  model 
           [0017]      FIG. 5  shows an open Queuing Network Model for LogN model 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0018]    For a processor with ‘N’ cores, where c i  , ( 1 ≦i≦N), be the i th  core, the binary tree based multi-level cache system is like a binary tree of ‘N’ terminals. 
         [0019]    The levels of cache are treated as intermediate nodes of a binary tree and all of these are binary shared 
         [0020]    Each core will have its own L 1  private cache, thus there are total ‘N’ caches at L 1 . 
         [0021]    At L 2 , ‘N’ L 1  caches are grouped such that two L 1  caches of neighbouring cores are connected to a L 2  cache. Therefore, at L 2  ‘N/ 2 ’ binary shared caches is required in total. 
         [0022]    Similarly at L 3 , two adjacent L 2  caches are connected to a L 3  cache. The number of L 3  caches is therefore ‘N/ 4 ’. 
         [0023]    And the same procedure continues for the higher level of cache. For every higher cache level the number of binary caches reduces to half as that of its lower level. 
         [0024]    The root of the tree is either the last level of cache or the main memory. These two configurations lead to two possible models “LogN+ 1 ” and “LogN”. 
         [0025]    In LogN+ 1  model, the root of a system cache is a single final level of cache, connected to the main memory with a very high and fast bandwidth interface. In this model, the number of cache levels is (Log 2 N+ 1 ), as shown in  FIG. 1 . 
         [0026]    
       FIG. 1 
     
         [0027]    In LogN model, (Log 2 N+ 1 ) th  level of cache is removed. Thus the two caches at (Log 2 N) level are connected to a main memory through a high interface bus. In this model, the number of cache levels is reduced to (Log 2 N). In LogN Model the whole memory system consists of (Log 2 N) levels of cache plus one level of main memory, as shown in  FIG. 2 . 
         [0028]    
       FIG. 2 
     
         [0029]    In LogN+ 1  Models every cache from L 2  to (Log 2 N+ 1 ) level has two descendants except L 1  cache, which is private to a core and always available to that core. Whereas, for other levels the fair probability of a cache of serving its one of the descendent is ½. 
         [0030]    Similarly, in LogN Models every cache from L 2  to (Log 2 N) level has two descendants except L 1  cache, which is private to a core and always available to that core. Whereas, for other levels the fair probability of a cache of serving its one of the descendent is ½. 
         [0031]    To satisfy the properties of memory hierarchy, In case of LogN+ 1  model, (Log 2 N) and in case of LogN model, (Log 2 N− 1 ) cache levels are inserted between CPU and main memory. 
         [0032]    Size and access time of each cache at different level are calculated using geometric propagation such that for ‘n’ numbers sequence {a o r k } k=0   n−1  to the ratio between two successive terms is a constant ‘r’ and ‘a’ is first number of the sequence. Here ‘n’ is number of cache levels to be inserted between the main memory (a) and CPU. However some other suitable propagation like arithmetic and other mathematical relationship exploiting principle of locality can also be used. 
         [0033]    Like any cache hierarchy, the binary tree based cache system may be analyzed using queuing theory by considering every cache as a server and data request either by a CPU or the lower level of cache as a client. A complete cache hierarchy may be considered as an open queuing network where multiple servers (caches) are attached in a specific pattern. A request from a client is served by a specific server (cache). If the server (cache) fulfils the request client leaves the queue otherwise the request is sent to next server (upper level cache). Probability of fulfilling or not of any request at any server (cache) is same as the hit or miss ratio. Using queuing network, performance parameters like marginal probabilities, utilization, throughput, mean number of jobs, mean queue length, mean response time and mean waiting time may be calculated for any individual server (cache) and for the complete network (cache hierarchy). 
         [0034]    Considering the proposed binary multi-level cache system where every cache level except L 1 , which is local to the core, has two descendants. Average request rate, λ, for first level of cache is the same as that of requests made by the respective cores. Request rates for rest of levels are Poisson, as they depend on the probability of cache miss at their respective descendants. The service rate of each cache depends on its frequency and access time. So it is deterministic. Here in our approach every cache level except the first one has two descendants i.e; clients, out of which only one can be served at a time on first come first serve basis with equal probabilities of being served. Therefore, M/D/ 1 / 2 -FIFO queuing model may be applied for analyzing any cache level except the first one for its utilization, throughput, average number of jobs, average queue length, average response time and average waiting time. This basic atomic M/D/ 1 / 2 -FIFO queuing model is presented in  FIG. 3 . 
         [0035]    
       FIG. 3 
     
         [0036]    Let λ i  where 
         [0000]    
       
         
           
             
               i 
               = 
               1 
             
             , 
             2 
             , 
             3 
             , 
             … 
              
             
                 
             
             , 
             
               Log 
                
               
                   
               
                
               N 
                
               
                   
               
                
               for 
                
               
                   
               
                
               Log 
                
               
                   
               
                
               N 
                
               
                   
               
                
               Model 
             
           
         
       
       
         
           
             
               i 
               = 
               1 
             
             , 
             2 
             , 
             3 
             , 
             … 
              
             
                 
             
             , 
             
               
                 Log 
                  
                 
                     
                 
                  
                 N 
               
               + 
               
                 1 
                  
                 
                     
                 
                  
                 for 
                  
                 
                     
                 
                  
                 Log 
                  
                 
                     
                 
                  
                 N 
               
               + 
               
                 1 
                  
                 
                     
                 
                  
                 Model 
               
             
           
         
       
     
         [0000]    be the arrival rate of requests at the ith level of cache, φ i,1    
         [0000]    
       
         
           
             
               i 
               = 
               1 
             
             , 
             2 
             , 
             3 
             , 
             … 
              
             
                 
             
             , 
             
               Log 
                
               
                   
               
                
               N 
                
               
                   
               
                
               for 
                
               
                   
               
                
               Log 
                
               
                   
               
                
               N 
                
               
                   
               
                
               Model 
             
           
         
       
       
         
           
             
               i 
               = 
               1 
             
             , 
             2 
             , 
             3 
             , 
             … 
              
             
                 
             
             , 
             
               
                 Log 
                  
                 
                     
                 
                  
                 N 
               
               + 
               
                 1 
                  
                 
                     
                 
                  
                 for 
                  
                 
                     
                 
                  
                 Log 
                  
                 
                     
                 
                  
                 N 
               
               + 
               
                 1 
                  
                 
                     
                 
                  
                 Model 
               
             
           
         
       
     
         [0000]    where be the probability of cache being hit and φ i,o  where 
         [0000]    
       
         
           
             
               i 
               = 
               1 
             
             , 
             2 
             , 
             3 
             , 
             
               … 
                
               
                   
               
                
               Log 
                
               
                   
               
                
               N 
                
               
                   
               
                
               for 
                
               
                   
               
                
               Log 
                
               
                   
               
                
               N 
                
               
                   
               
                
               Model 
             
           
         
       
       
         
           
             
               i 
               = 
               1 
             
             , 
             2 
             , 
             3 
             , 
             … 
              
             
                 
             
             , 
             
               
                 Log 
                  
                 
                     
                 
                  
                 N 
               
               + 
               
                 1 
                  
                 
                     
                 
                  
                 for 
                  
                 
                     
                 
                  
                 Log 
                  
                 
                     
                 
                  
                 N 
               
               + 
               
                 1 
                  
                 
                     
                 
                  
                 Model 
               
             
           
         
       
     
         [0000]    such that φ i,o =1−φ i,1 , be the probability of cache being missed at the i th  level and search will proceed in the upper (i+l) th  cache level. 
         [0037]    Atomic model for M/D/ 1 / 2 —FIFO for LogN+ 1  cache system ( FIG. 3 ) may be joined to form an open queue network of proposed binary based multi-level cache system. Every unit (cache) may be treated as a single object which leads to a queuing network from where network performance parameters for the whole cache system can be computed. Queuing networks for LogN+ 1  model is shown in  FIG. 4 . Here the number of queuing stage is same as that of the cache levels that is LogN+ 1 . 
         [0038]    Similarly, Atomic model for M/D/ 1 / 2 —FIFO for LogN cache system ( FIG. 3 ) may be joined to form an open queue network of proposed binary based multi-level cache system. Every unit (cache) may be treated as a single object, which leads to a queuing network from where network performance parameters for the whole cache system can be computed. Queuing networks for LogN model is shown in  FIG. 5 . 
         [0039]    
       FIG. 5 
     
         [0040]    Initially CPU generates a data request, which is searched in its private L 1  cache. In case of miss hit that is the requested data is not found in the respective L 1  cache, the search is extended to upper cache level associated with the L 1  cache. 
         [0041]    Thus In the invented cache system based on binary tree for multi-core processors all ‘N’ core can search their respective private L 1  cache in parallel. ‘N/ 2 ’ cache searches can be done in parallel at cache level  2 . Similarly ‘N/ 4 ’ searches at L 3  cache and so on. 
         [0042]    The foregoing description is intended to be illustrative and not limiting. Variation will occur to those skills in the art. Those variations are intended to be included in the invention, which is limited only by the spirit and scope of the claims.