CPMD-mindful task assignment for NPS-F

The multiprocessor scheduling scheme NPS-F for sporadic tasks has a highutilisation bound and an overall number of preemptions bounded at design time. NPS-Fbinpacks tasks offline to as many servers as needed. At runtime, the scheduler ensuresthat each server is mapped to at most one of the m processors, at any instant. Whenscheduled, servers use EDF to select which of their tasks to run. Yet, unlike the overallnumber of preemptions, the migrations per se are not tightly bounded. Moreover, wecannot know a priori which task a server will be currently executing at the instant whenit migrates. This uncertainty complicates the estimation of cache-related preemptionand migration costs (CPMD), potentially resulting in their overestimation. Therefore,to simplify the CPMD estimation, we propose an amended bin-packing scheme forNPS-F allowing us (i) to identify at design time, which task migrates at which instantand (ii) bound a priori the number of migrating tasks, while preserving the utilisationbound of NPS-F