Worst Case Execution Time Analysis

Abstract: This project is around the Eclipse eTrice project. For embedded systems with hard real time constraints it is crucial to be able to guarantee upper bounds of execution times. The eTrice project provides an implementation of the ROOM (Real time Object Oriented Modeling) language which is an event-driven system where the typical scenario is one where an interrupt creates an event which is handled by a state machine. This can further create more events which are processed by other state machines and so on. The main aim of this project is to develop an abstract execution engine which computes the longest execution time for a given initial event i.e. the time from the first event to the time the system is idle again.

Detailed Information: The eTrice project provides an implementation of the ROOM modeling language together with editors and code generators for Java, C and C++. It is defined in textual form with graphical editors for the structural and behavioural parts and is implemented the Xtext parser generator and textual IDE framework. To ease the definition of structural composition and of hierarchical state machines there are graphical editors (based on Graphiti) which read and modify the main model. Layout information is kept in a separate model which adds no semantic information and can be deleted and re-built from scratch.
Additionally there is an aggregation model which is created by model transformation from the original models and which significantly simplifies the task of code generation.
All models (even the textual ones) are internally represented using EMF (Eclipse Modeling Framework).

The kind of system this project focuses on is event driven system. State machines (the behaviour of the so called Actors) communicate with each other through the Actor's Ports asynchronously (by message passing).

In a simplified setting we consider one thread only. This thread has one event queue. If a new event is put into the queue the thread will wake up and deliver it to its destination which is a Port which in turn will hand it over to its Actor. The actor will handle the event and might in turn send one or more new events. After this Actor is finished the event queue will dispatch all new events one by one until no new event is found and then the thread is put to sleep again.

This project aims to compute the maximum time needed by the system from the occurrence of the first event until the thread is idle again.

The resources required for this project will be only those required for plugin development in Eclipse. This project will require some familiarity with eTrice and its meta models: Room.ecore and etricegen.ecore. The major implementation of the project will depend on the data structure used and the algorithm written to compute the worst case execution time.

For developers in the Eclipse and eTrice community, this project will have the following benefits:

1. For hard real time analysis, knowing the worst case execution time (WCET) is very important for their schedulability analysis. If the WCET for a system is greater than any execution time that can occur in that system, the scheduler is forced to assign more time to tasks than required. Thus, it determines the precision of the schedulability analysis.

2. It provides an estimate of the upper bound which further gives an idea whether there is more need for improvement in the system.

3. It works as a tab for the programmers to keep a check on the depth of their system model and make improvements to improve the time wherever possible

Background: As mentioned above, familiarity with plugin development and the eTrice framework is the starting point for this project. The author has already gone through the given documentation for the same and also developed and tested a few sample projects of his own. He has also very good knowledge of algorithms that is the major requirement for this project. In the time leading up to the start of the GSOC programme, the author plans to develop more complex systems in eTrice to fully understand its capability and also design a basic data structure and algorithm to be used to implement the project.

Deliverables: The strategy that would be followed to complete the project will be to compute a tree of possible executions beginning with the initial event. The first actor handles that depending on its current state. That is the point where the possibilities occur and the tree branches. A depth first computation is performed by picking one of the possible states and handling the event. The events sent in response have to be queued and processed recursively. Along this tree then the maximum time can be computed.

In brief, the deliverables for this project will be

1. Designing the algorithm and data structure needed to compute the tree.

2. Implementing and testing the algorithm.

3. Making more experiments and improving the algorithm.

4. Designing and implementing a way to specify temporal constraints and basic execution times.

5. Designing and implementing a convenient way of user feedback.

Schedule: Taking all the deliverables and the resources required into account, the following milestones are expected to be met during the actual implementation of the project.

Till April 23: Increase familiarity with eTrice and ROOM

April 23: Student proposal application finalised.

April 23 – May 21: Interact with mentor and also start designing the

algorithm and data structure needed.

May 21 – June 2: Implement and test the algorithm

June 3 – June 23: Make more experiments and improve the algorithm.

June 24 – July 8: Finalize build for mid-term evaluation

July 9 – July 13: Mid-term Evaluation

July 14 – July 28: Design a way to specify temporal constraints

July 29 – August 12: Design a user feedback system.

Aug 13 – Aug 20: Code clean up and final documentation of project

Aug 24: Final Evaluation.

My college exams will be finishing on the 2nd of May and my new session is starting from the 13th of August. As is clear from the schedule above, these dates should not interfere with my development of the project.

Expectations: My expectation out of this project is to learn and learn a lot from my mentor and from The Eclipse foundation.

Contact Info:

Name – Harjoben Singh

Contact - +65-98382053

Email – y090018@e.ntu.edu.sg

Address – 65-1-1338, hall of residence 14

34 Nanyang Crescent

Singapore – 637634

I’m a Computer Engineering undergraduate student pursuing my penultimate year from the Nanyang Technological University, Singapore. I’m well versed in Java and C++. I have a basic idea of EMF and plugin development in Eclipse. Last semester, I was interning at IBM, Singapore to develop a 2-factor authentication system from them. I’m currently a Microsoft Student Partner and have developed a couple of Android and Windows Phone apps in my free time. I feel that algorithms are my strong point and hence, believe that this project is just right for me and I can give my best to it in the summers, if approved.