Dear MPI people,
I am working on a graph partitioning problem,
where we have an undirected graph of p MPI processes. The edges have weights
that show how much communication processes do among themselves. The cluster has
multiple nodes (each node with 8 cores) and nodes are connected through
Infiniband fast network. The task is the partition the graph in k partitions
where k is the number of nodes such that the edge cut is minimized (across
partitions/nodes edges or communication). I wrote a distributed algorithm for
that. I will compare its quality with the algorithms from graph community, but
right now I am writing the algorithm for MPI applications. I have seen that
with 10% sparse undirected graph, I got upto 80% reduction in edge cut (for
k=2).
I checked the algorithm very deeply and I have seen that the optimal partitions
are residing on different nodes (I saw the IPs). Based on the NetPipe
benchmark, I wrote a test application where I randomly generate undirected
graphs. I run that application before doing the reduction of edge cut and after
reduction of edge cut. The processes that communicate more come to the same
nodes. In the algorithm, each process gets a new rank based on communication
requirement. The problem I am getting is that the overall execution time of the
test application should be less than the application that runs without
performing edge cut reduction but it does not happen. Here is the code for test
application (self explanatory) and the output of the program. Please help me
diagnosing the logical bug. We can discuss more.
MPI_Barrier(comm);
t0 = MPI_Wtime();
for(int j=0;j<10;j++)
{
for(int i=0; i<comm_size; i++)
{
int target = comminfo[i].rank;
int comm_amount = comminfo[i].comm;
if(comm_amount > 0)
{
buff = new Node[MAX_COMM*NTRIALS];
MPI_Irecv (buff, MAX_COMM * NTRIALS * sizeof(Node)/sizeof(char),
MPI_CHAR, MPI_ANY_SOURCE, 4600, comm, &recv_requests[i]);
recv_buffers.insert(recv_buffers.end(), buff);
}
}
for(int i=0; i<comm_size; i++)
{
int target = comminfo[i].rank;
int comm_amount = comminfo[i].comm;
if(comm_amount > 0)
{
buff = new Node[comm_amount/2*NTRIALS];
MPI_Isend((void*)buff, comm_amount/2 * NTRIALS *
sizeof(Node)/sizeof(char), MPI_CHAR, target, 4600, comm, &send_requests[i]);
send_buffers.insert(send_buffers.end(), buff);
}
}
MPI_Waitall(comm_size, send_requests, send_status);
MPI_Waitall(comm_size, recv_requests, recv_status);
}
t1 = MPI_Wtime();
MPI_Allreduce(&t0, &min_t0, 1, MPI_DOUBLE, MPI_MIN, comm);
MPI_Allreduce(&t1, &max_t1, 1, MPI_DOUBLE, MPI_MAX, comm);
diff = (max_t1 - min_t0) / NTRIALS;
retirm diff; // this value will be printed in main function....
.................. the output of the program is
mpprun INFO: Starting openmpi run on 2 nodes (16 ranks)...
P0 >> Without balancing: Execution took: 0.0081014822 secs
Edge_Cut_Before: 46864
Edge_Cut_After: 20097
Balancing took: 1.0993268490 secs
P0 >> After balancing: Execution took: 0.0095374639 secs
Please help me.
best regards,
Mudassar
