01 背景與問題

  網格對于數值模擬十分重要?；诰W格的離散是數值計算中最主流的空間離散方式，而網格的類型和質量直接影響計算的精度和效率。一般情況下，網格尺寸越小，數值離散引入的截斷誤差越小。但除此以外，網格的正交性、斜率，甚至與物理場特征的一致性也都或多或少會影響數值計算的誤差。另一方面，網格拓撲也決定了數值計算程序底層數據結構，從而很大程度上決定了計算的效率。例如，根據一般經驗，結構化網格計算效率約是非結構化網格的3倍。當然，除了以上因素，網格生成的難易程度也是影響實踐中網格選擇的重要因素。一些常用的網格形式列舉如下：

各種網格形式（素材來源于網絡）  

  隨著數值模擬精度和效率要求不斷提高，對網格生成的效率，以及網格相關計算精度和計算效率方面提出了更多挑戰。根據筆者視角來看，最典型問題包括網格生成效率低、多尺度特征捕捉和先進硬件平臺適配等問題。   

  問題一：網格生成效率低   

  手動生成高質量網格一直是非常費時費力的工作。美國工業軟件公司ENVENIO發布了一份針對仿真行業的調查報告《The CFD Survey》，該調查采訪了28個國家的116位仿真從業者，涉及不同規模的公司。調查結果中顯示（如下圖），不論規模大小，所有的公司都認為在網格生成上花費了太長的時間。一方面，隨著計算機算力提升，人力成本相對越來越昂貴。另一方面，數值模擬精度要求越來越高，所需網格數量逐漸增長到超過人工可控的規模。因此，網格生成的自動化、大規?；?、并行化是網格技術發展的大勢所趨。  

仿真行業的調查結果[1]

  問題二：多尺度特征捕捉   

  物理問題天然具有多尺度特性，精確捕捉關鍵跨尺度的特征對于實現高保真模擬至關重要。以流體力學為例，超聲速空氣流動中的激波、燃燒反應流中的火焰面、多相流中的兩相界面以及幾何曲率極大的區域等，都是對應場景中的關鍵跨尺度特征。因此，為了實現高保真模擬，同時保證計算量在可接受范圍，對計算域進行精確而有針對性的網格加密是非常重要的。正如，流體力學模擬中經常對邊界層和激波區域進行網格加密，結構力學模擬中經常對應力集中區域和斷裂破壞點進行加密。不幸的是，在實際問題模擬中，大多數情況下無法預先判斷跨尺度特征出現的區域和時機。在此情況下，必然要求網格具有跟隨物理場變化而自適應加密的能力，進而引發網格加密規則等功能性問題，以及并行情況下動態負載均衡等性能問題。  

廣泛存在的多尺度流動現象（素材來源于網絡）      

  問題三：先進處理器適配      

  誠然，計算機計算能力的提升，對數值計算的精度和效率提升具有決定性作用。但隨著半導體工業進入后摩爾定律時代，處理器單核心性能提升受限，處理體系架構從單核轉向多核，再進一步轉向眾核。對基于傳統網格類型的數值計算程序，特別是非結構網格程序，體系架構的復雜化為其計算效率的發揮設置了諸多障礙。例如，復雜的編程模型要求對傳統網格體系下的數據結構和算法進行重新設計，工作量十分繁巨。再如，眾核處理器訪存帶寬提升相對浮點性能提升而言存在嚴重滯后，使得傳統網格下的數值計算程序嚴重訪存受限。     

眾核處理器（GPU）日益嚴峻的“訪存墻”[5]

   

02 SAMR特點和優勢

  SAMR的全稱是（block) Structured Adaptive Mesh Refinement (結構網格自適應)[2][3]，是基于結構化網格塊的自適應加密體系的通稱。   

  提到SAMR就不得不提自適應加密技術。實際上，自適應加密技術AMR（Adaptive Mesh Refinement）與網格類型并沒有綁定關系，例如在非結構網格中也可以通過網格重構進行自適應加密。在數值計算實踐中，基于笛卡爾網格（直角坐標網格）自適應加密易于生成且可以適應復雜幾何，因此這種技術組合十分常見。狹義的AMR通常就是指代笛卡爾網格自適應加密，下文中不再加以區分。   

