JP2021093012A - Compilation program and information processing device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To optimize loop processing by an appropriate method. SOLUTION: An information processing apparatus 10 describes a first SIMD in which a loop process of repeating a process of executing operations in parallel by a SIMD instruction for one or more elements enabled by a mask based on a loop instruction sequence 1 is described. Generate instruction sequence 2. Next, the information processing device 10 stores a plurality of discontinuous elements in the array in a continuous area in the SIMD register, and executes operations in parallel with the SIMD instructions for the plurality of elements in the SIMD register. The second SIMD instruction sequence 3 in which the loop processing that repeats the above is described is generated. Then, the information processing apparatus 10 selects an instruction sequence to be included in the compiled program based on the first SIMD instruction sequence 2, the second SIMD instruction sequence 3, and the processing time. [Selection diagram] Fig. 1

Description

The present invention relates to a compilation program and an information processing device.

A program to be executed on a computer is generated by converting a source program written in a high-level language into an executable code string using a compiler. The computer that runs the compiler produces a program that is optimized for the microarchitecture of the processor that executes the program to be generated. The microarchitecture defines the logical structure of a processor circuit (structures such as registers, buses, SIMD (Single Instruction Multiple Data), and pipelines).

SIMD is an instruction execution method that realizes parallel processing by applying one instruction to a plurality of data at the same time. An instruction that instructs the execution of parallel processing by SIMD is called a SIMD instruction. Replacing the loop processing with processing that parallelizes using the SIMD instruction is called SIMD conversion.

When compiling a source program, a computer can significantly improve the processing efficiency of the program by optimizing the loop processing. For example, in the loop process, there is a process of performing the same operation for each of a plurality of elements (for example, data having a predetermined length) stored in a discontinuous area on the memory. As a method of optimizing such loop processing, there are a method of rewriting to an instruction sequence using a masked SIMD instruction and a method of rewriting to an instruction sequence using a gather instruction and a scatter instruction. Hereinafter, both the gather instruction and the scatter instruction may be referred to as a gather / scatter instruction.

The masked SIMD instruction indicates that the operation is executed in parallel only for some of the elements specified by the mask data among the plurality of elements stored in the SIMD instruction register (SIMD register). It is an instruction. By using the masked SIMD instruction, parallel processing by SIMD is possible even for a plurality of elements stored in a discontinuous area.

The gather instruction is an instruction for storing a plurality of elements stored in a discontinuous area on the memory in one SIMD register. The scatter instruction is an instruction to write a plurality of elements stored in one register to a discontinuous area in the memory. By the gather instruction, multiple elements are stored in the SIMD register from the discontinuous area in the memory, the same operation is executed in parallel by the SIMD instruction in those elements, and the element of the operation result is discontinuous in the memory by the scatter instruction. Can be exported to a continuous area. This makes it possible to improve the efficiency of loop processing.

As a technique related to a compiler, for example, a method of automating the generation of parallel SIMD native source code is disclosed. Further, a code generation method capable of efficiently executing the iterative processing of the same operation is also disclosed. Further, a compilation method for reducing the number of instructions of the generated object program and improving the execution performance is also disclosed.

Japanese Unexamined Patent Publication No. 2010-186468 JP-A-2018-124877 JP-A-2018-49461

In the loop processing using the masked SIMD instruction, the same operation can be executed in parallel for some of the unmasked elements stored in the SIMD register. On the other hand, in the loop processing using the gather / scatter instruction, the same operation can be executed in parallel for all the plurality of elements stored in the SIMD register. Therefore, in many cases, a significant performance improvement can be expected in the loop processing using the instruction sequence using the gather / scatter instruction rather than the loop processing using the instruction sequence using the masked SIMD instruction.

However, in general, the execution of the gather / scatter instruction takes longer than the execution of the load / store instruction to the SIMD register when using the masked SIMD instruction. Therefore, depending on the execution speed of the gather / scatter instruction, the loop processing using the masked SIMD instruction may be faster than the loop processing using the instruction sequence using the gather / scatter instruction.

In the past, it has not been properly determined whether loop processing using a masked SIMD instruction or loop processing using a gather / scatter instruction is more efficient, and loop processing is optimal with an appropriate method. It may not have been converted.

On the one hand, this case aims to enable the loop processing to be optimized in an appropriate manner.

One idea is to provide a compilation program that causes the computer to perform the following operations:
The computer extracts from the program to be compiled a loop instruction sequence that directs operations on some elements in the array. Next, the computer uses a mask that enables only the element to be calculated out of the multiple elements in the array based on the loop instruction sequence, and in parallel with the SIMD instruction for one or more elements enabled by the mask. A first SIMD instruction sequence is generated in which a loop process for repeating a process for executing an operation is described. In addition, the computer stores a plurality of discontinuous elements in the array in a continuous area in the SIMD register based on the loop instruction sequence, and performs operations in parallel with the SIMD instruction for the plurality of elements in the SIMD register. A second SIMD instruction sequence is generated in which a loop process that repeats the process to be executed is described. Further, the computer calculates the processing time of the first SIMD instruction sequence and the processing time of the second SIMD instruction sequence based on the execution time information in which the numerical value indicating the time required for executing each of the plurality of instructions is set. Then, the computer determines the instruction sequence to be included in the compiled program from the first SIMD instruction sequence and the second SIMD instruction sequence based on the processing time of the first SIMD instruction sequence and the processing time of the second SIMD instruction sequence. select.

According to one aspect, the loop processing can be optimized by an appropriate method.

It is a figure which shows an example of the compilation method by the information processing apparatus which concerns on 1st Embodiment. It is a figure which shows one configuration example of the hardware of the computer used for executing compilation. It is a block diagram which shows the function of a computer. It is a figure which shows an example of the instruction scheduling table. It is a figure which shows the example of the instruction sequence which describes the loop processing. It is a figure which shows the content of the loop processing which uses the masked SIMD instruction. It is a figure which shows the content of the loop processing which uses the gather / scatter instruction. It is a figure which shows the determination example of the loop instruction sequence to be adopted. It is a flowchart which shows an example of the procedure of a loop optimization process. It is a flowchart which shows an example of the procedure of a loop type determination process. It is a flowchart which shows an example of the procedure of the equivalent loop generation processing. It is a figure which shows the conversion example from the original loop of "TYPE1" to the equivalent loop of "TYPE2". It is a figure which shows the conversion example from the original loop of "TYPE2" to the equivalent loop of "TYPE1". It is a flowchart which shows an example of the procedure of instruction scheduling processing. It is a flowchart which shows an example of the procedure of a loop cost calculation process. It is a figure which shows the example of the fixed value of a mask in the SIMD instruction with a mask. It is a figure which shows an example of the loop instruction sequence in the case of an even number determination. It is a figure which shows an example of the loop instruction sequence when the stride width is "3". It is a figure which shows an example of the loop instruction sequence when the stride width is "4".

Hereinafter, the present embodiment will be described with reference to the drawings. It should be noted that each embodiment can be implemented by combining a plurality of embodiments within a consistent range.
[First Embodiment]
FIG. 1 is a diagram showing an example of a compilation method by the information processing apparatus according to the first embodiment. The information processing apparatus 10 can implement the compilation method shown in FIG. 1 by executing, for example, a compilation program.

The information processing device 10 has a storage unit 11 and a processing unit 12. The storage unit 11 is, for example, a memory or a storage device included in the information processing device 10. The processing unit 12 is, for example, a processor or an arithmetic circuit included in the information processing device 10.

The storage unit 11 stores, for example, the program 11a to be compiled and the execution time information 11b. The program 11a is, for example, a source file in which instructions are described in a high-level language. The execution time information 11b is set with a numerical value representing the time required to execute each of the plurality of instructions. The numerical value representing the time required for execution is, for example, the number of clock cycles of the processor required to execute each of the plurality of instructions. In this case, the processing time of the loop processing is represented by the time of one cycle of the clock of the processor as a unit time.

The processing unit 12 executes the following loop optimization processing in the processing of compiling the program 11a.
The processing unit 12 extracts from the program 11a a loop instruction sequence 1 that instructs an operation on some elements in the array (step S1). Here, the loop rotation speed (number of repetitions) of the loop processing shown in the loop instruction sequence 1 is set to n (n is an integer of 1 or more).

