API tools faq
paste
Guest User

Untitled

a guest
Jun 22nd, 2018
105
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.11 KB | None | 0 0
raw download clone embed print report
  1. MPI_Bcast(&lines, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
  2. MPI_Bcast(&width, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
  3. MPI_Bcast(&fillIn, 1, MPI_INT, ROOT, MPI_COMM_WORLD);
  4.  
  5. sum = (lines*width);
  6.  
  7. localLines = ((sum / width) / total);
  8. if (me == total-1) {
  9. localLines = (lines-(localLines*(total-1)));
  10. }
  11. int linesWidthSize = (localLines * width); // normale ChunkGroesse
  12. int absoluteStart = me * localLines; // absolute Startposition
  13. int absoluteEnd = absoluteStart + (linesWidthSize-1); // absolute Endposition
  14.  
  15.  
  16.  
  17. labChunk = (int*) malloc(linesWidthSize *sizeof(int)); // Laenge des Labyrinth-Teils
  18.  
  19.  
  20. int i, j, k, l;
  21.  
  22. printf("P%d: linesWidthSize = %d\n", me, linesWidthSize);
  23. printf("P%d: localLines = %d\n", me, localLines);
  24.  
  25. // Labyrinth in total Teile aufteilen an die Prozesse
  26. MPI_Scatter(labLine, linesWidthSize, MPI_INT, labChunk, linesWidthSize, MPI_INT, ROOT, MPI_COMM_WORLD);
  27.  
  28. MPI_Request request;
  29. MPI_Status status;
  30. MPI_Request request1;
  31. MPI_Status status1;
  32. MPI_Request request2;
  33. MPI_Status status2;
  34.  
  35. if (me == ROOT) {
  36. //printf(">> labChunkMax Array, %d, INT, an %d\n", maxLabChunkSize, (total-1));
  37. MPI_Isend(labChunkMax, maxLabChunkSize, MPI_INT, (total-1), 33, MPI_COMM_WORLD, &request);
  38. }
  39. if (me == (total-1)) {
  40. //printf("<< labChunk Array, %d, INT, von %d\n", linesWidthSize, ROOT);
  41. MPI_Recv(labChunk, linesWidthSize, MPI_INT, ROOT, 33, MPI_COMM_WORLD, &status);
  42. }
  43.  
  44. MPI_Barrier(MPI_COMM_WORLD);
  45.  
  46. // Jeder Prozess gibt sein lokales Labyrinth aus
  47. if (1) {
  48. for (i=0; i<total; i++) {
  49. if (me == i) {
  50. printf("P%d>>>>\n", me);
  51. showEmptyLab(labChunk, 1);
  52. }
  53. MPI_Barrier(MPI_COMM_WORLD);
  54. }
  55. }
  56.  
  57. printf("\n");
  58.  
  59. int *myOuts = (int*) malloc(sizeof(int) * width);
  60. int *hisOuts = (int*) malloc(sizeof(int) * width);
  61.  
  62. int *myIns = (int*) malloc(sizeof(int) * width);
  63. int *hisIns = (int*) malloc(sizeof(int) * width);
  64.  
  65. // Jeder schickt seine Ausgaenge an den naechstne damit dieser weiss wo die Eingaenge wirklich sind
  66.  
  67. for (j=0; j<width; j++) {
  68. int myOut, myIn;
  69. myOut = getValue((localLines-1), j);
  70. myIn = getValue(0, j);
  71. // Eingangsposition speichern
  72. if (myOut == fillIn) {
  73. //printf("P%d: Ausgang bei (%d, %d)\n", me, j, (localLines-1));
  74. myOuts[j] = fillIn;
  75. } else {
  76. myOuts[j] = 0;
  77. }
  78. //printf("P%d: bei (%d, %d) = [%d]\n", me, j, 0, myOut);
  79. if (myIn == fillIn) {
  80. //printf("P%d: Eingang bei (%d, %d)\n", me, j, 0);
  81. myIns[j] = fillIn;
  82. } else {
  83. myIns[j] = 0;
  84. }
  85.  
  86. //printf("P%d: bei (%d, %d) = [%d]\n", me, j, 0, myIn);
  87. }
  88. // an den naechsten schicken
  89. if (me != (total-1)) {
  90. MPI_Isend(myOuts, width, MPI_INT, (me+1), 22, MPI_COMM_WORLD, &request1);
  91. }
  92. if (me != ROOT) {
  93. MPI_Isend(myIns, width, MPI_INT, (me-1), 11, MPI_COMM_WORLD, &request2);
  94. }
  95.  
  96.  
  97. if (me != ROOT) {
  98. MPI_Recv(hisOuts, width, MPI_INT, (me-1), 22, MPI_COMM_WORLD, &status1);
  99. //printf("P%d: ich habe etwas empfangen!\n", me);
  100. for (i=0; i<width; i++) {
  101. if (hisOuts[i] == 1) {
  102. //printf("hisOuts[%d] = %d\n", i, hisOuts[i]);
  103. }
  104. }
  105. }
  106. if (me != (total-1)) {
  107. MPI_Recv(hisIns, width, MPI_INT, (me+1), 11, MPI_COMM_WORLD, &status2);
  108. //printf("P%d: ich habe etwas empfangen!\n", me);
  109. for (i=0; i<width; i++) {
  110. if (hisOuts[i] == 1) {
  111. //printf("hisOuts[%d] = %d\n", i, hisOuts[i]);
  112. }
  113. }
  114. }
  115.  
  116. MPI_Barrier(MPI_COMM_WORLD);
  117.  
  118.  
  119. // 1) labChunk (lokales Array) sichern
  120. // 2) Fuer jeden Eingang normal rekursiv durchsuchen, dabei Pfade abspeichern
  121. // 3) Wenn mehr als 1 Eingang existiert labChunk zurueckkopieren und weiter wie Schritt 2
  122.  
  123. // Pfade zusammenfuegen ....
  124.  
  125. // Teste getValue() Funktion
  126. if (0) {
  127. for (k=0; k<total; k++) {
  128. if (me == k) {
  129. for (i=0; i<localLines; i++) {
  130. for (j=0; j<width; j++) {
  131. int val = getValue(i,j);
  132. printf("%d", val);
  133. }
  134. printf("\n");
  135. }
  136. }
  137. MPI_Barrier(MPI_COMM_WORLD);
  138. }
  139. }
  140.  
  141. // Eingaenge bestimmen
  142.  
  143. realStart = (int*) calloc(width, sizeof(int));
  144. realEnd = (int*) calloc(width, sizeof(int));
  145.  
  146. int tmp;
  147. for (j=0; j<width; j++) {
  148. // echte Eingaenge
  149. tmp = getValue(0, j);
  150. if (me != ROOT) {
  151. if (hisOuts[j] == fillIn && tmp == fillIn) {
  152. realStart[j] = 1;
  153. printf("P%d: >>>>>>> echter Eingang [%d]\n", me, j);
  154. }
  155. } else {
  156. // ROOT hat nur einen Eingang !
  157. if (tmp == fillIn) {
  158. realStart[j] = 1;
  159. printf("P%d: >>>>>>> GLOBALER Eingang [%d]\n", me, j);
  160. }
  161. }
  162. MPI_Barrier(MPI_COMM_WORLD);
  163. // echte Ausgaenge
  164. tmp = getValue((localLines-1), j);
  165. if (me != (total-1)) {
  166.  
  167. if (hisIns[j] == fillIn && tmp == fillIn) {
  168. realEnd[j] = 1;
  169. printf("P%d: echter Ausgang [%d]\n", me, j);
  170. }
  171. } else {
  172. // P(last) hat nur einen Ausgang !
  173. if (tmp == fillIn) {
  174. realEnd[j] = 1;
  175. printf("P%d: >>>>>>> GLOBALER Ausgange [%d]\n", me, j);
  176. }
  177. }
  178. }
  179.  
  180.  
  181. if (me == 0) {
  182.  
  183. // Sicherheitskopie
  184. //int *copy = copyArray(labChunk, linesWidthSize);
  185. int *copy = (int*) malloc(linesWidthSize * sizeof(int));
  186. memcpy(copy, labChunk, linesWidthSize * sizeof(int));
  187.  
  188. // Pruefe fuer jeden Eingang den kuerzesten Weg
  189. for (i=0; i<width; i++) {
  190. if (realStart[i] == 1) {
  191. printf("Starte fuer (0,%d)\n", i);
  192. p1x = 0; p1y = i;
  193. shortestPath(labChunk, 0, 0, i);
  194. showLocalLab(labChunk, 20, 1);
  195. memcpy(labChunk, copy, linesWidthSize * sizeof(int));
  196. }
  197. }
  198.  
  199. // Pruefe auf Abschnite, die nicht an den Startknoten dranhaengen
  200. for (i=0; i<width; i++) {
  201. if (realEnd[i] == 1) {
  202. int result = searchStartPointInPath((localLines-1), i);
  203. if (result == 0) {
  204. printf("Starte (R) fuer (%d,%d)\n", (localLines-1), i);
  205. p1x = (localLines-1); p1y = i;
  206. shortestPath(labChunk, 0, (localLines-1), i);
  207. showLocalLab(labChunk, 20, 1);
  208. memcpy(labChunk, copy, linesWidthSize * sizeof(int));
  209. }
  210. }
  211. }
  212.  
  213. printf("PFADE folgen nun...\n");
  214. showPaths();
  215.  
  216. }
  217.  
  218.  
  219.  
  220. /* MPI Laufzeitsystem beenden */
  221. assert (MPI_Finalize() == MPI_SUCCESS);
  222.  
  223. // Kann wie ein 2D Array behandelt werden mit Zeilen und Spalten Indizes
  224.  
  225. return 0;
  226. }
  227.  
  228. int shortestPath (int* lab, int dist, int x, int y) {
  229.  
  230. dist += 1;
  231. int pos = ((x*width)+y);
  232.  
  233. if (x>=0 && x<localLines && y>=0 && y<lines && lab[pos] > dist) {
  234. //printf("Jap: (%d, %d) = [%d]\t\tlab[%d] = %d> %d\n", x, y, dist, pos, lab[pos], dist);
  235.  
  236. // pruefe in jede Richtung ob nicht ausserhalb des Labyrinths und ob der Weg laenger ist als jetzt
  237. // wenn ja dann rufe rekursiv auf:
  238.  
  239. lab[pos] = dist;
  240. // oben
  241. if (x>0 && lab[pos-width] > dist) {
  242. shortestPath(lab, dist, (x-1), y);
  243. }
  244. // unten
  245. if (x<(width-1) && lab[pos+width] > dist) {
  246. shortestPath(lab, dist, (x+1), y);
  247. }
  248. // links
  249. if (y>0 && lab[pos-1] > dist) {
  250. shortestPath(lab, dist, x, (y-1));
  251. }
  252. // rechts
  253. if (y<(lines-1) && lab[pos+1] > dist) {
  254. shortestPath(lab, dist, x, (y+1));
  255. }
  256.  
  257. // Pruefe ob aktuelles Feld in der letzten Zeile ist, also im Ziel und ob der Weg frei ist
  258. // Wenn ja, schreibe aktuelle Distanz rein und beende Rekursion
  259. if ((x == (localLines-1) || x == 0) && lab[pos] != 0) {
  260. //printf("Pfad: (%d, %d) => (%d, %d) = [%d]\n", p1x, p1y, x, y, dist);
  261.  
  262. // Pfade bei folgenden Konstellationen nicht speichern
  263. int itsself = (x == p1x && y == p1y);
  264. int tmp1 = realStart[y];
  265. int tmp2 = realEnd[y];
  266. int firstLine = ((x == 0 && x == p1x && !tmp1)); // Wenn Element in der ersten Zeile nebeneinander liegen und kein echter Startpunkt ist
  267. int lastLine = ((x == (localLines-1) && p1x == 0 && !tmp2)); // Wenn Element in der letzten Zeile nebeneinander liegen und kein echter Endpunkt ist
  268. if (itsself || firstLine || lastLine) {
  269. //printf("wird nicht gespeichert: (%d, %d) ==> (%d, %d)\t\t itsself=%d firstLine=%d lastLine=%d 1[%d] 2[%d]\n", p1x, p1y, x, y, itsself, firstLine, lastLine, tmp1, tmp2);
  270. } else {
  271. savePath(p1x, p1y, x, y, dist);
  272. //printf("wird gespeichert: (%d, %d) ==> (%d, %d)\t\t itsself=%d firstLine=%d lastLine=%d\n", p1x, p1y, x, y, itsself, firstLine, lastLine);
  273. }
  274. }
  275.  
  276. } else {
  277. return 0;
  278. }
  279. return 0;
  280. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!