Finding small vertex covers in a graph has applications in numerous domains. Two common formulations of the problem include: Minimum Vertex Cover, which finds the smallest vertex cover in a graph, and Parameterized Vertex Cover, which finds a vertex cover whose size is less than or equal to some parameter $k$. Algorithms for both formulations traverse a search tree, which grows exponentially with the size of the graph or the value of $k$. Parallelizing the traversal of the vertex cover search tree on GPUs is challenging for multiple reasons. First, the search tree is a narrow binary tree which makes it difficult to extract enough sub-trees to process in parallel to fully utilize the GPU's resources. Second, the search tree is highly imbalanced which makes load balancing across a massive number of parallel GPU workers challenging. Third, keeping around all the intermediate state needed to traverse many sub-trees in parallel puts high pressure on the GPU's memory resources and may act as a limiting factor to parallelism. To address these challenges, we propose an approach to traverse the vertex cover search tree in parallel using GPUs while handling dynamic load balancing. Each thread block traverses a different sub-tree using a local stack, however, we also use a global worklist to balance load. Blocks contribute branches of their sub-trees to the global worklist on an as-needed basis, while blocks that finish their sub-trees get new ones from the global worklist. We use degree arrays to represent intermediate graphs so that the representation is compact in memory to avoid limiting parallelism, but self-contained which is necessary for load balancing. Our evaluation shows that compared to prior work, our hybrid approach of using local stacks and a global worklist substantially improves performance and reduces load imbalance, especially on difficult instances of the problem.
翻译:在图形中查找小顶部封面有多个领域的应用。 问题的两个常见配方包括: 最小 Vertex Cover, 它在图形中找到最小的顶部封面, 以及 Parameterized Vertex Cover, 它在图形中找到一个大小小于或等于某个参数的顶部封面。 两个配方在搜索树上找到的顶部封面, 与图形的大小或美元值成倍增长。 平行的顶端树在图形的大小或美元值上平行增长。 平行的GPU的顶端搜索树搜索树的翻转是一个挑战性能。 首先, 搜索树是一个狭窄的双向双向树树层, 使得大量平行的 GPU 工人在搜索树上爬升。 第三, 保持所有中间状态, 平行的很多小树层在 GPUI 上运行, 使得 GPU 的内积分流存储器的存储资源压力很大, 但也有可能成为平行因素。 为了应对这些挑战, 我们提议一个平行的双向下层的双向轨道运行, 同时我们使用一个双向的双向的双向轨道 。