Achieving Global Fairness for On-Chip Network Using Group Allocation

Many papers focus on how to provide high performance for on-chip network. However, fewer papers have discussed fair resource allocation. In fact, global unfairness problem does exist in a network even if locally fair arbitration is adopted. In this paper, we propose Group Allocation to solve global unfairness problem. By controlling the timing to assert the allocation request, Group Allocation changes the service unit of allocation from packet to Group which takes one packet from every competing flow on an input port. In this way, router delivers one packet of every competing flow in an allocation round, so link bandwidth can be equally shared by competitors. Additionally, due to grouping, Group can be automatically adjusted based on the competition of flows. Hence, Group Allocation can be applied to various traffic patterns without prior knowledge of traffic patterns. Simulation results show Group Allocation is able to allocate bandwidth evenly and incur less impact on performance. In hotspot traffic case, the standard deviation of accepted throughputs under Group Allocation is 5.5179*10^-6 flits/cycle and it is 0.0210 flits/cycle under round robin policy. It confirms Group Allocation reduces the difference of bandwidth usage among flows and allows resource allocation to be fair.