[Libre-soc-dev] PLRU algorithms

[Luke Kenneth Casson Leighton]

paul, mikey, benjamin,

we've been converting dcache.vhdl for the past 2 weeks (i know it
sounds odd to do that, however we need things to be in nmigen before
being able to make significant augmentations).

in the process of that i encountered the plru.vhdl code which i
noticed uses arrays (pmux).  there's also a note in it to look at
converting it to a ROM.  i thought you might appreciate that almost 2
years ago we found a really decent implementation of a PLRU in
systemverilog:
https://github.com/openhwgroup/cva6/blob/master/src/tlb.sv

this used to be called "ariane" - it got renamed.

there's some notes on the algorithm, here:
https://git.libre-soc.org/?p=soc.git;a=blob;f=src/unused/TLB/ariane/p_lru.txt;hb=HEAD

and - ah yes! - that file indeed mentions a "ROM".  we converted it to
nmigen 2 years ago:
https://git.libre-soc.org/?p=soc.git;a=blob;f=src/unused/TLB/ariane/plru.py;h=70e212689cb783d24223c6e7f5ae7b640997ec9c;hb=HEAD

after running yosys on each of these i can confirm that it is a *lot*
smaller (a hell of a lot less gates).  i can't say it's a "ROM" - it's
more that the decision-tree is static, that bits are dropped into
multiple locations (a pascal's triangle of locations) and then ORed
and NOTed together elegantly.

the "shifts" that you see in both the python and the systemverilog
code are *not* HDL: they're variables (python variables in the case of
the nmigen code), that are used to statically compute which bits get
ORed and NOTed together.

anyway, the reason i mention this is for a number of reasons: firstly,
there's quite a lot of PLRUs used in microwatt (over 70?  64+8, 64 for
TLB, 8 for cache ways?) so there would be quite a bit of a saving,
there.  secondly: i'm not actually that good at algorithms, whereas i
know that you are.  consequently if you tackle this, i can then look
at what you've done and sort out libre-soc afterwards :)

l.

---
crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68