source: trunk/platforms/almos-tsarv3-platforms/common/generic_cache/include/generic_cache.h @ 259

Last change on this file since 259 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.