WO2022110567A1 - Data reuse memory access conflict elimination method for coarse-grained reconfigurable structure - Google Patents

Abstract

A data reuse memory access conflict elimination method for a coarse-grained reconfigurable structure. Provided is a loop transformation model which is applied to a perfect nested loop kernel and is used for maximizing effective data reuse so as to maximize available data reuse between iterations in a program running process and a configuration file change strategy in a code generation stage. Redundant memory access operation in a data reuse pair is eliminated, and memory access conflicts in the loop execution process are reduced.

Description

A Data Reuse Method to Eliminate Fetch Conflicts for Coarse-grained Reconfigurable Structures technical field

The present application relates to the field of coarse-grained reconfigurable structure compilers, and in particular, to a cyclic transformation model for maximizing effective data reuse for reconfigurable structures and a configuration file modification strategy for the code generation stage.

Background technique

Coarse-Grained Reconfigurable Architecture (CGRA) is a new hardware architecture with higher energy efficiency. It is mainly used for hardware acceleration of computationally intensive applications, such as video processing, neural network operations. After research and investigation, it is found that the application execution time is mainly consumed in the kernel part of the program loop. The reference ADRES[1] model gives a typical CGRA structure, as shown in Figure 1. The compiler abstracts the program loop kernel part as a data flow graph (DFG) and maps it to different processing elements (PE) in the coarse-grained processing element array (PEA), And it is executed through soft water technology. The machine cycle required between two loop iterations is called the initiation interval (II), and the smaller the II, the better the acceleration performance. One of the main goals of a compiler for coarse-grained reconfigurable architectures is to efficiently choose scheduling and mapping strategies to minimize the II of the loop kernel.

However, the software pipeline technology increases the requirement for the parallelism of data access to the on-chip register file (ORF), and the pipeline interruption caused by memory access conflicts becomes the bottleneck of the efficiency of CGRA. The ORF is connected to each column of PEA through the crossbar and the column bus, and different PEs can access each storage bank of the on-chip memory through the column bus where they are located. When multiple operations occupy the same hardware resources at the same time in the same cycle (such as accessing the same bank of multi-bank on-chip memory at the same time, or accessing on-chip memory through the column bus exceeds the bandwidth limit of the column bus), it will cause the soft pipeline to stall, resulting in II Increase.

Research on 22 commonly used computing cores shows that the number of memory access operations accounts for 52.2% of all operations, and the delay caused by memory access conflicts between memory access operations in the same control cycle accounts for 68.4% of the total running time. The existing work to eliminate memory access conflicts mostly focuses on adjusting the location of memory access operations in the scheduling and mapping stages, and adjusting the storage location of data in the on-chip memory, but it lacks the root cause of memory access conflicts, which is caused by soft pipelining technology. The excessive number of memory fetch operations is optimized.

Some studies and analyses are as follows:

1. Research on the application of polyhedral model to coarse-grained reconfigurable architecture

The cyclic transformation based on the polyhedral model is a new cyclic optimization method. Compared with the traditional unimodular matrix model, which uses affine transformation as the cyclic transformation, it has a wide range of applications, strong expressive ability, and large optimization space. advantage. Today's compilers in various fields such as Google MLIR[2], Polly[3], TVM[4] all use the polyhedron model. But less work has been done to apply the polyhedral compilation model to the compilation process for coarse-grained reconfigurable architectures. The PolyMap proposed in reference [5] utilizes the polyhedron compilation model, adjusts the hierarchical structure of the loop kernel through the analysis of the entire mapping flow, and realizes the parallelization of the loop unrolling in the inner layer of the loop kernel. Reference [6] will use the polyhedron model to represent the program and the program transformation process, and use the genetic algorithm to perform cyclic transformation to achieve higher computational efficiency. However, none of the above studies considered the application of the polyhedron model to increase data reuse between loop iterations to reduce the number of redundant memory access operations.

2. Research on reducing the conflict of operation access on CGRA

Memory fetch conflicts are mainly accessed by a large number of memory fetch operations at the same time. Existing researches on reducing memory access conflicts mostly focus on optimizing scheduling, mapping processes, and data storage methods in on-chip memory, so as to reduce multi-bank conflicts accordingly. Reference [7] divides the data into multiple clusters, so that the probability of different clusters being accessed is as equal as possible. This approach resolves conflicts at the high level of the array, and the coarse-grained approach results in limited optimization effects. Reference [8] analyzes all memory access addresses to a single array by the loop kernel in a single control cycle, and uses linear transformation to map different addresses to different storage locations in different on-chip memories. Reference [9] further subdivides the structure of the storage bank on the basis of reference [8], adds data partitions on the block, and increases the flexibility of linear transformation. Reference [10] upgrades the selection of linear transformation parameters from the analysis of single array access in a single control cycle to different array accesses in different control cycles, further reducing multi-bank conflicts. At the same time, a memory bank merging algorithm is proposed to improve the area-performance ratio of the memory bank. Reference [11], on the basis of Reference [10], changes the execution time of each access operator in the scheduling process to further reduce access conflicts. At the same time, a dual-forced scheduling scheme is proposed, and then the memory access operations are divided into different control cycles as much as possible. However, none of the above studies consider the method of reducing the number of memory access operations to reduce memory access conflicts.

