Solution for Problem 4 of EESM 5060 Assignment.

page_table.py

#
# Copyright by Lu Mingchaun
# 2016.10.21
# 
__author__ = "Nigshoxiz"

class Utils:
    @staticmethod
    def dec_to_bin(data, width):
        _bin_str = "{0:b}".format(data)
        if len(_bin_str) > width:
            return _bin_str[len(_bin_str)-width:len(_bin_str)]
        else:
            return "0" * (width - len(_bin_str)) + _bin_str

class Cache(object):
    def __init__(self,
                 associative=None,
                 LRU=True,
                 size=0,
                 bits_offset=0,
                 bits_index=0,
                 bits_tag=0,
                 show_steps=True
                 ):
        # main cache data
        # each row is an array of the following format:
        # [<valid bit>, <tag>, <data>]
        self.cache_table = []

        # if LRU = True, then lru_table is used to store
        # LRU counters (only available for associative caches)
        self.lru_table   = []

        self.associative = associative
        self.LRU = LRU
        self.size = size
        self.bits_offset = bits_offset
        self.bits_index  = bits_index
        self.bits_tag    = bits_tag
        self.show_steps  = show_steps
        
        self._way_sets = None
        self._size = size
        self._lru_size = None
        self._init_table()

    def _init_table(self):
        _size = self.size
        if _size == 0:
            if self.bits_index == 0:
                raise Exception("Cache Size is 0!")
            else:
                _size = 1 << self.bits_index
        # real size
        self._size = _size

        _way_size = 1
        _way_sets = 1
        if self.associative == "full":
            _way_size = _size
            _way_sets = 1
        elif self.associative == None or self.associative == 0:
            _way_size = 1
            _way_sets = _size
        else:
            if _size % self.associative != 0:
                raise Exception("Associative Number is improper!")
            else:
                _way_size = self.associative
                _way_sets = _size / self.associative
        self._way_sets = _way_sets
        for x in range(0, _way_sets):
            # [<valid bit>, <tag>, <data>]
            data_row = []
            for x in range(0, _way_size):
                item = [0, 0, 0]
                data_row.append(item)
            self.cache_table.append(data_row)

        # init LRU table
        _lru_size = 0
        _lru_sets = 0
        if self.LRU == True:
            if self.associative == "full":
                _lru_size = _size
                _lru_sets = 1
            elif self.associative == None or self.associative == 0:
                _lru_sets = 0
            else:
                if _size % self.associative != 0:
                    raise Exception("Associative Number is improper!")
                else:
                    _lru_size = self.associative
                    _lru_sets = _size / self.associative

            self._lru_size = _lru_size
        if _lru_sets > 0:
            for x in range(0, _lru_sets):
                row = [_lru_size] * _lru_size
                self.lru_table.append(row)

    def init_cell(self,cache_index, way_index, valid_bit, tag, data):
        '''
        set init status of cache by adding initial cache data
        :param data:
        :return:
        '''
        _cache_index = cache_index
        _way_index   = way_index
        if self.associative == "full":
            _cache_index = 0

        if self.associative == None or self.associative == 0:
            _way_index = 0

        cell = self.cache_table[_cache_index][_way_index]
        cell[0] = valid_bit
        cell[1] = tag
        cell[2] = data

    def _update_LRU(self, row_index, way_index, max_flag):
        if self.associative == 0 or self.associative == None:
            return None
        elif self.associative == "full":
            row_index = 0

        for lru_set in self.lru_table:
            for x in range(0, len(lru_set)):
                if lru_set[x] > 0:
                    lru_set[x] -= 1
        self.lru_table[row_index][way_index] = max_flag

    def _parse_address(self, address):
        if self.associative == "full":
            index = 0
            tag = int((address >> self.bits_offset))
        elif self.associative == 0 or self.associative == None:
            index = (address >> self.bits_offset) % self._size
            tag = int((address >> self.bits_offset) / self._size)
        else:
            index = (address >> self.bits_offset) % int(self._size / self.associative)
            tag = int((address >> self.bits_offset) / int(self._size / self.associative))

        return (tag, index)

    def read_hit(self, address):
        '''
        update cache when reading data
        return (<if hit>, <rtn_data>)
        '''
        tag, index = self._parse_address(address)
        # read hit
        _way_index = 0

        for i in self.cache_table[index]:
            _valid = i[0]
            _tag = i[1]
            _data  = i[2]
            if _tag == tag and _valid == 1:
                return_data = _data

                if self.show_steps == True:
                    print("(TLB) HIT row=%s, way=%s, tag=%s, data=%s\n" % (
                    index, _way_index, tag, _data))
                # LRU update
                if self.LRU == True:
                    self._update_LRU(index, _way_index, self._lru_size)
                return (True, return_data)
            _way_index += 1

        return (False, None)

    def read_miss(self, address, replace_data = None):
        tag, index = self._parse_address(address)

        if self.associative == None or self.associative == 0:
            _replace_way_index = 0
        else:
            _min = self.lru_table[index][0]
            _min_index = 0
            _replace_way_index = -1
            for x in range(0, len(self.lru_table[index])):
                if self.lru_table[index][x] <= _min:
                    _min = self.lru_table[index][x]
                    _min_index = x
                if self.cache_table[index][x][0] == 0:
                    # invalid
                    _replace_way_index = x
                    break

            if _replace_way_index == -1:
                _replace_way_index = _min_index

        # set valid
        self.cache_table[index][_replace_way_index][0] = 1
        # update tag
        self.cache_table[index][_replace_way_index][1] = tag
        # update data
        self.cache_table[index][_replace_way_index][2] = replace_data
        if self.show_steps == True:
            print("(TLB) MISS -> REPLACE row=%s, way=%s TO tag=%s, data=%s\n" % (index, _replace_way_index, tag, replace_data))

        if self.LRU == True:
            self._update_LRU(index, _replace_way_index, self._lru_size)

        return_data = replace_data
        return return_data

