基于概率模型檢驗的云渲染任務調度定量驗證*

高洪皓 , 繆淮扣 , 劉浩宇 , 許華虎,3 , 于芷若

1(上海大學 計算中心,上海 200444)2(上海大學 計算機工程與科學學院,上海 200444)3(上海大學 信息化辦公室,上海 200444)4(上海市計算機軟件評測重點實驗室,上海 201112)

影視動漫行業的渲染是對視頻動畫原模型進行貼圖、光照、陰影、紋理等逐幀計算的復雜過程[1-3].近年來,AR 和VR 產業的繁榮發展對計算機性能和GPU/CPU 計算能力提出了更高的性能要求,例如以3D 圖像和高清視頻技術為代表的視頻動畫,將決定畫質最終呈現的視覺效果[4,5].由于3D 模型和貼圖設計越來越細致,渲染任務將消耗大量的計算資源和存儲資源,同時也增加了更多時間來輸出相關渲染結果文件.但是在互聯網+的時代,影視動漫行業的創意具有時效性和緊迫性,其中縮短創作時間、減少資金成本以及提高渲染質量將是這類企業生存之道和發展關鍵.面對這一問題,越來越多的企業青睞于使用云渲染來降低構建私有渲染系統的經濟負擔和技術難度.云計算技術被引入到渲染領域[6],利用互聯網網絡的高速、互聯能力,將本應由計算能力有限的個人計算機執行的渲染任務分發給部署在網絡的高性能服務器集群上,再通過對計算節點進行統一管理和調度,為用戶提供便捷高效的渲染服務.因此,基于云服務實現渲染任務的計算模式正逐漸成為影視動漫行業節約時間和成本的重要實現手段.

云渲染系統提供的渲染服務屬于軟件即服務(SaaS)層面,以渲染作業為核心向外提供服務,具有資源虛擬化、按需使用、按需付費等特點.用戶通過Web 瀏覽器或客戶端軟件,提交需要渲染的模型文件并設定相應參數后,云渲染系統會根據用戶要求分配計算資源和存儲資源來完成相關渲染任務[7-9].由于互聯網的異構性、動態性和協同性,各種異常隨時會導致服務執行失效和服務中斷,嚴重影響渲染業務流程整體的正確性和可靠性.因此,云渲染系統需要不斷地調整渲染任務和執行動態配置策略,以適應不斷變化的用戶需求和不穩定的運行環境.其中,云渲染服務提供商通常定義服務等級協議(SLA)來明確服務質量QoS 參數和需履行的服務職責[10-12].但如何檢驗渲染業務任務調度是正確的并且滿足預期服務質量需求,卻是確保渲染任務能動態且高效執行的前提.

失效威脅是云渲染面臨的最嚴峻的挑戰,已有學者研究云計算的服務質量:一部分是用戶可感知屬性的研究[13,14],例如可用性和響應性屬性,用戶在使用渲染系統的過程中能夠直接感受到系統是否可以訪問,點擊按鈕后系統是否能夠及時反饋等.另一部分是用戶不可感知屬性的研究[15],例如系統可靠性屬性,表示系統在指定的一段時間內正常運行的概率.由于云服務資源的高度虛擬化,云渲染系統所使用的計算節點、存儲設備和系統的具體執行過程對用戶而言是透明的,而在其內部服務流程結構復雜且存在隨機失效現象.在云渲染系統執行渲染任務的全期間,用戶只能看到渲染進度和渲染結果,卻很難判斷云渲染系統是否按照約定提供了相應質量的服務.因此,需要服務提供商對系統進行評測后將可靠性計算結果反饋給用戶.本文考察的可靠性因素是指云渲染系統模塊或服務器出現各種失效的隨機概率,通過形式化驗證方法綜合評估系統可靠性,確保向用戶提供的渲染服務是可信的.傳統軟件測試采用數理統計方法得出系統執行成功的次數與總執行次數的比率或系統故障的時間與總運行時間的比率,以此來衡量系統的可靠性.傳統軟件測試只能使得錯誤盡可能少地出現,而采用形式化驗證方式,尤其是采用概率模型檢驗技術對云渲染系統任務調度進行定量檢驗,則可以同時證明相關服務流程的正確性和可靠性.

基于上述問題,本文針對云渲染系統的任務調度問題[16],對系統執行渲染任務的路徑和失效概率狀態等采用形式化方法進行建模,定量檢驗調度任務,評估服務流程性能,找出產生異常的環節或處理節點,提高渲染任務的成功率,并確保云渲染系統的可靠性.首先,針對云渲染系統的文件準備模塊、資源請求模塊、渲染任務執行模塊的概率建模問題,將云渲染系統任務調度的服務流程狀態集合分割成“正常”和“異常”兩類,采用離散時間馬爾可夫鏈DTMC 對系統各功能模塊進行概率建模;其次,從服務質量屬性QoS 定義角度,結合渲染需求給出多角度的可靠性屬性檢驗公式,使用模型檢驗工具PRISM[17,18]計算概率,并驗證云渲染系統可靠性;最后,在實驗部分,通過分析定量檢驗結果給出任務調度相關策略,用于指導云渲染系統的任務調度、資源調度和負載均衡.實驗對比分析改進前后的系統可靠性,驗證本文方法在提高云渲染系統可靠性方面具有較高應用價值.

本文第1 節介紹了云渲染系統概率建模方法.第2 節提出了可靠性相關屬性定義和其對應的概率計算樹邏輯PCTL 公式.第3 節通過實驗分析證明了本文方法的可行性.第4 節介紹了相關工作.第5 節總結了研究內容,提出今后研究方向.

1 云渲染概率模型建模

1.1 案例和動機

