Worst-Case and Best-Case Timing Analysis for Real-Time Embedded Systems with Limited Parallelism
Konstantinos Bletsas · 2007
Manufacturing advances throughout the last decade have led to a steady increase in the capacity of Field Programmable Gate Array (FPGAs). This development has in turn triggered the proliferation of mixed hardware/software implementations in the domain of embedded real-time systems. In such systems, part of the functionality of a process is implemented as software (running on a general-purpose processor core) and part of it is implemented by specialised co-processors, formed out of reconfigurable hardware logic. Such mixed systems are often the product of hardware/software codesign. Functions implemented in hardware nowadays are often complex and take up many clock cycles to execute. In that case, idling the processor while awaiting for the results of hardware computation would be inefficient. Instead, the processor is made available to other processes competing for it. Multiple processes may thus be executing simultaneously on a given instant – at most one on the processor, the rest in hardware. We term this behavior limited parallelism. For real-time systems, it is imperative that process deadlines be met even in the worst-case. Static timing analysis establishes upper bounds for worstcase process response times; a comparison of those bounds with the respective deadlines is a sufficient (but not necessary) test for schedulability. However, established timing analysis techniques (when applicable at all) are far from accurate when applied to limited parallel systems. Within this thesis, we formulate static analysis targeted at this class of systems which accurately characterises their timing behavior. Although this analysis stands out on its own merit, we note that is also suitable for use within a hardware/software codesign flow. This matters because mixed hardware/software systems are often developed via codesign.