Make balanced affinity work on AArch64 (and possibly other architectures too)

[pawosm01]

Summary

This patch enables balanced affinity on machines that do not have
hardware threads and/or do have cores clustered into packages. In facts,
balacing algorithm could be generalized for any arrangement with
at least two levels of hierarchy (depth > 1).

[jlpeyton]

Can you re-upload the patch with all context?

[pawosm01]

Hello?

[AndreyChurbanov]

The patch as it is does not work for the case of multi package non-uniform topology.

So this case should be either fixed or disabled.

runtime/src/kmp_affinity.cpp

3994 ↗

(On Diff #63996)

This is number of cores in the last package, as the code supposed to be run on single package topology only.

3995 ↗

(On Diff #63996)

This code does not take into account number of packages (supposed to be run on single-package topology).

4017 ↗

(On Diff #63996)

Here the memory gets overwritten when the last package has lesser number of cores than max available, because (core*nth_per_core+thread) can be bigger than nproc so that the write is out of array bound.

4655 ↗

(On Diff #63996)

This is the number of cores in the last package. Other packages are skipped (no threads bound there).

[pawosm01]

Seems like we wrote our comments at the same time. I'll look at the issues raised.

[pawosm01]

There are ARMv8 boards where cores of one SoC are clustered into two packages: one for LITTLE cores and one for big. With original limitations this affinity method refused to work (due to nPackages > 1) which is bit discriminatory.

Note that I tested both uniform (equal number of cores per clusters) and non-uniform (more LITTLE cores than big) arrangements.

What I couldn't test (but I may gain access to such x86_64 machine in the future) is multi-package hyper-threaded machine (more than one CPU on board, each with more than one core of which each has more than one hardware thread) - I need to check again what effect my chagnes have on such arrangement (e.g. possible overwrites in procarr array).

runtime/src/kmp_affinity.cpp

3994 ↗

(On Diff #63996)

The whole point of change in line 3967 is to lift the limitation that the code is supposed to be run on single package topology only.

3995 ↗

(On Diff #63996)

In case of nPackages > 1 and nCoresPerPkg, nth_per_core equals to nCoresPerPkg.
I did not change the algorithm, I didn't change names of the variables used either.

4655 ↗

(On Diff #63996)

Do you refer to the effect this has on line 4679? This code crashes when __kmp_ncores is used there instead.

[AndreyChurbanov]

Maybe I was not clear enough. The code works fine for multi package non-uniform if no hyperthreads available, but works incorrectly for multi package non-uniform with hyperthreads. So the simplest fix would be disable balanced affinity for this case.

I haven't finished debugging no-HT case yet, I expect there should not be any problems, because the output of verbose affinity looks fine there.
Just tried to flag the found problem early...

[pawosm01]

Still, I need to fix it as I plan to have machine arranged like that.

[AndreyChurbanov]

runtime/src/kmp_affinity.cpp

4655 ↗

(On Diff #63996)

My comment was probably irrelevant here. The problem was incorrect filling of the procarr array that only contained info on the last package. So if this array is in use (I mostly tested case on line 4710), then all threads were bound to this last package.

If you fix memory overwriting at initialization, then anyway ncores will need to be multiplied by number of packages here or extra loop over packages needs to be added, I think. Otherwise l don't see how all machine can be covered, given that loops for( int i = 0; i < ncores; i++ ) only walk through subset of all cores now.

BTW, I finished with debugging of no-HT case. It works fine because you effectively reduced this case to single package via shifting topology one level down and making the balanced affinity to see packages as cores and cores as threads. This trick does not work for HT enabled topology.

[pawosm01]

I prepared and made use of three helper functions to make dealing with any case of non-uniform arrangement easier. I did not touch uniform topology code as it does not seem to be affected by existence of package layer: for HT case there are always the two deepest levels in play anyway. I wonder if we need this uniform - non-uniform distinction at all, uniform topology is just a special case of non-uniform topology and my new approach is capable to deal with both.

[pawosm01]

Actually, these are four helper functions, I didn't notice the smallest which only calls the other one.

[AndreyChurbanov]

LGTM

The code may still degrade to affinity none in some exotic cases of non-uniform topology (when address2os array has info on cores with hyperthreads numbered not from 0), but the value of code is much bigger than the need to support balanced affinity for such cases.

openmp/trunk/runtime/src/kmp_affinity.cpp

__kmp_apply_thread_places(AddrUnsPair **pAddr, int depth)
     }
 _exit:
     if (__kmp_pu_os_idx != NULL) {
         __kmp_free(__kmp_pu_os_idx);
         __kmp_pu_os_idx = NULL;
     }
 }
 
+//
+// This function figures out the deepest level at which there is at least one cluster/core
+// with more than one processing unit bound to it.
+//
+static int
+__kmp_affinity_find_core_level(const AddrUnsPair *address2os, int nprocs, int bottom_level)
+{
+    int core_level = 0;
+
+    for( int i = 0; i < nprocs; i++ ) {
+        for( int j = bottom_level; j > 0; j-- ) {
+            if( address2os[i].first.labels[j] > 0 ) {
+                if( core_level < ( j - 1 ) ) {
+                    core_level = j - 1;
+                }
+            }
+        }
+    }
+    return core_level;
+}
+
+//
+// This function counts number of clusters/cores at given level.
+//
+static int __kmp_affinity_compute_ncores(const AddrUnsPair *address2os, int nprocs, int bottom_level, int core_level)
+{
+    int ncores = 0;
+    int i, j;
+
+    j = bottom_level;
+    for( i = 0; i < nprocs; i++ ) {
+        for ( j = bottom_level; j > core_level; j-- ) {
+            if( ( i + 1 ) < nprocs ) {
+                if( address2os[i + 1].first.labels[j] > 0 ) {
+                    break;
+                }
+            }
+        }
+        if( j == core_level ) {
+            ncores++;
+        }
+    }
+    if( j > core_level ) {
+        //
+        // In case of ( nprocs < __kmp_avail_proc ) we may end too deep and miss one core.
+        // May occur when called from __kmp_affinity_find_core().
+        //
+        ncores++;
+    }
+    return ncores;
+}
+
+//
+// This function finds to which cluster/core given processing unit is bound.
+//
+static int __kmp_affinity_find_core(const AddrUnsPair *address2os, int proc, int bottom_level, int core_level)
+{
+    return __kmp_affinity_compute_ncores(address2os, proc + 1, bottom_level, core_level) - 1;
+}
+
+//
+// This function finds maximal number of processing units bound to a cluster/core at given level.
+//
+static int __kmp_affinity_max_proc_per_core(const AddrUnsPair *address2os, int nprocs, int bottom_level, int core_level)
+{
+    int maxprocpercore = 0;
+
+    if( core_level < bottom_level ) {
+        for( int i = 0; i < nprocs; i++ ) {
+            int percore = address2os[i].first.labels[core_level + 1] + 1;
+
+            if( percore > maxprocpercore ) {
+                maxprocpercore = percore;
+            }
+       }
+    } else {
+        maxprocpercore = 1;
+    }
+    return maxprocpercore;
+}
 
 static AddrUnsPair *address2os = NULL;
 static int           * procarr = NULL;
 static int     __kmp_aff_depth = 0;
 
 #define KMP_EXIT_AFF_NONE                             \
     KMP_ASSERT(__kmp_affinity_type == affinity_none); \
     KMP_ASSERT(address2os == NULL);                   \
# endif
 
         case affinity_compact:
         if (__kmp_affinity_compact >= depth) {
             __kmp_affinity_compact = depth - 1;
         }
         goto sortAddresses;
 
         case affinity_balanced:
-        // Balanced works only for the case of a single package
-        if( nPackages > 1 ) {
+        if( depth <= 1 ) {
             if( __kmp_affinity_verbose || __kmp_affinity_warnings ) {
                 KMP_WARNING( AffBalancedNotAvail, "KMP_AFFINITY" );
             }
             __kmp_affinity_type = affinity_none;
             return;
         } else if( __kmp_affinity_uniform_topology() ) {
             break;
         } else { // Non-uniform topology
 
             // Save the depth for further usage
             __kmp_aff_depth = depth;
 
-            // Number of hyper threads per core in HT machine
-            int nth_per_core = __kmp_nThreadsPerCore;
+            int core_level = __kmp_affinity_find_core_level(address2os, __kmp_avail_proc, depth - 1);
+            int ncores = __kmp_affinity_compute_ncores(address2os, __kmp_avail_proc, depth - 1, core_level);
+            int maxprocpercore = __kmp_affinity_max_proc_per_core(address2os, __kmp_avail_proc, depth - 1, core_level);
 
-            int core_level;
-            if( nth_per_core > 1 ) {
-                core_level = depth - 2;
-            } else {
-                core_level = depth - 1;
+            int nproc = ncores * maxprocpercore;
+            if( ( nproc < 2 ) || ( nproc < __kmp_avail_proc ) ) {
+                if( __kmp_affinity_verbose || __kmp_affinity_warnings ) {
+                    KMP_WARNING( AffBalancedNotAvail, "KMP_AFFINITY" );
+                }
+                __kmp_affinity_type = affinity_none;
+                return;
             }
-            int ncores = address2os[ __kmp_avail_proc - 1 ].first.labels[ core_level ] + 1;
-            int nproc = nth_per_core * ncores;
 
             procarr = ( int * )__kmp_allocate( sizeof( int ) * nproc );
             for( int i = 0; i < nproc; i++ ) {
                 procarr[ i ] = -1;
             }
 
+            int lastcore = -1;
+            int inlastcore = 0;
             for( int i = 0; i < __kmp_avail_proc; i++ ) {
                 int proc = address2os[ i ].second;
-                // If depth == 3 then level=0 - package, level=1 - core, level=2 - thread.
-                // If there is only one thread per core then depth == 2: level 0 - package,
-                // level 1 - core.
-                int level = depth - 1;
-
-                // __kmp_nth_per_core == 1
-                int thread = 0;
-                int core = address2os[ i ].first.labels[ level ];
-                // If the thread level exists, that is we have more than one thread context per core
-                if( nth_per_core > 1 ) {
-                    thread = address2os[ i ].first.labels[ level ] % nth_per_core;
-                    core = address2os[ i ].first.labels[ level - 1 ];
+                int core = __kmp_affinity_find_core(address2os, i, depth - 1, core_level);
+
+                if ( core == lastcore ) {
+                    inlastcore++;
+                } else {
+                    inlastcore = 0;
                 }
-                procarr[ core * nth_per_core + thread ] = proc;
+                lastcore = core;
+
+                procarr[ core * maxprocpercore + inlastcore ] = proc;
             }
 
             break;
         }
 
         sortAddresses:
         //
         // Allocate the gtid->affinity mask table.
# endif
 
     return KMP_CPU_ISSET(proc, (kmp_affin_mask_t *)(*mask));
 }
 
 
 // Dynamic affinity settings - Affinity balanced
 void __kmp_balanced_affinity( int tid, int nthreads )
 {
+    bool fine_gran = true;
+
+    switch (__kmp_affinity_gran) {
+        case affinity_gran_fine:
+        case affinity_gran_thread:
+            break;
+        case affinity_gran_core:
+            if( __kmp_nThreadsPerCore > 1) {
+                fine_gran = false;
+            }
+            break;
+        case affinity_gran_package:
+            if( nCoresPerPkg > 1) {
+                fine_gran = false;
+            }
+            break;
+        default:
+            fine_gran = false;
+    }
+
     if( __kmp_affinity_uniform_topology() ) {
         int coreID;
         int threadID;
         // Number of hyper threads per core in HT machine
         int __kmp_nth_per_core = __kmp_avail_proc / __kmp_ncores;
         // Number of cores
         int ncores = __kmp_ncores;
+        if( ( nPackages > 1 ) && ( __kmp_nth_per_core <= 1 ) ) {
+            __kmp_nth_per_core = __kmp_avail_proc / nPackages;
+            ncores = nPackages;
+        }
         // How many threads will be bound to each core
         int chunk = nthreads / ncores;
         // How many cores will have an additional thread bound to it - "big cores"
         int big_cores = nthreads % ncores;
         // Number of threads on the big cores
         int big_nth = ( chunk + 1 ) * big_cores;
         if( tid < big_nth ) {
             coreID = tid / (chunk + 1 );
             threadID = ( tid % (chunk + 1 ) ) % __kmp_nth_per_core ;
         } else { //tid >= big_nth
             coreID = ( tid - big_cores ) / chunk;
             threadID = ( ( tid - big_cores ) % chunk ) % __kmp_nth_per_core ;
         }
 
         KMP_DEBUG_ASSERT2(KMP_AFFINITY_CAPABLE(),
           "Illegal set affinity operation when not capable");
 
         kmp_affin_mask_t *mask;
         KMP_CPU_ALLOC_ON_STACK(mask);
         KMP_CPU_ZERO(mask);
 
-        // Granularity == thread
-        if( __kmp_affinity_gran == affinity_gran_fine || __kmp_affinity_gran == affinity_gran_thread) {
+        if( fine_gran ) {
             int osID = address2os[ coreID * __kmp_nth_per_core + threadID ].second;
             KMP_CPU_SET( osID, mask);
-        } else if( __kmp_affinity_gran == affinity_gran_core ) { // Granularity == core
+        } else {
             for( int i = 0; i < __kmp_nth_per_core; i++ ) {
                 int osID;
                 osID = address2os[ coreID * __kmp_nth_per_core + i ].second;
                 KMP_CPU_SET( osID, mask);
             }
         }
         if (__kmp_affinity_verbose) {
             char buf[KMP_AFFIN_MASK_PRINT_LEN];
             __kmp_affinity_print_mask(buf, KMP_AFFIN_MASK_PRINT_LEN, mask);
             KMP_INFORM(BoundToOSProcSet, "KMP_AFFINITY", (kmp_int32)getpid(),
               tid, buf);
         }
         __kmp_set_system_affinity( mask, TRUE );
         KMP_CPU_FREE_FROM_STACK(mask);
     } else { // Non-uniform topology
 
         kmp_affin_mask_t *mask;
         KMP_CPU_ALLOC_ON_STACK(mask);
         KMP_CPU_ZERO(mask);
 
-        // Number of hyper threads per core in HT machine
-        int nth_per_core = __kmp_nThreadsPerCore;
-        int core_level;
-        if( nth_per_core > 1 ) {
-            core_level = __kmp_aff_depth - 2;
-        } else {
-            core_level = __kmp_aff_depth - 1;
-        }
-
-        // Number of cores - maximum value; it does not count trail cores with 0 processors
-        int ncores = address2os[ __kmp_avail_proc - 1 ].first.labels[ core_level ] + 1;
+        int core_level = __kmp_affinity_find_core_level(address2os, __kmp_avail_proc, __kmp_aff_depth - 1);
+        int ncores = __kmp_affinity_compute_ncores(address2os, __kmp_avail_proc, __kmp_aff_depth - 1, core_level);
+        int nth_per_core = __kmp_affinity_max_proc_per_core(address2os, __kmp_avail_proc, __kmp_aff_depth - 1, core_level);
 
         // For performance gain consider the special case nthreads == __kmp_avail_proc
         if( nthreads == __kmp_avail_proc ) {
-            if( __kmp_affinity_gran == affinity_gran_fine || __kmp_affinity_gran == affinity_gran_thread) {
+            if( fine_gran ) {
                 int osID = address2os[ tid ].second;
                 KMP_CPU_SET( osID, mask);
-            } else if( __kmp_affinity_gran == affinity_gran_core ) { // Granularity == core
-                int coreID = address2os[ tid ].first.labels[ core_level ];
-                // We'll count found osIDs for the current core; they can be not more than nth_per_core;
-                // since the address2os is sortied we can break when cnt==nth_per_core
-                int cnt = 0;
+            } else {
+                int core = __kmp_affinity_find_core(address2os, tid, __kmp_aff_depth - 1, core_level);
                 for( int i = 0; i < __kmp_avail_proc; i++ ) {
                     int osID = address2os[ i ].second;
-                    int core = address2os[ i ].first.labels[ core_level ];
-                    if( core == coreID ) {
+                    if( __kmp_affinity_find_core(address2os, i,  __kmp_aff_depth - 1, core_level) == core ) {
                         KMP_CPU_SET( osID, mask);
-                        cnt++;
-                        if( cnt == nth_per_core ) {
-                            break;
-                        }
-                    }
-                }
-            }
-        } else if( nthreads <= __kmp_ncores ) {
+        } else if( nthreads <= ncores ) {
 
             int core = 0;
             for( int i = 0; i < ncores; i++ ) {
                 // Check if this core from procarr[] is in the mask
                 int in_mask = 0;
                 for( int j = 0; j < nth_per_core; j++ ) {
                     if( procarr[ i * nth_per_core + j ] != - 1 ) {
                         in_mask = 1;
                         break;
                     }
                 }
                 if( in_mask ) {
                     if( tid == core ) {
                         for( int j = 0; j < nth_per_core; j++ ) {
                             int osID = procarr[ i * nth_per_core + j ];
                             if( osID != -1 ) {
                                 KMP_CPU_SET( osID, mask );
-                                // For granularity=thread it is enough to set the first available osID for this core
-                                if( __kmp_affinity_gran == affinity_gran_fine || __kmp_affinity_gran == affinity_gran_thread) {
+                                // For fine granularity it is enough to set the first available osID for this core
+                                if( fine_gran) {
                                     break;
                                 }
                             }
                         }
                         break;
                     } else {
                         core++;
                     }
                 }
             }
 
-        } else { // nthreads > __kmp_ncores
+        } else { // nthreads > ncores
 
             // Array to save the number of processors at each core
             int* nproc_at_core = (int*)KMP_ALLOCA(sizeof(int)*ncores);
             // Array to save the number of cores with "x" available processors;
             int* ncores_with_x_procs = (int*)KMP_ALLOCA(sizeof(int)*(nth_per_core+1));
             // Array to save the number of cores with # procs from x to nth_per_core
             int* ncores_with_x_to_max_procs = (int*)KMP_ALLOCA(sizeof(int)*(nth_per_core+1));
 
if( __kmp_affinity_uniform_topology() ) {
                     }
                 }
                 flag = 1;
             }
             int sum = 0;
             for( int i = 0; i < nproc; i++ ) {
                 sum += newarr[ i ];
                 if( sum > tid ) {
-                    // Granularity == thread
-                    if( __kmp_affinity_gran == affinity_gran_fine || __kmp_affinity_gran == affinity_gran_thread) {
+                    if( fine_gran) {
                         int osID = procarr[ i ];
                         KMP_CPU_SET( osID, mask);
-                    } else if( __kmp_affinity_gran == affinity_gran_core ) { // Granularity == core
+                    } else {
                         int coreID = i / nth_per_core;
                         for( int ii = 0; ii < nth_per_core; ii++ ) {
                             int osID = procarr[ coreID * nth_per_core + ii ];
                             if( osID != -1 ) {
                                 KMP_CPU_SET( osID, mask);
                             }
                         }
                     }