陸成剛 王安 王汗 洪榛

摘要：隨著視頻偵查手段在公安部門的日益推廣，為公安部門提供破案線索支持的視頻智能分析平臺也日益受到重視。任務(wù)調(diào)度機(jī)制作為視頻智能分析平臺的關(guān)鍵技術(shù)，必須保證視頻分析任務(wù)在不同計(jì)算節(jié)點(diǎn)間調(diào)度的合理性和有效性。論文提出了一種新的視頻分析平臺上的任務(wù)主動調(diào)度機(jī)制，減少了任務(wù)調(diào)度開銷，保證了任務(wù)總執(zhí)行時間，提升了視頻分析平臺的視頻分析效率。

關(guān)鍵詞：視頻分析 任務(wù)調(diào)度 主動調(diào)度

1 概述

隨著當(dāng)前智慧城市、平安城市等相關(guān)建設(shè)在各地的大力推廣，各地都建立了一定層次的視頻監(jiān)控網(wǎng)絡(luò)，為保證城市安全、維護(hù)社會穩(wěn)定起到了重要的作用。視頻偵查手段在公安部門的案件偵查、社會管理等業(yè)務(wù)中的重要性也日益突出，越來越受到各地公安部門的重視。然而隨著視頻監(jiān)控網(wǎng)絡(luò)建設(shè)的不斷推進(jìn)，公安部門在案件偵查過程中所需分析處理的案件視頻越來越多，人工對案件視頻進(jìn)行分析的難度也越來越大。

航天長峰為提升公安部門的視頻偵查水平，增進(jìn)公安部門的偵查辦案效率，建設(shè)了一套基于海量視頻的事件軌跡快速檢索平臺。該平臺通過多個進(jìn)行視頻分析的計(jì)算節(jié)點(diǎn)，對視頻進(jìn)行同步智能分析，為用戶提供諸如視頻智能摘要、目標(biāo)智能檢索的視頻分析服務(wù)，大大縮短了公安民警人工觀看視頻的時間，在多地的使用中取得了良好的效果。

該視頻分析平臺穩(wěn)定高效運(yùn)行所面臨的核心挑戰(zhàn)就是如何響應(yīng)用戶提出的視頻分析并發(fā)任務(wù)請求，并將其分配到合適的計(jì)算節(jié)點(diǎn)上加以分析，在用戶期望的時間內(nèi)向用戶返回結(jié)果。也就是說，如何對視頻分析任務(wù)實(shí)施合理的調(diào)度，形成視頻分析平臺的視頻分析任務(wù)智能調(diào)度機(jī)制，是系統(tǒng)實(shí)現(xiàn)的一大關(guān)鍵技術(shù)。

本文通過對視頻分析任務(wù)的特點(diǎn)加以分析，結(jié)合主動和被動調(diào)度思想，提出了一種新的任務(wù)調(diào)度機(jī)制，并在測試中驗(yàn)證了該機(jī)制的合理性和有效性。

2 視頻分析任務(wù)的特點(diǎn)

觀察視頻分析任務(wù)的運(yùn)行時間，可以發(fā)現(xiàn)視頻分析任務(wù)所需的運(yùn)行時間不確定性很高。其主要原因在于不同監(jiān)控視頻的分辨率、清晰度、目標(biāo)數(shù)目等眾多因素存在很大區(qū)別，而視頻分析任務(wù)的執(zhí)行時間受原始視頻的影響很大。這就造成視頻分析任務(wù)的時間很難預(yù)測，變化也很大。

記錄50次對同樣長度視頻進(jìn)行的視頻分析任務(wù)的執(zhí)行時間，結(jié)果如圖1所示。

由以上結(jié)果可見，對同樣長度視頻進(jìn)行的視頻分析的時間分布相當(dāng)隨機(jī)，不確定性很高。

