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.

• Avoid using functions that create huge lists. These functions usually don’t perform well when running in multiple threads.

• When doing extensive repetitions it might be a good idea to use loop/recur instead of using explicit recursion or even the sequence API.

• 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 at least a certain moment, as shown in the following image of the system monitor:

  

Deliverables

The program source file must include at the top the authors’ personal information (name and student id) within comments. For example:

;----------------------------------------------------------
; Activity: Using Parallel Map
; Date: October 26, 2017.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------

Also, each function should include a documentation string (docstring) with a brief description of its behavior. For example:

(defn max2
  "Returns the largest of the two numbers x and y."
  [x y]
  (if (> x y) x y))

Only one team member needs to upload the file.

Due date is Thursday, October 26.

Evaluation

This activity will be evaluated using the following criteria:

-10	The program doesn't contain within comments the author's personal information.
-30	A docstring is missing in one or more functions.
10	The program contains syntax errors.
1	The program was plagiarized in whole or in part.
100	The problem was solved correctly.