One embodiment of the present invention provides a system that decouples a tag access from a corresponding data access within a cache memory. The system operates by receiving a memory request at the cache memory, wherein the memory request includes an address identifying a memory location. Next, the system performs the tag access by looking up at least one tag from a tag array within the cache memory and comparing the at least one tag with a tag portion of the address to determine if a cache line containing the address is located in the cache memory. If the cache line containing the address is located in the cache memory but a data array containing the cache line is busy, the system performs the corresponding data access at a later time when the data array becomes free. Furthermore, if the memory request is for a load operation, the corresponding data access takes place without waiting for preceding load operations to complete.