Computing in parallel processing environments
A computing system comprises one or more core processors coupled to a communication network among the cores via a switch in each core and switching circuitry to forward data among cores and switches. Features include a programmable classification processor for directing packets, techniques for managing virtual functions on an IO accelerator card, packet scheduling techniques, multi-processor communication using shared FIFOs, programmable duty cycle adjustment and delay adjustment circuits, a new class of instructions that use a ready bit, and cache coherence and memory ordering techniques.
1. A method for maintaining cache coherence in a computing system, the method executed by a cache controller comprising:
producing from a write address of a given write operation, an N-bit compressed representation of the write address of the given write operation together with write addresses for write operations that have been sent to a coherence controller;
incrementing an outstanding write counter for the given write operation;
sending the given write operation to the coherency controller;
receiving an acknowledgement from the coherence controller and decrementing the write counter; and
clearing the N-bit compressed representation whenever the outstanding write counter clears to zero.
2. The method of claim 1 wherein the cache coherency is tracked by the cache controller and write transactions that hit in a shared L2 cache are tracked by the cache controller.
3. The method of claim 1 wherein the cache controller includes the outstanding write counter, and the method further comprises:
receiving a write transaction having an address; and
indicating whether the address of the received write transaction has been sent to the cache controller and has been mixed into the compressed N-bit representation.
4. The method of claim 1 wherein write operations are sent to a next level cache that includes coherency controller that sends the acknowledgement.
5. The method of claim 1 wherein the N-bit compressed representation is produced by applying a hash function such that the resulting N-bit compressed representation is conservative such that when the given address has been sent to the coherence controller and in the compressed N-bit representation, and a read request for the given address arrives, a comparison function indicates that there could be the write operation that is outstanding to the given address.
6. The system of claim 1 wherein producing the N-bit compressed representation further comprises:
executing by a processor a store having an address that hits in a shared cache;
recording by the cache controller a processor ID of the processor in a written by tag field for a cache block;
producing a new value of the N-bit compressed representation by the cache controller hashing the address and placing the hashed address into the N-bit compressed representation; and
incrementing by the cache controller the outstanding write counter in response to the store.
7. The method of claim 1 , further comprises:
receiving a read address;
indicating whether the read address corresponds to a write address has been sent to the coherence controller and that has been mixed into the representation; and if so, invalidating a cache block corresponding to the read address.
8. The method of claim 4 , further comprises:
receiving a read address;
indicating whether the read address corresponds to a write address that has been sent to the coherence controller and mixed into the N bit representation; and if not,
clearing a written by tag field for a cache block corresponding to the read address.
9. The method of claim 4 wherein the acknowledgement is a write acknowledgement that is received from the coherence controller, and the method further comprises:
upon receiving the write acknowledgement, decrementing the outstanding write counter; and
testing if the outstanding write counter equals zero.
10. The method of claim 1 further comprising:
determining that a read request from a processor hits on a cache block;
reading a written by tag field; and
determining whether the N-bit compressed representation equals zero.
11. The method of claim 10 wherein if the N-bit compressed representation equals zero, the method further comprises:
satisfying the read request; and
clearing the “written by” tag field for the cache block.
12. The method of claim 10 wherein if the N-bit compressed representation does not equal zero, the method further comprises:
applying a comparison function to the N-bit compressed representation; and if the comparison indicates that there could be an outstanding write to the cache block, then invalidating the cache block; and
sending the read request to the coherence controller.
13. The method of claim 10 wherein if the N-bit compressed representation does not equal zero, the method further comprises:
applying a comparison function to the N-bit compressed representation; and if the comparison indicates that there is not an outstanding write to the cache block, then satisfying the read request; and
clearing the “written by” tag field for the cache block.
14. A computing system comprising:
a cache coherency controller; and
a cache controller configured to:
produce from a write address of a given write operation, an N-bit compressed representation of the write address of the given write operation together with write addresses for write operations that have been sent to the coherence controller;
an outstanding write counter that is incremented for the given write operation sent to the cache coherency controller;
with the cache controller further configured to:
receive an acknowledgement from the coherence controller and decrement the outstanding write counter; and
clear the N-bit compressed representation whenever the outstanding write counter clears to zero.
15. The system of claim 14 further comprising:
a shared L2 cache, and with the cache controller tracking write transactions that hit in the shared L2 cache.
16. The system of claim 14 wherein writes are sent to a next level cache that includes the coherency controller that sends the acknowledgement.
17. The system of claim 14 wherein the N-bit compressed representation is produced by applying a hash function such that the resulting N-bit compressed representation is conservative.
18. The system of claim 14 wherein the system is further comprises a processor the executes a store having an address that hits in a shared cache, the cache controller further configured to:
record a processor ID of the processor in a written by tag field for a cache block;
produce a new value of the N-bit compressed representation by the cache controller by hashing the address and placing the hashed address into the N-bit compressed representation; and
increment by the cache controller the outstanding write counter in response to the store.
19. The system of claim 14 , further configured to:
receive a read address;
indicate whether the read address corresponds to a write address has been sent to the coherence controller and that has been mixed into the representation; and if so,
invalidate a cache block corresponding to the read address.
20. The system of claim 14 , further configured to:
receive a read address;
indicate whether the read address corresponds to a write address that has been sent to the coherence controller and mixed into the N bit representation; and if not, clear a written by tag field for a cache block corresponding to the read address.
21. The system of claim 14 wherein the acknowledgement is a write acknowledgement that is received from the coherence controller, and the system is further configured to:
decrement the outstanding write counter; and
test if the outstanding write counter equals zero.
22. A computer program product tangibly stored in non-transitory media, the computer program product executable on a system including a tiled multicore processor that includes plural processor tiles, with the processor tiles comprising a processor, memory and a switch, the computer program product comprising instructions to:
produce from a write address of a given write operation, an N-bit compressed representation of the write address of the given write operation together with write addresses for write operations that have been sent to a coherence controller;
increment an outstanding write counter for the given write operation;
sending the given write operation to the coherency controller;
receive an acknowledgement from the coherence controller and decrement the outstanding write counter; and
clear the N-bit compressed representation whenever the outstanding write counter clears to zero.
23. The computer program product of claim 22 further comprising instructions to:
receive an indication of a processor that executes a store having an address that hits in a shared cache;
record a processor ID of the processor in a written by tag field for a cache block;
produce a new value of the N-bit compressed representation by the cache controller by hashing the address and placing the hashed address into the N-bit compressed representation; and
increment by the cache controller the outstanding write counter in response to the store.