Разделение графа с использованием ParMETIS - PullRequest
Новая
       27

Разделение графа с использованием ParMETIS

0 голосов
/ 06 февраля 2019

Я пытаюсь разделить невзвешенный неориентированный график из 8 узлов на 4-ядерном ноутбуке с помощью ParMETIS. У меня есть следующий код: 

#include <cstdlib>
#include "parmetis.h"

int main(int argc, char **argv)
{
  MPI_Init(&argc, &argv);
  int np = 4;
  idx_t xadj_[3];
  idx_t adjncy_[5];
  int rank;
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    if (rank == 0)
  {
      xadj_[0] = 0;
      xadj_[1] = 2;
      xadj_[2] = 5;
      adjncy_[0] = 4;
      adjncy_[1] = 1;
      adjncy_[2] = 0;
      adjncy_[3] = 5;
      adjncy_[4] = 2;
  }
    if (rank == 1)
  {
      xadj_[0] = 0;
      xadj_[1] = 3;
      xadj_[2] = 5;
      adjncy_[0] = 1;
      adjncy_[1] = 6;
      adjncy_[2] = 3;
      adjncy_[3] = 2;
      adjncy_[4] = 7;
  }
    if (rank == 2)
  {
      xadj_[0] = 0;
      xadj_[1] = 2;
      xadj_[2] = 5;
      adjncy_[0] = 5;
      adjncy_[1] = 0;
      adjncy_[2] = 6;
      adjncy_[3] = 1;
      adjncy_[4] = 4;
  }
    if (rank == 3)
  {
      xadj_[0] = 0;
      xadj_[1] = 3;
      xadj_[2] = 5;
      adjncy_[0] = 7;
      adjncy_[1] = 2;
      adjncy_[2] = 5;
      adjncy_[3] = 3;
      adjncy_[4] = 6;
  }
  idx_t *xadj = xadj_;
  idx_t *adjncy = adjncy_;

  idx_t vtxdist_[] = {0,2,4,6,8};
  idx_t *vtxdist = vtxdist_;

  idx_t *vwgt = NULL;

  idx_t *adjwgt = NULL;

  idx_t wgtflag_[] = {0};
  idx_t *wgtflag = wgtflag_;

  idx_t numflag_[] = {0};
  idx_t *numflag = numflag_;

  idx_t ncon_[] = {1};
  idx_t *ncon = ncon_;

  idx_t nparts_[] = {np};
  idx_t *nparts = nparts_;

  real_t *tpwgts = new real_t[np*ncon[0]]; for(int i=0; i<np*ncon[0]; i++) {tpwgts[i] = 1.0/np;}

  real_t ubvec_[] = {1.05};
  real_t *ubvec = ubvec_;

  idx_t options_[] ={0, 0, 0};
  idx_t *options =options_;

  idx_t *edgecut;
  idx_t part[8];

  MPI_Comm comm_val=MPI_COMM_WORLD;
  MPI_Comm *comm=&comm_val;
  ParMETIS_V3_PartKway(vtxdist,xadj,adjncy, vwgt, adjwgt, wgtflag, numflag, ncon, nparts, tpwgts, ubvec, options, edgecut, part, comm);
  MPI_Barrier(comm_val);
  printf("Processor %d --- %d\n", rank,*edgecut);
    for (int i = rank*2 ; i < rank*2+2; i++)
    {
      printf("%d\n",part[i]);
    }
  MPI_Finalize();
  return 0;
}

Graph image

Для каждого ранга (ядра)Я установил Распределенный формат CSR и пытаюсь получить результат, но получаю следующее: 

Processor 0 --- 6
0
0
Processor 1 --- 6
0
0
Processor 2 --- 6
2101207184
22080
Processor 3 --- 6
1904762080
22069

Что я делаю не так? Может быть, это из-за общей памяти или из-за того, что каждое ядро ​​имеет свою часть [8]? Почему я получаютакой странный вывод?

1 Ответ

0 голосов
/ 10 февраля 2019

Я нашел ошибку.Я неправильно понял одну вещь, например, у меня есть 8 узлов и 4 ядра, и каждое ядро ​​будет иметь [part [0], part [vtxdist [rank + 1] -vtxdist [rank]]).Например, у меня vtxdist = [0,1,4], это означает, что я использую 2 ядра, и первое ядро ​​(rank = 0) будет иметь часть [0], а второе ядро ​​(rank = 1) будет иметь часть [0], part[1], часть [2]. 

#include <cstdlib>
#include "parmetis.h"

