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)

Supplementary material of Response Times Analysis in a Two-Level Hierarchical System with Static Multi-Access This is the document of detailed proofs of our article: "Response Times Analysis in a TwoLevel Hierarchical System with Static Multi-Access". For the remainder, a two-level hierarchical system is composed of two types of scheduling: •The scheduling of partitions; •A scheduling of task for each partition. A computational module is modeled as a 2-level hierarchical uniprocessor system. At the processor level, execution time is shared among mpartitions (m∈N∗) denoted A1, . . . , Am. Their scheduling is statically defined off-line by a periodic cycle of length Tcyc, which is repeated indefinitely. The partition model is static [?]. We study a multi-access partition model, where a partition can be granted access to the processor multiple times per cycle. We denote by Athis partition and by nA(with nA∈N∗and nA>1) the number of Access Time Intervals (ATIs). The kth ATI (with k∈ {1, . . . , nA}) is a non-null time interval [SA k, EA k]where SA kand EA kare respectively the start and end times within the cycle. Intervals are two by two disjoints and comprised into the cycle, then: 0≤SA 1< EA 1< SA 2< EA 2<· · · < SA nA< EA nA≤Tcyc The utilization factor of the k-th ATI, denoted UA k, is the ratio of time allowed to the ATI during a cycle. The utilization factor of partition A, denoted UA, is then the sum of the utilization of its ATI. UA= nA X k=1 UA kwith: UA k=EA k−SA k Tcyc We assume the study of an unique partition A. We want investigate the time allocated to it within an interval time of type [x, x +t](x, t)∈(R+)2. This supply time is modeled by the called function supply function. 1 (a) A A A A t partition scheduling (b) 0 t afA(t)1 (c) 0 t afA 1(t)1 SA 1EA 1SA 1 (d) 0 t afA 2(t)1 0SA 2EA 2SA 2 Tcyc 2Tcyc Figure 1: Periodic rectangular functions of a 2-access partition The supply function must be expressed for any intervals of the form [x,x+t] (Th.1). We propose a new formulation, which relies on the integration over the interval [x,x+t] of the Fourier series decomposition of the activation function afA(Lemma 1.). Lemma 1. (Section 4.1 - Page 4.) Considering a multi-access partition A, the Fourier series decomposition of the k-th access function fA kexists, and is equal to: afA k(t) = a0+ ∞ X n=1 (ancos(ωnθ)+bnsin(ωnθ)) with: ω=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)]. Proof. The function afA kis periodic according to Tand piecewise smooth, then it is decomposable into Fourier Series by afA k(t) = a0+ ∞ X n=1 (ancos(ωnt) + bnsin(ωnt)). Computing its coefficients: By definition, a0(afA k) = 1 Tcyc ZTcyc 0 afA k(u) du an(afA k) = 2 Tcyc ZTcyc 0 afA k(u) cos(ωnu) du bn(afA k) = 2 Tcyc ZTcyc 0 afA k(u) sin(ωnu) du 2 Then, a0(afA k) = 1 Tcyc ZEA k SA k afA k(u) du=1 Tcyc (EA k−SA k) = UA an(afA k) = 2 Tcyc ZEA k SA k cos(ωnu) du=2 ωnTcyc (sin(ωnEA k)−sin(ωnSA k)) bn(afA k) = 2 Tcyc ZEA k SA k sin(ωnu) du=2 ωnTcyc (cos(ωnSA k)−cos(ωnEA k)) Theorem 1. (Section 4.2 - Page 4.) Let be x∈[0, Tcyc), an explicit expression of the releasetime specific supply function sfA xis: sfA x(t) = Tcyc 2 nA X k=1 gx+t−EA k Tcyc −gx−EA k Tcyc  −gx+t−SA k Tcyc +gx−SA k Tcyc  with ∀y∈R+, g(y) = ⌊y⌋2−2y⌊y⌋+⌊y⌋ Proof. We have sfA x(t) = Zx+t x nA X k=1 afA k(u) du=Zx+t x nA X k=1 a0+ ∞ X n=1 (ancos(ωnu) + bnsin(ωnu))!du as the cumulative time in the interval [x,x+t]. TERM-BY-TERM INTEGRATION : If f is periodic, and in any finite interval is continuous except for a finite number of finite discontinuities, then, the Fourier series development no need to converge, the integral of f between any two finite limits may be obtained by integrating this series term-by-term between these limits. As afA kfunctions are piecewise continuous on the interval [x,x+t], we may use the term-byterm integration of Fourier series. Then: sfA x(t) = nA X k=1 Zx+t x a0du+ ∞ X n=1 Zx+t x (ancos(ωnu) + bnsin(ωnu)) du! 3 sfA x(t) = nA X k=1 a0Zx+t x du+ ∞ X n=1 anZx+t x cos(ωnu)du+bnZx+t x sin(ωnu) du! sfA x(t) = UAt+ nA X k=1 2 Tcycω2 ∞ X n=1 1 n2( sin(ωn(x+t)) sin(ωnEA k) | {z } 1 −sin(ωnx) sin(ωnEA k) | {z } 2 −sin(ωn(x+t)) sin(ωnSA k) | {z } 3 + sin(ωnx) sin(ωnSA k) | {z } 4 −cos(ωn(x+t)) cos(ωnSA k) | {z } 3 + cos(ωnx) cos(ωnSA k) | {z } 4 + cos(ωn(x+t)) cos(ωnEA k) | {z } 1 −cos(ωnx) cos(ωnEA k) | {z } 2 By coupling two integrations, we recognize 4 formulas of type: cos(a−b) = cos(a) cos(b) + sin(a) sin(b) Then, sfA x(t) = UAt+ nA X k=1 2 Tcycω2 ∞ X n=1 1 n2( cos(ωn(x+t−EA k)) −cos(ωn(x−EA k)) −cos(ωn(x+t−SA k)) + cos(ωn(x−SA k)) We have now four series of type cos(ny) n2. The result of this series is known as: ∀y∈[0,2π], ∞ X n=1 cos(ny) n2=y2 4−πy 2+π2 6 Then sfA x(t) = UAt+C nA X k=1 ∞ X n=1 cos(nzk,1(x, t)) n2−cos(nzk,2(x, t)) n2+ cos(nzk,4(x)) n2−cos(nzk,3(x)) n2 (1) with C=2 Tcycω2,zk,1(x, t) = ω(x+t−EA k),zk,2(x, t) = ω(x+t−SA k),zk,3(x) = ω(x−EA k) and zk,4(x) = ω(x−SA k). We study one of these series, using the 2−πperiodicity of cosine, we have: zk,1(x, t) mod 2π=zk,1(x, t)−zk,1(x, t) 2π2π= 2πx+t−EA k Tcyc −x+t−EA k Tcyc ∈[0,2π] 4 Then it is equal to: zk,1(x, t) mod 2π= 2πz′ k,1−z′ k,1 With z′ k,1=x+t−EA k Tcyc After fixing and computing each series of the same means: sfA x(t) = UAt+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) sfA x(t) = UAt+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) However, z′ k,1=z′ k,3+t Tcyc and z′ k,2=z′ k,4+t Tcyc sfA x(t) = UAt+Tcyc 2 nA X k=1 (2t(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) sfA x(t) = Tcyc 2 nA X k=1 g(z′ k,1)−g(z′ k,2)−g(z′ k,3) + g(z′ k,4) with ∀y∈R+, g(y) = ⌊y⌋2−2y⌊y⌋+⌊y⌋ 5 The variations of the supply function within a cycle are studied in Lemma 5., while the average value of the supply function within a cycle is given by theorem 5. Lemma 5. (Section 5.1 - Page 6.) Let k∈ {1, . . . , nA−1}, for all t∈R+, the minimum of the function x7→ sfA x(t)over (SA k;SA k+1]is always located at x=EA k. Likewise, the minimum over (SA nA;SA 1+Tcyc]is located at x=EA nA. Proof. Let t∈R+, we study variations of sfA xovert the interval [SA k, SA k+1[. For that, we derive according to x from the Eq. (1). The interversion between the derivation operator and each series is possible due to the uniform convergence of each series and of its derivate: ∂sfA x(t) ∂x =2 Tcyc nA X k=1 ∞ X n=1 sin(nzk,2(x, t)) n+sin(nzk,1(x, t)) n+ cos(nzk,3(x)) n−cos(nzk,4(x)) n According to the result of ∀y∈[0,2π], ∞ X n=1 sin(ny) n=π−y 2. Then, using the 2−πperiodicity of sine, we have: ∂sfA x(t) ∂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+t−EA k−SA k Tcyc , we have: ∂sfA x(t) ∂x =2π Tcyc nA X k=1 −z′ k,1+z′ k,2+z′ k,3−z′ k,4 ∂sfA x(t) ∂x =X k∈AT I (x+t−SA k Tcyc −x+t−EA k Tcyc ) | {z } =        1if x+t∈AT I 0else +x−EA k Tcyc −x−SA k Tcyc  | {z } =        −1if x∈AT I 0else Then ∂sfA x(t) ∂x    ≤0if x∈AT I ≥0else We can observe the variation of the supply function, with tfixed. 6 A A 1 2 Always minimum The average value of the supply function is given by the formula of theorem 5. Theorem 5. (Section 5.3 - Page 7.) The average value of a supply function sfA xk(with xk=EA k) within a cycle is equal to: sfA 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) Proof. sfA xk=1 Tcyc ZTcyc 0 sfA xk(t) dt =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 However, ω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, sfA 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]gives ω(EA k−SA q) = 2π(EA k−SA q) Tcyc ∈[−2π, 2π](same for the other cosine with EA q). Using the parity of cosine and the result of the series Xcos(ny) n2(= y2 4−πy 2+π2 6for y∈ [0,2π]) We have: 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, sfA 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 However, UATcyc 2= nA X q=1 EA q−SA q 2. Then, sfA 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