Parallel merging with restriction
Bahig, Hazem;
Abstract
In this paper, we study the merging of two sorted arrays A=(a1,a2,..., an1) and B=(b1,b2,...,bn2) on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n ,n ). (2) The elements are taken from either uniform distribution or non-uniform distribution such that #\{a∈A,b ∈ B {s.t.} ,a,b ∈ [(i-1) {n}{p}+1,i {n}p] }=O( n}{p} , for 1 i p∈(number of processors). We give a new optimal deterministic algorithm runs in O( {n}{p}) time using p processors on EREW PRAM. For p= n (g)} {n}}; the running time of the algorithm is O(log∈ n) which is faster than the previous results, where log∈ n=log∈log∈ n for g>1 and log∈ n=log∈n. We also extend the domain of input data to [1,n ], where k is a constant. © 2007 Springer Science+Business Media, LLC. 1 2 (g) (g) (g-1) (1) k
Other data
Title | Parallel merging with restriction | Authors | Bahig, Hazem | Keywords | EREW PRAM;Integer merging;Optimal algorithms;Parallel algorithms | Issue Date | 1-Jan-2008 | Publisher | SPRINGER | Journal | Journal of Supercomputing | Volume | 43 | Start page | 99 | End page | 104 | ISSN | 09208542 | DOI | 10.1007/s11227-007-0141-5 | Scopus ID | 2-s2.0-37649017663 | Web of science ID | WOS:000251972500006 |
Recommend this item
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.