# Multithreading-Based Algorithm for High-Performance Tchebichef Polynomials with Higher Orders
## 3 The Proposed Multithreaded Algorithm
For more elucidation and interpretation, Algorithm 1 provides the pseudo code. ``` Require:Polynomial size \(N\) and number of threads \(T\). \(\mathcal{T}^{N}\). \(\mathcal{T}^{N}\). algorithm. Specifically, we present the performance metrics and comparative analysis of our approach against existing methods, highlighting the effectiveness of our algorithm in reducing computational time. The experimental setup consisted of a PC with an eight-core CPU equipped with 16 GB of RAM, utilizing the MS Windows runtime library for multithreading. To thoroughly investigate the impact of thread parallelism on performance, we systematically analyzed the proposed multithreaded algorithms by varying the number of threads in the range {2, 4, 8, 10, 16, 20, 24, 32, 48, 64, 96, 128, 160, 192, 200, 256}. This involves the execution of the proposed algorithm with different threads to take into account how the performance metrics vary in response to increased thread concurrency. Furthermore, we tested the algorithm's scalability by applying it to a wide range of polynomial sizes, specifically 500, 1000, 2000, 4000, 6000, and 8000, to assess its performance under varying computational loads. It should be noted that each test was repeated 10 times and the average value is reported; this reduces the deviation that may result due to the environment conditions. The evaluation metric involved in this experiment is the improvement ratio in time, i.e., the proposed algorithm execution time to the unthreaded algorithm [33]. The formula of the improvement ratio in time is

\[Improvement\ Ratio=\frac{Untthreaded\ Time}{Thread\ Time} \tag{22}\]

For a polynomials size of 500 (see Figure 6), the experiment reveals that the algorithm performs best at threads equal to 8, where a speedup improvement of \(\sim\)4.2 is achieved. However, as the thread count increases beyond 8, the improvement in speed begins to decrease, indicating diminishing returns due to increased contention for shared resources, synchronization overhead, and scheduling overhead. Moreover, for thread counts above 128, the speedup is less than 1, indicating suboptimal performance due to the indication that the threading management overhead exceeds the timing savings achieved through parallelism. To optimize the algorithm, it is recommended to use 8 threads for a polynomials size of 500. For a polynomials size of 1000 (see Figure 7), the results indicate that multithreading yields significant performance improvements, with the highest improvement factor of \(\sim\)5, which is observed between 8 and 24 threads. This shows that the algorithm is highly parallelizable and that the addition of multiple threads can effectively utilize the available processing resources. However, as the number of threads increases beyond 20, the improvement factor begins to decrease. This is due to the overhead of thread management and

Figure 6: The computation time and speedup of the proposed algorithm for size of 500.

synchronization, which becomes more pronounced at higher thread counts. Notably, the improvement factor starts to drop significantly at 128 threads and beyond, showing that the algorithm is no longer able to effectively utilize the additional processing resources. This limitation is likely caused by the hardware's inability to handle the increased thread count, or the task's inherent sequential nature, which is also evident in the results for the case where the size was 500. For a polynomials size of 2000, the multithreading performance analysis depicts a significant improvement in execution time as the number of threads increases, with a peak improvement ratio of 5.73, which is observed at 24 threads (see Figure 8). This demonstrates that the multithreading algorithm is highly parallelizable, effectively utilizing available processing resources. However, as thread count exceeds 48, the improvement factor decreases, which is due to thread management and synchronization overhead. The optimal thread count lies between 16 and 48, where the improvement factor is highest.