混合任务调度方法研究及其应用

杜姗姗，冯瑞

混合任务调度方法研究及其应用

杜姗姗，冯瑞

面向异构多核系统的任务调度问题一直是业内的研究热点，提出了一种动态任务调度与静态任务调度相结合的混合任务调度方法，结合视频大数据的实际应用特点，提出软实时任务的降级分配策略，并将提出的混合任务调度方法应用到校园车辆行踪管控系统中，实现了校内车辆的身份识别与行踪轨迹重构，并在交互系统中实时展现，同时，持用户统计查询等相关管理操作，经过实际部署与长时间运行，系统运行稳定，对校园内机动车实现了有效管控，满足了校内车辆管理的实际应用需求。

视频大数据；任务调度；分布式系统；视频监控；车辆行踪

0 引言

随着大数据尤其是视频图像等多媒体数据的处理速度被日益关注，多核异构并行计算将成为必然的发展趋势。针对视频大数据的在线分析处理难题，学术界和产业界提出了异构多核处理的解决方案。面向异构多核系统的任务调度问题一直是业内的研究热点，结合视频大数据的应用实际，也需要给出相对应的任务分配调度机制。本文提出一种动态任务调度与静态任务调度相结合的混合任务调度方法，结合视频大数据的实际应用特点，提出软实时任务的降级分配策略。并将提出的混合任务调度方法应用到校园车辆行踪管控系统中，实现了校内车辆的身份识别与行踪轨迹重构，并在交互系统中实时展现，同时支持用户统计查询等相关管理操作，经过实际部署与长时间运行，系统运行稳定，对校园内机动车实现了有效管控，满足了校内车辆管理的实际应用需求。

1 基于视频的管控系统中的任务分析

在视频大数据的实际应用场景中，尽管会部署数以千计的高清摄像机，每秒产生高达TB级的视频数据，但是，这些实时产生的视频大数据，真正有意义的数据可能仅占10%，甚至更少，因此，对所有视频流数据全部在线分析显然不是最优方案，通过对实际应用场景的深入理解，可总结视频分析任务特点如下：

（1）大部分视频流数据不需要在线精细分析：视频数据一般包括目标检测、身份识别、在线跟踪、事件推断等4个层面的分析任务，算法复杂程度也根据分析层面的不同呈递进趋势，比如针对大尺度区域范围的视频监控系统，部署的高清相机将数以百计，但需要完成所有4个层面分析任务的相机仅占很少的比例。绝大部分相机在大部分时间内将仅需要完成目标检测等相对计算复杂度较低的任务，当检测到有目标的时候，才会进行进一步的分析任务，而需要进行精细分析的摄像机往往是极少的一部分；

（2）很多视频流数据不需要在线分析：同样是区域范围的视频监控任务，会部署相当数量的带云台球机，这些摄像机将负责全局监控的枪机进行联动，当枪机发现可疑异常时，将指挥带云台球机实现监控目标的对焦，利用球机完成进一步的深度分析。因此，只有在枪机发现可疑异常的时候，这些球机的视频数据才需要进行分析处理。

（3）重点监控区域具有可变性和不确定性：对于大尺度的区域监控系统，重点防控的区域往往是少数，而且，防控区域的重要程度会根据时间、监控目标等因素会发生变化，这些都会直接影响视频数据处理的精细程度与任务截止期。而区域的重要程度一般都是通过人机交互方式在线指定，系统设计时无法提前预知。

因此，为了兼顾视频大数据分析性能与计算资源利用的最大化，混合任务调度方法是一种较好的方案，目的是采用最少的计算节点数量实现视频大数据的在线分析处理。

2 混合任务调度方法

混合任务调度是指在计算节点内的异构系统中采用为静态任务调度，并计算节点间的同构系统采用动态任务调度。采用混合任务调度时，在计算节点之间，系统根据任务类别有若干个专门的计算节点作为中心任务调度资源，每个中心任务调度器负责对若干个计算节点进行任务分配，某种类别的任务将首先到达相应的中心任务调度器，由它来做统一的任务调度，然后这些任务被分配给其负责的计算节点去运行任务。在计算节点内部没有任务调度器，CPU与GPU的计算任务被事先设计指定。这种混合任务调度方式既可以实现节点间任务的灵活调度，又可以实现节点内部资源可控，提高系统运行可靠性与任务完成的可控性。

2.1 计算节点内部采用静态任务调度

