Hacker News Reader

Comment by ori_b | Hacker News Reader

I'm not saying that the cache should be fully associative, I'm saying that instead of each bucket being a power of two, make it a prime number -- eg, 67 byte cache lines instead of 64, for example, seem to me like they would prevent quite a bit of aliasing with common data sizes.

There would be more circuitry to divide the addresses. I haven't done too much with hardware (only some light FPGA experience), so I don't know how much extra, but it doesn't feel like it would be prohibitive. I could be wrong.

(If you're aware of someone doing analysis on that, I'd be curious to see it -- I haven't seen any.)

View on HN

Computer architecture researchers have been working at this for a long time. Here's a recent paper on a technique to do the division and modulus operations for arbitrary numbers of cache banks and set sizes.

http://www.cs.utexas.edu/~skeckler/pubs/MICRO_2014_Modulus_I...

They evaluate the technique on a GPU because bank and set conflicts can lead to bad performance more easily on a GPU than a CPU.

What I meant is that making the cache fully-associative would result in faster implementation than N-way associative with non-power-of-2 cache line size or bucket count because of the additional circuitry involved in selecting right bucket (integer modulus and so on).

Interesting trick is using different values for cache index and tag (logical address for index and physical address as tag is common, but that's mostly about doing cache lookup concurrently with TLB lookup). In theory one could use result of some hash function as index, which would certainly change the aliasing behavior (although it is not exactly certain that such change would be for the better) and again, there is the additional cost of calculating said hash function (in combinatorial logic and with reasonably small delay).

I don't know much about this either, but I think if cache line size is not a multiple of the RAM transfer size, bandwidth will be wasted.

It would be prohibitively slow. Division and modulus are the slowest integer operations.

Correction: Division by arbitrary integer valued variables are the slowest integer operations.

You can accomplish division by a constant / modulus by a constant without a full division, however. For example, (x == x % 256 - x * 256), mod 257. That sort of thing.

Reply on news.ycombinator.com