Lab 4: Execution Time Analysis

Expected effort: < 4h

In this lab assignment, you will estimate the execution time (worst and best) for a simple program using control-flow graphs (CFG) and integer linear programming (ILP). The assignment uses free online tools as well as an ILP solver installed on the login.student.lth.se Linux machines you can access via ssh, for instance.

Tools

As input, you are given a C program that has to be compiled for the CPU architecture used. The analysis will focus on a specific function or functions. These functions need to be examined in their machine instruction format and split into basic blocks (BB) connected into a CFG. For these steps, it is possible to use any number of tools - e.g. gcc, objdump, radare2, ghidra,… but an easy-to-use option is the online Compiler Explorer Links to an external site.. Using this you should be able to compile the code and get its CFG of BBs similar to the figure below:

Note that you may change the target architecture from the droplist above the assembly code window. Note also that you can display the CFG by selecting Graph output from the + droplist of the assembly code window. In this graph view, you can also zoom in/out and move your BB around to see how they connect.

Once you have the CFG and BBs you can write down the system of equations as in section 16.4 from the Lee & Seshia book. This system should be solved somehow. Again, you can use any method of solving this, but we do recommend you use the lp_solve tool already available on the student Linux machines. This solver can use any number of input formats including text files Links to an external site.  looking as follows:

/* ex16.lp
   example 16.10 in Lee&Seshia book for EDAN15
*/

/* Looking for WCET. BB time is ~size in bytes for this particular case */
max: 27 x1 + 2 x2 + 10 x3 + 16 x4 + 31 x5 + 4 x6;

x1 = 1;
x6 = 1;
x1 = d12;
x2 = d12 + d52;
x2 = d23 + d26;
x3 = d23;
x3 = d45;
x4 = d34;
x4 = d45;
x5 = d35 + d45;
x5 = d52;
x6 = d26;

x3 <= 32;

int x1,x2,x3,x4,x5,x6;

Solving this optimization problem amounts to calling lp_solve ex16.lp in your student shell, which should output:

$ lp_solve ex16.lp 

Value of objective function: 1921

Actual values of the variables:
x1                              1
x2                             33
x3                             32
x4                             32
x5                             32
x6                              1
d12                             1
d52                            32
d23                            32
d26                             1
d45                            32
d34                            32
d35                             0

WARNING: The documentation for the lp_solver (linked above) states that there is no semantic difference between '<' and '<=' or between '>' and '>='. Use the versions with '=' as your goto semantics.

Your Task

Estimate the WCET and BCET in clock cycles for function rotate in the C program below. Use a x86-64 clang 12.0.0 compiler for an x86-64 machine. Examine the CFG, derive the system of equations, and solve them to get BCET and WCET.

You can start by assuming each of the BBs executes in one clock cycle and solve your ILP problem. Write down the number of times each of your BBs is executed for both WCET and BCET.

You may then move on and assign weights to each of the BBs to model their execution time. Update your ILP models and solve them again. Make reasonable assumptions about the number of clock cycles for the instructions: e.g. one clock cycle per machine instruction (is this reasonable?). You should assume all instructions and data are already available in the caches (no cache misses) - so the cache will not play a role in your estimates. What other uncertainties are there in your estimations?

Note: for this assignment you do not need to understand what the different machine instructions do, only to make some assumptions about the number of clock cycles each BB takes to execute.

#include <stdio.h>
#include <string.h>

void rotate(const char *c, char* s){
    while(*c!='\0'){
        *s=*c;
        if(*c>='a' && *c<='z'){
            *s=((((*c)-'a')+13)%26)+'a';
        }
        if(*c>='A' && *c<='Z'){
            *s=((((*c)-'A')+13)%26)+'A';
        }
        c++; s++;
    }
}
     
int main(int argc, char* argv[]) {
    char s[41];
    memset(s, 0, 41);
    if(argc != 2) {
        printf("Usage: %s 'string to rot13'\n", argv[0]);
        return -1;
    }
    int sl = strlen(argv[1]);
    if(sl < 5 || sl > 40) return -2;
    rotate(argv[1],s);
    printf("%s",s);
    return 0;
}

The code above produces the ROT13 encoding of a string. An example of use (compiled with gcc -o rot13 rot13.c):

./rot13 'rot13 is easy!'
ebg13 vf rnfl!

Results To Show

• your ILP formulation
• your WCET for when the time for every BB = 1
• your BCET for when the time for every BB = 1
• your WCET for more realistic BB time figures and
• an example input (a string) using the rotate function causing WCET
• your BCET for more realistic BB time figures and
• an example input (a string) using the rotate function causing BCET