On the Complexity of List Ranking in the Parallel External Memory Model
On the Complexity of List Ranking in the Parallel External Memory Model
复制标题
DOI：
10.1007/978-3-662-44465-8_33
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
R. Jacob;T. Lieber;Nodari Sitchinava
中科院分区：
文献类型：
--
作者：
R. Jacob;T. Lieber;Nodari Sitchinava
本文研究了并行外部存储器（PEM）模型中的链表排序问题.我们观察到一个有趣的双重性质的硬度的问题，由于有限的信息交换之间的处理器的列表的结构，一方面，其密切的关系，置换数据的问题，这是已知的是很难的外部存储器models.By仔细定义的计算模型的权力，我们证明了置换的PEM模型的下限。此外，我们提出了一个更强的Ω（log2N）下界的问题的一个特殊的变体和一个特定的模型参数范围，这使我们更接近证明一个非平凡的下界的批量同步并行（BSP）和MapReduce模型中的列表排名问题。最后，我们还提出了一种算法，该算法比以前的工作中的模型的参数范围更大。
We study the problem oflist rankingin the parallel external memory (PEM) model. We observe an interesting dual nature for the hardness of the problem due to limited information exchange among the processors about the structure of the list, on the one hand, and its close relationship to the problem of permuting data, which is known to be hard for the external memory models, on the other hand.By carefully defining the power of the computational model, we prove a permuting lower bound in the PEM model. Furthermore, we present a stronger Ω(log2N) lower bound for a special variant of the problem and for a specific range of the model parameters, which takes us a step closer toward proving a non-trivial lower bound for the list ranking problem in the bulk-synchronous parallel (BSP) and MapReduce models. Finally, we also present an algorithm that is tight for a larger range of parameters of the model than in prior work.