Next, the processing unit 12 generates the first SIMD instruction sequence 2 based on the loop instruction sequence 1 (step S2). The first SIMD instruction sequence 2 uses a mask that enables only the element to be calculated among a plurality of elements in the array, and causes one or more elements enabled by the mask to execute operations in parallel by the SIMD instruction. This is an instruction sequence in which loop processing that repeats processing is described. For example, four instructions "instruction # 11" to "instruction # 14" are included in the loop processing shown in the first SIMD instruction sequence 2. "Instruction # 11" is an instruction to generate a mask. "Instruction # 12" is an instruction to load an element with a mask. "Instruction # 13" is an instruction that performs a SIMD operation with a mask. "Instruction # 14" is an instruction to store the operation result with a mask.

Next, the processing unit 12 generates the second SIMD instruction sequence 3 based on the loop instruction sequence 1 (step S3). The second SIMD instruction sequence 3 stores a plurality of discontinuous elements in the array in a continuous area in the SIMD register, and executes operations in parallel for the plurality of elements in the SIMD register by the SIMD instruction. This is an instruction sequence in which loop processing that repeats is described. For example, four instructions "instruction # 21" to "instruction # 24" are included in the loop processing shown in the second SIMD instruction sequence 3. "Instruction # 21" is an instruction for creating a list of index values to be processed. "Instruction # 22" is a gather instruction that loads discontinuous elements in the array into the continuous storage area in the SIMD register. "Instruction # 23" is an instruction that performs a SIMD operation. "Instruction # 24" is a scatter instruction that stores the operation result as the value of the discontinuous element of the array.

Next, the processing unit 12 sets the processing time of the first SIMD instruction sequence 2 and the processing time of the second SIMD instruction sequence 3 based on the execution time information 11b in which the number of cycles required for executing each of the plurality of instructions is set. Calculate (step S4). For example, the processing unit 12 refers to the execution time information 11b and recognizes the number of cycles required to execute the instructions included in the first SIMD instruction sequence 2 and the second SIMD instruction sequence 3. Then, the processing unit 12 multiplies the number of cycles required to execute the processing per rotation of the loop processing of the first SIMD instruction sequence 2 by the loop rotation number of the first SIMD instruction sequence 2 to obtain the value obtained by the first SIMD instruction sequence 2 The processing time of. Similarly, the processing unit 12 multiplies the number of cycles required to execute the processing per rotation of the loop processing of the second SIMD instruction sequence 3 by the loop rotation number of the second SIMD instruction sequence 3 to obtain the second SIMD instruction sequence. The processing time is 3.

The processing unit 12 uses, for example, the loop rotation speed of the first SIMD instruction sequence 2 as a value obtained by dividing the rotation speed of the loop processing in the loop instruction sequence 1 by the number of elements that can be stored in the SIMD register. Further, the processing unit 12 divides the number of rotations of the loop processing in the loop instruction sequence 1 by the number of elements that can be stored in the SIMD register and the increment value for each rotation of the loop processing of the index value indicating the element to be calculated. , The loop rotation speed of the second SIMD instruction sequence 3.

Then, the processing unit 12 is a program after compilation of the first SIMD instruction sequence 2 and the second SIMD instruction sequence 3 based on the processing time of the first SIMD instruction sequence 2 and the processing time of the second SIMD instruction sequence 3. The instruction sequence to be included in is selected (step S5). For example, the processing unit 12 selects the instruction sequence having the shorter processing time as the instruction sequence to be included in the compiled program.

In the example of FIG. 1, in the first SIMD instruction sequence 2, four instructions "instruction # 11" to "instruction # 14" are included in the processing of one rotation of the loop processing. The number of cycles required to execute "instruction # 11" is "4", the number of cycles required to execute "instruction # 12" is "10", and the number of cycles required to execute "instruction # 13" is "9". , And the number of cycles required to execute "instruction # 14" is "10". In the target microarchitecture, when the number of elements that can be stored in the SIMD register is "8", the loop rotation speed when using the masked SIMD instruction is "n / 8". Then, the time required to execute the first SIMD instruction sequence 2 becomes "4.1n (cycles)".

Further, in the second SIMD instruction sequence 3, four instructions "instruction # 21" to "instruction # 24" are included in the processing of one rotation of the loop processing. The number of cycles required to execute "instruction # 21" is "4", the number of cycles required to execute "instruction # 22" is "20", and the number of cycles required to execute "instruction # 23" is "9". , And the number of cycles required to execute "instruction # 24" is "40". Here, it is assumed that the number of elements that can be stored in the SIMD register is "8", and the increment value of the loop control variable in the loop instruction sequence 1 for each loop rotation is "2". In this case, the loop rotation speed when using the gather / scatter instruction is "n / 16". Then, the time required to execute the second SIMD instruction sequence 3 is "4.6n (cycles)".

In this case, the time required for execution of the first SIMD instruction sequence 2 is shorter than that of the second SIMD instruction sequence 3. Therefore, the processing unit 12 selects the first SIMD instruction sequence 2 as the instruction sequence to be included in the compiled program. That is, a loop instruction sequence that uses the masked SIMD instruction is selected.

According to such an information processing apparatus 10, when compiling the program 11a, it is possible to optimize the loop instruction sequence 1 capable of parallelizing operations using SIMD instructions by a method with higher processing efficiency. ..

The storage unit 11 can store the execution time information 11b corresponding to each of the plurality of microarchitectures. In this case, when selecting the instruction sequence, the processing unit 12 refers to the execution time information corresponding to the microarchitecture specified at compile time, and processes the first SIMD instruction sequence 2 and the second SIMD instruction sequence 3. Calculate the time. This makes it possible to calculate an appropriate processing time according to the microarchitecture.

When generating the first SIMD instruction sequence 2, the processing unit 12 can generate the first SIMD instruction sequence 2 that executes the mask generation process before the start of the loop process. As a result, the processing time required to execute the first SIMD instruction sequence 2 is further shortened.

Further, the processing unit 12 can suppress the execution of a part of the processing when it is known that the processing time of the second SIMD instruction sequence 3 is shorter without comparing the processing times. For example, the processing unit 12 determines whether or not the increment value of the loop control variable for each loop processing of the loop instruction sequence 1 exceeds a predetermined threshold value. When the incremental value exceeds the threshold value, the processing unit 12 suppresses the execution of the generation processing of the first SIMD instruction sequence 2 and the processing time calculation processing. Then, the processing unit 12 selects the second SIMD instruction sequence 3 as the instruction sequence to be included in the compiled program without comparing the processing time of the first SIMD instruction sequence 2 with the processing time of the second SIMD instruction sequence 3. To do.

When the increment value of the loop control variable is sufficiently large in this way, the loop rotation speed in the second SIMD instruction sequence 3 becomes much smaller than that in the first SIMD instruction sequence 2. Therefore, the processing time of the second SIMD instruction sequence 3 is shorter. In such a case, the efficiency of the compilation process can be improved by selecting the second SIMD instruction sequence 3 as the instruction sequence to be included in the compiled program without performing the process such as generating the first SIMD instruction sequence 2. Can be done.

[Second Embodiment]
Next, the second embodiment will be described. The second embodiment is a compilation technique that optimizes high-level languages such as C, C ++, and Fortran to faster objects (execution modules, object files, assembly language program files) for the target machine. is there.

FIG. 2 is a diagram showing a configuration example of computer hardware used for executing compilation. In the computer 100, the entire device is controlled by the processor 101. A memory 102 and a plurality of peripheral devices are connected to the processor 101 via a bus 109. The processor 101 may be a multiprocessor. The processor 101 is, for example, a CPU (Central Processing Unit), an MPU (Micro Processing Unit), or a DSP (Digital Signal Processor). At least a part of the functions realized by the processor 101 executing a program may be realized by an electronic circuit such as an ASIC (Application Specific Integrated Circuit) or a PLD (Programmable Logic Device).

Further, the processor 101 has a SIMD register group 101a. The SIMD register group 101a is a set of registers having a data width sufficient to store SIMD extension instructions. Since the processor 101 has the SIMD register group 101a, when the computer 100 performs compilation with the processor 101 as the target machine, the loop processing is optimized for parallel processing using the SIMD registers. Can be done.

The memory 102 is used as the main storage device of the computer 100. At least a part of an OS (Operating System) program or an application program to be executed by the processor 101 is temporarily stored in the memory 102. Further, various data used for processing by the processor 101 are stored in the memory 102. As the memory 102, for example, a volatile semiconductor storage device such as a RAM (Random Access Memory) is used.

Peripheral devices connected to the bus 109 include a storage device 103, a graphic processing device 104, an input interface 105, an optical drive device 106, a device connection interface 107, and a network interface 108.

The storage device 103 electrically or magnetically writes and reads data to and from the built-in recording medium. The storage device 103 is used as an auxiliary storage device for a computer. The storage device 103 stores an OS program, an application program, and various data. As the storage device 103, for example, an HDD (Hard Disk Drive) or an SSD (Solid State Drive) can be used.

A monitor 21 is connected to the graphic processing device 104. The graphic processing device 104 causes the image to be displayed on the screen of the monitor 21 in accordance with the instruction from the processor 101. The monitor 21 includes a display device using an organic EL (Electro Luminescence), a liquid crystal display device, and the like.

A keyboard 22 and a mouse 23 are connected to the input interface 105. The input interface 105 transmits signals sent from the keyboard 22 and the mouse 23 to the processor 101. The mouse 23 is an example of a pointing device, and other pointing devices can also be used. Other pointing devices include touch panels, tablets, touchpads, trackballs and the like.

The optical drive device 106 reads the data recorded on the optical disk 24 by using a laser beam or the like. The optical disk 24 is a portable recording medium on which data is recorded so that it can be read by reflection of light. The optical disk 24 includes a DVD (Digital Versatile Disc), a DVD-RAM, a CD-ROM (Compact Disc Read Only Memory), a CD-R (Recordable) / RW (ReWritable), and the like.

The device connection interface 107 is a communication interface for connecting peripheral devices to the computer 100. For example, a memory device 25 or a memory reader / writer 26 can be connected to the device connection interface 107. The memory device 25 is a recording medium equipped with a communication function with the device connection interface 107. The memory reader / writer 26 is a device that writes data to or reads data from the memory card 27. The memory card 27 is a card-type recording medium.

The network interface 108 is connected to the network 20. The network interface 108 transmits / receives data to / from another computer or communication device via the network 20.

The computer 100 can realize the processing function of the second embodiment by the hardware configuration as described above. The information processing device 10 shown in the first embodiment can also be realized by the same hardware as the computer 100 shown in FIG.

The computer 100 realizes the processing function of the second embodiment, for example, by executing a program recorded on a computer-readable recording medium. A program that describes the processing content to be executed by the computer 100 can be recorded on various recording media. For example, a program to be executed by the computer 100 can be stored in the storage device 103. The processor 101 loads at least a part of the program in the storage device 103 into the memory 102 and executes the program. Further, the program to be executed by the computer 100 can be recorded on a portable recording medium such as an optical disk 24, a memory device 25, and a memory card 27. The program stored in the portable recording medium can be executed after being installed in the storage device 103 under the control of the processor 101, for example. The processor 101 can also read and execute the program directly from the portable recording medium.

Next, the functions used by the computer 100 to compile the program will be described.
FIG. 3 is a block diagram showing the functions of the computer. The computer 100 has a storage unit 110 and a compiler 120.

The storage unit 110 stores the data used for compilation and the data generated by compilation. For example, the storage unit 110 stores a plurality of instruction scheduling tables 111a, 111b, ..., Source files 112, object files 113, execution program modules 114, assembly program files 115, and the like. The storage unit 110 is realized by using, for example, at least a part of the storage area of the memory 102 or the storage device 103.

The plurality of instruction scheduling tables 111a, 111b, ... Correspond to different microarchitectures. The instruction scheduling tables 111a, 111b, ... Are data tables in which information such as instruction latency that can be used in the corresponding microarchitecture is registered. The instruction scheduling tables 111a, 111b, ... Are examples of the execution time information 11b shown in the first embodiment.

The source file 112 is a file containing a program written in a high-level language such as C, C ++, or Fortran. The object file 113 is a program file generated by the compiler 120 and in which instructions are described in machine language. The execution program module 114 is a program file generated by the compiler 120 and in which machine language instructions are described so that it can be directly executed. The assembly program file 115 is a program file generated by the compiler 120 and in which instructions are described in assembly language.

The compiler 120 converts the source code described in the source file 112 into machine language and generates the object file 113. The compiler 120 has, for example, an analysis unit 121, an optimization unit 122, and a code output unit 123.

The analysis unit 121 analyzes the source code described in the source file 112. The analysis unit 121 converts, for example, a source code written in a high-level language into an intermediate language.
The optimization unit 122 optimizes the instruction sequence indicated in the intermediate language. For example, the optimization unit 122 changes the loop processing to parallel processing using the SIMD instruction. The optimizing unit 122 has a loop optimizing unit 122a and a SIMD optimizing unit 122b in order to optimize the loop processing.

The loop optimization unit 122a optimizes the loop processing. For example, the loop optimizing unit 122a describes an instruction sequence that describes loop processing that can be optimized using a masked SIMD instruction or an optimization using a gather / scatter instruction from an instruction sequence converted into an intermediate language. Extract (loop instruction sequence). Next, the loop optimization unit 122a determines the execution time of the loop processing when the extracted loop instruction sequence is optimized by using the masked SIMD instruction, and the loop processing when the extracted loop instruction sequence is optimized by using the gather / scatter instruction. Compare with the execution time of. Then, the loop optimizing unit 122a optimizes the loop instruction sequence so that the loop processing is executed by the method of shortening the execution time.

The SIMD conversion unit 122b converts a loop instruction sequence capable of parallel processing by the SIMD instruction into processing using the SIMD instruction. The SIMD conversion unit 122b executes SIMD conversion of the loop processing after the loop optimization processing by the loop optimization unit 122a.

The code output unit 123 converts the optimized intermediate language instruction into the machine language code, and outputs the object file 113 described in the machine language. For example, the code output unit 123 stores the object file 113 in the storage unit 110.

The line connecting each element (analysis unit 121, optimization unit 122, loop optimization unit 122a, SIMD conversion unit 122b, code output unit 123) shown in FIG. 3 indicates a part of the communication path. Yes, it is possible to set a communication path other than the communication path shown in the figure. Further, the function of each element shown in FIG. 3 can be realized, for example, by causing the computer 100 to execute a program module corresponding to the element.

Next, the instruction scheduling tables 111a, 111b, ... Stored in the storage unit 110 will be described in detail.
FIG. 4 is a diagram showing an example of an instruction scheduling table. The instruction scheduling table 111a is provided with columns for intermediate language instructions, latency information, pipeline information, and non-pipeline instruction flags.

Instructions used as an intermediate language (intermediate language instructions) are set in the intermediate language instruction column. For example, in the intermediate language instruction column, all intermediate language instructions that can be used at compile time are set.

In the latency information field, the latency (waiting time from the start of instruction execution to the end of execution) when executing the corresponding intermediate language instruction is set. Latency, for example, is represented by the number of cycles of the processor's operating clock. The latency of an intermediate language instruction may change depending on the arguments used when executing the intermediate language instruction and other conditions. For example, in the case of the gather instruction, the wider the distance between the elements to be acquired in the memory, the more the data of each element is read from the positions in the memory, and the latency becomes longer. Therefore, for example, the standard latency (representative value such as average and mode) of the intermediate language instruction is set in the latency information column.

In the pipeline information column, the names of one or more arithmetic units used to execute the corresponding intermediate language instructions are set. In the pipeline information column, when the names of multiple arithmetic units are connected by ",", it is indicated that both arithmetic units on both sides of "," are used. For example, when the pipeline information of the intermediate language instruction is "AGP, PRP", the arithmetic unit "AGP" (address calculation arithmetic unit) and the arithmetic unit "PRP" (predicate arithmetic unit) are used to execute the intermediate language instruction. And both are used. The predicate arithmetic unit is a control circuit for whether or not to output each instruction at the time of execution. In the pipeline information column, when the names of a plurality of arithmetic units are connected by "|", it is indicated that one of the arithmetic units on both sides of "|" is used. For example, when the pipeline information of an intermediate language instruction is "FPA | FPB", one of the arithmetic units "FPA" and "FPB" (both are floating-point arithmetic arithmetic units) is used to execute the intermediate language instruction. Will be done.

In the non-pipeline instruction flag field, a flag indicating whether or not the corresponding intermediate language instruction is a non-pipeline instruction is set. A non-pipeline instruction is an instruction that occupies a specific arithmetic unit by the amount of latency. When the intermediate language instruction is a non-pipeline instruction, a flag indicating that it is a non-pipeline instruction (indicated by a circle in FIG. 4) is set in the non-pipeline instruction flag field.

Information similar to that of the instruction scheduling table 111a is also set in the instruction scheduling tables 111b, ... Other than the instruction scheduling table 111a. Which instruction scheduling table is used at compile time is determined by the microarchitecture specified at compile time. That is, the target microarchitecture is specified in the compile execution instruction. The loop optimizing unit 122a refers to the instruction scheduling table corresponding to the specified microarchitecture and executes the loop optimizing process.

Next, the optimization method of the loop processing by the compiler 120 will be specifically described. As an optimization method for loop processing, there are an optimization using a masked SIMD instruction and an optimization using a gather / scatter instruction.

FIG. 5 is a diagram showing an example of an instruction sequence describing loop processing. FIG. 5 shows an example of a process of adding an element having the same index value in the array c to an element having an odd index value in the array b and storing the addition result as an element having the same index value in the array a. .. Such processing can be both optimization of loop processing using the masked SIMD instruction and optimization of loop processing using the gather / scatter instruction.

When the loop processing is executed by using the masked SIMD instruction, the loop instruction sequence 41 shown on the left side of the lower part of FIG. 5 is generated. When the loop processing is executed by using the gather / scatter instruction, the loop instruction sequence 42 shown on the lower right side of FIG. 5 is generated.

It is assumed that each of the array b and the array c has n elements. In this case, the loop instruction sequence 41 when using the masked SIMD instruction is described so as to loop (do i = 1, n) until i = n while counting up the loop control variable i by 1. Become. In the loop instruction sequence 41, when the index value is odd (the remainder when the value of the loop control variable i is divided by 2 is 1) by the instruction "if (mod (i, 2) == 1) the". , It is described that the operation "a (i) = b (i) + c (i)" is performed. Conditional branching using this remainder is realized by the mask given to the SIMD instruction.

Further, the loop instruction sequence 42 when the gather / scatter instruction is used is described so as to loop (do i = 1, n, 2) until i = n while counting up the loop control variable i by 2. .. In the case of processing for the elements of the index value at regular intervals on the array, simultaneous acquisition of a plurality of elements existing in the discrete areas on the array is realized by the gather instruction. In addition, the calculation result is stored in the discrete area on the array by the scatter instruction. A loop such as the loop instruction sequence 42 in which the value of the loop control variable i indicating the element to be acquired is increased by 2 or more instead of 1 is sometimes called a stride loop.

FIG. 6 is a diagram showing the contents of loop processing using the masked SIMD instruction. In the example of FIG. 6, it is assumed that the processor of the target machine in compilation has SIMD registers 51, 52, 53 with a width of 512 bits. Eight double-precision floating-point (8-byte) elements can be stored in each of these SIMD registers 51, 52, and 53 at the same time.

In the loop instruction sequence 41, only the elements having an odd index value are calculated. Therefore, when reading the elements of the array b, a load (load with mask) is performed using a mask 54 in which the corresponding element is “T” (true) and the other elements are “F” (false). In this load, the elements in the array having the same width as the SIMD register 51 are loaded, but only the elements having the index value set as "T" in the mask 54 are loaded into the SIMD register 51. In the example of FIG. 6, a load instruction is given to the eight elements of the index values “1” to “8”, and only the four elements of “T” are stored in the SIMD register 51 with the mask 54. Similarly, when reading the elements of the array c, a load with mask is performed, and only the four elements of "T" in the mask 55 are stored in the SIMD register 52.

Then, elements having the same index value (limited to an odd index value) of the SIMD registers 51 and 52 are added, and the addition result is stored in the SIMD register 53. The value stored in the SIMD register 53 is stored in the array a by a store with mask using a mask 56 in which an element having an odd index value is "T" and another element is "F". As a result, the operation result is stored in the array a only in the elements having odd index values. The load instruction and the store instruction when using the masked SIMD instruction are collectively referred to as a load / store instruction below.

In this way, when the loop instruction sequence 41 is optimized by SIMD, eight consecutive elements in the array are targeted for processing in one rotation of the loop, and the elements to be calculated are executed in parallel. It becomes a processing procedure to be performed. Therefore, the rotation speed of the loop is 1/8 of n. That is, what was loop rotation speed = n before SIM conversion becomes loop rotation speed = n / 8 after SIMD conversion.

FIG. 7 is a diagram showing the contents of loop processing using the gather / scatter instruction. In the loop instruction sequence 42, only the elements having an odd index value are calculated. Therefore, when reading the elements of the array b, eight elements of the discontinuous region in the array b are simultaneously read by the gather instruction and stored in the SIMD register 51. Similarly, when reading the elements of the array c, eight elements of the discontinuous region in the array c are simultaneously read by the gather instruction and stored in the SIMD register 52.

Then, elements having the same index value in the SIMD registers 51 and 52 are added, and the addition result is stored in the SIMD register 53. The value stored in the SIMD register 53 is stored in a discontinuous area in the array a by the scatter instruction.

If the gather / scatter instruction can be used in this way, all the areas of eight elements in double-precision floating point in the SIMD registers 51 to 53 having a width of 512 bits can be effectively used. As a result, in the loop instruction sequence 42 before SIMD conversion, the loop rotation speed = n / 2, but after SIMD conversion, the loop rotation speed = n / 2/8.

Comparing FIG. 6 and FIG. 7, it can be seen that the loop processing using the gather / scatter instruction requires only half the loop rotation speed. Here, if the time required to load and store the element is the same between the case of using the gather / scatter instruction and the load / store instruction in the masked SIMD, the loop processing using the gather / scatter instruction is adopted. This can be expected to significantly improve performance.

However, since the gather / scatter instruction accesses a discontinuous area, the time required for the processing is generally longer than the time required for the load / store instruction in the masked SIMD instruction. Therefore, depending on the time required to process the gather / scatter instruction, it may be faster to use the masked SIMD instruction that accesses the continuous area even if the rotation speed of the loop processing is doubled. ..

Whether to use the gather / scatter instruction or the masked SIMD instruction cannot be determined only by the latency information of each instruction of the microarchitecture. For example, if the time required for the calculation for one rotation of the loop (1 iteration) is long, the value of using the gather / scatter instruction increases even in the microarccha where the gather / scatter instruction is slow. On the other hand, when the time required for the calculation for one rotation of the loop is short, the speed of the gather / scatter instruction directly affects the performance of the loop, so that the value of using the gather / scatter instruction decreases. In order to improve the execution performance in this way, which loop instruction sequence should be used faster when using the loop instruction sequence of each method for the loop efficiency method that has a choice. It is important to make an appropriate judgment.

Therefore, in the compiler 120 of the computer 100, the loop optimizing unit 122a included in the optimizing unit 122 determines which loop instruction sequence to use by the following calculation.

[Procedure 1] The loop optimizing unit 122a multiplies the number of cycles for one iteration of the loop instruction sequence including the IF statement (using a masked SIMD instruction) by the number of loop rotations (for example, n / 8), and costs the loop. Is calculated.

[Procedure 2] The loop optimization unit 122a calculates the loop cost by multiplying the number of cycles for one iteration of the stride loop (using gather / scatter) by the loop rotation speed (for example, n / 16).

[Procedure 3] The loop optimizing unit 122a adopts a loop instruction sequence that uses the gather / scatter instruction or uses a masked SIMD instruction by comparing the cost calculated in procedure 1 with the cost calculated in step 2. Determines whether to adopt the loop instruction sequence.

