i attached files below
CEG 7370 (73110) - Distributed Computing Spring 2022 Assignment #4 Due next Thursday (2/16/2023). No late assignments. I- Investigate and provide a brief description of the concept along with a a simple C# coding example that explain the idea of locking in C#. Go over the handout of Materiel Multiplication and use this knowledge and write a program that find the multiplication of three (n*n) Matrix A, B, and C. Provide the code for: A- The three Matrix multiplication sequetial execution B- The three Matrix multiplication TPL e n y your improvement and explain why you get this improvement based on your number of CPU core, The way that memory is being accessed, @ pilot.wright.edu HW5-part-2: Parallelization of Quick Sort Due 9/30/2022 No Late Assignment 1- You need to understand the Quick sort algorithm and run the code provided on this handout. 2- Explain what is the time complexity of the algorithm through examples. Change the SEQUENTIAL_THRESHOLD = 1000; to 10000 and report the complexity and explain what did you notice and if it is important from Parallelization point of view. Explain why? 3- Is there any other way to improve the Parallelization of quick sort? Quick Sort Algorithm and Its Parallelization The popular Quicksort algorithms recursively partitions the data in two halves based on the pivot element. Quicksort, on average, makes O(n.log(n)) comparisons to sort n items. In the worst-case, it makes O(n2) comparisons, though this behavior is very rare. How Quicksort Works? Quicksort is a Divide and Conquer algorithm. Like all divide-and-conquer algorithms, it first divides a large array into two smaller subarrays and then recursively sort the subarrays. As seen in the below figure, three steps are involved in the whole process: Pivot selection: randomly pick an element from the array you want to sort, called a pivot, from the array (usually the leftmost or the rightmost element of the partition). Partitioning: Reorder the array such that all elements with values less than the pivot come before the pivot. In contrast, all elements with values greater than the pivot come after it. The equal values can go either way. After this partitioning, the pivot is in its final position. Recur: Recursively apply the above steps to the subarray of elements with smaller values than the pivot and separately to the subarray of elements with greater values than the pivot. The base case of the recursion is arrays of size 1, which never need to be sorted. The following is an example that shows how we choose the leftmost element as pivot at each step of the Quicksort algorithm, partition the array across the pivot, and recur on two subarrays we get after the partition process: Let’s take a look at an example to get a better understanding of the Quicksort algorithm. In this example, the array(shown in graphic below) contains unsorted values, which we will sort using Quicksort. Unsorted & Sorted Array 1). Selecting Pivot The process starts by selecting one element (known as the pivot) from the list; this can be any element. A pivot can be: • Any element at random • The first or last element • Middle element For this example, we’ll use the last element, 4, as our pivot. 2). Rearranging the Array Now, the goal here is to rearrange the list such that all the elements less than the pivot are towards the left of it, and all the elements greater than the pivot are towards the right of it. • The pivot element is compared to all of the items starting with the first index. If the element is greater than the pivot element, a second pointer is appended. • When compared to other elements, if a smaller element than the pivot element is found, the smaller element is swapped with the larger element identified before. Let’s simplify the above example, • Every element, starting with 7, will be compared to the pivot(4). A second pointer will be placed at 7 because 7 is bigger than 4. • The next element, element 2 will now be compared to the pivot. As 2 is less than 4, it will be replaced by the bigger figure 7 which was found earlier. • The numbers 7 and 2 are swapped. Now, pivot will be compared to the next element, 1 which is smaller than 4. • So once again, 7 will be swapped with 1. • The procedure continues until the next-to-last element is reached, and at the end the pivot element is then replaced with the second pointer. Here, number 4(pivot) will be replaced with number 6. As elements 2, 1, and 3 are less than 4, they are on the pivot’s left side. Elements can be in any order: ‘1’,’2’,’3’, or ‘3’,’1’,’2’, or ‘2’,’3’,’1’. The only requirement is that all of the elements must be less than the pivot. Similarly, on the right side, regardless of their sequence, all components should be greater than the pivot. In simple words, the algorithm searches for every value that is smaller than the pivot. Values smaller than pivot will be placed on the left, while values larger than pivot will be placed on the right. Once the values are rearranged, it will set the pivot in its sorted position. 3). Dividing Subarrays: Once we have partitioned the array, we can break this problem into two sub-problems. First, sort the segment of the array to the left of the pivot, and then sort the segment of the array to the right of the pivot. Sorting the sub-arrays • In the same way that we rearranged elements in step 2, we will pick a pivot element for each of the left and right sub-parts individually. • Now, we will rearrange the sub-list such that all the elements are less than the pivot point, which is towards the left. For example, element 3 is the largest among the three elements, which satisfies the condition, hence the element 3 is in its sorted position. • In a similar manner, we will again work on the sub-list and sort the elements 2 and 1. We will stop the process when we get a single element at the end. • Repeat the same process for the right-side sub-list. The subarrays are subdivided until each subarray consists of only one element. • Now At this point, the array is sorted :) Note: Please note that the pivot selection and partitioning steps can be made in several ways, and the choice of specific implementation schemes significantly affects the algorithm’s performance. https://www.techiedelight.com/quicksort/ https://www.geeksforgeeks.org/quick-sort/ Example of Parallelization of quick Sort Algorithm: quick Sort is a popular operation on large data, thus its parallelization is important to reduce the execution time. There are different ways to parallelize the sorting algorithm. One easy way to implement parallelization of Quicksort is to create two parallel tasks for each of the partitioned lists. To do this let us wright this coed to create a Windows forms application project called ParallelQuickSort and add a class to the project called QuicksortAlgorithms with the following code in it. class QuicksortAlgorithms { public static void Quicksort
(T[] data, int left, int right) where T : IComparable // The Quicksort method uses the IComparable implementation to sort the list entries. { if (right > left) { int pivot = Partition(data, left, right); Quicksort(data, left, pivot - 1); Quicksort(data, pivot + 1, right); } } public static void QuickSortParallel(T[] data, int left, int right) where T : IComparable { const int SEQUENTIAL_THRESHOLD = 1000; if (right > left) { if ((right - left) < sequential_threshold)="" quicksort(data,="" left,="" right);="" do="" sequential="" sort="" else="" {="" }="" }="" }="" int="" pivot="Partition(data," left,="" right);="" parallel.invoke(()=""> QuickSortParallel(data, left, pivot - 1), () => QuickSortParallel(data, pivot + 1, right)); private static int Partition(T[] data, int low, int high) where T : IComparable { int left, right; T pivotItem; pivotItem = data[low]; int pivot = left = low; right = high; while (left < right)="" {="" while="" (data[left].compareto(pivotitem)=""><= 0)="" {="" if="" (left="">< data.length="" -="" 1)="" left++;="" else="" }="" break;="" while="" (data[right].compareto(pivotitem)=""> 0) { if (right > 0) right--; else } break; if (left < right)="" swap(data,="" left,="" right);="" }="" data[low]="data[right];" data[right]="pivotItem;" 8="" return="" right;="" }="" private="" static="" void="">(T[] data, int i, int j) { T temp = data[i]; data[i] = data[j]; data[j] = temp; } } To test this code: add three buttons to the form as shown below. The code for the Form1 class along with the three button handlers is shown below. public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void btnSortSequential_Click(object sender, EventArgs e) { double[] data = { 3, 9, 15, 7, 8, 4, 11 }; QuicksortAlgorithms.Quicksort(data, 0, data.Length - 1); string out1 = ""; foreach (int n in data) out1 += n.ToString() + " " + "\n"; MessageBox.Show(out1); } private void btnSortSequentialLarge_Click(object sender, EventArgs e) { int size = 10000000; double[] data = new double[size]; 9 InitData(data); Stopwatch sw = new Stopwatch(); sw.Start(); QuicksortAlgorithms.Quicksort(data, 0, data.Length - 1); sw.Stop(); MessageBox.Show("Sequential: Time taken = " +sw.ElapsedMilliseconds.ToString()); } void InitData(double[] data) { Random rand = new Random(); for (int i = 0; i < data.length;="" i++)="" data[i]="rand.NextDouble()" *="" 1000="" +="" 5;="" }="" private="" void="" btnsortparallellarge_click(object="" sender,="" eventargs="" e)="" {="" int="" size="10000000;" double[]="" data="new" double[size];="" initdata(data);="" stopwatch="" sw="new" stopwatch();="" sw.start();="">(data, 0, data.Length - 1); sw.Stop(); MessageBox.Show("Parallel: Time taken = " + sw.ElapsedMilliseconds.ToString()); } } Test the execution time of the sequential and parallel quicksort algorithms by clicking on the “Sort Sequential large” and “Sort Sequential Parallel” buttons. 10