2021.1 Multicore Computing, Project #3 (Due : 11:59pm, May 24th)
Submission Rule
1. Create a directory {studentID#}_proj3 (example: 20123601_proj2). In the directory, create subdirectories ¡®prob1¡¯ and ¡®prob2¡¯.
2.a For problem 1, write (i)¡¯C with OpenMP¡¯ source code prob1.c, (ii)a document that reports the parallel performance of your code, and (iii) readme.txt into the directory “prob1”. The document that reports the parallel performance should contain (a) in what environment (e.g. CPU type, memory size, OS type …) the experimentation was performed, (b) tables and graphs that show the execution time (unit:milisecond) for thread number = {1,2,4,8,16}. (c) The document should also contain explanation on the results and why such results can be obtained. In readme.txt file, you
should briefly explain how to compile and execute
(i), (ii), and (iii) into the subdirectory ¡®prob1¡¯.
2.b For problem 2, write (i) a document,
ParkingSemaphore.java and insert (i) and (ii) into
3. zip the directory {studentID#}_proj3 and submit
¡ù If possible, use quad-core CPU (or CPU with more cores) rather than dual-core CPU for your experimentation, which will better show the performance gains of the parallelism.
[Problem 1] In project 1, we looked at the JAVA program that computes the number of ¡®prime numbers¡¯ between 1 and 200000. The parallel implementation of a static approach based on bad work decomposition (i.e. just dividing the entire range of the numbers into k consecutive sub-ranges, where k is the number of threads) may not give satisfactory performance because (i) higher ranges have fewer primes and (ii) larger numbers are harder (i.e. taking longer time) to test whether they are prime or not. Therefore thread workloads may become uneven and hard to predict. For better performance, we implemented dynamic load balancing approach in project 1 where each thread takes a number one by one and test whether the number is a prime number.
(i) Write ¡®C with OpenMP¡¯ code that computes the number of prime numbers between 1 and 200000. Your program should take two command line arguments: scheduling type number (1=static, 2=dynamic, 3=guided) and number of threads (1, 2, 4, 8, 16) as program input argument. Use schedule(static) , schedule(dynamic,4) , and schedule(guided,4). Your code should print the execution time as well as the number of the prime numbers between 1 and 200000.
command line execution: > a.out scheduling_type# #_of_thread
execution example> a.out 2 8 <---- this means the program use dynamic scheduling using 8 threads.
(ii) Write a document (in PDF file format) that reports the parallel performance of your code. The graph that shows the execution time when using 1,2,4,8,16 threads. There should be at least three graphs the show the result of static, dynamic, and guided scheduling policy. Your document also should mention which CPU (dualcore? or quadcore?, clock speed) was used for executing your code.
the source codes you submit. Insert the files
and (ii) ex1.java, ex2.java, ex3.java, the subdirectory ¡®prob2¡¯.
the zip file into eClass homework board.
exec time
1
2
4
8
16
static
dynamic
guided
performace (1/exec time)
1
2
4
8
16
static
dynamic
guided
[Problem 2] Visit the website http://tutorials.jenkov.com/java-util-concurrent/index.html that introduces and describes JAVA concurrency utilities: java.util.concurrent package.
1. You are supposed to study and summarize following classes that are important and useful for concurrent programming in JAVA. What you need to do in this problem is to write and submit a document (report) in PDF file format that includes:
(i)-a. Explain the interface/class BlockingQueue and ArrayBlockingQueue with your own English sentences. (DO NOT copy&paste)
(i)-b. Create and include (in your document) your own example of multithreaded JAVA code (ex1.java) that is simple and executable. Your example code should use put() and take() methods. Also, include example execution results (i.e. output) in your document.
(ii)-a. Do the things similar to (i)-a for the class ReadWriteLock.
(iii)-b. Do the things similar to (i)-b for lock(), unlock(), readLock() and writeLock() of ReadWriteLock. (ex2.java)
(iii)-a. Do the things similar to (i)-a for the class AtomicInteger.
(iii)-b. Do the things similar to (i)-b for get(), set(), getAndAdd(), and addAndGet() methods of AtomicInteger. (ex3.java)
(iv)-a. Explain the class Semaphore with your own English sentences. Your explanation should include the difference between binary semaphore and counting semaphore. (DO NOT copy&paste)
(iv)-b. Modify the original JAVA code ParkingGarageOperation.java, which we studied in lecture note 4-1 and project 2, and write a JAVA code generating the results that are equivalent to the results of the JAVA code ParkingGarageOperation.java by using Semaphore class in java.util.concurrent package. This is similar to Project 2, but the difference is that you need to do modification using Semaphore (i.e. counting semaphore class) in this project 3 instead of using ArrayBlockingQueue. The name of the JAVA code you create should be ParkingSemaphore.java.
2. Submit ex1.java, ex2.java, ex3.java, and ParkingSemaphore.java as well as the document described above.