Methodology for fast detection of false sharing in threaded scientific codes

A profiling tool identifies a code region with a false sharing potential. A static analysis tool classifies variables and arrays in the identified code region. A mapping detection library correlates memory access instructions in the identified code region with variables and arrays in the identified code region while a processor is running the identified code region. The mapping detection library identifies one or more instructions at risk, in the identified code region, which are subject to an analysis by a false sharing detection library. A false sharing detection library performs a run-time analysis of the one or more instructions at risk while the processor is re-running the identified code region. The false sharing detection library determines, based on the performed run-time analysis, whether two different portions of the cache memory line are accessed by the generated binary code.

BACKGROUND

This disclosure relates generally to a false sharing occurring in parallel computing systems, and particularly to a method for detecting the false sharing through a run-time analysis of a source code.

BACKGROUND OF THE INVENTION

A multi-threaded computing system utilizes cache memory devices by rewarding temporal and spatial locality within cache lines. However, an occurrence of false sharing degrades performance of the parallel computing system, e.g., by invoking a known cache memory coherence mechanism. False sharing occurs among threads when data that those threads access happen to be placed in the same cache line. False sharing causes “ping-pong” of invalidation to a same cache line from one thread writing to part of that cache line while the other thread accesses other parts of that cache line.

A known false sharing method relies on a compiler analysis and special hardware counters that track cache coherence traffic on processors. The drawback of this method is that special hardware counters are needed, and this method cannot distinguish between true sharing (i.e., two different threads modify a same portion of a same cache line) and false sharing (i.e., two different threads modify two different portions of a same cache line). Another known false sharing detection approach involves OS (Operating System) kernel programming. This method intercepts system calls, replaces each thread as a process, and maintains a transaction when these processes update a shared memory. The drawback of this approach includes that an application cannot afford to create many processes, e.g., more than 1 million processes, and system software on compute nodes may not allow an implementation of a transaction.

SUMMARY

There is provided a method for detecting a false sharing of a cache memory line in a multi-threaded computing environment. A compiler receives source code of a program written in a high-level programming language. The compiler compiles the received source code of the program in order to generate binary code of the program. A profiling tool identifies a code region, in the generated binary code, with a false sharing potential. A static analysis tool classifies variables and arrays in the identified code region. A mapping detection library is injected into the generated binary code in order to monitor every memory access instructions in the identified code region while a processor is running the identified code region. The mapping detection library identifies memory addresses accessed by the memory access instructions at runtime. Based on these identified memory addresses and the classification performed in the static analysis tool, one or more instructions at risk associated with one class of the classified variable and arrays are identified. Only these instructions at risk are analyzed by a false sharing detection library while the processor is re-running the identified code region. The false sharing detection library determines, based on the analysis of the one or more instructions at risk, whether two different portions of the cache memory line are accessed by the generated binary code. The false sharing detection library detects a false sharing of the cache memory line if the two different portions of the cache memory line are accessed by the generated binary code.

In order to classify the variables and arrays in the identified code region, the static analysis tool performs a static analysis on the received source code of the program. The static analysis tool defines a condition that the false sharing does not occur, based on an array size and index of an array in the received source code of the program.

The static analysis performed by the static analysis tool includes: classifying variables and arrays in the received source code into a first class representing read only variables and arrays, into a second class of variables and arrays belonging to a write operation with no false sharing risk, and into a third class of variables and arrays belonging to a write operation with a false sharing risk.

The mapping detection library is configured to generate a mapping between variables and the memory access instructions in the identified code region. Based on the generated mapping, only the one or more instructions at risk are being monitored by the false sharing detection library. The false sharing detection library reports at least one false sharing associated with the one or more instructions at risk.

The present disclosure presents a software method that uses instrumentation, a static analysis, and a run-time analysis for expediting of false sharing detection. This method includes, but is not limited to: instrumenting of binary code according to a result of source code static analysis, and feeding back run-time analysis information to a false sharing detection methodology. A mapping detection library is configured to capture relationships between load/store instructions and arrays, and feed those relationships to a run-time analysis tool which detects a false sharing occurrence. This method does not rely on special hardware, nor does it require support from OS. This method is oblivious to generating deep functional call chains and generating unorganized code.

DETAILED DESCRIPTION

FIG. 1illustrates a flow chart describing method steps for detecting a false sharing of a cache memory line in a multi-threaded computing environment. A multi-threaded computing environment includes, but is not limited to: IBM® BlueGene®. A processor in the multi-threaded computing environment receives source code100of a program written in a high-level programming language, e.g., Java®, .Net, C/C++. The processor runs a compiler in order to compile the received source code. By compiling the received source code, the compiler generates original binary code of the program.