Hereinafter, an example of determining the loop instruction sequence to be adopted will be described.
FIG. 8 is a diagram showing a determination example of the loop instruction sequence to be adopted. FIG. 8 shows an example of a case where there is a difference in execution time between the masked SIMD instruction and the gather / scatter instruction.

For example, if the instruction in one iteration of the loop instruction sequence 41 using the masked SIMD instruction is rewritten with the intermediate language instruction, the intermediate language instruction sequence 61 is obtained. The intermediate language instruction sequence 61 is an example of the first SIMD instruction sequence 2 shown in the first embodiment.

The first line of the intermediate language instruction column 61 is an instruction for setting a mask. By "(mod (i: i + 7,2) == (1,1,1,1,1,1,1,1)", each integer from the current value of the loop control variable i to i + 7 was divided by 2. If the remainder is 1, a mask of "T" is generated, and if it is not 1, a mask of "F" is generated. The generated mask is set in the register "p1".

The second line of the intermediate language instruction column 61 is a load instruction using a mask. By "vroad_with_mask (b (i: i + 7), p1)", the corresponding value in the mask is "T" among the elements of the array b whose index values are the integers from the current value of the loop control variable i to i + 7. The element that is is loaded from memory. The loaded element is set in the register "v1". Further, by "vroad_with_mask (c (i: i + 7), p1)", among the elements of the array c having each integer from the current value of the loop control variable i to i + 7 as an index value, the corresponding value in the mask is "T". The element that is "is loaded from memory. The loaded element is set in the register "v2". The two load instructions described on the second line can be executed in parallel.

The third line "badd_with_mask (v1, v2, p1)" of the intermediate language instruction string 61 is the addition of the elements of the register "v1" and the register "v2" whose corresponding values in the mask are "T". It is an instruction. The addition result is set in the register "v3".

The fourth line of the intermediate language instruction column 61 is a store instruction using a mask. By "vstore_with_mask (a (i: i + 7), v3, p1)", the value in the register "v3" whose corresponding value in the mask is "T" is an integer from the current value of the loop control variable i to i + 7. It is set in the element of the array a having each as the index value.

The loop optimizing unit 122a refers to the instruction scheduling table 111a and specifies the latency of each row of the intermediate language instruction column 61. The instruction for setting the mask in the first row of the intermediate language instruction column 61 corresponds to the intermediate language instruction "vcmp" in the instruction scheduling table 111a shown in FIG. Each instruction in the second to fourth rows of the intermediate language instruction column 61 corresponds to an intermediate language instruction having the same name in the instruction scheduling table 111a.

Then, the latency of the instruction in the first row of the intermediate language instruction column 61 is "4", the latency of the second row is "10", the latency of the third row is "9", and the latency of the fourth row is "10". .. As a result, the execution time of one iteration shown in the intermediate language instruction sequence 61 is "4 + 10 + 9 + 10 = 33 (cycles)". Since the loop rotation speed of the loop instruction sequence 41 using the masked SIMD instruction is "n / 8", the value "4.1n (cycles)" obtained by multiplying the execution time by the loop rotation speed uses the SIMD instruction. This is the execution time of the loop instruction sequence 41.

When the instruction in one iteration of the loop instruction sequence 42 using the gather / scatter instruction is rewritten with the intermediate language instruction, the intermediate language instruction sequence 62 is obtained. The intermediate language instruction sequence 62 is an example of the second SIMD instruction sequence 3 shown in the first embodiment.

The first line of the intermediate language instruction column 62 is an instruction for setting the index value of the element to be processed. By "vinex (i, 2)", a list of two index values is generated from the loop control variable i. In the list, index values of a number of elements (8 elements in the example of FIG. 8) corresponding to the size of the register "v0" are registered. The generated list is set in the register "v0".

The second line of the intermediate language instruction column 62 is a gather instruction. By "gather (b (v0))", the elements of the array b of the index values set in the register "v0" are loaded from the memory. The loaded element is set in the register "v1". Further, the element of the array c of the index values set in the register "v0" is loaded from the memory by "gather (c (v0))". The loaded element is set in the register "v2". The two gather instructions described on the second line can be executed in parallel.

The third line "vadd (v1, v2)" of the intermediate language instruction column 62 is an addition instruction between the corresponding elements of the register "v1" and the register "v2". The addition result is set in the register "v3".

The fourth line of the intermediate language instruction column 62 is a scatter instruction. By "scatter (a (v0), v3)", the value in the register "v3" is set in the element of the array a of the index values set in the register "v0".

The loop optimizing unit 122a refers to the instruction scheduling table 111a and specifies the latency of each row of the intermediate language instruction column 62. For example, the latency of the "scatter" that instructs the masked store in the fourth row of the intermediate language instruction column 62 is shown in the latency information of the intermediate language instruction "scatter" in the instruction scheduling table 111a shown in FIG. Each instruction in the first to third rows of the intermediate language instruction column 62 corresponds to an intermediate language instruction having the same name in the instruction scheduling table 111a.

Then, the latency of the instruction in the first row of the intermediate language instruction column 62 is "4", the latency of the second row is "20", the latency of the third row is "9", and the latency of the fourth row is "40". .. As a result, the execution time of one iteration shown in the intermediate language instruction sequence 62 is "4 + 20 + 9 + 40 = 73 (cycles)". Since the loop rotation speed of the loop instruction sequence 42 using the gather / scatter instruction is "n / 16", the value "4.6n (cycles)" obtained by multiplying the execution time by the loop rotation speed is the gather / scatter instruction. This is the execution time of the loop instruction sequence 42 to be used.

The loop optimizing unit 122a compares the execution time of the loop instruction sequence 41 using the SIMD instruction with the execution time of the loop instruction sequence 42 using the gather / scatter instruction, and adopts the loop instruction sequence having the shorter time. .. In the example of FIG. 8, the loop instruction sequence 41 using the SIMD instruction is adopted. That is, in the example of FIG. 8, it is more efficient to use the masked SIMD instruction even if the rotation speed is doubled.

The loop optimization unit 122a determines such an optimization method for loop processing for each loop. As a result, a large number of loop processes included in the source file 112 are individually optimized in an appropriate manner.

Hereinafter, the procedure of the loop optimization process will be described in detail with reference to the flowchart.
FIG. 9 is a flowchart showing an example of the procedure of the loop optimization process. Hereinafter, the process shown in FIG. 9 will be described along with the step numbers.

[Step S101] The loop optimizing unit 122a extracts loop instruction sequences one by one from the loop group in the source code in the analyzed source file 112. Hereinafter, the loop instruction sequence extracted from the source code will be referred to as an original loop.

[Step S102] The loop optimizing unit 122a determines whether or not the loop instruction sequence can be extracted in step S101. For example, when all the loop instruction sequences described in the source file 112 have been extracted, the process ends. The loop optimizing unit 122a advances the process to step S103 for the extracted loop instruction sequence. Further, the loop optimizing unit 122a ends the loop optimizing process when the loop instruction sequence cannot be extracted.

[Step S103] The loop optimizing unit 122a determines the loop type of the extracted loop instruction sequence. The loop type is a type of loop processing indicated by a loop instruction sequence.
Loop types include loop processing (TYPE1) that uses masked SIMD instructions when optimized, loop processing (TYPE2) that uses gather / scatter instructions when optimized, and other loop processing (TYPE0). ). The loop processing of "TYPE0" is a loop processing that is not the target of optimization by the loop optimizing unit 122a. The loop processing of "TYPE 1" is, for example, a processing of selecting an element to be calculated by a conditional branch (IF statement or the like) among continuous elements in an array. The loop process of "TYPE 2" is a process of executing an operation on an element having a discontinuous index value in the array (for example, an element having an index value of a constant stride width interval). Details of the loop type determination process will be described later (see FIG. 10).

[Step S104] The loop optimizing unit 122a determines whether or not the loop type of the loop processing shown in the loop instruction sequence is "TYPE1" or "TYPE2". If the loop type is "TYPE1" or "TYPE2", the loop optimizing unit 122a advances the process to step S105. If the loop type is "TYPE0", the loop optimizing unit 122a advances the process to step S101.

