On Wednesday, March 2, 2022 at 2:37:47 PM UTC-6, Stephen Fuld wrote:
> On 3/2/2022 11:26 AM, BGB wrote:
> > On 3/2/2022 12:25 PM, Anton Ertl wrote:
> >> BGB <cr8...@gmail.com> writes:
> >>> On 3/2/2022 3:12 AM, Anton Ertl wrote:
> >>>> A 512KB cache with 64-byte lines has 8192 cache lines, just like a
> >>>> 256KB cache with 32-byte lines and a 128KB cache with 16-byte lines.
> >>>> Without spatial locality, I would expect similar miss rates for all of
> >>>> them for the same associativity; and given that programs have spatial
> >>>> locality, I would expect the larger among these configurations to have
> >>>> an advantage. Are you sure that your cache simulator has no bugs?
> >> ...
> >>> After fixing this bug:
> >>> 131072 2.004% 1.318% (1 way, 16 line)
> >>> 65536 2.851% 1.516% (1 way, 16 line)
> >>> 32768 3.540% 1.445% (1 way, 16 line)
> >>> 16384 6.604% 4.043% (1 way, 16 line)
> >>> 8192 9.112% 6.052% (1 way, 16 line)
> >>> 4096 11.310% 4.504% (1 way, 16 line)
> >>> 2048 14.326% 5.990% (1 way, 16 line)
> >>> 1024 17.632% 7.066% (1 way, 16 line)
> >>>
> >>> 131072 1.966% 0.821% (2 way, 16 line)
> >>> 65536 2.550% 0.513% (2 way, 16 line)
> >>> 32768 3.303% 0.791% (2 way, 16 line)
> >>> 16384 6.779% 3.842% (2 way, 16 line)
> >>> 8192 8.484% 1.766% (2 way, 16 line)
> >>> 4096 10.905% 2.773% (2 way, 16 line)
> >>> 2048 13.588% 3.319% (2 way, 16 line)
> >>> 1024 16.022% 3.229% (2 way, 16 line)
> >>>
> >>> 262144 15.748% 14.750% (1 way, 32 line)
> >>> 131072 15.929% 14.382% (1 way, 32 line)
> >>> 65536 16.274% 14.057% (1 way, 32 line)
> >>> 32768 16.843% 14.122% (1 way, 32 line)
> >>> 16384 19.819% 16.567% (1 way, 32 line)
> >>> 8192 22.360% 18.319% (1 way, 32 line)
> >>> 4096 24.583% 16.422% (1 way, 32 line)
> >>> 2048 27.325% 16.513% (1 way, 32 line)
> >>>
> >>> 262144 2.093% 0.872% (2 way, 32 line)
> >>> 131072 2.893% 0.836% (2 way, 32 line)
> >>> 65536 3.540% 0.949% (2 way, 32 line)
> >>> 32768 4.854% 1.808% (2 way, 32 line)
> >>> 16384 8.788% 4.997% (2 way, 32 line)
> >>> 8192 11.456% 3.638% (2 way, 32 line)
> >>> 4096 14.699% 4.352% (2 way, 32 line)
> >>> 2048 17.580% 4.251% (2 way, 32 line)
> >>>
> >>> 524288 10.825% 10.370% (1 way, 64 line)
> >>> 262144 11.019% 10.412% (1 way, 64 line)
> >>> 131072 11.188% 10.232% (1 way, 64 line)
> >>> 65536 11.652% 10.320% (1 way, 64 line)
> >>> 32768 12.388% 10.699% (1 way, 64 line)
> >>> 16384 15.806% 13.581% (1 way, 64 line)
> >>> 8192 18.753% 15.604% (1 way, 64 line)
> >>> 4096 21.158% 13.259% (1 way, 64 line)
> >>>
> >>> 524288 0.863% 0.439% (2 way, 64 line)
> >>> 262144 1.297% 0.535% (2 way, 64 line)
> >>> 131072 1.896% 0.700% (2 way, 64 line)
> >>> 65536 2.505% 0.979% (2 way, 64 line)
> >>> 32768 3.876% 1.923% (2 way, 64 line)
> >>> 16384 8.341% 5.535% (2 way, 64 line)
> >>> 8192 11.346% 3.956% (2 way, 64 line)
> >>> 4096 14.262% 3.722% (2 way, 64 line)
> >>>
> >>>
> >>> It would appear that 1-way still does poorly with larger cache lines,
> >>
> >> Probably still a bug, see above.
> >>
> >>> As for why now 1-way 32B appears to be doing worse than 1-way 64B, no
> >>> idea, this doesn't really make sense.
> >>
> >> For the same number of cache lines, that's expected, due to spatial
> >> locality.
> >>
> >
> > After posting this, I did find another bug:
> > The cache index pairs were always being calculated as-if the cache line
> > were 16B. After fixing this bug, all the lines got much closer together
> > (as shown on another graph posted to Twitter after the last graph).
> >
> > In this case, now the overall hit/miss ratio is more consistent between
> > cache-line sizes. The main difference is that larger cache-line sizes
> > still have a higher proportion of conflict misses.
> >
> >
> > Values following the more recent bugfix:
> > 131072 2.004% 1.318% (1 way, 16 line)
> > 65536 2.851% 1.516% (1 way, 16 line)
> > 32768 3.540% 1.445% (1 way, 16 line)
> > 16384 6.604% 4.043% (1 way, 16 line)
> > 8192 9.112% 6.052% (1 way, 16 line)
> > 4096 11.310% 4.504% (1 way, 16 line)
> > 2048 14.326% 5.990% (1 way, 16 line)
> > 1024 17.632% 7.066% (1 way, 16 line)
> >
> > 131072 1.966% 0.821% (2 way, 16 line)
> > 65536 2.550% 0.513% (2 way, 16 line)
> > 32768 3.303% 0.791% (2 way, 16 line)
> > 16384 6.779% 3.842% (2 way, 16 line)
> > 8192 8.484% 1.766% (2 way, 16 line)
> > 4096 10.905% 2.773% (2 way, 16 line)
> > 2048 13.588% 3.319% (2 way, 16 line)
> > 1024 16.022% 3.229% (2 way, 16 line)
> >
> > 262144 0.905% 0.630% (1 way, 32 line)
> > 131072 1.326% 0.912% (1 way, 32 line)
> > 65536 1.976% 1.160% (1 way, 32 line)
> > 32768 2.712% 1.504% (1 way, 32 line)
> > 16384 5.964% 4.456% (1 way, 32 line)
> > 8192 8.728% 6.671% (1 way, 32 line)
> > 4096 11.262% 5.347% (1 way, 32 line)
> > 2048 14.579% 6.659% (1 way, 32 line)
> >
> > 262144 0.671% 0.329% (2 way, 32 line)
> > 131072 1.148% 0.436% (2 way, 32 line)
> > 65536 1.514% 0.348% (2 way, 32 line)
> > 32768 2.259% 0.795% (2 way, 32 line)
> > 16384 6.041% 4.169% (2 way, 32 line)
> > 8192 8.102% 2.335% (2 way, 32 line)
> > 4096 10.690% 3.071% (2 way, 32 line)
> > 2048 13.354% 3.134% (2 way, 32 line)
> >
> > 524288 0.442% 0.311% (1 way, 64 line)
> > 262144 0.717% 0.561% (1 way, 64 line)
> > 131072 1.023% 0.759% (1 way, 64 line)
> > 65536 1.661% 1.154% (1 way, 64 line)
> > 32768 2.538% 1.818% (1 way, 64 line)
> > 16384 6.168% 5.201% (1 way, 64 line)
> > 8192 9.279% 7.640% (1 way, 64 line)
> > 4096 12.084% 6.163% (1 way, 64 line)
> >
> > 524288 0.219% 0.079% (2 way, 64 line)
> > 262144 0.428% 0.215% (2 way, 64 line)
> > 131072 0.697% 0.251% (2 way, 64 line)
> > 65536 0.984% 0.298% (2 way, 64 line)
> > 32768 1.924% 1.005% (2 way, 64 line)
> > 16384 6.169% 4.797% (2 way, 64 line)
> > 8192 8.642% 2.983% (2 way, 64 line)
> > 4096 10.878% 2.647% (2 way, 64 line)
> >
> >
> > Though, it seems 16B cache lines are no longer a clear winner in this
> > case...
> I am not sure how you determined this. To do an apples to apples
> comparison, as Anton explained, you have to compare the same amount of
> total cache. Thus, for example, comparing a 16 byte line at a
> particular cache size should be compared against a 32 byte line at twice
> the cache size. Otherwise, the you can't distinguish between the total
> cache size effect and the cache line size effect. To me, it seems like
> for equivalent cache sizes, 16B lines are a clear win. This reflects a
> higher proportion of temporal locality than spatial locality.
<
And then there is that bus occupancy thing.........
>
> BTW, with a little more work, you can distinguish spatial locality hits
> from temporal locality hits. You have to keep the actual address that
> caused the miss, then on subsequent hits, see if they are to the same or
> a different address.
<
We figured out (around 1992) that one could model all cache sizes
and association levels simultaneously.
>
> One more suggestion. If you are not outputting a trace, but keeping the
> statistics "on the fly" in the emulator, this is non-optimal. Yes,
> outputting the full trace (of all loads and stores) will slow the
> emulator down significantly, you only have to do it once. Then by
> creating another program that just emulates the cache behavior, you can
> run lots of tests on the same trace data (different line sizes, cache
> sizes, LRU policies, number of ways, etc.) without rerunning the full
> simulator. This second program should be quite fast, as it doesn't have
> to emulate the whole CPU.
> > There is still a hump in the conflict miss estimates, I still suspect
> > this is likely due to the smaller caches hitting the limit of the 4-way
> > estimator.
> >
> > Well, either that, or I am not estimating conflict miss rate correctly...
> See
>
>
> https://en.wikipedia.org/wiki/Cache_performance_measurement_and_metric#Conflict_misses
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)