Parallelization: Sieve of Eratosthenes
By Aaron Weeden
Shodor, Durham, North Carolina
This module presents the Sieve of Eratosthenes, a method for finding the prime numbers below a certain integer. One can model the sieve for small integers by hand. For bigger integers, it becomes necessary to use a coded implementation. This code can be either serial (sequential) or parallel. Students will explore the various forms of parallelism (shared memory, distributed memory, and hybrid) as well as the scaling of the algorithm on multiple cores in its various forms, observing the relationship between run time of the program and number of cores devoted to the program. An assessment rubric, two exercises, and two student project ideas allow the student to consolidate her/his understanding of the material presented in the module. The documents can be downloaded below:
Resources:
Module Document (.docx) : The module document in .docx format.
Module Document (.pdf) : The module document in .pdf format.
Exercise 1 (.docx) : Student exercise 1 in .docx format.
Exercise 1 (.pdf) : Student exercise 1 in .pdf format.
Exercise 2 (.docx) : Student exercise 2 in .docx format.
Exercise 2 (.pdf) : Student exercise 2 in .pdf format.
Assessment Rubric (.docx) : Assessment rubric in .docx format.
Assessment Rubric (.pdf) : Assessment rubric in .pdf format.
sieve.zip : zip file with coded implementations of the parallel algorithm.