CN104572103B - A kind of the worst execution time WCET method for quick estimating based on distribution function - Google Patents

Abstract

The present invention provides a WCET fast estimation method based on the distribution function, obtain the disassembly file F by disassembling the DSP engineering target code (out file); analyze the disassembly file F, and obtain each divided basic block , get the basic block set B of the program; identify the relationship between the basic blocks in the basic block set B, construct the program flow graph C; calculate the execution time T of each basic block; compare the basic block execution time T with the basic block execution times Ts is used as a weight to obtain a weighted program flow graph Cw; analyze the weighted program flow graph Cw to obtain the path with the largest total weight, and use the largest total weight as the worst execution time WCET of the program. It solves the disadvantages of running a program to obtain test samples and the problem of too much manual intervention in the prior art, as well as the irrationality of the beta distribution parameter estimation method in the traditional PERT technology.

Description

A Fast Estimation Method of Worst Execution Time WCET Based on Distribution Function

technical field

The invention belongs to the field of real-time embedded software, in particular to a fast estimation method of Worst-Case Execution Time (WCET: Worst-Case Execution Time) based on distribution function in TI DSP technology, which can be used to evaluate the worst case of DSP engineering code or code fragment execution time.

Background technique

In a real-time embedded software system, the system has stricter requirements on time. The correctness of the system is not only related to the logic of its program, but also related to its time characteristics. Only when the specified task is completed within the specified time is it effective, otherwise it will be Lead to the reduction of the performance of the system or even the failure of the system. Therefore, obtaining the Worst Execution Time (WCET) of each task in the system in advance is of great significance for timing analysis of real-time systems.

At present, WCET analysis mainly includes three methods: static analysis method, dynamic measurement method and hybrid analysis method.

The dynamic measurement method is to dynamically test the execution time of the program by running the program, and then analyze and obtain WCET. However, this method has great disadvantages. First, the method requires a target machine, needs to actually run the program, and requires a lot of experiments, which consumes manpower and material resources. , financial resources, and in the field of aerospace and aviation, in many cases it is impossible to simulate the real target machine environment or the target machine is expensive and has high requirements for real-time performance. It is impossible to let untested programs run on the real target machine. In addition, this method is difficult to ensure that the measured results are safe, that is, it cannot guarantee that the worst execution time will not be underestimated, because it is difficult to ensure that the actual measurement made meets the conditions of the program WCET. For modern processors, This point is more difficult to do.

Hybrid analysis is a method that combines static analysis and dynamic measurement. This method is specifically divided into two situations. One is to first perform static analysis on the program, that is, use static analysis to analyze, and then analyze the The program is run and tested to finally determine the program's WCET; the other is to first test and analyze the program using the dynamic measurement method, and then perform static analysis on the basis of the dynamic measurement method to determine the program's WCET.

No matter which method is used, the hybrid analysis method includes the advantages of static analysis method and dynamic measurement method, but also contains their own disadvantages, and the hybrid analysis method is more complicated.

The static analysis method is to estimate the WCET of the program through theoretical analysis. This method can not only obtain the calculation results without running the program, but also ensure that the obtained results are safe. Therefore, this is a commonly used method at present.

The traditional static analysis method generally consists of three parts: ①The control flow analysis of the program, which mainly analyzes and determines the possible execution path, the maximum number of cycles, and the infeasible path of the program; ②The underlying analysis mainly considers the characteristics of the target machine, such as cache , pipeline, branch prediction, etc., the purpose is to determine the execution time of each assembly statement or each basic block; ③WCET calculation, according to the first two items of information, use specific calculation methods to calculate the WCET of the program, the main calculation methods are divided into Path methods, tree-based methods, and methods that imply path enumeration.

Generally speaking, the traditional static analysis method treats the execution time of each assembly instruction as a definite value during the WCET calculation process, and then obtains the WCET of the program through a certain method, but this value is also definite.

It can be seen that the traditional method does not take into account the uncertainty of program execution time. According to the characteristics of the current processor, this method obviously has great disadvantages, because the current processor adopts many advanced technologies to speed up the calculation. , such as high-level cache, pipeline, branch prediction, etc., make the uncertainty of program execution time more obvious.

