JP5146134B2 - Compile processing device, access pattern change processing method, and processing program - Google Patents

Description

  The present invention relates to a program compilation processing apparatus, an access pattern change processing method, and a processing program. More specifically, the present invention is executed at the time of compiling or linking a program, acquires an access pattern of a structure with memory access using the analysis result of the dynamic data structure of the program, and The present invention relates to processing for realizing processing for changing a position on an array.

  As a conventional technique related to array element assignment processing in program compilation processing and link processing, the reference order and reference count of array elements in the source program are maintained, and the array element indices are changed in accordance with the reference order, thereby providing a continuous area. There is known a method of assigning so as to be (see, for example, Patent Document 1).

  Also, run the program once in advance, create a graph of access patterns to array elements in the program, place array elements with a large number of accesses close to the base address of the activation record, or access A method of allocating a plurality of array elements that are close in time on the same cache line is known (see, for example, Patent Document 2).

  In addition, a method is known in which disk access is monitored during program execution, and an address block with a large number of accesses is made resident in a cache memory (see, for example, Patent Document 3).

The cache memory (cache) is the fastest storage device among the storage devices, and data reading can be optimized by storing frequently used data.
Japanese Patent Laid-Open No. 4-7748 JP-A-9-212369 Japanese Patent Publication No. 7-101402

  Consider a case in which a program compile processing apparatus accesses a structure having pointers to the structures (child1, child2) as in a program example described in the Fortran language shown in FIG.

  At this time, the structure (struct) is not an input program [struct] in which the structure type is defined, but another input program [main. f90]. As shown in FIG. 15B, the structure (struct) is allocated as n elements of the array (parent). Each structure (struct) as an element of the array has a pointer to a different structure as an element, and is referred to in order of definition from the top element.

  FIG. 15B is a diagram illustrating an example of an array to which a structure (struct) is assigned. A series of horizontal rows of rectangles in the array shown in FIG. 15B represents one structure. Each rectangle represents an area to which a component (structure element) of the structure is assigned.

  In this array, the areas of the structure elements child1, child2, and num1 of the n structures are secured in the order of “child1_1, child2_1, num1_1, child1_2, child2_2, num1_2,.

  Here, the program [main. f90], the region “child1_1, child1_2, child1_3,..., child1_n” of the structure element child1 is continuously accessed.

  In the arrangement of FIG. 15B, since the structure element child1 is not secured in a continuous area, the area of the structure element child1 may not be cached in the primary cache.

  In this way, when structure elements that are continuously accessed are not secured as continuous areas on the array, a state in which they are not cached at the same time may occur. Therefore, not only the use efficiency of the cache memory is lowered, but also the program execution performance is lowered.

  An object of the present invention has been made in view of such a problem. The object of the present invention is to analyze a dynamic data structure of a program and perform a memory access during program compilation processing or link processing. It is an object of the present invention to provide a program compile processing apparatus that acquires an access pattern to and that can change an arrangement for allocating elements of the structure based on the access pattern.

  Another object of the present invention is to make an access pattern change processing method executed by the program compilation processing device and a computer function as a processing device provided with processing means for processing executed by the access pattern change processing method. An access pattern change processing program is provided.

  The disclosed processing device is a compile processing device that compiles or links a program, analyzes an access operation of an instruction that accesses a memory from an analysis result of an input program, and an element of a structure related to the instruction An access pattern acquisition unit that acquires an access pattern including an arrangement on each array, the number of accesses, and an access order, and an access pattern change unit that changes the arrangement of the structure elements on the array based on the access pattern Prepare.

  The access pattern changing unit can assign the elements of the structure to be accessed to a continuous area from the top of the array based on the access order of the access patterns. As a result, there is a higher possibility that areas of structure elements that are successively accessed are cached simultaneously in the primary cache, the use efficiency of the cache memory is improved, and the execution performance of the program is also improved.

  Further, the access pattern changing unit can preferentially allocate the structure element having a high access count from the top area of the array based on the access count of the access pattern. As a result, there is a higher possibility that a frequently accessed structure element is preferentially cached in the primary cache. Therefore, the use efficiency of the cache memory is improved and the execution performance of the program is also improved.

  According to the disclosed processing device, it is highly likely that the structure elements to be accessed are cached simultaneously in the primary cache based on the access order and the number of accesses. The performance can be improved.

  FIG. 1 is a diagram showing a configuration example in the embodiment of the present invention.

  The compile processing apparatus 1 includes a compile processing unit 11, a link unit 12, an access pattern acquisition unit 13, and an access pattern change unit 14.

  The compile processing unit 11 includes a source analysis unit 111, an optimization unit 113, and a code generation unit 115, and compiles the source program to generate an object file. The source analysis unit 111, the optimization unit 113, and the code generation unit 115 execute processing by a known method, and description of each processing is omitted.

  The link means 12 performs link processing of the object file generated by the compile processing means 11 and generates an execution file.

  The access pattern acquisition unit 13 analyzes the access operation of the instruction that accesses the memory from the analysis result of the input program, and the arrangement of the structure elements (structure elements) of this instruction, the number of accesses, and the access Get access pattern including order.

  The access pattern changing unit 14 changes the arrangement of the structure elements of the access pattern based on the access pattern.

  The access pattern changing unit 14 assigns the structure elements to be accessed to a continuous area from the top of the array based on the access order or the number of accesses of the access patterns, and arranges the access pattern structure elements based on this assignment. change.

