CN118535352A - A multi-granularity remote memory runtime method based on user mode - Google Patents

Abstract

The invention discloses a multi-granularity remote memory runtime method based on user mode, which relates to the remote memory field, the invention introduces the support to the remote memory for the application written by the original C/C++/other language ecologically supported by LLVM by using the program analysis and program rewriting technology of the compiling period, and provides a new user mode remote memory runtime, the method can execute fine granularity management and swap-in and swap-out work of the remote memory in the user mode, and can enable the application to be compatible with the running time without source code level modification or with only a small amount of modification by the steps in the compiling period so as to consider the compatibility of the kernel mode solution and the high performance characteristic of the user mode solution. The invention has the advantages of high compatibility and high performance.

Description

A multi-granularity remote memory runtime method based on user mode

Technical Field

The present invention relates to the field of remote memory, and in particular to a multi-granularity remote memory runtime method based on user mode.

Background Art

With the advent of the big data era, memory-intensive applications in data centers are becoming more and more common. Such applications mainly include low-latency network applications (such as in-memory databases) and data-intensive applications (such as machine learning and graph computing). In this context, memory resources have gradually become one of the main bottlenecks in data centers.

There are two main problems caused by memory bottlenecks in data centers. One is the service instability and performance degradation caused by insufficient memory on a single machine. Modern operating systems usually use a memory swap mechanism to swap out cold pages to lower-level storage devices when memory pressure is high to achieve a certain degree of memory elasticity. However, the use of a swap mechanism will lead to a cliff-like drop in the performance of memory-intensive applications. According to data, about 790,000 tasks in Google's data centers were terminated due to memory pressure in a month. Existing solutions include using SSDs with higher I/O performance for page swapping, using memory compression technology, and using more aggressive page recycling mechanisms, but these only have a mitigating effect on performance issues. The second is the problem of single-machine memory utilization. For example, Google's tracking and analysis of data centers shows that applications often over-request memory, resulting in an actual memory utilization rate of only about 50%. Alibaba's research also shows that there is about 30% cold memory in data centers. Since the traditional monolithic server architecture lacks the ability to share memory across machines in the allocation and use of memory resources, these remaining memories cannot be efficiently shared with other servers at the data center level. Therefore, the lack of elasticity in memory allocation is also one of the key issues in memory allocation in data centers.

Memory disaggregation is a solution to the above problems proposed by the academic community in recent years. Its main content is to improve the elasticity of data center memory usage and improve the overall memory utilization rate by giving applications the ability to access memory on other nodes. The foundation of this technology lies in the Remote Direct Memory Access (RDMA) technology that has become increasingly mature in recent years. Through network devices that support RDMA, computing nodes can directly access the memory of remote nodes with microsecond delays, and do not require the participation of the remote node's CPU. Many studies have shown that memory-intensive applications can maintain high performance characteristics when the working set spans multiple nodes after being modified for RDMA. However, applying RDMA to the field of memory disaggregation, so that applications have the ability to use remote memory with little or no changes, requires redesigning the traditional software architecture that only targets local memory.

At present, research work in the field of remote memory is mainly divided into two mainstream directions:

The first is based on the kernel swap mechanism. Its main idea is to abstract the remote memory into a block device as a swap space of the system, and reuse the kernel swap mechanism to achieve the purpose of using remote memory. When an application accesses a page that is not in the local memory, the CPU will trigger a page fault and swap the page from the remote node to the local memory through the swap mechanism. Through the swap mechanism, the system will keep the hot page in the local memory and store the cold page in the remote memory. This idea uses page granularity to manage the remote memory. The advantage is that the application does not need to be modified, ensuring maximum compatibility. InfiniSwap first proposed and implemented this idea. In addition, the system robustness is ensured by asynchronously writing the swapped pages to the SSD. However, this method requires a complete kernel software stack, which will cause extremely high additional performance overhead, and the kernel's page swap page prefetching mechanism is not suitable for the scenario of fast access to remote memory. In addition, since the kernel swap mechanism itself is designed for disks, many of its internal algorithms are still being optimized for SSD scenarios (such as swap entry allocation algorithm), which is difficult to meet the high performance requirements of remote memory scenarios; the memory management method based on page granularity will also introduce the problem of read-write amplification.

