杜姍姍，馮瑞

混合任務(wù)調(diào)度方法研究及其應(yīng)用

杜姍姍，馮瑞

面向異構(gòu)多核系統(tǒng)的任務(wù)調(diào)度問(wèn)題一直是業(yè)內(nèi)的研究熱點(diǎn)，提出了一種動(dòng)態(tài)任務(wù)調(diào)度與靜態(tài)任務(wù)調(diào)度相結(jié)合的混合任務(wù)調(diào)度方法，結(jié)合視頻大數(shù)據(jù)的實(shí)際應(yīng)用特點(diǎn)，提出軟實(shí)時(shí)任務(wù)的降級(jí)分配策略，并將提出的混合任務(wù)調(diào)度方法應(yīng)用到校園車(chē)輛行蹤管控系統(tǒng)中，實(shí)現(xiàn)了校內(nèi)車(chē)輛的身份識(shí)別與行蹤軌跡重構(gòu)，并在交互系統(tǒng)中實(shí)時(shí)展現(xiàn)，同時(shí)，持用戶(hù)統(tǒng)計(jì)查詢(xún)等相關(guān)管理操作，經(jīng)過(guò)實(shí)際部署與長(zhǎng)時(shí)間運(yùn)行，系統(tǒng)運(yùn)行穩(wěn)定，對(duì)校園內(nèi)機(jī)動(dòng)車(chē)實(shí)現(xiàn)了有效管控，滿(mǎn)足了校內(nèi)車(chē)輛管理的實(shí)際應(yīng)用需求。

視頻大數(shù)據(jù)；任務(wù)調(diào)度；分布式系統(tǒng)；視頻監(jiān)控；車(chē)輛行蹤

0 引言

隨著大數(shù)據(jù)尤其是視頻圖像等多媒體數(shù)據(jù)的處理速度被日益關(guān)注，多核異構(gòu)并行計(jì)算將成為必然的發(fā)展趨勢(shì)。針對(duì)視頻大數(shù)據(jù)的在線分析處理難題，學(xué)術(shù)界和產(chǎn)業(yè)界提出了異構(gòu)多核處理的解決方案。面向異構(gòu)多核系統(tǒng)的任務(wù)調(diào)度問(wèn)題一直是業(yè)內(nèi)的研究熱點(diǎn)，結(jié)合視頻大數(shù)據(jù)的應(yīng)用實(shí)際，也需要給出相對(duì)應(yīng)的任務(wù)分配調(diào)度機(jī)制。本文提出一種動(dòng)態(tài)任務(wù)調(diào)度與靜態(tài)任務(wù)調(diào)度相結(jié)合的混合任務(wù)調(diào)度方法，結(jié)合視頻大數(shù)據(jù)的實(shí)際應(yīng)用特點(diǎn)，提出軟實(shí)時(shí)任務(wù)的降級(jí)分配策略。并將提出的混合任務(wù)調(diào)度方法應(yīng)用到校園車(chē)輛行蹤管控系統(tǒng)中，實(shí)現(xiàn)了校內(nèi)車(chē)輛的身份識(shí)別與行蹤軌跡重構(gòu)，并在交互系統(tǒng)中實(shí)時(shí)展現(xiàn)，同時(shí)支持用戶(hù)統(tǒng)計(jì)查詢(xún)等相關(guān)管理操作，經(jīng)過(guò)實(shí)際部署與長(zhǎng)時(shí)間運(yùn)行，系統(tǒng)運(yùn)行穩(wěn)定，對(duì)校園內(nèi)機(jī)動(dòng)車(chē)實(shí)現(xiàn)了有效管控，滿(mǎn)足了校內(nèi)車(chē)輛管理的實(shí)際應(yīng)用需求。

1 基于視頻的管控系統(tǒng)中的任務(wù)分析