class TLB(Cache):
    def __init__(self,
                 associative=None,
                 size=0,
                 bits_offset=0,
                 bits_index=0,
                 ):
        Cache.__init__(self, associative=associative,LRU=True, size=size, bits_offset=bits_offset, bits_index=0, bits_tag=20)

    def init(self, data):
        _index = 0
        if self.associative == "full":
            for i in data:
                self.init_cell(0, _index, i[0], i[1], i[2])
                _index += 1
        # direct mapping
        elif self.associative == None or self.associative == 0:
            for i in data:
                self.init_cell(_index, 0, i[0], i[1], i[2])
                _index += 1
        else:
            for row in range(0, (self._size / self.associative)):
                for col in range(0, self.associative):
                    i = data[_index]
                    self.init_cell(row, col, i[0], i[1], i[2])
                    _index += 1


    def parse_address(self, address):
        return self._parse_address(address)

    def show_full(self):
        print("\n----------------")
        print("FINAL TLB DATA:")
        print(" V | TAG | DATA")
        print("----------------")

        for i in self.cache_table[0]:
            print("  %s | %s  | %s |" % (i[0], i[1], i[2]))

    def show_2(self):
        print("\n----------------")
        print("FINAL TLB DATA:")
        print(" V | TAG | DATA || V | TAG | DATA")
        print("----------------------------------")

        for ii in self.cache_table:
            i = ii[0]
            j = ii[1]
            print(" %s | %s  | %s || %s | %s  | %s |" % (i[0], i[1], i[2], j[0],j[1],j[2]))

    def show_direct(self):
        print("\n----------------")
        print("FINAL TLB DATA:")
        print(" INDEX | V | TAG | DATA")
        print("----------------")

        _index = 0
        for ii in self.cache_table:
            i = ii[0]
            print("   %s  | %s | %s  | %s |" % (_index, i[0], i[1], i[2]))
            _index += 1



class PageTable(object):
    def __init__(self, size=0, show_steps = True):
        # content item:
        # [<valid>, <page num>]
        self.table_contents = []
        self.table_size = size
        self.show_steps = show_steps

        self._max_page_num = 0

        self._init_table()

    def _init_table(self):
        for x in range(0, self.table_size):
            arr = [0, 0]
            self.table_contents.append(arr)

    def init(self, data):
        '''
        data format:
        [
            [<valid>, <page num>],
            OR
            [0, "D"]
            ...
        ]
        :param data:
        :return:
        '''
        for i in range(0, len(data)):
            a = self.table_contents[i]
            a[0] = data[i][0]
            a[1] = data[i][1]
        self._get_max_page_num()

    def _get_max_page_num(self):
        _max = 0
        for y in self.table_contents:
            if y[1] == "D":
                continue
            if y[1] > _max:
                _max = y[1]

        self._max_page_num = _max

    def read_update(self, index):
        _row = self.table_contents[index]
        return_data = None
        # page hit
        if _row[0] == 1:
            return_data = _row[1]
            if self.show_steps == True:
                print("    (PAGE) HIT index=%s, page_num=%s" % (index, _row[1]))
        # page fault
        elif _row[0] == 0 and _row[1] == "D":
            self._max_page_num += 1
            _new_page_data = self._max_page_num
            # set valid bit
            self.table_contents[index][0] = 1
            # set data
            self.table_contents[index][1] = _new_page_data
            if self.show_steps == True:
                print("    (PAGE) FAULT -> REPLACE index=%s, page_num=%s" % (index, _new_page_data))

            return_data = _new_page_data
        else:
            return None
        return return_data

    def show(self):
        print("\n----------")
        print("FINAL PAGE TABLE:")
        print(" V | DATA")
        print("----------")

        for i in self.table_contents:
            print("  %s | %s |" % (i[0],i[1]))

def Homework_Four():
    init_tlb_table = [
        [1, 11, 12],
        [1, 7, 4],
        [1, 3, 6],
        [0, 4, 9]
    ]

    init_page_table = [
        [1, 5],
        [0, "D"],
        [0, "D"],
        [1, 6],
        [1, 9],
        [1, 11],
        [0, "D"],
        [1, 4],
        [0, "D"],
        [0, "D"],
        [1, 3],
        [1, 12]
    ]

    stream_A = [4095, 31272, 15789, 15000, 7193, 4096, 8912]
    stream_B = [9452, 30964, 19136, 46502, 38110, 16653, 48480]

    tlb = TLB(
        # associative = "full" || 2 || None
        associative="full",
        size = 4,
        # bits_offfsets = 12 -->(4k) || 14 --> (16k)
        bits_offset=12
    )

    pt = PageTable(
        size= len(init_page_table)
    )

    tlb.init(init_tlb_table)
    pt.init(init_page_table)

    #for address in stream_A || stream_B:
    for address in stream_B:
        _result, _ = tlb.read_hit(address)
        # tlb miss
        if _result == False:
            tag, index = tlb.parse_address(address)
            # Many thanks to Emily's correction of direct-mapping situation
            # Nigshoxiz
            # 23/10/2016
            page_num = pt.read_update((tag*tlb._way_sets) + index)
            # replace TLB then
            tlb.read_miss(address, page_num)

    # tlb.show_full() || tlb.show_2() || tlb.show_direct()
    tlb.show_full()
    pt.show()

Homework_Four()