1. Field of the Invention
The present invention is generally related to multiprocessor computing devices. More particularly, the present invention is directed to probabilistic arbitration for data packet routing in multiprocessor devices.
2. Description of Related Art
Many-core chip multiprocessors integrate dozens of small processing cores with an on-chip interconnect consisting of point-to-point links. This interconnection enables the processing cores to not only communicate, but to share common resources such as main memory resources and I/O controllers. In particular, accessing memory from shared memory controllers is especially performance sensitive and these types of systems will introduce non-uniformity into memory and I/O access. While systems may implement many cores, they may do so with only a few memory and I/O controllers. This brings new light to old problems of providing equal and fair access to a set of shared resources regardless of where, or which processing core, is scheduled to execute a thread.
In the past, the solution space has been divided into two basic approach classes. The first class of approaches is based on injection rate control. Injection rate control can be placed at either the injection point of each source or the input channel of each intermediate node to limit the maximum number of flits a network or an individual node can service for each flow over a period of time. This time period of bandwidth accounting has been called “frame” in some literature. The second class of approaches proposes sophisticated arbitration techniques to provide equal and fair service. Here, systems have been developed for equal and fair service in long-haul IP networks where large buffers are available. These may achieve fairness and high network utilization, but each router is required to maintain per-flow state and queues that would be impractical in an on-chip network.