While the compiler is compiling the received source code, at step105, a profiling tool (e.g., gprof, etc.) identifies at least one “hotspot”110, which is at least one code region (e.g., functions, loops, etc.) in the received source code having false-sharing potentials. gprof is a profiler provided from GNU and is described in detail Susan L. Graham, et al. “gprof: a Call Graph Execution Profiler,” Proceeding of the SIGPLAN '82 Symposium on Compiler Construction, June, 1982, whose contents are incorporated by reference as if set forth herein. The identification of the hopspot is done through either profiling (e.g., gprof, etc.) or collecting hardware events for “hints” of a false sharing of a cache memory line. Alternatively, a user may specify the hotspot. A code region with false-sharing potentials (i.e., hotspot) can also be identified, e.g., by collecting hardware events, for example, the number of cache coherent events. If this information, i.e., the collected hardware events, is not provided to the profiling tool, all processors in the multi-threaded computing environment may be configured to report the number of cache misses, which can be used as a hint. Alternatively, a code region taking more time than expected in the multi-threading computing environment may raise a flag indicating a potential false sharing. This identified code region (i.e., “hotspot”) is provided as inputs to method steps115-120and150.

At step120, a statistic analysis tool receives source code of the identified code region and performs parsing and/or known static analysis on the source code of the identified code region. Based on this performed parsing and/or known static analysis, the static analysis tool classifies 125 variables and arrays in the identified code region into a first class representing read only variables and arrays, into a second class of variables and arrays belonging to a write operation with no false sharing risk, and into a third class of variables and arrays belonging to a write operation with a false sharing risk. The read only variables and arrays possess no possibility of false sharing unless a read only variable or array is located in a same cache line being written.

The static analysis tool defines a condition, in a form of an expression that the false sharing does not occur, based on an array size and an index of an array in the identified code region. The compiler invokes the static analysis tool on the identified code region targeting arrays that are written to. The compiler issues compiler directives, e.g., labels, to infer how a loop is partitioned, and accordingly, defines the condition in the form of an expression that a certain write to an array will not incur the false sharing. These arrays are classified as the second class of the variables and arrays. In one embodiment, this second class of the variables and arrays are not monitored during a final run at step160, which is described in detail below.

Arrays and/or variables written to may be a source of false-sharing, but not always. Whether the false-sharing may occur depends on how many threads participate in running a loop, and how the loop is partitioned to run in parallel. For example, whether the following exemplary source code incurs a false-sharing depends on values of loop bounds.

In this exemplary source code, if s2 and s3 are small, e.g., number 1, an access to a[i][j][k] from different threads may be accessing to a same cache line. The static analysis tool analyzes an array access pattern, a loop partition strategy, and loop bounds, and comes up with an expression that the false sharing will not occur. In this example, the expression could be s2×s3×array element size>Cache line size. Thereby, the static analysis tool identifies which variables and arrays (and under what conditions) do not need to be watched during a run-time analysis and classifies 125 these variables and arrays as described above.

In one embodiment, at step115, a mapping detection library117is injected into the binary code of the identified code region, e.g., by using an instrumenting framework. An instrumenting framework is a tool used to modify original binary code, e.g., by adding another binary code into the original binary code. Examples of the instrumenting framework includes, but is not limited to: pSigma, DYNAMO, PIN, etc. A PIN—a dynamic binary instrumentation framework—is described in detail in http://www.pintool.org/, whose entire contents are incorporated by reference as set forth herein. The instrumenting framework receives the mapping detection library117and binary code of the identified code region (i.e., “hotspot”), injects the mapping detection library117into the binary code of the identified code region, and generates a first binary code130that combines the mapping detection library117and the binary code of the identified code region.

In another embodiment, a user may create the mapping detection library, e.g., by using one or more programming languages, e.g., C, C++, Java ®, .Net, based on the flow chart depicted inFIG. 3. Then, the user may compile the mapping detection library in order to generate corresponding binary code of this mapping detection library.

At step135, by running the first binary code130which combines the mapping detection library117and the binary code of the identified code region, the processor is configured to monitor every memory access instruction (e.g., load instructions, store instructions, etc.) in the identified code region, e.g., by using the mapping detection library117. Specifically, while the processor is running the first binary code130, the mapping detection library117is configured to identify the memory addresses accessed by all load and store instructions in the identified code region, and is further configured to associate these load and store instructions identified code region with variables and arrays in the identified code region, e.g., by comparing memory address fields of the load and store instructions against memory addresses of these variables and arrays. The mapping detection library outputs that association (i.e., mapping140inFIG. 1).

FIG. 3illustrates a flow chart that describes method steps run by the mapping detection library117in conjunction with the static analysis tool. At step300, the static analysis tool determines memory address ranges of variables and arrays in the identified code region, e.g., based on debugging information. As described above, the static analysis tool classifies these variables and arrays, e.g., based on the characteristic of each variable and array.

