A MARKOV MODEL FOR MULTIBUS MULTIPROCESSOR SYSTEMS UNDER ASYNCHRONOUSOPERATION

The multibus has been proposed as a simple, yet efficient, interconnec tion network for multiprocessors. Researchers have extensively investi gated the throughput of the multibus under synchronous operation. Howe ver, synchronous operation is mainly suitable when the messages exchan ged between the processors and memory modules of a multiprocessor are of fixed-length. In practice, these messages are usually variable in l ength, making asynchronous operation more efficient. We consider this type of operation in this paper. We model the multibus as a discrete-t ime Markov chain. The model is then used to evaluate the throughput of several example multibuses, under different working conditions. From these examples we gain insight into the operation of the multibus and identify the factors that greatly affect its throughput. A side benefi t of this work is that its results are immediately applicable to two o ther important types of interconnection networks, the crossbar switch and the shared bus, as they can both be looked upon as special cases o f the multibus.