partitioning on large graphs
Hello all,
I am running Metis 5.0.2 on graph with 129026358 vertices and 13968560. Number of partitions specified is 3. Even after 5 hrs, gpmetis was still running. The machine on which this is running has lots of RAM, so that isn't a problem. From the top command, it is consuming 14.3GB of virtual memory and 8.4GB of resident memory. Many vertices among them are isolated. Can something be done to speed it up? Can Metis handle graphs of this size? Are there any other graph partitioning software that can handle large graphs? I am not aware of tools in this area. Please let me know.
Thank you.
Submitted by Raghava on Mon, 2013-04-15 09:40
»
- Login to post comments
RE: I believe the issue is the
I believe the issue is the large number of isolated vertices. Here is what I suggest:
1. Download and run the 5.1 version of code.
2. Run it with -dbglvl=15 and send me the output that it generates while it is running.
If there is such a large number of isolated vertices, then why do you include them in the graph? You can take them out, partition the rest of the graph, and then equally distribute the isolated vertices.
RE: Thank you for the reply. I
Thank you for the reply. I have given the output of Metis 5.1.0 with -dbglvl=15 option after running it for 35mins below.
I have included isolated vertices because of the following observation regarding Metis. Please correct me if I am wrong.
If I remove isolated vertices, then the vertices won't be sequential i.e. there would be gaps in the vertex file. Consequently, in the adjacency list (that metis takes as input), line i in adjacency list does not represent the adjacent vertices of vertex i (in Metis sense). I believe Metis assumes that line i in adjacency list should belong to vertex i. Here, the first line might belong to vertex 3568 and second line to vertex 3650.
******************************************************************************
METIS 5.0 Copyright 1998-11, Regents of the University of Minnesota
(HEAD: , Built on: Apr 15 2013, 01:41:02)
size of idx_t: 64bits, real_t: 32bits, idx_t *: 64bits
Graph Information -----------------------------------------------------------
Name: adjvertex-r-00000-new, #Vertices: 129026358, #Edges: 13968560, #Parts: 3
Options ---------------------------------------------------------------------
ptype=kway, objtype=cut, ctype=shem, rtype=greedy, iptype=metisrb
dbglvl=15, ufactor=1.030, minconn=NO, contig=NO, nooutput=NO
seed=-1, niter=10, ncuts=1
Direct k-way Partitioning ---------------------------------------------------
Runtime parameters:
Objective type: METIS_OBJTYPE_CUT
Coarsening type: METIS_CTYPE_SHEM
Initial partitioning type: METIS_IPTYPE_METISRB
Refinement type: METIS_RTYPE_GREEDY
Number of balancing constraints: 1
Number of refinement iterations: 10
Random number seed: -1
Number of partitions: 3
Number of cuts: 1
User-supplied ufactor: 30
Minimize connectivity: No
Create contigous partitions: No
Target partition weights:
0=[3.33e-01] 1=[3.33e-01] 2=[3.33e-01]
Allowed maximum load imbalance: 1.030
129026358 27937120 27937120 [6451317] [ 30:129026358 ]
65440972 19254872 20868738 [6451317] [ 30:129026358 ]
gk_mcore statistics
coresize: 4128843728 nmops: 2048 cmop: 0
num_callocs: 4 num_hallocs: 0
size_callocs: 3620160368 size_hallocs: 0
cur_callocs: 0 cur_hallocs: 0
max_callocs: 3620160368 max_hallocs: 0
nbrpool statistics
nbrpoolsize: 0 nbrpoolcpos: 0
nbrpoolreallocs: 0
RE: From that trace it does
From that trace it does appear that the issue is the very large number of isolated vertices. Metis' coarsening stops when the number of vertices is more than the number of edges, which is what is happening in tis graph. Remove the isolated vertices.
RE: I removed the isolated
I removed the isolated vertices. I also filled the gaps in the sequential vertices, after removing the isolated vertices. Metis was able to compute partitions this time, but the number of vertices were still more than number of edges (given below). You mentioned last time that if #Vertices > #Edges, then Metis stops. But that was not the case. Why is that so?
#Vertices: 15708640
#Edges: 13968560
RE: Thank you for the reply and
Thank you for the reply and suggestion. I will remove the isolated vertices and try again. I have a question
I have included isolated vertices because of the following observation regarding Metis. Please correct me if this is wrong.
If I remove isolated vertices, then the vertices won't be sequential i.e. there would be gaps in the vertex file. Consequently, in the adjacency list (that metis takes as input), line i in adjacency list does not represent the adjacent vertices of vertex i (in Metis sense). I believe Metis assumes that line i in adjacency list should belong to vertex i. Here, the first line might belong to vertex 3568 and second line to vertex 3650. Wouldn't this be a problem to Metis partitioner?