一種多人在線網路遊戲伺服器的並行優化技術的製作方法

2023-05-29 23:06:41

專利名稱：一種多人在線網路遊戲伺服器的並行優化技術的製作方法
技術領域：
本發明涉及一種利用多處理器在多人在線網路遊戲中的伺服器端的優化技術
背景技術：
基於客戶端伺服器模式的多人在線網路遊戲中，伺服器需要把一個客戶端產生的消息轉發給其它的客戶端。事實上並不是所有客戶端都關心該消息，轉發無用消息引起了網絡帶寬過度佔用和資源大量消耗，從而使得網絡帶寬和資源成為影響響應延時和伺服器幀速率的瓶頸。興趣管理技術通過計算對事件感興趣的客戶端的方法，在增加處理器負載的前提下，有效緩解了帶寬佔用和資源消耗。 興趣過濾技術產生於支持DIS (Distributed Interactive Simulation)協議的實時分布仿真系統中，主要在軍事仿真、多人在線遊戲等領域得到運用，如ModSAF(ModularSemi-Automated Forces)是一個面向美國軍隊的構造模擬系統，產生在90年代。NPSNET(Naval Postgraduate School NET) [6]採用六邊形網格來近似表達實際的圓形"感興趣區域"。當實體前向運動時，在它加入新網格的前沿邊之後，離開老網格的尾沿邊之前，該網格的半徑即為實體的"感興趣區域"。 興趣管理技術通過計算實體感興趣的區域(A0I)過濾了無用的消息的同時增加了伺服器的計算負載。 為了能夠支持大量的計算負載，多伺服器技術是一種解決方案，多伺服器技術將虛擬場景劃分成若干區域，每個伺服器負責一個區域，在區域和區域之間以維護影子對象的方法實現無縫的移動。然而維護多伺服器的數據同步增加了額外的計算開銷和網絡負載。 近年來新興的單晶片多核體系結構是對多線程的晶片級別支持的一種大規模並行技術。使伺服器的流程並行化，充分利用多處理器的計算能力可增加伺服器支持的玩家數量。 為了快速開發利用這種晶片的並行性而獲取更高性能的並行應用程式需要採用合適的編程模型。0penMP作為編寫共享內存系統的並行程序的工業標準成為一個合理的候選者。OpenMP起源於ANSI標準，它具有簡單、移植性好和可擴展等優點，是共享存儲系統編程的一個工業標準。OpenMP並不是一門新的語言，它是對基本語言(如Fortan77、 01^肌90、(:、[++等)的擴展。OpenMP規範中定義的制導指令、運行庫和環境變量，能夠使用戶在保證程序的可移植性的前提下，按照標準將已有的串行程序逐步並行化。
本發明將伺服器流程並行化，運用0penMP將並行後的算法進行了實現。

發明內容
本發明要解決的技術問題是在多人在線網路遊戲中，克服了伺服器串行流程只能利用單處理器的不足，能夠充分利用多處理器的資源。
本發明採用的技術方案為將伺服器的興趣過濾、同步信息等流程並行化，其特點
3在於包括了以下四個步驟 (1)基於分組任務的模式並行處理生成實體興趣區域更新散列表和同步散列表這 兩個任務。運用這兩個散列表能夠使伺服器不必逐幀計算實體的興趣區域和同步實體的信 息從而增加伺服器可以承擔的玩家數量； (2)基於數據的分解模式並行計算實體的興趣列表，該興趣列表記錄了哪些客戶 端對該實體感興趣； (3)基於數據的分解模式並行處理伺服器的遊戲邏輯，遊戲邏輯包括實體位置更 新、毀傷計算、碰撞檢測等； (4)基於數據的分解模式並行同步客戶端和伺服器的信息。 所述實體興趣區域更新散列表和同步散列表記錄的是每一幀需要更新興趣區域 和需要同步實體信息的兩個二維數組。 假設伺服器要求在k幀內遍歷所有的實體並進行興趣區域實體更新，並假設有N 個實體，則每一幀需要更新的實體數為N/k個。為了支持並行數據分解模式，這裡設計了一 個二維數組AoIRefreshTable".來存儲每幀需要更新的實體列表。假如c表示當前幀數，一 維數組AoIRefreshTablei表示第i = c% k幀時需要更新的實體列表。圖1為當k等於30 時的興趣區域更新散列表。 此外基於類似的策略，伺服器端每一幀按照一定邏輯維護的實體狀態，這些邏 輯包括物理規則、遊戲規則等，但不必逐幀對客戶端進行實體狀態更新，可以隔幀進行同 步(包括位置信息、運動狀態等)。假設同步的周期為s幀，伺服器採用一個二維數組 SYNRefreshTableij來存儲每幀需要同步的實體列表。假設c表示當前幀數， 一維數組 SYNRefreshTablei表示第i = c% s幀時需要同步的實體列表。 運用這兩個數組，不必每幀所有實體的興趣區域和同步所有實體的信息，降低了 網絡和處理器的負載。 如果實體的數量有變動(如果有玩家退出、登陸、實體銷毀等)，則需要從新生成
實體興趣區域更新散列表和生成實體同步散列表，生成過程對於同一幀無依賴性，可以使
用了 OpenMP的section編譯製導語句，基於分組任務的分解模式進行任務並行。 所述並行計算實體的興趣列表中，興趣列表記錄了哪些客戶端對該實體感興趣。 在傳統的的伺服器流程中需要串行的計算所有實體的興趣區域。 為了突破以上限制，本發明使用興趣區域更新散列表AoIRefreshTable來記錄該
幀需要計算興趣區域的實體，假設伺服器要求在k幀內遍歷所有的實體並進行興趣區域實
體更新，並假設有N個實體，則每一幀需要更新的實體數為N/k個。需要更新的實體數由N
個減少到了 N/k個。 這N/k個實體的興趣區域的更新互相之間沒有數據相關性和順序相關性。可以使 用基於數據的分解模式進行並行優化。例如在一個有兩個處理器的伺服器上，可以用處理 器1計算[1， N/2k-l]這N/2k-l個實體，處理器2計算[N/2k， N/k]這些實體，這樣實現了 數據的並行處理。 所述並行處理伺服器的遊戲邏輯是並行計算實體位置更新、毀傷計算、碰撞檢測
等 伺服器在每一幀需要處理所有實體的遊戲邏輯，假設整個虛擬場景有N個實體，在在傳統的的伺服器流程中需要依次對這N個實體進行處理。 因為實體的計算遊戲邏輯的過程中，互相之間沒有相關性，本發明中基於數據的 分解模式進行並行優化。例如在一個有兩個處理器的伺服器上，可以用處理器l計算[1， N/2-1]這N/2-1個實體，處理器2計算[N/2， N]這些實體，這樣實現了數據的並行處理。
所述並行同步客戶端和伺服器的信息是並行計算客戶端的變化，並將這些變化和 客戶端保持同步。 在傳統的伺服器流程中，伺服器需要每一幀串行的同步所有實體的信息。 基於類似並行更新興趣區域的策略，本發明使用實體同步散列表
SYNRefreshTable來記錄該幀需要計同步的實體，假設伺服器有N個實體，要求在k幀內遍
歷所有的實體並進行同步，則每一幀需要同步的實體數為N/k個。需要同步的實體數由N
個減少到了 N/k個。這N/k個實體的興趣區域的更新互相之間沒有數據相關性和順序相關
性。採用和並行計算實體的興趣列表相同的策略進行同步並行化。


圖1為本發明所使用的伺服器幀速率為30幀時的更新散列表；
圖2為不使用並行優化的傳統的伺服器流程圖；
圖3為本發明使的伺服器流程圖；
圖4為本發明實現的網路遊戲原型； 圖5為使用本發明的更新散列表，在特定情況下改變更新周期為1， 2， 4， 8， 15， 30 時，伺服器端的CPU佔用率； 圖6為本發明在特定情況下，在多處理器上的性能表現數據。
具體實施例方式
為了實現和驗證本發明，我們設計實現了即時戰略類型的在線遊戲原型TankWar 0. l，遊戲的客戶端程序使用Microsoft DirectX編程接口，實現了簡單的三維場景繪製 包括基於高度圖的地形網格生成、動態紋理的天空盒。客戶端的界面如圖4所示。
遊戲的伺服器端採用基於OpenMP編程接口將算法進行處理。處理過程利用 0penMP的for、 section等編譯製導語句。 首先，伺服器端接收並處理玩家消息。這一步伺服器接收客戶端的消息，並對消息 做出響應。例如消息為新加入玩家消息，直接在玩家鍊表中加入玩家實體並通知別的客戶 端有玩家加入。並通知感興趣的玩家實體刪除消息。如果是移動物體的消息，把該物體標 記為移動的，並且給物體的目的地、速度等賦值。 第二步如果實體的數量有變動則並行生成實體興趣區域更新散列表和同步散列 表，這裡設計了一個二維數組AoIRefreshTableij來存儲每幀需要更新的實體列表。假如 c表示當前幀數，一維數組AoIRefreshTablei表示第i = c% k幀時需要更新的實體列表。 圖1為當k等於30時的興趣區域更新散列表。生成同步散列表的實現和生成實體興趣區 域更新散列表的方法相同，採用一個二維數組SYNRefreshTableij來存儲每幀需要同步的 實體列表。，一維數組SYNRefreshTablei表示第i = c% s幀時需要同步的實體列表。這兩 個步驟使用了 0penMP的section編譯製導語句，基於分組任務的分解模式進行任務並行。實現的偽代碼如下 if (objModified) { 〃如果有物體變動，更新興趣列表更新列散表同步列散表
#pragma omp sections private (i) { #pragma omp section 〃更新興趣列表更新列散表 for(0bjecti ;in objArray) A0IFreshTable[i% MFrame]. push_back(0bjecti); Spragma omp section 〃更新同步列散表 for(0bjecti ;in objArray) SYNFreshTable [i % SYNFrame]. push—back (0b ject》； } objModified = false ; } 第三步更新興趣列表，將興趣列表前後的變化通知給客戶端玩家。每個實體有
個NewAoIList和LastAoIList分別記錄這一幀(伺服器本次計算循環)和上一幀(服務 器上一次計算循環)中對該實體感興趣的其它實體的集合。 在更新完實體的興趣區域後，更新玩家的發現實體和實體離開的消息，對於實體 在objANewAoIList中，而不在objA的LastAoIList中。貝U向objA的所屬玩家playerA發 送發現實體消息。反之對於實體在ob jA的LastAoIList中，而不在ob jA的NewAoIList中。 則向objA的所屬玩家playerA發送實體離開的消息。 計算興趣列表和興趣列表前後的變化通知給客戶端玩家採用0penMP的for編譯 制導語句，基於數據的分解模式進行任務並行。 第四步處理伺服器遊戲邏輯。在這步處理攻擊，毀傷計算，碰撞檢測等信息。這一 步採用omp for指令展開到多個線程上執行，實現數據的並行計算。 第五步更新玩家實體狀態。經過前面步驟計算後，伺服器端的實體狀態發生變化 (如位置信息、運動狀態等)，這一步根據實體狀態同散列表SYNRefreshTable裡的信息對 玩家實體進行狀態更新，採用omp for指令將展開到多個線程上執行，實現數據的並行計算。 上述實現偽代碼如下 #pragma omp for 〃更新這一幀需要更新的興趣列表，並反饋給客戶端 for (0bjecti ;in AOIFreshTable[framecount% IMFrame]) { GenerateAOIList (0b ject》；〃 更新這一幀需要更新的興趣 列表 ReflectPlayerAOI (Object》； }〃反饋給客戶端 #pragma omp for 〃並行處理，這一幀的伺服器邏輯，如碰撞、移動(可以在這裡處理攻 擊等信息) for (0bjecti ;in objArray) Handlelxigic(Objecti); #pragma omp for 〃同步這一幀需要同步的客戶端 for (Object ;in SYNFreshTable[framecount% SYNFrame]) SynchPlayer(0bjecti); 圖3為採用上述發明並行優化後的伺服器端在兩個處理器上的流程圖，可以對比 串行流程(圖2)對比串行和並行的差異。 如圖5所示，是興趣區域更新周期IMFrame的取值對伺服器CPU的負載的影B向。本 測試在區域網中實現，保證伺服器幀速為25幀每秒。設置位置同步周期為50，即50幀同 步一次位置信息，區域網中共啟動25個客戶端，每個客戶端加入200個實體。在伺服器端 線程數等於處理器個數的時候，改變實體的被感興趣玩家列表的更新周期IMFrame，測試服 務器端CPU的佔用率。測試數據可以看出實體的被感興趣玩家列表的更新周期MFrame和 CPU的負載成的反比例關係。由此可以看出興趣區域更新散列表的發明能夠很大程度上降 低伺服器的計算負載。 圖6為該發明在多處理器伺服器上的性能表現，設置位置同步周期為50，即50幀 同步一次位置信息。為了增加CPU的負載，伺服器端每幀進行興趣過濾。區域網中共啟動 25個客戶端，每個客戶端依次加入200個實體。分別測試在不同伺服器上串行算法(單線 程)和並行算法(線程為處理器個數二倍時)伺服器可以保持的最大幀速並計算加速比和 CPU有效使用率。 加速比S(P)為程序在串行情況下的執行時間和並行執行時間的比值，定義如為
formula see original document page 7 效率E(P)的定義為加速比除以處理器個數，如下公式所示，其中P為處理器個數。 formula see original document page 7 其中T(l)為串行時每幀耗時，T(P)為並行程序的耗時。 測試說明了採用OpenMP進行並行優化後，充分的利用了 CPU的資源，使得服務能 夠保持的最大幀速得以提升。當線程數大於CPU的核數的時候，因為線程派生聚合的開銷 性能不會上升反而會有少量下降，如表6. 6中，在4處理器的伺服器上，8線程的時候性能 比4線程時略有降。這說明了該發明在能夠在多處理器伺服器上使得伺服器性能提升，在 多人在線網路遊戲中能夠得到運用。
權利要求
一種多人在線網路遊戲伺服器的並行優化方法，其特徵在於包括以下四個步驟(1)基於分組任務的模式並行的處理，生成實體興趣區域更新散列表和同步散列表；運用這兩個散列表使伺服器不必逐幀計算實體的興趣區域和同步實體的信息從而增加伺服器可以承擔的玩家數量；(2)根據步驟(1)中獲得的興趣區域更新散列表，基於數據的分解模式並行計算實體的興趣列表，所述興趣列表記錄了對該實體感興趣的客戶端；(3)基於數據的分解模式並行處理伺服器的遊戲邏輯，遊戲邏輯包括實體位置更新、毀傷計算、碰撞檢測；(4)根據步驟(1)中獲得的同步散列表，基於數據的分解模式並行同步客戶端和伺服器的信息。
2. 根據權利要求1所述的一種多人在線網路遊戲伺服器的並行優化方法，其特徵在於所述不必逐幀計算實體的興趣區域和同步實體的信息具體在於(1) 採用隔幀興趣區域實體更新策略假設伺服器要求在k幀內遍歷所有的實體並進行興趣區域實體更新，並假設有N個實體，則每一幀需要更新的實體數為N/k個；(2) 如果實體個數有變動，則計算興趣區域更新散列表和同步散列表，這兩個列表分別記錄了每一幀需要更新和同步的實體，保存在一個二維數組裡；(3) 基於類似的策略，伺服器端逐幀按照一定邏輯維護實體狀態，這些邏輯包括物理規則、遊戲規則，但不逐幀對客戶端進行實體狀態更新，而是隔幀進行同步。
3. 根據權利要求1所述的一種多人在線網路遊戲伺服器的並行優化方法，其特徵在於，所述基於分組任務的模式並行的處理和基於數據的分解模式的並行處理伺服器的遊戲邏輯(1) 生成實體興趣區域更新散列表和更新同步散列表的過程，相互間沒有先後依賴性，也沒有數據依賴性。因此基於分組任務的模式進行並行處理；(2) 計算實體的興趣列表，處理伺服器的遊戲邏輯，同步客戶端和伺服器的信息這三個步驟需要處理多個實體，被處理的實體互相之間沒有先後依賴性，也沒有數據依賴性，因此基於數據的分解模式並行處理。
全文摘要
多人在線網路遊戲伺服器的並行優化方法，包括以下四個步驟基於分組任務的模式使生成實體興趣區域更新散列表和同步散列表這兩個任務能夠並行的處理。這兩個散列表能夠使伺服器不必逐幀計算實體的興趣區域和同步實體的信息；基於數據的分解模式並行計算每個實體的興趣列表，該興趣列表記錄了哪些客戶端對該實體感興趣；基於數據的分解模式並行處理伺服器的遊戲邏輯，遊戲邏輯包括實體位置更新、毀傷計算、碰撞檢測等；基於數據的分解模式並行同步客戶端和伺服器的信息。本發明通過將興趣過濾、伺服器邏輯處理等計算負載分配到多個處理上，提高了遊戲的實時性，增加了可負載的玩家的數量。
文檔編號H04L29/06GK101795275SQ20101010524
公開日2010年8月4日 申請日期2010年2月3日 優先權日2010年2月3日
發明者楊碩磊, 王莉莉, 趙沁平, 郝愛民 申請人:北京航空航天大學