Faster merging networks with a small constant period

详细信息    查看全文

• 作者：Marek Piotró ; w ^{Marek.Piotrow@ii.uni.wroc.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Parallel merging ; Oblivious merging ; Comparison networks ; Merging networks ; Periodic networks ; Comparators
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：9 August 2016
• 年：2016
• 卷：640
• 期：Complete
• 页码：20-40
• 全文大小：935 K

文摘

We consider the problem of merging two sorted sequences on a comparator network that is used repeatedly, that is, if the output is not sorted, the network is applied again using the output as input. The challenging task is to construct such networks of small depth (called a period in this context). In our previous paper Faster 3-Periodic Merging Network   we reduced the time of merging on 3-periodic networks by a factor of 2, i.e. from 12log⁡N$12\log N$ to 6log⁡N$6\log N$, compared to the first construction given by Kutyłowski, Loryś and Oesterdiekhoff. Note that merging on 2-periodic networks requires linear time. In this paper we extend our construction, and the analysis from that paper to any period p≥3$p\ge 3$. For p≥3$p\ge 3$ our p  -periodic network merges two sorted sequences of length N/2$N/2$ in at most $\frac{2p}{p-2}\log N+p\frac{p-8}{p-2}$ rounds. The previous bound given by Kutyłowski et al. was $\frac{2.25p}{p-2.42}\log N$ for p≥4$p\ge 4$. That means, for example, that our 4-periodic merging networks work in time upper-bounded by 4log⁡N$4\log N$ and our 6-periodic ones in time upper-bounded by 3log⁡N$3\log N$ compared to the corresponding 5.67log⁡N$5.67\log N$ and 3.8log⁡N$3.8\log N$ previous bounds. Our construction is regular in the sense that it is parametrised with p   and one can set p=3$p=3$ to get the family of 3-periodic merging networks, whereas the previous constructions given for p=3$p=3$ and p≥4$p\ge 4$ differ in their structures. Moreover, our networks are also periodic sorters, and tests on random permutations suggest that the average sorting time might be close to log²⁡N${\log }^{2}N$.