$24
Assignment 6 Solution
TheGoalgoal of this assignment is to help students understand the concepts of Java Concurrency and Multi-threaded programming.
The attached source code shows an example of a program that can sort a set of
D scription:
numbers using the top-down MergeSort1 algorithm. In the given implementation,
the program uses a single thread to sort the whole input. MergeSort is a sorting
algorithm that can be easily parallelized due its divide-and-conquer nature2. On
CPUs with multiple cores, multiple threads can speed up the sorting time, by
splitting the work.
MergeSort is a divide-and-conquer algorithm. It divides input array in two halves,
calls itself for the two halves and then merges the two sorted halves. The
is key
function is used for merging two halves. The
process that assumes that
and
merge()
are sorted and merges
the two sorted sub-arrays into one.
merge(arr, l, m, r)
arr[l..m]
arr[m+1..r]
The figure below shows how an array of size 7 is split into two halves and it continues like that until each subarray is of size one, at which point it starts merging.
https://en.wikipedia.org/wiki/Merge_sort
https://en.wikipedia.org/wiki/Merge_sort#Parallel_merge_sort
The following is a pseudocode of the MergeSort algorithm:
mergeSort(arr[], l, r)
if r l
Find the middle point to divide the array into two halves:
middle m = (l+r)/2
Call mergeSort for first half:
Call mergeSort(arr, l, m)
Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
and
The psedocode above can be
modified to allow
mergeSort(arr, m+1, r)
to run in parallel.
mergeSort(arr, l, m)
parallelMergeSort(arr[], l,
r)
if r l
if (avalableTreads <= 1)
r) // Call original non-paralel mergeSort
mergeSort(arr[], l,
else
Find the middle point to divide the array into two halves:
middle m = (l+r)/2
Call parallelMergeSort for first half in a new thread:
Call parallelMergeSort(arr, l, m) in new thread
Call parallelMergeSort for second half in a new thread:
Call parallelMergeSort(arr, m+1, r) in new thread
Wait for threads to finish
Merge the two halves sorted in previous steps:
Call merg (arr, l, m, r)
Note that the pseudocode above uses the variable avalableTreads to decide
whether to allocate a new thread or not based on the number of threads that has
been made available to the program. That means that every time a new thread is
created, the variable available
.
should be updated to reflect the number of
threads that are still
leTreads
Tasks:
1. Modify the class to convert it into a parallelized MergeSort that uses multipleMergSorterthreadsto perform the sorting task. The maximum number of threads to be used should be passed as an argument to the sorting method. Your program should not allow more than the specified maximum number of threads to run in. parallel. Call the modified class ParallelMergeSorter
2. Modify the
class provided to run some sorting simulations
using the parallelized
, to assess the possible
SortTester
speedup from using multiple threads, as opposed to a single thread. Call the
modified class
ParallelMergeSorter
. Each experiment should time the
sorting speed with different sizes of random number arrays, starting from an
ParallelSortTester
array of size 1000 and doubling the size of the array at each round, for 15
rounds (last round array size should be
). Run the experiment
with different number of threads starting from one thread and doubling the
16384000
number of threads, up to the number of CPU cores available in your system.
The number of cores available in your computer can be obtained from Java
using the following statement
Submit.your output
CopyRuntimetheoutput.getRuntime()resultsand.pastevailableProcessors();themintotextfile.
At the end of this document you can see the outputtogetherof anwithexampleyourcoderunon. my computer.
Notes:
1. For task 2 you will need to generate arrays with randomly distributed numbers (integers or doubles).
2. To make sure that your parallelized MergeSort works correctly, use the
method , of the given class which takes an array as an inputisSortedargumentand returns true orSortTesterfalse,depending on if the input array is sorted or not.
ThisLogistics:assignment can be done and submitted individually by each student.
Submit your answer in a single file (assign6_xxxxxx.zip). The xxxxxx is your TX State NetID.
Submit an electronic copy only, using the Assignments tool on the TRACS website for this class. Do NOT include executable or .class files in your submission.
Sample output of ParallelSortTester:
1 threads:
elements
=
5
ms
1000
2000
elements
=
6
ms
4000
elements
=
13
ms
8000
elements
=
26
ms
16000
elements
=
5
ms
32000
elements
=
10
ms
64000
elements
=
14
ms
128000
elements
=
23
ms
256000
elements
=
50
ms
512000
elements
=
107
ms
1024000
elements
=
245
ms
2048000
elements
=
541
ms
4096000
elements
=
1243
ms
8192000
elements
=
2848
ms
16384000
elements
=
6425
ms
2 threads:
elements
=
1
ms
1000
2000
elements
=
1
ms
4000
elements
=
1
ms
8000
elements
=
2
ms
16000
elements
=
4
ms
32000
elements
=
6
ms
64000
elements
=
7
ms
128000
elements
=
16
ms
256000
elements
=
41
ms
512000
elements
=
105
ms
1024000
elements
=
155
ms
2048000
elements
=
360
ms
4096000
elements
=
803
ms
8192000
elements
=
1647
ms
16384000
elements
=
3474
ms
4 threads:
elements
=
1
ms
1000
2000
elements
=
1
ms
4000
elements
=
1
ms
8000
elements
=
1
ms
16000
elements
=
3
ms
32000
elements
=
6
ms
64000
elements
=
66
ms
128000
elements
=
12
ms
256000
elements
=
33
ms
512000
elements
=
54
ms
1024000
elements
=
131
ms
2048000
elements
=
270
ms
4096000
elements
=
690
ms
8192000
elements
=
1119
ms
16384000
elements
=
3014
ms
8 threads:
elements
=
1
ms
1000
2000
elements
=
1
ms
4000
elements
=
64
ms
8000
elements
=
1
ms
16000
elements
=
2
ms
32000
elements
=
3
ms
64000
elements
=
7
ms
128000
elements
=
18
ms
256000
elements
=
22
ms
512000
elements
=
43
ms
1024000
elements
=
104
ms
2048000
elements
=
250
ms
4096000
elements
=
537
ms
8192000
elements
=
1054
ms
16384000
elements
=
2115
ms
