Analyzing preemptive fixed priority scheduling of data flow graphs

A. Lele, O. Moreira, C.H. Berkel, van, J.P. Bastos, R. Almeida, P. Pedreiras

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
2 Downloads (Pure)


Data flow graphs can conveniently model embedded streaming applications (ESAs) that are typically implemented as networks of concurrent tasks having an iterative pipelined execution, where the activation of each task may be conditioned by intra- and inter-iteration data dependencies. We propose a novel analysis approach for preemptive Fixed Priority Scheduling (FPS) of multiple ESAs assuming a fixed mapping of tasks onto the processors of the underlying Heterogeneous Multi-Processor System-on-Chip (HMPSoC). The tasks of an ESA are event activated, have varying execution times, and participate in cyclic dependency chains such that they may not have an activation pattern that can be depicted using traditional periodic / sporadic event models. Instead we propose to characterize the data flow graphs of ESAs to upper bound the load they impose on a processor and use it to compute the worst-case response time of an actor executing on that processor at a lower priority. We show that ours is a generic approach for analyzing FPS of data flow graphs. We also propose a refinement of our technique for graphs with a dominant periodic source. We demonstrate our improvement over the state-of-the-art FPS analysis for data flow in our experiments.
Original languageEnglish
Title of host publication2014 IEEE 12th Symposium on Embedded Systems for Real-time Multimedia (ESTIMedia, Greater Noida, India, October 16-17, 2014)
PublisherInstitute of Electrical and Electronics Engineers
Publication statusPublished - 2014
Event12th IEEE Symposium on Embedded Systems for Real-time Multimedia (ESTIMedia 2014) - New Delhi, India
Duration: 16 Oct 201417 Oct 2014
Conference number: 12


Conference12th IEEE Symposium on Embedded Systems for Real-time Multimedia (ESTIMedia 2014)
Abbreviated titleESTIMedia 2014
CityNew Delhi
Internet address


Dive into the research topics of 'Analyzing preemptive fixed priority scheduling of data flow graphs'. Together they form a unique fingerprint.

Cite this