How to set the size of each partition with Metis

Hi,

I run into difficulty when using metis to split a graph into a group of partitions with predetermined size for each partition.

Let me take an example to explain. Suppose we have a graph with, say, 20 vertices. Now I want to partition this graph into 4 partitions, each of them contains 5 vertices. Can metis work with this restriction? If so, how do I set up this restriction in metis?

Any suggestions/comments are appreciated.

QG

RE: It is described in Metis' 5.0

It is described in Metis' 5.0 manual in section 4.1.3.

RE: Still can't understand how to

Still can't understand how to get this done. Sometimes metis doesn't return the same number of partitions as user expected. For example, the 7-vertices unweighted graph illustrated in Metis 5.1.0 manual (fig.2-a) has the following graph file:

7 11
5 3 2
1 3 4
5 4 2 1
2 3 6 7
1 3 6
5 4 7
6 4

If my under standarding is right, Metis will partition this graph into user specified number of components, each component contains one or more vertices. In an extreme case, if user run metis to partition this graph into 7 components then each resulted partition should contain 1 vertex. The output partition file should look like:

1
2
3
4
5
6
7

However, the actual result returned by Metis is as following:

4
4
4
4
4
4
4

This means partition 4 contains all vertices but other partitions (0,1,2,3,5,6) are empty.

Why this happens? Is there any way to set up metis job so that this case can be partitioned into exact number of non-empty components as user expected?

This is actually the same issue as I discribed in my first email. The background of this issue is how to use Metis to distribute the processes of a parallel job onto computer cluster with predetermined system resource. The example in this email says: distribute a 7-process job onto 7 cores (CPUs) located on 7 different computer nodes (one core per node). While the example in my previous email says: run a 20-process parallel job onto 4 nodes, each has 5 cores (5+5+5+5). The purpose here is to find the optimal process-to-computer mapping so that the entire inter-process communications between different computer nodes are minized.

I still don't get any clue on how Metis treat this kind of constraints in graph partitioning. Can anybody help provide more detailed guidance? for the 7-node graph example above, how can it be partitioned with the following distributions:

# of parts # vertices in each part
========== =======================
2 4 + 3
3 3 + 2 + 2
4 2 + 2 + 2 + 1
5 2 + 2 + 1 + 1 + 1
6 2 + 1 + 1 + 1 + 1 + 1
7 1 + 1 + 1 + 1 + 1 + 1 + 1

Thanks in advance for your kind advice.

QG