At step310, the mapping detection library117is configured to intercept all memory access instructions in the identified code region, e.g., load and store instructions, while the processor is running the first binary code130. At step320, the mapping detection library is configured to determine a memory address range that each intercepted memory access instruction touches, e.g., based on a memory address field in each memory access instruction. At step330, the mapping detection library117is configured to compare the determined memory address range of each memory access instruction against memory address ranges of the third class of variables and arrays that has a false sharing risk. Binary code of the identified code region may show memory addresses of the third class of variables and arrays. If the comparison finds a match, the mapping detection library117is configured to classify the corresponding memory access instruction as an instruction at risk. Otherwise, i.e., if the comparison results in no match, the mapping detection library117is configured to filter out the corresponding memory access instruction. A filtered-out memory access instruction is no longer monitored at the final run-time analysis at160which is described in detail below. Thereby, the mapping detection library is configured to detect and flag a presence of the one or more instructions at risk while the processor is running the first binary code130. The number of instructions needed to be monitored during the final run at 160 are also significantly reduced.

Returning toFIG. 1, at step135, the mapping detection library117is configured to perform an initial run-time analysis: monitoring a memory access pattern of every load and store instruction in the identified code region while the processor is running the first binary code135. During this initial run-time analysis, the mapping detection library117is configured to record which array or variable each load and store instruction in the identified code region touches. The initial run-time analysis may also include a run-time evaluation of arrays and variables involved in the defined false sharing condition captured in step120. Once memory access patterns of all load and store instructions to all arrays and variables are detected and values of the variables in the defined false sharing condition are identified, the initial run-time analysis is aborted. In one embodiment, a user may eliminate a need of the initial run-time analysis, e.g., by modifying the compiler.

At step150, the instrumenting tool receives the binary code of the identified code region110, the mapping140, the classifications of the variables and arrays125, and a false sharing detection library145. The instrumenting tool generates a second binary code155that combines the binary code of the identified code region110, the mapping140, the classifications of the variables and arrays125, and the false sharing detection library145. Note that during the initial run135, the mapping detection library117was configured to identify the instructions at risk. The false sharing detection library is injected to the second binary code155in order to inspect and/or analyze only the instructions at risk determined by the mapping detection library117while the processor is running the second binary code155. Tongping Lu, et al., “Precise Detection and Automatic Mitigation of False Sharing, ” April, 2011, describes a false sharing detection library in detail, whose entire contents are incorporated by reference as if set forth herein.

At step160, while the processor running the second binary code155, the false sharing detection library is configured to monitor only the instructions at risk, and is further configured to capture a stream of addresses accessed by the instructions at risk, time stamps at the moment that the instructions at risk are run, and identification numbers of threads that run the instructions at risk. Furthermore, while the processor is running the second binary code155, the false sharing detection library145processes the memory address stream and detects that multiple threads may access different portion of the same cache line. While the processor is running the second binary code155, the false sharing detection library evaluates, based on the monitored memory access patterns of the instructions at risk, whether a thread writes on a portion of a certain cache memory line and whether a different thread also writes on a different portion of that certain cache memory line. In other words, the false sharing detection library determines, based on the monitored memory access patterns, whether two different portions of a cache memory line are accessed while the processor is running the second binary code155.

At step160, the false sharing detection library detects, based on the monitored memory access patterns, a false sharing of a cache memory line if two different portions of that cache memory line are accessed while the processor is running the second binary code155. In one embodiment, this detection may be performed by a simulation of running of method steps inFIG. 1. The false sharing detection library reports165a specific source code line(s) that causes a false sharing of a cache memory line. In one embodiment, therefore, based on one or two instrumenting of the identified code region, the false sharing detection library can identify a specific source code line(s) that causes a false sharing of a cache memory line. Upon receiving the report165of the false sharing, a user may update or rewrite the identified specific source code lines in order to prevent the occurrence of the false sharing. Then, the user may re-run method steps inFIG. 1with the updated or re-written source code.

Running of method steps inFIG. 1does not require additional hardware. In other words, by performing method steps inFIG. 1during running the generate original binary code, the false sharing detection library can detect a false sharing without a need for additional hardware for detecting of the false sharing. Since the mapping detection library can successfully prune out the instructions that are not at risk, the number of variables to be monitored is reduced when compared to known false sharing systems. The number of instructions to be monitored is also reduced when compared to known false sharing systems. By reducing the number of instructions and variables to be monitored, the processor can detect a false sharing of a cache memory line faster than known false sharing detection systems. Method steps inFIG. 1can be run with any commercially available processor and thus independent on processor designs or architectures.

In one embodiment, as shown inFIG. 2, method steps described inFIG. 1can be implemented by a computing system, e.g., a parallel computing system200including at least one processor255and at least one memory device270, a mainframe computer205including at least one processor256and at least one memory device271, a desktop computer210including at least one processor257and at least one memory device272, a workstation215including at least one processor258and at least one memory device273, a tablet computer220including at least one processor256and at least one memory device974, a netbook computer225including at least one processor260and at least one memory device275, a smartphone230including at least one processor261and at least one memory device276, a laptop computer235including at least one processor262and at least one memory device277, or cloud computing system240including at least one storage device245and at least one server device250.