Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!gillies From: gillies@m.cs.uiuc.edu Newsgroups: comp.realtime Subject: Re: Predicting Execution Times for Proc Message-ID: <70900012@m.cs.uiuc.edu> Date: 10 Apr 90 07:05:00 GMT References: <765@telesoft.com> Lines: 52 Nf-ID: #R:telesoft.com:765:m.cs.uiuc.edu:70900012:000:2759 Nf-From: m.cs.uiuc.edu!gillies Apr 10 02:05:00 1990 > A brief examination of the 68020 instruction times pointed out a _wide_ > variation in instruction timings, depending on cache hits. Obviously, > normal multi-tasking operations such as preemption will wreak havoc with > cache hits at unpredictable times. Although I don't actually designing real-time systems (I just research scheduling), my rather extreme opinion is that the 68020 is a bullsh*t processor for implementing real-time systems. Even if you disable the 68020's caches, you still must worry that your runtime data may be misaligned in memory. The 68020 will happily compensate for this, slowing down your program considerably. In my opinion, you should stop thinking about the 68020 for real-time systems, and start thinking about highly deterministic RISC processors such as the R2000, or perhaps the MC88000. -------------------------------------------------------------------- Now here's a plug for our group's research. In some hard real-time systems, researchers have advanced the idea that if a task runs longer than its predicted execution, an error exception should be raised in the task. This exception must be handled and an "acceptable" result produced very quickly after the exception is raised. One way to do this is to have a "primary" (long) algorithm trying to get the best possible result, and a "fallback" algorithm that kluges something quickly when the system determines the primary algorithm is taking too long. Another way to do this is to use an algorithm whose results converge monotonically toward the optimal solution. At first a "mandatory" result is produced. Later, intermediate "optional" results are recorded. If the timer expires, the most accurate result yet computed becomes the final result. This type of system has been dubbed the "imprecise computation model" in the literature. Supposedly, this type of system can soak up 100% of the processor cycles, and behaves especially well under transient overloads, as long as the initial "mandatory" results can be produced quickly. I.e. during a transient overload, the system produces a bunch of crappy results in compensating for the transient, but presumably the system's design specification can tolerate very coarse accuracy for short periods of time, thus the system survives and continues to meet its real-time constraints. Perhaps later, precision increase to "make up" for the sloppiness during transient overload. Of course, both of these paradigms depend on being able to recast your entire real-time system into this framework, which may be very difficult. Don Gillies, Dept. of Computer Science, University of Illinois 1304 W. Springfield, Urbana, Ill 61801 ARPA: gillies@cs.uiuc.edu UUCP: {uunet,harvard}!uiucdcs!gillies