A cache includes a cache array and a cache controller. The cache array has a plurality of entries. The cache controller is coupled to the cache array. The cache controller evicts entries from the cache array according to a cache replacement policy. The cache controller evicts a first cache line from the cache array by generating a writeback request for modified data from the first cache line, and subsequently generates a writeback request for modified data from a second cache line if the second cache line is about to satisfy the cache replacement policy and stores data from a common locality as the first cache line.