Therefore, the running time of the program is not a single value, but a range of interval values.

The current solution to this problem is mainly to find WCET by probability method, that is, pWCET. This concept was proposed by Guillem Bernat in 2003. The main purpose is to solve the probability distribution problem of WCET of a certain code or a certain function. A lot of literature has been published using this method to calculate WCET, such as:

1) In 2003, Stefan M Petters proposed a method of using extreme value statistics theory to solve the program execution time interval. The general idea of this document is to run the program multiple times to obtain many program running time values, and then approximate it with the Gumble probability function to obtain the extreme value of the program running time, which is the WCET value. Analyzing this document, it can be easily seen that this method cannot be regarded as a pure static analysis, because it performs function fitting and approximation on the time value obtained by running the program multiple times, and the WCET obtained by finding the extreme value also has a dynamic measurement method limitations.

2) In 2006, Hu Minghua and Tang Mingduan proposed in the literature "Static Prediction of Program Execution Time Based on Distribution Function" to use probability distribution to simulate the running time of 8087 instructions, and use normal distribution to simulate the entire program execution time after instruction superposition method. However, this method requires a lot of preprocessing of the program to be analyzed in advance, such as expanding the loop statement according to the maximum number of loops, dividing the branch judgment statement into two branches, and dividing the case statement into multiple branches, etc., which limits the Its applicability and automation, especially for large-scale engineering programs, require a lot of human resources and have great limitations. In addition, this method draws on the idea of Program Review Technology (PERT). However, this literature uses the traditional PERT method, and the traditional PERT method itself has great drawbacks, mainly due to the inaccuracy of the beta distribution parameter estimation method .

3) In 2010, Zhang Baomin, Wu Guowei and others proposed in the document "Extreme Value Statistical Method of Program Execution Time" to use the measurement value of program execution time as a sample, and use the Gumble distribution to establish the worst statistical model of program execution time, thus Methods for Predicting WCET. However, this method still needs to run the program to obtain the measurement value samples, which has the limitation of the dynamic measurement method.

In summary, although the current WCET analysis method adopts the static analysis method and analyzes the WCET from the perspective of probability, it bypasses the modeling of complex underlying hardware and other characteristics, and simplifies the WCET estimation method. However, the static analysis method is not pure The static analysis of the program needs to run the program in advance to obtain the measurement value sample of the execution time, and then use the probability distribution to approximate it, so as to predict the WCET of the program. It is a hybrid analysis method, so it has great disadvantages. The method proposed by Hu Minghua et al. requires a lot of manual preprocessing of the program in advance, which cannot realize automatic analysis, and uses the traditional PERT technology, which has great limitations.

Contents of the invention

The purpose of the present invention is to propose a WCET fast estimation method based on the distribution function, to solve the drawbacks of the prior art that need to run the program to obtain the test sample and the problem of too much manual intervention and the beta distribution parameters in the traditional PERT technology Unreasonableness of the estimation method.

To achieve the above object, the technical solution of the present invention comprises the following steps:

(1) Obtain the disassembly file F by disassembling the DSP engineering target code (out file);

(2) Analyze the disassembly file F, obtain each basic block divided, and obtain the basic block set B of the program;

(3) Identify the relationship between the basic blocks in the basic block set B, and construct the program flow graph C;

(4) Calculate the execution time T of each basic block;

(5) A weighted program flow diagram Cw using the basic block execution time T and the basic block execution times Ts as weights;

(6) Analyze the weighted program flow graph Cw, obtain the path with the largest total weight, and use the largest total weight as the worst execution time WCET of the program.

The present invention has the following advantages:

1. The present invention carries out static analysis to DSP project assembly code, obtains the worst execution time under the situation that does not need to run DSP program, overcomes the drawback that needs to run program to obtain measured value sample in the traditional method, is convenient to implement, and is easy to operate;

2. The present invention adopts the method based on distribution function to estimate WCET, bypasses complex underlying hardware characteristics, solves the problem that the underlying hardware characteristics need to be modeled in traditional methods, and has the advantage of being easy to implement;

3. The present invention uses the basic block concept to automatically construct the program flow graph, analyzes the execution time of each node in the program flow graph and the path situation of the program flow graph, and obtains the WCET of the program with less manual intervention, which solves the problem in the traditional method. Problems that require a lot of human intervention;

4. The present invention adopts the improved PERT technology, which solves the irrationality problem of the beta distribution parameter estimation method in the traditional PERT technology, and makes the estimation of the basic block execution time more accurate.

Description of drawings

Fig. 1 is the realization flowchart of the present invention.

detailed description

The present invention will be described in further detail below with reference to the accompanying drawings.

With reference to Fig. 1, the concrete realization steps of the present invention are as follows:

Step 1, read the DSP project disassembly file:

Use TI's disassembly tool to disassemble the target file that is compiled by the DSP project, that is, the out file to obtain the disassembly file of the project.

Step 2, obtain the divided basic block, that is, the basic block division shown in Figure 1:

According to the characteristics of the DSP project disassembly file and the rules of basic block division, analyze the disassembly file line by line to obtain each basic block divided. The specific steps are as follows:

2.1) Determine the entry statement of the basic block

Scan the disassembly file line by line to judge whether it is the entry statement of the basic block. The specific judgment criteria are: ① the first statement of the program; ② the statement to which the conditional transfer statement or unconditional transfer statement can be transferred; The statement behind the statement; ④ the statement immediately following the unconditional transfer statement. If one of the above conditions is satisfied, it is judged to be a basic block entry statement, and the address corresponding to the basic block entry statement in the disassembly file is recorded at the same time.

In the TI C6000 series DSP assembly instructions, the transfer statement is mainly reflected in the B instruction, for example, [! A1] B.S10x00058 statement is a conditional transfer statement, which means that if A1 is equal to 0, the statement is executed, otherwise it is not executed; B.S1 0x00110 statement is an unconditional transfer statement, which means that the statement is executed unconditionally. For the B.S1 0x00110 statement, search for the 0x00110 value in the disassembly file, and use the corresponding assembly statement as the entry statement of the basic block, and at the same time, use the statement behind the statement as the entry statement of another basic block. According to the characteristics of this DSP assembly instruction and combined with the basic block entry sentence judgment criterion, the entry sentence of each basic block in the disassembly file can be judged.

2.2) Judge the exit statement of the basic block

Analyze the disassembly file line by line, if it satisfies one of the following two, it is determined as a basic block exit statement, and record the corresponding address of the basic block exit statement in the disassembly file, and the specific judgment criteria for the basic block exit statement are: ① The statement before the entry statement of the next basic block; ②The termination statement of the assembly code.

2.3) Determine the basic block range

A basic block consists of a sequence of assembly statements between the entry statement and the exit statement. After the basic block range is determined, each basic block is labeled as 1, 2, 3...n, n≥1.

Considering that the number of divided basic blocks is uncertain, in order to facilitate storage and management, the present invention uses a single linked list structure to define and store basic blocks and related information, mainly including basic block labels, addresses corresponding to basic block entry statements, and exit statement correspondences. the address of.

Step 3, obtain the program flow diagram shown in Figure 1:

According to the divided basic blocks and their labels and other information, the relationship between the basic blocks can be obtained, so as to obtain the program flow diagram of the assembly code.

Determining the relationship between basic blocks is mainly to judge whether each basic block is reachable. If reachable, there is a relationship between the basic blocks, otherwise there is no relationship. The specific judgment method is as follows:

3.1) If the exit statement of basic block i is a transfer statement (conditional or unconditional transfer statement), and the target address of the transfer statement is equal to the address corresponding to the entry statement of basic block j, then i can reach j;

3.2) If the exit statement of basic block i is a conditional transfer statement, and the address corresponding to the exit statement plus 4 is equal to the address corresponding to the entry statement of basic block k, then i can reach k;