int main(int argc, char **argv)
{
  MPI_Init(&argc, &argv);
  idx_t np = 4;
  idx_t xadj_[3];
  idx_t adjncy_[5];
  idx_t rank, npes;
  MPI_Comm comm;
  MPI_Comm_dup(MPI_COMM_WORLD, &comm);
  MPI_Comm_size(comm, &npes);
  MPI_Comm_rank(comm, &rank);
    if (rank == 0)
  {
      xadj_[0] = 0;
      xadj_[1] = 2;
      xadj_[2] = 5;
      adjncy_[0] = 4;
      adjncy_[1] = 1;
      adjncy_[2] = 0;
      adjncy_[3] = 5;
      adjncy_[4] = 2;
  }
    if (rank == 1)
  {
      xadj_[0] = 0;
      xadj_[1] = 3;
      xadj_[2] = 5;
      adjncy_[0] = 1;
      adjncy_[1] = 6;
      adjncy_[2] = 3;
      adjncy_[3] = 2;
      adjncy_[4] = 7;
  }
    if (rank == 2)
  {
      xadj_[0] = 0;
      xadj_[1] = 2;
      xadj_[2] = 5;
      adjncy_[0] = 5;
      adjncy_[1] = 0;
      adjncy_[2] = 6;
      adjncy_[3] = 1;
      adjncy_[4] = 4;
  }
    if (rank == 3)
  {
      xadj_[0] = 0;
      xadj_[1] = 3;
      xadj_[2] = 5;
      adjncy_[0] = 7;
      adjncy_[1] = 2;
      adjncy_[2] = 5;
      adjncy_[3] = 3;
      adjncy_[4] = 6;
  }
  idx_t *xadj = xadj_;
  idx_t *adjncy = adjncy_;

  idx_t vtxdist_[] = {0,2,4,6,8};
  idx_t *vtxdist = vtxdist_;

  idx_t *vwgt = NULL;

  idx_t *adjwgt = NULL;

  idx_t wgtflag = 0;

  idx_t numflag = 0;

  idx_t ncon_[] = {1};
  idx_t *ncon = ncon_;

  idx_t nparts_[] = {np};
  idx_t *nparts = nparts_;

  real_t *tpwgts = new real_t[np*ncon[0]]; for(int i=0; i<np*ncon[0]; i++) {tpwgts[i] = 1.0/np;}

  real_t ubvec_[] = {1.05};
  real_t *ubvec = ubvec_;

  idx_t options_[] ={0, 0, 0};
  idx_t *options =options_;

  idx_t edgecut;
  idx_t *part;

  ParMETIS_V3_PartKway(vtxdist,xadj,adjncy, vwgt, adjwgt, &wgtflag, &numflag, ncon, nparts, tpwgts, ubvec, options, &edgecut, part, &comm);
  int rnvtxs,i,penum;
  MPI_Status status;
  if (rank == 0) {
    idx_t count = 0;
    for (i=0; i<vtxdist[1]; i++)
    {
      printf("part[%"PRIDX"] = %"PRIDX"\n", count, part[i]);
      count++;
    }
    for (penum=1; penum<npes; penum++) {
      rnvtxs = vtxdist[penum+1]-vtxdist[penum];
      int *rpart = new int[rnvtxs];
      MPI_Recv((int*)rpart, rnvtxs, IDX_T, penum, 1, comm, &status);

      for (i=0; i<rnvtxs; i++)
        {
          printf("part[%"PRIDX"] = %"PRIDX"\n", count, rpart[i]);
          count++;
        }
    }
  }
  else
    MPI_Send((int *)part, vtxdist[rank+1]-vtxdist[rank], IDX_T, 0, 1, comm); 

  MPI_Finalize();
  return 0;
}

Итак, используя это с опциями компиляции: 

ParMETIS_INCLUDES = /home/user/Documents/parmetis/include
METIS_INCLUDES = /home/user/Documents/metis/include
ParMETIS_LIBS = /home/user/Documents/parmetis/lib
METIS_LIBS = /home/user/Documents/metis/lib

INCLUDES = -I${ParMETIS_INCLUDES} -I${METIS_INCLUDES}
LFLAGS =  -L${ParMETIS_LIBS} -L${METIS_LIBS}

CC = mpic++

par: par.cpp
    ${CC}  -Wall -g $(INCLUDES) -o par.out par.cpp $(LFLAGS) -lparmetis -lmetis

clean:
    rm *.o *.out *~

Запуск с: 

mpiexec -np 4 ./par.out

У меня есть: 

part[0] = 0
part[1] = 0
part[2] = 3
part[3] = 1
part[4] = 2
part[5] = 2
part[6] = 3
part[7] = 1

И с графическим тестовым файлом 

8 10
2 5
1 6 3
2 7 4
3 8
1 6
5 2 7
6 3 8
7 4

С опцией 

mpiexec -np 4 ./parmetis test.graph 1 4 1 1 6 1

У меня есть 

0
0
1
3
2
2
1
3

Если я добавлю: 

ParMETIS_V3_RefineKway(vtxdist,xadj,adjncy, vwgt, adjwgt, &wgtflag, &numflag, ncon, nparts, tpwgts, ubvec, options, &edgecut, part, &comm);

после ParMETIS_V3_PartKway я получаю: 

part[0] = 0
part[1] = 0
part[2] = 1
part[3] = 1
part[4] = 2
part[5] = 2
part[6] = 3
part[7] = 3
...