For example, a structure element to be accessed is allocated to a continuous area from the top of the array based on the access order of the access pattern, or a structure element with a high access count is allocated to the area of the array based on the access count of the access pattern. Prioritize the first area.

  Or, if there is a bias in the structure elements to be accessed in multiple functions related to the structure, only the structure elements to be accessed in the processing of each function are allocated to the continuous area from the beginning of the array. Add synchronization processing of structure information related to the function.

  Alternatively, if there is a bias in the structure element to be accessed in the loop process related to the structure, the structure element having a large number of accesses is allocated to the continuous area from the top of the array only in the loop process.

  The access pattern acquisition unit 13 and the access pattern change unit 14 can execute processing in cooperation with the compile processing unit 11 or the link unit 12.

  Hereinafter, the access pattern acquisition process and the change process in the compile processing apparatus 1 will be described in more detail. In the following example, it is assumed that the access pattern acquisition process and the change process are executed during the optimization process of the link unit 12.

[First processing example]
In the first processing example, the program shown in FIG.

  The access pattern acquisition unit 13 analyzes the dynamic data structure from the analysis result of the object file generated by the compile processing means 11, detects a memory access instruction, analyzes the access operation, and acquires the access pattern. .

  “Parent (i)% child1% num1” of the program in FIG. 15A is an instruction for performing memory access. By analyzing the access operation of this instruction, as shown in FIG. 15B, how many bytes are allocated from the top of the array to which the structure elements child1, child2, and num1 of the structure struct are allocated. Is identified. Furthermore, the number of accesses and the access order of each structure are analyzed. These pieces of analysis information are acquired as access patterns.

  Next, the access pattern changing unit 14 changes the arrangement of the structure elements so that the structure elements to be continuously accessed are allocated to the continuous areas of the array based on the access order of the access patterns.

  FIG. 2 shows an example of changing the allocation of structure elements.

  As shown in FIG. 2, first, the areas of “child1_1, child1_2,..., Child1_n” of the structure element child1 of the structure struct are sequentially allocated from the top of the array. Subsequently, the area “child2_1, child2_2,..., Child2_n” of the structure element child2 and the area “num1_1, num1_2,..., Num1_n” of num1 are continuously allocated from the next position.

  The link means 12 performs an optimization process based on the access pattern whose area allocation position has been changed.

  As a result, the structure elements that are continuously accessed are assigned to the continuous areas of the cache, and the possibility of being simultaneously cached in the primary cache increases. Therefore, the usage efficiency of the cache memory and the program execution performance can be improved.

  Further, in the first processing example, there is no possibility of causing processing overhead unlike the processing example described later.

