畢業(yè)設(shè)計(jì)（論文）--文獻(xiàn)翻譯原文題目ResearchChallengesinParallelandDistributedSimulation譯文題目并行與分布式仿真中的研究挑戰(zhàn)專(zhuān)業(yè)姓名學(xué)號(hào)指導(dǎo)教師并行與分布式仿真中的研究挑戰(zhàn)RICHARDM.FUJIMOTO,GeorgiaInstituteofTechnology摘要并行與分布式仿真領(lǐng)域從20世紀(jì)70年代和80年代就發(fā)展壯大起來(lái)，目前仍然是一個(gè)活躍的研究領(lǐng)域。介紹了該領(lǐng)域研究的簡(jiǎn)要概述。未來(lái)研究課題的領(lǐng)域，包括大規(guī)模系統(tǒng)和復(fù)雜網(wǎng)絡(luò)的問(wèn)題驅(qū)動(dòng)仿真、圖形處理單元硬件和云計(jì)算環(huán)境的開(kāi)發(fā)、系統(tǒng)管理和優(yōu)化的預(yù)測(cè)性在線模擬、移動(dòng)平臺(tái)和數(shù)據(jù)中心的電力及能源消耗、以及異構(gòu)仿真的組成。引言與歷史觀點(diǎn)并行與分布式仿真領(lǐng)域出現(xiàn)于20世紀(jì)70年代和80年代兩個(gè)不同的研究團(tuán)體。一方面，并??行離散事件仿真（PDES）團(tuán)體關(guān)注于通過(guò)開(kāi)發(fā)高性能計(jì)算平臺(tái)來(lái)加速離散事件仿真的執(zhí)行。在大致相同的時(shí)間框架內(nèi)，分布式仿真團(tuán)體形成，成為國(guó)防社會(huì)的重點(diǎn)研究和開(kāi)發(fā)工作，專(zhuān)注于通過(guò)本地和廣域網(wǎng)互連的計(jì)算機(jī)執(zhí)行互連仿真。盡管離散事件仿真與分布式仿真的工作有很大差異，但仍存在很多共同的問(wèn)題。在這里，我們將并行與分布式仿真非正式地定義為一個(gè)領(lǐng)域：專(zhuān)注于通過(guò)網(wǎng)絡(luò)在平臺(tái)范圍從緊密耦合并行計(jì)算機(jī)到松散耦合計(jì)算機(jī)的多個(gè)處理器上執(zhí)行仿真程序。需要特別強(qiáng)調(diào)的是離散事件仿真常用于系統(tǒng)分析。1.1并行離散事件仿真離散事件仿真涉及在高性能計(jì)算系統(tǒng)中，跨多個(gè)處理器為某個(gè)離散事件仿真程序分配單個(gè)執(zhí)行。這樣平臺(tái)包括共享內(nèi)存多處理器和基于消息的群集計(jì)算機(jī)。離散事件仿真的中心目標(biāo)通常是加速仿真的執(zhí)行。隨著時(shí)間的推移，離散事件仿真捕獲實(shí)際或預(yù)想的系統(tǒng)的行為。不像其他仿真以時(shí)間流逝的模式運(yùn)行和演變，系統(tǒng)的狀態(tài)一步到下一個(gè)。在離散事件仿真中，系統(tǒng)狀態(tài)的變化發(fā)生在不同的，通常離散的模擬時(shí)間點(diǎn)內(nèi)。一個(gè)連續(xù)的離散事件仿真程序包括兩個(gè)基本概念：捕獲正被建模的系統(tǒng)狀態(tài)的狀態(tài)變量以及事件計(jì)算或簡(jiǎn)單地將狀態(tài)變量從一個(gè)狀態(tài)轉(zhuǎn)換到下一個(gè)狀態(tài)的事件。在離散事件仿真中，模擬狀態(tài)的改變的發(fā)生僅通過(guò)事件計(jì)算。每個(gè)事件都包含一個(gè)代表狀態(tài)轉(zhuǎn)變發(fā)生的仿真時(shí)間點(diǎn)的時(shí)間戳。例如，機(jī)場(chǎng)的模擬可能包括表示跑道狀態(tài)的狀態(tài)變量（例如空閑或忙碌），以及其他方面，如等待起飛或著陸的飛機(jī)數(shù)量。活動(dòng)可能對(duì)應(yīng)于飛機(jī)到達(dá)或離港。并行離散事件仿真程序可以被看作是通過(guò)交換時(shí)間戳的消息進(jìn)行交互的許多順序離散事件仿真的集合。每個(gè)消息表示一個(gè)模擬器為另一個(gè)模擬器調(diào)度（發(fā)送）的事件。每個(gè)順序模擬器被稱(chēng)為邏輯進(jìn)程或LP。例如，可以通過(guò)創(chuàng)建每個(gè)機(jī)場(chǎng)的順序仿真，并允許每個(gè)模擬器調(diào)度事件（即，發(fā)送消息）到其他模擬器，來(lái)構(gòu)建全球空中交通系統(tǒng)的仿真。在機(jī)場(chǎng)模擬器之間傳輸?shù)男畔ⅲ赡艽盹w機(jī)從一個(gè)機(jī)場(chǎng)到達(dá)另一個(gè)機(jī)場(chǎng)。PDES中的大部分工作都集中在PDES程序的同步。同步問(wèn)題專(zhuān)注于確保一個(gè)PDES程序的執(zhí)行，能夠精確地或在某些情況下近似地產(chǎn)生與相同程序順序執(zhí)行一致的結(jié)果，其中所有事件都在另一個(gè)時(shí)間戳的命令之后被處理。可以看出，這可以通過(guò)確保來(lái)實(shí)現(xiàn)每個(gè)LP以時(shí)間戳順序處理事件，包括從其他處理器接收的消息（或事件;在這里，我們使用同義的術(shù)語(yǔ)消息和事件）。同步算法大致分為兩類(lèi)：保守型和樂(lè)觀型。保守算法，如Chandy/Misra/Bryant算法[Bryant1977;Chandy和Misra1978]使用阻止LP執(zhí)行的機(jī)制，直到它可以保證不再接收到具有更小時(shí)間戳的事件。這需要規(guī)定一個(gè)前置值。如果LP正處于時(shí)間T，其前置值為L(zhǎng)，則LP稍后發(fā)送的任何消息必須具有的時(shí)間戳至少為T(mén)+L。可以將前置值與鏈接相關(guān)聯(lián)，而不是邏輯進(jìn)程。所有保守算法都依賴于一個(gè)足夠大的前置值來(lái)實(shí)現(xiàn)事件的并發(fā)處理。最后，在類(lèi)保守算法中，一些算法使用全局屏障同步來(lái)管理執(zhí)行。顯著例子是有界滯后[Lubachevsky1989]和YAWNS[Nicol，Michealetal.1989]算法。雖然保守算法采取預(yù)防措施來(lái)確保LP始終在時(shí)間戳順序中處理事件，樂(lè)觀算法允許事件被無(wú)序處理，但是利用回滾機(jī)制從這樣的錯(cuò)誤中恢復(fù)。時(shí)間扭曲[Jefferson1985]是第一個(gè)樂(lè)觀同步算法，目前仍然是最廣泛使用的樂(lè)觀算法。在保守和樂(lè)觀算法里有著廣泛的文學(xué)。在Fujimoto中更詳細(xì)地介紹了大部分的工作[2000，2015]。1.2分布式仿真分布式仿真涉及跨越計(jì)算平臺(tái)的仿真執(zhí)行，其平臺(tái)是比并行電腦更廣泛的平臺(tái)。并行仿真中執(zhí)行仿真的處理器駐留在機(jī)房?jī)?nèi)的機(jī)柜中，與并行仿真相反，分布式仿真可以執(zhí)行一組通過(guò)局域網(wǎng)互連的機(jī)器，全球分布式計(jì)算機(jī)通過(guò)互聯(lián)網(wǎng)或嵌入物理環(huán)境的預(yù)測(cè)仿真進(jìn)行通信，例如監(jiān)測(cè)城市交通的傳感器網(wǎng)絡(luò)。運(yùn)用分布式仿真系統(tǒng)的中心目的是允許地理分布資源的開(kāi)發(fā)，如設(shè)備或分布式仿真練習(xí)中的人，或通過(guò)實(shí)時(shí)數(shù)據(jù)近似地執(zhí)行仿真以預(yù)測(cè)運(yùn)營(yíng)系統(tǒng)的未來(lái)狀態(tài)。一個(gè)中心問(wèn)題，往往也是利用分布式仿真的主要?jiǎng)訖C(jī)為，渴望集成在不同計(jì)算機(jī)上運(yùn)行的模擬器設(shè)備進(jìn)入單一模擬環(huán)境。大部分早期分布式仿真工作專(zhuān)注于訓(xùn)練系統(tǒng)坦克模擬器，飛行模擬器，電子計(jì)算機(jī)力量和其他各種可以創(chuàng)建人員可嵌入其中的分布式虛擬環(huán)境以訓(xùn)練假設(shè)場(chǎng)景和情況的模型。同步，也稱(chēng)為分布式仿真文學(xué)中的時(shí)間管理，也是分布式仿真中的一個(gè)問(wèn)題，它不是唯一的問(wèn)題，通常不是最重要的一個(gè)。大部分早期的分布式仿真的研究關(guān)注于模擬器的分布信息以有效和及時(shí)的方式參與到分布式仿真。大部分的工作涉及通信協(xié)議，如多路廣播機(jī)制或方法以減少大量需要通過(guò)技術(shù)使用來(lái)傳達(dá)的數(shù)據(jù)，如推算[Miller和Thorpe1995]或數(shù)據(jù)分發(fā)管理[MorseandZyda2001]技術(shù)。因?yàn)榉植际椒抡娴闹攸c(diǎn)在于已經(jīng)實(shí)現(xiàn)了個(gè)別發(fā)達(dá)模擬器之間的互操作性，大量的努力集中在開(kāi)發(fā)互連仿真標(biāo)準(zhǔn)。這導(dǎo)致了分布交互式仿真（DIS）（IEEE）標(biāo)準(zhǔn)1278.1-19951995，IEEE標(biāo)準(zhǔn)1278.2-19951995）和高級(jí)架構(gòu)（HLA）（IEEEStd1516-20102010，IEEEStd1516.1-20102010，IEEEStd1516.2-20102010）標(biāo)準(zhǔn)。在Fujimoto[2000]和Tolk[2012]進(jìn)行討論的分布式仿真研究社區(qū)解決了許多技術(shù)問(wèn)題。本文的其余部分組織如下。下一節(jié)簡(jiǎn)要介紹一下目前和未來(lái)六個(gè)方面的研究并行與分布式仿真需要的額外工作，并根據(jù)目前的技術(shù)趨勢(shì)和應(yīng)用爭(zhēng)辯為什么每個(gè)這些領(lǐng)域都是適時(shí)的。第3節(jié)是本文的主體。通過(guò)提出每一個(gè)在這一領(lǐng)域的總體挑戰(zhàn)、討論先前的工作、突出重點(diǎn)研究問(wèn)題和尚未得到圓滿解決的問(wèn)題，它更加詳細(xì)地討論了這六個(gè)研究領(lǐng)域。雖然這些挑戰(zhàn)中的一些僅與PDES或分布式仿真相關(guān)，但跨越兩個(gè)領(lǐng)域。最后，第5節(jié)提供了關(guān)于并行與分布式仿真領(lǐng)域未來(lái)的總結(jié)性結(jié)論。主要研究挑戰(zhàn)并行與分布式仿真領(lǐng)域在過(guò)去四十年不斷發(fā)展和演變。今天，這一領(lǐng)域面臨著許多新的挑戰(zhàn)，一方面這些挑戰(zhàn)源于新應(yīng)用的需求，另一方面由于其所運(yùn)作的基礎(chǔ)硬件和軟件系統(tǒng)的重大變化。在列舉的六個(gè)領(lǐng)域定義了技術(shù)挑戰(zhàn)，如果有重大進(jìn)展可能產(chǎn)生跨越多個(gè)應(yīng)用領(lǐng)域的影響，所以亟待解決：大型復(fù)雜網(wǎng)絡(luò)的應(yīng)用驅(qū)動(dòng)，可擴(kuò)展模擬。迄今為止關(guān)于大規(guī)模、大量并行仿真的研究側(cè)重于證明PDES技術(shù)對(duì)合成工作負(fù)載的能力。我們倡導(dǎo)以應(yīng)用驅(qū)動(dòng)的方式展示大規(guī)模的能力模擬以獲得對(duì)現(xiàn)實(shí)世界網(wǎng)絡(luò)規(guī)模的行為的新見(jiàn)解。例如，一個(gè)挑戰(zhàn)是創(chuàng)建具有偏斜節(jié)點(diǎn)度分布的不規(guī)則拓?fù)渚W(wǎng)絡(luò)的大規(guī)模仿真。利用圖形處理單元（GPU）開(kāi)發(fā)異構(gòu)機(jī)器體系結(jié)構(gòu)。GPU在從大型超級(jí)計(jì)算機(jī)到集群和臺(tái)式機(jī)的平臺(tái)中變得越來(lái)越普遍。越來(lái)越多的研究一直在探索開(kāi)發(fā)并行離散事件仿真應(yīng)用的相關(guān)設(shè)備。如果成功，在這一領(lǐng)域的研究可能使PDES為某些類(lèi)別的問(wèn)題去實(shí)現(xiàn)新的性能水平。通過(guò)更簡(jiǎn)單的模型開(kāi)發(fā)和云計(jì)算平臺(tái)，使并行與分布式仿真可以廣泛可用。開(kāi)發(fā)高效的并行仿真代碼的難度仍然是一個(gè)挑戰(zhàn)，并且簡(jiǎn)化軟件開(kāi)發(fā)和維護(hù)的技術(shù)也是迫切需要的。云計(jì)算能夠?yàn)閹缀跛杏脩籼峁┎⑿信c分布式仿真技術(shù)，而不會(huì)產(chǎn)生購(gòu)買(mǎi)和運(yùn)行高性能計(jì)算平臺(tái)的費(fèi)用，這是一個(gè)過(guò)去長(zhǎng)期存在的問(wèn)題，阻止了并行與分布式仿真技術(shù)的廣泛采用。在線決策使用實(shí)時(shí)分布式仿真。無(wú)處不在的計(jì)算、無(wú)線傳感器網(wǎng)絡(luò)和大量的數(shù)據(jù)的出現(xiàn)，使仿真能夠以諸如智能城市等新興領(lǐng)域的前所未有的規(guī)模嵌入到操作系統(tǒng)中。在操作系統(tǒng)的在線管理和優(yōu)化中，分布式仿真能發(fā)揮重要作用。節(jié)能和省電的并行與分布式仿真。電力和能源消費(fèi)已經(jīng)成為計(jì)算的主要問(wèn)題。它影響移動(dòng)計(jì)算平臺(tái)的電池壽命，是數(shù)據(jù)中心的主要費(fèi)用。然而，到目前為止，并行與分布式仿真領(lǐng)域的電力和能源消耗很少得到重視。關(guān)于并行與分布式仿真的電力和能源特性，或如何有效地管理程序執(zhí)行的這些方面，知之甚少。分布式仿真的快速組合。快速構(gòu)建單獨(dú)開(kāi)發(fā)的仿真，仍然是一個(gè)艱巨的挑戰(zhàn)。雖然已經(jīng)取得了許多進(jìn)展，例如，在創(chuàng)建支持軟件框架和標(biāo)準(zhǔn)的技術(shù)方面。然而，針對(duì)不同目的編寫(xiě)單獨(dú)開(kāi)發(fā)的仿真仍然是一個(gè)耗時(shí)的任務(wù)，或者甚至不可能。這一領(lǐng)域的重要性在不斷增加，認(rèn)識(shí)到在許多情況下，必須使用非還原性方法來(lái)整體研究系統(tǒng)，而不是其孤立的構(gòu)成部分。根據(jù)最近的技術(shù)趨勢(shì)和應(yīng)用需要，我們認(rèn)為這些領(lǐng)域的每一個(gè)研究都是適時(shí)的。關(guān)鍵因素激勵(lì)著前三個(gè)領(lǐng)域關(guān)注底層計(jì)算平臺(tái)的重要技術(shù)變化。這種現(xiàn)象對(duì)并行與分布式仿真來(lái)說(shuō)并不陌生。事實(shí)上，并行離散事件仿真隨著商業(yè)多處理器系統(tǒng)的可用性而出現(xiàn)，分布式仿真源于計(jì)算機(jī)網(wǎng)絡(luò)的進(jìn)步以及其他技術(shù)。大容量并行超級(jí)計(jì)算機(jī)包含超過(guò)百萬(wàn)個(gè)核心，GPUs，并且云計(jì)算在過(guò)去十年中已經(jīng)顯現(xiàn)出重要性，激發(fā)了并行與分布式仿真的研究，以開(kāi)發(fā)這些平臺(tái)。最近的趨勢(shì)，如物聯(lián)網(wǎng)和“大數(shù)據(jù)”對(duì)于并行與分布式仿真的未來(lái)有很大的影響。隨著移動(dòng)計(jì)算的出現(xiàn)和傳感器網(wǎng)絡(luò)等技術(shù)的發(fā)展，在線決策越來(lái)越重要。并行與分布式仿真是數(shù)據(jù)分析開(kāi)發(fā)的補(bǔ)充。雖然純粹來(lái)自數(shù)據(jù)分析的模型在許多情況下提升了提供預(yù)測(cè)能力的潛力，但這些模型不包括對(duì)被調(diào)查系統(tǒng)的行為描述，這些描述對(duì)于假設(shè)實(shí)驗(yàn)或分析足夠數(shù)據(jù)或正確數(shù)據(jù)不能用的情況分析（例如，由于隱私或其他問(wèn)題）而言是必要的。同時(shí)，電力和能源消耗已成為計(jì)算領(lǐng)域（包括移動(dòng)計(jì)算平臺(tái)和數(shù)據(jù)中心）的重要考慮因素。最后，雖然仿真的組成仍然是分布式仿真中多年存在的一個(gè)長(zhǎng)期問(wèn)題，新興應(yīng)用領(lǐng)域比如智能城市，它要求系統(tǒng)的建模系統(tǒng)突出該技術(shù)日益增長(zhǎng)的重要性。在開(kāi)發(fā)方法和標(biāo)準(zhǔn)方面取得了許多進(jìn)展，以使仿真能夠進(jìn)行互操作。然而，我們遠(yuǎn)遠(yuǎn)沒(méi)有實(shí)現(xiàn)方法，使得其單獨(dú)開(kāi)發(fā)的模型可以輕松地以“即插即用”的方式組合，并確保所得到的模型是有效的。六個(gè)研究挑戰(zhàn)在下文中，我們更詳細(xì)地回顧了每個(gè)這些領(lǐng)域的正在進(jìn)行的工作以及尚未解決的關(guān)鍵研究挑戰(zhàn)。我們開(kāi)始討論每一個(gè)擁有挑戰(zhàn)的領(lǐng)域，試圖在該領(lǐng)域進(jìn)行研究。3.1復(fù)雜網(wǎng)絡(luò)的大規(guī)模并行離散事件仿真挑戰(zhàn)1.創(chuàng)建可擴(kuò)展性。現(xiàn)實(shí)的大規(guī)模不規(guī)則系統(tǒng)的仿真，例如復(fù)雜網(wǎng)絡(luò)，并展示其為現(xiàn)實(shí)世界系統(tǒng)創(chuàng)造新見(jiàn)解的能力。第一個(gè)挑戰(zhàn)的核心是創(chuàng)造可信的現(xiàn)實(shí)網(wǎng)絡(luò)的仿真模型，其規(guī)模為了深入了解他們的行為。多年來(lái)，已經(jīng)取得了許多成功的成果，展示了PDES技術(shù)加速離散事件仿真執(zhí)行的能力。例如，F(xiàn)ujimoto等人[2003]檢查了超級(jí)計(jì)算機(jī)上計(jì)算機(jī)通信網(wǎng)絡(luò)的分組級(jí)仿真。并行模擬器在2003年使用1,536個(gè)處理器在超級(jí)計(jì)算機(jī)上執(zhí)行的保守同步算法，每秒可以產(chǎn)生高達(dá)超過(guò)2億事件（eps）的性能。相比之下，在順序機(jī)器上執(zhí)行的可比模擬器產(chǎn)生的性能小于20萬(wàn)次。2007年，通過(guò)合成基準(zhǔn)稱(chēng)為PHOLD的研究使用16,384處理器機(jī)器[Perumalla2007]上的樂(lè)觀同步算法獲得了超過(guò)5.29億eps的性能，2009年，通過(guò)65,536個(gè)處理器實(shí)現(xiàn)了122.6億eps的性能[Bauer等。2009]，都使用IBMBlueGene機(jī)器。2013年，Barnes等[2013]能夠使用近200萬(wàn)個(gè)藍(lán)色基因/Q機(jī)核心達(dá)到5040億個(gè)eps。對(duì)具體應(yīng)用的大規(guī)模模擬的研究包括流行病傳播[Bissetetal。2009年;Perumalla和Seal2010;Perumalla等人2014]和電磁信號(hào)傳播[Baueretal。2009年]。為此，我們使用事件/第二個(gè)度量，因?yàn)橐院笠玫难芯考性诿總€(gè)事件計(jì)算量適量的應(yīng)用程序，該度量對(duì)于沒(méi)有此屬性的應(yīng)用程序不太有用。在Fujimoto[2003]、Perumalla[2007]、Bauer[2009]、Barnes[2013]等人報(bào)道的研究，分別產(chǎn)生了138K[2003]，32K[2007]，187K[2009]和256K[2013]eps/core的單核事件發(fā)生率。這表示跨越10年的時(shí)間里單核性能方面只有雙重的改善。這些數(shù)據(jù)表明，今天的性能改進(jìn)幾乎完全由并行性的增加驅(qū)動(dòng)。這并不奇怪。由于2005年以來(lái)，由于散熱的物理限制，處理器時(shí)鐘頻率僅有小幅增長(zhǎng)，導(dǎo)致自2005年以來(lái)，超級(jí)計(jì)算機(jī)體系結(jié)構(gòu)中的核心數(shù)量爆炸式增長(zhǎng)。從20世紀(jì)90年代到2005年間的大部分時(shí)間里，最強(qiáng)大的超級(jí)計(jì)算機(jī)只包含數(shù)千的核心。今天最強(qiáng)大的機(jī)器包含數(shù)百萬(wàn)。剛才引用的研究在很大程度上集中于自下而上的技術(shù)手段。由此我們認(rèn)為這些研究集中在理解PDES技術(shù)本身的可擴(kuò)展性和局限性，這在很大程度上獨(dú)立于應(yīng)用。但是重要的是，需要一種關(guān)于具體的應(yīng)用問(wèn)題的選擇性的自上而下的問(wèn)題驅(qū)動(dòng)的方法。這些研究將集中在回答特定問(wèn)題領(lǐng)域的重要問(wèn)題和這些應(yīng)用的突出特性，稱(chēng)之為新的并行化方法。最近在計(jì)算機(jī)網(wǎng)絡(luò)仿真方面的工作包括Kunzetal。[2016]和金和尼科爾[2015]。為了說(shuō)明這一點(diǎn)，考慮網(wǎng)絡(luò)拓?fù)涞膯?wèn)題。前面所述的研究集中在高度規(guī)則的合成網(wǎng)絡(luò)拓?fù)洌鐖A形，環(huán)形或完全連接的網(wǎng)絡(luò)。PDES拓?fù)涫敲總€(gè)節(jié)點(diǎn)表示LP的圖形，并且每個(gè)連接兩個(gè)LP的鏈路表明，這些LP可以通過(guò)在它們之間發(fā)送消息來(lái)進(jìn)行通信。這里，我們假設(shè)無(wú)向弧，對(duì)發(fā)送和接收LP不進(jìn)行區(qū)分。前面描述的基準(zhǔn)測(cè)試研究都采用了一種常規(guī)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，例如環(huán)形線圈，其中工作負(fù)載可以在網(wǎng)絡(luò)上均勻分布，幾乎沒(méi)有困難。實(shí)際上，很少有現(xiàn)實(shí)世界的應(yīng)用展現(xiàn)出這樣的理想特性。過(guò)去十年的大量研究側(cè)重于在現(xiàn)實(shí)應(yīng)用中出現(xiàn)的網(wǎng)絡(luò)拓?fù)洹Ｍǔ＃袑?shí)際價(jià)值的網(wǎng)絡(luò)是非常不規(guī)則的。已經(jīng)觀察到一類(lèi)稱(chēng)為無(wú)規(guī)模網(wǎng)絡(luò)的拓?fù)鋄Barabasi和Albert1999]常常出現(xiàn)。無(wú)規(guī)模網(wǎng)絡(luò)是節(jié)點(diǎn)度數(shù)遵循冪律分布的網(wǎng)絡(luò)。無(wú)規(guī)模網(wǎng)絡(luò)的一個(gè)顯著特征是，大量的節(jié)點(diǎn)（被稱(chēng)為集線器節(jié)點(diǎn)）包含大的節(jié)點(diǎn)度，而大多數(shù)節(jié)點(diǎn)（通常稱(chēng)為葉節(jié)點(diǎn)）包含相對(duì)較小的節(jié)點(diǎn)度。無(wú)規(guī)模網(wǎng)絡(luò)是具有偏斜節(jié)點(diǎn)度分布的網(wǎng)絡(luò)的一個(gè)明確例子。近年來(lái)，無(wú)規(guī)模網(wǎng)絡(luò)受到了很多的關(guān)注，因?yàn)橐呀?jīng)觀察到許多現(xiàn)實(shí)世界的系統(tǒng)包含至少近似的無(wú)規(guī)模屬性的網(wǎng)絡(luò)[WangandChen2003]。例如，人們普遍認(rèn)為互聯(lián)網(wǎng)的自治系統(tǒng)（AS）級(jí)的拓?fù)浣Y(jié)構(gòu)是無(wú)規(guī)模的[Faloutsosetal。1999;Siganos等人2003;張等人2011]。在系統(tǒng)生物學(xué)的廣泛領(lǐng)域、復(fù)雜生物系統(tǒng)的研究里，蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)的研究已被證明遵循無(wú)規(guī)模分布[Kitano2002]。一些金融網(wǎng)絡(luò)，如同業(yè)支付網(wǎng)絡(luò)，顯示出無(wú)規(guī)模的行為[Soramakietal。2007年]。據(jù)報(bào)道，社會(huì)網(wǎng)絡(luò)、維網(wǎng)、超導(dǎo)體的內(nèi)部結(jié)構(gòu)、航空運(yùn)輸網(wǎng)絡(luò)以及諸如表征疾病傳播的人類(lèi)互動(dòng)網(wǎng)絡(luò)，都在不同程度上呈現(xiàn)出無(wú)規(guī)模屬性。雖然其他網(wǎng)絡(luò)沒(méi)有遵循冪律分布，但似乎他們的節(jié)點(diǎn)度分布很歪斜。例如，初步研究表明互聯(lián)網(wǎng)的路由器級(jí)拓?fù)渥裱瓋缏桑罱墓ぷ鲌?bào)告說(shuō)，拓?fù)溆晒こ毯徒?jīng)濟(jì)因素以及物理節(jié)點(diǎn)和鏈路容量約束驅(qū)動(dòng)，導(dǎo)致節(jié)點(diǎn)度分布是偏斜的，但是不遵循冪律[Li，Aldersonetal。2004年]。路由器級(jí)拓?fù)湓诰W(wǎng)絡(luò)邊緣包含許多高級(jí)路由器，用于將許多低帶寬連接的流量與具有較少數(shù)量高帶寬鏈路的大容量路由器的網(wǎng)狀核心進(jìn)行聚合。網(wǎng)絡(luò)拓?fù)鋵?duì)并行離散事件仿真在并行性和同步算法上的效率，有著很大的影響。例如，Guclu等人[2004]，配置在環(huán)形拓?fù)渲械腖P網(wǎng)絡(luò)增加了每個(gè)LP的一個(gè)附加鏈路，用于同步目的，以創(chuàng)建小世界拓?fù)洌蕴岣呖蓴U(kuò)展性。根據(jù)經(jīng)驗(yàn)觀察到，通信網(wǎng)絡(luò)的模擬中事件級(jí)并行性的分布，可能導(dǎo)致嚴(yán)重的負(fù)載不平衡[Liu和Chien2004]。在Dobrescu等人[2008]PDNS實(shí)驗(yàn)中，并行版本的NS2仿真[Rileyetal。2004]來(lái)模擬無(wú)規(guī)模網(wǎng)絡(luò)，報(bào)道了使用少量處理器實(shí)現(xiàn)加速的一些成功，但注意到僅使用六個(gè)處理器的仿真網(wǎng)絡(luò)流量，有適度的減緩。在D'Angelo和Ferretti[2009]中，并行無(wú)規(guī)模網(wǎng)絡(luò)仿真中的負(fù)載分配問(wèn)題，在模擬八卦協(xié)議中，有被檢查和評(píng)估。在Pienta和Fujimoto[2013]中研究了冪律拓?fù)渑c并行仿真器性能之間的關(guān)系，通過(guò)兩種分析模型和模擬觀察，非常大的網(wǎng)絡(luò)模擬可能產(chǎn)生非常有限的并行性。例如，包含數(shù)萬(wàn)個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的無(wú)規(guī)模網(wǎng)絡(luò)通常表現(xiàn)出少于百倍的并行性。最后，其他工作考察了無(wú)規(guī)模網(wǎng)絡(luò)生成中的并行性[Hruzetal。2010;Yoo和Henderson2010]和使用本地和全局同步技術(shù)的混合同步方法[LiuandRong2012]。對(duì)于一些PDES同步算法，無(wú)規(guī)模網(wǎng)絡(luò)是一個(gè)具有挑戰(zhàn)性的測(cè)試用例。它們有問(wèn)題的一個(gè)原因是因?yàn)闊o(wú)規(guī)模網(wǎng)絡(luò)擁有所謂的小世界屬性。小世界網(wǎng)絡(luò)的區(qū)別在于網(wǎng)絡(luò)中兩個(gè)隨機(jī)選擇的節(jié)點(diǎn)之間的平均最小路徑長(zhǎng)度非常小；即使對(duì)于包含數(shù)百萬(wàn)個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，該長(zhǎng)度也可能只有幾個(gè)跳數(shù)。冪律分布的特征在于參數(shù)λ，其決定了將發(fā)生的高度節(jié)點(diǎn)的數(shù)量。在的情況下，自然無(wú)規(guī)模網(wǎng)絡(luò)的