TY - GEN
T1 - Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers
AU - Hwang, Soonwook
AU - Chung, Kyusik
AU - Kim, Dongseung
PY - 2007
Y1 - 2007
N2 - Algorithms of finding prime numbers up to some integer N by Sieve of Eratosthenes are simple and fast. However, even with the time complexity no greater than O(N In In N), it may take weeks or even years of CPU time if N is large like over 15 decimal digits. No known shortcut was reported yet. We develop efficient parallel algorithms to balance the workload of each computer, and to extend memory limit with disk storage to accommodate Giga-bytes of data. Our experiments show that a complete set of up to 14-digit prime numbers can be found in a week of computing time (CPU time) using our 8 1.6GHz Pentium-4 PCs with Linux and MPI library. Also, by sieve of Eratosthenes, we think it is very unlikely that we can compute all primes up to 20 digits even using the fastest computers in the world.
AB - Algorithms of finding prime numbers up to some integer N by Sieve of Eratosthenes are simple and fast. However, even with the time complexity no greater than O(N In In N), it may take weeks or even years of CPU time if N is large like over 15 decimal digits. No known shortcut was reported yet. We develop efficient parallel algorithms to balance the workload of each computer, and to extend memory limit with disk storage to accommodate Giga-bytes of data. Our experiments show that a complete set of up to 14-digit prime numbers can be found in a week of computing time (CPU time) using our 8 1.6GHz Pentium-4 PCs with Linux and MPI library. Also, by sieve of Eratosthenes, we think it is very unlikely that we can compute all primes up to 20 digits even using the fastest computers in the world.
KW - Cluster computer
KW - Load balancing
KW - MPI
KW - Prime number
KW - Sieve of Eratosthenes
UR - http://www.scopus.com/inward/record.url?scp=38049009953&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38049009953&partnerID=8YFLogxK
U2 - 10.1109/CIT.2007.4385097
DO - 10.1109/CIT.2007.4385097
M3 - Conference contribution
AN - SCOPUS:38049009953
SN - 0769529836
SN - 9780769529837
T3 - CIT 2007: 7th IEEE International Conference on Computer and Information Technology
SP - 295
EP - 299
BT - CIT 2007
T2 - CIT 2007: 7th IEEE International Conference on Computer and Information Technology
Y2 - 16 October 2007 through 19 October 2007
ER -