A semi-partitioned approach for parallel real-time scheduling
A semi-partitioned approach for parallel real-time scheduling
复制标题
一种并行实时调度的半分区方法
DOI：
10.1145/2392987.2393006
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
J. Goossens
中科院分区：
文献类型：
--
作者：
Benjamin Bado;L. George;P. Courbin;J. Goossens
在本文中，我们考虑的问题，调度周期多阶段多线程任务的一组m个相同的处理器上的最早期限优先（EDF）调度。每个周期性任务都由一系列具有偏移的阶段定义，这些阶段可以并行化。我们使用分区半分区的方法，在分配给每个阶段的本地最后期限迁移。我们扩展这种方法，以考虑相位并行。我们考虑的阶段并行性是流行的作业并行性的扩展。一个阶段，如果是可并行的，可以被分解成在可配置数量的处理器上运行的并行线程。我们只需要在一个窗口内同时执行线程，该窗口等于其相关阶段的本地截止日期。为了决定多阶段多线程任务的可并行性，我们扩展了流行的单处理器EDF周期异步任务的可行性条件。我们提出了两个新的可扩展性测试EDF显着改善著名的梁和Merill可行性测试的基础上的可行性区间[Omin，Omax + 2P]，其中Omin和Omax分别是最小和最大的相位偏移和P的任务周期的最小公倍数。当需要EDF仿真时，使用第一个可扩展性测试，并且通过仿真，在仿真速度上获得44%的增益。第二种方法提供了一个充分的可扩展性测试的时间间隔长度为P的基础上的需求约束函数。最后，我们研究了三个局部的最后期限分配算法分配到可并行化的阶段。通过仿真比较分析了这三种局部截止期分配算法的性能。
In this paper, we consider the problem of scheduling periodic Multi-Phase Multi-Thread tasks on a set of m identical processors with Earliest Deadline First (EDF) scheduling. Each periodic task is defined by a sequence of phases with offsets that can be possibly parallelized. We use a portioned semi-partitioned approach with migrations at local deadlines assigned to each phase. We extend this approach to take into account phase parallelism. The phase parallelism we consider is an extension of the popular job parallelism. A phase, if parallelizable, can be decomposed into parallel threads run on a configurable number of processors. We only require simultaneous execution of threads inside a window equal to the local deadline of their associated phase. To decide on the schedulability of a Multi-Phase Multi-Thread task, we extend the popular uniprocessor EDF feasibility condition for periodic asynchronous tasks. We propose two new schedulability tests for EDF that significantly improve the well known Leung and Merill feasibility test based on the feasibility interval [Omin, Omax + 2P], where Omin and Omax are respectively the minimum and maximum phase offsets and P the least common multiple of the task periods. The first schedulability test is used when an EDF simulation is needed and gives, by simulation, a 44% gain in simulation speed. The second method provides a sufficient schedulability test with a time interval of length P based on the demand bound function. Finally, we study three local deadline assignment heuristics assigned to parallelizable phases. We compare and analyze the performances obtained by simulation for those three local deadline assignment heuristics.