蘇 謨,趙玉彬,郭銳鋒,王其樂

1(中國科學院大學,北京 100049)2(中國科學院 沈陽計算技術研究所,沈陽 110168)3(沈陽市第三十一中學,沈陽 110021)

1 引 言

隨著摩爾定律的失效及三維可視化[1]需求與設計的復雜性日益加深,邏輯處理的并行化[2]越來越受到重視.同時隨著Entity-Component-Entity[3-5]模型等面向數(shù)據設計方式的提出,邏輯的并行處理設計難度也越來越低.在虛擬仿真等三維可視化系統(tǒng)設計中,狀態(tài)存檔[6](存檔回放)一直作為一個必需的功能存在,是后期復盤分析以及系統(tǒng)的缺陷分析等需求的核心組成部分.在并行設計的虛擬仿真系統(tǒng)的中,系統(tǒng)狀態(tài)的變化需要滿足實時性,但是由于狀態(tài)改變的速率較快,需要存檔的狀態(tài)信息量較大,以及并行存檔過程為了解決并行沖突,必須采用串行化處理方式等,導致了并行系統(tǒng)的存檔過程延遲大等問題.而且,在并行邏輯處理的系統(tǒng)中,由于存在系統(tǒng)調度以及任務間交叉運行等動態(tài)情況,即使采用串行化的狀態(tài)存檔方式,也無法保證存檔的狀態(tài)是按照狀態(tài)改變的時序記錄下來的,會在存檔過程中出現(xiàn)狀態(tài)存檔的順序與實際狀態(tài)發(fā)生的順序不一致的情況.

針對并行系統(tǒng)中狀態(tài)存檔沖突的問題上,文獻[7]在設計異構并行仿真引擎的過程中,解決存儲沖突的方式是利用GPU的加法原子操作來設置同步點,多個線程在該點上順序執(zhí)行,這種方式原理上還是采用串行執(zhí)行的方法解決沖突;文獻[8]提出一種名為Instant Replay的存檔重放方法,這種方法按照訪問內存的順序進行存檔和設計回放,并且適用于并行系統(tǒng),然而從內存訪問層面設計狀態(tài)存檔會造成巨大的性能開銷;文獻[9]分析了存檔回放設計的困難原因,并且說明了正確使用互斥、同步等操作可以提高程序的性能,但是會由于狀態(tài)信息的數(shù)據量大而會造成很大的性能開銷;文獻[10]提出從效率方面對存檔回放進行分析和評價;文獻[11]分析了在狀態(tài)存檔和回放問題上的軟件和硬件實現(xiàn)的接口.由于并行的三維可視化系統(tǒng)狀態(tài)存檔屬于非嚴格確定性[10]的狀態(tài)存檔類別,保證可見狀態(tài)相同即可,對于線程間執(zhí)行期間的交叉順序并不敏感,通過邏輯時鐘來確狀態(tài)改變的順序是可以保證其正確性的.存檔性能開銷主要集中存檔過程的串行化處理上,雖然無鎖隊列[12]的應用一定程度上改進了狀態(tài)存檔過程中性能上的問題,但是無鎖隊列本身設計較復雜并且在狀態(tài)存檔過程中會出現(xiàn)時序錯亂的問題.因此,本文針對并行系統(tǒng)下狀態(tài)存檔以及時序上的問題,提出一種沖突消減的方法,減少并行存檔過程中的沖突,并且在狀態(tài)恢復時可以保證完整的時序,同時該方法具有簡明和高效等特點.

2 并行系統(tǒng)下狀態(tài)存檔問題分析與解決

并行系統(tǒng)下的狀態(tài)存檔問題集中點在如何避免并行狀態(tài)存檔下串行化的執(zhí)行問題,以及如何來滿足嚴格的時序性問題上.并行系統(tǒng)下存檔沖突的問題是難以避免的,但是通過一定的手段可以將發(fā)生沖突的概率降低.狀態(tài)存檔恢復過程的時序性是保證復原過程正確的關鍵,通過對于并行系統(tǒng)下狀態(tài)存檔的形式、目的進行分析,并且通過嚴格定義的方式,保證在復原過程中狀態(tài)序列的時序性特征,正確還原出整個狀態(tài)變化的過程.