本節通過一個平臺實例介紹云渲染系統形式化建模和驗證的必要性.特別是面向概率失效而引起的系統穩定性問題,急需能對渲染任務調度進行定量評估的解決方案.如圖1 所示是云渲染系統拓撲圖,平臺主要包括Web 服務器、文件服務器、平臺數據庫、節點管理服務器和云渲染資源節點,通過網絡實現互聯和調度.首先,用戶通過終端連接云渲染系統Web 服務器,將待渲染文件上傳到文件服務器中;隨后,Web 服務器向節點服務器請求云渲染資源,節點服務器收到請求后分配云渲染資源節點;接著,待渲染任務獲得云渲染資源后,由Web 服務器將用戶的渲染任務提交至節點管理服務器,節點管理服務器將任務分割并分發至計算節點執行渲染子任務,云渲染資源中的存儲節點保存數據塊和渲染子任務執行產生的中間結果;接著,待所有子任務執行完后,節點管理服務器合并存儲節點的渲染結果,將最終渲染結果上傳至云渲染平臺文件服務器;最后,由云渲染平臺Web 服務器通知用戶渲染任務完成.

Fig.1 Topology of general cloud rendering system圖1 云渲染系統拓撲圖

然而在云渲染系統環境下,為了完成渲染任務需要龐大的存儲資源保存待渲染文件,通過性能強大的CPU和GPU 計算以滿足執行大規模渲染任務的需求.高效的任務調度和渲染流程是保證渲染任務執行的前提.為了說明任務調度,如圖2 所示是上海大學承擔的上海市科委專項項目云渲染平臺所涉及的相關流程.該系統任務調度的服務流程分為校驗待渲染文件、請求云渲染資源、渲染子任務分配、節點執行渲染子任務、合并渲染結果等模塊.云渲染系統的執行步驟包括開始、校驗待渲染文件、請求云渲染資源、獲得云渲染資源、分配渲染子任務、執行渲染任務、保存中間結果、合并渲染結果、結束.網絡的不穩定性容易產生數據丟包現象,引起數據不一致、文件損壞、執行參數不一致等問題,進而導致渲染幀質量不高、結果輸出時間過長等問題,更有可能出現渲染任務無法順利執行或渲染服務異常等結果.因此,云渲染系統的任務調度流程在關注服務功能執行情況外,還需要考慮異常情況和概率因素.

Fig.2 Flow chart of task scheduling in cloud rendering system圖2 云渲染系統任務調度的流程圖

一方面,由于云渲染服務資源是有限的,且渲染任務需要大量的計算和存儲支持,常伴有請求資源不足等問題.其中,云渲染資源主要是指執行渲染任務的虛擬主機,是用于保存渲染結果的虛擬存儲單元.云渲染任務需要等待足夠云渲染資源后才能繼續執行.若等待請求云渲染資源時間過長,表明系統同時執行了較多用戶提交的渲染任務,虛擬主機正在執行繁重的渲染任務.云渲染資源的可用性是任務調度的重要考慮因素.另一方面,節點執行渲染子任務不總是成功的,各種軟硬件都容易出錯致使渲染子任務異常.因此當整個渲染任務完成時,需要檢查所有子任務是否都成功執行:若有執行失敗的子任務,重新分配這些渲染子任務并嘗試執行;當嘗試次數過多時,渲染任務被迫中止.只有所有渲染子任務成功執行,產生了正確的結果后,云渲染系統才會合并中間結果并將渲染最終結果交付給用戶.因此,云渲染子任務的成功執行率也是任務調度的重要考慮因素.根據上述原因分析,對云渲染系統中不同模塊異常與可靠性進行關聯分析,給出如下3 個角度的異常現象.

1) 文件準備模塊的異常現象

用戶通過網絡將待渲染的視頻、圖片和腳本等原始文件上傳到云渲染系統的文件服務器.根據文件大小,一般先被分割成若干小塊后存儲到存儲節點中.考慮到傳輸或存儲文件過程可能由于網絡、硬件等不確定因素導致文件損壞或者不兼容,云渲染系統在使用文件之前要先檢查文件的有效性.如果校驗結果為文件無效或損壞,系統將執行文件修復程序,此時可認為系統進入了異常狀態,即文件異常.如果系統發生多次異常或者大量文件異常,則可靠性較低.另一方面,如果修復程序成功地將文件恢復,系統可繼續執行下一步操作,即恢復到正常狀態.這種異常恢復能力可定義為異常恢復率.當文件異常恢復率較高時,可認為系統可靠性較高.

2) 云渲染資源請求模塊的異常現象

云渲染資源包括用于執行渲染任務的虛擬主機(即計算節點)和保存渲染結果的虛擬存儲單元(即存儲節點).通常,云渲染服務資源是有限的且需要共享,加上渲染任務需要大量的計算和存儲支持,可能導致渲染任務無法及時得到滿足.因此,若請求資源沒有得到滿足,渲染任務先進入等待狀態.此時可認為云渲染系統進入了異常狀態,即資源異常.無期限的等待將是致命的缺陷.若系統能在規定時間內及時分配給目標渲染任務足夠的云渲染資源,則可恢復執行下一步操作.若等待請求云渲染資源時間超時,可認為此系統無法承受當前工作負載的渲染任務請求,則直接終止任務.由此可定義資源異常恢復率為:在資源不足的情況下,系統能及時調度獲得目標資源的能力.云渲染資源異常率和資源異常恢復率影響著云渲染系統的可靠性.

3) 渲染任務執行模塊的異常現象

渲染節點執行子任務不總是成功的,即,有可能子任務雖然執行完畢但是輸出了無效的中間結果.因此,檢查所有子任務是否都產生了正確有效的結果是必要的.若有的子任務執行失敗,則需要重新分配并執行.重新執行子任務也存在一定的失敗概率.當多次嘗試重新執行子任務,渲染效果仍舊沒有達到預期效果,可認為執行失敗.如果所有子任務都成功執行且效果正確,則渲染系統合并所有中間結果后得到完整的渲染結果.極端情況下,如果節點執行任務出現嚴重錯誤導致整個系統無法正常工作,例如多個節點斷電或磁盤損壞等,將直接終止任務.渲染異常率表示節點執行渲染子任務失敗的概率.渲染異常恢復率表示當有子任務執行失敗時,系統重新分配子任務并且最終執行成功的概率.因此,渲染異常率和渲染異常恢復率也影響著云渲染系統的可靠性.