（笛卡爾）AMR網格示例（素材來源于網絡）

  SAMR是AMR的一個特例，其主要的特點即加密單元是結構化的網格塊。SAMR目前主要采用兩種加密結構：第一種是Tree-based樹型結構[4]，即網格按照空間多叉樹遞歸進行加密（下圖左）；第二種是Patch-based多層分塊結構，即按照多級網格疊加進行加密（下圖右）。Tree-based加密數據結構更加優美，一般網格塊具有相同的分辨率，因此在算法實現上更加整潔和高效。Patch-based加密區域更加靈活，例如不用受到樹形加密規則的約束，以及可以針對加密區域大小使用大小不同的網格塊。   

           

Tree-based                        Patch-based              

（素材來源于網絡）   

   SAMR網格具有局部結構化特點，同時能夠通過高效的自適應能力捕捉多尺度特征。雖然笛卡爾形式網格在精確刻畫邊界上有一定不足，但是通過浸沒邊界法等非貼體網絡邊界模型也可以較好地實現邊界條件。實際上，SAMR也完全可以使用曲線網格和貼體邊界，只不過處理起來相對復雜一些。正因為SAMR相對其它網格有其獨特性，在某些方面有其突出的優勢，主要包括以下幾個方面。

  優勢一：網格自動生成   

  主要采用笛卡爾網格的SAMR技術，網格結構比較簡單，天然適合自動生成網格。幾何特別復雜或沒有水密性（存在空洞或毛刺）情況下，通過一定的處理，使用SAMR技術也能成功生成網格。這一特性，可以讓前處理過程中的幾何簡化和幾何清理工作量大大降低，從而進一步降低人力成本。在邊界處，通過脫體網格在邊界處加密和采用合適的邊界模型，也可以得到較好的精度。  

  優勢二：高效自適應加密    

  主要采用笛卡爾網格的SAMR，網格可以非常集約地集中在需要加密的位置，且自適應加密或粗化非常直接和便于實施。相對于傳統結構化網格，可以更高效地利用網格，而不必按維度進行加密。相對于非結構網格，SAMR在保持局部結構化優勢前提下，利用非常直接的等分和合并規則快速地實現網格重構，比非結構網格局部重構更為高效。   

  優勢三：更高的計算效率   

  由于SAMR具有局部結構化特征，因此可以在適應復雜幾何前提下，保證局部能夠達到傳統結構化網格的計算效率。更進一步，采用笛卡爾網格的SAMR，相對一般曲線結構網格，可以大大節約幾何描述數據，對于緩解眾核處理器內存帶寬瓶頸十分有利。再次，SAMR可以在不影響數值計算精度的條件下，通過調整網格塊分辨率，適應包括眾核處理器在內的不同平臺硬件配置（如緩存行長度、緩存大小等），以充分發揮硬件性能。在SAMR體系下，算法經過特殊設計也可以提升計算效率，例如在不同的加密層級采用不同的時間推進尺度，從而大大節約計算量。  

 

SAMR適配神威·太湖之光處理器架構體系

03 我們的SAMR框架 

  神工坊團隊發展了一套三維SAMR框架。該框架是一個基于octree[4]的多層分塊（block）網格框架軟件，并在此基礎之上構建了多層分塊數據容器。SAMR框架封裝了八叉樹多層分塊網格的復雜算法和并行細節，只暴露簡單的功能接口，基于這些接口可快速構建求解器。SAMR框架的主要功能與特性主要包括：復雜幾何網格生成、網格自適應加密、動態逐層負載均衡、多層分塊數據容器、迭代器與從核迭代器。   

