NumaPerf: Predictive and Full NUMA Profiling

The remainder of this paper is organized as follows. Section 2 introduces the background of NUMA architecture and the basic ideas of NumaPerf. Then Section 3 presents the detailed implementation and Section 4 shows experimental results. After that, Section 5 explains the limitation and Section 6 discusses related work in this field. In the end, Section 7 concludes this paper.

Traditional computers use the Uniform Memory Access (UMA) model. In this model, all CPU cores share a single memory controller such that any core can access the memory with the same latency (uniformly). However, the UMA architecture cannot accommodate the increasing number of cores because these cores may compete for the same memory controller. The memory controller becomes the performance bottleneck in many-core machines since a task cannot proceed without getting its necessary data from the memory.

The Non-Uniform Memory Access (NUMA) architecture is proposed to solve this scalability issue, as further shown in Figure 1. It has a decentralized nature. Instead of making all cores waiting for the same memory controller, the NUMA architecture is typically equipped with multiple memory controllers, where each controller serves a group of CPU cores (called a “node” or “processor” interchangeably). Incorporating multiple memory controllers largely reduces the contention for memory controllers and therefore improves the scalability correspondingly. However, the NUMA architecture also introduce multiple sources of performance degradations (Blagodurov:2011:CNC:2002181.2002182, ), including Cache Contention, Node Imbalance, Interconnect Congestion, and Remote Accesses.

Cache Contention: the NUMA architecture is prone to cache contention, including false and true sharing. False sharing occurs when multiple tasks may access distinct words in the same cache line (Hoard, ), while different tasks may access the same words in true sharing. For both cases, multiple tasks may compete for the shared cache. Cache contention will cause more serious performance degradation, if data has to be loaded from a remote node.

Node Imbalance: When some memory controllers have much more memory accesses than others, it may cause the node imbalance issue. Therefore, some tasks may wait more time for memory access, thwarting the whole progress of a multithreaded application.

Interconnect Congestion: Interconnect congestion occurs if some tasks are placed in remote nodes that may use the inter-node interconnection to access their memory.

Remote Accesses: In a NUMA architecture, local nodes can be accessed with less latency than remote accesses. Therefore, it is important to reduce remote access to improve performance.

Existing NUMA profilers mainly focus on detecting remote accesses, while omitting other performance issues. In contrast, NumaPerf has different design goals as follows. First, it aims to identify different sources of NUMA performance issues, not just limited to remote accesses. Second, NumaPerf aims to design architecture- and scheduling-independent approaches that could report performance issues in any NUMA hardware. Third, it aims to provide sufficient information to guide bug fixes.

For the first goal, NumaPerf detects NUMA issues caused by cache contention, node imbalance, interconnect congestion, and remote accesses, where existing work only considers remote accesses. Cache contention can be either caused by false or true sharing, which will impose a larger performance impact and require a different fix strategy. Existing work never separates them from normal remote accesses. In contrast, NumaPerf designs a separate mechanism to detect such issues, but tracking possible cache invalidations caused by cache contention. It is infeasible to measure all node imbalance and interconnect congestion without knowing the actual memory and thread binding. Instead, NumaPerf focuses on one specific type of issues, which is workload imbalance between different types of threads. Existing work omits one type of remote access caused by thread migration, where thread migration will make all local accesses remotely. NumaPerf identifies whether an application has a higher chance of thread migrations, in addition to normal remote accesses. Overall, NumaPerf detects more NUMA performance issues than existing NUMA profilers. However, the challenge is to design architecture- and scheduling-independent methods.

The second goal of NumaPerf is to design architecture- and scheduling approaches that do not bind to specific hardware. Detecting remote accesses is based on the key observation of Section 1: if a thread accesses a physical page that was initially accessed by a different thread, then this access will be counted as remote access. This method is not bound to specific hardware, since memory sharing patterns between threads are typically invariant across multiple executions. NumaPerf tracks every memory access in order to identify the first thread working on each page. Due to this reason, NumaPerf employs fine-grained instrumentation, since coarse-grained sampling may miss the access from the first thread. Based on memory accesses, NumaPerf also tracks the number of cache invalidations caused by false or true sharing with the following rule: a write on a cache line with multiple copies will invalidate other copies. Since the number of cache invalidations is closely related to the number of concurrent threads, NumaPerf divides the score with the number of threads to achieve a similar result with a different number of concurrent threads, as further described in Section 3.2.3. Load imbalance will be evaluated by the total number of memory accesses of different types of threads. It is important to track all memory accesses including libraries for this purpose. To evaluate the possibility of thread migration, NumaPerf proposes to track the number of lock contentions and the number of condition and barrier waits. Similar to false sharing, NumaPerf eliminates the effect caused by concurrent threads by dividing with the number of threads. The details of these implementations can be seen in Section 3 .

