Memory-interference model for multiprocessors based on semi-Markov processes

Abstract: The interference that results from pro-cessors attempting to simultaneously access the same main memory in a multiprocessor can be reduced by constructing the memory from separate modules accessible through a crossbar network. The effectiveness of this solution depends on the number of processors and the number of memory modules, and on the parameters of the computation being executed, such as the think time of the processors, the frequency of their access to main memory, and the length of time these accesses are connected to memory. This paper presents a memory-interference model that allows one to evaluate the performance of crossbar-based multiprocessors. The model is a discrete-time model that explicitly describes each processing element's behaviour by means of a semi-Markov process. The chief advantage of the semi-Markov model is its conciseness and its capability of accounting for variance in model parameters. The model is first developed for the case in which memory accesses are directed to each memory module equiprobably. Central to the model is a theorem that gives the residual waiting time experienced by a processor when accessing a busy memory. Comparisons are made with earlier models. These comparisons show the semi-Markov model to be more accurate, particu-larly in those cases where there is a high degree of variance in the connection time. Finally, the model is generalised to deal with cases where accesses to each memory module are not equi-probable.