pad.mattdiesel.co.uk

Snippet - Direct-mapping Cache Example

Direct-mapping Cache Example (C++)


Created 2015-11-27 15:59:17.159470 by Matt.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <stdexcept>

inline int ilog2(unsigned int v) {
    static const unsigned int b[] = {0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0,
                                     0xFF00FF00, 0xFFFF0000
                                    };
    unsigned int r = (v & b[0]) != 0;
    for (int i = 4; i > 0; i--) {
        r |= ((v & b[i]) != 0) << i;
    }

    return r;
}

inline bool ispow2(unsigned int n) {
    return n && !(n & (n - 1));
}

class cache
{
    int _blocksize;
    int _blocks;
    int _size;
    int _assoc;
    int _wordsize;
    int _blocks_log2;
    unsigned int* _tags;
    int* _lastaccess;

public:
    int hits;
    int misses;
    int accesses;

    cache(int blocksize, int size, int associativity, int wordsize)
        : _blocksize(blocksize), _blocks(size / blocksize), _size(size), _assoc(associativity), _wordsize(wordsize), hits(0), misses(0), accesses(0)
    {
        if (!ispow2(size) || !ispow2(_blocks)) {
            // throw std::argument_exception("Size/blocks must be power of 2.");
            std::cout << "Size/blocks must be power of 2." << std::endl;
        }

        _blocks_log2 = ilog2(_blocks);

        _tags = new unsigned int[_blocks * _assoc];
        _lastaccess = new int[_blocks * _assoc];

        for (int i = 0; i < _blocks * _assoc; i++) {
            _lastaccess[i] = 0;
        }
    }
    ~cache() {
    };

    bool access(unsigned int addr) {
        int block = (addr >> (_wordsize - 1)) % _blocks;
        unsigned int t = addr >> (_wordsize - 1 + _blocks_log2);

        accesses++;
        int a = 0;
        for (a; a < _assoc; a++) {
            if (t == _tags[block + _blocks * a] && _lastaccess[block + _blocks * a]) {
                hits++;
                _lastaccess[block + _blocks * a] = accesses;
                return true;
            }
        }

        // Miss, add to cache
        misses++;
        int lru = 0xFFFF;
        int lrua = 0;

        for (a = 0; a < _assoc; a++) {
            if (_lastaccess[block + _blocks * a] < lru) {
                lru = _lastaccess[block + _blocks * a];
                lrua = a;
            }

            if (!_lastaccess[block + _blocks * a]) {
                // Empty set
                _lastaccess[block + _blocks * a] = accesses;
                _tags[block + _blocks * a] = t;
                return false;
            }
        }

        // No empty sets, remove lru.
        _lastaccess[block + _blocks * lrua] = accesses;
        _tags[block + _blocks * lrua] = t;

        return false;
    }
};

int main(int argc, char const *argv[])
{
    cache c(1, 8, 1, 1);

    std::cout << c.access(22) << std::endl;
    std::cout << c.access(26) << std::endl;
    std::cout << c.access(22) << std::endl;
    std::cout << c.access(26) << std::endl;
    std::cout << c.access(16) << std::endl;
    std::cout << c.access(3) << std::endl;
    std::cout << c.access(16) << std::endl;
    std::cout << c.access(19) << std::endl;
    std::cout << c.access(16) << std::endl;
    std::cout << c.access(3) << std::endl;

    std::cout << c.hits << " hits, " << c.misses << " misses, " << c.accesses << " accesses" << std::endl;

    return 0;
}