The second is based on user-mode runtime, the main idea is to make changes to the object-oriented model mechanism, expand the object life cycle of the programming language, garbage collection mechanism, etc. to use remote memory. However, the disadvantage of this mechanism is the lack of compatibility, or dependence on a specific language runtime, or the need to make a lot of modifications to the application source code before it can run.

In addition to these two mainstream directions, the academic community also has a series of solutions that combine software and hardware, but the problem still lies in compatibility.

In summary, the current remote memory system solutions have a pair of incompatible contradictions: it is impossible to take into account both the advantages of high compatibility and high performance (low kernel overhead/low read/write amplification). In order to resolve this contradiction, the present invention starts from a point of entry that has not been tried in previous work: using compile-time program analysis and program rewriting technology to introduce support for remote memory to applications. The present invention proposes a new user-mode remote memory runtime, which can perform fine-grained management and swapping in and out of remote memory in user mode, and by introducing pointer flow analysis and instruction rewriting steps in the program compilation process, the application can be compatible with the runtime without source code level modification or only introducing a small amount of modification, so as to take into account the compatibility of kernel-mode solutions and the high-performance characteristics of user-mode solutions.

Summary of the invention

In view of the above-mentioned defects of the prior art, the technical problem to be solved by the present invention is how to achieve both high compatibility and high performance.

To achieve the above-mentioned purpose, the present invention provides a multi-granularity remote memory runtime method based on user state, which is characterized in that the present invention introduces support for remote memory for applications written in native C/C++/other languages supported by the LLVM ecosystem by using compile-time program analysis and program rewriting technology, and proposes a new user-state remote memory runtime, which can perform fine-grained management and swapping in and out of remote memory in user state. Through the compile-time steps, the application does not need to be modified at the source code level or only introduces a small amount of modification to be compatible with the runtime, so as to take into account the compatibility of the kernel-state solution and the high-performance characteristics of the user-state solution.

Furthermore, the compile-time part is based on the LLVM tool chain, and is mainly implemented as a compiler plug-in module in the compilation tool chain, which is called in the LLVM optimizer; the compiler plug-in module targets codes in the form of LLVM IR, and the compile-time function can support native C/C++ and other languages supported by the LLVM ecosystem and can be compiled into any language of LLVM IR.

Furthermore, for the native C/C++ code repository, the following steps are performed to generate an executable file that supports the remote memory:

S1.1 Mark the code for dynamic memory allocation;

The S1.2 code is translated into LLVM IR intermediate representation code by the Clang compiler;

After pre-optimization, S1.3 uses the results of S1.1 to perform pointer flow analysis and mark all pointers that may point to dynamically allocated memory;

S1.4 performs binary rewriting on all memory accesses that may point to dynamically allocated memory pointers according to the configuration file, and inserts calls to remote memory processing functions;

The S1.5 compiler performs data flow analysis on loops in the code, identifies memory access patterns in the loops, and inserts memory prefetching code at appropriate locations to guide the runtime library to prefetch data;

The S1.6 code is post-optimized to complete the complete optimization flow. The linker links the rewritten LLVM IR with the remote memory runtime library to generate an executable file.

Furthermore, in the step S1.1, the method of using dynamic memory allocation in the standard glibc is automatically marked by the clang compiler.

Furthermore, in the step S1.3, the pointer flow analysis refers to the flow-sensitive, non-context-sensitive Andersen pointer flow analysis algorithm, and other more accurate pointer flow analysis algorithms may also be used in actual applications.

Furthermore, the memory access mode in step S1.5 is sequential memory access.

Furthermore, the runtime process is divided into an initialization process and a memory access process;

The initialization process is performed when the application is started, and is mainly responsible for establishing an RDMA link with the memory management program on the remote memory node and performing initialization operations on the local cache data structure and the remote memory.

Furthermore, the initialization process includes the following steps:

S2.1 The application calls the initialization callback function of the remote memory runtime library; the function call will be automatically inserted into the application initialization logic by the compiler plug-in during compilation;

S2.2 After the application calls the initialization callback, the runtime library allocates a fixed-size local memory as a cache for the remote memory and initializes the local cache data structure;

S2.3 The runtime library establishes an RDMA connection with the memory node program;

S2.4 After successfully establishing a connection, the memory node program sends BaseVA and R_key information to the runtime library on the computing node. These two pieces of information are used to calculate the virtual address of the remote memory object on the memory node and send RDMA read and write requests;

The S2.5 runtime library sends a request to the remote memory node to register a memory of a specified size as the remote memory exclusively used by the application;

After receiving the request, the S2.6 memory node program allocates a memory of a specified size in the local memory area and initializes the memory;

S2.7 If the memory node has enough memory, the memory node program returns a registration success instruction to the runtime library; if the registration fails, the entire initialization process is exited;

After receiving the successful registration request, the S2.8 runtime library returns the control flow to the application.

Furthermore, the memory access process is called when the application is running. Since the compiler plug-in has translated the remote memory access instruction into a callback function for accessing the remote memory in the runtime library during compilation, the application will automatically call the memory access process when accessing the memory managed by the runtime library. To support memory management of multiple granularities, the runtime library manages memories of different sizes through different data structures, wherein small-granularity memory is managed through a set-associative cache, and large-granularity memory is managed through a page cache in the form of a linked list and a separate page address mapping table. In addition to the application's explicit call to the prefetch function, the runtime library will also implicitly prefetch the memory when accessing memory to improve remote memory performance.

Furthermore, the memory access process includes the following steps:

S3.1 The application triggers the memory access callback function of the runtime library by accessing the heap memory;

The S3.2 runtime library determines the memory access granularity through the parameters in the callback function, determines the cache data structure to use based on the granularity, and searches the memory in the corresponding data structure;

If the search is successful, it means that the memory object exists in the local cache, and then jump directly to S3.6 to return; if the search fails, it means that the memory object needs to be retrieved from the remote end, and it is necessary to continue from the following steps;

S3.3 If the local cache is full, a local cache eviction operation is required. The runtime library selects a victim object victim and writes it back to the remote memory by sending an RDMA write request, and vacates the cache location.

The S3.4 runtime library reads the remote memory into the local empty cache location by sending an RDMA read request;

S3.5 If the current application memory access mode is recognized by the runtime library, the runtime library's default prefetch strategy is used to perform prefetching at a certain distance. The default prefetch strategy is sequential access and strided access.

After completing the above steps, S3.6 returns the control flow to the application.

The present invention has the following technical effects:

1. For applications written in native C/C++/other languages supported by the LLVM ecosystem, no or only a small amount of modification is required to enable them to support user-mode remote memory functions;

2. Remote memory access no longer uses OS memory pages as a fixed granularity, effectively reducing read and write amplification during remote memory access;

3. Improve the hit rate of remote memory prefetching and reduce the memory access waiting time in more complex memory access modes through prefetch optimization.

The concept, specific structure and technical effects of the present invention will be further described below in conjunction with the accompanying drawings to fully understand the purpose, characteristics and effects of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a system diagram of a preferred embodiment of the present invention;

FIG2 is a compile-time process and code example of a preferred embodiment of the present invention;

FIG3 is a run-time initialization process of a preferred embodiment of the present invention;

FIG. 4 is a schematic diagram of the runtime memory access process and data structure of a preferred embodiment of the present invention.

DETAILED DESCRIPTION

The following describes several preferred embodiments of the present invention with reference to the drawings in the specification, so that the technical content is clearer and easier to understand. The present invention can be embodied in many different forms of embodiments, and the protection scope of the present invention is not limited to the embodiments mentioned in the text.

In the drawings, components with the same structure are indicated by the same numerical reference numerals, and components with similar structures or functions are indicated by similar numerical reference numerals. The size and thickness of each component shown in the drawings are arbitrarily shown, and the present invention does not limit the size and thickness of each component. In order to make the illustration clearer, the thickness of the components is appropriately exaggerated in some places in the drawings.

As shown in Figure 1, the present invention introduces support for remote memory for applications written in native C/C++/other languages supported by the LLVM ecosystem by using program analysis and program rewriting technology during compilation, and proposes a new user-mode remote memory runtime, which can perform fine-grained management and swapping in and out of remote memory in user mode. Through the aforementioned steps during compilation, the application does not need to be modified at the source code level or only introduces a small amount of modification to be compatible with the runtime, so as to take into account the compatibility of the kernel-mode solution and the high-performance characteristics of the user-mode solution. The following examples describe the specific steps during compilation and during runtime.

1. Compilation period

The compile-time part is based on the LLVM toolchain, and is mainly implemented as a compiler plug-in module in the compilation toolchain, which is called in the LLVM optimizer. Since the compiler plug-in module targets the code in the form of LLVM IR (intermediate representation), in theory, the compile-time function can support native C/C++ and any other language supported by the LLVM ecosystem that can be compiled into LLVM IR. Referring to Figure 2 in the attached figure, for the native C/C++ code repository, perform the following steps to generate an executable file that supports remote memory:

S1.1 Annotate the code for dynamic memory allocation. The clang compiler automatically annotates the dynamic memory allocation method used in the standard glibc.

The S1.2 code is translated into LLVM IR intermediate representation code by the Clang compiler;

After pre-optimization, S1.3 uses the result of S1.1 to perform pointer flow analysis (in the figure, it is written as the non-flow-sensitive and non-context-sensitive Andersen pointer flow analysis algorithm. In actual application, other more accurate pointer flow analysis algorithms can also be used to mark all possible pointers pointing to dynamically allocated memory.

S1.4 performs binary rewriting on all memory accesses that may point to dynamically allocated memory pointers according to the configuration file, and inserts calls to remote memory processing functions;

The S1.5 compiler performs data flow analysis on the loops in the code, identifies the memory access mode in the loop (sequential memory access mode in the example), and inserts memory prefetch code at the appropriate location to guide the runtime library to perform data prefetching.

The S1.6 code is post-optimized to complete the optimization process. The linker links the rewritten LLVM IR with the remote memory runtime library to generate an executable file.

A specific example of code rewriting is shown in Figure 2. It can be seen that only step S1.1 in the above steps requires a small modification of the application code, which is a major innovation of this patent compared to other user-mode solutions that introduce very few modifications to the application.

2. Operation period

The runtime process is divided into initialization process and memory access process.

The initialization process is performed when the application starts. It is mainly responsible for establishing an RDMA link with the memory manager on the remote memory node and initializing the local cache data structure and the remote memory. As shown in Figure 3, the process mainly performs the following steps:

S2.1 The application calls the initialization callback function of the remote memory runtime library (hereinafter referred to as the "runtime library"). This function call will be automatically inserted into the application initialization logic by the compiler plug-in during compilation;

S2.2 After the application calls the initialization callback, the runtime library allocates a fixed-size local memory as a cache for the remote memory and initializes the local cache data structure;

S2.3 The runtime library establishes an RDMA connection with the memory node program (the handshake step required to establish the RDMA link is omitted here);

S2.4 After successfully establishing a connection, the memory node program sends BaseVA and R_key information to the runtime library on the computing node. These two pieces of information are used to calculate the virtual address of the remote memory object on the memory node and send RDMA read and write requests;

The S2.5 runtime library sends a request to the remote memory node to register a memory of a specified size as the remote memory exclusively used by the application;

After receiving the request, the S2.6 memory node program allocates a memory of a specified size in the local memory area and initializes the memory;

S2.7 If the memory node has enough memory, the memory node program returns a registration success instruction to the runtime library; if the registration fails, the entire initialization process is exited;

After receiving the successful registration request, the S2.8 runtime library returns the control flow to the application.

The memory access process is called when the application is running. Since the compiler plug-in has translated the remote memory access instructions into the callback function for accessing remote memory in the runtime library during compilation, the application will automatically call the memory access process when accessing the memory managed by the runtime library. As shown in Figure 4, in order to support memory management of multiple granularities, the runtime library manages memories of different sizes through different data structures, where small-granularity memory (256B, 512B, 1K, 2K) is managed through a set-associative cache, and large-granularity memory (greater than or equal to 4K) is managed through a page cache in the form of a linked list and a separate page address mapping table. In addition to the application's explicit call to the prefetch function, the runtime library will also implicitly prefetch the memory when accessing memory to improve remote memory performance. The specific steps of the memory access process are as follows:

S3.1 The application triggers the memory access callback function of the runtime library by accessing the heap memory;

The S3.2 runtime library determines the memory access granularity through the parameters in the callback function, determines the cache data structure to use based on the granularity, and searches the memory in the corresponding data structure;

If the search is successful, it means that the memory object exists in the local cache, and then jump directly to S3.6 to return. If the search fails, it means that the memory object needs to be retrieved from the remote end, and you need to continue with the following steps:

S3.3 If the local cache is full, a local cache eviction operation is required. The runtime library selects a victim object and writes it back to the remote memory by sending an RDMA write request, freeing up the cache location.

The S3.4 runtime library reads the remote memory into the local empty cache location by sending an RDMA read request;

S3.5 If the current application memory access mode is recognized by the runtime library, the runtime library's default prefetch strategy is used to perform prefetching at a certain distance. The default prefetch strategy includes sequential access, strided access, etc.

After completing the above steps, S3.6 returns the control flow to the application.

The preferred specific embodiments of the present invention are described in detail above. It should be understood that ordinary technicians in the field can make many modifications and changes based on the concept of the present invention without creative work. Therefore, all technical solutions that can be obtained by technicians in the technical field based on the concept of the present invention through logical analysis, reasoning or limited experiments on the basis of the prior art should be within the scope of protection determined by the claims.

Claims (10)

1. The invention provides a user-mode-based multi-granularity remote memory runtime method, which is characterized in that the method introduces support to remote memory for applications written in native C/C++/other languages ecologically supported by LLVM by using a program analysis and program rewriting technology in a compiling period, and provides a new user-mode remote memory runtime, wherein fine granularity management and swap-in and swap-out work of the remote memory can be executed in a user mode, and the applications can be compatible with the runtime without source code level modification or with only a small amount of modification by using the compiling period step, so that the compatibility of a kernel-mode solution and the high performance characteristics of the user-mode solution are considered.

2. The user-state-based multi-granularity remote memory runtime method of claim 1, wherein the compile-time is based in part on an LLVM tool chain, implemented primarily as a compiler plug-in module in the compile tool chain, invoked in an LLVM optimizer; the compiler plug-in module is aimed at codes in the form of LLVM IR, and the compiling period function can support native C/C++ and other languages which are supported by LLVM ecology and can be compiled into LLVM IR.

3. The user-state-based multi-granularity remote memory runtime method of claim 2, wherein for a native C/c++ code repository, performing the steps of generating an executable file that supports the remote memory:

s1.1, marking a part of dynamic memory allocation in a code;

S1.2, translating the codes into LLVM IR intermediate representation codes through a Clang compiler;

S1.3, after pre-optimization, performing pointer flow analysis by using the result of S1.1, and marking all pointers possibly pointing to the dynamic allocation memory;

S1.4, according to the configuration file, performing binary rewrite on all accesses possibly pointing to the dynamically allocated memory pointer, and inserting the call of a remote memory processing function;

S1.5, the compiler analyzes the data stream of the circulation in the code, identifies the access mode in the circulation, and inserts the memory pre-substitution code at a proper position to guide the database to pre-fetch the data during operation;

S1.6, the code completes the complete optimized flow through post-optimization. And the linker links the rewritten LLVM IR with a remote memory runtime library to generate an executable file.

4. The user-state-based multi-granularity remote memory runtime method of claim 3, wherein in step S1.1, the manner in which dynamic memory allocation in standard glibc is used is automatically marked by clang compiler.

5. The user-state-based multi-granularity remote memory runtime method of claim 4, wherein in step S1.3, the pointer flow analysis refers to a flow-sensitive, non-context-sensitive Andersen pointer flow analysis algorithm, and other more accurate pointer flow analysis algorithms can be used instead in practice.

6. The user-state-based multi-granularity remote memory runtime method of claim 5, wherein said memory access pattern in step S1.5 is a sequential memory access.

7. The user-state-based multi-granularity remote memory runtime method of claim 6, wherein the runtime process is divided into an initialization process and a memory access process;

the initialization process is performed when the application is started, and is mainly responsible for establishing RDMA (remote direct memory access) links with a memory management program on a remote memory node and initializing a local cache data structure and a remote memory.

8. The user-state based multi-granularity remote memory runtime method of claim 7, wherein the initializing process comprises the steps of:

s2.1, an application program calls an initialization callback function of a remote memory runtime library; the function call is automatically inserted into the application initialization logic by the compiler plug-in at compile time;

S2.2, after the application calls an initialization callback, the runtime library allocates a local memory with a fixed size as a cache of a remote memory for use, and initializes a local cache data structure;

s2.3, establishing RDMA connection between the runtime library and the memory node program;

S2.4, after the connection is successfully established, the memory node program sends BaseVA and R_key information to a runtime library on the computing node, wherein the two information are used for computing virtual addresses on the memory node of the remote memory object and sending RDMA read-write requests;

S2.5, the runtime library sends a request to a remote memory node, and registers a section of memory with a specified size as the remote memory exclusive to the application;

s2.6, after receiving the request, the memory node program allocates a section of memory with a specified size in the local memory area, and initializes the section of memory;

S2.7, if the memory node has enough memory, the memory node program returns a registration success instruction to the runtime library; if the registration fails, exiting the whole initialization flow;

S2.8, after receiving the request of successful registration, the runtime library returns the control flow to the application program.

9. The user-mode based multi-granularity remote memory runtime method of claim 8 wherein the memory access process is invoked at application runtime, the application automatically invoking the memory access process when accessing memory managed by the runtime library, since the compiler plug-in has translated remote memory access instructions into callback functions in the runtime library that access remote memory; in order to support memory management with multiple granularities, memories with different sizes are managed in a runtime library through different data structures, wherein small granularity memories are managed through group-associated caches, and large granularity memories are managed through page caches in a linked list form and an independent page address mapping table; in addition to applying explicit calls to prefetch functions, the runtime library can implicitly prefetch memory at memory access to improve remote memory performance.

10. The user-state-based multi-granularity remote memory runtime method of claim 9, wherein the memory access process comprises the steps of:

S3.1, triggering a memory access callback function of a runtime library by the application program in a mode of accessing a heap memory;

s3.2, the runtime library judges the granularity of access memory according to the parameters in the callback function, judges the used cache data structure according to the granularity, and searches the memory in the corresponding data structure;

if the search is successful, indicating that the memory object exists in the local cache, directly jumping to S3.6 for returning; if the search fails, the memory object is required to be retrieved from the remote end, and the following steps are required to be continued;

S3.3, if the local cache is full, local cache eviction operation is needed, the runtime library selects a victim object victim to write the victim object victim back to the remote memory by sending an RDMA write request, and the cache location is vacated;

S3.4, the runtime library reads the remote memory into a local empty cache position by sending an RDMA read request;

s3.5, if the current application access mode is identified by the runtime library, prefetching is performed for a certain distance by using a default prefetching strategy of the runtime library. Default prefetch policies are, for example, sequential access, cross access strided.

S3.6, after the steps are finished, the control flow is returned to the application program.