A Model for Memory Interference in Multiprocessors
Stanley N. Rabinowitz · Missouri Journal of Mathematical Sciences · 1991
A model is described and analyzed for a multiprocessor shared memory system in which each memory bank can service a fixed number of access requests per cpu cycle.If n processors simultaneously request data from a common shared memory, it is usually not possible for all the requests to be satisfied at the same time.This is because the memory system usually places a limit on the number of requests that it can service at any given time.A typical method for allowing multiple requests to be satisfied is to divide the memory into m banks each capable of satisfying requests independently.The memory banks are usually interleaved, so that requests to successive memory locations will be serviced by successive memory banks.Even if m = n, full memory bus bandwidth cannot usually be achieved.This is because of the fact that if n processors each make a memory request at random, it is unlikely that the n requests will all be to different memory banks.In fact, the probability that the n requests go to all n banks is just the number of permutations of Z n divided by the number of mappings of Z n into Z n , where Z n represents the set of integers from 1 to n.This