Multiprocessor shared memory access and rewards

Computer architecture and software have evolved largely independently of mathematical models for computers as physical systems. Most bus arbitration policies are independent of the algorithm being executed on the multiprocessing architecture. While this may be adequate for platforms for which utilization is much smaller than capacity, high-performance applications require maximum utilization of resources. Communications technologies such as Asynchronous Transfer Mode (ATM) have demonstrated the usefulness of arbitration schemes that are application dependent. This paper introduces the application of a Markov analysis based upon rewards to bus arbitration in shared memory architectures. A two-processor example is developed which relates system gain to algorithm. Generalization is provided so the formulation my be extended to Nprocessors.