b469f1f6-6a00-4958-bfb0-f9fbf427a589

Committed 06 Jun 2024 06:38PM UTC coverage: 93.399% (-0.03%) from 93.431%

Build # b469f1f6-6a00-4958-bfb0-f9fbf427a589

Build Type

push

circleci

Committed by

Nic30

Commit Message

docs

Run Details

8040 of 9100 branches covered (88.35%)

39136 of 41902 relevant lines covered (93.4%)

0.93 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.07

/hwtLib/amba/axi_comp/cache/cacheWriteAllocWawOnlyWritePropagating.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from typing import List

from hwt.code import Or, SwitchLogic, If
from hwt.code_utils import rename_signal
from hwt.hdl.types.bits import HBits
from hwt.hdl.types.defs import BIT
from hwt.hdl.types.struct import HStruct
from hwt.hwIOs.hwIOStruct import HwIOStruct
from hwt.hwIOs.hwIOStruct import HwIOStructRdVld
from hwt.hwIOs.std import HwIODataRdVld
from hwt.hwIOs.utils import addClkRstn, propagateClkRstn
from hwt.hwParam import HwParam
from hwt.math import log2ceil, isPow2
from hwt.pyUtils.typingFuture import override
from hwt.synthesizer.rtlLevel.rtlSignal import RtlSignal
from hwtLib.amba.axi4 import Axi4, Axi4_r, Axi4_addr, Axi4_w, Axi4_b
from hwtLib.amba.axi_comp.cache.addrTypeConfig import CacheAddrTypeConfig
from hwtLib.amba.axi_comp.cache.lru_array import AxiCacheLruArray, HwIOIndexWayRdVld
from hwtLib.amba.axi_comp.cache.tag_array import AxiCacheTagArray, \
    HwIOAxiCacheTagArrayLookupRes, HwIOAxiCacheTagArrayUpdate
from hwtLib.amba.axis_comp.builder import Axi4SBuilder
from hwtLib.amba.constants import RESP_OKAY, BURST_INCR, CACHE_DEFAULT, \
    LOCK_DEFAULT, BYTES_IN_TRANS, PROT_DEFAULT, QOS_DEFAULT
from hwtLib.commonHwIO.addr import HwIOAddrRdVld
from hwtLib.handshaked.builder import HsBuilder
from hwtLib.handshaked.reg import HandshakedReg
from hwtLib.handshaked.streamNode import StreamNode
from hwtLib.logic.binToOneHot import binToOneHot
from hwtLib.mem.ramTransactional import RamTransactional
from hwtLib.mem.ramTransactional_io import TransRamHsR, TransRamHsW
from pyMathBitPrecise.bit_utils import mask


