A multithreaded merge sorting program works as follows: A list of N integers is divided into...
Fantastic news! We've Found the answer you've been seeking!
Question:
![A multithreaded merge sorting program works as follows: A list of N integers is divided into k, sub-lists of](https://dsd5zvtm8ll6.cloudfront.net/si.experts.images/questions/2023/09/6502b5fbc7ead_1694676472328.jpg)
![Note: Multi-list merging can be done using a priority queue, where, at first start the minimum value is](https://dsd5zvtm8ll6.cloudfront.net/si.experts.images/questions/2023/09/6502b61892b6e_1694676503240.jpg)
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.
Expert Answer:
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
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these algorithms questions
-
A combined solar and auxiliary energy system is used to meet the same load as in Example 12.5. The total cost of the system to cover 65% of the load (solar fraction) is $20,000. The owner will pay a...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
How do researchers investigate the effectiveness of the integrated reporting initiative?
-
Jackie owns and operates a web - design business. To keep up with new technology, she spends $5,000 per year upgrading her computer equipment. She runs the business out of a room in her home. If she...
-
Northwest Pipe (NP) makes water pipe. NP is planning production for the next seven months,March through September. The forecast demands (in thousands of feet) are, respectively, 40, 60, 70, 80, 90,...
-
Develop a security-awareness training session for a group of employees from the accounts and marketing departments. LO.1
-
1. Identify and briefly describe four characteristics you would expect to find in a successful manager in this type of venture. 2. What steps does Jack need to follow to successfully identify and...
-
Alex Corporation reports the following components of stockholders' equity at December 31 of the prior year. Common stock-$25 par value, 70,000 shares authorized, 50,000 shares issued and outstanding...
-
Start with the partial model in the file Ch12 P10 Build a Model.xlsx on the text book's Web site, which contains the 2016 financial statements of Zieber Corporation. Forecast Zieber's 2017 income...
-
Question 4 of 5 View Policies Show Attempt History Current Attempt in Progress Blossom Company has these data at December 31, 2022, the end of its first year of operations. Debt Securities Cost Fair...
-
The transmitted energy expands out into space as it propagates at 3 GHz between the transmitter and the receiver over 30 km distance. Calculate the free space loss using a suitable formula and any...
-
What is the company featured in this episode of Undercover Boss? List 3 good professional activities that the CEO/president learned about their company by going undercover? List areas of the...
-
Assume there is a national lottery in the winning ticket is worth $10 million one winning ticket will be selected if there are 225 million tickets sold. What is the chance that a buyer of one ticket...
-
Description: Reference: Basu Thakur. (2015). PostcolonialTheory and Avatar (pp. 85-150,157-172). Bloomsbury PublishingUSAPre-Peer Paper Review for the Postcolonial Application Paper 1: Collecting...
-
NOT ASKING THE ACTUAL SHEAR STRESS. Please READ! Derive the shear stress distributed equation over the cross-section. Derive the equation and plot. 15 15 30 15 15 120 -90 20 0.5 m 72 kN 20 20 40 40...
-
Assume that the direct cost of belonging to the union in this labor market is $100/year dues, and that collective bargaining will cause each worker to lose 2 weeks pay (expected value) in the first...
-
On average there are four traffic accidents in a city during one hour of rush-hour traffic. Use the Poisson distribution to calculate the probability that in one such hour there arc (a) No accidents...
-
Describe the LUP decomposition of a diagonal matrix.
-
The version of PARTITION given in this chapter is not the original partitioning algorithm. Here is the original partition algorithm, which is due to C. A. R. Hoare: HOARE-PARTITION (A, p, r)...
-
Consider linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any...
-
Identify two constraints in accounting. AppendixLO1
-
A medium-sized UK-based insurance company underwrites mainly commercial and industrial property and motor and liability insurance. Outline, with reasons, the types of reinsurance it is likely to buy...
-
If the present value of $1.00 received N years from today at an interest rate of int% is 0.270, what is the future value of $1.00 invested today at an interest rate of int% for N years? a. $1.00 b....
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App