Cascaded round robin request selection method and apparatus

Abstract

A two-level cascaded round robin arbiter. The arbiter arbitrates between a plurality of requesters for a shared resource in a round robin fashion. The arbiter comprises a series of first level arbiters which each receive a group of the plurality of requesters and select one requester in each group in a round robin manner. The first level arbiters operate in parallel to select their one requester thereby improving the overall selection time. The first level arbiters provide their selected requester to a second level arbiter which selects one group's selected requester to award use of the shared resource. The second level arbiter selects from among the groups in a round robin manner subject to an indication of a wrap condition provided by each of the first level arbiters to the second level arbiter. A wrap condition occurs when, in the process of selecting a requester, a first level arbiter has cycled from the previously selected requester through the fixed round robin order down to the lowest number requester and back up to the highest number requester. The second level arbiter continues to select the previously selected group as long as a wrap condition has not occurred in the previously selected group. Once a wrap condition has occurred, the second level arbiter selects the next group in the fixed cyclical order which has a currently active request. Each arbitration period the requester selected by the second level arbiter is latched and fed back to the first and second level arbiters which use the feedback history to select requesters according to the fixed cyclical round robin order.