學(xué)術(shù)界過去對任務(wù)調(diào)度問題的研究主要集中于任務(wù)執(zhí)行時間可以預(yù)測的情形[1]。例如LS、Min-Min等被動調(diào)度算法，它們都需要了解任務(wù)在計(jì)算節(jié)點(diǎn)上的預(yù)期計(jì)算時間，并基于此預(yù)期計(jì)算時間進(jìn)行調(diào)度。然而從上面的分析可見，視頻分析任務(wù)運(yùn)行時間很難在事先確定，因此很難利用被動調(diào)度算法對視頻分析任務(wù)進(jìn)行有效的調(diào)度。而必須根據(jù)視頻分析任務(wù)的實(shí)際情形，結(jié)合主動調(diào)度相關(guān)思想，提出創(chuàng)新的視頻分析任務(wù)調(diào)度機(jī)制。

3 視頻分析任務(wù)的調(diào)度機(jī)制

顯然視頻分析任務(wù)的調(diào)度機(jī)制應(yīng)當(dāng)保證在高并發(fā)、大任務(wù)量時將任務(wù)合理地分配到各個計(jì)算節(jié)點(diǎn)上。此時的任務(wù)調(diào)度既要保證任務(wù)在用戶的預(yù)期執(zhí)行時間內(nèi)完成，即最小化任務(wù)的執(zhí)行時間；也要保證不同計(jì)算節(jié)點(diǎn)的負(fù)載相對均衡，使得計(jì)算節(jié)點(diǎn)能夠有效地完成視頻分析任務(wù)；還要盡量減小任務(wù)調(diào)度自身的時間、網(wǎng)絡(luò)等開銷。

如前所述，視頻分析任務(wù)很難在任務(wù)執(zhí)行之前準(zhǔn)確預(yù)測執(zhí)行時間，也就導(dǎo)致視頻分析平臺難于利用被動調(diào)度相關(guān)算法進(jìn)行任務(wù)調(diào)度。具體而言，當(dāng)有大量任務(wù)同時到達(dá)時，視頻分析平臺很難由調(diào)度服務(wù)器自身決定應(yīng)當(dāng)將任務(wù)分配到哪一個計(jì)算節(jié)點(diǎn)上進(jìn)行計(jì)算，而必須利用主動調(diào)度策略，由計(jì)算節(jié)點(diǎn)在空閑時向調(diào)度服務(wù)器申請任務(wù)，完成相關(guān)功能。

但同時也注意到當(dāng)系統(tǒng)空閑時，在主動調(diào)度機(jī)制下，計(jì)算節(jié)點(diǎn)會占用大量網(wǎng)絡(luò)資源向調(diào)度服務(wù)器請求任務(wù)[2]。這既造成了網(wǎng)絡(luò)資源的浪費(fèi)，也不利于系統(tǒng)的穩(wěn)定、可靠運(yùn)行。由于在系統(tǒng)不繁忙時，大量的計(jì)算節(jié)點(diǎn)空閑，偶然出現(xiàn)的任務(wù)總是會被分配到計(jì)算能力最強(qiáng)的節(jié)點(diǎn)上。為了在系統(tǒng)空閑時能夠合理地減小調(diào)度開銷，則可以引入被動調(diào)度機(jī)制，由調(diào)度服務(wù)器直接決定任務(wù)分配的計(jì)算節(jié)點(diǎn)。

基于上述分析，設(shè)計(jì)視頻分析平臺的任務(wù)調(diào)度機(jī)制如圖2所示。

視頻分析平臺的任務(wù)調(diào)度機(jī)制的運(yùn)行流程如下：

①視頻分析平臺以主動模式開始運(yùn)行。此時，調(diào)度服務(wù)器的用戶請求處理模塊接收用戶請求，將其緩存于自身的用戶任務(wù)隊(duì)列中。

②計(jì)算節(jié)點(diǎn)的狀態(tài)監(jiān)測模塊開始運(yùn)行后就不斷跟蹤每一個用戶任務(wù)的處理，統(tǒng)計(jì)出計(jì)算節(jié)點(diǎn)的平均響應(yīng)時間，并結(jié)合自身的CPU、內(nèi)存和網(wǎng)絡(luò)帶寬的利用率以及網(wǎng)絡(luò)可達(dá)性，周期性（如每秒1次）地計(jì)算自身的負(fù)載容量。

③計(jì)算節(jié)點(diǎn)的主動調(diào)度模塊根據(jù)狀態(tài)監(jiān)測模塊的決策規(guī)劃，將自身的服務(wù)質(zhì)量信息以及負(fù)載容量反饋給調(diào)度服務(wù)器的計(jì)算節(jié)點(diǎn)監(jiān)測模塊，主動向調(diào)度服務(wù)器發(fā)出請求，要求獲得與其負(fù)載能力相當(dāng)?shù)囊曨l分析任務(wù)。

④調(diào)度服務(wù)器的調(diào)度模塊根據(jù)計(jì)算節(jié)點(diǎn)的運(yùn)行狀態(tài)，利用一定的調(diào)度算法決定應(yīng)當(dāng)分配給相應(yīng)計(jì)算節(jié)點(diǎn)的視頻分析任務(wù)。并將這些任務(wù)通過任務(wù)分發(fā)模塊分發(fā)給對應(yīng)的計(jì)算節(jié)點(diǎn)。

⑤計(jì)算節(jié)點(diǎn)在接收到視頻分析任務(wù)后，利用自身的視頻分析模塊進(jìn)行視頻分析，并根據(jù)視頻分析任務(wù)包含的任務(wù)來源等相關(guān)信息，直接將結(jié)果反饋給發(fā)出任務(wù)的用戶。

⑥調(diào)度服務(wù)器始終監(jiān)測所有計(jì)算節(jié)點(diǎn)的狀態(tài)，當(dāng)過去一段時間（如10分鐘）內(nèi)所有的計(jì)算節(jié)點(diǎn)都處于空閑狀態(tài)，則通知所有計(jì)算節(jié)點(diǎn)轉(zhuǎn)入被動調(diào)度模式。在被動模式下，計(jì)算節(jié)點(diǎn)的狀態(tài)監(jiān)測功能退化為簡單的心跳功能，只在每隔較長的一段時間（如10分鐘）時向調(diào)度服務(wù)器發(fā)送心跳確認(rèn)在線。當(dāng)調(diào)度服務(wù)器在被動調(diào)度模式下收到任務(wù)時，在計(jì)算節(jié)點(diǎn)中選取合適的計(jì)算節(jié)點(diǎn)進(jìn)行處理，同時喚醒所有計(jì)算節(jié)點(diǎn)，將視頻分析平臺重新切入主動調(diào)度模式，即轉(zhuǎn)入第1步。

可以看出，在上面的任務(wù)調(diào)度流程中，分別牽涉到被動模式下和主動模式下的任務(wù)調(diào)度算法，即在被動模式下如何選擇合適的計(jì)算節(jié)點(diǎn)為新到來的視頻分析任務(wù)服務(wù)，以及在主動模式下如何為請求任務(wù)的計(jì)算節(jié)點(diǎn)分配適當(dāng)數(shù)目的任務(wù)。

首先討論被動模式下的任務(wù)調(diào)度算法，由于此時所有計(jì)算節(jié)點(diǎn)都處于空閑狀態(tài)，而調(diào)度服務(wù)器也剛剛接收到了新的視頻分析任務(wù)，無論采取何種調(diào)度算法都不大可能對任務(wù)執(zhí)行時間產(chǎn)生大的影響。因此可以在這時利用簡單的MET調(diào)度算法[3]，即將任務(wù)調(diào)度到能夠最快完成該任務(wù)的計(jì)算節(jié)點(diǎn)上。由于視頻分析任務(wù)的不可預(yù)測性，這也就意味著該任務(wù)應(yīng)當(dāng)被調(diào)度到具有最高配置的計(jì)算節(jié)點(diǎn)上執(zhí)行。

而視頻分析平臺在主動模式下的調(diào)度算法則可以采用主動調(diào)度模式下效果最好的TSS調(diào)度算法進(jìn)行[3]。該算法可以不斷調(diào)整分配給計(jì)算節(jié)點(diǎn)的任務(wù)塊大小，在保證任務(wù)執(zhí)行時間的前提下實(shí)現(xiàn)各計(jì)算節(jié)點(diǎn)間的負(fù)載均衡。

4 任務(wù)調(diào)度機(jī)制測試

本文為測試配置了8個計(jì)算節(jié)點(diǎn)，其中節(jié)點(diǎn)1-3使用Intel Core i5處理器，主頻為3.0GHz；節(jié)點(diǎn)4-8使用Intel Core2處理器，主頻為1.66GHz。在進(jìn)行任務(wù)調(diào)度時，模擬100個視頻分析任務(wù)供計(jì)算節(jié)點(diǎn)處理。為充分測試算法在不同情況下的調(diào)度可靠性，分別對計(jì)算節(jié)點(diǎn)數(shù)為2（取計(jì)算節(jié)點(diǎn)1、4參與計(jì)算）、4（取計(jì)算節(jié)點(diǎn)1、2、4、5參與計(jì)算）、8（取全部計(jì)算節(jié)點(diǎn)參與計(jì)算）這三種情況展開測試。

在仿真環(huán)境下對任務(wù)調(diào)度機(jī)制進(jìn)行測試，并記錄各個計(jì)算節(jié)點(diǎn)對任務(wù)的處理時間和由于通信、任務(wù)切換等因素造成的等待時間。同時也測試了單純將任務(wù)平均分配到各個計(jì)算節(jié)點(diǎn)上這種最“差”的調(diào)度機(jī)制。為直觀表明任務(wù)調(diào)度效果，以平均分配這一最“差”的調(diào)度機(jī)制形成的任務(wù)執(zhí)行時間除以新的調(diào)度機(jī)制形成的任務(wù)執(zhí)行時間，作為調(diào)度機(jī)制的加速比。由此繪制視頻分析任務(wù)的加速比如圖3所示。

■

圖3 任務(wù)執(zhí)行時間加速比

上述測試結(jié)果表明，本文提出的調(diào)度機(jī)制在多計(jì)算節(jié)點(diǎn)情況下，面對高并發(fā)的大量復(fù)雜計(jì)算任務(wù)，能夠進(jìn)行合理有效的任務(wù)調(diào)度，取得良好的調(diào)度效果。在計(jì)算節(jié)點(diǎn)越多時，調(diào)度效果越好，平均可以提升效率兩倍左右。

參考文獻(xiàn)：

[1]儲雅，馬廷淮，趙立成.云計(jì)算資源調(diào)度：策略與算法[J].計(jì)算機(jī)科學(xué)，2013，40（11）：8-13.

[2]金士堯，錢迎進(jìn)，章文嵩，王曉川.主動與被動混合調(diào)度網(wǎng)絡(luò)集群服務(wù)系統(tǒng)[J].計(jì)算機(jī)工程與科學(xué).2009，31（1）：17-19.

[3]A.T.Chronopoulos，R.Andonie，M.Benche，D.Grosu.A Class of Loop Self-Scheduling for Heterogeneous Clusters[C]. Proceedings of the 2001 IEEE International Conference on Cluster Computing.2002：113-122.

基金項(xiàng)目：

浙江省科技廳重大科技專項(xiàng)重點(diǎn)工業(yè)項(xiàng)目（2013C01045）。

作者簡介：

陸成剛（1973-），男，上海人，高級工程師，理學(xué)博士，智慧安居；

王安（1985-），男，江西撫州人，工程師，碩士，圖像與信息處理；

王汗（1989-），男，江蘇沭陽縣人，碩士研究生在讀，數(shù)字圖像處理；

洪榛（1983-），男，浙江臺州人，講師，工學(xué)博士，智慧安居。