Customization of arbitration policies and buffer space distribution using continuous-time Markov decision processes

This paper presents a stochastic approach for bus arbiter design. Arbiter design includes policy design, buffer insertion, and optimal buffer sizing. The methodology uses continuous-time Markov decision processes (CTMDPs) to get optimal arbitration policies and buffer space distribution. The mathematical formulation of this problem in terms of a CTMDP framework leads to a linear programming problem for bus architectures without bridges, and to a nonlinear formulation for bus architectures with bridges. In the second case, the methodology splits the nonlinear problem into several smaller, linear subsystems by introducing buffers at the bridges, and then solves the linear subsystems. In our experiments, we found that stochastic policies provide efficient arbitration for bus architectures with redundant buses for communication between processors. The size of buffers in some cases was reduced by 90%, and by 50% in the average sense. Data loss was reduced by 20% to 50% with redistribution of the buffer space.