Parallel merging with restriction期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

首页 | 本学科首页

官方微博 | 高级检索

Parallel merging with restriction

Authors:

Hazem M Bahig

Affiliation:

(1) Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo, Egypt

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 ₁,n ₂). (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 g>1 and log ⁽¹⁾ n=log n. We also extend the domain of input data to 1,n ^k], where k is a constant.

Hazem M. BahigEmail:

Keywords:

Parallel algorithms Optimal algorithms Integer merging EREW PRAM

本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