社會網絡仿真時間同步監管策略范文

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

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

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

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

混合時間管理同步協議

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

基于社區發現的時間管理策略優化設置

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

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

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

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

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

實驗結果與分析

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

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

結束語

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

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