How can caches be defeated?

I have this question on my assignment this week, and I don't understand how the caches can be defeated, or how I can show it with an assembly program.. Can someone point me in the right direction?

Show, with assembly program examples, how the two different caches (Associative and Direct Mapping) can be defeated. Explain why this occurs and how it can be fixed. Are the same programs used to defeat the caches the same?

Note开发者_如何学JAVA: This is homework. Don't just answer the question for me, it won't help me to understand the material.

---

A cache is there to increase performance. So defeating a cache means finding a pattern of memory accesses that decreases performance (in the presence of the cache) rather than increases it.

Bear in mind that the cache is limited in size (smaller than main memory, for instance) so typically defeating the cache involves filling it up so that it throws away the data you're just about to access, just before you access it.

---

If you're looking for a hint, think about splitting a data word across 2 cache lines.

(In case you're also looking for the answer, a similar problem was encountered by the x264 developers -- more information available here and here. The links are highly informative, and I really suggest you read them even after you've found your answer.)

---

Another thing to keep in mind is whether the caches you deal with are virtually or physically indexed / tagged. In some variants, cache aliasing forces line replacements even if the cache as such isn't completely filled. In other variants, cache/page coloring collisions might cause evictions. Finally, in multiprocessor systems under certain workloads, cacheline migrations (between the caches of different CPUs) may limit the usefulness of CPU caches.