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

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

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)結(jié)果與分析

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

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

結(jié)束語

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

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