| There are 8 basic states that depend on how many requests have been
accumulated in this cycle. The probabilities of being in each of
these states is as follows. Note that the distribution of lengths
can be gotten by subtracting adjacent probabilities. Also, after
eight requests have been accumulated, the next state is S[1], with
probability 1.
S[1]: 0.2999373
S[2]: 0.2666110
S[3]: 0.2036611
S[4]: 0.1300140
S[5]: 6.6607021E-02
S[6]: 2.5681773E-02
S[7]: 6.6275732E-03
S[8]: 8.5911941E-04
In reality, there are 8*2**8 states, where each state depends on the
immediately preceding request, and the set of requests that have already
been made. However, these can be coalesced into 2**7 equivalent states,
by adding some value (mod 8) to the accumulated requests, so that the
last request can be considered a request to 0. This gives a system of
128 equations in 128 unknowns (plus one more equation: the sum of the
probabilities of being in each state must sum to 1). However, the system
has already been 'diagonalized', and is trivially solvable. The above
figures represent sums over these states.
In case there's some confusion over the above figures, the following are
the corresponding figures for 4-way interleaving.
S[1]: 0.4222972
S[2]: 0.3378378
S[3]: 0.1858108
S[4]: 5.4054052E-02
And 2-way interleaving:
S[1]: 0.6000000
S[2]: 0.4000000
And if you're interested in comparing figures against the case of independent
requests, here they are, too.
S[1]: 0.3081647
S[2]: 0.2696441
S[3]: 0.2022330
S[4]: 0.1263957
S[5]: 6.3197829E-02
S[6]: 2.3699183E-02
S[7]: 5.9247972E-03
S[8]: 7.4059970E-04
- Gilbert
|
| And here's the program (in Bliss). The floating-point figures were
gotten by "Debug> examine/f_float s[0]:s[7]" at the end of the program.
module thaller (main=main, addressing_mode(external=general))=
begin
literal k_leaves = 8;
literal k_states = 1^(k_leaves-1);
own p: vector[k_states],
t: vector[k_leaves],
s: vector[k_leaves];
routine cnt (x: bitvector[%bpval]) =
begin
local c: initial(0);
decr i from %bpval-1 to 0 do if .x[.i] then c = .c + 1;
return .c;
end;
routine next_state (cs, nb) =
begin
local x;
x = (2*.cs + 1);
x = .x ^ k_leaves or .x;
if .x<.nb,1,0> then return 0; ! Is bit nb set in here?
x = (.x^-(.nb+1)) and (k_states-1);
return .x;
end;
routine main =
begin
builtin
cvtlf,
divf,
addf,
mulf;
local
x_one, ! 1.0
x_frac, ! 1/(k_leaves+1)
x_sum;
ch$fill(0, %allocation(p), p[0]);
ch$fill(0, %allocation(t), t[0]);
ch$fill(0, %allocation(s), s[0]);
cvtlf(%ref(1), x_one);
cvtlf(%ref(k_leaves+1), x_frac);
divf(x_frac, x_one, x_frac);
! T[i] is the probability that the next reference
! after x[k] is x[(k+i) mod k_leaves]
!
incr i from 0 to k_leaves-1 do t[.i] = .x_frac;
addf(x_frac, t[1], t[1]);
! P[i] is the probability that we're in state i.
! The following determines the state:
! the set of banks active (so far) in this cycle
! and the bank for the last request.
! However, by symettry we can always transform a state
! ending with a request to bank k into one ending with
! a request to bank 0, by subtracting k from each bank
! (modulo k_leaves).
!
cvtlf(%ref(1), p[0]); ! Set the probbability of state 0 to 1
incr n from 0 to k_leaves-1 do
begin
incr i from 0 to k_states-1 do if cnt(.i) eql .n then
begin
!
! See how much this contibutes to following states.
! Note that we keep p[0] fixed at 1.
!
decr j from k_leaves-1 to 0 do
begin
local k, x_prod;
k = next_state (.i, .j);
if .k neq 0 then
begin
mulf(p[.i], t[.j], x_prod);
addf(x_prod, p[.k], p[.k]);
end;
end;
end;
end;
! Now we must adjust p[0], and scale the values.
! Actually, we needn't explicitly adjust p[0], just scale everything.
!
cvtlf(%ref(0), x_sum);
incr i from 0 to k_states-1 do addf(p[.i], x_sum, x_sum);
incr i from 0 to k_states-1 do divf(x_sum, p[.i], p[.i]);
! Realize that we're more interested in probabilities of these in groups,
! such as all those with one bit set, et cetera.
!
incr i from 0 to k_states-1 do
begin
local c: initial(cnt(.i));
addf(p[.i], s[.c], s[.c]);
end;
! Now display the probabilities
!
0;
return 1;
end;
end
eludom
|
| Roughly, you can get your figures by computing X[i] = S[i+1]-S[i],
where S[9] is zero, and renormailizing so that the sum of the X[i]
is 1. Or (realizing that the sum of the differences is S[1]),
P[i] = (S[i+1]-S[i])/S[1]. This gives figures pretty close to yours.
I say roughly because the average lengths should really be computed
based on the 127 states, rather than these 8 states (there may be no
difference, but then again...). I'll modify the program to give this
information, too. Mebbe I'll even learn how to display floating point
numbers.
By the way, note that the program can be easily modified to compute
equivalent figures for other access distributions (that is, for any
set of T[i], where
P( a =(i+k)mod 8 | a =i ) = T[k]
j j-1
This may be worthwhile if you want to try the model that makes successive
accesses to the same bank more likely.
|