Exploiting Soft Computing for Real time performance

Abstract

The classic approach to the design of real time systems is to determine worst-case scenarios for the system statically and manually and then build the system with sufficient resources to meet deadlines and goals. This approach has worked well for traditional real time systems which operate in relatively simple, well-characterized environments. However the emerging generation of complex, dynamic and uncertain real time application domains accentuates the growing need for flexible, adaptable design approaches for real time systems. With the increasing complexity of real time systems, it is becoming infeasible to build systems with sufficient resources to meet the functional and timing requirements of all application tasks at all times. What is becoming increasingly important in the new paradigm of real time computing is the need to meet deadlines with sufficient system solution quality without having to design the system to support worst case program execution. In this thesis, we explore the possibility of exploiting "soft computing" properties of kernels to meet this objective. The chief characteristic of "soft computations" is the fact that they are able to provide cruder results before they complete, or they may execute for a long time refining an already adequate result. In other words, such computations are able to provide useful/incremental results before fully completing execution. More specifically they provide a trade-off between computation time and algorithm solution quality.

This thesis addresses the design issues involved in building a system that exploits the "soft computing" properties of kernels to optimize real time performance. In this context, we make the following contributions. Firstly we build a system prototype of a real time situational assessment scenario. We thereafter identify "soft computations" in the system and characterize the computation time/solution quality trade-off opportunities provided by them using performance profiles. Thirdly, we introduce a method to use performance profile based models at run time to determine the optimal composition of different "soft computations" in order to meet real time deadlines with sufficient system solution quality. We quantify the gains from our method both in terms of functional correctness of the system as well as CPU utilization as compared to conventional real time scheduling techniques. We observe that our dynamic scheduling scheme on an average is able to meet the system goals with 39% more accuracy with no missed deadlines as compared to conventional real time scheduling techniques for various design points that do not support worst case behavior. In addition, our method is able to meet the system objective while being highly utilized. Most importantly, our scheme exploits the soft computing properties of kernels to facilitate the design of the system at less aggressive design points while meeting deadlines and system goals at the same level as conventional real time design methodology. Finally, we perform an experimental study to understand the sensitivity of performance profiles to various input data parameters and identify the potential for online learning of performance profiles.