On Optimal Algorithms for List Ranking in the Parallel External Memory Model with Applications to Treewidth and other Elementary Graph Problems
On Optimal Algorithms for List Ranking in the Parallel External Memory Model with Applications to Treewidth and other Elementary Graph Problems
复制标题
DOI：
10.3929/ethz-a-010361860
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Lieber
中科院分区：
文献类型：
--
作者：
T. Lieber
许多算法在大型输入实例上的性能基本上取决于触发的缓存未命中的数量，而不是执行的操作的数量。这种行为是由外部记忆模型以自然的方式捕获的。它通过有限大小的快速缓存和概念上无限的（外部）内存对计算机进行建模。与经典 RAM 模型相反，复杂性度量是在高速缓存和内存之间传输的高速缓存行的数量。对缓存中元素的计算不计算在内。处理器设计的最新趋势和大数据计算的进步需要大规模并行算法。并行外部存储器 (PEM) 模型扩展了外部存储器模型，使其也捕获并行性。它由多个处理器组成，每个处理器都有一个私有缓存并共享（外部）内存。本文考虑了（并行）外部存储器算法背景下的三个计算问题。对于列表排序的基本问题，之前已知一种算法对于 PEM 模型的许多设置具有排序复杂性。在本文的第一部分中，该算法通过匹配大多数实际设置的下界来补充。有趣的是，显示了以前未考虑的参数范围的更强下限。通过对列表排序算法如何检索内存中列表结构的信息进行建模，我们给出了某些参数设置的排序复杂度的二次下限。值得注意的是，这个结果意味着批量同步并行和 MapReduce 模型的列表排名的第一个重要下限。这些下限由列表排名算法补充，与之前的算法相比，该算法针对 PEM 模型的所有参数设置进行分析。在第二部分中，提出了一种用于 PEM 模型计算图的有界宽度树分解的有效算法。主要挑战是实施负载平衡策略，以便运行
The performance of many algorithms on large input instances substantially depends on the number of triggered cache misses instead of the number of executed operations. This behavior is captured by the external memory model in a natural way. It models a computer by a fast cache of bounded size and a conceptually infinite (external) memory. In contrast to the classical RAMmodel, the complexity measure is the number of cache lines transferred between the cache and the memory. Computations on elements in the cache are not counted. Recent trends in processor design and advances in big data computing require massively parallel algorithms. The parallel external memory (PEM) model extends the external memory model so that it also captures parallelism. It consists of multiple processors which each have a private cache and share the (external) memory. This thesis considers three computational problems in the context of (parallel) external memory algorithms. For the fundamental problem of list ranking, previously, an algorithm was known that has sorting complexity for many settings of the PEM model. In the first part of this thesis, this algorithm is complemented by matching lower bounds for most practical settings. Interestingly, a stronger lower bound for parameter ranges which previously have not been considered is shown. By modeling how list ranking algorithms retrieve information on the structure of the list in the memory, we give a lower bound that is quadratic in sorting complexity for certain parameter settings. It is noteworthy that this result implies the first non-trivial lower bounds for list ranking for the bulk synchronous parallel and the MapReduce model. These lower bounds are complemented by a list ranking algorithm which is, in contrast to previous algorithms, analyzed for all parameter settings of the PEM model. In the second part, an efficient algorithm for the PEM model to compute a tree decomposition of bounded width for a graph is presented. The main challenge is to implement a load balancing strategy such that the running