Improved real-time scheduling of periodic tasks on multiprocessors

There is an increasing number of high-performance periodic real-time applications in areas such as control systems, autonomous robots and financial systems. This article presents a novel algorithm, called Notional Approximation for Balancing Load Residues (NABLR), for scheduling these applications on high-performance computing resources. The algorithm utilizes a combination of task residual loads and runtime laxities to carefully plan task execution between two consecutive job arrivals, so that available resources can be fully utilized and avoid deadline misses as possible. The empirical study in our article presented at the 2011 International Conference on High Performance Computing and Simulation (HPCS) was further extended by including additional static task sets and a new adaptive task set generated by our motivating application in brain-machine interfaces, which simulates the control of movement of a prosthetic limb according to activities of input signals. Out of 25,000 task sets, NABLR can schedule up to 76% of the sets versus 43% by the best known efficient algorithm (named anticipating slack earliest deadline first until zero laxity [ASEDZL]), while incurring significantly smaller overheads than those of a known optimal algorithm (on average, 80% fewer preemptions, migrations, and 75% fewer scheduler invocations), and being comparable to those of suboptimal schedulers (within only 12% more preemptions/migrations). Additionally, the evaluation results show that NABLR completes more task instances when compared with ASEDZL, which yields a greater system output accuracy. Copyright (c) 2012 John Wiley & Sons, Ltd.