1.2 基于DTMC的形式化描述

針對失效概率問題,提出概率模型用于云渲染系統形式化建模和驗證,從業務模型邏輯角度進行功能建模,從成功執行概率角度進行非功能性建模.云渲染系統任務調度需要慮內部流程結構和渲染服務,因此采用離散馬爾科夫鏈模型DTMC[19]對云渲染系統任務調度進行流程建模.

定義1.云渲染系統任務調度的概率模型定義為六元組:RM=(Snormal,Sexception,sinit,P,AP,L),其中,

1)Snormal是有限非空狀態集合,表示云渲染系統處于正常運行的狀態空間.包含所有的正常狀態,例如請求資源和分配任務等,以及初始狀態和成功結束狀態;

2)Sexception是有限非空狀態集合,表示云渲染系統處于異常運行的狀態空間,包含所有的異常狀態.除了修復文件、等待資源、重新渲染等異常狀態,還包含文件修復失敗、資源不足、渲染執行失敗等出錯狀態;

3)sinit∈Snormal代表初始狀態;

4)L:S→2AP標簽函數,用來描述狀態上的命題集合,標識具體狀態所對應的正在執行的任務操作或出錯情況.其中,AP是原子命題集合,S=Snormal∪Sexception是所有狀態空間集合;

5)P:S×S→[0,1]是狀態遷移概率函數,表示云渲染系統中從某一個狀態是否會遷移轉換到另一個狀態以及狀態遷移概率.

概率模型的每個狀態對應云渲染系統任務調度的一個任務節點,每次任務執行視為執行渲染服務或使用資源.該云渲染系統模型描述了流程狀態、狀態變遷信息和概率.此外,將系統狀態集合分成正常和異常兩種狀態集,用執行步驟與出錯描述作為狀態,并加入錯誤狀態描述出現的異常情況.為了將任務調度的流程轉化為相應的概率模型,給出了如下幾種通用轉化規則:

定義2.云渲染系統任務調度的形式化建模轉化規則包括順序執行、條件分支和循環操作等.

1)順序執行:按照渲染流程任務依次執行操作.圖3 給出了順序任務到概率模型的轉換規則;

2)條件分支:當流程中遇到條件判斷時會執行兩種不同的渲染操作,從而產生兩個不同的計算結果.在概率模型中可以直接展現成兩條概率路徑,但要求狀態轉移概率值相加為1.圖4 給出了條件分支任務到概率模型的轉換規則,其中,p和1-p分別是兩個分支的發生的概率;

3)循環操作:當流程中遇到條件判斷時,執行結果中有一分支是返回執行跳轉前的步驟以構成循環.圖5給出了循環任務到概率模型的轉換規則,其中,1-p是發生自循環的概率.

Fig.3 Transformation rule for sequence圖3 順序任務轉化

Fig.4 Transformation rule for branch圖4 條件分支任務轉化

Fig.5 Transformation rule for loop圖5 循環任務轉化

1.3 云渲染系統概率模型

根據上節定義1,結合圖2 所示平臺,將云渲染主要流程分為3 個模塊:準備待渲染文件、獲取云渲染資源、執行渲染任務.表1 所示云渲染系統模型的狀態定義信息.

定義3.將云渲染系統模型的狀態定義分為:

1)云渲染系統的執行成功狀態記為ssucc,失敗狀態記為sfail;

2)其他狀態用s(a,b)表示,表示a為功能模塊的編號,b為a功能模塊中某一步操作或者某一錯誤的編號.

結合定義2 轉化規則,如圖6 所示是圖2 云渲染系統的概率模型實例.

Table 1 State definition for cloud rendering system表1 云渲染系統模型的狀態定義表

Fig.6 An example of probabilistic model for cloud rendering system圖6 云渲染系統的概率模型實例

如圖7 所示是圖6 模型的準備渲染文件模塊,包括校驗文件完整性和修復損壞的文件.該模塊有兩個執行步驟和一個出錯描述,分別對應狀態s(1,1),s(1,2),s(1,3).校驗文件時可能會出現文件損壞異常,需要執行修復文件操作以恢復到正常狀態.如果修復操作執行失敗,云渲染系統無法繼續執行任務,則進入失敗狀態.因此,在跳轉到失敗狀態sfail前加上一個錯誤狀態s(1,3),用于描述系統運行失敗是由于文件無法修復導致的.而狀態s(1,2)到s(1,1)變化描述了可修復的概率遷移.

如圖8 所示是圖6 模型的請求云渲染資源模塊,包括請求云渲染資源、等待云渲染資源和獲得云渲染資源這3 個步驟,分別對應概率模型中的狀態s(2,1),s(2,2),s(2,3).在請求云渲染資源時,可能因資源被其他渲染任務占用而無法足夠分配,使得系統會進入等待云渲染資源的異常狀態.當等待時間超出限制時間時,系統返回云渲染資源不足的錯誤警告,表示運行失敗.因此,在失敗狀態sfail前添加一個云渲染資源不足的錯誤狀態節點.此外,等待云渲染資源和獲取云渲染資源是耗時操作,所以狀態s(2,2)和s(2,3)存在自循環.

Fig.8 Module of rendering resource request圖8 請求云渲染資源模塊說明

如圖9 所示是圖6 模型的渲染任務執行模塊,包括分配渲染子任務、執行渲染子任務、保存中間結果、刪除錯誤中間結果、重新分配未完成的渲染子任務、合并渲染結果等,分別對應狀態s(3,1),s(3,2),s(3,3),s(3,4),s(3,5),s(3,6).執行渲染子任務時,可能因為程序漏洞或硬件損壞導致渲染任務執行失敗,所以在失敗狀態sfail前添加渲染執行失敗的狀態s(3,7).然而即使渲染子任務執行成功了,也不能保證產生的中間結果是正確的,在這種情況下,系統會嘗試重新分配這些渲染子任務給計算節點執行.如果嘗試次數超出允許的最大次數,則進入狀態s(3,6)表示合并正確的中間結果.如果渲染子任務沒有全部完成,只合并了部分中間結果,也視為執行失敗,即狀態s(3,6)仍有一定概率遷移到錯誤狀態s(3,7).當所有渲染子任務都產生正確結果,則視為系統運行成功,即狀態s(3,6)遷移到成功狀態ssucc.

