Dependency mesh based instruction-level parallel scheduling method

Abstract

The invention discloses a dependency mesh based instruction-level parallel scheduling method. The method includes the steps of 1), acquiring data dependency relations among instructions in a target basic block and information of function units corresponding to the instructions, and setting and computing data dependency priority values of the instructions according to the data dependency relations; 2), partitioning the instructions according to the data dependency priority values and the function units, storing partitioned results according to a mesh form, and establishing dependency meshes obtaining dependency relations between the instructions and data dependency priorities as well as between the instructions and the function units; 3), performing parallelism analysis among the instructions according to the relations, in the dependency meshes obtained in the step 2, between the instructions and the data dependency priorities as well as between the instructions and the function units. The dependency mesh based instruction-level parallel scheduling method has the advantages that the method is capable of describing parallel relations among the instructions and relativity between the instructions and hardware structures by combining the data dependency relations and function unit allocation relations, and is simple in implementation, wide in application range and high in instruction-level parallelism.

Description

technical field [0001] The invention relates to the technical field of compilation optimization, in particular to an instruction-level parallel scheduling method based on dependency grid description. Background technique [0002] In a basic block, one of the most basic associations between instructions is the data dependency constraint caused by the data flow, which determines the running result of the program. In modern pipeline processors and superscalar processors, instruction rearrangement can be used to increase code parallelism to take advantage of advanced architectures, but this instruction rearrangement technology needs to be based on understanding the parallelism between instructions in basic blocks can be carried out on the basis of Therefore, before or during instruction rearrangement, an important task is to identify the parallelism among instructions in a basic block. [0003] In the prior art, the basic method for rearranging the instructions in the basic bl...

AI Technical Summary

Problems solved by technology

[0005]1) Although this method describes the data dependencies between instructions, it does not show other correlations between instructions, especially those related to the target system hardware. Therefore, the correlation between the instruction and the hardware structure cannot be determined during the execution scheduling process;

[0006]2) For the VLIW (Very Long Instruction Word, very long instruction word) architecture of the multi-function unit, because this method cannot reflect the difference between instructions due to different functional units Therefore, this method is not suitable for using more aggressive or forward-looking instruction rearrangement technology in the VLIW architecture, and it is not conducive to more fully exploring the basic block instructions brought by the architectural features. Inter-parallelism;

[0007]3) For the VLIW architecture of multifunctional units, since this method cannot reflect the real-time workload of each functional unit, it cannot also reflect in real time between instructions, instructions and The relationship between functional units, so when some instructions can be executed in any one of multiple functional units, this method cannot be combined with functional unit allocation to make instruction scheduling produce more architecture-appropriate optimization results

Images