高性能计算导论 Lab 2

全源最短路 大作业 实验报告

实现方法

实现了实验指导书的三阶段分块全源最短路算法, 并实现了二级分块优化策略:

• 一级分块以 $48$ 为步长, 将 $n\times n$ 大小的矩阵分为 $48\times 48$ 大小的一级块, 每个一级块由一个线程块进行处理, 存储在共享内存中.
• 二级分块以 $3$ 为步长, 将 $48\times 48$ 大小的一级块分为 $3\times 3$ 大小的二级块, 每个二级块由一个线程进行处理, 存储在寄存器中.

kernel1<<<blk1, thr>>>

分配 $1$ 个线程块 blk1, 每个线程块包含 $16\times 16$ 个线程 thr.

设置共享内存存储中心块数据, 在中心块内部执行 Floyd-Warshall 算法:

__shared__ int cen_block[FIRST_BLOCK_LEN][FIRST_BLOCK_LEN];

kernel2<<<blk2, thr>>>

分配 $N\times 2$ 个线程块 blk2, 每个线程块包含 $16\times 16$ 个线程 thr.

设置共享内存存储中心块、十字块数据, 设置局部内存存储二级块数据, 用中心块的结果和十字块中原本的其他结果更新十字块:

__shared__ int cen_block[FIRST_BLOCK_LEN][FIRST_BLOCK_LEN];
__shared__ int cross_block[FIRST_BLOCK_LEN][FIRST_BLOCK_LEN];
           int local_block[SECOND_BLOCK_LEN][SECOND_BLOCK_LEN];

kernel3<<<blk3, thr>>>

分配 $N\times N$ 个线程块 blk3, 每个线程块包含 $16\times 16$ 个线程 thr.

设置共享内存存储十字块、剩余块数据, 设置局部内存存储二级块数据, 用十字块的结果更新剩余的块:

__shared__ int cross_x_block[FIRST_BLOCK_LEN][FIRST_BLOCK_LEN];
__shared__ int cross_y_block[FIRST_BLOCK_LEN][FIRST_BLOCK_LEN];
__shared__ int rest_block[FIRST_BLOCK_LEN][FIRST_BLOCK_LEN];
           int local_block[SECOND_BLOCK_LEN][SECOND_BLOCK_LEN];

运行结果

$n$	1000	2500	5000	7500	10000
apsp_ref.cu	15.416 ms	377.811 ms	2986.876 ms	10051.554 ms	22835.954 ms
apsp.cu	1.400 ms	11.516 ms	77.646 ms	255.279 ms	556.766 ms
加速比	11.01	32.81	38.47	39.37	41.02