[Second processing example]
In the second processing example, the program shown in FIG.

  Similarly to the first processing example, the access pattern acquisition unit 13 acquires an access pattern of a memory access instruction for the program shown in FIG.

  In the program shown in FIG. 3, “parent (i)% child1% num1” in the function “call sub1 ()” and “parent (i)% child2% num1” in the function “call sub2 ()” are memory accesses. It is an instruction to perform.

  In the two functions, the access pattern of the same structure struct corresponding to the instruction is different.

  In this case, the access pattern can be optimized by acquiring and partially changing the access pattern of the structure struct in each instruction. In addition, it is not necessary to analyze access operations in the entire program.

  However, since the structure is multiplexed, it is necessary to perform synchronization processing.

  The access pattern changing unit 14 checks whether there is a bias in accessing the structure elements of the structure struct in the function.

  In the instruction “parent (i)% child1% num1” in the function “call sub1 ()”, there is a bias that only the structure elements child1 and num1 are accessed and the structure element child2 is not accessed. Similarly, the instruction “parent (i)% child2% num1” in the function “call sub1 ()” is biased to access only the structure elements child2 and num1.

  Therefore, the access pattern changing unit 14 creates a structure that defines only the structure element to be accessed as an element in the function.

  FIG. 4 shows a state in which a structure struct is created based on the structure element bias in the instructions “parent (i)% child1% num1” and “parent (i)% child2% num1” of the program of FIG. FIG.

  As shown in the broken-line rectangle part p1 of the program in FIG. 4, the definition of the structure struct having only the structure elements children1 and num1 as elements is created in response to the instruction “parent (i)% child1% num1”. doing. Further, as shown in the broken-line rectangular portion p2, the definition of the structure struct is similarly created for the instruction “parent (i)% child2% num1”.

  In these functions, the access pattern changing unit 14 allocates an area on the array only for the structure element based on the access pattern of the created structure struct. Here, the processing similar to the first processing example is performed to change the allocation of the arrangement on the array.

  FIGS. 5A and 5B show examples of changing the allocation of structure elements of the array corresponding to the instruction “parent (i)% child1% num1” and the instruction “parent (i)% child2% num1”, respectively. FIG.

  In the array of FIG. 5A, since only the structure elements child1 and num1 are referred to, as the elements of the array, “child1_1, children1_2,..., Child1_n” of the structure element child1 and “ num1_1, num1_2,..., num1_n ”are allocated.

  In the array of FIG. 5B, since only the structure elements child2 and num1 are referred to, the elements of the array “child2_1, children2_2,..., Child2_n” of the structure element child2 and the structure element num1 are used. Only “num1_1, num1_2,..., Num1_n” are allocated.

  In this way, it is possible to change the arrangement of structure elements on the array by changing to an access pattern in which unnecessary structure elements that are defined but not accessed are removed. Can be stopped.

  In the second processing example, since the structure struct is multiplexed, it is necessary to synchronize information among a plurality of structures.

  The access pattern changing unit 14 holds the structure elements of the original structure struct as an array, and synchronizes these pieces of information when the value of the structure element of the created structure changes. The synchronization process is performed by one of the following three processing methods.

  FIG. 6 is a diagram illustrating an example of synchronization processing by the first synchronization method.

  As a first synchronization method, the access pattern changing unit 14 generates a master structure struct_masterA and maps the information of the master structure onto all of the multiplexed structures structA1 and structA2. Information of each structure can be synchronized via the master structure struct_masterA.

  FIG. 7 is a diagram illustrating an example of synchronization processing by the second synchronization method.

  As a second synchronization method, the access pattern changing unit 14 maps the updated information to each multiplexed structure when the structure is updated. When the information of the structure structA1 is updated, the updated information is mapped to the structures structA2, structA3, structA4, and structA5. When the information on the structure structA2 is updated, the updated information is mapped to the structures structA1, structA3, structA4, and structA5. Every update, the information of all structures is mapped and can be synchronized.

  FIG. 8 is a diagram illustrating an example of synchronization processing by the third synchronization method.

  As a third synchronization method, the access pattern changing unit 14 sets the updated structure as a master, and sequentially maps the updated information to other structures.

  When the information of the structure structA1 is updated, the structure structA1 is set as a master, and the updated information is mapped to the structure structA2. Next, since the information of the structure structA2 is updated, the structure structA2 becomes the master, and the updated information is mapped to the structure structA3. Further, the updated information of the structure structA3 is similarly mapped to the structure structA4.

  When the information is updated, the information of the structure is mapped to the next structure, and the whole can be synchronized.

