Multiprocessor Architecture and Algorithms

[shaqnolysis]

Below is a QuickSort Serial Algorithm.....

1. procedure QUICKSORT(A,q,r)
2. begin
3. if q < r then
4. begin
5. x := A[q];
6. s := q;
7. for i := q+1 to r do
8. if A <= x then
9. begin
10. s :=s+1;
11. swap(A[s],A);
12. end if
13. swap(A[q],A[s]);
14. QUICKSORT(A,q,s);
15. QUICKSORT(A,s+1,r);
16. end if
17. end QUICKSORT

The above pseudo quicksort serial algorithm should be parallelized but i really do not know how to to it.I just know that parallelizing a program forces a compiler to transform eligible loops for parallel execution in multiprocessor machines.In line 14 and 15 there is recursion ,the method calls itself,am wondering if thats where we have to bisect the above algorithm and parallize it at that point.

After Parallizing the above algorithm i would be happy if someone can suggest a possible multiprocessor architecture to be used...and please state how scalable,flexible and efficient of your suggested architecture.

Including the limitations of the parallelized algorithm will be more appreciated.
Thanks in Advance guys.....God Bless.

[mor01607]

Below is a QuickSort Serial Algorithm.....

1. procedure QUICKSORT(A,q,r)
2. begin
3. if q < r then
4. begin
5. x := A[q];
6. s := q;
7. for i := q+1 to r do
8. if A <= x then
9. begin
10. s :=s+1;
11. swap(A[s],A);
12. end if
13. swap(A[q],A[s]);
14. QUICKSORT(A,q,s);
15. QUICKSORT(A,s+1,r);
16. end if
17. end QUICKSORT

The above pseudo quicksort serial algorithm should be parallelized but i really do not know how to to it.I just know that parallelizing a program forces a compiler to transform eligible loops for parallel execution in multiprocessor machines.In line 14 and 15 there is recursion ,the method calls itself,am wondering if thats where we have to bisect the above algorithm and parallize it at that point.

After Parallizing the above algorithm i would be happy if someone can suggest a possible multiprocessor architecture to be used...and please state how scalable,flexible and efficient of your suggested architecture.

Including the limitations of the parallelized algorithm will be more appreciated.
Thanks in Advance guys.....God Bless.

please help me with the above quiestion am given it as an assgnment
please say any thing about it replay today please please

[mor01607]

please help me with the above quiestion am given it as an assgnment
please say any thing about it replay today please please

[Rashakil Fol]

All this requires is some thinking. I don't see what prevents you from doing that.

[shaqnolysis]

This is how i answered the question.thanks the creators of google did a good job....i need some inputs though.

The quick sort is an in-place, divide-and-conquer, massively recursive sort. The quick sort algorithm is simple in theory, but very difficult to put into code .
The recursive algorithm consists of four steps :
1. If there are one or less elements in the array to be sorted, return immediately.
2. Pick an element in the array to serve as a "pivot" point. (Usually the left-most element in the array is used.)
3. Split the array into two parts - one with elements larger than the pivot and the other with elements smaller than the pivot.
4. Recursively repeat the algorithm for both halves of the original array.
The efficiency of the algorithm is majorly impacted by which element is choosen as the pivot point. The worst-case efficiency of the quick sort, O(n2), occurs when the list is sorted and the left-most element is chosen. Randomly choosing a pivot point rather than using the left-most element is recommended if the data to be sorted isn't random. As long as the pivot point is chosen randomly, the quick sort has an algorithmic complexity of O(n log n).
Pros: Extremely fast.
Cons: Very complex algorithm, massively recursive.

The quick sort is by far the fastest of the common sorting algorithms. It's possible to write a special-purpose sorting algorithm that can beat the quick sort for some data sets, but for general-case sorting there isn't anything faster.

(b)The QuicSort program can be parallelized by dividing the whole program into three parts and making all the four processor to work on a single part of the task until they finish and working on the second part till they finish all the tasks.

Each one of the tasks can be allocated several processors at a time such that all the given processors will work on the different instructions until the first task completes then they will move on to the next task until the whole program is processed. This will avoid complexity and the data dependencies of the tasks will be met since each task will begin after the other is done. The multiprocessor architecture that could be used is the SIMD (single instruction stream, multiple data stream.) because it supports the divide and conquer method of parallelism.

c. The method is very scalable because adding a processor or another task it will not cost any complexity to get the method working. The efficiency is high because each task is handled by different processors which will help perform the task in good time. The flexibility very good.

d. The parallelized algorithm is going to need division of tasks within the given tasks and synchronization as well as integration of the subtasks upon completion which may just increase complexity. Data dependencies within tasks may prove to be a problem and will
waste more time and computing power on a single task in which one of the processors may take more time to complete its instructions than the other processors which will have to wait till it completes them.

[mohanrobin]

I just know that parallelizing a program forces a compiler to transform eligible loops for parallel execution in multiprocessor machines.In line 14 and 15 there is recursion ,the method calls itself,am wondering if thats where we have to bisect the above algorithm and parallize it at that point.