Methods and apparatus for caching data in a non-blocking manner using a plurality of fill buffers

A method for caching data in a non-blocking manner comprising the steps of:

• a) storing a first plurality of cache lines of cache data and a first plurality of corresponding cache line addresses in a first plurality of cache data banks and a first cache tag array respectively, and staging a plurality of non-sequential missed cache lines of cache fill data within a plurality of fill buffers that store one of said first plurality of cache lines of cache data prior to storing in a cache memory;
• b) replacing one of said first plurality of cache lines whenever the filling of one of said staged cache lines is completed;
• c) tag matching a load address of a load operation against said first plurality of cache line addresses with first tag matching circuitry to determine if said load operation hits one of said first plurality of cache lines, and tag matching said load address against cache line addresses of said missed cache lines being filled with second tag matching circuitry to determine if said load operation hits one of said plurality of fill buffers, said tag matchings being performed concurrently with said staging in step (a) and said replacement in step (b);
• d) outputting load data for said load operation from one of said first plurality of cache lines and said plurality of fill buffers based on the results of said tag matchings in step (c), said outputting being performed, concurrently with said staging in step (a) and said replacement in step (b);
• and
• e) allocating one of said fill buffers to stage the missed cache line of cache data prior to storing said cache line of cache data in said plurality of cache data banks if said load operation misses all of said first plurality of cache lines and all of said plurality of fill buffers.

A processor comprising:

• an instruction fetch and dispatch unit that fetches and dispatches instructions;
• an execution unit coupled to said instruction fetch and dispatch unit that executes said instructions;
• and
• a non-blocking cache memory coupled to said execution unit that caches data in a non-blocking manner for said execution unit, said non-blocking cache memory having a plurality of data banks that store a plurality of cache lines of cache data, cache tag array and matching circuitry that stores cache line addresses corresponding to said cache lines of cache data and that tag matches memory accessing addresses of memory access operations to said cache line addresses, and a plurality of fill buffers that store non-sequential cache lines of cache data and that are configured concurrently to stage a first missed cache line, to replace a cache line in said data banks upon completion of a second missed cache line of cache data being loaded into one of said plurality of fill buffers, and to output a third cache line located in said fill buffers.

A computer system comprising:

• a memory unit that stores instruction and data;
• an instruction fetch and dispatch unit coupled to said memory unit that fetches and dispatches instructions;
• a non-blocking cache memory coupled to said memory unit that caches data in a non-blocking manner for said execution unit, said non-blocking cache memory having a plurality of data banks that store a plurality of cache lines of cache data, cache tag array and matching circuitry that stores cache line addresses corresponding to said cache lines of cache data and that tag matches memory accessing addresses of memory access operations to said cache line addresses, and a plurality of fill buffers that store non-sequential cache lines of cache data and that are configured concurrently to stage a first missed cache line, to replace a cache line in said data banks upon completion of a second missed cache line of cache data being loaded into one of said plurality of fill buffers, and to output a third cache line located in said fill buffers;
• and
• an execution unit coupled to said instruction fetch and dispatch unit that executes said instructions.

A non-blocking cache memory that caches data in a non-blocking manner, said non-blocking cache memory comprising:

• a plurality of data banks configured to store a plurality of cache lines of cache data;
• cache tag array and matching circuitry configured to store cache line addresses corresponding to said cache lines of cache data stored in said plurality of data banks, and to tag match memory accessing addresses of memory access operations to said cache line addresses;
• and
• a plurality of fill buffers configured to store non-sequential cache lines of cache data and concurrently to:
• (a) stage a first missed cache line of cache data;
• (b) replace a cache line in said plurality of data banks upon completion of a second missed cache line of cache data being loaded into one of said plurality of fill buffers;
• and
• (c) output a third cache line of cache data located in said fill buffers and addressed by a load operation.