Schedulability analysis of acyclic processes

The paper describes the analysis of worst case execution times for a class of acyclic processes that can express precedence constraints and internal computational delays. The motivation for our work comes from hardware designs where a scheduler allocates exclusive access to a memory bus. Blocks that execute concurrently generate read and write requests. The timing of these requests may depend on factors such as bus contention, internal buffering, internal timing delays, and pipelining. Adaptations of our proposed method have enabled the verification of the timing performance of all subprocesses of an industrial MPEG-2 audio/video decoder chip. The method is accurate enough to produce guaranteed deadlines that are within 1% of those obtained through performance simulation