The references mentioned above are as follows:

[1] Y.Park, J.J.K.Park, and S.Mahlke.2012.Efficient performance scaling of future CGRAs for mobile applications.In International Conference on Field-Programmable Technology(FPT).335–342.

[2] Lattner C, Amini M, Bondhugula U, et al. MLIR: A Compiler Infrastructure for the End of Moore's Law [J]. 2020.

[3] Grosser, T., Groesslinger, A., & Lengauer, C. (2012). Polly-Performing polyhedral optimizations on a low-level intermediate representation. Parallel Processing Letters, 22(4), 1–28.

[4] Chen, Tianqi, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan et al."TVM:An automated end-to-end optimizing compiler for deeplearning."In 13th USENIX Symposium on Operating Systems Design andImplementation (OSDI 18), pp.578-594.2018.

[5] Liu, D., Yin, S., Peng, Y., Liu, L., & Wei, S. (2015). Optimizing Spatial Mapping of Nested Loop for Coarse-Grained Reconfigurable Architectures. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 23(11), 2581–2594.

Armin,Siegmund N,et al.Speeding up Itewrative Polyhedral Schedule Optimization with Surrogate Performance Models[J].Acm Transactions on Architecture&Code Optimization,2018,15(4):1-27. [6] Ganser S,

Armin,Siegmund N,et al.Speeding up Itewrative Polyhedral Schedule Optimization with Surrogate Performance Models[J].Acm Transactions on Architecture&Code Optimization,2018,15(4):1-27.

[7] Kim, Y., Lee, J., Shrivastava, A., & Paek, Y. (2010). Operation and data mapping for CGRAs with multi-bank memory. Proceedings of the ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES), 17–25.

[8] Wang Y, Li P, Zhang P, et al. Memory partitioning for multidimensional arrays in high-level synthesis[C]//Acm/edac/ieee Design Automation Conference.IEEE, 2013.

[9] Wang, Y., Li, P., & Cong, J. (2014). Theory and algorithm for generalized memory partitioning in high-level synthesis. ACM/SIGDA International Symposium on Field Programmable Gate Arrays-FPGA, 199–208 .

[10] Yin S, Xie Z, Meng C, et al.MultiBank memory optimization for parallel data access in multiple data arrays[C]//IEEE/ACM International Conference on Computer-aided Design.IEEE, 2017.

[11] Park, Hyunchul & Fan, Kevin & Mahlke, Scott & Oh, Taewook & Kim, Heeseok & Kim, Hong-seok. (2008). Edge-centric modulo scheduling for coarse-grained reconfigurable architectures. Parallel Architectures and Compilation Techniques-Conference Proceedings, PACT.166-176.10. 1145/1454115.1454140.

SUMMARY OF THE INVENTION

In view of the above-mentioned defects of the prior art, the purpose of this application is to develop a new method based on the CGRA architecture, in the compilation stage, the software loop code is compiled and optimized to maximize the data available between iterations during the program running process. Reuse, and a method for eliminating redundant fetches in data-reuse pairs, thereby reducing fetch conflicts during loop execution.

Include the following steps:

Step 1. Use the CGRA compiler front-end to compile the loop kernel part of the source program into the first intermediate representation;

Step 2, performing a cyclic transformation of effective data reuse between iterations to obtain a transformed second intermediate representation;

Step 3. Generate a data flow graph to obtain a mapping result;

Step 4. Select a modification strategy for data reuse;

Step 5. Generate a configuration file;

The step 2 further includes:

Step 2.1, analyze the dependency relationship and data reuse relationship in the original code, and obtain the dependency set and the reuse set; wherein, the reuse relationship means that two operations in different iterations access the same location in the memory, then the two operations are reused relationship; the two operations in the reuse relationship form a producer/consumer pair that includes a producer and a consumer, and the type of the producer/consumer pair includes a Load-Load reuse pair , Load-Store reuse pair, Store-Load reuse pair and Store-Store reuse pair;

Step 2.2. Constrain the search space of the innermost time vector according to the dependency set; search the remaining search spaces that meet the constraints in turn, and find the innermost time vector with the largest number of effective reuses in the reuse set; according to the obtained optimal innermost time vector layer time vector, recursively get the outer layer time vector;

Step 2.3, generating the second intermediate representation according to the time vector of each layer;

Described step 4 further comprises:

