performance analysis of high-speed digital buses for multiprocessing systems
Current multiprocessing systems are often organized by connecting several devices with similar characteristics (usually processors) to a common bus. These devices present access with minimal delay; access is controlled by the bus arbitration algorithm. This paper presents a probabilistic analysis of several arbitration algorithms according to several criteria that reflect their relative performances in (1) rendering equal service to all competing devices and (2) allocating available bus bandwidth efficiently. The sensitivity of these criteria to the number of devices on the bus, the speed of the bus, and the distribution of interrequest times is considered. A probabilistic model for the quantitative comparison of these algorithms is constructed in which multiple devices repeatedly issue bus requests at random intervals according to an arbitrary distribution function and are serviced according to one of the algorithms; the devices do not buffer bus requests. The algorithms studied include the static priority, fixed time slice (FTS), two dynamic priority, and first-come, first-served (FCFS) schemes. The performance measures are computed by simulation. The analysis reveals that under heavy bus loads, the dynamic priority and FCFS algorithms offer significantly better performances by these measures than do the static priority and FTS schemes.
performance performance analysis analysis digitize systems device processor access minimal algorithm paper probabilistic analysis rendering bandwidth sensitive distributed timing probabilistic models comparisons randomization interval functional buffers priorities slice dynamic scheme performance measurement measurement simulation relation