Livelock prevention mechanism in a ring shaped interconnect utilizing round robin sampling

摘要

A novel and useful cost effective mechanism for detecting the livelock/starvation of transactions in a ring shaped interconnect that utilizes minimal logic resources. Rather than monitor all transactions concurrently in the ring, the mechanism monitors only a single transaction in the ring. A sampling point is located at a point in the ring which contains a set of N latches. If the monitored transaction is not being starved, it is released and the detection logic moves on the next candidate transaction in round robin fashion. If the monitored transaction passes the sampling point a threshold number of times, it is deemed to be starved and a starvation prevention handling procedure is activated. By traversing the entire ring a single transaction at a time, all starving transactions will eventually be detected with an upper limit on the detection time of O(N2).

主权项

1. A method of livelock prevention for use in an N-stage ring shaped interconnect, said method comprising:
injecting one or more transactions into said ring; sampling a single injected candidate transaction at a sample point in said ring after it has looped at least once around said ring; defining a starvation transaction as an injected transaction that has looped a predetermined threshold of times around the ring; and if said injected candidate transaction is a starvation transaction as defined, then flagging said injected candidate transaction as a starvation transaction.