Step 4.1. Analyze the data reuse relationship in the loop kernel to obtain different data reuse sets available; check whether each reuse relationship satisfies the hardware constraints in turn, and record the final available data reuse relationship in the producer and consumer nodes of the reuse relationship information;

Step 4.2: When the configuration file is generated, select the corresponding modification strategy according to the reuse relationship to which the node belongs.

Further, for the Load-Load reuse pair and the Store-Load reuse pair, in the step 2, a local register LRF (Local register file) is used to buffer the output of the producer, and the consumer loads data from the LRF.

Further, for the Load-Load reuse pair and the Store-Load reuse pair, in the step 2, a global register GRF (global register file) is used to buffer the output of the producer, and the consumer loads data from the GRF.

Further, in the step 2, a method based on affine transformation is used to arrange the execution sequence of the loop iteration.

Further, in the step 2.2, a first strategy is used to select cyclic transformations, wherein the first strategy refers to a strategy for narrowing the selection range of optional cyclic transformations based on dependencies, which includes the following steps:

为第m维的时间向量，表示在该层连续两次迭代之间所有循环索引的变化为

其中x _mi表示在完美嵌套循环的第m层，第i个循环变量每次循环迭代将会增加x _mi；设完美嵌套循环中依赖集合R＝{<s,d>}，即循环迭代s必须在循环迭代d之前执行；依赖集合中各元素的d与s的差值称为依赖向量，被保存在M _R中；对于一组依赖向量集合M _R，选取的时间向量组的最内层时间向量

至少满足公式(1)和公式(2)中的任意一个： definition

is the time vector of the mth dimension, indicating that the change of all loop indices between two consecutive iterations of this layer is

where x _mi indicates that at the mth level of the perfectly nested loop, the i-th loop variable will increase x _mi for each loop iteration; set the dependency set R={<s,d>} in the perfect nested loop, that is, the loop iteration s must be executed before loop iteration d; the difference between d and s of each element in the dependency set is called the dependency vector and is stored in _MR ; for a set of dependency vector sets _MR , the innermost value of the selected time vector group is layer time vector

At least one of formula (1) and formula (2) is satisfied:

其中c为实数且c取值范围为0＜c≤1。 Among them, cone(M _R ) represents a vertebral body formed by _MR elements, and cone( _MR -ir ) represents a vertebral body formed by elements other than i _{r ;} formula (1) represents the currently selected time vector The line where it is located cannot be in the vertebral body composed of dependency vectors; formula (2) means that the currently selected time vector can be collinear with a vector on the vertebral body surface composed of all dependency vectors, and the dependency vector must be greater than or equal to the time vector, i.e.

where c is a real number and the value range of c is 0<c≤1.

Further, in step 2.2, the innermost time vector is iteratively selected using the first strategy from the innermost loop; after selecting an innermost time vector, all the dependency vectors are projected onto the normal plane of the time vector, and iteratively choose the next dependency vector; finally get a cyclic transformation that satisfies the cyclic dependency.

Further, the step 2.2 includes a second strategy, and the second strategy refers to a strategy for selecting cyclic transformations to maximize effective data reuse, which includes the following steps:

表示访存操作p在迭代i中访问了片上存储器

地址；给定重用对

对应的下列公式(3)成立时，它是有效的；其中c是一个常量阈值，用于帮助选择有效的重用对： A memory fetch operation p is represented as

Indicates that the memory fetch operation p accessed on-chip memory in iteration i

address; given a reuse pair

It is valid when the corresponding following formula (3) holds; where c is a constant threshold to help select valid reuse pairs:

Each reuse pair has a corresponding formula (3), so that as many reuse pairs as possible are valid, that is, the innermost time vector that makes formula (3) true as much as possible is the optimal time vector; the optimal transformation search algorithm first searches The optimal time vector of the innermost layer, and then the time vector of the outer layer is recursively calculated according to the time vector of the inner layer using formula (2).

Further, in the step 4.2, modifying the strategy includes:

The Store-Store reuse pair is not limited by the interval iteration between producer and consumer, the producer in this reuse relationship pair is eliminated.

Further, in step 4.2, the modification strategy includes:

For the Store-Load reuse pair and the Load-Load reuse pair, data is transferred from the producer to the consumer.

Further, data is transferred from producers to consumers using interconnected resources.

Further, use registered resources to transfer data from producers to consumers.

Further, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes:

If the clock cycle I(r) ≤ 0 between the producer and the consumer, the reuse pair is invalid.

Further, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes:

The clock cycle I(r) between the producer and the consumer satisfies 1≥I(r)>0, and there is an interconnection resource connection between the PE where the producer is located and the PE where the consumer is located, then the reused Consumers are translated into routing operations that access data from the producer's output registers.

Further, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes:

The clock cycle I(r)>1 between the producer and the consumer uses register resources to temporarily store data.

Further, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes:

满足

的情形， For pe(s)=pe(t), and the remaining space of the LRF on pe(s)

Satisfy

situation,

The reused data is stored in the LRF, and the consumer is transformed into a routing operation that obtains data from the LRF, where II is the start interval of the software pipeline;

Among them, pe(s) and pe(t) represent the PE where the producer and consumer are located, respectively.

Further, the modification strategy includes:

In the case where LRF is not selected, and the remaining GRF space satisfies

GRF is then used to temporarily store data.

Further, the modification strategy includes:

For accumulation reuse, the output operation sends data to the input operation according to the modification policy of the Store-Load reuse pair, and memory access operations during accumulation are converted to no-ops.

Further, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes:

For the case of Con(r)=true, pe(s)≠pe(t), add additional routing nodes to move data through LRF;

Among them, pe(s) and pe(t) represent the PEs where the producer and the consumer are located, respectively, and Con(r)=true means that there is an interconnection resource connection between pe(s) and pe(t).

Further, the modification strategy includes:

In the case where LRF is not selected, and the remaining GRF space satisfies

GRF is then used to temporarily store data.

Further, the modification strategy includes:

For accumulation reuse, the output operation sends data to the input operation according to the modification policy of the Store-Load reuse pair, and memory access operations during accumulation are converted to no-ops.

Compared with the prior art, the beneficial effects of the present application are as follows:

1. Compared with the existing solutions for reducing memory access conflicts, the present application innovatively uses the data reuse relationship between loops to modify the configuration file in the configuration file generation stage to reduce the number of memory access operations of the CGRA operation loop kernel, thereby avoiding Fetch conflict.

2. This method is orthogonal to the existing methods for scheduling and mapping phase and data rearrangement and storage, and has strong scalability. It can simply work with the existing data placement scheme, scheduling and mapping scheme to achieve better results. High application speedup.

Description of drawings

Fig. 1 is a typical architecture diagram of a 4x4 CGRA in the prior art;

2 is a schematic diagram of a compiler backend flow diagram of an embodiment of the present application;

Fig. 3 is the cyclic transformation model process of the embodiment of the present application;

4 is a schematic diagram of a configuration file modification strategy according to an embodiment of the present application;

Figure 5 is the running time of an embodiment of the present application under 22 kernels on a 4x4 PEA.

Detailed ways

The preferred embodiments of the present application will be described below with reference to the accompanying drawings, so as to make its technical content clearer and easier to understand. The present application can be embodied in many different forms of embodiments, and the protection scope of the present application is not limited to the embodiments mentioned herein.

The concept, specific structure and technical effects of the present application will be further described below to fully understand the purpose, features and effects of the present application, but the protection of the present application is not limited to this.

As shown in FIG. 2, a schematic diagram of a compiler back-end flow according to an embodiment of the present application, wherein,

Step 201, adopts the CGRA compiler front-end based on LLVM (Low Level Virtual Machine) to compile the loop kernel part of the source program into the form of intermediate representation (IR);

Steps 202-204, for the IR generated by the front-end, using the cyclic transformation model that maximizes effective data reuse between iterations proposed by the present application, obtain a new affine-transformed cyclic kernel IR; wherein,

Step 202, analyze the dependency relationship and data reuse relationship in the original code to obtain a dependency set and a reuse set;

Step 203: Constrain the search space of the innermost time vector according to the dependency set; search the remaining search spaces that meet the constraints in turn, and find the innermost time vector with the largest number of effective reuses in the reuse set; The inner time vector, recursively get the outer time vector;

Step 204, generating a new intermediate representation according to each layer time vector;

From step 205 to step 210, a data flow graph is generated through the modified intermediate representation, and a mapping result is obtained by using the existing scheduling, data differentiation, and spatial mapping schemes in the prior art; wherein, the existing scheduling, data Discrimination and spatial mapping schemes can be obtained from documents [12] and [13], that is, documents [12] and [13] are incorporated into this application by reference, and documents [12] and [13] are listed in the detailed description end of section

Steps 211-212, selecting a modification strategy by adopting the configuration file modification scheme considering data reuse proposed in this application;

Step 211, analyze all data reuse relationships in the loop kernel, and obtain different data reuse sets available; check whether each reuse relationship satisfies hardware constraints in turn, and record the finally available data reuse relationship in the producer and consumer of the reuse relationship. User node information;

Step 212, when the configuration file is generated, select a corresponding modification strategy according to the reuse relationship to which the node belongs;

Step 213, generating a configuration file according to the previous modification policy.

In the above process, the method of reducing the number of redundant memory access operations is adopted to reduce the number of memory access conflicts during the execution of the loop kernel, which is the difference between the present application and other studies. In addition, unlike the existing work of reducing memory access conflicts, which is aimed at the placement, scheduling and mapping strategies of data in the on-chip memory, the present application can be orthogonally combined with the existing scheduling, data placement, and mapping strategies to further improve the The performance of existing optimization work. The use of the optimization method for reducing memory access conflicts for the front-end loop transformation and configuration file generation stages enables the present application to be combined with most existing methods for reducing memory access conflicts, which is another difference between the present application and other researches.

