A Study in Memory Interference Models (Performance Evaluation, Semi-Markov Process, Markov Chain, Multiprocessor, Multiple-Bus System).

Abstract

A discrete time model of memory interference in multiprocessors is developed. The model, termed the semi-Markov memory interference model, explicitly describes the behavior of each processing element by means of a semi-Markov process. The model requires as input the number of processing elements and the number of memory modules in the multiprocessor, the mean think time of the processing elements, the first and second moments of the connection time between the processing elements and the memories, and the probability mass function characterizing the destination of the requests for memories of the processing elements. The model produces as output the memory b and width, processing element utilization, memory module utilization average queue length at a memory, and average waiting time experienced by a processing element while waiting to access a memory. Thus, it is possible to analyze the interaction of variable connection time, think time and the distribution of the destination of the memory requests on the system performance. This modeling capability is attained without having to employ a complex Markov chain. Indeed, the number of states in the semi-Markov process describing a processing element is dependent only on the probability mass function describing the destination of the memory requests. For instance, in the simplest and most common case when requests are directed with equal probability to each memory module, a four state semi-Markov process is sufficient regardless of the think and connection time distributions. The accuracy and capability of the model is demonstrated by comparing the results of the model with simulation. Moreover, the performance of a multiprocessor system with cache memories is analyzed using the model which assumes that the interconnection network can be a full crossbar network or a multiple-bus network.