For the third goal, NumaPerf will utilize the data-centric analysis as existing work (XuNuma, ). That is, it could report the callsite of heap objects that may have NUMA performance issues. In addition, NumaPerf aims to provide useful information that helps bug fixes, which could be easily achieved when all memory accesses are tracked. NumaPerf provides word-based access information for cache contentions, helping programmers to differentiate false or true sharing. It provides threads information on page sharing (help determining whether to use block-wise interleave), and reports whether an object can be duplicated or not by tracking the temporal read/write pattern. NumaPerf also predicts a good thread assignment to achieve better performance for load imbalance issues. In summary, many of these features require fine-grained instrumentation in order to avoid false alarms.

Due to the reasons mentioned above, NumaPerf utilizes fine-grained memory accesses to improve the effectiveness and provide better information for bug fixes. NumaPerf employs compiler-based instrumentation in order to collect memory accesses due to the performance and flexibility concern. An alternative approach is to employ binary-based dynamic instrumentation (DynamoRlO, ; Valgrind, ; Pin, ), which may introduce more performance overhead but without an additional compilation step. NumaPerf inserts an explicit function call for each read/write access on global variables and heap objects, while accesses on stack variables are omitted since they typically do not introduce performance issues. To track thread migration, NumaPerf also intercepts synchronizations. To support data-centric analysis, NumaPerf further intercepts memory allocations to collect their callsites.

Figure 2 summarizes NumaPerf’s basic idea. NumaPerf includes two components, NumaPerf-Static and NumaPerf-Dynamic. NumaPerf-Static is a static compile-time based tool that inserts a function call before every memory access on heap and global variables, which compiles a program into an instrumented executable file. Then this executable file will be linked to NumaPerf-Dynamic so that NumaPerf could collect memory accesses, synchronizations, and information of memory allocations. NumaPerf then performs detection on NUMA-related performance issues, and reports to users in the end. More specific implementations are discussed in Section 3.

NumaPerf’s static component (NumaPerf-Static) performs the instrumentation on memory accesses. In particular, it utilizes static analysis to identify memory accesses on heap and global variables, while omitting memory accesses on static variables. Based on our understanding, static variables will never cause performance issues, if a thread is not migrated. NumaPerf-Static inserts a function call upon these memory accesses, where this function is implemented in NumaPerf-Dynamic library. In particular, this function provides detailed information on the access, including the address, the type (i.e., read or write), and the number of bytes.

NumaPerf employs the LLVM compiler to perform the instrumentation (llvm, ). It chooses the intermediate representation (IR) level for the instrumentation due to the flexibility, since LLVM provides lots of APIs and tools to manipulate the IR. The instrumentation pass is placed at the end of the LLVM optimization passes, where only memory accesses surviving all previous optimization passes will be instrumented. NumaPerf-Static traverses functions one by one, and instruments memory accesses on global and heap variables. The instrumentation is adapted from AddressSanitizer (AddressSanitizer, ).

This subsection starts with tracking application information, such as memory accesses, synchronizations, and memory allocations. Then it discusses the detection of each particular performance issue. In the following, NumaPerf is used to represent NumaPerf-Dynamic unless noted otherwise.

We evaluated NumaPerf on multiple HPC applications (e.g., AMG2006 (AMG2006, ), lulesh (LULESH, ), and UMT2013 (UMT2013, )) and a widely-used multithreaded application benchmark suite — PARSEC (parsec, ). Applications with NUMA performance issues are listed in Table 1. The performance improvement after fixing all issues is listed in “Improve” column, with the average of 10 runs, where all specific issues are listed afterwards. For each issue, the table listed the type of issue and the corresponding score, the allocation site, and the fix strategy. Note that the table only shows cases with page sharing score larger than 1500 (if without cache false/true sharing), false/true sharing score larger than 1, and thread migration score larger than 150. Further, the performance improvement of each specific issue is listed as well. We also present multiple cases studies that show how NumaPerf’s report is able to assist bug fixes in Section 4.2.

Overall, we have the following observations. First, it reports no false positives by only reporting scores larger than a threshold. Second, NumaPerf detects more performance issues than the combination of all existing NUMA profilers (Intel:VTune, ; Memphis, ; Lachaize:2012:MMP:2342821.2342826, ; XuNuma, ; NumaMMA, ; 7847070, ; diener2015characterizing, ; valat:2018:numaprof, ). The performance issues that cannot be detected by existing NUMA profilers are highlighted with a check mark in the last column of the table, although some can be detected by specific tools, such as cache false/true sharing issues (Sheriff, ; Predator, ; Cheetah, ; DBLP:conf/ppopp/ChabbiWL18, ; helm2019perfmemplus, ). This comparison with existing NUMA profilers is based on the methodology. Existing NUMA profilers cannot separate false or true sharing with normal remote accesses, and cannot detect thread migration and load imbalance issues.