cyclic transformation

If two operations in different iterations access the same location in memory, there is a reuse relationship between the two operations. Depending on the order in which the data is accessed, the two operations of a reuse relationship form a producer/consumer pair, also known as a reuse pair. Reuse pairs can be divided into four categories, namely Load-Load (two load operations), Load-Store (load first, then write), Store-Load (write first, then load), and Store-Store (two write operations) reuse. For Load-Load or Store-Load reuse pairs, we use a local register file (LRF) or a global register file (GRF) to buffer the output of the producer, so that the consumer only needs to load data from the LRF or GRF, There is no need to access the OGM, thereby reducing memory access operations. However, due to the limited size of GRFs and LRFs provided by the hardware, our compiler should guarantee that the reused data can be successfully preserved for the lifetime of the LRF or GRF. Therefore, the goal of our loop transformation model is to use an affine transformation-based approach to orchestrate the execution order of loop iterations to minimize the lifetime of reusing data between iterations.

In step 203 shown in FIG. 2 , the present application proposes a strategy for narrowing the selection range of optional cyclic transformations according to dependencies.

为第m维的时间向量，表示在该层连续两次迭代之间所有循环索引的变化为

其中x _mi表示在完美嵌套循环的第m层，第i个循环变量每次循环迭代将会增加x _mi。对于图3(a)中的循环程序，它的时间向量集合表示为

和

一组时间向量对应了一个确定的循环执行顺序，可以通过对一组时间向量进行仿射变换，从而调整循环内部迭代的执行顺序，但是此变换不可以违反原有循环的依赖关系。设完美嵌套循环中依赖集合R＝{<s,d>}，即循环迭代s必须在循环迭代d之前执行。依赖集合中各元素的d与s的差值称为依赖向量，被保存在M _R中。对于一组依赖向量集合M _R，选取的时间向量组的最内层时间向量

至少满足公式(1)和公式(2)中的任意一个，那么这一组时间向量组才有可能合法： definition

is the time vector of the mth dimension, indicating that the change of all loop indices between two consecutive iterations of this layer is

where _xmi denotes that at the mth level of a perfectly nested loop, the i-th loop variable will increase by _xmi for each loop iteration. For the loop program in Figure 3(a), its set of time vectors is expressed as

and

A set of time vectors corresponds to a certain loop execution order, and the execution order of iterations inside the loop can be adjusted by performing affine transformation on a set of time vectors, but this transformation cannot violate the dependencies of the original loop. Let the set of dependencies R={<s,d>} in a perfectly nested loop, that is, the loop iteration s must be executed before the loop iteration d. The difference between d and s of each element in the dependency set is called a dependency vector and is stored in _MR . For a set of dependency vector sets _MR , the innermost time vector of the selected time vector set

At least any one of formula (1) and formula (2) is satisfied, then this set of time vector groups may be legal:

其中c为实数且c取值范围为0＜c≤1。 Among them, cone( _MR ) _represents a vertebral body formed by elements of MR, and cone( _MR - _ir ) represents a vertebral body formed by elements other than _ir . Formula (1) indicates that the line where the currently selected time vector is located cannot be in the vertebral body composed of the dependency vectors; formula (2) indicates that the currently selected time vector can be collinear with a vector on the surface of the vertebral body composed of all dependent vectors, And the dependency vector must be greater than or equal to the time vector, that is

where c is a real number and the value range of c is 0<c≤1.

According to the above selection strategy, the present application iteratively uses this strategy to select the legal innermost time vector from the innermost loop. After selecting an innermost time vector, all dependency vectors can be projected onto the time vector normal plane, and the next dependency vector can be selected iteratively. Finally, a cyclic transformation that satisfies the cyclic dependency can be obtained.

表示访存操作p在迭代i中访问了片上存储器

地址。给定重用对

对应的下列公式(3)成立时，它是有效的。其中c是一个常量阈值，用于帮助选择有效的重用对。 In step 203 shown in FIG. 2, the present application proposes a strategy for selecting cyclic transformations to maximize effective data reuse. Whether a Load-Load or Store-Load reuse pair is valid depends on the innermost time vector when searching for optimal transitions. A fetch operation p can be represented as

Indicates that the memory fetch operation p accessed on-chip memory in iteration i

address. given reuse pair

It is valid when the corresponding following formula (3) holds. where c is a constant threshold used to help select valid reuse pairs.

Each reused pair has a corresponding formula (3), so that as many reused pairs as possible are valid, that is, the innermost time vector for which formula (3) is established as much as possible is the optimal time vector. The optimal transform search algorithm first searches for the optimal time vector of the innermost layer, and then uses formula (2) to recursively calculate the time vector of the outer layer according to the time vector of the inner layer.

