Stratix II - Asynchronous RAM Memory

The largest SII has 9 M-RAM blocks(512K bits, so you would make them 256Kx2 for your Main memory). So that's not even half of your main memory. If you start stitching M4Ks together, you need 64 of them stacked deep to do a single 256Kx1, so using every one you'll get another 11-12 bits, but you just don't have enough for the main memory.

If the main memory is off-chip, then the cache should fit into M512s pretty easily, and if you aren't using them all, then doubling them is pretty straightforward(I don't know what size device you're targeting)