2.1 并行狀態(tài)存檔中的原則與概念

在并行系統(tǒng)中狀態(tài)的存檔通常需要考慮的以下三個基本原則:

原則1.確定性:存檔的狀態(tài)數(shù)據作為輸入時,保證邏輯計算對于相同輸入獲得相同的輸出結果.針對于不確定的系統(tǒng)變量參與的計算,需要同時將這些系統(tǒng)外部參數(shù)作為確定性的狀態(tài)進行存檔,避免環(huán)境的不同而導致的計算結果的不同[13].

原則2.時序性:所有的狀態(tài)信息具有在整個狀態(tài)變化序列中對應的位置,從時序角度考慮為對應的狀態(tài)改變的時間節(jié)點,即狀態(tài)存檔的狀態(tài)信息在復原過程中需要滿足其生成時的時序性.廣義的方式是在存檔時將狀態(tài)打上邏輯時鐘時間戳來表示時序,則復原時可以保證時序性,同時邏輯時鐘需要滿足穩(wěn)定性、非遞減性等特點.

原則3.無感知性:狀態(tài)的存檔過程應該盡量低延遲.狀態(tài)存檔不得影響到正常的邏輯推進,不得使得某個線程長時間阻塞,所以應該是低延遲和穩(wěn)定延遲.

本文中包含的邏輯幀率與邏輯時鐘的相關概念解釋如下:

邏輯幀率:邏輯幀率為系統(tǒng)邏輯操作的處理頻率,與渲染幀率分離,可表示三維可視化系統(tǒng)中狀態(tài)更新的快慢.

邏輯時鐘:表示三維可視化系統(tǒng)內部操作的時間基準.可以與系統(tǒng)時鐘進行換算,并且通常是從零點開始計算.

2.2 并行系統(tǒng)狀態(tài)存檔問題分析

在并行系統(tǒng)狀態(tài)存檔過程中的性能和時序性上的問題,主要集中在狀態(tài)信息添加的方式采用追加的形式,但是由于并行執(zhí)行下很可能同時多個線程都需要進行狀態(tài)信息添加,從而導致排隊阻塞進而影響性能.雖然追加的方式在一定程度上滿足時序性,但是由于系統(tǒng)調度等因素,即使是追加的方式同樣也存在時序性不穩(wěn)定的情況出現(xiàn).

2.2.1 狀態(tài)時序性問題分解

通常定義一個狀態(tài)是否是同時發(fā)生,在不考慮偏序或全序的關系的條件的前提下,一般化的定義如公式(1)所示,這里同時發(fā)生的狀態(tài)實際上指的是在一個小時間間隔內同時發(fā)生的狀態(tài)改變.類比桶排序中的桶,這里引入時間桶的概念,將連續(xù)的時間離散成為一個個代表一段時間區(qū)間的緊密排列的時間桶,狀態(tài)改變時間在一個相同桶區(qū)間內通常認為是同時發(fā)生的.

|Tp1-Tp2|≤ε

(1)

如公式(1)表示線程P1產生狀態(tài)信息的時間和線程P2產生狀態(tài)信息的時間小于給定的閾值ε.因為模擬仿真等并行系統(tǒng)下采用的是非嚴格確定性狀態(tài)存檔,只要處理時間在一定范圍內我們可以認定兩者是同時發(fā)生的.基于這個認識,在并行處理的情況下將同時改變的狀態(tài)進行離散在不同的小時間片內,只要控制誤差范圍的精度,這種方式具有一定的可用性.并且在實際的情景下,線程的邏輯幀率處理是通過循環(huán)收集的方式,線程的執(zhí)行實際上是收集上一個邏輯幀到當前邏輯幀時間區(qū)間det內的事件.例如Unity中針對輸入的處理是在每個邏輯幀的某個階段去處理.

