source: trunk/lib/generic_llsc_local_table/include/generic_llsc_local_table.h @ 337

Last change on this file since 337 was 291, checked in by joannou, 12 years ago

Introducing new generic_llsc_local_table and generic_llsc_global_table components :
These two tables implement the new scalable LL/SC mechanism for TSAR.

  • generic_llsc_local_table, integrated in the vci_cc_vache_wrapper_v4 component. The table is accessed by the DCACHE_FSM. A two step registration (LL cmd/ LL rsp) sets a signature allocated by the global table for the pending LL/SC operation. An SC operation consumes the registration.
  • generic_llsc_global_table, integrated in the vci_mem_cache_v4 component. The table is accessed by the READ_FSM, WRITE_FSM, CAS_FSM, when accessing the directory. It generates a signature for LL registrations and performs SC operation by checking registration's valididty with that signature. SW operations simply invalidate a registrations.

N.B. :

  • The sizes of the tables are parameters, and are NOT a function of the architecture's size (scalable mechanism).
  • The LL are handled by the MEMCACHE in the READ_FSM.
  • The SC are handled by the MEMCACHE in the WRITE_FSM, and are no longer CAS emulated. CAS operation is now only performed by hardware mechanisms.
  • An extra field is added to the xram transaction table to save a pending LL's signature.