概率模型狀態轉移的概率參數值可以從實際云渲染系統中統計獲得.在概率模型的狀態遷移概率矩陣P中,行列分別對應云渲染系統概率模型的狀態,其中,pij表示狀態i遷移到狀態j的概率值.如下矩陣P是圖6 云渲染系統的概率模型各狀態之間的遷移概率信息示例.

Fig.9 Module of rendering task execution圖9 執行渲染任務功能模塊說明

2 可靠性檢驗性質描述

可靠的渲染服務不僅滿足預期用戶對渲染作業的功能性需求,而且在受到干擾(外部攻擊、錯誤操作或網絡環境影響)時,具有連續提供渲染服務的能力,不會出現用戶需求以外的錯誤行為.本節考慮云渲染服務質量屬性,基于PCTL 性質描述方法從系統運行結果、系統出現異常的概率、異常恢復概率這3 個方面定義可靠性檢驗公式.

2.1 概率計算樹邏輯PCTL

概率計算樹邏輯PCTL 用概率運算符號P～p定量地擴展了計算樹邏輯(CTL)的路徑量詞A(all)和E(exists).基于PCTL 能夠定量描述系統性質以及概率事件等.

定義4.每個PCTL 概率計算樹邏輯公式由原子命題、邏輯運算符、概率運算符以及時態運算符構成[18,19],通過以下公式構造獲得:

1)命題常量{true,false}和原子命題p是PCTL 公式;

2)如果φ,φ是PCTL 性質,則?φ,φ∧φ,φ∨φ,φ→φ,Xφ,Fφ,Gφ,φUφ和φU≤kφ是PCTL 公式;

3)如果φ是PCTL 性質,則P～p(φ)是PCTL 公式,稱為極值公式;

4)如果φ是PCTL 性質,則P=?(φ)是PCTL 公式,稱為計算公式.每個概率計算樹邏輯PCTL 公式由概率運算符和路徑公式組成,其中,路徑操作符包括X(next),F(future),G(globally),U(until)這4 種.概率運算符分為兩類.

· 第1 類是有關定量判斷限定符～∈{<,≤,>,≥},描述滿足性質的路徑概率是否符合用戶指定閾值.概率操作符～p表示可達概率,其中,p∈[0,1]是給定的限定(界限)概率值.k∈?＞0表示路徑的步長,≤k表示在k步執行之內;

· 第2 類是有關計算定量數值符號=?,計算滿足性質的路徑概率值.

概率模型檢驗工具PRISM 已實現對帶概率約束的系統行為進行建模和驗證,支持對PCTL,PCTL*等定量性質的執行.實例說明:如性質公式P≤0.75(trueU≤5login)表示至少在5 次操作內成功并登錄的概率最大值為0.75,而性質公式P=?(trueUfail)表示系統出現故障的概率;如性質公式P=?(FTaskFailed)表示計算將來出現任務失敗的概率;又如,性質公式P=?(F(RequestResources→FGetResources))表示計算發出請求資源后獲得資源的概率.

2.2 系統運行結果描述

云渲染系統執行渲染任務成功時會輸出渲染結果,而失敗分兩種情況:一是執行渲染任務之前出錯,導致任務提前終止;二是執行部分渲染子任務出錯,導致系統只輸出部分渲染結果并終止.針對云渲染系統運行狀態和渲染作業結果,基于PCTL 語法定義以下定量檢驗性質.

性質1.系統運行成功的概率:

性質公式描述了系統狀態遷移step步內,即在執行渲染任務過程中,異常次數未超出限制且完成了全部渲染子任務的概率.此時,若系統運行成功的概率設置為大于95%,則通過比較執行結果與95%得出定量結論.

性質2.系統運行失敗的概率:

性質公式表示系統狀態遷移step步內,即在執行渲染任務過程中,異常次數未超出限制、且未完成任何渲染子任務就到達失敗狀態的概率.其中,s=15 表示失效狀態,其他相關編碼見后文表4 所示.此時,若系統運行失敗的概率設置為小于1%,則通過比較執行結果與1%得出定量結論.

性質3.系統不能完成全部渲染子任務概率:

性質公式表示系統狀態遷移step步內,即在執行渲染任務過程中,異常次數未超出限制、但只完成部分渲染子任務的概率.此時,若系統不能完成全部渲染子任務概率設置為小于95%,則通過比較執行結果與95%得出結論.

上述性質1～性質3 的公式中,step表示系統狀態遷移的步長,exception表示系統出現異常狀態的總次數,upper表示允許系統出現異常最大次數.布爾變量all_complete表示系統是否完成所有的渲染子任務,布爾變量part_complete表示系統是否只完成部分渲染子任務.

2.3 系統出現異常描述

云渲染系統進入異常狀態主要分為3 種情況:(1) 接收用戶提交的云渲染任務和存儲待渲染文件的過程中有一定機率造成文件損壞,使得渲染文件不可用,若修復文件失敗,則整個渲染任務無法進行;(2) 請求云渲染資源時,可能會遇到計算資源不足的情況,導致當前云渲染任務長時間等待分配云渲染資源,整個渲染任務無法正常進行;(3) 由于計算節點配置各不相同,計算能力也有差異,不能保證每個渲染子任務都成功執行并得到正確結果.整個渲染任務結束后,系統將嘗試重新分配和執行未完成的子任務,但可能發生多次嘗試后仍然失敗的情況.針對云渲染系統的上述異常情況,基于PCTL 語法定義以下定量檢驗性質.

性質4.用戶上傳的文件損壞的概率:

