/mc970-t1-omp-for-prime

Primary LanguageC

OpenMP Parallel For: Primes

In this assignment you should parallelize a function that count how many primes are below a certain threshold. See Wikipedia for an explanation on prime numbers.

Input

This application reads a number N from stdin and counts how many prime numbers are below 2^N.

Output

The program will print a table where the first column is an integer m and the second column is the number of primes below m.

Tasks & Rules

You should do the following tasks:

  • Understand the serial code in src/prime-serial.c
  • Parallelize the code using OpenMP in the file src/prime-parallel.c
  • Run both versions and compare them. Did you get any speedup?

You must not change the serial implementation, only the parallel one.

Grading

Your assignment will be evaluated in terms of:

  • Correctness: your program returns the correct result;
  • Performance: your program runs faster than the serial implementation.

In order to test your solution, you can use one of the inputs available inside the tests/ directory. Whenever you push your changes to GitHub, the Continuous Integration (CI) system will compile, run and execute your program using those tests. Your grade will not be computed from the CI runs because other processes may be running in the server, thus interfering with runtime and speedup.

Your grade will be computed using an automated routine restricted to the instructors and TAs. This routine will be run after the assignment deadline, using the latest commit push to the branch master before the deadline. Your code will be ensured to run in an environment with no competition for resources.

Note: Both the CI and automatic grading routine expect your the output of your program to be formatted correctly. For that reason, you should not add printfs or any other function that writes to stdout, otherwise your assignment will be considered incorrect.

Note: Tampering with the serial implementation or the tests is considered cheating and will result in disqualification of the assignment.

Compiling & Running

After you have accepted this assignment on the course's GitHub Classroom page, clone it to your machine. First you have to generate the build system using CMake. Make sure you have it installed! You will also need an OpenMP compatible compiler. If you use Linux, you are good to go. For MacOS users, you can install the OpenMP libraries via Homebrew with the following command:

# Only for MacOS users
brew install libomp

Then, run the following commands:

# Where the build will live
mkdir build && cd build

# Generate the Makefiles
cmake -DCMAKE_BUILD_TYPE=Release ..

Having done that, still inside the build directory, run make to compile everything. Finally, from the root directory of the repo you can execute the serial and parallel versions like so:

build/serial tests/1.in
build/parallel tests/2.in

If you have any doubts or run into problems, please contact the TAs. Happy coding! 😄 ⌨️

Contribute

Found a typo? Something is missing or broken? Have ideas for improvement? The instructor and the TAs would love to hear from you!

About

This repository is one of the assignments handed out to the students in course "MO644/MC970 - Introduction to Parallel Programming" offered by the Institute of Computing at Unicamp.