畢業(yè)設計（論文）文獻譯文：并行與分布式仿真中的研究挑戰(zhàn)

畢業(yè)設計（論文）--文獻翻譯原文題目ResearchChallengesinParallelandDistributedSimulation譯文題目并行與分布式仿真中的研究挑戰(zhàn)專業(yè)信息與計算科學姓名學號指導教師并行與分布式仿真中的研究挑戰(zhàn)RICHARDM.FUJIMOTO,GeorgiaInstituteofTechnology摘要并行與分布式仿真領域從20世紀70年代和80年代就發(fā)展壯大起來，目前仍然是一個活躍的研究領域。介紹了該領域研究的簡要概述。未來研究課題的領域，包括大規(guī)模系統(tǒng)和復雜網(wǎng)絡的問題驅動仿真、圖形處理單元硬件和云計算環(huán)境的開發(fā)、系統(tǒng)管理和優(yōu)化的預測性在線模擬、移動平臺和數(shù)據(jù)中心的電力及能源消耗、以及異構仿真的組成。3.2利用并行和分布式仿真中的圖形處理單元挑戰(zhàn)2。開發(fā)實用，可擴展的技術，在現(xiàn)代高性能計算中利用圖形處理單元（GPU）加速器和移動計算平臺可以顯著加速現(xiàn)實世界的模擬應用程序?，F(xiàn)代超級計算機越來越多地利用硬件加速器來實現(xiàn)更高的并行性和更高的性能水平，特別是對于數(shù)據(jù)并行計算。GPU逐漸地出現(xiàn)在智能電話和移動計算設備中，從而增加了其計算能力。GPU是從中央處理單元（CPU）卸載計算任務的硬件加速器。最初設計用于在工作站和個人計算機中渲染圖形，因為它們被廣泛應用于加速數(shù)據(jù)密集型數(shù)字計算的手段。由于批量生產導致的低單位成本及其對數(shù)值計算的適用性使得GPU成為高性能計算和移動系統(tǒng)的有吸引力的組件。迄今為止的大部分工作都集中在利用GPU進行數(shù)值計算問題。然而，越來越多的工作集中在離散模擬，盡管迄今為止這項工作大部分集中在諸如細胞自動機之類的時間步長的仿真應用，而不是事件驅動的模擬。與利用GPU相關的許多挑戰(zhàn)來自于其獨特的硬件架構。需要開發(fā)一種將PDES計算映射到硬件的方法，以有效利用GPU。必須解決的主要挑戰(zhàn)可以分為PDES計算映射到GPU的計算、存儲器和通信架構的映射有：1.計算架構：離散事件仿真計算必須映射到單程序，多數(shù)據(jù)（SPMD）流式并行在GPU中使用的執(zhí)行。2.內存架構：通常在離散事件仿真中使用的不規(guī)則動態(tài)數(shù)據(jù)結構必須映射到GPU的存儲器架構，這更適合于靜態(tài)的常規(guī)數(shù)據(jù)結構，如矩陣和陣列。3.通信架構：用于向GPU傳輸數(shù)據(jù)的有限通信帶寬；在CPU和GPU存儲器之間復制數(shù)據(jù)可能是耗時的，并且必須保持在可管理的級別以避免性能嚴重下降。下面討論這些問題。3.2.1SPMD執(zhí)行出于這個討論的目的，我們將使用在HPC平臺中廣泛使用的NVIDIA<顯卡>GPU體系結構作為參考。圖2顯示了GM107的“麥克斯韋”體系結構。這GPU如同一個協(xié)處理器與通用CPU同時執(zhí)行計算。如圖所示，每個GPU包括幾個多流處理器（SMMs）。每個SMM都使用一個SPMD執(zhí)行模式，并在多個數(shù)據(jù)元素中并行執(zhí)行相同的程序。具體來說，每個SMM包括128個計算核心（也稱為CUDA核心或流處理器），其中每個核心都大致具有這種算術邏輯單元（ALU）的能力。每個SMM執(zhí)行計算的單位被稱為warps（與時間扭曲無關），其中每個warp由一組32個執(zhí)行線程組成。一個公共指令可以由所有32個線程并發(fā)執(zhí)行，每個線程都在不同的數(shù)據(jù)元素上運行。從程序員的角度來看，GPU計算是由一組線程塊組成，每個線程塊是由一個或多個warps組成。內核網(wǎng)格是CPU調用的線程塊的集合。每個線程塊被分配給一個單獨的SMM執(zhí)行。每個SMM可以支持多達2048個并發(fā)線程，或64個warps。32個線程的warps可以預定執(zhí)行的計算單位,如前所述,每個warp都和SPMD程序一樣執(zhí)行。離散事件模擬的計算可以看作是一組單獨的事件計算，其中每個事件計算可以（1）修改一個或多個狀態(tài)變量或（2）計劃新事件。GPU使用的SPMD<單程序流多數(shù)據(jù)流>范例意味著，模擬最好是包含少量不同類型的事件，理想情況下只有一個事件。例如，使用“先到先服務”(FCFS)規(guī)程的排隊網(wǎng)絡模擬可以用兩種事件類型來編程:離去和到達事件。但是，如果將工作從服務器轉移到另一個隊列的時間為零，那么就會發(fā)現(xiàn)，從一個隊列開始的工作在與該工作到達下一個隊列時完全相同的模擬時間發(fā)生。因此，離去和到達可以合并為一個事件，例如，將離去事件的計算和到達事件合并，與下一個隊列的工作到崗相對應。另外，如果使用了先到先服務的排隊規(guī)則，則可以完全排除離去事件，只處理到達事件。這樣的修改可以減少不同事件類型的數(shù)量，使程序更適合于SPMD處理。重組程序以減少不同類型的事件的數(shù)量不足以確保有效執(zhí)行。單個事件過程中的數(shù)據(jù)依從條件語句可以導致不同的事件計算(線程)來執(zhí)行不同的機器指令序列。換句話說，一些執(zhí)行基于一組數(shù)據(jù)的條件謂詞的LP可以接受if-then-else<如果-則-否則>語句的“then”<如果>子句，而其他使用相同謂詞的不同數(shù)據(jù)的LP可能執(zhí)行“else”<否則>子句。這些不同的指令序列的執(zhí)行必須在SPMD體系結構中順序執(zhí)行。因此，我們應該在程序中使用數(shù)據(jù)依從的條件控制流來盡量減少或排除語句中的語句。對于許多復雜的模擬來說，這可能很難或不可能。在SPMD架構上檢查PDES程序的執(zhí)行情況可以追溯到上世紀80年代末。早期的工作包括研究用于排隊網(wǎng)絡的SPMD架構和自旋模擬[Lubachevsky1989]以及電子電路的邏輯模擬[ChungandChung1991]。在GPU架構的環(huán)境下，一些工作已經解決了這個問題，例如昆茨等。[2012]。被描述為根據(jù)事件類型對事件進行排序，并將它們的執(zhí)行集中起來的一種方法，以解決前面描述的SPMD執(zhí)行所產生的問題。3.2.2不規(guī)則數(shù)據(jù)結構第二個挑戰(zhàn)涉及PDES程序使用的數(shù)據(jù)結構與現(xiàn)代GPU架構中提供的存儲器層次結構的映射。前面討論過的NVIDIAGPU包括一個全局內存，通常幾百兆字節(jié)到幾千兆字節(jié)，可以由SMM中的任意線程訪問。訪問全局內存相對較慢，吞吐量為每秒幾百GB；然而，GPU將通過將單個引用聚合為單個操作來優(yōu)化對連續(xù)存儲器位置的訪問。還有一個每個塊的內存可以訪問一個塊內的線程，這是幾十千字節(jié)，并提供了全球內存的七倍的帶寬。每塊存儲器被實現(xiàn)為一組N個存儲體。多個線程可以同時訪問存儲器的不同存儲區(qū)，但是必須對存儲單元內的值進行訪問。因此，為了最大限度地提高性能，必須注意將數(shù)據(jù)分配給存儲體。例如，如果將一列二維矩陣的元素映射到不同的存儲體，同時將列的元素映射到同一個存儲體，則可以有效地執(zhí)行對矩陣行進行操作的算術運算，而那些在單列上運行將導致內存爭用和序列化執(zhí)行。利用GPU進行PDES計算的兩個關鍵挑戰(zhàn)涉及內存分配和數(shù)據(jù)結構映射到GPU的內存。GPU最適合于對靜態(tài)向量或數(shù)據(jù)矩陣進行的常規(guī)計算。然而，傳統(tǒng)的PDES程序在一組LP之間分割模擬狀態(tài)，每個LP被視為模擬的自主組件，而不是數(shù)據(jù)陣列。這可能導致對存儲器元件的不規(guī)則訪問，這取決于LP在何時執(zhí)行，以及如何將LP存儲器映射到GPU的存儲器。此外，NVIDIAGPU不支持動態(tài)內存分配，而動態(tài)內存分配在許多PDES應用程序中很常見。這可以通過使用靜態(tài)分配的數(shù)組來存儲和數(shù)組索引而不是指針來管理。然而，除非對陣列的連續(xù)引用使用連續(xù)的存儲器位置，否則將難以利用GPU優(yōu)化，例如合并存儲器引用，并且與存儲器組的沖突可能導致性能下降。3.2.3通訊和記憶副本在諸如前面描述的NVIDIAGPU的系統(tǒng)中，CPU和GPU存儲器占用分開的地址空間；CPU不能直接訪問GPU的存儲器，反之亦然。通常情況下，GPU存儲器不夠大，不能保持整個計算，因此在整個模擬執(zhí)行過程中必須在CPU和GPU存儲器之間移動數(shù)據(jù)。兩個存儲器之間的通信是耗時的。這種限制可能在支持CPU和GPU之間的共享存儲器的未來體系結構中得到解決；然而現(xiàn)在，必須構建程序，因此CPU和GPU內存之間的副本不能頻繁發(fā)生，以避免顯著的性能下降。這突出了需要在存儲器復制操作之間進行大量的仿真計算。這個問題的變化在GPU發(fā)明前很久就出現(xiàn)在計算機體系結構中，在高速緩沖存儲器系統(tǒng)中出現(xiàn)類似的問題，其中數(shù)據(jù)必須在CPU能夠對數(shù)據(jù)進行操作之前傳輸?shù)礁咚倬彺?。解決高速緩存存儲器問題的常見方法是通過允許CPU在數(shù)據(jù)傳輸發(fā)生時執(zhí)行其他計算來隱藏與傳輸數(shù)據(jù)相關聯(lián)的延遲。這里可以采用類似的方法來解決CPU和GPU存儲器之間的存儲器傳輸延遲問題。理想情況下，GPU計算可以與到GPU存儲器的數(shù)據(jù)傳輸同時進行。Kunz等人討論了在GPU上執(zhí)行的PDES代碼的潛伏隱藏方法。[2012]?？紤]一組獨立的事件計算，并且可以并發(fā)執(zhí)行。使用流水線的方法用于隱藏CPU和GPU內存之間數(shù)據(jù)傳輸?shù)难舆t。管道由三個階段組成。第一個是將數(shù)據(jù)從CPU傳輸?shù)紾PU存儲器，第二個是在GPU內執(zhí)行事件計算，第三個是將這些計算的結果傳送回CPU存儲器。如果存在許多并發(fā)事件，并且事件計算涉及足夠的計算，以便GPU不必等待數(shù)據(jù)傳輸完成，則該方法可以實現(xiàn)GPU硬件的全面利用以實現(xiàn)并發(fā)事件處理，假設事件計算順利結構化為SPMD程序，如前所述。Kunz等人描述的整體方法。[2012]。還利用了多次仿真復制產生的并行性，以減少執(zhí)行多個獨立模擬運行所需的時間。調度和負載均衡是異構計算機體系結構中出現(xiàn)的其他重要問題。Romdhanne等人提出了一種解決這個問題的方法。[2013]。提出了基于使用時間驅動和事件驅動執(zhí)行的混合樣式的調度器。還提出了一種動態(tài)機制來最大化事件處理的流程。今天的超級計算機通常包括許多處理節(jié)點，每個處理節(jié)點都配備有通過高速網(wǎng)絡連接的多個CPU和GPU加速器。這些機器為大規(guī)模并行代碼帶來了額外的復雜性，進一步使前面所述的問題更為激烈。延遲隱藏技術在開發(fā)這些計算架構時變得更加重要[Zou等人。2013。在MIMD計算模型中使用大量內核的多核架構中，有效利用緩存和管理大量計算線程同樣重要。3.2.4應用迄今為止使用GPU進行離散模擬的大部分工作都集中在時間上的模型上。蜂窩自動機非常適合GPU架構所施加的約束。每個線程都可以捕獲單個單元的行為。因為單元格執(zhí)行相同的規(guī)則，所以計算非常適合于SPMD計算，只要規(guī)則不需要復雜的數(shù)據(jù)相關條件行為?？梢允褂渺o態(tài)數(shù)組數(shù)據(jù)結構來實現(xiàn)仿真的狀態(tài)，并且每個單元僅與相鄰單元進行交互的事實導致結構良好的規(guī)則的存儲器參考模式。此外，只要模擬狀態(tài)符合GPU內存，除了模擬開始和結束之外，CPU和GPU的存儲器之間不需要復制狀態(tài)。已經在諸如交通模擬的應用中探索了GPU的時間步長模擬的使用[Perumalla等人。2009年；徐等人2014]，系統(tǒng)生物學[Falk等人。2011]和IsingSpin[Hawick等人。2011]等。有限的研究集中在事件驅動的模擬執(zhí)行。Park和Fishwick。[2011]。中描述了一種在GPU上執(zhí)行排隊網(wǎng)絡仿真的方法。該方法有效地利用時間步長的執(zhí)行機制來實現(xiàn)離散事件仿真。該方法通過將事件時間戳強制到時間邊界上來引入計算中的錯誤，從而在精度和執(zhí)行效率之間引入折衷。盡管觀察到誤差隨著簇的大小而增加，但實現(xiàn)了10倍的加速度，具有小的誤差。Li等人描述了利用三步法生成事件，對它們進行排序，處理它們以及使用時間并行仿真技術的另一種方法。[2013]。最后，另一個研究領域集中在混合方法，其中模擬部分在GPU上執(zhí)行，而其余的模擬在CPU上執(zhí)行。例如，Liu等人。[2014]。描述了一種用于電信網(wǎng)絡的混合仿真的方法，其中由CPU執(zhí)行離散事件分組級仿真，同時由GPU執(zhí)行流量的連續(xù)數(shù)值流體流模擬。諸如這些方法涉及將計算分成單獨的任務，并將每個任務映射到最適合該任務的體系結構。3.2.5未來方向雖然有越來越多的PDES利用GPU硬件加速器的工作，但是使用這些架構并不常見，而且還有許多工作要做。從前面的討論中應該清楚，使用GPU加速器將PDES計算映射到并行計算機體系結構上并不是一件簡單的任務。在開發(fā)PDES代碼時，必須考慮到架構的許多低級細節(jié)。此外，隨著這些架構隨著時間的推移而發(fā)生變化，隨著架構的發(fā)展，可能需要重新編譯應用程序。解決這個問題