Task partitioning and priority assignment for distributed hard real-time systems

Ricardo Garibay-Martínez; Geoffrey Nelissen; Luis Lino Ferreira; Luís Miguel Pinho

doi:10.1016/j.jcss.2015.05.005

Task partitioning and priority assignment for distributed hard real-time systems

Ricardo Garibay-Martínez, Geoffrey Nelissen, Luis Lino Ferreira, Luís Miguel Pinho

Research output: Contribution to journal › Article › Academic › peer-review

7 Citations (Scopus)

Abstract

In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic that finds a feasible partitioning and priority assignment for distributed applications based on the linear transactional model. DOPA partitions the tasks and messages in the distributed system, and makes use of the Optimal Priority Assignment (OPA) algorithm known as Audsley's algorithm, to find the priorities for that partition. The experimental results show how the use of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the use of Deadline Monotonic (DM) usually favoured in other works. Afterwards, we extend these results to the assignment of Parallel/Distributed applications and present a second heuristic named Parallel-DOPA (P-DOPA). In that case, we show how the partitioning process can be simplified by using the Distributed Stretch Transformation (DST), a parallel transaction transformation algorithm introduced in [1].

Original language	English
Pages (from-to)	1542-1555
Number of pages	14
Journal	Journal of Computer and System Sciences
Volume	81
Issue number	8
DOIs	https://doi.org/10.1016/j.jcss.2015.05.005
Publication status	Published - 1 Dec 2015
Externally published	Yes

Funding

This work was partially supported by National Funds through FCT/MEC (Portuguese Foundation for Science and Technology) and when applicable, co-financed by ERDF (European Regional Development Fund) under the PT2020 Partnership, within project UID/CEC/04234/2013 (CISTER Research Centre); also by FCT/MEC and ERDF through COMPETE (Operational Programme ‘Thematic Factors of Competitiveness’), within project FCOMP-01-0124-FEDER-020447 (REGAIN); by FCT/MEC and the EU ARTEMIS JU within project ARTEMIS/0003/2012 – JU grant nr. 333053 (CONCERTO) and ARTEMIS/0001/2012 – JU grant nr. 332987 (ARROWHEAD); by FCT/MEC and ESF (European Social Fund) through POPH (Portuguese Human Potential Operational Program), under PhD grant SFRH/BD/71562/2010 .

Keywords

Distributed systems
Holistic analysis
Intermediate deadlines
Multi-threaded parallel tasks
Priority assignment
Real-time
Task allocation

Access to Document

10.1016/j.jcss.2015.05.005

Cite this

@article{a6ba89e471074ba6bbb70c07eb3afe8c,

title = "Task partitioning and priority assignment for distributed hard real-time systems",

abstract = "In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic that finds a feasible partitioning and priority assignment for distributed applications based on the linear transactional model. DOPA partitions the tasks and messages in the distributed system, and makes use of the Optimal Priority Assignment (OPA) algorithm known as Audsley's algorithm, to find the priorities for that partition. The experimental results show how the use of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the use of Deadline Monotonic (DM) usually favoured in other works. Afterwards, we extend these results to the assignment of Parallel/Distributed applications and present a second heuristic named Parallel-DOPA (P-DOPA). In that case, we show how the partitioning process can be simplified by using the Distributed Stretch Transformation (DST), a parallel transaction transformation algorithm introduced in [1].",

keywords = "Distributed systems, Holistic analysis, Intermediate deadlines, Multi-threaded parallel tasks, Priority assignment, Real-time, Task allocation",

author = "Ricardo Garibay-Mart{\'i}nez and Geoffrey Nelissen and Ferreira, {Luis Lino} and Pinho, {Lu{\'i}s Miguel}",

year = "2015",

month = dec,

day = "1",

doi = "10.1016/j.jcss.2015.05.005",

language = "English",

volume = "81",

pages = "1542--1555",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "8",

}

TY - JOUR

T1 - Task partitioning and priority assignment for distributed hard real-time systems

AU - Garibay-Martínez, Ricardo

AU - Nelissen, Geoffrey

AU - Ferreira, Luis Lino

AU - Pinho, Luís Miguel

PY - 2015/12/1

Y1 - 2015/12/1

N2 - In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic that finds a feasible partitioning and priority assignment for distributed applications based on the linear transactional model. DOPA partitions the tasks and messages in the distributed system, and makes use of the Optimal Priority Assignment (OPA) algorithm known as Audsley's algorithm, to find the priorities for that partition. The experimental results show how the use of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the use of Deadline Monotonic (DM) usually favoured in other works. Afterwards, we extend these results to the assignment of Parallel/Distributed applications and present a second heuristic named Parallel-DOPA (P-DOPA). In that case, we show how the partitioning process can be simplified by using the Distributed Stretch Transformation (DST), a parallel transaction transformation algorithm introduced in [1].

AB - In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic that finds a feasible partitioning and priority assignment for distributed applications based on the linear transactional model. DOPA partitions the tasks and messages in the distributed system, and makes use of the Optimal Priority Assignment (OPA) algorithm known as Audsley's algorithm, to find the priorities for that partition. The experimental results show how the use of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the use of Deadline Monotonic (DM) usually favoured in other works. Afterwards, we extend these results to the assignment of Parallel/Distributed applications and present a second heuristic named Parallel-DOPA (P-DOPA). In that case, we show how the partitioning process can be simplified by using the Distributed Stretch Transformation (DST), a parallel transaction transformation algorithm introduced in [1].

KW - Distributed systems

KW - Holistic analysis

KW - Intermediate deadlines

KW - Multi-threaded parallel tasks

KW - Priority assignment

KW - Real-time

KW - Task allocation

UR - http://www.scopus.com/inward/record.url?scp=84940447874&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2015.05.005

DO - 10.1016/j.jcss.2015.05.005

M3 - Article

AN - SCOPUS:84940447874

SN - 0022-0000

VL - 81

SP - 1542

EP - 1555

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 8

ER -

Task partitioning and priority assignment for distributed hard real-time systems

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this