# https://chipress.co/category/job-roles-titles/page/16/
# https://chipress.co/2019/04/13/can-you-show-the-state-transition-for-snoop-based-scheme-using-msi-protocol/
# https://github.com/airin711/Verilog-caches
# https://github.com/rajshadow/4-way-set-associative-cache-verilog
# https://github.com/xdesigns/4way-cache
# https://github.com/prasadp4009/2-way-Set-Associative-Cache-Controller
class AxiCacheWriteAllocWawOnlyWritePropagating(CacheAddrTypeConfig):
    """
    Non-blocking pipelined Set Associative cache for AXI interfaces which is designed
    to work with an LSU which solves only WAW (write-after-write) conflicts.


    :note: Write propagation in this context means that any read received will contain lastly written
        data in some time few clock before (derived from read latency of the LSU)
        the actual request (due to latency of the read resolution).
        This means that if master check last N transaction for collision the data is asserted to be
        in last version or to be marked with an invalidation flag. The N is usually 3 and
        is derived from the latency of LSU which should be connected behind this cache.

    :attention: This cache solves only WAW conflicts, this means that WAR and RAW conflicts
        are left unsolved and must be handled on master side. This is suitable for a cumulative
        operations in general as together with write propagating it allows master component
        to significantly reduce buffers and collision detection logic.

    .. figure:: ./_static/AxiCacheWriteAllocWawOnlyWritePropagating.png

    :see: :class:`hwtLib.amba.axi_comp.cache.CacheAddrTypeConfig`
    :ivar DATA_WIDTH: data width of interfaces
    :ivar WAY_CNT: number of places where one cache line can be stored

    :note: 1-way associative = directly mapped
    :note: This cache does not check access collision with a requests to main (slave) memory.
        It only provides an information for LSU to do so. The LSU is supposed to be connected
        between main memory and this cache (= on master port where slave should be connected).

    * The tag_array contains tags and cache line status flags for cache lines.
    * The lsu_array contains the data for data for pseudo LRU (Last Recently Used) cache replacement policy.
      It is stored in a separate array due to high requirements for concurrent access which results
      in increased memory consumption.
    * The data_array is a RAM where data for cache lines is stored.

    The memories are separated because they have a different memory port requirements
    and we want to keep the number of memory ports and the size of the memory minimal
    as resource requirements grow exponentially with increasing number of memory ports.

    .. hwt-autodoc:: _example_AxiCacheWriteAllocWawOnlyWritePropagating
    """

    @override
    def hwConfig(self):
        Axi4.hwConfig(self)
        self.WAY_CNT = HwParam(4)
        self.MAX_BLOCK_DATA_WIDTH = HwParam(None)
        self.IS_PREINITIALIZED = HwParam(False)
        CacheAddrTypeConfig.hwConfig(self)

    @override
    def hwDeclr(self):
        assert self.CACHE_LINE_CNT > 0, self.CACHE_LINE_CNT
        assert self.WAY_CNT > 0 and isPow2(self.WAY_CNT), self.WAY_CNT
        assert self.CACHE_LINE_CNT % self.WAY_CNT == 0, (self.CACHE_LINE_CNT, self.WAY_CNT)
        assert isPow2(self.CACHE_LINE_SIZE // (self.DATA_WIDTH // 8))
        assert self.DATA_WIDTH % 8 == 0, self.DATA_WIDTH
        self._compupte_tag_index_offset_widths()

        addClkRstn(self)
        with self._hwParamsShared():
            self.s = Axi4()
            self.m = Axi4()._m()

            rc = self.read_cancel = HwIOAddrRdVld()._m()
            rc.ID_WIDTH = 0

            self.tag_array = AxiCacheTagArray()
            self.lru_array = AxiCacheLruArray()
            for a in [self.tag_array, self.lru_array]:
                a.PORT_CNT = 2  # r+w

        da = RamTransactional()
        da.MAX_BLOCK_DATA_WIDTH = self.MAX_BLOCK_DATA_WIDTH
        da.WORD_WIDTH = self.CACHE_LINE_SIZE * 8
        da.DATA_WIDTH = self.DATA_WIDTH
        da.ADDR_WIDTH = log2ceil(self.CACHE_LINE_CNT)
        da.R_ID_WIDTH = self.ID_WIDTH
        da.W_PRIV_T = HStruct(
            # used to construct an address for flush of original item in cache which is beeing replaced
            (HBits(self.TAG_W), "victim_tag"),  # index part of address is an address on flush_data.addr channel
            (HBits(self.ID_WIDTH), "id"),
        )
        self.data_array = da

        # self.flush = HandshakeSync()
        # self.init = HandshakeSync()

    def axiAddrDefaults(self, a: Axi4_addr):
        a.burst(BURST_INCR)
        a.len(self.CACHE_LINE_SIZE // (self.DATA_WIDTH // 8) - 1)
        a.cache(CACHE_DEFAULT)
        a.lock(LOCK_DEFAULT)
        a.size(BYTES_IN_TRANS(self.DATA_WIDTH // 8))
        a.prot(PROT_DEFAULT)
        a.qos(QOS_DEFAULT)

    def connect_tag_lookup(self, init_in_progress: RtlSignal):
        in_ar, in_aw = self.s.ar, self.s.aw
        # connect address lookups to a tag array
        tags = self.tag_array
        for a, tag_lookup in zip((in_ar, in_aw), tags.lookup):
            tag_lookup.addr(a.addr)
            tag_lookup.id(a.id)
            if a is in_aw:
                rc = self.read_cancel
                rc.addr(a.addr)
                StreamNode([a], [tag_lookup, rc]).sync(~init_in_progress)
            else:
                StreamNode([a], [tag_lookup]).sync(~init_in_progress)

    def incr_lru_on_hit(self,
                        lru_incr: HwIOIndexWayRdVld,
                        tag_res: HwIOAxiCacheTagArrayLookupRes):
        index = self.parse_addr(tag_res.addr)[1]
        lru_incr.vld(tag_res.vld & tag_res.found)
        lru_incr.way(tag_res.way)
        lru_incr.index(index)

    def read_handler(self,
                     ar_tagRes: HwIOAxiCacheTagArrayLookupRes,  # in
                     axi_s_r: Axi4_r,  # out
                     ar_lru_incr: HwIOIndexWayRdVld,  # out
                     da_r: TransRamHsR,  # in
                     axi_m_ar: Axi4_addr,  # out
                     axi_m_r: Axi4_r  # in
                     ):
        """
        :param ar_tagRes: Read request including information from tag_array for given tag.
        :param axi_s_r: Read data requested by ar_tagRes.
        :param ar_lru_incr: Incrementing LRU for given address when tag is found.
        :param da_r: Read interface of data_array used when tag is found.
        :param axi_m_ar: Read address request interface to memory when tag is not found.
        :param axi_m_r: Read data requested by axi_m_ar from memory when tag is not found.

        .. figure:: ./_static/AxiCacheWriteAllocWawOnlyWritePropagating_read_handler.png
        """
        self.incr_lru_on_hit(ar_lru_incr, ar_tagRes)

        # addd a register with backup register for poential overflow
        # we need this as we need to check if we can store data in advance.
        # this is because we need a higher priority for flushing
        # in order to avoid deadlock.
        data_arr_read_req = HsBuilder(self, da_r.addr, master_to_slave=False)\
            .buff(1, latency=(1, 2))\
            .end

        # send read request to data_array
        ar_index = self.parse_addr(ar_tagRes.addr)[1]
        data_arr_read_req.priv(ar_tagRes.id)
        data_arr_read_req.addr(self.addr_in_data_array(ar_tagRes.way, ar_index)),

        # delegate read request to m.ar if not hit
        StreamNode(
            [ar_tagRes],
            [axi_m_ar, data_arr_read_req],
            extraConds={
                axi_m_ar: ar_tagRes.vld & ~ar_tagRes.found,
                data_arr_read_req: ar_tagRes.vld & ar_tagRes.found,
            },
            skipWhen={
                axi_m_ar: ar_tagRes.vld & ar_tagRes.found,
                data_arr_read_req: ar_tagRes.vld & ~ar_tagRes.found,
            },
        ).sync()

        axi_m_ar.addr(ar_tagRes.addr)
        axi_m_ar.id(ar_tagRes.id)
        self.axiAddrDefaults(axi_m_ar)

        data_arr_read = axi_s_r.__class__()
        data_arr_read._updateHwParamsFrom(axi_s_r)
        self.data_arr_read = data_arr_read

        data_arr_read(da_r.data, exclude=[data_arr_read.resp])
        data_arr_read.resp(RESP_OKAY)

        data_arr_read = Axi4SBuilder(self, data_arr_read)\
            .buff(1, latency=(1, 2))\
            .end

        s_r = Axi4SBuilder.join_prioritized(self, [
            data_arr_read,
            axi_m_r,
        ]).end
        axi_s_r(s_r)

    def resolve_victim(self, st0_o_tag_found: RtlSignal,  # in
                       st0_o_found_way: RtlSignal,  # in
                       st0_o_tags: List[HwIOStruct],  # in
                       victim_way: HwIODataRdVld  # in
                       ):
        _victim_way = self._sig("victim_way_tmp", HBits(log2ceil(self.WAY_CNT)))
        _victim_tag = self._sig("victim_tag_tmp", HBits(self.TAG_W))
        SwitchLogic(
            [
                # select first empty tag
                (~tag.valid, [
                    _victim_way(i),
                    _victim_tag(tag.tag),
                ]) for i, tag in enumerate(st0_o_tags)
            ],
            default=[
                # select an victim specified by victim_way
                _victim_way(victim_way.data),
                SwitchLogic([
                        (victim_way.data._eq(i), _victim_tag(tag.tag))
                        for i, tag in enumerate(st0_o_tags)
                    ],
                    default=_victim_tag(None)
                )
            ]
        )
        _victim_way = st0_o_tag_found._ternary(st0_o_found_way, _victim_way)
        return _victim_way, _victim_tag

    def write_handler(self,
                      aw_tagRes: HwIOAxiCacheTagArrayLookupRes,  # in
                      axi_s_b: Axi4_b,  # out
                      aw_lru_incr: HwIOIndexWayRdVld,  # out
                      victim_way_req: HwIOAddrRdVld, victim_way_resp: HwIODataRdVld,  # out, in
                      da_w: TransRamHsW,  # in
                      tag_update: HwIOAxiCacheTagArrayUpdate,  # out
                      init_in_progress: RtlSignal,  # in
                      ):
        """
        :param aw_tagRes: Write request including in information from tag_array for given tag.
        :param axi_s_b: Response requested by aw_tagRes
        :param aw_lru_incr: Incrementing LRU for given address when tag is found.
        :param victim_way_req: Request victim from LRU array for a specified index, when cache is full.
        :param victim_way_resp: Victim address requested by victim_way_req
        :param da_w: Write interface of data_array to write and initiate flush when cache is full.
        :param tag_update: Tag update interface for newly written data.

        .. figure:: ./_static/AxiCacheWriteAllocWawOnlyWritePropagating_write_handler.png
        """
        # note that the lru update happens even if the data is stalled
        # but that is not a problem because it wont change the order of the usage
        # of the cahceline
        self.incr_lru_on_hit(aw_lru_incr, aw_tagRes)

        st0 = HandshakedReg(HwIOStructRdVld)
        st0.T = HStruct(
            # the original id and address of a write transaction
            (self.s.aw.id._dtype, "write_id"),
            (self.s.aw.addr._dtype, "replacement_addr"),
            # array of tags for cachelines with this index
            (aw_tagRes.TAG_T[aw_tagRes.WAY_CNT], "tags"),
            (BIT, "tag_found"),
            (BIT, "had_empty"),  # had some empty tag
            (aw_tagRes.way._dtype, "found_way"),  # way of where tag was found
        )
        self.victim_load_status0 = st0

        st0_i = st0.dataIn.data
        # resolve if we need to select a victim and optianally ask for it
        has_empty = rename_signal(self, Or(*(~t.valid for t in aw_tagRes.tags)), "has_empty")
        st0_i.write_id(aw_tagRes.id),
        st0_i.replacement_addr(aw_tagRes.addr),
        st0_i.tags(aw_tagRes.tags),
        st0_i.tag_found(aw_tagRes.found),
        st0_i.found_way(aw_tagRes.way),
        st0_i.had_empty(has_empty),

        victim_way_req.addr(self.parse_addr(aw_tagRes.addr)[1])
        StreamNode(
            [aw_tagRes],
            [victim_way_req, st0.dataIn],
            skipWhen={
                victim_way_req: aw_tagRes.vld & (
                                aw_tagRes.found | 
                                has_empty
                            )
            },
            extraConds={
                victim_way_req:~aw_tagRes.found & ~has_empty
            }
        ).sync()

        ########################## st1 - pre (read request resolution, victim address resolution) ##############

        st0_o = st0.dataOut.data

        _victim_way, _victim_tag = self.resolve_victim(st0_o.tag_found, st0_o.found_way, st0_o.tags, victim_way_resp)

        da_w.addr.flush(rename_signal(self, st0.dataOut.vld & (~st0_o.had_empty & ~st0_o.tag_found), "need_to_flush"))
        da_w.addr.priv.id(st0_o.write_id)
        da_w.addr.addr(self.addr_in_data_array(st0_o.tag_found._ternary(st0_o.found_way, _victim_way),
                                               self.parse_addr(st0_o.replacement_addr)[1])),
        da_w.addr.priv.victim_tag(_victim_tag)

        MULTI_WORD = self.data_array.ITEM_WORDS > 1
        if MULTI_WORD:
            st1_id = HandshakedReg(HwIODataRdVld)
            st1_id.LATENCY = (1, 2)
            st1_id.DATA_WIDTH = self.ID_WIDTH
            self.victim_load_status1 = st1_id
            st1_id.dataIn.data(st0_o.write_id)
        # placed between st0, st1
        StreamNode(
            [victim_way_resp, st0.dataOut],
            [da_w.addr, st1_id.dataIn] if MULTI_WORD else [da_w.addr],
            extraConds={
                victim_way_resp:~st0_o.tag_found & ~st0_o.had_empty,
            },
            skipWhen={
                victim_way_resp: st0_o.tag_found | st0_o.had_empty,
            }
        ).sync()

        in_w = Axi4SBuilder(self, self.s.w)\
            .buff(self.tag_array.LOOKUP_LATENCY + 4)\
            .end
        if MULTI_WORD:
            StreamNode(
                [in_w, st1_id.dataOut],
                [da_w.data, axi_s_b],
                extraConds={axi_s_b: in_w.valid & in_w.last,
                            st1_id.dataOut: in_w.valid & in_w.last},
                skipWhen={axi_s_b: in_w.valid & ~in_w.last,
                          st1_id.dataOut: in_w.valid & ~in_w.last},
            ).sync(~init_in_progress)
            axi_s_b.id(st1_id.dataOut.data)  # todo
        else:
            StreamNode(
                [in_w],
                [da_w.data, axi_s_b],
                extraConds={axi_s_b: in_w.valid & in_w.last},
                skipWhen={axi_s_b:in_w.valid & ~in_w.last},
            ).sync(~init_in_progress)
            axi_s_b.id(st0_o.write_id)
        axi_s_b.resp(RESP_OKAY)

        da_w.data(in_w, exclude=[in_w.ready, in_w.valid])

        lru_array_set = self.lru_array.set

        init_cntr = self._reg("init_cntr", lru_array_set.addr._dtype, def_val=0)

        If(init_in_progress,
            tag_update.vld(1),
            tag_update.delete(1),
            tag_update.way_en(mask(tag_update.way_en._dtype.bit_length())),
            tag_update.addr(self.tag_array.deparse_addr(0, init_cntr, 0)),
            lru_array_set.addr(init_cntr),
            lru_array_set.data(0),
            lru_array_set.vld(1),
            If(init_cntr._eq(mask(init_cntr._dtype.bit_length())),
                init_cntr(0),
                init_in_progress(0),
            ).Else(
                init_cntr(init_cntr + 1),
            )
        ).Else(
            tag_update.vld(st0.dataOut.vld & da_w.addr.rd),
            tag_update.delete(0),
            tag_update.way_en(binToOneHot(_victim_way)),
            tag_update.addr(st0_o.replacement_addr),
            lru_array_set.addr(None),
            lru_array_set.data(None),
            lru_array_set.vld(0),
        )

    def flush_handler(self,
                   flush_data: TransRamHsW,  # in
                   axi_m_aw: Axi4_addr,  # out
                   axi_m_w: Axi4_w,  # out
                   axi_m_b: Axi4_b,  # in
                   ):
        id_tag = flush_data.addr.priv

        # potentially cut msb bits which do specify the way from address
        axi_m_aw.addr(self.deparse_addr(id_tag.victim_tag, flush_data.addr.addr[self.INDEX_W:], 0))
        axi_m_aw.id(id_tag.id)
        self.axiAddrDefaults(axi_m_aw)
        StreamNode(
            [flush_data.addr, ],
            [axi_m_aw, ]
        ).sync()

        axi_m_w.data(flush_data.data.data)
        axi_m_w.strb(mask(axi_m_w.data._dtype.bit_length() // 8))
        axi_m_w.last(flush_data.data.last)

        StreamNode(
            [flush_data.data],
            [axi_m_w],
        ).sync()

        axi_m_b.ready(1)

    @override
    def hwImpl(self):
        """
        Read operation:

        * Use index to lookup in tag memory
        * if tag matches return cacheline else dispatch read request
          (the transaction is dispatched with original id, upon data receive the transaction
          is passed to master without any synchronization with the cache )

        Write operation:

        * Use index to lookup in tag memory
        * If tag matches and the cacheline is not being replaced update the data in data array.
        * If tag is not found in corresponding set select a victim and read it from data array, flush it
          and write back cacheline to array and update tag
        """
        # transaction type usind in data array memory access pipeline
        init_in_progress = self._reg("init_in_progress", def_val=int(not self.IS_PREINITIALIZED))
        self.connect_tag_lookup(init_in_progress)
        ar_tagRes, aw_tagRes = self.tag_array.lookupRes

        self.read_handler(
            ar_tagRes,
            self.s.r,
            self.lru_array.incr[0],
            self.data_array.r,
            self.m.ar,
            self.m.r,
        )

        self.write_handler(
            aw_tagRes,
            self.s.b,
            self.lru_array.incr[1],
            self.lru_array.victim_req,
            self.lru_array.victim_data,
            self.data_array.w,
            self.tag_array.update[0],
            init_in_progress,
        )
        self.flush_handler(
            self.data_array.flush_data,
            self.m.aw,
            self.m.w,
            self.m.b,
        )

        propagateClkRstn(self)


def _example_AxiCacheWriteAllocWawOnlyWritePropagating():
    m = AxiCacheWriteAllocWawOnlyWritePropagating()
    m.DATA_WIDTH = 16
    m.CACHE_LINE_SIZE = 2
    m.WAY_CNT = 2
    m.CACHE_LINE_CNT = 16
    m.MAX_BLOCK_DATA_WIDTH = 8
    return m


if __name__ == "__main__":
    from hwt.synth import to_rtl_str
    from hwtLib.xilinx.constants import XILINX_VIVADO_MAX_DATA_WIDTH
    m = AxiCacheWriteAllocWawOnlyWritePropagating()
    m.DATA_WIDTH = 512
    m.CACHE_LINE_SIZE = m.DATA_WIDTH // 8
    m.WAY_CNT = 4
    m.CACHE_LINE_CNT = m.WAY_CNT * 4096
    m.MAX_BLOCK_DATA_WIDTH = XILINX_VIVADO_MAX_DATA_WIDTH
    # m.CACHE_LINE_SIZE = 64
    # m.DATA_WIDTH = 512
    # m.WAY_CNT = 2
    # m.CACHE_LINE_CNT = m.WAY_CNT * 4096
    # m = _example_AxiCacheWriteAllocWawOnlyWritePropagating()
    print(to_rtl_str(m))

1	#!/usr/bin/env python3
2	# -- coding: utf-8 --
3
4	from typing import List	1✔
5
6	from hwt.code import Or, SwitchLogic, If	1✔
7	from hwt.code_utils import rename_signal	1✔
8	from hwt.hdl.types.bits import HBits	1✔
9	from hwt.hdl.types.defs import BIT	1✔
10	from hwt.hdl.types.struct import HStruct	1✔
11	from hwt.hwIOs.hwIOStruct import HwIOStruct	1✔
12	from hwt.hwIOs.hwIOStruct import HwIOStructRdVld	1✔
13	from hwt.hwIOs.std import HwIODataRdVld	1✔
14	from hwt.hwIOs.utils import addClkRstn, propagateClkRstn	1✔
15	from hwt.hwParam import HwParam	1✔
16	from hwt.math import log2ceil, isPow2	1✔
17	from hwt.pyUtils.typingFuture import override	1✔
18	from hwt.synthesizer.rtlLevel.rtlSignal import RtlSignal	1✔
19	from hwtLib.amba.axi4 import Axi4, Axi4_r, Axi4_addr, Axi4_w, Axi4_b	1✔
20	from hwtLib.amba.axi_comp.cache.addrTypeConfig import CacheAddrTypeConfig	1✔
21	from hwtLib.amba.axi_comp.cache.lru_array import AxiCacheLruArray, HwIOIndexWayRdVld	1✔
22	from hwtLib.amba.axi_comp.cache.tag_array import AxiCacheTagArray, \	1✔
23	HwIOAxiCacheTagArrayLookupRes, HwIOAxiCacheTagArrayUpdate
24	from hwtLib.amba.axis_comp.builder import Axi4SBuilder	1✔
25	from hwtLib.amba.constants import RESP_OKAY, BURST_INCR, CACHE_DEFAULT, \	1✔
26	LOCK_DEFAULT, BYTES_IN_TRANS, PROT_DEFAULT, QOS_DEFAULT
27	from hwtLib.commonHwIO.addr import HwIOAddrRdVld	1✔
28	from hwtLib.handshaked.builder import HsBuilder	1✔
29	from hwtLib.handshaked.reg import HandshakedReg	1✔
30	from hwtLib.handshaked.streamNode import StreamNode	1✔
31	from hwtLib.logic.binToOneHot import binToOneHot	1✔
32	from hwtLib.mem.ramTransactional import RamTransactional	1✔
33	from hwtLib.mem.ramTransactional_io import TransRamHsR, TransRamHsW	1✔
34	from pyMathBitPrecise.bit_utils import mask	1✔
35
36
37	# https://chipress.co/category/job-roles-titles/page/16/
38	# https://chipress.co/2019/04/13/can-you-show-the-state-transition-for-snoop-based-scheme-using-msi-protocol/
39	# https://github.com/airin711/Verilog-caches
40	# https://github.com/rajshadow/4-way-set-associative-cache-verilog
41	# https://github.com/xdesigns/4way-cache
42	# https://github.com/prasadp4009/2-way-Set-Associative-Cache-Controller
43	class AxiCacheWriteAllocWawOnlyWritePropagating(CacheAddrTypeConfig):	1✔
44	"""
45	Non-blocking pipelined Set Associative cache for AXI interfaces which is designed
46	to work with an LSU which solves only WAW (write-after-write) conflicts.
47
48
49	:note: Write propagation in this context means that any read received will contain lastly written
50	data in some time few clock before (derived from read latency of the LSU)
51	the actual request (due to latency of the read resolution).
52	This means that if master check last N transaction for collision the data is asserted to be
53	in last version or to be marked with an invalidation flag. The N is usually 3 and
54	is derived from the latency of LSU which should be connected behind this cache.
55
56	:attention: This cache solves only WAW conflicts, this means that WAR and RAW conflicts
57	are left unsolved and must be handled on master side. This is suitable for a cumulative
58	operations in general as together with write propagating it allows master component
59	to significantly reduce buffers and collision detection logic.
60
61	.. figure:: ./_static/AxiCacheWriteAllocWawOnlyWritePropagating.png
62
63	:see: :class:`hwtLib.amba.axi_comp.cache.CacheAddrTypeConfig`
64	:ivar DATA_WIDTH: data width of interfaces
65	:ivar WAY_CNT: number of places where one cache line can be stored
66
67	:note: 1-way associative = directly mapped
68	:note: This cache does not check access collision with a requests to main (slave) memory.
69	It only provides an information for LSU to do so. The LSU is supposed to be connected
70	between main memory and this cache (= on master port where slave should be connected).
71
72	* The tag_array contains tags and cache line status flags for cache lines.
73	* The lsu_array contains the data for data for pseudo LRU (Last Recently Used) cache replacement policy.
74	It is stored in a separate array due to high requirements for concurrent access which results
75	in increased memory consumption.
76	* The data_array is a RAM where data for cache lines is stored.
77
78	The memories are separated because they have a different memory port requirements
79	and we want to keep the number of memory ports and the size of the memory minimal
80	as resource requirements grow exponentially with increasing number of memory ports.
81
82	.. hwt-autodoc:: _example_AxiCacheWriteAllocWawOnlyWritePropagating
83	"""
84
85	@override	1✔
86	def hwConfig(self):	1✔
87	Axi4.hwConfig(self)	1✔
88	self.WAY_CNT = HwParam(4)	1✔
89	self.MAX_BLOCK_DATA_WIDTH = HwParam(None)	1✔
90	self.IS_PREINITIALIZED = HwParam(False)	1✔
91	CacheAddrTypeConfig.hwConfig(self)	1✔
92
93	@override	1✔
94	def hwDeclr(self):	1✔
95	assert self.CACHE_LINE_CNT > 0, self.CACHE_LINE_CNT	1✔
96	assert self.WAY_CNT > 0 and isPow2(self.WAY_CNT), self.WAY_CNT	1✔
97	assert self.CACHE_LINE_CNT % self.WAY_CNT == 0, (self.CACHE_LINE_CNT, self.WAY_CNT)	1✔
98	assert isPow2(self.CACHE_LINE_SIZE // (self.DATA_WIDTH // 8))	1✔
99	assert self.DATA_WIDTH % 8 == 0, self.DATA_WIDTH	1✔
100	self._compupte_tag_index_offset_widths()	1✔
101
102	addClkRstn(self)	1✔
103	with self._hwParamsShared():	1✔
104	self.s = Axi4()	1✔
105	self.m = Axi4()._m()	1✔
106
107	rc = self.read_cancel = HwIOAddrRdVld()._m()	1✔
108	rc.ID_WIDTH = 0	1✔
109
110	self.tag_array = AxiCacheTagArray()	1✔
111	self.lru_array = AxiCacheLruArray()	1✔
112	for a in [self.tag_array, self.lru_array]:	1✔
113	a.PORT_CNT = 2 # r+w	1✔
114
115	da = RamTransactional()	1✔
116	da.MAX_BLOCK_DATA_WIDTH = self.MAX_BLOCK_DATA_WIDTH	1✔
117	da.WORD_WIDTH = self.CACHE_LINE_SIZE * 8	1✔
118	da.DATA_WIDTH = self.DATA_WIDTH	1✔
119	da.ADDR_WIDTH = log2ceil(self.CACHE_LINE_CNT)	1✔
120	da.R_ID_WIDTH = self.ID_WIDTH	1✔
121	da.W_PRIV_T = HStruct(	1✔
122	# used to construct an address for flush of original item in cache which is beeing replaced
123	(HBits(self.TAG_W), "victim_tag"), # index part of address is an address on flush_data.addr channel
124	(HBits(self.ID_WIDTH), "id"),
125	)
126	self.data_array = da	1✔
127
128	# self.flush = HandshakeSync()
129	# self.init = HandshakeSync()
130
131	def axiAddrDefaults(self, a: Axi4_addr):	1✔
132	a.burst(BURST_INCR)	1✔
133	a.len(self.CACHE_LINE_SIZE // (self.DATA_WIDTH // 8) - 1)	1✔
134	a.cache(CACHE_DEFAULT)	1✔
135	a.lock(LOCK_DEFAULT)	1✔
136	a.size(BYTES_IN_TRANS(self.DATA_WIDTH // 8))	1✔
137	a.prot(PROT_DEFAULT)	1✔
138	a.qos(QOS_DEFAULT)	1✔
139
140	def connect_tag_lookup(self, init_in_progress: RtlSignal):	1✔
141	in_ar, in_aw = self.s.ar, self.s.aw	1✔
142	# connect address lookups to a tag array
143	tags = self.tag_array	1✔
144	for a, tag_lookup in zip((in_ar, in_aw), tags.lookup):	1✔
145	tag_lookup.addr(a.addr)	1✔
146	tag_lookup.id(a.id)	1✔
147	if a is in_aw:	1✔
148	rc = self.read_cancel	1✔
149	rc.addr(a.addr)	1✔
150	StreamNode([a], [tag_lookup, rc]).sync(~init_in_progress)	1✔
151	else:
152	StreamNode([a], [tag_lookup]).sync(~init_in_progress)	1✔
153
154	def incr_lru_on_hit(self,	1✔
155	lru_incr: HwIOIndexWayRdVld,
156	tag_res: HwIOAxiCacheTagArrayLookupRes):
157	index = self.parse_addr(tag_res.addr)[1]	1✔
158	lru_incr.vld(tag_res.vld & tag_res.found)	1✔
159	lru_incr.way(tag_res.way)	1✔
160	lru_incr.index(index)	1✔
161
162	def read_handler(self,	1✔
163	ar_tagRes: HwIOAxiCacheTagArrayLookupRes, # in
164	axi_s_r: Axi4_r, # out
165	ar_lru_incr: HwIOIndexWayRdVld, # out
166	da_r: TransRamHsR, # in
167	axi_m_ar: Axi4_addr, # out
168	axi_m_r: Axi4_r # in
169	):
170	"""
171	:param ar_tagRes: Read request including information from tag_array for given tag.
172	:param axi_s_r: Read data requested by ar_tagRes.
173	:param ar_lru_incr: Incrementing LRU for given address when tag is found.
174	:param da_r: Read interface of data_array used when tag is found.
175	:param axi_m_ar: Read address request interface to memory when tag is not found.
176	:param axi_m_r: Read data requested by axi_m_ar from memory when tag is not found.
177
178	.. figure:: ./_static/AxiCacheWriteAllocWawOnlyWritePropagating_read_handler.png
179	"""
180	self.incr_lru_on_hit(ar_lru_incr, ar_tagRes)	1✔
181
182	# addd a register with backup register for poential overflow
183	# we need this as we need to check if we can store data in advance.
184	# this is because we need a higher priority for flushing
185	# in order to avoid deadlock.
186	data_arr_read_req = HsBuilder(self, da_r.addr, master_to_slave=False)\	1✔
187	.buff(1, latency=(1, 2))\
188	.end
189
190	# send read request to data_array
191	ar_index = self.parse_addr(ar_tagRes.addr)[1]	1✔
192	data_arr_read_req.priv(ar_tagRes.id)	1✔
193	data_arr_read_req.addr(self.addr_in_data_array(ar_tagRes.way, ar_index)),	1✔
194
195	# delegate read request to m.ar if not hit
196	StreamNode(	1✔
197	[ar_tagRes],
198	[axi_m_ar, data_arr_read_req],
199	extraConds={
200	axi_m_ar: ar_tagRes.vld & ~ar_tagRes.found,
201	data_arr_read_req: ar_tagRes.vld & ar_tagRes.found,
202	},
203	skipWhen={
204	axi_m_ar: ar_tagRes.vld & ar_tagRes.found,
205	data_arr_read_req: ar_tagRes.vld & ~ar_tagRes.found,
206	},
207	).sync()
208
209	axi_m_ar.addr(ar_tagRes.addr)	1✔
210	axi_m_ar.id(ar_tagRes.id)	1✔
211	self.axiAddrDefaults(axi_m_ar)	1✔
212
213	data_arr_read = axi_s_r.__class__()	1✔
214	data_arr_read._updateHwParamsFrom(axi_s_r)	1✔
215	self.data_arr_read = data_arr_read	1✔
216
217	data_arr_read(da_r.data, exclude=[data_arr_read.resp])	1✔
218	data_arr_read.resp(RESP_OKAY)	1✔
219
220	data_arr_read = Axi4SBuilder(self, data_arr_read)\	1✔
221	.buff(1, latency=(1, 2))\
222	.end
223
224	s_r = Axi4SBuilder.join_prioritized(self, [	1✔
225	data_arr_read,
226	axi_m_r,
227	]).end
228	axi_s_r(s_r)	1✔
229
230	def resolve_victim(self, st0_o_tag_found: RtlSignal, # in	1✔
231	st0_o_found_way: RtlSignal, # in
232	st0_o_tags: List[HwIOStruct], # in
233	victim_way: HwIODataRdVld # in
234	):
235	_victim_way = self._sig("victim_way_tmp", HBits(log2ceil(self.WAY_CNT)))	1✔
236	_victim_tag = self._sig("victim_tag_tmp", HBits(self.TAG_W))	1✔
237	SwitchLogic(	1✔
238	[
239	# select first empty tag
240	(~tag.valid, [
241	_victim_way(i),
242	_victim_tag(tag.tag),
243	]) for i, tag in enumerate(st0_o_tags)
244	],
245	default=[
246	# select an victim specified by victim_way
247	_victim_way(victim_way.data),
248	SwitchLogic([
249	(victim_way.data._eq(i), _victim_tag(tag.tag))
250	for i, tag in enumerate(st0_o_tags)
251	],
252	default=_victim_tag(None)
253	)
254	]
255	)
256	_victim_way = st0_o_tag_found._ternary(st0_o_found_way, _victim_way)	1✔
257	return _victim_way, _victim_tag	1✔
258
259	def write_handler(self,	1✔
260	aw_tagRes: HwIOAxiCacheTagArrayLookupRes, # in
261	axi_s_b: Axi4_b, # out
262	aw_lru_incr: HwIOIndexWayRdVld, # out
263	victim_way_req: HwIOAddrRdVld, victim_way_resp: HwIODataRdVld, # out, in
264	da_w: TransRamHsW, # in
265	tag_update: HwIOAxiCacheTagArrayUpdate, # out
266	init_in_progress: RtlSignal, # in
267	):
268	"""
269	:param aw_tagRes: Write request including in information from tag_array for given tag.
270	:param axi_s_b: Response requested by aw_tagRes
271	:param aw_lru_incr: Incrementing LRU for given address when tag is found.
272	:param victim_way_req: Request victim from LRU array for a specified index, when cache is full.
273	:param victim_way_resp: Victim address requested by victim_way_req
274	:param da_w: Write interface of data_array to write and initiate flush when cache is full.
275	:param tag_update: Tag update interface for newly written data.
276
277	.. figure:: ./_static/AxiCacheWriteAllocWawOnlyWritePropagating_write_handler.png
278	"""
279	# note that the lru update happens even if the data is stalled
280	# but that is not a problem because it wont change the order of the usage
281	# of the cahceline
282	self.incr_lru_on_hit(aw_lru_incr, aw_tagRes)	1✔
283
284	st0 = HandshakedReg(HwIOStructRdVld)	1✔
285	st0.T = HStruct(	1✔
286	# the original id and address of a write transaction
287	(self.s.aw.id._dtype, "write_id"),
288	(self.s.aw.addr._dtype, "replacement_addr"),
289	# array of tags for cachelines with this index
290	(aw_tagRes.TAG_T[aw_tagRes.WAY_CNT], "tags"),
291	(BIT, "tag_found"),
292	(BIT, "had_empty"), # had some empty tag
293	(aw_tagRes.way._dtype, "found_way"), # way of where tag was found
294	)
295	self.victim_load_status0 = st0	1✔
296
297	st0_i = st0.dataIn.data	1✔
298	# resolve if we need to select a victim and optianally ask for it
299	has_empty = rename_signal(self, Or(*(~t.valid for t in aw_tagRes.tags)), "has_empty")	1✔
300	st0_i.write_id(aw_tagRes.id),	1✔
301	st0_i.replacement_addr(aw_tagRes.addr),	1✔
302	st0_i.tags(aw_tagRes.tags),	1✔
303	st0_i.tag_found(aw_tagRes.found),	1✔
304	st0_i.found_way(aw_tagRes.way),	1✔
305	st0_i.had_empty(has_empty),	1✔
306
307	victim_way_req.addr(self.parse_addr(aw_tagRes.addr)[1])	1✔
308	StreamNode(	1✔
309	[aw_tagRes],
310	[victim_way_req, st0.dataIn],
311	skipWhen={
312	victim_way_req: aw_tagRes.vld & (
313	aw_tagRes.found \|
314	has_empty
315	)
316	},
317	extraConds={
318	victim_way_req:~aw_tagRes.found & ~has_empty
319	}
320	).sync()
321
322	########################## st1 - pre (read request resolution, victim address resolution) ##############
323
324	st0_o = st0.dataOut.data	1✔
325
326	_victim_way, _victim_tag = self.resolve_victim(st0_o.tag_found, st0_o.found_way, st0_o.tags, victim_way_resp)	1✔
327
328	da_w.addr.flush(rename_signal(self, st0.dataOut.vld & (~st0_o.had_empty & ~st0_o.tag_found), "need_to_flush"))	1✔
329	da_w.addr.priv.id(st0_o.write_id)	1✔
330	da_w.addr.addr(self.addr_in_data_array(st0_o.tag_found._ternary(st0_o.found_way, _victim_way),	1✔
331	self.parse_addr(st0_o.replacement_addr)[1])),
332	da_w.addr.priv.victim_tag(_victim_tag)	1✔
333
334	MULTI_WORD = self.data_array.ITEM_WORDS > 1	1✔
335	if MULTI_WORD:	1✔
336	st1_id = HandshakedReg(HwIODataRdVld)	1✔
337	st1_id.LATENCY = (1, 2)	1✔
338	st1_id.DATA_WIDTH = self.ID_WIDTH	1✔
339	self.victim_load_status1 = st1_id	1✔
340	st1_id.dataIn.data(st0_o.write_id)	1✔
341	# placed between st0, st1
342	StreamNode(	1✔
343	[victim_way_resp, st0.dataOut],
344	[da_w.addr, st1_id.dataIn] if MULTI_WORD else [da_w.addr],
345	extraConds={
346	victim_way_resp:~st0_o.tag_found & ~st0_o.had_empty,
347	},
348	skipWhen={
349	victim_way_resp: st0_o.tag_found \| st0_o.had_empty,
350	}
351	).sync()
352
353	in_w = Axi4SBuilder(self, self.s.w)\	1✔
354	.buff(self.tag_array.LOOKUP_LATENCY + 4)\
355	.end
356	if MULTI_WORD:	1✔
357	StreamNode(	1✔
358	[in_w, st1_id.dataOut],
359	[da_w.data, axi_s_b],
360	extraConds={axi_s_b: in_w.valid & in_w.last,
361	st1_id.dataOut: in_w.valid & in_w.last},
362	skipWhen={axi_s_b: in_w.valid & ~in_w.last,
363	st1_id.dataOut: in_w.valid & ~in_w.last},
364	).sync(~init_in_progress)
365	axi_s_b.id(st1_id.dataOut.data) # todo	1✔
366	else:
367	StreamNode(	1✔
368	[in_w],
369	[da_w.data, axi_s_b],
370	extraConds={axi_s_b: in_w.valid & in_w.last},
371	skipWhen={axi_s_b:in_w.valid & ~in_w.last},
372	).sync(~init_in_progress)
373	axi_s_b.id(st0_o.write_id)	1✔
374	axi_s_b.resp(RESP_OKAY)	1✔
375
376	da_w.data(in_w, exclude=[in_w.ready, in_w.valid])	1✔
377
378	lru_array_set = self.lru_array.set	1✔
379
380	init_cntr = self._reg("init_cntr", lru_array_set.addr._dtype, def_val=0)	1✔
381
382	If(init_in_progress,	1✔
383	tag_update.vld(1),
384	tag_update.delete(1),
385	tag_update.way_en(mask(tag_update.way_en._dtype.bit_length())),
386	tag_update.addr(self.tag_array.deparse_addr(0, init_cntr, 0)),
387	lru_array_set.addr(init_cntr),
388	lru_array_set.data(0),
389	lru_array_set.vld(1),
390	If(init_cntr._eq(mask(init_cntr._dtype.bit_length())),
391	init_cntr(0),
392	init_in_progress(0),
393	).Else(
394	init_cntr(init_cntr + 1),
395	)
396	).Else(
397	tag_update.vld(st0.dataOut.vld & da_w.addr.rd),
398	tag_update.delete(0),
399	tag_update.way_en(binToOneHot(_victim_way)),
400	tag_update.addr(st0_o.replacement_addr),
401	lru_array_set.addr(None),
402	lru_array_set.data(None),
403	lru_array_set.vld(0),
404	)
405
406	def flush_handler(self,	1✔
407	flush_data: TransRamHsW, # in
408	axi_m_aw: Axi4_addr, # out
409	axi_m_w: Axi4_w, # out
410	axi_m_b: Axi4_b, # in
411	):
412	id_tag = flush_data.addr.priv	1✔
413
414	# potentially cut msb bits which do specify the way from address
415	axi_m_aw.addr(self.deparse_addr(id_tag.victim_tag, flush_data.addr.addr[self.INDEX_W:], 0))	1✔
416	axi_m_aw.id(id_tag.id)	1✔
417	self.axiAddrDefaults(axi_m_aw)	1✔
418	StreamNode(	1✔
419	[flush_data.addr, ],
420	[axi_m_aw, ]
421	).sync()
422
423	axi_m_w.data(flush_data.data.data)	1✔
424	axi_m_w.strb(mask(axi_m_w.data._dtype.bit_length() // 8))	1✔
425	axi_m_w.last(flush_data.data.last)	1✔
426
427	StreamNode(	1✔
428	[flush_data.data],
429	[axi_m_w],
430	).sync()
431
432	axi_m_b.ready(1)	1✔
433
434	@override	1✔
435	def hwImpl(self):	1✔
436	"""
437	Read operation:
438
439	* Use index to lookup in tag memory
440	* if tag matches return cacheline else dispatch read request
441	(the transaction is dispatched with original id, upon data receive the transaction
442	is passed to master without any synchronization with the cache )
443
444	Write operation:
445
446	* Use index to lookup in tag memory
447	* If tag matches and the cacheline is not being replaced update the data in data array.
448	* If tag is not found in corresponding set select a victim and read it from data array, flush it
449	and write back cacheline to array and update tag
450	"""
451	# transaction type usind in data array memory access pipeline
452	init_in_progress = self._reg("init_in_progress", def_val=int(not self.IS_PREINITIALIZED))	1✔
453	self.connect_tag_lookup(init_in_progress)	1✔
454	ar_tagRes, aw_tagRes = self.tag_array.lookupRes	1✔
455
456	self.read_handler(	1✔
457	ar_tagRes,
458	self.s.r,
459	self.lru_array.incr[0],
460	self.data_array.r,
461	self.m.ar,
462	self.m.r,
463	)
464
465	self.write_handler(	1✔
466	aw_tagRes,
467	self.s.b,
468	self.lru_array.incr[1],
469	self.lru_array.victim_req,
470	self.lru_array.victim_data,
471	self.data_array.w,
472	self.tag_array.update[0],
473	init_in_progress,
474	)
475	self.flush_handler(	1✔
476	self.data_array.flush_data,
477	self.m.aw,
478	self.m.w,
479	self.m.b,
480	)
481
482	propagateClkRstn(self)	1✔
483
484
485	def _example_AxiCacheWriteAllocWawOnlyWritePropagating():	1✔
486	m = AxiCacheWriteAllocWawOnlyWritePropagating()	×
487	m.DATA_WIDTH = 16	×
488	m.CACHE_LINE_SIZE = 2	×
489	m.WAY_CNT = 2	×
490	m.CACHE_LINE_CNT = 16	×
491	m.MAX_BLOCK_DATA_WIDTH = 8	×
492	return m	×
493
494
495	if __name__ == "__main__":
496	from hwt.synth import to_rtl_str
497	from hwtLib.xilinx.constants import XILINX_VIVADO_MAX_DATA_WIDTH
498	m = AxiCacheWriteAllocWawOnlyWritePropagating()
499	m.DATA_WIDTH = 512
500	m.CACHE_LINE_SIZE = m.DATA_WIDTH // 8
501	m.WAY_CNT = 4
502	m.CACHE_LINE_CNT = m.WAY_CNT * 4096
503	m.MAX_BLOCK_DATA_WIDTH = XILINX_VIVADO_MAX_DATA_WIDTH
504	# m.CACHE_LINE_SIZE = 64
505	# m.DATA_WIDTH = 512
506	# m.WAY_CNT = 2
507	# m.CACHE_LINE_CNT = m.WAY_CNT * 4096
508	# m = _example_AxiCacheWriteAllocWawOnlyWritePropagating()
509	print(to_rtl_str(m))

Nic30 / hwtLib / b469f1f6-6a00-4958-bfb0-f9fbf427a589

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous