CN118820134A - Cache consistency optimization method in automatic thread-level parallelization - Google Patents

Abstract

The present disclosure relates to the field of computer technology, and in particular, to a cache coherence optimization method in automatic thread-level parallelization, the method comprising: obtaining a consistency shared variable; according to the consistency shared variable, searching access instructions accessing the consistency shared variable from all access instructions, and determining the access instructions as consistency instructions; according to a preset rule, determining a corresponding consistent instruction stream fragment and a private instruction stream fragment which does not contain a consistent instruction of each consistent instruction, generating a first target instruction subsequence for maintaining cache consistency for each consistent instruction stream fragment, and generating a second target instruction subsequence for not maintaining cache consistency for each private instruction stream fragment. The method can realize that the fragments of the consistent instruction stream are as small as possible, effectively reduce the overhead of cache consistency added by private variable access and the influence thereof, and the alternate times of the opening and closing of the cache consistency are as small as possible, thereby avoiding excessive additional overhead and further reducing the overhead.

Description

Cache consistency optimization method in automatic thread-level parallelization

Technical Field

The present disclosure relates to the field of computer technology, and in particular to a cache consistency optimization method in automatic thread-level parallelization.

Background Art

Each processor core on a modern many-core processor has a cache to increase data access speed and ensure ease of program writing. When running parallel programs, multiple threads or processes running on multiple processor cores may read and write data in the same shared memory area. In order to ensure the correctness of parallel program execution, cache coherence is required between different processors in the same computing node and between different processor cores of the same processor, so that the same data remains consistent between the caches of multiple processor cores. Therefore, many-core processors need to have a hardware system that maintains cache coherence.

With the continuous development of computer technology, almost all applications running on supercomputers have achieved process-level parallelism. However, in most cases, there is no shared memory area or variable between different processes, so cache consistency operations are usually not required between two processes. Some applications may have both process-level and thread-level parallelism capabilities, that is, a process will contain multiple threads running in the same computing node. Since all threads belonging to the same process share the memory space of the process, cache consistency operations are usually required between these threads. Nevertheless, each thread will also have private variables, so there will not be shared use of all variables between threads; even for the same shared variable, it may be shared read and written between multiple threads in a certain program segment, and may be privately used by each thread in another program segment. It can be seen that most cache consistency operations are redundant. Maintaining cache consistency will not only reduce the performance of parallel programs, but also increase the pressure of hardware system design. Therefore, a cache consistency optimization method in automatic thread-level parallelization is urgently needed.

The prior art introduces a solution for turning on and off the state of cache consistency, but this solution still cannot fully reduce the operation overhead.

Summary of the invention

The present disclosure provides a cache consistency optimization method, apparatus, device and storage medium in automatic thread-level parallelization.

In a first aspect, the present disclosure provides a cache consistency optimization method in automatic thread-level parallelization, comprising:

The compiler obtains all consistent shared variables in response to thread-level automatic parallelization compilation of a loop;

According to the consistent shared variable, searching for a memory access instruction for accessing the consistent shared variable from each memory access instruction, and determining the memory access instruction as a consistent instruction;

According to preset rules, the consistent instruction stream fragments corresponding to each of the consistent instructions and the private instruction stream fragments not containing the consistent instructions are determined, a first target instruction subsequence maintaining cache consistency is generated for each of the consistent instruction stream fragments, and a second target instruction subsequence not maintaining cache consistency is generated for each of the private instruction stream fragments;

The first target instruction subsequence and the second target instruction subsequence both correspond to a target processor; the target processor has the function of maintaining cache consistency between cores and supports executing memory access instructions when cache consistency is turned off.

In one embodiment, the compiler obtains all consistent shared variables in response to thread-level automatic parallelization compilation of a loop, including at least one of the following methods:

Acquire a cache consistency setting command from the guidance instruction of the automatic parallel compilation, and acquire all consistent shared variables from the cache consistency setting command;

Acquire attribute information of each variable, determine whether each variable is a consistent shared variable based on the attribute information, and determine all consistent shared variables.

In one embodiment, the method further comprises:

A current compilation option corresponding to the compiler is obtained, and a cache consistency compilation setting is obtained from the current compilation option. When the cache consistency compilation setting is to turn off cache consistency optimization, all variables are regarded as consistent shared variables.

In one embodiment, the target processor has a function of maintaining cache consistency between cores and supports executing memory access instructions with cache consistency turned off, including at least one of the following methods:

The target processor provides a cache consistency enable instruction and a cache consistency disable instruction, wherein the cache consistency enable instruction is used to set the state of the cache consistency protocol of the current processor core to the enable state, and the cache consistency disable instruction is used to set the state of the cache consistency protocol of the current processor core to the disable state;

The target processor provides cache coherent memory access instructions, private memory access instructions or ordinary memory access instructions, wherein the cache coherent memory access instructions initiate cache coherence operation requests when executed under any circumstances, the private memory access instructions do not initiate cache coherence operation requests when executed under any circumstances, the ordinary memory access instructions initiate cache coherence operation requests when the cache coherence protocol of the current processor core is in an on state, and the ordinary memory access instructions do not initiate cache coherence operation requests when the cache coherence protocol of the current processor core is in a off state; wherein, after a memory access instruction initiates a cache coherence operation request, the hardware system determines whether the current processor core is to initiate a cache coherence operation based on the coherence protocol state of the cache block corresponding to the request.

In one embodiment, the method further comprises:

When the cache coherence protocol of the current processor core is in the off state and a memory access instruction other than the cache coherence memory access instruction is executed, no operation related to cache coherence is initiated to the cache coherence hardware system;

The cache coherence closing instruction has a response opening mode and a response closing mode;

After executing the cache coherence closing instruction in the response opening mode, the current processor core always responds to the cache coherence operation initiated by other processor cores;

After executing the cache coherence shutdown instruction in the response shutdown mode, the current processor core ignores cache coherence operations initiated by other processor cores.

In one embodiment, generating a first target instruction subsequence for maintaining cache consistency for each of the consistent instruction stream fragments includes at least one of the following methods:

Each of the consistency instructions in each of the consistency instruction stream fragments corresponds to one of the cache consistent memory access instructions or one of the common memory access instructions in the first target instruction subsequence;

The first instruction of the first target instruction subsequence of one of the consistent instruction stream fragments is a cache consistency enable instruction, or the last instruction of the first target instruction subsequence of one of the consistent instruction stream fragments is a cache consistency disable instruction.

In one embodiment, generating a second target instruction subsequence that does not maintain cache coherence for each of the private instruction stream fragments includes at least one of the following methods:

Each memory access instruction in each of the private instruction stream fragments corresponds to one of the private memory access instructions or one of the common memory access instructions in the second target instruction subsequence;

The first instruction of the second target instruction subsequence of one of the private instruction stream fragments is a cache coherence off instruction, or the last instruction of the second target instruction subsequence of one of the private instruction stream fragments is a cache coherence on instruction.

In one embodiment, the determining of the consistent instruction stream segments corresponding to each consistent instruction and the private instruction stream segments not including the consistent instruction comprises:

Each of the consistent instruction stream fragments includes one or more instructions, and when only one instruction is included, the instruction is the consistent instruction;

Each instruction stream segment other than all the consistent instruction stream segments of the loop is determined as a private instruction stream segment.

In one embodiment, the step of determining the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule comprises:

Obtaining data dependencies between the consistency instructions;

Aggregate at least two consistent instructions with data dependencies into the same consistent instruction stream segment.

In one embodiment, the step of determining the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule comprises:

Obtaining data dependencies between the consistency instructions;

Scheduling at least two coherent instructions that have no data dependency relationship with each other to adjacent positions;

Aggregate the scheduled adjacent consistency instructions into the same consistency instruction stream fragment.

In one embodiment, the step of determining the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule comprises:

Determining a consistency instruction corresponding to the consistency shared variable in a plurality of iterations of a loop;

The consistency instructions corresponding to the consistency shared variables in multiple iterations are aggregated into the same consistency instruction stream segment.

In one embodiment, the step of determining the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule comprises:

According to the number N of the consistent shared variables, create a temporary array with N elements;

At intervals of N iterations, N elements of each of the coherent shared variables are read into the temporary array at one time or N elements of the temporary array are assigned to the coherent shared variables at one time; instructions for accessing each of the coherent shared variables are replaced with array access instructions for the temporary array;

The memory access instructions corresponding to the one-time read and the one-time assignment are added to the consistent instruction stream segment.

In one embodiment, the step of determining the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule comprises:

Acquire at least two consistent instructions within a preset range in execution order and memory access instructions between the consistent instructions within the preset range, and determine them as instructions to be merged;

Calculating the consistency operation overhead generated by the memory access instructions between the consistency instructions within a preset range when the instructions to be merged are merged into a consistency instruction stream segment, to obtain a first operation overhead;

Calculate the operation overhead reduced by reducing the number of times the state of the cache coherence protocol is turned on and off when the instructions to be merged are merged into a coherent instruction stream segment, to obtain a second operation overhead;

When the first operation overhead is less than the second operation overhead, it is determined that the instructions to be merged are merged into a consistent instruction stream segment.

In one embodiment, the step of determining the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule comprises:

Obtaining the number of memory access instructions between at least two consistent instructions within a preset range in execution order, and determining the number of other memory access instructions;

When the number of other memory access instructions is less than or equal to a preset instruction number threshold, at least two consistent instructions within a preset range in execution order and memory access instructions between consistent instructions within the preset range are merged into a consistent instruction stream segment.

In one embodiment, the step of determining the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule comprises:

A mutually exclusive region in the cache is determined, and all instructions in the mutually exclusive region are merged into a consistent instruction stream segment.

In one embodiment, the method further comprises:

In response to the execution of the data prefetch instruction, detecting whether at least one memory access instruction among the memory access instructions triggering the data prefetch instruction is a cache coherent memory access instruction or corresponds to an on state of a cache coherence protocol;

When at least one memory access instruction among the memory access instructions that trigger the data prefetch instruction is a cache coherent memory access instruction or corresponds to an on state of a cache coherence protocol, determining to initiate a cache coherence operation request when executing the data prefetch instruction;

When all memory access instructions that trigger the data prefetch instruction are private memory access instructions or correspond to a closed state of a cache coherence protocol, it is determined that no cache coherence operation request is initiated when executing the data prefetch instruction.

In a second aspect, the present disclosure provides a cache consistency optimization device in automatic thread-level parallelization, comprising:

Shared variable acquisition module, used to obtain consistent shared variables;

An instruction determination module, configured to find a memory access instruction for accessing the consistent shared variable from each memory access instruction according to the consistent shared variable, and determine the memory access instruction as a consistent instruction;

An instruction stream segment determination module, used to determine the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule;

An instruction insertion module is used to insert a cache consistency enable instruction before the execution order of each of the consistency instruction stream fragments, and insert a cache consistency disable instruction after the execution order of each of the consistency instruction stream fragments, wherein the cache consistency enable instruction is used to set the state of the cache consistency protocol of the current processor core to the enable state, and the cache consistency disable instruction is used to set the state of the cache consistency protocol of the current processor core to the disable state.

In a third aspect, the present disclosure provides a computer device, including a memory, a processor, and a computer program stored in the memory, wherein the processor executes the computer program to implement the steps of the method described in the above aspects.

In a fourth aspect, the present disclosure provides a computer-readable storage medium having a computer program stored thereon, which implements the steps of the method described in the above aspects when executed by a processor.

In a fifth aspect, the present disclosure provides a computer program product, including a computer program/instructions, which implements the steps of the method described in the above aspects when the computer program is executed by a processor.

The present disclosure provides a cache consistency optimization method, apparatus, device and storage medium in automatic thread-level parallelization, which can achieve the smallest possible consistency instruction stream fragments, effectively reduce the cache consistency overhead and its impact added by private variable access, and because the number of cache consistency on and off alternations is as small as possible, the calling frequency of cache consistency on and off instructions can be reduced, avoiding excessive additional overhead, thereby further reducing overhead.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic flow chart of a cache consistency optimization method in automatic thread-level parallelization provided by an embodiment of the present disclosure;

FIG2 is a schematic diagram of the structure of a cache consistency optimization device in automatic thread-level parallelization provided by an embodiment of the present disclosure;

FIG3A is a code implementation process of an OpenMP parallel program;

FIG3B is a diagram showing the implementation process of specifying consistent program fragments in a coarse-grained manner;

FIG3C is an implementation process of specifying consistent program fragments in a fine-grained manner;

FIG3D is an implementation process of specifying consistent shared variables based on guidance instructions for automatic parallel compilation provided by an embodiment of the present disclosure.

DETAILED DESCRIPTION

In order to make the purpose, technical solution and advantages of the present application more clearly understood, the present application is further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present application and are not used to limit the present application.

In order to enable those skilled in the art to better understand the technical solution of the present disclosure, and to fully understand and implement how the present disclosure applies technical means to solve technical problems and achieve the corresponding technical effects, the technical solution in the embodiments of the present disclosure will be clearly and completely described below in conjunction with the drawings in the embodiments of the present disclosure. Obviously, the described embodiments are only embodiments of a part of the present disclosure, not all of the embodiments. The embodiments of the present disclosure and the various features in the embodiments can be combined with each other without conflict, and the technical solutions formed are all within the scope of protection of the present disclosure. Based on the embodiments in the present disclosure, all other embodiments obtained by ordinary technicians in this field without making creative work should fall within the scope of protection of the present disclosure.

It should be noted that the terms "first", "second", etc. in the specification and claims of the present disclosure and the above-mentioned drawings are used to distinguish similar objects, and are not necessarily used to describe a specific order or sequence. It should be understood that the data used in this way can be interchangeable where appropriate, so that the embodiments of the present disclosure described herein can be implemented in an order other than those illustrated or described herein. In addition, the terms "including" and "having" and any variations thereof are intended to cover non-exclusive inclusions, for example, a process, method, system, product, or device that includes a series of steps or units is not necessarily limited to those steps or units that are clearly listed, but may include other steps or units that are not clearly listed or inherent to these processes, methods, products, or devices.

It should be noted that the steps shown in the flowcharts of the accompanying drawings can be executed in a computer system such as a set of computer executable instructions, and that, although a logical order is shown in the flowcharts, in some cases, the steps shown or described can be executed in an order different from that shown here.

There are two main cache consistency protocols: the snooping-based consistency protocol (hereinafter referred to as the snooping protocol) and the directory-based consistency protocol (hereinafter referred to as the directory protocol). The implementation of the snooping protocol relies on a bus or bus-like network connection. Using this network connection, all requests issued by the private cache of a single processor core will be broadcast to the private caches of all other processor cores in the system, and the access requests of all processors can also be sequenced on this bus to achieve the requirements for access order in the cache consistency model and the storage identity model. The snooping protocol can also handle multiple conflicting requests for the same data block well through the bus structure, and the private caches of multiple processors can also communicate directly through this bus structure, reducing communication delays. However, since all requests are transmitted through the bus, and the bus bandwidth resources are limited, it will affect the scalability of the entire system. The directory protocol uses a directory structure to manage cache lines. In the directory protocol, the memory access request issued by the private cache of the processor core will first be sent to the directory structure that owns the corresponding cache block. This directory structure records the sharing status of the current cache block. The directory structure controller will choose to respond to this request or forward this request to the private cache of other corresponding processor cores according to the status of the current cache block. This method does not need to rely on a network with a specific topology, and reduces bandwidth consumption in the network through point-to-point direct communication, which is easy to expand. However, in the implementation of the directory protocol, all requests must be processed through the directory structure, which will introduce additional delays.

For example, in commercial processors from companies such as AMD, the snooping protocol is mainly used to achieve cache consistency. Currently, the number of cores in a CPU has reached nearly 100, and a computing node in a supercomputer usually has two CPUs, which requires the snooping protocol to support the cache consistency of nearly 200 processor cores. This not only brings difficulties to the design and layout of the bus, but also makes the bus bandwidth resources more restrictive on the performance of parallel programs. As the number of processor cores in the same CPU or the same computing node increases, the directory protocol will also encounter bottleneck problems, such as the directory becoming larger and the access delay increasing. It can be seen that the cache consistency maintenance overhead not only affects the performance of parallel programs, but also increases the pressure on hardware system design.

In order to reduce the overhead brought by cache consistency to the application, the existing technology has proposed a method to reduce redundant cache consistency operations (China Patent No.: 202410831240.X), which initiates cache consistency closing instructions and opening instructions through the current thread of the application to realize the closing and opening of the cache consistency protocol of the current processor core. This technology points out that it is necessary to insert cache consistency closing instructions and opening instructions into the program code or assembly code by the programmer or compiler. In order to minimize the impact of cache consistency overhead, the cache consistency of each thread can be set to the closed state by default, and when the thread is running an instruction to access shared variables between processes or threads, the cache consistency is set to the open state. Although this can avoid the overhead of consistency operations generated by accessing private variables, there is a problem after using this existing technology to open and close the state of the consistency protocol: frequently opening and closing the state of the cache consistency protocol leads to increased system overhead.

To this end, in the scheme of the present application, the compiler, in response to thread-level automatic parallelization compilation of a loop, obtains a cache consistency setting command from the guidance instruction of the automatic parallelization compilation, obtains all consistency shared variables from the cache consistency setting command, finds all access instructions of all consistency shared variables from the complete instruction stream of the loop generated by the thread-level automatic parallelization compilation optimization, determines all consistency instruction stream fragments (i.e., a section of instruction stream that needs to maintain cache consistency) from the complete instruction stream, performs cache consistency operations when executing instructions in the consistency instruction stream fragment, and does not perform cache consistency operations when executing instructions outside the consistency instruction stream fragment.

In this way, the consistency instruction stream fragment can be made as small as possible, effectively reducing the cache consistency overhead and its impact caused by private variable access. In addition, since the number of alternations of turning cache consistency on and off is as small as possible, the calling frequency of cache consistency on and off instructions can be reduced, avoiding excessive additional overhead, thereby further reducing overhead.

Since multiple threads belonging to the same process share the storage space of the process, there are usually more consistent instruction stream fragments under thread-level parallelism. In a general environment with cache and its consistency protocol, thread-level parallelism is often conveniently implemented using compilation guidance instructions such as OpenMP and the automatic parallelization function of the compiler. For example, Figure 3A shows a typical OpenMP parallel program with two loops, in which the first loop calculates the shared variable A, and the second loop uses the shared variable A and calculates the shared variable B. Figure 3B shows a coarse-grained method for explicitly specifying a consistent program fragment (a source program fragment that needs to maintain cache consistency) for the thread-level parallel program in Figure 3A, in which both loops access the shared variable A and the shared variable A calculated by the first loop will be used by the second loop, so both loops are placed in the same consistent program fragment. This coarse-grained method causes the calculation process of private variables in both loops to trigger cache consistency operations, resulting in the inability to effectively reduce the overhead of cache consistency. FIG3C shows a fine-grained method for explicitly specifying consistent program fragments for the thread-level parallel program in FIG3A , in which only a small amount of calculations involving shared variables in each loop are set as consistent program fragments, and consistency enable instructions and cache consistency disable instructions are inserted before and after almost every instruction involving shared variables. Although this fine-grained method can minimize the overhead of cache consistency, each loop body will execute cache consistency enable instructions and disable instructions, which will bring considerable additional overhead. To this end, it is necessary to optimize the opening and closing of the cache consistency state, and then solve the problem of how to automatically insert cache consistency enable instructions and disable instructions in the process of automatic thread-level parallelization, so as to achieve the goal of keeping the consistency instruction stream fragment as small as possible and the number of executions of cache consistency enable instructions and disable instructions as small as possible. The method provided by the present application will be described in detail below through specific embodiments.

Embodiment 1

FIG1 is a flow chart of a cache consistency optimization method in automatic thread-level parallelization provided by an embodiment of the present disclosure. As shown in FIG1 , a cache consistency optimization method in automatic thread-level parallelization includes:

Step 110 : In response to thread-level automatic parallelization compilation of a loop, the compiler obtains all consistent shared variables.

In this embodiment, a consistent shared variable is a variable in the cache that is accessed and processed by multiple processor cores, while a variable in the cache that can only be accessed and processed by one processor core is a private variable. In this embodiment, the consistent shared variable is determined to enable each processor core to maintain the consistency of the shared variable for each processor core when accessing and processing the shared variable.

In this embodiment, the consistent shared variables are determined from the variables in the cache. The process of determining the consistent shared variables is as follows: the compiler, in response to the thread-level automatic parallelization compilation of a loop, obtains the cache consistency setting command from the guidance instruction of the automatic parallelization compilation, and obtains all the consistent shared variables from the cache consistency setting command. Thus, all the consistent shared variables in the threads of a loop are obtained.

The compiler can complete the compilation from the original high-level language program to the assembly language or binary program, and perform compilation optimization to improve the speed of program execution. During the compilation optimization process, the compiler will have an intermediate language. Based on the intermediate language, the variable corresponding to each memory access instruction in the instruction stream can be determined, so the memory access instruction that accesses any consistent shared variable can be found from the complete instruction stream.

Step 120 : According to the coherent shared variable, a memory access instruction for accessing the coherent shared variable is searched from various memory access instructions, and the memory access instruction is determined to be a coherent instruction.

In this embodiment, each memory access instruction refers to a plurality of memory access instructions executed in sequence, and may also be a plurality of memory access instructions in a complete instruction stream of a loop generated by the compiler from thread-level automatic parallel compilation optimization.

In this embodiment, all memory access instructions for accessing and processing shared variables are found from a complete instruction stream, and these memory access instructions are determined as consistent instructions, that is, the consistent instructions are memory access instructions for accessing shared variables.

The memory access instructions in this embodiment include both explicit memory access instructions such as load and store, and implicit memory access instructions such as hardware data prefetch. It can be understood that in order to keep the same data consistent between the caches of multiple processor cores, the state of the cache consistency protocol of each processor core is enabled by default.

Step 130, according to preset rules, determine the consistency instruction stream fragments corresponding to each of the consistency instructions and the private instruction stream fragments that do not contain the consistency instructions, generate a first target instruction subsequence that maintains cache consistency for each of the consistency instruction stream fragments, and generate a second target instruction subsequence that does not maintain cache consistency for each of the private instruction stream fragments; wherein, the first target instruction subsequence and the second target instruction subsequence both correspond to a target processor; the target processor has the function of maintaining cache consistency between cores, and supports executing memory access instructions when cache consistency is turned off.

In this embodiment, when the target processor has a cache-coherent memory access instruction, a first target instruction subsequence of a consistent instruction stream fragment can be generated based on the cache-coherent memory access instruction, wherein a corresponding cache-coherent memory access instruction in the first target instruction subsequence needs to be generated for each consistent instruction in the consistent instruction stream fragment, so that cache consistency of multiple threads accessing consistent shared variables in parallel can be maintained during the execution of the first target instruction subsequence.

When the target processor has private memory access instructions, a second target instruction subsequence of a private instruction stream fragment can be generated based on the private memory access instructions, wherein a corresponding private memory access instruction in the second target instruction subsequence needs to be generated for each memory access instruction in the private instruction stream fragment, so that no cache consistency operation request is initiated during the execution of the second target instruction subsequence.

The first target instruction subsequence and the second target instruction subsequence can also be generated based on the cache consistency on instruction and the off instruction. In this case, the memory access instructions in the target instruction subsequence can all be ordinary memory access instructions (it can be considered that all memory access instructions on the existing processor are ordinary memory access instructions). In the entire instruction stream of the loop, the consistency instruction stream fragments and the private instruction stream fragments appear alternately. Therefore, a cache consistency off instruction can be inserted between each consistency instruction stream fragment and its subsequent private instruction stream fragment, and a cache consistency on instruction can be inserted between each private instruction stream fragment and its subsequent consistency instruction stream fragment. At this time, the last instruction of the first target instruction subsequence or the first instruction of the second target instruction subsequence is a cache consistency off instruction, and the first instruction of the first target instruction subsequence or the last instruction of the second target instruction subsequence is a cache consistency on instruction.

Herein, a plurality of memory access instructions including a consistency instruction and other memory access instructions between the consistency instructions are determined as a consistency instruction stream segment. The consistency instruction stream segment may be a complete instruction stream in a cycle.

In this embodiment, the entire instruction stream of the loop can be divided into consistent instruction stream segments containing consistent instructions and private instruction stream segments not containing consistent instructions, that is, the entire instruction stream of the loop is composed of a plurality of consistent instruction stream segments and a plurality of private instruction stream segments connected alternately. Therefore, after determining all consistent instruction stream segments, all private instruction stream segments can be determined, and the specific method can be to determine each instruction stream segment other than all consistent instruction stream segments as a private instruction stream segment.

Since cache coherent memory access instructions do not change the cache coherence state of the current processor core, the additional overhead of executing cache coherent memory access instructions can be ignored. Therefore, when the target processor provides cache coherent memory access instructions, a coherent instruction stream segment can contain only one instruction, which is the coherent instruction.

In this embodiment, the consistency instruction stream fragment corresponding to the consistency instruction and the private instruction stream fragment that does not contain the consistency instruction can be determined by inserting the consistency enable instruction and the consistency disable instruction. Therefore, the size of the consistency instruction stream fragment finally generated can be determined by the specific insertion implementation method of the cache consistency enable instruction and the cache consistency disable instruction. The consistency enable instruction can be inserted before the consistency instruction stream fragment as the first instruction of the first target instruction subsequence, or it can be inserted after the private instruction stream fragment as the last instruction of the second target instruction subsequence; the consistency disable instruction can be inserted after the consistency instruction stream fragment as the last instruction of the first target instruction subsequence, or it can be inserted before the private instruction stream fragment as the first instruction of the second target instruction subsequence. This will be further elaborated in the following embodiment.

The cache coherence on instruction is used to set the state of the cache coherence protocol of the current processor core to an on state, and the cache coherence off instruction is used to set the state of the cache coherence protocol of the current processor core to a off state.

When the consistency instruction stream segment is too large, it is easy to cause a large impact on the cache consistency overhead; when the consistency instruction stream segment is too small, it may cause frequent calls to the cache consistency enable and disable instructions, which will also bring considerable additional overhead. Therefore, by presetting rules to determine the consistency instruction stream segment, it is possible to simultaneously achieve the consistency instruction stream segment as small as possible and the number of cache consistency enable and disable instructions executed as few times as possible.

In one embodiment, the step of determining the consistent instruction stream fragment corresponding to each consistent instruction according to a preset rule includes:

A cache consistency enable instruction is inserted before the execution order of each of the consistency instruction stream fragments, and a cache consistency disable instruction is inserted after the execution order of each of the consistency instruction stream fragments, with the consistency enable instruction, the consistency disable instruction and other instructions between the consistency enable instruction and the consistency disable instruction being the first target instruction subsequence.

In this embodiment, the instruction fragment stream without consistent instructions is a private instruction stream fragment, which is located outside the consistent instruction stream fragment or is interleaved with each of the consistent instruction stream fragments. Each instruction in the private instruction stream fragment is a second target instruction subsequence.

In this embodiment, the state of the cache consistency protocol of the processor core can be changed by a cache consistency enable instruction and a cache consistency disable instruction. Among them, the cache consistency enable instruction is used to enable the cache consistency protocol, which can make the cache consistency protocol of the processor core in the enabled state, including changing from the disabled state to the enabled state and continuing to maintain the enabled state; the cache consistency disable instruction is used to disable the cache consistency protocol, which can make the cache consistency protocol of the processor core in the disabled state, including changing from the enabled state to the disabled state and continuing to maintain the disabled state. Specifically, the cache consistency enable instruction and the cache consistency disable instruction can be inserted into the execution flow of the program code or the program, and the current processor core responds to the cache consistency enable instruction initiated by the current thread, and sets the state of the cache consistency protocol of the current processor core to the enabled state, and responds to the cache consistency disable instruction initiated by the current thread, and sets the state of the cache consistency protocol of the current processor core to the disabled state.

In this embodiment, the cache consistency on instruction and the cache consistency off instruction can be inserted into the program code by the programmer or compiler, or inserted into the execution flow of the program by the operating system when performing related operations of the process or thread, or written into certain function libraries. For redundant cache consistency operations in parallel programs, the state of the cache consistency protocol of the current processor core can be set to the off state through the cache consistency off instruction to avoid redundant cache consistency operations, thereby improving the performance of parallel running of applications, reducing the working pressure of the cache consistency bus or directory, and making it possible to reduce their working frequency, thereby reducing the power consumption of the CPU.

In this embodiment, a cache consistency enable instruction is inserted before each consistency instruction stream segment, and a cache consistency disable instruction is inserted after the consistency instruction stream segment. In this way, the state of the cache consistency protocol can be turned on and off for each memory access instruction stream segment involving access to a consistency shared variable. When executing the consistency instruction stream segment, the cache consistency protocol is in the enabled state, and when executing the memory access instruction, the cache consistency operation between the processor cores can be performed, that is, the memory access instruction is executed in accordance with the cache consistency protocol requirements between the processor cores. Specifically, for a processor that uses a snooping protocol to achieve cache consistency, the memory access instruction is executed in accordance with the requirements of the snooping protocol; for a processor that uses a directory protocol to achieve cache consistency, the memory access instruction is executed in accordance with the requirements of the directory protocol. After executing the consistency instruction stream segment, the cache consistency protocol is turned off, so that access that does not involve consistency shared variables does not generate cache consistency operations.

For other memory access instructions that are not within the consistent instruction stream fragment and do not involve access to consistent shared variables, the cache consistency protocol state is not turned on and off, thereby avoiding reducing the calling frequency of cache consistency opening and closing instructions, avoiding excessive additional overhead, and further reducing overhead.

In this embodiment, according to preset rules, the consistency instruction stream fragments corresponding to each consistency instruction are determined, and cache consistency enable instructions and cache consistency disable instructions are inserted before and after the consistency instruction stream fragments, so that the consistency instruction stream fragments can be as small as possible, effectively reducing the cache consistency overhead and its impact increased by private variable access. In addition, since the number of execution times of cache consistency enable instructions and disable instructions is as small as possible, the calling frequency of cache consistency enable instructions and disable instructions can be reduced, avoiding excessive additional overhead, thereby further reducing overhead.

Embodiment 2

In order to obtain or determine all consistent shared variables, based on any of the above embodiments, in the cache consistency optimization method in automatic thread-level parallelization provided in this embodiment, the compiler obtains all consistent shared variables in response to thread-level automatic parallelization compilation of a loop, including at least one of the following methods:

Acquire a cache consistency setting command from the guidance instruction of the automatic parallel compilation, and acquire all consistent shared variables from the cache consistency setting command;

Acquire attribute information of each variable, determine whether each variable is a consistent shared variable based on the attribute information, and determine all consistent shared variables.

In this embodiment, the cache consistency setting command can be searched and obtained from the guidance instructions automatically compiled in parallel by the compiler, so that the variable accessed by the cache consistency setting command can be found from the guidance instructions, that is, the consistency shared variable, so as to obtain all the consistency shared variables; in addition, the attribute information of each variable can be obtained, and whether a variable is a consistency shared variable is determined based on the attribute information, so that all the consistency shared variables are determined from all variables.

Based on any of the above embodiments, the cache consistency optimization method in automatic thread-level parallelization provided in this embodiment further includes: obtaining the current compilation options corresponding to the compiler, obtaining the cache consistency compilation settings from the current compilation options, and when the cache consistency compilation is set to turn off cache consistency optimization, all variables are treated as consistent shared variables.

In this embodiment, cache consistency compilation settings can be obtained through the compilation options corresponding to the compiler. In this way, when the cache consistency compilation is set to turn off cache consistency optimization, all variables can be determined to be consistent shared variables, thereby obtaining all consistent shared variables.

Based on any of the above embodiments, in the cache consistency optimization method in automatic thread-level parallelization provided in this embodiment, the target processor has the function of maintaining cache consistency between cores and supports executing memory access instructions when cache consistency is turned off, including at least one of the following methods:

The target processor provides a cache consistency enable instruction and a cache consistency disable instruction, wherein the cache consistency enable instruction is used to set the state of the cache consistency protocol of the current processor core to an enable state, and the cache consistency disable instruction is used to set the state of the cache consistency protocol of the current processor core to a disable state;

The target processor provides a cache coherent memory access instruction, a private memory access instruction or a common memory access instruction, wherein the cache coherent memory access instruction initiates a cache coherent operation request when executed in any case, the private memory access instruction does not initiate a cache coherent operation request when executed in any case, the common memory access instruction initiates a cache coherent operation request when the cache coherence protocol of the current processor core is in an on state, and the common memory access instruction does not initiate a cache coherent operation request when the cache coherence protocol of the current processor core is in a off state. After a memory access instruction initiates a cache coherent operation request, the hardware system determines whether the current processor core is to initiate a cache coherent operation based on the coherence protocol state of the cache block corresponding to the request.

It should be understood that with the development of processor technology, memory access instructions that independently control whether to maintain cache consistency may appear in the future after this application, for example: a memory access instruction that initiates a cache consistency operation request regardless of the cache consistency of the current processor core in any state (on or off), which is called a cache consistency memory access instruction; a memory access instruction that does not initiate a cache consistency operation request regardless of the cache consistency of the current processor core in any state, which is called a private memory access instruction; a memory access instruction that determines whether to initiate a cache consistency operation request based on the cache consistency state of the current processor core, which is called a normal memory access instruction. Cache consistency memory access instructions, private memory access instructions, and normal memory access instructions will not change the cache consistency state of the current processor core, so they can each be executed out of order with other memory access instructions.

Therefore, in this embodiment, the division of consistent instruction stream segments and private instruction stream segments can be achieved by inserting cache consistency enable instructions and cache consistency disable instructions, or the division of consistent instruction stream segments and private instruction stream segments can be achieved by setting cache consistent memory access instructions, private memory access instructions or ordinary memory access instructions. For example, at least two cache consistent memory access instructions and ordinary memory access instructions located between these cache consistent memory access instructions are divided into consistent instruction stream segments, and other single or multiple consecutive private memory access instructions are divided into private instruction stream segments. These private instruction stream segments are all located outside the consistent instruction stream segments. In this way, the consistent instruction stream segments containing the consistent instructions and the private instruction stream segments not containing the consistent instructions can be clearly divided, and each instruction in the consistent instruction stream segment is used as the first target instruction subsequence, and each instruction in the private instruction stream segment is used as the second target instruction subsequence.

According to the records of Chinese patent application 202410831240.X, when the state of the cache consistency protocol of the current processor core is closed, one or both of the following methods are performed during the execution of the memory access instruction: the current processor core does not initiate any cache consistency operations to the cache consistency hardware system; the current processor core ignores any cache consistency operations initiated by other processor cores. In addition, when the cache consistency protocol is in the open state, if the memory access instruction hits a cache block marked with a private access state, it is necessary to initialize the consistency state of the cache block according to the attributes of the current access and the cache consistency protocol, and remove the mark of the private access state. The above initialization process usually triggers cache consistency operations between processor cores, and may therefore cause the cache block data to be reloaded from other cores or memory. For this reason, in this application, when the current processor core is in the closed state of its cache consistency protocol, it does not initiate any cache consistency operations, but can choose whether to respond to cache consistency operations initiated by other processor cores. In one embodiment of the present application, in the cache consistency optimization method in automatic thread-level parallelization, the method also includes: when the cache consistency protocol of the current processor core is in the closed state and a memory access instruction that is not the cache consistency memory access instruction is executed, no cache consistency operation is initiated to the cache consistency hardware system; the cache consistency closing instruction has a response on mode and a response off mode; after executing the cache consistency closing instruction in the response on mode, the current processor core always responds to the cache consistency operations initiated by other processor cores; after executing the cache consistency closing instruction in the response off mode, the current processor core ignores the cache consistency operations initiated by other processor cores.

In this embodiment, when the cache consistency shutdown instruction is in response to the on mode, the current processor core still responds to the cache consistency operation initiated by other processor cores. The reason is that when a thread uses a shared variable when the cache consistency protocol is in the on state, it may be necessary to obtain the latest data of the shared variable from another thread when the cache consistency protocol is in the off state. In this way, the other thread needs to be able to respond to the cache consistency operation when the cache consistency protocol is in the off state. In this way, it can be avoided that other threads cannot obtain the latest data of the shared variable due to the cache consistency protocol of a certain thread being in the off state. When the cache consistency shutdown instruction is in the response off mode, the cache consistency operation initiated by other processor cores is ignored. In this way, the consistency operation overhead can be further reduced.

In order to generate a first target instruction subsequence, in one embodiment, the generation of the first target instruction subsequence for maintaining cache consistency for each of the consistency instruction stream fragments includes at least one of the following methods: each of the consistency instructions in each of the consistency instruction stream fragments corresponds to a cache consistent memory access instruction or a normal memory access instruction in the first target instruction subsequence; the first instruction of the first target instruction subsequence of a consistency instruction stream fragment is a cache consistency on instruction, or the last instruction of the first target instruction subsequence of a consistency instruction stream fragment is a cache consistency off instruction.

In the present embodiment, one method for generating the first target instruction subsequence is as follows: as described in the above embodiment, the target processor provides cache-consistent memory access instructions, private memory access instructions and ordinary memory access instructions, and each consistent instruction in each consistent instruction stream fragment is used as the cache-consistent memory access instruction or the ordinary memory access instruction in the first target instruction subsequence. In this way, cache consistency can be ensured for each instruction in the consistent instruction stream fragment during execution.

Another way is: the first instruction of the first target instruction subsequence is used as the cache consistency enable instruction, so that the subsequent memory access instructions in the first target instruction subsequence will initiate a cache consistency operation request, and before the first instruction of the first target instruction subsequence, it belongs to a private instruction stream fragment, and no cache consistency operation request is initiated; the last instruction of the first target instruction subsequence is used as the cache consistency disable instruction, then the instructions following the last instruction of the first target instruction subsequence belong to a private instruction stream fragment, and no cache consistency operation request is initiated, but before the last instruction of the first target instruction subsequence, a cache consistency operation request may be initiated because the consistency operation is not disabled.

In order to generate a second target instruction subsequence, in one embodiment, the second target instruction subsequence that does not maintain cache consistency is generated for each of the private instruction stream fragments, including at least one of the following methods: each memory access instruction in each of the private instruction stream fragments corresponds to a private memory access instruction or a common memory access instruction in the second target instruction subsequence; the first instruction of the second target instruction subsequence of a private instruction stream fragment is a cache consistency off instruction, or the last instruction of the second target instruction subsequence of a private instruction stream fragment is a cache consistency on instruction.

In this embodiment, in order to generate the first target instruction subsequence, one method is: each memory access instruction in each of the private instruction stream fragments is used as the private memory access instruction or the ordinary memory access instruction in the second target instruction subsequence, so that each instruction in the private instruction stream fragment does not initiate a cache consistency operation request when executed.

Another method is: the first instruction of the second target instruction subsequence is used as a cache consistency shutdown instruction, so that the following instructions in the second target instruction subsequence do not perform cache consistency operations, and before the first instruction of the second target instruction subsequence, it belongs to a consistency instruction stream segment, so the cache consistency operation is performed; the last instruction of the second target instruction subsequence is used as a cache consistency startup instruction, then the instructions following the last instruction of the second target instruction subsequence belong to a consistency instruction stream segment, and the cache consistency operation is performed, and before the last instruction of the second target instruction subsequence, the cache consistency operation is performed because the consistency operation is kept turned on.

The above two embodiments show that the cache consistency on instruction and the cache consistency off instruction can be used as the first instruction or the last instruction of the first target instruction subsequence or the second target instruction subsequence. The purpose is to initiate a cache consistency operation request when the instructions of the consistent instruction stream fragment are executed, and not initiate a cache consistency operation request when the private instruction stream fragment is executed.

In one embodiment, the determination of the consistent instruction stream fragments corresponding to each of the consistent instructions and the private instruction stream fragments that do not contain the consistent instructions includes: each of the consistent instruction stream fragments contains one or more instructions, and when only one instruction is contained, the instruction is described; each instruction stream fragment other than all the consistent instruction stream fragments of the loop is determined as a private instruction stream fragment.

In this embodiment, when the consistent instruction stream segment contains multiple instructions, a cache consistency on instruction or a cache consistency off instruction may be inserted before or after the consistent instruction stream segment, or a cache consistency off instruction or a cache consistency lock instruction may be inserted before or after the private instruction stream segment in the manner of the above embodiment. When the consistent instruction stream segment contains only one instruction, the only instruction in the consistent instruction stream segment is the consistent instruction stream segment, and the consistent instruction is the first target instruction subsequence. In addition, each discontinuous and continuous instruction stream segment other than the consistent instruction stream segment is determined as a private instruction stream segment, and the instruction in each private instruction stream segment is the corresponding first target instruction subsequence.

Embodiment 3

Based on any of the above embodiments, in the cache consistency optimization method in automatic thread-level parallelization provided in this embodiment, the step of determining the consistency instruction stream fragment corresponding to each consistency instruction according to preset rules includes: obtaining the data dependency relationship between each consistency instruction; and aggregating at least two consistency instructions with data dependencies into the same consistency instruction stream fragment.

In this embodiment, in the thread-level automatic parallel compilation optimization, the data dependency between the instructions in the loop will be analyzed. If the result calculated by instruction A will be used as input by instruction B, then B depends on A; if instruction C depends on B and B depends on A, then it can be considered that C also depends on A, that is, the data dependency can be transitive. Instruction scheduling optimization is performed based on the data dependency, and multiple consistent shared variables with data dependencies and other multiple access instructions between these consistent instructions are aggregated to form consistent instruction stream fragments. In this way, it is possible to avoid the consistent instructions with dependencies being divided into different consistent instruction stream fragments, thereby avoiding the destruction of data dependencies.

It is worth mentioning that this optimization method involves data dependency analysis related to consistent shared variable access instructions. In most cases, the compiler will perform compilation optimization for data dependency analysis, but under some compilation options, data dependency analysis can also be omitted.

Analyzing the data dependencies in a program and scheduling instructions based on them is a basic function of the compiler. A key problem solved by the present application is: how to aggregate multiple consistent shared variable access instructions without destroying the data dependencies, so that the distance between these instructions in the generated target instruction sequence can be minimized. Therefore, in the cache consistency optimization method in automatic thread-level parallelization provided in one embodiment of the present application, the step of determining the consistent instruction stream fragment corresponding to each of the consistent instructions according to preset rules includes: obtaining the data dependencies between each of the consistent instructions; scheduling at least two consistent instructions that have no data dependencies to adjacent positions; aggregating the scheduled adjacent consistent instructions into the same consistent instruction stream fragment.

In this embodiment, by analyzing the data dependency between all instructions in the parallel region, it is determined whether there is a direct or indirect dependency between two consistent shared variable access instructions. When there is no dependency between two consistent shared variable access instructions, the two instructions can be scheduled to adjacent positions, and when there is a dependency between two consistent shared variable access instructions, other instructions that have no dependency between them will not be scheduled between them, so as to avoid the destruction of data dependency.

In the cache consistency optimization method in automatic thread-level parallelization provided in one embodiment of the present application, the step of determining the consistency instruction stream fragment corresponding to each consistency instruction according to a preset rule includes: determining the consistency instructions corresponding to the consistency shared variable in multiple iterations of the loop; and aggregating the consistency instructions corresponding to the consistency shared variable in multiple iterations into the same consistency instruction stream fragment.

It should be understood that the optimization space of basic optimization methods is often limited. Automatic parallelization compilation is for loops in most cases, and there needs to be no dependencies between different iterations of the loop except for the mutually exclusive area. If there are dependencies, parallelization will destroy the dependencies and cause errors in the results of parallel operation. Therefore, loop unrolling can be used to aggregate access instructions to consistent shared variables (in the case of arrays) in multiple iterations.

In one embodiment, the step of determining the consistency instruction stream fragment corresponding to each consistency instruction according to a preset rule includes: creating a temporary array with N elements according to the number N of the consistency shared variables; reading N elements of each consistency shared variable into the temporary array at one time or assigning N elements of the temporary array to the consistency shared variable at one time every N iterations; replacing instructions for accessing each consistency shared variable with array access instructions for the temporary array, and adding memory access instructions corresponding to the one-time reading and the one-time assignment to the consistency instruction stream fragment.

It should be understood that although loop unrolling is a commonly used compilation optimization method, the number of unrolling is often limited, because loop unrolling will cause a sharp increase in the number of instructions generated by the compilation, and even make the instruction cache of the processor core unable to accommodate all the instructions of the loop body, thereby causing a sharp decrease in the program running speed. In the case where loop unrolling is not performed or the number of loop unrolling is small, a temporary array can be used to achieve the aggregation of access instructions of consistent shared variables (in the case of arrays) in multiple iterations. In this embodiment, first, a temporary array with N elements can be allocated to each consistent shared variable, and then every N iterations, the N elements of the consistent shared variable are read into the temporary array at one time, or the N elements in the temporary array are assigned to the consistent shared variable array at one time; and in the original loop body, the access to the consistent shared variable elements is replaced by the access to the corresponding temporary array elements. In this way, for the case where loop unrolling is not performed or the number of loop unrolling is small, the access instructions to the consistent shared variables in the temporary array are aggregated into the same consistent instruction stream fragment by creating a temporary array.

After completing the instruction scheduling optimization, a complete instruction stream can be obtained after the loop is automatically parallelized and compiled and optimized, in which all consistent shared variable access instructions can be marked. If the memory access instructions of two consistent shared variables are adjacent in the instruction stream, they can naturally be merged into the same consistent instruction stream fragment. For the two consistent instruction stream fragments before and after, if they are merged, the other memory access instructions between them will increase the consistency operation overhead (for example, the number of memory access instructions multiplied by the consistency operation overhead baseline value), and if they are not merged, it is necessary to insert multiple consistency opening instructions and closing instructions, which will also generate additional overhead. Therefore, it is necessary to reasonably judge whether to merge these consistent instructions into consistent instruction stream fragments. To this end, in one embodiment, the step of determining the consistent instruction stream fragment corresponding to each of the consistent instructions according to the preset rules includes:

Acquire at least two consistent instructions within a preset range in execution order and memory access instructions between the consistent instructions within the preset range, and determine them as instructions to be merged;

Calculating the consistency operation overhead generated by the memory access instructions between the consistency instructions within a preset range when the instructions to be merged are merged into a consistency instruction stream segment, to obtain a first operation overhead;

Calculate the operation overhead reduced by reducing the number of times the state of the cache coherence protocol is turned on and off when the instructions to be merged are merged into a coherent instruction stream segment, to obtain a second operation overhead;

When the first operation overhead is less than the second operation overhead, it is determined that the instructions to be merged are merged into a consistent instruction stream segment.

In this embodiment, multiple memory access instructions are merged into a consistent instruction stream segment, which can reduce the calling overhead of cache consistency enable instructions and cache consistency disable instructions. However, if there are too many other memory access instructions of non-consistent instructions in the merged consistent instruction stream segment, it will lead to high consistency operation overhead. Therefore, it is necessary to estimate and evaluate the two overheads.

In this embodiment, the preset range refers to the execution sequence range when the instructions are executed in the execution order, that is, the two consistency instructions to be merged can be two adjacent instructions, or there can be multiple other instructions between them. Among them, the preset range is usually the number of instructions (for example, 20 instructions). In this embodiment, the first operation overhead and the second operation overhead are both hypothetical overheads, wherein the first operation overhead is the assumption that at least two consistency instructions within the preset range and other memory access instructions between these consistency instructions are merged into the same consistency instruction stream fragment, compared with the case where the instructions are not merged and only the consistency shared variables involved are operated consistently, the increased consistency operation overhead; the second operation overhead is the assumption that at least two consistency instructions within the preset range and other memory access instructions between these consistency instructions are merged into the same consistency instruction stream fragment, compared with the case where the instructions are not merged, and the consistency opening instruction and the consistency closing instruction are inserted before and after each consistency instruction. The reduced consistency protocol control overhead. When the newly added first operation overhead is less than the reduced second operation overhead, it indicates that the consistency operation overhead generated by other memory access instructions after the merger is less than the call overhead generated by calling the consistency enable instruction and the disable instruction for each consistency instruction. Therefore, the two consistency instructions before and after and together with other instructions between them are merged into the same consistency instruction stream fragment, and the consistency enable instruction and the disable instruction are inserted before and after the entire consistency instruction stream fragment.

In a simpler implementation, if the number of other memory access instructions between the two consecutive consistent instruction stream segments does not exceed the memory access instruction number threshold, the segments are merged. For example, in one embodiment, the step of determining the consistent instruction stream segments corresponding to each consistent instruction according to a preset rule includes:

Obtaining the number of memory access instructions between at least two consistent instructions within a preset range in execution order, and determining the number of other memory access instructions;

When the number of other memory access instructions is less than or equal to a preset instruction number threshold, at least two consistent instructions within a preset range in execution order and memory access instructions between consistent instructions within the preset range are merged into a consistent instruction stream segment.

In this embodiment, another idea of merging consistency instructions is provided. If the number of other memory access instructions between the two consistency instructions does not exceed the preset instruction number threshold, the other memory access instructions between the two consistency instructions are merged with the two consistency instructions into a consistency instruction stream segment. It should be understood that when the number of other memory access instructions between any two consistency instructions in a preset range does not exceed the preset instruction number threshold, these consistency instructions in the preset range and the memory access instructions between the consistency instructions can also be merged into a consistency instruction stream segment.

Coherent shared variables can be obtained from the compilation guidance command. In addition, you can also declare the attribute information related to cache coherence of each variable in the program. The compiler can determine all the coherent shared variables contained in a program by recording the attribute information of each variable. The compiler will record the variable corresponding to a memory access instruction. When the variable corresponding to a memory access instruction is a coherent shared variable, this memory access instruction is a coherent memory access instruction.

Taking OpenMP as an example, the guidance instructions for automatic parallel compilation include the specification of private variables or shared variables in parallel regions (such as for loops in C/C++ language), the specification of mutually exclusive regions in parallel regions, etc. However, the existing guidance instructions cannot specify consistent shared variables (i.e., shared variables that need to ensure cache consistency during read and write access). Therefore, the specification of consistent shared variables is added to the guidance instructions. For example, a corresponding example is given in Figure 3D, where "CC_vars" is the keyword of the guidance instruction for specifying consistent shared variables, that is, the consistency identifier described in this embodiment.

During the automatic parallelization compilation process, all private variables and shared variables in the parallel region need to be determined. It is usually easy to assume that access to any shared variable needs to be guaranteed by cache consistency, that is, it is easy to assume that all shared variables are consistent shared variables. To this end, a keyword value, namely a consistency identifier, can be designed to conveniently specify this situation, such as "CC_vars (default shared)" in Figure 3D. However, there are also cases where access to some shared variables does not need to be guaranteed by cache consistency. For example, for the third loop in Figure 3D, although it uses shared variable A as input, it is not necessary to ensure the cache consistency of reading A in this loop, because the automatic parallelization method of the third loop will be the same as the second loop, and the second loop has read shared variable A before. In addition, the data of shared variables can also be manually divided according to the requirements of thread-level parallelism to avoid sharing of the same cache block between threads, so that there is no need to specify consistent shared variables. That is, program developers can reduce consistent shared variables based on their understanding or improvement of the program, thereby reducing cache consistency overhead. Therefore, the compilation guidance instructions for consistent shared variables can not only conveniently mark all shared variables, but also flexibly enumerate several specific shared variables.

In one embodiment, the step of determining the consistent instruction stream fragment corresponding to each consistent instruction according to a preset rule includes: determining a mutually exclusive area in a cache area, and merging all instructions in the mutually exclusive area into a consistent instruction stream fragment.

In this embodiment, there may be a mutex region in the loop to be automatically parallelized at the thread level, which allows only one thread to enter the execution at a time. The mutex region usually modifies shared variables. Therefore, the entire mutex region can be regarded as a consistent instruction stream segment, that is, the cache consistency enable instruction and the cache consistency disable instruction are inserted before and after the mutex region respectively.

The correctness of the optimization of removing redundant cache consistency operations is ensured by the programmer. Programmers often need to debug the correctness of the optimization implementation. A common debugging method is to check whether the program results with all cache consistency operations retained are exactly the same as the program results after removing redundant cache consistency operations. That is, check whether the program results are exactly the same before and after optimization. If the optimization can be turned on and off easily without changing the program, it will be more convenient to carry out the inspection work. A simple implementation method is to implement a compilation setting that can turn on or off cache consistency optimization in the compilation option design. When the compiler performs automatic thread-level parallelization, if it finds that the cache consistency compilation setting in the compilation option is to turn off cache consistency optimization, all variables are treated as consistent shared variables to ensure that the compiled target program does not remove any cache consistency operations.

According to the records of Chinese patent application 202410831240.X, when the state of the cache consistency protocol of the current processor core is closed, one or both of the following methods are performed during the execution of the memory access instruction: the current processor core does not initiate any cache consistency operations to the cache consistency hardware system; the current processor core ignores any cache consistency operations initiated by other processor cores. In addition, when the cache consistency protocol is in the open state, if the memory access instruction hits a cache block marked with a private access state, it is necessary to initialize the consistency state of the cache block according to the attributes of the current access and the cache consistency protocol, and remove the mark of the private access state. The above initialization process usually triggers cache consistency operations between processor cores, and may therefore cause the cache block data to be reloaded from other cores or memory. For this reason, in this application, when the current processor core is in the closed state of its cache consistency protocol, it does not initiate any cache consistency operations, but can choose whether to respond to cache consistency operations initiated by other processor cores. In one embodiment of the present application, the cache consistency off instruction has a response on mode and a response off mode, wherein, after executing the cache consistency off instruction in the response on mode, the current processor core always responds to cache consistency operations initiated by other processor cores; after executing the cache consistency off instruction in the response off mode, the current processor core ignores cache consistency operations initiated by other processor cores.

In this embodiment, when the cache consistency shutdown instruction is in response to the on mode, the current processor core still responds to the cache consistency operation initiated by other processor cores. The reason is that when a thread uses a shared variable when the cache consistency protocol is in the on state, it may be necessary to obtain the latest data of the shared variable from another thread when the cache consistency protocol is in the off state. In this way, the other thread needs to be able to respond to the cache consistency operation when the cache consistency protocol is in the off state. In this way, it can be avoided that other threads cannot obtain the latest data of the shared variable due to the cache consistency protocol of a certain thread being in the off state. When the cache consistency shutdown instruction is in the response off mode, the cache consistency operation initiated by other processor cores is ignored. In this way, the consistency operation overhead can be further reduced.

Many modern processors have the function of automatically prefetching cache data, among which the commonly used prefetching methods are adjacent prefetching and equal-span prefetching. It may happen that when the cache consistency protocol is turned off, the cache blocks that need to be accessed with cache consistency in the future are fetched in advance. After entering the area where the cache consistency protocol is started, if the cache blocks that have been prefetched before are accessed without checking whether other cores have changed the value of the cache blocks, the data may not be updated in time. Chinese patent application 202410831240.X proposes to mark the cache blocks accessed when the cache consistency protocol is turned off as private access states, and when the cache consistency protocol is turned on, the cache blocks marked as private access states are hit, and the cache blocks need to be cached or re-read to ensure the correctness of the data content in the cache blocks. The essence of this method is to treat the first access to the private access state cache block when the cache consistency protocol is turned on as a cache miss, so it will introduce a considerable amount of additional overhead. In this application, the cache consistency protocol is frequently turned on and off during the execution of the parallelized loop, resulting in the frequent occurrence of the phenomenon of prefetching consistent shared variables when the consistency protocol is turned off. The technical method proposed in Chinese patent application 202410831240.X will significantly reduce the significance of data prefetching for consistent shared variables. To this end, a more efficient technical method is needed. Data prefetch instructions are basically initiated based on the address change rules of load and store instructions, that is, a data prefetch instruction is triggered by several load and store instructions. Based on this, in one embodiment of the cache consistency optimization method in automatic thread-level parallelization provided in the present application, the method also includes: in response to the execution of the data prefetch instruction, detecting whether there is at least one memory access instruction among the memory access instructions that trigger the data prefetch instruction that is a cache consistent memory access instruction or corresponds to the open state of the cache consistency protocol; when there is at least one memory access instruction among the memory access instructions that trigger the data prefetch instruction that is a cache consistent memory access instruction or corresponds to the open state of the cache consistency protocol, determining to initiate a cache consistency operation request when executing the data prefetch instruction (execute the data prefetch instruction when the cache consistency protocol is in the open state, or use the corresponding data prefetch instruction in the cache consistent memory access instruction); when all the memory access instructions that trigger the data prefetch instruction are private memory access instructions or correspond to the closed state of the cache consistency protocol, determining not to initiate a cache consistency operation request when executing the data prefetch instruction (execute the data prefetch instruction when the cache consistency protocol is in the closed state, or use the corresponding data prefetch instruction in the private memory access instruction).

In this embodiment, when executing a data prefetch instruction, if at least one of the several memory access instructions that trigger the data prefetch instruction is a cache consistent memory access instruction or corresponds to the open state of the cache consistency protocol, it is determined that a cache consistency operation request is initiated when executing the instruction. In this way, it can effectively avoid the situation where data is not updated in time, and it will not cause additional overhead. When executing a data prefetch instruction, if all the memory access instructions that trigger the instruction are private memory access instructions or correspond to the closed state of the cache consistency protocol, it is determined that a cache consistency operation request is not initiated when executing the instruction.

Embodiment 4

FIG2 is a schematic diagram of the structure of a cache consistency optimization device in automatic thread-level parallelization provided by an embodiment of the present disclosure. As shown in FIG2, the cache consistency optimization device in automatic thread-level parallelization provided by this embodiment may include:

A shared variable acquisition module 210, used by the compiler to acquire all consistent shared variables in response to thread-level automatic parallelization compilation of a loop;

An instruction determination module 220, configured to find a memory access instruction for accessing the consistent shared variable from each memory access instruction according to the consistent shared variable, and determine the memory access instruction as a consistent instruction;

The instruction stream segment determination module 230 is used to determine the consistent instruction stream segment corresponding to each consistent instruction and the private instruction stream segment not containing the consistent instruction according to a preset rule, generate a first target instruction subsequence maintaining cache consistency for each consistent instruction stream segment, and generate a second target instruction subsequence not maintaining cache consistency for each private instruction stream segment;

The first target instruction subsequence and the second target instruction subsequence both correspond to a target processor; the target processor has the function of maintaining cache consistency between cores and supports executing memory access instructions when cache consistency is turned off.

The shared variable acquisition module is also used to acquire all consistent shared variables by at least one method:

Acquire a cache consistency setting command from the guidance instruction of the automatic parallel compilation, and acquire all consistent shared variables from the cache consistency setting command;

Acquire attribute information of each variable, determine whether each variable is a consistent shared variable based on the attribute information, and determine all consistent shared variables.

In one embodiment, the apparatus further comprises:

The consistent shared variable determination module is used to obtain the current compilation options corresponding to the compiler, obtain the cache consistency compilation settings from the current compilation options, and when the cache consistency compilation setting is to turn off cache consistency optimization, all variables are regarded as consistent shared variables.

In one embodiment, the target processor has a function of maintaining cache consistency between cores and supports executing memory access instructions with cache consistency turned off, including at least one of the following methods:

The target processor provides a cache consistency enable instruction and a cache consistency disable instruction, wherein the cache consistency enable instruction is used to set the state of the cache consistency protocol of the current processor core to an enable state, and the cache consistency disable instruction is used to set the state of the cache consistency protocol of the current processor core to a disable state;

The target processor provides cache consistent memory access instructions, private memory access instructions or ordinary memory access instructions, wherein the cache consistent memory access instructions initiate cache consistent operation requests when executed under any circumstances, the private memory access instructions do not initiate cache consistent operation requests when executed under any circumstances, the ordinary memory access instructions initiate cache consistent operation requests when the cache consistent protocol of the current processor core is in the turned-on state, and the ordinary memory access instructions do not initiate cache consistent operation requests when the cache consistent protocol of the current processor core is in the turned-off state.

In one embodiment, when the cache coherence protocol of the current processor core is in a closed state and a memory access instruction other than the cache coherence memory access instruction is executed, no cache coherence operation is initiated to the cache coherence hardware system;

The cache coherence closing instruction has a response opening mode and a response closing mode;

The device also includes:

A response enable module, configured to enable the current processor core to always respond to cache consistency operations initiated by other processor cores after executing a cache consistency disable instruction in the response enable mode;

The response closing module is used to execute the cache consistency closing instruction in the response closing mode, and the current processor core ignores the cache consistency operation initiated by other processor cores.

In one embodiment, the instruction stream segment determination module is further configured to:

Each of the consistency instructions in each of the consistency instruction stream fragments corresponds to one of the cache consistent memory access instructions or one of the common memory access instructions in the first target instruction subsequence;

The first instruction of the first target instruction subsequence of one of the consistent instruction stream fragments is a cache consistency on instruction, or the last instruction of the first target instruction subsequence of one of the consistent instruction stream fragments is a cache consistency off instruction.

In one embodiment, the instruction stream segment determination module is further configured to:

Each memory access instruction in each of the private instruction stream fragments corresponds to one of the private memory access instructions or one of the common memory access instructions in the second target instruction subsequence;

The first instruction of the second target instruction subsequence of one of the private instruction stream fragments is a cache coherence off instruction, or the last instruction of the second target instruction subsequence of one of the private instruction stream fragments is a cache coherence on instruction.

In one embodiment, the instruction stream segment determination module is further configured to:

Each of the consistent instruction stream fragments includes one or more instructions, and when only one instruction is included, the instruction is the consistent instruction;

Each instruction stream segment other than all the consistent instruction stream segments of the loop is determined as a private instruction stream segment.

In one embodiment, the instruction stream segment determination module includes:

A dependency acquisition unit, comprising acquiring data dependencies between the consistency instructions;

The instruction stream fragment aggregation unit includes aggregating at least two consistent instructions with data dependencies into the same consistent instruction stream fragment.

In one embodiment, the instruction stream segment determination module includes:

A dependency acquisition unit, comprising acquiring data dependencies between the consistency instructions;

The instruction stream fragment aggregation unit is used to schedule at least two consistent instructions that have no data dependency relationship to adjacent positions; and aggregate the scheduled adjacent consistent instructions into the same consistent instruction stream fragment.

In one embodiment, the instruction stream segment determination module includes:

An iterative instruction determination unit, used to determine the consistency instructions corresponding to the consistency shared variable in multiple iterations of the loop;

The instruction stream fragment aggregation unit comprises aggregating the consistency instructions corresponding to the consistency shared variable in multiple iterations into the same consistency instruction stream fragment.

In one embodiment, the instruction stream segment determination module includes:

A temporary array creation unit, used for creating a temporary array with N elements according to the number N of the consistency shared variables;

An instruction replacement unit, configured to read N elements of each of the coherent shared variables into the temporary array at one time or assign N elements of the temporary array to the coherent shared variables at one time; and replace instructions for accessing each of the coherent shared variables with array access instructions for the temporary array;

An instruction adding unit is used to add the memory access instructions corresponding to the one-time read and the one-time assignment to the consistent instruction stream segment.

In one embodiment, the instruction stream segment determination module includes:

A to-be-merged instruction determination unit, used to obtain at least two consistent instructions within a preset range in execution order and a memory access instruction between the consistent instructions within the preset range, and determine them as to-be-merged instructions;

A first operation cost calculation unit is used to calculate the consistency operation cost generated by the memory access instruction between the consistency instructions within a preset range when the instructions to be merged are merged into a consistency instruction stream fragment, so as to obtain a first operation cost;

A second operation cost calculation unit is used to calculate the operation cost reduced by reducing the number of times the state of the cache coherence protocol is turned on and off when the instructions to be merged are merged into a coherent instruction stream fragment, so as to obtain a second operation cost;

A merging unit is used to determine that each of the instructions to be merged is merged into a consistent instruction stream segment when the first operation overhead is less than the second operation overhead.

In one embodiment, the instruction stream segment determination module includes:

An instruction quantity acquisition unit, used to acquire the number of memory access instructions between at least two consistent instructions within a preset range in execution order, and determine it as the number of other memory access instructions;

A merging unit is used to merge at least two consistent instructions within a preset range in execution order and memory access instructions between consistent instructions within a preset range into a consistent instruction stream fragment when the number of other memory access instructions is less than or equal to a preset instruction number threshold.

In one embodiment, the instruction stream segment determination module is further used to determine a mutually exclusive area in the cache area, and merge all instructions in the mutually exclusive area into a consistent instruction stream segment.

In one embodiment, the apparatus further comprises:

A data prefetch instruction response module, configured to detect, in response to the execution of the data prefetch instruction, whether at least one memory access instruction among the memory access instructions triggering the data prefetch instruction is a cache coherent memory access instruction or corresponds to an on state of a cache coherent protocol;

A first prefetch instruction module, configured to determine to initiate a cache coherence operation request when executing the data prefetch instruction when at least one memory access instruction among the memory access instructions that trigger the data prefetch instruction is a cache coherence memory access instruction or corresponds to an on state of a cache coherence protocol;

The second prefetch instruction module is used to determine not to initiate a cache coherence operation request when executing the data prefetch instruction when all memory access instructions that trigger the data prefetch instruction are private memory access instructions or correspond to a closed state of the cache coherence protocol.

Embodiment 5

Based on the above embodiments, this embodiment provides an application example.

In response to thread-level automatic parallel compilation of a loop, the compiler obtains a cache consistency setting command from the guidance instruction of the automatic parallel compilation, obtains all consistent shared variables from the cache consistency setting command, finds all access instructions of all consistent shared variables from the complete instruction stream of the loop generated by thread-level automatic parallel compilation optimization, determines all consistent instruction stream fragments from the complete instruction stream, and inserts a cache consistency enable instruction and a cache consistency disable instruction before and after each of the consistent instruction stream fragments.

The step of finding all access instructions to all consistent shared variables from the complete instruction stream of the loop generated by thread-level automatic parallelization compilation optimization includes:

In the thread-level automatic parallel compilation optimization, the data dependency in the loop is analyzed, instruction scheduling optimization is performed according to the data dependency, and multiple access instructions to multiple consistent shared variables are aggregated.

Regarding the "cache consistency on instruction and cache consistency off instruction", it should be noted that: according to Chinese patent application 202410831240.X, the cache consistency off instruction sets the state of the cache consistency protocol of the current processor core to the off state, while the cache consistency on instruction sets the state of the cache consistency protocol of the current processor core to the on state. When the state of the cache consistency protocol of the current processor core is off, one or two of the following methods are performed during the execution of the memory access instruction: the current processor core does not initiate any cache consistency operations to the cache consistency hardware system; the current processor core ignores any cache consistency operations initiated by other processor cores. In addition, when the cache consistency protocol is in the on state, if the memory access instruction hits a cache block marked with a private access state, it is necessary to initialize the consistency state of the cache block according to the current access attributes and the cache consistency protocol, and remove the mark of the private access state. The above initialization process usually triggers cache consistency operations between processor cores, and may therefore cause the cache block data to be reloaded from other cores or memory.

The technology of the present application further considers that when the cache consistency protocol of the current processor core is in the off state, it does not initiate any operations related to cache consistency, but can choose whether to respond to cache consistency operations initiated by other processor cores. Therefore, the cache consistency off instruction has a response on and response off mode. Among them, after executing the cache consistency off instruction in the response on mode, the current processor core always responds to cache consistency operations initiated by other processor cores; after executing the cache consistency off instruction in the response off mode, the current processor core ignores cache consistency operations initiated by other processor cores.

In addition, the present application technology believes that the cache consistency shutdown instructions inserted by the compiler during the thread-level automatic parallelization compilation of the loop are all response-on modes. This is because when a thread uses a shared variable with the cache consistency protocol turned on, it may need to obtain the latest data of the shared variable from another thread with the cache consistency protocol turned off, that is, the other thread needs to be able to respond to the cache consistency operation when the cache consistency protocol is turned off.

Regarding “obtaining cache consistency setting commands from the guidance instructions of the automatic parallel compilation, and obtaining all consistent shared variables from the cache consistency setting commands”, it should be noted that: taking OpenMP as an example, the guidance instructions of the automatic parallel compilation include the specification of private variables or shared variables in parallel areas (such as for loops in C/C++ language), the specification of mutually exclusive areas in parallel areas, etc. However, the existing guidance instructions cannot specify consistent shared variables (i.e., shared variables that need to ensure cache consistency during read and write access). Therefore, adding the specification of consistent shared variables in the guidance instructions is an important innovation or technical feature of the technology of the present application. For example, a corresponding example is given in Figure 3D, where "CC_vars" is the keyword of the guidance instructions for specifying consistent shared variables.

During the automatic parallelization compilation process, all private variables and shared variables in the parallel region need to be determined. It is usually easy to assume that access to any shared variable needs to be guaranteed by cache consistency, that is, it is easy to assume that all shared variables are consistent shared variables. To this end, a keyword value (such as "CC_vars (default shared)") can be designed to conveniently specify this situation. However, there are also cases where access to some shared variables does not need to be guaranteed by cache consistency. For example, for the third loop in Figure 3D, although it uses shared variable A as input, it is not necessary to ensure the cache consistency of reading A in this loop, because the automatic parallelization method of the third loop will be the same as the second loop, and the second loop has read shared variable A before. In addition, program developers can also manually divide the data of shared variables according to the requirements of thread-level parallelism to avoid sharing the same cache block between threads, so that there is no need to specify consistent shared variables. That is, program developers can reduce consistent shared variables based on their understanding or improvement of the program, thereby reducing cache consistency overhead. Therefore, the compilation guidance instructions for consistent shared variables can not only conveniently mark all shared variables, but also flexibly enumerate several specific shared variables.

Regarding "finding all access instructions for all consistent shared variables from the complete instruction stream of the loop generated by thread-level automatic parallelization compilation optimization", it should be noted that the compiler can complete the compilation from the original high-level language program to assembly language or binary program, during which compilation optimization will be performed to increase the speed of program execution. During the compilation optimization process, the compiler will have an intermediate language, based on which the variable corresponding to each memory access instruction in the instruction stream can be determined, so the instruction to access any consistent shared variable can be found from the complete instruction stream.

In this application, an optimization method for consistent shared variable access instructions is provided, and this optimization method involves data dependency analysis related to consistent shared variable access instructions. That is, from thread-level automatic parallelization compilation to data dependency analysis, this is a specialization or scope reduction, because although the compiler will perform compilation optimization of data dependency analysis in most cases, it may not perform data dependency analysis under some compilation options (such as O0).

Therefore, regarding "analyzing the data dependency in the loop, optimizing instruction scheduling according to the data dependency, and aggregating multiple access instructions to multiple consistent shared variables", there are the following implementation methods:

Analyzing the data dependencies between variables in a program and scheduling instructions based on them is a basic function of the compiler. A key problem of the present application technology is how to aggregate multiple consistent shared variable access instructions without destroying the data dependencies, that is, to minimize the distance between these instructions in the generated target instruction sequence. There can be multiple compilation optimization methods with different optimization modes or optimization degrees:

1) Basic optimization method, that is, by analyzing the data dependencies between all instructions in the parallel region, determine whether there is a direct or indirect dependency between two consistent shared variable access instructions. When there is no dependency between two consistent shared variable access instructions, the two instructions can be scheduled to adjacent positions, and when there is a dependency between two consistent shared variable access instructions, it is necessary to try not to schedule other instructions that have no dependency between them between them.

2) Optimize based on loop unrolling. The optimization space of basic optimization methods is often limited. Automatic parallelization compilation is mostly for loops, and the parts of the loop other than the mutually exclusive area need to have no dependencies between different iterations (the programmer needs to ensure this), because if there are dependencies, parallelization will destroy the dependencies and cause errors in the results of parallel operation. Therefore, loop unrolling can be used to aggregate access instructions to consistent shared variables (in the case of arrays) in multiple iterations.

3) Optimization based on private temporary arrays. Although loop unrolling is a commonly used compilation optimization method, the number of unrollings is often limited, because loop unrolling will cause a sharp increase in the number of instructions generated by the compilation, and even make the instruction cache of the processor core unable to accommodate all the instructions of the loop body, resulting in a sharp decrease in the program running speed. In the case of no loop unrolling or a small number of loop unrollings, a temporary array can be used to achieve the aggregation of consistent shared variables (in the case of arrays) in multiple iterations. First, a temporary array with N elements can be allocated to each consistent shared variable, and then every N iterations, at most N elements of the consistent shared variable are read into the temporary array at one time, or at most N elements in the temporary array are assigned to the consistent shared variable array at one time; and in the original loop body, the access to the consistent shared variable elements is replaced with the access to the corresponding temporary array elements.

Regarding "determining all consistent instruction stream segments from the complete instruction stream, and inserting cache consistency enable instructions and cache consistency disable instructions before and after each consistent instruction stream segment", it should be noted that: after completing the instruction scheduling optimization, a complete instruction stream after the loop is automatically parallelized and compiled and optimized can be obtained, in which all consistent shared variable access instructions can be marked. If two consistent shared variable access instructions are adjacent in the instruction stream, they can naturally be merged into the same consistent instruction stream segment. For the two consistent instruction stream segments before and after, if they are merged, the other memory access instructions between them will increase the consistency operation overhead. At this time, the newly added consistency operation overhead can be estimated (for example, the number of memory access instructions multiplied by the consistency operation overhead benchmark value); the merger will also reduce the call of the cache consistency enable instruction and the cache consistency disable instruction once, so it is necessary to estimate the reduced consistency protocol control overhead, for example, using the consistency protocol control overhead benchmark value. When the newly added consistency operation overhead is less than the reduced consistency protocol control overhead, the two consistent instruction stream segments before and after, together with other instructions between them, are merged into the same consistent instruction stream segment. In a simpler implementation, if the number of other memory access instructions between two consecutive consistent instruction stream fragments does not exceed a threshold value for the number of memory access instructions, merging is performed.

Regarding the cache consistency implementation of data prefetching, it should be noted that many modern processors have the function of automatically prefetching cache data, among which the commonly used prefetching methods are adjacent prefetching and equal-span prefetching. It may happen that when the cache consistency protocol is turned off, the cache blocks that need to be accessed with cache consistency in the future are fetched in advance. After entering the area where the cache consistency protocol is enabled, if the cache blocks that have been prefetched before are accessed without checking whether other cores have changed the value of the cache blocks, the data may not be updated in time. Chinese patent application 202410831240.X proposes to mark the cache blocks that have been accessed when the cache consistency protocol is turned off as private access status, and when the cache consistency protocol is turned on, if a cache block marked as private access status is hit, the cache block needs to be cached or re-read to ensure the correctness of the data content in the cache block. The essence of this method is to treat the first access to the private access status cache block when the cache consistency protocol is turned on as a cache miss, which will introduce a considerable amount of additional overhead.

The technology of this application will cause the cache consistency protocol to be frequently turned on and off during the execution of the parallelized loop, resulting in the frequent occurrence of the phenomenon of prefetching consistent shared variables when the consistency protocol is in the off state. Chinese patent application 202410831240.X proposes a technical method that will significantly reduce the significance of data prefetching for consistent shared variables. To this end, a more efficient technical method is needed. Data prefetch instructions are basically initiated when the address change rules of load and store instructions are learned, that is, a data prefetch instruction is triggered by several load and store instructions. Based on this, this application proposes a new method for data prefetching: when executing a data prefetch instruction, if at least one of the several memory access instructions that trigger the instruction corresponds to the on state of the cache consistency protocol, the instruction is executed in the on state of the cache consistency protocol; if all memory access instructions that trigger the instruction correspond to the off state of the cache consistency protocol, the instruction is not initiated when the cache consistency operation is executed. The above technology enables the current processor core to use cache consistency operations to ensure the correctness of the prefetched data when the cache consistency protocol is in the off state. In hardware, the above functions are easy to implement.

Regarding the opening and closing of the consistency instructions of the mutex region: In the loop to be automatically parallelized at the thread level, there may be a mutex region that only allows one thread to enter the execution at a time. The mutex region usually modifies shared variables. Therefore, the entire mutex region can be regarded as a consistency instruction stream segment, that is, the cache consistency opening instruction and the cache consistency closing instruction are inserted before and after the mutex region respectively.

For automatic parallelization of non-loop programs: The entire parallel region to be automatically parallelized at the thread level by compiling the guidance statement may also be a non-loop program. The non-loop parallel region can also use the technology of the present application. In this case, it is only necessary to regard the parallel region as a special loop with a loop execution number of 1. The parallel region may also contain a small loop that accesses the consistent shared variables. In this case, in addition to the basic optimization method, the loop unrolling optimization and temporary array optimization mentioned above can also be used.

Embodiment 6

On the basis of the above embodiments, this embodiment provides a computer device, including a memory, a processor, and a computer program stored in the memory, wherein the processor executes the computer program to implement the steps of the method described in the above embodiments.

In some implementations of this embodiment, a computer-readable storage medium is provided, on which a computer program is stored. When the computer program is executed by a processor, the steps of the method described in the above embodiment are implemented.

In some implementations of this embodiment, a computer program product is provided, including a computer program/instructions, and when the computer program is executed by a processor, the steps of the method described in the above embodiment are implemented.

The processor may include, but is not limited to, one or more processors or microprocessors, etc. Each processor may be an application specific integrated circuit (ASIC), a digital signal processor (DSP), a digital signal processing device (DSPD), a programmable logic device (PLD), a field programmable gate array (FPGA), a controller, a microcontroller, a microprocessor or other electronic components to execute the methods in the above embodiments.

The computer-readable storage medium may be implemented by any type of volatile or non-volatile storage device or a combination thereof, and the computer-readable storage medium may include but is not limited to, for example, random access memory (RAM), read-only memory (ROM), flash memory, EPROM memory, EEPROM memory, registers, computer storage media (e.g., hard disk, floppy disk, solid-state drive, removable disk, CD-ROM, DVD-ROM, Blu-ray disc, etc.).

The computer-readable storage medium may also store at least one computer executable program/instruction, which may be, for example, a computer-readable instruction. The computer-readable storage medium includes, but is not limited to, for example, a volatile memory and/or a non-volatile memory. The volatile memory may include, for example, a random access memory (RAM) and/or a cache memory (cache), etc. The computer-readable storage medium may include, for example, a read-only memory (ROM), a hard disk, a flash memory, etc. For example, a non-transitory computer-readable storage medium may be connected to a computing device such as a computer, and then, when the computing device runs the computer-readable instructions stored on the computer-readable storage medium, the various methods described above may be performed.

In addition, the computer device may also include (but not limited to) a data bus, an input/output (I/O) bus, a display, and input/output devices (e.g., keyboard, mouse, speakers, etc.), etc.

The processor may communicate with external devices via an I/O bus via a wired or wireless network.

In one embodiment, the at least one computer executable instruction may also be compiled into or constitute a software product/computer program product, wherein one or more computer executable instructions are executed by a processor to perform the various functions and/or method steps in the embodiments described in the present technology.

In the embodiments provided in the present disclosure, it should be understood that the disclosed devices and methods can also be implemented in other ways. The device embodiments described above are merely schematic. For example, the flowcharts and block diagrams in the accompanying drawings show the possible architecture, functions and operations of the devices, methods and computer program products according to multiple embodiments of the present disclosure. In this regard, each box in the flowchart or block diagram can represent a module, a program segment or a part of a code, and the above-mentioned module, program segment or a part of the code contains one or more executable instructions for implementing the specified logical function. It should also be noted that in some alternative implementations, the functions marked in the box can also occur in a different order from the order marked in the accompanying drawings. For example, two consecutive boxes can actually be executed substantially in parallel, and they can sometimes be executed in the opposite order, depending on the functions involved. It should also be noted that each box in the block diagram and/or flowchart, and the combination of boxes in the block diagram and/or flowchart can be implemented with a dedicated hardware-based system that performs a specified function or action, or can be implemented with a combination of dedicated hardware and computer instructions.

It should be noted that in the present disclosure, the terms "include", "comprises" or any other variations thereof are intended to cover non-exclusive inclusion, so that a process, method, article or device including a series of elements includes not only those elements, but also other elements not explicitly listed, or also includes elements inherent to such process, method, article or device. In the absence of further restrictions, an element limited by the sentence "includes a ..." does not exclude the existence of other identical elements in the process, method, article or device including the element.

Although the embodiments disclosed in the present disclosure are as above, the above contents are only embodiments adopted for facilitating the understanding of the present disclosure and are not intended to limit the present disclosure. Any technician in the technical field to which the present disclosure belongs can make any modifications and changes in the form and details of the implementation without departing from the spirit and scope disclosed in the present disclosure, but the scope of patent protection of the present disclosure shall still be subject to the scope defined in the attached claims.

Claims (20)

1. A method for cache coherency optimization in automatic thread-level parallelization, comprising:

the compiler responds to automatic parallelization compiling of thread level of one cycle to acquire all consistency shared variables;

according to the consistency shared variable, searching access instructions accessing the consistency shared variable from all access instructions, and determining the access instructions as consistency instructions;

According to a preset rule, determining a corresponding consistency instruction stream fragment of each consistency instruction and a private instruction stream fragment not containing the consistency instruction, generating a first target instruction subsequence for maintaining cache consistency for each consistency instruction stream fragment, and generating a second target instruction subsequence for not maintaining cache consistency for each private instruction stream fragment;

The first target instruction sub-sequence and the second target instruction sub-sequence each correspond to a target processor; the target processor has the function of maintaining inter-core cache consistency and supports executing access instructions under the condition of closing the cache consistency.

2. The method of claim 1, wherein the compiler obtains all coherency shared variables in response to automatically parallelizing compilation at a thread level of one loop, comprising at least one of:

obtaining a cache consistency setting command from the guidance command of the automatic parallelization compilation, and obtaining all consistency shared variables from the cache consistency setting command;

and acquiring attribute information of each variable, determining whether each variable is a consistency shared variable based on the attribute information, and determining all consistency shared variables.

3. The method according to claim 1, characterized in that the method further comprises:

And acquiring a current compiling option corresponding to the compiler, acquiring cache consistency compiling setting from the current compiling option, and taking all variables as consistency shared variables when the cache consistency compiling setting is closing cache consistency optimization.

4. The method of claim 1, wherein the target processor has functionality to maintain inter-core cache coherency and supports execution of memory access instructions with cache coherency turned off, comprising at least one of:

The target processor provides a cache consistency opening instruction and a cache consistency closing instruction, wherein the cache consistency opening instruction is used for setting the state of a cache consistency protocol of a current processor core to be an opening state, and the cache consistency closing instruction is used for setting the state of the cache consistency protocol of the current processor core to be a closing state;

The target processor provides a cache consistency access instruction, a private access instruction or a common access instruction, wherein the cache consistency access instruction executes under any condition to initiate a cache consistency operation request, the private access instruction executes under any condition to not initiate the cache consistency operation request, the common access instruction initiates the cache consistency operation request when the cache consistency protocol of the current processor core is in an on state, and the common access instruction does not initiate the cache consistency operation request when the cache consistency protocol of the current processor core is in an off state.

5. The method according to claim 4, wherein the method further comprises:

when the cache consistency protocol of the current processor core is in a closed state and executes a memory access instruction which is not the cache consistency memory access instruction, no operation related to cache consistency is initiated to a hardware system of the cache consistency;

the cache consistency closing instruction has a response opening mode and a response closing mode;

After executing the cache consistency closing instruction in the response opening mode, the current processor core always responds to the cache consistency operation initiated by other processor cores;

and after executing the cache consistency closing instruction in the response closing mode, the current processor core ignores the cache consistency operation initiated by other processor cores.

6. The method of claim 4, wherein generating a first target instruction sub-sequence that maintains cache coherency for each of the coherent instruction stream fragments comprises at least one of:

Each consistent instruction in each consistent instruction stream segment corresponds to one cache consistent memory instruction or one common memory instruction in the first target instruction subsequence;

The first instruction of the first target instruction sub-sequence of one of the consistent instruction stream fragments is a cache coherency on instruction or the last instruction of the first target instruction sub-sequence of one of the consistent instruction stream fragments is a cache coherency off instruction.

7. The method of claim 4, wherein generating a second target instruction sub-sequence for each of the private instruction stream fragments that does not maintain cache coherency comprises at least one of:

each access instruction in each private instruction stream fragment corresponds to one private access instruction or one common access instruction in the second target instruction subsequence;

The first instruction of the second target instruction sub-sequence of one of the private instruction stream fragments is a cache coherence close instruction, or the last instruction of the second target instruction sub-sequence of one of the private instruction stream fragments is a cache coherence open instruction.

8. The method of claim 1, wherein determining the coherence instruction stream segment corresponding to each coherence instruction and the private instruction stream segment not containing the coherence instruction comprises:

Each consistent instruction stream fragment contains one or more instructions, and when only one instruction is contained, the instruction is the consistent instruction;

each instruction stream segment other than all of the consistent instruction stream segments of the loop is determined to be a private instruction stream segment.

9. The method according to claim 1, wherein the step of determining a consistent instruction stream segment corresponding to each consistent instruction according to a preset rule includes:

Acquiring a data dependency relationship between the consistency instructions;

At least two consistent instructions with data dependency are aggregated into the same consistent instruction stream segment.

10. The method according to claim 1, wherein the step of determining a consistent instruction stream segment corresponding to each consistent instruction according to a preset rule includes:

Acquiring a data dependency relationship between the consistency instructions;

scheduling at least two consistent instructions which have no data dependency relationship to each other to adjacent positions;

and aggregating the scheduled adjacent consistent instructions into the same consistent instruction stream fragment.

11. The method according to claim 1, wherein the step of determining a consistent instruction stream segment corresponding to each consistent instruction according to a preset rule includes:

determining a consistency instruction corresponding to the consistency shared variable in a plurality of iterations of the loop;

and aggregating the corresponding consistency instructions of the consistency shared variable in a plurality of iterations into the same consistency instruction stream segment.

12. The method according to claim 1, wherein the step of determining a consistent instruction stream segment corresponding to each consistent instruction according to a preset rule includes:

Creating a temporary array with the element number of N according to the number of the consistency shared variables of N;

reading N elements of each consistency shared variable into the temporary array once or assigning N elements of the temporary array to the consistency shared variable once every N iterations; replacing the instruction for accessing each consistency shared variable with an array access instruction for the temporary array;

And adding the memory access instruction corresponding to the one-time reading and the one-time assignment to the consistent instruction stream fragment.

13. The method according to claim 1, wherein the step of determining a consistent instruction stream segment corresponding to each consistent instruction according to a preset rule includes:

Acquiring at least two consistent instructions in a preset range according to an execution sequence and a memory access instruction between the consistent instructions in the preset range, and determining the memory access instruction as an instruction to be combined;

Under the condition that all the instructions to be combined are combined into a consistent instruction stream segment, calculating consistent operation cost generated by memory access instructions among consistent instructions in a preset range, and obtaining first operation cost;

Calculating operation cost reduced by the times of starting and closing states of a cache consistency protocol under the condition that the instructions to be combined are combined into a consistency instruction stream segment, and obtaining second operation cost;

and when the first operation cost is smaller than the second operation cost, determining that all the instructions to be combined are combined into a consistent instruction stream fragment.

14. The method according to claim 1, wherein the step of determining a consistent instruction stream segment corresponding to each consistent instruction according to a preset rule includes:

acquiring the number of access instructions between at least two consistency instructions in a preset range according to the execution sequence, and determining the number as the number of other access instructions;

And when the number of other memory access instructions is smaller than or equal to the preset instruction number threshold, merging at least two consistent instructions in a preset range according to the execution sequence and memory access instructions among the consistent instructions in the preset range into a consistent instruction stream fragment.

15. The method according to claim 1, wherein the step of determining a consistent instruction stream segment corresponding to each consistent instruction according to a preset rule includes:

and determining a mutual exclusion zone in the cache zone, and merging all instructions of the mutual exclusion zone into a consistent instruction stream fragment.

16. The method according to claim 1, wherein the method further comprises:

responding to execution of a data prefetching instruction, and detecting whether at least one access instruction exists in all access instructions triggering the data prefetching instruction as a cache consistent access instruction or an open state corresponding to a cache consistent protocol;

When at least one access instruction exists in each access instruction triggering the data prefetching instruction as a cache consistent access instruction or an open state corresponding to a cache consistency protocol, determining to initiate a cache consistency operation request when the data prefetching instruction is executed;

When all access instructions triggering the data prefetch instruction are private access instructions or a closed state corresponding to a cache coherency protocol, it is determined that a cache coherency operation request is not initiated when the data prefetch instruction is executed.

17. A cache coherency optimization apparatus in automatic thread-level parallelization, comprising:

The shared variable acquisition module is used for responding to automatic parallelization compiling of a thread level of one cycle by the compiler, acquiring a cache consistency setting command from a guidance instruction of the automatic parallelization compiling and acquiring all consistency shared variables from the cache consistency setting command;

The instruction determining module is used for searching access instructions accessing the consistency shared variable from all access instructions according to the consistency shared variable and determining the access instructions as consistency instructions;

The instruction stream segment determining module is used for determining the consistent instruction stream segment corresponding to each consistent instruction according to a preset rule;

The instruction insertion module is used for inserting a cache consistency starting instruction before the execution sequence of each consistency instruction stream segment and inserting a cache consistency closing instruction after the execution sequence of each consistency instruction stream segment, wherein the cache consistency starting instruction is used for setting the state of the cache consistency protocol of the current processor core into an on state, and the cache consistency closing instruction is used for setting the state of the cache consistency protocol of the current processor core into a closed state.

18. A computer device comprising a memory, a processor and a computer program stored on the memory, characterized in that the processor executes the computer program to carry out the steps of the method of any one of claims 1 to 16.

19. A computer readable storage medium, on which a computer program is stored, characterized in that the computer program, when being executed by a processor, implements the steps of the method of any of claims 1 to 16.

20. A computer program product comprising computer programs/instructions which, when executed by a processor, implement the steps of the method of any one of claims 1 to 16.