Слияние кода завершено, страница обновится автоматически
/*
* @HEADER
*
* ***********************************************************************
*
* Zoltan Toolkit for Load-balancing, Partitioning, Ordering and Coloring
* Copyright 2012 Sandia Corporation
*
* Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
* the U.S. Government retains certain rights in this software.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* 3. Neither the name of the Corporation nor the names of the
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Questions? Contact Karen Devine kddevin@sandia.gov
* Erik Boman egboman@sandia.gov
*
* ***********************************************************************
*
* @HEADER
*/
/**************************************************************
* Basic example of using Zoltan to partition a graph.
***************************************************************/
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "zoltan.h"
static int numbering = 0;
/* Name of file containing graph to be partitioned */
static char *global_fname="graph/tinys7.graph";
//static char *global_fname="graph/soc-LiveJournal1.txt";
/* Structure to hold graph data
ZOLTAN_ID_TYPE is defined when Zoltan is compiled. It's size can
be obtained at runtime by a library call. (See zoltan_types.h).
*/
typedef struct{
int numMyVertices; /* total vertices in in my partition */
int numAllNbors; /* total number of neighbors of my vertices */
ZOLTAN_ID_TYPE *vertexGID; /* global ID of each of my vertices */
int *nborIndex; /* nborIndex[i] is location of start of neighbors for vertex i */
ZOLTAN_ID_TYPE *nborGID; /* nborGIDs[nborIndex[i]] is first neighbor of vertex i */
int *nborProc; /* process owning each nbor in nborGID */
float *fvwgts;
float *fadjwgt;
int *status;
} GRAPH_DATA;
/* Application defined query functions */
static int get_number_of_vertices(void *data, int *ierr);
static void get_vertex_list(void *data, int sizeGID, int sizeLID,
ZOLTAN_ID_PTR globalID, ZOLTAN_ID_PTR localID,
int wgt_dim, float *obj_wgts, int *ierr);
static void get_num_edges_list(void *data, int sizeGID, int sizeLID,
int num_obj,
ZOLTAN_ID_PTR globalID, ZOLTAN_ID_PTR localID,
int *numEdges, int *ierr);
static void get_edge_list(void *data, int sizeGID, int sizeLID,
int num_obj, ZOLTAN_ID_PTR globalID, ZOLTAN_ID_PTR localID,
int *num_edges,
ZOLTAN_ID_PTR nborGID, int *nborProc,
int wgt_dim, float *ewgts, int *ierr);
/* Functions to read graph in from file, distribute it, view it, handle errors */
static int get_next_line(FILE *fp, char *buf, int bufsize);
static int get_next_vertex(FILE *fp, int *vals);
static void input_file_error(int numProcs, int tag, int startProc);
static void showGraphPartitions(int myProc, int numIDs, ZOLTAN_ID_TYPE *GIDs, int *parts, int nparts);
static int read_input_file(int myRank, int numProcs, char *fname, GRAPH_DATA *myData);
static unsigned int simple_hash(unsigned int *key, unsigned int n);
static void sendToBelongProc(int myProc, GRAPH_DATA *graph, int numGlobalVertices,
int *parts, int nparts);
int main_1(int argc, char *argv[])
{
int i, rc;
float ver;
struct Zoltan_Struct *zz;
int changes, numGidEntries, numLidEntries, numImport, numExport;
int myRank, numProcs;
ZOLTAN_ID_PTR importGlobalGids, importLocalGids, exportGlobalGids, exportLocalGids;
int *importProcs, *importToPart, *exportProcs, *exportToPart;
int *parts = NULL;
FILE *fp;
GRAPH_DATA myGraph;
/******************************************************************
** Initialize MPI and Zoltan
******************************************************************/
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myRank);
MPI_Comm_size(MPI_COMM_WORLD, &numProcs);
rc = Zoltan_Initialize(argc, argv, &ver);
if (rc != ZOLTAN_OK){
printf("sorry...\n");
MPI_Finalize();
exit(0);
}
/******************************************************************
** Read graph from input file and distribute it
******************************************************************/
fp = fopen(global_fname, "r");
if (!fp){
if (myRank == 0) fprintf(stderr,"ERROR: Can not open %s\n",global_fname);
MPI_Finalize();
exit(1);
}
fclose(fp);
read_input_file(myRank, numProcs, global_fname, &myGraph);
/******************************************************************
** Create a Zoltan library structure for this instance of load
** balancing. Set the parameters and query functions that will
** govern the library's calculation. See the Zoltan User's
** Guide for the definition of these and many other parameters.
******************************************************************/
zz = Zoltan_Create(MPI_COMM_WORLD);
/* General parameters */
Zoltan_Set_Param(zz, "DEBUG_LEVEL", "0");
Zoltan_Set_Param(zz, "LB_METHOD", "GRAPH");
Zoltan_Set_Param(zz, "LB_APPROACH", "PARTITION");
Zoltan_Set_Param(zz, "NUM_GID_ENTRIES", "1");
Zoltan_Set_Param(zz, "NUM_LID_ENTRIES", "1");
Zoltan_Set_Param(zz, "RETURN_LISTS", "ALL");
/* Graph parameters */
Zoltan_Set_Param(zz, "CHECK_GRAPH", "2");
Zoltan_Set_Param(zz, "PHG_EDGE_SIZE_THRESHOLD", ".35"); /* 0-remove all, 1-remove none */
/* Query functions - defined in simpleQueries.h */
Zoltan_Set_Num_Obj_Fn(zz, get_number_of_vertices, &myGraph);
Zoltan_Set_Obj_List_Fn(zz, get_vertex_list, &myGraph);
Zoltan_Set_Num_Edges_Multi_Fn(zz, get_num_edges_list, &myGraph);
Zoltan_Set_Edge_List_Multi_Fn(zz, get_edge_list, &myGraph);
/******************************************************************
** Zoltan can now partition the simple graph.
** In this simple example, we assume the number of partitions is
** equal to the number of processes. Process rank 0 will own
** partition 0, process rank 1 will own partition 1, and so on.
******************************************************************/
rc = Zoltan_LB_Partition(zz, /* input (all remaining fields are output) */
&changes, /* 1 if partitioning was changed, 0 otherwise */
&numGidEntries, /* Number of integers used for a global ID */
&numLidEntries, /* Number of integers used for a local ID */
&numImport, /* Number of vertices to be sent to me */
&importGlobalGids, /* Global IDs of vertices to be sent to me */
&importLocalGids, /* Local IDs of vertices to be sent to me */
&importProcs, /* Process rank for source of each incoming vertex */
&importToPart, /* New partition for each incoming vertex */
&numExport, /* Number of vertices I must send to other processes*/
&exportGlobalGids, /* Global IDs of the vertices I must send */
&exportLocalGids, /* Local IDs of the vertices I must send */
&exportProcs, /* Process to which I send each of the vertices */
&exportToPart); /* Partition to which each vertex will belong */
if (rc != ZOLTAN_OK){
printf("sorry...\n");
MPI_Finalize();
Zoltan_Destroy(&zz);
exit(0);
}
/******************************************************************
** Visualize the graph partitioning before and after calling Zoltan.
******************************************************************/
parts = (int *)malloc(sizeof(int) * myGraph.numMyVertices);
for (i=0; i < myGraph.numMyVertices; i++){
parts[i] = myRank;
}
if (myRank== 0){
printf("\nGraph partition before calling Zoltan\n");
}
showGraphPartitions(myRank, myGraph.numMyVertices, myGraph.vertexGID, parts, numProcs);
for (i=0; i < numExport; i++){
parts[exportLocalGids[i]] = exportToPart[i];
}
if (myRank == 0){
printf("Graph partition after calling Zoltan\n");
}
showGraphPartitions(myRank, myGraph.numMyVertices, myGraph.vertexGID, parts, numProcs);
if (parts) free(parts);
/******************************************************************
** Free the arrays allocated by Zoltan_LB_Partition, and free
** the storage allocated for the Zoltan structure.
******************************************************************/
Zoltan_LB_Free_Part(&importGlobalGids, &importLocalGids,
&importProcs, &importToPart);
Zoltan_LB_Free_Part(&exportGlobalGids, &exportLocalGids,
&exportProcs, &exportToPart);
Zoltan_Destroy(&zz);
/**********************
** all done ***********
**********************/
MPI_Finalize();
if (myGraph.numMyVertices > 0){
free(myGraph.vertexGID);
free(myGraph.nborIndex);
if (myGraph.numAllNbors > 0){
free(myGraph.nborGID);
free(myGraph.nborProc);
}
}
return 0;
}
/* Application defined query functions */
static int get_number_of_vertices(void *data, int *ierr)
{
GRAPH_DATA *graph = (GRAPH_DATA *)data;
*ierr = ZOLTAN_OK;
return graph->numMyVertices;
}
static void get_vertex_list(void *data, int sizeGID, int sizeLID,
ZOLTAN_ID_PTR globalID, ZOLTAN_ID_PTR localID,
int wgt_dim, float *obj_wgts, int *ierr)
{
int i;
GRAPH_DATA *graph = (GRAPH_DATA *)data;
*ierr = ZOLTAN_OK;
/* In this example, return the IDs of our vertices, but no weights.
* Zoltan will assume equally weighted vertices.
*/
for (i=0; i<graph->numMyVertices; i++){
globalID[i] = graph->vertexGID[i];
localID[i] = i;
}
}
static void get_num_edges_list(void *data, int sizeGID, int sizeLID,
int num_obj,
ZOLTAN_ID_PTR globalID, ZOLTAN_ID_PTR localID,
int *numEdges, int *ierr)
{
int i, idx;
GRAPH_DATA *graph = (GRAPH_DATA *)data;
if ( (sizeGID != 1) || (sizeLID != 1) || (num_obj != graph->numMyVertices)){
*ierr = ZOLTAN_FATAL;
return;
}
for (i=0; i < num_obj ; i++){
idx = localID[i];
numEdges[i] = graph->nborIndex[idx+1] - graph->nborIndex[idx];
}
*ierr = ZOLTAN_OK;
return;
}
static void get_edge_list(void *data, int sizeGID, int sizeLID,
int num_obj, ZOLTAN_ID_PTR globalID, ZOLTAN_ID_PTR localID,
int *num_edges,
ZOLTAN_ID_PTR nborGID, int *nborProc,
int wgt_dim, float *ewgts, int *ierr)
{
int i, j, from, to;
int *nextProc;
ZOLTAN_ID_TYPE *nextNbor;
GRAPH_DATA *graph = (GRAPH_DATA *)data;
*ierr = ZOLTAN_OK;
if ( (sizeGID != 1) || (sizeLID != 1) ||
(num_obj != graph->numMyVertices)||
(wgt_dim != 0)){
*ierr = ZOLTAN_FATAL;
return;
}
nextNbor = nborGID;
nextProc = nborProc;
for (i=0; i < num_obj; i++){
/*
* In this example, we are not setting edge weights. Zoltan will
* set each edge to weight 1.0.
*/
to = graph->nborIndex[localID[i]+1];
from = graph->nborIndex[localID[i]];
if ((to - from) != num_edges[i]){
*ierr = ZOLTAN_FATAL;
return;
}
for (j=from; j < to; j++){
*nextNbor++ = graph->nborGID[j];
*nextProc++ = graph->nborProc[j];
}
}
return;
}
/* Function to find next line of information in input file */
static int get_next_line(FILE *fp, char *buf, int bufsize)
{
int i, cval, len;
char *c;
while (1){
c = fgets(buf, bufsize, fp);
if (c == NULL)
return 0; /* end of file */
len = strlen(c);
for (i=0, c=buf; i < len; i++, c++){
cval = (int)*c;
if (isspace(cval) == 0) break;
}
if (i == len) continue; /* blank line */
if (*c == '#') continue; /* comment */
if (c != buf){
strcpy(buf, c);
}
break;
}
return strlen(buf); /* number of characters */
}
/* Function to find next line of information in input file */
static int get_next_vertex(FILE *fp, int *val)
{
char buf[512];
char *c = buf;
int num, cval, i = 0, j = 0, len = 0, bufsize = 512;
while (1){
c = fgets(buf, bufsize, fp);
/* end of the file */
if (c == NULL) {
if (j > 2)
val[1] = j - 2;
return j;
}
len = strlen(c);
for (i=0, c=buf; i < len; i++, c++){
cval = (int)*c;
if (isspace(cval) == 0) break;
}
if (i == len) continue; /* blank line */
if (*c == '#') continue; /* comment */
int from, to;
num = sscanf(buf, "%d%*[^0-9]%d", &from, &to);
if (num != 2)
perror("输入文件格式错误.\n");
if (j > 0) {
if (from + numbering == val[0])
val[j++] = to + numbering;
else {
fseek(fp, -1 * len, SEEK_CUR);
break;
}
}
else {
/* BUG: 当0顶点没有出边, 但是有入边时, 所有顶点号也应该加1 */
if (from == 0) numbering = 1;
val[j++] = from + numbering, val[j++] = 0, val[j++] = to + numbering;
}
}
val[1] = j - 2;
return j;
}
/* Proc 0 notifies others of error and exits */
static void input_file_error(int numProcs, int tag, int startProc)
{
int i, val[2];
val[0] = -1; /* error flag */
fprintf(stderr,"ERROR in input file.\n");
for (i=startProc; i < numProcs; i++){
/* these procs have posted a receive for "tag" expecting counts */
MPI_Send(val, 2, MPI_INT, i, tag, MPI_COMM_WORLD);
}
for (i=1; i < startProc; i++){
/* these procs are done and waiting for ok-to-go */
MPI_Send(val, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
}
MPI_Finalize();
exit(1);
}
/* Draw the partition assignments of the objects */
static void showGraphPartitions(int myProc, int numIDs, ZOLTAN_ID_TYPE *GIDs, int *parts, int nparts)
{
int partAssign[25], allPartAssign[25];
int i, j, part, cuts, prevPart=-1;
float imbal, localImbal, sum;
int *partCount;
memset(partAssign, 0, sizeof(int) * 25);
for (i=0; i < numIDs; i++){
printf("===>partAssign[%d-1]=parts[%d](%d)\n", GIDs[i], parts[i], parts[i]);
partAssign[GIDs[i]-1] = parts[i];
}
MPI_Reduce(partAssign, allPartAssign, 25, MPI_INT, MPI_MAX, 0, MPI_COMM_WORLD);
if (myProc == 0){
partCount = (int *)calloc(sizeof(int), nparts);
cuts = 0;
for (i=20; i >= 0; i-=5){
for (j=0; j < 5; j++){
part = allPartAssign[i + j];
partCount[part]++;
if (j > 0){
if (part == prevPart){
printf("-----%d",part);
}
else{
printf("--x--%d",part);
cuts++;
prevPart = part;
}
}
else{
printf("%d",part);
prevPart = part;
}
}
printf("\n");
if (i > 0){
for (j=0; j < 5; j++){
if (allPartAssign[i+j] != allPartAssign[i+j-5]){
printf("x ");
cuts++;
}
else{
printf("| ");
}
}
printf("\n");
}
}
printf("\n");
for (sum=0, i=0; i < nparts; i++){
sum += partCount[i];
}
imbal = 0;
for (i=0; i < nparts; i++){
/* An imbalance measure. 1.0 is perfect balance, larger is worse */
localImbal = (nparts * partCount[i]) / sum;
if (localImbal > imbal) imbal = localImbal;
}
printf("Object imbalance (1.0 perfect, larger numbers are worse): %f\n",imbal);
printf("Total number of edge cuts: %d\n\n",cuts);
if (nparts) free(partCount);
}
}
/*
* Read the graph in the input file and distribute the vertices.
*/
int read_input_file(int myRank, int numProcs, char *fname, GRAPH_DATA *graph)
{
char buf[512];
int bufsize;
int numGlobalVertices, numGlobalNeighbors;
int num, nnbors, ack=0;
int vGID;
int i, j, procID;
int vals[102400], send_count[2];
int *idx;
unsigned int id;
FILE *fp;
MPI_Status status;
int ack_tag = 5, count_tag = 10, id_tag = 15;
GRAPH_DATA *send_graph;
if (myRank == 0){
bufsize = 512;
fp = fopen(fname, "r");
/* Get the number of vertices */
num = get_next_line(fp, buf, bufsize);
numGlobalVertices = num;
if (num == 0) input_file_error(numProcs, count_tag, 1);
num = sscanf(buf, "%d", &numGlobalVertices);
if (num != 1) input_file_error(numProcs, count_tag, 1);
/* Get the number of vertex neighbors */
num = get_next_line(fp, buf, bufsize);
if (num == 0) input_file_error(numProcs, count_tag, 1);
num = sscanf(buf, "%d", &numGlobalNeighbors);
if (num != 1) input_file_error(numProcs, count_tag, 1);
/* Allocate arrays to read in entire graph */
graph->vertexGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * numGlobalVertices);
graph->nborIndex = (int *)malloc(sizeof(int) * (numGlobalVertices + 1));
graph->nborGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * numGlobalNeighbors);
graph->nborProc = (int *)malloc(sizeof(int) * numGlobalNeighbors);
graph->nborIndex[0] = 0;
int old_vid = 1;
for (i=0; i < numGlobalVertices; i++){
// num = get_next_line(fp, buf, bufsize);
// if (num == 0) input_file_error(numProcs, count_tag, 1);
//
// num = get_line_ints(buf, strlen(buf), vals);
//
// if (num < 2) input_file_error(numProcs, count_tag, 1);
num = get_next_vertex(fp, vals);
/*if (num != 0 && vals[0] == old_vid && old_vid != 1) {
printf("error input file.\n");
MPI_Finalize();
exit(1);
}*/
// printf("get num:%d\n", num);
if (num == 0) {
for (j = 1; i < numGlobalVertices; j++, i++) {
vGID = vals[0] + j;
nnbors = 0;
// printf("==Fill gap:%d 0\n", vGID);
graph->vertexGID[i] = (ZOLTAN_ID_TYPE)vGID;
graph->nborIndex[i+1] = graph->nborIndex[i] + nnbors;
}
break;
}
/*if (num < 2) input_file_error(numProcs, count_tag, 1);
for (k = 0; k < num; k++) {
printf("%d ", vals[k]);
}
printf("\n");*/
// printf("======>after get from point:%d\n", vals[0]);
/* 如果读取的图顶点的id, 与前一个读取的图顶点id不连续, 则需要补足中间不连续部分 */
if (vals[0] - old_vid > 1) {
if (vals[0] > numGlobalVertices) {
perror("读取的图顶点id大于了图的最大顶点数.\n");
MPI_Finalize();
exit(1);
}
for (j = vals[0] - old_vid - 1; j > 0; j--, i++) {
vGID = vals[0] - j;
nnbors = 0;
// printf("Fill gap:%d 0\n", vGID);
graph->vertexGID[i] = (ZOLTAN_ID_TYPE)vGID;
graph->nborIndex[i+1] = graph->nborIndex[i] + nnbors;
}
}
old_vid = vals[0];
vGID = vals[0];
nnbors = vals[1];
if (num < (nnbors + 2)) input_file_error(numProcs, count_tag, 1);
graph->vertexGID[i] = (ZOLTAN_ID_TYPE)vGID;
for (j=0; j < nnbors; j++){
graph->nborGID[graph->nborIndex[i] + j] = (ZOLTAN_ID_TYPE)vals[2 + j];
}
graph->nborIndex[i+1] = graph->nborIndex[i] + nnbors;
}
printf("成功读取文件, 开始随机分布顶点...\n");
fclose(fp);
/* Assign each vertex to a process using a hash function */
for (i=0; i <numGlobalNeighbors; i++){
id = (unsigned int)graph->nborGID[i];
graph->nborProc[i] = simple_hash(&id, numProcs);
}
/* Create a sub graph for each process */
send_graph = (GRAPH_DATA *)calloc(sizeof(GRAPH_DATA) , numProcs);
for (i=0; i < numGlobalVertices; i++){
id = (unsigned int)graph->vertexGID[i];
procID = simple_hash(&id, numProcs);
send_graph[procID].numMyVertices++;
}
for (i=0; i < numProcs; i++){
num = send_graph[i].numMyVertices;
send_graph[i].vertexGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * num);
send_graph[i].nborIndex = (int *)calloc(sizeof(int) , (num + 1));
}
/* 新增注释: 用来缓存目前为止各个进程已放入的顶点数 */
idx = (int *)calloc(sizeof(int), numProcs);
for (i=0; i < numGlobalVertices; i++){
id = (unsigned int)graph->vertexGID[i];
nnbors = graph->nborIndex[i+1] - graph->nborIndex[i];
procID = simple_hash(&id, numProcs);
j = idx[procID];
send_graph[procID].vertexGID[j] = (ZOLTAN_ID_TYPE)id;
send_graph[procID].nborIndex[j+1] = send_graph[procID].nborIndex[j] + nnbors;
idx[procID] = j+1;
}
for (i=0; i < numProcs; i++){
num = send_graph[i].nborIndex[send_graph[i].numMyVertices];
send_graph[i].nborGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * num);
send_graph[i].nborProc= (int *)malloc(sizeof(int) * num);
send_graph[i].numAllNbors = num;
}
memset(idx, 0, sizeof(int) * numProcs);
for (i=0; i < numGlobalVertices; i++){
id = (unsigned int)graph->vertexGID[i];
nnbors = graph->nborIndex[i+1] - graph->nborIndex[i];
procID = simple_hash(&id, numProcs);
j = idx[procID];
if (nnbors > 0){
memcpy(send_graph[procID].nborGID + j, graph->nborGID + graph->nborIndex[i],
nnbors * sizeof(ZOLTAN_ID_TYPE));
memcpy(send_graph[procID].nborProc + j, graph->nborProc + graph->nborIndex[i],
nnbors * sizeof(int));
idx[procID] = j + nnbors;
}
}
free(idx);
/* Process zero sub-graph */
free(graph->vertexGID);
free(graph->nborIndex);
free(graph->nborGID);
free(graph->nborProc);
*graph = send_graph[0];
// printf("========>图的随机划分完成.\n");
/* Send other processes their subgraph */
for (i=1; i < numProcs; i++){
send_count[0] = send_graph[i].numMyVertices;
send_count[1] = send_graph[i].numAllNbors;
MPI_Send(send_count, 2, MPI_INT, i, count_tag, MPI_COMM_WORLD);
MPI_Recv(&ack, 1, MPI_INT, i, ack_tag, MPI_COMM_WORLD, &status);
if (send_count[0] > 0){
MPI_Send(send_graph[i].vertexGID, send_count[0], ZOLTAN_ID_MPI_TYPE, i, id_tag, MPI_COMM_WORLD);
free(send_graph[i].vertexGID);
MPI_Send(send_graph[i].nborIndex, send_count[0] + 1, MPI_INT, i, id_tag + 1, MPI_COMM_WORLD);
free(send_graph[i].nborIndex);
if (send_count[1] > 0){
MPI_Send(send_graph[i].nborGID, send_count[1], ZOLTAN_ID_MPI_TYPE, i, id_tag + 2, MPI_COMM_WORLD);
free(send_graph[i].nborGID);
MPI_Send(send_graph[i].nborProc, send_count[1], MPI_INT, i, id_tag + 3, MPI_COMM_WORLD);
free(send_graph[i].nborProc);
}
}
}
free(send_graph);
/* signal all procs it is OK to go on */
ack = 0;
for (i=1; i < numProcs; i++){
MPI_Send(&ack, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
}
// printf("========>随机划分的图成功发往其他各部分.\n");
}
else{
MPI_Recv(send_count, 2, MPI_INT, 0, count_tag, MPI_COMM_WORLD, &status);
if (send_count[0] < 0){
MPI_Finalize();
exit(1);
}
ack = 0;
graph->numMyVertices = send_count[0];
graph->numAllNbors = send_count[1];
if (send_count[0] > 0){
graph->vertexGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * send_count[0]);
graph->nborIndex = (int *)malloc(sizeof(int) * (send_count[0] + 1));
if (send_count[1] > 0){
graph->nborGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * send_count[1]);
graph->nborProc = (int *)malloc(sizeof(int) * send_count[1]);
}
}
MPI_Send(&ack, 1, MPI_INT, 0, ack_tag, MPI_COMM_WORLD);
if (send_count[0] > 0){
MPI_Recv(graph->vertexGID,send_count[0],ZOLTAN_ID_MPI_TYPE, 0, id_tag, MPI_COMM_WORLD, &status);
MPI_Recv(graph->nborIndex,send_count[0] + 1, MPI_INT, 0, id_tag + 1, MPI_COMM_WORLD, &status);
if (send_count[1] > 0){
MPI_Recv(graph->nborGID,send_count[1], ZOLTAN_ID_MPI_TYPE, 0, id_tag + 2, MPI_COMM_WORLD, &status);
MPI_Recv(graph->nborProc,send_count[1], MPI_INT, 0, id_tag + 3, MPI_COMM_WORLD, &status);
}
}
/* ok to go on? */
MPI_Recv(&ack, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
if (ack < 0){
MPI_Finalize();
exit(1);
}
// printf("========>Process %d 成功接收来自process 0 发来的随机图.\n", myRank);
}
printf("成功将顶点随机分布到各个processor...\n");
return numGlobalVertices;
}
unsigned int simple_hash(unsigned int *key, unsigned int n)
{
unsigned int h, rest, *p, bytes, num_bytes;
char *byteptr;
num_bytes = (unsigned int) sizeof(int);
/* First hash the int-sized portions of the key */
h = 0;
for (p = (unsigned int *)key, bytes=num_bytes;
bytes >= (unsigned int) sizeof(int);
bytes-=sizeof(int), p++){
h = (h*2654435761U) ^ (*p);
}
/* Then take care of the remaining bytes, if any */
rest = 0;
for (byteptr = (char *)p; bytes > 0; bytes--, byteptr++){
rest = (rest<<8) | (*byteptr);
}
/* Merge the two parts */
if (rest)
h = (h*2654435761U) ^ rest;
/* Return h mod n */
return (h%n);
}
/* 将子图的各个顶点发送到对应进程上 */
static void sendToBelongProc(int myProc, GRAPH_DATA *graph, int numGlobalVertices,
int *parts, int nparts)
{
int numIDs = graph->numMyVertices;
int numProcs = nparts;
int num, nnbors, ack=0;
int i, j, k, procID;
int send_count[3][2], recv_count[3][2];
int *idx;
unsigned int id;
MPI_Status status;
int ack_tag = 5, count_tag = 10, id_tag = 15;
// printf("Process %d before send to belongs:", myProc);
// for (i = 0; i < numIDs; i++)
// printf(" %d ", graph->vertexGID[i]);
// printf("\n");
GRAPH_DATA *send_graph = (GRAPH_DATA *)calloc(sizeof(GRAPH_DATA) , numProcs);
GRAPH_DATA *recv_graph[nparts];
// printf("Process %d parts:", myProc);
for (i = 0; i < numGlobalVertices + 1; i++) {
// printf(" %d ", parts[i]);
//send_graph[parts[i]].numMyVertices++;
if (parts[i] != -1)
send_graph[parts[i]].numMyVertices++;
}
// printf("\n");
for (i=0; i < numProcs; i++){
num = send_graph[i].numMyVertices;
send_graph[i].vertexGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * num);
send_graph[i].nborIndex = (int *)calloc(sizeof(int) , (num + 1));
}
/* 新增注释: 用来缓存目前为止各个进程已放入的顶点数 */
idx = (int *)calloc(sizeof(int), numProcs);
for (i=0; i < numIDs; i++) {
id = (unsigned int)graph->vertexGID[i];
nnbors = graph->nborIndex[i+1] - graph->nborIndex[i];
procID = parts[graph->vertexGID[i]]; //parts[i]; //simple_hash(&id, numProcs);
j = idx[procID];
send_graph[procID].vertexGID[j] = (ZOLTAN_ID_TYPE)id;
send_graph[procID].nborIndex[j+1] = send_graph[procID].nborIndex[j] + nnbors;
idx[procID] = j+1;
}
for (i=0; i < numProcs; i++){
num = send_graph[i].nborIndex[send_graph[i].numMyVertices];
send_graph[i].nborGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * num);
send_graph[i].nborProc = (int *)malloc(sizeof(int) * num);
send_graph[i].numAllNbors = num;
}
memset(idx, 0, sizeof(int) * numProcs);
for (i=0; i < numIDs; i++){
id = (unsigned int)graph->vertexGID[i];
nnbors = graph->nborIndex[i+1] - graph->nborIndex[i];
procID = parts[graph->vertexGID[i]]; //parts[i]; //simple_hash(&id, numProcs);
j = idx[procID];
if (nnbors > 0){
memcpy(send_graph[procID].nborGID + j, graph->nborGID + graph->nborIndex[i],
nnbors * sizeof(ZOLTAN_ID_TYPE));
memcpy(send_graph[procID].nborProc + j, graph->nborProc + graph->nborIndex[i],
nnbors * sizeof(int));
idx[procID] = j + nnbors;
}
}
free(idx);
/* Process zero sub-graph */
free(graph->vertexGID);
free(graph->nborIndex);
free(graph->nborGID);
free(graph->nborProc);
// printf("Process %d send:", myProc);
// for (int i = 0; i < numProcs; i++) {
// printf(" (%d %d)", send_graph[i].numMyVertices, send_graph[i].numAllNbors);
// }
// printf("\n");
int *allparts = (int*)malloc((numGlobalVertices + 1) * sizeof(int));
MPI_Allreduce(parts, allparts, numGlobalVertices + 1, MPI_INT, MPI_MAX, MPI_COMM_WORLD);
// printf("Process %d allparts:", myProc);
// for (i = 0; i < numGlobalVertices + 1; i++)
// printf(" %d ", allparts[i]);
// printf("\n");
MPI_Barrier(MPI_COMM_WORLD);
//*graph = send_graph[myProc];
for (int i = 0; i < numProcs; i++) {
send_count[i][0] = send_graph[i].numMyVertices;
send_count[i][1] = send_graph[i].numAllNbors;
if (i != myProc) {
/* 交换vertex_counts和neighbor_counts */
MPI_Send(send_count[i], 2, MPI_INT, i, count_tag, MPI_COMM_WORLD);
MPI_Recv(recv_count[i], 2, MPI_INT, i, count_tag, MPI_COMM_WORLD, &status);
}
else {
recv_count[i][0] = send_count[i][0];
recv_count[i][1] = send_count[i][1];
}
}
// printf("Process %d recv:", myProc);
// for (int i = 0; i < numProcs; i++) {
// printf(" (%d %d)", recv_count[i][0], recv_count[i][1]);
// }
// printf("\n");
/* 同步并开始交换确认信息 */
MPI_Barrier(MPI_COMM_WORLD);
for (int i = 0; i < numProcs; i++) {
if (i != myProc) {
ack = 0;
MPI_Send(&ack, 1, MPI_INT, i, ack_tag, MPI_COMM_WORLD);
MPI_Recv(&ack, 1, MPI_INT, i, ack_tag, MPI_COMM_WORLD, &status);
}
}
for (int i = 0; i < numProcs; i++) {
if (i != myProc) {
recv_graph[i] = (GRAPH_DATA *)calloc(sizeof(GRAPH_DATA) , numProcs);
recv_graph[i]->vertexGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * recv_count[i][0]);
recv_graph[i]->nborIndex = (int *)malloc(sizeof(int) * (recv_count[i][0] + 1));
recv_graph[i]->numMyVertices = recv_count[i][0];
recv_graph[i]->numAllNbors = recv_count[i][0];
}
}
/* 同步并开始交换顶点信息: vertexGID */
MPI_Barrier(MPI_COMM_WORLD);
for (int i = 0; i < numProcs; i++) {
if (i != myProc) {
MPI_Send(send_graph[i].vertexGID, send_count[i][0], ZOLTAN_ID_MPI_TYPE, i, id_tag, MPI_COMM_WORLD);
MPI_Recv(recv_graph[i]->vertexGID,recv_count[i][0],ZOLTAN_ID_MPI_TYPE, i,id_tag, MPI_COMM_WORLD, &status);
free(send_graph[i].vertexGID);
}
}
// printf("Process %d recv ", myProc);
// for (int i = 0; i < numProcs; i++) {
// if (i != myProc) {
// printf(" from %d:", i);
// for (int j = 0; j < recv_count[i][0]; j++)
// printf(" %d ", recv_graph[i]->vertexGID[j]);
// }
// }
// printf("\n");
/* 同步并开始交换顶点邻居开始索引: nborIndex */
MPI_Barrier(MPI_COMM_WORLD);
for (int i = 0; i < numProcs; i++) {
if (i != myProc) {
MPI_Send(send_graph[i].nborIndex, send_count[i][0] + 1, MPI_INT, i, id_tag + 1, MPI_COMM_WORLD);
MPI_Recv(recv_graph[i]->nborIndex, recv_count[i][0] + 1, MPI_INT, i, id_tag + 1, MPI_COMM_WORLD, &status);
free(send_graph[i].nborIndex);
}
}
/* 同步并开始交换邻居: nborGID */
MPI_Barrier(MPI_COMM_WORLD);
for (int i = 0; i < numProcs; i++) {
if (i != myProc) {
recv_graph[i]->nborGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * recv_count[i][1]);
MPI_Send(send_graph[i].nborGID, send_count[i][1], ZOLTAN_ID_MPI_TYPE, i, id_tag+ 2, MPI_COMM_WORLD);
MPI_Recv(recv_graph[i]->nborGID, recv_count[i][1], ZOLTAN_ID_MPI_TYPE, i, id_tag + 2,
MPI_COMM_WORLD, &status);
free(send_graph[i].nborGID);
}
}
// printf("Process %d recv neighbor ", myProc);
// for (int i = 0; i < numProcs; i++) {
// if (i != myProc) {
// printf(" from %d:", i);
// for (int j = 0; j < recv_count[i][1]; j++)
// printf(" %d ", recv_graph[i]->nborGID[j]);
// }
// }
// printf("\n");
// /* 同步并开始交换邻居所在进程信息: nborProc */
// /* 同步过来的数据是错误的, 不如不同步这个nborProc数据 */
// MPI_Barrier(MPI_COMM_WORLD);
// for (int i = 0; i < numProcs; i++) {
// if (i != myProc) {
// recv_graph[i]->nborProc = (int *)malloc(sizeof(int) * recv_count[i][1]);
// MPI_Send(send_graph[i].nborProc, send_count[i][1], MPI_INT, i, id_tag + 3, MPI_COMM_WORLD);
// MPI_Recv(recv_graph[i]->nborProc,recv_count[i][1], MPI_INT, i, id_tag + 3, MPI_COMM_WORLD, &status);
// free(send_graph[i].nborProc);
// }
// }
/*将从其他processor获取的子图归并为一个大的子图 */
//graph = (GRAPH_DATA *)calloc(sizeof(GRAPH_DATA) , numProcs);
graph->numMyVertices = 0;
graph->numAllNbors = 0;
for (int i = 0; i < numProcs; i++) {
graph->numMyVertices += recv_count[i][0];
graph->numAllNbors += recv_count[i][1];
}
/* 将进程号为自己进程号的子图不需要发送, 直接给接收子图, 以供合并 */
recv_graph[myProc] = &send_graph[myProc];
// printf("===>Process %d numMyVertices:%d, numAllNbors:%d\n", myProc, graph->numMyVertices, graph->numAllNbors);
/* 为生成的新的子图申请空间 */
graph->vertexGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * graph->numMyVertices);
graph->nborIndex = (int *)malloc(sizeof(int) * graph->numMyVertices + 1);
graph->nborGID = (ZOLTAN_ID_TYPE *)malloc(sizeof(ZOLTAN_ID_TYPE) * graph->numAllNbors);
graph->nborProc = (int *)malloc(sizeof(int) * graph->numAllNbors);
int mergeposition[numProcs];
memset(mergeposition, 0, sizeof(int) * numProcs);
for (int i = 0; i < graph->numMyVertices; i++) {
int minGID = INT_MAX, minVidPosition = 0;
for (int j = 0; j < numProcs; j++) {
if (mergeposition[j] < recv_graph[j]->numMyVertices) {
if (recv_graph[j]->vertexGID[mergeposition[j]] < minGID) {
// printf("Process %d ===>mergeposition[%d] < recv_graph[%d]->numMyVertices: %d < %d, %d < %d\n",
// myProc, j, j, mergeposition[j], recv_graph[j]->numMyVertices,
// recv_graph[j]->vertexGID[mergeposition[j]], minGID);
minVidPosition = j;
minGID = recv_graph[j]->vertexGID[mergeposition[j]];
}
}
}
/* 将值进行拷贝 */
int nnbors = recv_graph[minVidPosition]->nborIndex[mergeposition[minVidPosition] + 1] -
recv_graph[minVidPosition]->nborIndex[mergeposition[minVidPosition]];
// printf("Process %d min vid %d(neighbor:%d) at %d\n", myProc, minGID, nnbors, minVidPosition);
graph->vertexGID[i] = recv_graph[minVidPosition]->vertexGID[mergeposition[minVidPosition]];
memcpy(graph->nborGID + graph->nborIndex[i], recv_graph[minVidPosition]->nborGID +
recv_graph[minVidPosition]->nborIndex[mergeposition[minVidPosition]],
sizeof(ZOLTAN_ID_TYPE) * nnbors);
// printf("=====>Process %d graph->nborProc + graph->nborIndex[%d]:%d\n", myProc, i, graph->nborIndex[i]);
// memcpy(graph->nborProc + graph->nborIndex[i], recv_graph[minVidPosition]->nborProc +
// recv_graph[minVidPosition]->nborIndex[mergeposition[minVidPosition]],
// sizeof(int) * nnbors);
graph->nborIndex[i + 1] = graph->nborIndex[i] + nnbors;
for (k = graph->nborIndex[i]; k < graph->nborIndex[i + 1]; k++)
graph->nborProc[k] = allparts[graph->nborGID[k]];
mergeposition[minVidPosition]++;
}
if (allparts) free(allparts);
for (int i = 0; i < numProcs; i++) {
free(recv_graph[i]->vertexGID);
free(recv_graph[i]->nborIndex);
free(recv_graph[i]->nborGID);
free(recv_graph[i]->nborProc);
}
if (INFO) {
printf("Process %d :", myProc);
for (i = 0; i < graph->numMyVertices; i++) {
printf(" %d", graph->vertexGID[i]);
printf("-->(");
for (j = graph->nborIndex[i]; j < graph->nborIndex[i + 1]; j++)
printf("%d@%d ", graph->nborGID[j], graph->nborProc[j]);
printf(") ");
}
printf("\n");
}
}
void graph_free(GRAPH_DATA *myGraph) {
if (myGraph->numMyVertices > 0){
free(myGraph->vertexGID);
free(myGraph->nborIndex);
if (myGraph->numAllNbors > 0){
free(myGraph->nborGID);
free(myGraph->nborProc);
}
free(myGraph->fvwgts);
free(myGraph->fadjwgt);
free(myGraph->status);
}
}
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )