A multithreaded merge sorting program works as follows: A list of N integers is divided into...

 

Transcribed Image Text:

A multithreaded merge sorting program works as follows: A list of N integers is divided into k, sub-lists of equal sizes. Then, a number equal to k sorting threads are created in order to sort each sub-list using any O(n log2 n) sorting algorithm. Because global data are shared across all threads, perhaps the easiest way to set up the shared data is to create a global integer array, A. Partitioned carefully, each sorting thread will work independently on one part of this array. A second local integer array, B, of the same size as A, will also be established. A merge thread will then merge the k sorted sub-lists into this second array, producing a sorted list. Graphically, the suggested program is structured as in the shown figure: sorting thread 7,12, 19, 3, 18 original list 7,12, 19, 3, 18, 4, 2, 6, 15,8 merge thread 2,3,4,6,7,8, 12, 15, 18, 19 sorted list sorting shread' 4.2.6, 15,8 Note: Multi-list merging can be done using a priority queue, where, at first start the minimum value is removed from each sub-list and inserted into the priority queue, along with its original location (i.e. from which sub-list it was removed), then the following three steps are repeated until all sub-lists are empty: 1) the minimum value is removed from the priority queue, its original location is noted; 2) its value is added in- order to array B; 3) the next value is removed from the noted location and added to the priority queue. Dr. A. M. Al-Qasimi Home Work +4, Spring 2022 Page 1 of 2 The main program (i.e. the main thread) shall initialize the global integer array, A, get integers N and k from the command line, generate N random integers in the range [0.. 10*N], and store them in A. The main thread shall then partition A into k equal-size sub-lists by creating k sets of (starting, ending} indices of A, create k sorting threads, and pass appropriate parameters to each of them. In particular, each sorting thread shall be able to identify the starting and ending indices of A, on which it shall operate to get it sorted. After that, the main thread shall wait for all the sorting threads to finish before it shall start being the merge thread acting to merge the sorted sub-lists. Before starting each sorting thread, the main thread shall print the thread ID and its assigned starting and ending indices of A. Similarly, the merge thread shall print the index-ranges of the sub-lists it is to merge. After merging of all the sorted sub-lists, the main thread shall output the sorted array. Waiting for Threads to Complete Read the multi-threaded example found in the course web site, and the related Java API documentation to learn how to create threads, pass the required parameters to them, and how to make a thread wait until the other threads are finished. What to do: Write a multithreaded program in Java, using the Java API, and java threads to sort a list of integers as described above. For phase #1, you can write any O(n log, n) sorting method or you can use java.util.Arrays.sort(A, s, e) method to sort sub-arrays of A from starting index s to ending index e. For phase #2, write a multiMerge() function using java.util. Priority Queue class as noted above. Your program shall read two command-line integer parameters N and k, indicating the list size and the number of threads respectively, generate a random integer list into array A, then it shall sort A utilizing all your CPU's core threads. Run the program 10 times: The first is a test run, use N = 24 and k = 5, save the program output. The second run is 100% serial, i.c. without multi-threading (k = 1); the other runs shall use the same N as the second run but with different values of k at 2, 3, 4, 8, 12, 16, 24 and 32. In all the cases measure the time it takes to do the sorting and merging only (i.c. without any I/O operations) and report the following: • The number of cores in your system. • For each run, report N, k and T, the amount of time it took to finish. • For first run only, the input random array and the output sorted array. • Plot k versus T. From the above results, calculate and report how much speedup is obtained when using the multi- threaded parallel approach. Note that in order to get significant timing measures, you need to have N very large! Try 1000,000. Also, in order to get consistent timing measures, close all programs, the network, and do not touch the mouse or keyboard during the measuring process. A multithreaded merge sorting program works as follows: A list of N integers is divided into k, sub-lists of equal sizes. Then, a number equal to k sorting threads are created in order to sort each sub-list using any O(n log2 n) sorting algorithm. Because global data are shared across all threads, perhaps the easiest way to set up the shared data is to create a global integer array, A. Partitioned carefully, each sorting thread will work independently on one part of this array. A second local integer array, B, of the same size as A, will also be established. A merge thread will then merge the k sorted sub-lists into this second array, producing a sorted list. Graphically, the suggested program is structured as in the shown figure: sorting thread 7,12, 19, 3, 18 original list 7,12, 19, 3, 18, 4, 2, 6, 15,8 merge thread 2,3,4,6,7,8, 12, 15, 18, 19 sorted list sorting shread' 4.2.6, 15,8 Note: Multi-list merging can be done using a priority queue, where, at first start the minimum value is removed from each sub-list and inserted into the priority queue, along with its original location (i.e. from which sub-list it was removed), then the following three steps are repeated until all sub-lists are empty: 1) the minimum value is removed from the priority queue, its original location is noted; 2) its value is added in- order to array B; 3) the next value is removed from the noted location and added to the priority queue. Dr. A. M. Al-Qasimi Home Work +4, Spring 2022 Page 1 of 2 The main program (i.e. the main thread) shall initialize the global integer array, A, get integers N and k from the command line, generate N random integers in the range [0.. 10*N], and store them in A. The main thread shall then partition A into k equal-size sub-lists by creating k sets of (starting, ending} indices of A, create k sorting threads, and pass appropriate parameters to each of them. In particular, each sorting thread shall be able to identify the starting and ending indices of A, on which it shall operate to get it sorted. After that, the main thread shall wait for all the sorting threads to finish before it shall start being the merge thread acting to merge the sorted sub-lists. Before starting each sorting thread, the main thread shall print the thread ID and its assigned starting and ending indices of A. Similarly, the merge thread shall print the index-ranges of the sub-lists it is to merge. After merging of all the sorted sub-lists, the main thread shall output the sorted array. Waiting for Threads to Complete Read the multi-threaded example found in the course web site, and the related Java API documentation to learn how to create threads, pass the required parameters to them, and how to make a thread wait until the other threads are finished. What to do: Write a multithreaded program in Java, using the Java API, and java threads to sort a list of integers as described above. For phase #1, you can write any O(n log, n) sorting method or you can use java.util.Arrays.sort(A, s, e) method to sort sub-arrays of A from starting index s to ending index e. For phase #2, write a multiMerge() function using java.util. Priority Queue class as noted above. Your program shall read two command-line integer parameters N and k, indicating the list size and the number of threads respectively, generate a random integer list into array A, then it shall sort A utilizing all your CPU's core threads. Run the program 10 times: The first is a test run, use N = 24 and k = 5, save the program output. The second run is 100% serial, i.c. without multi-threading (k = 1); the other runs shall use the same N as the second run but with different values of k at 2, 3, 4, 8, 12, 16, 24 and 32. In all the cases measure the time it takes to do the sorting and merging only (i.c. without any I/O operations) and report the following: • The number of cores in your system. • For each run, report N, k and T, the amount of time it took to finish. • For first run only, the input random array and the output sorted array. • Plot k versus T. From the above results, calculate and report how much speedup is obtained when using the multi- threaded parallel approach. Note that in order to get significant timing measures, you need to have N very large! Try 1000,000. Also, in order to get consistent timing measures, close all programs, the network, and do not touch the mouse or keyboard during the measuring process.

Answer rating: 100% (QA)

void sortervoid params parameters p parametersparams int begin pfromindex int end ptoindex 1 int temp 0 int i int j for i begin i end i for j begin j end 1 j if listj listj 1 temp listj listj listj 1 ... View the full answer