Name
Abstract | ||
|---|---|---|
In this paper, we study the merging of two sorted arrays $A=(a_{1},a_{2},\ldots, a_{n_{1}})$ and $B=(b_{1},b_{2},\ldots,b_{n_{2}})$ on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n 1,n 2). (2) The elements are taken from either uniform distribution or non-uniform distribution such that $\#\{a\in A\,\mbox{and}\,b\in B\,\mbox{s.t.}\,a,b\in [(i-1)\frac{n}{p}+1,i\,\frac{n}{p}]\}=O(\frac{n}{p})$ , for 1驴i驴p驴(number of processors). We give a new optimal deterministic algorithm runs in $O(\frac{n}{p})$ time using p processors on EREW PRAM. For $p=\frac{n}{\log^{(g)}{n}}$ ; the running time of the algorithm is O(log驴(g) n) which is faster than the previous results, where log驴(g) n=log驴log驴(g驴1) n for g1 and log驴(1) n=log驴n. We also extend the domain of input data to [1,n k ], where k is a constant. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s11227-007-0141-5 | The Journal of Supercomputing |
Keywords | Field | DocType |
Parallel algorithms,Optimal algorithms,Integer merging,EREW PRAM | Integer,Combinatorics,Computer science,Parallel computing,Algorithm,Deterministic algorithm,Merge (version control) | Journal |
Volume | Issue | ISSN |
43 | 1 | 0920-8542 |
Citations | PageRank | References |
1 | 0.35 | 12 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hazem M. Bahig | 1 | 24 | 7.61 |