性質公式表示系統狀態遷移step步內,即在執行渲染任務過程中,出現過異常且修復過文件的概率.此時,若用戶上傳的文件損壞的概率設置為小于1%,則通過比較執行結果與1%得出結論.

性質5.系統等待分配云渲染資源超時的概率:

性質公式表示系統狀態遷移step步內,即在執行渲染任務過程中,出現過異常且等待過云渲染資源的概率.此時,若系統等待分配云渲染資源超時的概率設置為小于1%,則通過比較執行結果與1%得出結論.

性質6.節點執行渲染子任務產生不正確結果的概率:

性質公式表示系統狀態遷移step步內,即在執行渲染任務過程中,出現過異常且重新嘗試過執行渲染子任務的概率.此時,若節點執行渲染子任務產生不正確結果的概率設置為小于1%,則通過比較執行結果與1%得出結論.

上述性質4～性質6 的公式中,step表示系統狀態遷移的步長,exception表示系統出現異常狀態的總次數,repair_file表示系統修復文件的次數,wait_resources表示系統進入等待計算資源的狀態的次數,rerendering表示系統重新執行失敗的渲染子任務的次數.

2.4 系統異常恢復描述

對于云渲染系統這種結構復雜的系統,運行時出現異常是不可避免的.但可靠性也表現為從異常狀態中恢復的能力.針對云渲染系統異常恢復,基于PCTL 語法定義以下定量檢驗性質:

性質7.用戶上傳的待渲染文件損壞時,系統能夠及時修復的概率:

在該性質公式的百分比中:分母為系統執行過程中出現文件損壞的概率;分子為系統狀態遷移step步內,修復文件且將文件修復完好的概率.整個公式表示系統在進入文件損壞異常時,修復文件成功的概率.此時,若系統能夠及時修復的概率設置為大于95%,則通過比較執行結果與95%得出結論.

性質8.系統等待分配云渲染資源超時后,能通過資源分配策略,經過有限的狀態遷移后獲得足夠資源的概率:

在該性質公式的百分比中:分母為系統執行過程中出現長時間等待云渲染資源情況的概率;分子為系統狀態在遷移step步內,等待云渲染資源且成功獲得云渲染資源的概率.整個公式表示系統在進入長時間等待云渲染資源異常時,能成功獲取到云渲染資源的概率.此時,若經過有限的狀態遷移后獲得足夠資源的概率設置為大于95%,則通過比較執行結果與95%得出結論.

性質9.當部分渲染子任務執行失敗時,系統通過重新分配子任務給計算節點進行渲染并執行成功,得到正確結果的概率:

在該性質公式的百分比中:分母為系統執行過程中渲染子任務執行失敗的概率;分子為系統狀態遷移step步內,重新執行過渲染子任務且最終完成所有渲染子任務的概率.整個公式表示系統在出現渲染異常時,能重新分配并完成所有任務的概率.此時,若系統通過重新分配子任務給計算節點進行渲染并執行成功,得到正確結果的概率設置大于95%,則通過比較執行結果與95%得出結論.

上述性質7～性質9 的公式中,step表示系統狀態遷移的步長,exception表示系統出現異常狀態的總次數,repair_file表示系統修復文件的次數,wait_resources表示系統進入等待計算資源狀態的次數,rerendering表示系統重新執行失敗的渲染子任務的次數,布爾變量file_ok表示用戶文件是否完好無損,布爾變量resources_ok表示系統是否獲得足夠的云渲染資源,布爾變量all_complete表示系統是否完成所有的渲染子任務.

1）葡萄已經生長到8片葉，受凍很嚴重，甚至所有新梢都凍死了。外國專家的建議是，不用剪掉已經凍死的枝條，讓其自然生長，葡萄自身具備受損后的恢復機能，會啟動新梢基部或原來新梢著生的結果母枝上的次生芽萌發出新的枝條，這些次生枝條當年可能會有一些有限的產量，但第2年的產量恢復情況會更好。如果人為剪掉凍壞的新梢，不但費工費時增加成本，還可能會不小心傷及基部的次生芽，得不償失。當然，由于新梢形成很晚，冬季修剪需要多下些功夫。

3 實驗與分析

本節實驗主要是采用PRISM 工具執行定量驗證,實驗對象為圖2 所示流程實例.為了進行仿真實驗,本文使用20 臺計算機搭建了小型云渲染系統的存儲和計算節點.實驗環境具體配置見表2.

Table 2 Computer configuration of experiment表2 實驗環境計算機配置

該云渲染系統運行一周后,從系統日志中得到狀態遷移概率矩陣P中的各項參數概率值.表3 是PRISM 代碼中描述概率的變量信息和相關賦值操作.表4 所示PRISM 代碼中描述變量的值與狀態名稱對應關系.具體云渲染系統概率模型詳見附錄1 的代碼.

Table 3 Probability of parameters from system running log表3 系統運行日志的參數概率值

Table 4 Mapping between state and value表4 狀態名稱對應表

3.1 基于PRISM的可靠性檢驗實驗

得到云渲染系統任務調度的概率模型后,根據第2 節描述的可靠性檢驗性質,執行概率模型檢驗.通過分析執行結果的定量數值,評估云渲染系統是否滿足預期可靠性需求.

圖10 是性質1 的檢驗結果,其中,橫坐標表示執行步長,縱坐標表示概率值.實驗分別設置upper為0～5.觀察結果可知:系統未出現異常狀態完成渲染任務的概率低于95%;系統出現1 次異常狀態完成渲染任務的概率大于95%;系統出現2 次及以上異常狀態完成渲染任務的概率接近97%.允許的異常狀態次數越多,渲染系統運行成功的概率越高.這是由于云渲染系統具有異常狀態修復能力.因此,系統滿足性質1,即該云渲染系統在允許出現異常的前提下,執行渲染任務成功的概率大于95%.

圖11 是性質2 的檢驗結果,其中,橫坐標表示執行步長,縱坐標表示概率值.實驗分別設置upper為1～5.從圖中結果發現:系統狀態轉移次數在6 次以內,渲染任務失敗的概率非常小,其原因可能是文件異常和云渲染資源不足;而隨著狀態轉移次數的不斷增加,系統執行渲染子任務失敗的概率明顯上升;另外,隨著允許出現異常狀態最大次數的增加,系統運行失敗的概率也隨之升高,接近1.5%.因此,該云渲染系統不滿足性質2,即系統狀態遷移6 步之外,執行渲染任務出錯的概率大于1%.

Fig.10 Verification result of property 1圖10 性質1 檢驗結果

Fig.11 Verification result of property 2圖11 性質2 檢驗結果

圖12 是性質3 的檢驗結果,其中,橫坐標表示執行步長,縱坐標表示概率值.實驗分別設置upper為1～5.觀察結果可知:隨著狀態遷移次數的增加,系統不能完成全部渲染子任務的概率不斷升高;當系統僅允許1 次異常時,部分任務失敗的概率小于1.675%;當系統的允許異常次數在2 次及以上時,部分任務失敗的概率超過1.675%.由于允許異常次數的增加,給了云渲染系統更多的機會去重新執行之前失敗的渲染子任務.因此,該云渲染系統不滿足性質3,即系統完成全部的渲染子任務的概率大于1%.

圖13 展示了性質4～性質6 的檢驗結果.觀察結果可知:文件損壞的異常出現得比較早,是因為執行渲染任務前首先要對待渲染文件進行檢驗;出現長時間等待云渲染資源的概率極小,不足0.25%;渲染異常與文件異常的概率較大,超過1.25%.因此,該云渲染系統滿足性質5,但不滿足性質4 和性質6.即系統運行過程中,發生文件損壞異常和渲染異常的概率大于1%,而發生長時等待云渲染資源的異常概率小于1%.

Fig.12 Verification result of property 3圖12 性質3 檢驗結果

Fig.13 Verification result of property 4～6圖13 性質4～性質6 檢驗結果

圖14 展示了對性質7～性質9 的檢驗結果.觀察結果可知:文件異常較渲染異常能更早得到修復,這也符合云渲染系統的實際任務執行流程.本實驗的云渲染系統對3 種異常的恢復能力相對較高,恢復到正常狀態的概率均大于95%.對文件異常的修復能力也較高,修復成功率大于97%.因此,該云渲染系統滿足性質7 至性質9,即系統運行過程中對文件異常,云渲染資源異常以及渲染異常的成功修復概率均大于95%.

通過對上述實驗結果的分析,統計出該云渲染系統可靠性檢驗結果,見表5.

在本實驗中,云渲染系統滿足了5 條檢驗性質,即性質公式1、性質公式5、性質公式7～性質公式9.考慮到性質公式2～性質公式4、性質公式6 不滿足,通過對定量數值進一步分析,給出了如下結論和建議.

1)從系統執行結果的角度看,系統在理想狀態(零異常發生)下執行渲染任務成功率為94%.出現異常次數越多,表明系統的穩定性越差.由于云渲染系統具備較好的異常狀態修復能力,當允許的異常次數增加,系統成功運行的概率也隨之提高.允許的異常次數大于2 時,系統成功運行的概率接近97%;

2)從異常率的角度看,文件發生異常的概率比較高,說明文件傳輸或文件存取模塊的程序存在漏洞,也有可能是因為存儲節點的硬件質量問題或硬件穩定性不達標.對于防范文件異常而言,需要更換高質量的存儲設備并優化文件傳輸和存取程序.渲染異常和文件異常的發生概率同樣高,這可能是由于計算節點的渲染算法或CPU 和GPU 計算壓力過大導致.對于防范渲染異常,需要優化渲染算法或者考慮選用計算能力更強的計算機作為計算節點.云渲染資源不足的異常率較低,說明在本實驗環境下該云渲染系統有充足的計算節點和存儲節點,能夠滿足渲染任務的資源需求;

3)從異常恢復率角度看,若損壞文件被成功修復的概率很高,說明文件備份和還原修復的功能良好.當渲染任務長時間等待云渲染資源時,若及時分配請求資源的概率較高,表明云渲染資源的分配和調度策略是適用于當前云渲染系統的.當部分渲染子任務失敗時,若能及時刪除并重新分配子任務,表明云渲染系統對渲染任務的分配和調度能力較高.總體來說,系統進入異常狀態后,能恢復到正常狀態的概率是評估可靠性的重要指標.

Fig.14 Verification result of property 7～9圖14 性質7～性質9 的檢驗結果

Table 5 Verification result of all given properties表5 云渲染系統可靠性檢驗結果

3.2 基于檢驗結果的改進實驗

綜合上述3 個方面的分析可知:如果要提高渲染系統可靠性,需要對文件準備模塊和渲染執行模塊進行優化配置.本節基于檢驗結果對云渲染系統提出改進方案以提高系統可靠性,之后再次執行概率模型檢驗對可靠性檢驗性質進行校驗,以期能提高相關定量數值.

首先,文件準備模塊主要執行校驗文件和修復文件等操作,所以文件的存儲方式和存儲節點的性能需要額外關注.在本實驗平臺下,在文件存儲到節點前,系統讀取預先設定好的存儲塊閾值,即根據BLOCK_SIZE的值來決定是否分割文件.如果文件大小超過預設大小,則文件會被分割成小于或等于BLOCK_SIZE大小的數據塊后再存儲到節點中.此外,數據塊會有多個副本存儲在不同節點上,但是由于實驗系統使用普通機器作為云渲染主機,其存儲和讀取數據的性能較低.如果數據塊副本數量適當增加,也可以提高存儲系統的容錯率,從而提高存儲和讀取可靠性.表6 代碼是為云渲染系統的HDFS 副本數量.

Table 6 Copy parameter setting of HDFS in cloud rendering system表6 云渲染HDFS 副本數量設置

其次,渲染執行模塊主要由計算節點接收和執行渲染子任務,要求執行渲染任務的計算節點能夠承擔高計算量并擁有足夠的穩定性,使得每個子任務順利執行.本實驗系統中的各個設備的CPU 和GPU 性能都較低,容易導致執行渲染子任務失敗.調整后的實驗設備硬件配置見表7.從表中可以看出:CPU 更換成英特爾i7 或i5 處理器,內存為8G 容量,同時更換了性能較高的顯卡.由于本實驗系統滿足性質5,即出現云渲染資源不足的異常概率較小,因此可以認為當前系統云渲染資源充足,不需要增加計算機設備數量.表7 是更新后的實驗配置,其中計算機數量與表2 保持一致.

Table 7 Updated computer configuration for experiment表7 更新后的計算機配置

根據上節內容調整策略后,向系統提交同樣數量和類型的渲染任務.待系統運行數周之后,再從系統日志管理模塊中獲取新的概率參數值.表8 是改進后云渲染系統的概率變量參數和數值.

Table 8 Probability of parameters after improvement表8 改進后的變量參數和概率數值

接著,執行概率模型檢驗,得到圖15～圖18 的實驗數據.

圖15 是對性質1 的檢驗結果.對照圖9 可知:改進前后的系統運行成功的概率隨系統狀態轉移步數的變化趨勢相似,但是改進后的系統運行成功的概率明顯提高.改進之前系統運行成功的概率接近97%,改進之后的概率超過了97.5%.因此,系統改進后仍滿足性質1,即系統運行成功的概率大于95%.

圖16 是對性質2 的檢驗結果.對照圖10 可知:系統狀態轉移次數在6 次以內,出現任務失敗的概率非常小;隨著狀態轉移次數的不斷增加,出現系統運行失敗概率驟增現象;當允許的異常狀態次數增加后,系統運行失敗的概率小幅上升;改進前的失敗概率接近1.5%,改進后的失敗概率值下降,接近1%.改進后的云渲染系統雖然仍不滿足性質2,但是可靠性已有小幅度提高.因此,該改進策略方向正確,具有一定的參考性.

Fig.15 Verification result of property 1圖15 改進后對性質1 的檢驗結果

Fig.16 Verification result of property 2圖16 改進后對性質2 的檢驗結果

圖17 是對性質3 的檢驗結果.對照圖11 可知:隨著系統狀態遷移次數的增加,系統不能完成全部渲染子任務的概率不斷升高;改進后,當系統僅允許2 次以內異常時,部分任務失敗的概率小于0.7%;當系統的異常次數在2 次以上時,系統只完成部分渲染子任務的概率增加,超過了0.7%,但均沒有超過1%.因此,改進后的云渲染系統滿足性質3,即系統不能完成全部的渲染子任務的概率小于1%.

圖18 展示了對性質4～性質6 的檢驗結果.對照圖12 可知:系統文件異常和渲染異常發生的概率明顯下降;文件異常發生的概率略高于0.8%,但低于1%;渲染子任務執行異常發生的概率在0.5%～0.6%之間;由于系統改進方案沒有涉及云渲染資源總量,云渲染資源不足的異常發生概率幾乎保持不變.改進后的云渲染系統同時滿足性質4～性質6,即云渲染系統3 個功能模塊發生異常的概率都小于1%.

Fig.17 Verification result of property 3圖17 改進后對性質3 的檢驗結果

Fig.18 Verification result of property 4～6圖18 改進后對性質4～性質6 的檢驗結果

圖19 展示了對性質7～性質9 的檢驗結果.對照圖13 可知:系統改進前后各個功能模塊的異常恢復率都高于95%.改進后的異常恢復率小幅提高,其中,由于改進方案中增加了數據塊的副本數,文件異常恢復率更加接近98%.在云渲染資源不足的情況下,由于改進方案中提升了計算節點的CPU 性能,異常恢復率和渲染子任務執行異常的恢復率也提升到了97.5%以上.因此,改進后的系統仍然滿足性質7～性質9,即3 個功能模塊的異常恢復率均大于95%.

綜上所述,表9 是對檢驗結果匯總.

總的來說,改進后的云渲染系統滿足8 條可靠性性質.相較于改進前,改進后的云渲染系統的可靠性水平有所升高.改進后的系統同時滿足了性質3、性質4 和性質6,說明改進后的云渲染系統出現文件損壞和文件無效的異常概率下降,節點執行渲染子任務失敗的概率也有所下降,這些都有助于確保渲染作業正確執行.

Fig.19 Verification result of property 7～9圖19 改進后對性質7～性質9 的檢驗結果

Table 9 Verification result of all given properties after improvement表9 改進后的系統可靠性性質檢驗結果匯總

4 相關工作

渲染任務是計算密集型和數據密集型作業.傳統以單機模式的渲染方法存在計算效率低和耗時等問題.因此,研究人員開始關注分布式計算方法以多機聯合輔助形式實現渲染任務.Mahsa 等人[20]提出了一種支持3D 視頻遠程渲染模型,能在減少視頻傳輸延遲的同時保障渲染質量.由于網絡和云的不確定性,延遲傳輸是導致系統異常的重要因素,提高可靠性問題是云渲染的任務調度和優化的核心.Donghyeok 等人[21]提出了一種基于移動云的交互式3D 渲染和流媒體系統,包括支持軟件定義網絡(SDN)的自適應云資源管理模塊和上下文感知的3D渲染和流媒體模塊,以提高渲染和流服務的服務質量.但該方法的自適應云資源管理和上下文感知涉及大規模流式數據的存儲和交換,因此,如何評估最優渲染服務器是非常重要的研究點.Audrius 等人[22]提出了基于Game Large 架構模式的遠程渲染系統.當客戶端的硬件或網絡不通暢時,系統通過視頻流將圖形渲染切換到服務器,并將結果壓縮為能夠在客戶端使用的視頻流.這一混合模式雖然提高了任務持續性,但是仍然缺乏大規模云端服務器應用的數據交換和服務器性能監控等相關方法和技術.Li 等人[23]提出了一種高效的兩層結構的作業調度和任務調度策略(RF-FD)用于集群渲染系統,其中:RF 策略利用低優先級作業使得作業在被阻塞時最大化資源利用率;而FD 策略利用資源使用反饋來選擇渲染器并為其分配相應線程,并將渲染節點劃分為細粒度渲染單元以平衡負載分布.從技術角度看,這些策略和方法有助于實現任務調度的可靠性,但是策略制定和自動化執行策略還需要進一步研究和提高.

針對云計算環境,相關分布式協作平臺和研究成果正促使傳統的渲染服務向云渲染模式方向發展.Liu 等人[24]提出了基于Hadoop 的大型渲染系統,將場景解析后每一幀渲染對應的場景文件存儲到HDFS 上,利用它的數據本地性減少數據傳輸消耗的時間;同時,利用MapReduce 編程模型完成作業的調度.Zhou 等人[25]針對超大規模渲染云問題,提出一種5 級軟件架構的黃金農場集群渲染平臺,包括基礎架構層、平臺服務層、應用服務層、服務管理和訪問接口.開發并部署在“天河-1A”超級計算機上,能夠管理多達2 000 個高性能渲染節點,支持同時使用24 000 個CPU 進行并行任務渲染.由于3D 模型的大小和復雜性,渲染過程耗時且生產力低下.Kijsipongse 等人[26]評估了BitTorrent 文件系統,通過對等方式傳播數據,并使用本地緩存來縮短渲染時間,改進了分布式動畫渲染的通信性能.Wu 等人[27]設計了云三維動畫渲染系統,通過云計算模式,可以縮減動畫的渲染時間,并且顯著提升渲染效果.雖然這些平臺在一定程度上解決了不同類型的渲染任務,但是值得注意的是:由于網絡不穩定性,任務調度的可靠性方面需要進一步研究.

渲染通常在分布式計算環境下進行,其執行大量并行計算來加速渲染作業,且異構網絡下的數據服務成本受限.因此,越來越多的學術界和工業界的研究者關注任務調度中數據流和工作負載等方面問題,致力于提高渲染效果.Cristian 等人[28]針對二維圖像的輸出序列中幀丟失問題,提出了一種并行計算解決方案.該方案由多個基于GPU 異構節點組成渲染方案實現交替幀渲染.在移動設備上處理3D 模型較為困難,Yan 等人[29]提出了一種包括自適應分裂和錯誤處理機制的傳輸控制方法,并將其與典型的遠程渲染系統相集成.該機制可以通過分割操作交易傳輸來降低傳輸頻率.Vilutis 等人[30]針對任務延遲問題,提出了混合云的工作負載均衡算法用于渲染服務,以確保其基于云的及時交付.Dobashi 等人[31]提出了一種借助求解反演渲染方法來解決渲染參數設置問題,給定非均勻的合成云密度分布,使用遺傳算法搜索最佳參數,對渲染合成云的參數進行估計.上述方法雖然考慮到任務/數據可靠性問題,但是在性能計算和評估方面還缺少相關技術支撐.近年來,越來越多的研究人員關注云渲染的可靠性,特別是對網絡系統、通信系統引起的不可靠、不可預測性行為進行定量建模和檢驗.形式化驗證技術作為一種可行方法,尤其是概率模型檢驗技術,能實現對流程進行定量和定性的檢驗.但目前鮮有概率模型檢驗技術在云渲染系統上的相關應用研究.與上述工作不同,本文重點關注采用概率模型檢驗驗證云渲染系統任務調度的流程可靠性,并通過定量的驗證結果數值指導如何設計云渲染系統優化改進策略,以確保云渲染系統提供可靠的渲染服務.

5 總結

隨著互聯網和云計算技術的快速發展,使用云渲染系統有助于企業在較短時間內完成預期的渲染工作,在影視和動畫等行業具有廣泛應用前景和推廣市場.渲染任務執行和調度過程對用戶而言是透明的,即提交渲染文件后由渲染系統在云端自動執行相對應的渲染操作并返回渲染結果.然而,網絡的不確定性等諸多影響因素使得用戶更加關心渲染任務的可靠性,因此,有必要針對云渲染系統任務調度流程進行正確性和可靠性檢驗.同時,可靠性評估的定量數值可以指導云渲染系統進行任務切換,以確保渲染服務持續和穩定運行.基于此,本文提出了基于概率模型檢驗的云渲染任務調度定量驗證方法.從系統運行成功率、異常率和異常恢復率這3 個角度分析云渲染系統的可靠性,并定義可靠性檢驗性質公式,通過PRISM 執行概率模型檢驗得到定量結果用于可靠性和系統性能評估.在實驗部分,搭建了實驗環境,一方面檢驗和計算云渲染系統可靠性;另一方面,根據性能評估結果執行指導云渲染資源的分配和調度策略.實驗證明了本文方法的可行性和有效性,對提高云渲染系統服務可靠性具有指導意義.

在未來工作方面,將增加實驗環境的計算節點數量,增加實驗用戶數和并發量,提交更多的渲染任務,研究分布式渲染數據的收集和處理方法.此外,針對定量檢驗結果,研究基于服務質量參數的自我評估和自動修正方法,從而增強異常情況下實時任務調度的可操作性.

附錄1 PRISM 構建云渲染系統概率模型

根據PRISM 建模語言語法規則,所構建的云渲染系統概率模型名為“Cloud Rendering System”,其核心代碼如下所示.

代碼的第2 行～第10 行對模型參數進行定義,具體變量描述見表10.代碼第11 行～第22 行為系統狀態遷移的定義,其中,在一些特定的狀態遷移中加入了對異常計數類參數的自增操作,是為了記錄系統到達某一狀態時的歷史信息.代碼23 行～第29 行對邊界條件進行判斷,例如:異常發生的次數超過邊界值,則直接進入失敗狀態.

Table 10 Parameters introduction for Cloud Rendering System model表10 Cloud Rendering System 模型的參數變量定義