Inverse Weight Based Arbitration Algorithm for On-Chip Networks

As the number of cores in general-purpose processors increases, quality of service becomes an increasingly serious problem. A key to its solution is arbitration algorithms in the on-chip network. Numerous algorithms have been proposed, each having some limitations. This paper introduces an algorithm based on inverse weights, dynamically assigned to each router port. The algorithm has three features. The first is logarithmic hardware cost scaling, i.e. practically unlimited network size. The second is low critical path delays as the arbiters can use relation matrices. The third is max-min fairness, i.e. adaptivity to non-uniform load. Experiments on a 8x8 mesh network model demonstrated better quality of service than existing algorithms of input-based or source-based round-robin and least-recently-used, and quota-based weighted arbitration.