On the scheduling of fork-join parallel/distributed real-time tasks

Ricardo Garibay-Martinez, Geoffrey Nelissen, Luis Lino Ferreira, Luis Miguel Pinho

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

9 Citations (Scopus)

Abstract

Modern real-time embedded applications present high computation requirements which need to be realized within strict time constraints. The current trend towards parallel processing in the embedded domain allows providing higher processing power. However, in some embedded applications, the use of powerful enough multi-core processors, may not be possible due to energy, space or cost constraints. A solution for this problem is to extend the parallel execution of the applications, allowing them to distribute their workload among networked nodes, on peak situations, to remote neighbour nodes in the system. In this context, we present the Partitioned-Distributed-Deadline Monotonic Scheduling algorithm for fork-join parallel/distributed fixed-priority tasks. We study the problem of scheduling fork-join tasks that execute in a distributed system, where the inherent transmission delay of tasks must be considered and cannot be deemed negligible, as in the case of multicore systems. Our scheduling algorithm is shown to have a resource augmentation bound of 4, which implies that any task set that is feasible on m unit-speed processors and a single shared real-time network, can be scheduled by our algorithm on m processors and a single real-time network that are 4 times faster. We confirm through simulations our analytical results.

Original languageEnglish
Title of host publication2014 International Conference on Engineering, Technology and Innovation
Subtitle of host publicationEngineering Responsible Innovation in Products and Services, ICE 2014
PublisherIEEE Computer Society
Pages31-40
Number of pages10
ISBN (Print)9781479940233
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event9th IEEE International Symposium on Industrial Embedded Systems, SIES 2014 - Pisa, Italy
Duration: 18 Jun 201420 Jun 2014

Publication series

NameProceedings of the 9th IEEE International Symposium on Industrial Embedded Systems, SIES 2014

Conference

Conference9th IEEE International Symposium on Industrial Embedded Systems, SIES 2014
CountryItaly
CityPisa
Period18/06/1420/06/14

Keywords

  • distributed systems
  • fork-join
  • parallel execution
  • real-time
  • Resource augmentation bound

Fingerprint Dive into the research topics of 'On the scheduling of fork-join parallel/distributed real-time tasks'. Together they form a unique fingerprint.

  • Cite this

    Garibay-Martinez, R., Nelissen, G., Lino Ferreira, L., & Pinho, L. M. (2014). On the scheduling of fork-join parallel/distributed real-time tasks. In 2014 International Conference on Engineering, Technology and Innovation: Engineering Responsible Innovation in Products and Services, ICE 2014 (pp. 31-40). [6871184] (Proceedings of the 9th IEEE International Symposium on Industrial Embedded Systems, SIES 2014). IEEE Computer Society. https://doi.org/10.1109/SIES.2014.6871184