Progress Report - 1

1 Background Reading

            I read a paper by Thomas Lundqvist and Per Stenstrom, An integrated Path and Timing analysis Method based on Cycle-Level Symbolic Execution           .

This paper presents a method that integrates path and timing analysis to accurately predict the worst case execution time. Till now i have only experimented with the timing analysis part. Thus, i will briefly talk about it. It extends traditional instruction level simulation technique with the capability to handle unknown data and with an extended semantics for all data manipulating instructions so that they function properly. This is known as symbolic level execution. I am basically stating the details of what I have mentioned before.

The load and stored need special treatment, since the reference address may be unknown. For load, thus, an unknown value will be loaded into the register. For stores, however, we might end up modifying an arbitrary memory location. Thus, we assign unknown to all memory locations.

When a conditional branch is encountered, whose branch condition is unknown, then both paths are simulated. And when branch condition is known then it excludes paths that can never be taken.

Path Analysis is further studied in detail by the authors. They describe further techniques in which the paths can be merged and thus this can reduce the complexity of iterating through loops.

2 Familiarization with Simplescalar

Simplescalar defines the various modules of a processor. The simulator starts with the execution of simulator.cc. Basically, the ROB (Input Buffers) stores the instructions in it. These are then executed one by one and go through the folllowing stages: Fetch stage, Decode, Execution, Memory Acess and Writeback.

We can specify how we want our pipeline to look like. As in how many execution units should be there etc. For now i have a very basic processor with: ROB = 4

3 Experiments

I did the following very simple experiment.

Wrote the following test file – test.c

int main()

{

     int a = 0;

     int b = 0;

     if( a = 0 )

       b = 1;

     else

       b = 2;

    return 0;

  }

Simulated it using the sslittle-na-sstrix-gcc and created a executable test. Then this was run on the Simplescalar simulator using sim_little. And a file called mt.base is created which contained the following information:

i)      Details of Simulation time

ii)    No. of Instructions

iii)   No. of cycles

iv)  Details about Instruction and Data Caches

v)    Processor details

The details can be seen here. 

4 Problems and Next Step

Problems during compiling and simulation lead to a little delay in the completion of the experimentation.

The very next step would be to, debug the executable using the simulator and put breakpoints and see the values of different registers at different points in the program. Then modify the simulator further so as to incorporate timing between ant two points. Also see how the simulator would deal with unknown values of inputs.

Further, i want to extend it to implement the path merging algorithms.

Back to Home Page