At Programming Homework Tutors, we believe in providing our students with practical, real-world examples of how to apply the concepts they learn in class. That’s why we’ve developed a variety of sample projects to help you see how our courses can be used to create impactful solutions in your field of study.

Description

The project will be an exercise in concurrent programming and will require you to parallelise the computation of sum of Euler totient computations over a range of integer values. The Euler totient function computes the number of integers that are coprime (⊥) to a given integer n. The totient function is defined as follows:

φ(n) = |{m ∈ N|m < n ∧ m⊥n}|

Two numbers m and n are said to be relativey prime, if the only integer number that divides them both is 1. It is therefore necessary to establish that their greatest

common divisor (gcd) is 1, i.e. m⊥n = gcd(m,n) = 1. The program should thus compute.

The Java code in listing 1 is a direct sequential implementation of the above specification and is provided as a starting point for your concurrent implementation. So, if the program is executed as follows: TotientRange _{1 100} , its output should be 3044.

         Instructions

In groups of at most 3 (you are responsible for forming your own group), provide a concurrent implementation of the code in listing 1 using threads in Java. Note that you are not allowed to change the sum of Euler totient algorithm such that it becomes more efficient. A deliberately inefficient sequential implementation has been provided so that any speed up via the employment of threads is not imperceptible. You will be required to study the implementation of the algorithm and identify which part(s) can be executed concurrently such that the overall result is correct but a faster execution is realized.

Bonus points will be awarded for any implementation that tries to optimize how data is shared among multiple threads for a faster runtime.

To establish a baseline of performance, you are required to execute the sequential implementation using the following inputs:

• Sum of totients between 1 and 10000
• Sum of totients between 1 and 20000
• Sum of totients between 1 and 50000

For larger ranges the runtime of the sequential implementation will increase; depending on the speed of your CPU, execution may take several minutes.

Listing 1: Implementation of Euler Specification

 Deliverables

You are required to submit a report (along with your source code) in the structure outlined below. If your report does not adhere to the specified structure and/or omits any sections there will be a deduction of marks. The report and accompanying source code should be uploaded as a single zipped archive.

        3.1    Report Structure

Introduction

Provide a summary of the requirements as well as a description of the environment in which the execution was performed. It would be worthy to mention details of the CPU, RAM and Operating System. [10 marks]

Sequential Implementation Measurements

Execute the sequential implementation with the ranges specified in Section 2. Explain what is observed from the executions and have a discussion of ways in which threads might be applied to improve performance. It is recommended to provide a simple graph of runtimes for the different inputs. [10 marks]

Concurrent Implementation Measurements

This section of the report should contain the runtime measurements of the concurrent implementation for the totient ranges specified in Section 2. There should be four graphs plotting the execution times of your concurrent implementation using 8, 16, 32 and 64 threads. [25 marks]

Sequential vs Concurrent Execution

This section should provide an evaluation of each implementation in terms of the speed of execution. You should discuss any difficulties encountered in constructing your concurrent implementation. A graph of the sequential vs concurrent implementation must be provided. [30 marks] Total [75 marks].

           Measurement Advice

It is advised for all of your measurements to be done on the same computer. Otherwise variability in the performance of different machines can pollute any observed difference in runtime. You should also be cautious of the number of threads launched, if too many threads are launched simultaneously it is possible for your machine to become soft locked.

Disclaimer

The sample projects provided on our website are intended to be used as a guide and reference for educational purposes only. While we have made every effort to ensure that the projects are accurate and up-to-date, we do not guarantee their accuracy or completeness. The projects should be used at your own discretion, and we are not responsible for any loss or damage that may result from their use.
At Programming Homework Tutors, we are dedicated to helping students and educators achieve their goals by providing them with the resources they need to succeed. Our website offers a variety of tools and resources that can help you with the project mentioned above.
Whether you need help with research, project management, or technical support, our team of experts is here to assist you every step of the way. We offer online courses, tutorials, and community forums where you can connect with other learners and get the support you need to succeed.
If you’re looking to take your skills to the next level and make an impact in your field, we invite you to explore our website and see how we can help you achieve your goals.