[Third processing example]
In the third processing example, the program shown in FIG.

  Similarly to the first processing example, the access pattern acquisition unit 13 acquires an access pattern of a memory access instruction for the program shown in FIG.

  In the instruction “parent (i)% child1% num1” in the loop processing, only the structure elements child1 and num1 of the corresponding structure are accessed, and the structure element child2 is not accessed. Therefore, optimization can be performed by preferentially assigning structure elements to be accessed on the array.

  The access pattern changing unit 14 rearranges the structure elements in the access order from the structure access pattern of the instruction “parent (i)% child1% num1” in the loop processing in the program shown in FIG. Elements are child1, num1, and child2.

  Furthermore, the access pattern changing unit 14 creates a working array parent_tmp of the array parent as a working structure, and assigns the areas in the order of the structure elements rearranged based on the access pattern access count. Allocate to consecutive areas from the top.

  FIG. 9 is a diagram illustrating a state example in which a structure in which structure elements are rearranged and a working array parent_tmp of the array parent are added to the program of FIG.

  In the work structure parent_tmp, the area of each structure element is allocated according to the replacement order. At the end of the loop processing, the information of the working array parent_tmp is mapped to the array parent.

  FIG. 10 shows an example of changing the allocation of structure elements in the working array parent_tmp.

  As shown in FIG. 10, according to the order in which the structures are replaced, the areas of “child1_1, child1_2,..., Child1_n” of the structure element child1 are allocated to continuous areas from the top of the work array. Subsequently, the area of “num1_1, num1_2,..., Num1_n” of the structure element num1 is allocated to continuous areas. Finally, the area of “child2_1, child2_2,..., Child2_n” of the structure element child2 is assigned to a continuous area from the next position.

  In the loop processing, by assigning the array areas in the descending order of the number of access of the structure element, the possibility that the area of the structure element having the highest access count is preferentially cached in the primary cache increases. Therefore, the cache memory usage efficiency and program execution performance can be improved.

  Below, the processing flow of the access pattern acquisition part 13 and the access pattern change part 14 is demonstrated.

  FIG. 11 is a diagram illustrating a processing flow of the access pattern acquisition unit 13.

  The access pattern acquisition unit 13 detects a memory access instruction from the analysis result of the input program (object file) (step S1), and acquires type information of a structure element related to the detected instruction (step S2). ). Further, the position of each structure element on the array (arrangement indicating how many bytes ahead from the head) is acquired (step S3). The dynamic data flow is analyzed from the control of the program, and the access order and the access count of the structure elements are analyzed (step S4). An access pattern including the arrangement of structure elements, access order, number of accesses, etc. is acquired (step S5).

  FIG. 12 is a diagram illustrating a processing flow of the access pattern changing unit 14 in the first processing example.

  The access pattern changing unit 14 detects an instruction to access the memory of the input program (step S11), and determines from the access pattern whether the instruction satisfies a predetermined condition (step S12). For example, the following conditions are set.

"Condition: An array (structure) is accessed in the loop processing, and the array access is accessing only a partial area."
Only when this instruction satisfies the above conditions (YES in step S12), it is determined whether each structure of the instruction has a pointer to another structure as an element (step S13).

  Only when the structure has a pointer to another structure as an element (YES in step S13), the area of the structure element to be accessed is continuously allocated from the top of the array based on the access order of the access pattern (Step S14).

  FIG. 13 is a diagram illustrating a processing flow of the access pattern changing unit 14 in the second processing example.

  The processing in steps S21 to S22 is the same as the processing in steps S11 to 12 in FIG.

  The access pattern changing unit 14 determines whether there is a bias in the structure element to be accessed in the function only in the case of the above condition (YES in step S22) (step S23). Only when it is determined that the structure element to be accessed is biased in the function (YES in step S33), a structure having only the structure element used in the function as an element is placed at the beginning of the function. Create (step S24).

  Further, based on the access order of the access pattern, the area of the structure element to be accessed is continuously allocated from the top of the array (step S25).

  Furthermore, a synchronization process of the multiplexed structure information is added (step S26).

  FIG. 14 is a diagram illustrating a processing flow of the access pattern changing unit 14 in the third processing example.

  The processing in steps S31 to S32 is the same as the processing in steps S11 to 12 in FIG.

  The access pattern changing unit 14 determines whether or not there is a bias in the structure element to be accessed in the loop processing only in the case of the above condition (YES in step S32) (step S33). Only when it is determined that the structure element to be accessed is biased in the loop process (YES in step S33), a working array (structure) corresponding to the original array is created before the loop process (step S33). S34), on the basis of the access count of the access pattern, the area of the structure element having a high access count is continuously allocated from the head of the work array (step S35). After that, at the end of the loop process, the working array information is mapped to the original array (step S36).

  Although the present invention has been described above with reference to the embodiments, it is obvious that the present invention can be variously modified within the scope of the gist thereof.

  Further, the compiler processing device disclosed in this embodiment can be implemented as a program that is read and executed by a computer. This program can be stored in an appropriate recording medium such as a portable medium memory, semiconductor memory, or hard disk, which can be read by a computer, provided by being recorded on these recording media, or via a communication interface. It can be provided by transmission / reception using various communication networks.

