0
$\begingroup$

Using pseudocode, I need to design a parallel algorithm that, when given k keys, a[0], a[1], a[2],... a[k-1] stored in an unsorted array a, would find the second largest key in it.

I'm new to parallel computing, so I know that in terms of sequential programming, we can use bubble sort with two passes. First pass gets your the largest element, while the second pass will get you the second largest element, the goal. Should we split the bubble sorta via parallel processing, we only need to do one pass each iterations largest element to find the second largest. My problem is I don't know how to exactly 'parallelize' the algorithm.

$\endgroup$
  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that, and without more to work with, it's hard to know how to help. You don't know whether you can use bubble sort in parallel programming: what are your thoughts? What's your reasoning? Try to reason it out, and then share your thoughts. You might want to take a look at meta.cs.stackexchange.com/q/1284/755 and then edit the question to improve it based on the guidelines there. $\endgroup$ – D.W. Oct 6 '16 at 17:40
  • 2
    $\begingroup$ Parallel in which model? $\endgroup$ – Raphael Oct 6 '16 at 19:39
1
$\begingroup$

I'll sketch informally one obvious variant, assuming some model with shared memory and unbounded parallelism (I'm not going to discuss the synchronization issues, though). Lets denote the size of the original array as $n$.

  1. Divide your array into $k$ subarrays of approximately equal sizes $s_i$, such that $s_i \approx \frac{n}{k} \wedge s_i \ge 2$, then assign each subarray to a thread or whatever you use, lets call it "process". This assignment procedure can be (should be) implemented in a way such that its time complexity is $O(1)$.
  2. Then $i$-th parallel process finds the largest $M_i$ and the second largest element $m_i$ of $i$-th subarray sequentially. It's an easy linear complexity algorithm, which works in one go through all the elements of the input. So, time complexity of this step is $O\left(\frac{n}{k}\right)$. $i$-th process will store the results in the first two elements of $i$-th subarray, so you won't need to send $M_i$ and $m_i$ anywhere and resolve the synchronization issues connected with sending/receiving. That's why we need $s_i \ge 2$, and if there is not enough elements then it is not worth to process it in parallel.
  3. Wait until all processes finish (its called a barrier). At this point you have an array of all the results ($M_i$ and $m_i$) of all processes. Now, simply use the sequential algorithm again. The resulting $m$ will be the answer for the whole original array. Time complexity of this step is $O(k)$.

The overall time complexity of our algorithm is $O\left(\frac{n}{k} + k\right)$. Under this very simplistic model it's better to have the number of parallel processes $k \sim \sqrt{n}$ to make the overall time complexity minimal: $O \left( \sqrt{n} \right)$. This result can be easily obtained using differential calculus. Of course, this result is very far from the reality of practical parallel computing: we don't have unbounded parallelism in practice and we need to consider the parallel processing management overhead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.