Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers

Soonwook Hwang; Kyusik Chung; Dongseung Kim

doi:10.1109/CIT.2007.4385097

Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers

Soonwook Hwang, Kyusik Chung, Dongseung Kim

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	CIT 2007
Subtitle of host publication	7th IEEE International Conference on Computer and Information Technology
Pages	295-299
Number of pages	5
DOIs	https://doi.org/10.1109/CIT.2007.4385097
Publication status	Published - 2007
Event	CIT 2007: 7th IEEE International Conference on Computer and Information Technology - Aizu-Wakamatsu, Fukushima, Japan Duration: 2007 Oct 16 → 2007 Oct 19

Publication series

Name	CIT 2007: 7th IEEE International Conference on Computer and Information Technology

Other

Other	CIT 2007: 7th IEEE International Conference on Computer and Information Technology
Country/Territory	Japan
City	Aizu-Wakamatsu, Fukushima
Period	07/10/16 → 07/10/19

Keywords

Cluster computer
Load balancing
MPI
Prime number
Sieve of Eratosthenes

ASJC Scopus subject areas

Computer Science Applications
Information Systems
Software
General Mathematics

Access to Document

10.1109/CIT.2007.4385097

Cite this

Hwang, S., Chung, K., & Kim, D. (2007). Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers. In CIT 2007: 7th IEEE International Conference on Computer and Information Technology (pp. 295-299). Article 4385097 (CIT 2007: 7th IEEE International Conference on Computer and Information Technology). https://doi.org/10.1109/CIT.2007.4385097

Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers. / Hwang, Soonwook; Chung, Kyusik; Kim, Dongseung.
CIT 2007: 7th IEEE International Conference on Computer and Information Technology. 2007. p. 295-299 4385097 (CIT 2007: 7th IEEE International Conference on Computer and Information Technology).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hwang, S, Chung, K & Kim, D 2007, Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers. in CIT 2007: 7th IEEE International Conference on Computer and Information Technology., 4385097, CIT 2007: 7th IEEE International Conference on Computer and Information Technology, pp. 295-299, CIT 2007: 7th IEEE International Conference on Computer and Information Technology, Aizu-Wakamatsu, Fukushima, Japan, 07/10/16. https://doi.org/10.1109/CIT.2007.4385097

@inproceedings{fd6ab56e34d94093a5bdc55f2621cb05,

title = "Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers",

abstract = "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.",

keywords = "Cluster computer, Load balancing, MPI, Prime number, Sieve of Eratosthenes",

author = "Soonwook Hwang and Kyusik Chung and Dongseung Kim",

year = "2007",

doi = "10.1109/CIT.2007.4385097",

language = "English",

isbn = "0769529836",

series = "CIT 2007: 7th IEEE International Conference on Computer and Information Technology",

pages = "295--299",

booktitle = "CIT 2007",

note = "CIT 2007: 7th IEEE International Conference on Computer and Information Technology ; Conference date: 16-10-2007 Through 19-10-2007",

}

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 -

Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this