|
|
|
|
|
|
|
Figure 6.21
Pipelined processors: (a) binomial model (simple processor); (b) typical
pipelined processor. |
|
|
|
|
|
|
|
|
Thus, the binomial approximation is useful whenever we have: |
|
|
|
|
|
|
|
|
1. Simple processor memory configuration (a binomial arrival distribution). |
|
|
|
|
|
|
|
|
3. Request-response behavior between processor and memory, where the processor makes exactly n requests per Tc. |
|
|
|
|
|
|
|
|
The Delta (d)-Binomial Model |
|
|
|
|
|
|
|
|
If we replace the simple processor (making a request each Tc) with a pipelined processor, the binomial model may fail. The binomial model assumes that the processor requests one memory access each Tc; n processors make n requests. Suppose that a processor has a buffer (e.g., I-buffer, register set, cache) that supplies many of the processor requests, so that the processor-requestor makes a request with probability d. This simple binomial model cannot be used as it cannot distinguish between a single simple processor (n = 1) making a request each Tc with probability = 1 and, e.g., two processors each making (on the average) 0.5 requests per Tc (n = 1 but d = 0.5). The former case has no contention, but the latter case has memory contention, as both sources will occasionally make simultaneous requests to the same memory module. Worse still is the case where each of two sources makes requests with Prob = 0.25. Now n (requests per Tc) = 0.5 and the simple binomial model fails. |
|
|
|
|
|
|
|
|
To correct this, we introduce the d-binomial model. |
|
|
|
|
|
|
|
|
Suppose the processor makes a request each Tc with probability p (p ¹ 1). This can occur even in relatively simple processors with register sets (DF used primarily on loads) or with very simple I-buffers (IF fetches perhaps two instructions). |
|
|
|
|
|
|
|
|
Since we still assume a relatively simple processor, when a request is made to the memory any resulting contention directly affects performance. The MB/B/1 closed-queue model is still appropriate, but d, the probability of a processor access during Tc, does not equal one (in fact, p = d/m). In the simple binomial model, the restriction on n (n ³ 1) is a direct consequence of d = 1. Thus, we have a more general definition of p: |
|
|
|
|
|
