Changeset 826 for soft/giet_vm/applications/rosenfeld/src-par/mca_rosenfeld.c

Timestamp:

Jul 13, 2017, 11:01:58 AM (7 years ago)

Author:

meunier

Message:

• Mise à jour NR2 et Rosenfeld

File:

• soft/giet_vm/applications/rosenfeld/src-par/mca_rosenfeld.c (modified) (18 diffs)

soft/giet_vm/applications/rosenfeld/src-par/mca_rosenfeld.c

@@ -12 +12 @@
 #include <string.h>
 #include <math.h>
-#include <assert.h>
 #if PARMERGE
 #include <pthread.h>
@@ -27 +26 @@
 #else
     #include <stdbool.h>
+    #include <assert.h>
 #endif
 
@@ -165 +165 @@
     pthread_spin_lock(&F[e1][e0].lock);
     if (D[e1][e0] != eps || D[r1][r0] != root) {
-        // Someone change the root of epsilon or "root", need to find the new root
+        // Someone changed the root of epsilon or "root", need to find the new root
         pthread_spin_unlock(&F[e1][e0].lock);
         pthread_spin_unlock(&F[r1][r0].lock);
@@ -203 +203 @@
     if (D[e1][e0] != eps) {
         // Someone change the root of epsilon, need to find the new root
-        printf("race cond 1\n");
+        //printf("race cond 1\n");
         pthread_spin_unlock(&F[e1][e0].lock);
         pthread_spin_unlock(&F[r1][r0].lock);
@@ -210 +210 @@
     if (D[r1][r0] != root) {
         // Someone change the root of "root", need to find the new root
-        printf("race cond 2\n");
+        //printf("race cond 2\n");
         pthread_spin_unlock(&F[e1][e0].lock);
         pthread_spin_unlock(&F[r1][r0].lock);
@@ -235 +235 @@
 
 
+#if FEATURES && PARMERGE && ARSP
+// ------------------------------------------------------------------------------------------
+static void Propagate_Features(uint32 e0, uint32 e1, uint32 * T, RegionStats ** F, int shift)
+// ------------------------------------------------------------------------------------------
+{
+    uint32 i;
+    const int mask = (1 << shift) - 1;
+    for (i = e0; i <= e1; i++) {
+        uint32 root = T[i];
+        if (root != i) {
+            uint32 r1 = root >> shift;
+            uint32 r0 = root & mask;
+
+            uint32 l1 = i >> shift;
+            uint32 l0 = i & mask;
+            // We only lock the destination Features object
+            pthread_spin_lock(&F[r1][r0].lock);
+
+            // F(eps) = F(eps) U F(root)
+            F[r1][r0].xmin = ui16min2(F[l1][l0].xmin, F[r1][r0].xmin);
+            F[r1][r0].xmax = ui16max2(F[l1][l0].xmax, F[r1][r0].xmax);
+            F[r1][r0].ymin = ui16min2(F[l1][l0].ymin, F[r1][r0].ymin);
+            F[r1][r0].ymax = ui16max2(F[l1][l0].ymax, F[r1][r0].ymax);
+
+            F[r1][r0].S  += F[l1][l0].S;
+            F[r1][r0].Sx += F[l1][l0].Sx;
+            F[r1][r0].Sy += F[l1][l0].Sy;
+
+            pthread_spin_unlock(&F[r1][r0].lock);
+        }
+    }
+}
+#endif // FEATURES && PARMERGE && ARSP
+
 
 #if FAST
@@ -405 +439 @@
 
 
-#if FAST && !FEATURES && PARMERGE && ARSP
+#if FAST && PARMERGE && ARSP
 // ----------------------------------------------------------------------------------------------------------------
 static bool SetRoot_Parallel_Arsp_Rosenfeld_Dist(uint32 ** D, uint32 root, uint32 eps, int shift, RegionStats ** F)
 // ----------------------------------------------------------------------------------------------------------------
 {
+    // QM : Pour la version avec features, on est obligé de faire l'accumulation à la fin une fois la fermeture
+    // transitive globale réalisée : sinon, on peut perdre des features quand on propage vers un epsilon qui
+    // n'est pas une racine.
     assert(root != 0 && eps != 0);
 
-    MCA_VERBOSE3(printf("F(%d) += F(%d)\n", eps, root));
-    
     uint32_t mask = (1 << shift) - 1;
 
@@ -419 +454 @@
     uint32_t r0 = root & mask;
     
+    // @QM
+    // A priori ici il n'y a pas besoin de prendre le lock sur eps
+    // car ce n'est pas une racine
     pthread_spin_lock(&F[r1][r0].lock);
     if (D[r1][r0] != root) {
@@ -430 +468 @@
     return true;
 }
-
-// FAST && !FEATURES && PARMERGE && ARSP
-
+#endif // FAST && PARMERGE && ARSP
+
+
+#if FAST && PARMERGE && ARSP
 // ------------------------------------------------------------------------------------------------------------------------------
 static inline bool FindSmallerAncestor_Link(uint32 ** D, uint32_t rl, uint32_t el, uint32_t rd, uint32_t shift, RegionStats ** F)
 // ------------------------------------------------------------------------------------------------------------------------------
 {
+    // Fait pointer rd (racine) vers rl (pas racine) a priori
+    // mais il faut que l'élément vers lequel rd pointe soit plus petit que rd
+    // On "remonte" donc vers la racine de rl jusqu'à atteindre un élément plus petit que rd
+    // Si on atteint la racine de rl et que cette derniÚre est toujours plus grande que rd,
+    // on fait alors pointer rl vers rd
     bool ok;
     uint32_t el1, el0;
@@ -462 +506 @@
 }
 
-// FAST && !FEATURES && PARMERGE && ARSP
+// FAST && PARMERGE && ARSP
 
 // -----------------------------------------------------------------------------------------------------------------------
@@ -513 +557 @@
 }
 
-// FAST && !FEATURES && PARMERGE && ARSP
+// FAST && PARMERGE && ARSP
 
 // -------------------------------------------------------------------------------------------------------------------------------------
@@ -617 +661 @@
     } while (!ok);
 }
-#endif // FAST && !FEATURES && PARMERGE && ARSP
+#endif // FAST && PARMERGE && ARSP
 
 
@@ -1395 +1439 @@
         if (r < e) {
             T[e] = r; // racine de la classe d'equivalence
-#if FEATURES
+#if FEATURES && !(PARMERGE && ARSP)
             RegionStats_Accumulate_Stats1_From_Index(Stats, r, e);
 #endif
@@ -1519 +1563 @@
     // -- parallel transitive closure --
     // ---------------------------------
-    // identique a la version sans Features
      
     CLOCK_THREAD_START_STEP(p, 2);
@@ -1532 +1575 @@
     CLOCK_THREAD_END_STEP(p, 2);
 
+#if FEATURES && ARSP
+    pthread_barrier_wait(&main_barrier);
+#endif
+
     // To avoid uninitialized accesses
     CLOCK_THREAD_START_STEP(p, 3);
+    // With FEATURES and ARSP, STEP 3 is the Features propagation
+#if FEATURES && ARSP
+    Propagate_Features(e0, e1, T, F, mca->alpha);
+#endif
     CLOCK_THREAD_END_STEP(p, 3);
 }
@@ -1616 +1667 @@
     CLOCK_THREAD_END_STEP(p, 2);
 }
-#endif // !FEATURES
+#endif // !PARMERGE
 
 
@@ -1636 +1687 @@
     uint32 * T = mca->T;
 
-    CLOCK_THREAD_START_STEP(mca->p, 3);
+    CLOCK_THREAD_START_STEP(mca->p, 4);
     for (int i = i0; i <= i1; i++) {
         for (int j = j0; j <= j1; j++) {
@@ -1645 +1696 @@
         }
     }
-    CLOCK_THREAD_END_STEP(mca->p, 3);
+    CLOCK_THREAD_END_STEP(mca->p, 4);
 }