在視頻大數(shù)據(jù)的實(shí)際應(yīng)用場(chǎng)景中，盡管會(huì)部署數(shù)以千計(jì)的高清攝像機(jī)，每秒產(chǎn)生高達(dá)TB級(jí)的視頻數(shù)據(jù)，但是，這些實(shí)時(shí)產(chǎn)生的視頻大數(shù)據(jù)，真正有意義的數(shù)據(jù)可能僅占10%，甚至更少，因此，對(duì)所有視頻流數(shù)據(jù)全部在線分析顯然不是最優(yōu)方案，通過(guò)對(duì)實(shí)際應(yīng)用場(chǎng)景的深入理解，可總結(jié)視頻分析任務(wù)特點(diǎn)如下：

（1）大部分視頻流數(shù)據(jù)不需要在線精細(xì)分析：視頻數(shù)據(jù)一般包括目標(biāo)檢測(cè)、身份識(shí)別、在線跟蹤、事件推斷等4個(gè)層面的分析任務(wù)，算法復(fù)雜程度也根據(jù)分析層面的不同呈遞進(jìn)趨勢(shì)，比如針對(duì)大尺度區(qū)域范圍的視頻監(jiān)控系統(tǒng)，部署的高清相機(jī)將數(shù)以百計(jì)，但需要完成所有4個(gè)層面分析任務(wù)的相機(jī)僅占很少的比例。絕大部分相機(jī)在大部分時(shí)間內(nèi)將僅需要完成目標(biāo)檢測(cè)等相對(duì)計(jì)算復(fù)雜度較低的任務(wù)，當(dāng)檢測(cè)到有目標(biāo)的時(shí)候，才會(huì)進(jìn)行進(jìn)一步的分析任務(wù)，而需要進(jìn)行精細(xì)分析的攝像機(jī)往往是極少的一部分；

（2）很多視頻流數(shù)據(jù)不需要在線分析：同樣是區(qū)域范圍的視頻監(jiān)控任務(wù)，會(huì)部署相當(dāng)數(shù)量的帶云臺(tái)球機(jī)，這些攝像機(jī)將負(fù)責(zé)全局監(jiān)控的槍機(jī)進(jìn)行聯(lián)動(dòng)，當(dāng)槍機(jī)發(fā)現(xiàn)可疑異常時(shí)，將指揮帶云臺(tái)球機(jī)實(shí)現(xiàn)監(jiān)控目標(biāo)的對(duì)焦，利用球機(jī)完成進(jìn)一步的深度分析。因此，只有在槍機(jī)發(fā)現(xiàn)可疑異常的時(shí)候，這些球機(jī)的視頻數(shù)據(jù)才需要進(jìn)行分析處理。

（3）重點(diǎn)監(jiān)控區(qū)域具有可變性和不確定性：對(duì)于大尺度的區(qū)域監(jiān)控系統(tǒng)，重點(diǎn)防控的區(qū)域往往是少數(shù)，而且，防控區(qū)域的重要程度會(huì)根據(jù)時(shí)間、監(jiān)控目標(biāo)等因素會(huì)發(fā)生變化，這些都會(huì)直接影響視頻數(shù)據(jù)處理的精細(xì)程度與任務(wù)截止期。而區(qū)域的重要程度一般都是通過(guò)人機(jī)交互方式在線指定，系統(tǒng)設(shè)計(jì)時(shí)無(wú)法提前預(yù)知。

因此，為了兼顧視頻大數(shù)據(jù)分析性能與計(jì)算資源利用的最大化，混合任務(wù)調(diào)度方法是一種較好的方案，目的是采用最少的計(jì)算節(jié)點(diǎn)數(shù)量實(shí)現(xiàn)視頻大數(shù)據(jù)的在線分析處理。

2 混合任務(wù)調(diào)度方法