It is a figure which shows the structural example in embodiment of this invention. It is a figure which shows the example of a change of allocation of the structure element in a 1st process example. It is a figure which shows the example of a program of the process target in a 2nd process example. FIG. 4 is a diagram illustrating an example of a state in which a structure definition is created corresponding to each instruction and the structures are multiplexed in the program of FIG. 3. It is a figure which shows the example of a change of arrangement | positioning corresponding to the part p1 and the part p2 in a 2nd process example. It is a figure which shows the example of the synchronization process by a 1st synchronization method. It is a figure which shows the example of the synchronization process by a 2nd synchronization method. It is a figure which shows the example of the synchronization process by a 3rd synchronization method. FIG. 10 is a diagram illustrating a state example in which a structure in which structure elements are rearranged and a working array are created in a loop process in the third processing example. It is a figure which shows the example of a change of allocation of the arrangement | sequence for work in the 3rd process example. It is a figure which shows the processing flow of an access pattern acquisition part. It is a figure which shows the processing flow of the access pattern change part in a 1st process example. It is a figure which shows the processing flow of the access pattern change part in a 2nd process example. It is a figure which shows the processing flow of the access pattern change part in a 3rd process example. It is a figure which shows the example of allocation of the example of the program which is input, and the structure element array of the instruction which performs the memory access in a program.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Compile processing apparatus 11 Compile process means 12 Link means 13 Access pattern acquisition part 14 Access pattern change part 111 Source analysis part 113 Optimization part 115 Code generation part

Claims (8)

In a compile processing device that performs program compile processing or link processing or these processing,
An access pattern acquisition unit that analyzes the access operation of the instruction that accesses the memory from the analysis result of the input program and acquires the access pattern including the arrangement of the elements of the structure related to the instruction, the number of accesses, and the access order When,
A compile processing apparatus comprising: an access pattern changing unit that changes an arrangement of elements of the structure on an array based on the access pattern. The compiling apparatus according to claim 1, wherein the access pattern changing unit assigns a structure element to be accessed to a continuous area from the top of the array based on an access order of the access patterns. 3. The access pattern change unit, according to the access count of the access pattern, assigns a structure element having a high access count preferentially from the top area of the array. The compile processing device described in 1. The access pattern changing unit, when there is a bias in the elements of the structure to be accessed in a plurality of functions related to the structure, only the elements of the structure to be accessed in the processing of each of the functions are stored in the array. The compile processing device according to claim 1, wherein the compile processing device is assigned to a continuous area from the top and a synchronization process of information on a structure related to the function is added. The access pattern changing unit, when there is a bias in a structure element to be accessed in a loop process associated with the structure, only accesses the structure element that has been accessed many times within the loop process. The compile processing device according to claim 1, wherein the compile processing device is assigned to a continuous area from the top. 6. The access pattern acquisition unit and the access pattern change unit are activated and executed while one of the compile processing and the link processing is being executed. The compile processing device according to any one of the above. An access pattern change processing method executed by a computer during program compilation processing or link processing or these processing.
Access pattern acquisition processing that analyzes the access operation of the instruction that accesses the memory from the analysis result of the input program, and acquires the access pattern including the arrangement of the elements of the structure related to the instruction, the number of accesses, and the access order Process,
An access pattern change processing method, comprising: an access pattern change process for changing an arrangement of elements of the structure on the array based on the access pattern. A computer that compiles or links programs or performs these processes,
An access pattern acquisition unit that analyzes the access operation of the instruction that accesses the memory from the analysis result of the input program, and acquires the access pattern including the arrangement of the elements of the structure related to the instruction, the number of accesses, and the access order When,
An access pattern change processing program comprising: an access pattern change unit that changes an arrangement of elements of the structure on an array based on the access pattern.

Images