1. Modify the MergeSorter class to convert it into a parallelized MergeSort that
ID: 3572126 • Letter: 1
Question
1. Modify the MergeSorter class to convert it into a parallelized MergeSort that uses multiple threads to 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 create more threads than the allowed maximum. Call the modified class ParallelMergeSorter.
2. Modify the SortTester class provided to run some simulations using the parallelized ParallelMergeSorter,to assess the possible speedup from using multiple threads, as opposed to a single thread. Call the modified class ParallellSortTester. Each experiment should time the sorting speed wiht different sizes of random number arryas, starting from an array of size 1000 and doubling the size of the arrya at each round, for 15 rounds (last round arrya size should be 16384000). Run the experiment wiht different number of threads starting form one thread and doubling the number of threads, up to the number of CPU cores available in your system. The number cores available in your computer can be obtained from Java using the following statement:
Runtime.getRuntime().availableProcessors();
Copy the output results and paste them into a text file. Submit your output together with your code. Here are examples of output from my computer:
1 threads:
1000 elements => 5 ms
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 => 0 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
MergeSorter code given:
import java.util.*;
public class MergeSorter{
public static <E> void sort(E[] a, Comparator<? super E> comp){
mergeSort(a, 0, a.length - 1, comp);
}
private static <E> void mergeSort(E[] a, int from, int to, Comparator<? super E> comp) {
if (from == to) {
return;
}
int mid = (from + to) / 2;
// Sort the first and the second half
mergeSort(a, from, mid, comp);
mergeSort(a, mid + 1, to, comp);
merge(a, from, mid, to, comp);
}
@SuppressWarnings("unchecked")
private static <E> void merge(E[] a, int from, int mid, int to, Comparator <? super E> comp) {
int n = to - from + 1;
Object[] b = new Object[n];
int i1 = from;
int i2 = mid + 1;
int j = 0;
while (i1 <= mid && i2 <= to) {
if (comp.compare(a[i1], a[i2]) < 0) {
b[j] = a[i1];
i1++;
} else {
b[j] = a[i2];
i2++;
}
j++;
}
while (i1 <= mid) {
b[j] = a[i1];
i1++;
j++;
}
while (i2 <= to) {
b[j] = a[i2];
i2++;
j++;
}
for (j = ; j < n; j++) {
a[from + j] = (E) b[j];
}
}
}
SortTester code given:
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class SortTester {
public static void main(String[] args) {
runSortTester();
}
public static void runSortTester() {
int LENGTH = 10000;
Integer[] a = createRandomArray(LENGTH);
Comparator<Integer> comp = new Comparator<Integer>() {
public int compare(Integer d1, Integer d2) {
return d1.compareTo(d2);
}
}
long startTime = System.currentTimeMillis();
MergeSorter.sort(a, comp);
long endTime = System.currentTimeMillis();
if (!isSorted(a, comp)) {
throw new RuntimeExcepetion("not sorted afterward: " + Arrays.toString(a));
}
System.out.printf("%10d elements => %6d ms ", LENGTH, endTime - startTime);
}
public static <E> boolean isSorted(E[] a, Comparator<? super E> comp) {
for (int i = 0; i < a.length - 1; i++) {
if (comp.compare(a[1], a[i+1]) > 0) {
System.out.println(a[i] + " > " + a[i+1]);
return false;
}
}
return true;
}
public static <E> void shuffle(E[] a) {
for (int i = 0; i < a.length; i++) {
int randomIndex = (int)(math.random() * a.length - i);
swap(a, i, i + randomIndex);
}
}
public static final <E> void swap(E[] a, int i, int j) {
if (i != j) {
E temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
public static Integer [] createRandomArray(int length) {
Integer [] a = new Integer[length];
Random rand = new Random(System.currentTimeMillis());
for ( int i = 0; i < a.length; i++) {
a[i] = rand.nextInt(1000000);
}
return a;
}
}
Explanation / Answer
Output:
Enter the maximum number of threads:8
1 Threads:
1000 elements => 4 ms
2000 elements => 6 ms
4000 elements => 12 ms
8000 elements => 53 ms
16000 elements => 43 ms
32000 elements => 15 ms
64000 elements => 29 ms
128000 elements => 126 ms
256000 elements => 217 ms
512000 elements => 323 ms
1024000 elements => 718 ms
2048000 elements => 2807 ms
4096000 elements => 6501 ms
8192000 elements => 10143 ms
16384000 elements => 27612 ms
2 Threads:
1000 elements => 2 ms
2000 elements => 1 ms
4000 elements => 1 ms
8000 elements => 2 ms
16000 elements => 5 ms
32000 elements => 10 ms
64000 elements => 16 ms
128000 elements => 29 ms
256000 elements => 131 ms
512000 elements => 169 ms
1024000 elements => 393 ms
2048000 elements => 792 ms
4096000 elements => 6333 ms
8192000 elements => 11595 ms
16384000 elements => 6998 ms
4 Threads:
1000 elements => 1 ms
2000 elements => 1 ms
4000 elements => 1 ms
8000 elements => 1 ms
16000 elements => 2 ms
32000 elements => 4 ms
64000 elements => 7 ms
128000 elements => 17 ms
256000 elements => 77 ms
512000 elements => 102 ms
1024000 elements => 284 ms
2048000 elements => 613 ms
4096000 elements => 1762 ms
8192000 elements => 11249 ms
16384000 elements => 16788 ms
MergeSorter.java
package mergesort;
import java.util.Comparator;
public class MergeSorter {
public static <E> void sort(E[] a, Comparator<? super E> comp) {
mergeSort(a, 0, a.length - 1, comp);
}
private static <E> void mergeSort(E[] a, int from, int to, Comparator<? super E> comp) {
if (from == to) {
return;
}
int mid = (from + to) / 2;
// Sort the first and the second half
mergeSort(a, from, mid, comp);
mergeSort(a, mid + 1, to, comp);
merge(a, from, mid, to, comp);
}
@SuppressWarnings("unchecked")
private static <E> void merge(E[] a, int from, int mid, int to, Comparator<? super E> comp) {
int n = to - from + 1;
Object[] b = new Object[n];
int i1 = from;
int i2 = mid + 1;
int j = 0;
while (i1 <= mid && i2 <= to) {
if (comp.compare(a[i1], a[i2]) < 0) {
b[j] = a[i1];
i1++;
} else {
b[j] = a[i2];
i2++;
}
j++;
}
while (i1 <= mid) {
b[j] = a[i1];
i1++;
j++;
}
while (i2 <= to) {
b[j] = a[i2];
i2++;
j++;
}
for (j = 0; j < n; j++) {
a[from + j] = (E) b[j];
}
}
}
SortTester.java
package mergesort;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class SortTester {
public static void main(String[] args) throws NumberFormatException, IOException {
runSortTester();
}
public static void runSortTester() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter the maximum number of threads:");
int maxAllowedThreads = Integer.parseInt(br.readLine());
int processorNumber = Runtime.getRuntime().availableProcessors();
maxAllowedThreads = maxAllowedThreads < processorNumber ? maxAllowedThreads : processorNumber;
for (int j = 1; j <= maxAllowedThreads; j = j * 2) {
int LENGTH = 1000;
System.out.println(j + " Threads:");
for (int i = 1; i <= 15; i++) {
Integer[] a = createRandomArray(LENGTH);
Comparator<Integer> comp = new Comparator<Integer>() {
public int compare(Integer d1, Integer d2) {
return d1.compareTo(d2);
}
};
long startTime = System.currentTimeMillis();
parallelMergeSort(a, comp, j);
long endTime = System.currentTimeMillis();
if (!isSorted(a, comp)) {
throw new RuntimeException("not sorted afterward: " + Arrays.toString(a));
}
System.out.printf("%10d elements => %6d ms ", LENGTH, endTime - startTime);
LENGTH = LENGTH * 2;
}
}
System.out.println("*********************");
}
public static void parallelMergeSort(Integer[] a, Comparator<Integer> comp, int maxAllowedThreads) {
if (maxAllowedThreads <= 1) {
MergeSorter.sort(a, comp);
} else if (a.length >= 2) {
Integer[] left = Arrays.copyOfRange(a, 0, a.length / 2);
Integer[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
// MergeSorter.sort(left, comp);
// MergeSorter.sort(left, comp);
Thread lThread = new Thread((Runnable) new Sorter(left, comp, maxAllowedThreads / 2));
Thread rThread = new Thread((Runnable) new Sorter(right, comp, maxAllowedThreads / 2));
lThread.start();
rThread.start();
try {
lThread.join();
rThread.join();
} catch (InterruptedException ie) {
}
// merge them back together
merge(left, right, a);
}
}
public static void merge(Integer[] left, Integer[] right, Integer[] a) {
int i1 = 0;
int i2 = 0;
for (int i = 0; i < a.length; i++) {
if (i2 >= right.length || (i1 < left.length && left[i1] < right[i2])) {
a[i] = left[i1];
i1++;
} else {
a[i] = right[i2];
i2++;
}
}
}
public static <E> boolean isSorted(E[] a, Comparator<? super E> comp) {
for (int i = 0; i < a.length - 1; i++) {
if (comp.compare(a[1], a[i + 1]) > 0) {
System.out.println(a[i] + " > " + a[i + 1]);
return false;
}
}
return true;
}
public static <E> void shuffle(E[] a) {
for (int i = 0; i < a.length; i++) {
int randomIndex = (int) (Math.random() * a.length - i);
swap(a, i, i + randomIndex);
}
}
public static final <E> void swap(E[] a, int i, int j) {
if (i != j) {
E temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
public static Integer[] createRandomArray(int length) {
Integer[] a = new Integer[length];
Random rand = new Random(System.currentTimeMillis());
for (int i = 0; i < a.length; i++) {
a[i] = rand.nextInt(1000000);
}
return a;
}
}
Sorter.java
package mergesort;
import java.util.Comparator;
public class Sorter implements Runnable {
private Integer[] a;
private int threadCount;
private Comparator<Integer> comp;
public Sorter(Integer[] a, Comparator<Integer> comp, int threadCount) {
this.a = a;
this.comp = comp;
this.threadCount = threadCount;
}
public void run() {
SortTester.parallelMergeSort(a,comp, threadCount);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.