A comparison of threaded versus non-threaded computing on the sieve of Eratosthenes Algorithm

Performance enhancement in computers is a constant challenge for computer engineers, emanating from the constantly changing needs of consumers. Around the 1970s and 80s, computer engineers started designing computer architectures with multiple processors onboard, in order to address the performance challenge. These newer architectures provided a platform that enabled multiprocessing at affordable retail prices. This in turn created an opportunity for software developers to enhance program performance by creating software that could leverage on the underlying architecture through parallelisation to provide a performance advantage over sequential programs. This was not always achieved, however, since parallel programs present more opportunities to generate overhead, which can limit, or even deteriorate a program’s overall performance. In this study, an experimental analysis of two Sieve of Eratosthenes programs, one sequential and one parallel, was conducted in order to verify that parallelisation provided a computational advantage in the program under investigation, to establish whether a variation in the number of available processors had an effect on the overhead incurred, and lastly to investigate the mathematical nature of the overhead incurred. The study concluded that the parallel program provided a computational advantage over the sequential program for all threads computing prime numbers in the ranges greater than 10,000. The results of the study also determined that there existed a positive statistically significant relationship between the number of threads employed and the overhead incurred. In addition to this, the study also determined that overhead was mathematically quantifiable, but not in relation to the number of threads employed. Instead, it was learned that overhead is a product of the parallel program’s execution time and the fraction of efficiency lost. All in all, the study certainly highlighted one benefit of parallelisation, namely performanc