矩阵分块乘法的并行实现以及缓存优化
- 0 Collaborators
矩阵乘法的一般形式是C=A*B，使用串行计算的矩阵乘法需要三层循环，操作次数为2*M*N*K。 为了减少矩阵乘法的计算成本，本实验决定对计算结果的矩阵C进行分块，分成大小相同的若干块，这些工作块的计算分别要用到矩阵A和矩阵B的部分行和列。由gpu并行进行工作块的计算，从而达到矩阵分块乘法的并行实现，提高矩阵乘法的效率。 在将矩阵分块计算的时候，读取内存的次数并没有改变，只是利用gpu并行计算将计算时间缩短。因此设置缓存块，在每一块的运算中，将工作块按照缓存块大小分割，单次循环缓存足以计算出缓存块大小的矩阵A和矩阵B的数据，减少迭代次数，从而减少访问内存的次数，实现矩阵分块乘法的缓存优化。 ...learn more
Project status: Under Development
Overview / Usage
矩阵乘法（Matrix Multiplication）的一般形式是C=A*B，A，B，C三个矩阵的维度分别为M*K，K*N，M*N，且三个矩阵中的数据都是单精度浮点数。使用串行计算的矩阵乘法操作次数为2*M*N*K当矩阵的M，N，K较大时，就会导致矩阵乘法串行计算的操作次数和读取内存次数急剧增大，最终计算耗时巨大。
为了提高矩阵乘法的效率，本次实验决定将计算结果的矩阵C分块，由gpu并行进行每个工作块的计算，从而实现对矩阵乘法效率的提高。
并且通过改变读取数据的方式，减少对内存的访问次数，从而减少访问耗时，提高矩阵乘法效率。
Methodology / Approach
该项目的核心是使用DPC++实现矩阵乘法的并行算法，并完成算法的缓存优化 。
矩阵乘法的一般形式是C=A*B，A，B，C三个矩阵的维度分别为M*K，K*N，M*N。矩阵乘法的串行计算主要实现内容为三层循环。外两层层循环为对矩阵A的行和矩阵B的列的循环遍历，第三层循环是对矩阵A的行和矩阵B的列中的K个元素的循环遍历。在三层循环内再进行矩阵A的行和矩阵B的列中K个元素的相乘和相加，最终操作次数为2MNK。
实现矩阵乘法的效率提高的主要核心就是并行式计算。矩阵分块乘法的主要原理就是将结果矩阵C按照block的大小分为多个工作块，每一个工作块的结果计算是相互独立的，只需要从矩阵A和矩阵B中获取相应数据计算即可计算出，不会相互影响结果，因此可以使用gpu进行多个工作块的并行计算，从而实现矩阵分块乘法的并行计算，提高矩阵乘法的效率，减小耗时。
在矩阵分块并行计算的基础上，需要优化该算法访问缓存的次数，置缓存块用于划分矩阵C，每一个工作块的计算单次循环需要缓存计算一个缓存块所需的所有数据，从而减少对矩阵A和矩阵B的遍历次数，减少内存访问的次数，达到缓存优化的效果，从而提高矩阵分块乘法并行计算的效率。
Technologies Used
Intel OneAPI