## 3 Improved Inter-Node Load Balancing for Multithreaded Applications
### Multithreaded Applications and Their Memory Access in Linux  
During the execution of a multithreaded application, threads are created as needed. In Linux, these threads form one thread group. The first thread in a multithreaded process is the thread group leader, and other threads are the members of this thread group. Each thread is regarded as one schedulable entity in the Linux kernel, so it is one task. Threads of the same thread group share the same memory address space and page table. When a task is created, the OS scheduler dispatches it to the core with the least load to maintain load balance within multi-core systems. On NUMA systems, threads of the same thread group may be distributed on different nodes, and their memory pages can also be allocated on several nodes, as shown in Figure 3. Therefore, memory pages are local memory pages for some threads and remote memory pages for others. Access to Data0 is local access for threads T0, T1, and T7 and remote access for threads T2, T3, T4, T5, and T6. The difference in the total memory access cost for a thread group when one of its threads is migrated across nodes must be determined. As depicted in Figure 4, threads within one thread group can be scheduled to run on different nodes, and their memory spaces can be on different nodes. A thread group's total memory access cost sums up the local memory access costs and the remote memory access costs for threads in this thread group. For a NUMA system with \(n\) nodes for which the memory access latency from a remote node to the local node is constant, the number of threads within a specific thread group on the NUMA node \(i\) is denoted as \(N_{i}\). The number of memory pages allocated to this thread group on the NUMA node \(i\) is denoted as \(R_{i}\). Regardless of the locality of memory references, the latency for all threads in the thread group to access the entire memory allocated to the thread group, which is the estimated total memory access cost, is shown in Equation (1). The local memory access cost is shown in Equation (2). Equation (3) shows the remote memory access cost, in which f is the NUMA factor that represents the ratio between the remote memory access latency and the local memory access latency. Total memory access cost (TMA) = Local memory access cost (LMA) + Cache miss cost + Remote memory access cost (RMA) (1)  
\[\text{Local memory access cost }(\text{LMA})=\sum_{i=0}^{n-1}N_{i}*R_{i} \tag{2}\]  
\[\text{Remote memory access cost }(\text{RMA})=(\sum_{i=0}^{n-1}\sum_{\forall j \
eq i}N_{i}*R_{j})*f \tag{3}\]  
Therefore, for the case in Figure 4, the estimated total memory access cost for this thread group is the value that is shown in Equation (4):  
\[ \begin{array}{l}\text{TMA}=\sum_{i=0}^{3}N_{i}*R_{i}+\text{Cache miss cost}+(\sum_{i=0}^{3}\sum_{\forall j\
eq i}N_{i}*R_{j})*f\\ =N_{0}R_{0}+N_{1}R_{1}+N_{2}R_{2}+N_{3}R_{3}+\text{Cache miss cost}+\\ (N_{0}R_{1}+N_{0}R_{2}+N_{0}R_{3}+N_{1}R_{0}+N_{1}R_{2}+N_{1}R_{3}+N_{2}R_{0}+ N_{2}R_{1}+N_{2}R_{3}+N_{3}R_{0}+N_{3}R_{1}+N_{3}R_{2})*f\end{array}  \tag{4}\]  
Because only the values of \(N_{0}\) and \(N_{2}\) change, and the others remain the same, the difference between the total memory access cost after a thread is migrated from node 0 to node 2 is simplified and calculated using Equation (5):  
Figure 4: Migrating one thread of a specific thread group across nodes. Figure 3: The memory pages and threads for a multithreaded process can be scattered on different nodes.