Partitioning for complex objectives
Partitioning for complex objectives
复制标题
复杂目标的划分
DOI：
10.1109/ipdps.2001.925098
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
B. Hendrickson
中科院分区：
文献类型：
--
作者：
Ali Pinar;B. Hendrickson
图划分是在并行机的处理器之间分配工作的重要工具，但它不适合一些重要的应用。具体地说，图划分要求每个处理器的工作是顶点权重的简单和。对于许多应用程序来说，这一假设是不正确的--工作(或内存)是分区的复杂函数。在本文中，我们描述了一个解决这种划分问题的通用框架，并研究了它在两个应用上的应用--划分以使重叠的子域是平衡的，以及划分以最小化计算和通信时间之和。
Graph partitioning is an important tool for dividing work amongst processors of a parallel machine, but it is unsuitable for some important applications. Specifically, graph partitioning requires the work per processor to be a simple sum of vertex weights. For many applications, this assumption is not true — the work (or memory) is a complex function of the partition. In this paper we describe a general framework for addressing such partitioning problems and investigate its utility on two applications — partitioning so that overlapped subdomains are balanced and partitioning to minimize the sum of computation plus communication time.