source: branches/v4/platforms/almos-tsarv3-platforms/common/generic_cache/include/generic_cache.h

Last change on this file was 259, checked in by almaless, 12 years ago

Introduce ALMOS used platforms for TSAR.
See the package's README file for more information.
File size: 22.5 KB
Line 
1/* -*- c++ -*-
2 *
3 * SOCLIB_LGPL_HEADER_BEGIN
4 *
5 * This file is part of SoCLib, GNU LGPLv2.1.
6 *
7 * SoCLib is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU Lesser General Public License as published
9 * by the Free Software Foundation; version 2.1 of the License.
10 *
11 * SoCLib is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with SoCLib; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 * 02110-1301 USA
20 *
21 * SOCLIB_LGPL_HEADER_END
22 *
23 * Copyright (c) UPMC, Lip6
24 *         Alain Greiner <alain.greiner@lip6.fr> July 2008
25 *
26 * Maintainers: alain yang
27 */
28
29//////////////////////////////////////////////////////////////////////////////////
30// This object is a generic, set associative, cache providing read(), write(),
31// inval() and update() access primitives. The replacement policy is pseudo-LRU.
32// The DATA part is implemented as an int32_t array.
33// The DIRECTORY part is implemented as an uint32_t array.
34//
35// Constructor parameters are :
36// - std::string    &name
37// - size_t         nways   : number of associativity levels
38// - size_t         nsets   : number of sets
39// - size_t         nwords  : number of words in a cache line
40// The nways, nsets, nwords parameters must be power of 2
41// The nsets parameter cannot be larger than 1024
42// The nways parameter cannot be larger than 16
43// The nwords parameter cannot be larger than 64
44//
45// Template parameter is :
46// - addr_t : address format to access the cache
47// The address can be larger than 32 bits, but the TAG field
48// cannot be larger than 32 bits.
49/////////////////////////////////////////////////////////////////////////////////
50// History :
51// 05/01/2010
52// Two new methods select_before_update(), and update_after_select() have
53// been introduced to support update in two cycles, when the cache directory
54// is implemented as a simple port RAM.
55/////////////////////////////////////////////////////////////////////////////////
56
57#ifndef SOCLIB_GENERIC_CACHE_H
58#define SOCLIB_GENERIC_CACHE_H
59
60#include <systemc>
61#include <cassert>
62#include "arithmetics.h"
63#include "static_assert.h"
64#include "mapping_table.h"
65#include <cstring>
66
67namespace soclib { 
68
69//////////////////////////
70template<typename addr_t>
71class GenericCache
72//////////////////////////
73{
74    typedef uint32_t    data_t;
75    typedef uint32_t    tag_t;
76
77    data_t              *r_data ;
78    tag_t               *r_tag ;
79    bool                *r_val ;
80    bool                *r_lru ;
81
82    size_t              m_ways; 
83    size_t              m_sets; 
84    size_t              m_words;
85    size_t              m_next_way;
86
87    const soclib::common::AddressMaskingTable<addr_t>  m_x ;
88    const soclib::common::AddressMaskingTable<addr_t>  m_y ;
89    const soclib::common::AddressMaskingTable<addr_t>  m_z ;
90
91    //////////////////////////////////////////////////////////////
92    inline data_t &cache_data(size_t way, size_t set, size_t word)
93    {
94        return r_data[(way*m_sets*m_words)+(set*m_words)+word];
95    }
96
97    //////////////////////////////////////////////
98    inline tag_t &cache_tag(size_t way, size_t set)
99    {
100        return r_tag[(way*m_sets)+set];
101    }
102
103    //////////////////////////////////////////////
104    inline bool &cache_val(size_t way, size_t set)
105    {
106        return r_val[(way*m_sets)+set];
107    }
108
109    //////////////////////////////////////////////
110    inline bool &cache_lru(size_t way, size_t set)
111    {
112        return r_lru[(way*m_sets)+set];
113    }
114
115    //////////////////////////////////////////////
116    inline void cache_set_lru(size_t way, size_t set)
117    {
118        size_t way2;
119
120        cache_lru(way, set) = true;
121        for (way2 = 0; way2 < m_ways; way2++ ) {
122            if (cache_lru(way2, set) == false) return;
123        }
124        /* all lines are new -> they all become old */
125        for (way2 = 0; way2 < m_ways; way2++ ) {
126            cache_lru(way2, set) = false;
127        }
128    }
129
130public:
131
132    //////////////////////////////////////////////
133    GenericCache(   const std::string   &name,
134                    size_t              nways, 
135                    size_t              nsets, 
136                    size_t              nwords)
137        : m_ways(nways),
138          m_sets(nsets),
139          m_words(nwords),
140
141#define l2 soclib::common::uint32_log2
142
143          m_x( l2(nwords), l2(sizeof(data_t))),
144          m_y( l2(nsets), l2(nwords) + l2(sizeof(data_t))),
145          m_z( 8*sizeof(addr_t) - l2(nsets) - l2(nwords) - l2(sizeof(data_t)),
146               l2(nsets) + l2(nwords) + l2(sizeof(data_t)))
147
148#undef l2
149    {
150        assert(IS_POW_OF_2(nways));
151        assert(IS_POW_OF_2(nsets));
152        assert(IS_POW_OF_2(nwords));
153        assert(nwords);
154        assert(nsets);
155        assert(nways);
156        assert(nwords <= 64);
157        assert(nsets <= 1024);
158        assert(nways <= 16);
159
160#ifdef GENERIC_CACHE_DEBUG
161        std::cout
162            << " m_x: " << m_x
163            << " m_y: " << m_y
164            << " m_z: " << m_z
165            << std::endl;
166#endif
167
168        r_data = new data_t[nways*nsets*nwords];
169        r_tag  = new tag_t[nways*nsets];
170        r_val  = new bool[nways*nsets];
171        r_lru  = new bool[nways*nsets];
172        m_next_way = 0;
173    }
174
175    ////////////////
176    ~GenericCache()
177    {
178        delete [] r_data;
179        delete [] r_tag;
180        delete [] r_val;
181        delete [] r_lru;
182    }
183
184    ////////////////////
185    inline void reset( )
186    {
187        std::memset(r_data, 0, sizeof(*r_data)*m_ways*m_sets*m_words);
188        std::memset(r_tag, 0, sizeof(*r_tag)*m_ways*m_sets);
189        std::memset(r_val, 0, sizeof(*r_val)*m_ways*m_sets);
190        std::memset(r_lru, 0, sizeof(*r_lru)*m_ways*m_sets);
191    }
192
193    ////////////////////////////////////////////////////////
194    inline bool flush(size_t way, size_t set, addr_t* nline)
195    {
196        if ( cache_val(way,set) ) 
197        {
198            cache_val(way,set) = false;
199            *nline = (data_t)cache_tag(way,set)* m_sets + set;
200            return true;
201        }
202        return false;
203    }
204
205    /////////////////////////////////////////
206    inline bool read( addr_t ad, data_t* dt)
207    {
208        const tag_t       tag  = m_z[ad];
209        const size_t      set  = m_y[ad];
210        const size_t      word = m_x[ad];
211
212#ifdef GENERIC_CACHE_DEBUG
213        std::cout << "Reading data at " << ad << ", "
214                  << " s/t=" << set << '/' << tag
215                  << ", ";
216#endif
217
218        for ( size_t way = 0; way < m_ways; way++ ) {
219            if ( (tag == cache_tag(way, set)) && cache_val(way, set) ) {
220                *dt = cache_data(way, set, word);
221                cache_set_lru(way, set);
222
223#ifdef GENERIC_CACHE_DEBUG
224                std::cout << "hit"
225                          << " w/s/t=" << way << '/' << set << '/' << tag
226                          << " = " << *dt << std::endl;
227#endif
228                return true;
229            }
230        }
231
232#ifdef GENERIC_CACHE_DEBUG
233        std::cout << "miss" << std::endl;
234#endif
235        return false;
236    }
237
238    /////////////////////////////////////////////////////////////////////
239    inline bool read( addr_t ad, data_t* dt, size_t* n_way, size_t* n_set)
240    {
241        const tag_t       tag  = m_z[ad];
242        const size_t      set  = m_y[ad];
243        const size_t      word = m_x[ad];
244
245#ifdef GENERIC_CACHE_DEBUG
246        std::cout << "Reading data at " << ad << ", "
247                  << " s/t=" << set << '/' << tag
248                  << ", ";
249#endif
250
251        for ( size_t way = 0; way < m_ways; way++ ) {
252            if ( (tag == cache_tag(way, set)) && cache_val(way, set) ) {
253                *dt = cache_data(way, set, word);
254                cache_set_lru(way, set);
255                *n_way = way;
256                *n_set = set;
257
258#ifdef GENERIC_CACHE_DEBUG
259                std::cout << "hit"
260                          << " w/s/t=" << way << '/' << set << '/' << tag
261                          << " = " << *dt << std::endl;
262#endif
263                return true;
264            }
265        }
266#ifdef GENERIC_CACHE_DEBUG
267        std::cout << "miss" << std::endl;
268#endif
269        return false;
270    }
271
272    //////////////////////////////////////////////////////
273    inline bool setinbit( addr_t ad, bool* buf, bool val )
274    {
275        const tag_t       tag  = m_z[ad];
276        const size_t      set  = m_y[ad];
277
278        for ( size_t way = 0; way < m_ways; way++ ) {
279            if ( (tag == cache_tag(way, set)) && cache_val(way, set) ) {
280                buf[m_sets*way+set] = val;
281
282#ifdef GENERIC_CACHE_DEBUG
283                std::cout << "hit"
284                          << " w/s=" << way << '/' << set
285                          << std::endl;
286#endif
287                return true;
288            }
289        }
290#ifdef GENERIC_CACHE_DEBUG
291        std::cout << "miss" << std::endl;
292#endif
293        return false;
294    }
295
296    ////////////////////////////////////////////
297    inline tag_t get_tag(size_t way, size_t set)
298    {
299        return cache_tag(way, set);
300    }
301
302    /////////////////////////////////////////
303    inline bool write( addr_t ad, data_t dt )
304    {
305        const tag_t       tag  = m_z[ad];
306        const size_t      set  = m_y[ad];
307        const size_t      word = m_x[ad];
308
309#ifdef GENERIC_CACHE_DEBUG
310        std::cout << "Writing data at " << ad << ", "
311                  << " s/t=" << set << '/' << tag
312                  << ", ";
313#endif
314
315        for ( size_t way = 0; way < m_ways; way++ ) {
316            if ( (tag == cache_tag(way, set)) && cache_val(way, set) ) {
317                cache_data(way, set, word) = dt;
318                cache_set_lru(way, set);
319
320#ifdef GENERIC_CACHE_DEBUG
321                std::cout << "hit"
322                          << " w/s/t=" << way << '/' << set << '/' << tag
323                          << std::endl;
324#endif
325                return true;
326            }
327        }
328
329#ifdef GENERIC_CACHE_DEBUG
330        std::cout << "miss" << std::endl;
331#endif
332        return false;
333    }
334
335    /////////////////////////////////////////////////////////////////////
336    inline bool write( addr_t ad, data_t dt, size_t* nway, size_t* nset )
337    {
338        const tag_t       tag  = m_z[ad];
339        const size_t      set  = m_y[ad];
340        const size_t      word = m_x[ad];
341
342#ifdef GENERIC_CACHE_DEBUG
343        std::cout << "Writing data at " << ad << ", "
344                  << " s/t=" << set << '/' << tag
345                  << ", ";
346#endif
347
348        for ( size_t way = 0; way < m_ways; way++ ) {
349            if ( (tag == cache_tag(way, set)) && cache_val(way, set) ) {
350                cache_data(way, set, word) = dt;
351                cache_set_lru(way, set);
352                *nway = way;
353                *nset = set;
354
355#ifdef GENERIC_CACHE_DEBUG
356                std::cout << "hit"
357                          << " w/s/t=" << way << '/' << set << '/' << tag
358                          << std::endl;
359#endif
360                return true;
361            }
362        }
363
364#ifdef GENERIC_CACHE_DEBUG
365        std::cout << "miss" << std::endl;
366#endif
367        return false;
368    }
369
370    inline void write(size_t way, size_t set, size_t word, data_t data)
371    {
372        cache_data(way, set, word) = data;
373    }
374
375    //////////////////////////////
376    inline bool inval( addr_t ad )
377    {
378        bool        hit = false;
379        const tag_t       tag = m_z[ad];
380        const size_t      set = m_y[ad];
381
382#ifdef GENERIC_CACHE_DEBUG
383        std::cout << "Invalidating data at " << ad << ", "
384                  << " s/t=" << set << '/' << tag
385                  << ", ";
386#endif
387
388        for ( size_t way = 0 ; way < m_ways && !hit ; way++ ) {
389            if ( (tag == cache_tag(way, set)) && cache_val(way, set) ) {
390                hit     = true;
391                cache_val(way, set) = false;
392                cache_lru(way, set) = false;
393
394#ifdef GENERIC_CACHE_DEBUG
395                std::cout << "hit"
396                          << " w/s/t=" << way << '/' << set << '/' << tag
397                          << " ";
398#endif
399            }
400        }
401
402#ifdef GENERIC_CACHE_DEBUG
403        std::cout << std::endl;
404#endif
405        return hit;
406    }
407
408    ////////////////////////////////////////////////////////////
409    inline bool inval( addr_t ad, size_t* n_way, size_t* n_set )
410    {
411        bool    hit = false;
412        const tag_t       tag = m_z[ad];
413        const size_t      set = m_y[ad];
414
415#ifdef GENERIC_CACHE_DEBUG
416        std::cout << "Invalidating data at " << ad << ", "
417                  << " s/t=" << set << '/' << tag
418                  << ", ";
419#endif
420
421        for ( size_t way = 0 ; way < m_ways && !hit ; way++ ) {
422            if ( (tag == cache_tag(way, set)) && cache_val(way, set) ) {
423                hit     = true;
424                cache_val(way, set) = false;
425                cache_lru(way, set) = false;
426                *n_way = way;
427                *n_set = set;
428
429#ifdef GENERIC_CACHE_DEBUG
430                std::cout << "hit"
431                          << " w/s/t=" << way << '/' << set << '/' << tag
432                          << " ";
433#endif
434            }
435        }
436
437#ifdef GENERIC_CACHE_DEBUG
438        std::cout << std::endl;
439#endif
440        return hit;
441    }
442
443    ///////////////////////////////////////////////////////////////////
444    // This function implements a pseudo LRU policy for a one cycle
445    // line replacement. It can be used if the directory is implemented
446    // as a dual port RAM.
447    // 1 - First we search an invalid way
448    // 2 - Il all ways are valid, we search the first old way
449    // 3 - If all ways are recent, they are all transformed to old.
450    //     and we select the way with index 0.
451    // The victim line index is returned in the victim parameter.
452    // This function returns true, if the victim line is valid.
453    ///////////////////////////////////////////////////////////////////
454    inline bool update( addr_t ad, data_t* buf, addr_t* victim )
455    {
456        size_t set, way;
457        bool   cleanup = victim_select(ad, victim, &way, &set);
458        victim_update_tag (ad, way, set);
459
460        for ( size_t word = 0 ; word < m_words ; word++ ) {
461            cache_data(way, set, word) = buf[word] ;
462        }
463
464        return cleanup;
465    }
466
467    inline bool victim_select( addr_t ad, addr_t* victim, size_t * way, size_t * set )
468    {
469        bool   found   = false;
470        bool   cleanup = false;
471        *set = m_y[ad];
472        *way = 0;
473
474        // Schearch and invalid slot
475        for ( size_t _way = 0 ; _way < m_ways && !found ; _way++ )
476        {
477            if ( !cache_val(_way, *set) )
478            {
479                found   = true;
480                cleanup = false;
481                *way    = _way;
482            }
483        }
484
485        // No invalid way, scearch the lru
486        if ( !found )
487        { 
488            for ( size_t _way = 0 ; _way < m_ways && !found ; _way++ )
489            {
490                if ( !cache_lru(_way, *set) )
491                {
492                    cache_val (_way, *set) = false;
493                    found   = true;
494                    cleanup = true;
495                    *way    = _way;
496                }
497            }
498        }
499
500        assert(found && "all ways can't be new at the same time");
501
502        *victim = (addr_t)((cache_tag(*way,*set) * m_sets) + *set);
503
504        return cleanup;
505    }
506
507    inline void victim_update_tag( addr_t ad, size_t way, size_t set )
508    {
509        tag_t  tag     = m_z[ad];
510
511        cache_tag    (way, set) = tag;
512        cache_val    (way, set) = true;
513        cache_set_lru(way, set);
514    }
515
516/*
517    //////////////////////////////////////////////////////////////////////////////
518    // The two functions select_before_update() & update_after_select()
519    // can be used to perform a line replacement in two cycles
520    // (when the directory is implemented as a single port RAM)
521    //
522    // The select_before_update function implements a pseudo LRU
523    // policy and and returns the victim line index and the selected
524    // way in the return arguments. The selected cache line is invalidated.
525    // This function returns true, il the victim line is valid,
526    ////////////////////////////////////////////////////////////////////////////////
527    inline bool select_before_update( addr_t ad, size_t* selway, addr_t* victim )
528    {
529        size_t      set     = m_y[ad];
530        // search an empty slot (using valid bit)
531        for ( size_t way = 0 ; way < m_ways ; way++ )
532        {
533            if ( !cache_val(way, set) )
534            {
535                *selway = way;
536                *victim = (addr_t)((cache_tag(way, set) * m_sets) + set);
537                return  false;
538            }
539        }
540        // search an old line (using lru bit)
541        for ( size_t way = 0 ; way < m_ways ; way++ )
542        {
543            if ( !cache_lru(way, set) )
544            {
545                cache_val(way, set) = false;
546                *selway = way;
547                *victim = (addr_t)((cache_tag(way, set) * m_sets) + set);
548                return  true;
549            }
550        }
551        assert("all lines can't be new at the same time");
552        return true;
553    }
554
555    /////////////////////////////////////////////////////////////////////
556    // The two functions select_before_update() & update_after_select()
557    // can be used to perform a line replacement in two cycles
558    // (when the directory is implemented as a single port RAM)
559    //
560    // The update_after select() function performs the actual
561    // update of the cache line.
562    /////////////////////////////////////////////////////////////////////
563    inline void update_after_select( data_t* buf, size_t way, addr_t ad)
564    {
565        tag_t       tag     = m_z[ad];
566        size_t      set     = m_y[ad];
567
568        cache_tag(way, set) = tag;
569        cache_val(way, set) = true;
570        cache_set_lru(way, set);
571        for ( size_t word = 0 ; word < m_words ; word++ ) cache_data(way, set, word) = buf[word] ;
572    }
573*/
574    ///////////////////////////
575    inline bool find( addr_t ad, 
576                      bool* itlb_buf, bool* dtlb_buf,
577                      size_t* n_way, size_t* n_set, 
578                      addr_t* victim )
579    {
580        size_t      set     = m_y[ad];
581        size_t      selway  = 0;
582        bool        found   = false;
583        bool        cleanup = false;
584
585        for ( size_t way = 0 ; way < m_ways && !found ; way++ ) {
586            if ( !cache_val(way, set) ) {
587                found   = true;
588                cleanup = false;
589                selway  = way;
590            }
591        }
592        if ( !found ) {
593            /* No invalid way, look for an old way, in priotity order:
594             * an old way which is not refereced by any tlb
595             * an old way which is not referenced by the itlb
596             * an old way which is not referenced by the dtlb
597             * an old way
598             */
599            for ( size_t way = 0 ; way < m_ways && !found ; way++ ) {
600                if ( !cache_lru(way, set) && !itlb_buf[m_sets*way+set]
601                    && !dtlb_buf[m_sets*way+set]) {
602                    found   = true;
603                    cleanup = true;
604                    selway  = way;
605                }
606            }
607            for ( size_t way = 0 ; way < m_ways && !found ; way++ ) {
608                if ( !cache_lru(way, set) && !itlb_buf[m_sets*way+set]) {
609                    found   = true;
610                    cleanup = true;
611                    selway = way;
612                }
613            }
614            for ( size_t way = 0 ; way < m_ways && !found ; way++ ) {
615                if ( !cache_lru(way, set) && !dtlb_buf[m_sets*way+set]) {
616                    found   = true;
617                    cleanup = true;
618                    selway = way;
619                }
620            }
621            for ( size_t way = 0 ; way < m_ways && !found ; way++ ) {
622                if ( !cache_lru(way, set)) {
623                    found   = true;
624                    cleanup = true;
625                    selway = way;
626                }
627            }
628        }
629        assert(found && "all ways can't be new at the same time");
630        *victim = (addr_t)((cache_tag(selway, set) * m_sets) + set);
631        cache_val(selway, set) = false;
632        *n_way = selway;
633        *n_set = set;
634        return cleanup;
635    }
636
637    /////////////////////////////////////////////////////////////////////////
638    inline void update( addr_t ad, size_t n_way, size_t n_set, data_t* buf )
639    {
640        tag_t tag = m_z[ad];
641
642        cache_tag(n_way, n_set) = tag;
643        cache_val(n_way, n_set) = true;
644        cache_set_lru(n_way, n_set);
645        for ( size_t word = 0 ; word < m_words ; word++ ) {
646            cache_data(n_way, n_set, word) = buf[word] ;
647        }
648    }
649
650    ///////////////////////////////////////////////////////////////////
651    // cleanupcheck function is used for checking whether a line exists
652    inline bool cleanupcheck( addr_t ad )
653    {
654        const tag_t       tag  = m_z[ad];
655        const size_t      set  = m_y[ad];
656
657        for ( size_t way = 0; way < m_ways; way++ ) {
658            if ( (tag == cache_tag(way, set)) && cache_val(way, set) ) {
659                return true;
660            }
661        }
662        return false;
663    }
664
665    ///////////////////////////
666    void fileTrace(FILE* file)
667    {
668        for( size_t nway = 0 ; nway < m_ways ; nway++) 
669        {
670            for( size_t nset = 0 ; nset < m_sets ; nset++) 
671            {
672                if( cache_val(nway, nset) ) fprintf(file, " V / ");
673                else                        fprintf(file, "   / ");
674                fprintf(file, "way %d / ", (int)nway);
675                fprintf(file, "set %d / ", (int)nset);
676                fprintf(file, "@ = %08zX / ", ((cache_tag(nway, nset)*m_sets+nset)*m_words*4));
677                for( size_t nword = m_words ; nword > 0 ; nword--) 
678                {
679                    unsigned int data = cache_data(nway, nset, nword-1);
680                    fprintf(file, "%08X ", data );
681                }
682                fprintf(file, "\n");
683            }
684        }
685    }
686
687    ////////////////////////
688    inline void printTrace()
689    {
690        for ( size_t way = 0; way < m_ways ; way++ ) 
691        {
692            for ( size_t set = 0 ; set < m_sets ; set++ )
693            {
694                if ( cache_val(way,set) ) std::cout << "  * " ;
695                else                      std::cout << "    " ;
696                std::cout << std::dec << "way " << way << std::hex << " | " ;
697                std::cout << "@ " << (cache_tag(way,set)*m_words*m_sets+m_words*set)*4 ;
698                for ( size_t word = 0 ; word < m_words ; word++ )
699                {
700                    std::cout << " | " << cache_data(way,set,word) ;
701                }
702                std::cout << std::endl ;
703            }
704        }
705    }
706   
707};
708
709} // namespace soclib
710
711#endif
712
713// Local Variables:
714// tab-width: 4
715// c-basic-offset: 4
716// c-file-offsets:((innamespace . 0)(inline-open . 0))
717// indent-tabs-mode: nil
718// End:
719
720// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
721
Note: See TracBrowser for help on using the repository browser.