混合任務(wù)調(diào)度是指在計(jì)算節(jié)點(diǎn)內(nèi)的異構(gòu)系統(tǒng)中采用為靜態(tài)任務(wù)調(diào)度，并計(jì)算節(jié)點(diǎn)間的同構(gòu)系統(tǒng)采用動(dòng)態(tài)任務(wù)調(diào)度。采用混合任務(wù)調(diào)度時(shí)，在計(jì)算節(jié)點(diǎn)之間，系統(tǒng)根據(jù)任務(wù)類(lèi)別有若干個(gè)專(zhuān)門(mén)的計(jì)算節(jié)點(diǎn)作為中心任務(wù)調(diào)度資源，每個(gè)中心任務(wù)調(diào)度器負(fù)責(zé)對(duì)若干個(gè)計(jì)算節(jié)點(diǎn)進(jìn)行任務(wù)分配，某種類(lèi)別的任務(wù)將首先到達(dá)相應(yīng)的中心任務(wù)調(diào)度器，由它來(lái)做統(tǒng)一的任務(wù)調(diào)度，然后這些任務(wù)被分配給其負(fù)責(zé)的計(jì)算節(jié)點(diǎn)去運(yùn)行任務(wù)。在計(jì)算節(jié)點(diǎn)內(nèi)部沒(méi)有任務(wù)調(diào)度器，CPU與GPU的計(jì)算任務(wù)被事先設(shè)計(jì)指定。這種混合任務(wù)調(diào)度方式既可以實(shí)現(xiàn)節(jié)點(diǎn)間任務(wù)的靈活調(diào)度，又可以實(shí)現(xiàn)節(jié)點(diǎn)內(nèi)部資源可控，提高系統(tǒng)運(yùn)行可靠性與任務(wù)完成的可控性。

2.1 計(jì)算節(jié)點(diǎn)內(nèi)部采用靜態(tài)任務(wù)調(diào)度

靜態(tài)任務(wù)調(diào)度是指在多計(jì)算節(jié)點(diǎn)間的同構(gòu)系統(tǒng)和節(jié)點(diǎn)內(nèi)的異構(gòu)系統(tǒng)的計(jì)算任務(wù)全部事先指定，根據(jù)視頻分析任務(wù)的特點(diǎn)，將任務(wù)固定的分配給各計(jì)算節(jié)點(diǎn)與節(jié)點(diǎn)內(nèi)部的GPU計(jì)算資源，每個(gè)計(jì)算節(jié)點(diǎn)負(fù)責(zé)一路或者多路視頻數(shù)據(jù)的分析處理，如果是多路視頻，采用輪詢(xún)處理方式。優(yōu)點(diǎn)是計(jì)算資源事先規(guī)劃好，資源可控，可靠性好。缺點(diǎn)是靈活度不夠，系統(tǒng)資源難以實(shí)現(xiàn)最大化利用。計(jì)算節(jié)點(diǎn)內(nèi)部的靜態(tài)任務(wù)調(diào)度方法根據(jù)實(shí)際的視頻分析任務(wù)提前設(shè)計(jì)，一般將視頻解碼、特征提取等具有大規(guī)模重復(fù)簡(jiǎn)單計(jì)算的任務(wù)交由GPU完成，將分類(lèi)器、輸入輸出等計(jì)算量較小的任務(wù)交由CPU處理。

2.2 計(jì)算節(jié)點(diǎn)間采用動(dòng)態(tài)任務(wù)調(diào)度

動(dòng)態(tài)任務(wù)調(diào)度是指計(jì)算節(jié)點(diǎn)間的同構(gòu)系統(tǒng)和節(jié)點(diǎn)內(nèi)的異構(gòu)系統(tǒng)的計(jì)算任務(wù)全部動(dòng)態(tài)調(diào)度，一般會(huì)有兩個(gè)調(diào)度器，一個(gè)用于調(diào)度計(jì)算節(jié)點(diǎn)的任務(wù)，一個(gè)用于調(diào)度節(jié)點(diǎn)內(nèi)部的任務(wù)，用于調(diào)度節(jié)點(diǎn)內(nèi)部任務(wù)的調(diào)度器由該計(jì)算節(jié)點(diǎn)的CPU實(shí)現(xiàn)。優(yōu)點(diǎn)是靈活性好，能根據(jù)視頻數(shù)據(jù)的變化靈活調(diào)度各節(jié)點(diǎn)的計(jì)算任務(wù)，以及節(jié)點(diǎn)內(nèi)部CPU、GPU的計(jì)算資源；缺點(diǎn)是可靠性較差，尤其是節(jié)點(diǎn)內(nèi)部的資源調(diào)度，一旦任務(wù)的截止期無(wú)法在某個(gè)處理器上被滿(mǎn)足，則要將該任務(wù)遷移到其他可以保證截止期的處理器上去運(yùn)行，從而降低整體的運(yùn)行效率，另外系統(tǒng)運(yùn)行效率可控性較差。

