Head of line blocking mitigation in a reconfigurable data processor
A coarse-grained reconfigurable (CGR) processor comprises a first network and a second network; a plurality of agents coupled to the first network; an array of CGR units coupled together by the second network; and a tile agent coupled between the first network and the second network. The tile agent comprises a plurality of links, a plurality of credit counters associated with respective agents of the plurality of agents, a plurality of credit-hog counters associated with respective links of the plurality of links, and an arbiter to manage access to the first network from the plurality of links based their associated credit-hog counters. Furthermore, a credit-hog counter of the plurality of credit-hog counters changes in response to processing a request for a transaction from its associated link.
1. A coarse-grained reconfigurable (CGR) processor comprising:
a first network and a second network;
a plurality of agents coupled to the first network;
an array of CGR units coupled together by the second network; and
a tile agent coupled between the first network and the second network, the tile agent comprising:
a plurality of links;
a plurality of credit counters associated with respective agents of the plurality of agents;
a plurality of credit-hog counters associated with respective links of the plurality of links, including a first credit-hog counter and a second credit-hog counter; and
an arbiter to manage access to the first network from the plurality of links based their associated credit-hog counters and to perform a high priority arbitration cycle that includes a first transaction request based on a value of the first credit-hog counter and excludes a second transaction request based on a value of the second credit-hog counter, and a low priority arbitration cycle that includes both the first transaction request and the second transaction independent of the value of the first credit-hog counter and the value of the second credit-hog counter;
wherein a credit-hog counter of the plurality of credit-hog counters changes in response to processing a request for a transaction from its associated link,
and
an arbiter to manage access of the first network from the plurality of links based their associated credit-hog counters.
2. The CGR processor of claim 1 , the arbiter configured to provide a first level of bandwidth on the first network to a first link of the plurality of links in response to its associated credit-hog counter having a value in a first range, and to provide a second level of bandwidth on the first network to a second link of the plurality of links in response to its associated credit-hog counter having a value in a second range, wherein the first level of bandwidth is higher than the second level of bandwidth.
3. The CGR processor of claim 1 , further comprising circuitry to assign a first priority to a first set of links of the plurality of links having values of their associated credit-hog counters in a first range and to assign a second priority to a second set of links of the plurality of links having values of their associated credit-hog counters in a second range; and
the arbiter including the first set of links in a first percentage of arbitration cycles for the first network and including the second set of links in a second percentage of arbitration cycles for the first network that is lower than the first percentage.
4. The CGR processor of claim 3 , wherein a link is included in the first set of links or the second set of links only if it has a pending transaction and a credit counter associated with a destination agent for the pending transaction indicates that credits are available.
5. The CGR processor of claim 3 , further comprising a low priority ratio register, wherein the second percentage is set based on a value set in the low priority ratio register.
6. The CGR processor of claim 5 , wherein the first percentage is 100% and the second percentage is determined by a ratio of the value set in the low priority ratio register to 16.
7. The CGR processor of claim 1 , further comprising circuitry to change credit-hog counters of the plurality of credit-hog counters, the circuitry configured to decrement the credit-hog counter associated with a particular link of the plurality of links in response to the processing of the request to an agent of the plurality of agents from the particular link unless it is incremented in response the processing of the request because an immediately prior request from the particular link was to the same agent and the credit counter associated with the agent indicates that less than a predetermined threshold of credits are available.
8. The CGR processor of claim 7 , wherein the plurality of credit counters and the plurality of credit-hog counters are saturating counters that do not change when decremented while having a value of all zeros or when incremented while having a value of all ones.
9. The CGR processor of claim 8 , the arbiter configured to provide a first level of bandwidth on the first network to a first link of the plurality of links in response to its respective credit-hog counter having a value less than or equal to a credit-hog threshold, and to provide a second level of bandwidth on the first network to a second link of the plurality of links in response to its respective credit-hog counter having a value greater than the credit-hog threshold, wherein the first level of bandwidth is higher than the second level of bandwidth.
10. The CGR processor of claim 9 , wherein the credit-hog threshold is 0.
11. The CGR processor of claim 10 , further comprising a low priority ratio register; and the arbiter configured to perform R low priority arbitration cycles and N-R high priority arbitration cycles out of a group of N arbitration cycles, where R is a value retrieved from the low priority ratio register and N is a predetermined constant.
12. The CGR processor of claim 1 , the plurality of links in the tile agent including a first link and a second link;
the plurality of credit counters in the tile agent including a first credit counter associated with a first agent of the plurality of agents and a second credit counter associated with a second agent of the plurality of agents;
wherein the first credit counter is initialized to zero, incremented in response to sending a first transaction from a link of the plurality of links to the first agent over the first network, and decremented in response to receiving a token from the first agent on a credit network of the first network; and
the second credit counter is initialized to zero, incremented in response to sending a second transaction from a link of the plurality of links to the second agent over the first network, and decremented in response to receiving a token from the second agent on the credit network of the first network.
13. The CGR processor of claim 12 , wherein the first credit counter comprises a first request network credit counter, the first transaction and the second transaction are sent over a request network of the first network and the token from the first agent and the token from the second agent represent end-to-end request credits.
14. A method to arbitrate for a first network in a coarse-grained reconfigurable (CGR) processor that includes the first network and a second network, a plurality of agents coupled to the first network, an array of CGR units coupled together by the second network, and a tile agent coupled between the first network and the second network, the tile agent having a plurality of links, a plurality of credit-hog counters associated with respective links of the plurality of links, and an arbiter to manage access to the first network from the plurality of links, the method comprising:
queueing a request for a first transaction on the first network from a first link in the plurality of links, wherein a value of a first credit-hog counter of the plurality of credit-hog counters associated with the first link is in a first range;
queueing a request for a second transaction on the first network from a second link in the plurality of links, wherein a value of a second credit-hog counter of the plurality of credit-hog counters associated with the second link is in a second range;
performing a high priority arbitration cycle, by the arbiter, that includes the first transaction request in the high priority arbitration cycle based on the value of the first credit-hog counter being in the first range and excludes the second transaction request based on the value of the second credit-hog counter being in the second range;
performing a low priority arbitration cycle, by the arbiter, that includes both the first transaction request and the second transaction request in the low priority arbitration cycle, independent of the value of the first credit-hog counter and the value of the second credit-hog counter;
updating the first credit-hog counter upon processing a request for a transaction on the first network from the first link; and
updating the second credit-hog counter upon processing a request for a transaction on the first network from the second link.
15. The method of claim 14 , wherein updating a particular credit-hog counter, including the first credit-hog counter and the second credit-hog counter, comprises:
incrementing the particular credit-hog counter associated with a particular link of the plurality of links upon processing a second of two consecutive requests from the particular link to a single agent of the plurality of agents while a credit counter associated with the single agent indicates fewer than a predetermined threshold of credits are available;
decrementing the particular credit-hog counter upon processing the second of two consecutive requests from the particular link to the single agent of the plurality of agents while the credit counter associated with the single agent indicates a number of available credits greater than or equal to the predetermined threshold; and
decrementing the particular credit-hog counter upon processing a request from the particular link that is not the second of two consecutive requests;
wherein the particular credit-hog counter is a saturating counter that does not change when decremented while having a value of all zeros or when incremented while having a value of all ones.
16. The method of claim 14 , the tile agent including a plurality of credit counters associated with respective agents of the plurality of agents, the method further comprising:
initializing a particular credit counter of the plurality of credit counters to zero;
incrementing the particular credit counter in response to sending a transaction from a link of the plurality of links to a particular agent of the plurality of agents associated with the particular credit counter over the first network; and
decrementing the particular credit counter in response to receiving a credit from the particular agent on a credit network of the first network.
17. The method of claim 14 , further comprising:
receiving, in a low priority ratio register, a low priority count value R; and
performing, by the arbiter, a predetermined number of arbitration cycles N, where R of the N arbitration cycles are low priority arbitration cycles and N-R of the N arbitration cycles are high priority arbitration cycles.
18. The method of claim 17 , wherein Nis 16 and R is 8 or less.
19. The method of claim 14 , wherein the first range is 0 and the second range is 1 to a maximum value of a credit-hog counter of the plurality of credit-hog counters.
20. The method of claim 14 , further comprising:
including a transaction request from a link of the plurality of links in a high priority arbitration cycle only if a credit counter associated a destination agent of the transaction request shows that credits are available.