source: branches/v4/lib/generic_llsc_global_table/include/generic_llsc_global_table.h @ 647

Last change on this file since 647 was 334, checked in by joannou, 12 years ago

Separated stat counters resets from internal registers resets

File size: 17.1 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); //nb_procs must be more than 1
305        //TODO >= or > ?
306        assert(nb_slots >= L2(nb_procs)); // nb_slot cannot be less then log2(nb_procs)
307        #undef L2
308        init();
309        init_block_mask();
310    }
311
312    ////////////////////////////////////////////////////////////////////////////
313    ~GenericLLSCGlobalTable()
314    {
315    }
316
317    ////////////////////////////////////////////////////////////////////////////
318    //  This function initializes the table (all slots empty)
319    inline void init()
320    {
321        // making all slots available by reseting all valid bits
322        std::memset(r_val, 0, sizeof(*r_val)*nb_slots);
323
324        // init registers
325        r_next_key          = 0;
326        r_last_counter      = 0; //TODO static in updateVictimSlot() ?
327        r_write_ptr         = 0;
328        r_last_empty        = 0;
329    }
330
331    ////////////////////////////////////////////////////////////////////////////
332    inline uint32_t ll(const addr_t ad)
333    //  This method registers an LL in the table and returns the key associated
334    //  with the registration
335    {
336        // increment the ll access counter (for stats)
337        m_cpt_ll++;
338
339        // hit addr ?
340        // YES
341        //      enough time left ?
342        //      YES
343        //          use this registration, return key
344        //      NO
345        //          update this registration with a new key, return new key
346        // NO
347        //      table has an empty slot ?
348        //      YES
349        //              select empty slot
350        //      NO
351        //              select victim slot (r_write_ptr)
352        //              update next victim
353        //      open registration on selected slot
354        //      update next key
355        //      return the registration key
356
357        //  Is the address found in the table ?
358        int pos = hitAddr(ad);
359
360        //  Yes, then return the associated key
361        if (pos >= 0)
362        {
363            if(r_key[pos] - r_next_key > life_span)
364                return r_key[pos];
365            r_key[pos] = r_next_key;
366            upNextKey();
367            m_cpt_ll_update++;
368            return r_key[pos];
369        }
370
371        //  No, then try to find an empty slot
372        pos = nextEmptySlot();
373
374        //  If there is no empty slot,
375        //  evict an existing registration
376        if (pos == -1)
377        {
378            //  get the position of the evicted registration
379            pos = r_write_ptr;
380            //  update the victim slot for the next eviction
381            updateVictimSlot();
382            // increment the eviction counter (for stats)
383            m_cpt_evic++;
384        }
385
386        // get the key for the new registration
387        uint32_t key    = r_next_key;
388        //  update the registration slot
389        r_key[pos]      = key   ;
390        r_addr[pos]     = ad    ;
391        r_val[pos]      = true  ;
392        //  compute the next key
393        upNextKey();
394
395        // return the key of the new registration
396        return key;
397
398    }
399
400    ////////////////////////////////////////////////////////////////////////////
401    inline bool sc(const addr_t ad, const uint32_t key)
402    //  This method checks if there is a valid registration for the SC (ad &&
403    //  key) and, in case of hit,invalidates the registration and returns true
404    //  (returns false otherwise)
405    //
406    //  The return value can be used to tell if the SC is atomic
407    {
408        // increment the sc access counter (for stats)
409        m_cpt_sc++;
410        // hit addr && hit key ?
411        // NO
412        //      return miss
413        // YES
414        //      inval registration and return hit
415
416        //  Is there a valid registration in the table ?
417        int pos = hitAddrKey(ad, key);
418        if(pos >= 0)
419        {
420            // increment the sc success counter (for stats)
421            m_cpt_sc_success++;
422            // invalidate the registration
423            r_val[pos] = false;
424            // return the success of the sc operation
425            return true;
426        }
427        else
428        {
429            // return the failure of the sc operation
430            return false;
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
454    ////////////////////////////////////////////////////////////////////////////
455    /*
456    void fileTrace(FILE* file)
457    {
458    }
459    */
460
461    ////////////////////////////////////////////////////////////////////////////
462    inline void print_trace(std::ostream& out = std::cout)
463    {
464        out <<  " ___________________________________" << std::endl
465            <<  "| " << std::setw(33) << "generic_llsc_global_table" << " |" << std::endl
466            <<  "| " << std::setw(33) << name << " |" << std::endl
467            <<  " ===================================" << std::endl
468            <<  "| "
469            <<  std::setw(11) << "addr"   << " | "
470            <<  std::setw(11) << "key"    << " | "
471            <<  std::setw(5)  << "val"
472            << " |" << std::endl
473            <<  " -----------------------------------" << std::endl;
474        for ( size_t i = 0; i < nb_slots ; i++ )
475        {
476            out << "| "
477                << std::showbase
478                << std::setw(11) << std::setfill('0')   << std::hex       << r_addr[i]    << " | "
479                << std::noshowbase
480                << std::setw(11) << std::setfill('0')   << std::dec       << r_key[i]     << " | "
481                << std::setw(5)  << std::setfill(' ')   << std::boolalpha << r_val[i]     << " |" << std::endl ;
482        }
483        out <<  " -----------------------------------" << std::endl
484            << std::noshowbase << std::dec << std::endl ;
485    }
486
487    ////////////////////////////////////////////////////////////////////////////
488    inline void print_stats(std::ostream& out = std::cout)
489    {
490        out << "# of ll accesses : " << m_cpt_ll            << std::endl
491            << "# of ll updates  : " << m_cpt_ll_update     << std::endl
492            << "# of sc accesses : " << m_cpt_sc            << std::endl
493            << "# of sc success  : " << m_cpt_sc_success    << std::endl
494            << "# of sw accesses : " << m_cpt_sw            << std::endl
495            << "# of evictions   : " << m_cpt_evic          << std::endl ;
496    }
497
498};
499
500} // end namespace soclib
501
502#endif
503
504// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
Note: See TracBrowser for help on using the repository browser.