静态任务调度是指在多计算节点间的同构系统和节点内的异构系统的计算任务全部事先指定，根据视频分析任务的特点，将任务固定的分配给各计算节点与节点内部的GPU计算资源，每个计算节点负责一路或者多路视频数据的分析处理，如果是多路视频，采用轮询处理方式。优点是计算资源事先规划好，资源可控，可靠性好。缺点是灵活度不够，系统资源难以实现最大化利用。计算节点内部的静态任务调度方法根据实际的视频分析任务提前设计，一般将视频解码、特征提取等具有大规模重复简单计算的任务交由GPU完成，将分类器、输入输出等计算量较小的任务交由CPU处理。

2.2 计算节点间采用动态任务调度

动态任务调度是指计算节点间的同构系统和节点内的异构系统的计算任务全部动态调度，一般会有两个调度器，一个用于调度计算节点的任务，一个用于调度节点内部的任务，用于调度节点内部任务的调度器由该计算节点的CPU实现。优点是灵活性好，能根据视频数据的变化灵活调度各节点的计算任务，以及节点内部CPU、GPU的计算资源；缺点是可靠性较差，尤其是节点内部的资源调度，一旦任务的截止期无法在某个处理器上被满足，则要将该任务迁移到其他可以保证截止期的处理器上去运行，从而降低整体的运行效率，另外系统运行效率可控性较差。

2.3 软实时任务的降级分配策略

在分析视频大数据分析处理特点部分，明确指出，在视频大数据分析处理中，存在很多软实时任务，在进行系统任务设计时，应明确区分哪些任务属于硬实时任务，哪些任务属于软实时任务，并且对这些软实时任务进行服务等级划分，在软实时任务中，服务等级越高的任务，在满足硬实时任务被执行的前提下，应优先被执行，然而如果发现该任务在某个计算节点上运行无法满足其截止时间和资源需求时，则该任务的服务等级将被降级，这种降级策略将一直持续，直至该任务达到可分配的条件或服务等级已经减至最低，最坏情况是该任务被取消。

显然，这种降级策略是通过牺牲软实时任务的分析结果质量来提高整体任务的分配成功率，考虑到视频数据中绝大部分的任务为软实时任务，因此，也为视频大数据的在线处理提供了一种有效的解决思路。

2.4 硬实时任务和软实时的混合动态调度

计算节点间的动态任务调度方法可看成是实时分布式同构系统的动态任务调度，即对动态到达的有n个任务的任务集S，从中找出m个任务子集，将其分配给m个计算节点，每个任务在所分配的处理器运行时，针对硬实时任务，结合具体应用场景，在规定的时间和系统资源范围内完成，对于软实时任务，每个任务对应会有一个权重，在每个权重等级下，规定时间和系统资源能得到满足，这样就完成了任务集合S的完整任务调度。针对此类实时系统的动态任务调度问题，是学术界和业内公认的NP完全问题，不存在最优算法，在实际应用中，一般采用启发式算法解决。其中经典的调度算法是近视算法。

近视算法对一组动态到达，具有资源约束的实时任务所组成的任务集合进行启发式搜索。搜索树中的一个节点表示一个局部调度或任务集合一个可行调度。在任务搜索的过程当中，每次对当前的任务集合进行扩充前，都要对扩充后的任务集合进行可行性检查，以确认当前任务分配的合理性，只有通过了可行性检查，任务调度才可能发生。可行性检查的标准：如果当前任务分配被可行性检查任务集的人一个任务扩充后仍为可行的，则当前任务分配是可行调度，否则就是不可行任务。在近视算法中，每个任务都定义了一个目标函数H，H=任务截止期+任务最早可用时间*权重，每次选择目标函数最小（最优）的任务扩充当前任务集，如果当前调度不是可行调度，就要回溯到上层节点，重新选择目标函数次小（次优）的任务扩充任务集，为了限制搜索次数，算法定义最大回溯次数或目标函数的最大估算值，如果达到最大回溯次数或者目标函数达到了最大估算值，则停止回溯，相应的任务将被抛弃，表明没有找到一个可行的任务分配。近视算法选择一个新的任务扩充当前任务集合时，当多个计算节点都能满足新进任务的截止时间时，对计算节点的选择基于目标函数最优，实际上是选择最早可用时间最小的计算节点，没有考虑计算节点的最早可用时间与资源的最早可用时间之间的关系，一方面会导致计算节点处理时间的浪费，另一方面会影响任务分配的成功率。

为了克服近视算法的不足，有学者提出一种节约算法，其选择计算节点的策略是在满足新进任务截止时间的前提下，尽量延迟任务的开始运行时间，使得所选的计算节点最早可运行任务的时间尽可能接近任务截止时间，这样做的好处是计算节点最早可用时间可以被提前，使得新进任务有较早开始运行的机会，进而加大任务调度的成功率。但这种策略倾向于负载重的计算节点负载越重，负载轻的计算节点负载越清，因此，可能造成某些节点有较多的任务等待执行，某些节点没有分配任务，不利于算法性能的提高。

从搜索策略来看，近视算法和节约算法每次扩充任务集合的时候，都只是选择一项任务进行扩充，其结果是任务分配的预测性对整个任务集合S来说极其有限。为了提高任务分配的成功率，有学者提出采用批量任务分配策略，即每次不是分配一个任务，而是一批任务，通过提高任务分配集合的可预测性来提高任务分配的成功率。当然，这种方法仍然无法避免任务分配失败的情况，其根本原因是计算节点的不足，只能通过增加计算节点资源来提高任务分配的成功率。

3 校园车辆行踪管控系统

校园车辆行踪管控系统包含校内车辆的身份识别与行踪轨迹重构，并在交互系统中实时展现，同时支持用户统计查询等相关管理应用。

3.1 系统体系框架设计

本文所述校园车辆行踪管控系统由覆盖校园的1080P高清摄像机，用于动态任务分配调度的处理节点服务器、用于视频数据在线分析的多核异构计算设备、万兆网络交换机、用于信息展示用大屏幕、人机交互用客户端计算机组成，系统硬件组成，如图1所示：

图1 校园车辆行踪管控系统组成

管控系统需要对校园内经过的车辆实现检测与身份识别（包括车牌识别、车身颜色识别、车型识别、车标识别、车辆整体特征识别），为了提高身份识别精度，本系统架设的摄像机采用1080P（200万像素）的高清摄像机，采集1920 ×1080高清图像，如果每帧图像都在线进行分析处理，会导致视频分析计算资源的负荷较高，利用前述的混合任务分配方法，将高清视频数据计算任务动态分配给各多核异构计算节点，在计算节点内部利用GPU计算资源完成H.264视频解码和特征提取任务，利用CPU计算资源完成分类及节点内部管理任务（进程、线程、IO、传输等）。在视频数据传输方面，采用光纤、万兆交换机，以保证高清视频及时稳定传输。考虑到任务分配计算节点运算复杂度不高，但是对稳定性和可靠性要求很高，因此采用Intel至强CPU和服务器级别内存与硬盘，多核异构计算节点分析任务完成后将结果返回给该节点，采用Intel Haswell系列CPU，内部集成GPU计算资源，存储方面采用速度更快的SSD硬盘，在保证计算任务高效完成的基础上，有效降低成本。人机交互系统用于将校园车辆行踪状态结果和轨迹信息、地理信息等融合，并在用户端展示，同时支持用户对这些信息的查询和管理。

3.2 动态任务分配系统

车辆检测与身份识别系统运行在多核异构计算节点上，每个计算节点包括1个4核8线程CPU（Intel Haswell i7-4700EQ）和1个GPU(GT2 HD Graphics P4600)，为简单起见，对用于数据分析的CPU和GPU资源按70%测算，剩下的30%将包含网络传输、数据IO、数据交换等系统开销，以及为系统预留冗余资源。经实际系统测试，每个包含CPU和GPU的异构计算节点完成200万像素的高清视频分析所需的运行时间如表1所示：

表1 单计算节点每帧高清视频运行时间表

根据实际测算，集成GPU的计算性能与CPU计算能力相当，从表1中不难看出，如果所有分析任务都在CPU中完成，考虑到校园内车辆的车速较慢，按＜40km/h计算，则平均每秒钟处理5帧即可满足要求，则每个节点可处理约4路视频，加上GPU计算资源，可处理约8路视频。因此，GPU计算资源的加入，可使每个节点计算能力提高一倍。

在实际应用中，按每个摄像机内出现的车辆数量峰值为40辆/分钟，平均为10辆/分钟，针对摄像机的视频数据，每帧视频的解码与车辆检测任务都要完成，当有车辆时，都要进行车牌识别，目前全天候条件下车牌识别精度约为90%，在识别失败的10%车牌中包括车牌污损、无牌车、故意遮挡、光照影响等因素。如果车牌识别失败，则需要联合完成车身颜色和车标识别，目前根据车身颜色+车标识别对车辆的识别率约为80%，如果车身颜色与车标识别失败，则开始进行整体特征识别。按车辆数量峰值计算，一分钟将有1500帧（25帧/秒×60秒）图像完成解码与车辆检测任务，40帧图像需要完成车牌识别任务，4帧图像需要完成车身颜色与车标识别任务，整体特征识别车辆按1辆车/小时计算。如按平均通过车辆数计算，一分钟将有1500帧（25fps×60s）图像完成解码与车辆检测任务，10帧图像需要完成车牌识别任务，1帧图像需要完成车身颜色与车标识别任务，整体特征识别车辆按1辆车/小时计算。根据上述分析可知，车辆整体特征识别可不做考虑，峰值情况平均每帧视频需要70ms（40ms解码+检测，27ms车牌识别，1.5ms车身颜色+车标识别）。则每个计算节点可处理12路视频数据（每秒5帧，每个CPU核心可处理3路视频，一个节点4个CPU核可处理12路），加上GPU计算资源，计算性能增加一倍，则可以处理24路。

综上所述，针对本系统具有4个计算节点的情况下，可实现24路视频/节点×4个计算节点=96路高清视频的在线处理。除去视频解码与车辆检测任务都要处理，按96路高清视频流进行计算，峰值情况下，平均每秒会有64个车牌识别任务，6个车身颜色与车标识别任务，按200ms的任务截止期，则任务队列中平均情况会有14个任务，有4个计算节点，按照批量任务分配方法，即可完成各节点间的动态任务分配。

4 总结

本文提出一种动态任务调度与静态任务调度相结合的混合任务调度方法，结合视频大数据的实际应用特点，提出软实时任务的降级分配策略。并将提出的混合任务调度方法应用到校园车辆行踪管控系统中，实现了校内车辆的身份识别与行踪轨迹重构，并在交互系统中实时展现，同时支持用户统计查询等相关管理操作，经过实际部署与长时间运行，系统运行稳定，对校园内机动车实现了有效管控，满足了校内车辆管理的实际应用需求。

[1] 张丽.车辆视频检测与跟踪系统的算法研究[D].杭州:浙江大学,2003.

[2] Chafi, Hassan, et al. A domain-specific approach to heterogeneous parallelism. Proceedings of the 16th ACM symposium on Principles and practice of parallel programming. [M]ACM, 2011.

[3] Li, Hengjie, et al. SWAP: Parallelization through Algorithm Substitution. [J]IEEE Micro, 2012,32(2).

[4] A. Guha et al. [J]Systematic evaluation of workload clustering for extremely energy-efficient architectures. ACM SIGARCH Computer Architecture News, 2013, 41(2).

[5] D. Tiwari et al. Architectural characterization and similarity analysis of sunspider and Google’s V8 Javascript benchmarks. [C]Proceedings of International Symposium on Performance Analysis of Systems & Software, 2012.

[6] M. Ferdman et al. Clearing the cloud: a study of emerging scale-out workloads on modern hardware. Proceedings of International Conference on Architectural Support for Programming Languages and Operating Systems [C](ASPLOS), 2012.

Hybrid Task Schedule and Its Application

Du Shanshan, Feng Rui
(School of Computer Science, Fudan University, Shanghai 201203, China)

Multi-core heterogeneous systems oriented task scheduling problem has being a research focus in the industry, this paper proposes a dynamic task scheduling and the hybrid task scheduling method of combining static task scheduling, combining with the practical application characteristics of the of large video data, it proposes relegation for soft real-time task allocation strategy. The proposed hybrid task scheduling method is applied to the campus vehicle movement control system, which realizes the campus vehicle identification and whereabouts trajectory reconstruction and real-time display in the interactive system. Meanwhile it supports the relevant management operations like user statistics query. After the actual deployment and long time running, the system stably runs and effectively controls the motor vehicle on campus,. It meets the demand of the practical application of the campus vehicle management.

Large Scale Video; Task Schedule; Distributed System; Surveillance; Vehicle Trajectory

TP319

A

2014.11.23）

1007-757X(2015)01-0014-03

科技部支撑计划（2013BAH09F01）；上海市科委科技创新行动计划（14511106901）

杜姗姗（1983-），女，复旦大学计算机科学技术学院，上海视频技术与系统工程研究中心，硕士研究生，研究方向：计算机图像识别与

处理，上海，201203

冯 瑞（1971-），男，复旦大学计算机科学技术学院，上海视频技术与系统工程研究中心，副教授，研究方向：计算机图像识别与处理，上海，201203