As shown in FIG. 3 , in order to further illustrate the above-mentioned cyclic transformation method, the program shown in FIG. 3( a ) is taken as an example. The goal of the optimization problem is to maximize the number of equations established in Figure 3(e). The nodes in Fig. 3(g) represent the innermost candidate time vectors, where the feasible solutions to the optimization problem are nodes, highlighted as gray nodes. Figure 3(f) shows the time vector for each recurrent layer. Figure 3(h) shows the transformed program, while the innermost loop is split into two layers in order to traverse all iterations.

Configuration file correction

During configuration file generation, we propose a configuration file modification strategy to eliminate unnecessary memory access operations by exploiting data reuse between iterations. The algorithm first analyzes whether each group of reused pairs satisfies the time constraints and register space constraints, and then adopts different modification strategies to reduce memory access operations. The modification strategy is shown in Figure 4. Figure 4(a) is a representation of the PE structure, where Op represents an operation placed on the PE, including P represents a producer in a reused pair, C represents a consumer, and R represents a routing node. The LRF owned by each PE is also marked, and the LRF mark drawn with a diagonal pattern indicates that the LRF stores data.

Store-Store reuse is not limited by interval iterations between producers and consumers. If such a reuse relationship exists, the producer in the reuse relationship pair needs to be eliminated. Figure 4(b) shows the modification strategy for Store-Store reuse.

For Store-Load and Load-Load reuse, interconnect resources or registered resources should be used to move data from producers to consumers. Given a data reuse pair, r = <s,t,d>, where s is the producer in the reused pair, t is the consumer in the reused pair, and d is the interval iteration number between s and t. Assuming that the operation s is mapped to the pe(s)th PE of the control cycle time(s) in the software pipeline, the reuse of the clock cycle I(r) between the producer and the consumer can be passed through I(r) =d×II+(time(t)-time(s)), where II is the start interval of software pipeline.

If I(r) ≤ 0, the reuse pair is invalid for the producer to perform after or at the same time as the consumer.

When I(r)>0, the space constraints of this reused pair should be checked. Assuming that there is an interconnection resource connection between pe(s) and pe(t) where the producer and consumer are located, let Con(r) be true. Figure 4(d) shows the strategy chosen when I(r) = 1 and Con(r) = true, where the reused consumer is transformed into a routing operation that accesses data from the producer's output register.

When I(r)>1, register resources must be used to temporarily store data.

满足

重用的数据应该存储到LRF中，消费者被转换为从LRF获取数据的路由操作。 Fig. 4(c) shows the state when pe(s)=pe(t). If the remaining space of the LRF on pe(s)

Satisfy

The reused data should be stored into the LRF and the consumer is converted to a routing operation that gets the data from the LRF.

However, when I(r)≥1, Con(r)=true, and pe(s)≠pe(t), additional routing nodes need to be added for data movement. Suppose there are two empty operations np and nc, they satisfy pe(np)=pe(s), pe(nc)=pe(t), (time(nc)-time(np))mod II=1, the reused Data will be moved through the LRF by these two routing nodes. It is worth noting that producers and consumers can also be selected as np and nc. Figure 4(e) shows different strategies, including the strategy of selecting producers and consumers as routing nodes. The four diagrams from left to right show the location of producers and consumers. When the producer is selected as np, the consumer is selected as nc, or the spare nodes other than the producer and consumer are selected as np and nc configuration file remediation policy.

则GRF将用于临时存储数据。这种情况的修改策略如图4(f)所示。 If the above strategy is not selected, and the remaining GRF space should satisfy

Then the GRF will be used to temporarily store the data. The modification strategy for this case is shown in Fig. 4(f).

Beyond that, there are cumulative uses. That is to say, there is an accumulation operation on the data of the same storage location in the operation, and this operation can be temporarily performed in the local register without constantly accessing the main memory. Given a store-load reuse pair r=<s,t,d>, we call r a cumulative reuse if r′=<t,s,d> is a Load-Store reuse pair. The modification strategy for cumulative reuse is shown in Fig. 4(g) and Fig. 4(h), where the rectangular box containing the I and O blocks represents the set of all operations except memory access operations. Nodes marked I and O are operations that are directly connected to load and store operations (called input operations and output operations). Output operations send data to input operations according to the Store-Load reuse modification strategy, and memory access operations during accumulation should be converted to no-ops.

The selected strategy will be recorded, and in the configuration file generation stage of step 213, the generated configuration file will be modified through the selected strategy.

Outcome evaluation

