社會網(wǎng)絡(luò)仿真時間同步監(jiān)管策略范文

本站小編為你精心準備了社會網(wǎng)絡(luò)仿真時間同步監(jiān)管策略參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

Chandy－Misra－Bryant算法是應(yīng)用最為廣泛的保守時間管理算法，該算法通過比較所有邏輯進程的本地虛擬（LocalVirtualTime，簡稱LVT）來保持全局因果序一致，同時通過發(fā)送空消息（NullMessage）來避免死鎖；Chandy和Misra在文獻中提出的兩段（Two－Phase）保守時間管理算法則通過搜索全局最小時戳事件來避免死鎖。TimeWarp樂觀時間管理算法最早提出了亂序事件處理發(fā)掘系統(tǒng)并行性，同時通過回滾保持事件因果序的思想。Steinman則在TimeWarp時間管理算法的基礎(chǔ)上對節(jié)點間消息發(fā)送方式進行限制，提出了呼吸時間桶算法，減少了級聯(lián)回滾帶來的額外開銷。

保守和樂觀同步策略各有優(yōu)劣，在復雜應(yīng)用背景下，仿真開發(fā)人員往往難以確定一種合適的時間管理策略，因此從上世紀末開始，研究者試圖通過結(jié)合兩種策略的優(yōu)勢來獲取更好的整體性能。目前，這類研究主要分為以下兩個方向：（1）一部分研究者認為保守策略在事件處理的限制上過于嚴格，導致過多的CPU空轉(zhuǎn)；而樂觀策略則過于放松，導致了額外的回滾開銷，因此希望通過對兩者的折衷來減少額外同步開銷。Xu和McGinnis提出optimistic－conservative算法將樂觀事件處理機制引入保守時間管理算法，以發(fā)掘更多的系統(tǒng)并行性；Sokol等人提出的MovingTimeWindow算法和Ball等人提出的Adap－tiveTimeWarp算法則是在樂觀時間管理算法中加入一定限制，減少整體回滾次數(shù)。（2）另一部分研究者則提出混合時間管理協(xié)議，在仿真系統(tǒng)中同時支持保守和樂觀時間管理策略，甚至允許在運行時自由切換，從而最大限度地根據(jù)應(yīng)用特征優(yōu)化系統(tǒng)的性能。李宏亮等提出的一種層次的、混合并行離散事件仿真算法將整個系統(tǒng)分為多個組，組內(nèi)采用保守策略，組間采用樂觀策略。Rajaei等人提出的LocalTimeWarp算法則將仿真應(yīng)用分為兩個層次，底層采用樂觀策略發(fā)掘系統(tǒng)并行性，而在上層采用保守策略限制回滾。這兩個算法適用于實體間交互特征相對穩(wěn)定的仿真應(yīng)用，但由于不支持運行時切換時間管理策略，限制了對動態(tài)性較強的仿真應(yīng)用的支持。

Jha和Bagrodia提出的混合策略框架則支持在邏輯進程的粒度上自由選擇保守和樂觀時間管理策略，同時支持運行時切換時間管理策略，具有較廣的適用范圍。混合時間管理協(xié)議由于能更好地根據(jù)應(yīng)用特征優(yōu)化系統(tǒng)性能，已應(yīng)用到多個領(lǐng)域，正逐漸成為研究的熱點。混合時間管理協(xié)議研究的最主要問題是如何根據(jù)應(yīng)用特征來指定邏輯進程所采用的時間管理策略。據(jù)筆者所知，本文是第一次將混合時間管理協(xié)議運用到社會網(wǎng)絡(luò)仿真領(lǐng)域，并根據(jù)社會網(wǎng)絡(luò)仿真中社區(qū)結(jié)構(gòu)對仿真性能進行優(yōu)化的研究。

混合時間管理同步協(xié)議

本文采用的混合時間管理同步協(xié)議參考了Jha和Bagrodia提出的混合策略框架，其基本思路是將整個時間管理系統(tǒng)分為兩個部分：全局控制部分（GlobalControlMechanism，簡稱GCM）和局部控制部分（LocalControlMechanism，簡稱LCM）。為描述方便，這里為每個邏輯進程設(shè)置兩個基本數(shù)據(jù)結(jié)構(gòu)：（1）事件隊列FEL：存儲所有未處理的事件，隊列按時戳升序排列。Tf表示隊列中的最小時戳，如果隊列為空，則Tf為無窮大。（2）邏輯進程狀態(tài)項集SL：該集合由邏輯進程L的所有狀態(tài)項S［n］組成，每個狀態(tài)項是一個五元組〈t，I（t），S（t），O（t），c〉，其中，t表示仿真時間，I（t）表示輸入事件，S（t）表示t時刻邏輯進程狀態(tài)，O（t）表示處理后的輸出事件集，c為loo－kahead。SL中所有狀態(tài)項按仿真時間t升序排列，設(shè)共有n＋1個項，則S［0］表示最新的已提交狀態(tài)，S［n］表示最新修改的狀態(tài)。全局控制部分主要負責全局時間同步、I／O處理和內(nèi)存管理等工作，其中全局時間同步是時間管理的關(guān)鍵部分，其具體工作是計算每個邏輯進程未來可能處理事件的最小時戳（EarliestInputTime，簡稱EIT）。該值在保守時間管理機制中做為下界時戳（LowerBoundTimeStamp，簡稱LBTS）使用，而在樂觀時間管理機制中做為全局虛擬時鐘（GlobalVirtualTime，簡稱GTV）使用。計算EIT時，可以選用已有LTBS柵欄算法和GVT算法。局部控制部分主要負責控制邏輯進程采用不同的策略處理相關(guān)事件。在邏輯進程采用樂觀策略時，允許邏輯進程任意處理到達事件，并通過回滾機制保證因果序一致。如果Tf＞S［n］．t，則表示事件處理時序正確，令I(lǐng)表示最小時戳事件，〈S（t′），O（t′），c〉＝process（S［n］．S（t），I），將O（t′）事件集發(fā)送出去，將S［n＋1］：〈Tf，I，S（t′），O（t′），c〉加入到狀態(tài)記錄集；如果Tf＜S［n］．t，則表示事件處理出現(xiàn)亂序需要回滾，找到最大的i，使得Tf＞S［i］．t，回滾到S［i］，將相關(guān)事件重新加入到事件隊列，重復處理；同時，依據(jù)EIT來回收用于存儲狀態(tài)的資源。在邏輯進程采用保守策略時，只允許邏輯進程處理時間戳小于EIT的事件，因此不用保存過多的狀態(tài)。令〈S（t′），O（t′），c〉＝process（S［n］．S（t），I），將O（t′）事件集發(fā)送出去。將S［n＋1］：〈t′，I，S（t′），O（t′），c〉加入到狀態(tài)集，并刪除S［n］。全局控制部分和局部控制部分功能相對獨立，邏輯進程可以自由地選用支持不同時間策略的LCM。當邏輯進程需要運行時動態(tài)切換時，采用保守策略的邏輯進程可直接進行樂觀處理；而由樂觀策略向保守策略轉(zhuǎn)化時，有兩種轉(zhuǎn)化方法：（1）直接回滾到S［0］，將所有時戳t＞S［0］．t的事件重新加入到事件隊列中，狀態(tài)集只留下S［0］，處理模式由樂觀轉(zhuǎn)化為保守。（2）選擇性回滾：等待EIT到達S［n］．t，在狀態(tài)集中只留下S［n］，處理模式由樂觀轉(zhuǎn)化為保守；如果事件隊列中出現(xiàn)Tf＜S［n］．t，則先使用樂觀LCM后半段回滾到Tf，在完成上述操作后轉(zhuǎn)換為保守策略。

基于社區(qū)發(fā)現(xiàn)的時間管理策略優(yōu)化設(shè)置

社區(qū)結(jié)構(gòu)是社會網(wǎng)絡(luò)的一個顯著的拓撲特征，絕大部分的社會網(wǎng)絡(luò)都是由一些內(nèi)部結(jié)構(gòu)緊密的社區(qū)組成，在一些文獻中也稱之為聚集性（Clustering）或模塊性（Modularity）。社區(qū)可以非形式化地定義為社會網(wǎng)絡(luò)中一系列個體的集合，集合內(nèi)部個體連接緊密，集合間個體連接稀疏。目前，業(yè)界還未形成統(tǒng)一的社區(qū)數(shù)學描述，其中應(yīng)用最為廣泛的是plantedl－partition模型，該模型為社會網(wǎng)絡(luò)中的每個個體定義pin和pout兩個連接概率，當pin＞pout時則判定該個體屬于某一社區(qū)。

由于社會網(wǎng)絡(luò)仿真中存在大量社會各異個體，即使是同一社區(qū)中的個體的行為模型也可能存在較大差異，因而難以提取合適的Lookahead以保證保守策略的高效運行，需要采用樂觀策略來提高運行效率；而社區(qū)結(jié)構(gòu)卻對樂觀策略的運行效率提出了挑戰(zhàn)，社區(qū)結(jié)構(gòu)內(nèi)個體連接緊密，個體間交互頻繁，單個個體回滾容易引起社區(qū)內(nèi)關(guān)聯(lián)個體回滾；如果由于關(guān)聯(lián)個體的回滾引起其他社區(qū)內(nèi)個體回滾，則可能導致回滾影響在社區(qū)間不斷傳播，形成系統(tǒng)級的回滾風暴，從而極大地影響整體性能。

因此，面向社會網(wǎng)絡(luò)仿真的混合時間管理算法需要解決以下兩方面的問題：一方面需要盡可能多選取邏輯進程采用樂觀策略，以減少個體行為模型差異所帶來的空轉(zhuǎn)等待；另一方面通過指定關(guān)鍵通信節(jié)點采用保守策略以限制級聯(lián)回滾的可能性。基于社區(qū)發(fā)現(xiàn)的混合時間管理策略優(yōu)化設(shè)置思想如圖1和圖2所示。整個算法主要包含兩部分：（1）通過社區(qū)發(fā)現(xiàn)算法挖掘出社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。圖1b則顯示了圖1a所示網(wǎng)絡(luò)示例通過社區(qū)發(fā)現(xiàn)算法所得到的社區(qū)劃分。（2）對社區(qū)內(nèi)的節(jié)點進行分析，找到社區(qū)間通信的關(guān)鍵節(jié)點，將這些節(jié)點設(shè)置為保守策略以限制回滾在社區(qū)間的傳播，同時將社區(qū)內(nèi)其他節(jié)點設(shè)置為樂觀策略。圖2顯示了對圖1b各社區(qū)的設(shè)置。本文采用由Rosvall和Bergstrom提出的In－fomap社區(qū)發(fā)現(xiàn)算法來挖掘社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

該算法將社區(qū)發(fā)現(xiàn)問題轉(zhuǎn)化為一個網(wǎng)絡(luò)結(jié)構(gòu)信息壓縮優(yōu)化問題，即如何最有效地對網(wǎng)絡(luò)結(jié)構(gòu)進行編碼，一方面使得壓縮比率盡可能高，另一方面通過該壓縮編碼還原的網(wǎng)絡(luò)結(jié)構(gòu)盡可能貼近原有網(wǎng)絡(luò)結(jié)構(gòu)。算法中采用隨機游走（RandomWalk）動態(tài)過程來獲取壓縮編碼，并通過隨機游走動態(tài)過程的最小描述長度（MinimumDescriptionLength）作為評估函數(shù)來優(yōu)化編碼，而最優(yōu)的編碼可對應(yīng)得到最終社區(qū)劃分。該算法具有社區(qū)劃分結(jié)果優(yōu)、運行效率高的特點，文獻通過對比測試，認為該算法是目前整體性能最優(yōu)的社區(qū)發(fā)現(xiàn)算法。

完成社區(qū)劃分后，逐個分析各個社區(qū)內(nèi)的節(jié)點，如果存在與其他社區(qū)節(jié)點的連接，則將該節(jié)點設(shè)置為保守策略，否則將該節(jié)點設(shè)置為樂觀策略。設(shè)置后系統(tǒng)仿真時間同步可等效分為兩個層次：社區(qū)內(nèi)節(jié)點時間同步采用基于TimeWarp同步協(xié)議的樂觀時間管理算法，社區(qū)間時間同步則基于保守時間管理策略。設(shè)置為保守策略的社區(qū)間連接節(jié)點作為各個社區(qū)的網(wǎng)關(guān)，其主要功能包括：（1）參與全局EIT計算；（2）根據(jù)全局EIT處理該節(jié)點相關(guān)事件，并直接調(diào)度社區(qū)內(nèi)節(jié)點事件；（3）緩存社區(qū)間調(diào)度事件，將安全的事件調(diào)度消息發(fā)往其他社區(qū)目標節(jié)點。設(shè)置為樂觀策略的社區(qū)內(nèi)部節(jié)點處理相關(guān)事件則不受EIT的限制，以減少處理器空轉(zhuǎn)等待；而由于社區(qū)間連接節(jié)點采用保守策略，其樂觀處理的不安全事件不會影響到其他社區(qū)，因而，當某一社區(qū)內(nèi)節(jié)點回滾時，其影響僅限于本社區(qū)內(nèi)，避免出現(xiàn)系統(tǒng)級聯(lián)回滾。根據(jù)上述思想，基于社區(qū)發(fā)現(xiàn)的混合時間管理策略優(yōu)化設(shè)置啟發(fā)式算法描述如下：設(shè)｜E｜表示網(wǎng)絡(luò)的邊數(shù)，Infomap社區(qū)發(fā)現(xiàn)算法的算法時間復雜度為O（｜E｜），對社區(qū)內(nèi)節(jié)點分析算法時間復雜度為O（2｜E｜），則上述啟發(fā)式算法時間復雜度為O（3｜E｜）。

實驗結(jié)果與分析

PHOLD測試模型［23］是目前并行仿真領(lǐng)域廣泛使用的標準測試程序。本文實驗采用基于PHOLD測試模型的社會網(wǎng)絡(luò)交互測試用例，其基本描述如下：實驗仿真系統(tǒng)由N個社會網(wǎng)絡(luò)個體構(gòu)成，每個網(wǎng)絡(luò)個體映射到一個邏輯進程上，負責存儲個體狀態(tài)和處理相關(guān)事件，邏輯進程通過事件調(diào)度與網(wǎng)絡(luò)中相鄰的邏輯進程進行交互；系統(tǒng)中設(shè)置M（M＜N）個初始事件，隨機調(diào)度到M個邏輯進程上；當一個邏輯進程接受一個事件后，則隨機選擇網(wǎng)絡(luò)中相鄰的一個邏輯進程，調(diào)度該邏輯進程上未來的一個事件；事件調(diào)度時間間隔由調(diào)度者lookahead決定。實驗采用的網(wǎng)絡(luò)結(jié)構(gòu)基于Barabási和Albert提出的BA模型生成。本次實驗參數(shù)設(shè)置如表1所示。實驗仿真軟件平臺為喬治亞理工學院（Geor－giaInstituteofTechnology）開發(fā)的開源并行離散事件仿真平臺μsik；硬件環(huán)境為4計算節(jié)點Linux集群系統(tǒng)，每個計算節(jié)點包含兩個主頻2．53GHzQuadCoreXeon處理器，主存8GB操作系統(tǒng)為KylinServer3．1，GCC版本為4．1．2。

實驗結(jié)果如圖3所示。由測試結(jié)果可以看出，在計算資源固定的條件下，在整體負載較輕時，采用樂觀策略能減少空轉(zhuǎn)等待，平均性能要優(yōu)于保守算法，但隨著負載的增加，回滾帶來的額外開銷越來越大，樂觀機制性能下降較快，在重負載下保守策略平均性能較優(yōu)。混合策略時間管理算法則整體性能穩(wěn)定，對負載不敏感，具有良好的可擴展性；在負載適中時，平均性能優(yōu)于單純的樂觀和保守策略。

結(jié)束語

利用并行仿真技術(shù)以滿足社會網(wǎng)絡(luò)仿真對計算資源的需求是當前研究的趨勢，而仿真時間同步機制是決定并行仿真性能的重要因素。社會網(wǎng)絡(luò)仿真中個體間行為模式差異較大，難以提取合適的Lookahead以保證保守策略的高效運行；同時，社會網(wǎng)絡(luò)仿真中個體交互情況復雜，采用樂觀策略時，容易引起系統(tǒng)內(nèi)大量級聯(lián)回滾，因此傳統(tǒng)粗粒度的保守或樂觀時間管理算法都無法適應(yīng)社會網(wǎng)絡(luò)仿真的需求。本文提出一種基于社區(qū)發(fā)現(xiàn)的混合時間管理機制，在仿真系統(tǒng)中同時支持保守和樂觀時間管理策略，允許在邏輯進程的粒度上自由選擇保守和樂觀時間管理策略，并根據(jù)社會網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)特性優(yōu)化設(shè)置邏輯進程所采用的時間管理策略，從而最大限度地發(fā)掘系統(tǒng)的性能，同時減少級聯(lián)回滾的風險。實驗結(jié)果證明了該算法的有效性。

作者：張穎星姚益平單位：國防科學技術(shù)大學計算機學院