應用於加速晶圓等級多工處理器運算有限元素法之切割與擺置演算法

A Partitioning and Placement Framework for Accelerating the Finite Element Method with Wafer-scale Multiprocessors

黃禹靖(Yu-Ching Huang)

指導教授 ： 張耀文

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202200156

摘要

以有限元素法（the finite element method）迅速地執行大規模的工程模型可以帶來許多應用。在本篇論文中，為了提高有限元素法的運算效率，我們提出一個切割與擺置架構將有限元素法運算工作量對應至目前最大的單片（monolithic）晶片—晶元等級引擎（the wafer-scale engine）。我們的演算法架構由三個主要階段組成：（1）一個精準評估熱圖（heat map）與運算資源量的剖析方法、（2）一個最大化計算資源運用量同時最佳地利用晶元等級引擎平行化能力的切割搜尋演算法與切割策略、與（3）一個有效且快速地將已切割的有限元素法之運算工作量擺至晶元等級引擎的演算法。與2021國際積體電路實體設計會議（International Symposium on Physical Design）：晶元等級物理模型競賽的所有參加隊伍相比，我們提出的演算法達到最高的整體分數。

關鍵字

有限元素法 ； 晶元等級多工處理器 ； 區域分解 ； 超大型積體電路擺置

並列摘要

Fast execution of the finite element method (FEM) for large-scale engineering models facilitates numerous applications. This thesis presents a partitioning and placement framework to map FEM workloads onto the currently largest monolithic chip, called the wafer-scale engine (WSE), to boost the efficiency of the FEM. Our framework consists of three major stages: (1) a profiling method to accurately evaluate heat maps and computation resources, (2) a partition-searching algorithm with a partitioning scheme to maximize the computation resource usage and to exploit the WSE parallelism simultaneously, and (3) a placement algorithm to place the partitioned FEM workloads onto the WSE effectively and efficiently. Our algorithm achieves the best overall score compared with the participating teams of the ISPD 2021 Wafer-Scale Physics Modeling Contest.

並列關鍵字

Finite Element Method ； Wafer-scale Multiprocessor ； Domain Decomposition ； VLSI Placement

參考文獻

[1] The cerebras wafer-scale engine. [Online]. Available: https://cerebras.net

[2] M. Al-Nasra and D. Nguyen, “An algorithm for domain decomposition in finite element analysis,” Computers Structures, vol. 39, no. 3-4, pp. 277–289, 1991.

[3] N. Bell and M. Garland, “Efficient sparse matrix-vector multiplication on CUDA,” Citeseer, Tech. Rep., 2008.

[4] T. Belytschko, E. J. Plaskacz, J. M. Kennedy, and D. L. Greenwell, “Finite element analysis on the connection machine,” Computer Methods in Applied Mechanics and Engineering, vol. 81, no. 2, pp. 229–254, 1990.

[5] C. Cecka, A. J. Lew, and E. Darve, “Assembly of finite element methods on graphics processors,” International Journal for Numerical Methods in Engineering, vol. 85, no. 5, pp. 640–669, 2011.