TY - JOUR
T1 - CPMD-mindful task assignment for NPS-F
AU - Nelissen, Geoffrey
AU - Bletsas, Konstantinos
AU - Goossens, Joël
PY - 2014/10/22
Y1 - 2014/10/22
N2 - The multiprocessor scheduling scheme NPS-F for sporadic tasks has a high utilisation bound and an overall number of preemptions bounded at design time. NPS-F binpacks tasks offline to as many servers as needed. At runtime, the scheduler ensures that each server is mapped to at most one of the m processors, at any instant. When scheduled, servers use EDF to select which of their tasks to run. Yet, unlike the overall number of preemptions, the migrations per se are not tightly bounded. Moreover, we cannot know a priori which task a server will be currently executing at the instant when it migrates. This uncertainty complicates the estimation of cache-related preemption and migration costs (CPMD), potentially resulting in their overestimation. Therefore, to simplify the CPMD estimation, we propose an amended bin-packing scheme for NPS-F allowing us (i) to identify at design time, which task migrates at which instant and (ii) bound a priori the number of migrating tasks, while preserving the utilisation bound of NPS-F.
AB - The multiprocessor scheduling scheme NPS-F for sporadic tasks has a high utilisation bound and an overall number of preemptions bounded at design time. NPS-F binpacks tasks offline to as many servers as needed. At runtime, the scheduler ensures that each server is mapped to at most one of the m processors, at any instant. When scheduled, servers use EDF to select which of their tasks to run. Yet, unlike the overall number of preemptions, the migrations per se are not tightly bounded. Moreover, we cannot know a priori which task a server will be currently executing at the instant when it migrates. This uncertainty complicates the estimation of cache-related preemption and migration costs (CPMD), potentially resulting in their overestimation. Therefore, to simplify the CPMD estimation, we propose an amended bin-packing scheme for NPS-F allowing us (i) to identify at design time, which task migrates at which instant and (ii) bound a priori the number of migrating tasks, while preserving the utilisation bound of NPS-F.
KW - Bin packing
KW - CPMD estimation
KW - Multiprocessor
KW - NPS-F
KW - Real-time scheduling
KW - Semi-partitioned
UR - http://www.scopus.com/inward/record.url?scp=84910116852&partnerID=8YFLogxK
U2 - 10.1007/s11241-014-9206-8
DO - 10.1007/s11241-014-9206-8
M3 - Article
AN - SCOPUS:84910116852
VL - 50
SP - 585
EP - 591
JO - Real-Time Systems
JF - Real-Time Systems
SN - 0922-6443
IS - 5-6
ER -