[Step S105] The loop optimizing unit 122a performs a process of generating an equivalent loop equivalent to the original loop extracted in step S101. The equivalent loop is a loop instruction sequence of a different loop type that obtains the same processing result as the extracted loop instruction sequence. For example, the loop optimizing unit 122a generates a loop instruction sequence of "TYPE2" that obtains the same processing result if the loop type of the extracted loop instruction sequence is "TYPE1". Further, the loop optimizing unit 122a generates a loop instruction sequence of "TYPE1" that obtains the same processing result if the loop type of the extracted loop instruction sequence is "TYPE2". The details of the equivalent loop generation process will be described later (see FIG. 11).

[Step S106] The loop optimizing unit 122a performs instruction scheduling processing for each of the original loop and the equivalent loop. In the instruction scheduling process, for example, the order of instructions is changed so as to improve the processing efficiency. For example, the loop optimizing unit 122a rewrites the loop processing that can be processed in parallel by the SIMD instruction into an instruction sequence using the SIMD instruction. Details of the instruction scheduling process will be described later (see FIG. 14).

[Step S107] The loop optimizing unit 122a performs loop cost calculation processing for each of the original loop and the equivalent loop. The loop cost calculation process is a process of converting the time (execution time of one iteration x number of revolutions) required for executing the entire loop process according to the loop instruction sequence as a cost. The details of the loop cost calculation process will be described later (see FIG. 15).

[Step S108] The loop optimizing unit 122a compares the loop costs of the original loop and the equivalent loop, and determines whether or not the loop cost of the original loop is larger than the loop cost of the equivalent loop. If the loop cost of the original loop is larger, the loop optimizing unit 122a advances the process to step S109. If the loop optimization unit 122a has the same loop cost or the equivalent loop is larger, the loop optimizing unit 122a advances the process to step S101.

[Step S109] The loop optimizing unit 122a replaces the loop instruction sequence of the original loop with the loop instruction sequence of the equivalent loop.
[Step S110] The loop optimizing unit 122a discards the rejected loop instruction sequence and proceeds to the process in step S101.

In this way, the loop optimizing unit 122a shortens the processing time for loop processing that can be executed by both the loop instruction sequence that uses the masked SIMD instruction and the loop instruction sequence that uses the gather / scatter instruction. The loop instruction sequence of can be adopted.

Next, the loop type determination process will be described in detail.
FIG. 10 is a flowchart showing an example of the procedure of the loop type determination process. Hereinafter, the process shown in FIG. 10 will be described along with the step numbers.

[Step S121] The loop optimizing unit 122a determines whether or not the loop control variable is recognized from the original loop. The loop control variable is a variable that is updated every rotation of the loop, such as the variable "i" in "do i = s, n, k". The loop optimizing unit 122a recognizes, for example, a variable that is updated once per rotation (1 iteration) by the rotation of the loop as a loop control variable. The loop optimizing unit 122a recognizes that a variable having two or more updates per iteration is not a loop control variable because the variable is not optimized.

When the loop optimizing unit 122a recognizes the loop control variable, the loop optimizing unit 122a advances the process to step S122. If the loop optimizing unit 122a cannot recognize the loop control variable, the loop optimizing unit 122a advances the process to step S125.

[Step S122] The loop optimizing unit 122a recognizes the incremental value of the loop control variable. The incremental value is the amount of increase in the loop control variable per iteration. For example, the constant "k" in "do i = s, n, k" is an incremental value. The increment value represents the stride width of the index value of the element to be calculated.

The loop processing can also be described as "do i = s, n". In this description, the description of the increment value "1" defined as the default value is omitted. When "do i = s, n" is described, the loop optimization unit 122a determines that this description is equivalent to "do i = s, n, 1", and sets the increment value to "1". recognize.

[Step S123] The loop optimizing unit 122a determines whether or not the initial value s of the loop control variable (“s” in “do i = s, n, k”) is a constant of 0 or more. When the initial value s is a constant of 0 or more, the loop optimization unit 122a advances the process to step S124. If the initial value s is not a constant of 0 or more, the loop optimizing unit 122a advances the process to step S125.

[Step S124] The loop optimization unit 122a determines whether or not the increment value k is a constant. When the increment value k is a constant, the loop optimizing unit 122a advances the process to step S126. If the increment value k is not a constant, the loop optimizing unit 122a advances the process to step S125.

[Step S125] The loop optimizing unit 122a ends the loop type determination process with the return value of the loop type determination process set to "TYPE0". That is, the loop optimizing unit 122a determines the loop type of the original loop to be "TYPE0".

[Step S126] The loop optimization unit 122a determines whether or not the increment value k = 1. If the increment value k = 1, the loop optimization unit 122a advances the process to step S127. Further, the loop optimization unit 122a advances the process to step S129 unless the increment value k = 1.

[Step S127] The loop optimizing unit 122a determines whether or not the original loop satisfies the IF mask type condition. The IF mask type conditions are, for example, the following five conditions.
-There is one branch (IF statement) other than the loop rotation branch.
-The conditional clause of the IF statement is "mod (loop control variable, threshold) == constant VAL".
-The constant VAL satisfies "0 ≤ constant VAL <incremental value k".
-The operation under the IF statement is executed for data of a certain width.
-The instruction sequence other than the IF conditional clause, IF branch, and loop repetition judgment is under the IF statement.

If all of these five conditions are satisfied, the loop optimization unit 122a determines that the IF mask type condition is satisfied, and proceeds to step S128. If at least one of these five conditions is not satisfied, the loop optimization unit 122a determines that the IF mask type condition is not satisfied, and proceeds to step S130.

[Step S128] The loop optimizing unit 122a ends the loop type determination process with the return value of the loop type determination process set to "TYPE1". That is, the loop optimizing unit 122a determines the loop type of the original loop to be "TYPE1".

[Step S129] The loop optimization unit 122a determines whether or not the increment value k is larger than the preset threshold value. The threshold value can be arbitrarily set by the user. For example, if only the loop processing that performs an operation on an element having an odd or even index value is optimized, the user may set "2" as the threshold value. If the increment value k is larger than the threshold value, the loop optimization unit 122a advances the process to step S130. If the increment value k is equal to or less than the threshold value, the loop optimization unit 122a advances the process to step S131.

[Step S130] The loop optimizing unit 122a ends the loop type determination process with the return value of the loop type determination process set to "TYPE0". That is, the loop optimizing unit 122a determines the loop type of the original loop to be "TYPE0".

[Step S131] The loop optimizing unit 122a ends the loop type determination process with the return value of the loop type determination process set to "TYPE2". That is, the loop optimizing unit 122a determines the loop type of the original loop to be "TYPE2".

In this way, the loop type of the original loop is determined according to the content of the loop processing shown in the loop instruction sequence. Then, the loop instruction sequence of "TYPE1" or "TYPE2" is the object of optimization by the loop optimizing unit 122a. When the loop type determination is completed, the equivalent loop generation process is executed.

FIG. 11 is a flowchart showing an example of the procedure of the equivalent loop generation process. Hereinafter, the process shown in FIG. 11 will be described along with the step numbers.
[Step S141] The loop optimizing unit 122a determines whether or not the loop type of the original loop is "TYPE1". If the loop type is "TYPE1", the loop optimizing unit 122a advances the process to step S142. If the loop type is "TYPE2", the loop optimizing unit 122a advances the process to step S143.

[Step S142] The loop optimizing unit 122a generates a loop instruction sequence (loop instruction sequence using the gather / scatter instruction) of "TYPE2" that can obtain the same processing result as the original loop as an equivalent loop. After that, the loop optimization unit 122a advances the process to step S144.

[Step S143] The loop optimizing unit 122a generates a loop instruction sequence (loop instruction sequence using a masked SIMD instruction) of "TYPE1" that can obtain the same processing result as the original loop.

[Step S144] The loop optimizing unit 122a optimizes a portion of the loop instruction sequence that is an equivalent loop that can be made a constant. Then, the loop optimizing unit 122a converts the description of the corresponding portion into a constant. For example, when s of "mod (s, stride)" is a constant and the stride indicating the increment value is also a constant, the loop optimizing unit 122a states that the constant calculation result of "mod (s, stride)" is "1". If so, the "mod (s, stride)" is converted to the constant "1".

