5,337
edits
Parallel Algorithms: Difference between revisions
→Technique: Merge Sorting Cluster
| Line 106: | Line 106: | ||
* Given an algorithm for merging, we know A(i) belongs in C(j) so Rank(A(i), B) = j-i | * Given an algorithm for merging, we know A(i) belongs in C(j) so Rank(A(i), B) = j-i | ||
* Given an algorithm for ranking, we get A(i) belongs in C(j) where j = Rank(A(i), B) + i | * Given an algorithm for ranking, we get A(i) belongs in C(j) where j = Rank(A(i), B) + i | ||
;Naive algorithm | |||
Apply binary search element wise on concurrent read system. | |||
O(log n) time, O(nlog n) work | |||
<pre> | |||
for 1 <= i <= n pardo | |||
Rank(A(i), B) | |||
Rank(B(i), A) | |||
</pre> | |||
;Partitioning paradigm | |||
Input size: n | |||
* Partition the input into p jobs of size approx. n/p | |||
* Do small jobs concurrently using a separate (possibly serial) algo for each. | |||
Example: | |||
Total work O(n), total time O(log n) | |||
<pre> | |||
// Partitioning | |||
for 1 <= i <= p pardo | |||
b(i) = Rank((n/p)(i-1)+1, B) | |||
a(i) = Rank((n/p)(i-1)+1, A) | |||
// Total slice size is <= 2n/p. Total 2p slices. | |||
// E.g. slice size is 2 * log(n) if p=n/log(n). | |||
// Work | |||
for 1 <= i <= p pardo | |||
k = ceil(b(i)/(n/p)) % (n/p) | |||
merge slice A[(n/p)(i-1)+1:min(a(i), (n/p)i+1)] and B[b(i):min(b(i+1), b(i) + k)] | |||
</pre> | |||
===Techinque: Divide and Conquer=== | ===Techinque: Divide and Conquer=== | ||