混合任務調度方法研究及其應用

杜姍姍，馮瑞

混合任務調度方法研究及其應用

杜姍姍，馮瑞

面向異構多核系統的任務調度問題一直是業內的研究熱點，提出了一種動態任務調度與靜態任務調度相結合的混合任務調度方法，結合視頻大數據的實際應用特點，提出軟實時任務的降級分配策略，并將提出的混合任務調度方法應用到校園車輛行蹤管控系統中，實現了校內車輛的身份識別與行蹤軌跡重構，并在交互系統中實時展現，同時，持用戶統計查詢等相關管理操作，經過實際部署與長時間運行，系統運行穩定，對校園內機動車實現了有效管控，滿足了校內車輛管理的實際應用需求。

視頻大數據；任務調度；分布式系統；視頻監控；車輛行蹤

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