1. A method for operating a cache, comprising: in a prediction mechanism, performing operations for: performing a lookup in each table in a hierarchy of lookup tables in parallel to determine if a memory request is predicted to be a hit in the cache, each table in the hierarchy comprising predictions whether memory requests to corresponding regions of a main memory will hit in the cache, each of the regions in a given table including a corresponding number of addresses in the main memory, wherein the regions include a smaller number of addresses in the main memory for each table lower in the hierarchy.