2.3 軟實(shí)時(shí)任務(wù)的降級(jí)分配策略

在分析視頻大數(shù)據(jù)分析處理特點(diǎn)部分，明確指出，在視頻大數(shù)據(jù)分析處理中，存在很多軟實(shí)時(shí)任務(wù)，在進(jìn)行系統(tǒng)任務(wù)設(shè)計(jì)時(shí)，應(yīng)明確區(qū)分哪些任務(wù)屬于硬實(shí)時(shí)任務(wù)，哪些任務(wù)屬于軟實(shí)時(shí)任務(wù)，并且對(duì)這些軟實(shí)時(shí)任務(wù)進(jìn)行服務(wù)等級(jí)劃分，在軟實(shí)時(shí)任務(wù)中，服務(wù)等級(jí)越高的任務(wù)，在滿(mǎn)足硬實(shí)時(shí)任務(wù)被執(zhí)行的前提下，應(yīng)優(yōu)先被執(zhí)行，然而如果發(fā)現(xiàn)該任務(wù)在某個(gè)計(jì)算節(jié)點(diǎn)上運(yùn)行無(wú)法滿(mǎn)足其截止時(shí)間和資源需求時(shí)，則該任務(wù)的服務(wù)等級(jí)將被降級(jí)，這種降級(jí)策略將一直持續(xù)，直至該任務(wù)達(dá)到可分配的條件或服務(wù)等級(jí)已經(jīng)減至最低，最壞情況是該任務(wù)被取消。

顯然，這種降級(jí)策略是通過(guò)犧牲軟實(shí)時(shí)任務(wù)的分析結(jié)果質(zhì)量來(lái)提高整體任務(wù)的分配成功率，考慮到視頻數(shù)據(jù)中絕大部分的任務(wù)為軟實(shí)時(shí)任務(wù)，因此，也為視頻大數(shù)據(jù)的在線處理提供了一種有效的解決思路。

2.4 硬實(shí)時(shí)任務(wù)和軟實(shí)時(shí)的混合動(dòng)態(tài)調(diào)度

計(jì)算節(jié)點(diǎn)間的動(dòng)態(tài)任務(wù)調(diào)度方法可看成是實(shí)時(shí)分布式同構(gòu)系統(tǒng)的動(dòng)態(tài)任務(wù)調(diào)度，即對(duì)動(dòng)態(tài)到達(dá)的有n個(gè)任務(wù)的任務(wù)集S，從中找出m個(gè)任務(wù)子集，將其分配給m個(gè)計(jì)算節(jié)點(diǎn)，每個(gè)任務(wù)在所分配的處理器運(yùn)行時(shí)，針對(duì)硬實(shí)時(shí)任務(wù)，結(jié)合具體應(yīng)用場(chǎng)景，在規(guī)定的時(shí)間和系統(tǒng)資源范圍內(nèi)完成，對(duì)于軟實(shí)時(shí)任務(wù)，每個(gè)任務(wù)對(duì)應(yīng)會(huì)有一個(gè)權(quán)重，在每個(gè)權(quán)重等級(jí)下，規(guī)定時(shí)間和系統(tǒng)資源能得到滿(mǎn)足，這樣就完成了任務(wù)集合S的完整任務(wù)調(diào)度。針對(duì)此類(lèi)實(shí)時(shí)系統(tǒng)的動(dòng)態(tài)任務(wù)調(diào)度問(wèn)題，是學(xué)術(shù)界和業(yè)內(nèi)公認(rèn)的NP完全問(wèn)題，不存在最優(yōu)算法，在實(shí)際應(yīng)用中，一般采用啟發(fā)式算法解決。其中經(jīng)典的調(diào)度算法是近視算法。

