Advertisement
Guest User

Untitled

a guest
Dec 3rd, 2016
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 6.60 KB | None | 0 0
  1. /*
  2.  * Kruskal's MPI
  3.  * Copyright (C) 2015 George Piskas
  4.  *
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 2 of the License, or
  8.  * (at your option) any later version.
  9.  *
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13.  * GNU General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU General Public License along
  16.  * with this program; if not, write to the Free Software Foundation, Inc.,
  17.  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18.  *
  19.  * Contact: geopiskas@gmail.com
  20.  */
  21.  
  22. #include <stdio.h>
  23. #include <stdlib.h>
  24. #include <mpi.h>
  25. #include <inttypes.h>
  26. #include <time.h>
  27. #include "edge.h"
  28. #include "disjointset.h"
  29.  
  30. FILE *input = NULL;
  31.  
  32. // MPI related variables.
  33. MPI_Datatype mpiEdge; // MPI datatype of edge.
  34. int mpiNp; // Total # of processors.
  35. int mpiRank; // Rank of a processor.
  36.  
  37. uint64_t nVerts; // Total # of vertices.
  38. uint64_t nEdges; // Total # of edges.
  39.  
  40. edge *edges; // Contains the edges of a processor.
  41. edge *edges_sort_buffer; // Used for parallel quicksorting of 'edges' for performance.
  42. uint64_t edgeCount;
  43.  
  44. edge *mst; // Contains the MST edges of a processor. Also used as send/recv MPI buffer.
  45. uint64_t mstEdgeCount;
  46. double mstLength;
  47.  
  48. // Timing variables.
  49. double commTime;
  50. double procTime;
  51. double parseTime;
  52.  
  53.  
  54. // Checks if (l  <=  x  <  r)
  55. /*inline int in(uint32_t x, uint32_t l, uint32_t r) {
  56.     return ((x >= l) && (x < r));
  57. }*/
  58.  
  59. // Finalizes MPI and frees buffers.
  60. inline void finalize() {
  61.     MPI_Type_free(&mpiEdge);
  62.     MPI_Finalize();
  63. }
  64.  
  65. // Force kill due to initialization error.
  66. inline void die(char *msg) {
  67.     printf("%d: %s\n",mpiRank, msg);
  68.     if (input != NULL) fclose(input);
  69.     MPI_Type_free(&mpiEdge);
  70.     MPI_Finalize();
  71.     exit(0);
  72. }
  73.  
  74. // Initializes MPI and mpiEdge datatype.
  75. inline void initMPI(int argc, char **argv) {
  76.     MPI_Init(&argc, &argv);
  77.     MPI_Comm_rank(MPI_COMM_WORLD, &mpiRank);
  78.     MPI_Comm_size(MPI_COMM_WORLD, &mpiNp);
  79.     MPI_Type_contiguous(3, MPI_UNSIGNED, &mpiEdge);
  80.     MPI_Type_commit(&mpiEdge);
  81. }
  82.  
  83. // Constructs a random graph.
  84. inline void initInput() {
  85.    
  86.     if ((mpiNp & (mpiNp - 1)) != 0)
  87.         die("* Please make sure that the number of processors is a power of 2\n");
  88.     nEdges = nVerts * (nVerts - 1) / 2;
  89.  
  90.     uint64_t ePerProc = nEdges/mpiNp; //Edges per processor
  91.     uint64_t firstEdge = mpiRank * ePerProc;
  92.     uint64_t lastEdge = (mpiRank + 1) * ePerProc;
  93.     if (mpiRank == mpiNp - 1) {
  94.         ePerProc += nEdges%mpiNp;
  95.         lastEdge += nEdges%mpiNp;
  96.     }
  97.    
  98.     // Mem allocation.
  99.     edges = malloc(ePerProc * sizeof(edge));
  100.    
  101.     // Allocating x2 because of merging. The first part of mst buffer contains the
  102.     // MST edges and the second part is used as a receive MPI buffer.
  103.     mst = malloc(2 * (nVerts - 1) * sizeof(edge));
  104.    
  105.     edgeCount = 0;
  106.     uint64_t count = 0;
  107.     uint64_t count2 = 0;
  108.     uint32_t i, j, minj, maxj;
  109.     edge e;
  110.     for (i = nVerts-1; i > 0; i--){
  111.         count2 += nVerts - i;
  112.         if (count2 < firstEdge){
  113.             count = count2;
  114.             continue;
  115.         }
  116.        
  117.         maxj = nVerts;
  118.         if (count2 > lastEdge)
  119.             maxj -= count2 - lastEdge;
  120.        
  121.         minj = i + 1;
  122.         if (count < firstEdge)
  123.             minj += firstEdge - count;
  124.        
  125.         for (j = minj; j <= maxj; j++) {
  126.             e.u = i-1;
  127.             e.v = j-1;
  128.             e.weight = drand48();
  129.             edges[edgeCount++] = e;
  130.         }
  131.         count = count2;
  132.         if (count >= lastEdge)
  133.             break;
  134.     }
  135.    
  136.     parseTime = MPI_Wtime() - parseTime;
  137.     MPI_Barrier(MPI_COMM_WORLD);
  138. }
  139.  
  140. // Calculates the MST.
  141. inline void calculateMst() {
  142.     // Quicksort.
  143.     qsort(edges, edgeCount, sizeof(edge), compareEdges);
  144.     free(dsSet);
  145.     dsMakeSet(nVerts);
  146.     // Looping trhough all edges in increasing weight order.
  147.     mstEdgeCount = 0;
  148.     mstLength = 0;
  149.     uint32_t i = 0;
  150.     for(; i < edgeCount; i++) {
  151.         // Find parent sets of the nodes.
  152.         dsNode *vParent = dsFind(&dsSet[edges[i].v]);
  153.         dsNode *uParent = dsFind(&dsSet[edges[i].u]);
  154.         // If they are from two different sets, merge them.
  155.         if(vParent != uParent) {
  156.             mst[mstEdgeCount++] = edges[i];
  157.             mstLength += edges[i].weight;
  158.             dsUnion(vParent, uParent);
  159.         }
  160.     }
  161. }
  162.  
  163. inline void processTree(int n) {
  164.    
  165.     parseTime = MPI_Wtime();
  166.     nVerts = n;
  167.     initInput();
  168.  
  169.     // Processing.
  170.     double tmpTime;
  171.     procTime = MPI_Wtime();
  172.     // In case of 1 processor, act as serial application.
  173.     if (mpiNp == 1) {
  174.         calculateMst();
  175.     } else {
  176.         int processors = mpiNp;
  177.         int pow2 = 1; // Used to find out where to send/recv.
  178.         MPI_Status mpiStatus;
  179.         int recvEdgeCount;
  180.         while(processors > 1) {
  181.             // Calculate the local MST using 'edges' buffer.
  182.             calculateMst();
  183.  
  184.             // Communication part.
  185.             if((mpiRank/pow2)%2 != 0) {
  186.                 // Send from the first half of 'mst'.
  187.                 MPI_Send(mst, mstEdgeCount, mpiEdge, (mpiRank-pow2), 0, MPI_COMM_WORLD);
  188.                 break; // Processor did his job and can now exit.
  189.             } else {
  190.                 // Receive into the second half of 'mst'.
  191.                 tmpTime = MPI_Wtime();
  192.                 MPI_Recv(mst+mstEdgeCount, nVerts-1, mpiEdge, (mpiRank+pow2), 0, MPI_COMM_WORLD, &mpiStatus);
  193.                 MPI_Get_count(&mpiStatus, mpiEdge, &recvEdgeCount);
  194.                 commTime += MPI_Wtime() - tmpTime; // Communication time is equal to the waiting-to-recv time.
  195.             }
  196.             // Pointer swap between 'edges' and 'mst'.
  197.             // 'edges' will be reused to calculate a new local MST.
  198.             // 'mst' will contain that new local MST.
  199.             edge *tmp = edges;
  200.             edges = mst;
  201.             mst = tmp;
  202.             edgeCount = mstEdgeCount + recvEdgeCount; // New edge count after merging.
  203.  
  204.             processors /= 2;
  205.             pow2 *= 2;
  206.         }
  207.  
  208.         // Only the root will execute this last calculation.
  209.         if(mpiRank == 0) calculateMst();
  210.     }
  211.     procTime = (MPI_Wtime() - procTime) - commTime;
  212.  
  213.     if(mpiRank == 0)
  214.         printf("%d nodes, %" PRIu64 " vertices: %.3fs\n", mpiNp, nVerts, parseTime + commTime + procTime);
  215.  
  216. }
  217.  
  218. int main (int argc, char **argv) {
  219.     initMPI(argc, argv);
  220.         int numv = 256;
  221.         if (argc > 1)
  222.                 numv = atoi(argv[1]);
  223.         srand48(time(NULL));
  224.         processTree(numv);
  225.         MPI_Barrier(MPI_COMM_WORLD);
  226.     finalize();
  227.         return 0;
  228. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement