Using Parallel Map

Objectives

During this activity, students should be able to:

Solve a programming problem using Clojure’s parallel map function in order to obtain a better performance in a multi-core system.

This activity helps the student develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.

Activity Description

Individually or in pairs, solve the following problem. This problem is an adaptation of problem 10 Summation of primes from Project Euler.

The sum of the primes below 10 is:

2 + 3 + 5 + 7 = 17

Find the sum of all the primes below five million.

Spoiler alert: The correct answer is 838,596,693,108.

Write a Clojure function that allows you to compute this solution in parallel (with the help of Clojure’s pmap function), using a computer system with a dual-core CPU or better. The name of the function must be prime-sum and it should take as an argument the number of threads to use during the computation. Place your code on a file called parallel.clj.

You can use the following code to check if a certain number is prime:

(defn prime?
  "Returns true if n is a prime number, otherwise returns false."
  [n]
  (if (< n 2)
    false
    (loop [i 2]
       (if (<= (* i i) n)
         (if (zero? (rem n i))
           false
           (recur (inc i)))
         true))))

For examples, theses expressions:

(time (println (prime-sum 1)))
(time (println (prime-sum 2)))
(time (println (prime-sum 4)))
(time (println (prime-sum 8)))

would produce (in a system with eight logical cores) the following output at the console:

838596693108
"Elapsed time: 16667.419293 msecs"
838596693108
"Elapsed time: 10960.127025 msecs"
838596693108
"Elapsed time: 6997.414449 msecs"
838596693108
"Elapsed time: 5770.025455 msecs"

NOTE: Elapsed times in your system may vary considerably from the ones presented here.

Please consider the following when programming your solution:

You may define any number of additional auxiliary functions. Just make sure every single function contains a doc-string explaining its purpose.
Avoid using functions that create huge lists. These functions usually don't perform well when running in multiple threads. This means that when doing repetitions you might be better off using loop/recur.
Run your functions multiple times and measure how long they take to execute for different number of threads. Make sure that your solution runs faster when using two or more threads than when using only one thread.
When running the function with the number of threads equal to the number of available CPU cores, make sure that all CPU cores get used at near 100% their capacity during a certain moment, as shown in the following image of the system monitor:

Deliverables

✔ Upload Instructions

Deliver a single file called parallel.clj containing your solution. Please provide the following information:

Request PIN

IMPORTANT: The program source file must include at the top the author's personal information (name and student id) within comments. For example:

;;; ITESM CEM, October 31, 2016.
;;; Clojure Source File
;;; Activity: Using Parallel Map
;;; Authors: 
;;;          A01166611 Pepper Pots
;;;          A01160611 Anthony Stark

    .
    . (The rest of the program goes here)
    .

Due date is Monday, October 31.

Evaluation

This activity will be evaluated using the following criteria:

-10	The program doesn't contain within comments the author's personal information.
10	The program contains syntax errors.
DA	The program was plagiarized.
10-100	Depending on the quality of the solution.

Programming Languages