A Prediction Method for Upper Bound of Reorder Buffer of NoCs Based on Network Calculus

In multi-path routing NoCs, the problem of packets disorder will occur due to the conflicts among flows. Reorder buffer at target node can keep the order of sending the packets by storing the packets temporarily. Traditional way is traversing all the paths to get the maximal value of reorder buffer, which is the upper bound of reorder buffer. As to a network of lager scale, traversal way is a time-consuming and low efficiency process. An prediction method to calculate the upper bound of reorder buffer was proposed: derive conflict coefficient of each target sub-flow from conflict matrix, and select the non-cross path pairs which have maximal conflict coefficient, predict the upper bound of reorder buffer through these path pairs. Compared to traditional way, this prediction method can shorten analysis time, simplify algorithm complexity, improve efficiency, and thus effectively reduce reorder buffer area and the design cost of NoC.