File size: 18.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_LOCAL_TABLE_H
28#define SOCLIB_GENERIC_LLSC_LOCAL_TABLE_H
29
30#include <systemc>
31#include <cassert>
32#include <cstring>
33#include <iostream>
34#include <iomanip>
35
36namespace soclib {
37
38//////////////////////////
39//TODO switch to this
40/*
41template
42<
43size_t          nb_slots,   // max number of authorized atomic operation per agent
44typename        key_t,      // key type => max number of key; TODO wich one ?
45unsigned int    t_network,  // max number of cycle spent in the network when responding to a client (or more)
46unsigned int    t_inter_op, // min number of cycle between 2 reservation operation (or less but > 0)
47typename        addr_t      // ressource identifier type
48>
49*/
50template
51<
52uint32_t    life_span               ,   // desired life-span for a reservation
53size_t      nb_slots    = 1         ,   // desired number of reservation
54typename    addr_t      = uint32_t  ,   // ressource identifier type
55typename    index_t     = size_t    ,   // transaction index/identifier type (trdid size)
56typename    key_t       = uint32_t      // key identifier type
57>
58class GenericLLSCLocalTable
59///////////////////////////
60{
61    public:
62
63    // command type
64    enum cmd_t
65    {
66        LL_CMD  = 0x8,  // create a reservation in the table (to be called when an ll cmd is emited)
67        LL_RSP  = 0x4,  // updates a reservation in the table (to be called when an ll rsp is received)
68        SC_CMD  = 0x2,  // invalidate a reservation (if necessary) and reset the wait register
69        SW_CMD  = 0x1,  // invalidate a reservation (if necessary)
70        NOP     = 0x0   // no operation (internal updates only : aging counters)
71    };
72
73    struct in_t
74    {
75        addr_t  address ;   // the address  argument of the command
76        index_t index   ;   // the index    argument of the command
77        key_t   key     ;   // the key      argument of the command
78        cmd_t   cmd     ;   // the command for the table to execute
79    };
80
81    struct out_t
82    {
83        bool    done    ;   // true if operation was actually performed
84        bool    hit     ;   // true if there was a hit on the address
85        key_t   key     ;   // the matching key for an SC_CMD
86        index_t index   ;   // the index of the reservation for a LL_CMD
87    };
88
89    private :
90
91    const std::string           name                ;   // component name
92
93    addr_t                      r_addr  [nb_slots]  ;   // array of addresses
94    key_t                       r_key   [nb_slots]  ;   // array of keys
95    uint32_t                    r_cnt   [nb_slots]  ;   // array of aging counters
96    bool                        r_val   [nb_slots]  ;   // array of valid bits
97
98    uint32_t                    r_wait              ;   // number of cycles to wait (when trying to perform a reservation)
99    uint32_t                    r_wait_cnt          ;   // counter counting down from r_wait to 0
100    size_t                      r_write_ptr         ;   // index of next slot to replace
101    size_t                      r_last_empty        ;   // index of last empty slot used
102
103    uint32_t                    m_cpt_ll_cmd        ;   // number of ll_cmd accesses to the table
104    uint32_t                    m_cpt_ll_cmd_done   ;   // number of ll_cmd accesses to the table (effectivelly done)
105    uint32_t                    m_cpt_ll_rsp        ;   // number of ll_rsp accesses to the table
106    uint32_t                    m_cpt_sc_cmd        ;   // number of sc_cmd accesses to the table
107    uint32_t                    m_cpt_sw_cmd        ;   // number of sw_cmd accesses to the table
108    uint32_t                    m_cpt_nop           ;   // number of nop    accesses to the table
109    uint32_t                    m_cpt_evic          ;   // number of eviction in the table
110    uint32_t                    m_cpt_death         ;   // number of death of reservations due to aging
111
112    ////////////////////////////////////////////////////////////////////////////
113    inline int hitAddr(const addr_t & address)
114    //  HIT on the address only
115    //  This function takes an addr_t address
116    //  It returns :
117    //  - the position of the first HIT in the table
118    //  - -1 in case of MISS
119    //  NB : HIT = (slot addr == ad) AND (slot is valid)
120    {
121        // checking all slots
122        for (size_t i = 0; i < nb_slots; i++)
123        {
124            // if HIT, returning its position
125            if(address == r_addr[i] && r_val[i]) return i;
126        }
127
128        // MISS
129        return -1;
130    }
131
132    ////////////////////////////////////////////////////////////////////////////
133    inline int nextEmptySlot()
134    //  This function returns :
135    //  - the position of the first next empty slot in the table
136    //    (starting from the last empty slot used)
137    //    and updates the r_last_empty_slot register
138    //  - -1 if the table is full
139    {
140        size_t i = r_last_empty;
141        do
142        {
143            // checking if current slot is empty
144            if(!r_val[i])
145            {
146                // updating last empty slot and returning its position
147                r_last_empty = i;
148                return i;
149            }
150            // selecting next slot
151            i = (i+1) % nb_slots;
152        }
153        // stop if all slots have been tested
154        while(i != r_last_empty);
155
156        // the table is full
157        return -1;
158    }
159
160    ////////////////////////////////////////////////////////////////////////////
161    inline void updateVictimSlot()
162    //  This function selects the next slot to be evicted
163    //  This is done by updating the value of r_write_ptr
164    {
165        r_write_ptr = 0;
166    }
167
168    public:
169
170    ////////////////////////////////////////////////////////////////////////////
171    GenericLLSCLocalTable(  const std::string    &n = "llsc_local_table" )
172    :   name(n)
173    {
174        init();
175    }
176
177    ////////////////////////////////////////////////////////////////////////////
178    ~GenericLLSCLocalTable()
179    {
180    }
181
182    ////////////////////////////////////////////////////////////////////////////
183    inline void init()
184    //  This function initializes the table (all slots empty)
185    {
186        // making all slots available by reseting all valid bits
187        std::memset(r_val, 0, sizeof(*r_val)*nb_slots);
188
189        // init registers
190        r_wait              = 0;
191        r_wait_cnt          = 0;
192        r_write_ptr         = 0;
193        r_last_empty        = 0;
194
195        // init stat counters
196        m_cpt_ll_cmd        = 0;
197        m_cpt_ll_cmd_done   = 0;
198        m_cpt_ll_rsp        = 0;
199        m_cpt_sc_cmd        = 0;
200        m_cpt_sw_cmd        = 0;
201        m_cpt_nop           = 0;
202        m_cpt_evic          = 0;
203        m_cpt_death         = 0;
204    }
205
206    ////////////////////////////////////////////////////////////////////////////
207    inline void exec(const in_t & in, out_t & out)
208    // This function has to be called every cycle !
209    // It implements the behaviour of the generic_llsc_local_table.
210    // 5 commands can be performed :
211    // - LL_CMD
212    // - LL_RSP
213    // - SC_CMD
214    // - SW_CMD
215    // - NOP
216    // Each one of them are described further below
217    {
218        // First check the command
219        switch(in.cmd)
220        {
221            case LL_CMD :
222            // INPUTS :
223            // - address
224            //
225            // Check if r_wait_cnt has reached 0
226            // - YES
227            //      - the wait counter is re initialized with the content of the
228            //        r_wait register
229            //      - the r_wait register is doubled (<< 1) (delay mechanism)
230            //      - check if there is an empty slot
231            //          if YES, select the empty slot
232            //          if NO, select victim slot and update next victim
233            //      - the address of the selected slot is initialized with the given
234            //        address
235            //      - the aging counter of the selected slot is initialized with
236            //        the life-span of a reservation
237            //      - the valid bit of the selected slot is set to true
238            //
239            //          - out.hit   <= don't care
240            //          - out.done  <= true
241            //          - out.key   <= don't care
242            //          - out.index <= i the index of the selected slot
243            //
244            // - NO
245            //      - decrement r_wait_cnt
246            //
247            //          - out.hit   <= don't care
248            //          - out.done  <= false
249            //          - out.key   <= don't care
250            //          - out.index <= don't care
251            {
252                // increment the ll_cmd access counter (for stats)
253                m_cpt_ll_cmd++;
254
255                if(r_wait_cnt == 0)
256                {
257                    // increment the ll_cmd access counter (effectivelly done) (for stats)
258                    m_cpt_ll_cmd_done++;
259
260                    // increase the lenght of the next waiting session
261                    //r_wait      = (r_wait << 1) + 1 ;
262                    // re initialize the wait counter //TODO check this...
263                    //r_wait_cnt  = r_wait;
264
265                    // select a slot for the reservation
266                    // first check for an empty slot ...
267                    int pos = nextEmptySlot();
268                    // If there is no empty slot,
269                    // evict an existing registration
270                    if (pos == -1)
271                    {
272                        // get the position of the evicted registration
273                        pos = r_write_ptr;
274                        // update the victim slot for the next eviction
275                        updateVictimSlot();
276                        // increment the eviction counter (for stats)
277                        m_cpt_evic++;
278                    }
279
280                    // inscription in the slot
281                    r_addr  [pos]   =   in.address  ;
282                    r_cnt   [pos]   =   life_span   ;
283                    r_val   [pos]   =   true        ;
284
285                    // construct out argument
286                    //out.hit   = don't care;
287                    out.done    = 1;
288                    //out.key   = don't care;
289                    out.index   = pos;
290                }
291                else
292                {
293                    // decrement the wait counter
294                    r_wait_cnt--;
295
296                    // construct out argument
297                    //out.hit   = don't care;
298                    out.done    = 0;
299                    //out.key   = don't care;
300                    //out.index = don't care;
301                }
302            }
303            break;
304            case LL_RSP :
305            // INPUTS :
306            // - index
307            // - key
308            //
309            //  - the key of the reservation is updated with the given key
310            //
311            //      - out.hit   <= don't care
312            //      - out.done  <= true
313            //      - out.key   <= don't care
314            //      - out.index <= don't care
315            {
316                // increment the ll_rsp access counter (for stats)
317                m_cpt_ll_rsp++;
318
319                // insert new key in reservation
320                r_key[in.index]  = in.key;
321
322                // construct out argument
323                out.hit     = 1;
324                out.done    = 1;
325                //out.key   = don't care;
326                //out.index = don't care;
327            }
328            break;
329            case SC_CMD :
330            // INPUTS :
331            // - address
332            //
333            // Check if there is a hit for the address
334            // - HIT
335            //      - invalidate reservation
336            //      - reset r_wait to 0
337            //
338            //          - out.hit   <= true
339            //          - out.done  <= true
340            //          - out.key   <= r_key[hit_index]
341            //          - out.index <= don't care
342            //
343            // - NO HIT
344            //
345            //      - out.hit   <= false
346            //      - out.done  <= true
347            //      - out.key   <= don't care
348            //      - out.index <= don't care
349            {
350                // increment the sc_cmd access counter (for stats)
351                m_cpt_sc_cmd++;
352
353                // Is there a valid reservation in the table ?
354                int pos = hitAddr(in.address);
355                if(pos >= 0)
356                {
357                    // invalidate reservation
358                    r_val[pos]  = false     ;
359                    // reset r_wait to 0
360                    r_wait      = 0         ;
361                    // construct out argument
362                    out.hit     = 1         ;
363                    out.done    = 1         ;
364                    out.key     = r_key[pos];
365                }
366                else
367                {
368                    // construct out argument
369                    out.hit     = 0;
370                    out.done    = 1;
371                    //out.key   = don't care;
372                    //out.index = don't care;
373                }
374            }
375            break;
376            case SW_CMD :
377            // INPUTS :
378            // - address
379            //
380            // Check if there is a hit for the address
381            // - HIT
382            //      - invalidate reservation
383            //
384            //          - out.hit   <= true
385            //          - out.done  <= true
386            //          - out.key   <= don't care
387            //          - out.index <= don't care
388            //
389            // - NO HIT
390            //
391            //      - out.hit   <= false
392            //      - out.done  <= true
393            //      - out.key   <= don't care
394            //      - out.index <= don't care
395            {
396                // increment the sw_cmd access counter (for stats)
397                m_cpt_sw_cmd++;
398
399                // Is there a valid reservation in the table ?
400                int pos = hitAddr(in.address);
401                if(pos >= 0)
402                {
403                    // invalidate reservation
404                    r_val[pos]  = false     ;
405                    // construct out argument
406                    out.hit     = 1         ;
407                    out.done    = 1         ;
408                    //out.key   = don't care ;
409                    //out.index = don't care;
410                }
411                else
412                {
413                    // construct out argument
414                    out.hit     = 0;
415                    out.done    = 1;
416                    //out.key   = don't care;
417                    //out.index = don't care;
418                }
419            }
420            break;
421            case NOP :
422            // NOTHING except for the usual aging counter updates
423            //
424            //      - out.hit   <= don't care
425            //      - out.done  <= 1
426            //      - out.key   <= don't care
427            //      - out.index <= don't care
428            {
429                // increment the nop access counter (for stats)
430                m_cpt_nop++;
431                // construct out argument
432                //out.hit   = don't care;
433                out.done    = 1;
434                //out.key   = don't care;
435                //out.index = don't care;
436            }
437            break;
438        }
439        // aging counters ...
440        // for each slot
441        for (size_t i = 0; i < nb_slots; i++)
442        {
443            // decrement the counter
444            r_cnt[i]--;
445            // check if the counter has reached 0 (for an actual reservation,
446            // i.e. a valid reservation)
447            if(r_cnt[i] == 0 && r_val[i])
448            {
449                // increment the death counter (for stats)
450                m_cpt_death++;
451                // invalidate the reservation
452                r_val[i] = false;
453            }
454        }
455    }
456
457    ////////////////////////////////////////////////////////////////////////////
458    inline void print_trace(std::ostream& out = std::cout)
459    {
460        out <<  " _________________________________________________" << std::endl
461            <<  "| " << std::setw(47) << "generic_llsc_local_table" << " |" << std::endl
462            <<  "| " << std::setw(47) << name << " |" << std::endl
463            <<  " =================================================" << std::endl
464            <<  "| "
465            <<  std::setw(11) << "addr"   << " | "
466            <<  std::setw(11) << "key"    << " | "
467            <<  std::setw(11) << "cnt"    << " | "
468            <<  std::setw(5)  << "val"
469            << " |" << std::endl
470            <<  " -------------------------------------------------" << std::endl;
471        for ( size_t i = 0; i < nb_slots ; i++ )
472        {
473            out << "| "
474                << std::showbase
475                << std::setw(11) << std::setfill('0')   << std::hex       << r_addr[i]    << " | "
476                << std::noshowbase
477                << std::setw(11) << std::setfill('0')   << std::dec       << r_key[i]     << " | "
478                << std::setw(11) << std::setfill('0')   << std::dec       << r_cnt[i]     << " | "
479                << std::setw(5)  << std::setfill(' ')   << std::boolalpha << r_val[i]     << " |" << std::endl ;
480        }
481        out <<  " -------------------------------------------------" << std::endl
482            << std::noshowbase << std::dec << std::endl ;
483    }
484
485    ////////////////////////////////////////////////////////////////////////////
486    inline void print_stats(std::ostream& out = std::cout)
487    {
488        out << "# of ll_cmd accesses                     : " << m_cpt_ll_cmd        << std::endl
489            << "# of ll_cmd accesses (effectivelly done) : " << m_cpt_ll_cmd_done   << std::endl
490            << "# of ll_rsp accesses                     : " << m_cpt_ll_rsp        << std::endl
491            << "# of sc_cmd accesses                     : " << m_cpt_sc_cmd        << std::endl
492            << "# of sw_cmd accesses                     : " << m_cpt_sw_cmd        << std::endl
493            << "# of nop    accesses                     : " << m_cpt_nop           << std::endl
494            << "# of eviction                            : " << m_cpt_evic          << std::endl
495            << "# of death by aging                      : " << m_cpt_death         << std::endl ;
496    }
497
498};
499
500} // 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.