近視算法對(duì)一組動(dòng)態(tài)到達(dá)，具有資源約束的實(shí)時(shí)任務(wù)所組成的任務(wù)集合進(jìn)行啟發(fā)式搜索。搜索樹(shù)中的一個(gè)節(jié)點(diǎn)表示一個(gè)局部調(diào)度或任務(wù)集合一個(gè)可行調(diào)度。在任務(wù)搜索的過(guò)程當(dāng)中，每次對(duì)當(dāng)前的任務(wù)集合進(jìn)行擴(kuò)充前，都要對(duì)擴(kuò)充后的任務(wù)集合進(jìn)行可行性檢查，以確認(rèn)當(dāng)前任務(wù)分配的合理性，只有通過(guò)了可行性檢查，任務(wù)調(diào)度才可能發(fā)生。可行性檢查的標(biāo)準(zhǔn)：如果當(dāng)前任務(wù)分配被可行性檢查任務(wù)集的人一個(gè)任務(wù)擴(kuò)充后仍為可行的，則當(dāng)前任務(wù)分配是可行調(diào)度，否則就是不可行任務(wù)。在近視算法中，每個(gè)任務(wù)都定義了一個(gè)目標(biāo)函數(shù)H，H=任務(wù)截止期+任務(wù)最早可用時(shí)間*權(quán)重，每次選擇目標(biāo)函數(shù)最?。ㄗ顑?yōu)）的任務(wù)擴(kuò)充當(dāng)前任務(wù)集，如果當(dāng)前調(diào)度不是可行調(diào)度，就要回溯到上層節(jié)點(diǎn)，重新選擇目標(biāo)函數(shù)次?。ù蝺?yōu)）的任務(wù)擴(kuò)充任務(wù)集，為了限制搜索次數(shù)，算法定義最大回溯次數(shù)或目標(biāo)函數(shù)的最大估算值，如果達(dá)到最大回溯次數(shù)或者目標(biāo)函數(shù)達(dá)到了最大估算值，則停止回溯，相應(yīng)的任務(wù)將被拋棄，表明沒(méi)有找到一個(gè)可行的任務(wù)分配。近視算法選擇一個(gè)新的任務(wù)擴(kuò)充當(dāng)前任務(wù)集合時(shí)，當(dāng)多個(gè)計(jì)算節(jié)點(diǎn)都能滿(mǎn)足新進(jìn)任務(wù)的截止時(shí)間時(shí)，對(duì)計(jì)算節(jié)點(diǎn)的選擇基于目標(biāo)函數(shù)最優(yōu)，實(shí)際上是選擇最早可用時(shí)間最小的計(jì)算節(jié)點(diǎn)，沒(méi)有考慮計(jì)算節(jié)點(diǎn)的最早可用時(shí)間與資源的最早可用時(shí)間之間的關(guān)系，一方面會(huì)導(dǎo)致計(jì)算節(jié)點(diǎn)處理時(shí)間的浪費(fèi)，另一方面會(huì)影響任務(wù)分配的成功率。

為了克服近視算法的不足，有學(xué)者提出一種節(jié)約算法，其選擇計(jì)算節(jié)點(diǎn)的策略是在滿(mǎn)足新進(jìn)任務(wù)截止時(shí)間的前提下，盡量延遲任務(wù)的開(kāi)始運(yùn)行時(shí)間，使得所選的計(jì)算節(jié)點(diǎn)最早可運(yùn)行任務(wù)的時(shí)間盡可能接近任務(wù)截止時(shí)間，這樣做的好處是計(jì)算節(jié)點(diǎn)最早可用時(shí)間可以被提前，使得新進(jìn)任務(wù)有較早開(kāi)始運(yùn)行的機(jī)會(huì)，進(jìn)而加大任務(wù)調(diào)度的成功率。但這種策略?xún)A向于負(fù)載重的計(jì)算節(jié)點(diǎn)負(fù)載越重，負(fù)載輕的計(jì)算節(jié)點(diǎn)負(fù)載越清，因此，可能造成某些節(jié)點(diǎn)有較多的任務(wù)等待執(zhí)行，某些節(jié)點(diǎn)沒(méi)有分配任務(wù)，不利于算法性能的提高。

從搜索策略來(lái)看，近視算法和節(jié)約算法每次擴(kuò)充任務(wù)集合的時(shí)候，都只是選擇一項(xiàng)任務(wù)進(jìn)行擴(kuò)充，其結(jié)果是任務(wù)分配的預(yù)測(cè)性對(duì)整個(gè)任務(wù)集合S來(lái)說(shuō)極其有限。為了提高任務(wù)分配的成功率，有學(xué)者提出采用批量任務(wù)分配策略，即每次不是分配一個(gè)任務(wù)，而是一批任務(wù)，通過(guò)提高任務(wù)分配集合的可預(yù)測(cè)性來(lái)提高任務(wù)分配的成功率。當(dāng)然，這種方法仍然無(wú)法避免任務(wù)分配失敗的情況，其根本原因是計(jì)算節(jié)點(diǎn)的不足，只能通過(guò)增加計(jì)算節(jié)點(diǎn)資源來(lái)提高任務(wù)分配的成功率。

3 校園車(chē)輛行蹤管控系統(tǒng)

校園車(chē)輛行蹤管控系統(tǒng)包含校內(nèi)車(chē)輛的身份識(shí)別與行蹤軌跡重構(gòu)，并在交互系統(tǒng)中實(shí)時(shí)展現(xiàn)，同時(shí)支持用戶(hù)統(tǒng)計(jì)查詢(xún)等相關(guān)管理應(yīng)用。

3.1 系統(tǒng)體系框架設(shè)計(jì)

本文所述校園車(chē)輛行蹤管控系統(tǒng)由覆蓋校園的1080P高清攝像機(jī)，用于動(dòng)態(tài)任務(wù)分配調(diào)度的處理節(jié)點(diǎn)服務(wù)器、用于視頻數(shù)據(jù)在線分析的多核異構(gòu)計(jì)算設(shè)備、萬(wàn)兆網(wǎng)絡(luò)交換機(jī)、用于信息展示用大屏幕、人機(jī)交互用客戶(hù)端計(jì)算機(jī)組成，系統(tǒng)硬件組成，如圖1所示：

圖1 校園車(chē)輛行蹤管控系統(tǒng)組成

管控系統(tǒng)需要對(duì)校園內(nèi)經(jīng)過(guò)的車(chē)輛實(shí)現(xiàn)檢測(cè)與身份識(shí)別（包括車(chē)牌識(shí)別、車(chē)身顏色識(shí)別、車(chē)型識(shí)別、車(chē)標(biāo)識(shí)別、車(chē)輛整體特征識(shí)別），為了提高身份識(shí)別精度，本系統(tǒng)架設(shè)的攝像機(jī)采用1080P（200萬(wàn)像素）的高清攝像機(jī)，采集1920 ×1080高清圖像，如果每幀圖像都在線進(jìn)行分析處理，會(huì)導(dǎo)致視頻分析計(jì)算資源的負(fù)荷較高，利用前述的混合任務(wù)分配方法，將高清視頻數(shù)據(jù)計(jì)算任務(wù)動(dòng)態(tài)分配給各多核異構(gòu)計(jì)算節(jié)點(diǎn)，在計(jì)算節(jié)點(diǎn)內(nèi)部利用GPU計(jì)算資源完成H.264視頻解碼和特征提取任務(wù)，利用CPU計(jì)算資源完成分類(lèi)及節(jié)點(diǎn)內(nèi)部管理任務(wù)（進(jìn)程、線程、IO、傳輸?shù)龋Ｔ谝曨l數(shù)據(jù)傳輸方面，采用光纖、萬(wàn)兆交換機(jī)，以保證高清視頻及時(shí)穩(wěn)定傳輸?？紤]到任務(wù)分配計(jì)算節(jié)點(diǎn)運(yùn)算復(fù)雜度不高，但是對(duì)穩(wěn)定性和可靠性要求很高，因此采用Intel至強(qiáng)CPU和服務(wù)器級(jí)別內(nèi)存與硬盤(pán)，多核異構(gòu)計(jì)算節(jié)點(diǎn)分析任務(wù)完成后將結(jié)果返回給該節(jié)點(diǎn)，采用Intel Haswell系列CPU，內(nèi)部集成GPU計(jì)算資源，存儲(chǔ)方面采用速度更快的SSD硬盤(pán)，在保證計(jì)算任務(wù)高效完成的基礎(chǔ)上，有效降低成本。人機(jī)交互系統(tǒng)用于將校園車(chē)輛行蹤狀態(tài)結(jié)果和軌跡信息、地理信息等融合，并在用戶(hù)端展示，同時(shí)支持用戶(hù)對(duì)這些信息的查詢(xún)和管理。

3.2 動(dòng)態(tài)任務(wù)分配系統(tǒng)

車(chē)輛檢測(cè)與身份識(shí)別系統(tǒng)運(yùn)行在多核異構(gòu)計(jì)算節(jié)點(diǎn)上，每個(gè)計(jì)算節(jié)點(diǎn)包括1個(gè)4核8線程CPU（Intel Haswell i7-4700EQ）和1個(gè)GPU(GT2 HD Graphics P4600)，為簡(jiǎn)單起見(jiàn)，對(duì)用于數(shù)據(jù)分析的CPU和GPU資源按70%測(cè)算，剩下的30%將包含網(wǎng)絡(luò)傳輸、數(shù)據(jù)IO、數(shù)據(jù)交換等系統(tǒng)開(kāi)銷(xiāo)，以及為系統(tǒng)預(yù)留冗余資源。經(jīng)實(shí)際系統(tǒng)測(cè)試，每個(gè)包含CPU和GPU的異構(gòu)計(jì)算節(jié)點(diǎn)完成200萬(wàn)像素的高清視頻分析所需的運(yùn)行時(shí)間如表1所示：

表1 單計(jì)算節(jié)點(diǎn)每幀高清視頻運(yùn)行時(shí)間表

根據(jù)實(shí)際測(cè)算，集成GPU的計(jì)算性能與CPU計(jì)算能力相當(dāng)，從表1中不難看出，如果所有分析任務(wù)都在CPU中完成，考慮到校園內(nèi)車(chē)輛的車(chē)速較慢，按＜40km/h計(jì)算，則平均每秒鐘處理5幀即可滿(mǎn)足要求，則每個(gè)節(jié)點(diǎn)可處理約4路視頻，加上GPU計(jì)算資源，可處理約8路視頻。因此，GPU計(jì)算資源的加入，可使每個(gè)節(jié)點(diǎn)計(jì)算能力提高一倍。

在實(shí)際應(yīng)用中，按每個(gè)攝像機(jī)內(nèi)出現(xiàn)的車(chē)輛數(shù)量峰值為40輛/分鐘，平均為10輛/分鐘，針對(duì)攝像機(jī)的視頻數(shù)據(jù)，每幀視頻的解碼與車(chē)輛檢測(cè)任務(wù)都要完成，當(dāng)有車(chē)輛時(shí)，都要進(jìn)行車(chē)牌識(shí)別，目前全天候條件下車(chē)牌識(shí)別精度約為90%，在識(shí)別失敗的10%車(chē)牌中包括車(chē)牌污損、無(wú)牌車(chē)、故意遮擋、光照影響等因素。如果車(chē)牌識(shí)別失敗，則需要聯(lián)合完成車(chē)身顏色和車(chē)標(biāo)識(shí)別，目前根據(jù)車(chē)身顏色+車(chē)標(biāo)識(shí)別對(duì)車(chē)輛的識(shí)別率約為80%，如果車(chē)身顏色與車(chē)標(biāo)識(shí)別失敗，則開(kāi)始進(jìn)行整體特征識(shí)別。按車(chē)輛數(shù)量峰值計(jì)算，一分鐘將有1500幀（25幀/秒×60秒）圖像完成解碼與車(chē)輛檢測(cè)任務(wù)，40幀圖像需要完成車(chē)牌識(shí)別任務(wù)，4幀圖像需要完成車(chē)身顏色與車(chē)標(biāo)識(shí)別任務(wù)，整體特征識(shí)別車(chē)輛按1輛車(chē)/小時(shí)計(jì)算。如按平均通過(guò)車(chē)輛數(shù)計(jì)算，一分鐘將有1500幀（25fps×60s）圖像完成解碼與車(chē)輛檢測(cè)任務(wù)，10幀圖像需要完成車(chē)牌識(shí)別任務(wù)，1幀圖像需要完成車(chē)身顏色與車(chē)標(biāo)識(shí)別任務(wù)，整體特征識(shí)別車(chē)輛按1輛車(chē)/小時(shí)計(jì)算。根據(jù)上述分析可知，車(chē)輛整體特征識(shí)別可不做考慮，峰值情況平均每幀視頻需要70ms（40ms解碼+檢測(cè)，27ms車(chē)牌識(shí)別，1.5ms車(chē)身顏色+車(chē)標(biāo)識(shí)別）。則每個(gè)計(jì)算節(jié)點(diǎn)可處理12路視頻數(shù)據(jù)（每秒5幀，每個(gè)CPU核心可處理3路視頻，一個(gè)節(jié)點(diǎn)4個(gè)CPU核可處理12路），加上GPU計(jì)算資源，計(jì)算性能增加一倍，則可以處理24路。

綜上所述，針對(duì)本系統(tǒng)具有4個(gè)計(jì)算節(jié)點(diǎn)的情況下，可實(shí)現(xiàn)24路視頻/節(jié)點(diǎn)×4個(gè)計(jì)算節(jié)點(diǎn)=96路高清視頻的在線處理。除去視頻解碼與車(chē)輛檢測(cè)任務(wù)都要處理，按96路高清視頻流進(jìn)行計(jì)算，峰值情況下，平均每秒會(huì)有64個(gè)車(chē)牌識(shí)別任務(wù)，6個(gè)車(chē)身顏色與車(chē)標(biāo)識(shí)別任務(wù)，按200ms的任務(wù)截止期，則任務(wù)隊(duì)列中平均情況會(huì)有14個(gè)任務(wù)，有4個(gè)計(jì)算節(jié)點(diǎn)，按照批量任務(wù)分配方法，即可完成各節(jié)點(diǎn)間的動(dòng)態(tài)任務(wù)分配。

4 總結(jié)

本文提出一種動(dòng)態(tài)任務(wù)調(diào)度與靜態(tài)任務(wù)調(diào)度相結(jié)合的混合任務(wù)調(diào)度方法，結(jié)合視頻大數(shù)據(jù)的實(shí)際應(yīng)用特點(diǎn)，提出軟實(shí)時(shí)任務(wù)的降級(jí)分配策略。并將提出的混合任務(wù)調(diào)度方法應(yīng)用到校園車(chē)輛行蹤管控系統(tǒng)中，實(shí)現(xiàn)了校內(nèi)車(chē)輛的身份識(shí)別與行蹤軌跡重構(gòu)，并在交互系統(tǒng)中實(shí)時(shí)展現(xiàn)，同時(shí)支持用戶(hù)統(tǒng)計(jì)查詢(xún)等相關(guān)管理操作，經(jīng)過(guò)實(shí)際部署與長(zhǎng)時(shí)間運(yùn)行，系統(tǒng)運(yùn)行穩(wěn)定，對(duì)校園內(nèi)機(jī)動(dòng)車(chē)實(shí)現(xiàn)了有效管控，滿(mǎn)足了校內(nèi)車(chē)輛管理的實(shí)際應(yīng)用需求。

[1] 張麗.車(chē)輛視頻檢測(cè)與跟蹤系統(tǒng)的算法研究[D].杭州:浙江大學(xué),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

科技部支撐計(jì)劃（2013BAH09F01）；上海市科委科技創(chuàng)新行動(dòng)計(jì)劃（14511106901）

杜姍姍（1983-），女，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海視頻技術(shù)與系統(tǒng)工程研究中心，碩士研究生，研究方向：計(jì)算機(jī)圖像識(shí)別與

處理，上海，201203

馮 瑞（1971-），男，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海視頻技術(shù)與系統(tǒng)工程研究中心，副教授，研究方向：計(jì)算機(jī)圖像識(shí)別與處理，上海，201203