Supplementary material of the paper "Response Times Analysis in a two-Level Hierarchical System with Static Multi-Access" (submission 5686) submitted to the 41st ACM/SIGAPP Symposium on Applied Computing (SAC)

Supplemen a y ma e ial o Response Times Analysis in a
Two-Le el Hie a chical Sys em wi h S a ic Mul i-Access
This is he documen o de ailed p oo s o ou a icle: "Response Times Analysis in a Two-
Le el Hie a chical Sys em wi h S a ic Mul i-Access". Fo he emainde , a wo-le el hie a chical
sys em is composed o wo ypes o scheduling:
•The scheduling o pa i ions;
•A scheduling o ask o each pa i ion.
A compu a ional module is modeled as a 2-le el hie a chical unip ocesso sys em. A he
p ocesso le el, execu ion ime is sha ed among mpa i ions (m∈N∗) deno ed A1, . . . , Am.
Thei scheduling is s a ically de ined o -line by a pe iodic cycle o leng h Tcyc, which is epea ed
inde ini ely. The pa i ion model is s a ic [?]. We s udy a mul i-access pa i ion model, whe e a
pa i ion can be g an ed access o he p ocesso mul iple imes pe cycle. We deno e by A his
pa i ion and by nA(wi h nA∈N∗and nA>1) he numbe o Access Time In e als (ATIs).
The k h ATI (wi h k∈ {1, . . . , nA}) is a non-null ime in e al [SA
k, EA
k]whe e SA
kand EA
ka e
espec i ely he s a and end imes wi hin he cycle. In e als a e wo by wo disjoin s and
comp ised in o he cycle, hen:
0≤SA
1< EA
1< SA
2< EA
2<· · · < SA
nA< EA
nA≤Tcyc
The u iliza ion ac o o he k- h ATI, deno ed UA
k, is he a io o ime allowed o he
ATI du ing a cycle. The u iliza ion ac o o pa i ion A, deno ed UA, is hen he sum o he
u iliza ion o i s ATI.
UA=
nA
X
k=1
UA
kwi h: UA
k=EA
k−SA
k
Tcyc
We assume he s udy o an unique pa i ion A. We wan in es iga e he ime alloca ed o i
wi hin an in e al ime o ype [x, x + ](x, )∈(R+)2. This supply ime is modeled by he
called unc ion supply unc ion.
1
(a) A A A A
pa i ion
scheduling
(b) 0
a A( )1
(c) 0
a A
1( )1
SA
1EA
1SA
1
(d) 0
a A
2( )1
0SA
2EA
2SA
2
Tcyc 2Tcyc
Figu e 1: Pe iodic ec angula unc ions o a 2-access pa i ion
The supply unc ion mus be exp essed o any in e als o he o m [x,x+ ] (Th.1). We
p opose a new o mula ion, which elies on he in eg a ion o e he in e al [x,x+ ] o he
Fou ie se ies decomposi ion o he ac i a ion unc ion a A(Lemma 1.).
Lemma 1. (Sec ion 4.1 - Page 4.) Conside ing a mul i-access pa i ion A, he Fou ie se ies
decomposi ion o he k- h access unc ion A
kexis s, and is equal o:
a A
k( ) = a0+
∞
X
n=1
(ancos(ωnθ)+bnsin(ωnθ))
wi h: ω=2π
Tcyc
,a0=UA
k,
∀n∈N∗, an=2
ωnTcyc
[sin(ωnEA
k)−sin(ωnSA
k)],
and ∀n∈N∗, bn=2
ωnTcyc
[cos(ωnSA
k)−cos(ωnEA
k)].
P oo . The unc ion a A
kis pe iodic acco ding o Tand piecewise smoo h, hen i is decom-
posable in o Fou ie Se ies by a A
k( ) = a0+
∞
X
n=1
(ancos(ωn ) + bnsin(ωn )). Compu ing i s
coe icien s:
By de ini ion,
a0(a A
k) = 1
Tcyc ZTcyc
0
a A
k(u) du
an(a A
k) = 2
Tcyc ZTcyc
0
a A
k(u) cos(ωnu) du
bn(a A
k) = 2
Tcyc ZTcyc
0
a A
k(u) sin(ωnu) du
2
Then,
a0(a A
k) = 1
Tcyc ZEA
k
SA
k
a A
k(u) du=1
Tcyc
(EA
k−SA
k) = UA
an(a A
k) = 2
Tcyc ZEA
k
SA
k
cos(ωnu) du=2
ωnTcyc
(sin(ωnEA
k)−sin(ωnSA
k))
bn(a A
k) = 2
Tcyc ZEA
k
SA
k
sin(ωnu) du=2
ωnTcyc
(cos(ωnSA
k)−cos(ωnEA
k))
Theo em 1. (Sec ion 4.2 - Page 4.) Le be x∈[0, Tcyc), an explici exp ession o he elease-
ime speci ic supply unc ion s A
xis:
s A
x( ) = Tcyc
2
nA
X
k=1 gx+ −EA
k
Tcyc −gx−EA
k
Tcyc 
−gx+ −SA
k
Tcyc +gx−SA
k
Tcyc 
wi h ∀y∈R+, g(y) = ⌊y⌋2−2y⌊y⌋+⌊y⌋
P oo . We ha e
s A
x( ) = Zx+
x
nA
X
k=1
a A
k(u) du=Zx+
x
nA
X
k=1 a0+
∞
X
n=1
(ancos(ωnu) + bnsin(ωnu))!du
as he cumula i e ime in he in e al [x,x+ ].
TERM-BY-TERM INTEGRATION :
I is pe iodic, and in any ini e in e al is con inuous excep o a ini e numbe o ini e
discon inui ies, hen, he Fou ie se ies de elopmen no need o con e ge, he in eg al o
be ween any wo ini e limi s may be ob ained by in eg a ing his se ies e m-by- e m be ween
hese limi s.
As a A
k unc ions a e piecewise con inuous on he in e al [x,x+ ], we may use he e m-by-
e m in eg a ion o Fou ie se ies. Then:
s A
x( ) =
nA
X
k=1 Zx+
x
a0du+
∞
X
n=1 Zx+
x
(ancos(ωnu) + bnsin(ωnu)) du!
3
s A
x( ) =
nA
X
k=1 a0Zx+
x
du+
∞
X
n=1
anZx+
x
cos(ωnu)du+bnZx+
x
sin(ωnu) du!
s A
x( ) = UA +
nA
X
k=1
2
Tcycω2
∞
X
n=1
1
n2( sin(ωn(x+ )) sin(ωnEA
k)
| {z }
1
−sin(ωnx) sin(ωnEA
k)
| {z }
2
−sin(ωn(x+ )) sin(ωnSA
k)
| {z }
3
+ sin(ωnx) sin(ωnSA
k)
| {z }
4
−cos(ωn(x+ )) cos(ωnSA
k)
| {z }
3
+ cos(ωnx) cos(ωnSA
k)
| {z }
4
+ cos(ωn(x+ )) cos(ωnEA
k)
| {z }
1
−cos(ωnx) cos(ωnEA
k)
| {z }
2
By coupling wo in eg a ions, we ecognize 4 o mulas o ype:
cos(a−b) = cos(a) cos(b) + sin(a) sin(b)
Then,
s A
x( ) = UA +
nA
X
k=1
2
Tcycω2
∞
X
n=1
1
n2( cos(ωn(x+ −EA
k)) −cos(ωn(x−EA
k))
−cos(ωn(x+ −SA
k)) + cos(ωn(x−SA
k))
We ha e now ou se ies o ype cos(ny)
n2. The esul o his se ies is known as:
∀y∈[0,2π],
∞
X
n=1
cos(ny)
n2=y2
4−πy
2+π2
6
Then
s A
x( ) = UA +C
nA
X
k=1
∞
X
n=1
cos(nzk,1(x, ))
n2−cos(nzk,2(x, ))
n2+
cos(nzk,4(x))
n2−cos(nzk,3(x))
n2
(1)
wi h C=2
Tcycω2,zk,1(x, ) = ω(x+ −EA
k),zk,2(x, ) = ω(x+ −SA
k),zk,3(x) = ω(x−EA
k)
and zk,4(x) = ω(x−SA
k).
We s udy one o hese se ies, using he 2−πpe iodici y o cosine, we ha e:
zk,1(x, ) mod 2π=zk,1(x, )−zk,1(x, )
2π2π= 2πx+ −EA
k
Tcyc
−x+ −EA
k
Tcyc ∈[0,2π]
4
Then i is equal o:
zk,1(x, ) mod 2π= 2πz′
k,1−z′
k,1
Wi h z′
k,1=x+ −EA
k
Tcyc
A e ixing and compu ing each se ies o he same means:
s A
x( ) = UA +2Tcyc
4π2
nA
X
k=1
(
4π2(z′
k,1−jz′
k,1k)2
4−
2π2(z′
k,1−jz′
k,1k)
2−
4π2(z′
k,2−jz′
k,2k)2
4+
2π2(z′
k,2−jz′
k,2k)
2−
4π2(z′
k,3−jz′
k,3k)2
4+
2π2(z′
k,3−jz′
k,3k)
2+
4π2(z′
k,4−jz′
k,4k)2
4−
2π2(z′
k,4−jz′
k,4k)
2)
s A
x( ) = UA +Tcyc
2
nA
X
k=1
((z′
k,1−z′
k,1)2−z′
k,1+z′
k,1−(z′
k,2−z′
k,2)2+z′
k,2−z′
k,2−(z′
k,3+
z′
k,3)2+z′
k,3−z′
k,3+ (z′
k,4−z′
k,4)2−z′
k,4+z′
k,4)
Howe e , z′
k,1=z′
k,3+
Tcyc
and z′
k,2=z′
k,4+
Tcyc
s A
x( ) = UA +Tcyc
2
nA
X
k=1
(2 (z′
k,3−z′
k,4)
Tcyc
+z′
k,12−2z′
k,1z′
k,1+z′
k,1−z′
k,22+ 2z′
k,2z′
k,2−
z′
k,2−z′
k,32+ 2z′
k,3z′
k,3−z′
k,3+z′
k,42−2z′
k,4z′
k,4+z′
k,4)
s A
x( ) = Tcyc
2
nA
X
k=1 g(z′
k,1)−g(z′
k,2)−g(z′
k,3) + g(z′
k,4)
wi h ∀y∈R+, g(y) = ⌊y⌋2−2y⌊y⌋+⌊y⌋
5

The a ia ions o he supply unc ion wi hin a cycle a e s udied in Lemma 5., while he
a e age alue o he supply unc ion wi hin a cycle is gi en by heo em 5.
Lemma 5. (Sec ion 5.1 - Page 6.) Le k∈ {1, . . . , nA−1}, o all ∈R+, he minimum o
he unc ion x7→ s A
x( )o e (SA
k;SA
k+1]is always loca ed a x=EA
k. Likewise, he minimum
o e (SA
nA;SA
1+Tcyc]is loca ed a x=EA
nA.
P oo . Le ∈R+, we s udy a ia ions o s A
xo e he in e al [SA
k, SA
k+1[. Fo ha , we de i e
acco ding o x om he Eq. (1). The in e e sion be ween he de i a ion ope a o and each
se ies is possible due o he uni o m con e gence o each se ies and o i s de i a e:
∂s A
x( )
∂x =2
Tcyc
nA
X
k=1
∞
X
n=1
sin(nzk,2(x, ))
n+sin(nzk,1(x, ))
n+
cos(nzk,3(x))
n−cos(nzk,4(x))
n
Acco ding o he esul o ∀y∈[0,2π],
∞
X
n=1
sin(ny)
n=π−y
2. Then, using he 2−πpe iodici y
o sine, we ha e:
∂s A
x( )
∂x =2π
Tcyc
nA
X
k=1 z′
k,1−z′
k,1−z′
k,2+z′
k,2−z′
k,3+z′
k,3+z′
k,4−z′
k,4
As z′
k,1+z′
k,4=z′
k,2+z′
k,3=2x+ −EA
k−SA
k
Tcyc
, we ha e:
∂s A
x( )
∂x =2π
Tcyc
nA
X
k=1 −z′
k,1+z′
k,2+z′
k,3−z′
k,4
∂s A
x( )
∂x =X
k∈AT I
(x+ −SA
k
Tcyc −x+ −EA
k
Tcyc )
| {z }
=







1i x+ ∈AT I
0else
+x−EA
k
Tcyc −x−SA
k
Tcyc 
| {z }
=







−1i x∈AT I
0else
Then
∂s A
x( )
∂x 


≤0i x∈AT I
≥0else
We can obse e he a ia ion o he supply unc ion, wi h ixed.
6
A A
1 2
Always minimum
The a e age alue o he supply unc ion is gi en by he o mula o heo em 5.
Theo em 5. (Sec ion 5.3 - Page 7.) The a e age alue o a supply unc ion s A
xk(wi h
xk=EA
k) wi hin a cycle is equal o:
s A
xk=
nA
X
q=1
(EA
k−SA
q)2−(EA
k−EA
q)2
2Tcyc
+
nA
X
q=k+1
(EA
q−SA
q)
P oo .
s A
xk=1
Tcyc ZTcyc
0
s A
xk( ) d
=UATcyc
2+
nA
X
q=12
T2
cycω3
∞
X
n=1 sin(ωn(EA
k+Tcyc −EA
q))
n3−sin(ωn(EA
k−EA
q))
n3
−sin(ωn(EA
k+Tcyc −SA
q))
n3+sin(ωn(EA
k−SA
q))
n3
−ωTcyc cos(ωn(EA
k−EA
q))
n2+ωTcyc cos(ωn(EA
k−SA
q))
n2
Howe e ,
ωn(EA
k+Tcyc −SA
q) = ωn(EA
k−SA
q)+2πn
Then,
sin(ωn(EA
k+Tcyc −SA
q)) = sin(ωn(EA
k−SA
q))
7
Then,
s A
xk=UATcyc
2+
nA
X
q=1 2
Tcycω2
∞
X
n=1 cos(ωn(Ek−Sq))
n2−cos(ωn(Ek−Eq)
n2
EA
k∈[0, Tcyc]gi es ω(EA
k−SA
q) = 2π(EA
k−SA
q)
Tcyc
∈[−2π, 2π](same o he o he cosine wi h
EA
q).
Using he pa i y o cosine and he esul o he se ies Xcos(ny)
n2(= y2
4−πy
2+π2
6 o y∈
[0,2π]) We ha e:
nA
X
q=1
2
Tcycω2
∞
X
n=1
cos(ωn(EA
k−SA
q))
n2=
k
X
q=1 (EA
k−SA
q)2
2Tcyc
−(EA
k−SA
q)
2+
nA
X
q=k+1 (SA
q−EA
k)2
2Tcyc
−(SA
q−EA
k)
2+π2
6
=
nA
X
q=1
(EA
k−SA
q)2
2Tcyc
+
k
X
q=1
SA
q−EA
k
2−
nA
X
q=k+1
SA
q−EA
k
2+π2
6
And:
nA
X
q=1
2
Tcycω2
∞
X
n=1
cos(ωn(EA
k−EA
q))
n2=
nA
X
q=1
(EA
k−EA
q)2
2Tcyc
+
k
X
q=1
EA
q−EA
k
2−
nA
X
q=k+1
EA
q−EA
k
2+π2
6
Then,
s A
xk=
nA
X
q=1 (EA
k−SA
q)2
2Tcyc
−(EA
k−EA
q)2
2Tcyc +
k
X
q=1
SA
q−EA
q
2+
nA
X
q=k+1
EA
q−SA
q
2+UATcyc
2
Howe e , UATcyc
2=
nA
X
q=1
EA
q−SA
q
2.
Then,
s A
xk=
nA
X
q=1
(EA
k−SA
q)2−(EA
k−EA
q)2
2Tcyc
+
nA
X
q=k+1
(EA
q−SA
q)
8