source: trunk/lib/generic_llsc_global_table/include/generic_llsc_global_table.h @ 482

Last change on this file since 482 was 482, checked in by joannou, 11 years ago

Updated llsc memcache table interface for sw operation (now able to invalidate a range of addresses)

File size: 17.8 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 * Alexandre JOANNOU <alexandre.joannou@lip6.fr>
24 *
25 */
26
27#ifndef SOCLIB_GENERIC_LLSC_GLOBAL_TABLE_H
28#define SOCLIB_GENERIC_LLSC_GLOBAL_TABLE_H
29
30#include <systemc>
31#include <arithmetics.h>
32#include <cassert>
33#include <cstring>
34#include <cmath>
35#include <iostream>
36#include <iomanip>
37
38namespace soclib
39{
40
41//////////////////////////
42//TODO switch to this
43/*
44template
45<
46size_t          nb_slots,   // max number of concerned shared resources
47typename        key_t,      // key type => max number of key; TODO wich one ?
48unsigned int    t_network,  // max number of cycle spent in the network when responding to a client (or more)
49unsigned int    t_inter_op, // min number of cycle between 2 reservation operation (or less but > 0)
50typename        addr_t      // ressource identifier type
51>
52*/
53template
54<
55size_t          nb_slots,   // desired number of slots
56unsigned int    nb_procs,   // number of processors in the system
57unsigned int    life_span,  // registratioçn life span (in # of LL operations)
58typename        addr_t      // address type
59>
60class GenericLLSCGlobalTable
61////////////////////////////
62{
63    private :
64
65    const std::string           name              ; // component name
66
67    uint32_t                    r_key  [nb_slots] ; // array of key
68    addr_t                      r_addr [nb_slots] ; // array of addresses
69    bool                        r_val  [nb_slots] ; // array of valid bits
70
71    uint32_t                    r_next_key        ; // value of the next key
72    sc_dt::sc_uint<nb_slots>    r_block_mask      ; // mask for the slots blocks
73    sc_dt::sc_uint<nb_slots>    r_last_counter    ; // mask for the slots blocks
74    size_t                      r_write_ptr       ; // index of next slot to replace
75    size_t                      r_last_empty      ; // index of last empty slot used
76
77    uint32_t                    m_cpt_evic        ; // number of eviction in the table
78    uint32_t                    m_cpt_ll          ; // number of ll accesses to the table
79    uint32_t                    m_cpt_ll_update   ; // number of ll accesses to the table that trigger an update TODO check that
80    uint32_t                    m_cpt_sc          ; // number of sc accesses to the table
81    uint32_t                    m_cpt_sc_success  ; // number of sc accesses to the table that are successful
82    uint32_t                    m_cpt_sw          ; // number of sw accesses to the table
83
84    ////////////////////////////////////////////////////////////////////////////
85    inline void upNextKey()
86    //  This function generates a new value for the next key
87    {
88        // generating a new key in r_next_key
89        r_next_key++;
90    }
91
92    ////////////////////////////////////////////////////////////////////////////
93    /*
94    inline void updateVictimSlot()
95    //  This function selects the next slot to be evicted
96    //  This is done by updating the value of r_write_ptr
97    {
98        // updates the position of the next slot to be replaced
99
100        static unsigned int count = 0;
101
102
103        // for each slot, check if it actually is the slot to replace
104        // this is done by checking count % 2^(i+1) == (2^i)-1
105        // 2^(i+1) being the period
106        // (2^i)-1 being the first apparition
107        // NB : the -1 in (2^i)-1 is here because of the 0 indexed array
108
109        for (size_t i = 0 ; i < nb_slots; i++)
110            if (count % (int)pow(2,i+1) == pow(2,i)-1)
111                r_write_ptr = i;
112
113        count = (count + 1) % (int) pow(2,nb_slots);    // mustn't go further than 2^nb_slots
114                                                        // or (2^nb_slots)+1 for a 1 indexed array
115                                                        // 2^32 = periodicity of slot #31
116    }
117    */
118    ////////////////////////////////////////////////////////////////////////////
119    inline void updateVictimSlot()
120    //  This function selects the next slot to be evicted
121    //  This is done by updating the value of r_write_ptr
122    {
123        sc_dt::sc_uint<nb_slots> new_counter;
124        sc_dt::sc_uint<nb_slots> xor_counter;
125
126        new_counter = newCounter(r_block_mask, r_last_counter);
127        xor_counter = new_counter ^ r_last_counter;
128
129        for (size_t i = nb_slots - 1; i >= 0; --i)
130        {
131            if(xor_counter[i])
132            {
133                r_write_ptr = i;
134                break;
135            }
136        }
137
138        r_last_counter = new_counter;
139    }
140
141    ////////////////////////////////////////////////////////////////////////////
142    inline sc_dt::sc_uint<nb_slots> newCounter(const sc_dt::sc_uint<nb_slots>& mask,
143                                               const sc_dt::sc_uint<nb_slots>& counter)
144    // This function generates the new counter //TODO comment more
145    {
146        //
147        return ((((~counter) & (counter << 1)) & mask) | (counter + 1));
148    }
149
150    ////////////////////////////////////////////////////////////////////////////
151    inline void init_block_mask()
152    //TODO
153    //This function selects the block mask to be used
154    //Need to provide another way to do that ?
155    {
156        /*
157        //try to dynamically compute the block mask ...
158        #define L2 soclib::common::uint32_log2
159        unsigned int budget = nb_slots - (L2(nb_procs) + 1); //TODO +1?
160        #undef L2
161        */
162
163        switch(nb_slots)
164        {
165            case 12:
166            r_block_mask = sc_dt::sc_uint<nb_slots>("0x000");
167            break;
168            case 16 :
169            r_block_mask = sc_dt::sc_uint<nb_slots>("0xA800");
170            break;
171            case 20 :
172            r_block_mask = sc_dt::sc_uint<nb_slots>("0xD5500");
173            break;
174            case 24 :
175            r_block_mask = sc_dt::sc_uint<nb_slots>("0xDB5540");
176            break;
177            case 28 :
178            r_block_mask = sc_dt::sc_uint<nb_slots>("0xEEDAAA0");
179            break;
180            case 32 :
181            r_block_mask = sc_dt::sc_uint<nb_slots>("0xF776D550");
182            break;
183            case 36 :
184            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFBDDDB550");
185            break;
186            case 40 :
187            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFDF7BB6D50");
188            break;
189            case 44 :
190            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFEFBDEEDAA8");
191            break;
192            case 48 :
193            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFF7EFBDDDAA8");
194            break;
195            case 52 :
196            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFFBFBF7BBB6A8");
197            break;
198            case 56 :
199            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFFDFEFDF7BB6A8");
200            break;
201            case 60 :
202            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFFF7FDFDF7BB6A8");
203            break;
204            case 64 :
205            r_block_mask = sc_dt::sc_uint<nb_slots>("0xFFFBFF7FBF7BB6A8");
206            break;
207            default:
208            assert(false && "nb_slots must be either 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60 or 64");
209        }
210    }
211
212    ////////////////////////////////////////////////////////////////////////////
213    inline int nextEmptySlot()
214    //  This function returns :
215    //  - the position of the first next empty slot in the table
216    //    (starting from the last empty slot used)
217    //    and updates the r_last_empty_slot register
218    //  - -1 if the table is full
219    {
220        size_t i = r_last_empty;
221        do
222        {
223            // checking if current slot is empty
224            if(!r_val[i])
225            {
226                // updating last empty slot and returning its position
227                r_last_empty = i;
228                return i;
229            }
230            // selecting next slot
231            i = (i+1) % nb_slots;
232        }
233        // stop if all slots have been tested
234        while(i != r_last_empty);
235
236        // the table is full
237        return -1;
238    }
239
240    ////////////////////////////////////////////////////////////////////////////
241    inline int hitAddr(const addr_t ad)
242    //  HIT on the address only
243    //  This function takes an addr_t ad
244    //  It returns :
245    //  - the position of the first HIT in the table
246    //  - -1 in case of MISS
247    //  NB : HIT = (slot addr == ad) AND (slot is valid)
248    {
249        // checking all slots
250        for (size_t i = 0; i < nb_slots; i++)
251        {
252            // if HIT, returning its position
253            if(ad == r_addr[i] && r_val[i]) return i;
254        }
255
256        // MISS
257        return -1;
258    }
259
260    ////////////////////////////////////////////////////////////////////////////
261    inline int hitAddrKey(const addr_t ad, const uint32_t key)
262    //  HIT on the address AND the on the signature
263    //  This function takes an addr_t ad and a uint32_t key
264    //  It returns :
265    //  - the position of the first HIT in the table
266    //  - -1 in case of MISS
267    //  NB : HIT = (slot addr == ad) AND (slot key == key)
268    //                               AND (slot is valid)
269    {
270        // checking all slots
271        for (size_t i = 0; i < nb_slots; i++)
272        {
273            // if HIT, returning its position
274            if(ad == r_addr[i] && key == r_key[i] && r_val[i]) return i;
275        }
276
277        // MISS
278        return -1;
279    }
280
281    ////////////////////////////////////////////////////////////////////////////
282    inline void reset()
283    {
284        // init the table
285        init();
286
287        // init stat counters
288        m_cpt_evic          = 0;
289        m_cpt_ll            = 0;
290        m_cpt_ll_update     = 0;
291        m_cpt_sc            = 0;
292        m_cpt_sc_success    = 0;
293        m_cpt_sw            = 0;
294    }
295
296
297    public:
298
299    ////////////////////////////////////////////////////////////////////////////
300    GenericLLSCGlobalTable( const std::string   &n = "llsc_global_table" )
301    :   name(n)
302    {
303        #define L2 soclib::common::uint32_log2
304        assert(nb_procs > 1); 
305        assert((int)nb_slots >= L2(nb_procs));
306        #undef L2
307        init();
308        init_block_mask();
309    }
310
311    ////////////////////////////////////////////////////////////////////////////
312    ~GenericLLSCGlobalTable()
313    {
314    }
315
316    ////////////////////////////////////////////////////////////////////////////
317    //  This function initializes the table (all slots empty)
318    inline void init()
319    {
320        // making all slots available by reseting all valid bits
321        std::memset(r_val, 0, sizeof(*r_val)*nb_slots);
322
323        // init registers
324        r_next_key          = 0;
325        r_last_counter      = 0; //TODO static in updateVictimSlot() ?
326        r_write_ptr         = 0;
327        r_last_empty        = 0;
328    }
329
330    ////////////////////////////////////////////////////////////////////////////
331    inline uint32_t ll(const addr_t ad)
332    //  This method registers an LL in the table and returns the key associated
333    //  with the registration
334    {
335        // increment the ll access counter (for stats)
336        m_cpt_ll++;
337
338        // hit addr ?
339        // YES
340        //      enough time left ?
341        //      YES
342        //          use this registration, return key
343        //      NO
344        //          update this registration with a new key, return new key
345        // NO
346        //      table has an empty slot ?
347        //      YES
348        //              select empty slot
349        //      NO
350        //              select victim slot (r_write_ptr)
351        //              update next victim
352        //      open registration on selected slot
353        //      update next key
354        //      return the registration key
355
356        //  Is the address found in the table ?
357        int pos = hitAddr(ad);
358
359        //  Yes, then return the associated key
360        if (pos >= 0)
361        {
362            if(r_key[pos] - r_next_key > life_span)
363                return r_key[pos];
364            r_key[pos] = r_next_key;
365            upNextKey();
366            m_cpt_ll_update++;
367            return r_key[pos];
368        }
369
370        //  No, then try to find an empty slot
371        pos = nextEmptySlot();
372
373        //  If there is no empty slot,
374        //  evict an existing registration
375        if (pos == -1)
376        {
377            //  get the position of the evicted registration
378            pos = r_write_ptr;
379            //  update the victim slot for the next eviction
380            updateVictimSlot();
381            // increment the eviction counter (for stats)
382            m_cpt_evic++;
383        }
384
385        // get the key for the new registration
386        uint32_t key    = r_next_key;
387        //  update the registration slot
388        r_key[pos]      = key   ;
389        r_addr[pos]     = ad    ;
390        r_val[pos]      = true  ;
391        //  compute the next key
392        upNextKey();
393
394        // return the key of the new registration
395        return key;
396
397    }
398
399    ////////////////////////////////////////////////////////////////////////////
400    inline bool sc(const addr_t ad, const uint32_t key)
401    //  This method checks if there is a valid registration for the SC (ad &&
402    //  key) and, in case of hit,invalidates the registration and returns true
403    //  (returns false otherwise)
404    //
405    //  The return value can be used to tell if the SC is atomic
406    {
407        // increment the sc access counter (for stats)
408        m_cpt_sc++;
409        // hit addr && hit key ?
410        // NO
411        //      return miss
412        // YES
413        //      inval registration and return hit
414
415        //  Is there a valid registration in the table ?
416        int pos = hitAddrKey(ad, key);
417        if(pos >= 0)
418        {
419            // increment the sc success counter (for stats)
420            m_cpt_sc_success++;
421            // invalidate the registration
422            r_val[pos] = false;
423            // return the success of the sc operation
424            return true;
425        }
426        else
427        {
428            // return the failure of the sc operation
429            return false;
430        }
431    }
432
433    ////////////////////////////////////////////////////////////////////////////
434    /*
435    inline void sw(const addr_t ad)
436    //  This method checks if there is a valid registration for the given
437    //  address and, in case of hit, invalidates the registration
438    {
439        // increment the sw access counter (for stats)
440        m_cpt_sw++;
441        // hit addr ?
442        // YES
443        //      inval registration
444        // NO
445        //      nothing
446
447        //  Is there a registration for the given address ?
448        int pos = hitAddr(ad);
449        //  If there is one, invalidate it
450        if(pos >= 0) r_val[pos] = false;
451    }
452    */
453    inline void sw(const addr_t nline, unsigned int min, unsigned int max)
454    //  This method checks if there is / are valid registration(s) for the given
455    //  range and, in case of hit(s), invalidates the registration(s)
456    {
457        // increment the sw access counter (for stats)
458        m_cpt_sw++;
459        // hit range ?
460        // YES
461        //      inval registration(s)
462        // NO
463        //      nothing
464
465        // for every address in the given range ...
466        for (unsigned int i = min; i <= max; i++)
467        {
468            //  Is there a registration for the given address ?
469            int pos = hitAddr(nline + i * 4);
470            //  If there is one, invalidate it
471            if (pos >= 0)
472            {
473                r_val[pos] = false;
474            }
475        }
476    }
477
478    ////////////////////////////////////////////////////////////////////////////
479    /*
480    void fileTrace(FILE* file)
481    {
482    }
483    */
484
485    ////////////////////////////////////////////////////////////////////////////
486    inline void print_trace(std::ostream& out = std::cout)
487    {
488        out <<  " ___________________________________" << std::endl
489            <<  "| " << std::setw(33) << "generic_llsc_global_table" << " |" << std::endl
490            <<  "| " << std::setw(33) << name << " |" << std::endl
491            <<  " ===================================" << std::endl
492            <<  "| "
493            <<  std::setw(11) << "addr"   << " | "
494            <<  std::setw(11) << "key"    << " | "
495            <<  std::setw(5)  << "val"
496            << " |" << std::endl
497            <<  " -----------------------------------" << std::endl;
498        for ( size_t i = 0; i < nb_slots ; i++ )
499        {
500            out << "| "
501                << std::showbase
502                << std::setw(11) << std::setfill('0')   << std::hex       << r_addr[i]    << " | "
503                << std::noshowbase
504                << std::setw(11) << std::setfill('0')   << std::dec       << r_key[i]     << " | "
505                << std::setw(5)  << std::setfill(' ')   << std::boolalpha << r_val[i]     << " |" << std::endl ;
506        }
507        out <<  " -----------------------------------" << std::endl
508            << std::noshowbase << std::dec << std::endl ;
509    }
510
511    ////////////////////////////////////////////////////////////////////////////
512    inline void print_stats(std::ostream& out = std::cout)
513    {
514        out << "# of ll accesses : " << m_cpt_ll            << std::endl
515            << "# of ll updates  : " << m_cpt_ll_update     << std::endl
516            << "# of sc accesses : " << m_cpt_sc            << std::endl
517            << "# of sc success  : " << m_cpt_sc_success    << std::endl
518            << "# of sw accesses : " << m_cpt_sw            << std::endl
519            << "# of evictions   : " << m_cpt_evic          << std::endl ;
520    }
521
522};
523
524} // end namespace soclib
525
526#endif
527
528// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
Note: See TracBrowser for help on using the repository browser.