Randomized Algorithms: A System-Level, Poly-Time Analysis of Robust Computation

AbstractÐThis paper provides a methodology for analyzing the performance degradation of a computation once affected by perturbations. The suggested methodology, by relaxing all assumptions made in the related literature, provides design guidelines for the subsequent implementation of complex computations in physical devices. Implementation issues, such as finite precision representation, fluctuations of the production parameters, and aging effects, can be studied directly at system level, independently from any technological aspect and quantization technique. Only the behavioral description of the computational flow, which is assumed to be Lebesgue measurable and the architecture to be investigated are needed. The suggested analysis is based on the recent theory of Randomized Algorithms, which transforms the computationally intractable problem of robustness investigation in a poly-time algorithm by resorting to probability. Index TermsÐEmbedded system design, finite precision error analysis, randomized algorithms, sensitivity analysis, system level design. æ