代写CEG5201 Hardware Technologies, Principles, & Platforms (Semester I, AY2024/2025)代做Python编程

CEG5201 Hardware Technologies, Principles, & Platforms

(Semester I, AY2024/2025)

CA-2 Statement

I. Objective

In this group assignment, each member will focus on benchmarking one of the following sorting algorithms—Merge Sort, Bucket Sort, Quicksort, or Odd-Even Transposition Sort— using both sequential and multiprocessing methods. The objective is to compare the performance of these algorithms across different implementations.

To complete the assignment, all group members should familiarize themselves with the Python multiprocessingpackage using the following resources:

•    Python multiprocessing tutorial:https://www.datacamp.com/tutorial/python- multiprocessing-tutorial

•    The pool class -https://superfastpython.com/multiprocessing-pool-python/

•    Multiprocessing pool example -https://superfastpython.com/multiprocessing-pool- example/

•    Threadpool vs. pool class differences -https://superfastpython.com/threadpool-vs-pool- in-python

Feel free to explore additional learning materials and share useful links by posting on the Canvas Discussion to benefit your classmate

II. Project Overview

In this project, your team will implement four sorting algorithms shown in Table II. Each team will select one of the sorting algorithms and implement it in both sequential and multiprocessing modes. Furthermore, in addition to individual tasks, the project includes joint tasks as detailed in Table I.

•    Individual tasks are highlighted as blue.

•    Joint tasks are highlighted as yellow.

Table I. Overview of the tasks

Task ID	Task description
O	Getting started
A	Unsorted array generation
Bn	Sequential implementation
cn	Multiprocessing implementation
Dn	Determining the ultimate speed-up
E	Comparison of the algorithms

For tasks B, C, and D, each team member will work on one algorithm. The algorithm assigned to each member is determined using the following formula:

n = (JroupID + memberID)% 4 + 1

Where % shows the modulo operation and the algorithm corresponding to  n  is listed in Table II.

Table II. List of the algorithms used

S/N (n)             Algorithm

1                      Merge sort

2                      Bucket sort

3                      Quicksort

4                      Odd-even transposition sort

Refer to Appendix A for more details on each algorithm.

III. Task description

[O] Getting started

As a team, first fix the hardware platform. that you are going to use – multi-core CPU / GPU before doing individual coding.

[A] Unsorted Array Generation

Generate 8 unsorted array instances, denoted as  Ai   where  i  ∈ [0, 1, … 7]. The length denoted by  Ni   of each array instance  Ai    is chosen from the  set  {64,  128, 256, 512,  1024, 2048, 4096, 8192}. Note that the value of each element  Ai [j], should be between 0 and 255 (random integers only). Next, generate 10 groups of such list of arrays  Gj ,  j  ∈ [0, 1, … 9]. All the team members need to use the same set of  G  for their subsequent tasks.

[Bn ] Sequential Processing

For [Bn1] follow these instructions:

•    Sort all 8 arrays in group  Go    sequentially.

•    Record the time taken for each array  Ai    and the cumulative total time. This will give you the sequential processing time for the group  G0 .

•    Present your results in Table  Bn1    as shown below.

•    Put the table in your report exactly as it appears.

Table  Bn1 : Processing time of  G0   under sequential implementation

For [Bn2] follow these instructions:

•    Repeat the above processes for all the 10 groups. This is the sequential processing time of all groups

•    Present the results obtained in Table  Bn2    shown below. Please put the table in your report exactly as it appears.

Table  Bn2 : Processing time of all groups under sequential implementation

[cn ] Multiprocessing

Identify the bottleneck in the sequential processing and try to accelerate it using multiple processes.

For [cn1 ] follow these instructions:

•    Record  the  time it takes to complete the processing of  Go    by varying the number of processes.

•    Present the obtained results in Table  cn1    shown below. Note, the columns with number of processes  ≥   8, are optional for you to fill.

•    Put the table in your report exactly as it appears.

Table  cn1 : Processing time of  Go    under multiprocessing implementation

For [cn2 ] follow these instructions:

•    Record the time it takes to complete the processing of all groups by varying the number of processes.

•    Present the obtained results in Table  cn2    shown below. Note the columns with number of processes  ≥   8, are optional for you to fill.

•    Put the table in your report exactly as it appears.

Table  cn2 : Processing time of all groups under multiprocessing implementation

[Dn]  Determine the speed-up

For [Dn1 ] follow these instructions:

•    Determine the  speed-up of processing  Go    under multiprocessing implementation (cn1) versus sequential implementation (Bn1).

For [Dn2 ] follow these instructions:

•    Determine the speed-up of processing all groups under multiprocessing implementation (cn2) versus sequential implementation (Bn2).

•    Plot  the  speed-up  curves  w.r.t the number of processes and the number of workloads (pairs/groups) and write a detailed discussion.

[E] Compare the algorithms

Combine the results from all team members and provide a detailed comparison of the different algorithms in your report.

IV. Submission

What to submit?

Each group should upload only one compressed file (.zip) to Canvas, including three types of files:

1.    The report (.pdf)

2.    The source code file(s) (.py)

3.    The README text file (.txt)

File Naming Instructions

Follow the rules below to name your files:

•    For the compressed file:

   CA2_(Group ID)_(Matriculation number of all team members separated by an underscore).zip

   Example: CA2_ 12_A0213331Z_A0010101Y_A0340127X_A0711001X.zip

•    For the report file:

   CA2_Report_(Group ID)_(Matriculation number of all team members separated by an underscore).pdf

   Example:CA2_Report_ 12_A0213331Z_A0010101Y_A0340127X_A0711001X. pdf

Report Format

•    Formatting Guidelines:

Use single-column format with the main body text in Times New Roman, 12pt font.

•    Page Limit:

Maximum of 12 pages, excluding the first and last pages.

•    First Page of your report:

Title + Full Names + Matriculation Numbers (this page is not counted in the report page limit mentioned below).

•    Last Page of your report:

Title: Coding effort (this page is not counted in the report page limit mentioned below). Please see the next subsection on what to write here.

•    Code file(s):

Please put useful comments generously throughout in your code file for readers to understand the gist of computation taking place.

Coding effort

Attach ONE separate page titled “Coding Effort - <your name>” at the end of report. Describe how much your coding effort is (quantify in %). If you had either directly or partly used any CODE(s) from github or from any other site, list those sites and point us exactly where you obtained those codes. If you have used others’ codes and did not list or cite the reference directly no marks will be awarded. If you have generated your own data, describe how you generated your data needed for your experiments. If you are using any tools for your experiments (not for data), then point to them. These also can be part of your references listing after conclusions.

Readme file

This file must contain clear instructions to facilitate running your program and use of data and parameters. If you are using any specific packages, list them and also indicate the URLs from where the readers can download. If you are using any specific DATA from any URL, indicate the URL. If the readers need to set any input parameters (hard coded way) explicitly state that requirement. Do NOT ASSUME anything and omit details. Step-by-step instructions will be very useful.