[Step S145] The loop optimizing unit 122a optimizes invariants that cannot be made constant. For example, the loop optimizing unit 122a expels the mod (s, stride) out of the loop when the stride is a constant, even if the s of the mod (s, stride) is not a constant.

[Step S146] The loop optimizing unit 122a outputs the generated equivalent loop as a return value, and ends the equivalent loop generation process.
In this way, an equivalent loop that can obtain the same processing result as the original loop is generated. The loop optimizing unit 122a stores the generated original loop and the equivalent loop in the memory 102.

FIG. 12 is a diagram showing an example of conversion from the original loop of “TYPE 1” to the equivalent loop of “TYPE 2”. In the original loop 71 shown in FIG. 12, the condition “mod (i, stride) .eq. Val” is shown in the IF statement. This is a condition that the remainder when the loop control variable i is divided by the constant "stride" is equal to the constant "val". The loop processing in which the conditions are defined in such a loop processing is optimized by the SIMD conversion unit 122b for the processing using the mask SIMD instruction.

In the equivalent loop 72 generated based on the original loop 71, the loop control variable is increased at regular intervals by “i + = stride” in the loop processing. The loop processing accompanied by the increase of the loop control variable with such a constant stride width is optimized by the SIMD conversion unit 122b for the processing using the gather / scatter instruction. Further, in the equivalent loop 72, the value of the loop control variable i that first satisfies the condition in the IF statement of the original loop 71 is calculated by the two lines of instructions before the loop processing. As a result, the processing time per iteration in the loop processing can be shortened.

FIG. 13 is a diagram showing an example of conversion from the original loop of “TYPE 2” to the equivalent loop of “TYPE 1”. In the original loop 73 shown in FIG. 13, the loop control variable is increased at regular intervals by “i + = stride” in the loop processing. The loop processing accompanied by the increase of the loop control variable with such a constant stride width is optimized by the SIMD conversion unit 122b for the processing using the gather / scatter instruction.

In the equivalent loop 74 generated based on the original loop 73, the condition “mod (i, stride) .eq. Mod (s, stride)” is shown in the IF statement. The loop processing in which the conditions are defined in such a loop processing is optimized by the SIMD conversion unit 122b for the processing using the mask SIMD instruction.

By generating the equivalent loop based on the original loop, a pair of the loop instruction sequence of "TYPE1" and the loop instruction sequence of "TYPE2" is generated. Then, the loop optimizing unit 122a performs instruction scheduling processing on the set of loop instruction sequences.

FIG. 14 is a flowchart showing an example of the instruction scheduling process procedure. Hereinafter, the process shown in FIG. 14 will be described along with the step numbers.
[Step S151] The loop optimizing unit 122a acquires the loop instruction sequence of "TYPE1" from the memory 102.

[Step S152] The loop optimizing unit 122a performs instruction scheduling of the loop instruction sequence of "TYPE1". For example, the loop optimizing unit 122a performs instruction scheduling by referring to the latency information for each instruction and the arithmetic unit information to be used from the instruction scheduling table 111a. For example, the loop optimizing unit 122a rearranges the order of instructions within a range that does not affect the calculation result so that the loop processing can be executed efficiently. As the instruction scheduling method, the loop optimizing unit 122a can use, for example, a method such as list scheduling or software pipeline.

[Step S153] The loop optimizing unit 122a acquires the loop instruction sequence of "TYPE 2" from the memory 102.
[Step S154] The loop optimizing unit 122a refers to the instruction scheduling table 111a and performs instruction scheduling of the loop instruction sequence of "TYPE 2" in the same manner as in step S152.

[Step S155] The loop optimizing unit 122a outputs a set of loop instruction sequences of "TYPE1" and "TYPE2" after instruction scheduling as a return value, and ends the instruction scheduling process. The loop instruction sequence after the instruction scheduling process is described by, for example, an intermediate language instruction. The loop optimizing unit 122a stores in the memory 102 a set of loop instruction sequences of "TYPE1" and "TYPE2" after instruction scheduling.

After that, the loop optimizing unit 122a calculates the loop cost of each of the loop instruction sequences of "TYPE1" and "TYPE2".
FIG. 15 is a flowchart showing an example of the procedure of the loop cost calculation process. Hereinafter, the process shown in FIG. 15 will be described along with the step numbers.

[Step S161] The loop optimizing unit 122a acquires the loop instruction sequence after instruction scheduling of "TYPE1" from the memory 102.
[Step S162] The loop optimizing unit 122a calculates the number of processing cycles C1 of the processor required to execute the instruction sequence of the critical path in one rotation (1 iteration) of the loop instruction sequence of "TYPE1". The critical path is the processing route with the longest processing time in the chain of instructions in the loop. Multiplying the calculated number of cycles by the period of the operating clock of the processor that executes the program gives the processing time in that processor.

[Step S163] The loop optimizing unit 122a calculates the loop rotation speed × the number of cycles C1 after SIMD in the case of “TYPE1”, and sets it as the loop cost TC1 of “TYPE1”. For example, when eight elements can be stored in the SIMD register, the loop rotation speed after SIMD conversion in the case of "TYPE 1" is one-eighth of the loop rotation speed before SIMD conversion.

[Step S164] The loop optimizing unit 122a acquires the loop instruction sequence after instruction scheduling of "TYPE2" from the memory 102.
[Step S165] The loop optimizing unit 122a calculates the number of processing cycles C2 of the processor required to execute the instruction sequence of the critical path in one rotation (1 iteration) of the loop instruction sequence of "TYPE2".

[Step S166] The loop optimizing unit 122a calculates the loop rotation speed x the number of cycles C2 after SIMD in the case of "TYPE2", and sets the loop cost TC2 of "TYPE2". For example, when eight elements can be stored in the SIMD register and the increment value of the loop control variable i is 2, the loop rotation speed after SIMD conversion in the case of "TYPE2" is 16 minutes of the loop rotation speed before SIMD conversion. It is one of.

[Step S167] The loop optimizing unit 122a outputs the loop costs TC1 and TC2 of each of the loop instruction sequences of "TYPE1" and "TYPE2" as return values, and ends the loop cost calculation process.

After calculating the loop costs TC1 and TC2 of each of the loop instruction sequences of "TYPE1" and "TYPE2" in this way, the loop optimization unit 122a applies the loop instruction sequence having the lower loop cost to the compiled program. Adopt as a command sequence. As a result, the object file 113 that can execute the processing more efficiently is generated.

Further, the loop optimizing unit 122a replaces a part of the loop instruction sequence that can be made into a constant with a constant. As a result, the efficiency of loop processing can be improved. Further, the loop optimizing unit 122a simplifies the processing in the loop by moving the instruction that can move out of the loop out of the loop. As a result, the efficiency of the loop processing can be further improved.

For example, in the case of a loop instruction sequence using a masked SIMD instruction, the mask can be set to a fixed value.
FIG. 16 is a diagram showing an example of fixing the mask value in the masked SIMD instruction. The loop instruction sequence 81 shown in FIG. 16 is a fixed value definition of the mask of the loop instruction sequence 41 shown in FIG. The loop instruction sequence 41 is a process of executing an operation on an element having an odd index value in the array. In this case, as shown in the loop instruction sequence 81, a fixed value mask can be defined outside the loop with "mask = (/ T, F, T, F, T, F, T, F /)". it can. By taking the mask definition out of the loop in this way, the instruction related to the mask definition can be excluded from the intermediate language instruction sequence 82 of the processing of one iteration in the loop processing. As a result, the loop cost becomes "3.6n", which is smaller than the loop cost of the loop instruction sequence 41 shown in FIG.

In this way, the loop optimizing unit 122a fixes the mask and defines the mask outside the loop, so that the use of the SIMD instruction with a mask improves the performance in an increasing number of cases.
In the above description, an example of determining that the index value is odd (odd number determination) is used, but it is also possible to determine that the index value is even (even number determination). , Applicable as well.

