A Parallel Technique for Partitioning Nodes of Weighted Graphs

摘要

In this paper we describe the basic scheme of an algorithm for optimising graph partitions which arise in mapping an application represented by an undirected graph to parallel computers. We introduce the domain of a minimum and two kinds of operations, simple migration and subgraph migration. The first one consists of moving one vertex of a graph at a time and can be effectively used inside domains to reach local minima. The second is used to change the domain, when the first one cannot operate. Subgraph migration consists of moving a connected subgraph to get out of the local minimum. We give the properties and principles of subset migration, and demonstrate these by experimental results.