(2)

如公式(2)det是兩次邏輯幀的時間間隔,f代表px線程的第i個邏輯幀結束時間.計算在px線程在時間區(qū)間det范圍內的所有的邏輯并更新狀態(tài),雖然通常認為狀態(tài)改變是立即發(fā)生,實際上并不按照狀態(tài)改變的時刻立即執(zhí)行.本質上這里是允許有ε的誤差的,所以假設將狀態(tài)信息放入時間桶時,可以放在表示當前時間節(jié)點的時間桶前或者后距離ε/2的范圍內的桶里.

2.2.2 針對嚴格時序性的改造

以上方式在某些情況下是可行的,比如邏輯時鐘的粒度比較大時,但是實際環(huán)境下狀態(tài)的存檔由于并非是嚴格按照時序排列,而且通常ε的值較小,所以可以進行操縱的空間很小.在嚴格場景的情況下邏輯處理由于時間序的錯亂會引發(fā)一定的問題.

針對以上的分析進行擴展,因為通常的狀態(tài)存檔操作是為了后期的復盤分析等使用,所以需要在分析和復原的過程中才要求嚴格的時序排列.實際一定范圍內的存檔序列不符合嚴格的狀態(tài)時序序列,在恢復時采用批量加載的情形下,是可以不影響恢復過程的嚴格有序與時間復雜度的.由于嚴格的時序排列存檔過程在并行執(zhí)行下,必然會引發(fā)沖突而降低效率并且時序性也不能根本保證,所以為了提高效率降低延時,可以將整個狀態(tài)存檔信息按照狀態(tài)生成時的序列設計為基本有序即可,允許在時間片段ε之內是無序的,并且保證時間片段ε的無序并不影響狀態(tài)的恢復.這里的ε不再是之前的誤差,而是人為設定的值,可以比誤差大的多,即在這個范圍內并不嚴格要求狀態(tài)存檔時完全按照狀態(tài)改變時的時序排序.而且我們保證的這個局部的無序是向前的,即狀態(tài)放置位置在時間桶中存放更靠前,這樣的設計具有很好的性質可被利用.

圖1 狀態(tài)存檔示例Fig.1 Status record example

如圖1所示為一個人為設置的ε=3的誤差范圍的示例,第一行為邏輯時鐘,時序性使用邏輯時鐘來表示,邏輯時鐘用來表示系統(tǒng)推進的速度以及狀態(tài)發(fā)生的時間節(jié)點.邏輯時鐘是均勻嚴格的遞增序列,如果按照嚴格的時序狀態(tài)信息存檔,即傳統(tǒng)的追加的方式應該是第三行的完全時間序列,但是這種方式在并行的情況下det范圍內可能需要存檔多個狀態(tài)數(shù)據,而不是上面所列的一個狀態(tài)數(shù)據,這樣多個狀態(tài)因為都要追加到最靠前的狀態(tài)數(shù)據后面,會形成串行化的處理,必須等待同時間段的其他先提交的線程處理完才能輪到自己.第二行是非嚴格的狀態(tài)存檔順序,并且ε=3,如圖1時間戳為t的值,最終會落在狀態(tài)區(qū)間[t-3,t]的范圍內,如在t=6的時候的狀態(tài)信息,實際上落在了t=4的位置,t=8的狀態(tài)信息實際上落在了t=7的位置.這里的偏移不會超過ε,并且是完全向前偏移,例如時間t=5的狀態(tài)信息不會出現(xiàn)在t>5的位置,也不會出現(xiàn)在t<5-ε的位置.所以當有一條狀態(tài)數(shù)據的時候,我們獲得當前的邏輯時鐘并通過哈希函數(shù)把他放在之前的ε的位置區(qū)間內即可,由于這樣的位置有多個,所以大幅度減少線程并行之間的沖突.

2.3 不嚴格時序方法的偏移ε分析

這里將存檔問題進行抽象簡化,將多線程并行的存檔看做周期性循環(huán)的行為,每個周期都是M個進程同時存入狀態(tài)數(shù)據,多個周期是相互獨立的.由于ε個桶被訪問到的概率相同,則對于單獨一個桶中被線程并行訪問數(shù)量X服從二項分布.

(3)

(4)

(5)

公式(3)中的P{X=k}代表一個桶中同時k個線程訪問的概率,p代表一個線程落在某個桶中的概率,ε是線程可以存放的狀態(tài)桶的數(shù)量,M是線程的數(shù)量.當X為0和1的時候我們認為沒有出現(xiàn)碰撞,當k>1時代表發(fā)生了碰撞并且需要等待前面k-1個線程的完成,則某個桶中發(fā)生碰撞時需要等待的前面需要處理的線程的期望如公式(4)所示.通過組合數(shù)和二項分布概率計算化簡得到在一個寫入周期內,每個桶中出現(xiàn)等待線程數(shù)量的期望如公式(5)所示,其中E′代表一個桶中線程需要等待處理線程數(shù)量的期望.

E″=εE′

(6)

(7)

由于可以認為每個桶相互獨立,則每個周期出現(xiàn)等待的期望通過期望公式計算得出結果為公式(6)所示,整理得到公式(7)所示,其中一個周期的總期望用E″表示.通過公式(7)的分析,在M確定的情況可以觀察到隨著ε的增大期望值在減少;在ε確定的情況,隨著M的增加期望值在增大,由于M表示并行度,可以理解為固定值.實際上可以通過以上的計算獲得理論上在并行狀態(tài)存檔的過程中的實際加速比如公式(8)所示.

(8)

通過公式(8)的計算我們可以得出通過M在執(zhí)行寫入需要等待的時間期望與加速比.以上的公式結果可以用來評估并行狀態(tài)存檔過程中等待時延、發(fā)生碰撞概率等情況,可用于調整初始參數(shù).通過以上公式分析,在M確定的時候,當ε增大到一定范圍,則E″趨近與0,例如當M=4,ε=100時E″=0.06,由此可知等待線程數(shù)量的期望值較小,即碰撞的線程數(shù)量很少.此時的狀態(tài)存檔過程的加速比是Sp≈4.

另外,當發(fā)生沖突的時候并不一定就需要一定放在某個桶里,這里只要求放在[T-ε,T]的范圍內的桶里即可,所以可以放入桶有多個.當放入過程與其他的線程放入過程產生沖突是可以使用重哈希操作,再次進行哈希操作來找沒有發(fā)生沖突的桶進行加入狀態(tài)信息,這種方式極端情況下會出現(xiàn)“餓死”現(xiàn)象,不是延遲穩(wěn)定的,所以本文主要針對沖突等待的情況.

2.4 不嚴格時序方法狀態(tài)復原分析

在不嚴格時序方法狀態(tài)復原的過程中,涉及到兩個問題,分別是針對給定的一批數(shù)據,如何判斷給定邏輯時鐘區(qū)間內的狀態(tài)數(shù)據被加載完成,以及如果對加載完成的狀態(tài)數(shù)據進行排序處理.

問題1.給定一個如上文所提到的非嚴格時間遞增的狀態(tài)序列,根據前面的介紹這里可以認為理解為一個存在磁盤上的數(shù)據文件,從這個文件中批量加載數(shù)據,如何確定在[0,T]這段邏輯時鐘區(qū)間內的狀態(tài)已經完整被加載到內存中.

因為數(shù)據文件中的狀態(tài)數(shù)據是亂序的,在正常情況下無法一次將整個數(shù)據文件全部加載到內存排序.需要判斷加載到一定數(shù)據量之后,來確定[0,T]的時間段內的狀態(tài)是否已經完整了,這個時候才可以執(zhí)行到當前的邏輯時鐘T,否則可能會出現(xiàn)狀態(tài)丟失的情況.

針對這個問題,首先在狀態(tài)復原過程中,發(fā)現(xiàn)時間戳是T的狀態(tài)并不意味著[0,T]的區(qū)間內已經初始化完成,因為這條狀態(tài)很有可能是前移的了.當批量文件中的狀態(tài)數(shù)據時,發(fā)現(xiàn)加載的狀態(tài)的時間戳t并且滿足t>T+ε時,可以確定之前[0,T]區(qū)間所有狀態(tài)數(shù)據已經就緒了.這里的采用貪心的方式進行證明:由于狀態(tài)數(shù)據包含表示狀態(tài)發(fā)生時的時間戳信息,當發(fā)現(xiàn)第一個時間戳大于等于T的狀態(tài)數(shù)據,此時這個狀態(tài)可能向前發(fā)生了偏移,而且最多前推ε個時間間隔,所以此時最多向后再推ε個邏輯時鐘間隔,就可以保證T之前的數(shù)據完全加載到了,判斷的依據就是出現(xiàn)了t>T+ε的狀態(tài).所以需要找到時間戳t>T+ε的記錄,此時可以保證時間T之前的狀態(tài)數(shù)據已經被完全加載.同理也可以推斷如果通過批量加載最后的狀態(tài)時間戳是T,則表示T-ε之前的狀態(tài)已經加載完成.

問題2.如何將批量加載到內存的狀態(tài)數(shù)據進行排序使其嚴格的按照邏輯時鐘順序遞增.首先通過前面的分析,可以假定一定數(shù)量的狀態(tài)數(shù)據已經存在于內存中了,現(xiàn)在需要對這些含有時間戳的狀態(tài)數(shù)據進行排序.前面已經證明了在一段時間[0,T]如何確定是否已經數(shù)據加載完成.由于這里主要是一個局部是無序的而不是完全無序的,所以可以直接使用桶進行排序,每個狀態(tài)都有時間戳信息所以在哪個桶代表的時間間隔里是確定了的,只要通過計算將其放在對應的桶中即可,這里可以假定有一個無限時長的分好時間桶的數(shù)據結構,只需要計算出每個狀態(tài)在這個桶中的位置即可.這種方式的時間復雜度為對于每條狀態(tài)所用的時間復雜度為O(1),所有狀態(tài)恢復的時間復雜度與狀態(tài)數(shù)量N成正比為O(N).綜上,在復原過程主要步驟為:確定時間節(jié)點T、批量加載狀態(tài)數(shù)據并進行桶排序.

3 狀態(tài)存檔與復原實現(xiàn)方法

本小節(jié)主要針對如上所提出的方法的基本思想的實現(xiàn),主要包括狀態(tài)磁盤存檔以及狀態(tài)如何從磁盤中讀出進行復原的過程.

3.1 狀態(tài)存檔實現(xiàn)

針對前面介紹的存檔的過程,首先系統(tǒng)中的邏輯時鐘設置為T,為穩(wěn)定嚴格遞增序列.這里采用交替使用存檔模板來進行存檔數(shù)據,基本實現(xiàn)方式如圖2所示.采用多模板的設計,模板即按照邏輯時鐘將一段時間分成多個區(qū)間并且每個區(qū)間用時間桶表示,通過模板之間的拼接形成完整的時間序列,為了簡化對模板的操作,模板應當根據邏輯時鐘T的粒度,將模板分成的時間桶數(shù)量最少要大于ε.

圖2 多模板存檔圖Fig.2 Multiple template storage diagrams

在多模板的狀態(tài)序列生成過程中的方式序列的生成過程可以分為如下幾個步驟:

Step 1.初始化

在邏輯時鐘的0時刻從按照偏移ε找到S位置,系統(tǒng)的初始化的狀態(tài)寫入模板對應的[0,S]的區(qū)間內,標記第一個模板的首個桶代表的邏輯時鐘是-ε.

Step 2.新狀態(tài)添加

生成新的狀態(tài)添加到當前的模板中,首先查看當前的邏輯時鐘T,將數(shù)據寫入桶中對應的[T-ε,T]的位置里,狀態(tài)需要附帶邏輯時鐘屬性,表明當前狀態(tài)發(fā)生的時間節(jié)點.

Step 3.模板拼接

隨著邏輯時鐘的前進,當前模板表示的邏輯時鐘范圍用盡,則通過兩個模板拼接,拼接之后可以看成是連續(xù)的時間模板,隨著邏輯時鐘的進一步推進,模板拼接分為以下幾個步驟:

步驟1.一個模板隨著邏輯時鐘的推進,當一個模板被首次使用的時候,會標記它第一個桶所對應的邏輯時鐘,之后按照每個桶針對首個桶的偏移計算對應的邏輯時鐘.

步驟2.當狀態(tài)數(shù)據添加的位置超過一個模板的第ε個位置,即達到如圖2所示的E的位置時,此時可以認定前面一個模板的數(shù)據不會再發(fā)生改變,可以將其持久到磁盤中.

步驟3.當一段相當長的時間不添加新的狀態(tài),此時狀態(tài)已經不會在寫入到如圖2的第二個模板中的,并且邏輯時鐘跨越了多個模板,當這樣的狀態(tài)產生時,則從重新生成一個新模板,記錄新模板的首個時間桶的邏輯時鐘為T-ε,并從新的模板ε處開始添加狀態(tài)數(shù)據.然后將前面兩個模板進行數(shù)據的持久化.

磁盤持久化過程描述如下:操作采用單線程線程池方式,接收任務后按照線程加入順序執(zhí)行,這種方式可以保證寫入的順序性.線程池執(zhí)行的線程的基本邏輯是按照模板的先后順序將模板中的數(shù)據從前向后掃描然后寫入到一個固定的磁盤文件,每個桶中的提取可以使用先入先出的方式.系統(tǒng)中由于狀態(tài)數(shù)據跨越時間跨越較大等原因可能需要多個模板,此時可以將模板作為一種資源池化,從而降低模板生成和銷毀的開銷.

3.2 狀態(tài)復原實現(xiàn)

狀態(tài)的復原并不涉及復雜的邏輯計算和交互行為,本小節(jié)介紹單線程驅動模型來說明將數(shù)據恢復的過程的實現(xiàn).前面提到了在恢復的過程可能會涉及到狀態(tài)的排序、邏輯時鐘節(jié)點T的確定等問題.首先針對排序問題進行進行處理是采用單個的模板進行排序操作,基本方式如圖3所示.

圖3 狀態(tài)恢復圖Fig.3 State recovery diagram

這里采用的方式在單線程模式下,僅使用一個存檔模板,這個存檔模板同樣按照邏輯時鐘的粒度將時間分割成一個個連續(xù)的時間桶.模板分割的時間桶的數(shù)量C要嚴格大于ε.執(zhí)行過程如下:首先批量加載磁盤中的數(shù)據,依據狀態(tài)數(shù)據的邏輯時間戳Time,通過Time%C的值作為索引將狀態(tài)添加到對應位置的時間桶中,這里一個時間桶里面可能有多條狀態(tài)數(shù)據,先加入時間桶中的數(shù)據在最前面,后加入的在時間桶的后面,采用先進先出的方式,可以理解為每一個時間桶為一個隊列.在桶的數(shù)量嚴格大于ε的情況下,可以避免桶中數(shù)據加入的過程中,邏輯時鐘時間戳靠后的狀態(tài)在一個桶中時間戳靠后的狀態(tài)數(shù)據之前,從而在遍歷桶中數(shù)據時只要發(fā)現(xiàn)當前邏輯時鐘與桶中狀態(tài)數(shù)據的時間戳的差值大于ε,則認為不是當前邏輯時鐘的狀態(tài)數(shù)據,然后順序遍歷下一個桶中的狀態(tài)數(shù)據.

處理方式可以總結為如下幾個步驟:

步驟1.批量讀取狀態(tài)數(shù)據文件中的狀態(tài),并根據Time%C的方式將其加入到當前的桶中.同時記錄每批最后一個狀態(tài)數(shù)據的時間戳t.

步驟2.當發(fā)現(xiàn)時間戳t>T+ε的狀態(tài)數(shù)據時,停止批量加載的過程,開始按照邏輯時鐘的速率,將加載的狀態(tài)按照當前邏輯時鐘推進T時間節(jié)點.

步驟3.邏輯推進過程按照邏輯幀率從對應的桶中取出數(shù)據,此時需要判斷是否是當前幀的數(shù)據,即當前的邏輯幀和桶中包含狀態(tài)的時間戳進行對比,如果當前狀態(tài)數(shù)據的時間戳與邏輯時鐘的差值小于ε(通常會比ε小很多,比較結果是兩者相近或者差值較大,差值大于等于ε或者接近于0),如果差值大于ε則不在當前邏輯幀中,停止執(zhí)行當前邏輯幀,如果小于ε則執(zhí)行狀態(tài)數(shù)據并且在桶中刪除這條狀態(tài)數(shù)據,重復步驟3.

時間桶的大小是固定的,復原線程按照狀態(tài)數(shù)據的邏輯時鐘的時間戳加載到對應的時間桶中,并且按照與狀態(tài)存檔時相同的邏輯時鐘執(zhí)行,每一個邏輯幀處理一個桶中當前幀的數(shù)據,并且是循環(huán)執(zhí)行,當執(zhí)行時間桶的結尾時,再次從時間桶的開頭進行處理.實際上將上面的單線程模型擴展為雙線程模型時,任務分解為加載線程來負責數(shù)據的排序和批量加載到時間桶,另一個線程通過按照幀率來進行狀態(tài)數(shù)據的處理,當加載線程處理的添加狀態(tài)的邏輯時鐘大于處理線程C個邏輯時鐘時,兩個可以獨立運行并且相互不沖突的,其中C為模板的時間桶的個數(shù).

4 實驗結果與分析

本模擬實驗的硬件平臺Intel Core(TM)i3-4160 3.6GHz四核處理器物理機1臺,內存為8GB,算法的實現(xiàn)與測試均采用Java語言.

其中對所提出的狀態(tài)存檔方法進行性能驗證,主要變量有每邏輯幀的并行度以及ε偏移等,評估指標為CPU使用率、邏輯幀率等,其中參與對比的方法為傳統(tǒng)多線程狀態(tài)追加方式.

4.1 實驗方法

在狀態(tài)存檔過程中,通常狀態(tài)改變時會涉及到對象屬性的一個數(shù)據切面的變化,例如控制運動的線程會同時改變位置、朝向等多個數(shù)據.為了使得模擬實驗的基本環(huán)境相同,這里采用首先生成一定數(shù)量的數(shù)據(Component),這些Component邏輯代表實際對象的狀態(tài)改變的內容.為了使得這里的數(shù)據具有一般性,數(shù)據采用如圖4所示的定義,并將所有Component離散加載在內存中來避免連續(xù)的Component排列因CPU Cache影響性能測試.

首先所有的數(shù)據的參數(shù)i和data的大小都是采用正態(tài)分布隨機生成一定期望范圍內的值,并且在測試之前進行存儲,針對在測試不同參數(shù)和方法的時候,每一種都是使用同一份數(shù)據集;針對不同的參數(shù)和方法分別在相同的數(shù)據集合上測試多次取平均值,并以相同的方式測試不同的數(shù)據集合,最終取平均值作為評估結果.

圖4 狀態(tài)結構圖Fig.4 State structure diagram

數(shù)據的持久化采用如圖5所示的定義,狀態(tài)信息在存儲時需要包含邏輯時鐘時間戳.邏輯時鐘時間戳用來表明狀態(tài)改變時對應的時間節(jié)點.

圖5 狀態(tài)存檔圖Fig.5 State storage diagram

4.2 實驗結果分析

針對以上實驗的設計,實驗的對比結果如表1所示.其中針對本文所介紹的方法的ε的值為100個邏輯時鐘的大小,同時設定邏輯幀率的狀態(tài)數(shù)據總量為定值,將狀態(tài)總量分配到不同線程中執(zhí)行并計算相關指標.

表1 性能對比表
Table 1 Performance comparison

方法指標并行數(shù)量(個)邏輯幀率/fpsCPU使用率/%傳統(tǒng)多線程狀態(tài)追加方式129422486346986本文方法127432516547290

實驗結果分析,當線程并行數(shù)量為1時,即為傳統(tǒng)單線程執(zhí)行方式中,采用追加的方式要優(yōu)于本文所提出的方法,原因主要是單線程下本文所提方法中需要處理的模版操作要更復雜,同時由于不能利用多核優(yōu)勢,CPU使用率以及邏輯幀率較低.傳統(tǒng)方式和本文方式在多線程下都獲了很大程度的加速,但是本文所提出的方法由于減少了在狀態(tài)存檔過程中的沖突概率,性能要優(yōu)于傳統(tǒng)狀態(tài)追加的方式,同時由于降低了沖突率,CPU的利用率獲得一定程度的提高.并且由于針對偏移量的嚴格定義,本文所提出的方式可以嚴格的保證在狀態(tài)恢復過程的時序性,比傳統(tǒng)追加的方式在理論上對于時序性的保證更加可靠.傳統(tǒng)狀態(tài)追加的方法與本文所提的方法在并發(fā)數(shù)增加到2時邏輯幀率提高幅度接近一倍,但邏輯幀率再次增加時邏輯幀率提高幅度比率降低,主要因素有并行場景中存在并發(fā)調度以及加鎖等耗時操作.

針對ε值的選擇,實驗結果如圖6所示,通過前面的理論分析和實驗驗證,實際上當ε大約大于二倍并行數(shù)量時,此時對于ε的繼續(xù)增大并不會對性能提升產生明顯影響.同時發(fā)現(xiàn)當線程數(shù)量過多的時候,性能并不會繼續(xù)提升反而會下降,對于實驗分析和解釋是,本方法中的大部分線程處理邏輯本身屬于計算較密集型的,當線程數(shù)量過多的時候會導致CPU的上下文切換反而增加了時間開銷.實驗結果表明,在多核處理器的操作下,并行數(shù)量應當小于等于物理機器的核心數(shù)量.

圖6 ε與并行度關系Fig.6 Relationship of concurrency and ε

從實現(xiàn)復雜度以及適用性角度分析,本文所提出的方法主要的運用的數(shù)據結構是上文所提出的時間模板,原則上使用數(shù)組結構即可完成設計,與無鎖隊列等實現(xiàn)方式相對,減少了很多高級復雜的原子元語操作的過程,在工程實踐層面非常易于實現(xiàn),并且保證了更加嚴格的時序性.同時,本文所提出的方法針對并行系統(tǒng)的日志記錄等場景下的沖突問題同樣具有借鑒意義.

5 總結與展望

本文提出一種在并行系統(tǒng)下狀態(tài)存檔的沖突消減方法,本方法充分分析了狀態(tài)存檔寫入沖突發(fā)生的原因、時序性的含義等問題.通過對這些問題的深入研究,提出了一種不嚴格時序方法,主要體現(xiàn)在主動引入偏移量ε,通過偏移量ε將狀態(tài)存檔的偏移度保持在一定的范圍內,從而解決并行系統(tǒng)存檔過程中追加方式造成的沖突.同時通過確定性的定義ε范圍,可以合理的利用數(shù)據恢復過程中批量加載的特性,對偏移量ε內的數(shù)據進行有效的排序,通過數(shù)學分析和理論證明以及實驗驗證,證明了本方法的有效性和正確性.

針對本文所提出的方法,接下來的工作主要從以下幾個方面來進行強化,第一,當前的算法與ECS(Entity-Component-System)模型進行整合,根據ECS模型的特點進行優(yōu)化.第二,在狀態(tài)存檔文件上建立有效的索引機制,通過索引機制實現(xiàn)快速跳躍復原等功能.