SAMR框架網格切面示意圖   

  功能特性一：網格自動生成   

  根據輸入的幾何模型（目前支持STL格式）文件，本框架可自動生成octree-block網格塊。在此基礎之上，根據octree-block網格塊自動生成block內部網格。根據所采用的邊界模型，可以選擇性地對網格進行體素化，即對網格單元相對封閉幾何表面的內外關系進行標記（對于非封閉幾何（如平板），或者采用浸沒邊界條件，體素化過程并不是必須的）。

  

STL幾何模型

  功能特性二：網格自適應   

  通過選取計算域物理場某個特征量作為加密依據，SAMR框架可以自動根據加密依據加密或粗化網格。例如在流動模擬中，選取速度梯度作為加密依據，速度梯度大則代表流場變化劇烈，通過加密該區域可以更精確解析流場。

跟隨特征的網格自適應示意圖

  功能特性三：動態逐層負載均衡   

  自適應網格的計算負載必然是動態變化的，而SAMR體系上多采用多時間尺度推進算法，因此動態逐層負載均衡是保證效率必備的功能。區別于一般負載均衡策略，逐層特指各加密層級必須都是負載均衡的。下圖中，左圖呈現的是非逐層的負載均衡，右圖呈現的是逐層負載均衡。本框架針對負載均衡功能，采用了優化的任務分割策略和數據傳輸策略，實現了高效的動態負載均衡。

   

一般負載均衡與逐層負載均衡策略的差異

  功能特性四：友好開發接口   

  SAMR框架通過容器化封裝，將網格、場和計算域等數據對象進行了容器化實現，屏蔽了底層復雜的眾核并行與MPI分布式并行相關數據結構和算法。用戶通過使用容器和容器提供的函數式編程接口（函數指針+迭代器），可以在SAMR框架上快速開發所需的物理模型或求解算法。

 

算子定義示意圖

  功能特性五：眾核加速   

  眾核是當前高性能處理器普遍采用的架構體系，SAMR框架設計充分考慮了眾核二級并行加速需求。目前，SAMR框架在典型應用測試中，基于國產神威·太湖之光超級計算機，實現了核心熱點的20倍左右眾核加速。未來，SAMR框架將考慮兼容GPU（CUDA）等其它平臺。  

04 一個應用例子

  為了充分驗證當前框架的功能特性，我們選取了潛艇標模suboff繞流算例進行驗證。該算例主要采用格子Boltzmann方法（LBM），基本調用了框架所有主要功能。   

  算例網格量為2億，并行規模為2000進程，LBM求解器，Re為40000。網格最大層數 為8，自適應間隔 50。2億網格在2000進程下的自動生成過程僅不到十分鐘，初始網格如圖，圖中顯示為網格塊（每個網格塊為10*10*10的網格）。   

初始網格塊   

  模擬結果如下圖所示。可以看到suboff周圍以及尾跡區被有效加密，若使用均勻網格，要達到同等的計算精度，網格量將達到百億級別。目前SAMR框架的功能基本實現，下一步將進行功能完善和性能優化工作。（本文作者：高飛）   

suboff流場局部

參考文獻    

[1] https://zhuanlan.zhihu.com/p/47164365 

[2] Dubey A , Almgren A , Bell J , et al. Asurvey of high level frameworks in block-structured adaptive mesh refinementpackages[J]. Journal of Parallel & Distributed Computing, 2014,74(12):3217-3227.

[3] Schornbaum F , U Rüde. Extreme-ScaleBlock-Structured Adaptive Mesh Refinement[J]. SIAM Journal on ScientificComputing, 2017, 40(3). 

[4] Burstedde C , Wilcox L C , Ghattas O .p4est : Scalable Algorithms for Parallel Adaptive Mesh Refinement on Forests ofOctrees[J]. Siam Journal on Scientific Computing, 2011, 33(3):1103-1133.

[5] https://medium.com/riselab/ai-and-memory-wall-2cb4265cb0b8