基于位运算Hilbert曲线的DGTD方法缓存优化策略研究

      A Hilbert Curve-Based Cache Optimization Strategy for the DGTD Method

      • 摘要: 时域间断伽辽金方法(DGTD)在电磁仿真问题中具有很强的几何适应能力和并行计算能力。对于大规模非结构四面体网格,在离散的内存地址中进行物理空间的邻近关系计算会导致求解过程中出现大量非连续访存行为,特别是在时间步进计算过程中,缓存未命中的频繁发生限制了求解器的计算效率。针对上述问题,本文提出了一种基于位运算的Hilbert曲线高效单元重排方法。该方法通过有限状态机与位运算相结合的方式快速计算空间状态编码,得到Hilbert曲线一维连续线性索引,用来重构单元和节点的数据存储布局,使数据组织方式能够更好地匹配DGTD计算过程中局部通量交换及单元积分所对应的访存特征。数值实验结果表明,该方法仅需较小的前处理开销就能改善数据访问模式,有效减少主存访问次数。实验表明,重排后的数据布局增强了内存空间局部性,在不影响计算精度的前提下,求解器整体运行效率获得了显著提升。

         

        Abstract: The discontinuous Galerkin time-domain (DGTD) method exhibits great geometric adaptability and parallel computing capability for electromagnetic simulations involving complex structures. For large-scale unstructured tetrahedral meshes, the evaluation of spatial adjacency relationships over discretely allocated memory addresses leads to extensive non-contiguous memory accesses during the solution process. This issue becomes particularly pronounced in time-marching computations, where frequent cache misses significantly constrain solver performance. To address this problem, a high-efficiency Hilbert-curve-based element reordering method utilizing bitwise operations is proposed. By combining a finite-state machine with bitwise manipulation, the proposed approach rapidly generates spatial state codes and constructs one-dimensional continuous Hilbert indices. These indices are then employed to reorganize the storage layouts of elements and nodes, enabling the data arrangement to better match the memory access characteristics associated with local flux exchanges and element integrations in DGTD computations. Numerical results demonstrate that the proposed method improves data access patterns with only a small preprocessing overhead and effectively reduces accesses to main memory. The reordered data layout enhances spatial memory locality and yields a significant improvement in overall solver efficiency without compromising computational accuracy.

         

      /

      返回文章
      返回