3.3) If the exit statement of basic block i is an unconditional transfer statement, and the address corresponding to the exit statement plus 4 is equal to the address corresponding to the entry statement of basic block k, then i can reach k, but at this time basic block k is in basic block i , execute after the basic block j;

3.4) If the exit statement of basic block i is not a transfer statement (conditional or unconditional transfer statement), and the address corresponding to the exit statement of the basic block plus 4 is equal to the address corresponding to the entry statement of basic block m, then i can reach m.

Through the above judgment method, the relationship between each basic can be determined, and the directed graph based on the adjacency list in the data structure can be used to describe and store, and the basic block can be used as each node in the directed graph to obtain the program flow graph.

Step 4, calculate the basic block execution time shown in Figure 1:

According to the divided basic blocks and their information, statically estimate the execution time of basic blocks. The basic idea is: from the perspective of probability, grasp the running time interval of the program macroscopically, bypass the complex underlying hardware characteristics, and adopt improved plan review technology PERT simulates the expected value and variance of the running time of each instruction. According to the central limit theorem, the running time of the entire basic block is simulated with a normal distribution after instruction superposition. However, the parallel conditions of instructions need to be considered before instruction superposition. The present invention takes the largest instruction execution time among the parallel instructions as the final execution time of the several parallel instructions, and then participates in the instruction superposition operation. The specific implementation steps are:

4.1) Calculate the expected value μ _i and variance σ _i ² of the running time of each instruction

According to the idea of PERT, the present invention simulates the running time of each DSP assembly instruction with the improved PERT to obtain its expected value and variance, that is, uses the approximate formula of Perry-Greig expected value to calculate the expected value μ of the running time of each DSP instruction _i , using the Person-Turkry variance approximation formula to calculate the variance σ _i ² of the running time of each DSP instruction, the specific calculation formulas are:

μ _i =0.630m _i +0.185(b _i +a _i ),

σ _i ² =0.630(m _i -u _i ) ² +0.185[(b _i -u _i ) ² +(a _i -u _i ) ² ],

In the formula, b _i represents the peak value of the running time of each instruction, a _i represents the valley value of the running time of each instruction, and _mi represents the most likely value of the running time of each instruction. According to the experimental analysis, take The value range of i is [1-N], and N is the number of basic block instructions;

4.2) Screen parallel instructions

There may be instructions executed in parallel in the basic block, and it is necessary to analyze the instruction parallelism, so that the estimated execution time of the basic block is more accurate. According to the expected value μ _i and variance σ _i ² of the running time of each instruction obtained in step 4.2, and combined with the instruction parallelism, the instruction information finally participating in the instruction superposition operation is obtained by screening, specifically:

F _j = max(t ₁ ,L,t _k ,L,t ₈ ),

Among them, t _k represents the execution time of the kth instruction in each parallel execution block in the basic block, and the value range of k is [1-8], because only 8 instructions can be executed in parallel in TI DSP, and max is Take the maximum value operation, t _k =A _k +2S _k , A _k is the expected value of the execution time of the instruction in the basic block corresponding to the kth instruction in the parallel execution block, and S _k is the corresponding basic block of the kth instruction in the parallel execution block The variance of the execution time of the instruction, F _j represents the execution time of each parallel execution block in the basic block, the value range of j is [1-M], and M represents the number of parallel execution blocks contained in the basic block.

4.3) Calculate the mean value μ and variance σ ² of the execution time of the basic block. The specific calculation formulas are:

Among them, μ _j represents the expected value of the instruction running time corresponding to F _j , and σ ² _j represents the variance of the instruction running time corresponding to F _j .

4.4) Get basic block execution time T