Using the simulation environment designed and implemented for the typical CGRA structure based on ADRES mentioned in the Background Art section, the test integrates the cyclic transformation model and configuration file modification strategy proposed in this application in 22 typical calculation-intensive application test sets, 22 Compute-intensive cores are selected from datasets derived from digital signal processing, computer vision, and dynamic programming, such as existing benchmarks such as EEMBC, Polybench, and Machsuite. Figure 5 shows the integrated modulo scheduling compiler of the present application and the original compiler (that is, not using the present application, but using the compilation flow based on the following references [12] and [13], denoted as THP+DP) generation The configuration package execution time comparison. The results show that the configuration information generated by this application can achieve an average performance improvement of 44.4%, indicating that the solution described in this application can effectively improve the performance of the configuration information package generated by the coarse-grained reconfigurable architecture compiler compared with the existing solutions.

Table 1 shows the comparison of the number of memory access operations before and after the implementation of the solution described in this application:

It can be seen that the average memory access operation is reduced to 55.4% of the previous value, indicating that our model greatly reduces the number of memory access operations. Among them, the potential data reuse relationship of aes3, bezier1, and strassen1 is explored through the cyclic transformation model, and the number of data reuse pairs between two consecutive iterations in these three kernels increases from 0, 1, 14 to 4, 9, and 23. Furthermore, other kernels achieve maximum data reuse in their default state, so the loop transformation model effectively maximizes all available reuse relationships between loop iterations.

references

[12]Z.Zhao et al.,"Towards Higher Performance and Robust Compilation for CGRA Modulo Scheduling,"in IEEE Transactions on Parallel and Distributed Systems,vol.31,no.9,pp.2201-2219,1 Sept.2020 , doi:10.1109/TPDS.2020.2989149.

[13] Z. Zhao, Y. Liu, W. Sheng, T. Krishna, Q. Wang, and Z. Mao, “Optimizing the data placement and transformation for multi-bank cgra computing system,” in DATE, 2018, pp .1087–1092.

The preferred specific embodiments of the present application are described in detail above. It should be understood that many modifications and changes can be made in accordance with the concept of the present application without creative efforts by those skilled in the art. Therefore, any technical solutions that can be obtained by those skilled in the art through logical analysis, reasoning or limited experiments on the basis of the prior art according to the concept of the present application shall fall within the protection scope determined by the claims.

Claims (20)

A method for eliminating fetch conflicts by data reuse for coarse-grained reconfigurable structures, comprising the following steps: Step 1. Use the CGRA compiler front-end to compile the loop kernel part of the source program into the first intermediate representation; Step 2, performing a cyclic transformation of effective data reuse between iterations to obtain a transformed second intermediate representation; Step 3. Generate a data flow graph to obtain a mapping result; Step 4. Select a modification strategy for data reuse; Step 5. Generate a configuration file; The step 2 further includes: Step 2.1, analyze the dependency relationship and data reuse relationship in the original code, and obtain the dependency set and the reuse set; wherein, the reuse relationship refers to that two operations in different iterations access the same location in the memory, then the two operations are reused relationship; the two operations in the reuse relationship form a producer/consumer pair that includes a producer and a consumer, and the type of the producer/consumer pair includes a Load-Load reuse pair , Load-Store reuse pair, Store-Load reuse pair and Store-Store reuse pair; Step 2.2: Constrain the search space of the innermost time vector according to the dependency set; search the remaining search spaces that meet the constraints in turn, and find the innermost time vector with the largest number of effective reuses in the reuse set; The optimal innermost time vector, recursively obtain the outer time vector; Step 2.3, generating the second intermediate representation according to the time vector of each layer; Described step 4 further comprises: Step 4.1, analyze the data reuse relationship in the loop kernel, and obtain different data reuse sets available; check whether each reuse relationship satisfies the hardware constraints in turn, and record the finally available data reuse relationship in the reuse relationship. Producer and consumer node information; Step 4.2: When the configuration file is generated, select a corresponding modification strategy according to the reuse relationship to which the node belongs. The method for eliminating access conflict according to claim 1, wherein, in the step 2, for the Load-Load reuse pair and the Store-Load reuse pair, a local register LRF is used to buffer the output of the producer, The consumer loads data from the LRF. The method for eliminating memory access conflicts according to claim 1, wherein, in the step 2, for the Load-Load reuse pair and the Store-Load reuse pair, a global register GRF is used to buffer the output of the producer, The consumer loads data from the GRF. The method for eliminating memory access conflicts according to claim 1, wherein, in step 2, a method based on affine transformation is used to arrange the execution sequence of loop iterations. The method for eliminating memory access conflicts according to claim 4, wherein, in step 2.2, a first strategy is used to select cyclic transformations, wherein the first strategy refers to a strategy for narrowing the selection range of optional cyclic transformations based on dependencies, including Follow the steps below: definition

is the time vector of the mth dimension, indicating that the change of all loop indices between two consecutive iterations of this layer is

