Advertisement
Guest User

Untitled

a guest
Nov 18th, 2016
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.69 KB | None | 0 0
  1. #include <mpi.h>
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <math.h>
  6. #include <iostream>
  7. #include <stdlib.h>
  8. #include <utility>
  9. #include <time.h>
  10. #include <stddef.h>
  11. using namespace std;
  12.  
  13. template<typename T>
  14. struct tree_element {
  15. tree_element* parent;
  16. T elem;
  17. int operation_counter;
  18. int rank;
  19. tree_element(T e) {
  20. operation_counter = 0;
  21. elem = e;
  22. parent = this;
  23. rank = 0;
  24. }
  25. tree_element() {
  26. elem = 0;
  27. parent = this;
  28. rank = 0;
  29. }
  30. tree_element* Union(tree_element& e) {
  31. tree_element* a = find_set(this);
  32. tree_element* b = find_set(&e);
  33. e.operation_counter++;
  34. if(a->rank > b->rank) {
  35. b->parent = a;
  36. } else {
  37. a->parent = b;
  38. if(rank == e.rank) {
  39. b->rank++;
  40. }
  41. }
  42. return parent;
  43. }
  44. static tree_element* find_set(tree_element* e);
  45. void print() {
  46. tree_element* current = this;
  47. printf("%d\n", current->elem);
  48. while(current != current->parent) {
  49. current = current->parent;
  50. printf("%d\n", current->elem);
  51. }
  52. }
  53. };
  54.  
  55. template<typename T>
  56. tree_element<T>* tree_element<T>::find_set(tree_element<T>* e) {
  57. e->operation_counter++;
  58. if (e != e->parent) {
  59. e->parent = find_set(e->parent);
  60. e->operation_counter++;
  61. }
  62. return e->parent;
  63. }
  64.  
  65.  
  66.  
  67. struct Edge{
  68. int in;
  69. int out;
  70. double cost;
  71. int used;
  72. int range;
  73. int inconsistent;
  74. };
  75.  
  76. struct Node {
  77. double x;
  78. double y;
  79. int id;
  80. };
  81.  
  82. double getDistance(Node& n1, Node& n2) {
  83. return sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y));
  84. }
  85.  
  86. long long int operation_counter = 0;
  87.  
  88. bool operator<(const Edge &e1, const Edge &e2) {
  89. operation_counter++;
  90. return e1.cost < e2.cost;
  91. }
  92.  
  93. void null_element_usage(vector<Edge> edges_vector) {
  94. std::vector<Edge>::iterator it = edges_vector.begin();
  95. for(;it!=edges_vector.end(); it++) {
  96. it->used = false;
  97. }
  98. }
  99.  
  100. void null_element_usage(Edge* edges_vector, int size) {
  101. for(int i = 0; i < size; i++) {
  102. edges_vector[i].used = false;
  103. }
  104. }
  105.  
  106. void unnull_element_usage(Edge* edges_vector, int size) {
  107. for(int i = 0; i < size; i++) {
  108. edges_vector[i].used = false;
  109. }
  110. }
  111.  
  112. Edge* concat_arrays(Edge* arr1, Edge* arr2, int size1, int size2) {
  113. Edge* new_edges = new Edge[size1+size2];
  114. copy(arr1, arr1 + size1, new_edges);
  115. copy(arr2, arr2 + size2, new_edges + size1);
  116. return new_edges;
  117. }
  118.  
  119. pair<Edge*,int> run_MST(Edge* edges, int N, int size) {
  120. vector<Edge> edges_vector;
  121. for(int i = 0; i < size; i++) {
  122. edges_vector.push_back(edges[i]);
  123. }
  124. sort(edges_vector.begin(), edges_vector.end());
  125. tree_element<int>* elements = new tree_element<int>[N];
  126. std::vector<Edge>::iterator it = edges_vector.begin();
  127. int operation_counter = 0;
  128. int len = 0;
  129. Edge* edges_recieved = new Edge[2*N];
  130. for(;it != edges_vector.end();it++) {
  131. operation_counter++;
  132. if(!it->used && tree_element<int>::find_set(&elements[it->in]) != tree_element<int>::find_set(&elements[it->out])) {
  133. it->used = true;
  134. it->range = len;
  135. elements[it->in].Union(elements[it->out]);
  136. edges_recieved[len] = *it;
  137. len++;
  138. operation_counter++;
  139. }
  140. }
  141. for(int kk = 0; kk < N; kk++) {
  142. operation_counter += elements[kk].operation_counter;
  143. }
  144. delete [] elements;
  145. return make_pair(edges_recieved, len);
  146. }
  147.  
  148. int main(int argc, char **argv) {
  149. const int tag = 13;
  150. int rank, wsize;
  151. MPI_Init (&argc, &argv); /* starts MPI */
  152. MPI_Comm_rank (MPI_COMM_WORLD, &rank); /* get current process id */
  153. MPI_Comm_size (MPI_COMM_WORLD, &wsize); /* get number of processes */
  154. int highest_rank = 0;
  155. int size = wsize - 1;
  156. while(size/2 > 0) {
  157. highest_rank++;
  158. size = size / 2;
  159. }
  160. size = wsize - 1;
  161. int number_of_processes = wsize;
  162. //construct Edge type
  163. const int nitems=6;
  164. int blocklengths[6] = {1,1,1,1,1,1};
  165. MPI_Datatype types[6] = {MPI_INT, MPI_INT, MPI_DOUBLE, MPI_INT, MPI_INT, MPI_INT};
  166. MPI_Datatype mpi_edge;
  167. MPI_Aint offsets[6];
  168. offsets[0] = offsetof(struct Edge, in);
  169. offsets[1] = offsetof(struct Edge, out);
  170. offsets[2] = offsetof(struct Edge, cost);
  171. offsets[3] = offsetof(struct Edge, used);
  172. offsets[4] = offsetof(struct Edge, range);
  173. offsets[5] = offsetof(struct Edge, inconsistent);
  174. MPI_Type_create_struct(nitems, blocklengths, offsets, types, &mpi_edge);
  175. MPI_Type_commit(&mpi_edge);
  176. //construct Node type
  177. const int nitems_=3;
  178. int blocklengths_[6] = {1,1,1};
  179. MPI_Datatype types_[3] = {MPI_DOUBLE, MPI_DOUBLE, MPI_INT};
  180. MPI_Datatype mpi_node;
  181. MPI_Aint offsets_[6];
  182. offsets_[0] = offsetof(struct Node, x);
  183. offsets_[1] = offsetof(struct Node, y);
  184. offsets_[2] = offsetof(struct Node, id);
  185. MPI_Type_create_struct(nitems_, blocklengths_, offsets_, types_, &mpi_node);
  186. MPI_Type_commit(&mpi_node);
  187. MPI_Status status;
  188. //main process
  189. if(rank == 0) {
  190. const clock_t begin_time = clock();
  191. int cases = 1;
  192. FILE* pf = fopen("./tests1000.txt","r");
  193. FILE* pfresult = fopen("./result.txt", "a");
  194. FILE* out_MST = fopen("./MST.txt", "w");
  195. FILE* out_clasters = fopen("./clasters.txt", "w");
  196. FILE* out_cluster_points = fopen("./cluster_points.txt", "w");
  197. int N;
  198. fscanf(pf,"%d", &N);
  199. int each = N / (number_of_processes - 1);
  200. tree_element<int>* elements = new tree_element<int>[N];
  201. Node* nodes = new Node[N];
  202. MPI_Bcast(&N, 1 , MPI_INT, 0, MPI_COMM_WORLD);
  203.  
  204. for(int j = 0; j < N; j++) {
  205. double x,y;
  206. fscanf(pf,"%lf %lf", &x, &y);
  207. Node n;
  208. n.x = x;
  209. n.y = y;
  210. n.id = j;
  211. elements[j].elem = j;
  212. nodes[j] = n;
  213. }
  214. MPI_Bcast(nodes, N , mpi_node, 0, MPI_COMM_WORLD);
  215. vector<Edge> edges_used;
  216. int full_size = 0;
  217. int result_size = 0;
  218. MPI_Recv(&result_size, 1 , MPI_INT, 1, tag, MPI_COMM_WORLD, &status);
  219. operation_counter++;
  220. Edge* edges_new_recieved = new Edge[result_size];
  221. MPI_Recv(edges_new_recieved, result_size , mpi_edge, 1, tag, MPI_COMM_WORLD, &status);
  222. operation_counter++;
  223. for(int k = 0; k < result_size; k++) {
  224. if(edges_new_recieved[k].used) {
  225. edges_used.push_back(edges_new_recieved[k]);
  226. full_size++;
  227. }
  228. }
  229. vector<Edge> edges_vector_;
  230. for(int j = 0; j < full_size; j++) {
  231. edges_used[j].used = false;
  232. edges_vector_.push_back(edges_used[j]);
  233. }
  234. delete [] elements;
  235. elements = new tree_element<int>[N];
  236. sort(edges_vector_.begin(), edges_vector_.end());
  237. std::vector<Edge>::iterator it = edges_vector_.begin();
  238. int len = 0;
  239. for(;it != edges_vector_.end();it++) {
  240. if(!it->used && tree_element<int>::find_set(&elements[it->in]) != tree_element<int>::find_set(&elements[it->out])) {
  241. it->used = true;
  242. len++;
  243. it->range = len;
  244. elements[it->in].Union(elements[it->out]);
  245. }
  246. }
  247. for(int kk = 0; kk < N; kk++) {
  248. operation_counter += elements[kk].operation_counter;
  249. }
  250. it = edges_vector_.begin();
  251. long long int* op_counts = new long long int [number_of_processes];
  252. long long int all_operation_counter = operation_counter;
  253. long long int new_counter;
  254. MPI_Recv(&new_counter, 1 , MPI_LONG_LONG_INT, 1, tag, MPI_COMM_WORLD, &status);
  255. operation_counter++;
  256. all_operation_counter += new_counter;
  257. double clusters = 10;
  258. fprintf(pfresult, "time: %lf ; number_of_processes: %d ; data vol: %d ; number of operations: %lld ; flops: %lf \n", float( clock () - begin_time ) / CLOCKS_PER_SEC, number_of_processes, N , all_operation_counter, all_operation_counter / (float( clock () - begin_time ) / CLOCKS_PER_SEC));
  259. for(;it != edges_vector_.end();it++) {
  260. if(it->used) {
  261. fprintf(out_MST, "%lf %lf %lf %lf %lf\n", nodes[it->in].x, nodes[it->in].y, nodes[it->out].x, nodes[it->out].y, it->cost);
  262. if(it->range <= len - clusters) {
  263. fprintf(out_clasters, "%lf %lf %lf %lf %lf\n", nodes[it->in].x, nodes[it->in].y, nodes[it->out].x, nodes[it->out].y, it->cost);
  264. } else {
  265. it->inconsistent = true;
  266. }
  267. }
  268. }
  269. it = edges_vector_.begin();
  270. tree_element<int>* elements_new = new tree_element<int>[N];
  271. for(;it != edges_vector_.end();it++) {
  272. if(it->used && !it->inconsistent) {
  273. elements_new[it->in].Union(elements_new[it->out]);
  274. }
  275. }
  276. for(int k = 0; k < N; k++) {
  277. elements_new[k].elem = k;
  278. }
  279. for(int k = 0; k < N; k++) {
  280. int cluster = tree_element<int>::find_set(&elements_new[k])->elem;
  281. fprintf(out_cluster_points, "%lf %lf %d\n", nodes[k].x, nodes[k].y, cluster);
  282. }
  283. delete [] elements_new;
  284. } else {
  285. int N;
  286. MPI_Bcast(&N, 1, MPI_INT, 0, MPI_COMM_WORLD);
  287. tree_element<int>* elements = new tree_element<int>[N];
  288. Node* nodes = new Node[N];
  289. int each = N / (number_of_processes - 1);
  290. MPI_Bcast(nodes, N , mpi_node, 0, MPI_COMM_WORLD);
  291. int len = 0;
  292. int result_start = N - each * (rank - 1);
  293. vector<Edge> edges_vector;
  294. for(int i = N - result_start; i < (N - (result_start - each)); i++) {
  295. operation_counter++;
  296. for(int j = i + 1; j < N; j++) {
  297. double dist = getDistance(nodes[i], nodes[j]);
  298. operation_counter++;
  299. Edge e;
  300. e.in = nodes[i].id;
  301. e.out = nodes[j].id;
  302. e.cost = dist;
  303. e.used = 0;
  304. e.inconsistent = 0;
  305. edges_vector.push_back(e);
  306. len++;
  307. }
  308. }
  309.  
  310. sort(edges_vector.begin(), edges_vector.end());
  311. std::vector<Edge>::iterator it = edges_vector.begin();
  312. Edge* edges_recieved = new Edge[2*N];
  313. int kk = len;
  314. len = 0;
  315. for(;it != edges_vector.end();it++) {
  316. operation_counter++;
  317. if(!it->used && tree_element<int>::find_set(&elements[it->in]) != tree_element<int>::find_set(&elements[it->out])) {
  318. it->used = true;
  319. it->range = len;
  320. elements[it->in].Union(elements[it->out]);
  321. edges_recieved[len] = *it;
  322. len++;
  323. operation_counter++;
  324. }
  325. }
  326. delete [] elements;
  327. for(int kk = 0; kk < N; kk++) {
  328. operation_counter += elements[kk].operation_counter;
  329. }
  330. operation_counter++;
  331. int mult = 1;
  332. while(highest_rank > 0) {
  333. mult*=2;
  334. highest_rank--;
  335. if((rank -1) % mult == 0) {
  336. int result_size = 0;
  337. MPI_Recv(&result_size, 1 , MPI_INT, rank+(mult/2), tag, MPI_COMM_WORLD, &status);
  338. Edge* edges_new_recieved = new Edge[result_size];
  339. MPI_Recv(edges_new_recieved, result_size , mpi_edge, rank+(mult/2), tag, MPI_COMM_WORLD, &status);
  340. long long int new_counter;
  341. MPI_Recv(&new_counter, 1 , MPI_LONG_LONG_INT, rank+(mult/2), tag, MPI_COMM_WORLD, &status);
  342. operation_counter += new_counter;
  343. Edge* concated_edges = concat_arrays(edges_recieved, edges_new_recieved, len, result_size);
  344. delete [] edges_recieved;
  345. delete [] edges_new_recieved;
  346. null_element_usage(concated_edges,len+result_size);
  347. pair<Edge*,int> result = run_MST(concated_edges, N, len+result_size);
  348. len = result.second;
  349. edges_recieved = result.first;
  350. } else {
  351. MPI_Send(&len, 1 , MPI_INT, rank-(mult/2), tag, MPI_COMM_WORLD);
  352. MPI_Send(edges_recieved, len , mpi_edge, rank-(mult/2), tag, MPI_COMM_WORLD);
  353. MPI_Send(&operation_counter, 1 , MPI_LONG_LONG_INT, rank-(mult/2), tag, MPI_COMM_WORLD);
  354. break;
  355. }
  356. }
  357. if(highest_rank ==0 && rank == 1) {
  358. MPI_Send(&len, 1 , MPI_INT, 0, tag, MPI_COMM_WORLD);
  359. MPI_Send(edges_recieved, len , mpi_edge, 0, tag, MPI_COMM_WORLD);
  360. MPI_Send(&operation_counter, 1 , MPI_LONG_LONG_INT, 0, tag, MPI_COMM_WORLD);
  361. }
  362. }
  363. MPI_Finalize();
  364. return 0;
  365. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement