## 5 Performance Analysis
### TSAFP Algorithm Testing  
The LCS algorithm was implemented and first tested in comparison to direct hyperperiod simulation. In order to keep the value of \(h\) tractable task periods were limited to the interval [1, 100] ms, and the number of tasks restricted to 10; this ensured each individual test could be performed in less than 20 minutes on the target hardware. In total 1,000 different representative task sets were generated as follows; periods were randomly generated, and assigned to tasks. Following this, (3) was used to determine the tick interval, and (17) applied to calculate _p'_. Offsets were then randomly assigned within this bound. Task computation times were then assigned in the interval [0.1 _tTick_, _tTick_] us. The resulting task sets were then used as input to both LCS and a hyperperiod simulation algorithm, and the resulting computation times for each are shown in Figures 9 and 10. A summary of the results is given in Table 1, with units of seconds.  
Following this, a number of tests were performed to gauge the increase in complexity of the proposed algorithm as the number of tasks in the input set was increased. The restriction on task  
Figure 8: ITLB algorithm, in pseudo-code.  
periods was lifted for these tests, and task periods were generated in the interval [1, 1,000] ms. Starting from \(n=5\), the number of tasks was increased in steps of 5 up to and including \(n=30\) tasks. At each step, 100,000 task sets were randomly generated and used as input to LCS. The results of these tests are given in Table 2, with units of seconds, and are shown graphically in Figure 11.  
It can be seen from Table 1 that in all cases, the LCS method was significantly faster than basic hyperperiod simulation for solving TSASP. As can be seen from the results, LCS is extremely robust in terms of the task parameters; in comparison, hyperperiod simulation sees huge fluctuations in computation time as the task parameters vary, in some cases taking in excess of 16 minutes to solve these vastly restricted instances. Considering now the results of Table 2, it can be seen that as the number of tasks increases, the worst case computation time reflects the exponential in \(n\); however,  
\begin{table}
\begin{tabular}{c c c} \hline  & **LCS** & **Hyperperiod** \\ \hline Min & 0.0000023 & 0.0000218 \\ Max & 0.0000385 & 1,007.2945080 \\ Ave & 0.0000066 & 188.4035393 \\ \hline \end{tabular}
\end{table}
Table 1: Comparative results of computation times.  
Figure 10: LCS algorithm performance.  
Figure 9: Hyperperiod simulation performance.  
even given this complexity rise the worst case recorded for \(n=30\) was under 400 \(\upmu s\). It should be noted that reduced hyperperiod simulation (as outlined in Section 4.1) was employed on average less than 1% of the time. Despite this exponential rise, the LCS algorithm in its current formulation is still extremely efficient at this level, and gives a huge gain in efficiency over basic hyperperiod simulation. For example, with \(n=30\) and periods in the range 1-1,000 ms, out of 100 randomly generated instances, not a single one could be solved in under 1 hrs computation time. Extrapolating the results from Table 1--using the calculated length of \(h\)--indicated that most would take around \(10^{70}\) Centuries to solve.