After obtaining the mean and variance of the execution time of the basic block, given the time t, we can calculate P(T'≤t), that is, the probability that the execution time of the basic block is not greater than a given value.

For the normal distribution X:N(μ,σ ² ), there are the following facts:

P(t≤μ+σ)=84.15%,

P(t≤μ+2σ)=97.7%,

P(t≤μ+3σ)=99.85%,

In this example, T=μ+2σ is taken as the execution time of the basic block.

Step five, obtain the weighted program flow graph shown in Figure 1:

The worst execution time (WCET) of a program is not only related to the execution path of the program, but also related to the execution time and execution times of the basic block. The combination of execution time and number of executions. Based on this reason, the present invention constructs a weighted program flow graph with basic block execution time and execution times as weights, wherein the basic block execution times need to be manually estimated and determined in advance. The specific implementation method is to add the execution time and execution times information for each basic block in the obtained program flow graph, that is, add the basic block execution time and execution times information in the storage structure of each basic block in the program flow graph, so as to obtain the weighted program flow graph.

Step 6, calculate the worst execution time WCET

After constructing the weighted program flow graph shown in Figure 1, that is, the weighted directed graph, some processing methods of the directed graph can be used to obtain the required information. This embodiment utilizes the path search algorithm to find a path with the largest total weight shown in Figure 1, then its execution time is the longest, and the total weight on this path is used as the WCET of the program. The specific implementation steps are as follows:

6.1) Use the depth-first algorithm to obtain each path of the weighted program flow graph, the specific method is:

6.1.1) Determine the start point and end point of the program flow graph, the specific judgment method is: the start point is the first basic block of the program flow graph, that is, the basic block labeled 1; the end point is the entire basic block of the program flow graph A basic block with an out-degree of 0 in the block adjacency list;

6.1.2) Push the starting point onto the stack and set it as visited;

6.1.3) Determine whether the top node of the stack is the termination point, if so, execute step 6.1.4), otherwise execute step 6.1.5);

6.1.4) Save the elements in the stack, which are the nodes included in the path, and perform step 6.1.6);

6.1.5) Check whether there is any successor and unvisited node in the top node of the stack, if there is, select one of them and put it on the stack, and set it as visited, and execute step 6.1.3), otherwise execute step 6.1.6);

6.1.6) Check whether the element in the stack is empty, if so, end the execution, otherwise, pop the top node of the stack and set it as unvisited, and execute step 6.1.5);

6.2) Calculate the execution time on each path. The specific calculation method is: firstly, multiply the execution time of each basic block on each path by the execution times of the corresponding basic blocks, and then accumulate and sum to obtain the execution time on this path. time;

6.3) Find the maximum value of execution time on all paths, that is, the maximum execution time shown in FIG. 1 , and the maximum execution time is the WCET of the program.

In summary, it is not difficult to see that through static analysis of the DSP engineering assembly code, the worst execution time can be obtained without running the DSP program, which overcomes the disadvantages of running the program to obtain the measured value samples in the traditional method, and is easy to implement and operate. Simple; use the distribution function-based method to estimate WCET, bypass the complex underlying hardware characteristics, solve the problem of modeling the underlying hardware characteristics in traditional methods, and have the advantage of being easy to implement; use the concept of basic blocks to automatically construct program flow graphs , analyze the execution time of each node in the program flow graph and the path of the program flow graph, and obtain the WCET of the program with less manual intervention, which solves the problem of requiring a lot of manual intervention in the traditional method; using the improved PERT technology, It solves the irrationality problem of the beta distribution parameter estimation method in the traditional PERT technology, and makes the estimation of the basic block execution time more accurate.

Claims (7)

