## 3 Improved Inter-Node Load Balancing for Multithreaded Applications
### Task Selection Policy with Exclusivity for Multithreaded Applications  
For existing policies, except for the First-Fit policy used in the unmodified Linux kernel, memory-aware policies, such as MB [4] and BCE [4] work with the kMLB mechanism. The Linux kernel must be modified to allow the kMLB mechanism to be used to determine the per-node memory pages per task. When the invoked functions or required data, structures are changed in the newer kernel, these memory-aware policies and the kMLB mechanism also require modification. This study proposes a new thread-aware policy named Exclusivity (Excl) that does not require the kMLB mechanism. Instead, it considers the exclusivity of thread distribution on nodes for a thread group. The more evenly the threads of a thread group are distributed to nodes, the less beneficial it is for data mapping and thread mapping. Migrating a task across nodes also changes the thread distribution for the thread group. It is better to select a task for which its thread group's threads are distributed more evenly on nodes. The Excl policy selects the task for which the thread group is least exclusive in terms of thread distribution for inter-node migration. Figure 9 illustrates an example in which 10 tasks belong to two thread groups. Most threads of one thread group are distributed on Node #0, but threads of the other group are evenly distributed on nodes. Migrating Task#10 is more beneficial. Figure 8: Tasks in a thread group share memory management information. Figure 7: Several multithreaded processes running on a 4-node NUMA system. For the proposed policy using the thread distribution of its thread group, for each movable task \(p\) in the runqueue, Equation (7) is used to evaluate the exclusivity of this thread group. _third_nri_ means the number of threads on NUMA node \(i\), and \(n\) is the number of nodes. For tasks in the source core's runqueue, the task for which the thread group has the minimum value for exclusivity is selected. For tasks with equal exclusivity, the first one to be evaluated is the target task:  
\[Excl_{p}=\underset{0\leq i\leq n-1}{\textit{max}}\textit{thrd\_nri}/\sum_{i=0} ^{n-1}\textit{thrd\_nri} \tag{7}\]  
In Figure 9, threads in hexagon have the value of exclusivity 0.8, and threads in the rectangle have the value of exclusivity 0.4. In Figure 7, Task #11 is selected because it is the least exclusive. The evaluation is listed in Table 3.  
However, exclusivity is not the sole criterion for consideration. There is an exceptional case for a multithreaded process for which most of the memory pages are allocated on some nodes, but most threads are on other nodes. In this situation, much remote memory access is necessary. As shown in Figure 10, the thread group in the hexagon and the thread group in the rectangle both have the same value of exclusivity 0.8. However, more remote memory access is necessary for the thread group in the hexagon. Suppose the task for which the \begin{table}
\begin{tabular}{c c c c} \hline \hline  & \multicolumn{3}{c}{**(a)**} \\ \hline \multirow{2}{*}{**Thread Group**} & \multicolumn{2}{c}{**Thread Group Members in**} & \multirow{2}{*}{\(Excl_{p}\)} & \multirow{2}{*}{**Selected Task**} \\  & **Core@0 Runqueue** & & \\ \hline \multirow{2}{*}{hexagon} & TGLR, Task\#4, Task\#5 & 4/5 = 0.8 & \multirow{2}{*}{Task\#10} \\ \hline rectangle & Task\#10 & 2/5 = 0.4 & \\ \hline \multirow{2}{*}{**Thread Group**} & \multicolumn{2}{c}{**Thread Group Members in**} & \multirow{2}{*}{\(Excl_{p}\)} & \multirow{2}{*}{**Selected Task**} \\  & **Core@1 Runqueue** & & \\ \hline pentagon & Task\#3 & 3/4 = 0.75 & \\ \hline rectangle & Task\#11 & 2/5 = 0.4 & \multirow{2}{*}{Task\#11} \\ \hline shape & Task\#19, Task\#16 & 2/5 = 0.4 & \\ \hline hexagon & Task\#6, Task\#9 & 3/5 = 0.6 & \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The evaluation of the Exclusivity policy. (**a**) The evaluation for tasks in Figure 9; (**b**) The evaluation for tasks in Figure 7.  
Figure 9: Two thread groups with different levels of exclusivity.