FIG. 17 is a diagram showing an example of a loop instruction sequence in the case of even number determination. In the loop instruction sequence 91 that uses the masked SIMD instruction, the condition in the IF statement is "mod (i, 2) == 0". As a result, when the index value is divisible by 2, the determination result of the IF statement becomes true, and the operation is performed on the element having an even index value. In the loop instruction sequence 92 using the gather / scatter instruction, the loop control variable is increased from the even initial value "2" to the increment value "2" for each loop rotation by "do i = 2, n, 2". Let me.

Even in the case of even-numbered determination, the loop optimizing unit 122a can adopt the loop instruction sequence having the better processing efficiency by comparing the loop costs of the loop instruction sequences 91 and 92 shown in FIG. it can.

In the odd-numbered determination and the even-numbered determination, the stride width (incremental value of the index value) of the element to be calculated is "2", but the stride width may be "3" or more.
FIG. 18 is a diagram showing an example of a loop command sequence when the stride width is “3”. In the loop instruction sequence 93 using the masked SIMD instruction, the condition in the IF statement is "mod (i, 3) == 1". As a result, when the remainder when the index value is divided by 3 is 1, the determination result of the IF statement becomes true, and the operation is performed on the corresponding element. In the loop instruction sequence 94 using the gather / scatter instruction, the loop control variable is increased from the initial value "1" to the increment value "3" for each loop rotation by "do i = 1, n, 3".

Even when the stride width is "3", the loop optimizing unit 122a adopts the loop instruction sequence having the better processing efficiency by comparing the loop costs of the loop instruction sequences 93 and 94 shown in FIG. can do.

FIG. 19 is a diagram showing an example of a loop command sequence when the stride width is “4”. In the loop instruction sequence 95 that uses the masked SIMD instruction, the condition in the IF statement is "mod (i, 4) == 1". As a result, when the remainder when the index value is divided by 4 is 1, the determination result of the IF statement becomes true, and the operation is performed on the corresponding element. In the loop instruction sequence 96 using the gather / scatter instruction, the loop control variable is increased from the even initial value "1" to the increment value "4" for each loop rotation by "do i = 1, n, 4". Let me.

Even when the stride width is “4”, the loop optimizing unit 122a adopts the loop instruction sequence having the better processing efficiency by comparing the loop costs of the loop instruction sequences 95 and 96 shown in FIG. can do.

The larger the stride width, the smaller the number of elements that can be processed in parallel by the SIMD instruction when the masked SCID instruction is used. Therefore, as the stride width becomes larger, the loop instruction sequence using the gather / scatter instruction is more likely to be more efficient than the loop instruction sequence using the masked SCID instruction. Therefore, in the loop type determination process (see FIG. 10), the loop optimizing unit 122a sets the loop type to "TYPE 0" when the increment value k is other than "1" and is larger than a predetermined threshold value. The process of is omitted to improve the efficiency of the compilation process.

That is, when the increment value k is other than "1", the original loop is a loop instruction sequence using the gather / scatter instruction, but when the increment value k exceeds the threshold value, it is not necessary to calculate the loop cost. It is more efficient to use the gather / scatter instruction. In such a case, the loop optimizing unit 122a aims to improve the efficiency of the processing at the time of compilation by omitting the generation of the equivalent loop and the calculation processing of the loop cost.

[Other embodiments]
The second embodiment shows an example in which the size of the SIMD register is 512 bits (64 bytes), but the size of the SIMD register is not limited to 512 bits. Further, in the second embodiment, the data length of the element to be calculated by the SIMD instruction is 8 bytes, but the data length of the element is not limited to 8 bytes. The loop rotation speed in each loop instruction sequence decreases as the size of the SIMD register increases, and increases as the size of the data to be calculated increases.

Although the embodiment has been illustrated above, the configuration of each part shown in the embodiment can be replaced with another having the same function. Further, any other components or processes may be added. Further, any two or more configurations (features) of the above-described embodiments may be combined.

1 Loop instruction sequence 2 First SIMD instruction sequence 3 Second SIMD instruction sequence 10 Information processing device 11 Storage unit 11a Program 11b Execution time information 12 Processing unit

Claims (7)

On the computer
Extract a loop instruction sequence that directs operations on some elements in the array from the program to be compiled.
Based on the loop instruction sequence, a mask that enables only the element to be calculated among the plurality of elements in the array is used, and SIMD (Single Instruction Multiple Data) is applied to one or more elements enabled by the mask. Generate a first SIMD instruction sequence that describes a loop process that repeats the process of executing operations in parallel by instructions.
Based on the loop instruction sequence, a plurality of discontinuous elements in the array are stored in a continuous area in the SIMD register, and operations are executed in parallel by the SIMD instruction for the plurality of elements in the SIMD register. Generates a second SIMD instruction sequence that describes the loop processing that repeats the processing to be performed.
Based on the execution time information in which the numerical value indicating the time required for executing each of the plurality of instructions is set, the processing time of the first SIMD instruction sequence and the processing time of the second SIMD instruction sequence are calculated.
Based on the processing time of the first SIMD instruction sequence and the processing time of the second SIMD instruction sequence, the instruction sequence to be included in the compiled program among the first SIMD instruction sequence and the second SIMD instruction sequence is selected. select,
A compilation program that executes processing. In the calculation of the processing time, the value obtained by multiplying the time required for executing the processing per rotation of the loop processing of the first SIMD conversion instruction sequence by the loop rotation speed of the first SIMD conversion instruction sequence is multiplied by the loop rotation speed of the first SIMD conversion instruction sequence. The processing time is defined as the processing time of the second SIMD instruction sequence, which is obtained by multiplying the time required for executing the processing per rotation of the loop processing of the second SIMD instruction sequence by the loop rotation speed of the second SIMD instruction sequence. To
The compilation program according to claim 1. In the calculation of the processing time, the value obtained by dividing the number of rotations of the loop processing in the loop instruction sequence by the number of elements that can be stored in the SIMD register is used as the loop rotation number of the first SIMD instruction sequence, and is used in the loop instruction sequence. The loop rotation of the second SIMD instruction sequence is obtained by dividing the number of rotations of the loop processing by the number of elements that can be stored in the SIMD register and the increment value for each rotation of the index value indicating the element to be calculated. Number,
The compilation program according to claim 2. It has the execution time information corresponding to each of a plurality of microarchitectures,
In the calculation of the processing time, the processing time between the first SIMD instruction sequence and the second SIMD instruction sequence is calculated with reference to the execution time information corresponding to the microarchitecture specified at compile time.
The compilation program according to claim 2 or 3. In the generation of the first SIMD instruction sequence, the first SIMD instruction sequence for executing the mask generation process before the start of the loop process is generated.
The compilation program according to any one of claims 1 to 4. On the computer,
It is determined whether or not the increment value of the loop control variable for each loop processing of the loop instruction sequence exceeds a predetermined threshold value.
When the increment value exceeds a predetermined threshold value, a process of suppressing the generation of the first SIMD instruction sequence and the execution of the calculation of the processing time is executed.
In the selection of the command sequence, when the incremental value exceeds a predetermined threshold value, the second SIMD command sequence is selected.
The compilation program according to any one of claims 1 to 5. A storage unit that stores the program to be compiled,
A mask that extracts a loop instruction sequence instructing an operation on some elements in the array from the program and enables only the element to be operated out of a plurality of elements in the array based on the loop instruction sequence. Is used to generate a first SIMD instruction sequence in which a loop process of repeating a process of executing operations in parallel by a SIMD (Single Instruction Multiple Data) instruction for one or more elements enabled by the mask is generated. Based on the loop instruction sequence, a plurality of discontinuous elements in the sequence are stored in a continuous area in the SIMD register, and operations are executed in parallel by the SIMD instruction for the plurality of elements in the SIMD register. The processing time of the first SIMD instruction sequence is based on the execution time information in which the second SIMD instruction sequence in which the loop processing that repeats the processing is described is generated and a numerical value indicating the time required for executing each of the plurality of instructions is set. And the processing time of the second SIMD instruction sequence are calculated, and based on the processing time of the first SIMD instruction sequence and the processing time of the second SIMD instruction sequence, the first SIMD instruction sequence and the second SIMD instruction sequence are calculated. Of the instruction sequences, the processing unit that selects the instruction sequences to be included in the compiled program, and
Information processing device with.

Images