Optimization Of Error Detection In Embedded Systems

Abstract: This thesis deals with algorithms that optimize the implementation of the error detection technique for soft real-time and multimedia applications in order to minimize their average execution times. We aimed to design the algorithms such that with little hardware available we could achieve maximum time gain. In the context of electronic systems implemented with modern semiconductor technologies transient faults have become more and more frequent. Factors like high complexity, smaller transistor sizes, higher operational frequencies and lower voltage levels have contributed to the increase in the rate of transient faults in modern electronic systems. As error detection is needed, no matter what tolerance strategy is applied, the detection mechanisms are always present and active. Unfortunately, they are also a major source of time overhead. In order to reduce this overhead designers try to implement error detection in hardware, but this approach increases the overall cost of the system. In general there are three approaches to implement the error detection technique. One extreme implementation involves software only and another extreme implementation involves hardware only.  But we focus on the mixed one which involves both hardware as well as software, in order to generate the best system performance with minimal costs. To reduce the time overhead and to achieve maximum time gain, we place as much as possible of the checking expressions in hardware depending on the available resources. The decision is taken based on the frequency information obtained from an execution profile of the program. To achieve our goal we have formulated the problem as a knapsack problem, for which we proposed two algorithms.  The first one is a greedy approach and the second one finds the optimal solution using dynamic programming. To compare the result for these two algorithms and evaluate their efficiency we have run a series of experiments considering applications with different number of detectors and checking expressions. We have also run our optimization on a real-life application (GSM encoder) to see the how these algorithms perform under real-life scenarios. The experimental evaluation has proved the efficiency of our algorithms under different scenarios. Our optimization reduces the time overhead incurred by the error detection component in systems with tight resource constraints. The results presented in this thesis can be used as a foundation for future research in the area. For example, our algorithms could be extended to consider partially dynamically reconfigurable FPGAs or they could be extended so that they give probabilistic guarantees (and could be used in hard real-time systems).