# Multithreading-Based Algorithm for High-Performance Tchebichef Polynomials with Higher Orders
## 3 The Proposed Multithreaded Algorithm
Notably, the improvement factor drops to 3.19 at 256 threads, indicating that excessive threading leads to decreased performance. This stable improvement at a high number of threads is due to the fact that the computational loads are high, leading to diminishing threading overheads. This is clear

Figure 8: The computation time and speedup of the proposed algorithm for size of 2000. Figure 7: Computation time and performance gain of the proposed algorithm for size 1000.

from the improvement achieved at 256 threads, where it drops to 17.9% and 27.4% from the optimal improvement at size of 500 and 1000, respectively. At a size of 2000, the improvement in 256 threads decreases to 55.7% with respect to the maximum improvement. The results for a size of 4000 and 6000 are depicted in Figures 9 and 10. The experiment shows that the thread-scaling results exhibit a nonlinear relationship between thread count and improvement. This is characterized by a rapid increase in improvement up to 16 threads, where a plateau is reached. The improvement then continues to increase, reaching the peak at \(\sim\)20 threads, before a subsequent decline. This behavior is attributed to the interplay between parallelism and overhead, where the benefits of parallelism are initially dominant. The optimal thread count corresponds to an inflection point where the parallelism benefits are maximized and the overhead is minimized, with the maximum improvement occurring in the region between 16 and 64 threads for a size of 4000 and between 16 and 96 threads for a size of 6000. However, eventually, the benefits of parallelism give way to the increasing overhead of thread creation, synchronization, and communication, leading to diminishing returns after 64 threads for a size of 4000 and after 96 threads for a size of 6000. Figure 10: The computation time and speedup of the proposed algorithm for size of 6000. Figure 9: Computation time and performance gain of the proposed algorithm for size 4000. For a size of 8000, the results shown in Figure 11 reveal that the improvement in performance increases and reaches the optimal thread with a maximum improvement of 7.22 at 32 threads. Beyond this point, the improvement values start to decline, indicating that the overhead costs of thread creation, synchronization, and communication begin to dominate, leading to diminishing returns. The optimal number for this case occurs at thread count 16 to 96. Based on the observed results of the conducted experiments, the number of threads that achieves the maximum improvement is different for each size and does not follow a linear relation. The highest improvements are observed in a range of threads, especially in the sizes 4000 to 8000, with a very slight difference between them. For example, at size = 4000, the highest improvement was achieved in the range of 16 to 64 threads. It should be noted that the results represent the average of 10 executions to reduce the deviations; despite that, the environment conditions, namely the other tasks running in the background, have some effect on the experimental results, leading to this non-linearity. The experimental results for the sizes of 4000, 6000, and 8000 show that the improvement at 256 threads drops to only 87.4%, 89.9%, and 90.3% from the peak improvement value at a size of 4000, 6000, and 8000, respectively. The improvement through threading is dependent on the available computing resources, represented by the number of cores. Figure 12 shows the calculation improvement as a function of the number of threads for different numbers of cores, namely one, two, three, and four cores. In general, the improvement increases with an increase in the number of cores. The one-core case shows small improvement at a small number of threads for sizes 500, 1000, and 2000, and this improvement falls below 1 at higher numbers of threads, which indicates a degradation.