source: trunk/modules/vci_mem_cache_v4/caba/source/include/mem_cache_directory_v4.h @ 142

Last change on this file since 142 was 142, checked in by guthmull, 14 years ago

Eviction can now be random. Unselected by default.

  • Property svn:eol-style set to native
  • Property svn:keywords set to "Author Date Id Rev URL Revision"
  • Property svn:mime-type set to text/plain
File size: 18.9 KB
Line 
1#ifndef SOCLIB_CABA_MEM_CACHE_DIRECTORY_V4_H
2#define SOCLIB_CABA_MEM_CACHE_DIRECTORY_V4_H
3
4#include <inttypes.h>
5#include <systemc>
6#include <cassert>
7#include "arithmetics.h"
8
9#define L1_MULTI_CACHE      1
10//#define RANDOM_EVICTION
11
12namespace soclib { namespace caba {
13
14  using namespace sc_core;
15
16  ////////////////////////////////////////////////////////////////////////
17  //                    A LRU entry
18  ////////////////////////////////////////////////////////////////////////
19  class LruEntry {
20
21    public:
22
23      bool recent;           
24
25      void init()
26      {
27        recent=false;
28      }
29
30  }; // end class LruEntry
31
32  ////////////////////////////////////////////////////////////////////////
33  //                    An Owner
34  ////////////////////////////////////////////////////////////////////////
35  class Owner{
36    typedef uint32_t size_t;
37   
38    public:
39    // Fields
40      bool      inst;       // Is the owner an ICache ?
41      size_t    srcid;      // The SRCID of the owner
42#if L1_MULTI_CACHE
43      size_t    cache_id;   // In multi_cache configuration
44#endif
45
46    ////////////////////////
47    // Constructors
48    ////////////////////////
49      Owner(bool   i_inst
50            ,size_t i_srcid
51#if L1_MULTI_CACHE
52            ,size_t i_cache_id
53#endif
54            ){
55        inst    = i_inst;
56        srcid   = i_srcid;
57#if L1_MULTI_CACHE
58        cache_id= i_cache_id;
59#endif
60      }
61
62      Owner(const Owner &a){
63        inst    = a.inst;
64        srcid   = a.srcid;
65#if L1_MULTI_CACHE
66        cache_id= a.cache_id;
67#endif
68      }
69
70      Owner(){
71        inst    = false;
72        srcid   = 0;
73#if L1_MULTI_CACHE
74        cache_id= 0;
75#endif
76      }
77      // end constructors
78
79  }; // end class Owner
80
81
82  ////////////////////////////////////////////////////////////////////////
83  //                    A directory entry                               
84  ////////////////////////////////////////////////////////////////////////
85  class DirectoryEntry {
86
87    typedef uint32_t tag_t;
88    typedef uint32_t size_t;
89
90    public:
91
92    bool    valid;                  // entry valid
93    bool    is_cnt;                 // directory entry is in counter mode
94    bool    dirty;                  // entry dirty
95    bool    lock;                   // entry locked
96    tag_t   tag;                    // tag of the entry
97    size_t  count;                  // number of copies
98    Owner   owner;                  // an owner of the line
99    size_t  ptr;                    // pointer to the next owner
100
101    DirectoryEntry()
102    {
103      valid         = false;
104      is_cnt        = false;
105      dirty         = false;
106      lock          = false;
107      tag           = 0;
108      count         = 0;
109      owner.inst    = 0;
110      owner.srcid   = 0;
111#if L1_MULTI_CACHE
112      owner.cache_id= 0;
113#endif
114      ptr           = 0;
115    }
116
117    DirectoryEntry(const DirectoryEntry &source)
118    {
119      valid         = source.valid;
120      is_cnt        = source.is_cnt;
121      dirty         = source.dirty;
122      lock          = source.lock;
123      tag           = source.tag;
124      count         = source.count;
125      owner         = source.owner;
126      ptr           = source.ptr;
127    }         
128
129    /////////////////////////////////////////////////////////////////////
130    // The init() function initializes the entry
131    /////////////////////////////////////////////////////////////////////
132    void init()
133    {
134      valid     = false;
135      is_cnt    = false;
136      dirty     = false;
137      lock      = false;
138      count     = 0;
139    }
140
141    /////////////////////////////////////////////////////////////////////
142    // The copy() function copies an existing source entry to a target
143    /////////////////////////////////////////////////////////////////////
144    void copy(const DirectoryEntry &source)
145    {
146      valid         = source.valid;
147      is_cnt    = source.is_cnt;
148      dirty         = source.dirty;
149      lock          = source.lock;
150      tag           = source.tag;
151      count     = source.count;
152      owner     = source.owner;
153      ptr       = source.ptr;
154    }
155
156    ////////////////////////////////////////////////////////////////////
157    // The print() function prints the entry
158    ////////////////////////////////////////////////////////////////////
159    void print()
160    {
161      std::cout << "Valid = " << valid << " ; IS COUNT = " << is_cnt << " ; Dirty = " << dirty << " ; Lock = "
162                << lock
163                << " ; Tag = " << std::hex << tag << std::dec
164                << " ; Count = " << count
165                << " ; Owner = " << owner.srcid
166#if L1_MULTI_CACHE
167                << "." << owner.cache_id
168#endif
169                << " " << owner.inst
170                << " ; Pointer = " << ptr << std::endl;
171    }
172
173  }; // end class DirectoryEntry
174
175  ////////////////////////////////////////////////////////////////////////
176  //                       The directory 
177  ////////////////////////////////////////////////////////////////////////
178  class CacheDirectory {
179
180    typedef sc_dt::sc_uint<40> addr_t;
181    typedef uint32_t data_t;
182    typedef uint32_t tag_t;
183    typedef uint32_t size_t;
184
185    private:
186
187    // Directory constants
188    size_t                                      m_ways;
189    size_t                                      m_sets;
190    size_t                                      m_words;
191    size_t                                      m_width;
192    uint32_t                lfsr;
193
194    // the directory & lru tables
195    DirectoryEntry                              **m_dir_tab;
196    LruEntry                                    **m_lru_tab;
197
198    public:
199
200    ////////////////////////
201    // Constructor
202    ////////////////////////
203    CacheDirectory( size_t ways, size_t sets, size_t words, size_t address_width)       
204    {
205      m_ways  = ways;
206      m_sets  = sets;
207      m_words = words;
208      m_width = address_width;
209      lfsr = -1;
210
211      m_dir_tab = new DirectoryEntry*[sets];
212      for ( size_t i=0; i<sets; i++ ) {
213        m_dir_tab[i] = new DirectoryEntry[ways];
214        for ( size_t j=0 ; j<ways ; j++) m_dir_tab[i][j].init();
215      }
216      m_lru_tab = new LruEntry*[sets];
217      for ( size_t i=0; i<sets; i++ ) {
218        m_lru_tab[i] = new LruEntry[ways];
219        for ( size_t j=0 ; j<ways ; j++) m_lru_tab[i][j].init();
220      }
221    } // end constructor
222
223    /////////////////
224    // Destructor
225    /////////////////
226    ~CacheDirectory()
227    {
228      for(size_t i=0 ; i<m_sets ; i++){
229        delete [] m_dir_tab[i];
230        delete [] m_lru_tab[i];
231      }
232      delete [] m_dir_tab;
233      delete [] m_lru_tab;
234    } // end destructor
235
236    /////////////////////////////////////////////////////////////////////
237    // The read() function reads a directory entry. In case of hit, the
238    // LRU is updated.
239    // Arguments :
240    // - address : the address of the entry
241    // - way : (return argument) the way of the entry in case of hit
242    // The function returns a copy of a (valid or invalid) entry 
243    /////////////////////////////////////////////////////////////////////
244    DirectoryEntry read(const addr_t &address,size_t &way)
245    {
246
247#define L2 soclib::common::uint32_log2
248      const size_t set = (size_t)(address >> (L2(m_words) + 2)) & (m_sets - 1);
249      const tag_t  tag = (tag_t)(address >> (L2(m_sets) + L2(m_words) + 2));
250#undef L2
251
252      bool hit       = false;
253      for ( size_t i=0 ; i<m_ways ; i++ ) {
254        bool equal = ( m_dir_tab[set][i].tag == tag );
255        bool valid = m_dir_tab[set][i].valid;
256        hit = equal && valid;
257        if ( hit ) {                   
258          way = i;
259          break;
260        }
261      }
262      if ( hit ) {
263        m_lru_tab[set][way].recent = true;
264        return DirectoryEntry(m_dir_tab[set][way]);
265      } else {
266        return DirectoryEntry();
267      }
268    } // end read()
269
270    /////////////////////////////////////////////////////////////////////
271    // The write function writes a new entry,
272    // and updates the LRU bits if necessary.
273    // Arguments :
274    // - set : the set of the entry
275    // - way : the way of the entry
276    // - entry : the entry value
277    /////////////////////////////////////////////////////////////////////
278    void write(const size_t &set, const size_t &way, const DirectoryEntry &entry)
279    {
280      assert( (set<m_sets)
281          && "Cache Directory write : The set index is invalid");
282      assert( (way<m_ways)
283          && "Cache Directory write : The way index is invalid");
284
285      // update Directory
286      m_dir_tab[set][way].copy(entry);
287
288      // update LRU bits
289      bool all_recent = true;
290      for ( size_t i=0 ; i<m_ways ; i++ ) {
291        if ( i != way ) all_recent = m_lru_tab[set][i].recent && all_recent;
292      }
293      if ( all_recent ) {
294        for( size_t i=0 ; i<m_ways ; i++ ) m_lru_tab[set][i].recent = false;
295      } else {
296        m_lru_tab[set][way].recent = true;
297      }
298    } // end write()
299
300    /////////////////////////////////////////////////////////////////////
301    // The print() function prints a selected directory entry
302    // Arguments :
303    // - set : the set of the entry to print
304    // - way : the way of the entry to print
305    /////////////////////////////////////////////////////////////////////
306    void print(const size_t &set, const size_t &way)
307    {
308      std::cout << std::dec << " set : " << set << " ; way : " << way << " ; " ;
309      m_dir_tab[set][way].print();
310    } // end print()
311
312    /////////////////////////////////////////////////////////////////////
313    // The select() function selects a directory entry to evince.
314    // Arguments :
315    // - set   : (input argument) the set to modify
316    // - way   : (return argument) the way to evince
317    /////////////////////////////////////////////////////////////////////
318    DirectoryEntry select(const size_t &set, size_t &way)
319    {
320      assert( (set < m_sets)
321          && "Cache Directory : (select) The set index is invalid");
322
323      for(size_t i=0; i<m_ways; i++){
324        if(!m_dir_tab[set][i].valid){
325          way=i;
326          return DirectoryEntry(m_dir_tab[set][way]);
327        }
328      }
329
330#ifdef RANDOM_EVICTION
331      lfsr = (lfsr >> 1) ^ ((-(lfsr & 1)) & 0xd0000001);
332      way = lfsr % m_ways;
333      return DirectoryEntry(m_dir_tab[set][way]);
334#endif
335
336      for(size_t i=0; i<m_ways; i++){
337        if(!(m_lru_tab[set][i].recent) && !(m_dir_tab[set][i].lock)){
338          way=i;
339          return DirectoryEntry(m_dir_tab[set][way]);
340        }
341      }
342      for(size_t i=0; i<m_ways; i++){
343        if( !(m_lru_tab[set][i].recent) && (m_dir_tab[set][i].lock)){
344          way=i;
345          return DirectoryEntry(m_dir_tab[set][way]);
346        }
347      }
348      for(size_t i=0; i<m_ways; i++){
349        if( (m_lru_tab[set][i].recent) && !(m_dir_tab[set][i].lock)){
350          way=i;
351          return DirectoryEntry(m_dir_tab[set][way]);
352        }
353      }
354      way = 0;
355      return DirectoryEntry(m_dir_tab[set][0]);
356    } // end select()
357
358    /////////////////////////////////////////////////////////////////////
359    //          Global initialisation function
360    /////////////////////////////////////////////////////////////////////
361    void init()
362    {
363      for ( size_t set=0 ; set<m_sets ; set++ ) {
364        for ( size_t way=0 ; way<m_ways ; way++ ) {
365          m_dir_tab[set][way].init();
366          m_lru_tab[set][way].init();
367        }
368      }
369    } // end init()
370
371  }; // end class CacheDirectory
372
373  ///////////////////////////////////////////////////////////////////////
374  //                    A Heap Entry
375  ///////////////////////////////////////////////////////////////////////
376  class HeapEntry{
377    typedef uint32_t size_t;
378
379    public:
380    // Fields of the entry
381      Owner     owner;
382      size_t    next;
383
384    ////////////////////////
385    // Constructor
386    ////////////////////////
387      HeapEntry()
388      :owner(false,0
389#if L1_MULTI_CACHE
390             ,0
391#endif
392             )
393      {
394        next = 0;
395      } // end constructor
396
397    ////////////////////////
398    // Constructor
399    ////////////////////////
400      HeapEntry(const HeapEntry &entry){
401        owner.inst  = entry.owner.inst;
402        owner.srcid = entry.owner.srcid;
403#if L1_MULTI_CACHE
404        owner.cache_id = entry.owner.cache_id;
405#endif       
406        next           = entry.next;
407      } // end constructor
408
409    /////////////////////////////////////////////////////////////////////
410    // The copy() function copies an existing source entry to a target
411    /////////////////////////////////////////////////////////////////////
412      void copy(const HeapEntry &entry){
413        owner.inst     = entry.owner.inst;
414        owner.srcid    = entry.owner.srcid;
415#if L1_MULTI_CACHE
416        owner.cache_id = entry.owner.cache_id;
417#endif
418        next           = entry.next;
419      } // end copy()
420
421    ////////////////////////////////////////////////////////////////////
422    // The print() function prints the entry
423    ////////////////////////////////////////////////////////////////////
424      void print(){
425        std::cout
426        << " -- owner.inst     : " << std::dec << owner.inst << std::endl
427        << " -- owner.srcid    : " << std::dec << owner.srcid << std::endl
428#if L1_MULTI_CACHE
429        << " -- owner.cache_id : " << std::dec << owner.cache_id << std::endl
430#endif
431        << " -- next           : " << std::dec << next << std::endl;
432
433      } // end print()
434
435  }; // end class HeapEntry
436
437  ////////////////////////////////////////////////////////////////////////
438  //                        The Heap
439  ////////////////////////////////////////////////////////////////////////
440  class HeapDirectory{
441    typedef uint32_t size_t;
442   
443    private:
444    // Registers and the heap
445      size_t    ptr_free;
446      bool      full;
447      HeapEntry *m_heap_tab;
448
449    // Constants for debugging purpose
450      size_t    tab_size;
451
452    public:
453    ////////////////////////
454    // Constructor
455    ////////////////////////
456      HeapDirectory(uint32_t size){
457        assert(size>0 && "Memory Cache, HeapDirectory constructor : invalid size");
458        ptr_free    = 0;
459        full        = false;
460        m_heap_tab  = new HeapEntry[size];
461        tab_size    = size;
462      } // end constructor
463
464    /////////////////
465    // Destructor
466    /////////////////
467      ~HeapDirectory(){
468        delete [] m_heap_tab;
469      } // end destructor
470
471    /////////////////////////////////////////////////////////////////////
472    //          Global initialisation function
473    /////////////////////////////////////////////////////////////////////
474      void init(){
475        ptr_free=0;
476        full=false;
477        for(size_t i=0; i< tab_size-1;i++){
478          m_heap_tab[i].next = i+1;
479        }
480        m_heap_tab[tab_size-1].next = tab_size-1;
481        return;
482      }
483
484    /////////////////////////////////////////////////////////////////////
485    // The print() function prints a selected directory entry
486    // Arguments :
487    // - ptr : the pointer to the entry to print
488    /////////////////////////////////////////////////////////////////////
489      void print(const size_t &ptr){
490        std::cout << "Heap, printing the entry : " << std::dec << ptr << std::endl;
491        m_heap_tab[ptr].print();
492      } // end print()
493
494    /////////////////////////////////////////////////////////////////////
495    // The print_list() function prints a list from selected directory entry
496    // Arguments :
497    // - ptr : the pointer to the first entry to print
498    /////////////////////////////////////////////////////////////////////
499      void print_list(const size_t &ptr){
500        bool end = false;
501        size_t ptr_temp = ptr;
502        std::cout << "Heap, printing the list from : " << std::dec << ptr << std::endl;
503        while(!end){
504            m_heap_tab[ptr_temp].print();
505            if(ptr_temp == m_heap_tab[ptr_temp].next) end = true;
506            ptr_temp = m_heap_tab[ptr_temp].next;
507        }
508      } // end print_list()
509
510    /////////////////////////////////////////////////////////////////////
511    // The is_full() function return true if the heap is full.
512    /////////////////////////////////////////////////////////////////////
513      bool is_full(){
514        return full;
515      } // end is_full()
516
517    /////////////////////////////////////////////////////////////////////
518    // The next_free_ptr() function returns the pointer
519    // to the next free entry.
520    /////////////////////////////////////////////////////////////////////
521      size_t next_free_ptr(){
522        return ptr_free;
523      } // end next_free_ptr()
524
525    /////////////////////////////////////////////////////////////////////
526    // The next_free_entry() function returns
527    // a copy of the next free entry.
528    /////////////////////////////////////////////////////////////////////
529      HeapEntry next_free_entry(){
530        return HeapEntry(m_heap_tab[ptr_free]);
531      } // end next_free_entry()
532   
533    /////////////////////////////////////////////////////////////////////
534    // The write_free_entry() function modify the next free entry.
535    // Arguments :
536    // - entry : the entry to write
537    /////////////////////////////////////////////////////////////////////
538      void write_free_entry(const HeapEntry &entry){
539        m_heap_tab[ptr_free].copy(entry);
540      } // end write_free_entry()
541
542    /////////////////////////////////////////////////////////////////////
543    // The write_free_ptr() function writes the pointer
544    // to the next free entry
545    /////////////////////////////////////////////////////////////////////
546      void write_free_ptr(const size_t &ptr){
547        assert( (ptr<tab_size) && "HeapDirectory error : try to write a wrong free pointer");
548        ptr_free = ptr;
549      } // end write_free_ptr()
550
551    /////////////////////////////////////////////////////////////////////
552    // The set_full() function sets the full bit (to true).
553    /////////////////////////////////////////////////////////////////////
554      void set_full(){
555        full = true;
556      } // end set_full()
557
558    /////////////////////////////////////////////////////////////////////
559    // The unset_full() function unsets the full bit (to false).
560    /////////////////////////////////////////////////////////////////////
561      void unset_full(){
562        full = false;
563      } // end unset_full()
564
565    /////////////////////////////////////////////////////////////////////
566    // The read() function returns a copy of
567    // the entry pointed by the argument
568    // Arguments :
569    //  - ptr : the pointer to the entry to read
570    /////////////////////////////////////////////////////////////////////
571      HeapEntry read(const size_t &ptr){
572        assert( (ptr<tab_size) && "HeapDirectory error : try to write a wrong free pointer");
573        return HeapEntry(m_heap_tab[ptr]);
574      } // end read()
575
576    /////////////////////////////////////////////////////////////////////
577    // The write() function writes an entry in the heap
578    // Arguments :
579    //  - ptr : the pointer to the entry to replace
580    //  - entry : the entry to write
581    /////////////////////////////////////////////////////////////////////
582      void write(const size_t &ptr, const HeapEntry &entry){
583        assert( (ptr<tab_size) && "HeapDirectory error : try to write a wrong free pointer");
584        m_heap_tab[ptr].copy(entry);
585      } // end write()
586
587  }; // end class HeapDirectory
588
589
590}} // end namespaces
591
592#endif
593
594// Local Variables:
595// tab-width: 4
596// c-basic-offset: 4
597// c-file-offsets:((innamespace . 0)(inline-open . 0))
598// indent-tabs-mode: nil
599// End:
600
601// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
602
Note: See TracBrowser for help on using the repository browser.