Optimizations of ℋ-matrix-vector Multiplication
for Modern Multi-core Processors

Tetsuya Hoshino (Information Technology Center, Nagoya univ., E-mail: hoshino@cc.nagoya-u.ac.jp)

Hierarchical matrices (ℋ-matrices)ℋ-matrix• Approximation method for dense matrices such as the coefficient matrixof the boundary element method (BEM)• Expressed by a set of low-rank approximated and small dense submatrices• Reduce memory O(N2) -> O(N log N)• ℋ-matrix-vector multiplication (HiMV) is important kernel

Dense sub-matrix
Low-rank sub-matrix

 For example, earthquake simulations require >10,000 HiMV executions

Optimizations of HiMV𝒚𝒚• To optimize the HiMV kernel for modern multi-core CPUs, thefollowing optimizations were applied
1. firsttouch: First touch
2. contiguous: Contiguous memory placement bychanging from a tree structure to a onedimensional array
3. avoidAtomic: A reduce algorithm that avoids
atomic operations
4. balancing: Inter-thread load balancing
5. padding: Zero padding for aligned memory access6. blocking: ℋ-matrix Storage for cache blocking
7. sort: Submatrix sorting for efficient cache usage

64 byte aligned(cache line size) H1x8: Humanoid objects lined up in onedimension
 H3x3: Humanoid objects aligned in twodimension
 Sp: Single spherical object (a threedimensional example)
 Di: Two spherical object, such as the Earthand Moon S16: A tetrahedron with 16 objects (fournear each vertex)

Summary

𝑻𝑻𝟏𝟏𝒚𝒚reduce

𝒚𝒚𝟑𝟑

𝒚𝒚𝟒𝟒

𝑻𝑻𝟐𝟐

𝑻𝑻𝟏𝟏=𝒚𝒚𝟓𝟓

𝑻𝑻𝟑𝟑

*𝑻𝑻𝟓𝟓

𝑻𝑻𝟒𝟒=

𝑻𝑻𝟒𝟒

0 padding

𝑻𝑻𝟓𝟓

𝑻𝑻𝟏𝟏

𝑻𝑻𝟐𝟐

𝑻𝑻𝟒𝟒

𝑻𝑻𝟑𝟑

ShapeH3x3-4

Humanoid 1x8

H3x3-6

H3x3-8Humanoid 3x310-610-8176,976*𝑻𝑻𝟓𝟓

Input ℋmatrices
H1x8-8𝒙𝒙

𝑨𝑨𝒚𝒚′ (Shared 1-D array)

𝑻𝑻𝟐𝟐
𝑻𝑻𝟑𝟑

• Evaluated on modern multi-core processor• Evaluated by valuable types of ℋ-matrices
appearing in electrostatic field analysis

𝒙𝒙

𝑨𝑨

𝒚𝒚𝟏𝟏
𝒚𝒚𝟐𝟐
atomicadd

Load imbalance

HiMV applied avoidAtomic and balancing

Experimental results A64FX with HBM2, AMD EPYC Rome, Intel
Xeon CascadeLake

Original HiMV

Sp-8s
Sp-8Single Sphere

Di-8s
Di-8
DipoleSpheres 1610-8
20,000 200,000

10-821,600 160,000

10-8216,000

S16-8ℋ-matrix Accuracy# unknowns

10-8
157,312# low rank sub-mats

129,678

139,588

16,640182,176

17,002

149,426

195,178# dense sub-mats

243,328

288,876

29,480242,976

33,096

248,864

322,800(MAX, AVE) rank
Memory [GB]Memory vs. dense [%](70,21)
4.243
2.143

(34,16)
0.460
14.38

(35,14)
6.791
2.122

(53,17)
0.453
12.14

(52,16)
5.148
2.514

(53,16)
6.491
1.739

10-4(22,8)
3.293
1.314

(44,14)
6.045
2.412

(75,22)
9.695
3.869

Evaluation results on single socket A64FX, Rome, and CascadeLake
WO (A64FX)DGEMV(4 numa)

ES4 (Rome Single Socket)

DGEMV(4 numa)• By applying the series of optimizations,
we obtained the following performance A64FX: 57.9 ~ 84.8% of dgemv
 EPYC Rome: 93.2 ~ 100.7% of dgemv
 CascadeLake: 97.6 ~ 98.7% of dgemv

OBCX (CLX Single Socket)• We found that for A64FX with HBM2,
optimization to increase the efficiency ofcache utilization is important
For more information, please refer to the following paper: T. Hoshino, A.
Ida and T. Hanawa, "Optimizations of H-matrix-vector Multiplication forModern Multi-core Processors," (CLUSTER 2022)

Information Technology Center, Nagoya University
http://www.icts.nagoya-u.ac.jp/en/center/

DGEMV