where x _mi indicates that at the mth level of the perfectly nested loop, the i-th loop variable will increase x _mi for each loop iteration; set the dependency set R={<s,d>} in the perfect nested loop, that is, the loop iteration s must be executed before loop iteration d; the difference between d and s of each element in the dependency set is called the dependency vector and is stored in _MR ; for a set of dependency vector sets _MR , the innermost value of the selected time vector group is layer time vector

At least one of formula (1) and formula (2) is satisfied:

Among them, cone(M _R ) represents a vertebral body formed by _MR elements, and cone( _MR -ir ) represents a vertebral body formed by elements other than i _{r ;} formula (1) represents the currently selected time vector The line where it is located cannot be in the vertebral body composed of dependency vectors; formula (2) means that the currently selected time vector can be collinear with a vector on the vertebral body surface composed of all dependency vectors, and the dependency vector must be greater than or equal to the time vector, i.e.

where c is a real number and the value range of c is 0<c≤1. The method for eliminating memory access conflicts according to claim 5, wherein, in step 2.2, the innermost time vector is iteratively selected from the innermost loop using the first strategy; after selecting an innermost time vector, All dependency vectors are projected onto the normal plane of the time vector, and the next dependency vector is selected iteratively; finally a cyclic transformation that satisfies the cyclic dependency is obtained. The method for eliminating memory access conflicts as claimed in claim 5, wherein the step 2.2 includes a second strategy, and the second strategy refers to a strategy for selecting cyclic transformations to maximize effective data reuse, which includes the following steps: A memory fetch operation p is represented as

Indicates that the memory fetch operation p accessed on-chip memory in iteration i

address; given a reuse pair

It is valid when the corresponding following formula (3) holds; where c is a constant threshold to help select valid reuse pairs:

Each reuse pair has a corresponding formula (3), where the innermost time vector that makes formula (3) true as much as possible is the optimal time vector; the optimal transformation search algorithm first searches for the innermost optimal time vector, Then, according to the time vector of the inner layer, formula (2) is used to recursively calculate the time vector of the outer layer. The method for eliminating memory access conflict according to claim 1, wherein, in step 4.2, the modifying strategy comprises: The Store-Store reuse pair is not limited by the interval iteration between the producer and the consumer, the producer in this reuse relationship pair is eliminated. The method for eliminating memory access conflict according to claim 1, wherein, in step 4.2, the modifying strategy comprises: For the Store-Load reuse pair and the Load-Load reuse pair, data is transferred from the producer to the consumer. 9. The method of eliminating fetch conflicts of claim 9, wherein the data is transferred from the producer to the consumer using an interconnect resource. The method of eliminating fetch conflicts of claim 9, wherein the data is transferred from the producer to the consumer using a registered resource. The method for eliminating access conflict according to claim 9, wherein, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes: If the clock cycle I(r) ≤ 0 between the producer and the consumer, the reuse pair is invalid. The method for eliminating access conflict according to claim 9, wherein, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes: The clock cycle I(r) between the producer and the consumer satisfies 1≥I(r)>0, and there is mutual interaction between the PE where the producer is located and the PE where the consumer is located. Resource connections are wired, and the reused consumer is transformed into a routing operation that accesses data from the producer's output register. The method for eliminating access conflict according to claim 9, wherein, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes: The clock cycle I(r)>1 between the producer and the consumer uses register resources to temporarily store data. The method for eliminating access conflicts according to claim 14, wherein, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes: pe(s)=pe(t), and the remaining space of the LRF on pe(s)

Satisfy

The reused data is stored in the LRF, and the consumer is converted into a routing operation that obtains data from the LRF, where II is the start interval of software pipeline; Among them, pe(s) and pe(t) represent the PE where the producer and consumer are located, respectively. The method for eliminating access conflict of claim 15, wherein the modification strategy comprises: In the case where LRF is not selected, and the remaining GRF space satisfies

GRF is then used to temporarily store data. The method for eliminating access conflicts of claim 16, wherein the modification strategy comprises: For accumulation reuse, the output operation sends data to the input operation according to the modification policy of the Store-Load reuse pair, and memory access operations during accumulation are converted to no-ops. The method for eliminating access conflicts according to claim 14, wherein, in the step 4.2, for the Store-Load reuse pair and the Load-Load reuse pair, the modification strategy includes: Con(r)=true, pe(s)≠pe(t), add additional routing nodes to move data through LRF; Among them, pe(s) and pe(t) represent the PEs where the producer and the consumer are located, respectively, and Con(r)=true means that there is an interconnection resource connection between pe(s) and pe(t). The method for eliminating access conflicts as claimed in claim 18, wherein the modifying strategy comprises: In the case where LRF is not selected, and the remaining GRF space satisfies

GRF is then used to temporarily store data. The method for eliminating access conflicts as claimed in claim 19, wherein the modification strategy comprises: For accumulation reuse, the output operation sends data to the input operation according to the modification policy of the Store-Load reuse pair, and memory access operations during accumulation are converted to no-ops.

Images