Probabilistic Distance-based Arbitration: Providing Equality of Service for Many-core CMPs

Michael M. Lee
John Kim
Dennis Abts
Jae W. Lee
MICRO43: Proceedings of the 43rd Annual International Symposium on Microarchitecture, IEEE/ACM(2010)
Google Scholar


Emerging many-core chip multiprocessors will integrate dozens of small processing cores with an on-chip interconnect consisting of point-to-point links. The interconnect enables the processing cores to not onl communicate, but to share common resources such as main memory resources and I/O controllers. In this work, we propose an arbitration scheme to enable equality of service (EoS) in access to a chip's shared resources. That is, we seek to remove any bias in a core's access to a shared resource based on its location within the CMP. We propose using probabilistic arbitration combined with distance-based weights to achieve EoSand overcome the limitation of conventional round-robin arbiter. We describe how nonlinear weights need to be used with probabilistic arbiters and propose three different arbitration weight metrics -- fixed weight, constantly increasing weight, and variably increasing weight. By only modifying the arbitration of an on-chip router, we do not require any additional buffers or virtual channels and create a simple, low-cost mechanism for achieving EoS. We evaluate our arbitration scheme across a wide range of traffic patterns. In addition to providing EoS, the proposed arbitration has additional benefits which include providing quality-of-service features (such as differentiated service) and providing fairness in terms of both throughput and latency that approaches the global fairness achieved with age-base arbitration -- thus, providing a more stable network by achieving high sustained throughput beyond saturation.