When comparing to a specific profiler, NumaPerf also has better results even on detecting remote accesses. For lulesh, HPCToolkit detects issues of # 4  (XuNuma, ), while NumaPerf detects three more issues (# 3, 5, 7). Fixing these issues improves the performance by up to 504% (with the threads binding). Multiple reasons may contribute to this big difference. First, NumaPerf’s predictive method detects some issues that are not occurred in the current scheduling and the current hardware, while HPCToolkit has no such capabilities. Second, HPCToolkit requires to bind threads to nodes, which may miss remote accesses caused by its specific binding. Third, NumaPerf’s fine-grained profiling provides a better effectiveness than a coarse-grained profiler like HPCToolkit. NumaPerf may have false negatives caused by its instrumentation. NumaPerf cannot detect an issue of UMT2013 reported by HPCToolkit (XuNuma, ). The basic reason is that NumaPerf cannot instrument Fortran code. NumaPerf’s limitations are further discussed in Section 4.2.

In this section, multiple case studies are shown how programmers could fix performance issues based on the report.

We also evaluated the performance of NumaPerf on PARSEC applications, and the performance results are shown in Figure 3. On average, NumaPerf’s overhead is around 585%, which is orders-of-magnitude smaller than the state-of-the-art fine-grained profiler — NUMAPROF (valat:2018:numaprof, ). In contrast, NUMAPROF’s overhead runs $316\times$ slower than the original one. NumaPerf is designed carefully to avoid such high overhead, as discussed in Section 3. Also, NumaPerf’s compiler-instrumentation also helps reduce some overhead by excluding memory accesses on stack variables.

There are some exceptions. Two applications impose more than $10\times$ overhead, including Swaption and x264. Based on our investigation, the instrumentation with an empty function imposes more than $5\times$ overhead. The reason is that they have significantly more memory accesses compared with other applications like blackscholes. Based on our investigation, swaption has more than $250\times$ memory accesses than blackscholes in a time unit. Applications with low overhead can be caused by not instrumenting libraries, which is typically not the source of NUMA performance issues.

We further evaluated NumaPerf’s memory overhead with PARSEC applications. The results are shown in Table 2. In total, NumaPerf’s memory overhead is around 28%, which is much smaller than the state-of-the-art fine-grained profiler — NUMAPROF (valat:2018:numaprof, ). NumaPerf’s memory overhead is mainly coming from the following resources. First, NumaPerf records the detailed information in page-level and cache-level, so that we could provide detailed information to assist bug fixes. Second, NumaPerf also stores allocation callsites for every object in order to attribute performance issues back to the data.

We notice that some applications have a larger percentage of memory overhead, such as streamcluster. For it, a large object has very serious NUMA issues. Therefore, recording page and cache level detailed information contributes to the major memory overhead. However, overall, NumaPerf’s memory overhead is totally acceptable, since it provides much more helpful information to assist bug fixes.

We further confirm whether NumaPerf is able to detect similar performance issues when running on a non-NUMA or UMA machine. We further performed the experiments on a two-processor machine, where each processor is Intel(R) Xeon(R) Gold 6230 and each processor has 20 cores. We explicitly disabled all cores in node 1 but only utilizing 16 hardware cores in node 0. This machine has 256GB of main memory, 64KB L1 cache, and 1MB of L2 cache. The experimental results are further listed in Table 3. For simplicity, we only listed the applications, the issue number, and serious scores in two different machines.

Table 3 shows that most reported scores in two machines are very similar, although with small variance. The small variance could be caused by multiple factors, such as parallelization degree (concurrency). However, this table shows that all serious issues can be detected on both machines. This indicates that NumaPerf achieves its design goal, which could even detect NUMA issues without running on a NUMA machine.

RTHMS also employs PIN to collect memory traces, and then assigns a score to each object-to-memory based on its algorithms (RTHMS, ). It aims for identifying the peformance issues for the hybrid DRAM-HBM architecture, but not the NUMA architecture, and has a higher overhead than NumaPerf. Some tools focus on the detection of false/true sharing issues (Sheriff, ; Predator, ; Cheetah, ; DBLP:conf/ppopp/ChabbiWL18, ; helm2019perfmemplus, ), but skipping other NUMA issues.

SyncPerf also detects load imablance and predicts the optimal thread assignment (SyncPerf, ). SyncPerf aims to achieve the optimal thread assignment by balancing the waiting time of each types of threads. In contrast, NumaPerf suggests the optimal thread assignment based the number of accesses of each thread, which indicates the actual workload.