liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Optimization Of Error Detection In Embedded Systems
Linköping University, Department of Computer and Information Science, ESLAB - Embedded Systems Laboratory.
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 30 credits / 45 HE creditsStudent thesis
Abstract [en]

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).

Place, publisher, year, edition, pages
2011. , 53 p.
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-64395ISRN: LIU-IDA/LITH-EX-A—10/053—SEOAI: diva2:390227
2011-01-17, John von Neumann, Linköping University, Linköping, 15:00 (English)
Available from: 2011-01-21 Created: 2011-01-21 Last updated: 2011-01-21Bibliographically approved

Open Access in DiVA

fulltext(1534 kB)343 downloads
File information
File name FULLTEXT01.pdfFile size 1534 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Muhammad Hassan, Syed
By organisation
ESLAB - Embedded Systems Laboratory
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 343 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 340 hits
ReferencesLink to record
Permanent link

Direct link