Memory Efficient Multithreaded Incremental Segmented Sieve Algorithm: Implementation by@multithreading
Memory Efficient Multithreaded Incremental Segmented Sieve Algorithm: Implementation
by MultiThreading.Tech: #1 Publication on Concurrent ProgrammingMarch 29th, 2024
Too Long; Didn't Read
With the growing computational needs associated with prime enumeration tasks, traditional implementations of the Sieve algorithm remain a bottleneck.
This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Evan Ning, Milton Academy & [email protected];
(2) David R. Kaeli, Department of Electrical and Computer Engineering & Northeastern University [email protected].
Table of Links
- Introduction
- Sieve Optimizations
- Mathematical Optimization
- Implementation
- Results and Discussions
- Conclusions, Source Code & References
4.0 Implementation
In Figure 3, we provide a diagram of our multithreaded Sieve algorithm's execution flow when utilizing multiple threads. We show the thread structure and flow of the information. In Figure 4 we provide pseudocode for our implementation. In each iteration, the newly found prime numbers are stored in the Prime Number Data Store, which we currently store in a linked list. The primes are also stored in the Sieve Data Store, but only up to the square root of the numbe,r since we only need to sieve up to the square root of the number. This is because for any prime greater than the square root, P2 would be greater than N and there would be nothing to sieve.
L O A D I N G
. . . comments & more!
. . . comments & more!