1. A Worst Execution Time WCET fast estimation method based on distribution function, is characterized in that, comprises the following steps: 1), read the DSP project disassembly file: use TI's disassembly tool to disassemble the target file compiled by the DSP project to obtain the disassembly file F of the DSP project; 2) Obtain the divided basic block set B: According to the characteristics of the DSP disassembly file and the rules of basic block division, analyze the disassembly file F line by line, obtain each basic block divided, and obtain the basic block set B of the program; 3), identify the relationship between the basic blocks in the basic block set B, and construct the program flow graph C; 4) Calculate the execution time T of each basic block; 5), using the basic block execution time T and the basic block execution times Ts as the weighted program flow diagram Cw; 6), analyze the weighted program flow graph Cw, obtain the path with the largest total weight, and use the largest total weight as the worst execution time WCET of the program; The concrete process of described step 4) is: 4.1) Calculate the expected value μ _i and variance σ _i ² of the running time of each instruction According to PERT, the running time of each DSP assembly instruction is simulated with the improved PERT to obtain its expected value and variance, that is, the expected value μ _i of the running time of each DSP instruction is calculated by using the approximate formula of Perry-Greig expected value, and Person -Turkry variance approximation formula calculates the variance σ _i ² of the running time of each DSP instruction, and the specific calculation formulas are: μ _i =0.630m _i +0.185(b _i +a _i ), σ _i ² =0.630(m _i -u _i ) ² +0.185[(b _i -u _i ) ² +(a _i -u _i ) ² ], In the formula, b _i represents the peak value of the running time of each instruction, a _i represents the valley value of the running time of each instruction, and _mi represents the most likely value of the running time of each instruction. According to the experimental analysis, take The value range of i is [1-N], and N is the number of basic block instructions; 4.2) Screen parallel instructions There may be instructions executed in parallel in the basic block, and the instruction parallelism needs to be analyzed, so that the estimated execution time of the basic block is more accurate, according to the expected value μ _i and variance σ of the running time of each instruction obtained in step 4.1) _i ² , combined with the instruction parallelism, to filter and obtain the instruction information that finally participates in the instruction superposition operation, specifically: F _j = max(t ₁ ,L,t _k ,L,t ₈ ), Among them, t _k represents the execution time of the kth instruction in each parallel execution block in the basic block, and the value range of k is [1-8], because only 8 instructions can be executed in parallel in TI DSP, and max is Take the maximum value operation, t _k =A _k +2S _k , A _k is the expected value of the execution time of the instruction in the basic block corresponding to the kth instruction in the parallel execution block, and S _k is the corresponding basic block of the kth instruction in the parallel execution block The variance of the execution time of the instruction, F _j represents the execution time of each parallel execution block in the basic block, the value range of j is [1-M], and M represents the number of parallel execution blocks contained in the basic block; 4.3) Calculate the mean value μ and variance σ ² of the execution time of the basic block. The specific calculation formulas are: $\mathrm{<span\; class="notranslate">\; \&mu;</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; \&mu;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ,</span>$ ${\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{<span\; class="notranslate">\; \&Sigma;</span>}}{{\mathrm{<span\; class="notranslate">\; \&sigma;</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; ;</span>$ Where μ _j represents the expected value of the instruction running time corresponding to F _j , and σ ² _j represents the variance of the instruction running time corresponding to F _j ; 4.4) Get basic block execution time T After obtaining the mean and variance of the execution time of the basic block, given the time t, you can calculate P(T'≤t), that is, the probability that the execution time of the basic block is not greater than a given value; For the normal distribution X:N(μ,σ ² ), there are the following facts: P(t≤μ+σ)=84.15%, P(t≤μ+2σ)=97.7%, P(t≤μ+3σ)=99.85%; In this example, T=μ+2σ is taken as the execution time of the basic block. 2. the worst execution time WCET fast estimation method based on distribution function as claimed in claim 1, is characterized in that: the concrete process of described step 2) is: 2.1) Determine the entry statement of each basic block in the basic block set B: Read one line of assembly code from the first line of the disassembly file F, judge whether the line is the entry statement of the basic block, if so, then judge the line as the entry statement of the basic block, and record the basic block simultaneously The address corresponding to the entry statement in the disassembly file F; otherwise, continue to read and analyze the next line until the end of the file F; 2.2) Judge the exit statement of each basic block in the basic block set B: read a line of assembly code from the first line of the disassembly file F, and judge whether it is the exit statement of the basic block, if so, record the exit statement of the basic block in The corresponding address in the disassembly file F; otherwise, continue to read and analyze the next line until the end of the file F; 2.3) Determine the range of each basic block: The basic block is composed of an assembly statement sequence between the entry statement and the exit statement. After determining the scope of each basic block, each basic block is sequentially labeled as 1, 2, 3...n, n≥1 ; So far, the basic block set B is obtained. 3. the worst execution time WCET fast estimation method based on distribution function as claimed in claim 1, is characterized in that: the concrete process of described step 3) is: obtain according to dividing basic block, basic block label, basic block entry The address corresponding to the statement and the address corresponding to the exit statement obtain the relationship between each basic block, thereby obtaining the program flow diagram of the assembly code; Determining the relationship between each basic block is mainly to judge whether each basic block is reachable, if reachable, there is a relationship between the basic blocks, otherwise there is no relationship, the specific judgment method is as follows: 3.1) If the exit statement of the basic block i is a transfer statement, and the target address of the transfer statement is equal to the address corresponding to the entry statement of the basic block j, then i can reach j; 3.2) If the exit statement of basic block i is a conditional transfer statement, and the address corresponding to the exit statement plus 4 is equal to the address corresponding to the entry statement of basic block k, then i can reach k; 3.3) If the exit statement of basic block i is an unconditional transfer statement, and the address corresponding to the exit statement plus 4 is equal to the address corresponding to the entry statement of basic block k, then i can reach k, but at this time basic block k is in basic block i , execute after the basic block j; 3.4) If the exit statement of the basic block i is not a transfer statement, and the address corresponding to the exit statement of the basic block plus 4 is equal to the address corresponding to the entry statement of the basic block m, then i can reach m; In this way, the relationship between each basic block can be determined, and described and stored by the directed graph based on the adjacency list in the data structure, and each basic block is used as each node in the directed graph to obtain the program flow graph C. 4. the worst execution time WCET fast estimation method based on distribution function as claimed in claim 1, is characterized in that: the specific process of described step 5) is, take basic block execution time and execution number of times as the weighted program of weight In the flow graph Cw, the execution times of the basic blocks need to be manually estimated and determined in advance. The specific implementation method is: add the basic block execution time and execution times information to the storage structure of each basic block in the program flow graph C, so as to obtain the weighted program flow graph Cw. 5. the worst execution time WCET fast estimation method based on distribution function as claimed in claim 1, is characterized in that: the concrete process of described step 6) is: 6.1) Use the depth-first algorithm to obtain each path of the weighted program flow graph Cw, the specific method is: 6.1.1) Determine the start point and end point of the program flow graph, the specific judgment method is: the start point is the first basic block of the program flow graph, that is, the basic block labeled 1; the end point is the entire basic block of the program flow graph A basic block with an out-degree of 0 in the block adjacency list; 6.1.2) Push the starting point onto the stack and set it as visited; 6.1.3) Determine whether the top node of the stack is the termination point, if so, execute step 6.1.4), otherwise execute step 6.1.5); 6.1.4) Save the elements in the stack, which are the nodes included in the path, and perform step 6.1.6); 6.1.5) Check whether there is any successor and unvisited node in the top node of the stack, if there is, select one of them and put it on the stack, and set it as visited, and execute step 6.1.3), otherwise execute step 6.1.6); 6.1.6) Check whether the element in the stack is empty, if so, end the execution, otherwise, pop the top node of the stack and set it as unvisited, and execute step 6.1.5); 6.2) Calculate the execution time on each path. The specific calculation method is: firstly, multiply the execution time of each basic block on each path by the execution times of the corresponding basic blocks, and then accumulate and sum to obtain the execution time on this path. time; 6.3) Find the maximum value of execution time on all paths, which is the WCET of the program. 6. the worst execution time WCET fast estimation method based on distribution function as claimed in claim 1, is characterized in that: the judgment criterion of the entry statement of described basic block is: 1. the first statement of program; 2. conditional transfer statement Or the statement that the unconditional transfer statement can transfer to; ③The statement immediately following the conditional transfer statement; ④The statement immediately following the unconditional transfer statement; If one of the above conditions is satisfied, it is judged as a basic block entry statement. 7. the worst execution time WCET fast estimation method based on distribution function as claimed in claim 1, is characterized in that: the judgment criterion of the exit statement of described basic block is: 1. that statement before the next basic block entry statement ; ②The termination statement of the assembly code, that is, if each line in the disassembly file F scanned and analyzed meets any one of the two conditions, it is considered as the exit statement of the basic block.